How to write a constant time function to copy the most significant bit to all bits
bit-manipulation, c, cryptography
Solution
How about:
#define uint8_msb_to_all_bits(x) (0xFF * ((x) >> 7))
or even better:
#define uint8_msb_to_all_bits(x) (-((x) >> 7))
The way these both work is that, if `x` is an 8-bit unsigned integer, then `x >> 7` is 1 if the MSB of `x` is set, and 0 otherwise. All that remains is then mapping 1 to 0xFF, which can be done either by multiplication, or, in this particular case, simply by negating the number.
(Yes, negating an unsigned number is well defined in C.)
Problem
I'd like to write a function, in C, which takes the MSB of `uint8_t`, and if it's set, returns `0xFF` and if not `0x00`. In short, which returns an integer where all the bits are set to the same value as the MSB. But I'd like to do it in a completely constant time way, no branches, no array offsets, just mathematical operations which are guaranteed to always touch the same number of bits. And ideally, without any undefined behavior. How can this be done?