はじめに

以前にudm差分ファイル作成ツールを使った自動アップデート機能の作り方という記事で、
「udm差分ファイル作成ツール」を紹介しましたが、
このツールはプロプライエタリであり、また最新のWindowsをサポートできていないという問題があります。
将来的に使っていけるようにbsdiff/bspatchを使ったパッチツールを自作してみようかなと思い、
調査内容を何回かにわけてまとめていきます。

最終的なゴール

ディレクトリの差分を適用する自己解凍方式のパッチを作る(udm差分ファイル作成ツールの代替）
圧縮効率の高いbsdiff/bspatchを流用する
Windows対応

今回はbsdiff/bspatchに関する調査内容を記載します。

bsdiff/bspatchとは

bsdiff/bspatchはUNIXやLinuxで利用されているバイナリの差分作成ツールです。
この仕組みはどうやらGoogle Chromeのアップデートパッチでも利用されているようです。
（参考記事：Google Chromeアップデート高速化の秘密、bsdiffと逆アセンブラ | マイナビニュース）

コマンドラインでの使い方

bsdiffコマンドの使い方: UNIX/Linuxの部屋からの引用ですが、使い方は単純で下記のように実行すればよさそうです。

bsdiff はバイナリファイルのパッチ (差分ファイル) を生成する。
% bsdiff bin.old bin.new bin.bsdiff
⇒ bin.old と bin.new の差分を抽出し、パッチファイル bin.bsdiff を生成する。
生成したパッチをあてるには bspatch を使う。
% bspatch bin.old bin.new bin.bsdiff
⇒ bin.old にパッチファイル bin.bsdiff をあて、bin.new を生成する。

bsdiff/bspatchを実際に使ってみる

インストールと基本的な動作の確認

ためしに手持ちのMac(Mojave 10.14.5)にbsdiffをインストールして使ってみます。

# インストール
$ brew install bsdiff
==> Downloading https://homebrew.bintray.com/bottles/bsdiff-4.3.mojave.bottle.tar.gz
######################################################################## 100.0%
==> Pouring bsdiff-4.3.mojave.bottle.tar.gz
🍺  /usr/local/Cellar/bsdiff/4.3: 4 files, 21.5KB

# テストファイル作成
$ echo "version 1.00" > v1.dat
$ echo "version 2.00" > v2.dat

# パッチ作成
$ bsdiff v1.dat v2.dat patch_v1_to_v2

# 中身を覗いてみる。中身はバイナリデータ。
$ less patch_v1_to_v2
BSDIFF40+^@^@^@^@^@^@^@(^@^@^@^@^@^@^@^M^@^@^@^@^@^@^@BZh91AY&SY<B3>7-<87>^@^@^E<C0>@T
@^@ ^@!<80>^L^A<D6>M[qw$S<85>   ^K3r<D8>pBZh91AY&SoI}^@^@^B<C0>^@d^@ ^@0<CC>    4<CA>^Gaw$S<85> ^@<86><F4><97><D0>BZh9^WrE8P<90>^@^@^@^@
patch_v1_to_v2 (END)

# パッチ適用のために、v1.datをコピーしておく
$ cp v1.dat src.dat
# パッチ適用
$ bspatch src.dat dst.dat patch_v1_to_v2
# 確認
$ cat dst.dat
version 2.00

たしかに変わってますね。

コマンドライン引数を確認

bsdiff/bspatchのコマンドライン引数を見てみます。

$ bsdiff --help
bsdiff: usage: bsdiff oldfile newfile patchfile

$ man bsdiff
BSDIFF(1)                 BSD General Commands Manual                BSDIFF(1)

NAME
     bsdiff -- generate a patch between two binary files

SYNOPSIS
     bsdiff <oldfile> <newfile> <patchfile>

DESCRIPTION
     bsdiff compares <oldfile> to <newfile> and writes to <patchfile> a binary patch suitable for use by bspatch(1).  When <oldfile> and <newfile> are two versions of an executable
     program, the patches produced are on average a factor of five smaller than those produced by any other binary patch tool known to the author.

     bsdiff uses memory equal to 17 times the size of <oldfile>, and requires an absolute minimum working set size of 8 times the size of oldfile.

SEE ALSO
     bspatch(1)

AUTHORS
     Colin Percival <cperciva@freebsd.org>

FreeBSD                          May 18, 2003                          FreeBSD
(END)

オプションとか特になさそう…？

$ bspatch --help
bspatch: usage: bspatch oldfile newfile patchfile

$ man bspatch
BSPATCH(1)                BSD General Commands Manual               BSPATCH(1)

NAME
     bspatch -- apply a patch built with bsdiff(1)

SYNOPSIS
     bspatch <oldfile> <newfile> <patchfile>

DESCRIPTION
     bspatch generates <newfile> from <oldfile> and <patchfile> where <patchfile> is a binary patch built by bsdiff(1).

     bspatch uses memory equal to the size of <oldfile> plus the size of <newfile>, but can tolerate a very small working set without a dramatic loss of performance.

SEE ALSO
     http://www.daemonology.net/bsdiff/

AUTHORS
     Colin Percival <cperciva@freebsd.org>

FreeBSD                          May 18, 2003                          FreeBSD

こちらも特にない。

なぜコマンドライン引数を見たかというと、GNUのsedコマンドの-iのようなファイルをそのまま置き換えるといったオプションがあるかどうか確認したかったからです。
どうやらなさそうなので、パッチを適用時に古いものと新しいものを混在させておいて最後に切り替えるのが良さそうです。

ディレクトリに適用できるのか確認

コマンドライン引数を見ると、その可能性はなさそうにみえますが、、、一応やってみます。

$ mkdir v1 v2
$ echo "version 1.00" > v1/data
$ echo "version 2.00" > v2/data
$ echo "additional data" > v2/data_additional
$ bsdiff v1 v2 patch_v1_to_v2
bsdiff: v1: Is a directory

ですよね。。。なので、差分生成のアルゴリズムとしてbsdiff/bspatchは使えるが、
ファイルやディレクトリも含めた差分を出すには自力で頑張る必要がありそうです。

diff/patchコマンドでディレクトリ構造を含めてパッチが作れるけど？

サブタイトルのような疑問をいだいた方はいると思います。
例えばdiffコマンドでは下記のようにディレクトリを含めてパッチを作ることができます。

$ diff -crN -a --binary v1 v2 > patch_v1_to_v2
# 検証用にディレクトリをコピー
$ cp -R v1 v1_test

# パッチ適用
$ cd v1_test && patch < ../patch_v1_to_v2 && cd ..
patching file data
patching file data_additional

# 確認
$ cat v1_test/data
version 2.00
$ cat v1_test/data_additional
additional data

ではなぜこれを使わないのでしょうか？
理由はdiff/patchは改行を想定しているためです。
いままでのテストでは普通のテキストデータしか出てきませんでしたが、バイナリデータを作って検証してみます。

$ mkdir v1 v2

# 1MBのバイナリデータを作成
$ head -c 1048576 /dev/urandom > v1/data
# \rと\nを除く
$ vim v1/data
# :%s/\r/A/g
# :%s/\n/B/g
# :wq
$ ll v1/data
-rw-r--r--  1 USER  GROUP  1048578  2  9 17:31 v1/data
# 2バイト増えているので2バイト削る
$ head -c 1048576 v1/data > v1/data.2
$ mv v1/data.2 v1/data
 ll v1/data
-rw-r--r--  1 USER  GROUP  1048576  2  9 17:32 v1/data

# v2では1バイトだけいじってみる
$ head -c 1000000 v1/data > v2/data
$ echo -n "a" >> v2/data
$ tail -c 48575 v1/data >> v2/data

この状態でdiffとbsdiffで比較してみます。

$ diff -c -a --binary v1/data v2/data > diff_v1_v2
$ bsdiff v1/data v2/data bsdiff_v1_v2

# 比較結果
$ ll *diff_v1_v2
-rw-r--r--  1 USER  GROUP      153  2  9 17:34 bsdiff_v1_v2
-rw-r--r--  1 USER  GROUP  2097348  2  9 17:33 diff_v1_v2

1行ずつ比較をとるdiffではバイナリパッチには不向きであることがわかります。

bsdiff/bspatchをどうやって組み込むか？

ソースコードについて

bsdiff/bspatchは下記にソースコードが公開されております。
https://github.com/mendsley/bsdiff

ライセンスは「2条項BSDライセンス」となっており、下記を満たせばソースやバイナリの再配布が可能です。

変更の有無を問わず、ソースやバイナリ形式での再配布や利用は、次の条件を満たせば許可される。
・ソースコードの再配布は、上記の著作権表示、ここに列挙された条件、および下記の免責条項を保持すること。
・バイナリ形式の再配布は、上記の著作権表示、ここに列挙された条件、および下記の免責条項は、ドキュメントまたは他の資料で配布すること。

GPL/LGPL等のようにソースコードの公開は必須ではないので安心して使えますね。

ソースコードを読み解く - bsdiff.c

アルゴリズムについて知っておきたい気もしますが…
やりたいのはただbsdiffの機能を拝借するだけなので、とりあえずmain関数を見てみます。

int main(int argc,char *argv[])
{
	int fd;
	int bz2err;
	uint8_t *old,*new;
	off_t oldsize,newsize;
	uint8_t buf[8];
	FILE * pf;
	struct bsdiff_stream stream;
	BZFILE* bz2;

	memset(&bz2, 0, sizeof(bz2));
	stream.malloc = malloc;
	stream.free = free;
	stream.write = bz2_write;

この辺は変数の宣言とメモリの初期化。

	if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);

	/* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
		that we never try to malloc(0) and get a NULL pointer */
	if(((fd=open(argv[1],O_RDONLY,0))<0) ||
		((oldsize=lseek(fd,0,SEEK_END))==-1) ||
		((old=malloc(oldsize+1))==NULL) ||
		(lseek(fd,0,SEEK_SET)!=0) ||
		(read(fd,old,oldsize)!=oldsize) ||
		(close(fd)==-1)) err(1,"%s",argv[1]);


	/* Allocate newsize+1 bytes instead of newsize bytes to ensure
		that we never try to malloc(0) and get a NULL pointer */
	if(((fd=open(argv[2],O_RDONLY,0))<0) ||
		((newsize=lseek(fd,0,SEEK_END))==-1) ||
		((new=malloc(newsize+1))==NULL) ||
		(lseek(fd,0,SEEK_SET)!=0) ||
		(read(fd,new,newsize)!=newsize) ||
		(close(fd)==-1)) err(1,"%s",argv[2]);

この辺は与えられた引数（ファイル）に関するバリデーションです。
メモリが足りない場合もエラーになります。

	/* Create the patch file */
	if ((pf = fopen(argv[3], "w")) == NULL)
		err(1, "%s", argv[3]);

ここで書き込むパッチファイルをオープンしています。

	/* Write header (signature+newsize)*/
	offtout(newsize, buf);
	if (fwrite("ENDSLEY/BSDIFF43", 16, 1, pf) != 1 ||
		fwrite(buf, sizeof(buf), 1, pf) != 1)
		err(1, "Failed to write header");

ヘッダです。bspatchを叩くときに使うのでしょう。
シグネチャとパッチ適用後のファイルサイズ(64bit)が入ります。

	if (NULL == (bz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)))
		errx(1, "BZ2_bzWriteOpen, bz2err=%d", bz2err);

bsdiffは内部的にbzip2を使っているようです。
bzip2についてはこちらを参考にさせていただきました。
libbzip2 の使い方 - 矢田晋
なお、bzip2はBSDライクなライセンスなので組み込んでもソースコードの開示は不要です。

	stream.opaque = bz2;
	if (bsdiff(old, oldsize, new, newsize, &stream))
		err(1, "bsdiff");

ここで実際にbsdiffを使った差分を抽出して、データに書き出しています。

	BZ2_bzWriteClose(&bz2err, bz2, 0, NULL, NULL);
	if (bz2err != BZ_OK)
		err(1, "BZ2_bzWriteClose, bz2err=%d", bz2err);

bzip2の説明をみると、このクローズのタイミングで圧縮データをファイルに保存していそうです。

	if (fclose(pf))
		err(1, "fclose");

	/* Free the memory we used */
	free(old);
	free(new);

	return 0;
}

ファイルにフラッシュして終了。
bsdiff.cは単一の実行プログラムなので、これでは利便性が低いですが、
main関数と同様に、比較対象2つとパッチデータの出力先を引数とする関数を.a/.libや.so/.dllに公開すれば、アプリケーション側で好きに利用ができそうですね。
Windowsへのビルドにはmingw-w64等を使うか、Visual Studioに対応させるかは後ほど考えます。

ソースコードを読み解く - bspatch.c

同様にしてこちらもみてみます。

int main(int argc,char * argv[])
{
	FILE * f;
	int fd;
	int bz2err;
	uint8_t header[24];
	uint8_t *old, *new;
	int64_t oldsize, newsize;
	BZFILE* bz2;
	struct bspatch_stream stream;
	struct stat sb;

この辺は変数の宣言とメモリの初期化。

	if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);

	/* Open patch file */
	if ((f = fopen(argv[3], "r")) == NULL)
		err(1, "fopen(%s)", argv[3]);

ここで与えられた引数に対するバリデーション。

	/* Read header */
	if (fread(header, 1, 24, f) != 24) {
		if (feof(f))
			errx(1, "Corrupt patch\n");
		err(1, "fread(%s)", argv[3]);
	}

	/* Check for appropriate magic */
	if (memcmp(header, "ENDSLEY/BSDIFF43", 16) != 0)
		errx(1, "Corrupt patch\n");

	/* Read lengths from header */
	newsize=offtin(header+16);
	if(newsize<0)
		errx(1,"Corrupt patch\n");

ヘッダの整合性をチェック。合わせて、出力後のファイルサイズも取得。

	/* Close patch file and re-open it via libbzip2 at the right places */
	if(((fd=open(argv[1],O_RDONLY,0))<0) ||
		((oldsize=lseek(fd,0,SEEK_END))==-1) ||
		((old=malloc(oldsize+1))==NULL) ||
		(lseek(fd,0,SEEK_SET)!=0) ||
		(read(fd,old,oldsize)!=oldsize) ||
		(fstat(fd, &sb)) ||
		(close(fd)==-1)) err(1,"%s",argv[1]);

適用前のファイルサイズを取得し、適用前のファイルのデータを読み込む

if((new=malloc(newsize+1))==NULL) err(1,NULL);

適用後のバッファを用意。

	if (NULL == (bz2 = BZ2_bzReadOpen(&bz2err, f, 0, 0, NULL, 0)))
		errx(1, "BZ2_bzReadOpen, bz2err=%d", bz2err);

bzip2で圧縮したので、bzip2を解凍するための準備です。
第2引数のfはパッチファイル(ヘッダ部分を読み飛ばしたところにカーソルがある)です。

	stream.read = bz2_read;
	stream.opaque = bz2;
	if (bspatch(old, oldsize, new, newsize, &stream))
		errx(1, "bspatch");

ここが実際にbsdiffを使って抽出した差分を適用する処理です。

	/* Clean up the bzip2 reads */
	BZ2_bzReadClose(&bz2err, bz2);
	fclose(f);

読み込んでいたファイルを解放。

	/* Write the new file */
	if(((fd=open(argv[2],O_CREAT|O_TRUNC|O_WRONLY,sb.st_mode))<0) ||
		(write(fd,new,newsize)!=newsize) || (close(fd)==-1))
		err(1,"%s",argv[2]);


	free(new);
	free(old);

	return 0;

ファイルに書き込んで終了。
自己解凍形式にするなら、第1引数のファイル名と第3引数のデータを
自分のプログラム中にデータを埋め込むように作り直せばいけそうですね。
データの埋め込みはパッチを作る際にソースコードをビルドするでも良いし、
Windowsならリソースという機能を使って埋め込むことができます。
方針は後ほど考えます。

今後の方針

bsdiff/bspatchはそのままの形では使えないのでアルゴリズムを流用する
bsdiffはライブラリ化して、パッチ作成ツールから呼び出せるようにする
bspatchで引数で与えていたbsdiffで作ったパッチ情報を実行可能ファイルに内包するようにして、自己解凍パッチを作る