共计 32906 个字符，预计需要花费 83 分钟才能阅读完成。
tinker 有个非常大的亮点就是自研发了一套 dex diff、patch 相关算法。本篇文章主要目的就是分析该算法。当然值得注意的是，分析的前提就是需要对 dex 文件的格式要有一定的认识，否则的话可能会一脸懵逼态。
所以，本文会先对 dex 文件格式做一个简单的分析，也会做一些简单的实验，最后进入到 dex diff,patch 算法部分。
首先简单了解下 Dex 文件，大家在反编译的时候，都清楚 apk 中会包含一个或者多个 *.dex 文件，该文件中存储了我们编写的代码，一般情况下我们还会通过工具转化为 jar，然后通过一些工具反编译查看。
jar 文件大家应该都清楚，类似于 class 文件的压缩包，一般情况下，我们直接解压就可以看到一个个 class 文件。而 dex 文件我们无法通过解压获取内部的一个个 class 文件，说明 dex 文件拥有自己特定的格式：
dex 对 Java 类文件重新排列，将所有 JAVA 类文件中的常量池分解，消除其中的冗余信息，重新组合形成一个常量池，所有的类文件共享同一个常量池，使得相同的字符串、常量在 DEX 文件中只出现一次，从而减小了文件的体积。
接下来我们看看 dex 文件的内部结构到底是什么样子。
分析一个文件的组成，最好自己编写一个最简单的 dex 文件来分析。
首先我们编写一个类 Hello.java：
public class Hello{public static void main(String[] args){System.out.println("hello dex！");
}
}然后进行编译：
javac -source 1.7 -target 1.7 Hello.java最后通过 dx 工作将其转化为 dex 文件：
dx --dex --output=Hello.dex Hello.classdx 路径在 Android-sdk/build-tools/ 版本号 /dx 下，如果无法识别 dx 命令，记得将该路径放到 path 下，或者使用绝对路径。
这样我们就得到了一个非常简单的 dex 文件。
首先展示一张 dex 文件的大致的内部结构图：
当然，单纯从一张图来说明肯定是远远不够的，因为我们后续要研究 diff，patch 算法，理论上我们应该要知道更多的细节，甚至要细致到：一个 dex 文件的每个字节表示的是什么内容。
对于一个类似于二进制的文件，最好的办法肯定不是靠记忆，好在有这么一个软件可以帮助我们的分析：
- 软件名称：010 Editor
下载完成安装后，打开我们的 dex 文件，会引导你安装 dex 文件的解析模板。
最终打开效果图如下：
上面部分代表了 dex 文件的内容（16 进制的方式展示），下面部分展示了 dex 文件的各个区域，你可以通过点击下面部分，来查看其对应的内容区域以及内容。
当然这里也非常建议，阅读一些专门的文章来加深对 dex 文件的理解：
- DEX 文件格式分析
- Android 逆向之旅—解析编译之后的 Dex 文件格式
本文也仅会对 dex 文件做简单的格式分析。
dex_header
首先我们队 dex_header 做一个大致的分析，header 中包含如下字段：
首先我们猜测下 header 的作用，可以看到起包含了一些校验相关的字段，和整个 dex 文件大致区块的分布 (off 都为偏移量)。
这样的好处就是，当虚拟机读取 dex 文件时，只需要读取出 header 部分，就可以知道 dex 文件的大致区块分布了；并且可以检验出该文件格式是否正确、文件是否被篡改等。
- 能够证明该文件是 dex 文件
- checksum 和 signature 主要用于校验文件的完整性
- file_size 为 dex 文件的大小
- head_size 为头文件的大小
- endian_tag 预设值为 12345678，标识默认采用 Little-Endian(自行搜索)。
剩下的几乎都是成对出现的 size 和 off，大多代表各区块的包含的特定数据结构的数量和偏移量。例如：string_ids_off 为 112，指的是偏移量 112 开始为 string_ids 区域；string_ids_size 为 14，代表 string_id_item 的数量为 14 个。剩下的都类似就不介绍了。
结合 010Editor 可以看到各个区域包含的数据结构，以及对应的值，慢慢看就好了。
除了 header 还有个比较重要的部分是 dex_map_list，首先看个图：
首先是 map_item_list 数量，接下来是每个 map_item_list 的描述。
map_item_list 有什么用呢？
可以看到每个 map_list_item 包含一个枚举类型，一个 2 字节暂未使用的成员、一个 size 表明当前类型的个数，offset 表明当前类型偏移量。
拿本例来说：
- 首先是 TYPE_HEADER_ITEM 类型，包含 1 个 header(size=1)，且偏移量为 0。
- 接下来是 TYPE_STRING_ID_ITEM，包含 14 个 string_id_item（size=14），且偏移量为 112（如果有印象，header 的长度为 112，紧跟着 header）。
剩下的依次类推~~
这样的话，可以看出通过 map_list，可以将一个完整的 dex 文件划分成固定的区域（本例为 13），且知道每个区域的开始，以及该区域对应的数据格式的个数。
通过 map_list 找到各个区域的开始，每个区域都会对应特定的数据结构，通过 010 Editor 看就好了。
现在我们了解了 dex 的基本格式，接下来我们考虑下如何做 dex diff 和 patch。
先要考虑的是我们有什么：
- old dex
- new dex
我们想要生成一个 patch 文件，该文件和 old dex 通过 patch 算法还能生成 new dex。
- 那么我们该如何做呢？
根据上文的分析，我们知道 dex 文件大致有 3 个部分 (这里 3 个部分主要用于分析，勿较真)：
- header
- 各个区域
- map list
header 实际上是可以根据后面的数据确定其内容的，并且是定长 112 的；各个区域后面说；map list 实际上可以做到定位到各个区域开始位置;
我们最终 patch + old dex -> new dex；针对上述的 3 个部分，
- header 我们可以不做处理，因为可以根据其他数据生成；
- map list 这个东西，其实我们主要要的是各个区域的开始 (offset)
- 知道了各个区域的 offset 后，在我们生成 new dex 的时候，我们就可以定位各个区域的开始和结束位置，那么只需要往各个区域写数据即可。
那么我们看看针对一个区域的 diff，假设有个 string 区域，主要用于存储字符串：
old dex 该区域的字符串有：Hello、World、zhy
new dex 该区域的字符串有：Android、World、zhy
可以看出，针对该区域，我们删除了 Hello，增加了 Android。
那么 patch 中针对该区域可以如下记录：
“del Hello , add Android”（实际情况需要转化为二进制）。
想想应用中可以直接读取出 old dex，即知道:
- 原来该区域包含：Hello、World、zhy
- patch 中该区域包含：”del Hello , add Android”
那么，可以非常容易的计算出 new dex 中包含：
Android、World、zhy。
这样我们就完成了一个区域大致的 diff 和 patch 算法，其他各个区域的 diff 和 patch 和上述类似。
这样来看，是不是觉得这个 diff 和 patch 算法也没有那么的复杂，实际上 tinker 的做法与上述类似，实际情况可能要比上述描述要复杂一些，但是大体上是差不多的。
有了一个大致的算法概念之后，我们就可以去看源码了。
这里看代码实际上也是有技巧的，tinker 的代码实际上蛮多的，往往你可以会陷在一堆的代码中。我们可以这么考虑，比如 diff 算法，输入参数为 old dex、new dex，输出为 patch file。
那么肯定存在某个类，或者某个方法接受和输出上述参数。实际上该类为 DexPatchGenerator：
diff 的 API 使用代码为：
@Test
public void testDiff() throws IOException {File oldFile = new File("Hello.dex");
File newFile = new File("Hello-World.dex");
File patchFile = new File("patch.dex");
DexPatchGenerator dexPatchGenerator
= new DexPatchGenerator(oldFile, newFile);
dexPatchGenerator.executeAndSaveTo(patchFile);
}写一个单元测试或者 main 方法，上述几行代码就是 diff 算法。
所以查看代码时要有针对性，比如看 diff 算法，就找到 diff 算法的入口，不要在 gradle plugin 中去纠结。
public DexPatchGenerator(File oldDexFile, File newDexFile) throws IOException {this(new Dex(oldDexFile), new Dex(newDexFile));
}将我们传入的 dex 文件转化为了 Dex 对象。
public Dex(File file) throws IOException {
// 删除了一堆代码
InputStream in = new BufferedInputStream(new FileInputStream(file));
loadFrom(in, (int) file.length());
}
private void loadFrom(InputStream in, int initSize) throws IOException {byte[] rawData = FileUtils.readStream(in, initSize);
this.data = ByteBuffer.wrap(rawData);
this.data.order(ByteOrder.LITTLE_ENDIAN);
this.tableOfContents.readFrom(this);
}首先将我们的文件读取为 byte[] 数组（这里还是蛮耗费内存的），然后由 ByteBuffer 进行包装，并设置字节顺序为小端（这里说明 ByteBuffer 还是蛮方便的。然后通过 readFrom 方法为 Dex 对象的 tableOfContents 赋值。
#TableOfContents
public void readFrom(Dex dex) throws IOException {readHeader(dex.openSection(header));
// special case, since mapList.byteCount is available only after
// computeSizesFromOffsets() was invoked, so here we can't use
// dex.openSection(mapList) to get dex section. Or
// an {@code java.nio.BufferUnderflowException} will be thrown.
readMap(dex.openSection(mapList.off));
computeSizesFromOffsets();}在其内部执行了 readHeader 和 readMap，上文我们大致分析了 header 和 map list 相关，实际上就是将这两个区域转化为一定的数据结构，读取然后存储到内存中。
首先看 readHeader:
private void readHeader(Dex.Section headerIn) throws UnsupportedEncodingException {byte[] magic = headerIn.readByteArray(8);
int apiTarget = DexFormat.magicToApi(magic);
if (apiTarget != DexFormat.API_NO_EXTENDED_OPCODES) {throw new DexException("Unexpected magic:" + Arrays.toString(magic));
}
checksum = headerIn.readInt();
signature = headerIn.readByteArray(20);
fileSize = headerIn.readInt();
int headerSize = headerIn.readInt();
if (headerSize != SizeOf.HEADER_ITEM) {throw new DexException("Unexpected header: 0x" + Integer.toHexString(headerSize));
}
int endianTag = headerIn.readInt();
if (endianTag != DexFormat.ENDIAN_TAG) {throw new DexException("Unexpected endian tag: 0x" + Integer.toHexString(endianTag));
}
linkSize = headerIn.readInt();
linkOff = headerIn.readInt();
mapList.off = headerIn.readInt();
if (mapList.off == 0) {throw new DexException("Cannot merge dex files that do not contain a map");
}
stringIds.size = headerIn.readInt();
stringIds.off = headerIn.readInt();
typeIds.size = headerIn.readInt();
typeIds.off = headerIn.readInt();
protoIds.size = headerIn.readInt();
protoIds.off = headerIn.readInt();
fieldIds.size = headerIn.readInt();
fieldIds.off = headerIn.readInt();
methodIds.size = headerIn.readInt();
methodIds.off = headerIn.readInt();
classDefs.size = headerIn.readInt();
classDefs.off = headerIn.readInt();
dataSize = headerIn.readInt();
dataOff = headerIn.readInt();}如果你现在打开着 010 Editor，或者看一眼最前面的图，实际上就是将 header 中所有的字段定义出来，读取响应的字节并赋值。
接下来看 readMap:
private void readMap(Dex.Section in) throws IOException {int mapSize = in.readInt();
Section previous = null;
for (int i = 0; i < mapSize; i++) {short type = in.readShort();
in.readShort(); // unused
Section section = getSection(type);
int size = in.readInt();
int offset = in.readInt();
section.size = size;
section.off = offset;
previous = section;
}
header.off = 0;
Arrays.sort(sections);
// Skip header section, since its offset must be zero.
for (int i = 1; i < sections.length; ++i) {if (sections[i].off == Section.UNDEF_OFFSET) {sections[i].off = sections[i - 1].off;
}
}
}这里注意，在读取 header 的时候，实际上已经读取除了 map list 区域的 offset，并存储在 mapList.off 中。所以 map list 中实际上是从这个位置开始的。首先读取的就是 map_list_item 的个数，接下来读取的就是每个 map_list_item 对应的实际数据。
可以看到依次读取：type,unused,size,offset，如果你还有印象前面我们描述了 map_list_item 是与此对应的，对应的数据结构为 TableContents.Section 对象。
computeSizesFromOffsets() 主要为 section 的 byteCount（占据了多个字节）参数赋值。
到这里就完成了 dex file 到 Dex 对象的初始化。
有了两个 Dex 对象之后，就需要去做 diff 操作了。
继续回到源码：
public DexPatchGenerator(File oldDexFile, InputStream newDexStream) throws IOException {this(new Dex(oldDexFile), new Dex(newDexStream));
}直接到两个 Dex 对象的构造函数：
public DexPatchGenerator(Dex oldDex, Dex newDex) {
this.oldDex = oldDex;
this.newDex = newDex;
SparseIndexMap oldToNewIndexMap = new SparseIndexMap();
SparseIndexMap oldToPatchedIndexMap = new SparseIndexMap();
SparseIndexMap newToPatchedIndexMap = new SparseIndexMap();
SparseIndexMap selfIndexMapForSkip = new SparseIndexMap();
additionalRemovingClassPatternSet = new HashSet<>();
this.stringDataSectionDiffAlg = new StringDataSectionDiffAlgorithm(
oldDex, newDex,
oldToNewIndexMap,
oldToPatchedIndexMap,
newToPatchedIndexMap,
selfIndexMapForSkip
);
this.typeIdSectionDiffAlg = ...
this.protoIdSectionDiffAlg = ...
this.fieldIdSectionDiffAlg = ...
this.methodIdSectionDiffAlg = ...
this.classDefSectionDiffAlg = ...
this.typeListSectionDiffAlg = ...
this.annotationSetRefListSectionDiffAlg = ...
this.annotationSetSectionDiffAlg = ...
this.classDataSectionDiffAlg = ...
this.codeSectionDiffAlg = ...
this.debugInfoSectionDiffAlg = ...
this.annotationSectionDiffAlg = ...
this.encodedArraySectionDiffAlg = ...
this.annotationsDirectorySectionDiffAlg = ...
}看到其首先为 oldDex,newDex 赋值，然后依次初始化了 15 个算法，每个算法代表每个区域，算法的目的就像我们之前描述的那样，要知道“删除了哪些，新增了哪些”；
我们继续看代码:
dexPatchGenerator.executeAndSaveTo(patchFile);有了 dexPatchGenerator 对象后，直接指向了 executeAndSaveTo 方法。
public void executeAndSaveTo(File file) throws IOException {
OutputStream os = null;
try {os = new BufferedOutputStream(new FileOutputStream(file));
executeAndSaveTo(os);
} finally {if (os != null) {
try {os.close();
} catch (Exception e) {// ignored.}
}
}
}到 executeAndSaveTo 方法：
public void executeAndSaveTo(OutputStream out) throws IOException {
int patchedheaderSize = SizeOf.HEADER_ITEM;
int patchedStringIdsSize = newDex.getTableOfContents().stringIds.size * SizeOf.STRING_ID_ITEM;
int patchedTypeIdsSize = newDex.getTableOfContents().typeIds.size * SizeOf.TYPE_ID_ITEM;
int patchedProtoIdsSize = newDex.getTableOfContents().protoIds.size * SizeOf.PROTO_ID_ITEM;
int patchedFieldIdsSize = newDex.getTableOfContents().fieldIds.size * SizeOf.MEMBER_ID_ITEM;
int patchedMethodIdsSize = newDex.getTableOfContents().methodIds.size * SizeOf.MEMBER_ID_ITEM;
int patchedClassDefsSize = newDex.getTableOfContents().classDefs.size * SizeOf.CLASS_DEF_ITEM;
int patchedIdSectionSize =
patchedStringIdsSize
+ patchedTypeIdsSize
+ patchedProtoIdsSize
+ patchedFieldIdsSize
+ patchedMethodIdsSize
+ patchedClassDefsSize;
this.patchedHeaderOffset = 0;
this.patchedStringIdsOffset = patchedHeaderOffset + patchedheaderSize;
this.stringDataSectionDiffAlg.execute();
this.patchedStringDataItemsOffset = patchedheaderSize + patchedIdSectionSize;
this.stringDataSectionDiffAlg.simulatePatchOperation(this.patchedStringDataItemsOffset);
// 省略了其余 14 个算法的一堆代码
this.patchedDexSize
= this.patchedMapListOffset
+ patchedMapListSize;
writeResultToStream(out);
}因为涉及到 15 个算法，所以这里的代码非常长，我们这里只拿其中一个算法来说明。
每个算法都会执行 execute 和 simulatePatchOperation 方法：
首先看 execute:
public void execute() {this.patchOperationList.clear();
// 1. 拿到 oldDex 和 newDex 的 itemList
this.adjustedOldIndexedItemsWithOrigOrder = collectSectionItems(this.oldDex, true);
this.oldItemCount = this.adjustedOldIndexedItemsWithOrigOrder.length;
AbstractMap.SimpleEntry<Integer, T>[] adjustedOldIndexedItems = new AbstractMap.SimpleEntry[this.oldItemCount];
System.arraycopy(this.adjustedOldIndexedItemsWithOrigOrder, 0, adjustedOldIndexedItems, 0, this.oldItemCount);
Arrays.sort(adjustedOldIndexedItems, this.comparatorForItemDiff);
AbstractMap.SimpleEntry<Integer, T>[] adjustedNewIndexedItems = collectSectionItems(this.newDex, false);
this.newItemCount = adjustedNewIndexedItems.length;
Arrays.sort(adjustedNewIndexedItems, this.comparatorForItemDiff);
int oldCursor = 0;
int newCursor = 0;
// 2. 遍历，对比，收集 patch 操作
while (oldCursor < this.oldItemCount || newCursor < this.newItemCount) {if (oldCursor >= this.oldItemCount) {
// rest item are all newItem.
while (newCursor < this.newItemCount) {// 对剩下的 newItem 做 ADD 操作}
} else if (newCursor >= newItemCount) {
// rest item are all oldItem.
while (oldCursor < oldItemCount) {// 对剩下的 oldItem 做 DEL 操作}
} else {AbstractMap.SimpleEntry<Integer, T> oldIndexedItem = adjustedOldIndexedItems[oldCursor];
AbstractMap.SimpleEntry<Integer, T> newIndexedItem = adjustedNewIndexedItems[newCursor];
int cmpRes = oldIndexedItem.getValue().compareTo(newIndexedItem.getValue());
if (cmpRes < 0) {int deletedIndex = oldIndexedItem.getKey();
int deletedOffset = getItemOffsetOrIndex(deletedIndex, oldIndexedItem.getValue());
this.patchOperationList.add(new PatchOperation<T>(PatchOperation.OP_DEL, deletedIndex));
markDeletedIndexOrOffset(this.oldToPatchedIndexMap, deletedIndex, deletedOffset);
++oldCursor;
} else if (cmpRes > 0) {
this.patchOperationList.add(new PatchOperation<>(PatchOperation.OP_ADD,
newIndexedItem.getKey(), newIndexedItem.getValue()));
++newCursor;
} else {int oldIndex = oldIndexedItem.getKey();
int newIndex = newIndexedItem.getKey();
int oldOffset = getItemOffsetOrIndex(oldIndexedItem.getKey(), oldIndexedItem.getValue());
int newOffset = getItemOffsetOrIndex(newIndexedItem.getKey(), newIndexedItem.getValue());
if (oldIndex != newIndex) {this.oldIndexToNewIndexMap.put(oldIndex, newIndex);
}
if (oldOffset != newOffset) {this.oldOffsetToNewOffsetMap.put(oldOffset, newOffset);
}
++oldCursor;
++newCursor;
}
}
}
// 未完
}可以看到首先读取 oldDex 和 newDex 对应区域的数据并排序，分别 adjustedOldIndexedItems 和 adjustedNewIndexedItems。
接下来就开始遍历了，直接看 else 部分：
分别根据当前的 cursor，获取 oldItem 和 newItem，对其 value 对对比：
- 如果 <0 , 则认为该 old Item 被删除了，记录为 PatchOperation.OP_DEL，并记录该 oldItem index 到 PatchOperation 对象，加入到 patchOperationList 中。
- 如果 >0, 则认为该 newItem 是新增的，记录为 PatchOperation.OP_ADD，并记录该 newItem index 和 value 到 PatchOperation 对象，加入到 patchOperationList 中。
- 如果 =0, 不会生成 PatchOperation。
经过上述，我们得到了一个 patchOperationList 对象。
继续下半部分代码：
public void execute() {
// 接上...
// 根据 index 排序，如果 index 一样，则先 DEL 后 ADD
Collections.sort(this.patchOperationList, comparatorForPatchOperationOpt);
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;}
}
// Finally we record some information for the final calculations.
patchOperationIt = this.patchOperationList.iterator();
while (patchOperationIt.hasNext()) {PatchOperation<T> patchOperation = patchOperationIt.next();
switch (patchOperation.op) {
case PatchOperation.OP_DEL: {indexToDelOperationMap.put(patchOperation.index, patchOperation);
break;
}
case PatchOperation.OP_ADD: {indexToAddOperationMap.put(patchOperation.index, patchOperation);
break;
}
case PatchOperation.OP_REPLACE: {indexToReplaceOperationMap.put(patchOperation.index, patchOperation);
break;
}
}
}
}- 首先对 patchOperationList 按照 index 排序，如果 index 一致则先 DEL、后 ADD。
- 接下来一个对所有的 operation 的迭代，主要将 index 一致的，且连续的 DEL、ADD 转化为 REPLACE 操作。
- 最后将 patchOperationList 转化为 3 个 Map，分别为：indexToDelOperationMap，indexToAddOperationMap,indexToReplaceOperationMap。
ok，经历完成 execute 之后，我们主要的产物就是 3 个 Map，分别记录了：oldDex 中哪些 index 需要删除；newDex 中新增了哪些 item；哪些 item 需要替换为新 item。
刚才说了每个算法除了 execute() 还有个 simulatePatchOperation()
this.stringDataSectionDiffAlg
.simulatePatchOperation(this.patchedStringDataItemsOffset);传入的偏移量为 data 区域的偏移量。
public void simulatePatchOperation(int baseOffset) {
int oldIndex = 0;
int patchedIndex = 0;
int patchedOffset = baseOffset;
while (oldIndex < this.oldItemCount || patchedIndex < this.newItemCount) {if (this.indexToAddOperationMap.containsKey(patchedIndex)) {
// 省略了一些代码
T newItem = patchOperation.newItem;
int itemSize = getItemSize(newItem);
++patchedIndex;
patchedOffset += itemSize;
} else if (this.indexToReplaceOperationMap.containsKey(patchedIndex)) {
// 省略了一些代码
T newItem = patchOperation.newItem;
int itemSize = getItemSize(newItem);
++patchedIndex;
patchedOffset += itemSize;
} else if (this.indexToDelOperationMap.containsKey(oldIndex)) {++oldIndex;} else if (this.indexToReplaceOperationMap.containsKey(oldIndex)) {++oldIndex;} else if (oldIndex < this.oldItemCount) {
++oldIndex;
++patchedIndex;
patchedOffset += itemSize;
}
}
this.patchedSectionSize = SizeOf.roundToTimesOfFour(patchedOffset - baseOffset);
}遍历 oldIndex 与 newIndex，分别在 indexToAddOperationMap,indexToReplaceOperationMap,indexToDelOperationMap 中查找。
这里关注一点最终的一个产物是 this.patchedSectionSize，由 patchedOffset-baseOffset 所得。
这里有几种情况会造成 patchedOffset+=itemSize：
- indexToAddOperationMap 中包含 patchIndex
- indexToReplaceOperationMap 包含 patchIndex
- 不在 indexToDelOperationMap 与 indexToReplaceOperationMap 中的 oldDex.
其实很好理解，这个 patchedSectionSize 其实对应 newDex 的这个区域的 size。所以，包含需要 ADD 的 Item，会被替代的 Item，以及 OLD ITEMS 中没有被删除和替代的 Item。这三者相加即为 newDex 的 itemList。
到这里，一个算法就执行完毕了。
经过这样的一个算法，我们得到了 PatchOperationList 和对应区域 sectionSize。那么执行完成所有的算法，应该会得到针对每个算法的 PatchOperationList，和每个区域的 sectionSize；每个区域的 sectionSize 实际上换算得到每个区域的 offset。
每个区域的算法，execute 和 simulatePatchOperation 代码都是复用的，所以其他的都只有细微的变化，可以自己看了。
接下来看执行完成所有的算法后的 writeResultToStream 方法。
private void writeResultToStream(OutputStream os) throws IOException {DexDataBuffer buffer = new DexDataBuffer();
buffer.write(DexPatchFile.MAGIC); // DEXDIFF
buffer.writeShort(DexPatchFile.CURRENT_VERSION); /0x0002
buffer.writeInt(this.patchedDexSize);
// we will return here to write firstChunkOffset later.
int posOfFirstChunkOffsetField = buffer.position();
buffer.writeInt(0);
buffer.writeInt(this.patchedStringIdsOffset);
buffer.writeInt(this.patchedTypeIdsOffset);
buffer.writeInt(this.patchedProtoIdsOffset);
buffer.writeInt(this.patchedFieldIdsOffset);
buffer.writeInt(this.patchedMethodIdsOffset);
buffer.writeInt(this.patchedClassDefsOffset);
buffer.writeInt(this.patchedMapListOffset);
buffer.writeInt(this.patchedTypeListsOffset);
buffer.writeInt(this.patchedAnnotationSetRefListItemsOffset);
buffer.writeInt(this.patchedAnnotationSetItemsOffset);
buffer.writeInt(this.patchedClassDataItemsOffset);
buffer.writeInt(this.patchedCodeItemsOffset);
buffer.writeInt(this.patchedStringDataItemsOffset);
buffer.writeInt(this.patchedDebugInfoItemsOffset);
buffer.writeInt(this.patchedAnnotationItemsOffset);
buffer.writeInt(this.patchedEncodedArrayItemsOffset);
buffer.writeInt(this.patchedAnnotationsDirectoryItemsOffset);
buffer.write(this.oldDex.computeSignature(false));
int firstChunkOffset = buffer.position();
buffer.position(posOfFirstChunkOffsetField);
buffer.writeInt(firstChunkOffset);
buffer.position(firstChunkOffset);
writePatchOperations(buffer, this.stringDataSectionDiffAlg.getPatchOperationList());
// 省略其他 14 个 writePatch...
byte[] bufferData = buffer.array();
os.write(bufferData);
os.flush();}- 首先写了 MAGIC，CURRENT_VERSION 主要用于检查该文件为合法的 tinker patch 文件。
- 然后写入 patchedDexSize
- 第四位写入的是数据区的 offset，可以看到先使用 0 站位，等所有的 map list 相关的 offset 书写结束，写入当前的位置。
- 接下来写入所有的跟 maplist 各个区域相关的 offset（这里各个区域的排序不重要，读写一致即可）
- 然后执行每个算法写入对应区域的信息
- 最后生成 patch 文件
我们依旧只看 stringDataSectionDiffAlg 这个算法。
private <T extends Comparable<T>> void writePatchOperations(DexDataBuffer buffer, List<PatchOperation<T>> patchOperationList) {List<Integer> delOpIndexList = new ArrayList<>(patchOperationList.size());
List<Integer> addOpIndexList = new ArrayList<>(patchOperationList.size());
List<Integer> replaceOpIndexList = new ArrayList<>(patchOperationList.size());
List<T> newItemList = new ArrayList<>(patchOperationList.size());
for (PatchOperation<T> patchOperation : patchOperationList) {switch (patchOperation.op) {
case PatchOperation.OP_DEL: {delOpIndexList.add(patchOperation.index);
break;
}
case PatchOperation.OP_ADD: {addOpIndexList.add(patchOperation.index);
newItemList.add(patchOperation.newItem);
break;
}
case PatchOperation.OP_REPLACE: {replaceOpIndexList.add(patchOperation.index);
newItemList.add(patchOperation.newItem);
break;
}
}
}
buffer.writeUleb128(delOpIndexList.size());
int lastIndex = 0;
for (Integer index : delOpIndexList) {buffer.writeSleb128(index - lastIndex);
lastIndex = index;
}
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;
}
for (T newItem : newItemList) {if (newItem instanceof StringData) {buffer.writeStringData((StringData) newItem);
}
// else 其他类型，write 其他类型 Data
}
}首先将我们的 patchOperationList 转化为 3 个 OpIndexList，分别对应 DEL,ADD,REPLACE，以及将所有的 item 存入 newItemList。
然后依次写入：
- del 操作的个数，每个 del 的 index
- add 操作的个数，每个 add 的 index
- replace 操作的个数，每个需要 replace 的 index
- 最后依次写入 newItemList.
其他的算法也是执行了类似的操作。
最好来看看我们生成的 patch 是什么样子的：
- 首先包含几个字段，证明自己是 tinker patch
- 包含生成 newDex 各个区域的 offset，即可以将 newDex 划分了多个区域，定位到起点
- 包含 newDex 各个区域的 Item 的删除的索引 (oldDex)，新增的索引和值，替换的索引和值
那么这么看，我们猜测 Patch 的逻辑时这样的：
- 首先根据各个区域的 offset，确定各个区域的起点
- 读取 oldDex 各个区域的 items，然后根据 patch 中去除掉 oldDex 中需要删除的和需要替换的 item，再加上新增的 item 和替换的 item 即可组成 newOld 该区域的 items。
即，newDex 的某个区域的包含：
oldItems - del - replace + addItems + replaceItems这么看挺清晰的，下面看代码咯~
与 diff 一样，肯定有那么一个类或者方法，接受 old dex File 和 patch File，最后生成 new Dex。不要陷在一堆安全校验，apk 解压的代码中。
这个类叫做 DexPatchApplier, 在 tinker-commons 中。
patch 的相关代码如下：
@Test
public void testPatch() throws IOException {File oldFile = new File("Hello.dex");
File patchFile = new File("patch.dex");
File newFile = new File("new.dex");
DexPatchApplier dexPatchGenerator
= new DexPatchApplier(oldFile, patchFile);
dexPatchGenerator.executeAndSaveTo(newFile);
}可以看到和 diff 代码类似，下面看代码去。
public DexPatchApplier(File oldDexIn, File patchFileIn) throws IOException {this(new Dex(oldDexIn), new DexPatchFile(patchFileIn));
}oldDex 会转化为 Dex 对象，这个上面分析过，主要就是 readHeader 和 readMap. 注意我们的 patchFile 是转为一个 DexPatchFile 对象。
public DexPatchFile(File file) throws IOException {this.buffer = new DexDataBuffer(ByteBuffer.wrap(FileUtils.readFile(file)));
init();}首先将 patch file 读取为 byte[]，然后调用 init
private void init() {byte[] magic = this.buffer.readByteArray(MAGIC.length);
if (CompareUtils.uArrCompare(magic, MAGIC) != 0) {throw new IllegalStateException("bad dex patch file magic:" + Arrays.toString(magic));
}
this.version = this.buffer.readShort();
if (CompareUtils.uCompare(this.version, CURRENT_VERSION) != 0) {throw new IllegalStateException("bad dex patch file version:" + this.version + ", expected:" + CURRENT_VERSION);
}
this.patchedDexSize = this.buffer.readInt();
this.firstChunkOffset = this.buffer.readInt();
this.patchedStringIdSectionOffset = this.buffer.readInt();
this.patchedTypeIdSectionOffset = this.buffer.readInt();
this.patchedProtoIdSectionOffset = this.buffer.readInt();
this.patchedFieldIdSectionOffset = this.buffer.readInt();
this.patchedMethodIdSectionOffset = this.buffer.readInt();
this.patchedClassDefSectionOffset = this.buffer.readInt();
this.patchedMapListSectionOffset = this.buffer.readInt();
this.patchedTypeListSectionOffset = this.buffer.readInt();
this.patchedAnnotationSetRefListSectionOffset = this.buffer.readInt();
this.patchedAnnotationSetSectionOffset = this.buffer.readInt();
this.patchedClassDataSectionOffset = this.buffer.readInt();
this.patchedCodeSectionOffset = this.buffer.readInt();
this.patchedStringDataSectionOffset = this.buffer.readInt();
this.patchedDebugInfoSectionOffset = this.buffer.readInt();
this.patchedAnnotationSectionOffset = this.buffer.readInt();
this.patchedEncodedArraySectionOffset = this.buffer.readInt();
this.patchedAnnotationsDirectorySectionOffset = this.buffer.readInt();
this.oldDexSignature = this.buffer.readByteArray(SizeOf.SIGNATURE);
this.buffer.position(firstChunkOffset);
}还记得我们写 patch 的操作么，先写了 MAGIC 和 Version 用于校验该文件是一个 patch file；接下来为 patchedDexSize 和各种 offset 进行赋值；最后定位到数据区（firstChunkOffset），还记得写的时候，该字段在第四个位置。
定位到该位置后，后面读取的就是数据了，数据存的时候按照如下格式存储的：
- del 操作的个数，每个 del 的 index
- add 操作的个数，每个 add 的 index
- replace 操作的个数，每个需要 replace 的 index
- 最后依次写入 newItemList.
简单回忆下，我们继续源码分析。
public DexPatchApplier(File oldDexIn, File patchFileIn) throws IOException {this(new Dex(oldDexIn), new DexPatchFile(patchFileIn));
}
public DexPatchApplier(
Dex oldDexIn,
DexPatchFile patchFileIn) {
this.oldDex = oldDexIn;
this.patchFile = patchFileIn;
this.patchedDex = new Dex(patchFileIn.getPatchedDexSize());
this.oldToPatchedIndexMap = new SparseIndexMap();}除了 oldDex,patchFile, 还初始化了一个 patchedDex 作为我们最终输出 Dex 对象。
构造完成后，直接执行了 executeAndSaveTo 方法。
public void executeAndSaveTo(File file) throws IOException {
OutputStream os = null;
try {os = new BufferedOutputStream(new FileOutputStream(file));
executeAndSaveTo(os);
} finally {if (os != null) {
try {os.close();
} catch (Exception e) {// ignored.}
}
}
}直接到 executeAndSaveTo(os), 该方法代码比较长，我们分 3 段讲解：
public void executeAndSaveTo(OutputStream out) throws IOException {TableOfContents patchedToc = this.patchedDex.getTableOfContents();
patchedToc.header.off = 0;
patchedToc.header.size = 1;
patchedToc.mapList.size = 1;
patchedToc.stringIds.off
= this.patchFile.getPatchedStringIdSectionOffset();
patchedToc.typeIds.off
= this.patchFile.getPatchedTypeIdSectionOffset();
patchedToc.typeLists.off
= this.patchFile.getPatchedTypeListSectionOffset();
patchedToc.protoIds.off
= this.patchFile.getPatchedProtoIdSectionOffset();
patchedToc.fieldIds.off
= this.patchFile.getPatchedFieldIdSectionOffset();
patchedToc.methodIds.off
= this.patchFile.getPatchedMethodIdSectionOffset();
patchedToc.classDefs.off
= this.patchFile.getPatchedClassDefSectionOffset();
patchedToc.mapList.off
= this.patchFile.getPatchedMapListSectionOffset();
patchedToc.stringDatas.off
= this.patchFile.getPatchedStringDataSectionOffset();
patchedToc.annotations.off
= this.patchFile.getPatchedAnnotationSectionOffset();
patchedToc.annotationSets.off
= this.patchFile.getPatchedAnnotationSetSectionOffset();
patchedToc.annotationSetRefLists.off
= this.patchFile.getPatchedAnnotationSetRefListSectionOffset();
patchedToc.annotationsDirectories.off
= this.patchFile.getPatchedAnnotationsDirectorySectionOffset();
patchedToc.encodedArrays.off
= this.patchFile.getPatchedEncodedArraySectionOffset();
patchedToc.debugInfos.off
= this.patchFile.getPatchedDebugInfoSectionOffset();
patchedToc.codes.off
= this.patchFile.getPatchedCodeSectionOffset();
patchedToc.classDatas.off
= this.patchFile.getPatchedClassDataSectionOffset();
patchedToc.fileSize
= this.patchFile.getPatchedDexSize();
Arrays.sort(patchedToc.sections);
patchedToc.computeSizesFromOffsets();
// 未完待续...
}这里实际上，就是读取 patchFile 中记录的值给 patchedDex 的 TableOfContent 中各种 Section(大致对应 map list 中各个 map_list_item) 赋值。
接下来排序呢，设置 byteCount 等字段信息。
继续：
public void executeAndSaveTo(OutputStream out) throws IOException {
// 省略第一部分代码
// Secondly, run patch algorithms according to sections' dependencies.
this.stringDataSectionPatchAlg = new StringDataSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.typeIdSectionPatchAlg = new TypeIdSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.protoIdSectionPatchAlg = new ProtoIdSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.fieldIdSectionPatchAlg = new FieldIdSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.methodIdSectionPatchAlg = new MethodIdSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.classDefSectionPatchAlg = new ClassDefSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.typeListSectionPatchAlg = new TypeListSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.annotationSetRefListSectionPatchAlg = new AnnotationSetRefListSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.annotationSetSectionPatchAlg = new AnnotationSetSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.classDataSectionPatchAlg = new ClassDataSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.codeSectionPatchAlg = new CodeSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.debugInfoSectionPatchAlg = new DebugInfoItemSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.annotationSectionPatchAlg = new AnnotationSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.encodedArraySectionPatchAlg = new StaticValueSectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.annotationsDirectorySectionPatchAlg = new AnnotationsDirectorySectionPatchAlgorithm(patchFile, oldDex, patchedDex, oldToPatchedIndexMap);
this.stringDataSectionPatchAlg.execute();
this.typeIdSectionPatchAlg.execute();
this.typeListSectionPatchAlg.execute();
this.protoIdSectionPatchAlg.execute();
this.fieldIdSectionPatchAlg.execute();
this.methodIdSectionPatchAlg.execute();
this.annotationSectionPatchAlg.execute();
this.annotationSetSectionPatchAlg.execute();
this.annotationSetRefListSectionPatchAlg.execute();
this.annotationsDirectorySectionPatchAlg.execute();
this.debugInfoSectionPatchAlg.execute();
this.codeSectionPatchAlg.execute();
this.classDataSectionPatchAlg.execute();
this.encodedArraySectionPatchAlg.execute();
this.classDefSectionPatchAlg.execute();
// 未完待续...
}这一部分很明显初始化了一堆算法，然后分别去执行。我们依然是拿 stringDataSectionPatchAlg 来分析。
public void execute() {final int deletedItemCount = patchFile.getBuffer().readUleb128();
final int[] deletedIndices = readDeltaIndiciesOrOffsets(deletedItemCount);
final int addedItemCount = patchFile.getBuffer().readUleb128();
final int[] addedIndices = readDeltaIndiciesOrOffsets(addedItemCount);
final int replacedItemCount = patchFile.getBuffer().readUleb128();
final int[] replacedIndices = readDeltaIndiciesOrOffsets(replacedItemCount);
final TableOfContents.Section tocSec = getTocSection(this.oldDex);
Dex.Section oldSection = null;
int oldItemCount = 0;
if (tocSec.exists()) {oldSection = this.oldDex.openSection(tocSec);
oldItemCount = tocSec.size;
}
// Now rest data are added and replaced items arranged in the order of
// added indices and replaced indices.
doFullPatch(oldSection, oldItemCount, deletedIndices, addedIndices, replacedIndices);
}再贴一下我们写入时的规则：
看代码，读取顺序如下：
- del 的数量，del 的所有的 index 存储在一个 int[] 中；
- add 的数量，add 的所有的 index 存储在一个 int[] 中；
- replace 的数量，replace 的所有的 index 存储在一个 int[] 中；
是不是和写入时一致。
继续，接下来获取了 oldDex 中 oldItems 和 oldItemCount。
那么现在有了：
- del count and indices
- add count add indices
- replace count and indices
- oldItems and oldItemCount
拿着我们拥有的，继续执行 doFullPatch
private void doFullPatch(
Dex.Section oldSection,
int oldItemCount,
int[] deletedIndices,
int[] addedIndices,
int[] replacedIndices) {
int deletedItemCount = deletedIndices.length;
int addedItemCount = addedIndices.length;
int replacedItemCount = replacedIndices.length;
int newItemCount = oldItemCount + addedItemCount - deletedItemCount;
int deletedItemCounter = 0;
int addActionCursor = 0;
int replaceActionCursor = 0;
int oldIndex = 0;
int patchedIndex = 0;
while (oldIndex < oldItemCount || patchedIndex < newItemCount) {if (addActionCursor < addedItemCount && addedIndices[addActionCursor] == patchedIndex) {T addedItem = nextItem(patchFile.getBuffer());
int patchedOffset = writePatchedItem(addedItem);
++addActionCursor;
++patchedIndex;
} else
if (replaceActionCursor < replacedItemCount && replacedIndices[replaceActionCursor] == patchedIndex) {T replacedItem = nextItem(patchFile.getBuffer());
int patchedOffset = writePatchedItem(replacedItem);
++replaceActionCursor;
++patchedIndex;
} else
if (Arrays.binarySearch(deletedIndices, oldIndex) >= 0) {T skippedOldItem = nextItem(oldSection); // skip old item.
++oldIndex;
++deletedItemCounter;
} else
if (Arrays.binarySearch(replacedIndices, oldIndex) >= 0) {T skippedOldItem = nextItem(oldSection); // skip old item.
++oldIndex;
} else
if (oldIndex < oldItemCount) {T oldItem = adjustItem(this.oldToPatchedIndexMap, nextItem(oldSection));
int patchedOffset = writePatchedItem(oldItem);
++oldIndex;
++patchedIndex;
}
}
}先整体上看一下，这里的目的就是往 patchedDex 的 stringData 区写数据，写的数据理论上应该是：
- 新增的数据
- 替代的数据
- oldDex 中出去新增和被替代的数据
当然他们需要顺序写入。
所以看代码，首先计算出 newItemCount=oldItemCount + addCount – delCount，然后开始遍历，遍历条件为 0~oldItemCount 或 0~newItemCount。
我们期望的是，在 patchIndex 从 0~newItemCount 之间都会写入对应的 Item。
Item 写入通过代码我们可以看到：
- 首先判断该 patchIndex 是否包含在 addIndices 中，如果包含则写入；
- 再者判断是否在 repalceIndices 中，如果包含则写入；
- 然后判断如果发现 oldIndex 被 delete 或者 replace，直接跳过；
- 那么最后一个 index 指的就是，oldIndex 为非 delete 和 replace 的，也就是和 newDex 中 items 相同的部分。
上述 1.2.4 三个部分即可组成完整的 newDex 的该区域。
这样的话就完成了 stringData 区域的 patch 算法。
其他剩下的 14 个算法的 execute 代码是相同的（父类），执行的操作类似，都会完成各个部分的 patch 算法。
当所有的区域都完成恢复后，那么剩下的就是 header 和 mapList 了，所以回到所有算法执行完成的地方：
public void executeAndSaveTo(OutputStream out) throws IOException {
//1. 省略了 offset 的各种赋值
//2. 省略了各个部分的 patch 算法
// Thirdly, write header, mapList. Calculate and write patched dex's sign and checksum.
Dex.Section headerOut = this.patchedDex.openSection(patchedToc.header.off);
patchedToc.writeHeader(headerOut);
Dex.Section mapListOut = this.patchedDex.openSection(patchedToc.mapList.off);
patchedToc.writeMap(mapListOut);
this.patchedDex.writeHashes();
// Finally, write patched dex to file.
this.patchedDex.writeTo(out);
}定位到 header 区域，写 header 相关数据；定位到 map list 区域，编写 map list 相关数据。两者都完成的时候，需要编写 header 中比较特殊的两个字段：签名和 checkSum, 因为这两个字段是依赖 map list 的，所以必须在编写 map list 后。
这样就完成了完整的 dex 的恢复，最后将内存中的所有数据写到文件中。
刚才我们有个 Hello.dex，我们再编写一个类：
public class World{public static void main(String[] args){System.out.println("nani World");
}
}然后将这个类编译以及打成 dx 文件。
javac -source 1.7 -target 1.7 World.java
dx --dex --output=World.dex World.class这样我们就准备好了两个 dex，Hello.dex 和 World.dex.
使用 010 Editor 分别打开两个 dex，我们主要关注 string_id_item；
两边分别 13 个字符串，按照我们上面介绍的 diff 算法，我们可以得到以下操作：
两边的字符串分别开始遍历对比：
del 1
add 1 LWorld;
del 2
add 8 World.java
del 10
add 11 naniWorld然后是根据索引排序，没有变化；
接下来遍历所有的操作，将 index 一致且 DEL 和 ADD 相邻的操作替换为 replace
replace 1 LWorld
del 2
add 8 World.java
del 10
add 11 naniWorld最终在 write 时，会做一次遍历，将操作按 DEL,ADD,REPLACE 进行分类，并且将出现的 item 放置到 newItemList 中。
del ops:
del 2
del 10
add ops:
add 8
add 11
replace ops:
replace 1newItemList 变为：
LWorld //replace 1
World.java //add 8
naniWorld //add 11然后写入，那么写入的顺序应该是：
2 //del size
2
8 // index - lastIndex
2 // add size
8
3 // index - lastIndex
1 //replace size
1
LWorld
World.java
naniWorld这里我们直接在 DexPatchGenerator 的 writeResultToStream 的相关位置打上日志：
buffer.writeUleb128(delOpIndexList.size());
System.out.println("del size =" + delOpIndexList.size());
int lastIndex = 0;
for (Integer index : delOpIndexList) {buffer.writeSleb128(index - lastIndex);
System.out.println("del index =" + (index - lastIndex));
lastIndex = index;
}
buffer.writeUleb128(addOpIndexList.size());
System.out.println("add size =" + addOpIndexList.size());
lastIndex = 0;
for (Integer index : addOpIndexList) {buffer.writeSleb128(index - lastIndex);
System.out.println("add index =" + (index - lastIndex));
lastIndex = index;
}
buffer.writeUleb128(replaceOpIndexList.size());
System.out.println("replace size =" + addOpIndexList.size());
lastIndex = 0;
for (Integer index : replaceOpIndexList) {buffer.writeSleb128(index - lastIndex);
System.out.println("replace index =" + (index - lastIndex));
lastIndex = index;
}
for (T newItem : newItemList) {if (newItem instanceof StringData) {buffer.writeStringData((StringData) newItem);
System.out.println("stringdata =" + ((StringData) newItem).value);
}
}可以看到输出为：
del size = 2
del index = 2
del index = 8
add size = 2
add index = 8
add index = 3
replace size = 2
replace index = 1
stringdata = LWorld;
stringdata = World.java
stringdata = nani World与我们上述分析结果一致 ~~
那么其他区域可以用类似的方式去验证，patch 的话也差不多，就不赘述了。
