XCHG RAX, RAX: 0x09, what does this code do and how does it work?

Question

Given the following short assembly snippet:

shr   rax, 3
adc   rax, 0

I worked this out a bit:

• We know SHR sets the CF with the last bit shifted.
• We know ADC dest, 0 is just adding the CF.

So looking at the bits,

        128  64  32  16  8   4   2   1 
        8    7   6   5   4   3   2   1
        ------------------------------
        1    1   1   1   1   CF  X   X
CF=1 |  0    0   0   1   1   1   1   1  ; shr 3

So if we div 8 and add the CF the most correct function is something like this,

def f(x):
  return x//8  + int( (x//4) % 2 )

When would that be useful. Quickly testing it, I can see that I am right.

rax = 0  -> 0
rax = 1  -> 0
rax = 2  -> 0
rax = 3  -> 0

rax = 4  -> 1
rax = 7  -> 1
rax = 8  -> 1
rax = 11 -> 1

rax = 12 -> 2
rax = 13 -> 2
rax = 14 -> 2
rax = 15 -> 2
rax = 16 -> 2
rax = 17 -> 2
rax = 18 -> 2
rax = 19 -> 2

...

rax = 20 -> 3
rax = 28 -> 4

Decompilation with Radare is also not useful here,

int64_t entry0 (void) {
    rax >>= 3;
    __asm ("adc rax, 0");
}

My questions is, therefore, although I do understand the immediate impact these instructions have on the operand register, what is the higher level meaning of this instruction sequence?

---

This is riddle 0x09 from the XCHG RAX, RAX book.

Answer 1

The shr rax, 3 is an unsigned divide by 8 with truncation towards zero. The inclusion of the adc rax, 0 makes the division round to nearest instead. (Though 0.5 will always be rounded up)

So this operation sets RAX to

• 1 if RAX is in the range of [4-11] (8*1 ±4)
• 2 if RAX is in the range of [12-20] (8*2 ±4)
• 3 if RAX is in the range of [20-27] (8*3 ±4)

You can simplify this further by reducing the shift to 1.

mov rax, 47  ; (remember 47/2 is 23.5)
shr rax, 1   ; rax = 23
adc rax, 0   ; rax = 24

If we do it again,

mov rax, 46  ; (remember 46/2 is 23)
shr rax, 1   ; rax = 23
adc rax, 0   ; rax = 23