Re:We Need Hardware Traps for Integer Overflow
by stormbrew on Wednesday June 04, 2014 @06:27PM
(#7848816)
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 -- 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)
Re:We Need Hardware Traps for Integer Overflow
by danbruc on Wednesday June 04, 2014 @06:56PM
(#7848969)
Looking at the GCC source [1] starting at line 150 this is almost what GCC actually does - perform the multiplication with twice the operand size and then check by shifting right but GCC compares the result of two shift operations differing by one in the shift amount.
[1] https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c
Re:We Need Hardware Traps for Integer Overflow
by stormbrew on Wednesday June 04, 2014 @06:58PM
(#7848986)
For future reference, you can link to a specific line in github with #LNNN. Which you can get by clicking on the line number. Pretty handy.
https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c#...
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:
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:
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