[Bug other/60843] New: Documentation: 4.5 Integers/C99 6.3.1.3 ("reduce modulo 2^N")

[Bug other/60843] New: Documentation: 4.5 Integers/C99 6.3.1.3 ("reduce modulo 2^N")

[kdevel at vogtner dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60843

            Bug ID: 60843
           Summary: Documentation: 4.5 Integers/C99 6.3.1.3 ("reduce
                    modulo 2^N")
           Product: gcc
           Version: 4.8.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: other
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kdevel at vogtner dot de

Section 4.5 states [1]:

"The result of, or the signal raised by, converting an integer to a signed
integer type when the value cannot be represented in an object of that type
(C90 6.2.1.2, C99 6.3.1.3).

For conversion to a type of width N, the value is reduced modulo 2^N to be
within range of the type; no signal is raised."

Reduce A modulo M usually means find the least integer R in the range [0, M -
1] such that A is congruent R modulo M. But this is not what gcc compiled
programs do on i686/x86_64: One finds e.g. (int) 2147483649u == -2147483647.
The original bits are taken "as is", which equivalents to *subtraction* of 2^N
(N=32) giving -2147483647.

[1] http://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/Integers-implementation.html

[Bug other/60843] Documentation: 4.5 Integers/C99 6.3.1.3 ("reduce modulo 2^N")

[joseph at codesourcery dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60843

--- Comment #1 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Tue, 15 Apr 2014, kdevel at vogtner dot de wrote:

> For conversion to a type of width N, the value is reduced modulo 2^N to be
> within range of the type; no signal is raised."
> 
> Reduce A modulo M usually means find the least integer R in the range [0, M -
> 1] such that A is congruent R modulo M. But this is not what gcc compiled

I don't see the problem.  It explicitly says "reduced modulo 2^N to be 
within range of the type", and that unambiguously defines the result 
value, as there is exactly one result within the range of the type that is 
equal to the input, modulo 2^N.  The qualifier "to be within range of the 
type" says that [0, M - 1] is irrelevant, because that isn't the range of 
the type in question.

This is the normal form of modulo arithmetic for signed types, as used for 
example by -fwrapv (and defined in detail in the first (1994) edition of 
LIA-1; the second (2012) edition removes the modulo operations, but the 
underlying wrap_I operation is in LIA-2).

[Bug other/60843] Documentation: 4.5 Integers/C99 6.3.1.3 ("reduce modulo 2^N")

[kdevel at vogtner dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60843

--- Comment #2 from Stefan <kdevel at vogtner dot de> ---
(In reply to joseph@codesourcery.com from comment #1)
> > Reduce A modulo M usually means find the least integer R in the range [0, M -
> > 1] such that A is congruent R modulo M. But this is not what gcc compiled
> 
> I don't see the problem.

The problem is the erroneous wording "reduction modulo 2^N". *Reduction* by
definition results in the least *nonnegative* number out of the list of
congruent numbers, cf. http://www.youtube.com/watch?v=SO6l6sDwEFg&t=5m50s

What gcc does is not reduction.

> It explicitly says "reduced modulo 2^N to be 
> within range of the type", and that unambiguously defines the result 
> value, as there is exactly one result within the range of the type that is 
> equal to the input, modulo 2^N.

The reduction of 2147483649 modulo 2^32 is unambigously 2147483649. Therefore
by reduction one does not get a number which is within the range of int.
"Reduce A modulo M" is definitionally complete. Adjoining "to be within range
of type" does not change or extend its meaning it only clarifies the intent.

> The qualifier "to be within range of the 
> type" says that [0, M - 1] is irrelevant, because that isn't the range of 
> the type in question.

If you remove the "least nonnegative" part from the definition of reduction you
no longer have a reduction modulo 2^N but something else, e.g. subtraction.

> This is the normal form of modulo arithmetic for signed types, as used for 
> example by -fwrapv (and defined in detail in the first (1994) edition of 
> LIA-1; the second (2012) edition removes the modulo operations, but the 
> underlying wrap_I operation is in LIA-2).

Thanks for these references. AFAICS neither ISO/IEC 10967-1:1994(E) nor
:2012(E) provide a definition of the notion of reduction modulo some number.
They do not use the notion either. ISO/IEC 10967-1:1994(E) defines conversion
between distint integer types in § 5.3 by means of a function wrap_I which is
defined in § 5.1.2 as (if x not in I):

    wrap_I: Z -> I
    wrap_I(x) = x + j * (maxint - minint + 1) for some j in Z
    wrap_I(x) in I

In ISO/IEC 10967-2:2001 wrap_I is defined in § 5.1.1 as (if x not in I):

    wrap_I: Z -> I
    wrap_I(x) = x - (n · (maxint_I - minint_I + 1)) where n in Z  is chosen
        such that the result is in I

This wrapper function does not reduce modulo 2^N and it is not named
"reduction".
>From gcc-bugs-return-450223-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Apr 30 10:43:12 2014
Return-Path: <gcc-bugs-return-450223-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 18419 invoked by alias); 30 Apr 2014 10:43:11 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 18393 invoked by uid 48); 30 Apr 2014 10:43:08 -0000
From: "pierre.labastie at neuf dot fr" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/61011] New: libstdc++-v3 should be target-libstdc++-v3 in top level configure
Date: Wed, 30 Apr 2014 10:43:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: unknown
X-Bugzilla-Keywords:
X-Bugzilla-Severity: minor
X-Bugzilla-Who: pierre.labastie at neuf dot fr
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter
Message-ID: <bug-61011-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-04/txt/msg02243.txt.bz2
Content-length: 919

http://gcc.gnu.org/bugzilla/show_bug.cgi?ida011

            Bug ID: 61011
           Summary: libstdc++-v3 should be target-libstdc++-v3 in top
                    level configure
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pierre.labastie at neuf dot fr

When passing --disable-libstdcxx to top level configure the following code is
executed:
------------
if test "${ENABLE_LIBSTDCXX}" = "no" ; then
  noconfigdirs="$noconfigdirs libstdc++-v3"
fi
------------
This does not have the desired effect, since "make" still tries to build the
target libstdc++.

The above code should be changed to:
------------
if test "${ENABLE_LIBSTDCXX}" = "no" ; then
  noconfigdirs="$noconfigdirs target-libstdc++-v3"
fi
------------

Thanks

[Bug other/60843] Documentation: 4.5 Integers/C99 6.3.1.3 ("reduce modulo 2^N")

[joseph at codesourcery dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60843

--- Comment #3 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Wed, 30 Apr 2014, kdevel at vogtner dot de wrote:

> The problem is the erroneous wording "reduction modulo 2^N". *Reduction* by
> definition results in the least *nonnegative* number out of the list of
> congruent numbers, cf. http://www.youtube.com/watch?v=SO6l6sDwEFg&t=5m50s

It's perfectly normal English usage for "X with qualifier" to be outside 
what would be understood by X without the qualifier.  I think the use in 
the GCC manual is a perfectly ordinary and well-understood use of the 
term.  The GCC manual is not trying to refer to any particular set of 
definitions as normative references, and it's not trying to give formal 
definitions.

If anything, I'd say strictly reduction modulo 2^N is a map from Z to Z / 
2^N Z, i.e. producing an equivalence class of integers rather than a 
single integer (and for modulo arithmetic, integer types are interpreted 
as having values that are such equivalence classes).