[Bug libc/15799] New: glibc div() code is broken

["guilliam.xavier at gmail dot com" <sourceware-bugzilla at sourceware dot org>]

http://sourceware.org/bugzilla/show_bug.cgi?id=15799

            Bug ID: 15799
           Summary: glibc div() code is broken
           Product: glibc
           Version: 2.18
            Status: NEW
          Severity: minor
          Priority: P2
         Component: libc
          Assignee: unassigned at sourceware dot org
          Reporter: guilliam.xavier at gmail dot com
                CC: drepper.fsp at gmail dot com

Created attachment 7126
  --> http://sourceware.org/bugzilla/attachment.cgi?id=7126&action=edit
Integer division example table ("truncated division" gives column A)

Overview:  The logic of the code in stdlib/div.c is actually broken relative to
all C (and C++) Standards.


=== It is broken relative to C89 (and C++98/03). ===

### CONTEXT (scroll down for actual BUG) ###

Given two integer values N and D, with D != 0, let's define q and r:

  int q = N / D;
  int r = N % D;

The C89 Standard section 3.3.5 Multiplicative operators (as well as the C++98
Standard section 5.6) puts constraints on values of q and r , which can be
formulated like this (here using assert informally, and ignoring possible
overflows):

  assert(q * D + r == N);
  assert(abs(r) < abs(D));
  if (N >= 0 && D >= 0) assert(r >= 0);

With the first two constraints, there are two possible (q, r) values for each
(N, D).  The third constraint specifies the choice when neither N nor D is
strictly negative, but if either is then the choice is implementation-defined
(see attachment for an example).

But the standard div function has specified semantics in all cases (section
4.10.6.2 The div function).  Its (q, r) output is under the same three
constraints as above, plus a fourth, which can be expressed as:

  assert(abs(q * D) <= abs(N));

or equivalently:

  assert((r < 0) == (N < 0));  // sign(r) == sign(N)

In effect, this is the behaviour of "truncated division", where q has any
fractional part discard (is truncated towards 0) and r has the same sign as N.

### BUG ###

Now, looking at the code at
http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/div.c;h=44a30a7ea485a9eef38fb4ffe6aaebdc06468b3b;hb=HEAD
you actually find that it only handles one of the three possible "wrong" cases
(relative to the attached example, it handles (33, -5) yielding (-7, -2), and
corrects it to (-6, 3), but it does not handle (-33, 5) yielding (-7, 2), nor
(-33, -5) yielding (7, 2)).

It is difficult to give a test case, as a real one would require different
machines with different types of built-in division.  What I did is copy-paste
the code (and change the function name), manually set the values of numer and
denom and force the "wrong" answer for result.quot and result.rem, and assert
the expected results before the return.


=== It is also "broken" relative to C99/11 (and C++11). ===

In newer versions of the Standard, the built-in integer division (used by / and
% operators) has specified semantics in all cases (C99 section 6.5.5):  the
quotient is always truncated towards 0 and (equivalently) the remainder always
has the same sign as the numerator (dividend).

This means that div(numer, denom) should simply return the results of numer /
denom and numer % denom directly (C99 section 7.20.6.2), and the old incomplete
run-time test-and-adjustment code (and the obsolete comment block) should be
removed entirely.  Currently, the code is needlessly complex and (potentially)
inefficient.


Additional information:  The original implementor himself, Chris Torek,
confirmed the issue:
http://stackoverflow.com/a/17901906/688659

The linked page also contains links to "fix attempts" but none seems completely
correct.

-- 
You are receiving this mail because:
You are on the CC list for the bug.