Google chrome 的心得-(2) 如何實作patcher BSDiff

在網路上 我們常常會看到 Patcher(補丁)的存在
為什麼要使用patch技術呢
最主要就是節省傳輸的size
例如執行檔更新 一般來說 除非改動很大
否則 前後兩個版本基本上 不會差異太大
可以選擇
1. 執行檔更新 (3Mb)
2. patch檔 (<200k)
一個檔案可能會差了1~2Mb
如果檔案一多 就差異很大了
況且 現在網路的時候 頻寬就是金錢 能夠省下傳輸檔案的大小 就是省下錢


那如何在程式套用這些東西進去 以及哪裡有win32可用的原始碼
在Google chrome的原始碼裡面
有實作一個Bsdiff的程式
這個程式 有三個部份的原始碼 是可以很方便套用在自己的程式裡面

1. 如何實作一各patcher diff db
2. How to patch a diff to a file
3. CRC32 的原始碼 (用來檢查patched file)

Part1 binary patcher
Tools-->bsdiff project
BSDiff 可以觀看網頁 http://www.daemonology.net/bsdiff/
基本上 就是利用fast suffix sorting 的邏輯 去找出
在offset[x]的位置
(1)需要修改(modify)哪些bytes or
(2)或是要解開(extract)某些bytes
然後 把這些資料寫入檔案 以及舊檔案的CRC32 長度等等資料

MBSPatchHeader==>output file header
MBSPatchTriple -->patch的資料
<br />typedef struct MBSPatchHeader_ {<br /> /* "MBDIFF10" */<br /> char tag[8];<br /> <br /> /* Length of the file to be patched */<br /> unsigned int slen;<br /><br /> /* CRC32 of the file to be patched */<br /> unsigned int scrc32;<br /><br /> /* Length of the result file */<br /> unsigned int dlen;<br /><br /> /* Length of the control block in bytes */<br /> unsigned int cblen;<br /><br /> /* Length of the diff block in bytes */<br /> unsigned int difflen;<br /><br /> /* Length of the extra block in bytes */<br /> unsigned int extralen;<br /><br /> /* Control block (MBSPatchTriple[]) */<br /> /* Diff block (binary data) */<br /> /* Extra block (binary data) */<br />} MBSPatchHeader;<br /><br />typedef struct MBSPatchTriple_ {<br /> unsigned int x; /* add x bytes from oldfile to x bytes from the diff block */<br /> unsigned int y; /* copy y bytes from the extra block */<br /> int z; /* seek forwards in oldfile by z bytes */<br />} MBSPatchTriple;<br />


檔案的架構
MBSPatchHeader
MBSPatchTriple * n
db (modify binary data)
eb (extract binary data)



Part2 patch diff to file
在google chrome有提供library 可以讓我們直接把patch打進某個檔案的API
Libraries-->bspatch project
bspatch用的header跟part2是共用的

mbspatch.h
<br />/**<br /> * Apply the given patch file to a given source file. This method validates <br /> * the CRC of the original file stored in the patch file, before applying the <br /> * patch to it.<br /> */<br />int ApplyBinaryPatch(const wchar_t *old_file, const wchar_t *patch_file,<br /> const wchar_t *new_file);<br />

只要呼叫ApplyBinaryPatch 就可以在你的程式 做出patch的功能了

Part3 CRC32
在Libraries -->lzma_sdk project中
可以看到7zCrc.c 7zCrc.h
是用c實作的原始碼
關於CRC32 的原理不在這邊討論
7zCrc.h
<br />void MY_FAST_CALL CrcGenerateTable();<br />UInt32 MY_FAST_CALL CrcUpdate(UInt32 crc, const void *data, size_t size);<br />UInt32 MY_FAST_CALL CrcCalc(const void *data, size_t size);<br />

CrcGenerateTable() 用來initialize CRC32 table ==>(有興趣的人可以把這個部分做更好的處理 )
CrcCalc() ->計算某塊buffer的CRC32值(內部其實是call CrcUpdate(CRC_INIT_VAL, data, size) )
CrcUpdate()->計算某塊buffer的CRC32值 然後update在輸入的舊CRC32值