今天介绍常用的三种差分算法,分别是Xdelta3 bsdiff Courgette。

Xdelta3

官网地址: http://xdelta.org

源码地址:https://github.com/jmacd/xdelta

xdelta是delta编码的命令行程序,它生成两个文件之间的差异。 这与diff和patch类似,但它针对二进制文件 ,不会生成人类可读的输出。

它于1997年首次发布。xdelta的开发人员是Joshua MacDonald,该程序目前由他维护。 xdelta1算法基于rsync算法,由Andrew Tridgell开发,使用比rsync更小的块大小。

xdelta3可以生成标准化的VCDIFF格式,实现了支持VCDIFF格式的其他delta编码软件的兼容性。 它运行在类Unix操作系统和Microsoft Windows上 。 xdelta最多可处理2^64字节文件,适用于大型备份。

下面关于VCDIFF算法的介绍摘自网络:原文

Vcdiff可以实现文件的差分并压缩的功能,当原文件为空时,则相当于对新的文件直接压缩。Vcdiff采用差分文件包含:ADD、COPY、RUN[、NOOP(空)]等操作方式。生成差分文件前,需要首先进行Vcdiff decoding,具体采用128进制来重新编码,带来的好处:一是在不同的系统中统一采用8比特的字节编码方式,二是对于小数字则可以节省存储空间;在RF3284给出的示例将123456789,经过编码后表示为MSB+58,MSB+111,MSB+26,0+21,二进制值为10111010 11101111 10011010 0010101,最高位MSB用来表示数据是否完成,1时表示下个字节仍属于同一数据块,即123456789 = 128(128(58 * 128 + 111) + 26) + 21。编码完成后的文件生成差分格式包,也可进行压缩后再进行传输。差分包执行过程示例如下,旧的文件内容为a b c d e f g h i j k l m n o p,差分包包含指令COPY 4, 0;ADD 4, w x y z;COPY 4, 4;COPY 12, 24;RUN 4, z COPY指令带有两个参数,第一个为长度,第二个为地址;ADD指令带有长度和,相应插入的符号信息;RUN指令将某字符重复多次。

在生成差分文件时需要进行字符串比较,有后缀树及hash等方式,Vdelta中使用快速字符串比较算法(a fast string matching algorithm 可以使用相对其他算法较少的内存空间,hash表索引)。Vdelta的过程就是压缩的过程,生成差分包的过程,可以理解为原始包和新的包级联,然后进行压缩,只输出新包部分的信息即为差分包。理解生成差分包过程如下,采用最低3个字节匹配(需要使用合适前缀匹配,简单理解当匹配字符串太长时,匹配成功可能性低,较短如一个字符比较时,索引开销可能比存储Index还大)。

虽然Vcdiff本身压缩能够覆盖大部分使用,在Vcdiff中还支持二次压缩以达到更好的效果,也就是对生成的信息再一次压缩,压缩方式可以在文件头信息中携带。另外在考虑资源消耗方面,Vcdiff支持分成多块(window),这样可以减少过程中内存等资源的需求,Vcdiff差分包格式主要信息格式Header Info+Window1 Info + Window2…。

bsdiff

官网地址:http://www.daemonology.net/bsdiff/

源码地址:http://www.daemonology.net/bsdiff/bsdiff-4.3.tar.gz

官网描述:

bsdiff routinely produces binary patches 50-80% smaller than those produced by Xdelta, and 15% smaller than those produced by .RTPatch (a $2750/seat commercial patch tool).

bsdiff通常生成的二进制补丁比Xdelta生成的补丁少50-80%,比.RTPatch生成的二进制补丁小15%(2750 美元/套 的商业补丁工具)

下面关于bsdiff算法的介绍摘自网络:原文

Bsdiff采用差分文件信息包含三个部分:
一是ADD和INSERT的控制信息;一部分是包含概率匹配中不同字节差异文件(difference);最后一部分是不属于概率匹配内容的额外信息(extra文件)。Bsdiff算法使用的的前提条件,一是文件直接修改引起的变化相当稀疏,二是数据和代码倾向于成块进行移动,导致大部分不同地址调整了相同的大小。ADD指令操作对象包含源文件中信息的偏移、长度以及需要添加的值;INSERT包含需要添加的长度以及需要添加的信息。区别于Vcdiff,Bsdiff只是差分文件生成的作用,而生成的文件并不会比源文件小,但其具有高度可压缩性,使得压缩后的差分文件比较小,参考文献中使用bzip2的压缩方法。生成差分包的时候,首先对旧文件进行后缀排序(使用faster string matching 算法),然后使用二分查找的方法将新文件中的字符串和旧文件字符串进行比较生成相应的diff文件。而差分包与旧有的文件生成新文件时会简单些,直接利用差分信息进行处理,无需排序等操作。
如下为排序过程,首先按照字符值直接排序,第一次排序完成后,13、6、5的字符顺序即可确定,由于这些字符唯一,而其他出现重叠的字符需要根据其后续字符再次排序,如index3的e和index12的e,需要使用其后续的第一个字符o和$比较再次排序,依次类推,直至将所有的元素排序完成。

字符串查找方式如下,采用二分法,示例需要找到”obeo”字符串,先找到I index为( 0 + 13 ) / 2的位置6,对应原来字符串的index 10进行字符串比较,obeo > obe$因此再到( 6 + 13 ) / 2的位置即index 9 对应元字符串的index 7,以此类推。通过字符串的查找和比较,从新文件头字符串开始,依次到旧文件排序信息中查找字符串位置进行对比,得到旧文件的位置和匹配长度信息等。

Bsdiff生成的差分包由几个部分组成,Header文件头、控制信息、diff部分的信息,其中头文件包含目标文件大小、控制信息长度等,以及extra部分信息。通过两种操作ADD、INSERT进行合并。控制信息用三元组表示,由add长度,insert长度以及从旧文件忽略长度三部分表示。

Courgette

官网地址:http://www.chromium.org

源码地址:https://chromium.googlesource.com/chromium/src/courgette/+/master/

git clone https://chromium.googlesource.com/chromium/src/courgette

效率对比

根据chromium官网的介绍,他们尝试了几种二进制差异算法,到目前为止一直使用bsdiff 。

我们是bsdiff的忠实拥趸——它比我们尝试过的其他任何东西都小而且工作得更好。
但是bsdiff仍然在制作比我们觉得有必要更大的差异。所以我们编写了一个新的差异算法,它更多地了解我们正在推进的数据类型——包含已编译可执行文件的大文件。

以下是chromium官方的差分效果对比,dev分支190.1-> 190.4更新的字节大小:

更新方式 文件大小
Full update 10,385,920
bsdiff update 704,512
Courgette update 78,848

原理分析

以下内容翻译自chromium官网,略有删改。而且因为翻译水平有限,错误在所难免,欢迎指正。

编译应用程序的问题是,即使是小的源代码更改也会导致字节级别更改数量不成比例。例如,添加几行代码时,需要进行范围检查以防止缓冲区溢出,随后的所有代码都会移动以便为新指令腾出空间。编译后的代码充满了内部引用,其中某些指令或数据包含另一条指令或数据的地址(或偏移量)。在几乎所有这些内部指针具有不同的值之前,它只需要进行一些源代码更改。

源代码没有这个问题,因为源代码中的所有实体都是符号的。在编译过程中,在汇编或链接过程中,函数不会被提交到特定的地址。如果我们可以稍微向后退一点,并再次使内部指针具有象征意义,我们是否可以获得更小的更新?

courgette使用原始反汇编器来查找内部指针。反汇编器将程序分成三部分:内部指针的目标地址列表,所有其他字节,以及一个’指令’序列,它决定了普通字节和指针如何交错和调整以获取原始输入。我们称之为“汇编语言”,因为我们可以运行“汇编程序”来处理指令并发出一系列字节来恢复原始文件。

非指针部分大约是原始程序大小的80%,并且由于它没有任何混合的指针,它往往表现良好,其差异大小与源代码中的更改一致。简单地将程序转换为汇编语言形式可以使bsdiff产生的差异缩小约30%。

我们通过引入地址的“标签”来控制指针。地址存储在一个数组中,指针列表被数组索引列表替换。 该数组是一个基本的“符号表”,符号名称或“标签”是数组中的整数索引。我们从符号表中得到的是我们表达程序的自由度。只要我们对索引列表进行相应的更改,我们就可以在数组中移动地址。

courgette与bsdiff流程对比

比如原始文件叫original,新的文件叫update。

bsdiff升级的方式:

server:
        diff = bsdiff(original, update)
        transmit diff

client:
        receive diff
        update = bspatch(original, diff)

服务器将使用bsdiff预先计算差异,然后将差分包直接传输,客户端再使用bspatch合成新的包,然后使用新的包升级。

courgette升级方式:

server:
    asm_old = disassemble(original)
    asm_new = disassemble(update)
    asm_new_adjusted = adjust(asm_new, asm_old)
    asm_diff = bsdiff(asm_old, asm_new_adjusted)
    transmit asm_diff

client:
    receive asm_diff
    asm_old = disassemble(original)
    asm_new_adjusted = bspatch(asm_old, asm_diff)
    update = assemble(asm_new_adjusted)
生成patch:

合成新文件:


Courgette将程序转换为原始汇编语言,并在汇编级别进行差异化处理。

其中最与众不同的地方是adjust步骤。Courgette移动asm_new符号表中的地址以最大限度地减小asm_diff的大小。两个符号表中的地址在它们的统计属性上匹配,这确保了索引列表具有许多长的公共子串。匹配不会根据周围的代码或调试信息使用任何启发式来对齐地址。

More than one executable, less than an executable

对于上面的工作,“汇编”和“反汇编”必须是严格反转,“original”和“update”必须是单一格式可执行文件。

如果“original”和“update”可以包含多个可执行文件以及大量非编译文件(如JavaScript和PNG图像),则它更加有用。

对于GoogleChrome,“original”和“update”是一个存档文件,其中包含安装和运行浏览器所需的所有文件。我们可以将差异更新视为一种预测,然后是一种猜谜游戏。在其最简单的形式(只是bsdiff/bspatch)中,客户端只有一个愚蠢的猜测,即“original”,所以服务器发送一个二进制比较来将“original”更正为所需的答案“update”。现在,如果服务器可以传递可用于产生更好猜测的提示,但我们不确定猜测是否会有用。我们可以通过将原始和猜测结合起来作为差异的基础来确保不会丢失信息:

server:
        hint = make_hint(original, update)
        guess = make_guess(original, hint)
        diff = bsdiff(concat(original, guess), update)
        transmit hint, diff

client
        receive hint, diff
        guess = make_guess(original, hint)
        update = bspatch(concat(original, guess), diff)

这个系统有一些有趣的属性。如果猜测是空字符串,那么我们与普通的bsdiff具有相同的差异。 如果猜测是完美的,差异将很小,只是一个复制猜测的指令。

在极端之间,猜测可能是“update”的完美子集。然后bsdiff会构造一个差异,主要是从完美预测和原始材料中构建更新。这就是Courgette如何处理包含可执行文件和其他文件的tar文件的输入。 提示是每个嵌入式可执行文件的位置以及asm_diff。

一旦我们有了这个预测/修正方案,我们就可以用它来减少客户需要完成的工作量。 可执行文件通常具有不包含内部指针的较大区域,如资源部分通常包含字符串表和各种可视元素(如图标和位图)。反汇编程序生成一个汇编语言程序,几乎可以说“这是一大块常量数据”,其中的数据与原始文件相同。 bsdiff然后为常量数据生成一个diff。 我们可以通过从反汇编中省略无指针区域并让最终差异来完成工作来获得基本相同的效果。

总结

Courgette将输入转换为一种比直接二进制比较更有效的形式(assemble),在变换后的空间进行差分压缩,并将变换反转以获得原始格式的补丁输出。

Xdelta3 bsdiff Courgette三种差分算法比较
Tagged on:             

One thought on “Xdelta3 bsdiff Courgette三种差分算法比较

发表评论

电子邮件地址不会被公开。 必填项已用*标注