Is this a bad pointer bug?

[Joe Buck]

On Fri, Jul 18, 2003 at 10:21:09AM -0400, Daniel Jacobowitz wrote:
> On Fri, Jul 18, 2003 at 07:12:13AM -0700, H. J. Lu wrote:
[ artificial pointer-subtraction example ]
> > What does C standard say on this?
> 
> That there's no bug.
> 
>        [#9]  When  two pointers are subtracted, both shall point to
>        elements of the same array object,  or  one  past  the  last
>        element of the array object; the result is the difference of
>        the subscripts of the two array elements.

GCC contains some clever number theory to avoid division operations in
cases like this: it must compute the address difference and divide it
by sizeof(struct foo).  If it is known b divides a evenly, it's possible
to compute a/b mod N with a multiplication and shift operations instead.
Here N is 2**32 on a 32-bit machine.  Consider the case where b is odd.
Then there is some number inv_b such that (inv_b * b) mod N is 1.  In
that case, (a/b) mod N is equal to (a*inv_b) mod N.  If b is even,
and it evenly divides a, then we apply enough right shifts to a and b
to get an odd denominator.

So, if the size of the struct is 44, we need to compute (diff/44) mod
2**32 on a 32-bit machine.  The first operation is a shift by two, so
we compute (diff_shift/11) mod 2**32.  We compute the inverse of 11
at compile time, giving a constant C such that C*11 mod 32 is 1.  It
turns out that C is 3123612579.  So the pointer subtraction code
has a shift-right by two and then an unsigned multiplication by C.

A consequence is that for invalid pointer subtractions (where the difference
is not a multiple of sizeof(T)) gcc will return nonsense, as it is allowed
to do.

the emitted 

 
> 
> -- 
> Daniel Jacobowitz
> MontaVista Software                         Debian GNU/Linux Developer

-- 
Q. What's more of a headache than a bug in a compiler.
A. Bugs in six compilers.  -- Mark Johnson