DexDiff：基于dex文件反编译生成dex增量包

前段时间微信分享了一篇文章——微信Android热补丁实践演进之路, 这篇文章主要讲了目前流行的Android热修复方案，同时微信在QZone方案的基础上优化出一套dex全量替换的热修复方案（Tinker）。个人认为微信的这套方案尽管规避掉了Qzone方案中插桩导致的问题，但是由于需要在运行时加载全量的dex，这可能会在运行时内存占用上有一定的影响，目前这个仅仅是猜测，有待调研。

GitHub上已有Tinker方案仿版——Tinker_imitator，但带有个人感情色彩且不负责任地说，这套方案基本是堆砌各项技术然后封装成套装，应该属于比较糙的仿版，方案在生成差分dex的时候采用的是现成的bsdiff算法，这个通用的二进制差分算法很牛逼，但由于不能很好的利用dex本身的结构，因此会导致可能仅仅添加一句代码也需要下发不小的增量包（参考chrome增量更新小胡瓜中的见解），相对于微信文章中提到的自研DexDiff算法来说，这个就相对弱一点了。

这么一大段背景介绍，我想表达的是我认为微信这篇文章对我而言最关键的价值在于DexDiff的概念，看完这篇文章之后，我去学习了bsdiff算法，学习完发现bsdiff算法用于apk的增量更新或许不错，但是用来做dex的增量包的确是少了许多对dex进行量身定制的优势，于是我尝试去思考如何根据dex的数据格式来实现DexDiff，本文主要分享我的一些思路，希望起到抛砖引玉的作用。

dex文件格式

dex文件是运行在Dalvik中的字节码文件，类似于运行于JVM中的class文件，熟悉class文件格式的同学应该很容易理解，dex文件的布局可以用下图来进行说明：

dex文件布局

如果想更细致地了解dex文件中每部分数据的具体格式以及意义，请移步至官方文档Dalvik Executable format，建议可以使用010 Editor学习dex文件，当打开dex文件时该编辑器会自动推荐安装解析dex文件的插件，安装完插件便能与dex文件愉快地玩耍了。

反编译dex文件

了解了dex文件的基本格式之后，就可以开始dex文件的反编译之旅了，Android反编译套装（apktool、smail、dex2jar、jd-gui）现在基本是居家必备了，而今天要出场的大牌就是dex2jar（~~Orz），dex2jar采用了跟asm一样的套路，摇身一变便成了解析和生成dex文件的神器，建议没看过asm源码的Android开发小伙伴，可以直接撸一把dex2jar的源码，相信会有不少收获，至少对了解dex文件的内部数据格式来讲，会得到量与质的提升。源码都亮出来了，似乎没必要在解释下去了，但是为了能够圆润地过渡，我决定还是说明下dex2jar解析完dex文件后的数据结构：

dex2jar解析完dex文件后的数据结构

dex2jar实际上是依据Java中Class的属性来设计数据结构的，自上而下，一目了然。同时，数据结构中的各项数据都能在dex文件找到对应的数据块：比如className对应于dex文件格式中的type_id_item，而type_id_item指向的是string_id_item，通过string_id_item中的偏移便可以定位到data section中相应的string_data_item，从而解析出类字符串；再比如annotations对应于dex中的annotation_set_item，而annotation_set_item包含多个annotation_item，每一个annotation_item都可以通过其encoded_annotation解析出对应的type_id_item以及包含的key-value对，从而可以得到修饰类、字段或方法的注解数据。如果想要更全面更细致地了解如何解析dex文件得到上述数据结构集，请撸dex2jar。

dex文件的差分与合成

前奏终于结束了，可以开始正题了，不过不要担心，因为正二八经的内容会比你想象的少很多。DexDiff的目的在于对比新旧dex生成补丁数据，然后利用补丁数据和旧dex合成新dex，目前DexDiff的实现中，我的思路是这样的：

1. 基于dex2jar库反编译新旧dex
2. 逐个对比新旧dex中的class：
   • 若class仅存在于旧dex，保存旧dex中的class至deleteClasses
   • 若class仅存在于新dex，保存新dex中的class至replaceClasses
   • 若class存在于新旧dex，但class数据不一致，保存新dex中的class至replaceClasses
3. 编译得到的replaceClasses得到replace.dex
4. 记录deleteClasses中类的标识字符串得到delete.data
5. 根据replace.dex、delete.data以及旧dex便可以使用dex2jar编译得到新dex

其中对比新旧dex中两个对应的class以确定其是否一致时，采用的方式是逐个对比class中的属性（accessFlags，superClass，interfaces，fields，methods等），若有一项属性不一致则定义该class为需要用新dex中数据替换旧dex中对应数据。通过这样的方式可以实现class粒度上的dex差分，这样程度的差分可以应用于生成QZone方案中的热修复补丁包了，如果做增量更新的话，class粒度下的增量包大小也是可以接受的。实现DexDiff的思路就是这么简单粗暴，但是在实现的过程中还是也还是一波三折，尤其是在比较method中的指令部分时遇到了不少坑，项目源码已经上传至GitHub DexDiff。

优化思路

目前版本中做差分的粒度是class，但是实际上同样的思路可以实现method粒度以及instruction粒度的差分。方法级别的差分做法应该可以完全照搬class级别的差分做法；而instruction粒度的差分需要做适当的调整和改进，因为instruction级别不能像class或method一样可以直接整个替换，我们需要对比指令的语义，并且记录指令的删除或插入位置偏移，初步的想法是可以设计自己的数据格式来存储这些指令差异，但这在我估计总体的实现难度跟class粒度方案比应该不在一个量级，并且应用instruction粒度方案时的整体的稳定性、兼容性等都将是较大的挑战，单从技术上来讲还是值得试的，如果后续完成实践再分享。

GitHub

DexDiff：求围观^_