[zxspectrum] I miei loaders: come funzionano
- From: Paolo Ferraris <pieffe8@xxxxxxxxx>
- To: zxspectrum@xxxxxxxxxxxxx
- Date: Fri, 05 Apr 2013 00:37:34 -0700
Ciao a tutti,
ho deciso di prendermi una pausa nel testare il mio turbo loader sullo
Spectrum, e di sperimentarlo sul TS 2068 che ho a disposizione qui. Le
caratteristiche tecniche sono molto simili allo Spectrum, ed e`
probabile che quello che funziona su uno funzioni sull'altro (a parte le
incompatibilita` del BASIC, chiaramente...)
In questo momento il turbo loader "B" del #13 richiede circa 16 secondi
per caricarsi, ma solo perche` i leaders sono molto lunghi. Si puo`
accorciare a circa 13 secondi che e` circa il tempo che il loader di
Antonio impiega per caricare manic miner compresso con LZ usando un wav
da 44100 campioni/secondo come faccio io. Come gia` spiegato in passato,
la compressione migliore di solito si ottiene applicando prima LZ e poi
Huffman. Pensate, se si riuscisse ad ottenere una compressione anche
solo simile alla deflate si potrebbe caricare Manic Miner in meno di 10
secondi!
Nel frattempo vi spiego la codifica che ho usato nei due turbo loader.
Tralasciamo per il momento la compressione Huffman. Come gia` spiegato
in passato la codifica del mio loader originario e`
0 = AABB
1 = BBAA
2 = AAAABBBB
3 = BBBBAAAA
(A = alto, B = basso). Chiaramente la codifica e` differenziale (cioe` a
volte i segnali sono invertiti a seconda del segnale precedente) ma per
semplicita` assumiamo che non lo sia. La durata di ogni segnale e` 1
campione alla frequenza di 44100 Hz, quindi un bit rate medio di
44100 * 2 / 6 = 14700. In pratica il loader determina il bit piu` basso
leggendo il valore del segnale dopo il primo campione, ed il secondo dal
tempo che passa prima del fronte d'onda. Dopo il fronte d'onda il loader
e` libero di usare i 2 bit per la decompressione di Huffman.
Migliorare questa codifica non e` semplice. Si potrebbe pensare di usare
semplicemente
0 = AB
1 = BA
ma il problema e` che non ci sarebbe abbastanza tempo tra due segnali
per la decompressione. Ma questo problema non esiste con la seguente
equivalente (22050 bps) codifica a 4 segnali, usata dalla versione "B"
del loader #13:
0 = AABB
1 = ABAB
2 = BABA
3 = BBAA
Il loader determina il valore dei due bit leggendo a meta` del primo e
del secondo campione. Dopodiche` si sincronizza con il fronte tra il
secondo e terzo campione, lasciando il tempo di 2 campioni e mezzo per
la decompressione.
In teoria, in entrambe le versioni del loader ci sarebbero abbastanza
cicli a dispozione per spingere ulteriormente la frequenza da 44100
campioni/secondo ai 48000 campioni/secondo, ma la sincronizzazione
diventa ancora piu` problematica in questa maniera.
Infine, per chi e` interessato, la decompressione huffman e` molto
simile a quello usato in DigiSynth e poi da Stefano Donato per il suo
loader, ma adattato a nodi con piu` di due rami.
L'albero di Huffman e` organizzato come segue:
1) Ogni ramo e` rappresentato da due byte consecutivi (o per essere piu`
precisi, un bit e un byte)
2) Ogni nodo non terminale e` rappresentato dalla sequenza dei suoi
rami. La sequenza non e` terminata in maniera esplicita: i dati di
caricamento eviteranno di usare rami che non esistono (se sono meno di 4).
3) Tutti i nodi non terminali sono memorizzati in maniera consecutiva,
con nessun figlio che precede il genitore. (Il motivo sara` chiaro in
seguito.) Chiaramente il primo nodo e` la radice.
4) Se il bit di un ramo e` 0 allora il nodo successivo e` una foglia, ed
il byte contiene il suo valore.
5) Se il bit di un ramo e` 1 allora il nodo successivo e` non terminale,
ed il byte contiene la distanza - in paia di bytes - tra le locazioni di
memoria del ramo corrente e dove il nodo e` memorizzato. (Nell'algoritmo
di DIgi Synth la distanza e` in multipli di 4 (possibile perche` ogni
nodo consiste di 4 bytes) e non dal ramo corrente ma dalla radice.)
L'algoritmo di decompressione e` quindi il seguente:
0) D = indirizzo dove memorizzare i dati, L = lunghezza dei dati
1) X = indirizzo della radice dell'albero
2) leggi due bit e memorizzali in BB
3) X = X + 2 * BB
4) se il bit in X e` 0 vai al comando 7
5) X = X + 2 * Y, dove Y e` il contenuto del byte all'indirizzo X+1
6) Ripeti dalla linea 2
7) Leggi e memorizza in D il contenuto del byte all'indirizzo X+1 e
incrementa D
8) Decrementa L e, se diverso da 0, ritorna alla linea 1.
Ciao,
Paolo
Other related posts:
