Re: Fixed point cairo.. or no cairo?

[Jorn Baayen <jorn openedhand com>]

Hi,

Thanks a lot for the pointers! I have added comments below.

On Mon, 2006-08-14 at 09:34 -0700, Carl Worth wrote:
> On Mon, 14 Aug 2006 10:09:48 +0300, Jorn Baayen wrote:
> >
> > On Tue, 2006-08-08 at 10:46 -0700, Carl Worth wrote:
> >
> > > I'm planning to put new fixed<->floating-point conversion code into
> > > cairo this week.
> >
> > Any progress on this?
> 
> Nope. Didn't happen yet.
> 
> If someone wants to look at it, here are some details of what could be
> done:
> 
> 1) The current implementation has complete function-call
>    overhead. Could easily be reduced with inlining, (if the compiler's
>    not doing that automatically), or macros.
> 
> So that's the easy one that doesn't actually change the code at
> all. Next is the stuff that will take a little more investigation:
> 
> 2) There's some discussion of the correctness of the rounding of the
>    current code here. For any new implementation, I would like to see
>    comments indicating that the code respects the concerns raised
>    here:
> 
> 	https://bugs.freedesktop.org/show_bug.cgi?id=4846
> 
>    (And better, than comments would be some test cases that ensure the
>    desired behavior is met.)
> 
> 3) Finally, a couple of people have proposed much faster mechanisms
>    for implementing the conversion. First was Bill Spitzak who
>    provided some code here:
> 
> 	http://lists.freedesktop.org/archives/cairo/2005-June/004419.html
> 
>    Then later, Tim Rowley independently provided a source explaining
>    the code along with a very similar implementation:
> 
> 	http://thread.gmane.org/gmane.comp.lib.cairo/5228/focus=5228
> 
>    What I've been planning to do for a while was to write some
>    configure-time check to ensure that the assumptions made in this
>    code (IEEE floating-point) are valid and conditionally compile this
>    code only where we know it will work.

I had a look at the various options available and their rounding
correctness. What I was able to find out was:

o The current cairo_fixed_from_double() does not adhere to the rules of
  either mathematical nor banker's rounding.

o Correct mathematical rounding can be achieved using round(), this
  however is even slower than the current cairo_fixed_from_double()
  implementation. Also round() is c99.

o Correct and fast banker's rounding can be achieved using Sree's
  Real2Int[1]. This depends on doubles being in IEEE format- do
  any of the platforms cairo does/will run on *not* use IEEE
  doubles?

o I was not able to come up with an implementation doing fast and
  correct mathematical rounding. This is probably just me, though.


I am attaching code illustrating all these cases.


Thanks,

Jorn



[1] http://www.stereopsis.com/FPU.html


-- 
OpenedHand Ltd.
http://o-hand.com/

/* gcc test.c -o test -lm -std=c99 `pkg-config --libs --cflags glib-2.0` */

#include <math.h>
#include <glib.h>

/* #define SHOWNUMBERS 1 */

#define N_TESTS 21

const struct {
        double d;
        gint32 i;
} tests[N_TESTS] = {
        { + (.5 - 0x1p-54), 0 },
        { - (.5 - 0x1p-54), 0 },
        { 1.5, 2 },
        { 2.5001, 3 },
        { 2.6, 3 },
        { 2.9, 3 },
        { 1.0, 1 },
        { 0.9, 1 },
        { 0.5, 1 },
        { -0.5, -1 },
        { 0.49, 0 },
        { 0.51, 1 },
        { 8.5, 9 },
        { 9.5, 10 },
        { 8.75, 9 },
        { -0.49, 0 },
        { -0.51, -1 },
        { -1.5, -2 },
        { -1.2, -1 },
        { -3.2, -3 },
        { -3.5, -4 }
};

#ifdef WORDS_BIGENDIAN

  #define iman 1

#else

  #define iman 0

#endif

const double _double2fixmagic52 = 6755399441055744.0; /* 2 ^ 52 * 1.5        */
const double _double2fixmagic36 = 103079215104.0;     /* 2 ^ (52 - 16) * 1.5 */

/* This is the fastest, but it uses banker's rounding. */
gint32
fixed_from_double_sree (double val)
{
        val = val + _double2fixmagic52;
        
        return ((gint32 *) &val)[iman];
}

/* This tries to do mathematical rounding right, but fails. */
gint32
fixed_from_double_useless (double val)
{
        val = val + 0.5 + _double2fixmagic52;
        
        return ((gint32 *) &val)[iman];
}

/* This tries to do mathematical rounding right, but fails. */
gint32
fixed_from_double_shift (double val)
{
        val = val + 0.5 + _double2fixmagic36;

	return ((gint32 *) &val)[iman] >> 16;
}

/* This is the only one with 100% correct mathematical rounding,
 * but it is also the slowest. */
gint32
fixed_from_double_round (double val)
{
        val = round (val) + _double2fixmagic52;

	return ((gint32 *) &val)[iman];
}

/* This is what cairo currently uses. It's slow and does not stick to a
 * particular style of rounding. */
gint32
fixed_from_double_cairo (double val)
{
        return (gint32) floor (val + 0.5);
}

static void
run (const char *desc, gint32 (* func) (double val))
{
        gint32 result;
        GTimer *timer;
        int i, passed = 0;

        g_print ("=== %s ===\n", desc);

        timer = g_timer_new ();
        g_timer_start (timer);
        
        for (i = 0; i < N_TESTS; i++) {
                result = func (tests[i].d);

                if (result == tests[i].i) {
#ifdef SHOWNUMBERS
                        g_print ("Passed test #%d: d: %.20lf i: %d result: %d.\n",
                                i, tests[i].d, tests[i].i, result);
#endif

                        passed++;
                } else {
#ifdef SHOWNUMBERS
                        g_print ("Failed test #%d: d: %.20lf i: %d result: %d.\n",
                                i, tests[i].d, tests[i].i, result);
#endif
                }
        }

        g_print ("\nElapsed: %lfs\n", g_timer_elapsed (timer, NULL));
        g_timer_destroy (timer);
        
        g_print ("Passed: %f\%\n\n\n",
                 ((double) passed / (double) N_TESTS) * 100.0);
}

int
main (int argc, char **argv)
{
        run ("Failed attempt at fast mathematical rounding #1",
             fixed_from_double_useless);
        run ("Failed attempt at fast mathematical rounding #2",
             fixed_from_double_shift);
        run ("Sree's Real2Int (banker's rounding)", fixed_from_double_sree);
        run ("Correct, but slow mathematical rounding using round()",
             fixed_from_double_round);
        run ("Current cairo function", fixed_from_double_cairo);
}