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

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.

Složenost tog algoritma je O(mn), tako da ne dolazi u obzir.

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.

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.

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

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.

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?

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.

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?

Zavisi od kompresora.

Evo na šta sam zapravo mislio. Da bi program radio, neophodno je imati lzma.exe.

Koji kompajler si koristio?

Pitam zbog ovoga:

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.

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.

Eto ti ga, pa ga testiraj. Samo napred.



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?