Help stabilising mini-gmp

Nelson H. F. Beebe beebe at
Thu Dec 1 15:57:12 UTC 2016

Niels M{\"o}ller and Torbj{\"o}rn Granlund write on Sunday 27-Nov-2016:

>> ...
>>   But it's surprising to me too that also non-overflowing left shift of
>>   negative values is undefined. So it seems generally unsafe to use shift
>>   on signed types, except possibly for constants.
>> It is pretty silly.  By leaving a useful operation undefined, one cannot
>> use it anywhere if one cares about perfect portability.  Here we have an
>> operation which in practce will work anywhere made somewhat useless by
>> the C/C++ committees.
>> ...

I believe there is a misunderstanding of the C/C++ standards.

Here is verbatim text lifted from Technical Corrigendum 3 (2007)
of the ISO/IEC 9899 standard (aka C99):

>> ...
>>      6.5.7 Bitwise shift operators
>>      Syntax
>> 1             shift-expression:
>>                       additive-expression
>>                       shift-expression << additive-expression
>>                       shift-expression >> additive-expression
>>      Constraints
>> 2    Each of the operands shall have integer type.
>>      Semantics
>> 3    The integer promotions are performed on each of the operands. The type of the result is
>>      that of the promoted left operand. If the value of the right operand is negative or is
>>      greater than or equal to the width of the promoted left operand, the behavior is undefined.
>> ...

Notice that it does NOT prohibit left-shifting negative values: it
just says that behavior with negative SHIFT COUNTS is undefined.

The reason for that is that low-level expressions in C have always
been intended, and assumed, to have straightforward mappings into
hardware instructions.  The meaning of a negative shift has always
been dependent on the machine's instruction set.

For example, the famous IBM System/360 architecture from 1964,
stil marketed as the IBM z9000 architecture, says in its
Principles of Operation manual:

>> ...
>> The second-operand address is not used to address data; its
>> rightmost six bits indicate the number of bit positions to be
>> shifted.  The remainder of the address is ignored.
>> ...

In particular, consider positive and negative 4-bit shifts with
these encodings in two's-complement arithmetic:

  4  0x00000004   -4  0xfffffffc

For the negative shift, the count is picked up as 0x3c == 60.  In
other words, a shift of -n bits is really a shift or 64 - n bits.

For the signed right shift operation it prescribes this:

>> ...
>> 1. A right shift of one bit position is equivalent to division
>> by 2 with rounding downward. When an even number is shifted
>> right one position, the result is equivalent to dividing the
>> number by 2. When an odd number is shifted right one position,
>> the result is equivalent to dividing the next lower number by
>> 2. For example, +5 shifted right by one bit position yields
>> +2, whereas -5 yields -3.
>> 2. For SHIFT RIGHT SINGLE (SRA), shift amounts from 31 to 63
>> cause the entire numeric part to be shifted out of the
>> register, leaving a result of -1 or zero, depending on whether
>> or not the initial contents were negative. For SHIFT RIGHT
>> SINGLE (SRAG), a shift amount of 63 causes the same effect.
>> ...

>From the DEC VAX architecture handbook, the sign of the shift
count determines the direction: left for positive, move for zero,
right for negative. It says that on overflow in a left shift, the
result is the low-order bits of the true result.

On the DEC PDP-10, action is, like the VAX, according to the sign
of the shift.

The MIPS R1000 architecture manual says that the shift count
operand is greater that 31, or less than 0, the shift is by that
value MOD 32.

On Hewlett-Packard, PA-RISC, the shift count is an unsigned 5-bit
field in the instruction word.

On Sun SPARC, the shift count is taken from the 5 or 6
lower-order bits of the count operand; a compile-time constant
shift can be embedded in the instruction word.

The Motorola M68000 arithmetic left and right shifts operate only
one bit at a time, so a compiler must generate an n-bit shift
with an n-iteration loop (perhaps unrolled when n is a
compile-time constant).

The Intel x86 and x86-64 architectures use the low-order bits of
the shift-count operand to determine the actual shift.

These behavioral differences across various systems (all of which
have had multiple C compilers), forced the C Standard to
prescribe negative shift counts as undefined behavior.  In all
cases, the generated assembly code will produce REPRODUCIBLE
results on a single architecture, but those results may DIFFER
across architectures.

- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                    FAX: +1 801 581 4148                  -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe at  -
- 155 S 1400 E RM 233                       beebe at  beebe at -
- Salt Lake City, UT 84112-0090, USA    URL: -

More information about the gmp-devel mailing list