Implementazione dell'algoritmo Adler-32 in Assembly MIPS realizzata da @And98 e @pusi77 per un progetto relativo al corso universitario di Calcolatori Elettronici.
L'Adler-32 è un algoritmo per il calcolo del checksum (o somma di controllo) sviluppato da Mark Adler nel 1995. Qui si possono trovare maggiori informazioni.
Come si può leggere qui ci sono metodi di implementazione differenti per il momento in cui viene eseguito l'operatore modulo della divisione. I principali sono il calcolo del modulo ad ogni iterazione (opzione più lenta e meno efficiente, ma più sicura) oppure una volta calcolate le somme finali (metodo migliore per le prestazioni, ma vulnerabile a problemi in caso una delle due somme diventi troppo grande in modulo).
La nostra è un'implementazione ibrida, come si potrà evincere poco più in basso nel paragrafo chiamato Funzionamento.
Data una stringa di byte D con lunghezza n, data A la somma del valore Ascii di ogni byte più 1 e B la somma dei valori di A per ogni iterazione:
A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
= n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521)
Adler-32(D) = B * 65536 + A
| Character | ASCII Code | A | B |
|---|---|---|---|
| W | 87 | A1 = 1 + 87 = 88 | B1 = A1 = 88 |
| i | 105 | A2 = A1 + 105 = 193 | B2 = B1 + A2 = 281 |
| k | 107 | A3 = A2 + 107 = 300 | B3 = B2 + A3 = 581 |
| i | 105 | A4 = A3 + 105 = 405 | B4 = B3 + A4 = 986 |
| p | 112 | A5 = A4 + 112 = 517 | B5 = B4 + A5 = 1503 |
| e | 101 | A6 = A5 + 101 = 618 | B6 = B5 + A6 = 2121 |
| d | 100 | A7 = A6 + 100 = 718 | B7 = B6 + A7 = 2839 |
| i | 105 | A8 = A7 + 105 = 823 | B8 = B7 + A8 = 3662 |
| a | 97 | A9 = A8 + 97 = 920 | B9 = B8 + A9 = 4582 |
A = 920 = 0x398 (base 16)
B = 4582 = 0x11E6
Output = 0x11E6 << 16 + 0x398 = 0x11E60398
N.B. : è possibile utilizzare correttamente il programma unicamente su simulatore Mars a causa dell'utilizzo della Syscall 34 per la stampa di un intero in formato esadecimale. Per l'esecuzione su altri simulatori che non supportano la syscall in questione è possibile sostituire il codice chiamata con quello per la stampa di un numero decimale (1) e in seguito convertirlo.
All'avvio il programma richiede una stringa composta da caratteri in codifica ASCII (non estesa). La stringa deve essere inserita mediante la console I/O e deve essere terminata con Invio, fatta eccezione nel caso si raggiunga la capacità massima della memoria a disposizione. In tal caso la stringa verrà troncata automaticamente.
La lunghezza massima della stringa è fissata ad 1 KB (1024 caratteri, compreso il carattere di terminazione). Per aumentare questo limite è sufficiente modificare le costanti delle righe 7 e 18 con il valore desiderato, in ogni caso il limite teorico dovrebbe essere 0xFFFFFFFF - 0x10010088 (4.026.466.167 caratteri) senza contare lo spazio per lo stack.
Caricata in memoria la stringa, ne viene letto un carattere per volta tramite un loop. Il valore di ogni carattere viene quindi utilizzato secondo l'algoritmo, sommandolo ad A e sommando la A trovata a B.
Ad ogni iterazione del loop viene controllato che il carattere letto non sia un carattere di fine stringa, ovvero null oppure /n. In seguito vengono aggiornate le somme di A e B, controllando che il valore di B non superi il valore 0x70000000 (questo valore non è frutto di calcoli, ma è stato scelto arbitrariamente, di conseguenza può essere migliorato riducendo calcoli supreflui). Nel caso ciò accada, viene calcolato il modulo della divisione tra B e il numero primo a 16 bit maggiore possibile, ovvero 65521, e viene aggiornato B con il resto trovato per ridurne la dimensione.
Il programma si arresta a stringa finita stampando il valore esadecimale ottenuto dall'algoritmo.
Per controllare i risultati e generare le stringhe di test sono comodi i seguenti siti: