CODEWITHSUNDEEP
ccryptographybit-manipulation
Alex Gaynor
Alex Gaynor

Reputation: 15009

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?

Upvotes: 9

Views: 603

Answers (3)

Ilmari Karonen
Ilmari Karonen

Reputation: 50328

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

Upvotes: 6

6502
6502

Reputation: 114481

What about

- (x >> 7)

?

Only the MSB is retained and math negation is used to replicate it to all bits.

Upvotes: 5

user529758
user529758

Reputation:

Given the declaration of your uint8_t:

uint8_t x = // MSB is either 1 or 0 if `x` depending on the signed value of `x`

A cheat that assumes 2's complement for signed integers:

return (((uint16_t)(int8_t)x) >> 8) & 0xff;

Upvotes: 2

Related Questions