Názory k článku Kompresní algoritmy v souborech ZIP: Store a Shrink

Central Directory na konci souboru. Tato vlastnost také umožňuje pěknou hříčku, jak vytvořit soubor, který se chová zároveň jako PNG tak i jako ZIP.
Tak se ZIPem se obecně dají dělat různé kousky, třeba zip bomba. Kdysi jsem k tomu četl pěkný článek a myslím, že to byl tento - https://www.bamsoftware.com/hacks/zipbomb
(Mám trochu nepořádek v záložkách)

Myslím, že těch triků s central directory bylo víc. Jeden srandovní trik spočíval v tom, že se vytvořil soubor ZIP se dvěma centrálními adresáři, což v součinnosti s některými programy dělalo divy. Trik byl určený k obejití ochrany emailů. Při kontrole emailu se objevil a prošel legitimní soubor (třeba JPG), ale při rozbalování se rozbalovalo podle druhého centrálního adresáře (v konkrétně šlo o spustitelný soubor). Ale záleželo to na tom, jak se program stavěl k okolnostem, které nebyly zcela definované ve specifikaci. Tam sice je, že centrální adresář musí být jen jeden, ale už tam myslím není, že je to nutné kontrolovat a jak se má program zachovat, když tam jsou dva. WinRAR to sežral i s navijákem, průzkumník Windows vyhodil chybu a skončil a 7-zip zobrazil chybu, ale dál fungoval a rozbaloval stejné soubory které se kontrolovaly.

[ https://www.bleepingcomputer.com/news/security/specially-crafted-zip-files-used-to-bypass-secure-email-gateways/ ]

Něco podobného bylo problémem na Androidu. Android aplikace (soubory s příponou *.apk) jsou vlastně *.jar archívy, což jsou vlastně *.zip archívy. Archív obsahoval dva soubory, třeba a.class a b.class. Kde ten první obsahuje nevinný kód aplikace a ten druhý obsahuje malware nebo virus. Hex editorem potom v tom ZIPu přejmenujeme b.class na a.class (a možná opravíme checksum, už si to nepamatuju). Při instalaci takové aplikace ji jedna komponenta Androidu napřed zkontroluje. Jiná komponenta Androidu ji pak nainstaluje. Problém je v tom, že každá komponenta Androidu rozbalí jiný soubor a.class, tudíž kontrola projde, ale nainstaluje se virus. Jedna komponenta byla napsaná v Cčku a druhá v Javě. Řešením je (podle mě) odmítnout takový archív v obou komponentách. Marek.

Neřekl bych, že je "store" algoritmus nezajímavý. Napadají mě hned tři další využití. První je jednoduchá možnost šifrování, která je dostupná v převážné většině počítačů (doporučuji ale zjistit, jak kvalitně šifruje používaný program).
Druhé využití je zrychlení kopírování v případě, kdy jde o kopírování malých souborů. Záleži hodně na okolnostech, ale nějaká výhoda to je.
Třetí možnost jsem využil nedávno. Zálohoval jsem něco na externí disk a zjistil jsem, že 300 GB dat zabírá na disku 600 GB! (Malé soubory a velké clustery). Po velmi rychlém "store" zazipování jsem to setřepal na očekávaných 300GB

Algoritmus store je zajímavý také pro soubory, které už samy o sobě jsou komprimované – PNG, JPG, OOXML, ODF… Komprimovat je znovu je jen ztráta času, je jen věcí náhody, jestli se o pár bajtů zmenší nebo zvětší.

To zip nedělá, že by kontroloval kompresibilitu a podle toho měnil algoritmus. To musí udělat uživatel přepínačem -0, ale pak se to týká všech souborů. Ono je lepší asi pustit na všechno Deflate, již komprimované soubory se nijak podstatně nezvetší.

Tak jak říkáte tu kompresibilitu dopředu testuje například lrzip, k testování použije rychlý algoritmus lz4.

Malý test:

$ zip -r foo.zip *
....
adding: test/ugly/thre­enleof-vg.txt (deflated 45%)
adding: test/ugly/twobl-vg.txt (deflated 45%)
adding: test/ugly/twonleof-vg.txt (deflated 45%)
adding: test/ugly/hsclass-vg.txt (deflated 45%)
adding: test/.asm (stored 0%)
adding: test/test-int.out (deflated 73%)
adding: test/all.diff (stored 0%)
adding: test/selfcheck.out (stored 0%)

[jirka@omelette trunk]$ zip --version
Copyright (c) 1990-2008 Info-ZIP - Type 'zip "-L"' for software license.
This is Zip 3.0 (July 5th 2008), by Info-ZIP.

Výstup PKZIPu byl podobný (deflating, storing. imploding). Tak jsem něco asi špatně pochopil

No nevím, co jsou ty .asm, all.diff a selfcheck.out zač. Nemají velikost 0 třeba?

Teď jsem to tu zkoušel a deflate dělá u všeho včetně jpg, odt, pdf, kromě adresářů, nulových souborů a zip souborů, tam dělá store.

Ještě kompresibilitu testuje btrfs s parametrem compress=. Ale dělá to jen na kousku ze začátku souboru, takže pokud máte soubor na začátku náhodný a pak samé nuly, tak se nebude na disku komprimovat. Ono zase testovat celý soubor by trvalo dlouho.

Jde to obejít pomocí compress-force=, pak se nic netestuje a vše komprimuje.

Nedělá. On většinou ten deflate něco málo ubere, takže když jde člověk na hranu, tak to může dávat smysl. Pokud jde ale o soubory, které se pravidelně v runtime otvírají (například JAR), tak to procento ušetřené velikosti je dost kontraproduktivní, bo cena za opakovaně přetěžované CPU bude vyšší než ušetřených pár bytů.

Řešili jsme to někdy před dvaceti lety, když jsme vytvářeli zip se soubory pro hru - tehdy to byl snad jednoduchý shell nebo perl script, který pouštěl zip -0 nebo zip -9 podle přípony. Později jsem za jiným účelem napsal něco podobného znovu, s tím, že to rozlišovalo i úspěšnost komprese (byla to hračka na odpoledne, takže neumí příliš extra a má limity například kvůli byte array length, ale účel to splnilo, pull requests případně vítány ): https://github.com/kvr000/adaptive-zip

PS: zip dnes umí například i Zstandard, který je většinou lepší než Deflate, ale bude samozřejmě chvilku trvat, než jej budou všechny zip utility podporovat...

Nezajímavý pro popis, jinak uplatnění si najde. Stejně je možné použít tar a rychlou kompresi lzop, lz4, nebo zstd.

Díky moc za velmi zajímavý a názorný článek. Komprese pro mě byla vždy tak trochu magie. Těším se na pokračování.

Pro nas pomalejsi, slo by dovysvetlit jak probiha ta rekonstrukce slovniku prosim?

Při dekompresi? Stejně jako při kompresi. Dostanu kód pro T, dám na výstup T, další je kód pro R, na výstup dám R. Ve slovníku není ještě TR, tak ho tam doplním s následujícím kódem.

Mo diky. Myslim ze jsem odpovedel off thread omylem. Kdyztak pls koukni.

Aha. To zni podezrele jednoduse.
Zkusim to parafrazovat - zakaldemje ze mame znamy prvotni slovnik, kde kazda osmibitova kombinace ma kod.. osmibitovy. (v clanku pises znak - coz mi zni spatne neb komprimujeme i binarky, proto to pisu tak divne)

Ted tedy dekomprimuji - najedu neznamy kod (pro TR) a jelikoz znam kody T a R, pak si domyslim TR? Ne to nezni spravne...

Kod pro TR se tedy nemuze objevit dokud se neobjevi T i R? Asi ano.. pak to dava smysl...

Prosim jeste doupresnuj. Je to zajimavy trik.

Jak pises "TR" jeste ve slovniku neni, takze vlastne na zacatku celeho streamu jdou data bez komprimace (ted trosku zjednodusuju). Prijde T, dekomprimujes na T, prijde R, dekomrimujes na R *a pritom tvoris slovnik*, takze ti dalsi TR uz prijde v jinem kodu (treba 257).

Hm. Tak to zase chapu o neco min

Zkusím, co je na tom možná neintuitivního. Jak při kompresi, tak při dekompresi, se vytváří slovník z toho co bylo, BEZ OHLEDU na fakt, zda je to prospěšné či není.
- Takže přijde "T" - to už je ve slovníku, to je základní písmeno.
- Přijde "R" - podíváme do slovníku zda máme "TR", nemáme, takže na výstup musíme dát stále ještě jen čisté "R" (to už je ve slovníku, to je základní písmeno). A do interního slovníku, pro tento soubor a tuto kompresi, přidáme "TR", pokud bychom ho MOŽNÁ NĚKDY PŘÍŠTĚ během této (de)komprese uviděli, můžeme použít jako unikátní zakódované slovo.

Důsledky:
- První výskyt "TR" ještě není zakódovaně přímo, ale jako jednotlivá písmena, takže žádná úspora při prvním výskytu.
- Pokud se dané slovo (sekvence) vyskytuje jen jednou, nebo málo často, akorát nám zabírá místo ve slovníku (a unikátní kód) naprosto zbytečně.
- Proto to dobře funguje na delší běžný psaný text (opakující se stejná slova, sekvence), delší zdrojáky a podobně, méně kvalitně pak na binární věci.
- Interní slovník se po každé jednotlivé kompresi (každém jednom souboru) zahodí a jinde využívaný není. Některé kompresní programy to mají jinak, slovníky mohou zachovávat přes více souborů (má to výhody i nevýhody), ale v ZIP se slovník zahazuje a vždy vytváří znovu.

Cau! Jo to je dobre doplneni. diky.

Dve doplnujici otazky
1) zakaldani slovnik ma 255 "znaku", tedy obsahuje vsechny byty. Na pozici 256 bude kod prvniho dvoubytove kombinace. oook? Na pozici 257 pak dalsi dvoubytvoa kombinaci priapdne prvni trojbytova. oook?

2) dekomprese - tedy restrukturalizace slovniku - najdu kod 0-255 to je jednoduche, v okamziku kdy najdu vyssi, tak se podivam tim stromem nahoru, z ceho byl ten "znak" slozen?

Diky za trpelivost!

Díky moc za pěkný článek. Vůbec jsem netušil jak zip algoritmus funguje a celkem mě překvapuje, že jsem se s tím nikde nesetkal. Já jsem moc nepochopil reset slovníku. To se jako začne ten slovník tvořit uplně znovu a ty současné kódy se uplně zahodí? Tj. komprese začne znovu úplně od začátku?

21. 4. 2021, 15:19 editováno autorem komentáře