[MIPS] Arrays and Strings

"MEMORY is a large single-dimensional array, with the address acting as the index"

Arrays

Since an integer takes up a word, an integer array can be represented through a sequence of words in memory. 1 word is 4 bytes of memory, so the byte address of an integer element is always 4 bytes greater than that of the previous element in the array. Note that in MIPS, therefore all words start at addresses that are multiples of 4. 

 

Addresses of array elements increment by 4

Say that there is an array A with integer elements A[0]...A[n]. The base address of the array is where A[0] is located. Since byte addresses of integer elements increment by 4, the offset for the location of some element A[i] is calculated as 4*i. 

The byte address of A[i] = offset + base address = 4*i + base address

 

Assume $s3 is the base register of A, or that $s3 stores the base address of A. The address of A[i] can be represented in the form offset(base register). For example, the address of A[3] is represented as 12($s3). 

Accessing and printing A[8]:

#$s0 = base address of array A
#$s1 = index of A = 8
la $s0, A
addi $s1, $zero, 8

#$t1 = offset 
addi $t1, $s1, $zero #$t1 = 8
sll $t1, $t1, 2	#$t1 = $t1 * 2^2 = 8*4

#$t2 = offset + $s0 = the address of A[8]
add $t2, $s0, $t1

#$t3 = data stored in A[8] 
lw $t3, 0($t2)

#print A[8]
add $a0, $t3, $zero
li $v0, 1
syscall

Strings

A string is an array of ASCII characters. A character occupies 1 byte of memory, so a string can be represented as a sequence of bytes in memory. Each character in a string can be accessed by incrementing 1 byte at a time, NOT 4 bytes like when iterating through an integer array. A string is terminated with a null char, which is 0 in ASCII. 

Finding the index of an element in A: 

#$t0 = the address of element A[i]
#$t1 = index i (0, 1, ...n-1)
#$t2 = target element

forloop:
	#$t3 = A[i] 
	lb $t3, ($t0)

	#branch to 'notfound' if iteration is over, which is when $t3 == null char 
	beq $t3, $zero, notfound
    
	#branch to 'found' if $t3 == target
	beq $t3, $t2, found 

	#increment $t0 and $t1  
	addi $t0, $t0, 1 
	addi $t1, $t1, 1 

	j loop

 

Note that we used lb instead of lw to access individual characters. The full code for the above snippet is provided below. 

.data 
arrayA: .asciiz "ABCDE" 
msg: .asciiz "Element not found" 

.text
main: 
	#$s3 = the base address of array A
	la $s3, arrayA 

	#$t0 = the address of element A[i]
	#$t1 = index i (0, 1, ...n-1)
	#$t2 = target element
    
	add $t0, $s3, $zero
	add $t1, $zero, $zero #i = 0
	addi $t2, $zero, 'E'

forloop:
	#$t3 = A[i] 
	lb $t3, ($t0)

	#branch to 'notfound' if iteration is over, which is when $t3 == null char 
	beq $t3, $zero, notfound
    
	#branch to 'found' if $t3 == target
	beq $t3, $t2, found 

	#increment $t0 and $t1  
	addi $t0, $t0, 1 
	addi $t1, $t1, 1 

	j loop 

found: 
	#print int value stored in $t0 
	add $a0, $t1, $zero
	li $v0, 1
	syscall
	
	#terminate
	li $v0, 10		
	syscall
	
notfound: 
	#print error message 
	la $a0, msg 
	li $v0, 4
	syscall

	#terminate
	li $v0, 10		
	syscall