Vectors: indexing by position

A vector is an array: a sequence of numbers stored next to each other in memory. In the previous lesson you summed one by moving a pointer forward 4 bytes for each element. That same method works here. There is another common way to reach an element: by index. An index is the position of an element counted from the start, where the first element has index 0, the second has index 1, and so on.

Summing a vector by walking a pointer

.data
a: .word 5, 10, 15, 20 # four elements
.text
la   t0, a # t0 = address of a
li   t1, 4 # t1 = number of elements left
li   t2, 0 # t2 = running total
loop:
  beq  t1, zero, done
  lw   t3, 0(t0) # load current element
  add  t2, t2, t3 # add to total
  addi t0, t0, 4 # advance to next word (4 bytes)
  addi t1, t1, -1 # one fewer left
  j loop
done:
  mv a0, t2 # print total: 5+10+15+20 = 50
  li a7, 1
  ecall
  li a7, 10
  ecall

The loop runs as follows. t0 holds the address of a, and t1 holds the number of elements remaining, starting at 4. On each pass, beq t1, zero, done ends the loop when the count reaches zero. lw t3, 0(t0) loads the element at the address in t0. add t2, t2, t3 adds that value to the running total. addi t0, t0, 4 advances the pointer to the next word. addi t1, t1, -1 decreases the count. After four passes (5 + 10 + 15 + 20), done prints 50. This is the same pattern used in the memory lesson, now applied to a vector.

From index to address

Indexing computes an address from a base pointer and a position: address = base + index * 4. The 4 is the size of a word in bytes. A compiler generates this same computation for a[i] in a language such as C. The index itself never accesses memory. Only the address computed from it does.

slli t5, t3, 2 # t5 = index * 4 (word size)
add  t6, t0, t5 # t6 = address of element[index]
lw   t6, 0(t6) # t6 = element[index]

slli t5, t3, 2 shifts the index in t3 left by 2 bits, which multiplies it by 4 (two doublings: 2 x 2), the size of one word. Adding the result to the base pointer gives the address of element[index]. This shift is the same power-of-two method from the arithmetic lesson, and it is the standard way to scale an index by the size of a word.

Summing a vector by index

.data
a: .word 5, 10, 15, 20 # four elements
.text
la   t0, a # t0 = base address of a
li   t1, 4 # t1 = number of elements
li   t2, 0 # t2 = index, starts at 0
li   t3, 0 # t3 = running total
loop:
  beq  t2, t1, done
  slli t4, t2, 2 # t4 = index * 4 (byte offset)
  add  t5, t0, t4 # t5 = address of a[index]
  lw   t5, 0(t5) # t5 = a[index]
  add  t3, t3, t5 # total += a[index]
  addi t2, t2, 1 # move to the next index
  j loop
done:
  mv a0, t3 # print total: 5+10+15+20 = 50
  li a7, 1
  ecall
  li a7, 10
  ecall

The loop runs as follows. t2 is the index, starting at 0. On each pass, beq t2, t1, done ends the loop when the index reaches 4, the element count held in t1. slli t4, t2, 2 converts the index to a byte offset. add t5, t0, t4 adds that offset to the base address in t0 to produce the address of a[index]. lw t5, 0(t5) loads the value stored there. That value is added to the running total in t3, and addi t2, t2, 1 advances to the next index. After four passes (5 + 10 + 15 + 20), done prints 50.

Adding two vectors, element by element

.data
a: .word 3, 6, 9, 12 # first vector
b: .word 1, 2, 3, 4 # second vector
c: .space 16 # room for 4 result words
.text
la   t0, a # base address of a
la   t1, b # base address of b
la   t2, c # base address of c
li   t3, 0 # index, starts at 0
li   t4, 4 # number of elements
li   s0, 0 # running total
loop:
  beq  t3, t4, done
  slli t5, t3, 2 # byte offset = index * 4
  add  t6, t0, t5 # address of a[index]
  lw   t6, 0(t6) # value of a[index]
  add  a0, t1, t5 # address of b[index]
  lw   a0, 0(a0) # value of b[index]
  add  t6, t6, a0 # a[index] + b[index]
  add  a0, t2, t5 # address of c[index]
  sw   t6, 0(a0) # c[index] = a[index] + b[index]
  add  s0, s0, t6 # total += c[index]
  addi t3, t3, 1 # move to the next index
  j loop
done:
  mv a0, s0 # print total: 4+8+12+16 = 40
  li a7, 1
  ecall
  li a7, 10
  ecall

The loop runs as follows. slli t5, t3, 2 converts the index t3 to a byte offset. Adding it to each base pointer (t0, t1, t2) gives the addresses of a[i], b[i], and c[i]. On each pass, both elements are loaded, added together, stored into c, and added to the running total in s0. addi t3, t3, 1 advances to the next index, and the loop repeats until all four elements are processed.