Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why bit-shift in two steps?

In the Linux kernel, I found the following code:

static inline loff_t pos_from_hilo(unsigned long high, unsigned long low)
{
#define HALF_LONG_BITS (BITS_PER_LONG / 2)
    return (((loff_t)high << HALF_LONG_BITS) << HALF_LONG_BITS) | low;
}

The code is used to combine syscall arguments into one wider variable, so for example on ia32 the offset of pwritev is specified in two 32 bit registers.

On x64, loff_t and unsigned long are both 64 bit wide. In this case, the high variable is ignored and only low is used. On ia32, loff_t is 64 bit wide and unsigned long is 32 bit wide. In this case the two arguments high and low are combined.

I was wondering why the code bit-shifts twice instead of once. There's a bit more information about this code in the commit message and in an LWN article: System calls and 64-bit architectures, but no explanation for the double bit-shift.

like image 229
Georg Schölly Avatar asked Aug 06 '21 15:08

Georg Schölly


People also ask

What is the purpose of bit shifting?

A bit shift is a bitwise operation where the order of several bits is moved, either to the left or right, to efficiently perform a mathematical operation. Bit shifts help with optimization in low-level programming because they require fewer calculations for the CPU than conventional math.

How does binary shift work?

To divide a number, a binary shift moves all the digits in the binary number along to the right and fills the gaps after the shift with 0: to divide by two, all digits shift one place to the right. to divide by four, all digits shift two places to the right.

How does left and right shift work?

The bitwise shift operators move the bit values of a binary object. The left operand specifies the value to be shifted. The right operand specifies the number of positions that the bits in the value are to be shifted.


1 Answers

The following warning in a test app helped my figure this out:

test.c:8:27: warning: left shift count >= width of type [-Wshift-count-overflow]
    8 |     return (((loff_t)high << (2*HALF_LONG_BITS))) | low;

The double bit-shift protects against undefined behavior. From the C spec:

6.5.7 3) ... If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

On a 64 bit machine both loff_t and long are 64 bits wide. If we did the shift at once, we would shift high by 64 bits which according to the statement above is undefined behavior. Doing it in two steps makes high into 0.


PS: I wrote a test program to investigate this and to my surprise I got different results when I replaced the two bit-shifts with a single bit-shift.

like image 62
Georg Schölly Avatar answered Oct 16 '22 05:10

Georg Schölly