Esercizio 33array in assembly ARM, contare e invertire

1. conta

Registri. All'ingresso: r0 = v (indirizzo del primo elemento), r1 = n, r2 = soglia. Si usano r3 (elemento letto) e r12 (contatore c). Si scorre l'array con il puntatore r0 e si consuma n contando alla rovescia: il test n > 0 sostituisce i < n.

Scelte.

• LDR r3, [r0], #4: post-indicizzato: legge *r0 e poi incrementa r0 di 4 (un int è di 4 byte): fa in un'istruzione r3 = *p; p++.
• CMP r3, r2 e ADDGT: esecuzione condizionata: se $v[i] >$ soglia (confronto con segno, quindi GT e non HI) si incrementa il contatore, senza saltare. Un salto su un corpo di una sola istruzione costerebbe di più (vedi Branch predictionTecniche per gli hazard sul controllo: stallo, flussi multipli, prelievo anticipato del bersaglio, loop buffer, salto ritardato; predizione statica e dinamica con bit di storia, predittore a 1 e a 2 bit con esempio su un ciclo, tabella dei bersagli (BTB); costo di una predizione errata.Branch prediction →).
• CMP r1, #0 / BLE fine: il ciclo termina quando $n \le 0$ (con segno: anche $n$ negativo dà zero iterazioni, come in C).

conta:  MOV   r12, #0           @ c = 0
ciclo:  CMP   r1, #0
        BLE   fine              @ n <= 0: finito
        LDR   r3, [r0], #4      @ r3 = *p; p++
        CMP   r3, r2
        ADDGT r12, r12, #1      @ se *p > soglia: c++
        SUB   r1, r1, #1        @ n--
        B     ciclo
fine:   MOV   r0, r12           @ risultato in r0
        BX    lr

Traccia con v = {5, -2, 9, 0, 7}, soglia = 3 (stato a ogni inizio di ciclo, prima del CMP r1, #0):

Con $n = 0$ si esce subito e r12 = 0 è il risultato; la funzione restituisce 3.

Con indice invece del puntatore (più vicino al C): LDR r4, [r0, r3, LSL #2] con r3 come indice i e CMP r3, r1 / BGE fine per il test; ma serve un registro in più per l'elemento, e se non basta r12 ci si deve appoggiare a un registro callee-saved (r4–r11) da salvare con PUSH e ripristinare con POP: per una funzione foglia la versione col puntatore è più economica.

2. inverti

Registri. r0 = p (parte da v), r1 prima è n e poi diventa q, r2, r3 temporanei.

Scelte.

• ADD r1, r0, r1, LSL #2: r1 = v + 4n, cioè l'indirizzo subito dopo l'ultimo elemento (offset scalato con LSL #2); SUB r1, r1, #4 lo riporta a &v[n-1]. Per $n = 0$ risulta $q = v - 4 < p$ e il ciclo non gira.
• Il test p < q è un confronto tra indirizzi: si usa il confronto senza segno, BHS (higher or same): si esce se $p \ge q$. Con BGE (con segno) un indirizzo alto potrebbe apparire negativo.
• Lo scambio sfrutta il post-indicizzato: STR r3, [r0], #4 scrive *q (già letto in r3) in *p e fa avanzare p; STR r2, [r1], #-4 scrive il vecchio *p (in r2) in *q e fa arretrare q. Le due LDR vengono prima delle due STR, perciò non si perde nessuno dei due valori.

inverti: ADD   r1, r0, r1, LSL #2   @ r1 = v + 4n
         SUB   r1, r1, #4           @ r1 = &v[n-1] = q
ciclo:   CMP   r0, r1
         BHS   fine                 @ p >= q (senza segno): finito
         LDR   r2, [r0]             @ r2 = *p
         LDR   r3, [r1]             @ r3 = *q
         STR   r3, [r0], #4         @ *p = vecchio *q; p++
         STR   r2, [r1], #-4        @ *q = vecchio *p; q--
         B     ciclo
fine:    BX    lr

Traccia con $v = \{1,2,3,4,5\}$ ($n = 5$): $p$ e $q$ puntano a 1 e 5: scambio → 5 2 3 4 1; poi 2 e 4: 5 4 3 2 1; poi $p = q$ (entrambi su 3): BHS esce. Con $n = 4$, $\{1,2,3,4\}$: 4 2 3 1, poi 4 3 2 1; poi $p > q$: esce. Il numero di scambi è $\lfloor n/2 \rfloor$: $O(n)$ tempo, $O(1)$ spazio.

Verifica

Le due funzioni sono state assemblate ed eseguite in un emulatore ARM (stesso codice dei riquadri) su 500 casi casuali ciascuna, con $n$ da 0 a 12 e valori negativi, confrontando il risultato con quello di una funzione Python equivalente; in più si è controllato che i registri callee-saved r4–r6 restino invariati dopo la chiamata. Esiti sul caso della traccia: conta → 3; inverti su {1,2,3,4,5} → {5,4,3,2,1}; su {1,2,3,4} → {4,3,2,1}; su un array vuoto non cambia niente.

Errori comuni

• Passo sbagliato: avanzare di 1 invece di 4 nell'array di int (LDR r3, [r0], #4).
• Condizione con segno al posto di senza segno (e viceversa): GT/LT per i valori, HI/HS/LO/LS per gli indirizzi e per i valori senza segno (vedi Strutture di controllo in assembly ARMSalti B e condizionati, codici di condizione con e senza segno; traduzione di if, if-else, while, for e do-while da C ad ARM; esecuzione condizionata per eliminare salti brevi; switch con tabella di salto.Strutture di controllo in assembly ARM →).
• Usare r4–r11 in una funzione foglia senza salvarli: li deve preservare il chiamante.
• Scrivere con STR prima di aver letto con LDR entrambi gli elementi nello scambio.
• Dimenticare di sottrarre 4 dopo ADD r1, r0, r1, LSL #2 (si punterebbe oltre l'ultimo elemento).
• Dimenticare BX lr: l'esecuzione prosegue nelle istruzioni successive.