Rappresentazione dei dati e aritmetica binaria

Rappresentazione lineare dello stack e offset relativi

Pensare agli indirizzi di memoria come a una linea numerica orizzontale semplifica il ragionamento sullo stack rispetto ai classici diagrammi verticali.

Indirizzi minori < ------------------------------------------------ > Indirizzi maggiori
... --- [rsp - 0x10] --- [rsp - 0x08] --- [rsp] --- [rsp + 0x08] --- [rsp + 0x10] --- ...

• Sinistra: indirizzi numerici più piccoli, ad esempio rsp - 8.
• Centro: il punto attuale indicato dallo stack pointer (rsp).
• Destra: indirizzi numerici più grandi, ad esempio rsp + 8.

Direzionalità degli offset (rsp)

La direzione dello spostamento in memoria dipende dal segno dell'offset applicato al registro rsp.

Disposizione dei dati di avvio del kernel

All'avvio del programma, il kernel Linux posiziona le informazioni di bootstrap, come argc e i puntatori argv, a partire dall'indirizzo puntato da rsp. Tutti questi dati iniziali si estendono verso destra sulla linea numerica, occupando indirizzi progressivamente più grandi ([rsp + 0x08], [rsp + 0x10], e così via).

Dalla teoria alla pratica: lettura di argc

Applicando il modello della linea numerica, il primo valore utile che si trova esattamente in [rsp], senza alcun offset, è tipicamente il conteggio degli argomenti (argc) passati al programma.

mov rax, [rsp]

Da questo punto in poi, muovendosi verso destra con offset multipli di 8 byte, la dimensione di un puntatore a 64 bit, si trovano in sequenza i puntatori argv[0], argv[1] e così via, fino al terminatore NULL che segna la fine dell'array degli argomenti.

Rappresentazione dei dati: binario, decimale ed esadecimale

Bit e byte

• Bit: la singola cifra binaria (0 o 1), l'unità fondamentale del computer. N bit possono rappresentare 2 elevato a N combinazioni possibili (1 bit = 2 valori, 4 bit = 16 valori, 8 bit = 256 valori).
• Byte: un gruppo di 8 bit, uno standard convenzionale scelto storicamente, derivato da potenze di 2.

Il problema del sistema decimale (base 10)

• Mancanza di confini puliti: il sistema decimale non si allinea bene con i bit, perché servono circa 3,32 bit per rappresentare ogni singola cifra decimale (logaritmo in base 2 di 10).
• Difficoltà di conversione: calcolare a colpo d'occhio l'equivalente binario di un numero decimale è complesso, perché non esiste un rapporto 1 a 1 tra cifre decimali e blocchi di bit.

La soluzione: sistema esadecimale (base 16)

L'esadecimale si allinea perfettamente con la memoria binaria.

• Simboli: utilizza 16 cifre, da 0 a 9 e da a a f.
• Regola dei 4 bit: 1 cifra esadecimale equivale a esattamente 4 bit.
• 1 byte = 2 cifre hex: 8 bit si rappresentano in modo compatto con sole 2 cifre esadecimali, ad esempio 0x3e equivale a 0011 1110.
• Semplicità: per convertire a mente basta ricordare le potenze di 2 associate a 4 bit, cioè 8, 4, 2, 1.

Notazione delle costanti numeriche

Le potenze di 2 da ricordare a memoria

Numeri negativi e complemento a due

Perché si usa il complemento a due

Nelle CPU, l'ALU, l'unità logica aritmetica, ha bisogno di un sistema efficiente per gestire i numeri negativi. Il complemento a due è lo standard universale perché risolve due grandi difetti del bit di segno tradizionale.

• Elimina il doppio zero: non esistono più +0 e -0, ma un solo zero (00000000).
• Circuito aritmetico unico: la CPU esegue le stesse identiche operazioni di addizione e sottrazione sia per i numeri signed sia per quelli unsigned.

La regola d'oro: griglia dei pesi (valore unsigned)

La regola del bit di segno (signed)

Nel sistema signed, in complemento a due, il primo bit a sinistra, quello con peso 128, funge da interruttore per determinare il segno del numero.

Caso A, il primo bit è 0 (numeri positivi): il valore signed è identico al valore unsigned. Esempio (00110110): 32 + 16 + 4 + 2, cioè +54.

Caso B, il primo bit è 1 (numeri negativi): valore signed = somma unsigned - 256, cioè meno 2 elevato a 8. Esempio (11100100): somma dei pesi 228, quindi 228 - 256 = -28.

Casi limite (eccezioni estreme)

• 10000000 (il minimo assoluto): somma unsigned 128, quindi 128 - 256 = -128, il numero negativo più basso rappresentabile in 8 bit.
• 11111111 (il valore -1): somma unsigned 255, quindi 255 - 256 = -1. In qualsiasi ampiezza di bit, 8, 16, 32 o 64, una sequenza formata da soli 1 rappresenta sempre il valore -1.

Schema decisionale rapido

Numero binario: [X] X X X X X X X
E' 0? SI: POSITIVO, fai solo la somma dei pesi.
E' 1? SI: NEGATIVO, fai la somma dei pesi e sottrai 256.

Perché non basta invertire il segno

Un dubbio comune è: perché la CPU non usa semplicemente un bit dedicato al segno, lasciando invariati gli altri 7 bit, come accade con il segno meno in decimale. Il problema, come accennato sopra, è che questo approccio produce due rappresentazioni distinte per lo zero, complicando sia i circuiti di confronto sia le operazioni aritmetiche. Il complemento a due elimina questa ambiguità e permette all'ALU di trattare addizione e sottrazione con un unico circuito, indipendentemente dal segno degli operandi.

Complemento a due a 16 bit e calcolo tramite Python

Scalabilità del complemento a due

Il meccanismo del complemento a due si applica identicamente a qualsiasi ampiezza di bit, come 16, 32 o 64 bit, ad esempio nei registri rax, rdi e simili.

• 8 bit: costante di sottrazione 2 elevato a 8, cioè 256.
• 16 bit: costante di sottrazione 2 elevato a 16, cioè 65536.
• 64 bit: costante 2 elevato a 64.

L'intervallo dei valori a 16 bit

Valori chiave: 0111111111111111 è il massimo signed (+32767); 1000000000000000 è il minimo signed, calcolato come 32768 - 65536 = -32768; 1111111111111111 rappresenta sempre -1, calcolato come 65535 - 65536 = -1.

Calcolo pratico con Python

Dato che i numeri a 16 bit sono complessi da calcolare a mente, si utilizza la shell interattiva IPython. Il prefisso 0b indica a Python che il numero è scritto in notazione binaria.

hacker@dojo$ ipython

Si inserisce il numero binario per ottenere il valore unsigned, poi si sottrae 65536 poiché il numero inizia con 1 ed è quindi un negativo a 16 bit.

In [1]: 0b1001111101011100
Out[1]: 40796
In [2]: 40796 - 65536
Out[2]: -24740

Un'alternativa comoda per verificare il risultato nella direzione opposta è usare le funzioni built-in bin() e hex() di Python per ottenere la rappresentazione binaria o esadecimale a partire da un intero, incluso un valore negativo.

In [3]: bin(-24740)

Soluzione della sfida (16 bit)

/challenge/decode

Complemento a due a 32 bit (4 byte) e intervalli di memoria

Estensione della logica a 32 bit

Il principio del complemento a due rimane identico passando a 32 bit, pari a 4 byte di memoria, tipicamente ospitati nei registri a 32 bit come eax, la porzione bassa del registro a 64 bit rax.

• Dimensione: 32 bit consentono 2 elevato a 32, cioè 4.294.967.296 combinazioni possibili.
• Costante di sottrazione: quando il MSB, il 32esimo bit da destra, è impostato a 1, il numero è negativo. Per ottenere il valore con segno si sottrae 2 elevato a 32, cioè 4.294.967.296.

Intervalli e valori chiave a 32 bit

Calcolo pratico con Python

Per evitare errori nei calcoli manuali su stringhe a 32 bit, si usa la stessa calcolatrice IPython: si inserisce il numero binario anteponendo 0b per ricavare il valore unsigned, poi si verifica il bit di segno e, se la sequenza inizia con 1, si sottrae 2**32.

hacker@dojo$ ipython

In [1]: val = 0b10000000000000000000000000000001
In [2]: val
Out[2]: 2147483649
In [3]: val - (2**32)
Out[3]: -2147483647

Soluzione della sfida (32 bit)

/challenge/decode

Conversione da decimale a binario a 8 bit

Per convertire un numero decimale, ad esempio 42, nel corrispondente valore binario a 8 bit (00101010), si segue un procedimento in tre fasi: divisioni successive, lettura dei resti e aggiunta degli zeri di riempimento, detto padding.

Passo 1: divisioni successive per 2

• 42 / 2 = 21 con resto 0 (bit meno significativo, LSB, a destra)
• 21 / 2 = 10 con resto 1
• 10 / 2 = 5 con resto 0
• 5 / 2 = 2 con resto 1
• 2 / 2 = 1 con resto 0
• 1 / 2 = 0 con resto 1 (bit più significativo, MSB, a sinistra)

Passo 2: lettura dei resti (dal basso verso l'alto)

Raccogliendo i resti dall'ultima divisione effettuata fino alla prima, si ottiene il numero binario puro a 6 bit: 101010.

Passo 3: padding a 8 bit

Il risultato ottenuto contiene solo 6 cifre. Poiché la memoria del computer lavora a blocchi di byte (8 bit), si aggiungono due zeri a sinistra per completare la larghezza di 8 bit, ottenendo 00101010.

Schema riassuntivo

Conversione da binario a esadecimale (metodo della somma pesata 8-4-2-1)

Il principio dei 4 bit (nibble)

Un byte, 8 bit, si divide esattamente in 2 gruppi da 4 bit, detti nibble. Ogni nibble possiede una propria griglia di pesi basata sulle potenze di 2: 8, 4, 2, 1.

Regola della somma pesata passo-passo

1. Separazione: dividi il byte a 8 bit a metà, ottenendo due gruppi da 4 bit, sinistra e destra.
2. Somma pesata: per ciascun gruppo, somma i pesi (8, 4, 2, 1) in corrispondenza dei bit impostati a 1.
3. Mappatura esadecimale: se la somma è tra 0 e 9, scrivi la cifra così com'è; se la somma è tra 10 e 15, convertila nella lettera corrispondente (10 = a, 11 = b, 12 = c, 13 = d, 14 = e, 15 = f).
4. Unione e prefisso: concatena i due risultati e anteponi il prefisso 0x.

Esempi pratici

Esempio 1, 00010110: separazione 0001 e 0110. Primo gruppo, solo il peso 1 attivo, uguale a 1. Secondo gruppo, pesi 4 + 2 attivi, uguale a 6. Risultato: 0x16.

Esempio 2, 11100011: separazione 1110 e 0011. Primo gruppo, pesi 8 + 4 + 2 = 14, uguale a e. Secondo gruppo, pesi 2 + 1 = 3. Risultato: 0xe3.

Esecuzione della sfida

/challenge/convert

Decodifica da esadecimale a binario (espansione a 4 bit)

Il principio inverso: da hex a binario

La decodifica esegue l'operazione opposta rispetto alla codifica, mappando ogni simbolo esadecimale direttamente nel suo blocco di bit corrispondente: 1 cifra esadecimale si espande in esattamente 4 bit; 2 cifre esadecimali, 1 byte, si espandono in esattamente 8 bit.

Tabella di lookup esadecimale-binario

Esempio pratico: decodifica di 0x0a

Scomponendo il valore 0x0a: la cifra 0 vale 0, nessun peso attivo, quindi 0000; la cifra a vale 10, pesi 8 e 2 attivi, quindi 1010. Concatenando i due blocchi si ottiene il risultato a 8 bit: 00001010.

Soluzione della sfida

/challenge/convert

Sintesi operativa: le 4 interpretazioni dello stesso valore

Il concetto chiave

La memoria del computer memorizza esclusivamente sequenze di bit (0 e 1). Un singolo blocco di bit non ha un significato intrinseco: la CPU e il programmatore possono interpretarlo in 4 modi diversi, a partire dallo stesso valore 11100100: come binario puro, come coppia esadecimale (0xe4), come decimale unsigned (228, sempre positivo) e come decimale signed in complemento a due (-28).

Matrice di conversione (8 bit)

Esercizi di riepilogo svolti (passo-passo)

Esercizio 1, partendo dal binario 10110110 (8 bit)

• Esadecimale: separazione 1011 e 0110. Blocco 1, 8 + 2 + 1 = 11, uguale a b. Blocco 2, 4 + 2 = 6. Risultato hex: 0xb6.
• Decimale unsigned: somma pesi 128 + 32 + 16 + 4 + 2 = 182.
• Decimale signed: il primo bit è 1, quindi 182 - 256 = -74.

Esercizio 2, partendo dall'esadecimale 0xff00 (16 bit)

• Binario: ogni cifra hex diventa 4 bit, f = 1111, f = 1111, 0 = 0000, 0 = 0000. Risultato: 1111111100000000.
• Decimale unsigned: 65280.
• Decimale signed: il primo bit è 1, ampiezza 16 bit (2 elevato a 16 = 65536), quindi 65280 - 65536 = -256.

Esercizio 3, partendo dal decimale signed -42 (8 bit)

• Decimale unsigned: formula inversa, signed + 256, quindi -42 + 256 = 214.
• Binario: 214 sui pesi 128, 64, 32, 16, 8, 4, 2, 1, uguale a 128 + 64 + 16 + 4 + 2, risultato 11010110.
• Esadecimale: separazione 1101 e 0110. 1101 (8 + 4 + 1 = 13, d), 0110 (4 + 2 = 6). Risultato hex: 0xd6.

Palestra autonoma di esercitazione

Prova a risolvere questi 3 casi compilando tutte e 4 le interpretazioni.

• Caso A (8 bit): dato il valore binario 11001001, calcola hex, unsigned e signed.
• Caso B (8 bit): dato il valore esadecimale 0x3f, calcola binario, unsigned e signed.
• Caso C (8 bit): dato il valore decimale signed -15, calcola unsigned, binario ed esadecimale.