[zxspectrum] Re: Perche` non turbo con decompressore Huffman?

  • From: Stefano Donati <sd75@xxxxxxxxxx>
  • To: "zxspectrum@xxxxxxxxxxxxx" <zxspectrum@xxxxxxxxxxxxx>
  • Date: Sun, 17 Feb 2013 10:00:54 +0100

Ciao Paolo,

probabilmente è per via del fatto che il loader con decodifica Huffman è stato 
già fatto anni fa: sicuramente conoscerai il demo DigiSynth, che al momento mi 
pare sia l'unico software che si carica utilizzando questa tecnica (facendo, 
tra l'altro, un uso massiccio delle routine di caricamento in ROM - quindi 
senza turbo). La "proof of concept" che ho realizzato sfrutta anche un altro 
loader già esistente e opportunamente adattato che combina la codifica 
Manchester inversa alla codifica Huffman, riducendo notevolmente i tempi di 
caricamento.

La combinazione LZ+Huffman mi pare molto interessante, anche se secondo me pone 
grossi vincoli alle massime frequenze utilizzabili, vista la quantità di codice 
necessaria.

Il compressore Huffman è già scritto, per quello LZ mi ci vuole un po' di 
più... ne varrà la pena?

Buona domenica a tutti. 

Stefano D.

Il giorno 17/feb/2013, alle ore 07:24, "Paolo Ferraris" <pieffe8@xxxxxxxxx> ha 
scritto:

> Ciao a tutti,
> seguo con molto interesse l'evoluzione di questi caricatori turbo con 
> decompressione integrata. Ho lavorato molto con compressori per il minigame 
> 4k race e penso di aver imparato molto, ma per la minigame compo il loader 
> era tradizionale, quindi non mi sono mai spinto nell'integrare la 
> decompressione nel loader, anche se la cosa mi e` sempre interessata. 
> Chissa`, magari mi torna la voglia... :-)
> 
> Vedo che vi state orientando verso la decompressione LZ nel turbo loader. 
> Credo invece che possa essere ancora piu` interessante la decompressione 
> Huffman. Fatemi spiegare perche`.
> 
> Per ottenere una compressione piu` efficiente di solito si comprime prima con 
> LZ poi con Huffman, invece che solo con LZ. Per esempio il deflate si basa 
> praticamente su questo concetto. Il problema piu` grosso di una 
> decompressione Huffman e` la sua lentezza: infatti l'operazione di navigare 
> un albero richiede parecchi cicli di CPU, mentre una LZ consiste 
> semplicemente nella copia di bytes.
> 
> La decompressione Huffman secondo me si adatta invece bene ai cicli CPU persi 
> durante il caricamento da nastro: ad ogni bit letto si scende di un nodo 
> dell'albero di Huffman. Se si raggiunge una foglia si scrive il valore in 
> memoria e si riparte dalla radice. Quindi secondo me la decompressione 
> Huffman durante il loading ha un suo valore.
> 
> La decompressione LZ nel loading anche se "figa" dal punto di vista tecnico 
> ha meno valore pratico, dato che la decompressione LZ si potrebbe effettuare 
> alla fine del caricamento in maniera veloce senza che nessuno praticamente se 
> ne accorda, a differenza di quanto non avvenga con Huffman. Tra l'altro si 
> potrebbe usare una compressione LZ piu` efficiente fuori dal loader, per 
> esempio memorizzando la lunghezza dei blocchi ripetuti non in base 0 come 
> credo che i vari loader facciano.
> 
> Poi volendo si potrebbero integrare sia Huffman che LZ nello stesso loader, 
> ma forse si esagera un po' in questa maniera. :-)
> 
> Altra considerazione: si potrebbe bilanciare l'albero di Huffman considerando 
> che uno 0 richiede meta` del tempo di un 1.
> 
> 
> Che ne pensate?
> Paolo
> 
> 

Other related posts: