From: Seebs Date: 2009-09-15T06:40:11+09:00 Subject: Re: Overflow behavior On 2009-09-14, Markus Roberts wrote: > I haven't looked at it in several years, but at one time I was pretty > deep in that code and my recollection is that it's solid. Can you > explain your misgivings in more detail (e.g. outline a hypothetical > failure mode, even if you can't produce a concrete example)? I'm not sure I can. The first thing to keep in mind: Overflow in signed integers is pure undefined behavior, so we don't have any guarantee that we get exactly the expected results. This is my big misgiving; I don't necessarily expect any consistent behavior on overflow. (We only have a promise of modulos-N overflow for *unsigned* integers.) Quick review: #define INT2FIX(i) ((VALUE)(((long)(i))<<1 | FIXNUM_FLAG)) #define LONG2FIX(i) INT2FIX(i) #define FIX2LONG(x) RSHIFT((long)x,1) So, the value 0x03 represents the long value 1, and the value 3 would become the fix value 0x7. long a, b, c; VALUE r; a = FIX2LONG(x); if (a == 0) return x; b = FIX2LONG(y); c = a * b; r = LONG2FIX(c); if (FIX2LONG(r) != c || c/a != b) { r = rb_big_mul(rb_int2big(a), rb_int2big(b)); } return r; Hmm. I guess the likely boundary cases would be near 2^(n/2) or thereabouts. If a and b are both 2^16, c will be 2^32, which we suspect comes out 0, so we trip the c/a != b. Hmm. I think this is going to work, because the /a will produce 0 in most overflow cases. In particular, it can't actually produce b, because if c/a == b, then b had no higher bits than those that survived the multiplication. Well, let's see. Imagine that c is 2^30. The creation of r is undefined behavior, because E1*2 is not representable in the result type. On most systems, we'll end up with r being -(2^31)+1 (0x80000001). When we calculate FIX2LONG(r), we will get either 0xc0000000 or 0x40000000, probably -- it's implementation-defined. So 2^30 would become a bignum, which I guess is probably intentional, since it's out of the effective range of a 31-bit integer. In terms of strict C conformance, then, the code is not safe -- it invokes undefined behavior at least twice for some plausible input values. I'm pretty sure that on most current CPUs, it'll do what is intended. I also don't know what the desired behavior would be for FIX2LONG(LONG2FIX()) on 2^30; I am pretty sure that there exist both systems which zero-fill and systems which sign-extend on right shift. -s -- Copyright 2009, all wrongs reversed. Peter Seebach / usenet-nospam@seebs.net http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!