Perfect Prevention of Int Overflows

May 17, 2014

C++ Trivia Question: Given int x which of the following is true?

x < (int)(float)x
x == (int)(float)x
x > (int)(float)x

I’ll give you a moment to think. Both int and float types are 32 bits. Proceed when ready.

The correct answer is… All of the above and then some. It can also cause an integer overflow which is an undefined operation. How delightful. Thanks C++!

Real World Bug

The inspiration for this post came from an actual bug in Planetary Annihilation. Here’s what that situation looked like.

float rate = ...; // may be very small 
float amount = ...; // may be relatively large 
float seconds_left = amount / rate; // may be VERY large 
int ms_left = secondsToMilliseconds(seconds_left); // DANGER!
int end_time = current_time + ms_left; // DANGER: may overflow

The context is a fabber unit constructing a building. It’s building at some rate. There is some amount left to build. It calculates the build time left in seconds as a float. That value is converted from float seconds to int milliseconds. That value is added to the current build time to store the exact time the building will be complete.

Seems reasonable. 2^31 milliseconds gives you 24.86 days of uniform time which almost always enough1. Almost.

In some rare cases it worked out that a fabber’s build rate was so small (for a single tick) it wouldn’t finish construction for 25+ days. The integer overflowed and the game crashed itself shortly thereafter due to bad data. Kaboom!

Fixing the Bug

There are a few places this bug could be fixed.

My issue with these is the vagueness of ‘sufficiently’. We could ballpark it.

if (rate < .0001f) {...}  
if (seconds_left > 1073741824.f) {...}  
if (2147483647 - current_time >= ms_left) {...}

Gross. That’s hand wavey magic number crap. It’s not even good magic number crap either. It’d maybe possibly fix the bug in some cases but not all. I know we can do better.

Perfect Prevention

This led me to a question. Is it possible to perfectly predict which floats will overflow when converted to an int?

A 32-bit signed integer supports values from -2^31 to 2^31–1. Any float values outside of that range will obviously not convert.

Also of interest is that that every integer can not be perfectly represented by a float. The further away from 0 a float gets the less precision it has. Here’s a handy dandy chart2.

Floats Chart

Source: Bruce Dawson

This chart tells us a few things. Given the floating point number 1000000000.f (one billion) the next float is 1000000064.f (one billion sixty four). There are no 32-bit floating point numbers in between. You can’t represent “one billion and one” or “one billion and fifty” exactly.

Now is when things start to get fun. The largest int is 2147483647 (2^31–1). If you convert that int to a float it rounds up to 2147483650.0f. If you cast that back to an int you get an overflow!

int x = (int)(float)2147483647; // OVERFLOW!

Other integers may round down when cast to float. Only some can be perfectly represented2. That’s why the answer to the trivia question was all of the above and more.

Finding the Limits

Now that our trivia question is sufficiently answered it’s time to fix that damn bug. What floats, exactly, are safe to cast to an int.

Solving empirically, the largest integer that can be exactly represented as a float is 2147483520 aka 2^31–128. The next floating point number after that is 2147483648f aka 2^31 which is just beyond the maximum int value of 2^31–13.

Putting It All Together

What’s the final product look like? First, the float to int overflow.

bool float_to_int_safe(float f) { 
    const float max_safe = 2147483520.f; // 2^31 - 128 
    const float low_safe = -2147483648.f; // -2^31 
    return std::isfinite(f) && f >= low_safe && f <= max_safe; 
}

Second, the int plus int overflow. I’ll leave understanding the details of this as an exercise for the reader.

bool int_add_safe(int a, int b) { 
    if (a >= 0 && b >= 0) 
        return INT_MAX - a >= b; 
    if (a < 0 && b < 0)
        return INT_MIN - a <= b;
    return true;
}

Tada! For the Planetary Annihilation bug the solution is to behave as if the rate is zero if the any of the operations would cause an overflow. It's like an epsilon check, but a really really precise one!

To be honest I'm not comfortable calling these functions "perfectly correct". The nuance required to get floating point operations perfectly correct is exceptional. I'm sure I missed something but I do not know what. If you spot something please let me know in the comments3.

Edit: After making this post someone immediately pointed out a bug. The original version of int_add_safe had the line const int min = 0x80000000;. That innocuous line is undefined behavior! The goal is end up with an int with that bit pattern. However that literal is an unsigned int of value 2^31!

The correct thing to do here is use INT_MIN which appears in limits.h as #define INT_MIN (-2147483647 - 1). This goes to show that getting everything right is more than a little tricky4.

Bonus Fun

Here are three inequalities that I find wonderfully weird.

(int_max - 190) < (int)(float)(int_max - 190)  
(int_max - 127) == (int)(float)(int_max - 127)
(int_max - 64) > (int)(float)(int_max - 64)

It gets even better. What holds true depends on dynamic floating point round controls! A single int converted to float may round up or down based on FPU settings.

This also means that a particular integer may or may not overflow when cast to a float and back. It all depends5!

Again I say, thanks C++!

Nasal Demons

There's an important bit about undefined operations that I want to explicitly call out. It is absolutely mandatory that undefined operations be prevented before they occur. It is not enough to detect the operation after it happens.

To emphasis this point let me share with you one of my most favorite definitions.

nasal demons: noun.

When the compiler encounters an undefined operation it is legal for it to make demons fly out of your nose.

— John F. Woods

The compiler could even format your hard drive if it wanted to. Suffice to say that undefined operations, such as integer overflows, are a very bad thing.

Conclusions

Undefined operations are catastrophic and floats are deceptively nasty. The fact that int->float->int->overflow can happen is remarkably counter-intuitive. Be careful out there!

Footnotes

  1. For details on why integer milliseconds are used see this post.
  2. The first integer that can NOT be perfectly represented as a float is 16,777,217 aka 2^24+1.
  3. Be gentle!
  4. Having such a bug is painfully ironic and very embarrassing. I’m leaving the edit text to further demonstrate how insane all of this is. Hopefully my shame can be a learning tool for others.
  5. Not that I would recommend casting numbers like that, of course.