Samuel Neves via RT
2014-10-06 16:21:50 UTC
Attached is a patch that makes all the arithmetic in constant-time operations unsigned. This avoids two sources of unspecified behavior in the C standard:
- Signed right shifts, when the sign bit is 1, are implementation-defined (C99 §6.5.7/5);
- Converting an unsigned integer to signed when out of signed range is also implementation-defined, and may trap (C99 §6.3.1.3/3).
The code and formulas are based off of https://gist.github.com/sneves/10845247, and all the formulas have been computer-verified, using a SAT solver, to be correct.
The formula for "less than" is essentially the same as the current one, but optimized to use 5 instead of 7 bitwise operations; the formula for "greater or equal" is simply the negation of "less than", and can be simplified as such. Generating masks using -(unsigned >> 31) requires one more operation than the arithmetic shift version, but compilers seem to be pretty good at recognizing and generating the arithmetic shift anyway, where available.
- Signed right shifts, when the sign bit is 1, are implementation-defined (C99 §6.5.7/5);
- Converting an unsigned integer to signed when out of signed range is also implementation-defined, and may trap (C99 §6.3.1.3/3).
The code and formulas are based off of https://gist.github.com/sneves/10845247, and all the formulas have been computer-verified, using a SAT solver, to be correct.
The formula for "less than" is essentially the same as the current one, but optimized to use 5 instead of 7 bitwise operations; the formula for "greater or equal" is simply the negation of "less than", and can be simplified as such. Generating masks using -(unsigned >> 31) requires one more operation than the arithmetic shift version, but compilers seem to be pretty good at recognizing and generating the arithmetic shift anyway, where available.