前端时间关注团队的增量更新功能，重点看了一下bdiff算法的部分，扒到了一篇bsdiff原始的论文，边阅读边翻译了一下，发出来方便大家。

可执行代码差分

Colin Percival

牛津大学计算实验室

摘要

严重安全缺陷越来越高频率的被发现，并且它们被开发利用的情况越来越迅速，这使得程序需要快速更新的情况比以往显得更加重要。虽然二进制文件的更新普遍比源代码文件更新要方便很多，但是始终贯穿可执行文件的指针问题是的要想产生非常紧致的补丁包比较困难。

与早期依赖了解一个特定程序可执行文件的内部结构的工作想对比，我们描述了一种能够对任何可执行文件产生生成具有竞争力的补丁包的方法。

1 前言

历史上，二进制补丁包使用复制和插入两种基本操作进行构建。使用字串匹配或者hash技术寻找新文件和旧文件中匹配的部分，这部分区域的数据将会被赋值，剩下的新增部分字节存储到补丁文件中，我们称之为插入。因此，采用了这种方式生成补丁包的方式可以称之为包含复制和插入两种指令的程序。

非常不幸的是，任何源代码文件的修改通常都会导致整个可执行文件的变化。增加或者删除代码或者数据的一小部分字节，通过调整跳过修改区域的相对分支的未知，将会改变代码段的相对位置；相似地任何位于修改部分后边的数据将会有一个不同的地址，这将导致整个文件的数据指针被改变。这将导致采用传统复制插入方法产生的补丁包的大小比必要的大小要大一些；一行源代码在一个500KB的可执行程序中可以产生50KB大小的补丁包。

一种解决该问题的办法依赖对于一种可执行文件内部结构了解的知识。如果在老的可执行文件中的一个指向A地址的指针在新的文件中指向了地址B，那么很可能指向地址A的其他指针发生了同样的变化。结果是，通过高效的分析整个文件记录这种替换的第一个实例，就能够预测将来的替换，这样就消除了记录他们的必要性。然而，任何使用这种方法的必要的分析工具都是完全的平台相关的。

2 BSDIFF

为了以一种便携的方式解决指针问题，我们做出了两个重要的观察结论。首先，在一个可执行文件中不被一个修改直接影响的那一部分，通常差异是相当稀疏的。不只是修改地址包括仅仅的是一个编译代码的一小部分，而且地址大部分仅仅改变了一个或者两个字节。其次，数据和代码倾向于成块的移动，结果导致大部分的不同地址调整了相同的大小。这两个观察结论得出一个重要的事实，那就是一个可执行程序的两个版本中相对于同一行代码的部分，彼此是一样的，这就导致字节差异是零，并且即便不是零，某一个值的数量也比其他多得多，总之，这样的字节差异字符串具有高度的可压缩特性。

我们现在以以下的方式构建二进制补丁包。首先，我们读取旧文件并且执行一些索引排序，这种排序可以基于hashing技术也可以基于后缀排序。接下来，使用这个索引，我们遍历新文件去发现和旧文件部分相同的区域集合。为了后续更加清楚的缘由，我们仅仅记录包括与前一个匹配至少有8个不同字节的前向延伸扩展的区域（例如，如果前一个匹配是new[x…x+k]=old[y…y+k]，我们要寻找一个新的匹配new[x’…x’+k]=old[y’…y’+k’]，并且在这个匹配中至少有8个不同的索引i，能够使得new[x’+i]!=old[x’+i+(y-x)]）。

传统的二进制补丁工具将会把这种完美匹配的集合转化到一个补丁文件中。相反的，我们通过在匹配对的两个方向延展从而生成成对的并集，这种延展要满足一下要求每一个向前延展的扩展后缀（和每一个向后延展的前缀）都至少匹配它自己50%的字节内容。这个大概的匹配将概略地相当于可执行代码来自于源代码中没有修改的区域部分，而新文件中不是大概配对的部分概略地相当于源代码文件中修改的代码行。这种延展配对的方法是为什么我们会忽略不必之前的配对好8个字节的方法。

补丁文件由三部分构成：第一是一个包含了ADD和INSERT指令的控制文件；第二是一个包含了概率匹配中不同字节内容的差异文件；第三是一个包含了不属于概略匹配中内容的额外的文件。每一个ADD指令指定了旧文件中的偏移位置和长度，从旧文件中读取相应数量的字节内容并且从差异文件中读取相同字节的内容添加进去。INSERT指令仅仅制定一个长度，用于从额外文件中读取指定数量的字节内容。同时可知这三个文件在一起的大小要稍微大于原始的目标文件，控制文件和差异文件是高度可压缩的；尤其是bzip2算法倾向于有显著的优异表现（大概是由于这两个文件高度结构化的天然属性）。

我们已经在一个名为BSDiff的工具中实现了这个方法。

3 性能

为了评估BSDiff在两个可执行文件版本之中应用的性能，我们使用了19对DEC UNIX ALPHA二进制的Exediff方法做对比，而Exediff方法是这个平台中被指定使用的方法。表1列出了这些升级对的新版本原始大小，新版本压缩后的大小，采用杰出的免费二进制补丁工具Xdelta生成的补丁大小，采用广泛使用的商用工具.RTPatch生成的补丁大小，Exediff生成的补丁大小以及使用BSDiff生成的补丁大小。为了对比的公平期间，我们所以用了bzip2压缩工具对Exediff补丁进行了压缩而没有使用gzip，因为bzip2的表现更加优秀。

 http://s15/mw690/001pV51vzy7a5fbnmPk1e&690

除了两个例外的情况，差异文件都是非常小的。Apache1.2.4升级到1.3.0的例子中，直接压缩新二进制文件的包比任何一种方法都要优一些。我们可以从结果中发现一个很明显的现象：XDelta生成了最大的补丁，ExeDiff生成了最小的补丁，而BSDiff和.RTPatch的结果是第二大和第二小。通过使用精确的数学方法考虑了原始文件的大小，我们发现bzip2有了2.8倍的压缩，XDelta是5.2倍的压缩，.RTPatch是10.2倍，Exediff是13.7倍，而BSDiff是11.6倍。排除了Apache1.2.4到1.3.0的情况（我们注意到这两个版本的代码有一多半的源代码不同，所以补丁包大一些也就不足为奇），XDelta是5.3倍的压缩，.RTPatch是11.6倍，Exediff是16.8倍，而BSDiff是13.0倍。

比上边的版本之间升级的考虑更加重要的是，就是安全更新。这在根本上是不一样的，源代码的修改通常是非常小的，经常是一行代码的修改量。我们以i386下的FreeBSD4.7 Release版本和4_7的一个安全分支做比较。总的来说，一共有97哥修改的二进制文件，大小是36397575字节，使用bzip2压缩可以压缩到13566233(2.7倍)，Xdelta可以产生3288540大小的补丁包（11倍），.RTPatch可以产生749710字节的补丁包(47.7)，而BSDiff可以产生621277字节的补丁包（58.3倍）。

4 结论

我们提出了一种用于在两个可执行程序版本之间产生补丁包的算法，它能够一致地产生比当前杰出的二进制补丁包工具生成的补丁还要小的补丁文件；当应用到安全更新上，生成的补丁包格外的紧致。

然而他的性能达不到平台相关的工具，我们相信BSDiff能够接近于非平台依赖工具的最好性能。

bsdiff is quite memory-hungry. It requires max(17*n,9*n+m)+O(1) bytes of memory, where n is the size of the old file and m is the size of the new file. bspatch requires n+m+O(1) bytes.

bsdiff runs in O((n+m) log n) time; on a 200MHz Pentium Pro, building a binary patch for a 4MB file takes about 90 seconds. bspatch runs in O(n+m) time; on the same machine, applying that patch takes about two seconds.