[cairo] _cairo_color_compute_shorts fails with FPU set to single precision

[Carl Worth]

On Sat, 15 Jul 2006 21:58:23 -0400, Behdad Esfahbod wrote:
> There's this bug:
>
>   https://bugs.freedesktop.org/show_bug.cgi?id=7497
>
> Carl likes to see discussion on the list about it before we make any
> change.  So, bithackers please comment.

No takers yet on this one, so I'll have to expose some of my own
ignorance. I've recently been looking at the proposals for improving
the performance of _cairo_fixed_from_double and I thought I should
look into the above problem at the same time.

For anyone too lazy to follow the above link, (I know I would be), the
issue concerns the correct way to convert a floating-point color
channel value in [0.0, 1.0] to an integer value in [0, 65535]. In
particular, the current implementation of _cairo_color_compute_shorts
fails when the FPU is set to single-precision mode.

As background, consider Owen Taylor's note on converting integers from
a range of [0, M] to a range of [0, N]:

	http://people.redhat.com/otaylor/pixel-converting.html

He begins that discussion by presenting two common options for
converting a floating-point value f in [0.0, 1.0] to an integer i in
[0, N]. Either option has the desirable characteristic that if f is
computed as i/N then it will round-trip exactly to i again.

The first option separates the range into N+1 equally-sized
regions. The second option instead centers N+1 regions around the
positions to which integers will be mapped to the floating-point range
by the function i/N.

This second option is quite easy to compute as:

	i = floor (f * N + 0.5)

and this approach was even suggested by Billy Biggs at one point with
the following patch:

	http://vektor.ca/bugs/round-colors.diff

The drawback of this approach is that the regions that map to values
of 0 and N are half the size of the regions that map to all other
values.

So, we've instead been attempting to implement the first approach,
with equally-sized divisions of the floating-point range. Something
that is very close to correct is:

	i = floor (f * (N+1))

This is correct for all input values in [0.0, 1.0). But given a value
f of 1.0 this function will return N+1 rather than N as desired, (and
that N+1 value will be truncated down to 0 if we're choosing N as to
use every last bit available in i).

So we need to tweak the computation very slightly in order to ensure
that 1.0 maps correctly. The current implementation of
_cairo_color_compute_shorts attempts a tweak by using the following
computation instead:

	i = floor (f * (N+1-epsilon))

In this particular case, we're mapping to a 16-bit integer so N is
65535. And in the current implementation the value for epsilon is
1e-5, (chosen as something near 1/65535 I suppose).

Now, this computation with this epsilon works given sufficient
precision in the floating-point representation, but it is rather
demanding. In particular, the value 65536 - 1e-5 has a binary
representation with 32 bits of 1 in its significand before the first
0. So, if this value is computed with fewer than 33 available
significand bits then it will get rounded up to 65536. This will cause
a 1.0 input value to map to 0 rather than the correct value of
65535. This is exactly the behavior reported in the original bug
report above.

Behdad has cooked up some patches that attempt to address this by
using a slightly different approach of:

	i = floor (f * ((N+1) * (1.0 - epsilon)))

Where the code actually uses DBL_EPSILON as defined by float.h for its
epsilon value, (or 1e-7 if DBL_EPSILON is not found in a system
header). This seems like an improvement at first, but it won't
actually help with the original bug report which was triggered by
setting the FPU to single-precision mode at run time. So getting a
compile-time constant based on what float.h advertises won't help I
think.

I'm open to suggestions on how to correctly fix this bug.

One idea I have is to simply special case the one value we know is
problematic:

	if (f == 1.0)
	    i = N;
	else
	    i = floor (f * (N+1));

The branch is certainly not lovely, but I'm hoping that this
floating-to-fixed conversion for colors won't be a hot spot, (unlike
the floating-to-fixed conversion of _cairo_fixed_from_double which is
used much more often and is already a known hot spot for some
architectures).

Meanwhile, since we know we're dealing with non-negative values here,
can't we just drop the floor() and rely on the rounding-toward-zero
truncation mandated by the C specification?

-Carl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20060829/5f98371e/attachment.pgp