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);
}
_______________________________________________
Performance-list mailing list
Performance-list@gnome.org
http://mail.gnome.org/mailman/listinfo/performance-list
