Dopo aver scaricato ChessBase Reader e aver giocato un po 'con ProcMon per trovare la funzione che legge l'archivio e scrive il file di dati, ho caricato il tutto in IDA per analizzarlo. I dati sono codificati da Huffman.
Ogni blocco di dati ha la seguente struttura. Si noti che la compressione di Huffman funziona con i bit, non con i byte, quindi anche ogni dimensione nella tabella seguente è in bit. La lunghezza del blocco è di 16 bit o 2 byte, ad esempio.
+ ------------------------- --------------------- + | || 16 bit - lunghezza del blocco non compressa (len) || | + ----------- + ---------------------------------- + | | || Ripeti | 4 bit - lunghezza della voce (n) || 256 | || volte + ---------------------------------- + | | || una voce | n bit - albero sinistra / destra || per byte | informazioni per questo byte || (0-255) | || | | + ----------- + ---------------------------------- + | || Huffman codifica sequenze di bit. Il numero di || bits non è memorizzato da nessuna parte, ma il numero || di sequenze, che è uguale al numero || di byte di output, è la lunghezza del blocco (len) || | + ---------------------------------------------- +
Supponendo che la parola "foobar" sia stata codificata in questo schema, questo potrebbe risultare in (ho inventato i valori dei bit per i caratteri):
+ ---------------- + | Il codice di Huffman per || carattere è | + -------- + ------- + | | || o | 0 || f | 100 || b | 101 || a | 110 || r | 111 || | | + -------- + ------- +
Ciò comporterebbe che la parola foobar venga codificata come
100 0 0 101 110 111
. La lunghezza è di 6 byte o 0000 0000 0000 0110
in 16 bit.
Il bitarray per foobar
, formattato nella tabella sopra, leggerebbe
0000 0000 0000 0110 (lunghezza uscita 16 bit) ..... indice array 0 per byte '\ 0' ..... indice array 1 per byte '\ 1' ... ..0011 110 indice array 97 per byte 'a' (3 bit) 0011 101 indice array 98 per byte 'b' (3 bit) ..... 0011100 indice array 102 per byte 'f' (3 bit). .... 0001 0 indice array 111 per byte 'o' (1 bit) ..... 0011 101 indice array 114 per byte 'r' (3 bit) ..... combo bit rimanenti - 255100 0 0101 110 111 foobar text
L'implementazione costruisce un albero binario dalla tabella dei codici. Quando legge i dati, inizia dalla radice dell'albero; ogni bit si sposta lungo l'albero, a sinistra oa destra, a seconda del valore del bit successivo. Quando viene raggiunta una foglia, viene emesso il byte corrispondente. Questo si ripete finché non viene raggiunta la lunghezza del flusso di output.
Le funzioni correlate dal binario sono queste:
BECAA0
: decodifica i dati di archivio. Legge 16 bit per la lunghezza; quindi legge la tabella di codifica in due array agli offset 080A
(bit) e 0E10
(lunghezze di bit) all'interno della classe del decodificatore. Dopodiché, chiama BEC930
per decodificare i byte di dati.
BEBF30
: un parametro (numero di bit), ottiene questo numero di bit dall'array di input . Alla fine della funzione, la parola in offset 1014
ha questi bit.
BEBAD0
: costruisce l'albero dagli array in 080A
e 0E10
BEC930
: chiama BEBAD0
per costruire l'albero, quindi legge i bit rimanenti dal flusso di input. Cammina l'albero per ogni bit; emette un byte quando viene trovata una foglia. Alla fine, chiama BEBA90
per distruggere l'albero.
BEBA90
: Elimina ricorsivamente un nodo eliminando i figli di sinistra e di destra, il nodo stesso.
Non credo che il debug del writer sarebbe più facile se lo desideri leggere i file; la compressione ha molte strutture logiche e di dati e sapere come funziona "un modo" non ti aiuta necessariamente nell'altro modo. In questo caso, fortunatamente, è un algoritmo ben noto, ma se l'algoritmo è sconosciuto può essere abbastanza difficile da comprimere in modo efficace se sai solo come decomprimerlo.