Help stabilising mini-gmp
Nelson H. F. Beebe
beebe at math.utah.edu
Fri Dec 2 01:15:54 UTC 2016
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/ -
-------------------------------------------------------------------------------
More information about the gmp-devel
mailing list