Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Pravljenje zakrpa programa

[es] :: Art of Programming :: Pravljenje zakrpa programa

[ Pregleda: 3409 | Odgovora: 16 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.



+2789 Profil

icon Pravljenje zakrpa programa26.08.2010. u 14:15 - pre 165 meseci
Kako se u praksi prave zakrpe i nadgradnje programa? Da li se jednostavno svi izmenjeni fajlovi arhiviraju ili postoji neko pametnije rešenje (tipa nekog binarnog diff-a)?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

AmoK

Član broj: 39404
Poruke: 61
109.175.70.*



+1 Profil

icon Re: Pravljenje zakrpa programa26.08.2010. u 19:14 - pre 165 meseci
Ovaj sam lično koristio prije 4-5 godina i dobro me služio.


Ostali možeš pronaći ovdje:
http://download.fyxm.net/Coding-Patchers-15-98-0-0-0.html
Cheaters ARE NOT hackers. Hackers MAKE cheats, cheaters USE cheats... I use Microsoft Windows but nobody call me Bill Gates either... damn!
 
Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
*.dynamic.isp.telekom.rs.



+1 Profil

icon Re: Pravljenje zakrpa programa27.08.2010. u 11:21 - pre 165 meseci
Pa predlozio bih algoritam najmanjeg rastojanja.

Uzmes pocetni fajl, krajnji fajl i operacije kojima dolazis od pocetnog do krajnjeg fajla.
Operacije mogu biti izbaci bajt ili niz bajtova, umetni bajt ili niz bajtova, pomeri bajt ili sekvencu ...

http://en.wikipedia.org/wiki/Levenshtein_distance

Izlaz iz algoritma je shema kako da dobijes od pocetnog, krajnji fajl.
Pretpostavka je da je ovaj deo optimalan nacin da zapises razliku. Zatim ti treba
kod koji ce da primeni to na stvarnom fajlu.

Mozes ubaciti i neki checksum da budes siguran da je patch uspeo.

Znaci

1. Pravljenje patcha (algoritam najmanjeg rastojanja po zadatoj metrici - od metrike zavisi velicina patch-a i kako on menja fajl - raspored operacija)

2. Primena patcha:
1. Napravis backup
2. Primenis patch
3. Proveris checksum
4. ako je sve ok i ne treba ti vise - obrises backup

Uzmi u obzir da u zavisnosti od operativnog sistema, mozes ili ne iz samog programa da menjas sadrzaj programskog
fajla na disku.

Pod Windows-om je recimo jednostavnije da imash patcher program koji menja aplikaciju. I aplikacija kada treba da se update-uje
(nadje noviji patch na serveru), skine ga i pokrene patcher koji ceka da se aplikacija ugasi (sama aplikacija onda ide na exit). Kada
patcher preko handle-a proveri da je proces aplikacije zavrsen, odradi patching i posle startuje aplikaciju a sam se ugasi.

Ili to ili da je kompletan kod u plugin arhitekturi. Onda shell koji inace ucitava i startuje plugine po potrebi korisnika, nosi kod za update
pluginova. Pa kad treba da update neki plugin onda ide unload plugin, patch plugin, reload plugin.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.



+2789 Profil

icon Re: Pravljenje zakrpa programa27.08.2010. u 13:27 - pre 165 meseci
Složenost tog algoritma je O(mn), tako da ne dolazi u obzir.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Pravljenje zakrpa programa27.08.2010. u 20:57 - pre 165 meseci
Ne znam sto se toliko zezas sa ovim? Cisto teorijski ili je praktican problem? Ako je praktican ustedi sebi vreme i isporuci kompletne nove verzije fajlova. Bajtovi su jeftini danas, i za storage i za prenos.
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 00:38 - pre 165 meseci
Ma, zezam se i pravim jedan patcher zasnovan na LZMA2 algoritmu. Zasad će biti zavistan of lzma.exe programa autora Igora Pavlova (koji je napisao 7z) dok ne nađem tekstualnu specifikaciju LZMA2 algoritma.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 07:52 - pre 165 meseci
Onda nisam siguran da mozes da izbegnes O(mn) kompleksnost u LCS resenjima, eventualno mozda da primenis neke optimizacije

http://en.wikipedia.org/wiki/L...ence_problem#Code_optimization
http://en.wikipedia.org/wiki/Hirschberg's_algorithm
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 11:05 - pre 165 meseci
Pa, ne koristim taj pristup.

Poenta je sledeća: Neka je F 1-1 transformacija nizova bajtova koja ima sledeću osobinu: F(A*)=F(A)*, gde AB označava nadovezivanje nizaa bajtova B na kraj niza bajtova A, a * označava proizvoljan niz bajtova. Ako je A stara verzija, B nova verzija fajla i F(AB)=F(A)C, onda se korisniku isporučuje zakrpa C. Znajući F, A i C, korisnik može da dobije B. Za F koristim LZMA2 algoritam.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 14:41 - pre 165 meseci
Nisam siguran da mi je bas najjasnije. Ok, lossless kompresija kao 1-1 preslikavanje, ali F(A*) = F(A)* mi nije bas najjasnije, kako moze izlaz iz kompresora da ignorise * (proizvoljan niz bajtova dodat na A)? A cak i da to radi patchovanje nije samo appending, promene su skoro uvek prisutne sirom promenjenog fajla?

Jel ovo neka fora slicna reed-solomonu? Error correction primenjen na promenu fajla?
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.



+2789 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 15:58 - pre 165 meseci
Recimo da imam dve verzije fajla - staru A i novu B.

Pravljenje zakrpe:

1. Komprimujem fajl A i kao rezultat dobijem fajl A.l dužine n.

2 . Generišem fajl AB čiji se sadržaj dobija nadovezivanjem sadržaja B na kraj sadržaja A. Dakle, ako je fajl A imao sadržaj "Marija", a fajl B imao sadržaj "na", onda fajl AB ima sadržaj "Marijana".

3. Komprimujem fajl AB i dobijem fajl AB.l.

Ovde se pretpostavlja da je kompresija takva da AB.l ima veću dužinu od A.l (koju sam označio sa n), ali da se prvih n bajtova od AB.l poklapa sa bajtovima iz A.l.

4. Generišem fajl B.p koji predstavlja sadržaj fajla AB.l od n+1-vog bajta, pa nadalje. Fajl B.p predstavlja zakrpu koju šaljem.

Primena zakrpe:

Korisnik ima fajlove A i B.p

1. Komprimuje fajl A i dobija fajl A.l..

2. Generiše fajl koji se dobija nadovezivanjem sadržaja fajla B.p na kraj sadržaja fajla A.l i dobija fajl AB.i

3. Dekomprimuje fajl AB.l i dobija fajl AB.

4. Generiše fajl B čiji su sadržaj bajtovi fajla AB od m+1-vog pa nadalje, gde je m dužina fajla A. To je nova verzija fajla.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 16:35 - pre 165 meseci
Aha, znaci u osnovi koristis lookup tabele koje je kompresor vec izgradio za fajl A da bi B.p bio manji od B.l koristeci hunch da postoji velika entropija u fajlu AB? Al zar nema kompresor neki prakticni limit koliko daleko gleda unazad za lookup?
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 16:42 - pre 165 meseci
Zavisi od kompresora.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 19:29 - pre 165 meseci
Evo na šta sam zapravo mislio. Da bi program radio, neophodno je imati lzma.exe.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Prikačeni fajlovi
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4901
212.200.65.*

Jabber: xfiles@elitesecurity.org


+638 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 19:59 - pre 165 meseci
Koji kompajler si koristio?

Pitam zbog ovoga:
Citat:

// ...
char command[2*strlen(fileName) + 14];
// ...
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Pravljenje zakrpa programa28.08.2010. u 20:12 - pre 165 meseci
MinGW C kompajler gcc.

To dopuštaju GNU kompajleri. Time se na steku alocira onoliko prostora koliko je potrebno ya niz. Zapravo, to je ekvivalent alloca funkcije, koja ovom sintaksom postaje nepotrebna.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

vlada_vlada
Uber
Beograd

Član broj: 259596
Poruke: 68
*.dynamic.sbb.rs.



+7 Profil

icon Re: Pravljenje zakrpa programa29.08.2010. u 19:28 - pre 165 meseci
Interesatna ideja.

Bilo bi lepo videti koliko program efikasno pronalazi binarne razlike (velicina_promene / velicina_patcha ) za razlicite tipove podataka (tekst, slika, zvuk, executable).

Takodje bilo bi lepo videti kako se ponasa za razlicite velicine fajlova.

Inace evo jos jednog pristupa binarnim patchevima: http://www.samba.org/rsync/tech_report/node2.html

Autor je Andrew Tridgell koji je osim po rsync-u, poznat i po SAMBA projektu ;)

"Rolling checksum" iliti centralni deo algoritma za pronalazenje binarnih razlika je ujedno i glavna tema Andrew-ove PhD teze.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
212.200.65.*



+2789 Profil

icon Re: Pravljenje zakrpa programa29.08.2010. u 22:58 - pre 165 meseci
Citat:
vlada_vlada: Bilo bi lepo videti koliko program efikasno pronalazi binarne razlike (velicina_promene / velicina_patcha ) za razlicite tipove podataka (tekst, slika, zvuk, executable).

Takodje bilo bi lepo videti kako se ponasa za razlicite velicine fajlova.


Eto ti ga, pa ga testiraj. Samo napred.

Citat:
vlada_vlada: Inace evo jos jednog pristupa binarnim patchevima: http://www.samba.org/rsync/tech_report/node2.html

Autor je Andrew Tridgell koji je osim po rsync-u, poznat i po SAMBA projektu ;)

"Rolling checksum" iliti centralni deo algoritma za pronalazenje binarnih razlika je ujedno i glavna tema Andrew-ove PhD teze.


Rekao bih da nije reč o istom problemu. Tamo kompjuteri koji sporo komuniciraju imaju pristup različitim verzijama fajla, a kod mene jedna strana ima pristup do obe verzije fajla.

Ima li uopšte smisla da napravim jedan prenosivi FOSS patcher, koji bi patch-ovao više fajlova, generisao samostalan izvršni patcher i proveravao CRC-ove?
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

[es] :: Art of Programming :: Pravljenje zakrpa programa

[ Pregleda: 3409 | Odgovora: 16 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.