Xdelta3bsdiffCourgette三种差分算法⽐较 今天介绍常⽤的三种差分算法，分别是Xdelta3 bsdiff Courgette。
Xdelta3
官⽹地址：
源码地址：
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
官⽹地址：
源码地址：
官⽹描述：
bsdiff routinely produces binary patches 50-80% smaller than those produced by Xdelta, and 15% s
maller 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
官⽹地址：
源码地址：
git clone lesource/chromium/src/courgette
效率对⽐
根据chromium官⽹的介绍，他们尝试了⼏种⼆进制差异算法，到⽬前为⽌⼀直使⽤bsdiff 。
我们是bsdiff的忠实拥趸——它⽐我们尝试过的其他任何东西都⼩⽽且⼯作得更好。
但是bsdiff仍然在制作⽐我们觉得有必要更⼤的差异。所以我们编写了⼀个新的差异算法，它更多地了解我们正在推进的数据类型——包含已编译可执⾏⽂件的⼤⽂件。
以下是chromium官⽅的差分效果对⽐，dev分⽀190.1-> 190.4更新的字节⼤⼩：
更新⽅式⽂件⼤⼩
Full update10,385,920
bsdiff update704,512
Courgette update78,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具有相同的差异。 如果猜测是完美的，差异将很⼩，只是⼀个复制猜测的指令。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议