Esercizio 35leggere un programma in assembly ARM

Frammento A

Lettura. r1 è un contatore (parte da 0). A ogni giro: LDRB r2, [r0], #1 legge un byte (zero-esteso a 32 bit) dall'indirizzo r0 e poi incrementa r0 di 1 (post-indicizzato: scorre la stringa); CMP r2, #0 / BEQ fine ferma la lettura al terminatore '\0'. Poi:

SUB   r3, r2, #97       @ r3 = c - 'a'
CMP   r3, #25
ADDLS r1, r1, #1        @ se r3 <= 25 (SENZA segno): r1++

LS (lower or same) è la condizione senza segno: $r3 \le 25$ come numero senza segno. Se $c$ è tra 'a' (97) e 'z' (122), $c - 97 \in [0, 25]$ e la condizione è vera. Se $c < 97$ la sottrazione dà un numero negativo, che letto senza segno è molto grande ($2^{32} - k > 25$): la condizione è falsa. Se $c > 122$ è $> 25$: falsa. Quindi un solo confronto senza segno controlla l'appartenenza a un intervallo a <= c <= z.

Funzione C equivalente:

int conta_minuscole(const char *s) {
    int n = 0;
    for (; *s != '\0'; s++)
        if (*s >= 'a' && *s <= 'z') n++;
    return n;
}

Traccia per "Ab1c" (byte 0x41 0x62 0x31 0x63 0x00):

MOV r0, r1 → il risultato è 2 (le lettere minuscole sono b e c).

Costo. Una iterazione per carattere: $O(n)$ per una stringa di $n$ caratteri, spazio $O(1)$. L'esecuzione condizionata di ADDLS evita un salto per carattere.

Errori da evitare (varianti scorrette):

• ADDLE al posto di ADDLS: LE è con segno, e 0xFFFFFFE0 è $-32 \le 25$ (vero): contererebbe anche 'A', '1'... tutto ciò che sta sotto 'a'.
• LDR r2, [r0], #1 al posto di LDRB: leggerebbe 4 byte alla volta (e non scorrerebbe per byte).
• CMP r3, #26 con LS: includerebbe anche il carattere dopo la 'z'.

Frammento B

Lettura. r1 accumula; in ogni giro AND r2, r0, #1 isola il bit meno significativo di r0 (0 o 1), ADD r1, r1, r2 lo somma, e MOV r0, r0, LSR #1 sposta a destra di un bit (logical shift right: divide per 2 scartando il bit appena contato). Si ferma quando r0 diventa 0. Il risultato è la somma dei bit di r0: il numero di bit a 1.

int conta_uni(unsigned x) {
    int n = 0;
    while (x != 0) {
        n += x & 1;
        x >>= 1;
    }
    return n;
}

Traccia per r0 = 22 = 10110$_2$:

Risultato: 3 ($22 = 10110_2$ ha tre bit a 1).

Costo. Un giro per ogni bit fino al bit più significativo a 1: $\lfloor \log_2 x \rfloor + 1$ giri per $x > 0$, quindi $O(\log x)$, al massimo 32. Per $x = 0$ non gira.

Osservazioni. Il LSR è logico: con un valore "negativo" in complemento a 2 (r0 = 0xFFFFFFFF) si ottiene 32; con un ASR (aritmetico) il bit di segno si replicherebbe e il ciclo non terminerebbe mai. Il test iniziale CMP r0, #0 all'inizio del ciclo (non in fondo) fa funzionare anche il caso $x = 0$.

Verifica

I due frammenti sono stati assemblati ed eseguiti in un emulatore ARM: il frammento A su 500 stringhe casuali (lettere maiuscole, minuscole, cifre e simboli), il B su 500 interi a 32 bit casuali (più 0 e 0xFFFFFFFF), confrontando con le funzioni C riscritte in Python; risultati: A su "Ab1c" → 2, B su 22 → 3, B su 0xFFFFFFFF → 32, B su 0 → 0. Le due varianti scorrette (ADDLE per A, ASR per B) sono state provate: la prima conta anche 'A' e '1' (da 2 a 4 sulla stessa stringa), la seconda non termina su un valore con il bit di segno a 1.

Errori comuni

• Credere che CMP r3, #25 / ADDLS confronti con segno: i suffissi HI, HS, LO, LS sono senza segno, GT, GE, LT, LE con segno (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 →).
• Dimenticare che LDRB legge un solo byte e che il post-indice #1 incrementa di 1 (per un array di int sarebbe 4).
• Confondere LSR (logico) con ASR (aritmetico) nello scorrimento di un numero senza segno.
• Costruire la traccia saltando il terminatore '\0' o il test iniziale del ciclo.
• Non scrivere il risultato in r0 prima di BX lr.