4 ms·

Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). I'm not

Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.

sounds 12y ago
In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul http://www.aldeid.com/wiki/X86-assembly/Instructions/mul Checking for overflow is just a matter of testing if the high-order bits are zero.
- stormbrew 12y ago
  Yep, in assembly it's usually no question possible. That's why I specified portable C. C has some interesting gaps for something that's long been described as a macro for assembly. A rotate operator would also be nice.
- pbsd 12y ago
  The correct thing to do is also to check the carry and overflow flags after (I)MUL, which does the right thing even when only the lower bits of the multiplication are saved. Here's an example where there is overflow, but your suggestion would not catch it: mov eax, 0x7fffffff mov ecx, 2 imul ecx ; edx:eax = eax * ecx ; edx = 0 ; eax = 0xfffffffe ; overflow flag = 1 There is signed overflow here, but testing edx (the higher word of the result) would not catch it.
  - sounds 12y ago
    Yes. I decided not to mention IMUL to keep the post simple. There are also issues with detecting overflow of SSE multiplies (signed and unsigned).
jcalvinowens 12y ago
> Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). Yeah, you're absolutely right. > I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea. I've never tried to implement this, but couldn't you look at the position of the most significant bit in the multiplicands to guess if the multiply will overflow? You'd have to be okay with false positives I suppose? Naively it would be slow, but if you have a hardware CLZ instruction it could be pretty fast. I did find this on SO: x = a * b; if (a != 0 && x / a != b) { // overflow handling } That makes sense, but of course it would be HORRENDOUSLY expensive. If you're willing to not be non-portable, you could just do expanding multiplies and check the high word: struct exmulres { unsigned long hi; unsigned long lo; }; static inline __attribute__((always_inline)) struct exmulres do_one_expanding_multiply(unsigned long a, unsigned long b) { struct exmulres res; #if defined(__x86_64__) asm ("movq %0,%%rax; mulq %1; movq %%rdx,%1; movq %%rax,%0" : "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%rax","%rdx"); #elif defined(__i386__) asm ("movl %0,%%eax; mull %1; movl %%edx,%1; movl %%eax,%0" : "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%eax","%edx"); #elif defined(__arm__) asm ("umull %0,%1,%2,%3" : "=r" (res.lo), "=r" (res.hi) : "r" (a), "r" (b) :); #else #error "No expanding multiply assembly has been written for your architecture" #endif return res; } It probably wouldn't be very difficult to fill that out for all the CPU architectures Linux supports, which would cover all your bases unless you're doing super embedded stuff. EDIT: Typo
- stormbrew 12y ago
  Yeah that div check works I guess, but as you say is horribly expensive. For the latter it looks like at least on recent versions of gcc, you can do something like (WARNING: Just a vague proof of concept, please don't use it. It might kill kittens): uint64_t func(uint64_t a, uint64_t b) { unsigned __int128 res = (unsigned __int128)a * (unsigned __int128)b; if (res >> 64) { asm volatile ("nop;" ::); /* handle here */ } return (uint64_t)res; } Which compiles to this in gcc -Os and -O3: 0: 48 89 f8 mov %rdi,%rax 3: 48 f7 e6 mul %rsi 6: 48 85 d2 test %rdx,%rdx 9: 74 01 je c <func+0xc> b: 90 nop c: f3 c3 repz retq Which I'm pretty sure could be optimized further by using the overflow flag, but the compiler doesn't seem to want to ignore the upper word. edit: and it probably suffers the same problem as described here: https://news.ycombinator.com/item?id=7848771 https://news.ycombinator.com/item?id=7848771 -- and also probably has general issues with signedness that would need to be further checked. edit2: changed it to uints to simplify and avoid a whole class of problem. I still don't think you should go use this, though. (inspiration from SO: http://stackoverflow.com/a/13187798 http://stackoverflow.com/a/13187798)
xenonflash 12y ago
He also picked one of the most trivial cases - unsigned addition. Signed data, especially signed multiplication, requires a lot more steps. I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary duplication of computational effort. However, that is a lot of work and has the potential for hidden programmer introduced errors. The real problem is that languages like C simply don't allow you to take advantage of hardware which already exists in the CPU without writing in-line assembler. A standard set of "checked" math macros which handled the portability issues would probably satisfy most C applications. Edit: For addition, subtraction, and multiplication, you just take one operand, calculate the largest possible second operand for that data type which won't overflow, and check that the actual second operand doesn't exceed it (remembering to take signs into account). For division and modulus, check for division by zero. For multiplication, division, modulus, negation, and absolute value of signed values, check that you are not negating the maximum negative integer, as integer ranges are not symmetrical (e.g. one byte is -128 to +127). If you are looping over arrays and have multiple checks for different cases (e.g. negative, positive, etc.), then you can have different loops for different cases and so avoid redundant checks for that data. I'm working on this sort of application, so the above works out best for that. If you're doing something a bit different, then different algorithms may make sense. Unfortunately, there's not universal one-size-fits-all solution to this problem in software.
- stormbrew 12y ago
  It's surprising there aren't at least intrinsics for some of these things in GCC/clang. At least as far as I can tell.
  - Someone 12y ago
    http://clang.llvm.org/docs/LanguageExtensions.html#builtin-functions http://clang.llvm.org/docs/LanguageExtensions.html#builtin-f..., the search for "Checked Arithmetic Builtins"
Someone 12y ago
A smarter way is to split both numbers to multiply into two halves, and pretend to do two-word arithmetic on a machine with words half the size. In decimal, that means that you compute the product of two-digit numbers using single-digit multiplications and shifts (= multiplications by 10): 23 x 67 = (20+3) x (60+7) = (2x3) x 100 + (2x6) x 10 + (3x7) x 10 + 3x7
maxlybbert 12y ago
There are better checks. I'm generally not a fan of Microsoft, but the SafeInt library ( https://safeint.codeplex.com/ https://safeint.codeplex.com/ ) does those kinds of checks in sofware. I don't remember where I read it, but regarding multiplication: if you multiply two N-bit numbers together, the result will always fit in a 2N-bit number. For instance, the product of two 16 bit numbers will fit in 32 bits, the product of two 32 bit numbers will fit in 64 bits, etc. You can assign the product to an integer able to hold the larger size and then check if it would also fit in an integer of the smaller size.

sounds 12y ago

In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul http://www.aldeid.com/wiki/X86-assembly/Instructions/mul Checking for overflow is just a matter of testing if the high-order bits are zero.

stormbrew 12y ago
Yep, in assembly it's usually no question possible. That's why I specified portable C. C has some interesting gaps for something that's long been described as a macro for assembly. A rotate operator would also be nice.
pbsd 12y ago
The correct thing to do is also to check the carry and overflow flags after (I)MUL, which does the right thing even when only the lower bits of the multiplication are saved. Here's an example where there is overflow, but your suggestion would not catch it: mov eax, 0x7fffffff mov ecx, 2 imul ecx ; edx:eax = eax * ecx ; edx = 0 ; eax = 0xfffffffe ; overflow flag = 1 There is signed overflow here, but testing edx (the higher word of the result) would not catch it.
- sounds 12y ago
  Yes. I decided not to mention IMUL to keep the post simple. There are also issues with detecting overflow of SSE multiplies (signed and unsigned).

jcalvinowens 12y ago

> Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). Yeah, you're absolutely right. > I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea. I've never tried to implement this, but couldn't you look at the position of the most significant bit in the multiplicands to guess if the multiply will overflow? You'd have to be okay with false positives I suppose? Naively it would be slow, but if you have a hardware CLZ instruction it could be pretty fast. I did find this on SO: x = a * b; if (a != 0 && x / a != b) { // overflow handling } That makes sense, but of course it would be HORRENDOUSLY expensive. If you're willing to not be non-portable, you could just do expanding multiplies and check the high word: struct exmulres { unsigned long hi; unsigned long lo; }; static inline __attribute__((always_inline)) struct exmulres do_one_expanding_multiply(unsigned long a, unsigned long b) { struct exmulres res; #if defined(__x86_64__) asm ("movq %0,%%rax; mulq %1; movq %%rdx,%1; movq %%rax,%0" : "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%rax","%rdx"); #elif defined(__i386__) asm ("movl %0,%%eax; mull %1; movl %%edx,%1; movl %%eax,%0" : "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%eax","%edx"); #elif defined(__arm__) asm ("umull %0,%1,%2,%3" : "=r" (res.lo), "=r" (res.hi) : "r" (a), "r" (b) :); #else #error "No expanding multiply assembly has been written for your architecture" #endif return res; } It probably wouldn't be very difficult to fill that out for all the CPU architectures Linux supports, which would cover all your bases unless you're doing super embedded stuff. EDIT: Typo

stormbrew 12y ago
Yeah that div check works I guess, but as you say is horribly expensive. For the latter it looks like at least on recent versions of gcc, you can do something like (WARNING: Just a vague proof of concept, please don't use it. It might kill kittens): uint64_t func(uint64_t a, uint64_t b) { unsigned __int128 res = (unsigned __int128)a * (unsigned __int128)b; if (res >> 64) { asm volatile ("nop;" ::); /* handle here */ } return (uint64_t)res; } Which compiles to this in gcc -Os and -O3: 0: 48 89 f8 mov %rdi,%rax 3: 48 f7 e6 mul %rsi 6: 48 85 d2 test %rdx,%rdx 9: 74 01 je c <func+0xc> b: 90 nop c: f3 c3 repz retq Which I'm pretty sure could be optimized further by using the overflow flag, but the compiler doesn't seem to want to ignore the upper word. edit: and it probably suffers the same problem as described here: https://news.ycombinator.com/item?id=7848771 https://news.ycombinator.com/item?id=7848771 -- and also probably has general issues with signedness that would need to be further checked. edit2: changed it to uints to simplify and avoid a whole class of problem. I still don't think you should go use this, though. (inspiration from SO: http://stackoverflow.com/a/13187798 http://stackoverflow.com/a/13187798)

xenonflash 12y ago

He also picked one of the most trivial cases - unsigned addition. Signed data, especially signed multiplication, requires a lot more steps. I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary duplication of computational effort. However, that is a lot of work and has the potential for hidden programmer introduced errors. The real problem is that languages like C simply don't allow you to take advantage of hardware which already exists in the CPU without writing in-line assembler. A standard set of "checked" math macros which handled the portability issues would probably satisfy most C applications. Edit: For addition, subtraction, and multiplication, you just take one operand, calculate the largest possible second operand for that data type which won't overflow, and check that the actual second operand doesn't exceed it (remembering to take signs into account). For division and modulus, check for division by zero. For multiplication, division, modulus, negation, and absolute value of signed values, check that you are not negating the maximum negative integer, as integer ranges are not symmetrical (e.g. one byte is -128 to +127). If you are looping over arrays and have multiple checks for different cases (e.g. negative, positive, etc.), then you can have different loops for different cases and so avoid redundant checks for that data. I'm working on this sort of application, so the above works out best for that. If you're doing something a bit different, then different algorithms may make sense. Unfortunately, there's not universal one-size-fits-all solution to this problem in software.

stormbrew 12y ago
It's surprising there aren't at least intrinsics for some of these things in GCC/clang. At least as far as I can tell.
- Someone 12y ago
  http://clang.llvm.org/docs/LanguageExtensions.html#builtin-functions http://clang.llvm.org/docs/LanguageExtensions.html#builtin-f..., the search for "Checked Arithmetic Builtins"

Someone 12y ago

A smarter way is to split both numbers to multiply into two halves, and pretend to do two-word arithmetic on a machine with words half the size. In decimal, that means that you compute the product of two-digit numbers using single-digit multiplications and shifts (= multiplications by 10): 23 x 67 = (20+3) x (60+7) = (2x3) x 100 + (2x6) x 10 + (3x7) x 10 + 3x7

maxlybbert 12y ago

There are better checks. I'm generally not a fan of Microsoft, but the SafeInt library ( https://safeint.codeplex.com/ https://safeint.codeplex.com/ ) does those kinds of checks in sofware. I don't remember where I read it, but regarding multiplication: if you multiply two N-bit numbers together, the result will always fit in a 2N-bit number. For instance, the product of two 16 bit numbers will fit in 32 bits, the product of two 32 bit numbers will fit in 64 bits, etc. You can assign the product to an integer able to hold the larger size and then check if it would also fit in an integer of the smaller size.