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). Yeah,
by 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 agoYeah 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)
- danbruc 12y agoLooking 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 https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c
- stormbrew 12y agoFor 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#L151 https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c#...