Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to write a constant time function to copy the most significant bit to all bits

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?

like image 509
Alex Gaynor Avatar asked Nov 18 '13 22:11

Alex Gaynor


1 Answers

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.)

like image 125
Ilmari Karonen Avatar answered Sep 23 '22 10:09

Ilmari Karonen