3.60

Corrections: In C code, parameter n should be of type int, as per the assembly code.

Problem

Consider the following assembly code:

    long loop(long x, int n)
    x in %rdi, n in %esi
1   loop:
2     movl  %esi, %ecx
3     movl  $1, %edx
4     movl  $0, %eax
5     jmp   .L2
6   .L3:
7     movq  %rdi, %r8
8     andq  %rdx, %r8
9     orq   %r8, %rax
10    salq  %cl, %rdx
11  .L2:
12    testq %rdx, %rdx
13    jne   .L3
14    rep; ret

The preceding code was generated by compiling C code that had the following overall form:

1   long loop(long x, int n)
2   {
3       long result = _____;
4       long mask;
5       for (mask = _____; mask _____; mask = _____){
6           result |= _____;
7       }
8       return result;
9   }

Your task is to fill in the missing parts of the C code to get a program equivalent to the generated assembly code. Recall that the result of the function is returned in register %rax. You will find it helpful to examine the assembly code before, during, and after the loop to form a consistent mapping between the registers and the program variables.

A. Which registers hold program values x, n, result, and mask? B. What are the initial values of result and mask? C. What is the test condition for mask? D. How does mask get updated? E. How does result get updated? F. Fill in all the missing parts of the C code.

Solution

A.

x \(\rightarrow\) %rdi

n \(\rightarrow\) %esi

result \(\rightarrow\) %rax

mask \(\rightarrow\) %rdx

B.

result = 0, mask = 1

C.

mask != 0

D.

mask << n

Note: In the assembly code, we see that only the lower 8 bytes of n (%cl) are taken. It is undefined behaviour in C as to what happens when a shift is attempted with a number greater than 32 or 64, but most processors would behave as if modulo 64 or modulo 32 that value was passed.

E.

result |= x & mask

F.

1   long loop(long x, int n)
2   {
3       long result = 0;
4       long mask;
5       for (mask = 1; mask != 0; mask = mask << n){
6           result |= x & mask;
7       }
8       return result;
9   }