Chrome的新differential压缩算法 - Courgette
meta
Chromium Blog上提到的Google Chrome用于推送升级包的新的二进制differential 压缩算法Courgette.
文中举了一个Develper Channel从190.1到190.4的升级例子:
- 完整升级包：10,385,920字节
- 一般bsdiff算法：704,512字节
- Courgette算法：78,848字节
Linker
On 7/16/09, meta <carma...@gmail.com> wrote:
> <http://dev.chromium.org/developers/design-documents/software-updates-courgette>Chromium
> Blog
> <http://blog.chromium.org/2009/07/smaller-is-faster-and-safer-too.html>上提到的Google
> Chrome用于推送升级包的新的二进制differential
> 压缩算法Courgette<http://dev.chromium.org/developers/design-documents/software-updates-courgette>
> .
> 文中举了一个Develper Channel从190.1到190.4的升级例子:
>
> - 完整升级包：10,385,920字节
> - 一般bsdiff算法：704,512字节
> -
> Courgette<http://dev.chromium.org/developers/design-documents/software-updates-courgette>
> 算法：78,848字节
>
> 很可怕的压缩率. 然后去看了看design
> document<http://dev.chromium.org/developers/design-documents/software-updates-courgette>,
> 其中心思想和我们平时写代码所提倡的不要使用"magic number"有异曲同工之妙: 可以避免对源文件的大量重复修改.
> 这里是用一个disassembler
> 来将二进制文件中所有的internal pointer/reference的地址重新符号化, 然后再计算differential.
> patch文件到客户端进行re-link, 从而恢复成最新文件.
>
--
Sent from my mobile device
Regards,
Linker Lin
linker...@gmail.com
SevenCat
On 7月17日, 上午12时37分, Linker <linker.m....@gmail.com> wrote:
> 不明白. 难道和完整比得到不同的文件？
>
> On 7/16/09, meta <carmack....@gmail.com> wrote:
>
>
>
> > <http://dev.chromium.org/developers/design-documents/software-updates-...>Chromium
> > Blog
> > <http://blog.chromium.org/2009/07/smaller-is-faster-and-safer-too.html>上提到的Google
> > Chrome用于推送升级包的新的二进制differential
> > 压缩算法Courgette<http://dev.chromium.org/developers/design-documents/software-updates-...>
> > .
> > 文中举了一个Develper Channel从190.1到190.4的升级例子:
>
> > - 完整升级包：10,385,920字节
> > - 一般bsdiff算法：704,512字节
> > -
> > Courgette<http://dev.chromium.org/developers/design-documents/software-updates-...>
> > 算法：78,848字节
>
> > 很可怕的压缩率. 然后去看了看design
> > document<http://dev.chromium.org/developers/design-documents/software-updates-...>,
> > 其中心思想和我们平时写代码所提倡的不要使用"magic number"有异曲同工之妙: 可以避免对源文件的大量重复修改.
> > 这里是用一个disassembler
> > 来将二进制文件中所有的internal pointer/reference的地址重新符号化, 然后再计算differential.
> > patch文件到客户端进行re-link, 从而恢复成最新文件.
>
> --
> Sent from my mobile device
>
> Regards,
> Linker Lin
Sisong Hou
我的算法有个简单的证明，在某个假设的框架下我的算法生成的是最优的补丁；
<一个高效的二进制数据补丁算法> : http://blog.csdn.net/housisong/archive/2006/04/11/658863.aspx
2009/7/17 SevenCat <BastE...@gmail.com>:
Mikster.Z
--
EX - EMBEDDED SYSTEM DEVELOPER
SOFTWARE ENGINEER
Name : Mikster
Corp: NokiaSiemensNetwork
DaiZW
server:
asm_old = disassemble(original) // 把老文件Fo在 assembly
level上分解为pointer/reference和代码段/数据段的集合A
asm_new = disassemble(update) // 把新文件Fn在 assembly
level上分解为pointer/reference和代码段/数据段的集合B
asm_new_adjusted = adjust(asm_new, asm_old) //
按照A中pointer/reference的地址, 修改B中pointer/reference的地址,
得到调整后的集合C(这种调整应该不影响C的功能, 就是说把C组合为文件后和Fn的功能等价)
asm_diff = bsdiff(asm_old, asm_new_adjusted) // diff C 和 B
transmit asm_diff
client:
receive asm_diff
asm_old = disassemble(original)
asm_new_adjusted = bspatch(asm_old, asm_diff)
update = assemble(asm_new_adjusted)
之所以需要按A来调整B是因为调整之后可以更接近A, 从而得到更小的diff文件; 也就是说从功能上讲"调整"这步不是必须的.
2009/7/16 meta <carma...@gmail.com>:
Wei Hu
On Jul 16, 10:42 am, meta <carmack....@gmail.com> wrote:
> <http://dev.chromium.org/developers/design-documents/software-updates-...>Chromium
> Blog <http://blog.chromium.org/2009/07/smaller-is-faster-and-safer-too.html>上提到的Google
> Chrome用于推送升级包的新的二进制differential
> 压缩算法Courgette<http://dev.chromium.org/developers/design-documents/software-updates-...>
> .
> 文中举了一个Develper Channel从190.1到190.4的升级例子:
>
> - 完整升级包：10,385,920字节
> - 一般bsdiff算法：704,512字节
> - Courgette<http://dev.chromium.org/developers/design-documents/software-updates-...>
> 算法：78,848字节
>
> 很可怕的压缩率. 然后去看了看design
> document<http://dev.chromium.org/developers/design-documents/software-updates-...>,
est
然后再patch比较旧版本，得到Courgette。。。貌似是这样的。。。。
这种一个很明显的优势就是在PE结构基础上再运算，比直接比较exe二进制效率肯定高多了。。。
On Jul 17, 7:44 am, Sisong Hou <housis...@gmail.com> wrote:
> 几年前我也写过一个patch算法，不知道谁的更好：） (英文太差，看不懂他的)
> 我的算法有个简单的证明，在某个假设的框架下我的算法生成的是最优的补丁；
> <一个高效的二进制数据补丁算法> :http://blog.csdn.net/housisong/archive/2006/04/11/658863.aspx
>
> 2009/7/17 SevenCat <BastEt.W...@gmail.com>:
tangl_99
它的意思就是计算一个字符串通过"替换，移动，删除，增加"这一系列操作最后变成另外一个字符串的最小步数。通过一个典型的动态规划的算法可以求解得
到。
On Jul 16, 10:42 pm, meta <carmack....@gmail.com> wrote:
> <http://dev.chromium.org/developers/design-documents/software-updates-...>Chromium
> Blog <http://blog.chromium.org/2009/07/smaller-is-faster-and-safer-too.html>上提到的Google
> Chrome用于推送升级包的新的二进制differential
> 压缩算法Courgette<http://dev.chromium.org/developers/design-documents/software-updates-...>
> .
> 文中举了一个Develper Channel从190.1到190.4的升级例子:
>
> - 完整升级包：10,385,920字节
> - 一般bsdiff算法：704,512字节
> - Courgette<http://dev.chromium.org/developers/design-documents/software-updates-...>
> 算法：78,848字节
>
> 很可怕的压缩率. 然后去看了看design
> document<http://dev.chromium.org/developers/design-documents/software-updates-...>,
nleven
不同单独搞出来处理。然后disassembler去搞定真正代码不同的变化。
On 7月16日, 下午10时42分, meta <carmack....@gmail.com> wrote:
> <http://dev.chromium.org/developers/design-documents/software-updates-...>Chromium
> Blog <http://blog.chromium.org/2009/07/smaller-is-faster-and-safer-too.html>上提到的Google
> Chrome用于推送升级包的新的二进制differential
> 压缩算法Courgette<http://dev.chromium.org/developers/design-documents/software-updates-...>
> .
> 文中举了一个Develper Channel从190.1到190.4的升级例子:
>
> - 完整升级包：10,385,920字节
> - 一般bsdiff算法：704,512字节
> - Courgette<http://dev.chromium.org/developers/design-documents/software-updates-...>
> 算法：78,848字节
>
> 很可怕的压缩率. 然后去看了看design
> document<http://dev.chromium.org/developers/design-documents/software-updates-...>,
raymond
Flier Lu
1. 把可执行文件看作多个代码流单独进行比较，而不是整文件粒度比较；这样整体结构上的变化不会对单个代码流产生影响，类似的思路可以用在其他的结构
化文件中，例如zip或com结构化文件等等
2. 通过代码分析，把可能relocate的符号抽取出来单独处理；因为这些部分在每次编译时都有可能不同，但对整体代码流影响不大。说白了就是把变
化和不变的分离考虑，减少冗余的比较。
3. 结合反汇编代码流和编译后符号和整体文件分析，而不是只在某个层面比较；实际上这个思路在很多新兴项目里面都有应用，例如LLVM将整个程序生命
期都作为优化的不同阶段，而非传统的编译阶段。
之前也写过一些类似的代码，例如代码流一级的比较之类，但没有他怎么彻底和全面，还是水平有差距啊 :(