Skip to main content

Section D.3 Exercise Sheet 3

1. Mixed Bag.

This exercise deals with important terms and concepts from the script.

  1. What is the difference between $1 and 1 in a MIPS instruction?

  2. Which categories of MIPS instructions exist?

  3. Why are there four addition instructions add, addi, addu and addiu?

  4. What is .text? Which other directives have you learned or can you find in the script?

  5. What purpose does for example blub: serve in MIPS? Which disadvantages do absolute values have when used instead of labels in instructions?

202207281550

202204291400
Solution.
  1. $1 designates a register, whereas 1 is a constant.

  2. The lecture discussed four categories in total:

    • Computational instructions: With these instructions, computational operations on registers are realized. For example: addu, subu, and, slt.

    • Memory instructions: These transfer data between the memory and the registers. For example: lw, lh, sb.

    • Branch instructions: With these instruction, the program's next instruction is influenced by conditionally changing the program counter. Other instructions than the one after the current instruction can be targeted and jumped to. For example beq, bne, jr.

    • Pseudo instructions: Instructions which exist to make the programmer's life easier. They can be expressed as several primitive instructions. For example: li, la, not.

  3. There are two main reasons as to why these instructions exist. An i (immediate) is used when a register and a constant is used instead of two registers. A u means that the result of an addition shall be interpreted as unsigned, in which case a signed overflow does not throw an exception in contrast to add. If no overflow occurs, addu and add behave equally. If we for example assume 4-bit integers, then we can represent the numbers 0-15 using unsigned interpretation, and the numbers -8 to 7 using signed interpretation.

    unsigned signed
    1 0 0 1 9 -7
    + 0 0 1 1 3 3
    = 1 1 0 0 12 -4
    \(\rightarrow\) No signed overflow, so add and addu behave equally.

    unsigned signed
    0 1 1 0 6 6
    + 0 0 1 1 3 3
    0 1 1 0
    = 1 0 0 1 9 -7
    \(\rightarrow\) Signed overflow (\(6+3 = -7\)), resulting in an exception of add. With unsigned interpretation, the result is correct and addu does not raise an exception. A signed overflow can easily be identified using the last two carry bits (read from right to left). If the bits differ, a signed overflow occured, otherwise this is not the case.

    unsigned signed
    1 1 1 1 15 -1
    + 1 1 0 0 12 -4
    1 1 0 0
    = 1 0 1 1 11 -5
    \(\rightarrow\) No signed overflow, so add and addu behave the same and no exception is raised. However, when inspecting the unsigned result, one notices that an unsigned overflow has occured (\(15+12=11\)). Thus, when working with unsigned numbers, one has to manually identify such overflows. This is however easy check, as an unsigned overflow occured if the result is smaller than one of the operands (unsigned comparison!). Here, we have \(11 < 15\text{,}\) so an overflow occured.

    unsigned signed
    1 0 0 1 9 -7
    + 1 0 1 0 10 -6
    1 0 0 0
    = 0 0 1 1 3 3
    \(\rightarrow\) Signed overflow, causing add to raise an exception, which addu does not raise. However, an unsigned overflow also occurs.

  4. The directive .text marks the start of the code segment. Another special directive is .data, which marks the start of the data segment. There are also the directives .ascii, .asciiz, .byte, .half, .word, which all store objects of a specific size in memory. To allocate storage, the directive .space can be used. With .align, the next data entry is aligned. Lastly, .globl makes a symbol visible for other files.

  5. Labels are used to mark points in the code to which branch instructions can jump. They serve as an aid for the programmer to make the code more readable. If a program is written without labels, the program becomes hard to maintain. For example, if an instruction is added in code which uses absolute values for jump targets, then it may be that the addresses are incorrect after the instruction is inserted.

2. Register Contents.

In the following table, 32-bit register contents are listed, either in hexadecimal or binary representation. Fill in the missing table entries. Don't forget that 4 bits in binary correspond to 1 digit in hexadecimal.

Binary Hexadecimal
11111111 00000000 11110000 10101010 FF 00 F0 AA
11001010 11111110 10111010 10111110
32 AB 03 1F
202207281550

202204291400
Solution.
Binary Hexadecimal
11111111 00000000 11110000 10101010 FF 00 F0 AA
11001010 11111110 10111010 10111110 CA FE BA BE
00110010 10101011 00000011 00011111 32 AB 03 1F

3. Buggy.

In this exercise you must find the errors in a MIPS program (see buggy.zip). Find the errors and correct them. There are two errors per exercise. First, try to solve the exercise without using MARS.

  1. In buggyProgram1.asm, all numbers in an array are supposed to be added and the results should be printed to the console.

  2. A fellow student asks for your help. He tried to write down the faculty program from the lecture by himself, but for some reason it does not work. His attempt can be found in buggyProgram2a.asm and buggyProgram2b.asm.

Remark: To test these programs in MARS, copy them into the same directory and select the options Assemble all files in directory and Initialize Program Counter to global 'main' if defined in the settings of MARS.

202207281550

202204291400
Solution.
  1. The end address of the array is incorrect. A word is four bytes, to access the last element of the array we need to point to the address behind the fourth word, i.e. address of the first word plus 4 * 4 = 16.

    addiu $a2 $a1 4     # wrong
    addiu $a2 $a1 16    # correct
    

    The data is stored as words, but is loaded as bytes. To load words, one must use lw instead of lb.

    lb $t0 0($a1)       # wrong
    lw $t0 0($a1)       # correct
    

  2. The subroutine fac did not make its definition visible to external programs, therefore it cannot be used by main.

    .globl fac          # insert below .text
    

    The loop counts from n to 0, which causes the result to be always zero.

    bgez $a0 loop      # wrong
    bgtz $a0 loop      # correct
    

4. Pseudo Instructions.

The MIPS assembler offers a variety of pseudo-instructions. These are helpful instructions which are not implemented in hardware, but can easily be expressed as one or two existing instructions. Specify the implementations of the pseudo-instructions blt, bgt, ble, neg, not, bge, li, la, lw, move, sge and sgt.

202207281550

202204291400
Solution.
  • blt $t8 $t9 label:

    slt $at $t8 $t9
    bne $at $zero label
    

  • bgt $t8 $t9 label:

    slt $at $t9 $t8
    bne $at $zero label
    

  • ble $t8 $t9 label:

    slt $at $t9 $t8
    beq $at $zero label
    

  • neg $t8 $t9:

    sub $t8 $zero $t9
    

  • not $t8 $t9:

    nor $t8 $t9 $zero
    

  • bge $t8 $t9 label:

    slt $at $t8 $t9
    beq $at $zero label
    

  • li $t8 i: An instruction can contain an immediate that is at most 16 bits long. Hence, the constant must be split in two halves and copied in the register when it is larger.

    \begin{gather*} i = \langle b_{31} \cdots b_{0} \rangle\\ i_u = \langle b_{31} \cdots b_{16} \rangle\\ i_l = \langle b_{15} \cdots b_{0} \rangle \end{gather*}

    If \(i < 2^{16} - 1\text{:}\)

    ori $t8 $zero i
    

    If \(i \ge 2^{16} - 1\text{:}\)

    lui $at iu
    ori $t8 $at il
    

  • la $t8 i($t9):

    ori $at $zero i
    add $t8 $t9 $at
    

  • lw $t8 add: Depending on the size of the address, it must be loaded in two steps, similar to li.

  • move $t8 $t9:

    addu $t8 $zero $t9
    

  • sge $t8 $t9 $t1:

    slt $at $t9 $t1
    xori $t8 $at 1
    

  • sgt $t8 $t9 $t1:

    slt $t8 $t1 $t9
    

5. Code Comprehension.

Take a look at the following MIPS program. Try to solve this exercise without using MARS.

main:
  li $a1 5
  li $a2 10
  li $a3 7
  
  sltu $t1 $a1 $a2
  beqz $t1 case2
  
case1:
  sltu $t1 $a2 $a3
  beqz $t1 reta2
  b reta3

case2:
  sltu $t1 $a3 $a1
  beqz $t1 reta3
  b reta1

reta1:
  addu $a0 $0 $a1
  b end

reta2:
  addu $a0 $0 $a2 
  b end
  
reta3:
  addu $a0 $zero $a3
  b end
  
end:
  li $v0 1
  syscall
  li $v0 10
  syscall
  1. What value is stored in register $a0 after execution of this code?

  2. What does the program compute for general values in $a1, $a2 and $a3 (assuming the program loads different values into the registers in lines 2-4)?

  3. Two of the instructions can be stripped from the program without changing the semantics (for arbitrary values of $a1, $a2 and $a3). Which lines can be removed?

202207281550

202204291400
Solution.
  1. 10

  2. The maximum of the three numbers.

  3. The branches in line 17 and 28, since they only jump to the next instruction.

6. Alignment.

Take a look at the following program:

.data
msg: .byte 'P','r','o','g',0
num: .byte 2,0,0,0

.text
la $a0 msg
li $v0 4 #Print string (syscall 4)
syscall
lw $a0 num
li $v0 1 #Print integer (syscall 1)
syscall
  1. Why does the execution of the program fail? Find the error and fix the program so that is print the message "Prog2".

  2. Is it possible to fix the alignment of num using .space? Explain!

  3. Find another possiblity to load the number \(2\) from the data segment without changing the alignment of num.

  4. Challenge: The student Konrad Clever has a revolutionary idea: A program that loads a word into a register without assuming that the memory address loaded from is correctly aligned. Unfortuantely, he has lost his notes on which he wrote his code. Can you help him?

    Hint: Utilize shifts.

    You may use the following code skeleton:

    .data
    .space 1
    word:
    .byte 4,3,2,1
    
    .text
    la $a0 word
        
    #TODO Load word at label word (0x01020304)
        
    li $v0 1
    syscall
    

    The correct program prints the number \(16909060\text{.}\)

202207281550

202204291400
Solution.
  1. The program fails because it attempts to load a word at a memory address which is not divisible by 4. Hence, a .align 2 must be inserted, such that the label num is now located at an address divisible by 4. (Reminder: .align n makes sure that the next instruction is located at a memory address divisible by \(2^n\text{!}\))

    .data
    msg: .byte 'P','r','o','g',0
    .align 2
    num: .byte 2,0,0,0
    
    .text
    la $a0 msg
    ...
    
  2. Yes, this is possible by inserting a .space 3 at the same spot, since this inserts three bytes of space behind the fifth byte of msg and aligns the next line by 4 in the process. Nevertheless, alignment by .align should be preferred, as the alignment still stays correct after the program is modified, which may not be the case for .space.

  3. One possibility is to use lb instead of lw to load the number \(2\) from memory:

    .data
    msg: .byte 'P','r','o','g',0
    num: .byte 2,0,0,0
    
    .text
    la $a0 msg
    li $v0 4 #Print string (syscall 4)
    syscall
    lb $a0 num
    li $v0 1 #Print integer (syscall 1)
    syscall
    

    This only works because 2, the number we want to load, fits into a byte. If we wanted to load a number \(x\) such that \(x \lt -128 \vee x \gt 127\text{,}\) this would not work.

  4. One solution would be the following program:

    .data
    .space 1
    word: .byte 4,3,2,1
    
    .text
    la $t0 word
    
    lb $a0 0($t0)
    lb $t1 1($t0)
    sll $t1 $t1 8
    or $a0 $a0 $t1
    lb $t1 2($t0)
    sll $t1 $t1 16
    or $a0 $a0 $t1
    lb $t1 3($t0)
    sll $t1 $t1 24
    or $a0 $a0 $t1
    
    li $v0 1
    syscall
    

7. Interpretation and Storage of Binary Data.

The following memory footprint of a MIPS program shows the content of the memory starting from address 0x10000000. It contains the personal data of a student. In the following illustration, four MIPS words in hexadecimal representation are displayed per row, 16 bytes in total.

Memory address Content of memory
0x10000000 74733973 64757473 07d00c19 fffffde8
0x10000010 42464e49 00000003 00000000 00000000
  1. Which values are stored if we assume the following interpretations? Remember that in MIPS, the first byte of a multi-byte number contains the least sigificant bits (little endian).
    Offset Interpretation
    0-7 s9-identification (8 ASCII characters)
    8 Birthday: Day (unsigned, 1 byte)
    9 Birthday: Month (unsigned, 1 byte)
    10-11 Birthday: Year (unsigned, 2 bytes)
    12-15 Semester fee (signed, 4 bytes)
    16-18 Course of studies (3 ASCII characters)
    19 Graduation degree (1 ASCII character)
    20 Term of studying (unsigned, 1 byte)
  2. Write down the data definitions (.data) which lead to this memory layout. Validate the effect of the data definitions in MARS.

202207281550

202204291400
Solution.
  1. The values:

    Offset Interpretation Values
    0-7 s9-identification (8 ASCII characters) "s9ststud"
    8 Birthday: Day (unsigned, 1 byte) 0x19 (25)
    9 Birthday: Month (unsigned, 1 byte) 0x0c (12)
    10-11 Birthday: Year (unsigned, 2 bytes) 0x07d0 (2000)
    12-15 Semester fee (signed, 4 bytes) 0xfffffde8 (-536)
    16-18 Course of studies (3 ASCII characters) "INF"
    19 Graduation degree (1 ASCII character) "B"
    20 Term of studying (unsigned, 1 byte) 0x03 (3)
  2. The data definitions:

    .data
    .ascii "s9ststud"    # sequence of 8 chars, 8 bytes
    .byte  25            # unsigned integer, 1 byte
    .byte  12            # unsigned integer, 1 byte
    .half  2000          # unsigned integer, 2 bytes
    .word  -536          # signed integer, 4 bytes
    .ascii "INF"         # sequence of 3 chars, 3 bytes
    .ascii "B"           # char, 1 byte
    .byte  3             # unsigned integer, 1 byte
    

8. Conditional Branch (or not).

Write an assembler program which calculates the absolute value of a 32-bit value from the data segment and prints it to the console. Assume that the value resides at the memory address with label number.

  1. Implement the program using a branch.

  2. Implement the program without using a branch.

.data
number:
  .word -2147

.text
#Your solution goes here

202207281550

202204291400
Solution.
  1. With branch:

    .data
    number:
      .word -2147
    
    .text
      lw $a0 number
      bgez $a0 exit
      subu $a0 $0 $a0
    exit:
      li $v0 1 #Output
      syscall
      li $v0 10
      syscall
    
  2. Without branch:

    .data
    number:
      .word -2147
    
    .text
      lw $a0 number
      # $a0 >= 0        $a0 < 0
    
      sra  $t0 $a0 31 
      # $t0  = 0...0    $a0 < 0: $t0  = 1...1
    
      xor  $a0 $a0 $t0 
      # $a0 ^ 0 = $a0,$a0 xor 1...1 = one's complement $a0
    
      subu $a0 $a0 $t0 
      # $a0 -= 0 = $a0, $a0 -= -1 -> two's complement $a0 
    
      li $v0 1
      syscall
      li $v0 10
      syscall
    

9. RGB Basics.

You receive an unsigned number representing an RGB value in register $a0. Extract the individual color values, negate them and print them to the console. A color is negated by replacing each color value \(x\) by \(255 - x\text{.}\)

Hint: A number in the RGB format contains one component value in between 0 and 255 for the primary colors red, green and blue. The component values are specified successively in this order.

Example: The following bit string represents an RGB value with the red component of 50, a green component of 100 and a blue component of 150:

\begin{equation*} 00000000 \ \underbrace{00110010}_{red} \ \underbrace{01100100}_{green} \ \underbrace{10010110}_{blue} \end{equation*}

Note that the first 8 bits are always zero. When we negate these values, we obtain a red component of 205, a green component of 155 and a blue component of 105, i.e. the RGB color:

\begin{equation*} 00000000 \ \underbrace{11001101}_{red} \ \underbrace{10011011}_{green} \ \underbrace{01101001}_{blue} \end{equation*}

What do you notice when looking at this example? Does your observation hold for all colors? Why?

202207281550

202204291400
Solution.

The individual bits are just flipped. This holds for all values, since 255 is the largest value that is representable by unsigned interpretation of 8 bits.

# negated input
li $t0 0x00FFFFFF
sub $a0 $t0 $a0
# copy negated input argument into a1
move $a1 $a0

# shift red component value
srl $a0 $a0 16
# print
li $v0 1
syscall

# copy negated argument back into a0
move $a0 $a1
# shift green component value back
sll $a0 $a0 16
srl $a0 $a0 24
# print
syscall

# copy negated argument back into a0
move $a0 $a1
# shift blue component value back
sll $a0 $a0 24
srl $a0 $a0 24
# print
syscall

10. String Reversal.

Write a program which reverses a null-terminated ASCII string. You receive the starting address of the string in $a0 and the starting address of the buffer to write the reversed string into in $a1. You may assume that the buffer is big enough.

If you have trouble with this exercise, consider the following hints:

  1. Recall what the special properties of a string are.

  2. Start by writing the part of the program that searches for the end of the string.

  3. Now write another part of the program which copies the characters from one address to another.

  4. Connect the pieces in a sensible manner. Remember to correctly exit the program.

202207281550

202204291400
Solution.

The following program is correct:

.text
  move     $t0 $a0         # save start address

# ---b---
loop_scan:
  lbu      $t1 ($t0)
  addiu    $t0 $t0 1       # look at next character
  bnez     $t1 loop_scan   # end of string reached?


found_end:
  addiu    $t0 $t0 -2      # last character of input

# ---c/d---
loop_write:
  bltu     $t0 $a0 finish  # back to start of string?
    
  lbu      $t1 ($t0)       # copy char into buffer
  sb       $t1 ($a1)
  addiu    $t0 $t0 -1      # go to next character
  addiu    $a1 $a1 1

  j        loop_write

# ---d---
finish:
  sb       $zero ($a1)     # end string with 0

  li       $v0 10          # exit program
  syscall

11. Stack Frames.

Take a look at the MIPS program below.

.text
    .globl confusion
confusion:
    and      $t0 $t0 $zero
    or       $t0 $t0 $a0
    add      $t1 $a1 $t0
    or       $s1 $t0 $t1
    move     $s0 $t0
    jal      mystery
    add      $t0 $t1 $v0
    add      $v0 $a0 $t0
    jr       $ra
Listing D.3.1. A program that disregards the calling convention.
  1. Change the program such that it respects the calling convention. Try to be as memory-efficient as possible, i.e. only save the necessary registers. State which instructions must be inserted between which line numbers.

  2. Sketch a depiction of the stack prior to execution of the instruction jal mystery. Also specify the address of the stack pointer at this point. Assume that the stackpointer has a value of 0x7ffffffc before confusion is called. To this end, complete the table below.

    Address Saved register
    0x7ffffffc -
    ... ...
  3. Explain why you must save the registers in such a "long-winded" manner. Would it not be easier if a subroutine foo would store its registers at a fixed place in the static part of the data segment?

202207281550

202204291400
Solution.
  1. Prologue between line 3 and 4:
    addiu    $sp $sp -8
    sw       $s0 ($sp)
    sw       $s1 4($sp)
    
    Saving of registers between line 8 and 9:
    addiu    $sp $sp -12
    sw       $t1 ($sp)
    sw       $a0 4($sp)
    sw       $ra 8($sp)
    
    Loading of registers between line 9 and 10:
    lw       $t1 ($sp)
    lw       $a0 4($sp)
    lw       $ra 8($sp)
    addiu    $sp $sp 12
    
    Epilogue between line 11 and 12:
    lw       $s0 ($sp)
    lw       $s1 4($sp)
    addiu    $sp $sp 8
    
  2. Address Saved register
    0x7ffffffc -
    0x7ffffff8 $s1
    0x7ffffff4 $s0
    0x7ffffff0 $ra
    0x7fffffec $a0
    0x7fffffe8 $t1
    The address of the stack pointer is: 0x7fffffe8.
  3. Recursive subroutines would overwrite their data from a previous call this way.

12. The Sieve of Eratosthenes.

Given the natural numbers from 1 to 49, sift out the prime numbers using the sieve of Eratosthenes Algorithm discussed in Chapter 3.2. Start by filling a table with the numbers from 1 to 49.

202207281550

202204291400
Solution.
This is the inital table.
\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|} \hline 1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \\ \hline 8 \amp 9 \amp 10 \amp 11 \amp 12 \amp 13 \amp 14 \\ \hline 15 \amp 16 \amp 17 \amp 18 \amp 19 \amp 20 \amp 21 \\ \hline 22 \amp 23 \amp 24 \amp 25 \amp 26 \amp 27 \amp 28 \\ \hline 29 \amp 30 \amp 31 \amp 32 \amp 33 \amp 34 \amp 35 \\ \hline 36 \amp 37 \amp 38 \amp 39 \amp 40 \amp 41 \amp 42 \\ \hline 43 \amp 44 \amp 45 \amp 46 \amp 47 \amp 48 \amp 49 \\ \hline \end{array} \end{equation*}
No we cross out all the multiples of 2.
\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|} \hline 1 \amp 2 \amp 3 \amp \amp 5 \amp \amp 7 \\ \hline \amp 9 \amp \amp 11 \amp \amp 13 \amp \\ \hline 15 \amp \amp 17 \amp \amp 19 \amp \amp 21 \\ \hline \amp 23 \amp \amp 25 \amp \amp 27 \amp \\ \hline 29 \amp \amp 31 \amp \amp 33 \amp \amp 35 \\ \hline \amp 37 \amp \amp 39 \amp \amp 41 \amp \\ \hline 43 \amp \amp 45 \amp \amp 47 \amp \amp 49 \\ \hline \end{array} \end{equation*}
No we cross out all the multiples of 3.
\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|} \hline 1 \amp 2 \amp 3 \amp \amp 5 \amp \amp 7 \\ \hline \amp \amp \amp 11 \amp \amp 13 \amp \\ \hline \amp \amp 17 \amp \amp 19 \amp \amp \\ \hline \amp 23 \amp \amp 25 \amp \amp \amp \\ \hline 29 \amp \amp 31 \amp \amp \amp \amp 35 \\ \hline \amp 37 \amp \amp \amp \amp 41 \amp \\ \hline 43 \amp \amp \amp \amp 47 \amp \amp 49 \\ \hline \end{array} \end{equation*}
We do not need to consider the multiples of 4 because every multiple of 4 is also a multiple of 2 and thus already crossed out. So now we cross out all the multiples of 5.
\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|} \hline 1 \amp 2 \amp 3 \amp \amp 5 \amp \amp 7 \\ \hline \amp \amp \amp 11 \amp \amp 13 \amp \\ \hline \amp \amp 17 \amp \amp 19 \amp \amp \\ \hline \amp 23 \amp \amp \amp \amp \amp \\ \hline 29 \amp \amp 31 \amp \amp \amp \amp \\ \hline \amp 37 \amp \amp \amp \amp 41 \amp \\ \hline 43 \amp \amp \amp \amp 47 \amp \amp 49 \\ \hline \end{array} \end{equation*}
We do not need to consider the multiples of 6 because every multiple of 6 is also a multiple of 2 and thus already crossed out So now we cross out all the multiples of 7.
\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|} \hline 1 \amp 2 \amp 3 \amp \amp 5 \amp \amp 7 \\ \hline \amp \amp \amp 11 \amp \amp 13 \amp \\ \hline \amp \amp 17 \amp \amp 19 \amp \amp \\ \hline \amp 23 \amp \amp \amp \amp \amp \\ \hline 29 \amp \amp 31 \amp \amp \amp \amp \\ \hline \amp 37 \amp \amp \amp \amp 41 \amp \\ \hline 43 \amp \amp \amp \amp 47 \amp \amp \\ \hline \end{array} \end{equation*}
We know that we can stop crossing out as soon as we reach the square root of 49. Thus the prime numbers between 1 and 49 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

13. The Tortoise and the Hare.

Take a look at the MIPS program below.

  1. How do linked lists work in MIPS? Complete the following program, which should add up all the numbers, contained in the linked list and print the result on the console.
    .text
    # $a0: address of first element
    
    add_numbers:
    
        # TODO
    
  2. Now, you should implement an algorithm, that checks, if a linked list ends in a cycle. The algorithm you should use is called "the tortoise and the hare".

    "In each step, the tortoise advances one list element and the hare advances two elements. Now, the claim is that the tortoise and the hare meet (both pointers are equal) if and only if the list ends in a cycle. It is straightforward that they never meet if there is no cycle. But why do they meet if there is a cycle?

    Assume that the list has \(n\) elements and ends in a cycle of \(l\) nodes. So, after \(n-l\) steps, the tortoise reaches element \(0\) of the cycle. This element is the only element to which a pointer from outside the cycle points to. Assume that the hare is at element \(d\) of the cycle. Now, in each step the distance from hare to tortoise will decrease by one. (The hare is in fact moving one element away from the tortoise in each step, but because they run on the cycle, it is actually moving closer.) So, after \(l-d\) steps they stand on the same element."

    .text
    .globl tortoise_and_hare
      
    # $a0: address of first element
    
    tortoise_and_hare:
        # $a0 Hare
        # $a1 Tortoise
        move  $a1 $a0
    loop:
      
          # TODO 
    
    cyclic:  
        li  $v0 1
        jr  $ra
    not_cyclic:
        li  $v0 0
        jr  $ra
    
  3. Change your algorithm, so that the hare advances 3 instead of 2 steps each time. Also you can write a main function to test your implementation with an example list.

  4. Does that still work in all cases (every circle length)? Justify your answer. If you think, this cobination does work for all cases, can you find one where it does not?

202207281550

202204291400
Solution.
  1. The following code is correct:

    .text
    # $a0: address of first element
    
    add_numbers:
        move  $t0  $a0
        li  $t2 0         # result
    loop:
        lw  $t1 ($t0)     # element
        add $t2 $t2 $t1   
        lw  $t0 4($t0)    # next address
        beqz  $t0 end
        b loop
    end:
        li  $v0 1
        move  $a0 $t2
        syscall
    
  2. Please, have a look at the script at chapter 3.5.

  3. The following code is correct:

    .text
    .globl tortoise_and_hare
      
    # $a0: address of first element
    tortoise_and_hare:
        # $a0 Hase
        # $a1 Igel
        move  $a1 $a0
    loop:
        beqz  $a0 not_cyclic
        lw  $a0 4($a0)
        beqz  $a0 not_cyclic
        lw  $a0 4($a0)
        beqz  $a0 not_cyclic
        lw  $a0 4($a0)
        lw  $a1 4($a1)
        beq  $a0 $a1 cyclic
        b  loop
    cyclic:  
        li  $v0 1
        jr  $ra
    not_cyclic:
        li  $v0 0
        jr  $ra
    
        .data
    L1:
        .word 1
        .word L6
    L2:
        .word 2
        .word L4
    L3:
        .word 3
        .word L5
    L4:
        .word 4
        .word L3
    L5:
        .word 5
        .word 0
    L6:
        .word 6
        .word L2
      
    .text
    .globl   main
    main:
        la      $a0 L1
        jal     tortoise_and_hare
        move    $a0 $v0
        li      $v0 1
        syscall
        li      $v0 10
        syscall
    
  4. Yes, it does. The algorithm does only work if the greatest common divisor of the stepsize of tortoise and hare is not a divisor (or 1) of the length of the circle. Since the greatest common divisor of 1 and 3 is 1, this condition is fullfilled.

    So, yes, there exist combinations where the algorithm fails e.g. if the stepsize of the tortoise is 2 and the one for the hare is 4, we will not be able to find cycles with even size.