簡介qt環(huán)境下移植bsdiff并采用qlz壓縮算法生成增量補丁包的項目源碼包面向需要為Qt桌面或嵌入式應用設計差分升級機制的開發(fā)者幫助解決全量更新體積大、傳輸耗時的問題適合具備基礎C與Qt知識的進階學習者。壓縮包共705個文件以675個idx索引文件為主體包含差分計算所需的索引數據另有cpp源碼、h頭文件、ui界面、pro工程文件、bin可執(zhí)行文件及調試遺存等整體約6.22MB目錄結構清晰便于對照工程分析編譯產物與源碼對應關系。已有496人學習下載。包內提供了可運行的demo二進制與Qt工程模板讀者可以借此掌握bsdiff差異比較邏輯在Qt中的接口封裝方式理解qlz壓縮流如何替代默認bzip2并參考其性能優(yōu)化與多線程數據流處理思路同時了解壓縮失敗或異常時的錯誤處理與狀態(tài)恢復設計為自研輕量級軟件更新方案提供可直接復用的代碼骨架。1. 為什么Qt工程里最終選了bsdiff加qlz來做升級做Qt客戶端和嵌入式設備升級的開發(fā)者遲早會碰到同一個問題舊版本怎么平滑升級到新版本。整包更新最簡單但安裝包稍微大點幾MB的補丁下載成本就會讓用戶抱怨在網速受限的嵌入式環(huán)境里更是直接勸退。bsdiff是二進制差分算法里的老牌方案它能拿舊文件和新文件對比生成一個只包含差異部分的patch包客戶端拿到patch后和本地舊文件合并就能還原出完整的新文件。原生bsdiff默認用bzip2做壓縮但bzip2在生成patch時壓縮速度偏慢庫的依賴也重搬進Qt工程并不順手。把壓縮算法換成QuickLZqlz之后patch生成速度快了一個量級內存占用更可控整個補丁鏈路也變成了一套純C加Qt就能獨立維護的小模塊。這篇文章就圍繞“qt移植bsdiff生成patch包壓縮算法采用qlz”這條主線把原理、移植步驟、文件格式設計和踩坑點一次說透適合正在做OTA和固件差分升級的工程師參考。2. 先看bsdiff的算法結構和壓縮瓶頸2.1 bsdiff的差分過程后綴數組、diff流、extra流bsdiff的聰明之處在于它不逐字節(jié)做簡單比較而是先對舊文件做一次后綴排序。舊文件的每個后綴都生成一個索引然后按字典序排成一個數組。接下來遍歷新文件的每個位置在后綴數組里做二分查找找出舊文件中能和當前位置內容形成最長匹配的位置。匹配上的部分用diff流記錄因為舊文件和新文件在對應位置上大概率只差幾個字節(jié)把每個字節(jié)的差值存下來數據會非常小且重復度高后續(xù)壓縮收益極大。匹配不上的部分無法和舊文件對應就原樣塞進extra流。生成patch的過程最終被抽象成一組控制三元組也就是bsdiff里最核心的ctrl塊。每個三元組包含三個數字x表示本輪要從diff流里拷多少字節(jié)y表示要從extra流里拷多少字節(jié)z表示下一個匹配在舊文件里的偏移修正量。bspatch應用patch時就是讀一個三元組先從diff流拷貝x個字節(jié)并和舊文件對應位置相加再從extra流拷貝y個字節(jié)原樣寫入最后把舊文件指針按z調整繼續(xù)下一個循環(huán)。這個設計讓bspatch不需要掃描全量新文件只需要跳著讀舊文件配合壓縮后的三個數據塊就能把新文件完整重建出來。一個典型的例子是固件鏡像升級。鏡像里可能只是改了版本號、簽名或者某個配置文件新舊文件大部分區(qū)域完全一致。bsdiff跑一輪后diff流里大量字節(jié)都是0或者很小的差值extra流幾乎為空整個patch包可能只有幾百字節(jié)。這也是為什么差分升級能極大降低分發(fā)成本。不過要注意bsdiff的后綴排序階段計算量相當大對舊文件越大的場景排序時間越長內存占用也越高這一點在選型時就要有心理預期。2.2 原生bzip2鏈路為什么搬進Qt工程不順手原版bsdiff默認用bzip2做壓縮這個選擇在幾十年前是合理的畢竟當年bzip2壓縮率高patch包能壓到很小。但放到現在的Qt工程里問題很明顯。第一是依賴問題bzip2是一套獨立的庫在桌面平臺還好到了交叉編譯環(huán)境要么手動交叉編譯一份libbz2要么在qmake里鏈接一個靜態(tài)庫多引入一個第三方依賴就讓工程復雜不少。第二是壓縮速度bzip2的壓縮主要靠BWT變換配合Huffman編碼算法本身很重一個幾百MB的固件跑完patch生成等待時間長到會讓調試節(jié)奏變得非常難受。第三是流式IO和內存模型的問題。bsdiff原版用bzip2的流式接口把三個數據塊寫進patch文件同時bspatch也以多路bz流的方式邊讀邊解壓。這個設計本身沒問題但移植到Qt場景時維護多個BZ2_stream狀態(tài)還要處理讀一半斷流的情況代碼復雜度一下就上來了。而且bzip2解壓時對緩沖區(qū)的大小和清零要求也比較苛刻在內存受限的設備上解壓一個大的extra塊往往要臨時申請大塊內存一旦分配失敗整個升級流程就卡住了。2.3 換成QuickLZ之后性能指標發(fā)生了哪些變化QuickLZ可以簡單理解為一種面向速度和輕量集成的LZ系列壓縮庫。它最大的特點是壓縮和解壓都極其快代價是壓縮率不如bzip2但patch包體積在差分升級場景里本來就不是唯一指標。我自己在實際項目中感受到的差異是這樣的同樣的兩個文件做差分用bzip2壓縮過的patch很小但生成時間多出好幾倍換成qlz后patch生成時間大幅縮短patch包會大一些但對OTA分發(fā)影響有限因為diff流和extra流里大量相似數據依然能壓掉很大一部分。下面是兩種壓縮算法在我常用的開發(fā)機上的表現對比數據和環(huán)境有關但量級差異是有參考價值的項目bzip2原生bsdiffQuickLZqlz壓縮速度偏慢大文件要等快接近LZ4級別解壓速度一般很快適合嵌入式壓縮率較高中等第三方依賴需要libbz2只有quicklz.c和quicklz.h線程安全流狀態(tài)需要隔離狀態(tài)結構需要隔離但要簡單很多內存模型流式可邊讀邊寫塊式一次壓縮一整段數據QuickLZ的塊式壓縮模型對移植是有利的。它在調用前把一塊完整數據放進緩沖區(qū)壓縮后得到一塊完整數據不需要像bzip2那樣維護在線流狀態(tài)。這樣一來補丁生成和應用兩側的邏輯都變得直白先緩沖數據再壓縮再把長度信息和壓縮數據一起寫文件。雖然文件頭需要多記錄幾個字段但換來的是代碼可讀性和調試友好度大幅提升。3. 在Qt工程里移植bsdiff并把壓縮算法換成qlz3.1 工程組織qmake項目文件與源碼放置移植的第一步不是改算法而是先把代碼結構理清。我習慣把bsdiff核心算法、bspatch核心算法、QuickLZ分別放在獨立目錄里再用qmake把它們組合成一個靜態(tài)庫或者直接編進主工程。下面是一個典型的qmake組織方式QT core CONFIG console c11 TEMPLATE app DEFINES _FILE_OFFSET_BITS64 INCLUDEPATH $$PWD/3rdparty/quicklz SOURCES \ main.cpp \ patch_generator.cpp \ patch_applier.cpp \ bsdiff_core.c \ bspatch_core.c \ $$PWD/3rdparty/quicklz/quicklz.c HEADERS \ patch_generator.h \ patch_applier.h \ bsdiff_core.h \ bspatch_core.h \ $$PWD/3rdparty/quicklz/quicklz.h這段配置里有幾個關鍵點。_FILE_OFFSET_BITS64必須加上尤其當你需要在32位平臺上處理超過2GB的文件時否則bsdiff里的off_t會退化成32位整數讀寫位置直接溢出。quicklz.c放在SOURCES里qmake會按C文件編譯不會受到C名字修飾的影響。bsdiff_core.c和bspatch_core.c里保留原版的差分和合并算法但在對外接口處用C風格函數暴露方便后面用C封裝。我一般會砍掉bsdiff_core.c里原有的main函數和命令行解析只保留核心的diff計算函數比如bsdiff算法的入口。這樣Qt層可以自己決定從哪里讀文件、往哪里寫patch而不是被標準輸入輸出限制住。同理bspatch_core.c里也只保留“從內存中讀取三個塊并合并出新文件”的核心邏輯文件讀取交給Qt側管理。3.2 為qlz訂制補丁文件頭彌補流式壓縮和塊壓縮的格式差異原版bsdiff的patch文件頭只有幾個字段magic、三個塊的壓縮后大小、新文件大小。因為bzip2是流式的bspatch知道自己按流讀到多少字節(jié)算完不需要提前知道解壓后大小。但QuickLZ的塊式壓縮不同解壓時需要明確知道目標緩沖區(qū)的大小否則qlz_decompress不知道預期輸出多少字節(jié)很容易越界。所以移植時一定要改patch文件格式給每個數據塊同時記錄解壓前大小和壓縮后大小。我采用的自定義頭結構如下#define QLZ_PATCH_MAGIC 0x514C505A0401ULL typedef struct { quint64 magic; quint64 new_size; quint64 ctrl_raw_size; quint64 ctrl_comp_size; quint64 diff_raw_size; quint64 diff_comp_size; quint64 extra_raw_size; quint64 extra_comp_size; } QlzPatchHeader;ctrl_raw_size表示控制塊解壓后的字節(jié)數ctrl_comp_size表示壓縮后的字節(jié)數diff和extra同理。new_size是最終新文件的總長度bspatch用它來預先創(chuàng)建輸出文件。這個頭結構總共8個字段每個8字節(jié)固定64字節(jié)沒有對齊問題也很容易做小端序列化。在生成patch時我會先把整個頭用占位數據寫進文件然后依次寫入三個壓縮塊最后再回過頭把真實的長度數據填進頭部。這樣寫入邏輯不用關心頭的總長度也方便后面增加字段?？紤]到不同平臺字節(jié)序可能不同所有長度字段在寫入時統(tǒng)一轉成小端讀取時再轉回主機字節(jié)序這樣patch包才能跨設備通用。3.3 生成側改動把diff和extra塊批量交給qlz_compress生成側的核心改動在于把原來直接調用bzip2流式寫入的地方替換成一個獨立的寫塊函數。這個函數接收一段完整的原始數據用QuickLZ壓縮后連同raw_size和comp_size一起寫入patch文件。代碼實現如下static bool write_qlz_block(QFile out, const QByteArray raw, quint64 *raw_size, quint64 *comp_size) { quint64 raw_len (quint64)raw.size(); quint64 comp_len 0; qlz_state_compress state_compress; QByteArray comp; comp.resize(raw.size() 400); // QuickLZ壓縮時允許的最大膨脹量 comp_len qlz_compress((const void *)raw.data(), (void *)comp.data(), raw.size(), state_compress); *raw_size raw_len; *comp_size comp_len; out.write((const char *)raw_len, sizeof(quint64)); out.write((const char *)comp_len, sizeof(quint64)); out.write(comp.data(), (qint64)comp_len); return true; }寫入時先寫raw_len再寫comp_len最后寫壓縮數據。這樣讀取側能先知道要分配多大的解壓緩沖再決定讀多少壓縮數據。qlz_compress的第四個參數是QuickLZ要求的狀態(tài)結構這里在函數內部定義每次調用都是全新的狀態(tài)避免線程間互相污染。輸出緩沖大小給raw.size()加400這是QuickLZ文檔建議的安全余量因為極端情況下壓縮輸出可能略微膨脹。生成patch的整體流程會把這個函數調用三次分別壓縮ctrl塊、diff塊和extra塊。這三個塊的原始數據從哪里來bsdiff算法在跑完后會得到一整段控制數據和一整段diff、extra拼接數據在原有C代碼里它們是直接按內存塊處理的。我把bsdiff_core.c中間結果通過結構體返回給Qt層Qt層再把它裝進QByteArray調三次write_qlz_block就完成patch文件的主體寫入。這種方式有一個值得注意的副作用原來的bzip2流式寫入可以邊計算邊寫不會額外占用太多內存。改成qlz塊式壓縮后diff塊和extra塊必須全部緩存在內存里才能一次性壓完。對于幾十MB的固件這個代價可以接受對于數GB的文件就要評估設備內存是否夠用。后面避坑章節(jié)會專門講這一點。3.4 應用側改動用qlz_decompress還原三個數據塊并合并應用側也就是bspatch的邏輯改動同樣集中在塊讀取上。原來bzip2是流式讀現在需要把每個壓縮塊完整讀進內存然后一次性解壓。讀取側的代碼和寫入側對稱static bool read_qlz_block(QFile in, QByteArray raw) { quint64 raw_len, comp_len; if (in.read((char *)raw_len, sizeof(quint64)) ! sizeof(quint64)) return false; if (in.read((char *)comp_len, sizeof(quint64)) ! sizeof(quint64)) return false; if (comp_len 1ULL * 1024 * 1024 * 1024) return false; QByteArray comp; comp.resize((qint64)comp_len); if (in.read(comp.data(), (qint64)comp_len) ! (qint64)comp_len) return false; qlz_state_decompress state_decompress; raw.resize((qint64)raw_len); size_t got qlz_decompress((const void *)comp.data(), (void *)raw.data(), raw.size(), state_decompress); return got (size_t)raw_len; }comp_len設置了上限1GB防止損壞的patch文件導致程序嘗試申請超大內存。qlz_decompress的目標長度直接傳raw_len函數返回實際解壓得到的字節(jié)數如果不等于預期就說明patch文件損壞或者版本不匹配。解壓完成后bpatch的合并循環(huán)并不需要改動多少。它從ctrl塊里順序讀出三元組再從diff塊和extra塊里取出對應數據按規(guī)則寫入新文件。因為三個完整塊都常駐內存循環(huán)里只是做內存拷貝和字節(jié)加法運算不再有任何文件IO所以bspatch的跑分通常不會比生成側慢。3.5 在Qt層封裝成生成器和應用器純粹暴露C函數給Qt調用雖然可行但用起來不順。我習慣再包一層帶QString參數的類讓調用方可以直接傳文件路徑內部統(tǒng)一處理異常和錯誤信息。核心類的接口大概是這樣class PatchGenerator { public: bool generate(const QString oldPath, const QString newPath, const QString patchPath, QString *errorMessage); }; class PatchApplier { public: bool apply(const QString oldPath, const QString patchPath, const QString newPath, QString *errorMessage); };在Qt層面我會用QFile讀取文件內容并映射到QByteArray然后調用bsdiff_core.c里的核心函數。整個過程不需要把整個文件再復制一份舊文件和新文件各留一份原始數據再加上diff和extra的緩存內存占用量已經是理論下限的一部分。錯誤處理盡量控制在C層core層只返回整數錯誤碼避免把C的errno和Qt的錯誤機制糾纏在一起。為了讓生成和應用兩側的日志可讀我還會在類里記錄每個階段的耗時和內存占用比如“后綴排序耗時”“diff塊壓縮字節(jié)數”“patch最終大小”這類信息。這些數據在優(yōu)化參數時很有用后面驗證章節(jié)會展開說明。4. 移植避坑清單5個最容易翻車的地方4.1 補丁頭只存壓縮大小導致qlz_decompress內存越界現象生成的patch在生產環(huán)境能正常應用換一個文件就崩潰或者解壓出的內容末尾變成亂碼。排查下來發(fā)現是bspatch側申請的解壓緩沖區(qū)大小不夠qlz_decompress把數據寫到了緩沖區(qū)邊界之外。原因原版bsdiff文件頭只保存三個塊的壓縮后大小因為bzip2流式解壓不需要預先知道解壓后字節(jié)數。QuickLZ不一樣qlz_decompress需要明確指定目標緩沖區(qū)大小而這個值只有生成側知道。解決補丁文件頭必須為每個塊同時保存raw_size和comp_size讀取側嚴格按raw_size分配緩沖區(qū)并在解壓后比較實際返回值。我在read_qlz_block里加了一個斷言got不等于raw_len直接返回失敗避免數據損壞時無感繼續(xù)。4.2 32位平臺下off_t溢出超過2GB的文件直接崩現象在32位的嵌入式設備上跑bspatch文件讀到一半位置變成負數或者生成patch時后綴排序數組下標變成負數程序退出。原因bsdiff原生代碼里的off_t在32位編譯環(huán)境下是32位有符號整數能表達的最大長度只有2GB左右。固件鏡像一旦超過這個閾值所有偏移計算都不可信了。這不是QuickLZ引入的問題是bsdiff本身就需要處理的大文件隱患。解決qmake工程里統(tǒng)一加DEFINES _FILE_OFFSET_BITS64確保glibc的off_t按64位擴展。同時在自己寫的Qt封裝層里所有文件偏移和長度類型都強制用qint64不跟平臺的long類型混用。交叉編譯時還要確認工具鏈默認的off_t實現支持64位。4.3 qlz狀態(tài)結構體在線程池里被共用壓縮結果全亂現象單線程生成patch一切正常把生成任務丟進QThreadPool并發(fā)跑多個文件有的patch能出來有的壓縮數據完全是爛的偶爾還直接crash。原因QuickLZ要求調用者提供壓縮狀態(tài)結構這個結構內部保存了上一輪匹配的窗口信息。多個線程共用同一個state對象時寫操作互相覆蓋壓縮結果自然不可預測。bsdiff原版的bzip2流也類似但塊式壓縮讓這個錯誤更容易被忽略。解決把qlz_state_compress和qlz_state_decompress定義成write_qlz_block和read_qlz_block的局部變量每個線程每次調用都有自己的狀態(tài)。不要嘗試在線程池里緩存狀態(tài)來省那幾十KB內存收益太低風險太高。4.4 端序不同導致patch在另一個架構上不兼容現象在x86開發(fā)機上生成的patch包部署到ARM設備上應用失敗控件不匹配或者解壓后數據錯位。原因bsdiff原版把控制三元組直接按off_t的內存布局寫入文件在不同字節(jié)序平臺上內存布局正好相反。QuickLZ自帶的壓縮頭雖然宣稱跨端序安全但我們的自定義文件頭和控制塊數據都是二進制格式不能假定雙方主機字節(jié)序一致。解決文件頭和ctrl塊三元組在寫入時統(tǒng)一用小端序讀取時用小端轉主機序的函數解析。不要讓結構體直接memcpy到文件里把字段逐個用put_le64和get_le64處理一遍代碼多十幾行但patch包的兼容性問題是徹底解決了。4.5 排序階段內存占用疊加分配失敗卻沒有任何報錯現象處理大文件時程序在某一步突然卡死或者被系統(tǒng)OOM殺掉。用日志看內存占用爬升到接近設備物理內存上限然后進程消失。原因bsdiff的后綴排序階段本身就需要給舊文件每個后綴建立一個索引內存占用大約是舊文件大小的4到8倍。換掉bzip2之后diff塊和extra塊又必須在內存里完整緩存再疊加QuickLZ的輸出緩沖峰值內存比原來的方案還要高。很多移植代碼忽略了對內存峰值的估算分配失敗時又只檢查了一個中間指針沒有形成閉環(huán)。解決生成patch前先做一次內存預測。我用的經驗公式是峰值內存約等于舊文件大小的6倍加上新文件大小的4倍再加上輸出緩沖的余量。在資源受限設備上先驗算一遍超了就改用分塊策略或者在小文件上跑生成側把應用側放到設備端。另外所有malloc和QByteArray::resize都要檢查返回值resize失敗時立即給出明確錯誤信息而不是讓后續(xù)邏輯繼續(xù)踩空指針。5. 移植完怎么驗證回歸測試與性能基線5.1 建立最小回歸用例覆蓋三類邊界數據移植完成后我建議先跑一個最樸素的回歸腳本不要上來就拿真實固件壓測。準備三組測試數據一組是只有幾十字節(jié)差異的小文本文件一組是結構完全不同的兩個二進制文件一組是內容整體偏移了幾個字節(jié)的模擬固件。生成patch、應用patch然后直接比較新文件和原文件是否完全一致用字節(jié)級比較確認差異為零。# 回歸測試三步走 ./patchtool gen old.bin new.bin patch.qlz ./patchtool apply old.bin patch.qlz out.bin cmp new.bin out.bin echo patch round-trip ok這三組數據分別覆蓋了diff流占主導、extra流占主導、以及匹配偏移修正占主導的三種典型場景。bpatch的合并邏輯在這三類輸入下最容易暴露出邊界錯誤比如偏移修正量為負、diff塊用完而extra塊還有很多剩余數據之類的情況跑過這三組再上真機才算心里有底。5.2 參數調整QLZ壓縮級別與匹配窗口的取舍QuickLZ的壓縮級別通過宏控制常見做法是在編譯時指定壓縮等級。等級越高壓縮率越好但內存和CPU開銷也隨之增大。在差分升級場景里我傾向于先測試兩份參數一個追求最小patch體積一個追求最快生成速度然后把patch大小和生成時間放到一張表里對比。以模擬項目X的固件驗證為例兩組參數下的數據差異是低級配置生成時間縮短了近一半patch體積只增大了百分之十到二十。如果分發(fā)渠道的帶寬緊張幾MB的差異確實值得換壓縮級別如果每次更新都有幾十上千臺設備并發(fā)下載生成速度反而更重要。沒有絕對正確的參數只有適合你業(yè)務約束的選擇。我自己在實際工程里養(yǎng)成了一個習慣在每個版本的性能基準測試里固定記錄三項指標——patch生成耗時、patch包體積、設備端應用耗時。這些數據作為歷史基線留在工程里下次改算法或者換壓縮庫時就能用同一組測試數據橫向比較而不是靠感覺判斷方案是否退步。建議你也在移植完成后跑完這幾項寫進自己的工程筆記里后續(xù)維護時能省不少心。這類移植工作最怕的不是算法復雜而是出了問題不知道是格式錯誤、內存問題還是字節(jié)序問題。數據記錄下來日志打清楚驗證腳本跑起來整個鏈路就不那么像玄學了。希望這幾個步驟和避坑經驗能幫你順利把bsdiff加qlz的方案落地到自己的Qt工程里。本文還有配套的精品資源點擊獲取 Qt工程移植bsdiff生成patch包：壓縮算法替換為QuickLZ的完整實踐
簡介qt環(huán)境下移植bsdiff并采用qlz壓縮算法生成增量補丁包的項目源碼包面向需要為Qt桌面或嵌入式應用設計差分升級機制的開發(fā)者幫助解決全量更新體積大、傳輸耗時的問題適合具備基礎C與Qt知識的進階學習者。壓縮包共705個文件以675個idx索引文件為主體包含差分計算所需的索引數據另有cpp源碼、h頭文件、ui界面、pro工程文件、bin可執(zhí)行文件及調試遺存等整體約6.22MB目錄結構清晰便于對照工程分析編譯產物與源碼對應關系。已有496人學習下載。包內提供了可運行的demo二進制與Qt工程模板讀者可以借此掌握bsdiff差異比較邏輯在Qt中的接口封裝方式理解qlz壓縮流如何替代默認bzip2并參考其性能優(yōu)化與多線程數據流處理思路同時了解壓縮失敗或異常時的錯誤處理與狀態(tài)恢復設計為自研輕量級軟件更新方案提供可直接復用的代碼骨架。1. 為什么Qt工程里最終選了bsdiff加qlz來做升級做Qt客戶端和嵌入式設備升級的開發(fā)者遲早會碰到同一個問題舊版本怎么平滑升級到新版本。整包更新最簡單但安裝包稍微大點幾MB的補丁下載成本就會讓用戶抱怨在網速受限的嵌入式環(huán)境里更是直接勸退。bsdiff是二進制差分算法里的老牌方案它能拿舊文件和新文件對比生成一個只包含差異部分的patch包客戶端拿到patch后和本地舊文件合并就能還原出完整的新文件。原生bsdiff默認用bzip2做壓縮但bzip2在生成patch時壓縮速度偏慢庫的依賴也重搬進Qt工程并不順手。把壓縮算法換成QuickLZqlz之后patch生成速度快了一個量級內存占用更可控整個補丁鏈路也變成了一套純C加Qt就能獨立維護的小模塊。這篇文章就圍繞“qt移植bsdiff生成patch包壓縮算法采用qlz”這條主線把原理、移植步驟、文件格式設計和踩坑點一次說透適合正在做OTA和固件差分升級的工程師參考。2. 先看bsdiff的算法結構和壓縮瓶頸2.1 bsdiff的差分過程后綴數組、diff流、extra流bsdiff的聰明之處在于它不逐字節(jié)做簡單比較而是先對舊文件做一次后綴排序。舊文件的每個后綴都生成一個索引然后按字典序排成一個數組。接下來遍歷新文件的每個位置在后綴數組里做二分查找找出舊文件中能和當前位置內容形成最長匹配的位置。匹配上的部分用diff流記錄因為舊文件和新文件在對應位置上大概率只差幾個字節(jié)把每個字節(jié)的差值存下來數據會非常小且重復度高后續(xù)壓縮收益極大。匹配不上的部分無法和舊文件對應就原樣塞進extra流。生成patch的過程最終被抽象成一組控制三元組也就是bsdiff里最核心的ctrl塊。每個三元組包含三個數字x表示本輪要從diff流里拷多少字節(jié)y表示要從extra流里拷多少字節(jié)z表示下一個匹配在舊文件里的偏移修正量。bspatch應用patch時就是讀一個三元組先從diff流拷貝x個字節(jié)并和舊文件對應位置相加再從extra流拷貝y個字節(jié)原樣寫入最后把舊文件指針按z調整繼續(xù)下一個循環(huán)。這個設計讓bspatch不需要掃描全量新文件只需要跳著讀舊文件配合壓縮后的三個數據塊就能把新文件完整重建出來。一個典型的例子是固件鏡像升級。鏡像里可能只是改了版本號、簽名或者某個配置文件新舊文件大部分區(qū)域完全一致。bsdiff跑一輪后diff流里大量字節(jié)都是0或者很小的差值extra流幾乎為空整個patch包可能只有幾百字節(jié)。這也是為什么差分升級能極大降低分發(fā)成本。不過要注意bsdiff的后綴排序階段計算量相當大對舊文件越大的場景排序時間越長內存占用也越高這一點在選型時就要有心理預期。2.2 原生bzip2鏈路為什么搬進Qt工程不順手原版bsdiff默認用bzip2做壓縮這個選擇在幾十年前是合理的畢竟當年bzip2壓縮率高patch包能壓到很小。但放到現在的Qt工程里問題很明顯。第一是依賴問題bzip2是一套獨立的庫在桌面平臺還好到了交叉編譯環(huán)境要么手動交叉編譯一份libbz2要么在qmake里鏈接一個靜態(tài)庫多引入一個第三方依賴就讓工程復雜不少。第二是壓縮速度bzip2的壓縮主要靠BWT變換配合Huffman編碼算法本身很重一個幾百MB的固件跑完patch生成等待時間長到會讓調試節(jié)奏變得非常難受。第三是流式IO和內存模型的問題。bsdiff原版用bzip2的流式接口把三個數據塊寫進patch文件同時bspatch也以多路bz流的方式邊讀邊解壓。這個設計本身沒問題但移植到Qt場景時維護多個BZ2_stream狀態(tài)還要處理讀一半斷流的情況代碼復雜度一下就上來了。而且bzip2解壓時對緩沖區(qū)的大小和清零要求也比較苛刻在內存受限的設備上解壓一個大的extra塊往往要臨時申請大塊內存一旦分配失敗整個升級流程就卡住了。2.3 換成QuickLZ之后性能指標發(fā)生了哪些變化QuickLZ可以簡單理解為一種面向速度和輕量集成的LZ系列壓縮庫。它最大的特點是壓縮和解壓都極其快代價是壓縮率不如bzip2但patch包體積在差分升級場景里本來就不是唯一指標。我自己在實際項目中感受到的差異是這樣的同樣的兩個文件做差分用bzip2壓縮過的patch很小但生成時間多出好幾倍換成qlz后patch生成時間大幅縮短patch包會大一些但對OTA分發(fā)影響有限因為diff流和extra流里大量相似數據依然能壓掉很大一部分。下面是兩種壓縮算法在我常用的開發(fā)機上的表現對比數據和環(huán)境有關但量級差異是有參考價值的項目bzip2原生bsdiffQuickLZqlz壓縮速度偏慢大文件要等快接近LZ4級別解壓速度一般很快適合嵌入式壓縮率較高中等第三方依賴需要libbz2只有quicklz.c和quicklz.h線程安全流狀態(tài)需要隔離狀態(tài)結構需要隔離但要簡單很多內存模型流式可邊讀邊寫塊式一次壓縮一整段數據QuickLZ的塊式壓縮模型對移植是有利的。它在調用前把一塊完整數據放進緩沖區(qū)壓縮后得到一塊完整數據不需要像bzip2那樣維護在線流狀態(tài)。這樣一來補丁生成和應用兩側的邏輯都變得直白先緩沖數據再壓縮再把長度信息和壓縮數據一起寫文件。雖然文件頭需要多記錄幾個字段但換來的是代碼可讀性和調試友好度大幅提升。3. 在Qt工程里移植bsdiff并把壓縮算法換成qlz3.1 工程組織qmake項目文件與源碼放置移植的第一步不是改算法而是先把代碼結構理清。我習慣把bsdiff核心算法、bspatch核心算法、QuickLZ分別放在獨立目錄里再用qmake把它們組合成一個靜態(tài)庫或者直接編進主工程。下面是一個典型的qmake組織方式QT core CONFIG console c11 TEMPLATE app DEFINES _FILE_OFFSET_BITS64 INCLUDEPATH $$PWD/3rdparty/quicklz SOURCES \ main.cpp \ patch_generator.cpp \ patch_applier.cpp \ bsdiff_core.c \ bspatch_core.c \ $$PWD/3rdparty/quicklz/quicklz.c HEADERS \ patch_generator.h \ patch_applier.h \ bsdiff_core.h \ bspatch_core.h \ $$PWD/3rdparty/quicklz/quicklz.h這段配置里有幾個關鍵點。_FILE_OFFSET_BITS64必須加上尤其當你需要在32位平臺上處理超過2GB的文件時否則bsdiff里的off_t會退化成32位整數讀寫位置直接溢出。quicklz.c放在SOURCES里qmake會按C文件編譯不會受到C名字修飾的影響。bsdiff_core.c和bspatch_core.c里保留原版的差分和合并算法但在對外接口處用C風格函數暴露方便后面用C封裝。我一般會砍掉bsdiff_core.c里原有的main函數和命令行解析只保留核心的diff計算函數比如bsdiff算法的入口。這樣Qt層可以自己決定從哪里讀文件、往哪里寫patch而不是被標準輸入輸出限制住。同理bspatch_core.c里也只保留“從內存中讀取三個塊并合并出新文件”的核心邏輯文件讀取交給Qt側管理。3.2 為qlz訂制補丁文件頭彌補流式壓縮和塊壓縮的格式差異原版bsdiff的patch文件頭只有幾個字段magic、三個塊的壓縮后大小、新文件大小。因為bzip2是流式的bspatch知道自己按流讀到多少字節(jié)算完不需要提前知道解壓后大小。但QuickLZ的塊式壓縮不同解壓時需要明確知道目標緩沖區(qū)的大小否則qlz_decompress不知道預期輸出多少字節(jié)很容易越界。所以移植時一定要改patch文件格式給每個數據塊同時記錄解壓前大小和壓縮后大小。我采用的自定義頭結構如下#define QLZ_PATCH_MAGIC 0x514C505A0401ULL typedef struct { quint64 magic; quint64 new_size; quint64 ctrl_raw_size; quint64 ctrl_comp_size; quint64 diff_raw_size; quint64 diff_comp_size; quint64 extra_raw_size; quint64 extra_comp_size; } QlzPatchHeader;ctrl_raw_size表示控制塊解壓后的字節(jié)數ctrl_comp_size表示壓縮后的字節(jié)數diff和extra同理。new_size是最終新文件的總長度bspatch用它來預先創(chuàng)建輸出文件。這個頭結構總共8個字段每個8字節(jié)固定64字節(jié)沒有對齊問題也很容易做小端序列化。在生成patch時我會先把整個頭用占位數據寫進文件然后依次寫入三個壓縮塊最后再回過頭把真實的長度數據填進頭部。這樣寫入邏輯不用關心頭的總長度也方便后面增加字段?？紤]到不同平臺字節(jié)序可能不同所有長度字段在寫入時統(tǒng)一轉成小端讀取時再轉回主機字節(jié)序這樣patch包才能跨設備通用。3.3 生成側改動把diff和extra塊批量交給qlz_compress生成側的核心改動在于把原來直接調用bzip2流式寫入的地方替換成一個獨立的寫塊函數。這個函數接收一段完整的原始數據用QuickLZ壓縮后連同raw_size和comp_size一起寫入patch文件。代碼實現如下static bool write_qlz_block(QFile out, const QByteArray raw, quint64 *raw_size, quint64 *comp_size) { quint64 raw_len (quint64)raw.size(); quint64 comp_len 0; qlz_state_compress state_compress; QByteArray comp; comp.resize(raw.size() 400); // QuickLZ壓縮時允許的最大膨脹量 comp_len qlz_compress((const void *)raw.data(), (void *)comp.data(), raw.size(), state_compress); *raw_size raw_len; *comp_size comp_len; out.write((const char *)raw_len, sizeof(quint64)); out.write((const char *)comp_len, sizeof(quint64)); out.write(comp.data(), (qint64)comp_len); return true; }寫入時先寫raw_len再寫comp_len最后寫壓縮數據。這樣讀取側能先知道要分配多大的解壓緩沖再決定讀多少壓縮數據。qlz_compress的第四個參數是QuickLZ要求的狀態(tài)結構這里在函數內部定義每次調用都是全新的狀態(tài)避免線程間互相污染。輸出緩沖大小給raw.size()加400這是QuickLZ文檔建議的安全余量因為極端情況下壓縮輸出可能略微膨脹。生成patch的整體流程會把這個函數調用三次分別壓縮ctrl塊、diff塊和extra塊。這三個塊的原始數據從哪里來bsdiff算法在跑完后會得到一整段控制數據和一整段diff、extra拼接數據在原有C代碼里它們是直接按內存塊處理的。我把bsdiff_core.c中間結果通過結構體返回給Qt層Qt層再把它裝進QByteArray調三次write_qlz_block就完成patch文件的主體寫入。這種方式有一個值得注意的副作用原來的bzip2流式寫入可以邊計算邊寫不會額外占用太多內存。改成qlz塊式壓縮后diff塊和extra塊必須全部緩存在內存里才能一次性壓完。對于幾十MB的固件這個代價可以接受對于數GB的文件就要評估設備內存是否夠用。后面避坑章節(jié)會專門講這一點。3.4 應用側改動用qlz_decompress還原三個數據塊并合并應用側也就是bspatch的邏輯改動同樣集中在塊讀取上。原來bzip2是流式讀現在需要把每個壓縮塊完整讀進內存然后一次性解壓。讀取側的代碼和寫入側對稱static bool read_qlz_block(QFile in, QByteArray raw) { quint64 raw_len, comp_len; if (in.read((char *)raw_len, sizeof(quint64)) ! sizeof(quint64)) return false; if (in.read((char *)comp_len, sizeof(quint64)) ! sizeof(quint64)) return false; if (comp_len 1ULL * 1024 * 1024 * 1024) return false; QByteArray comp; comp.resize((qint64)comp_len); if (in.read(comp.data(), (qint64)comp_len) ! (qint64)comp_len) return false; qlz_state_decompress state_decompress; raw.resize((qint64)raw_len); size_t got qlz_decompress((const void *)comp.data(), (void *)raw.data(), raw.size(), state_decompress); return got (size_t)raw_len; }comp_len設置了上限1GB防止損壞的patch文件導致程序嘗試申請超大內存。qlz_decompress的目標長度直接傳raw_len函數返回實際解壓得到的字節(jié)數如果不等于預期就說明patch文件損壞或者版本不匹配。解壓完成后bpatch的合并循環(huán)并不需要改動多少。它從ctrl塊里順序讀出三元組再從diff塊和extra塊里取出對應數據按規(guī)則寫入新文件。因為三個完整塊都常駐內存循環(huán)里只是做內存拷貝和字節(jié)加法運算不再有任何文件IO所以bspatch的跑分通常不會比生成側慢。3.5 在Qt層封裝成生成器和應用器純粹暴露C函數給Qt調用雖然可行但用起來不順。我習慣再包一層帶QString參數的類讓調用方可以直接傳文件路徑內部統(tǒng)一處理異常和錯誤信息。核心類的接口大概是這樣class PatchGenerator { public: bool generate(const QString oldPath, const QString newPath, const QString patchPath, QString *errorMessage); }; class PatchApplier { public: bool apply(const QString oldPath, const QString patchPath, const QString newPath, QString *errorMessage); };在Qt層面我會用QFile讀取文件內容并映射到QByteArray然后調用bsdiff_core.c里的核心函數。整個過程不需要把整個文件再復制一份舊文件和新文件各留一份原始數據再加上diff和extra的緩存內存占用量已經是理論下限的一部分。錯誤處理盡量控制在C層core層只返回整數錯誤碼避免把C的errno和Qt的錯誤機制糾纏在一起。為了讓生成和應用兩側的日志可讀我還會在類里記錄每個階段的耗時和內存占用比如“后綴排序耗時”“diff塊壓縮字節(jié)數”“patch最終大小”這類信息。這些數據在優(yōu)化參數時很有用后面驗證章節(jié)會展開說明。4. 移植避坑清單5個最容易翻車的地方4.1 補丁頭只存壓縮大小導致qlz_decompress內存越界現象生成的patch在生產環(huán)境能正常應用換一個文件就崩潰或者解壓出的內容末尾變成亂碼。排查下來發(fā)現是bspatch側申請的解壓緩沖區(qū)大小不夠qlz_decompress把數據寫到了緩沖區(qū)邊界之外。原因原版bsdiff文件頭只保存三個塊的壓縮后大小因為bzip2流式解壓不需要預先知道解壓后字節(jié)數。QuickLZ不一樣qlz_decompress需要明確指定目標緩沖區(qū)大小而這個值只有生成側知道。解決補丁文件頭必須為每個塊同時保存raw_size和comp_size讀取側嚴格按raw_size分配緩沖區(qū)并在解壓后比較實際返回值。我在read_qlz_block里加了一個斷言got不等于raw_len直接返回失敗避免數據損壞時無感繼續(xù)。4.2 32位平臺下off_t溢出超過2GB的文件直接崩現象在32位的嵌入式設備上跑bspatch文件讀到一半位置變成負數或者生成patch時后綴排序數組下標變成負數程序退出。原因bsdiff原生代碼里的off_t在32位編譯環(huán)境下是32位有符號整數能表達的最大長度只有2GB左右。固件鏡像一旦超過這個閾值所有偏移計算都不可信了。這不是QuickLZ引入的問題是bsdiff本身就需要處理的大文件隱患。解決qmake工程里統(tǒng)一加DEFINES _FILE_OFFSET_BITS64確保glibc的off_t按64位擴展。同時在自己寫的Qt封裝層里所有文件偏移和長度類型都強制用qint64不跟平臺的long類型混用。交叉編譯時還要確認工具鏈默認的off_t實現支持64位。4.3 qlz狀態(tài)結構體在線程池里被共用壓縮結果全亂現象單線程生成patch一切正常把生成任務丟進QThreadPool并發(fā)跑多個文件有的patch能出來有的壓縮數據完全是爛的偶爾還直接crash。原因QuickLZ要求調用者提供壓縮狀態(tài)結構這個結構內部保存了上一輪匹配的窗口信息。多個線程共用同一個state對象時寫操作互相覆蓋壓縮結果自然不可預測。bsdiff原版的bzip2流也類似但塊式壓縮讓這個錯誤更容易被忽略。解決把qlz_state_compress和qlz_state_decompress定義成write_qlz_block和read_qlz_block的局部變量每個線程每次調用都有自己的狀態(tài)。不要嘗試在線程池里緩存狀態(tài)來省那幾十KB內存收益太低風險太高。4.4 端序不同導致patch在另一個架構上不兼容現象在x86開發(fā)機上生成的patch包部署到ARM設備上應用失敗控件不匹配或者解壓后數據錯位。原因bsdiff原版把控制三元組直接按off_t的內存布局寫入文件在不同字節(jié)序平臺上內存布局正好相反。QuickLZ自帶的壓縮頭雖然宣稱跨端序安全但我們的自定義文件頭和控制塊數據都是二進制格式不能假定雙方主機字節(jié)序一致。解決文件頭和ctrl塊三元組在寫入時統(tǒng)一用小端序讀取時用小端轉主機序的函數解析。不要讓結構體直接memcpy到文件里把字段逐個用put_le64和get_le64處理一遍代碼多十幾行但patch包的兼容性問題是徹底解決了。4.5 排序階段內存占用疊加分配失敗卻沒有任何報錯現象處理大文件時程序在某一步突然卡死或者被系統(tǒng)OOM殺掉。用日志看內存占用爬升到接近設備物理內存上限然后進程消失。原因bsdiff的后綴排序階段本身就需要給舊文件每個后綴建立一個索引內存占用大約是舊文件大小的4到8倍。換掉bzip2之后diff塊和extra塊又必須在內存里完整緩存再疊加QuickLZ的輸出緩沖峰值內存比原來的方案還要高。很多移植代碼忽略了對內存峰值的估算分配失敗時又只檢查了一個中間指針沒有形成閉環(huán)。解決生成patch前先做一次內存預測。我用的經驗公式是峰值內存約等于舊文件大小的6倍加上新文件大小的4倍再加上輸出緩沖的余量。在資源受限設備上先驗算一遍超了就改用分塊策略或者在小文件上跑生成側把應用側放到設備端。另外所有malloc和QByteArray::resize都要檢查返回值resize失敗時立即給出明確錯誤信息而不是讓后續(xù)邏輯繼續(xù)踩空指針。5. 移植完怎么驗證回歸測試與性能基線5.1 建立最小回歸用例覆蓋三類邊界數據移植完成后我建議先跑一個最樸素的回歸腳本不要上來就拿真實固件壓測。準備三組測試數據一組是只有幾十字節(jié)差異的小文本文件一組是結構完全不同的兩個二進制文件一組是內容整體偏移了幾個字節(jié)的模擬固件。生成patch、應用patch然后直接比較新文件和原文件是否完全一致用字節(jié)級比較確認差異為零。# 回歸測試三步走 ./patchtool gen old.bin new.bin patch.qlz ./patchtool apply old.bin patch.qlz out.bin cmp new.bin out.bin echo patch round-trip ok這三組數據分別覆蓋了diff流占主導、extra流占主導、以及匹配偏移修正占主導的三種典型場景。bpatch的合并邏輯在這三類輸入下最容易暴露出邊界錯誤比如偏移修正量為負、diff塊用完而extra塊還有很多剩余數據之類的情況跑過這三組再上真機才算心里有底。5.2 參數調整QLZ壓縮級別與匹配窗口的取舍QuickLZ的壓縮級別通過宏控制常見做法是在編譯時指定壓縮等級。等級越高壓縮率越好但內存和CPU開銷也隨之增大。在差分升級場景里我傾向于先測試兩份參數一個追求最小patch體積一個追求最快生成速度然后把patch大小和生成時間放到一張表里對比。以模擬項目X的固件驗證為例兩組參數下的數據差異是低級配置生成時間縮短了近一半patch體積只增大了百分之十到二十。如果分發(fā)渠道的帶寬緊張幾MB的差異確實值得換壓縮級別如果每次更新都有幾十上千臺設備并發(fā)下載生成速度反而更重要。沒有絕對正確的參數只有適合你業(yè)務約束的選擇。我自己在實際工程里養(yǎng)成了一個習慣在每個版本的性能基準測試里固定記錄三項指標——patch生成耗時、patch包體積、設備端應用耗時。這些數據作為歷史基線留在工程里下次改算法或者換壓縮庫時就能用同一組測試數據橫向比較而不是靠感覺判斷方案是否退步。建議你也在移植完成后跑完這幾項寫進自己的工程筆記里后續(xù)維護時能省不少心。這類移植工作最怕的不是算法復雜而是出了問題不知道是格式錯誤、內存問題還是字節(jié)序問題。數據記錄下來日志打清楚驗證腳本跑起來整個鏈路就不那么像玄學了。希望這幾個步驟和避坑經驗能幫你順利把bsdiff加qlz的方案落地到自己的Qt工程里。本文還有配套的精品資源點擊獲取