Source: CS:APP3e, Bryant and O’Hallaron, homework problem 3.58

For a function with prototype long decode2(long x, long y, long z), gcc generates the following [x86-64] assembly code:

decode2:
    subq    %rdx, %rsi
    imulq   %rsi, %rdi
    movq    %rsi, %rax
    salq    $63,  %rax
    sarq    $63,  %rax
    xorq    %rdi, %rax
    ret

Parameters x, y, and z are passed in registers %rdi, %rsi, and %rdx. The code stores the return value in register %rax. Write C code for decode2 that will have an effect equivalent to the assembly code shown.

Solution

1. Annotate the assembly instructions

  • Function signature: long decode2(long x, long y, long z)
  • Parameter x passed in %rdi
  • Parameter y passed in %rsi
  • Parameter z passed in %rdx
  • Return value in %rax
decode2: 
  subq    %rdx, %rsi   ; Decrement %rsi by the quad word value in %rdx 
                       ; C: y = y - z 

  imulq   %rsi, %rdi   ; Multiply %rdi * %rsi and store quad word result  
                       ; in %rdi 
                       ; C: x = x * y 

  movq    %rsi, %rax   ; Move quad word from register %rsi to register  
                       ; %rax, which stores the return value. 
                       ; C: long result = y 

  salq    $63,  %rax   ; Left-shift (logical): %rax << $63 and store 
                       ; quad word result in %rax 
                       ; C: result = result << 63 

  sarq    $63,  %rax   ; Arithmetic right-shift: %rax >> $63 and store 
                       ; quad word result in %rax 
                       ; C: result = result >> 63 

  xorq    %rdi, %rax   ; Exclusive or: %rax ^ %rdi and store quad word 
                       ; result in %rax 
                       ; C: result = result ^ x
  ret                  ; Return the value in `%rax`.
                       ; C: return result

2. Write equivalent C

1
2
3
4
5
6
7
8
9

long decode2(long x, long y, long z) {
    y -= z;
    x *= y;
    long result = y;
    result <<= 63;
    result >>= 63;
    result ^= x;
    return result;
}

3. Generate x86-64 assembly code

Red Hat Linux 4.4.7-23, gcc 4.4.7:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

% gcc -O1 -S decode2.c && cat decode2.s
    .file   "decode2.c"
    .text
.globl decode2
    .type   decode2, @function
decode2:
.LFB0:
    .cfi_startproc
    subq    %rdx, %rsi
    movq    %rsi, %rax
    salq    $63, %rax
    sarq    $63, %rax
    imulq   %rdi, %rsi
    xorq    %rsi, %rax
    ret
    .cfi_endproc
.LFE0:
    .size   decode2, .-decode2
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-23)"
    .section    .note.GNU-stack,"",@progbits

Notes

Compiled on MacOS 10.12.6 with gcc 4.8.1, my C code produces the x86-64 assembly given in the textbook, in EXACTLY that order of instructions. Compiled on Red Hat Linux 4.4.7-23 with gcc 4.4.7, it produces the same instructions in a different order, but the effect is the same:

subq    %rdx, %rsi   ; y -= z
movq    %rsi, %rax   ; long result = y
salq    $63, %rax    ; result <<= 63
sarq    $63, %rax    ; result >>= 63
imulq   %rdi, %rsi   ; x *= y
xorq    %rsi, %rax   ; result ^= x
ret