1 bites grafika tomoritesi kiserletek vizualizalva...

HoH projekt kereteben, sajat tomorito algoritmusok keszultek. Kicsit bovebben arrol van szo, hogy rogeszmemme valt, hogy a leheto legkisebb file-meretre torekedjek. Mar-mar annyira, hogy komolyan gondolkodom C helyett inkabb 68k assembly-ben csinalom az egeszet. Mindenesetre a kicsomagolo kodot biztosan!

Szoval a tomorites otlete szinte magatol ertetodott, ugyanis a CW (CodeWarrior) a C forrasba agyazott bitmap adatokat enyhen tomoritve tarolja resource-kent a resource fork-ban. Mivel ez a tomorites eleg gyenge, gondoltam kezbe veszem a dolgot, es megnezem mit tudok kihozni belole. Megjegyeznem, hogy nem vagyok sem matematikus, sem tomorites-szakerto, szoval igencsak az elejen kezdtem. Eloszoris probaltam vadaszni meglevo tomorito algoritmus forraskodokat (sikertelenul - talaltam de...), majd olvastam kicsit a temaban, amiben a legfontosabb amit sikerult leszurnom, hogy hogyan tudok szamokat kevesebb biten tarolni. Most mielott ossze-vissza belekezdenek mindenfelebe, par szot arrol, mi is van a jobb oldalon.

A jobb oldalon 14 csoportban kis 1 bites "bitmap"-eket, a keszulo jatek keszulo grafikai elemeit lathatjuk (Az elso csoportban a c64 karatkerkeszlete a kivetel). Minden egyes csoport az eredetivel indul, majd mellette sorban lathatoak az ujabb es ujabb tomorito algoritmusok tomoritesei ($AA padding), es az utolso helyen osszehasonlitaskeppen a zip tomoritese. Mindezt ugye kepekben latjuk: az 1 bites grafika lenyege, hogy 1 byte-on 8 keppontot tarolunk, minden egyes bit 1 keppont. 1 byte 8 keppontja egymas mellett helyezkedik el. A memoriaban levo kep soronkent van tarolva, ezert a szelesseguk pixelben mindig 8 szorzata. Szoval a byte-okon pixeleket tarolunk, es ez tokeletesen latszik az eredeti grafikan, viszont a tomorites folyaman, a pixeleket szamkent kezeljuk, es matematikailag probaljuk meg ezeket a szamokat kevesebb byte-on tarolni ugy, hogy visszafejtheto legyen. Ennek az eredmenye, hogy a tomoritett adatban egyre kevesbe ertelmezheto az eredeti grafika, es annal inkabb dominalnak a szamok, ami random pixelhalmaznak tunik ranezesre. Es most arrol, hogyan is keszulnek.

Packer1

Ez az a tomorites, amit a CodeWarrior is csinal(t), es amit mar 13 evesen c64-en is sikerult megcsinalnom, igazan nem nagy kaland, viszont azert nem is rossz. A lenyege, hogy a memoriaban levo byte-ok sorozataban kiszuri az egymast koveto azonos byte-okat, es helyettesiti 3-byte-tal a jo esetben sokkal hosszabb sorozatot.

Tomorites: megkeresi a legritkabban elofordulo ertekeket a byte-ok sorozataban, optimalis esetben van 1 vagy tobb olyan ertek ami nem szerepel. Ez lesz a Control-byte. Kitomoritesnel amikor olvassa a tomoritett byte-sorozatot, ha a Control-byte tal talalkozik, az jelzi, hogy ismetles lesz.

Elonye, hogy mind a tomorites, mind a kitomorites nagyon gyors, a leheto leggyorsabb, gyorsabb mintha a memoriaban a kitomoritett kepet masolnank egyik helyrol a masikra. Hatranya, hogy reszletgazdag grafikaknal nem tul hatekony.

Packer3

Mint korabban irtam a kepek a memoriaban byte sorokbol alnak, igy egy 32x32 pixeles grafika 1. sora az elso negy byte-bol all ( 0 1 2 3 ), es ezt 31-szer koveti ujabb 4 byteüos sor ( 4 5 6 7 ... ). Ez a kismeretu grafikak eseteben, ha a byte-sorozatban egymast koveto ismetleseket akarok kiszurni, nem tul optimalis, ezert tomorites elott atrendezem a byte-okat (nem orulok ennek*) ugy, hogy az egymast koveto byte-ok, a kepen egymas ala essenek. Igy az elozo grafika elso soraban a kovetkezo byte-ok lesznek: 0 32 64 96, a kovetkezoben meg 1 33 65 97, es igy a 32. sorig.
* Nem orulok neki, mert a sorrend visszaallitasa kitomorites utan ujabb nyug, de szerencsere viszonylag gyorsan es keves extra memoria felhasznalasaval megoldhato.

A tomorito algoritmus ugyan az mint az elozo valtozatnal, megis ijesztoen javult a hatekonysag, mindezt az adatok optimalis sorrendjenek koszonhetoen.

Packer7o

Ez most kicsit mas. Annyira mas, hogy itt nem a byte-ok ismetledeset szurom ki, hanem a biteket.

Packer8o

Ujra byte-okkal dolgozik a kod, de most kezd vegre javulni igazan a hatekonysag, mert most mar nem csak az egymast koveto ismetleseket keresi, sot, azt konkretan nem is, hanem a grafika teljes byte sorozatat (a modositottat) atnezve megkeres minden ismetlodo sorozatot (repeats), ezekbol kiszuri az atfedeseket, es ugy hasznalja fel, hogy a leheto legkisebb kozok (streams) maradjanak. Ezzel a modszerrel, control-byte-okkal, es 8 es 16 bites szamlalokkal es mutatokkal is, nagyon sokat javult a hatekonysaga.

Packer9o

Tovabbra is stream-ek ismetledeset szuri ki a kod, de a control byte-ok, szamlalok, mutatok bitekre vannak szedve, optimalizalva...

Packer9bo

Lookup table...

Zip

Nagyon jo erzes volt sokszor megverni a zip-et, de most nagyon kihangsulyoznam, hogy a zip osszehasonlithatatlanul jobb, altalanos felhasznalasu tomorito, amiert az enyem nyerhetett, az a manipulalt byte-sorrend, valamint a kis meret (byte-ban), es a kifejezetten a bitmap grafika tomoritesere elezett algoritmus. A mintakon szereplo zip tomorites, a zip file-bol kinyert nyers tomoritett adat, levagva minden egyeb, min 170 byte meretu sallangot. Csak hogy korrektebb legyen az osszehasonlitas.

1 bit graphic compression experiment visualized...

6 differend compression methods are used and shown.
PACKER1: simple byte packer (remove repeated bytes)
PACKER3: simple byte packer but with different byte order (Y,X). Remarkable how much better is it than Packer1
PACKER7: bit packer with bit repeat packing, but support multiple Length storage type, extra optimization, and supports different bit order read.
PACKER8: better byte packer (remove redundant byte streams). This one take a huge amount of time and memory, but provides a fabulous packing ratio, and one of the fastest decompressing time, with a simle lightwight depacker code
PACKER7o: same as the previous but this time with optimization enabled
PACKER8o: different markers (saved some bytes)
PACKER9: bitcoded stream/repeat informations + better algorithm
PACKER9b: bitcoded stream/repeat informations + lookup table with bitcoded index
PACKER9bo: bitcoded stream/repeat informations + optimized bitcoded index
Zipped: Just to compare... (only the compressed data, no file/directory info, headers, etc)

Precalculated samples

__c64font2

Original:  4096 bytes
Packed1:   3820 bytes (  6.74 %, saved   276 bytes)     2.7000 ms
Packed3:   3436 bytes ( 16.11 %, saved   660 bytes)     2.7999 ms
Packed7o:  3486 bytes ( 14.89 %, saved   610 bytes)    36.8999 ms
Packed8o:  1248 bytes ( 69.53 %, saved  2848 bytes)  2710.0000 ms
Packed9o:  1018 bytes ( 75.15 %, saved  3078 bytes)  3735.5000 ms
Packed9bo:  844 bytes ( 79.39 %, saved  3252 bytes)  3746.6000 ms
Zipped:    1584 bytes ( 61.33 %, saved  2512 bytes)

__16x16_(font)

Original:  2048 bytes
Packed1:   1704 bytes ( 16.80 %, saved   344 bytes)     0.7999 ms
Packed3:   1300 bytes ( 36.52 %, saved   748 bytes)     0.6000 ms
Packed7o:  1474 bytes ( 28.03 %, saved   574 bytes)     6.6000 ms
Packed8o:  1016 bytes ( 50.39 %, saved  1032 bytes)   255.9999 ms
Packed9o:   814 bytes ( 60.25 %, saved  1234 bytes)  1129.6000 ms
Packed9bo:  678 bytes ( 66.89 %, saved  1370 bytes)  1158.6999 ms
Zipped:     633 bytes ( 69.09 %, saved  1415 bytes)

__24x24_(tiny_sprites_32x24)

Original:   864 bytes
Packed1:    768 bytes ( 11.11 %, saved    96 bytes)     0.2999 ms
Packed3:    586 bytes ( 32.18 %, saved   278 bytes)     0.3000 ms
Packed7o:   590 bytes ( 31.71 %, saved   274 bytes)     2.6000 ms
Packed8o:   572 bytes ( 33.80 %, saved   292 bytes)    47.8999 ms
Packed9o:   560 bytes ( 35.19 %, saved   304 bytes)   227.7000 ms
Packed9bo:  674 bytes ( 21.99 %, saved   190 bytes)   269.6000 ms
Zipped:     618 bytes ( 28.47 %, saved   246 bytes)

__32x16_(floor_border)

Original:    64 bytes
Packed1:     64 bytes (  0.00 %, saved     0 bytes)     0.0999 ms
Packed3:     50 bytes ( 21.88 %, saved    14 bytes)     0.0999 ms
Packed7o:    38 bytes ( 40.63 %, saved    26 bytes)     0.3000 ms
Packed8o:    44 bytes ( 31.25 %, saved    20 bytes)     0.7000 ms
Packed9o:    32 bytes ( 50.00 %, saved    32 bytes)     3.9999 ms
Packed9bo:   34 bytes ( 46.88 %, saved    30 bytes)     5.0000 ms
Zipped:      49 bytes ( 23.44 %, saved    15 bytes)

__32x48_(floors)

Original:  1344 bytes
Packed1:   1266 bytes (  5.80 %, saved    78 bytes)     0.3999 ms
Packed3:   1026 bytes ( 23.66 %, saved   318 bytes)     0.5000 ms
Packed7o:  1090 bytes ( 18.90 %, saved   254 bytes)     4.0000 ms
Packed8o:   626 bytes ( 53.42 %, saved   718 bytes)   170.0000 ms
Packed9o:   478 bytes ( 64.43 %, saved   866 bytes)   584.0999 ms
Packed9bo:  422 bytes ( 68.60 %, saved   922 bytes)   585.2000 ms
Zipped:     416 bytes ( 69.05 %, saved   928 bytes)

__32x16_alphaonly_tmirror_(walls)

Original:  1280 bytes
Packed1:    478 bytes ( 62.66 %, saved   802 bytes)     0.2999 ms
Packed3:    286 bytes ( 77.66 %, saved   994 bytes)     0.3000 ms
Packed7o:   318 bytes ( 75.16 %, saved   962 bytes)     2.4999 ms
Packed8o:   164 bytes ( 87.19 %, saved  1116 bytes)    13.0999 ms
Packed9o:   128 bytes ( 90.00 %, saved  1152 bytes)   478.4000 ms
Packed9bo:  124 bytes ( 90.31 %, saved  1156 bytes)   489.1999 ms
Zipped:     135 bytes ( 89.45 %, saved  1145 bytes)

__32x72_tmirror_(doorbase_elevated)

Original:   288 bytes
Packed1:    278 bytes (  3.47 %, saved    10 bytes)     0.2000 ms
Packed3:    270 bytes (  6.25 %, saved    18 bytes)     0.0999 ms
Packed7o:   266 bytes (  7.64 %, saved    22 bytes)     1.2999 ms
Packed8o:   244 bytes ( 15.28 %, saved    44 bytes)    10.4000 ms
Packed9o:   222 bytes ( 22.92 %, saved    66 bytes)    42.7000 ms
Packed9bo:  246 bytes ( 14.58 %, saved    42 bytes)    47.8999 ms
Zipped:     239 bytes ( 17.01 %, saved    49 bytes)

__32x112_tmirror_(walls)

Original:  8960 bytes
Packed1:   8802 bytes (  1.76 %, saved   158 bytes)     2.0999 ms
Packed3:   7760 bytes ( 13.39 %, saved  1200 bytes)     2.0000 ms
Packed7o:  7594 bytes ( 15.25 %, saved  1366 bytes)    30.5000 ms
Packed8o:  5308 bytes ( 40.76 %, saved  3652 bytes)  8405.0999 ms
Packed9o:  4926 bytes ( 45.02 %, saved  4034 bytes) 19085.9000 ms
Packed9bo: 4908 bytes ( 45.22 %, saved  4052 bytes) 19008.4000 ms
Zipped:    5831 bytes ( 34.92 %, saved  3129 bytes)

__48x48_alpha_(sprites)

Original:  9792 bytes
Packed1:   7974 bytes ( 18.57 %, saved  1818 bytes)     2.3000 ms
Packed3:   5832 bytes ( 40.44 %, saved  3960 bytes)     1.9000 ms
Packed7o:  6106 bytes ( 37.64 %, saved  3686 bytes)    32.4999 ms
Packed8o:  4832 bytes ( 50.65 %, saved  4960 bytes)  4706.2000 ms
Packed9o:  4080 bytes ( 58.33 %, saved  5712 bytes) 45086.8000 ms
Packed9bo: 3848 bytes ( 60.70 %, saved  5944 bytes) 41432.0000 ms
Zipped:    4043 bytes ( 58.71 %, saved  5749 bytes)

__48x48_alpha_tmirror_(sprites)

Original: 20736 bytes
Packed1:  17186 bytes ( 17.12 %, saved  3550 bytes)     4.5999 ms
Packed3:  11490 bytes ( 44.59 %, saved  9246 bytes)     3.9000 ms
Packed7o: 11986 bytes ( 42.20 %, saved  8750 bytes)    42.7000 ms
Packed8o:  7750 bytes ( 62.63 %, saved 12986 bytes) 17320.5000 ms
Packed9o:  6316 bytes ( 69.54 %, saved 14420 bytes) 58749.2000 ms
Packed9bo: 5878 bytes ( 71.65 %, saved 14858 bytes) 42294.9000 ms
Zipped:    6421 bytes ( 69.03 %, saved 14315 bytes)

__48x64_alpha_tmirror_(sprites)

Original:  1536 bytes
Packed1:   1178 bytes ( 23.31 %, saved   358 bytes)     0.4000 ms
Packed3:    852 bytes ( 44.53 %, saved   684 bytes)     0.7000 ms
Packed7o:   956 bytes ( 37.76 %, saved   580 bytes)     8.6999 ms
Packed8o:   774 bytes ( 49.61 %, saved   762 bytes)   327.0999 ms
Packed9o:   628 bytes ( 59.11 %, saved   908 bytes)  2263.5999 ms
Packed9bo:  584 bytes ( 61.98 %, saved   952 bytes)  1181.3999 ms
Zipped:     623 bytes ( 59.44 %, saved   913 bytes)

__48x112_alpha_tmirror_(doors)

Original:  2688 bytes
Packed1:   2364 bytes ( 12.05 %, saved   324 bytes)     0.6999 ms
Packed3:   1256 bytes ( 53.27 %, saved  1432 bytes)     0.5000 ms
Packed7o:  1272 bytes ( 52.68 %, saved  1416 bytes)     4.5000 ms
Packed8o:   998 bytes ( 62.87 %, saved  1690 bytes)   204.4000 ms
Packed9o:   914 bytes ( 66.00 %, saved  1774 bytes)  4537.8000 ms
Packed9bo:  966 bytes ( 64.06 %, saved  1722 bytes)  3728.1000 ms
Zipped:    1226 bytes ( 54.39 %, saved  1462 bytes)

__64x56_alpha_(sprites)

Original:  5376 bytes
Packed1:   4030 bytes ( 25.04 %, saved  1346 bytes)     1.1000 ms
Packed3:   3086 bytes ( 42.60 %, saved  2290 bytes)     1.0000 ms
Packed7o:  3372 bytes ( 37.28 %, saved  2004 bytes)    13.4000 ms
Packed8o:  2288 bytes ( 57.44 %, saved  3088 bytes)  1537.5000 ms
Packed9o:  1970 bytes ( 63.36 %, saved  3406 bytes)  9992.5000 ms
Packed9bo: 1964 bytes ( 63.47 %, saved  3412 bytes)  9914.5999 ms
Zipped:    2327 bytes ( 56.72 %, saved  3049 bytes)

__64x56_alpha_tmirror_(sprites)

Original:  6272 bytes
Packed1:   4242 bytes ( 32.37 %, saved  2030 bytes)     1.4000 ms
Packed3:   2938 bytes ( 53.16 %, saved  3334 bytes)     1.1999 ms
Packed7o:  3310 bytes ( 47.23 %, saved  2962 bytes)    10.8000 ms
Packed8o:  2504 bytes ( 60.08 %, saved  3768 bytes)  1225.7000 ms
Packed9o:  2120 bytes ( 66.20 %, saved  4152 bytes) 19167.6000 ms
Packed9bo: 2100 bytes ( 66.52 %, saved  4172 bytes) 19712.1999 ms
Zipped:    2533 bytes ( 59.61 %, saved  3739 bytes)

--------------------------------------------------------------------------------------

Total Loaded:      65344 bytes
Total Packed1:     54154 bytes (  17.12 % )
Total Packed3:     40168 bytes (  38.52 % )
Total Packed7o:    41858 bytes (  35.94 % )
Total Packed8o:    28368 bytes (  56.58 % )
Total Packed9o:    24206 bytes (  62.95 % )
Total Packed9bo:   23270 bytes (  64.38 % )
Total Zipped:      26678 bytes (  59.17 % )
BEST TOTAL packed: 23078 bytes (  64.68 % )


The End