Domanda:
Algoritmo di decompressione sconosciuto
antoyo
2015-03-29 22:10:07 UTC
view on stackexchange narkive permalink

Lavoro sul reverse engineering dell'archivio ChessBase (.cbv).

Ho trovato la struttura generale del file e posso già decomprimere alcuni file.

Puoi vedere il mio lavoro attuale qui.

Tuttavia, alcuni file .cbv che sono più grandi sembrano utilizzare un secondo algoritmo di compressione.

Sono riuscito a trovare il primo algoritmo di compressione eseguendo il debug del software ChessBase Reader 2013, ma non riesco a dare un senso al secondo algoritmo di compressione.

Ho provato alcuni strumenti come signsrch per trovare quale algoritmo è stato utilizzato senza fortuna: sembra essere un algoritmo personalizzato.

Ecco un file che sono in grado di decomprimere in parte con il mio strumento (il mio strumento stamperà Cosa fare? quando rileva che è stato utilizzato l'algoritmo di compressione sconosciuto).

Hai idea di quale algoritmo di compressione viene utilizzato?

In caso contrario, hai qualche modo per trovarlo guardando il file compresso?

Sono in grado di creare archivi quindi posso ve file che sono sia compressi che non: mi chiedo se ci sia un modo per trovare un modello di compressione in una situazione del genere.

Una risposta:
Guntram Blohm supports Monica
2015-03-30 19:10:51 UTC
view on stackexchange narkive permalink

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.

la crittografia del database è sicuramente un'opzione. Vedi http://www.chesscentral.com/basic_chess_database_a/300.htm quindi è possibile che sia quello che stai guardando.
@broadway Grazie per averlo sottolineato. Comunque nel frattempo ho massaggiato IDA un po 'di più; Sono abbastanza sicuro che questo sia un algoritmo di decompressione di Huffman, anche se non ho ancora risolto tutto.
Guardando gli ultimi kilobyte, puoi vedere frammenti di "testo normale" intervallati da codici binari. Sicuramente una variante di Huffman.
Grazie per la tua risposta: guarderò questo. @Jongware: Conosco già l'algoritmo di compressione utilizzato quando vediamo normali frammenti di testo (vedi il mio strumento su GitHub). Il mio problema è quando non ci sono frammenti di testo. A proposito, sarebbe più facile capire l'algoritmo eseguendo il debug dell'applicazione che crea tali archivi (ChessBase)?


Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 3.0 con cui è distribuito.
Loading...