(26-05-2016, 10:25)Ash Skrev: http://stackoverflow.com/questions/14275...nary-files

Enjoy random binary fil med random data

Men alligevel... Det tager møj lang tid uanset hvad. Ud fra udregningen (16^5*4.3) skal der stadigvæk pakkes 16^5 filer (1.048.576) på 4.3GB hver

Bortset fra at når du har pakket den første fil fylder den ikke længere 4.3 GB, men 4.16 MB. Den zip-fil kopierer du så 15 gange (i alt 16 zip filer), pakker dem ned sammen og får en fil på 165 KB. Kopiér den 15 gange, pak sammen, næste fil fylder 32 KB, næste fylder 29 KB og den næste igen fylder 34.9 KB (Overhead har nok taget overhånd her).
Det vil sige at det reelt set kun er én gang du skal pakke 4.3 GB ned. Derefter er det bare en håndfuld MB og så nogle få KB.

Desuden tænker jeg, som nævnt tidligere, at filen ikke har ret mange forskellige tegn, siden den overhovedet kan fylde så lidt efter en tur gennem ZIP, og dette tager desuden kortere tid at pakke ned i forhold til tilfældige data.
Jeg mindes at ZIP bygger på huffman træer, som er ekstremt effektive når der er mange gentagelser, hvilket der er når det er den samme fil der er kopieret 16 gange og komprimeret på samme måde.

(26-05-2016, 15:00)Doctor Blue Skrev: Bortset fra at når du har pakket den første fil fylder den ikke længere 4.3 GB, men 4.16 MB. Den zip-fil kopierer du så 15 gange (i alt 16 zip filer), pakker dem ned sammen og får en fil på 165 KB. Kopiér den 15 gange, pak sammen, næste fil fylder 32 KB, næste fylder 29 KB og den næste igen fylder 34.9 KB (Overhead har nok taget overhånd her).
Det vil sige at det reelt set kun er éen gang du skal pakke 4.3 GB ned. Derefter er det bare en håndfuld MB og så nogle få KB.

Desuden tænker jeg, som nævnt tidligere, at filen ikke har ret mange forskellige tegn, siden den overhovedet kan fylde så lidt efter en tur gennem ZIP, og dette tager desuden kortere tid at pakke ned i forhold til tilfældige data.
Jeg mindes at ZIP bygger på huffman træer, som er ekstremt effektive når der er mange gentagelser, hvilket der er når det er den samme fil der er kopieret 16 gange og komprimeret på samme måde.

Yeah det er måske rigtigt nok. Men hvordan kan det kun være 4.3 GB -> 4.16 MB -> 165 KB osv. osv.? Jeg tvivler på, man kun skal pakke de 4.3 GB ned én gang.

(26-05-2016, 15:18)Ash Skrev: Yeah det er måske rigtigt nok. Men hvordan kan det kun være 4.3 GB -> 4.16 MB -> 165 KB osv. osv.? Jeg tvivler på, man kun skal pakke de 4.3 GB ned én gang.

Erh, det var noget vi lærte i algoritmer og datastrukturer, men det er ikke just mit favoritfag. Kort fortalt laver du en tabel over hvor ofte hver byte forekommer. Så laver du en kode (et symbol), for hver byte, som er kortere end en byte. Jo oftere byten forekommer, jo kortere symbol får den. Så hvis f.eks. 0xAA optræder oftest, siger du at 0xAA får symbolet 0. 0xBB forekommer næst-oftest, så den får 1. 0xCC forekommer tredje-oftest, så den får 10 osv. Så hvis du har en fil der kun består af 0x00 (nul-bytes), vil du give 0x00 symbolet 0 (1 bit). Så starter filen med en tabel der beskriver symbolet for hver byte, efterfulgt af den kodede fil, som i dette tilfælde ville være én 0-bit for hver 0x00 byte i filen. Hvis din fil er så simpel, kan du sågar gentage det samme (Hvilket jeg antager at ZIP gør, jeg ved det ikke) og gøre filen endnu mindre, da din fil så kommer til at bestå af, igen, 0-bits. Præcis samme fremgangsmåde, de får koden 0 og du mindsker filens størrelse 8 gange igen (Fordi én bit erstatter en byte i det her tilfælde). Til sidst er der en smule overhead i at gemme frekvenstabellen, så derfor vokser filen igen på et tidspunkt.

Det er en hurtig ikke-gennemlæst version af huffman-kodning jeg har i hovedet, men jeg anbefaler at du bare læser om det fra en som ikke bare prøver at få 02+ i et datalogi-fag ;)
https://en.wikipedia.org/wiki/Huffman_coding

ZIP bruger oftest DEFLATE som er en kombination af LZ77 og huffman-kodning, så der er lidt mere over det, men jeg tror at den kære huffman gør det meste af arbejdet i dette tilfælde.
https://en.wikipedia.org/wiki/DEFLATE

EDIT: Det kan være at jeg laver nogle mere dybdegående (og gennemtænkte) tråde om pensum i algoritmer og datastrukturer når jeg går i gang med at forberede eksamen om ikke så frygteligt længe. Det kommer lidt an på hvor presset jeg er :)

(26-05-2016, 22:28)Doctor Blue Skrev: Erh, det var noget vi lærte i algoritmer og datastrukturer, men det er ikke just mit favoritfag. Kort fortalt laver du en tabel over hvor ofte hver byte forekommer. Så laver du en kode (et symbol), for hver byte, som er kortere end en byte. Jo oftere byten forekommer, jo kortere symbol får den. Så hvis f.eks. 0xAA optræder oftest, siger du at 0xAA får symbolet 0. 0xBB forekommer næst-oftest, så den får 1. 0xCC forekommer tredje-oftest, så den får 10 osv. Så hvis du har en fil der kun består af 0x00 (nul-bytes), vil du give 0x00 symbolet 0 (1 bit). Så starter filen med en tabel der beskriver symbolet for hver byte, efterfulgt af den kodede fil, som i dette tilfælde ville være én 0-bit for hver 0x00 byte i filen. Hvis din fil er så simpel, kan du sågar gentage det samme (Hvilket jeg antager at ZIP gør, jeg ved det ikke) og gøre filen endnu mindre, da din fil så kommer til at bestå af, igen, 0-bits. Præcis samme fremgangsmåde, de får koden 0 og du mindsker filens størrelse 8 gange igen (Fordi én bit erstatter en byte i det her tilfælde). Til sidst er der en smule overhead i at gemme frekvenstabellen, så derfor vokser filen igen på et tidspunkt.

Det er en hurtig ikke-gennemlæst version af huffman-kodning jeg har i hovedet, men jeg anbefaler at du bare læser om det fra en som ikke bare prøver at få 02+ i et datalogi-fag ;)
https://en.wikipedia.org/wiki/Huffman_coding

ZIP bruger oftest DEFLATE som er en kombination af LZ77 og huffman-kodning, så der er lidt mere over det, men jeg tror at den kære huffman gør det meste af arbejdet i dette tilfælde.
https://en.wikipedia.org/wiki/DEFLATE

EDIT: Det kan være at jeg laver nogle mere dybdegående (og gennemtænkte) tråde om pensum i algoritmer og datastrukturer når jeg går i gang med at forberede eksamen om ikke så frygteligt længe. Det kommer lidt an på hvor presset jeg er :)

Well okay, lad os antage jeg forstod det og sige du har sgu nok ret ja.
Burde nok have taget det fag også

(26-05-2016, 22:39)Ash Skrev: Well okay, lad os antage jeg forstod det og sige du har sgu nok ret ja.
Burde nok have taget det fag også

Det er interessant, men også tungt, stof. Hvis jeg selv havde valgt faget var det nok mere af interesse end af nød, for jeg sigter meget langt udenfor det område når jeg engang skal søge arbejde.

(26-05-2016, 22:48)Doctor Blue Skrev: Det er interessant, men også tungt, stof. Hvis jeg selv havde valgt faget var det nok mere af interesse end af nød, for jeg sigter meget langt udenfor det område når jeg engang skal søge arbejde.

Det er rimelig tungt stof ja. Det siger mine klassekammerater også. Meeen så vil jeg sgu hellere have IT sikkerhed.

Jeg skulle lige prøve at pakke en stor fil. Her er resultatet:

Citer:Denne (ældre) maskine har 16GB ram og 2x 4 kerner:
vendor_id : GenuineIntel
model name : Intel® Xeon® CPU E5410 @ 2.33GHz
cpu MHz : 2327.515
cache size : 6144 KB
cpu cores : 4

Jeg har ikke målt skrivehastigheden, men maskinen har et raid af WD RED 3 TB diske.

CPUen stod på mellem ~70 og 78% mens filen blev pakket.

Citer:root@hacker:/var/zipbomb# /usr/bin/time -f "%E" zip zipbomb.zip zipbomb.bin
adding: zipbomb.bin (deflated 100%)
4:20:24
root@hacker:/var/zipbomb#

Så det har taget fire timer og tyve minutter at pakke godt en 1TB fil.

Citer:root@hacker:/var/zipbomb# ls -Alh
totalt 1,1T
-rw-r--r-- 1 root root 1,1T maj 26 14:42 zipbomb.bin
-rwxr--r-- 1 root root 343 maj 26 10:21 zipbomb.rb
-rw-r--r-- 1 root root 1018M maj 26 19:11 zipbomb.zip
root@hacker:/var/zipbomb#

root@hacker:/var/zipbomb# ls -Al
totalt 1074785000
-rw-r--r-- 1 root root 1099512676352 maj 26 14:42 zipbomb.bin
-rwxr--r-- 1 root root 343 maj 26 10:21 zipbomb.rb
-rw-r--r-- 1 root root 1067045307 maj 26 19:11 zipbomb.zip
root@hacker:/var/zipbomb#

Det kan være jeg prøver at pakke en stak af disse sammen, bare for at se hvad det ender med.

---

Ok, det gav så ikke meget at pakke 16 filer sammen:

Citer:root@hacker:/var/zipbomb/l2# ls -Alh
totalt 32G
-rw-r--r-- 1 root root 1018M maj 27 12:24 zipbomb_10.zip
-rw-r--r-- 1 root root 1018M maj 27 12:25 zipbomb_11.zip
-rw-r--r-- 1 root root 1018M maj 27 12:25 zipbomb_12.zip
-rw-r--r-- 1 root root 1018M maj 27 12:25 zipbomb_13.zip
-rw-r--r-- 1 root root 1018M maj 27 12:25 zipbomb_14.zip
-rw-r--r-- 1 root root 1018M maj 27 12:26 zipbomb_15.zip
-rw-r--r-- 1 root root 1018M maj 27 12:26 zipbomb_16.zip
-rw-r--r-- 1 root root 1018M maj 27 12:23 zipbomb_2.zip
-rw-r--r-- 1 root root 1018M maj 27 12:24 zipbomb_3.zip
-rw-r--r-- 1 root root 1018M maj 27 12:24 zipbomb_4.zip
-rw-r--r-- 1 root root 1018M maj 27 12:24 zipbomb_5.zip
-rw-r--r-- 1 root root 1018M maj 27 12:24 zipbomb_6.zip
-rw-r--r-- 1 root root 1018M maj 27 12:24 zipbomb_7.zip
-rw-r--r-- 1 root root 1018M maj 27 12:24 zipbomb_8.zip
-rw-r--r-- 1 root root 1018M maj 27 12:24 zipbomb_9.zip
-rw-r--r-- 1 root root 16G maj 27 12:33 zipbomb_l2.zip
-rw-r--r-- 1 root root 1018M maj 26 19:11 zipbomb.zip

Gad vide om WinZIP eller noget andet er brugt?!