[Pixman] [PATCH] Resolve implementation-defined behaviour for division rounded to -infinity

[Ben Avison]

On Wed, 26 Aug 2015 10:22:22 +0100, Siarhei Siamashka <siarhei.siamashka at gmail.com> wrote:

> On Fri, 14 Aug 2015 15:06:07 +0100
> Ben Avison <bavison at 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