前言

微信的熱修復(fù)框架Tinker已經(jīng)在國慶節(jié)之前開源了，成為了github.com/Tecent下第一個項目，刷爆了各位開發(fā)者的朋友圈畅蹂。作為一個超級APP的HotFix庫垒拢，Tinker不僅值得我們compile旬迹，更值得我們read。

原理

Tinker和以往的HotFix庫思路不太一樣求类，它更像是APP的增量更新奔垦，在服務(wù)器端通過差異性算法，計算出新舊dex之間的差異包尸疆，推送到客戶端宴倍，進行合成。傳統(tǒng)的差異性算法有BsDiff仓技，而Tinker的牛逼之處就在于它自己基于Dex的文件格式鸵贬，研發(fā)出了DexDiff算法。

補丁生成之DexDiff

補丁生成是在編譯階段進行的脖捻，當(dāng)我們在build.gradle中配置好tinkerOldApkPath后阔逼，調(diào)用tinkerPatchDebug，補丁就開始生成了地沮。

調(diào)用鏈為：

TinkerPatchSchemaTask.tinkerPatch()
->Runner.gradleRun()
->Runner.run()
->Runner.tinkerPatch()
->ApkDecoder.patch()
......
->DexPatchGenerator.executeAndSaveTo()

executeAndSaveTo()方法是DexDiff算法的真正入口嗜浮，DexDiff算法的特點在于它深入分析了Dex文件格式，深度利用Dex的格式來減少差異大小摩疑。

在了解DexDiff之前危融，我們需要對Dex文件有個初步了解，Dex的文件格式如下表雷袋。參考自這里：Dalvik可執(zhí)行格式（dex）上

想要深入了解Dex文件格式的可以看Google官方文檔：https://source.android.com/devices/tech/dalvik/dex-format.html谤祖，《Android軟件安全與逆向分析》這本書里關(guān)于Dex文件也有很詳細(xì)的講解婿滓。

了解了Dex的格式后老速，讓我們來看一下DexDiff的基本步驟粥喜。

DexDiff的主要步驟如下：

Step1:計算出new dex中每項Section的大小，比如string_ids在dex文件中所占大小橘券。

int patchedStringIdsSize = newDex.getTableOfContents().stringIds.size * SizeOf.STRING_ID_ITEM;

step2:根據(jù)表中前一項的偏移地址和大小额湘，計算出每項Section的偏移地址卿吐。

this.patchedStringIdsOffset = patchedHeaderOffset + patchedheaderSize;

step3:調(diào)用DexSectionDiffAlgorithm.execute()，將new dex與old dex中的每項section進行對比锋华，對于每項Section嗡官，遍歷其每一項Item，進行新舊對比毯焕，記錄ADD衍腥，DEL標(biāo)識，存放于patchOperationList中纳猫。接著遍歷patchOperationList婆咸，添加REPLACE標(biāo)識，最后將ADD芜辕，DEL尚骄，REPLACE操作分別記錄到各自的List中。

這里面的新舊對比的算法很有趣侵续，它是直接將oldItem.compareTo(newItem)倔丈，結(jié)果小于0記為DEL，大于0記為ADD状蜗。為什么可以直接這樣比較呢需五？別忘啦，從上面Dex文件格式表中可知轧坎，Dex文件中的Section都是經(jīng)過排序的警儒。

上圖中，old dex中下標(biāo)為2的item "c" 被DEL眶根，c后面的元素前移蜀铲，new dex中下標(biāo)5處ADD一個item "f"，而在下標(biāo)8處又ADD一個item "j"属百。

下標(biāo)5的"f"在這里被記為ADD记劝，但是它其實是REPLACE了"g"。在之后遍歷patchOperationList時族扰，算法會判斷operation前一個opearation（prevPatchOperation）的類型厌丑，若prevPatchOperation為DEL，而自己剛好為ADD渔呵，那么就將自己的類型改為REPLACE怒竿。

Iterator<PatchOperation<T>> patchOperationIt = this.patchOperationList.iterator();
PatchOperation<T> prevPatchOperation = null;
while (patchOperationIt.hasNext()) {
   PatchOperation<T> patchOperation = patchOperationIt.next();
   if (prevPatchOperation != null
       && prevPatchOperation.op == PatchOperation.OP_DEL
       && patchOperation.op == PatchOperation.OP_ADD
      ) {
          if (prevPatchOperation.index == patchOperation.index) {
              prevPatchOperation.op = PatchOperation.OP_REPLACE;
              prevPatchOperation.newItem = patchOperation.newItem;
              patchOperationIt.remove();
              prevPatchOperation = null;
            } else {
              prevPatchOperation = patchOperation;
            }
        } else {
            prevPatchOperation = patchOperation;
        }
 }

step4:調(diào)用DexPatchGenerator.writePatchOperations()，將記錄寫入補丁扩氢。
對于DEL：
開辟一塊DelOpIndexList大小的區(qū)域(DelOpIndexList中記錄了每塊要刪除部分的索引),遍歷記錄DelOpIndexList耕驰，對于每一個DEL索引，計算出其相對于前一個DEL索引的偏移录豺，記錄偏移量朦肘。

buffer.writeUleb128(delOpIndexList.size());
    int lastIndex = 0;
    for (Integer index : delOpIndexList) {
        buffer.writeSleb128(index - lastIndex);
        lastIndex = index;
    }

對于ADD和REPLACE饭弓，也會進行和DEL一樣的操作。

buffer.writeUleb128(addOpIndexList.size());
    lastIndex = 0;
    for (Integer index : addOpIndexList) {
        buffer.writeSleb128(index - lastIndex);
        lastIndex = index;
    }
    
buffer.writeUleb128(replaceOpIndexList.size());
    lastIndex = 0;
    for (Integer index : replaceOpIndexList) {
        buffer.writeSleb128(index - lastIndex);
        lastIndex = index;
    }

不同的一點是媒抠，ADD和REPALACE還會接著寫入新增和替換的item弟断。

 for (T newItem : newItemList) {
        if (newItem instanceof StringData) {
            buffer.writeStringData((StringData) newItem);
        } else
        if (newItem instanceof Integer) {
            // TypeId item.
            buffer.writeInt((Integer) newItem);
        } else
        if (newItem instanceof TypeList) {
            buffer.writeTypeList((TypeList) newItem);
        }
        ......
}

總結(jié)

這里只是簡單的介紹了DexDiff的簡要過程，中間其實省去了很多細(xì)節(jié)趴生，而這些細(xì)節(jié)與Dex文件格式聯(lián)系非常緊密阀趴，想要徹底的了解DexDiff原理，還需好好研究Dex文件苍匆。

(轉(zhuǎn)載請注明ID:半棧工程師舍咖，歡迎訪問個人博客：https://halfstackdeveloper.github.io/)

歡迎關(guān)注我的知乎專欄：https://zhuanlan.zhihu.com/halfstack