Help stabilising mini-gmp

[Nelson H. F. Beebe]

Vincent clarifies about my response on about zero shift counts:

>> ...
>> I'm not talking about a zero shift count, but a shift of the value 0
>> with an arbitrary shift count, e.g. (uint64_t) 0 << 64. This is
>> undefined behavior, but I wonder why. When mapped to a hardware
>> instruction, does the result depend on the platform?
>> ...

It isn't the issue of a zero value being shifted, but rather, the
range of allowable shift values.  The ISO 1999 C Standard's relevent
restriction is:

>> ...
>> 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.
>> ...

That is, with an n-bit word, shift counts from 0 to n - 1 are legal,
but negative shift counts, and counts of n or larger, are undefined
behavior.

The reason is that hardware implementations do different things: as my
first message today pointed out, some encode the shift count in the
instruction in an n-bit field, and that field can only hold values
from 0 to n - 1.  Requesting a shift of n bits would very likely mean
that the stored shift count would be the low-order n bits, a value
that is 0.  For shifts larger than n, the effective shift would be
encoded as n mod (2**n), so n + 1 would become 1, n + 2 would become
2, and so on.

Such shifts would be extremely surprising to a programmer who did not
understand what is really happening, because humans tend naturally to
think of exact (infinite precision) integer arithmetic: surely a
33-bit left shift of a 32-bit word should just clear that word to
zero!  No, it does not on many systems: it instead becomes a 1-bit
left shift.

Thus, the ISO Standards committee properly defines n (and higher) bit
shifts to be undefined.

In an ideal world, all compilers would at least have a option to do
compile-time tests of constant shifts, and force run-time tests of
variable shifts, so that such behavior could be caught, diagnosed, and
repaired.

A few compilers now do just that.  Recent gcc compilers provide this
info-node documentation:

>> ...
>> '-fsanitize=undefined'
>>      Enable UndefinedBehaviorSanitizer, a fast undefined behavior
>>      detector.  Various computations will be instrumented to detect
>>      undefined behavior at runtime.  Current suboptions are:
>> 
>>      '-fsanitize=shift'
>>           This option enables checking that the result of a shift
>>           operation is not undefined.  Note that what exactly is
>>           considered undefined differs slightly between C and C++, as
>>           well as between ISO C90 and C99, etc.
>>      ... and many more ...
>> ...
     
Recent clang compilers provide

>> ...
>> 	-fsanitize=undefined: UndefinedBehaviorSanitizer, a fast and
>>          compatible undefined behavior checker.
>> 	[from http://clang.llvm.org/docs/UsersManual.html]
>> 
>> 	-fsanitize=shift: Shift operators where the amount shifted is
>>          greater or equal to the promoted bit-width of the left hand
>>          side or less than zero, or where the left hand side is
>>          negative. For a signed left shift, also checks for signed
>>          overflow in C, and for unsigned overflow in C++. You can use
>>          -fsanitize=shift-base or -fsanitize=shift-exponent to check
>>          only left-hand side or right-hand side of shift operation,
>>          respectively.
>> 	[from http://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html#ubsan-checks]
>> ...

-------------------------------------------------------------------------------
- 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 math.utah.edu  -
- 155 S 1400 E RM 233                       beebe at acm.org  beebe at computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------