Vettori: indicizzazione in base alla posizione

Un vettore è un array: una sequenza di numeri memorizzati uno accanto all'altro in memoria. Nella lezione precedente ne hai sommato uno spostando un puntatore in avanti di 4 byte per ogni elemento. Lo stesso metodo funziona qui. C'è un altro modo comune per raggiungere un elemento: tramite indice. Un indice è la posizione di un elemento contata dall'inizio, dove il primo elemento ha indice 0, il secondo ha indice 1, e così via.

Somma un vettore avanzando un puntatore

.data
a: .word 5, 10, 15, 20 # quattro elementi
.text
la   t0, a # t0 = indirizzo di a
li   t1, 4 # t1 = numero di elementi rimanenti
li   t2, 0 # t2 = somma corrente
loop:
  beq  t1, zero, done
  lw   t3, 0(t0) # carica l'elemento corrente
  add  t2, t2, t3 # aggiunge al totale
  addi t0, t0, 4 # avanza alla parola successiva (4 byte)
  addi t1, t1, -1 # uno in meno
  j loop
done:
  mv a0, t2 # stampa il totale: 5+10+15+20 = 50
  li a7, 1
  ecall
  li a7, 10
  ecall

Il ciclo funziona come segue. t0 contiene l'indirizzo di a, e t1 contiene il numero di elementi rimanenti, a partire da 4. A ogni passaggio, termina il ciclo quando il conteggio raggiunge zero. carica l'elemento all'indirizzo in t0. aggiunge quel valore al totale corrente. fa avanzare il puntatore alla parola successiva. decrementa il conteggio. Dopo quattro passaggi (5 + 10 + 15 + 20), done stampa 50. Questo è lo stesso schema usato nella lezione sulla memoria, ora applicato a un vettore.

Dall’indice all’indirizzo

L'indicizzazione calcola un indirizzo da un puntatore di base e una posizione: address = base + index * 4. Il 4 è la dimensione di una parola in byte. Un compilatore genera questo stesso calcolo per a[i] in un linguaggio come C. L'indice stesso non accede mai alla memoria. Solo l'indirizzo calcolato da esso lo fa.

Indice in indirizzo, usando uno spostamento

slli t5, t3, 2 # t5 = indice * 4 (dimensione di una parola)
add  t6, t0, t5 # t6 = indirizzo di element[index]
lw   t6, 0(t6) # t6 = element[index]

sposta l'indice in t3 a sinistra di 2 bit, il che lo moltiplica per 4 (due raddoppi: 2 x 2), la dimensione di una parola. Aggiungendo il risultato al puntatore di base si ottiene l'indirizzo di element[index]. Questo spostamento è lo stesso metodo delle potenze di due della lezione sull'aritmetica, ed è il modo standard per scalare un indice in base alla dimensione di una parola.

Calcolo dell'indirizzo

indirizzo=base+0×4=base+0

a[0]3

0x10010000

a[1]6

0x10010004

a[2]9

0x10010008

a[3]12

0x1001000c

a[0]: indice 0, offset 0.

La barra del puntatore e il badge esadecimale si muovono insieme mentre l'indice percorre 0, 1, 2, 3. Presentano lo stesso fatto in due forme: i come posizione, e l'indirizzo che quella posizione produce dopo che lo scala di 4 e lo aggiunge alla base. I numeri esadecimali sono gli indirizzi reali che a occupa quando il simulatore esegue questo programma. L'obiettivo è prevedere l'indirizzo successivo prima che compaia. Questo ti permette di leggere dentro un ciclo incrementale, o a[i] in un linguaggio simile a C, e immaginare l'indirizzo di memoria che tocca invece di trattare la notazione come una scatola nera.

Sommare un vettore per indice

Somma un vettore usando un indice

.data
a: .word 5, 10, 15, 20 # quattro elementi
.text
la   t0, a # t0 = indirizzo base di a
li   t1, 4 # t1 = numero di elementi
li   t2, 0 # t2 = indice, inizia a 0
li   t3, 0 # t3 = totale cumulativo
loop:
  beq  t2, t1, done
  slli t4, t2, 2 # t4 = indice * 4 (offset in byte)
  add  t5, t0, t4 # t5 = indirizzo di a[index]
  lw   t5, 0(t5) # t5 = a[index]
  add  t3, t3, t5 # total += a[index]
  addi t2, t2, 1 # passa all'indice successivo
  j loop
done:
  mv a0, t3 # stampa il totale: 5+10+15+20 = 50
  li a7, 1
  ecall
  li a7, 10
  ecall

Il ciclo funziona come segue. t2 è l'indice, a partire da 0. A ogni passaggio, termina il ciclo quando l'indice raggiunge 4, il conteggio degli elementi contenuto in t1. converte l'indice in un offset in byte. aggiunge quell'offset all'indirizzo di base in t0 per produrre l'indirizzo di a[index]. carica il valore memorizzato lì. Quel valore viene aggiunto al totale corrente in t3, e avanza all'indice successivo. Dopo quattro passaggi (5 + 10 + 15 + 20), done stampa 50.

Somma di due vettori, elemento per elemento

c[i] = a[i] + b[i]

.data
a: .word 3, 6, 9, 12 # primo vettore
b: .word 1, 2, 3, 4 # secondo vettore
c: .space 16 # spazio per 4 parole di risultato
.text
la   t0, a # indirizzo base di a
la   t1, b # indirizzo base di b
la   t2, c # indirizzo base di c
li   t3, 0 # indice, inizia da 0
li   t4, 4 # numero di elementi
li   s0, 0 # totale corrente
loop:
  beq  t3, t4, done
  slli t5, t3, 2 # offset in byte = indice * 4
  add  t6, t0, t5 # indirizzo di a[index]
  lw   t6, 0(t6) # valore di a[index]
  add  a0, t1, t5 # indirizzo di b[index]
  lw   a0, 0(a0) # valore di b[index]
  add  t6, t6, a0 # a[index] + b[index]
  add  a0, t2, t5 # indirizzo di c[index]
  sw   t6, 0(a0) # c[index] = a[index] + b[index]
  add  s0, s0, t6 # totale += c[index]
  addi t3, t3, 1 # passa all'indice successivo
  j loop
done:
  mv a0, s0 # stampa il totale: 4+8+12+16 = 40
  li a7, 1
  ecall
  li a7, 10
  ecall

Il ciclo funziona come segue. converte l'indice t3 in un offset in byte. Aggiungendolo a ciascun puntatore di base (t0, t1, t2) si ottengono gli indirizzi di a[i], b[i] e c[i]. A ogni passaggio, entrambi gli elementi vengono caricati, sommati, memorizzati in c, e aggiunti al totale corrente in s0. avanza all'indice successivo, e il ciclo si ripete finché tutti e quattro gli elementi non sono elaborati.

💡

Questo schema di indicizzazione, base + index * dimensione dell'elemento, è il modo in cui ogni accesso a un array viene compilato, in qualsiasi linguaggio. Tienilo a mente: la prossima lezione usa la stessa idea due volte contemporaneamente per raggiungere una matrice.

Apri in Litessera Lux, l'assembler RISC-V Offrimi un caffè