Resolve implementation-defined behaviour for division rounded to -infinity

Submitted by Ben Avison on Aug. 14, 2015, 2:06 p.m.

Details

Message ID 1439561167-21423-1-git-send-email-bavison@riscosopen.org
State Under Review
Headers show

Commit Message

Ben Avison Aug. 14, 2015, 2:06 p.m.
The previous implementations of DIV and MOD relied upon the built-in / and %
operators performing round-to-zero. This is true for C99, but rounding is
implementation-defined for C89 when divisor and/or dividend is negative, and
I believe Pixman is still supposed to support C89.
---
 pixman/pixman-private.h |    8 ++++----
 1 files changed, 4 insertions(+), 4 deletions(-)

Patch hide | download patch | download mbox

diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
index 73108a0..80506be 100644
--- a/pixman/pixman-private.h
+++ b/pixman/pixman-private.h
@@ -889,12 +889,12 @@  pixman_list_move_to_front (pixman_list_t *list, pixman_link_t *link)
 #endif
 
 /* Integer division that rounds towards -infinity */
-#define DIV(a, b)					   \
-    ((((a) < 0) == ((b) < 0)) ? (a) / (b) :                \
-     ((a) - (b) + 1 - (((b) < 0) << 1)) / (b))
+#define DIV(a, b) \
+    ((a) / (b) - ((a) % (b) != 0 && ((a) % (b) < 0) != ((b) < 0) ? 1 : 0))
 
 /* Modulus that produces the remainder wrt. DIV */
-#define MOD(a, b) ((a) < 0 ? ((b) - ((-(a) - 1) % (b))) - 1 : (a) % (b))
+#define MOD(a, b) \
+    ((a) % (b) + ((a) % (b) != 0 && ((a) % (b) < 0) != ((b) < 0) ? (b) : 0))
 
 #define CLIP(v, low, high) ((v) < (low) ? (low) : ((v) > (high) ? (high) : (v)))
 

Comments

Bill Spitzak Aug. 15, 2015, 12:06 a.m.
Can't this just assume/require b to be positive? That would make them a lot
simpler:

 #define DIV(a,b) ((a) / (b) - ((a) % (b) < 0 ? (b) : 0))
 #define MOD(a,b) ((a) % (b) + ((a) % (b) < 0 ? (b) : 0))



On Fri, Aug 14, 2015 at 7:06 AM, Ben Avison <bavison@riscosopen.org> wrote:

> The previous implementations of DIV and MOD relied upon the built-in / and
> %
> operators performing round-to-zero. This is true for C99, but rounding is
> implementation-defined for C89 when divisor and/or dividend is negative,
> and
> I believe Pixman is still supposed to support C89.
> ---
>  pixman/pixman-private.h |    8 ++++----
>  1 files changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
> index 73108a0..80506be 100644
> --- a/pixman/pixman-private.h
> +++ b/pixman/pixman-private.h
> @@ -889,12 +889,12 @@ pixman_list_move_to_front (pixman_list_t *list,
> pixman_link_t *link)
>  #endif
>
>  /* Integer division that rounds towards -infinity */
> -#define DIV(a, b)                                         \
> -    ((((a) < 0) == ((b) < 0)) ? (a) / (b) :                \
> -     ((a) - (b) + 1 - (((b) < 0) << 1)) / (b))
> +#define DIV(a, b) \
> +    ((a) / (b) - ((a) % (b) != 0 && ((a) % (b) < 0) != ((b) < 0) ? 1 : 0))
>
>  /* Modulus that produces the remainder wrt. DIV */
> -#define MOD(a, b) ((a) < 0 ? ((b) - ((-(a) - 1) % (b))) - 1 : (a) % (b))
> +#define MOD(a, b) \
> +    ((a) % (b) + ((a) % (b) != 0 && ((a) % (b) < 0) != ((b) < 0) ? (b) :
> 0))
>
>  #define CLIP(v, low, high) ((v) < (low) ? (low) : ((v) > (high) ? (high)
> : (v)))
>
> --
> 1.7.5.4
>
> _______________________________________________
> Pixman mailing list
> Pixman@lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/pixman
>
Ben Avison Aug. 18, 2015, 10:19 p.m.
On Sat, 15 Aug 2015 01:06:14 +0100, Bill Spitzak <spitzak@gmail.com> wrote:

> Can't this just assume/require b to be positive? That would make them a lot simpler:
>
>  #define DIV(a,b) ((a) / (b) - ((a) % (b) < 0 ? (b) : 0))
>  #define MOD(a,b) ((a) % (b) + ((a) % (b) < 0 ? (b) : 0))

I had contemplated Euclidean division/modulus too, reasoning that it
might come in handy somewhere if we ever get better support for reflected
images, but it just seemed even more complex to express in portable C
(and to be honest I haven't formulated a detailed argument of how it
would be used). It seemed safe to at least follow what the comments said,
and make it round to -infinity.

I've run the "make check" suite with added debugging to ensure that b is
never negative, and this does indeed seem to be the case, so we could
make such a change without any side effects (at least for current uses of
the macros). There was a slight error in your version, though - a correct
version would look like:

#define DIV(a, b) ((a) / (b) - ((a) % (b) < 0))
#define MOD(a, b) ((a) % (b) + ((a) % (b) < 0) ? (b) : 0))

Does anyone have any objections to such a change of definition?

Ben


> On Fri, Aug 14, 2015 at 7:06 AM, Ben Avison <bavison@riscosopen.org> wrote:
>
>> The previous implementations of DIV and MOD relied upon the built-in / and
>> %
>> operators performing round-to-zero. This is true for C99, but rounding is
>> implementation-defined for C89 when divisor and/or dividend is negative,
>> and
>> I believe Pixman is still supposed to support C89.
>> ---
>>  pixman/pixman-private.h |    8 ++++----
>>  1 files changed, 4 insertions(+), 4 deletions(-)
>>
>> diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
>> index 73108a0..80506be 100644
>> --- a/pixman/pixman-private.h
>> +++ b/pixman/pixman-private.h
>> @@ -889,12 +889,12 @@ pixman_list_move_to_front (pixman_list_t *list,
>> pixman_link_t *link)
>>  #endif
>>
>>  /* Integer division that rounds towards -infinity */
>> -#define DIV(a, b)                                         \
>> -    ((((a) < 0) == ((b) < 0)) ? (a) / (b) :                \
>> -     ((a) - (b) + 1 - (((b) < 0) << 1)) / (b))
>> +#define DIV(a, b) \
>> +    ((a) / (b) - ((a) % (b) != 0 && ((a) % (b) < 0) != ((b) < 0) ? 1 : 0))
>>
>>  /* Modulus that produces the remainder wrt. DIV */
>> -#define MOD(a, b) ((a) < 0 ? ((b) - ((-(a) - 1) % (b))) - 1 : (a) % (b))
>> +#define MOD(a, b) \
>> +    ((a) % (b) + ((a) % (b) != 0 && ((a) % (b) < 0) != ((b) < 0) ? (b) :
>> 0))
>>
>>  #define CLIP(v, low, high) ((v) < (low) ? (low) : ((v) > (high) ? (high)
>> : (v)))
>>
>> --
>> 1.7.5.4
>>
>> _______________________________________________
>> Pixman mailing list
>> Pixman@lists.freedesktop.org
>> http://lists.freedesktop.org/mailman/listinfo/pixman
Siarhei Siamashka Aug. 26, 2015, 9:22 a.m.
On Fri, 14 Aug 2015 15:06:07 +0100
Ben Avison <bavison@riscosopen.org> wrote:

> The previous implementations of DIV and MOD relied upon the built-in / and %
> operators performing round-to-zero. This is true for C99, but rounding is
> implementation-defined for C89 when divisor and/or dividend is negative, and
> I believe Pixman is still supposed to support C89.

Do you have a practical example of an existing C89 compiler, which
differs from C99 when handling '/' and '%' operators?

My understanding is that C compilers just used to emit a single
division instruction as implemented by the target processor. This
provides the best performance, but is not perfectly portable in
theory. But in practice, after decades of evolution, all the
remaining (major) CPU architectures happen to handle integer
division rounding in the same way (round-to-zero). And C99 just
promoted the de-facto standard to the official standard status
(regardless of whatever was the official justification).

Right now pixman also assumes two's complement representation
of negative numbers and is doing right shifts with integer types
(pixman_fixed_t). In theory this all is implementation defined.
In practice, non-two's complement systems are already extinct
and they are even not supported by GCC:
   https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html

The pixman way of dealing with this stuff is to make sure that all
the assumptions are verified by the test suite. If you are worried
about / and % operators behaviour, then it's best to make sure that
it has proper coverage in the pixman tests and will report an error
if somebody ever tries to build pixman for an unusual system with
an unusual compiler. As an example, we used to assume that powerpc
is always big endian and x86 is always little endian. Now it turned
out that little endian powerpc systems actually exist. This did not
cause any serious troubles for distro maintainers and users because
the test suite was able to catch this problem:
   https://bugs.freedesktop.org/show_bug.cgi?id=81229
And it was reasonably easy to workaround (by disabling vmx
optimizations) and then add support for the little endian variant.
Should we start worrying about a hypothetical big endian x86
variant right now? Maybe not yet.

Over years, pixman has evolved into a rather hostile environment
for bugs. And this did not happen magically itself, but is a result
of taking care to adjust the test suite to catch even more bugs
and trying more corner cases. One more example, again powerpc
related. We got a bug report:
    http://lists.freedesktop.org/archives/pixman/2013-August/002871.html
It was only reproducible on power7 system, so the test suite was
obviously not good enough to detect this reliably. We found the
root cause of the bug, fixed it:
    http://cgit.freedesktop.org/pixman/commit/?id=b6c5ba06f0c5c0bd8d186e7a4879fd3b33e7e13f
And also extended the test suite with a more reliable test:
    http://cgit.freedesktop.org/pixman/commit/?id=0438435b9c915b61af21446b2cb2f77a2b98a3b9
Now if anything like this ever happens again (on powerpc or
any other architecture), we should get it detected.

There are also compiler bugs. In fact, pixman happens to be a compiler
bug magnet. We have found and reported a handful of bugs to GCC and
Clang. Here is an example of the last one:
    https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64172
Based on our experience, compiler bugs are not so uncommon. So when
somebody wants to compile pixman for some unusual system with an
unusual or very new version of the compiler, we can't be sure if
the resulting binary is going to work fine unless it passes the
tests.

> ---
>  pixman/pixman-private.h |    8 ++++----
>  1 files changed, 4 insertions(+), 4 deletions(-)
> 
> diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
> index 73108a0..80506be 100644
> --- a/pixman/pixman-private.h
> +++ b/pixman/pixman-private.h
> @@ -889,12 +889,12 @@ pixman_list_move_to_front (pixman_list_t *list, pixman_link_t *link)
>  #endif
>  
>  /* Integer division that rounds towards -infinity */
> -#define DIV(a, b)					   \
> -    ((((a) < 0) == ((b) < 0)) ? (a) / (b) :                \
> -     ((a) - (b) + 1 - (((b) < 0) << 1)) / (b))
> +#define DIV(a, b) \
> +    ((a) / (b) - ((a) % (b) != 0 && ((a) % (b) < 0) != ((b) < 0) ? 1 : 0))
>  /* Modulus that produces the remainder wrt. DIV */
> -#define MOD(a, b) ((a) < 0 ? ((b) - ((-(a) - 1) % (b))) - 1 : (a) % (b))
> +#define MOD(a, b) \
> +    ((a) % (b) + ((a) % (b) != 0 && ((a) % (b) < 0) != ((b) < 0) ? (b) : 0))
>  
>  #define CLIP(v, low, high) ((v) < (low) ? (low) : ((v) > (high) ? (high) : (v)))

I'm not saying that this patch is wrong, but how can we be sure that it
is doing the right thing? The new variant of this code still relies on /
and % operators (which are implementation-defined) and uses them with
negative numbers. A more in-depth explanation would be useful, or a
confirmation that it fixes a real problem on a real system.

Moreover, previously we assumed that / and % operators are rounding
towards zero and had special DIV and MOD macro variants, which are
rounding towards minus infinity. If we are really worried about
rounding in general, should we review all the uses of / and %
operators in the code too? And for the sake of consistency introduce
new macro variants, which are rounding towards zero?

There is also additional concern about the performance. Is the new
code slower/faster than the old one?

To sum it up. I think that we really should just rely on the test
suite to take care of verifying the rounding behaviour (and improve
the test suite if it is not good enough to catch this type of problems).
If the rounding behaviour is confirmed to be a real problem on some
real hardware with a real compiler, then we can deal with it.
Ben Avison Aug. 26, 2015, 1:21 p.m.
On Wed, 26 Aug 2015 10:22:22 +0100, Siarhei Siamashka <siarhei.siamashka@gmail.com> wrote:

> On Fri, 14 Aug 2015 15:06:07 +0100
> Ben Avison <bavison@riscosopen.org> wrote:
>
>> The previous implementations of DIV and MOD relied upon the built-in
>> / and % operators performing round-to-zero. This is true for C99, but
>> rounding is implementation-defined for C89 when divisor and/or
>> dividend is negative
>
> Do you have a practical example of an existing C89 compiler, which
> differs from C99 when handling '/' and '%' operators?

No, but I'd have thought it was bad practice to assume C99 behaviour when
compiling C89. The absence of any discussion in the accompanying comments
made me wonder if the author was aware of the issue - it's certainly
relevant when the whole point of those macros is to force a particular
rounding direction when dealing with negative numbers.

> My understanding is that C compilers just used to emit a single
> division instruction as implemented by the target processor. This
> provides the best performance, but is not perfectly portable in
> theory. But in practice, after decades of evolution, all the
> remaining (major) CPU architectures happen to handle integer
> division rounding in the same way (round-to-zero). And C99 just
> promoted the de-facto standard to the official standard status
> (regardless of whatever was the official justification).

Don't forget not all architectures even have divide instructions - ARM
only just started regularly implementing them (at least for its A profile
CPUs) at the Cortex-A15. Typically it's then the job of a runtime support
function to do the division, and who's to say how that works?

> I'm not saying that this patch is wrong, but how can we be sure that it
> is doing the right thing? The new variant of this code still relies on /
> and % operators (which are implementation-defined) and uses them with
> negative numbers. A more in-depth explanation would be useful

OK, a bit of context. I was working on some iterator code (not yet
posted) which supported tiled repeat, which caused me to inspect the
repeat() function in pixman-inlines.h, which in turn uses the MOD macro.
This immediately set off alarm bells in my head, because I'd encountered
the woolly definition in C89 several years ago.

I confess that my approach to writing a correct algorithm was to hit
Google and adapt one of the first well-reasoned hits I encountered into
macro form, to let somebody else do the hard work. The page I used was

http://www.microhowto.info/howto/round_towards_minus_infinity_when_dividing_integers_in_c_or_c++.html

which cites a couple of other references.

As described on that page, the approach it uses will work irrespective of
the rounding rules employed by the built-in / and % operators.

> If we are really worried about
> rounding in general, should we review all the uses of / and %
> operators in the code too? And for the sake of consistency introduce
> new macro variants, which are rounding towards zero?

Arguably, maybe we should aspire to, yes. Whenever the dividend and
divisor are both positive, there's no ambiguity, and this should rule out
the vast majority of cases that don't already need round-to-minus-
infinity, I'd expect. Even if this isn't done immediately, it wouldn't
prevent us from getting the minus-infinity case right now.

Of course, there is an easy fix, which is to say that Pixman has to be
compiled in C99 mode, or at least to wrap different implementations in
#if __STDC_VERSION__ < 199901L.

> There is also additional concern about the performance. Is the new
> code slower/faster than the old one?

I hadn't really investigated that, but having had a bit of a play with
ARM GCC, I see that it fails to use the runtime function that returns
both the quotient and remainder (__aeabi_idivmod) with the operations in
macro form. I get more luck writing them as functions:

inline int
DIV (int a, int b)
{
    int q = a / b;
    int r = a - q * b;
    return q - (r < 0);
}

inline int
MOD (int a, int b)
{
    int r = a % b;
    if (r < 0)
      r += b;
    return r;
}

with the caveat that these are based on the macros from my 2015-08-18
post, which rely on b being positive. (Set aside for the moment whether
an inline function with an all-caps name is a good idea...)

Ben
Alan Coopersmith Aug. 26, 2015, 2:34 p.m.
On 08/26/15 06:21 AM, Ben Avison wrote:
> No, but I'd have thought it was bad practice to assume C99 behaviour when
> compiling C89.

Perhaps the AC_PROG_CC_C99 macro should be added to the pixman/configure.ac
to avoid that then.
Siarhei Siamashka Aug. 26, 2015, 3:40 p.m.
On Wed, 26 Aug 2015 07:34:13 -0700
Alan Coopersmith <alan.coopersmith@oracle.com> wrote:

> On 08/26/15 06:21 AM, Ben Avison wrote:
> > No, but I'd have thought it was bad practice to assume C99 behaviour when
> > compiling C89.
> 
> Perhaps the AC_PROG_CC_C99 macro should be added to the pixman/configure.ac
> to avoid that then.

If we start compiling pixman in C99 mode by default, then this will make
it harder for us to identify potential C89 compatibility issues. One of
such recurring issues in the past were the cases of doing variable
declaration in the middle of code:

    http://lists.freedesktop.org/archives/pixman/2013-October/003033.html
    http://lists.freedesktop.org/archives/pixman/2013-September/002954.html

We got this under control by using the -Wdeclaration-after-statement
option in order to at least issue a compilation warning:

    http://cgit.freedesktop.org/pixman/commit/?id=9e81419ed5c0ee490ddacf7bada516a25cae87eb

And as explained to Ben in my previous message, pixman currently
relies on certain implementation defined behaviour, which happens
to be implemented in the same predictable way on all the known
systems in the world (maybe excluding some museum exhibits or really
oddball special-purpose hardware). We are not relying on undefined
behaviour, which is a totally different matter. And we have an
extensive test suite in place, which exists to ensure that the
compiled pixman library behaves in the intended way. This also
includes verifying that our current assumptions about the
implementation defined behaviour are satisfied on every target
system.

Basically, there is no real problem to solve (yet). And we are well
prepared to deal with the theoretical problems if they ever get
discovered in practice.

For example, I really would not like to see anyone getting inspired
by this discussion thread and going on a crusade against the two's
complement signed integer representation assumptions.
Alan Coopersmith Aug. 26, 2015, 3:46 p.m.
On 08/26/15 08:40 AM, Siarhei Siamashka wrote:
> If we start compiling pixman in C99 mode by default, then this will make
> it harder for us to identify potential C89 compatibility issues.

Do we still need to care about C89 compatibility issues?  C99 is 16 years old
now, it's about time to rely on it.
Siarhei Siamashka Aug. 26, 2015, 4:03 p.m.
On Wed, 26 Aug 2015 08:46:57 -0700
Alan Coopersmith <alan.coopersmith@oracle.com> wrote:

> On 08/26/15 08:40 AM, Siarhei Siamashka wrote:
> > If we start compiling pixman in C99 mode by default, then this will make
> > it harder for us to identify potential C89 compatibility issues.
> 
> Do we still need to care about C89 compatibility issues?  C99 is 16 years old
> now, it's about time to rely on it.

Have you actually checked the links to the bugreports in the mailing
list archive that I have given to you?

We did have to care about C89 compatibility in 2013, as can be seen
based on the feedback from the real users. And maybe still do even now.
Alan Coopersmith Aug. 26, 2015, 4:31 p.m.
On 08/26/15 09:03 AM, Siarhei Siamashka wrote:
> On Wed, 26 Aug 2015 08:46:57 -0700
> Alan Coopersmith <alan.coopersmith@oracle.com> wrote:
>
>> On 08/26/15 08:40 AM, Siarhei Siamashka wrote:
>>> If we start compiling pixman in C99 mode by default, then this will make
>>> it harder for us to identify potential C89 compatibility issues.
>>
>> Do we still need to care about C89 compatibility issues?  C99 is 16 years old
>> now, it's about time to rely on it.
>
> Have you actually checked the links to the bugreports in the mailing
> list archive that I have given to you?

Yes.

> We did have to care about C89 compatibility in 2013, as can be seen
> based on the feedback from the real users. And maybe still do even now.

I wasn't asking about 2013, I was asking if maybe we don't still need to now.

I know Microsoft's C compiler was a holdout for a long time, but thought it
finally got most of C99 brought in since it was required for C++11 support.
Pekka Paalanen Aug. 27, 2015, 9:28 a.m.
On Wed, 26 Aug 2015 14:21:07 +0100
"Ben Avison" <bavison@riscosopen.org> wrote:

> I hadn't really investigated that, but having had a bit of a play with
> ARM GCC, I see that it fails to use the runtime function that returns
> both the quotient and remainder (__aeabi_idivmod) with the operations in
> macro form. I get more luck writing them as functions:
> 
> inline int
> DIV (int a, int b)
> {
>     int q = a / b;
>     int r = a - q * b;
>     return q - (r < 0);
> }
> 
> inline int
> MOD (int a, int b)
> {
>     int r = a % b;
>     if (r < 0)
>       r += b;
>     return r;
> }
> 
> with the caveat that these are based on the macros from my 2015-08-18
> post, which rely on b being positive. (Set aside for the moment whether
> an inline function with an all-caps name is a good idea...)

FWIW, when I looked at the macros (old and proposed), my head started
spinning. Looking at these inline functions, I feel I could actually
understand them without rewriting them.
- my 2c on readability

Not to mention that unlike the macros, these do not evaluate the
arguments multiple times.

Btw. I personally agree with Siarhei's testing argument. If there is
any uncertainty whether existing code is good or not, writing a test to
explicitly check for it is a nice way. If users come back reporting
test failures, then we have a problem. Otherwise no need to pay
attention.

I just wish testing for performance was as reliable as for
correctness...


Thanks,
pq