3 ms·

I wrote a very similar article about how testing for integer overflow is also harder than it looks: http://blog.reverberate.org/2012/12/testing-for-integer-over

I wrote a very similar article about how testing for integer overflow is also harder than it looks: http://blog.reverberate.org/2012/12/testing-for-integer-overflow-in-c-and-c.html http://blog.reverberate.org/2012/12/testing-for-integer-over...

mjewkes 14y ago
Its pretty easy to be sunk by floats: http://twistedoakstudios.com/blog/Post3044_my-bug-my-bad-2-sunk-by-float http://twistedoakstudios.com/blog/Post3044_my-bug-my-bad-2-s...
cjh_ 14y ago
Well written article. One of the things I found amazing about learning assembly was that in x86 asm it is relatively trivial to check for overflow (after an operation has happened) by checking if the overflow flag [1] is set. Although this doesn't help with detecting if overflow will occur from an operation, it can be used to detect when it has occurred and assist recovery. [1] http://en.wikipedia.org/wiki/Overflow_flag http://en.wikipedia.org/wiki/Overflow_flag
- haberman 14y ago
  Thanks! Yes I am also impressed by how relatively easy this is to implement at the machine level. One thing I meant to do for that article but didn't get to is implement each of those algorithms in assembly directly and see if the C/C++ solution would compile into the optimal machine code (or something equally efficient). In assembly you have the luxury of no undefined or implementation-defined behavior. This makes things a lot easier, since you can count on things like two's complement. In assembly these checks are probably as easy as (untested): will_u64_overflow_u32: ; If any of the high 32 bits are set. shr rdi, 32 setne al ret will_u64_overflow_i32: ; If any of the high 33 bits are set. shr rdi, 33 setne al ret will_i64_overflow_i32 ; If the high 32 bits are other than all 0 or all 1. shr rdi, 32 add edi, 1 cmp edi, 1 seta al ret I'm not sure if these are exactly right, but I think the right answers are about this simple. Any of these could also be written simply in C/C++ also, the main difference is just that in assembly you can make machine-specific assumptions (like two's complement) since you're already doing something machine-specific.
  - pbsd 14y ago
    The shift in the second one should be 31, if I understand what you're doing correctly. The third one is incorrect. Consider, for example, the integer 0xFFFFFFFF00000001, which is -4294967295 in 2's complement. It passes your test, but is not representable as a 32-bit signed integer. An alternative might be: movsxd rax, edi ; signextend(rdi mod 2^32) == rdi cmp rax, rdi setz al ret
    - haberman 14y ago
      Brilliant, I love it. Thanks for the corrections.
peripetylabs 14y ago
I'm glad the subject is being studied, it's a very interesting problem. Proper solutions are much more sophisticated than it seems. You have to ensure that the checks you use in the checker functions don't themselves cause overflows. If you're interested, I'll write about an algorithm for your WillOverflow function which has been proved correct.

mjewkes 14y ago

Its pretty easy to be sunk by floats: http://twistedoakstudios.com/blog/Post3044_my-bug-my-bad-2-sunk-by-float http://twistedoakstudios.com/blog/Post3044_my-bug-my-bad-2-s...

cjh_ 14y ago

Well written article. One of the things I found amazing about learning assembly was that in x86 asm it is relatively trivial to check for overflow (after an operation has happened) by checking if the overflow flag [1] is set. Although this doesn't help with detecting if overflow will occur from an operation, it can be used to detect when it has occurred and assist recovery. [1] http://en.wikipedia.org/wiki/Overflow_flag http://en.wikipedia.org/wiki/Overflow_flag

haberman 14y ago
Thanks! Yes I am also impressed by how relatively easy this is to implement at the machine level. One thing I meant to do for that article but didn't get to is implement each of those algorithms in assembly directly and see if the C/C++ solution would compile into the optimal machine code (or something equally efficient). In assembly you have the luxury of no undefined or implementation-defined behavior. This makes things a lot easier, since you can count on things like two's complement. In assembly these checks are probably as easy as (untested): will_u64_overflow_u32: ; If any of the high 32 bits are set. shr rdi, 32 setne al ret will_u64_overflow_i32: ; If any of the high 33 bits are set. shr rdi, 33 setne al ret will_i64_overflow_i32 ; If the high 32 bits are other than all 0 or all 1. shr rdi, 32 add edi, 1 cmp edi, 1 seta al ret I'm not sure if these are exactly right, but I think the right answers are about this simple. Any of these could also be written simply in C/C++ also, the main difference is just that in assembly you can make machine-specific assumptions (like two's complement) since you're already doing something machine-specific.
- pbsd 14y ago
  The shift in the second one should be 31, if I understand what you're doing correctly. The third one is incorrect. Consider, for example, the integer 0xFFFFFFFF00000001, which is -4294967295 in 2's complement. It passes your test, but is not representable as a 32-bit signed integer. An alternative might be: movsxd rax, edi ; signextend(rdi mod 2^32) == rdi cmp rax, rdi setz al ret
  - haberman 14y ago
    Brilliant, I love it. Thanks for the corrections.

peripetylabs 14y ago

I'm glad the subject is being studied, it's a very interesting problem. Proper solutions are much more sophisticated than it seems. You have to ensure that the checks you use in the checker functions don't themselves cause overflows. If you're interested, I'll write about an algorithm for your WillOverflow function which has been proved correct.