Undefined behavior: "shift exponent X is too large"

[tdulcet]

Undefined behavior detected when Mlucas is compiled with UBSan enabled.

GCC:

../src/Mlucas.c:3083:58: runtime error: shift exponent 64 is too large for 64-bit type 'long long unsigned int'
../src/dft_macro.c:5057:39: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
../src/dft_macro.c:3279:38: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'

Clang:

../src/Mlucas.c:3083:58: runtime error: shift exponent 64 is too large for 64-bit type 'uint64' (aka 'unsigned long long')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/Mlucas.c:3083:58 in 
 ../src/dft_macro.c:5057:39: runtime error: shift exponent 32 is too large for 32-bit type 'uint32' (aka 'unsigned int')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/dft_macro.c:5057:39 in 
../src/dft_macro.c:3279:38: runtime error: shift exponent 32 is too large for 32-bit type 'uint32' (aka 'unsigned int')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/dft_macro.c:3279:38 in 

---

Clang Tidy also outputs similar warnings, although some of these may be false positives:

$ grep -A 2 clang-analyzer-core.BitwiseShift clang-tidy.log
 ../src/Mlucas.c:5558:28: warning: Left shift by '64' overflows the capacity of 'uint64' [clang-analyzer-core.BitwiseShift]
 5558 |                                 curr_word = (curr_wd64 << (64 - bits[ii]));                     /* Off-shift everything but the bits we need... */
      |                                              ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
--
 ../src/Mlucas.c:5633:28: warning: Left shift by '64' overflows the capacity of 'uint64' [clang-analyzer-core.BitwiseShift]
 5633 |                                 curr_word = (curr_wd64 << (64 - bits[ii]));                     /* Off-shift everything but the bits we need... */
      |                                              ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
--
 ../src/mi64.c:692:16: warning: Left shift overflows the capacity of 'uint64' [clang-analyzer-core.BitwiseShift]
  692 |                 y[i] = (x[i] << nshift) + (x[i-1] >> m64bits);
      |                         ~~~~~^~~~~~~~~
--
 ../src/mi64.c:695:15: warning: Left shift overflows the capacity of 'uint64' [clang-analyzer-core.BitwiseShift]
  695 |         y[0] = (x[0] << nshift);
      |                 ~~~~~^~~~~~~~~
--
 ../src/mi64.c:1146:16: warning: Right shift overflows the capacity of 'uint64' [clang-analyzer-core.BitwiseShift]
 1146 |                 y[i] = (x[i] >> nshift) + (x[i+1] << m64bits);
      |                         ~~~~~^~~~~~~~~
--
 ../src/mi64.c:1149:23: warning: Right shift overflows the capacity of 'uint64' [clang-analyzer-core.BitwiseShift]
 1149 |         y[len-1] = (x[len-1] >> nshift);
      |                     ~~~~~~~~~^~~~~~~~~
--
 ../src/mi64.c:3910:14: warning: Left shift overflows the capacity of 'unsigned long long' [clang-analyzer-core.BitwiseShift]
 3910 |                 j = ((1ull << exp)+63)>>6;
      |                       ~~~~~^~~~~~
--
 ../src/mi64.c:8374:20: warning: Right shift by '64' overflows the capacity of 'uint64' [clang-analyzer-core.BitwiseShift]
 8374 |                 lead_chunk = lo64>>(64-log2_numbits);
      |                              ~~~~^~~~~~~~~~~~~~~~~~~
--
 ../src/qfloat.c:546:4: warning: Right operand is negative in right shift [clang-analyzer-core.BitwiseShift]
  546 |                         QRSHIFT(qt, shft, qt);
      |                         ^
--
 ../src/twopmodq80.c:2374:14: warning: Right operand is negative in right shift [clang-analyzer-core.BitwiseShift]
 2374 |                 if((pshift >> j) & (uint32)1)
      |                     ~~~~~~~^~~~

[ldesnogu]

The warning for Mlucas.c is correct but causes no harm. The mod64=0 case that would cause the undefined behavior is taken care of by the masking and will produce the expected 0 value.

The two warnings for dft_macro.c need more digging into the code.