Reversowanie starej gierki

Ostatnio mnie wzięło, aby odnowić gierkę z czasów dosa - produkcja Virgin Interactive z 1994 roku :) Wiadomo, że w tamtych czasach każdy programista starał się o jak najmniejsze rozmiary swoich produkcji, tylko jak teraz odgadnąć co to za rodzaj kompresji? Udało mi się zdobyć dwa pliki - jeden skompresowany i drugi identyczny bez kompresji. Wrzucam tu ich kawałki - jeżeli ktoś domyśla się z czym to się je, to proszę o info :) Na jakiegoś Huffmana mi to nie wygląda (identyczne symbole są definiowane kilkukrotnie), arytmetyczne kodowanie raczej to też nie jest (chociaż nie jestem do końca pewien). Pewnie jest to jakaś słownikowa dynamiczna metoda, ponieważ dane lecą od razu, bez początkowego zestawu symboli ani headerów. Fragment po kompresji:

00100000 10010011 01001000 11000000 11100011 01100001 10100100 11011110 01101110 00011000 10000000 00100001 00110000 10101000 01011100 00110010 00011011 00001101 00001111 10000011 11000111 10000000 00000000 00100011 00000100 01111110 00111111 01100000 11000011 10100011 00110001 10101000 01011001 11110100 00001100 01000000 00000000 00000000 01000000 00000000 00100000 00000000 00001110 00100110 00000000 10001111 10000001 01000000 00000000 01100000 00000000 00011100 00000000 00001000 10010011 10000000 00000001 00100000 00000000 01010000 00000000 00010110 00000000 00000110 01001100 00000001 10100000 00000000 01110000 00000000 00011110

Fragment oryginału:

01000001 01001101 01000110 00001110 01101100 01101001 01101111 01101110 00110001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111 00001111 00111100 00000000 00000100 11000001 00111111 00111111 11000001 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 01111101 00000110 01000000 00000000 00000001 00000000 00000010 00000000 00000011 00000000 00000100 00000000 01000000 00000000 00000101 00000000 00000110 00000000 00000111 00000000 00001000 00000000 01000000 00000000 00001001 00000000 00001010 00000000 00001011 00000000 00001100 00000000 01000000 00000000 00001101 00000000 00001110 00000000 00001111 00000000

Tutaj trochę uporządkowałem kawałek skompresowanych danych:

0- 01000001- 0- 01001101- 0- 01000110- 0- 00001110- 0- 01101100- 0- 01101001- 0- 01101111- 0- 01101110- 0- 00110001- 0- 00000000 tu jest 26 zer: 100001001100001010100001011100001100100001101100001101- 0- 00011111- 0- 00001111- 0- 00111100- 0- 00000000- 0- 00000100- 0- 11000001- 0- 00111111- 0- 00111111- 0- 11000001- tu jest 27 zer: 100001110100011001100011010100001011- 0- 01111101- 0- 00000110

--- edit --- może to niezbyt cenne info, ale plik przed kompresją ma 49kb, po dzikiej kompresji 43.5kb, natomiast spakowany zipem 34.5kb :)

proponuje pogrzebac w exeku. chyba prosciej wyripowac dekompresje niz samemu ja pisac od zera, oczywiscie zakladajac, ze uda sie zgadnac algo :p

Tylko, że disasmy zazwyczaj dawały mi totalny bajzel i połowa kodu to było "db ...", a sam exek zajmował ponad 650kb (na DOS to bardzo dużo), więc więcej czasu zajęłoby mi przejrzenie zdisasmowanego kodu, niż odkrycie samego algorytmu :)

zalacz plik gry tutaj do post'a, wtedy ludzie sobie poogladaja i byc moze ktos ci powie co to jest :)

mozliwe, ze exek jest spakowany. sprawdz dosowym toolsem "fileinfo".

Ten algorytm to Lempel-Ziv-Welsch, czyli LZW :). Wiem, bo kiedyś to w asmie klepałem :P. Właściwie tutaj jest jakaś modyfikacja, ale generalnie idea jest zachowana. Algorytm działa tak: 0. Początkowo słownik jest pusty --- 1. Pobierz bajt z wejścia 2. Jeżeli nie masz takiego w słowniku to dodaj go tam i przypisz mu pierwszy wolny nr. Następnie wypisz bit 0 oraz jawnie ten cały bajt 3. Jeżeli masz, to wypisz bit 1 oraz nr w słowniku. Następnie tą parę bajtów dodaj do słownika z kolejnym numerem 4. Pętla ;) Dlaczego tak? Pierwsze bajty są wypisywane kolejno poprzedzone zerem (bo jak na razie są wyjątkowe, nie było wcześniej takich). Pierwszy bajt jaki się powtarza to 00000000 i jak sprawdzisz ma on przypisany nr 9 w słowniku (zaczynamy liczyć od zera). Więc zamiast powtarzać ten bajt wypisujemy bit 1 oraz nr w słowniku, czyli binarnie 00001001. Ale zapamiętujemy, że od teraz jeśli wystąpia 2 bajty 00000000 pod rząd to mają one w słowniku kolejny nr, czyli 10 dziesiętnie. I tak rzeczywiście się dzieje, więc znowu wypisujemy bit 1 oraz nr w słowniku, czyli 00001010. Teraz zapamiętujemy, że 3 bajty 00000000 pod rząd mają nr w słowniku 11 dziesiętnie. I to tak dalej idzie. Zauważ, że ten ciąg, bitów, które tam wypisałeś da właśnie 26 zer w końcu, a później 27. Nie wiem jak to prościej wytłumaczyć, ale na pewno chodzi o ten algos. Poczytaj o LZW, przeanalizuj co tu pisałem, a jakby co postaram się jaśniej jeszcze wytłumaczyć :)

Długo myślałem nad tym, czy to LZW, ale teraz jestem prawie pewny, że to jakaś jego modyfikacja. Głównie nie mogę dojsć do tego, dlaczego jest 26 zer (jak dla mnie to tam zakodowane jest 20 zgodnie z algorytmem LZW :mellow:). Podam ten fragment w czytelniejszej fomie. Tam gdzie napisałem dziesiętnie, to jest numer w słowniku (9,10,11,12,13,13 musi dać 26 zer, a 14,25,26,11 - 27 zer). W pierwszym wypadku po dekompresji wychodzi mi o 6 zer za mało, w drugim jeszcze nie patrzyłem. Czemu tak jest?

0x41 'A' 0x4d 'M' 0x46 'F' 0x0e '' 0x6c 'l' 0x69 'i' 0x6f 'o' 0x6e 'n' 0x31 '1' 0x00 ' ' 9 - tu wstawiam 0 10 - tu wstawiam 00 11 - tu wstawiam 000 12 - tu wstawiam 0000 13 - tu wstawiam 00000 13 - tu wstawiam 00000 0x1f '' 0x0f '' 0x3c '<' 0x00 ' ' 0x04 '' 0xc1 'Á' 0x3f '?' 0x3f '?' 0xc1 'Á' 14 25 26 11 0x7d '}' 0x06 '' 0x40 '@'

no to idziemy w zaparte, zamiast w prosty sposob przeanalizowac kod :), ale jak ktos lubi sobie utrudniac zycie to juz jego sprawa

Rozbiłem na bajty ten ciąg co ma utworzyć 26 zer:

1 00001001 - 2 zera
1 00001010 - 3 zera
1 00001011 - 4 zera
1 00001100 - 5 zer
1 00001101 - 6 zer
1 00001101 - znowu 6 zer

2+3+4+5+6+6 = 26 Czyli generalnie to co napisałem w pierwszym moim poście jest dobre, z tym, że tam miałem drobny błąd. Pisałem, że kod 9 wypisze jedno zero, kod 10 dwa zera, itd, kiedy to kod 9 wypisuje już dwa zera, kod 10 trzy... Idea jest taka jak pisałem. A jeżeli rzeczywiście chcesz implementować dekompresję samemu, a nie ripować to z programu, to ja od razu odradzam asm albo C. Najlepiej chyba użyć C++ z STLem albo w ogóle jakiegoś Pythona, gdzie masz dostępną mapę asocjacyjną (tablicę haszową). EDIT: Chociaż w tym drugim wypadku coś nie gra:

1 00001110 - 7 zer
1 00011001 - 8 zer
1 00011010 - 9 zer
1 00001011 - 4 zera

7+8+9+4=28 Na pewno tam w nieskompresowanych danych było 27, a nie 28 zer?

przeanalizujcie sobie kod, modyfikacji LZW jest prawdopodobnie tyle ile implementacji ;] więc zgadywanie o co chodzi nie ma raczej sensu...

przeanalizujcie sobie kod, modyfikacji LZW jest prawdopodobnie tyle ile implementacji ;] więc zgadywanie o co chodzi nie ma raczej sensu...

Jasne, że ma sens :D Na pewno ma jakąś wartość edukacyjną. Po dłuuugich godzinach siedzenia nad plikami i kodem udało mi się uzyskać ostateczny cel - rozpracowałem kompresję od podstaw w czystym C++ ;) Dzięki wszystkim, którzy udzielali się w tym temacie, szczególne dzięki za naprowadzenie na LZW (na początku to mi na to nie wyglądało, dopiero wypowiedź Reverenda skłoniła mnie do głębszych przemyśleń). Trochę roboty z tym było, bo rzeczywiście jedynie sama idea tego algorytmu jest zachowana. Teraz pozostaje tylko rozpracować formaty plików graficznych, dźwiękowych, animacji i leveli :D No to do dzieła! ;P --- edit --- zostały mi już same mapki leveli do rozpracowania :D