前言
微信的热修复框架Tinker已经在国庆节之前开源了，成为了github.com/Tecent下第一个项目，刷爆了各位开发者的朋友圈。作为一个超级APP的HotFix库，Tinker不仅值得我们compile，更值得我们read。
原理
Tinker和以往的HotFix库思路不太一样，它更像是APP的增量更新，在服务器端通过差异性算法，计算出新旧dex之间的差异包，推送到客户端，进行合成。传统的差异性算法有BsDiff，而Tinker的牛逼之处就在于它自己基于Dex的文件格式，研发出了DexDiff算法。
补丁生成之DexDiff
补丁生成是在编译阶段进行的，当我们在build.gradle中配置好tinkerOldApkPath后，调用tinkerPatchDebug，补丁就开始生成了。
调用链为：
TinkerPatchSchemaTask.tinkerPatch()
->Runner.gradleRun()
->Runner.run()
->Runner.tinkerPatch()
->ApkDecoder.patch()
……
->DexPatchGenerator.executeAndSaveTo()
executeAndSaveTo()方法是DexDiff算法的真正入口，DexDiff算法的特点在于它深入分析了Dex文件格式，深度利用Dex的格式来减少差异大小。
在了解DexDiff之前，我们需要对Dex文件有个初步了解，Dex的文件格式如下表。参考自这里：Dalvik可执行格式（dex）上
了解了Dex的格式后，让我们来看一下DexDiff的基本步骤。想要深入了解Dex文件格式的可以看Google官方文档：https://source.android.com/devices/tech/dalvik/dex-format.html，《Android软件安全与逆向分析》这本书里关于Dex文件也有很详细的讲解。
DexDiff的主要步骤如下：
Step1:计算出new dex中每项Section的大小，比如string_ids在dex文件中所占大小。
int patchedStringIdsSize = newDex.getTableOfContents().stringIds.size * SizeOf.STRING_ID_ITEM;
step2:根据表中前一项的偏移地址和大小，计算出每项Section的偏移地址。
this.patchedStringIdsOffset = patchedHeaderOffset + patchedheaderSize;
step3:调用DexSectionDiffAlgorithm.execute()，将new dex与old dex中的每项section进行对比，对于每项Section，遍历其每一项Item，进行新旧对比，记录ADD，DEL标识，存放于patchOperationList中。接着遍历patchOperationList，添加REPLACE标识，最后将ADD，DEL，REPLACE操作分别记录到各自的List中。
这里面的新旧对比的算法很有趣，它是直接将oldItem.compareTo(newItem)，结果小于0记为DEL，大于0记为ADD。为什么可以直接这样比较呢？别忘啦，从上面Dex文件格式表中可知，Dex文件中的Section都是经过排序的。
上图中，old dex中下标为2的item “c” 被DEL，c后面的元素前移，new dex中下标5处ADD一个item “f”，而在下标8处又ADD一个item “j”。
下标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:调用DexPatchGenerator.writePatchOperations()，将记录写入补丁。
对于DEL：
开辟一块DelOpIndexList大小的区域(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);
}
......
}总结
这里只是简单的介绍了DexDiff的简要过程，中间其实省去了很多细节，而这些细节与Dex文件格式联系非常紧密，想要彻底的了解DexDiff原理，还需好好研究Dex文件。