[cairo] Patch: speeding up _cairo_fixed_from_double

[Bill Spitzak]

I also posted the same thing some time ago, not sure what happened to 
that as I never got any response. My code uses the exact same trick (and 
I'm sure shares the same original source). The only difference is that I 
also made a fast test to see if the conversion is out of range that may 
be useful. In our software using similar code to replace float->int the 
speedup is considerable, like the 25% Tim Rowley claims.

I would describe the trick as "add a large enough constant so that all 
the interesting range has the same exponent, then mask off the bits set 
by this constant"

Note: this comment is misleading, the code does the rounding that the 
FPU is set to, which is round-to-nearest by default, not floor:
/* 236 * 1.5,  (52-_shiftamt=36) uses limited precision to floor */

=== cut here for fast_DoubleToFixed_test.c ===
/*
Copyright (c) 2005 by Bill Spitzak
Permission is hereby granted to use this code in any manner.
*/

#include <stdio.h>
#include <stdlib.h>

#if __BIG_ENDIAN_
#define iman_ 1
#else
#define iman_ 0
#endif

/**
   Fast version of XDoubleToFixed(f)
   Works for -32768.0 .. 32767.99999
   Requires IEEE floating point.
*/
inline int fast_DoubleToFixed(double val) {
   val = val + (68719476736.0*1.5);
   return ((long*)&val)[iman_];
}

/**
   Puts fast_DoubleToFixed() into *out.
   Returns true if out of range error.
   Requires IEEE floating point.
*/
inline int checkDoubleToFixed(double val, int* out) {
   val = val + (32768+68719476736.0*1.5);
   *out = ((int*)&val)[iman_]^0x80000000;
   return ((int*)&val)[1-iman_] != 0x42380000;
}

#define XFixedToDouble(f)    (((double) (f)) / 65536)

int main(int argc, char** argv) {
   int i, j;
   double f;
   if (argc < 2) {
     fprintf(stderr, "Return fast_rint(x) for each argument\n");
     return 1;
   }
   for (i = 1; i < argc; i++) {
     f = strtod(argv[i],0);
     j = fast_DoubleToFixed(f);
     printf("fast_DoubleToFixed(%g) == %.10g (0x%08x)\n", f, 
XFixedToDouble(j), j);
     if (checkDoubleToFixed(f, &j)) {
       printf("checkDoubleToFixed(%g) == FAIL\n", f);
     } else {
       printf("checkDoubleToFixed(%g) == %.10g (0x%08x)\n", f, 
XFixedToDouble(j), j);
     }
   }
   return 0;
}
=== cut here ===

Tim Rowley wrote:
> Doing some profiling runs with gradients, I noticed that a lot of the 
> time was disappearing into _cairo_fixed_from_double (and its 
> descendents, ftol and floor).  Searching around I found this page that 
> talks about doing fast floating point to integer conversion:
> 
>     http://www.stereopsis.com/FPU.html
> 
> Adapting one of the methods for cairo gave about a 25% speed increase in 
> our gradient tests.