[ODE] dRandInt Crash Fix

[Adam D. Moss]

Jaroslav Sinecky wrote:
> I think there was someone on the list saying that he modified dRandInt to
> use only integer aritmetics and worked fine even with quite a gain in
> performance
> ... oh yes, I found it: http://q12.org/pipermail/ode/2005-May/015834.html

Put into ODE parlance and tweaked a bit, this simply reduces to
something like:

int dRandInt (int n)
{
   const unsigned long r = dRand();
   return ((r>>12)*n)>>20;
}

... which is basically the double-using algorithm converted to
fixed-point.  However, that's just not accurate enough -- try
it with n=5000 for example; it'll leave swathes of the range
untouched.  That's not incorrect behaviour per se, but QuickStep's
solution quality actually relies on dRandInt() not totally sucking.

For an all-int solution, I think it's better to xor-fold
dRand()'s output until we don't feel so bad taking the modulus.

Something like:

int dRandInt (unsigned long un)
{
   unsigned long r = dRand();

   /* probably more aggressive xor-folding than necessary, but...*/
   if (un <= 0x00010000UL) {
     r ^= (r >> 16);
     if (un <= 0x00000100UL) {
       r ^= (r >> 8);
       if (un <= 0x00000010UL) {
         r ^= (r >> 4);
         if (un <= 0x00000004UL) {
           r ^= (r >> 2);
           if (un <= 0x00000002UL) {
             r ^= (r >> 1);
           }
         }
       }
     }
   }

   return (int) (r % un);
}


--adam
-- 
Adam D. Moss   -   adam at gimp.org