Answers to tutorial exercises #3: MIPS assembly language programming

QUESTION 1
Here is a small program in MIPS assembly language. Mentally trace through
its execution to find out what it does. Add a comment to the end of each line
to record what the code on that line does. (Actually, a comment at the ends
of most lines is sufficient, provided you pick the right lines.)

        .data
str:    .asciiz "abcde"

        .text
        .globl  main
main:
        li      $s0, 0
        la      $s1, str
test:
        lb      $s2, 0($s1)
        beqz    $s2, done
        addi    $s0, $s0, 1
        addi    $s1, $s1, 1
        j       test
done:
        li      $v0, 1
        move    $a0, $s0
        syscall
        li      $v0, 11
        li      $a0, 10
        syscall

        jr      $ra

Hint: when you get to the code at the "done" label, look up figure A.9.1
in Hennessy & Patterson Appendix A, or table 1 in SPIM 20, both of which
are available both in the printed lecture notes and on the resources tab
on the subject's LMS page.

ANSWER
It computes and prints the length of the string in str by counting characters
until it finds the NUL character.

Here is a commented version of the code, which shows its workings in detail.

        .data
str:    .asciiz "abcde"

        .text
        .globl  main
main:
        li      $s0, 0          # len = 1
        la      $s1, str        # s = str
test:
        lb      $s2, 0($s1)     # c = *s
        beqz    $s2, done       # if c == '\0', branch to "done"
        addi    $s0, $s0, 1     # len = len + 1
        addi    $s1, $s1, 1     # s = s + 1
        j       test
done:
        li      $v0, 1          # syscall code: print_int
        move    $a0, $s0
        syscall
        li      $v0, 11         # syscall code: print_char
        li      $a0, 10         # pass newline character
        syscall

        jr      $ra

QUESTION 2
Here is another version of the same program, which differs from the previous
version only in that it replaces the instruction "addi $s1, $s1, 1"
with the four-instruction sequence starting with "la $t0, test" below.
Mentally trace through the program's execution to find out what it does.

        .data
str:    .asciiz "abcde"

        .text
        .globl  main
main:
        li      $s0, 0
        la      $s1, str
test:
        lb      $s2, 0($s1)
        beqz    $s2, done
        addi    $s0, $s0, 1

        la      $t0, test
        lw      $t1, 0($t0)
        addi    $t1, $t1, 1
        sw      $t1, 0($t0)

        j       test
done:
        li      $v0, 1
        move    $a0, $s0
        syscall
        li      $v0, 11
        li      $a0, 10
        syscall

        jr      $ra

Of the two versions of this code, which would you prefer? Give a list of
reasons for your preference.

ANSWER
It does the same task. Both programs access the current character in the string
using the instruction "lb $s2, 0($s1)". The first version goes on to the next
character by incrementing $s1. This version goes on to the next character by
replacing the 0 with 1, then the 1 with 2, and so on. It does this by
loading the lb instruction itself into a register ($t1) and incrementing it.
This increments the least significant bits of the instruction, which are the
ones that store the 16-bit immediate. This immediate, which starts out as 0,
then becomes 1, then 2, etc.

        .data
str:    .asciiz "abcde"

        .text
        .globl  main
main:
        li      $s0, 0          # len = 1
        la      $s1, str        # s = str
test:
        lb      $s2, 0($s1)     # c = *s
        beqz    $s2, done       # if c = '\0', branch to "done"
        addi    $s0, $s0, 1     # len = len + 1

        la      $t0, test       # load the address of
                                # the lb instruction into $t0
        lw      $t1, 0($t0)     # load the lb instruction into $t1
        addi    $t1, $t1, 1     # increment the instruction,
                                # and hence the 16-bit offset in it
        sw      $t1, 0($t0)     # store the incremented instruction

        j       test
done:
        li      $v0, 1          # syscall code: print_int
        move    $a0, $s0
        syscall
        li      $v0, 11         # syscall code: print_char
        li      $a0, 10         # pass newline character
        syscall

        jr      $ra

The first version is preferable for several reasons.

- It works even for strings whose length exceeds 2^15.
- It leaves the code unchanged, so if this code were made part of a larger
  program that wanted to invoke it repeatedly, those repeated invocations would
  work.
- It is conceptually much simpler.
- It is shorter.
- It is faster.

QUESTION 3
Here is a small program in MIPS assembly language. Mentally trace through
its execution to find out what it does. Add a comment to the end of each line
to record what the code on that line does. (Actually, a comment at the ends
of most lines is sufficient, provided you pick the right lines.)

        .data
        .globl str
str:    .asciiz "abccbd"

        .text
        .globl  main
main:
        li      $s0, 0
        la      $s1, str

        .globl test
test:
        lb      $s2, 0($s1)
        beqz    $s2, done
        addi    $s0, $s0, 1
        addi    $s1, $s1, 1
        j       test

        .globl done
done:
        sub     $s0, $s0, 1
        sra     $s2, $s0, 1
        la      $s3, str
        li      $s4, 0
        li      $s5, 0

        .globl test2
test2:
        sgt     $t0, $s4, $s2
        bgtz    $t0, done2

        add     $t1, $s3, $s4
        lb      $t3, 0($t1)

        add     $t2, $s3, $s0
        sub     $t2, $t2, $s4
        lb      $t4, 0($t2)

        sne     $t5, $t3, $t4
        add     $s5, $s5, $t5

        li      $v0, 11
        move    $a0, $t3
        syscall

        li      $v0, 11
        move    $a0, $t4
        syscall

        li      $v0, 1
        move    $a0, $t5
        syscall

        li      $v0, 11
        li      $a0, 10
        syscall

        addi    $s4, $s4, 1
        j       test2

        .globl done2
done2:
        li      $v0, 1
        move    $a0, $s5
        syscall

        li      $v0, 11
        li      $a0, 10
        syscall

        jr      $ra

ANSWER
The program checks whether the string at location "str" is a palindrome or not,
i.e. whether it has the same sequence of characters forwards and backwards.

The way it does this is by first computing its length, and then looping over
the first half of the string. When looking at the nth character from the
front of the string, the program compares it to the nth character from the end,
and expresses the result of the comparison as a number: 0 if they are the same,
1 if they are different. (This is done by the "sne" instruction and the
instructions before it that prepare its input.) The program then adds up
these numbers in $s5. At the end, $s5 contains the number of character
positions at which the nth character from the front differs from the nth
character from the end. If the string is a palindrome, this will be zero;
otherwise, it will be greater than zero.

Here is a commented version of the code:

        .data
        .globl str
str:    .asciiz "abccbd"

        .text
        .globl  main
main:
        li      $s0, 0          # len = 1
        la      $s1, str        # s = str
        .globl test
test:
        lb      $s2, 0($s1)     # c = *s
        beqz    $s2, done       # if c = '\0', branch to "done"
        addi    $s0, $s0, 1     # len = len + 1
        addi    $s1, $s1, 1     # s = s + 1
        j       test

        .globl done
done:

# $s0: len
# $s2: limit
# $s3: str
# $s4: i
# $s5: sum of differences

        sub     $s0, $s0, 1     # len = len - 1
                                # first character is at offset 0, not 1
        sra     $s2, $s0, 1     # limit = len / 2
        la      $s3, str        # s = str
        li      $s4, 0          # i = 0
        li      $s5, 0          # sum = 0

        .globl test2
test2:
        sgt     $t0, $s4, $s2   # is i > limit?
        bgtz    $t0, done2      # if yes, goto done2

        add     $t1, $s3, $s4   # load s[i]
        lb      $t3, 0($t1)

        add     $t2, $s3, $s0   # load s[len - i]
        sub     $t2, $t2, $s4
        lb      $t4, 0($t2)

        sne     $t5, $t3, $t4   # compute difference
        add     $s5, $s5, $t5

        li      $v0, 11         # print_char
        move    $a0, $t3
        syscall

        li      $v0, 11         # print_char
        move    $a0, $t4
        syscall

        li      $v0, 1          # print_int
        move    $a0, $t5
        syscall

        li      $v0, 11         # print_char
        li      $a0, 10
        syscall

        addi    $s4, $s4, 1     # i = i + 1
        j       test2

        .globl done2
done2:
        li      $v0, 1          # print_int
        move    $a0, $s5
        syscall

        li      $v0, 11         # print_char
        li      $a0, 10
        syscall

        jr      $ra