OTA差分算法（bsdiff,hdiffpatch,xdelta3）和OTA升级update.zip介绍

1.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长度以及从旧文件忽略长度三部分表示。执行方式如下

如何安装还有使用命令的教程给列出来。

① 依赖的tar bsdiff-4.3.tar.gz    bzip2-1.0.6.tar.gz

     解压:    tar –zxvf bsdiff-4.3.tar.gz  

      解压:    tar –zxvf bzip2-1.0.6.tar.gz

      重命名:  mv bzip2-1.0.6.tar.gz  bzip2

      将bzip2文件夹移动到 /usr/local/include :   sudo  cp –r bzip2 /usr/local/include

② 依赖的源

       yum install bzip2-devel.x86_64 进行下载

③ 修改 bsdiff-4.3 文件夹里面的 bsdiff.c 和bspatch.c

在include 头里添加

#include &＃8220;bzip2/bzlib.c&＃8221;

#include &＃8220;bzip2/crctable.c&＃8221;

#include &＃8220;bzip2/compress.c&＃8221;

#include &＃8220;bzip2/decompress.c&＃8221;

#include &＃8220;bzip2/randtable.c&＃8221;

#include &＃8220;bzip2/blocksort.c&＃8221;

#include &＃8220;bzip2/huffman.c&＃8221;

修改Makefile

 在.ifndef和.endif 前面加一个 tab 空出距离，否则报错

如图:

④准备工作完成以后 进行编译 : make

⑤运行命令

两个绿色的就是编译出的命令行

 差分:  ./bsdiff  [oldfile] [newfile] [patchName]

 合成:  ./bspatch [oldfile] [newFileName] [patchName]

对比文件是否有差异: sha1sum  [fileName] 检验文件完整性和hash值。

2.hdiffpatch

① 需要用到的zip包:  HDiffPatch-master.zip , lz4-dev.zip, zstd-dev.zip, lzma-master.zip

②解压

   unzip HDiffPatch-master.zip

   unzip lz4-dev.zip

unzip zstd-dev.zip

unzip lzma-master.zip

③重命名

mv HDiffPatch-master  hdiffpatch

mv lz4-dev  lz4

mv zstd-dev  zstd

mv lzma-master  lzma

在/usr/local/include/bzip2 目录下 将 bzlib.h 复制到 /usr/local/include  

sudo   cp bzlib.h  ../

安装 zlib:  yum install -y zlib zlib-devel (如果是ubuntu的话 需要  apt-get install zlib1g zlib1g-dev)

④ 编译: make

成功结果:

2.1使用命令

执行命令的语法:

   拆分: ./hdiffz [oldFile] [newFile] [patchName]

   合成: ./hpatchz [oldFile] [patchName][oldFileName]

命令详解:

hdiffz [-m[-matchScore]|-s[-matchBlockSize]]  [-c-compressType[-compressLevel]] [-o] oldFile newFile outDiffFile

hpatchz  [-m|-s[-s-cacheSize]]  [-o] oldFile diffFile outNewFile

建议命令参数:

      hdiffz run by: -s-128 -c-bzip2-9 [oldFile] [newFile] [outDiffFile]
    hpatchz run by: -s-4m [oldFile] [diffFile] [outNewFile]
对比文件是否有差异: sha1sum  [fileName] 检验文件完整性和hash值。

2.2hdiffz 参数简介

-m matchScore使用matchScore将所有文件加载到内存中，默认是difffileSize 这种方式不推荐.

-s-matchBlockSize所有文件加载为流式处理，参数由matchBlockSize决定，参数设置例如 128 128K 128M

默认128，建议32 &＃8211; 16K 64K 1M等。

特殊选项：

C-压缩-压缩能级，设置差分文件的压缩类型和级别，默认不压缩；

支持压缩类型和级别：

（参考：HTTPS://Github. COM/SISON/LZTAMP/BROB/MARST/LZTAT17171SORTED.D）

       -zlib[-{1..9}]              DEFAULT level 9

        -bzip2[-{1..9}]             DEFAULT level 9
        -lzma[-{0..9}[-dictSize]]   DEFAULT level 7
            dictSize(==decompress stream size) can like 4096 or 4k or 4m or 128m etc&＃8230;, DEFAULT 4m
        -lz4                         no level
        -lz4hc[-{3..12}]            DEFAULT level 11
        -zstd[-{0..22}]             DEFAULT level 20

2.3hpatchz 参数简介

内存参数:

  -m  旧文件全部加载入内存

  -s-cacheSize  旧文件以流的方式加载。

  cacheSize can like 262144 or 256k or 512m or 2g etc&＃8230;, DEFAULT 128m

3.Xdelta3

依赖的包 xdelta-gpl-release3_1.zip
解压，unzip xdelta-gpl-release3_1.zip
cd   xdelta-gpl-release3_1/xdelta3

在当前文件夹执行命令:   ./run_release.sh

                                        autoscan .

                                        aclocal

                                        autoheader

                                        automake –add-missing

                                       ./configure

                                       make

3.1命令

执行命令的方法

拆分 :  ./xdelta3 -v -e -s [oldFile] [newFile] [patchName]

合成 :  ./xdelta3 -v -d -s [oldFile] [patchName] [newFileName]

对比文件是否有差异: sha1sum  [fileName]  检验文件完整性和hash值。

命令详细参数

用法: xdelta3 [命令/选项] [input [output]]

特殊命令名:

    config      输出 xdelta3 配置信息

    decode      解压缩 input

    encode      压缩 input

    test        运行内置的测试

为 VCDIFF 输入所用的特殊命令:

    printdelta  输出整个变化的信息

    printhdr    输出第一个窗口的信息

    printhdrs   输出所有窗口的信息

标准选项:

   -0 .. -9     压缩等级

   -c           使用 stdout

   -d           解压缩

   -e           压缩

   -f           强制覆盖

   -h           显示帮助

   -q           静默模式

   -v           使用详细信息(最大2)

   -V           显示版本

内存选项:

   -B bytes     源窗口大小

   -W bytes     输入窗口大小

压缩选项:

   -s source    如果存在，选择来源文件从哪儿复制

   -S [djw|fgk] 启用/弃用二级压缩

   -N           弃用小字符串匹配压缩

   -D           弃用外部解压缩 (压缩/解压缩)

   -R           弃用外部重压缩 (压缩)

   -n           弃用校验 (压缩/解压缩)

   -C           软配置 (压缩, 无文档的)

   -A [apphead] 弃用/提供程序头部 (压缩)

4.系统环境 系统:centos7

update.zip包整理
一、 update.zip包的目录结构
          |&＃8212;-boot.img
          |&＃8212;-system/
          |&＃8212;-recovery/
                `|&＃8212;-recovery-from-boot.p
                `|&＃8212;-etc/
                        `|&＃8212;-install-recovery.sh
          |&＃8212;META-INF/
              `|CERT.RSA
              `|CERT.SF
              `|MANIFEST.MF
              `|&＃8212;-com/
                     `|&＃8212;-google/
                             `|&＃8212;-android/
                                    `|&＃8212;-update-binary
                                    `|&＃8212;-updater-script
                             `|&＃8212;-android/
                                    `|&＃8212;-metadata
二、文件描述

boot.img 包含kernel和ramdisk，用来更新boot分区所需要的文件
system 内容升级后放在系统的system分区，主要更新一些apk和so库
recovery/目录中的recovery-from-boot.p是boot.img和recovery.img的补丁(patch),主要用来更新recovery分区，其中etc/目录下的install-recovery.sh是更新脚本
update-binary是一个二进制文件，相当于一个脚本解释器，能够识别updater-script中的描述的操作，该文件在具体的更新包中名字由源码中bootable/recovery/install.c中的
ASSUMED_UPDATE_BINARY_NAME的值而定
updater-script：此文件是一个脚本文件，具体描述更新过程，在之前可以根据具体情况编写该脚本适应我们的具体需求，该文件的命名由源码中的bootable/recovery/ 
updater/updater.c文件中的SCRIPT_NAME的值而定
metadata文件是描述设备信息及环境变量的元数据，主要包括一些编译选项，签名公钥，时间戳以及设别型号等
uesrdata目录，用来更新系统中的用户数据部分，这部分内容在更新后会存放在系统的data目录下，但是在Android M后data分区默认加密，在OTA的时候不能挂载data分
区，所以不能进行更新
在update.zip包生成后需要对其进行签名，否则在升级时会出现认证失败的错误提示。而且签名要使用和目标版本一致的加密公钥。加密公钥以及加密所需的三个文件在Android源码编译后生成的具体路径为：
out/host/linux-x86/framework/signapk.jar
build/target/product/security/testkey.x509.pem
build/target/product/security/testkey.pk8
具体的加密方法：$ java -jar out/host/linux-x86/framework/signapk.jar -w build/traget/product/security/tesetkey.x509.pem build/target/product/security/testkey.pk8 update.zip update_signed.zip
MANIFEST.MF :这个manifest文件定义了与包的组成结构相关的数据，类似Android应用的manifest.xml文件
CERT.RSA：与签名文件相关联的签名程序块文件，他存储了用于签名jar文件的公共签名
CERT.SF：这是jar文件的签名文件，其中前缀CERT代表签名者
在具体升级的时候，对update.zip包检查时大致会分成三步：1.检验SF文件与RSA文件是否匹配。2、检验MANIFEST.MF与签名文件中的digest是否一致。3.检验包中的文件与MANIFEST中所描述的是否一致。

三、Android升级包update.zip的生成过程分析（全部系统包）
使用make otapackage命令生成update.zip的过程分析。
在源码根目录下执行make otapackage命令生成update.zip包主要分为两步，

第一步是根据Makefile执行编译生成一个update原包（zip格式）。

第二步是运行一个python脚本，并以上一步准备的zip包作为输入，最终生成我们需要的升级包。

下面进一步分析这两个过程。（简单来说就是，首先生成cota包，在利用cota包生成差分包和整包）
            第一步：编译Makefile。对应的Makefile文件所在位置：build/core/Makefile。从该文件会生成一个zip包，这个包最后会用来制作OTA package 或者filesystem image。
根据Makefile可以分析这个包的生成过程：
            首先创建一个root_zip根目录，并依次在此目录下创建所需要的如下其他目录
            ①创建RECOVERY目录，并填充该目录的内容，包括kernel的镜像和recovery根文件系统的镜像。此目录最终用于生成recovery.img。
            ②创建并填充BOOT目录。包含kernel和cmdline以及pagesize大小等，该目录最终用来生成boot.img。
            ③向SYSTEM目录填充system image。
            ④向DATA填充data image。
            ⑤用于生成OTA package包所需要的额外的内容。主要包括一些bin命令。
            ⑥创建META目录并向该目录下添加一些文本文件，如apkcerts.txt(描述apk文件用到的认证证书)，misc_info.txt(描述Flash内存的块大小以及boot、recovery、system、userdata等分区的大小信息)。
            ⑦使用保留连接选项压缩我们在上面获得的root_zip目录。
            ⑧使用fs_config(build/tools/fs_config)配置上面的zip包内所有的系统文件(system/下各目录、文件)的权限属主等信息。fs_config包含了一个头文件#include“private/android_filesystem_config.h”。在这个头文件中以硬编码的方式设定了system目录下各文件的权限、属主。执行完配置后会将配置后的信息以文本方式输出 到META/filesystem_config.txt中。并再一次zip压缩成我们最终需要的原始包。

           第二步：上面的zip包只是一个编译过程中生成的原始包。这个原始zip包在实际的编译过程中有两个作用，一是用来生成OTA update升级包，二是用来生成系统镜像。在编译过程中若生成OTA update升级包时会调用（具体位置在Makefile的1037行到1058行）一个名为ota_from_target_files的Python脚本，位置在/build/tools/releasetools/ota_from_target_files。这个脚本的作用是以第一步生成的zip原始包作为输入，最终生成可用的OTA升级zip包。

./ota_from_target_files  -p . -s &＃8220;../../../../device/qcom/common&＃8221;, -t $1 -v -d MTD -v -i ./v1/targetfiles.zip  ./v2/targetfiles.zip update.zip
用法&＃8212;Usage: ota_from_target_files [flags] input_target_files output_ota_package
                        -b 过时的。
                        -k签名所使用的密钥
                        -i生成增量OTA包时使用此选项。后面我们会用到这个选项来生成OTA增量包。
                        -w是否清除userdata分区
                        -n在升级时是否不检查时间戳，缺省要检查，即缺省情况下只能基于旧版本升级。
                        -e是否有额外运行的脚本
                        -m执行过程中生成脚本(updater-script)所需要的格式,目前有两种即amend和edify。对应上两种版本升级时会采用不同的解释器。缺省会同时生成两种格式的脚 本。
                        -p定义脚本用到的一些可执行文件的路径。
                        -s定义额外运行脚本的路径。
                        -x定义额外运行的脚本可能用的键值对。
                        -v执行过程中打印出执行的命令。
                        -h命令帮助

下面我们分析ota_from_target_files这个python脚本是怎样生成最终zip包的。
                      主函数main是python的入口函数，我们从main函数开始看，大概看一下main函数（脚本最后）里的流程就能知道脚本的执行过程了。
                       ① 在main函数的开头，首先将用户设定的option选项存入OPTIONS变量中，它是一个python中的类。紧接着判断有没有额外的脚本，如果有就读入到OPTIONS变量中。
                       ② 解压缩输入的zip包，即我们在上文生成的原始zip包。然后判断是否用到device-specific extensions（设备扩展）如果用到，随即读入到OPTIONS变量中。
                       ③ 判断是否签名，然后判断是否有新内容的增量源，有的话就解压该增量源包放入一个临时变量中（source_zip）。自此，所有的准备工作已完毕，随即会调用该 脚本中最主要的函数WriteFullOTAPackage(input_zip,output_zip)
                       ④ WriteFullOTAPackage函数的处理过程是先获得脚本的生成器。默认格式是edify。然后获得metadata元数据，此数据来至于Android的一些环境变量。然后获得设备配置参数比如api函数的版本。然后判断是否忽略时间戳。
                       ⑤ WriteFullOTAPackage函数做完准备工作后就开始生成升级用的脚本文件(updater-script)了。生成脚本文件后将上一步获得的metadata元数据写入到输出包out_zip。
                       ⑥至此一个完整的update.zip升级包就生成了。将升级包拷贝到SD卡中就可以用来升级了。

四、 Android OTA增量包update.zip的生成
在上面的过程中生成的update.zip升级包是全部系统的升级包，而在实际升级中，我们只希望能够升级我们改变的那部分内容。这就需要使用增量包来升级。生成增量包的过程也需要上文中提到的ota_from_target_files.py的参与。
         下面是制作update.zip增量包的过程。
          ① 在源码根目录下依次执行下列命令
           $ . build/envsetup.sh
           $ lunch XXX
           $ make
           $ make otapackage
           执行上面的命令后会在out/target/product/tcc8800/下生成我们第一个系统升级包。我们先将其命名为A.zip
          ② 在源码中修改我们需要改变的部分，比如修改内核配置，增加新的驱动等等。修改后再一次执行上面的命令。就会生成第二个我们修改后生成的update.zip升级包。将其命名为B.zip。
          ③ 在上文中我们看了ota_from_target_files.py脚本的使用帮助，其中选项-i就是用来生成差分增量包的。使用方法是以上面的A.zip 和B.zip包作为输入，以update.zip包作为输出。生成的update.zip就是我们最后需要的增量包。
              具体使用方式是：将上述两个包拷贝到源码根目录下，然后执行下面的命令。
              $ ./build/tools/releasetools/ota_from_target_files -i A.zip B.zip update.zip。（还可以加入其他参数，例如-x，-k，-p等等）
              在执行上述命令时会出现未找到recovery_api_version的错误。原因是在执行上面的脚本时如果使用选项i则会调用WriteIncrementalOTAPackage会从A包和B包中的META目录下搜索misc_info.txt来读取recovery_api_version的值。但是在执行make  otapackage命令时生成的update.zip包中没有这个目录更没有这个文档。
              此时我们就需要使用执行make otapackage生成的原始的zip包。这个包的位置在out/target/product/XX/obj/PACKAGING/target_files_intermediates/目录下（cota包），它是在用命令make otapackage之后的中间生产物，是最原始的升级包。我们将两次编译的生成的包分别重命名为A.zip和B.zip，并拷贝到SD卡根目录下重复执行上面的命令：  $ ./build/tools/releasetools/ota_form_target_files -i A.zip B.zip update.zip。
           
另：生成差分包调用的是文件./build/tools/releasetools/ota_from_target_files中的WriteIncrementalOTA方法，调用时需要将两个版本的差分资源包作为参数传进来，形如：
./build/tools/releasetools/ota_from_target_files –n –i ota_v1.zip ota_v2.zip update.zip
其中，参数n表示忽略时间戳；i表示生成增量包（即差分包）；ota_v1.zip与ota_v2.zip分别代表前后两个版本的差分资源包；而update.zip则表示最终生成的差分包。
WriteIncrementalOTA函数会计算输入的两个差分资源包中版本的差异，并将其写入到差分包中；同时，将updater及生成脚本文件udpate-script添加到升级包中。