Android - JNI移植 bspatch 实现增量更新功能

增量更新技术源于 Android 4.1 Google Play 引入的一项技术,以实现apk升级节约2/3的流量。Google 把这个功能叫做 Smart App Updates

增量更新的原理:就是将手机上已安装apk与服务器端最新apk进行二进制对比,得到差分包,用户更新程序时,只需要下载差分包,并在本地使用差分包与已安装apk,合成新版apk。

现在这个功能基本上是所有应用市场必备功能了,在这里我们抛开服务器更新流程,只谈 差分合并 的功能应该如何实现?

bsdiff and bspatch

bsdiffbspatch 是一个创建和应用补丁到二进制文件的工具。

bsdiff:用于拆分
bapatch:用于合并

在 Ubuntu 和 Mac 上这两个工具都可以在包管理中安装。

Ubuntu:

1
2
sudo apt-get install bsdiff
sudo apt-get install bspatch

Mac:

1
2
brew install bsdiff
brew install bspatch

当然我们也需要源码,因为最终合并的操作是在客户端完成的:http://www.daemonology.net/bsdiff/

bsdiff 用到了 bzip2 这个库:http://www.bzip.org/downloads.html

初体验

在电脑上安装了 bsdiffbspatch,可以立马来体验一下,因为这个工具是基于二进制的,所以根本不挑文件格式,我这里直接拿我本机的两张图片来测试,且这两张图是毫无关系的两张。

两个工具的参数都是:old file,new file,patch file。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
test tree
.
├── image1.png
└── image2.png
# 差分生成补丁文件:image1-image2.p
test bsdiff image1.png image2.png image1-image2.p
test tree
.
├── image1-image2.p
├── image1.png
└── image2.png
# 合并补丁 生成 image2-new.png
test bspatch image1.png image2-new.png image1-image2.p
test tree
.
├── image1-image2.p
├── image1.png
├── image2-new.png
└── image2.png

这个时候我们检查一下 image2.pngimage2-new.png 的 MD5 值。

1
2
3
4
5
test md5 image2.png
MD5 (image2.png) = 04cb578da2c3eb671c1bb08a813d4fac
test md5 image2-new.png
MD5 (image2-new.png) = 04cb578da2c3eb671c1bb08a813d4fac

很神奇吧,两个文件MD5一模一样,说明就是同一个文件,这就是增量更新实现方案,站在巨人的肩膀上很轻松就实现了。

移植 Android

其实就把 bsdiffbzlib2 两个库用 ndk 编译,然后 jni 调用即可。

新建一个C项目

具体参见官方文档:向您的项目添加 C 和 C++ 代码

拷贝 bsdiff 和 bzip2 库

将相关库文件拷贝至 cpp 目录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
➜ cpp git:(master) ✗ tree -L 2
.
├── bsdiff
│   ├── bsdiff.c
│   └── bspatch.c
├── bzip2
│   ├── blocksort.c
│   ├── bzlib.c
│   ├── bzlib.h
│   ├── bzlib_private.h
│   ├── compress.c
│   ├── crctable.c
│   ├── decompress.c
│   ├── huffman.c
│   └── randtable.c

编写 jni

jni基础相关内容参见之前的文章:Java-写给Android应用开发者的JNI快速入门指北

我们这里通过直接调用 bspatch main 函数的方式来实现合并查分包的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include "cn_quickits_patch_library_BsPatch.h"
#include <android/log.h>
#include "bzip2/blocksort.c"
#include "bzip2/bzlib.c"
#include "bzip2/compress.c"
#include "bzip2/crctable.c"
#include "bzip2/decompress.c"
#include "bzip2/huffman.c"
#include "bzip2/randtable.c"
#include "bsdiff/bspatch.c"
#define LOG_TAG "QPatch"
#define LOGD(...) __android_log_print(ANDROID_LOG_DEBUG,LOG_TAG,__VA_ARGS__)
JNIEXPORT void JNICALL Java_cn_quickits_patch_library_BsPatch_bspatch
(JNIEnv *env, jclass clz, jstring oldFile, jstring newFile, jstring patchFile) {
int argc = 4;
char *oldfile = (char *) (*env)->GetStringUTFChars(env, oldFile, NULL);
char *newfile = (char *) (*env)->GetStringUTFChars(env, newFile, NULL);
char *patchfile = (char *) (*env)->GetStringUTFChars(env, patchFile, NULL);
char *argv[4];
argv[0] = "bspatch";
argv[1] = oldfile;
argv[2] = newfile;
argv[3] = patchfile;
bspatch_main(argc, argv);
(*env)->ReleaseStringUTFChars(env, oldFile, oldfile);
(*env)->ReleaseStringUTFChars(env, newFile, newfile);
(*env)->ReleaseStringUTFChars(env, patchFile, patchfile);
LOGD("%s", "finish");
}

java 调用

1
QPatch.patch(oldFile, newFile, patchFile);

源码

https://github.com/gavinliu/QPatch

算法原理

尽可能多的利用old文件中已有的内容,尽可能少的加入新的内容来构建new文件,通常的做法是对old文件和new文件做子字符串匹配或使用hash技术,提取公共部分,将new文件中剩余的部分打包成patch包,在Patch阶段中,用copy和insert两个基本操作即可将old文件和patch包合成new文件。

  1. 对文件中所有字符串形成一个字典;
  2. 对比两个文件,产生 不同部分新增部分
  3. 不同部分新增部分 以及相应的控制字用 zip 压缩成一个 patch 包。

参考:BSDiff算法学习笔记

更多资料

由于 bsdiff 效率不是很高,于是乎出现了下面两种方案,由于篇幅原因就不做介绍了。

Gavin Liu wechat
欢迎您扫一扫上面的二维码,订阅我的微信公众号!