Functions and the Stack

Examples of conditionals and loops

Looping over a string

section .data

buf:    db    "Hello, world!", 10
BUFLEN: equ   $-buf

section .text
...

  mov rax, buf

.begin_loop:
  cmp rax, buf + BUFLEN
  je .end_loop

    ... ; Process byte [rax]

  jmp .begin_loop
.end_loop:
...

This is equivalent to a while loop, as if BUFLEN was 0, the loop would not run at all.

Computing the sign of `rax`

This sets rbx to -1 if rax is negative, 0 if it is equal to 0, and +1 if it is positive:


  cmp rax, 0
  jl .negative
  jg .positive

.zero:              ; The zero label is never used, it's just for consistency
  xor rbx, rbx
  jmp .done

.negative:
  mov rbx, -1
  jmp .done

.positive
  mov rbx, +1
  jmp .done

.done:
  ...

Nested loops

This loops rax over 0 to 9 and (inside that) rbx over 0 to 15:

  xor rax, rax            ; rax = 0  
.outer_loop:
    xor rbx, rbx            ; rbx = 0
.inner_loop:

      ... ; Use rax, rbx

      inc rbx
      cmp rbx, 16
      jb .inner_loop

    inc rax
    cmp rax, 10
    jb .outer_loop

  ... ; Rest of the program

Example: Looping over user input

We want to write a program which will input up to 256 bytes from the user, and then capitalize any lower-case letters and print out the result. The main loop of this, in C/C++, would look like this:

char buffer[256];
// Read input

unsigned rdi = 0;
while(rdi < 256) {
    if(buffer[rdi] >= 'a' && buffer[rdi] <= 'z')
        buffer[rdi] -= 32;

    ++rdi;
}

// print buffer

;;;;
;;;; sys_read.s
;;;; Read from stdin into a buffer.
;;;; 
section .bss

; Buffer of 256 bytes
BUFLEN:   equ           256
buf:      resb          BUFLEN

SYS_read:   equ         0
SYS_write:  equ         1
SYS_stdin:  equ         0
SYS_stdout: equ         1
SYS_exit:   equ         60

section .text

to_uppercase:

  ; rdi = addr of character
  cmp byte [rdi], 'a'
  jb .done

  cmp byte [rdi], 'z'
  ja .done

  sub byte [rdi], 32 ; Convert to upper-case

  .done:
  ret


global _start
_start:

  ; Read syscall
  mov rax, SYS_read
  mov rdi, SYS_stdin
  mov rsi, buf
  mov rdx, BUFLEN
  syscall

  mov rcx, rax          ; rax = number of bytes read
  mov rdi, buf          ; rdi = addr. of char to process
  .capitalize_loop:

    call to_uppercase

    inc rdi
    dec rcx
    jnz .capitalize_loop  ; No cmp; dec sets ZF for us 

  ; Write syscall
  mov rdx, rax          ; rax = number of bytes read
  mov rax, SYS_write
  mov rdi, SYS_stdout
  mov rsi, buf
  syscall

  ; Exit syscall
  mov rax, SYS_exit
  mov rdi, 0
  syscall

This introduces a simple function to_uppercase which handles converting a single character to uppercase.

Conditional moves

As a solution to the problem of expensive conditional jumps, conditional moves were added. A conditional move is simply a mov which checks the flags register and only performs the mov if the flags are set according to the condition. The condition codes are the same as for conditional jumps:

Operation	Description	Flag condition
`cmove`	Move if `op1 == op2`	`ZF == 1`
`cmovne`	Move if `op1 != op2`	`ZF == 0`
`cmovl`	Move if `op1 < op2`, signed	`SF != OF`
`cmovle`	Move if `op1 <= op2`, signed	`ZF == 1 or SF != OF`
`cmovg`	Move if `op1 > op2`, signed	`ZF == 0 and SF == OF`
`cmovge`	Move if `op1 >= op2`, signed	`SF == OF`
`cmovb`	Move if `op1 < op2`, unsigned	`CF == 1`
`cmovbe`	Move if `op1 <= op2`, unsigned	`CF == 1 or ZF == 1`
`cmova`	Move if `op1 > op2`, unsigned	`CF == 0 and ZF == 0`
`cmovae`	Move if `op1 >= op2`, unsigned	`CF == 0`

Operation	Description
`cmovna`	Move if not above
`cmovnae`	Move if not above or equal
`cmovnb`	Move if not below
`cmovnbe`	Move if not below or equal
`cmovng`	Move if not greater-than
`cmovnge`	Move if not greater-than or equal
`cmovnl`	Move if not less-than
`cmovnle`	Move if not less-than or equal

Operation	Description
`cmovc`	Move if `CF == 1`
`cmovnc`	Move if `CF == 0`
`cmovz`	Move if `ZF == 1`
`cmovnz`	Move if `ZF == 0`
`cmovo`	Move if `OF == 1`
`cmovno`	Move if `OF == 0`
`cmovs`	Move if `SF == 1`
`cmovns`	Move if `SF == 0`
`cmovz`	Move if `ZF == 1`
`cmovnz`	Move if `ZF == 0`
`cmovp`	Move if `PF == 1`
`cmovpo`	Move if `PF == 1` (jump if parity odd)
`cmovpe`	Move if `PF == 0` (jump if parity even)

There are some additional restrictions on the cmov** instructions beyond those that apply to the normal mov instruction:

The destination must be a register, it cannot be a memory operand.
The source must be a register or memory operand, it cannot be an immediate.
Single-byte conditional moves are not supported at all.

For example, to take the absolute value of rax using conditional jumps we would do:

  cmp rax, 0
  jge .positive
  neg rax
.positive:
  ...

To do this with a conditional move we would do

  mov rbx, rax      ; rbx = rax
  neg rbx           ; rbx = -rax
  cmp rax, 0        
  cmovl rax, rbx   ; rax = rbx, if rax < 0

Although this might seem like more work for the processor, as we perform an extra mov and neg if when we don’t need it, but this approach may actually be faster, due to avoiding branching and keeping the execution pipeline full.

Linear search

To review looping and branching, we’re going to build a linear search function. This function will just loop through an array from beginning to end, searching for a particular value. If it finds the value, it will return the index of the value within the array; if it does not, it returns -1 (= 0xffffff… unsigned).

In C/C++ this would be

unsigned linear_search(char* buffer, unsigned length, char target) {
    unsigned i = 0;
    while(i != length) {
        if(buffer[i] == target)
            return i;

        ++i;
    }

    return -1;
}

In assembly we’re going to go through the steps of also loading the array from a file of random data, in order to introduce a few new syscalls. The existing syscalls we will use are:

read (0) – Read a specific number of bytes from a file descriptor
exit (60) – End process

The new syscalls we will use are

open (2) – Open a file. The parameters to this syscall are the (nul-terminated) filename, the file access mode (read-only, write-only, or read-write), and the file creation mode, which is ignored unless a new file is being created. open returns a file descriptor in rax, or -1 on error.
close (3) – Closes an open file descriptor. Parameter is the file descriptor (from open).

The .data section looks like this:

section .data

TARGET:         equ     126

filename:       db      "random.dat", 0         ; Filenames are nul-terminated

; 1M buffer to load the file
BUFLEN:         equ     1024*1024
buffer:         times BUFLEN    db 0

;; Syscalls
SYS_open:       equ     2
SYS_close:      equ     3
SYS_read:       equ     0
SYS_exit:       equ     60

;; File access mode
O_RDONLY:       equ     0

(The file random.dat is present on the server in /usr/local/class/cs241/random.dat. It contains 1MB of random data.)

The main steps of our program are:

Open the file random.dat
If the file opened successfully, read 1MB from the file into buffer
Close the file
Do a linear search for TARGET
Exit process, with the index returned by 4 as the exit code

Step 1 is just a matter of passing the parameters to the open syscall:

    mov rax, SYS_open
    mov rdi, filename   ; nul-terminated filename
    mov rsi, O_RDONLY   ; access mode: read only
    mov rdx, 0          ; mode: ignored if file already exists
    syscall

Step 2: If the file could not be opened, rax will be -1, so we check for this and then exit if it is the case:

    ; Check return value: -1 indicates error
    cmp rax, -1
    jne .read_file
    ; Otherwise file did not open correctly.
    ; Exit with status code 1
    mov rdi, 1
    jmp .exit

.read_file:

.exit is a label at the end of the _start function which calls the exit syscall:

.exit:
    mov rax, SYS_exit
    syscall

The .read_file: label marks the beginning of the second part of step 2:

.read_file:
    ; File is open, rax = FD
    ; Read the entire file into the buffer.
    mov rdi, rax        ; rdi = FD
    mov rax, SYS_read
    mov rsi, buffer
    mov rdx, BUFLEN
    syscall

rax contains the file descriptor returned by open, but read expects the FD to be in rdi and the syscall in rax, so we have to shuffle things around a bit.

Step 3: Once the file has been read, we can close it with just

    mov rax, SYS_close
    ; rdi still contains FD
    syscall

(rdi was set to the file descriptor in step 2, and syscalls are guaranteed to preserve rdi, so we don’t need to save it to a different register like we do with rcx.)

For step 4 we set up the parameters to the linear_search function and then call it:

    mov rdi, buffer
    mov rsi, BUFLEN
    mov dl, TARGET
    call linear_search

And then finally we move the return value of linear_search (which is in rax), into the exit code of the program (in rdi) and call SYS_exit:

    mov rdi, rax    ; Return value is exit code
.exit:
    mov rax, SYS_exit
    syscall

Note that if we jumped to .exit due to the file not opening, rdi will have been set to 1 at the beginning of step 2.

All that remains is to write the linear_search function:

linear_search:
    ; rdi = address of array
    ; rsi = length of array
    ; dl = target to search for
    ; Returns: rax = index of target, or -1 (0xffff...) if not found

    ... ; Function body

    ret

For reference, the C/C++ code we are translating is

    unsigned i = 0;
    while(i != length) {
        if(buffer[i] == target)
            return i;

        ++i;
    }

    return -1;

We have a while loop, so we initialize the loop counter (in rax, because that will eventually be our return value) to 0 and then check the condition:

    mov rax, 0

.while:
    cmp rax, rsi
    jne .not_found

    ...

.not_found:
    mov rax, -1
    ret

The .not_found label and following code corresponds to the return -1 after the end of the while loop. Within the loop, we need to compare the target (in dl) to the current array element. Although we could go to the trouble of adding rax to rdi to get the address of the current element, we’ll shortcut the process and just increment rdi along with rax, so rdi always points to the current array element. Thus, we have

        cmp dl, byte [rdi]
        jne .continue       ; Not equal: next iteration
        ret                 ; Equal, return current rax

where .continue: labels the tail end of the while loop, where we increment the index (and the address) and jump to the start of the loop:

    .continue:
        inc rax
        inc rdi
        jmp .while

The whole function looks like this:

linear_search:
    ; rdi = address of array
    ; rsi = length of array
    ; dl = target to search for
    ; Returns: rax = index of target, or -1 (0xffff...) if not found

    mov rax, 0

    .while:
        cmp rax, rsi
        je .not_found

        cmp dl, byte [rdi]
        jne .continue       ; Not equal: next iteration
        ret                 ; Equal, return current rax

    .continue:
        inc rax
        inc rdi
        jmp .while
    .not_found:
    mov rax, -1
    ret