Understanding a MIPS algorithm

Question

I'm very new into coding and we started with MIPS. We were kind of "thrown in to the cold water" and had to implement an algorithm that checks whether the elements of an array are sorted in ascending order. If it is sorted, a 1 is to be stored in $v0, otherwise a 0. The solution that was given us:

.data
A: .word 1, 2, 3, 4, 5
l: .word 5

.text
main:
la $s0, A #address of A
lw $s1, l
add $t0, $0, $0 #counter for loop
addi $v0, $0, 1
sub $s1, $s1, $v0
for:
beq $t0, $s1, done
sll $t1, $t0, 2 #byte offset
add $t1, $t1, $s0
lw $t1, 0($t1) #$t1 = A[j]
addi $t2, $t0, 1
sll $t2, $t2, 2
add $t2, $t2, $s0
lw $t2, 0($t2) #$t2 = A[j + 1]
sub $t3, $t2, $t1 #$s3 = A[j+1] - A[j]?
slt $t4, $t3, $0
addi $t3, $0, 1
beq $t3, $t4 unsort #A isn’t sorted if A[j+1] - A[j] has a negative value
addi $t0, $t0, 1 #$t0 = $t0 + 1
j for

unsort:
add $v0, $0, $0 #set $v0 if array isn’t sorted

done:

I'm having trouble understanding this code/algorithm. First of all what is an Array and why do we need specifically 5 of them? But much more important to me is understanding this code/algorithm. So I need someone who is kind enough and explains to me step by step and in simple word :D, how this code works.

Would be very helpful and thanks in advance.

Answer 1

Short answer

Basically, this program iterates over the array A in a loop with loop counter, say i. The index i is initialized with 0 and in every loop iteration incremented by 1 until it reaches l-1, where l is the size/length of the array A. In every iteration the algorithm checks if A[i] < A[i + 1] (i.e. if the i-th and the (i+1)-th element in A are in ascending order and thus are sorted). If so, it continues execution and $v0 remains 1. Otherwise it sets $v0 to 0 and terminates.

---

Long answer

Arrays and memory

An array is basically an ordered list of data – in this case it is an ordered list of words (a word in MIPS means: 32-bit value, and it consists of 4 bytes, each of which has 8 bits of information). So in this case, every word represents a 32-bit integer.
If we have an array A of length l, the elements are indexed from 0 to l-1. The first element in an array A (notation: A[0]) is saved at a certain address in memory, let's call it addr. The i-th element in A (A[i]) is then saved at the memory address addr + 4*i. This is because memory in MIPS is byte-addressable, i.e., every byte has his own address and because a word consists of 4 bytes, word addresses are offset by 4 (see below).

---

.data section

A: .word 1, 2, 3, 4, 5
l: .word 5

With that you will realize that you don't have 5 arrays but only one (called A) and it contains the values 1, 2, 3, 4 and 5. Thus, the length is 5 and it is specified in the word l. You could add more values to your array but then you would have to adjust the length because otherwise, strange things will happen (or at least the result will be random). Your data is specified in this .data section and is therefore somewhere stored in your program's memory space.

---

MIPS assembly

In order to understand the code in the .text section, you have to understand MIPS assembly. If I write about a register, just think about it as a placeholder for a 32-bit value. For example, $0 is the zero register and it always stores a 32-bit 0. Other registers are used to temporarily store values used in your program. The instructions you use are:

• la rd, label ("load address")
  (rd = address of label; stores the address of the word specified by "label" in the destination register rd)
• lw rd, label ("load word")
  or
  lw rd, offset(rs)
  (load data specified by label, or data at address rs+offset into destination register rd)
• add rd, rs, rt
  (rd = rs + rt; adds source registers rs and rt and stores result in destination register rd)
• addi rd, rs, imm ("add immediate")
  (rd = rs + imm; adds source register rs and immediate (16-bit constant) value and stores result in destination register rd)
• sub rd, rs, rt ("subtract")
  (rd = rs - rt; subtracts source register rt from source register rs and stores result in destination register rd)
• beq rs, rt, label ("branch if equal")
  (if value in rs is equal to value in rt, jump to label)
• sll rd, rs, shamt ("shift logic left")
  (rd = rs << 2; shift value in rs by two bits the left and store it in rd)
• slt rd, rs, rt ("set less than")
  (rd = (rs < rt) ? 1 : 0; if the value in rs is smaller than the value in rt, set rd to 32-bit 1, otherwise to 32-bit 0)
• j label ("jump")
  (jump to label)

---

.text section

main:
la $s0, A
lw $s1, l
add $t0, $0, $0
addi $v0, $0, 1
sub $s1, $s1, $v0

for:
beq $t0, $s1, done
sll $t1, $t0, 2 #byte offset
add $t1, $t1, $s0
lw $t1, 0($t1) #$t1 = A[j]
addi $t2, $t0, 1
sll $t2, $t2, 2
add $t2, $t2, $s0
lw $t2, 0($t2) #$t2 = A[j + 1]
sub $t3, $t2, $t1 #$s3 = A[j+1] - A[j]?
slt $t4, $t3, $0
addi $t3, $0, 1
beq $t3, $t4 unsort #A isn’t sorted if A[j+1] - A[j] has a negative value
addi $t0, $t0, 1 #$t0 = $t0 + 1
j for

unsort:
add $v0, $0, $0 #set $v0 if array isn’t sorted

done:

This assembly code is equivalent to the pseudocode (if you are not used to pseudocode or to while loops, please look it up in the internet):

s0 <- address of first element in A
s1 <- l
t0 <- 0
v0 <- 1
s1 <- s1-1

while (t0 != s1) do
    t1 <- 4 * t0
    t1 <- t1 + s0
    t1 <- word at address t1
    t2 <- t0 + 1
    t2 <- 4 * t2
    t2 <- t2 + s0
    t2 <- word at address t2
    t3 <- t2 - t1
    if (t3 < 0) then t4 <- 1
    else t4 <- 0
    t3 <- 1
    if (t3 == t4) then
        v0 <- 0
        return
    else t0 <- t0 + 1

Hope, this helped. I think it is quite ambitious to start with assembly code if you haven't coded before. Good luck!