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

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

[guilliam.xavier at gmail dot com]

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.

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

[guilliam.xavier at gmail dot com]

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

--- Comment #1 from Guilliam Xavier <guilliam.xavier at gmail dot com> ---
* I must make a small correction:

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

is correct, but the following is actually not strictly equivalent:

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

because we can have N == -10, D == 5 and q == -2, r == 0 (the quotient is
exact), so I think a corrected equivalent would be rather:

  assert(r == 0 || (r < 0) == (N < 0));

(And just after that: typo: "discard" -> "discarded".)

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

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

[guilliam.xavier at gmail dot com]

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

--- Comment #2 from Guilliam Xavier <guilliam.xavier at gmail dot com> ---
Created attachment 7133
  --> http://sourceware.org/bugzilla/attachment.cgi?id=7133&action=edit
More examples (3 types of division, plus exact quotient and zero)

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

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

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
       via  bbea82f7fe8af40fd08e8956e1aaf4d877168652 (commit)
      from  977f4b31b7ca4a4e498c397f3fd70510694bbd86 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=bbea82f7fe8af40fd08e8956e1aaf4d877168652

commit bbea82f7fe8af40fd08e8956e1aaf4d877168652
Author: Ondřej Bílka <neleai@seznam.cz>
Date:   Wed Oct 30 16:07:15 2013 +0100

    Remove code from div that is by C99 obsolete. Fixes bug 15799

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog      |    7 +++++++
 NEWS           |    8 ++++----
 stdlib/div.c   |   22 ----------------------
 stdlib/ldiv.c  |   22 ----------------------
 stdlib/lldiv.c |   22 ----------------------
 5 files changed, 11 insertions(+), 70 deletions(-)

-- 
You are receiving this mail because:
You are on the CC list for the bug.
>From glibc-bugs-return-20009-listarch-glibc-bugs=sources.redhat.com@sourceware.org Wed Oct 30 15:09:57 2013
Return-Path: <glibc-bugs-return-20009-listarch-glibc-bugs=sources.redhat.com@sourceware.org>
Delivered-To: listarch-glibc-bugs@sources.redhat.com
Received: (qmail 13102 invoked by alias); 30 Oct 2013 15:09:56 -0000
Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <glibc-bugs.sourceware.org>
List-Subscribe: <mailto:glibc-bugs-subscribe@sourceware.org>
List-Post: <mailto:glibc-bugs@sourceware.org>
List-Help: <mailto:glibc-bugs-help@sourceware.org>, <http://sourceware.org/lists.html#faqs>
Sender: glibc-bugs-owner@sourceware.org
Delivered-To: mailing list glibc-bugs@sourceware.org
Received: (qmail 13064 invoked by uid 48); 30 Oct 2013 15:09:53 -0000
From: "neleai at seznam dot cz" <sourceware-bugzilla@sourceware.org>
To: glibc-bugs@sourceware.org
Subject: [Bug libc/15799] glibc div() code is broken
Date: Wed, 30 Oct 2013 15:09:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: glibc
X-Bugzilla-Component: libc
X-Bugzilla-Version: 2.18
X-Bugzilla-Keywords:
X-Bugzilla-Severity: minor
X-Bugzilla-Who: neleai at seznam dot cz
X-Bugzilla-Status: RESOLVED
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: unassigned at sourceware dot org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cc resolution
Message-ID: <bug-15799-131-KUxEWNzlmz@http.sourceware.org/bugzilla/>
In-Reply-To: <bug-15799-131@http.sourceware.org/bugzilla/>
References: <bug-15799-131@http.sourceware.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://sourceware.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2013-10/txt/msg00368.txt.bz2
Content-length: 572

https://sourceware.org/bugzilla/show_bug.cgi?id\x15799

Ondrej Bilka <neleai at seznam dot cz> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |neleai at seznam dot cz
         Resolution|---                         |FIXED

--- Comment #4 from Ondrej Bilka <neleai at seznam dot cz> ---
Fixed.

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

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

[fweimer at redhat dot com]

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

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
              Flags|                            |security-

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