CATEGORY:
MITRE CWE-194: Unexpected Sign Extension.
REFERENCE:
https://cwe.mitre.org/data/definitions/194.html
EXPLANATION:
The expression '1 << 31' is made up of two (signed) 'int' constant
operands; therefore, the result of the shift operation will be of type
'int' as well. On a 32-bit platform, the resulting bit pattern of 1 << 31
is 0x80000000 which, interpreted as 'signed int', corresponds to -2^31, or
-2147483648. Interpreted as an 'unsigned int' ('size_t') this is again
0x80000000, exactly what is desired.
The problem arises on platforms where 'size_t' comprises more than 32 bits,
like on most 64-bit platforms. On 64-bit platforms, 'size_t' is typically
64 bits in order to support a 64-bit address space. In those cases, the
sign bit (the bit at offset 31 on a 32-bit signed integer) is extended
(copied) to all bit offsets higher than 31. Hence, instead of the expected
value 0x0000000080000000 the initial mask value will be 0xFFFFFFFF80000000.
CONSEQUENCES:
On 64-bit platforms, 'leadingZeros' computes wrong results because the
while loop counts way too many bits; consequently, the values calculated by
'log2ceil' are wrong, too.
BUGFIX:
The main mistake in 'leadingZeros' is that there is a mix of
signed/unsigned types in this statement:
size_t mask = (1 << 31);
One possibility to fix this is by explicitly casting the literal operands to
'size_t', but appending a 'U' qualifier suffices:
size_t mask = (1U << 31U);
Due to the fact that now all operands are unsigned, no unexpected sign
extension will take place when the 32-bit result of the shift operation is
extended to a 64-bit 'size_t' value.
REMARKS:
This portability issue would have remained dormant had the more natural
expression
while ((mask & n) != 0)
been used.