h45h

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

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 '@'

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 :)

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 :)