☰

» »

[Naloga] : Max kompresija testne datoteke

[Naloga] : Max kompresija testne datoteke

StratOS ::

Pozdravljeni.

Vaša naloga :
Imate Small PE.exe (v tem primeru gre za PE izvršilno ).
Gre za nezlonamerno kodo, če že koga zanima !
Gre namreč za majhno izvršilno datoteko 680 bytes, ki ven vrže Messagebox z sledečim napisom

Hex vsebina :


Torej, potrebujemo kompresijski algoritem ki bo preslikal testno datoteko v novo datoteko, ki bo manjše velikosti, pri čem bo inverzna operacija algoritma vrnila točno isto in enako testno datoteko.

Uporabljate lahko različne prijeme in programe v zgoraj navedenimi prijemih testne datoteke.
Sam sem probal z različnimi pristopi, programi ipd, vendar kompresija mi pod 369 bajti ne gre več ( recimo lzh kompresija ).
Torej iščemo kompresirano datoteko z najmanjšo možno velikost ob popolni reverzni preslikavi, torej dekompresiji.
Torej iščemo najboljši tip kompresije za zelo majhne datoteke oziroma le ta tip vsebine datoteke.

Vsak preglog in test dobrodošel

Trenutno najboljši : Quikee 332b
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

t909 ::

paging Thomas...

Quikee ::

LZMA - 333b

netanyahu ::

Obstaja trivialen algoritem, ki natanko in le tvojo datoteko stisne na 1 bit. Velik je 680 + nekaj bajtov. Ostale datoteke podaljša za en bit.

StratOS ::

Quikee
LZMA - 333b


Bi prosil še link do programa oz. nastavitve parametrov programa/algoritma ter upload kompresirane datoteke, če lahko.
Hvala.

[EDIT]
Hvala že našel lzma:
http://sourceforge.net/project/download...

Probal se bom še malce pozabavati z switchi.
Z standardnim dobim 332b
lzma e "Small PE.exe" "Small PE.exe.lzma"

LZMA  4.58 beta  Copyright (c) 1999-2008 Igor Pavlov  2008-05-05
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Zgodovina sprememb…

  • spremenila: StratOS ()

Jean-Paul ::

Prvi, ki sem ga preizkusil:
paq8o10t (http://www.cs.fit.edu/~mmahoney/compres...

Prevajanje:
nasm -f elf paq7asm.asm
g++ paq8o10t.cpp -DUNIX -O2 -Os -s -march=pentium4 -fomit-frame-pointer -o paq8o10t paq7asm.o

Pognal sem ga tako:
./paq8o10t -2 Small\ PE.exe

Rezultat je komprimirana datoteka velikosti 328 B

Bojevnik ::

Lahko ga pa tudi sam napišeš, glede na to, da je v tvoji datoteki zelo veliko zaporedji samih nul, ne bi smelo biti težko.

StratOS ::

Dobro, v kompresijo se kaj dobro poznam, vendar v tem primerih niti ne postavljam kakšnih dobrih kompresij, tudi 500b po frekvencah je zelo OK. Probaj sam, pa javi. Ni tako lahko.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Bojevnik ::

Mislil sem tako npr imaš

0000 0000 0000 0000, to lahko zakriptiraš 0120 (12 neprekinjenih ničel)
0000 -> 040 (4 ničle)
A400 04500 0066 -> A403 0450 4066
Paš namesto neprekinjenega števila ničel vstaviš 0<število ničel>0

Pri tem sta problem samo ko imaš eno ali dve ničli ker ti stvar dejansko razširi. Ker je pa dvojnih ničel zelo malo lahko brez problema pustiš 020,
enojne pa lahko spremeniš v 00 namesto 010.

Res pa je, da kaj takega nisem nikoli programiral, tako da lahko nimam pojma :)

Zgodovina sprememb…

  • spremenilo: Bojevnik ()

StratOS ::

Hja 680b--> 500b je že kar nekaj na lastnem zeljniku, vendar ne bom ugotavljal Jean-Paul in njegovih 328b, tu pa gre res za bite.
Torej že 100+ bitov špar placa na lastnem zeljniku je dokaj veliko, seveda pa treba napisati tudi loseless inverzijo funkciji kompresije za pridobitev identične datoteke.
Probal sem z različnimi varijantami raw video in avdio kompresije, rezultati se ne morejo primerjati z obstoječimi.

Vseeno pa hvala na razmišljanju, še vedno iščemo zmagovalca.
328b
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

MaFijec ::

Heh. Kompresiraš samo eno datoteko. Tako lahko narediš program, ki kot spremenljivko vsebuje to datoteko. Kompresirana datoteka je lahko kar prazna. Nazaj bos dobil natanko isto datoteko (izpišes vrednost spremenljivke) :)

Bolje definiraj problem.

StratOS ::

Bi rekel, da bolje preberi problem, ne gre le za način kompresiranja in sam algoritem, gre tudi za inverzno funkcijo in pridobitev originalnih podatkov in ne za konstante kot izhodišče, v tem primeru ne gre za nobeno kompresijo, ampak samo raw zapis - eden in isti, torej kompresirana datoteka je enaka izvirniku, in kje ti vidiš tu napredek. Iz 680b sedaj z kompresijo dobimo 328b datoteko, ki jo lahko inverzno pretvorimo v original, torej cca 48,2% kompresija. Tudi v tvojem primeru izhodna datoteka 'ne more biti prazna', po drugi strani bi pa uporabljal kar 2 ( najsibo tudi konstanto ).In kaj bi prazna datoteka in preslikava pomenila ?
Gre za čisto ne-injektivno preslikavo, čisto neodvisno od zastavljenih osnovnih pogojev.Pri bijektivni preslikavi pa gre ravno za enak problem, vedno obstaja inverzna funkcija, vendar v tem primeru ne gre za kompresijo (enako število elementov).
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

MaFijec ::

Ne razumeš. Napišeš program, ki kot parameter dobi tvojo datoteko. Le to datoteko zakodiraš v sam program. Po kompresiranju vrneš recimo prazno datoteko. Iz prazne datoteke bijektivno! preslikaš v originalno datoteko.

Druga stvar je, če hočeš algoritem, ki ne bo kompresiral samo končne množice datotek, ampak bo deloval za poljubno datoteko.
Ali pa podaš omejitev velikosti programa, ki kompresira.

krneki0001 ::

Ne da se exeja snet dol z neta, drugače bi se malo igral.

Jean-Paul ::

MaFijec ma čisto prav. Vendar se zdi smiselno postaviti omejitev t.i. "read-only" programa. Torej program ne sme več spreminjati samega sebe po tem, ko je že "vrgel uč" na vhodno datoteko, piše lahko le v izhodno (komprimirano) datoteko.

Zgodovina sprememb…

MaFijec ::

V bistvu je problem že, ker je podana omejitev na majhne datoteke. To je končna množica. Množico lahko zmeraj znova oštevilčimo tako, da je je kompresirana datoteka prva. To ponazorimo tako, da jo preslikamo v prazno datoteko. Druge datoteke indeksiramo poljubno.

Torej bo program malo večji kot zasedejo prostora vse možne majhne datoteke skupaj. Katerokoli datoteko bo sposoben kompresirati v prazno. Preslikava bo seveda bijektivna. Koda programa bo fiksna!

StratOS ::

Torej, potrebujemo kompresijski algoritem ali program, ki bo preslikal testno datoteko v novo datoteko, ki bo manjĹĄe velikosti, pri Äem bo inverzna operacija algoritma vrnila toÄno isto in enako testno datoteko.

Torej kompresijski algoritem mora delovati tudi na vseh ostalih moĹžnih testnih datotekah. Rezultate kompresij sem pa zaradi laĹžje predstave fiksiral na zgornje omenjeno testno datoteko,tako da lahko to tudi ovrednotimo.Torej algoritem ali program more delovati na poljubni datoteki in inverzna funkcija - dekompresija vrne isto vhodno datoteko.
Res pa je da sem ĹĄel v ekstrem malih datotek, lahko bi izbral katerikoli drugo vrsto datotek (testnih),glavno pa je v tem, da ne morete uporabljati kakĹĄnih PE kompresijskih algoritmov ( torej ni pogoj, da je izhodni MsgBox isti, kar bi lahko najhitreje naredil z zelo kratko VB ipd skripto, gre torej le za kompresijski algoritem celotne datoteke in ne le doloÄenih PE headerjev in konÄni runtime izgled te 'aplikacije' - testne datoteke ).

Upam da smo se razumeli da gre le za inverzen kompresijski primer, ki se boduje paÄ na tej datoteki.

Hja, no z bbb (Burrows-Wheeler transform) se dobi tudi 319b.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Zgodovina sprememb…

  • spremenila: StratOS ()

BigWhale ::

A bi rad napisal specificni algoritem, ki bo stisnil tako dobro stisnil samo tole datoteko? Ali bi rad, da vse datoteke stisne cim bolje? Tisto kar je opisal Bojevnik je RLE kompresija, ki je dobra v nekaterih primerih. Ne v vseh. Podobna je packedbits kompresija od appla. Nekaj casa nazaj sem v sluzbi uporabil modificirano varianto packed bits kompresije za precej velika polja bitov.

StratOS ::

Algoritem in sam postopek kompresije je odvisen od začetne datoteke in sekvence znakov itd ..
Torej gre le za primerjavo kompresije te datoteke, pri kateri drugi ali spremenjeni datoteki bi kateri drugi program/algoritem bil boljši.
Torej točkuje se na to datoteko.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Wrop ::

Jaz sm dobil s svojim algoritmom nekaj manj kot 400B. Inverza še nisem naredil. Bom pa v nekaj dneh, če se mi bo dalo. No saj ni nič posebnega, samo bere znake in če še so trije ali več zaporedoma, jih skrajša.

Thomas ::

Hja, smo dal računati Critticallu. Za začetek je rezultat 320 byteov, brez razvite kode.

http://critticall.com/cache.html
Man muss immer generalisieren - Carl Jacobi

-_- ::

Jaz prišel na 251 bajtov veliko datoteko. Za kompresijo in inverzijo sem uporabil bbb. Spodaj je opis, ki velja za PE datoteke, za ostale pa se uporabi samo bbb.

PE datoteke imajo prvih 128 bajtov enakih, kar nam da datoteko veliko 552 bajtov, vzamemo pa še 2 bajta za oznako datoteke in dobimo datoteko veliko 554 bajtov.Potem datoteko kompresiramo z bbb in dobimo velikost datoteke 251 bajtov. Inverzijo naredimo z bbb. Najprej preverimo prva dva bajta, potem namesto njiju v datoteko vstavimo oznako za PE datoteke in imamo enako izvorno datoteko.

Thomas ::

More bit pod 200 ...
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Dobro za to vrsto PE kode bi lahko rekli, da ima 134b istih, vendar pa gre za kompresijo celotne datoteke.
Ok ostali del datoteke lahko z bbb enkodirtamo in na začetek kompresirane nove datoteke dodamo pač znak za začeten vriv PE headerja, pač za ta tip datoteke (134b), ostale pa potem inverzno z bbb prispojimo še ustvarjenem headerju PE fajla.
Res je da za ta tip datoteke v celoti trenutno vodi bbb 319b.

Zato bi hotel da se z isto metodo algoritma kompresira celotna datoteka in ne z pomočjo kakšnih delov ali konstant v osnovni datoteki ustvarjamo nove parametre oz. datoteke.

Lahko pa se uporabi sequenčna in frekvenčna analiza, vendar lastne izkušnje zaradi majhnosti datoteke ne dajo preveč velikih končnih rezultatov. Sam tudi sprobavam loseless raw kompresijo videa in avdia kot binarni zapis podatkovnega headerja zapisa torej testne datoteke. Probleme imam z časovno postavitvijo trajanja oz. frami, da kreiram raw video/audio iz te testne datoteke. Ima kdo kakšen boljši pristop k temu ?
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Zgodovina sprememb…

  • spremenila: StratOS ()

Thomas ::

Sej. Iz ust si mi vzel. Da nekaj nekam skopiraš, ne velja, če tistega ne šteješ zraven. Se bom zvečer razpisal mau.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Recimo ... šteti k komprimiranemu delu, je treba tudi kompres algoritem sam!!!

Naslednji kompres je precej učinkovit na tejle datoteki. 00000000->0 else XYZTWURS->1XYZTWURS

Torej, 8 zaporednih bitnih ničel označimo z 0, vsak drug bitni string dolžine 8, pa zapišemo kot 1 plus tisti string.

A algoritem je treba pripisati k outputu. Kako?
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Zato je mečkanje majhnih datotek še bolj kočljiva reč. Pripisati kar ves zipper.exe k megabyteu stisnjene datoteke, kar je, kot smo rekli, edino pravično, ne pomeni nič.

Pri majhnih datotekah pa je 20 kB ogromno, celo prevladujoča količina.

Zato bi naloga morala biti mogoče takale: Kdo bo naredil najmanjši exe, ki naredi takle string, če exe zalaufaš.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Torej selfextractor v sistemu Windows, brez dosptopa do Interneta. Celo brez dostopa do sistemskih datotek Windows, da ne bi iz kakšnega dll potegnil manjkajoče kose.

Ne vela.

Zato nam preostane bolj teoretično razglabljanje. IMO.
Man muss immer generalisieren - Carl Jacobi

BigWhale ::

Thomas, nekaj podobnega smo ze poceli davno nazaj... Tule. :))

Zgodovina sprememb…

  • spremenil: BigWhale ()

Thomas ::

Strogo govorjeno, nekaj informacije, da Unzip.exe lahko naredi en .TXT fajl iz .ZIP ven, je skrito v mikrokodi procesorja Intel ali AMD. Zato tudi self extractor, se na to informacijo fundamentalno naslanja. Kompres je vedno relativen, odvisen od informacij v okolju, za katere bi se kdo prehitro zaklel, da jih ni.

Ko Unzip.exe opravi svoj unziping bitnega stringa, je uvozil nekaj informacije tudi iz Maxwellovih zakonov!

Težko rečem koliko, ampak po moje kakšnih 100 bitov. Od oka.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Je pa tudi res, da pkzip/pkunzip exe lahko porazdelimo na vse z njim stisnjene datoteke tega sveta. Tako, da na vsako ne pride niti en bit pkzip.exe-ja.

Cache kompres, ki ga jaz predlagam na strani ki sem jo linkal, je učinkovit. Zevoluira sam, sploh če imamo variabilno število prediction spremenljivk.
Man muss immer generalisieren - Carl Jacobi

Thomas :: 


 DECLAREINT unpredicted one four zero mm i characters x p1 p2
 $DIMENSION input[680] output[680]
 $WEIGHTS commands=0
 $PENVAL unpredicted 
 $RESVAR unpredicted x characters input[]
 $INVAR input[](77,90,144,0,3,0,0,0,4,0,0,0,255,255,0,0,184,0,0,0,0,0,0,0,64,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,128,0,0,0,14,31,186,14,0,180,9,205,33,184,1,76,205,33,84,104,105,115,32,112,114,111,103,114,97,109,32,99,97,110,110,111,116,32,98,101,32,114,117,110,32,105,110,32,68,79,83,32,109,111,100,101,46,13,13,10,36,0,0,0,0,0,0,0,80,69,0,0,76,1,1,0,129,66,72,66,0,0,0,0,0,0,0,0,224,0,15,1,11,1,2,50,8,1,0,0,0,0,0,0,0,0,0,0,210,1,0,0,160,1,0,0,0,0,0,0,0,0,64,0,4,0,0,0,4,0,0,0,4,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,168,2,0,0,160,1,0,0,0,0,0,0,2,0,0,0,0,0,16,0,0,16,0,0,0,0,16,0,0,16,0,0,0,0,0,0,16,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,60,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,80,2,0,0,20,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,46,116,101,120,116,0,0,0,6,1,0,0,160,1,0,0,8,1,0,0,160,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,32,0,0,224,84,104,101,32,115,109,97,108,108,101,115,116,32,80,69,32,116,104,105,110,103,32,58,41,0,72,101,114,101,32,119,101,32,103,111,32,97,103,97,105,110,32,100,117,100,101,32,58,41,0,106,0,104,160,1,64,0,104,185,1,64,0,106,0,232,7,0,0,0,106,0,232,12,0,0,0,255,37,80,2,64,0,255,37,84,2,64,0,255,37,92,2,64,0,204,204,60,2,0,0,0,0,0,0,0,0,0,0,126,2,0,0,80,2,0,0,72,2,0,0,0,0,0,0,0,0,0,0,152,2,0,0,92,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,100,2,0,0,114,2,0,0,0,0,0,0,138,2,0,0,0,0,0,0,100,2,0,0,114,2,0,0,0,0,0,0,138,2,0,0,0,0,0,0,157,1,77,101,115,115,97,103,101,66,111,120,65,0,98,2,119,115,112,114,105,110,116,102,65,0,117,115,101,114,51,50,46,100,108,108,0,0,128,0,69,120,105,116,80,114,111,99,101,115,115,0,107,101,114,110,101,108,51,50,46,100,108,108,0,0,0,0) characters (680)
 $RETVAR output[]
 $MINIMIZE LINES 50
 
 unpredicted=characters; // setting unpredicted to the number of characters
 one=1;four=4;zero=0;
 for (x=zero; x<characters; x++) { 
 mm=input[x]; 
 if (mm==p1) {
 unpredicted--; // decrease unpredicted ($PENVAL unpredicted ) it had been predicted right
 } else { 
 if (mm==p2) {unpredicted--;} // decrease unpredicted ($PENVAL unpredicted ) it had been predicted right
 } 
 output[x]=input[x]; // copy a character (its ASCII number) from input to output data
 $BES
 // HERE, a predicting algorithm should evolve. 
 // This is the area, where Evolution may take place and grow an embryo code.
 // In attempt to minimize the value of uncached, misspredicted characters 
 $EES
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Ja res je BigWhale, z tem smo se zabavljali pred nekaj časa, kaj moreš, še dobro, da se nekateri spomnejo 'mučenja', no zdaj smo zašli spet v druge vode.
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Thomas ::

No, da pokomentiram kodo, ki sem jo pustil zgoraj. Cache kompres. Veliko je različnih cacheov, ki ugibajo, kakšen bi bil naslednji byte ali več byteov ali določeno število bitov.

Iščemo torej takšen cache, ki ugane čimveč. Pa vendar naj bo čim manj biten, ker sicer bo preveč luksuzno treba zapisati vsak zadetek in stopnja kompresa ne bo prav velika.

Optimalni kompromis je N mnogo spremenljivk p1, p2, ... pN tako, da bo čimvekrat v vsaj eni od teh spremenljivk pravilna vrednost. Ki bo hkrati pokrila največ od teh 8*680=5440 bitov.

Če je p1="00000000" in p2="0000000000000000", potem bomo imeli takole preveden niz:

iz byteov:

77,90,144,0,3,0,0,0,4,0,0,0,255,255,0,0,184,0,0,0,0,0,0,0,64,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

v bite:

101001101,101011010,110010000,00,100000011,01,00,100000100,01,00 ....

Možnik keširanj in njih politik, je maljone maljard, po tamalem. Zgornji Critticall source vam (morda še dodatno izboljšan), evoluira tele cache in cache komprese. Pod 200 byteov se da priti že na ta način. NI pa najboljši od vseh možnih.
Man muss immer generalisieren - Carl Jacobi

StratOS ::

Hja problem pri vsaki frekvenčni analizi je vzpostava ustreznega parametra,byta in to čimmanjšega.
Večkrat ponovljeni deli (skupki bytov) lahko predstavljajo kak nov alla 'parameter' recimo en byt, ki pa se v celotni datoteki ne ponavlja, zato je možna inverzna transformacija.

Primer datoteke : (povzemimo thomasa, datoteka kot celota bytov)
Raw:
77,90,144,0,3,0,0,0,4,0,0,0,255,255,0,0,184,0,0,0,0,0,0,0,64,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Transformacija bytov :
00 -->1
000 -->2
0000000 -->5
000000000000000000 -->6
255,255 -->7

Bi bilo lahko po transformaciji frekvenc :
77,90,144,0,3,2,4,2,7,1,184,5...
77,90,144,0,3,2,4,2,7,1,184,2,2,0 ...
ipd ...

Seveda to velja le za manjše datoteke in tak pristop je čisto odvisen od sequenc ipd ...
Inverzna funkcija obstaja, če imamo označbo takšnega parametra z dodatnim marker bitom, inverzne sekvenčne analize, torej da bo byt 5 pretvoril v 0000000 (v bytih) in ne v 5, vse ostalo ostaja isto, če ni markerja za inverz parametra v/na.
77,90,144,0,3,x2,4,x2,x7,x1,184,x5...
Torej je x tak marker ali pa preslikana inverzna funkcija,algoritem ipd ...

Drug princij je seveda komprimacija 8 bytov, če imajo vrednosti 0 in 1 po konverziji nazaj v byte :

primer za byte:
0,1,1,0,0,0,0,0,4,0,0,0,0,1,0,0 --->
--------------- -------------
|||
96,4,4
Seveda nucamo markerje :
x96,4,x4 ipd ...

Obstaja še mnogo primerov za različne vrste kompresije ...
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"The one who is digging the hole for the other to fall in is allready in it."

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

iptables restart

Oddelek: Omrežja in internet		71773 (1596) BRBR
»

Dodajanje nove statične route?

Oddelek: Omrežja in internet		112118 (1963) BlueRunner
»

vista in dve mrežni kartici - problem

Oddelek: Omrežja in internet		62471 (2297) sosko1
»

Iskanje podvojenih zaporedij

Oddelek: Programiranje		91869 (1649) Gundolf
»

Slovenija IP range

Oddelek: Omrežja in internet		154762 (4291) Soprano

Več podobnih tem