Section 5: Assembly exercises

In today’s section, we’ll walk through a selection of our assembly exercises, which are problems taken from prior exams. Also take the opportunity to ask questions about the problem set and class material.

All exercises assume a 64-bit x86-64 architecture unless otherwise stated.

The main subjects of these exercises are:

ASM-1. Assembly properties

Here’s some assembly produced by compiling a C program. (The instructions are labeled with byte offsets for your convenience.)

             .globl  f
             .align  16, 0x90
             .type   f,@function
f:
   0:        movl    $1, %r8d
   6:        jmp     b <f+0xb>

   8:        incl    %r8d

   b:        movl    %r8d, %ecx
   e:        imull   %ecx, %ecx
  11:        movl    $1, %edx

  16:        movl    %edx, %edi
  18:        imull   %edi, %edi
  1b:        movl    $1, %esi

  20:        movl    %esi, %eax
  22:        imull   %eax, %eax
  25:        addl    %edi, %eax
  27:        cmpl    %ecx, %eax
  29:        je      40 <f+0x40>
  2b:        cmpl    %edx, %esi
  2d:        leal    1(%rsi), %eax
  30:        movl    %eax, %esi
  32:        jl      20 <f+0x20>
  34:        cmpl    %r8d, %edx
  37:        leal    1(%rdx), %eax
  3a:        movl    %eax, %edx
  3c:        jl      16 <f+0x16>
  3e:        jmp     8 <f+0x8>

  40:        pushq   %rax
  41:        movl    $.L.str, %edi
  46:        xorl    %eax, %eax
  48:        callq   printf
  4d:        movl    $1, %eax
  52:        popq    %rcx
  53:        retq

             .type   .L.str,@object
.L.str:
             .asciz  "%d %d\n"
             .size   .L.str, 7

QUESTION ASM-1A. How many arguments might this function take? Circle all that apply.

  1. 0
  2. 1
  3. 2
  4. 3 or more

QUESTION ASM-1B. What might this function return? Circle all that apply.

  1. 0
  2. 1
  3. −1
  4. Its first argument, whatever that argument is
  5. A square number other than 0 or 1
  6. None of the above

QUESTION ASM-1C. Which callee-saved registers does this function save and restore? Circle all that apply.

  1. %rax
  2. %rbx
  3. %rcx
  4. %rdx
  5. %rbp
  6. %rsi
  7. %rdi
  8. None of the above

QUESTION ASM-1D. This function handles signed integers. If we changed the C source to use unsigned integers instead, which instructions would change? Circle all that apply.

  1. movl
  2. imull
  3. addl
  4. cmpl
  5. je
  6. jl
  7. popq
  8. None of the above

QUESTION ASM-1E. What might this function print? Circle all that apply.

  1. 0 0
  2. 1 1
  3. 3 4
  4. 4 5
  5. 6 8
  6. None of the above

ASM-2. Disassembly

Here is some x86 assembly code.

f:
         movl a, %eax
         movl b, %edx
         andl $255, %edx
         subl %edx, %eax
         movl %eax, a
         retq

QUESTION ASM-2A. Write valid C code that could have compiled into this assembly (i.e., write a C definition of function f), given the global variable declarations “extern unsigned a, b;.” Your C code should compile without warnings.

QUESTION ASM-2B. Write different valid, warning-free C code that could have compiled into that assembly. This version should contain different operators than your first version. (For extra credit, use only one operator.)

QUESTION ASM-2C. Again, write different valid, warning-free C code that could have compiled into that assembly. In this version, f should have a different type than in your first version.

ASM-6. Data structure assembly

Here are four assembly functions, f1 through f4.

f1:
        testl   %esi, %esi
        jle     LBB0_3
        incl    %esi
LBB0_2:
        movq    8(%rdi), %rdi
        decl    %esi
        cmpl    $1, %esi
        jg      LBB0_2
LBB0_3:
        movl    (%rdi), %eax
        retq
f2:
        pushq   %rbp
        movq    %rsp, %rbp
        movslq  %esi, %rax
        movq    (%rdi,%rax,8), %rcx
        movl    (%rcx,%rax,4), %eax
        popq    %rbp
        retq
f3:
        testl   %esi, %esi
        jle     LBB2_3
        incl    %esi
LBB2_2:
        movl    %edx, %eax
        andl    $1, %eax
        movq    8(%rdi,%rax,8), %rdi
        sarl    %edx
        decl    %esi
        cmpl    $1, %esi
        jg      LBB2_2
LBB2_3:
        movl    (%rdi), %eax
        retq
f4:
        movslq  %esi, %rax
        movl    (%rdi,%rax,4), %eax
        retq

QUESTION ASM-6A. Each function returns a value loaded from some data structure. Which function uses which data structure?

  1. Array
  2. Array of pointers to arrays
  3. Linked list
  4. Binary tree

QUESTION ASM-6B. The array data structure is an array of type T. Considering the code for the function that manipulates the array, which of the following types are likely possibilities for T? Circle all that apply.

  1. char
  2. int
  3. unsigned long
  4. unsigned long long
  5. char*
  6. None of the above

ASM-16. Calling convention

The following questions concern valid C++ functions compiled using the normal x86-64 calling convention. True or false?

QUESTION ASM-16A. If the function’s instructions do not save and restore any registers, then the C++ function did not call any other function.

QUESTION ASM-16B. If the function’s instructions do not change the stack pointer, then the function’s instructions do not contain a call instruction.

QUESTION ASM-16C. If the function’s instructions do not change the stack pointer, then the C++ function did not call any other function. Explain your answer briefly.

QUESTION ASM-16D. If the function’s instructions do not modify the %rax register, then the C++ function must return void.

QUESTION ASM-16E. If the function’s instructions store a local variable on the stack, then that variable’s address will be less than the function’s initial stack pointer.

ASM-23. Get–set interfaces

The following questions concern get–set interfaces. These are map-like data structures which support two operations:

void set(container, key, value)
Change container’s value for key to value.

value_type get(container, key)
Returns container’s current value for key. This is the most recent value set by set(container, key, value) or, if there is no previous set, the natural default for the value type (0, nullptr, empty string—whatever’s appropriate).

Here’s the assembly definition of xxx1, which is either get or set for a data structure.

_Z4xxx1...:
    movq    (%rdi,%rsi,8), %rax
    ret

QUESTION ASM-23A. Is this get or set?

QUESTION ASM-23B. What kind of data structure is this?

QUESTION ASM-23C. What can you tell about the key type for this data structure?

QUESTION ASM-23D. What can you tell about the value type?

QUESTION ASM-23E. Write a C++ version of the other operation for the same data structure, including a function signature and any type definitions required.

Here’s the assembly definition of get2, which is get for a different data structure.

_Z4get2...:
.L28:
    testq   %rdi, %rdi
    je  .L30
    movq    (%rdi), %rax
    cmpq    %rsi, %rax
    je  .L35
    cmpq    %rax, %rsi
    jnb .L27
    movq    16(%rdi), %rdi
    jmp .L28
.L27:
    movq    24(%rdi), %rdi
    jmp .L28
.L30:
    xorl    %eax, %eax
    ret
.L35:
    movq    8(%rdi), %rax
    ret

QUESTION ASM-23F. What value is returned if the key parameter is not present in the data structure?

QUESTION ASM-23G. Write a struct definition for the data structure being accessed by this code.

QUESTION ASM-23H. What kind of data structure is being accessed by this code?