Assembly Bit Shifts, x86 Edition!

I got my degrees in Physics and Math, not computer science or computer engineering. So assembly kind of terrifies me. However since Sergei told me about the asm function in C that allows you to use assembly in the context of readable code, I've wanted to put it to some use. We were talking about the bit shift operators in C and how they depend on the variable types and lack rotations, so I asked Serge to write some C code for implementing the bit shifts in assembly.

The asm function

The asm declaration basically follows this format

asm("assembly" : "=reg" (outputVar) : "reg" (inputVar1), "reg" (inputVar2) : "clobberedReg1", "clobberedReg2")

The "reg" argument refers to the register (memory bank on the cpu). There are several registers usually with specific purposes. They can be refered to via a letter; "a" for the accumulator register, "b" for the base register , "c" for the counter register, and so on. Within the assembly itself you don't refer to the register by letter, but rather by size specific names. For the "a" register you use %eax for 32-bits, %ax for 16 bits, and %al for  8 bits.

asm, by default, uses a flavor of assembly called the AT&T style (vs the intel style). In the AT&T style register names are prefixed with %, the order of operands is source first and destination last, and the size of the operands is specified by appending a (b for 8-bits, w for 16-bits, and l for 32-bits) to the opcode. Another notable features is that dollars signs prefix immediate (i.e. hardcoded) values such as in "addl $5, %eax", and when the $ prefix is used before a variable it refers to the address of the variable. You can find more complete coverage of AT&T syntax here.

You can avoid specifying a register and instead use "r", which means any register, or "g" which refers to any general register. You can even combine constraints like "r,g". A more comprehensive list of constraints can be found here. To use these arguments in the assembly without referring directly to the register you can refer to the arguments in the order outputs then inputs via %0, %1, and so on. Or you can name the arguments by writing %[var1] "r" within the argument and using %[var1] in the assembly. Lastly, if you want an input and output to share a register put the number of the input in the constraint of the output. Now here's an example use of the asm function in use:

int logical_shift_right(unsigned int in, unsigned char offset){
    asm("shrl %%cl, %%eax" : "=r" (in) : "c" (offset), "0" (in));
    return in;
}

The double percentage symbol is simply because within the assembler template, % is a special character and %% is the escape. Here the output and the second input share the %eax register. Even though our only constraint is "r" GCC knows to use "a" because %eax is specified in the assembly.

Bit shifts

There are generally four types of bit shifts. logical shifts, arithmetic shifts, rotations, and rotations through carry. We'll be using the shl, sal, rol, rcl opcodes for this. A more comprehensive list of opcodes can be found here.

Logical shifts shift the left bit off and replace the empty bit with a 0 as so.

Logical left shift (src)

int logical_shift_left(unsigned int in, unsigned char offset){
    asm("shll %%cl, %%eax" : "=r" (in) : "c" (offset), "0" (in));
    return in;
}

Arithmetic shifts are similar except they preserve the sign of the number by replacing the first number with it's previous value regardless of the shift.

Arithmetic right shift (src)

int arithmetic_shift_right(unsigned int in, unsigned char offset){
    asm("sarl %%cl, %%eax" : "=r" (in) : "c" (offset), "0" (in));
    return in;
}

Rotations just take the bit shifted off and place it in the empty bit.

Left rotation (src)

int rotate_left(unsigned int in, unsigned char offset){
    asm("roll %%cl, %%eax" : "=r" (in) : "c" (offset), "0" (in));
    return in;
}

Lastly rotations through carry replace the empty bit with the value in a external bit called the carry bit then they take the bit shifted off and place it in the carry bit.

Left rotation though carry (src)

int rotate_left_through_carry(unsigned int in, unsigned char offset){
    asm("rcll %%cl, %%eax" : "=r" (in) : "c" (offset), "0" (in));
    return in;
}

We can now give a full C example utilizing all the bit shift functions. If you follow this link then compile and run main "-948243243" "1" in the terminal you should see all the different bit shifts. If that link breaks you can also just download the code here.

Extra Credit Reading

Check out what the the compiled versions of the functions look like here. You'll see that it's mostly padding from the function's scope, with only one instruction different among them. Some other important lines, are movzbl -0x4(%ebp),%edx, mov 0x8(%ebp),%eax which set up our variables according to our extended asm input specifiers. You may be wondering what this "ebp" is, it stands for base pointer, and the best way to think of it is as a pointer to the argumetns; parameters are accessed by subtracting a constant offset from ebp. You can read further about function stacks here.

While researching we came across a number of cool details. For instance the size specific register names actually refer to different regions of the register and have historical origins as explained here. And because we we're wondering if how physical these registers were, we came across this stack overflow answer that explains how cpu's use multiple registers by parallelizing code using a process called register renaming. I'm not going into the process in detail, but it makes an interesting read.