Project import
diff --git a/bsdiff/.clang-format b/bsdiff/.clang-format
new file mode 100644
index 0000000..998f530
--- /dev/null
+++ b/bsdiff/.clang-format
@@ -0,0 +1,4 @@
+BasedOnStyle: Chromium
+
+MaxEmptyLinesToKeep: 2
+AllowShortBlocksOnASingleLine: true
diff --git a/bsdiff/Android.mk b/bsdiff/Android.mk
new file mode 100644
index 0000000..12ee3e8
--- /dev/null
+++ b/bsdiff/Android.mk
@@ -0,0 +1,154 @@
+# Copyright (C) 2008 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+LOCAL_PATH := $(call my-dir)
+
+# Common project flags.
+bsdiff_common_cflags := \
+ -D_FILE_OFFSET_BITS=64 \
+ -Wall \
+ -Werror \
+ -Wextra \
+ -Wno-unused-parameter
+
+bsdiff_common_static_libs := \
+ libbz
+
+# "bsdiff" program.
+bsdiff_static_libs := \
+ libdivsufsort64 \
+ libdivsufsort \
+ $(bsdiff_common_static_libs)
+
+bsdiff_src_files := \
+ bsdiff.cc
+
+# "bspatch" program.
+bspatch_src_files := \
+ bspatch.cc \
+ extents.cc \
+ extents_file.cc \
+ file.cc \
+ memory_file.cc
+
+# Unit test files.
+bsdiff_common_unittests := \
+ bsdiff_unittest.cc \
+ bspatch_unittest.cc \
+ extents_file_unittest.cc \
+ extents_unittest.cc \
+ test_utils.cc
+
+# Target static libraries.
+
+include $(CLEAR_VARS)
+LOCAL_MODULE := libbspatch
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := $(bspatch_src_files)
+LOCAL_CFLAGS := $(bsdiff_common_cflags)
+LOCAL_STATIC_LIBRARIES := $(bsdiff_common_static_libs)
+include $(BUILD_STATIC_LIBRARY)
+
+include $(CLEAR_VARS)
+LOCAL_MODULE := libbsdiff
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := $(bsdiff_src_files)
+LOCAL_CFLAGS := $(bsdiff_common_cflags)
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)
+LOCAL_STATIC_LIBRARIES := $(bsdiff_static_libs)
+include $(BUILD_STATIC_LIBRARY)
+
+# Host static libraries.
+
+include $(CLEAR_VARS)
+LOCAL_MODULE := libbspatch
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := $(bspatch_src_files)
+LOCAL_CFLAGS := $(bsdiff_common_cflags)
+LOCAL_STATIC_LIBRARIES := $(bsdiff_common_static_libs)
+include $(BUILD_HOST_STATIC_LIBRARY)
+
+include $(CLEAR_VARS)
+LOCAL_MODULE := libbsdiff
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := $(bsdiff_src_files)
+LOCAL_CFLAGS := $(bsdiff_common_cflags)
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)
+LOCAL_STATIC_LIBRARIES := $(bsdiff_static_libs)
+include $(BUILD_HOST_STATIC_LIBRARY)
+
+# Target executables.
+
+include $(CLEAR_VARS)
+LOCAL_MODULE := bspatch
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := bspatch_main.cc
+LOCAL_CFLAGS := $(bsdiff_common_cflags)
+LOCAL_STATIC_LIBRARIES := \
+ libbspatch \
+ $(bsdiff_common_static_libs)
+include $(BUILD_EXECUTABLE)
+
+# bspatch used in recovery by update_engine_sideload.
+include $(CLEAR_VARS)
+LOCAL_MODULE := bspatch_recovery
+LOCAL_MODULE_STEM := bspatch
+LOCAL_FORCE_STATIC_EXECUTABLE := true
+LOCAL_MODULE_PATH := $(TARGET_RECOVERY_ROOT_OUT)/sbin
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := bspatch_main.cc
+LOCAL_CFLAGS := $(bsdiff_common_cflags)
+LOCAL_STATIC_LIBRARIES := \
+ libbspatch \
+ $(bsdiff_common_static_libs)
+include $(BUILD_EXECUTABLE)
+
+# Host executables.
+
+include $(CLEAR_VARS)
+LOCAL_MODULE := bsdiff
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := bsdiff_main.cc
+LOCAL_CFLAGS := $(bsdiff_common_cflags)
+LOCAL_STATIC_LIBRARIES := \
+ libbsdiff \
+ $(bsdiff_static_libs)
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+LOCAL_MODULE := bspatch
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := bspatch_main.cc
+LOCAL_CFLAGS := $(bsdiff_common_cflags)
+LOCAL_STATIC_LIBRARIES := \
+ libbspatch \
+ $(bsdiff_common_static_libs)
+include $(BUILD_HOST_EXECUTABLE)
+
+# Unit tests.
+
+include $(CLEAR_VARS)
+LOCAL_MODULE := bsdiff_unittest
+LOCAL_MODULE_TAGS := debug tests
+LOCAL_CPP_EXTENSION := .cc
+LOCAL_SRC_FILES := $(bsdiff_common_unittests) \
+ testrunner.cc
+LOCAL_CFLAGS := $(bsdiff_common_cflags) \
+ -DBSDIFF_TARGET_UNITTEST
+LOCAL_STATIC_LIBRARIES := \
+ libbsdiff \
+ libbspatch \
+ libgmock \
+ $(bsdiff_static_libs)
+include $(BUILD_NATIVE_TEST)
diff --git a/bsdiff/CleanSpec.mk b/bsdiff/CleanSpec.mk
new file mode 100644
index 0000000..b84e1b6
--- /dev/null
+++ b/bsdiff/CleanSpec.mk
@@ -0,0 +1,49 @@
+# Copyright (C) 2007 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+
+# If you don't need to do a full clean build but would like to touch
+# a file or delete some intermediate files, add a clean step to the end
+# of the list. These steps will only be run once, if they haven't been
+# run before.
+#
+# E.g.:
+# $(call add-clean-step, touch -c external/sqlite/sqlite3.h)
+# $(call add-clean-step, rm -rf $(PRODUCT_OUT)/obj/STATIC_LIBRARIES/libz_intermediates)
+#
+# Always use "touch -c" and "rm -f" or "rm -rf" to gracefully deal with
+# files that are missing or have been moved.
+#
+# Use $(PRODUCT_OUT) to get to the "out/target/product/blah/" directory.
+# Use $(OUT_DIR) to refer to the "out" directory.
+#
+# If you need to re-do something that's already mentioned, just copy
+# the command and add it to the bottom of the list. E.g., if a change
+# that you made last week required touching a file and a change you
+# made today requires touching the same file, just copy the old
+# touch step and add it to the end of the list.
+#
+# ************************************************
+# NEWER CLEAN STEPS MUST BE AT THE END OF THE LIST
+# ************************************************
+
+# For example:
+#$(call add-clean-step, rm -rf $(OUT_DIR)/target/common/obj/APPS/AndroidTests_intermediates)
+#$(call add-clean-step, rm -rf $(OUT_DIR)/target/common/obj/JAVA_LIBRARIES/core_intermediates)
+#$(call add-clean-step, find $(OUT_DIR) -type f -name "IGTalkSession*" -print0 | xargs -0 rm -f)
+#$(call add-clean-step, rm -rf $(PRODUCT_OUT)/data/*)
+
+# ************************************************
+# NEWER CLEAN STEPS MUST BE AT THE END OF THE LIST
+# ************************************************
diff --git a/bsdiff/LICENSE b/bsdiff/LICENSE
new file mode 100644
index 0000000..c8607a9
--- /dev/null
+++ b/bsdiff/LICENSE
@@ -0,0 +1,58 @@
+This project governed by the following BSD-style licenses. Check each file
+header to known the licenses applying to it:
+
+--------------------------------------------------------------------------------
+
+Copyright 2003-2005 Colin Percival
+All rights reserved
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted providing that the following conditions
+are met:
+1. Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+2. Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.
+
+--------------------------------------------------------------------------------
+
+Copyright 2015 The Chromium OS Authors. All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+ * Redistributions of source code must retain the above copyright
+notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above
+copyright notice, this list of conditions and the following disclaimer
+in the documentation and/or other materials provided with the
+distribution.
+ * Neither the name of Google Inc. nor the names of its
+contributors may be used to endorse or promote products derived from
+this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/bsdiff/MODULE_LICENSE_BSD_LIKE b/bsdiff/MODULE_LICENSE_BSD_LIKE
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/bsdiff/MODULE_LICENSE_BSD_LIKE
diff --git a/bsdiff/Makefile b/bsdiff/Makefile
new file mode 100644
index 0000000..fbfe56a
--- /dev/null
+++ b/bsdiff/Makefile
@@ -0,0 +1,85 @@
+# Default options
+USE_BSDIFF ?= y
+
+BINARIES-y = bspatch
+BINARIES-$(USE_BSDIFF) += bsdiff
+
+BINARIES += $(BINARIES-y)
+
+INSTALL = install
+CFLAGS += -O3 -Wall -Werror
+CXXFLAGS += -std=c++11
+
+DESTDIR ?=
+PREFIX = /usr
+BINDIR = $(PREFIX)/bin
+DATADIR = $(PREFIX)/share
+MANDIR = $(DATADIR)/man
+MAN1DIR = $(MANDIR)/man1
+INSTALL_PROGRAM ?= $(INSTALL) -c -m 755
+INSTALL_MAN ?= $(INSTALL) -c -m 444
+
+.PHONY: all test clean
+all: $(BINARIES)
+test: unittests
+clean:
+ rm -f *.o $(BINARIES) unittests
+
+BSDIFF_LIBS = -lbz2 -ldivsufsort -ldivsufsort64
+BSDIFF_OBJS = \
+ bsdiff.o
+
+BSPATCH_LIBS = -lbz2
+BSPATCH_OBJS = \
+ bspatch.o \
+ extents.o \
+ extents_file.o \
+ file.o \
+ memory_file.o
+
+UNITTEST_LIBS = -lgmock -lgtest -lpthread
+UNITTEST_OBJS = \
+ bsdiff_unittest.o \
+ bspatch_unittest.o \
+ extents_file_unittest.o \
+ extents_unittest.o \
+ test_utils.o \
+ testrunner.o
+
+bsdiff: $(BSDIFF_OBJS) bsdiff_main.o
+bsdiff: LDLIBS += $(BSDIFF_LIBS)
+
+bspatch: $(BSPATCH_OBJS) bspatch_main.o
+bspatch: LDLIBS += $(BSPATCH_LIBS)
+
+unittests: LDLIBS += $(BSDIFF_LIBS) $(BSPATCH_LIBS) $(UNITTEST_LIBS)
+unittests: $(BSPATCH_OBJS) $(BSDIFF_OBJS) $(UNITTEST_OBJS)
+
+unittests bsdiff bspatch:
+ $(CXX) $(CPPFLAGS) $(CXXFLAGS) -o $@ $^ $(LDLIBS)
+
+# Source file dependencies.
+bsdiff.o: bsdiff.cc
+bsdiff_main.o: bsdiff_main.cc bsdiff.h
+bsdiff_unittest.o: bsdiff_unittest.cc bsdiff.h test_utils.h
+bspatch.o: bspatch.cc bspatch.h extents.h extents_file.h file_interface.h \
+ file.h
+bspatch_main.o: bspatch_main.cc bspatch.h
+bspatch_unittest.o: bspatch_unittest.cc bspatch.h test_utils.h
+extents.o: extents.cc extents.h extents_file.h file_interface.h
+extents_file.o: extents_file.cc extents_file.h file_interface.h
+extents_file_unittest.o: extents_file_unittest.cc extents_file.h \
+ file_interface.h
+extents_unittest.o: extents_unittest.cc extents.h extents_file.h \
+ file_interface.h
+file.o: file.cc file.h file_interface.h
+memory_file.o: memory_file.cc memory_file.h file_interface.h
+testrunner.o: testrunner.cc
+test_utils.o: test_utils.cc test_utils.h
+
+install:
+ mkdir -p $(DESTDIR)$(BINDIR) $(DESTDIR)$(MAN1DIR)
+ $(INSTALL_PROGRAM) $(BINARIES) $(DESTDIR)$(BINDIR)
+ifndef WITHOUT_MAN
+ $(INSTALL_MAN) $(BINARIES:=.1) $(DESTDIR)$(MAN1DIR)
+endif
diff --git a/bsdiff/NOTICE b/bsdiff/NOTICE
new file mode 120000
index 0000000..7a694c9
--- /dev/null
+++ b/bsdiff/NOTICE
@@ -0,0 +1 @@
+LICENSE
\ No newline at end of file
diff --git a/bsdiff/README.android b/bsdiff/README.android
new file mode 100644
index 0000000..9458d41
--- /dev/null
+++ b/bsdiff/README.android
@@ -0,0 +1,6 @@
+This is bsdiff-4.3 from http://www.daemonology.net/bsdiff/.
+
+This file, the Android.mk makefile, and the empty
+MODULE_LICENSE_BSD_LIKE file were added.
+
+Changes in the source are marked with "// android" comments.
diff --git a/bsdiff/README.chromium b/bsdiff/README.chromium
new file mode 100644
index 0000000..5ae005b
--- /dev/null
+++ b/bsdiff/README.chromium
@@ -0,0 +1,12 @@
+Homepage: http://www.daemonology.net/bsdiff/
+Version: 4.3.1
+License: BSD-2
+
+Description:
+
+Binary diff/patch utility.
+
+bsdiff and bspatch are tools for building and applying patches to binary
+files. By using suffix sorting and taking advantage of how executable files
+change, bsdiff routinely produces binary patches 50-80% smaller than those
+produced by Xdelta, and 15% smaller than those produced by .RTPatch.
diff --git a/bsdiff/bsdiff.1 b/bsdiff/bsdiff.1
new file mode 100644
index 0000000..659f5ff
--- /dev/null
+++ b/bsdiff/bsdiff.1
@@ -0,0 +1,64 @@
+.\"-
+.\" Copyright 2003-2005 Colin Percival
+.\" All rights reserved
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted providing that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\" notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\" notice, this list of conditions and the following disclaimer in the
+.\" documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+.\" WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+.\" DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+.\" IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+.\" POSSIBILITY OF SUCH DAMAGE.
+.\"
+.\" $FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.1,v 1.1 2005/08/06 01:59:05 cperciva Exp $
+.\"
+.Dd May 18, 2003
+.Dt BSDIFF 1
+.Os FreeBSD
+.Sh NAME
+.Nm bsdiff
+.Nd generate a patch between two binary files
+.Sh SYNOPSIS
+.Nm
+.Ar oldfile newfile patchfile
+.Sh DESCRIPTION
+.Nm
+compares
+.Ar oldfile
+to
+.Ar newfile
+and writes to
+.Ar patchfile
+a binary patch suitable for use by
+.Xr bspatch 1 .
+When
+.Ar oldfile
+and
+.Ar 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.
+.Pp
+.Nm
+uses memory equal to 17 times the size of
+.Ar oldfile ,
+and requires
+an absolute minimum working set size of 8 times the size of oldfile.
+.Sh SEE ALSO
+.Xr bspatch 1
+.Sh AUTHORS
+.An Colin Percival Aq cperciva@freebsd.org
diff --git a/bsdiff/bsdiff.cc b/bsdiff/bsdiff.cc
new file mode 100644
index 0000000..669a1e5
--- /dev/null
+++ b/bsdiff/bsdiff.cc
@@ -0,0 +1,350 @@
+/*-
+ * Copyright 2003-2005 Colin Percival
+ * All rights reserved
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted providing that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+ * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#if 0
+__FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c,v 1.1 2005/08/06 01:59:05 cperciva Exp $");
+#endif
+
+#include "bsdiff.h"
+
+#include <sys/types.h>
+
+#include <bzlib.h>
+#include <err.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include <algorithm>
+
+#if _FILE_OFFSET_BITS == 64
+#include "divsufsort64.h"
+#define saidx_t saidx64_t
+#define divsufsort divsufsort64
+#else
+#include "divsufsort.h"
+#endif
+
+namespace bsdiff {
+
+static off_t matchlen(const u_char* old, off_t oldsize, const u_char* new_buf,
+ off_t newsize) {
+ off_t i;
+
+ for(i=0;(i<oldsize)&&(i<newsize);i++)
+ if(old[i]!=new_buf[i]) break;
+
+ return i;
+}
+
+// This is a binary search of the string |new_buf| of size |newsize| (or a
+// prefix of it) in the |old| string with size |oldsize| using the suffix array
+// |I|. |st| and |en| is the start and end of the search range (inclusive).
+// Returns the length of the longest prefix found and stores the position of the
+// string found in |*pos|.
+static off_t search(saidx_t* I, const u_char* old, off_t oldsize,
+ const u_char* new_buf, off_t newsize, off_t st, off_t en,
+ off_t* pos) {
+ off_t x,y;
+
+ if(en-st<2) {
+ x=matchlen(old+I[st],oldsize-I[st],new_buf,newsize);
+ y=matchlen(old+I[en],oldsize-I[en],new_buf,newsize);
+
+ if(x>y) {
+ *pos=I[st];
+ return x;
+ } else {
+ *pos=I[en];
+ return y;
+ }
+ };
+
+ x=st+(en-st)/2;
+ if(memcmp(old+I[x],new_buf,std::min(oldsize-I[x],newsize))<=0) {
+ return search(I,old,oldsize,new_buf,newsize,x,en,pos);
+ } else {
+ return search(I,old,oldsize,new_buf,newsize,st,x,pos);
+ };
+}
+
+static void offtout(off_t x,u_char *buf)
+{
+ off_t y;
+
+ if(x<0) y=-x; else y=x;
+
+ buf[0]=y%256;y-=buf[0];
+ y=y/256;buf[1]=y%256;y-=buf[1];
+ y=y/256;buf[2]=y%256;y-=buf[2];
+ y=y/256;buf[3]=y%256;y-=buf[3];
+ y=y/256;buf[4]=y%256;y-=buf[4];
+ y=y/256;buf[5]=y%256;y-=buf[5];
+ y=y/256;buf[6]=y%256;y-=buf[6];
+ y=y/256;buf[7]=y%256;
+
+ if(x<0) buf[7]|=0x80;
+}
+
+int bsdiff(const char* old_filename, const char* new_filename,
+ const char* patch_filename) {
+ int fd;
+ u_char *old_buf,*new_buf;
+ off_t oldsize,newsize;
+
+ /* 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(old_filename,O_RDONLY,0))<0) ||
+ ((oldsize=lseek(fd,0,SEEK_END))==-1) ||
+ ((old_buf=static_cast<u_char*>(malloc(oldsize+1)))==NULL) ||
+ (lseek(fd,0,SEEK_SET)!=0) ||
+ (read(fd,old_buf,oldsize)!=oldsize) ||
+ (close(fd)==-1)) err(1,"%s",old_filename);
+
+ /* 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(new_filename,O_RDONLY,0))<0) ||
+ ((newsize=lseek(fd,0,SEEK_END))==-1) ||
+ ((new_buf = static_cast<u_char*>(malloc(newsize+1)))==NULL) ||
+ (lseek(fd,0,SEEK_SET)!=0) ||
+ (read(fd,new_buf,newsize)!=newsize) ||
+ (close(fd)==-1)) err(1,"%s",new_filename);
+
+ int ret = bsdiff(old_buf, oldsize, new_buf, newsize, patch_filename);
+
+ free(old_buf);
+ free(new_buf);
+
+ return ret;
+}
+
+int bsdiff(const u_char* old_buf, off_t oldsize, const u_char* new_buf,
+ off_t newsize, const char* patch_filename) {
+ saidx_t *I;
+ off_t scan,pos=0,len;
+ off_t lastscan,lastpos,lastoffset;
+ off_t oldscore,scsc;
+ off_t s,Sf,lenf,Sb,lenb;
+ off_t overlap,Ss,lens;
+ off_t i;
+ off_t dblen,eblen;
+ u_char *db,*eb;
+ u_char buf[8];
+ u_char header[32];
+ FILE * pf;
+ BZFILE * pfbz2;
+ int bz2err;
+
+ if((I=static_cast<saidx_t*>(malloc((oldsize+1)*sizeof(saidx_t))))==NULL)
+ err(1,NULL);
+
+ if(divsufsort(old_buf, I, oldsize)) err(1, "divsufsort");
+
+ if(((db=static_cast<u_char*>(malloc(newsize+1)))==NULL) ||
+ ((eb=static_cast<u_char*>(malloc(newsize+1)))==NULL)) err(1,NULL);
+ dblen=0;
+ eblen=0;
+
+ /* Create the patch file */
+ if ((pf = fopen(patch_filename, "w")) == NULL)
+ err(1, "%s", patch_filename);
+
+ /* Header is
+ 0 8 "BSDIFF40"
+ 8 8 length of bzip2ed ctrl block
+ 16 8 length of bzip2ed diff block
+ 24 8 length of new file */
+ /* File is
+ 0 32 Header
+ 32 ?? Bzip2ed ctrl block
+ ?? ?? Bzip2ed diff block
+ ?? ?? Bzip2ed extra block */
+ memcpy(header,"BSDIFF40",8);
+ offtout(0, header + 8);
+ offtout(0, header + 16);
+ offtout(newsize, header + 24);
+ if (fwrite(header, 32, 1, pf) != 1)
+ err(1, "fwrite(%s)", patch_filename);
+
+ /* Compute the differences, writing ctrl as we go */
+ if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
+ errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
+ scan=0;len=0;
+ lastscan=0;lastpos=0;lastoffset=0;
+ while(scan<newsize) {
+ oldscore=0;
+
+ /* If we come across a large block of data that only differs
+ * by less than 8 bytes, this loop will take a long time to
+ * go past that block of data. We need to track the number of
+ * times we're stuck in the block and break out of it. */
+ int num_less_than_eight = 0;
+ off_t prev_len, prev_oldscore, prev_pos;
+ for(scsc=scan+=len;scan<newsize;scan++) {
+ prev_len=len;
+ prev_oldscore=oldscore;
+ prev_pos=pos;
+
+ len=search(I,old_buf,oldsize,new_buf+scan,newsize-scan,
+ 0,oldsize-1,&pos);
+
+ for(;scsc<scan+len;scsc++)
+ if((scsc+lastoffset<oldsize) &&
+ (old_buf[scsc+lastoffset] == new_buf[scsc]))
+ oldscore++;
+
+ if(((len==oldscore) && (len!=0)) ||
+ (len>oldscore+8)) break;
+
+ if((scan+lastoffset<oldsize) &&
+ (old_buf[scan+lastoffset] == new_buf[scan]))
+ oldscore--;
+
+ const off_t fuzz = 8;
+ if (prev_len-fuzz<=len && len<=prev_len &&
+ prev_oldscore-fuzz<=oldscore &&
+ oldscore<=prev_oldscore &&
+ prev_pos<=pos && pos <=prev_pos+fuzz &&
+ oldscore<=len && len<=oldscore+fuzz)
+ ++num_less_than_eight;
+ else
+ num_less_than_eight=0;
+ if (num_less_than_eight > 100) break;
+ };
+
+ if((len!=oldscore) || (scan==newsize)) {
+ s=0;Sf=0;lenf=0;
+ for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
+ if(old_buf[lastpos+i]==new_buf[lastscan+i]) s++;
+ i++;
+ if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
+ };
+
+ lenb=0;
+ if(scan<newsize) {
+ s=0;Sb=0;
+ for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) {
+ if(old_buf[pos-i]==new_buf[scan-i]) s++;
+ if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; };
+ };
+ };
+
+ if(lastscan+lenf>scan-lenb) {
+ overlap=(lastscan+lenf)-(scan-lenb);
+ s=0;Ss=0;lens=0;
+ for(i=0;i<overlap;i++) {
+ if(new_buf[lastscan+lenf-overlap+i]==
+ old_buf[lastpos+lenf-overlap+i]) s++;
+ if(new_buf[scan-lenb+i]==
+ old_buf[pos-lenb+i]) s--;
+ if(s>Ss) { Ss=s; lens=i+1; };
+ };
+
+ lenf+=lens-overlap;
+ lenb-=lens;
+ };
+
+ for(i=0;i<lenf;i++)
+ db[dblen+i]=new_buf[lastscan+i]-old_buf[lastpos+i];
+ for(i=0;i<(scan-lenb)-(lastscan+lenf);i++)
+ eb[eblen+i]=new_buf[lastscan+lenf+i];
+
+ dblen+=lenf;
+ eblen+=(scan-lenb)-(lastscan+lenf);
+
+ offtout(lenf,buf);
+ BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
+ if (bz2err != BZ_OK)
+ errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
+
+ offtout((scan-lenb)-(lastscan+lenf),buf);
+ BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
+ if (bz2err != BZ_OK)
+ errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
+
+ offtout((pos-lenb)-(lastpos+lenf),buf);
+ BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
+ if (bz2err != BZ_OK)
+ errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
+
+ lastscan=scan-lenb;
+ lastpos=pos-lenb;
+ lastoffset=pos-scan;
+ };
+ };
+ BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
+ if (bz2err != BZ_OK)
+ errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
+
+ /* Compute size of compressed ctrl data */
+ if ((len = ftello(pf)) == -1)
+ err(1, "ftello");
+ offtout(len-32, header + 8);
+
+ /* Write compressed diff data */
+ if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
+ errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
+ BZ2_bzWrite(&bz2err, pfbz2, db, dblen);
+ if (bz2err != BZ_OK)
+ errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
+ BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
+ if (bz2err != BZ_OK)
+ errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
+
+ /* Compute size of compressed diff data */
+ if ((newsize = ftello(pf)) == -1)
+ err(1, "ftello");
+ offtout(newsize - len, header + 16);
+
+ /* Write compressed extra data */
+ if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
+ errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
+ BZ2_bzWrite(&bz2err, pfbz2, eb, eblen);
+ if (bz2err != BZ_OK)
+ errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
+ BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
+ if (bz2err != BZ_OK)
+ errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
+
+ /* Seek to the beginning, write the header, and close the file */
+ if (fseeko(pf, 0, SEEK_SET))
+ err(1, "fseeko");
+ if (fwrite(header, 32, 1, pf) != 1)
+ err(1, "fwrite(%s)", patch_filename);
+ if (fclose(pf))
+ err(1, "fclose");
+
+ /* Free the memory we used */
+ free(db);
+ free(eb);
+ free(I);
+
+ return 0;
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/bsdiff.h b/bsdiff/bsdiff.h
new file mode 100644
index 0000000..370ee03
--- /dev/null
+++ b/bsdiff/bsdiff.h
@@ -0,0 +1,24 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef _BSDIFF_BSDIFF_H_
+#define _BSDIFF_BSDIFF_H_
+
+#include <sys/types.h>
+
+namespace bsdiff {
+
+int bsdiff(const char* old_filename,
+ const char* new_filename,
+ const char* patch_filename);
+
+int bsdiff(const u_char* old_buf,
+ off_t oldsize,
+ const u_char* new_buf,
+ off_t newsize,
+ const char* patch_filename);
+
+} // namespace bsdiff
+
+#endif // _BSDIFF_BSDIFF_H_
diff --git a/bsdiff/bsdiff_main.cc b/bsdiff/bsdiff_main.cc
new file mode 100644
index 0000000..db3026c
--- /dev/null
+++ b/bsdiff/bsdiff_main.cc
@@ -0,0 +1,14 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <err.h>
+
+#include "bsdiff.h"
+
+int main(int argc, char* argv[]) {
+ if (argc != 4)
+ errx(1, "usage: %s oldfile newfile patchfile\n", argv[0]);
+
+ return bsdiff::bsdiff(argv[1], argv[2], argv[3]);
+}
diff --git a/bsdiff/bsdiff_unittest.cc b/bsdiff/bsdiff_unittest.cc
new file mode 100644
index 0000000..b3aae3e
--- /dev/null
+++ b/bsdiff/bsdiff_unittest.cc
@@ -0,0 +1,64 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "bsdiff.h"
+
+#include <gtest/gtest.h>
+#include <string>
+#include <vector>
+
+#include "test_utils.h"
+
+using std::string;
+using std::vector;
+using test_utils::BsdiffPatchFile;
+
+namespace bsdiff {
+
+class BsdiffTest : public testing::Test {
+ protected:
+ BsdiffTest()
+ : old_file_("bsdiff_oldfile.XXXXXX"),
+ new_file_("bsdiff_newfile.XXXXXX"),
+ patch_file_("bsdiff_patchfile.XXXXXX") {
+ }
+ ~BsdiffTest() override {}
+
+ test_utils::ScopedTempFile old_file_;
+ test_utils::ScopedTempFile new_file_;
+ test_utils::ScopedTempFile patch_file_;
+};
+
+// Check that a file with no changes has a very small patch (no extra data).
+TEST_F(BsdiffTest, EqualEmptyFiles) {
+ // Empty old and new files.
+ EXPECT_EQ(0, bsdiff(old_file_.filename().c_str(),
+ new_file_.filename().c_str(),
+ patch_file_.filename().c_str()));
+ BsdiffPatchFile patch;
+ EXPECT_TRUE(patch.LoadFromFile(patch_file_.filename()));
+ EXPECT_TRUE(patch.IsValid());
+
+ // An empty bz2 file will have 14 bytes.
+ EXPECT_EQ(14, patch.diff_len);
+ EXPECT_EQ(14U, patch.extra_len);
+}
+
+TEST_F(BsdiffTest, EqualSmallFiles) {
+ string some_text = "Hello world!";
+ vector<uint8_t> vec_some_text(some_text.begin(), some_text.end());
+ test_utils::WriteFile(old_file_.filename(), vec_some_text);
+ EXPECT_EQ(0, bsdiff(old_file_.filename().c_str(),
+ new_file_.filename().c_str(),
+ patch_file_.filename().c_str()));
+ BsdiffPatchFile patch;
+ EXPECT_TRUE(patch.LoadFromFile(patch_file_.filename()));
+ EXPECT_TRUE(patch.IsValid());
+
+ // An empty bz2 file will have 14 bytes.
+ EXPECT_EQ(14, patch.diff_len);
+ EXPECT_EQ(14U, patch.extra_len);
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/bspatch.1 b/bsdiff/bspatch.1
new file mode 100644
index 0000000..ecac8db
--- /dev/null
+++ b/bsdiff/bspatch.1
@@ -0,0 +1,77 @@
+.\"-
+.\" Copyright 2003-2005 Colin Percival
+.\" All rights reserved
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted providing that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\" notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\" notice, this list of conditions and the following disclaimer in the
+.\" documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+.\" WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+.\" DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+.\" IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+.\" POSSIBILITY OF SUCH DAMAGE.
+.\"
+.\" $FreeBSD: src/usr.bin/bsdiff/bspatch/bspatch.1,v 1.1 2005/08/06 01:59:06 cperciva Exp $
+.\"
+.Dd May 18, 2003
+.Dt BSPATCH 1
+.Os FreeBSD
+.Sh NAME
+.Nm bspatch
+.Nd apply a patch built with bsdiff(1)
+.Sh SYNOPSIS
+.Nm
+.Ar oldfile newfile patchfile
+.Op Ar old-extents new-extents
+.Sh DESCRIPTION
+.Nm
+generates
+.Ar newfile
+from
+.Ar oldfile
+and
+.Ar patchfile ,
+where
+.Ar patchfile
+is a binary patch built by
+.Xr bsdiff 1 .
+.Pp
+When provided,
+.Ar old-extents
+and
+.Ar new-extents
+instruct
+.Nm
+to read specific chunks of data from the old file and to write to specific
+locations in the new file, respectively. Each is a comma-separated list of
+extents of the form
+.Ar offset : Ns Ar length ,
+where
+.Ar offset
+is either -1 or a non-negative integer and
+.Ar length
+is a positive integer. An offset value of -1 denotes a sparse extent, namely a
+sequence of zeros that entails neither reading nor writing of actual file
+content.
+.Pp
+.Nm
+uses memory equal to the size of
+.Ar newfile ,
+but can tolerate a very small working set without a dramatic loss
+of performance.
+.Sh SEE ALSO
+.Xr bsdiff 1
+.Sh AUTHORS
+.An Colin Percival Aq cperciva@freebsd.org
diff --git a/bsdiff/bspatch.cc b/bsdiff/bspatch.cc
new file mode 100644
index 0000000..550c6c7
--- /dev/null
+++ b/bsdiff/bspatch.cc
@@ -0,0 +1,358 @@
+/*-
+ * Copyright 2003-2005 Colin Percival
+ * All rights reserved
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted providing that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+ * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#if 0
+__FBSDID("$FreeBSD: src/usr.bin/bsdiff/bspatch/bspatch.c,v 1.1 2005/08/06 01:59:06 cperciva Exp $");
+#endif
+
+#include "bspatch.h"
+
+#include <bzlib.h>
+#include <err.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <inttypes.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <algorithm>
+#include <memory>
+#include <limits>
+#include <vector>
+
+#include "extents.h"
+#include "extents_file.h"
+#include "file.h"
+#include "file_interface.h"
+#include "memory_file.h"
+
+namespace {
+
+int64_t ParseInt64(u_char* buf) {
+ int64_t y;
+
+ y = buf[7] & 0x7F;
+ y = y * 256;
+ y += buf[6];
+ y = y * 256;
+ y += buf[5];
+ y = y * 256;
+ y += buf[4];
+ y = y * 256;
+ y += buf[3];
+ y = y * 256;
+ y += buf[2];
+ y = y * 256;
+ y += buf[1];
+ y = y * 256;
+ y += buf[0];
+
+ if (buf[7] & 0x80)
+ y = -y;
+
+ return y;
+}
+
+bool ReadBZ2(BZFILE* pfbz2, uint8_t* data, size_t size) {
+ int bz2err;
+ size_t lenread = BZ2_bzRead(&bz2err, pfbz2, data, size);
+ if (lenread < size || (bz2err != BZ_OK && bz2err != BZ_STREAM_END))
+ return false;
+ return true;
+}
+
+bool ReadBZ2AndWriteAll(const std::unique_ptr<bsdiff::FileInterface>& file,
+ BZFILE* pfbz2,
+ size_t size,
+ uint8_t* buf,
+ size_t buf_size) {
+ while (size > 0) {
+ size_t bytes_to_read = std::min(size, buf_size);
+ if (!ReadBZ2(pfbz2, buf, bytes_to_read))
+ return false;
+ if (!WriteAll(file, buf, bytes_to_read))
+ return false;
+ size -= bytes_to_read;
+ }
+ return true;
+}
+
+} // namespace
+
+namespace bsdiff {
+
+bool WriteAll(const std::unique_ptr<FileInterface>& file,
+ const uint8_t* data,
+ size_t size) {
+ size_t offset = 0, written;
+ while (offset < size) {
+ if (!file->Write(data + offset, size - offset, &written) || written == 0)
+ return false;
+ offset += written;
+ }
+ return true;
+}
+
+bool IsOverlapping(const char* old_filename,
+ const char* new_filename,
+ const std::vector<ex_t>& old_extents,
+ const std::vector<ex_t>& new_extents) {
+ struct stat old_stat, new_stat;
+ if (stat(new_filename, &new_stat) == -1) {
+ if (errno == ENOENT)
+ return false;
+ err(1, "Error stat the new filename %s", new_filename);
+ }
+ if (stat(old_filename, &old_stat) == -1)
+ err(1, "Error stat the old filename %s", old_filename);
+
+ if (old_stat.st_dev != new_stat.st_dev || old_stat.st_ino != new_stat.st_ino)
+ return false;
+
+ if (old_extents.empty() && new_extents.empty())
+ return true;
+
+ for (ex_t old_ex : old_extents)
+ for (ex_t new_ex : new_extents)
+ if (static_cast<uint64_t>(old_ex.off) < new_ex.off + new_ex.len &&
+ static_cast<uint64_t>(new_ex.off) < old_ex.off + old_ex.len)
+ return true;
+
+ return false;
+}
+
+int bspatch(
+ const char* old_filename, const char* new_filename,
+ const char* patch_filename,
+ const char* old_extents, const char* new_extents) {
+ FILE* f, *cpf, *dpf, *epf;
+ BZFILE* cpfbz2, *dpfbz2, *epfbz2;
+ int bz2err;
+ ssize_t bzctrllen, bzdatalen;
+ u_char header[32], buf[8];
+ off_t ctrl[3];
+
+ int using_extents = (old_extents != NULL || new_extents != NULL);
+
+ // Open patch file.
+ if ((f = fopen(patch_filename, "r")) == NULL)
+ err(1, "fopen(%s)", patch_filename);
+
+ // File format:
+ // 0 8 "BSDIFF40"
+ // 8 8 X
+ // 16 8 Y
+ // 24 8 sizeof(new_filename)
+ // 32 X bzip2(control block)
+ // 32+X Y bzip2(diff block)
+ // 32+X+Y ??? bzip2(extra block)
+ // with control block a set of triples (x,y,z) meaning "add x bytes
+ // from oldfile to x bytes from the diff block; copy y bytes from the
+ // extra block; seek forwards in oldfile by z bytes".
+
+ // Read header.
+ if (fread(header, 1, 32, f) < 32) {
+ if (feof(f))
+ errx(1, "Corrupt patch\n");
+ err(1, "fread(%s)", patch_filename);
+ }
+
+ // Check for appropriate magic.
+ if (memcmp(header, "BSDIFF40", 8) != 0)
+ errx(1, "Corrupt patch\n");
+
+ // Read lengths from header.
+ uint64_t oldsize, newsize;
+ bzctrllen = ParseInt64(header + 8);
+ bzdatalen = ParseInt64(header + 16);
+ int64_t signed_newsize = ParseInt64(header + 24);
+ newsize = signed_newsize;
+ if ((bzctrllen < 0) || (bzdatalen < 0) || (signed_newsize < 0))
+ errx(1, "Corrupt patch\n");
+
+ // Close patch file and re-open it via libbzip2 at the right places.
+ if (fclose(f))
+ err(1, "fclose(%s)", patch_filename);
+ if ((cpf = fopen(patch_filename, "r")) == NULL)
+ err(1, "fopen(%s)", patch_filename);
+ if (fseek(cpf, 32, SEEK_SET))
+ err(1, "fseeko(%s, %lld)", patch_filename, (long long)32);
+ if ((cpfbz2 = BZ2_bzReadOpen(&bz2err, cpf, 0, 0, NULL, 0)) == NULL)
+ errx(1, "BZ2_bzReadOpen, bz2err = %d", bz2err);
+ if ((dpf = fopen(patch_filename, "r")) == NULL)
+ err(1, "fopen(%s)", patch_filename);
+ if (fseek(dpf, 32 + bzctrllen, SEEK_SET))
+ err(1, "fseeko(%s, %lld)", patch_filename, (long long)(32 + bzctrllen));
+ if ((dpfbz2 = BZ2_bzReadOpen(&bz2err, dpf, 0, 0, NULL, 0)) == NULL)
+ errx(1, "BZ2_bzReadOpen, bz2err = %d", bz2err);
+ if ((epf = fopen(patch_filename, "r")) == NULL)
+ err(1, "fopen(%s)", patch_filename);
+ if (fseek(epf, 32 + bzctrllen + bzdatalen, SEEK_SET))
+ err(1, "fseeko(%s, %lld)", patch_filename,
+ (long long)(32 + bzctrllen + bzdatalen));
+ if ((epfbz2 = BZ2_bzReadOpen(&bz2err, epf, 0, 0, NULL, 0)) == NULL)
+ errx(1, "BZ2_bzReadOpen, bz2err = %d", bz2err);
+
+ // Open input file for reading.
+ std::unique_ptr<FileInterface> old_file = File::FOpen(old_filename, O_RDONLY);
+ if (!old_file)
+ err(1, "Error opening the old filename");
+
+ std::vector<ex_t> parsed_old_extents;
+ if (using_extents) {
+ if (!ParseExtentStr(old_extents, &parsed_old_extents))
+ errx(1, "Error parsing the old extents");
+ old_file.reset(new ExtentsFile(std::move(old_file), parsed_old_extents));
+ }
+
+ if (!old_file->GetSize(&oldsize))
+ err(1, "cannot obtain the size of %s", old_filename);
+ uint64_t old_file_pos = 0;
+
+ // Open output file for writing.
+ std::unique_ptr<FileInterface> new_file =
+ File::FOpen(new_filename, O_CREAT | O_WRONLY);
+ if (!new_file)
+ err(1, "Error opening the new filename %s", new_filename);
+
+ std::vector<ex_t> parsed_new_extents;
+ if (using_extents) {
+ if (!ParseExtentStr(new_extents, &parsed_new_extents))
+ errx(1, "Error parsing the new extents");
+ new_file.reset(new ExtentsFile(std::move(new_file), parsed_new_extents));
+ }
+
+ if (IsOverlapping(old_filename, new_filename, parsed_old_extents,
+ parsed_new_extents)) {
+ // New and old file is overlapping, we can not stream output to new file,
+ // cache it in the memory and write to the file at the end.
+ new_file.reset(new MemoryFile(std::move(new_file), newsize));
+ }
+
+ // The oldpos can be negative, but the new pos is only incremented linearly.
+ int64_t oldpos = 0;
+ uint64_t newpos = 0;
+ std::vector<uint8_t> old_buf(1024 * 1024), new_buf(1024 * 1024);
+ while (newpos < newsize) {
+ int64_t i;
+ // Read control data.
+ for (i = 0; i <= 2; i++) {
+ if (!ReadBZ2(cpfbz2, buf, 8))
+ errx(1, "Corrupt patch\n");
+ ctrl[i] = ParseInt64(buf);
+ }
+
+ // Sanity-check.
+ if (ctrl[0] < 0 || ctrl[1] < 0)
+ errx(1, "Corrupt patch\n");
+
+ // Sanity-check.
+ if (newpos + ctrl[0] > newsize)
+ errx(1, "Corrupt patch\n");
+
+ // Add old data to diff string. It is enough to fseek once, at
+ // the beginning of the sequence, to avoid unnecessary overhead.
+ if ((i = oldpos) < 0) {
+ // Write diff block directly to new file without adding old data,
+ // because we will skip part where |oldpos| < 0.
+ if (!ReadBZ2AndWriteAll(new_file, dpfbz2, -i, new_buf.data(),
+ new_buf.size()))
+ errx(1, "Error during ReadBZ2AndWriteAll()");
+
+ i = 0;
+ }
+
+ // We just checked that |i| is not negative.
+ if (static_cast<uint64_t>(i) != old_file_pos && !old_file->Seek(i))
+ err(1, "error seeking input file to offset %" PRId64, i);
+ if ((old_file_pos = oldpos + ctrl[0]) > oldsize)
+ old_file_pos = oldsize;
+
+ size_t chunk_size = old_file_pos - i;
+ while (chunk_size > 0) {
+ size_t read_bytes;
+ size_t bytes_to_read = std::min(chunk_size, old_buf.size());
+ if (!old_file->Read(old_buf.data(), bytes_to_read, &read_bytes))
+ err(1, "error reading from input file");
+ if (!read_bytes)
+ errx(1, "EOF reached while reading from input file");
+ // Read same amount of bytes from diff block
+ if (!ReadBZ2(dpfbz2, new_buf.data(), read_bytes))
+ errx(1, "Corrupt patch\n");
+ // new_buf already has data from diff block, adds old data to it.
+ for (size_t k = 0; k < read_bytes; k++)
+ new_buf[k] += old_buf[k];
+ if (!WriteAll(new_file, new_buf.data(), read_bytes))
+ err(1, "Error writing new file.");
+ chunk_size -= read_bytes;
+ }
+
+ // Adjust pointers.
+ newpos += ctrl[0];
+ oldpos += ctrl[0];
+
+ if (oldpos > static_cast<int64_t>(oldsize)) {
+ // Write diff block directly to new file without adding old data,
+ // because we skipped part where |oldpos| > oldsize.
+ if (!ReadBZ2AndWriteAll(new_file, dpfbz2, oldpos - oldsize,
+ new_buf.data(), new_buf.size()))
+ errx(1, "Error during ReadBZ2AndWriteAll()");
+ }
+
+ // Sanity-check.
+ if (newpos + ctrl[1] > newsize)
+ errx(1, "Corrupt patch\n");
+
+ // Read extra block.
+ if (!ReadBZ2AndWriteAll(new_file, epfbz2, ctrl[1], new_buf.data(),
+ new_buf.size()))
+ errx(1, "Error during ReadBZ2AndWriteAll()");
+
+ // Adjust pointers.
+ newpos += ctrl[1];
+ oldpos += ctrl[2];
+ }
+
+ // Close input file.
+ old_file->Close();
+
+ // Clean up the bzip2 reads.
+ BZ2_bzReadClose(&bz2err, cpfbz2);
+ BZ2_bzReadClose(&bz2err, dpfbz2);
+ BZ2_bzReadClose(&bz2err, epfbz2);
+ if (fclose(cpf) || fclose(dpf) || fclose(epf))
+ err(1, "fclose(%s)", patch_filename);
+
+ if (!new_file->Close())
+ err(1, "Error closing new file %s", new_filename);
+
+ return 0;
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/bspatch.h b/bsdiff/bspatch.h
new file mode 100644
index 0000000..3de2874
--- /dev/null
+++ b/bsdiff/bspatch.h
@@ -0,0 +1,32 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef _BSDIFF_BSPATCH_H_
+#define _BSDIFF_BSPATCH_H_
+
+#include <memory>
+#include <vector>
+
+#include "extents_file.h"
+
+namespace bsdiff {
+
+int bspatch(const char* old_filename,
+ const char* new_filename,
+ const char* patch_filename,
+ const char* old_extents,
+ const char* new_extents);
+
+bool WriteAll(const std::unique_ptr<FileInterface>& file,
+ const uint8_t* data,
+ size_t size);
+
+bool IsOverlapping(const char* old_filename,
+ const char* new_filename,
+ const std::vector<ex_t>& old_extents,
+ const std::vector<ex_t>& new_extents);
+
+} // namespace bsdiff
+
+#endif // _BSDIFF_BSPATCH_H_
diff --git a/bsdiff/bspatch_main.cc b/bsdiff/bspatch_main.cc
new file mode 100644
index 0000000..51ceebd
--- /dev/null
+++ b/bsdiff/bspatch_main.cc
@@ -0,0 +1,27 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <err.h>
+#include <stdlib.h>
+
+#include "bspatch.h"
+
+#define USAGE_TEMPLATE_STR \
+ "usage: %s oldfile newfile patchfile [old-extents new-extents]\n" \
+ "with extents taking the form \"off_1:len_1,...,off_n:len_n\"\n"
+
+int main(int argc, char* argv[]) {
+ const char* old_extents = NULL;
+ const char* new_extents = NULL;
+
+ if ((argc != 6) && (argc != 4))
+ errx(1, USAGE_TEMPLATE_STR, argv[0]);
+
+ if (argc == 6) {
+ old_extents = argv[4];
+ new_extents = argv[5];
+ }
+
+ return bsdiff::bspatch(argv[1], argv[2], argv[3], old_extents, new_extents);
+}
diff --git a/bsdiff/bspatch_unittest.cc b/bsdiff/bspatch_unittest.cc
new file mode 100644
index 0000000..04ec666
--- /dev/null
+++ b/bsdiff/bspatch_unittest.cc
@@ -0,0 +1,42 @@
+// Copyright 2016 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "bspatch.h"
+
+#include <unistd.h>
+
+#include <gtest/gtest.h>
+
+#include "test_utils.h"
+
+namespace bsdiff {
+
+class BspatchTest : public testing::Test {
+ protected:
+ BspatchTest()
+ : old_file_("bsdiff_oldfile.XXXXXX"),
+ new_file_("bsdiff_newfile.XXXXXX") {}
+
+ test_utils::ScopedTempFile old_file_;
+ test_utils::ScopedTempFile new_file_;
+};
+
+TEST_F(BspatchTest, IsOverlapping) {
+ const char* old_filename = old_file_.c_str();
+ const char* new_filename = new_file_.c_str();
+ EXPECT_FALSE(IsOverlapping(old_filename, "does-not-exist", {}, {}));
+ EXPECT_FALSE(IsOverlapping(old_filename, new_filename, {}, {}));
+ EXPECT_EQ(0, unlink(new_filename));
+ EXPECT_EQ(0, symlink(old_filename, new_filename));
+ EXPECT_TRUE(IsOverlapping(old_filename, new_filename, {}, {}));
+ EXPECT_TRUE(IsOverlapping(old_filename, old_filename, {}, {}));
+ EXPECT_FALSE(IsOverlapping(old_filename, old_filename, {{0, 1}}, {{1, 1}}));
+ EXPECT_FALSE(IsOverlapping(old_filename, old_filename, {{2, 1}}, {{1, 1}}));
+ EXPECT_TRUE(IsOverlapping(old_filename, old_filename, {{0, 1}}, {{0, 1}}));
+ EXPECT_TRUE(IsOverlapping(old_filename, old_filename, {{0, 4}}, {{2, 1}}));
+ EXPECT_TRUE(IsOverlapping(old_filename, old_filename, {{1, 1}}, {{0, 2}}));
+ EXPECT_TRUE(IsOverlapping(old_filename, old_filename, {{3, 2}}, {{2, 2}}));
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/extents.cc b/bsdiff/extents.cc
new file mode 100644
index 0000000..52cf404
--- /dev/null
+++ b/bsdiff/extents.cc
@@ -0,0 +1,113 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "extents.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <limits.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#include <algorithm>
+#include <limits>
+
+namespace bsdiff {
+
+/* The maximum accepted value for a given integer type when parsed as a signed
+ * long long integer. This is defined to be the smaller of the maximum value
+ * that can be represented by this type and LLONG_MAX. This bound allows us to
+ * properly check that parsed values do not exceed the capacity of their
+ * intended store, regardless of how its size relates to that of a signed long
+ * long integer. Note: this may mean that we are losing the most significant
+ * bit of an unsigned 64-bit field (e.g. size_t on some platforms), however
+ * still permitting values up to 2^62, which is more than enough for all
+ * practical purposes. */
+#define MAX_ALLOWED(t) \
+ (std::min(static_cast<uint64_t>(std::numeric_limits<t>::max()), \
+ static_cast<uint64_t>(std::numeric_limits<long long>::max())))
+
+/* Get the type of a struct field. */
+#define FIELD_TYPE(t, f) decltype(((t*)0)->f)
+
+
+/* Reads a long long integer from |s| into |*val_p|. Returns a pointer to the
+ * character immediately following the specified |delim|, unless (a) parsing
+ * failed (overflow or no valid digits); (b) the read value is less than
+ * |min_val| or greater than |max_val|; (c) the delimiter character is not
+ * |delim|, or the string ends although |may_end| is false. In any of these
+ * cases, returns NULL. */
+const char* read_llong(const char* s,
+ long long* val_p,
+ long long min_val,
+ long long max_val,
+ char delim,
+ int may_end) {
+ assert(val_p);
+ const char* next_s;
+ errno = 0;
+ long long val = strtoll(s, (char**)&next_s, 10);
+ if (((val == LLONG_MAX || val == LLONG_MIN) && errno == ERANGE) ||
+ next_s == s || val < min_val || val > max_val ||
+ (*next_s ? *next_s != delim : !may_end))
+ return NULL; /* bad value or delimiter */
+ *val_p = val;
+ if (*next_s)
+ next_s++; /* skip delimeter */
+ return next_s;
+}
+
+
+/* Reads a comma-separated list of "offset:length" extents from |ex_str|. If
+ * |ex_arr| is NULL, then |ex_count| is ignored and it attempts to parse valid
+ * extents until the end of the string is reached. Otherwise, stores up to
+ * |ex_count| extents into |ex_arr|, which must be of at least this size.
+ * Returns the number of correctly parsed extents, or -1 if a malformed extent
+ * was found. */
+static ssize_t extents_read(const char* ex_str, ex_t* ex_arr, size_t ex_count) {
+ size_t i;
+ size_t last_i = ex_count - 1;
+ if (!ex_arr) {
+ ex_count = SIZE_MAX;
+ last_i = 0;
+ }
+ for (i = 0; *ex_str && i < ex_count; i++) {
+ long long raw_off = 0, raw_len = 0;
+ if (!((ex_str =
+ read_llong(ex_str, &raw_off, -1,
+ MAX_ALLOWED(FIELD_TYPE(ex_t, off)), ':', false)) &&
+ (ex_str = read_llong(ex_str, &raw_len, 1,
+ MAX_ALLOWED(FIELD_TYPE(ex_t, len)), ',',
+ i >= last_i))))
+ return -1; /* parsing error */
+ if (ex_arr) {
+ ex_arr[i].off = raw_off;
+ ex_arr[i].len = raw_len;
+ }
+ }
+ return i;
+}
+
+
+bool ParseExtentStr(const char* ex_str, std::vector<ex_t>* extents) {
+ // Sanity check: a string must be provided.
+ if (!ex_str)
+ return false;
+
+ /* Parse string and count extents. */
+ ssize_t ret = extents_read(ex_str, NULL, 0);
+ if (ret < 0)
+ return false; // parsing error.
+
+ // Input is good, commit to extent count.
+ extents->resize(ret);
+ if (ret == 0)
+ return true; // No extents, nothing to do.
+
+ // Populate the extent array.
+ extents_read(ex_str, extents->data(), extents->size());
+ return true;
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/extents.h b/bsdiff/extents.h
new file mode 100644
index 0000000..de3eb27
--- /dev/null
+++ b/bsdiff/extents.h
@@ -0,0 +1,23 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef _BSDIFF_EXTENTS_H_
+#define _BSDIFF_EXTENTS_H_
+
+#include <vector>
+
+#include "extents_file.h"
+
+namespace bsdiff {
+
+// Parses a string representation |ex_str| and populates the vector |extents|
+// of ex_t. The string is expected to be a comma-separated list of pairs of the
+// form "offset:length". An offset may be -1 or a non-negative integer; the
+// former indicates a sparse extent (consisting of zeros). A length is a
+// positive integer. Returns whether the parsing was successful.
+bool ParseExtentStr(const char* ex_str, std::vector<ex_t>* extents);
+
+} // namespace bsdiff
+
+#endif // _BSDIFF_EXTENTS_H_
diff --git a/bsdiff/extents_file.cc b/bsdiff/extents_file.cc
new file mode 100644
index 0000000..01d31a6
--- /dev/null
+++ b/bsdiff/extents_file.cc
@@ -0,0 +1,117 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "extents_file.h"
+
+#include <string.h>
+
+#include <algorithm>
+
+// Extent files implementation extending FileInterface.
+//
+// This class allows to map linear positions in a file to a list of regions in
+// another file. All the reads and writes are unbuffered, passed directly to the
+// underlying file. Seeking is done in O(log(N)), where N is the number of
+// extents in the file, but sequential reads jump to the next extent in O(1).
+
+namespace bsdiff {
+
+ExtentsFile::ExtentsFile(std::unique_ptr<FileInterface> file,
+ const std::vector<ex_t>& extents)
+ : file_(std::move(file)), extents_(extents) {
+ acc_len_.reserve(extents.size());
+ for (const ex_t& extent : extents) {
+ acc_len_.push_back(total_ex_len_);
+ total_ex_len_ += extent.len;
+ }
+}
+
+ExtentsFile::~ExtentsFile() {
+ Close();
+}
+
+bool ExtentsFile::Read(void* buf, size_t count, size_t* bytes_read) {
+ return IOOperation(&FileInterface::Read, buf, count, bytes_read);
+}
+
+
+bool ExtentsFile::Write(const void* buf, size_t count, size_t* bytes_written) {
+ return IOOperation(&FileInterface::Write, buf, count, bytes_written);
+}
+
+bool ExtentsFile::Seek(off_t pos) {
+ if (pos < 0 || static_cast<uint64_t>(pos) > total_ex_len_)
+ return false;
+ if (acc_len_.empty())
+ return true;
+ // Note that the first element of acc_len_ is always 0, and pos is at least 0,
+ // so the upper_bound will never return acc_len_.begin().
+ curr_pos_ = pos;
+ curr_ex_idx_ = std::upper_bound(acc_len_.begin(), acc_len_.end(), pos) -
+ acc_len_.begin();
+ // We handle the corner case where |pos| is the size of all the extents by
+ // leaving the value of curr_ex_idx_ the same way AdvancePos(0) would leave it
+ // after the seek.
+ if (curr_pos_ < total_ex_len_)
+ curr_ex_idx_--;
+ return true;
+}
+
+bool ExtentsFile::Close() {
+ return file_->Close();
+}
+
+bool ExtentsFile::GetSize(uint64_t* size) {
+ *size = total_ex_len_;
+ return true;
+}
+
+void ExtentsFile::AdvancePos(uint64_t size) {
+ curr_pos_ += size;
+ for (; curr_ex_idx_ < extents_.size(); curr_ex_idx_++) {
+ if (curr_pos_ < acc_len_[curr_ex_idx_] + extents_[curr_ex_idx_].len)
+ return;
+ }
+ return;
+}
+
+template <typename T>
+bool ExtentsFile::IOOperation(bool (FileInterface::*io_op)(T*, size_t, size_t*),
+ T* buf,
+ size_t count,
+ size_t* bytes_processed) {
+ bool result = true;
+ size_t processed = 0;
+ AdvancePos(0);
+ while (count > 0 && curr_ex_idx_ < extents_.size()) {
+ const ex_t& ex = extents_[curr_ex_idx_];
+ off_t curr_ex_off = curr_pos_ - acc_len_[curr_ex_idx_];
+ size_t chunk_size =
+ std::min(static_cast<uint64_t>(count), ex.len - curr_ex_off);
+ size_t chunk_processed = 0;
+ if (ex.off < 0) {
+ chunk_processed = chunk_size;
+ } else {
+ if (!file_->Seek(ex.off + curr_ex_off) ||
+ !(file_.get()->*io_op)(buf, chunk_size, &chunk_processed)) {
+ processed += chunk_processed;
+ result = processed > 0;
+ break;
+ }
+ }
+ processed += chunk_processed;
+ count -= chunk_processed;
+ // T can be either const void* or void*. We const_cast it back to void* and
+ // then char* to do the arithmetic operation, but |buf| will continue to be
+ // const void* if it was defined that way.
+ buf = static_cast<char*>(const_cast<void*>(buf)) + chunk_processed;
+ AdvancePos(chunk_processed);
+ if (!chunk_processed)
+ break;
+ }
+ *bytes_processed = processed;
+ return result;
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/extents_file.h b/bsdiff/extents_file.h
new file mode 100644
index 0000000..865e2a2
--- /dev/null
+++ b/bsdiff/extents_file.h
@@ -0,0 +1,92 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef _BSDIFF_EXTENTS_FILE_H_
+#define _BSDIFF_EXTENTS_FILE_H_
+
+#include <stdio.h>
+
+#include <memory>
+#include <vector>
+
+#include "file_interface.h"
+
+/*
+ * Extent files.
+ *
+ * This modules provides a familiar interface for handling files through an
+ * indirection layer of extents, which are contiguous chunks of variable length
+ * at arbitrary offsets within a file. Once an extent file handle is obtained,
+ * users may read, write and seek as they do with ordinary files, having the I/O
+ * with the underlying file done for them by the extent file implementation. The
+ * implementation supports "sparse extents", which are assumed to contain zeros
+ * but otherwise have no actual representation in the underlying file; these are
+ * denoted by negative offset values.
+ *
+ * Unlike ordinary files, the size of an extent file is fixed; it is not
+ * truncated on open, nor is writing past the extent span allowed. Also, writing
+ * to a sparse extent has no effect and will not raise an error.
+ */
+
+namespace bsdiff {
+
+/* An extent, defined by an offset and a length. */
+struct ex_t {
+ off_t off; // the extent offset; negative indicates a sparse extent.
+ uint64_t len; // the extent length.
+};
+
+class ExtentsFile : public FileInterface {
+ public:
+ // Creates an ExtentsFile based on the underlying |file| passed. The positions
+ // in the ExtentsFile will be linearly mapped to the extents provided in
+ // |extents|. The created ExtentsFile takes ownership of the |file| will close
+ // it on destruction.
+ ExtentsFile(std::unique_ptr<FileInterface> file,
+ const std::vector<ex_t>& extents);
+
+ ~ExtentsFile() override;
+
+ // FileInterface overrides.
+ bool Read(void* buf, size_t count, size_t* bytes_read) override;
+ bool Write(const void* buf, size_t count, size_t* bytes_written) override;
+ bool Seek(off_t pos) override;
+ bool Close() override;
+ bool GetSize(uint64_t* size) override;
+
+ private:
+ void AdvancePos(uint64_t size);
+
+ // Performs an I/O operation (either read or write). This template shares the
+ // code for both Read() and Write() implementations.
+ template <typename T>
+ bool IOOperation(bool (FileInterface::*io_op)(T*, size_t, size_t*),
+ T* buf,
+ size_t count,
+ size_t* bytes_processed);
+
+ // The underlying FileInterace instance.
+ std::unique_ptr<FileInterface> file_;
+
+ // The list of extents mapping this instance to |file_|.
+ const std::vector<ex_t> extents_;
+
+ // The accumulated length of the extents. The i-th element contains the sum of
+ // the length of all the extents from 0 up to but not including the i-th
+ // extent. This reduces the complexity for random-access Seek() calls.
+ std::vector<uint64_t> acc_len_;
+
+ // Current extent index.
+ size_t curr_ex_idx_{0};
+
+ // Current logical file position.
+ uint64_t curr_pos_{0};
+
+ // Total length of all extents (constant).
+ uint64_t total_ex_len_{0};
+};
+
+} // namespace bsdiff
+
+#endif // _BSDIFF_EXTENTS_FILE_H_
diff --git a/bsdiff/extents_file_unittest.cc b/bsdiff/extents_file_unittest.cc
new file mode 100644
index 0000000..73cedb2
--- /dev/null
+++ b/bsdiff/extents_file_unittest.cc
@@ -0,0 +1,211 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "extents_file.h"
+
+#include <gtest/gtest.h>
+#include <gmock/gmock.h>
+#include <string>
+#include <vector>
+
+#include "file_interface.h"
+
+using std::string;
+using std::vector;
+using testing::AnyNumber;
+using testing::StrictMock;
+using testing::Return;
+using testing::InSequence;
+using testing::_;
+
+namespace bsdiff {
+
+// Mock class for the underlying file interface.
+class MockFile : public FileInterface {
+ public:
+ MOCK_METHOD3(Read, bool(void*, size_t, size_t*));
+ MOCK_METHOD3(Write, bool(const void*, size_t, size_t*));
+ MOCK_METHOD1(Seek, bool(off_t));
+ MOCK_METHOD0(Close, bool());
+ MOCK_METHOD1(GetSize, bool(uint64_t*));
+};
+
+ACTION(SucceedIO) {
+ // Check that arg1 (count) can be converted
+ *arg2 = arg1;
+ return true;
+}
+
+ACTION_P(SucceedPartialIO, bytes) {
+ // Check that arg1 (count) can be converted
+ *arg2 = bytes;
+ return true;
+}
+
+class ExtentsFileTest : public testing::Test {
+ protected:
+ void SetUp() {
+ mock_file_ = new StrictMock<MockFile>();
+ mock_file_ptr_.reset(mock_file_);
+ // The destructor of the ExtentsFile will call Close once.
+ EXPECT_CALL(*mock_file_, Close()).WillOnce(Return(true));
+ }
+
+ // Pointer to the underlying File owned by the ExtentsFile under test. This
+ // pointer is invalidated whenever the ExtentsFile is destroyed.
+ StrictMock<MockFile>* mock_file_;
+ std::unique_ptr<FileInterface> mock_file_ptr_;
+};
+
+TEST_F(ExtentsFileTest, DestructorCloses) {
+ ExtentsFile file(std::move(mock_file_ptr_), {});
+}
+
+TEST_F(ExtentsFileTest, CloseIsForwarded) {
+ ExtentsFile file(std::move(mock_file_ptr_), {});
+ EXPECT_TRUE(file.Close());
+ EXPECT_CALL(*mock_file_, Close()).WillOnce(Return(false));
+}
+
+TEST_F(ExtentsFileTest, GetSizeSumExtents) {
+ ExtentsFile file(std::move(mock_file_ptr_),
+ {ex_t{10, 5}, ex_t{20, 5}, {25, 2}});
+ uint64_t size;
+ EXPECT_TRUE(file.GetSize(&size));
+ EXPECT_EQ(12U, size);
+}
+
+TEST_F(ExtentsFileTest, SeekToRightOffsets) {
+ ExtentsFile file(std::move(mock_file_ptr_),
+ {ex_t{10, 5}, ex_t{20, 5}, {25, 2}});
+ vector<std::pair<off_t, off_t>> tests = {
+ // Seek to the beginning of the file.
+ {0, 10},
+ // Seek to the middle of a extent.
+ {3, 13},
+ {11, 26},
+ // Seek to the extent boundary.
+ {5, 20}, // Seeks to the first byte in the second extent.
+ {10, 25},
+ };
+ for (const auto& offset_pair : tests) {
+ // We use a failing Read() call to trigger the actual seek call to the
+ // underlying file.
+ EXPECT_CALL(*mock_file_, Seek(offset_pair.second)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(_, _, _)).WillOnce(Return(false));
+
+ EXPECT_TRUE(file.Seek(offset_pair.first));
+ size_t bytes_read;
+ EXPECT_FALSE(file.Read(nullptr, 1, &bytes_read));
+ }
+
+ // Seeking to the end of the file is ok, but not past it.
+ EXPECT_TRUE(file.Seek(12));
+ EXPECT_FALSE(file.Seek(13));
+
+ EXPECT_FALSE(file.Seek(-1));
+}
+
+TEST_F(ExtentsFileTest, ReadAcrossAllExtents) {
+ ExtentsFile file(std::move(mock_file_ptr_),
+ {ex_t{10, 5}, ex_t{20, 7}, {27, 3}});
+ InSequence s;
+ char* buf = reinterpret_cast<char*>(0x1234);
+
+ EXPECT_CALL(*mock_file_, Seek(10)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf, 5, _)).WillOnce(SucceedIO());
+ EXPECT_CALL(*mock_file_, Seek(20)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf + 5, 7, _)).WillOnce(SucceedIO());
+ EXPECT_CALL(*mock_file_, Seek(27)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf + 12, 3, _)).WillOnce(SucceedIO());
+
+ // FileExtents::Read() should read everything in one shot, by reading all
+ // the little chunks. Note that it doesn't attempt to read past the end of the
+ // FileExtents.
+ size_t bytes_read = 0;
+ EXPECT_TRUE(file.Read(buf, 100, &bytes_read));
+ EXPECT_EQ(15U, bytes_read);
+}
+
+TEST_F(ExtentsFileTest, MultiReadAcrossAllExtents) {
+ ExtentsFile file(std::move(mock_file_ptr_),
+ {ex_t{10, 5}, ex_t{20, 7}, {27, 3}});
+ InSequence s;
+ char* buf = reinterpret_cast<char*>(0x1234);
+
+ EXPECT_CALL(*mock_file_, Seek(10)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf, 2, _)).WillOnce(SucceedIO());
+ EXPECT_CALL(*mock_file_, Seek(12)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf, 3, _)).WillOnce(SucceedIO());
+ EXPECT_CALL(*mock_file_, Seek(20)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf + 3, 5, _)).WillOnce(SucceedIO());
+ EXPECT_CALL(*mock_file_, Seek(25)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf, 2, _)).WillOnce(SucceedIO());
+ EXPECT_CALL(*mock_file_, Seek(27)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf + 2, 3, _)).WillOnce(SucceedIO());
+
+ size_t bytes_read = 0;
+ EXPECT_TRUE(file.Read(buf, 2, &bytes_read));
+ EXPECT_EQ(2U, bytes_read);
+ EXPECT_TRUE(file.Read(buf, 8, &bytes_read));
+ EXPECT_EQ(8U, bytes_read);
+ EXPECT_TRUE(file.Read(buf, 100, &bytes_read));
+ EXPECT_EQ(5U, bytes_read);
+}
+
+TEST_F(ExtentsFileTest, ReadSmallChunks) {
+ ExtentsFile file(std::move(mock_file_ptr_), {ex_t{10, 1}, ex_t{20, 10}});
+ InSequence s;
+ char* buf = reinterpret_cast<char*>(0x1234);
+
+ EXPECT_CALL(*mock_file_, Seek(10)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(buf, 1, _)).WillOnce(SucceedIO());
+ EXPECT_CALL(*mock_file_, Seek(20)).WillOnce(Return(true));
+ // We expect to read only part of the second extent.
+ EXPECT_CALL(*mock_file_, Read(buf + 1, 1, _)).WillOnce(SucceedIO());
+
+ size_t bytes_read = 0;
+ EXPECT_TRUE(file.Read(buf, 2, &bytes_read));
+ EXPECT_EQ(2U, bytes_read);
+}
+
+TEST_F(ExtentsFileTest, ReadFailureFails) {
+ ExtentsFile file(std::move(mock_file_ptr_), {ex_t{10, 1}, ex_t{20, 10}});
+ EXPECT_CALL(*mock_file_, Seek(_))
+ .Times(AnyNumber())
+ .WillRepeatedly(Return(true));
+ EXPECT_CALL(*mock_file_, Read(_, 1, _)).WillOnce(SucceedIO());
+ // A second read that fails will succeed if there was partial data read.
+ EXPECT_CALL(*mock_file_, Read(_, 10, _)).WillOnce(Return(false));
+
+ size_t bytes_read = 0;
+ EXPECT_TRUE(file.Read(nullptr, 100, &bytes_read));
+ EXPECT_EQ(1U, bytes_read);
+}
+
+TEST_F(ExtentsFileTest, ReadFails) {
+ ExtentsFile file(std::move(mock_file_ptr_), {ex_t{10, 1}, ex_t{20, 10}});
+ EXPECT_CALL(*mock_file_, Seek(10)).WillOnce(Return(true));
+ EXPECT_CALL(*mock_file_, Read(_, 1, _)).WillOnce(Return(false));
+ size_t bytes_read;
+ EXPECT_FALSE(file.Read(nullptr, 1, &bytes_read));
+}
+
+TEST_F(ExtentsFileTest, ReadPartialReadsAndEOF) {
+ ExtentsFile file(std::move(mock_file_ptr_), {ex_t{10, 1}, ex_t{20, 10}});
+ EXPECT_CALL(*mock_file_, Seek(_))
+ .Times(AnyNumber())
+ .WillRepeatedly(Return(true));
+ char* buf = reinterpret_cast<char*>(0x1234);
+ InSequence s;
+ EXPECT_CALL(*mock_file_, Read(buf, 1, _)).WillOnce(SucceedIO());
+ EXPECT_CALL(*mock_file_, Read(buf + 1, _, _)).WillOnce(SucceedPartialIO(3));
+ EXPECT_CALL(*mock_file_, Read(buf + 4, _, _)).WillOnce(SucceedPartialIO(0));
+
+ size_t bytes_read = 0;
+ EXPECT_TRUE(file.Read(buf, 100, &bytes_read));
+ EXPECT_EQ(4U, bytes_read);
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/extents_unittest.cc b/bsdiff/extents_unittest.cc
new file mode 100644
index 0000000..84be2e1
--- /dev/null
+++ b/bsdiff/extents_unittest.cc
@@ -0,0 +1,56 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "extents.h"
+
+#include <gtest/gtest.h>
+#include <vector>
+
+namespace bsdiff {
+
+// ex_t comparator used for testing.
+bool operator==(const struct ex_t& lhs, const struct ex_t& rhs) {
+ return lhs.off == rhs.off && lhs.len == rhs.len;
+}
+
+// PrintTo is used by gtest framework whenever it needs to print our type.
+void PrintTo(const struct ex_t& extent, ::std::ostream* os) {
+ *os << extent.off << ":" << extent.len;
+}
+
+class ExtentsTest : public testing::Test {
+ protected:
+ std::vector<ex_t> extents_;
+};
+
+TEST_F(ExtentsTest, CornerCasesHandledTest) {
+ EXPECT_TRUE(ParseExtentStr("", &extents_));
+ EXPECT_TRUE(extents_.empty());
+}
+
+TEST_F(ExtentsTest, SimpleCasesTest) {
+ EXPECT_TRUE(ParseExtentStr("10:20,30:40", &extents_));
+ std::vector<ex_t> expected_values = {{10, 20}, {30, 40}};
+ EXPECT_EQ(expected_values, extents_);
+}
+
+TEST_F(ExtentsTest, MalformedExtentsTest) {
+ std::vector<const char*> test_cases = {
+ ":", ",", "1,2", "1:", "1,", ":2", ",2", "1,2:3", "10:-1", "-2:10"};
+ for (const char* test_case : test_cases) {
+ std::vector<ex_t> extents;
+ EXPECT_FALSE(ParseExtentStr(test_case, &extents)) << "while testing case \""
+ << test_case << "\"";
+ EXPECT_EQ(std::vector<ex_t>(), extents);
+ }
+}
+
+TEST_F(ExtentsTest, NegativeValuesTest) {
+ // |-1| is used as a special case to read zeros for that extent.
+ EXPECT_TRUE(ParseExtentStr("10:20,-1:40,50:60", &extents_));
+ std::vector<ex_t> expected_values = {{10, 20}, {-1, 40}, {50, 60}};
+ EXPECT_EQ(expected_values, extents_);
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/file.cc b/bsdiff/file.cc
new file mode 100644
index 0000000..11b6104
--- /dev/null
+++ b/bsdiff/file.cc
@@ -0,0 +1,131 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "file.h"
+
+#include <errno.h>
+#include <fcntl.h>
+#ifdef __linux__
+#include <linux/fs.h>
+#endif // __linux__
+#include <string.h>
+#include <sys/ioctl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+// TEMP_FAILURE_RETRY is defined by some versions of <unistd.h>.
+#ifndef TEMP_FAILURE_RETRY
+#include <utils/Compat.h>
+#endif
+
+#include <algorithm>
+
+namespace bsdiff {
+
+std::unique_ptr<File> File::FOpen(const char* pathname, int flags) {
+ int fd = TEMP_FAILURE_RETRY(open(pathname, flags, 0644));
+ if (fd < 0)
+ return std::unique_ptr<File>();
+ return std::unique_ptr<File>(new File(fd));
+}
+
+File::~File() {
+ Close();
+}
+
+bool File::Read(void* buf, size_t count, size_t* bytes_read) {
+ if (fd_ < 0) {
+ errno = EBADF;
+ return false;
+ }
+ ssize_t rc = TEMP_FAILURE_RETRY(read(fd_, buf, count));
+ if (rc == -1)
+ return false;
+ *bytes_read = static_cast<size_t>(rc);
+ return true;
+}
+
+bool File::Write(const void* buf, size_t count, size_t* bytes_written) {
+ if (fd_ < 0) {
+ errno = EBADF;
+ return false;
+ }
+ ssize_t rc = TEMP_FAILURE_RETRY(write(fd_, buf, count));
+ if (rc == -1)
+ return false;
+ *bytes_written = static_cast<size_t>(rc);
+ return true;
+}
+
+bool File::Seek(off_t pos) {
+ if (fd_ < 0) {
+ errno = EBADF;
+ return false;
+ }
+ // fseek() uses a long value for the offset which could be smaller than off_t.
+ if (pos > std::numeric_limits<long>::max()) {
+ errno = EOVERFLOW;
+ return false;
+ }
+ off_t newpos = lseek(fd_, pos, SEEK_SET);
+ if (newpos < 0)
+ return false;
+ if (newpos != pos) {
+ errno = EINVAL;
+ return false;
+ }
+ return true;
+}
+
+bool File::Close() {
+ if (fd_ < 0) {
+ errno = EBADF;
+ return false;
+ }
+ bool success = close(fd_) == 0;
+ if (!success && errno == EINTR)
+ success = true;
+ fd_ = -1;
+ return success;
+}
+
+bool File::GetSize(uint64_t* size) {
+ struct stat stbuf;
+ if (fstat(fd_, &stbuf) == -1)
+ return false;
+ if (S_ISREG(stbuf.st_mode)) {
+ *size = stbuf.st_size;
+ return true;
+ }
+ if (S_ISBLK(stbuf.st_mode)) {
+#if defined(BLKGETSIZE64)
+ return ioctl(fd_, BLKGETSIZE64, size);
+#elif defined(DKIOCGETBLOCKCOUNT)
+ uint64_t sectors = 0;
+ if (ioctl(fd_, DKIOCGETBLOCKCOUNT, §ors) == 0) {
+ *size = sectors << 9;
+ return true;
+ }
+ return false;
+#else
+ // Fall back to doing seeks to know the EOF.
+ off_t pos = lseek(fd_, 0, SEEK_CUR);
+ if (pos == -1)
+ return false;
+ off_t end_pos = lseek(fd_, 0, SEEK_END);
+ if (end_pos == -1)
+ return false;
+ *size = end_pos;
+ lseek(fd_, 0, SEEK_END);
+ return true;
+#endif
+ }
+ return false;
+}
+
+File::File(int fd)
+ : fd_(fd) {}
+
+} // namespace bsdiff
diff --git a/bsdiff/file.h b/bsdiff/file.h
new file mode 100644
index 0000000..ad1fd2f
--- /dev/null
+++ b/bsdiff/file.h
@@ -0,0 +1,39 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef _BSDIFF_FILE_H_
+#define _BSDIFF_FILE_H_
+
+#include <memory>
+
+#include "file_interface.h"
+
+namespace bsdiff {
+
+class File : public FileInterface {
+ public:
+ // Opens a file |pathname| with flags |flags| as defined by open(2). In case
+ // of error, an empty unique_ptr is returned and errno is set accordingly.
+ static std::unique_ptr<File> FOpen(const char* pathname, int flags);
+
+ ~File() override;
+
+ // FileInterface overrides.
+ bool Read(void* buf, size_t count, size_t* bytes_read) override;
+ bool Write(const void* buf, size_t count, size_t* bytes_written) override;
+ bool Seek(off_t pos) override;
+ bool Close() override;
+ bool GetSize(uint64_t* size) override;
+
+ private:
+ // Creates the File instance for the |fd|. Takes ownership of the file
+ // descriptor.
+ explicit File(int fd);
+
+ int fd_;
+};
+
+} // namespace bsdiff
+
+#endif // _BSDIFF_FILE_H_
diff --git a/bsdiff/file_interface.h b/bsdiff/file_interface.h
new file mode 100644
index 0000000..a643f45
--- /dev/null
+++ b/bsdiff/file_interface.h
@@ -0,0 +1,48 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef _BSDIFF_FILE_INTERFACE_H_
+#define _BSDIFF_FILE_INTERFACE_H_
+
+#include <sys/types.h>
+
+namespace bsdiff {
+
+class FileInterface {
+ public:
+ virtual ~FileInterface() = default;
+
+ // Reads synchronously from the current file position up to |count| bytes into
+ // the passed |buf| buffer. On success, stores in |bytes_read| how many bytes
+ // were actually read from the file. In case of error returns false. This
+ // method may read less than |count| bytes even if there's no error. If the
+ // end of file is reached, 0 bytes will be read and this methods returns true.
+ virtual bool Read(void* buf, size_t count, size_t* bytes_read) = 0;
+
+ // Writes synchronously up to |count| bytes from to passed |buf| buffer to
+ // the file. On success, stores in |bytes_written| how many bytes
+ // were actually written to the file. This method may write less than |count|
+ // bytes and return successfully, or even write 0 bytes if there's no more
+ // space left on the device. Returns whether the write succeeded.
+ virtual bool Write(const void* buf, size_t count, size_t* bytes_written) = 0;
+
+ // Change the current file position to |pos| bytes from the beginning of the
+ // file. Return whether the seek succeeded.
+ virtual bool Seek(off_t pos) = 0;
+
+ // Closes the file and flushes any cached data. Returns whether the close
+ // succeeded.
+ virtual bool Close() = 0;
+
+ // Compute the size of the file and store it in |size|. Returns whether it
+ // computed the size successfully.
+ virtual bool GetSize(uint64_t* size) = 0;
+
+ protected:
+ FileInterface() = default;
+};
+
+} // namespace bsdiff
+
+#endif // _BSDIFF_FILE_INTERFACE_H_
diff --git a/bsdiff/memory_file.cc b/bsdiff/memory_file.cc
new file mode 100644
index 0000000..59e2c7d
--- /dev/null
+++ b/bsdiff/memory_file.cc
@@ -0,0 +1,49 @@
+// Copyright 2016 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "memory_file.h"
+
+#include "bspatch.h"
+
+namespace bsdiff {
+
+MemoryFile::MemoryFile(std::unique_ptr<FileInterface> file, size_t size)
+ : file_(std::move(file)) {
+ buffer_.reserve(size);
+}
+
+MemoryFile::~MemoryFile() {
+ Close();
+}
+
+bool MemoryFile::Read(void* buf, size_t count, size_t* bytes_read) {
+ return false;
+}
+
+bool MemoryFile::Write(const void* buf, size_t count, size_t* bytes_written) {
+ const uint8_t* data = static_cast<const uint8_t*>(buf);
+ buffer_.insert(buffer_.end(), data, data + count);
+ *bytes_written = count;
+ return true;
+}
+
+bool MemoryFile::Seek(off_t pos) {
+ return false;
+}
+
+bool MemoryFile::Close() {
+ if (!WriteAll(file_, buffer_.data(), buffer_.size()))
+ return false;
+ // Prevent writing |buffer_| to |file_| again if Close() is called more than
+ // once.
+ buffer_.clear();
+ return file_->Close();
+}
+
+bool MemoryFile::GetSize(uint64_t* size) {
+ *size = buffer_.size();
+ return true;
+}
+
+} // namespace bsdiff
diff --git a/bsdiff/memory_file.h b/bsdiff/memory_file.h
new file mode 100644
index 0000000..3e80b8a
--- /dev/null
+++ b/bsdiff/memory_file.h
@@ -0,0 +1,42 @@
+// Copyright 2016 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef _BSDIFF_MEMORY_FILE_H_
+#define _BSDIFF_MEMORY_FILE_H_
+
+#include <memory>
+#include <vector>
+
+#include "file_interface.h"
+
+namespace bsdiff {
+
+class MemoryFile : public FileInterface {
+ public:
+ // Creates a MemoryFile based on the underlying |file| passed. The MemoryFile
+ // will cache all the write in memory and write it to to |file| when it's
+ // closed. MemoryFile does not support read and seek.
+ // |size| should be the estimated total file size, it is used to reserve
+ // buffer space.
+ MemoryFile(std::unique_ptr<FileInterface> file, size_t size);
+
+ ~MemoryFile() override;
+
+ // FileInterface overrides.
+ bool Read(void* buf, size_t count, size_t* bytes_read) override;
+ bool Write(const void* buf, size_t count, size_t* bytes_written) override;
+ bool Seek(off_t pos) override;
+ bool Close() override;
+ bool GetSize(uint64_t* size) override;
+
+ private:
+ // The underlying FileInterace instance.
+ std::unique_ptr<FileInterface> file_;
+
+ std::vector<uint8_t> buffer_;
+};
+
+} // namespace bsdiff
+
+#endif // _BSDIFF_MEMORY_FILE_H_
diff --git a/bsdiff/test_utils.cc b/bsdiff/test_utils.cc
new file mode 100644
index 0000000..f369f80
--- /dev/null
+++ b/bsdiff/test_utils.cc
@@ -0,0 +1,146 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "test_utils.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include <gtest/gtest.h>
+#include <vector>
+
+using std::string;
+using std::vector;
+
+namespace {
+
+// If |path| is absolute, or explicit relative to the current working directory,
+// leaves it as is. Otherwise, if TMPDIR is defined in the environment and is
+// non-empty, prepends it to |path|. Otherwise, prepends /tmp. Returns the
+// resulting path.
+const string PrependTmpdir(const string& path) {
+ if (path[0] == '/')
+ return path;
+
+ const char* tmpdir = getenv("TMPDIR");
+ const string prefix = (tmpdir && *tmpdir ? tmpdir : "/tmp");
+ return prefix + "/" + path;
+}
+
+bool MakeTempFile(const string& base_filename_template, string* filename) {
+ const string filename_template = PrependTmpdir(base_filename_template);
+ vector<char> result(filename_template.size() + 1, '\0');
+ memcpy(result.data(), filename_template.data(), filename_template.size());
+
+ int mkstemp_fd = mkstemp(result.data());
+ if (mkstemp_fd < 0) {
+ perror("mkstemp()");
+ return false;
+ }
+ close(mkstemp_fd);
+
+ if (filename)
+ *filename = result.data();
+ return true;
+}
+
+} // namespace
+
+namespace test_utils {
+
+void BsdiffTestEnvironment::SetUp() {
+#ifdef BSDIFF_TARGET_UNITTEST
+#define BSDIFF_TARGET_TMP_BASE "/data/tmp"
+ if (access(BSDIFF_TARGET_TMP_BASE, F_OK) == -1) {
+ mkdir(BSDIFF_TARGET_TMP_BASE, S_IRWXU | S_IRWXG | S_IROTH | S_IWOTH);
+ }
+ setenv("TMPDIR", BSDIFF_TARGET_TMP_BASE, 1);
+#endif // defined (BSDIFF_TARGET_UNITTEST)
+}
+
+bool ReadFile(const string& path, vector<uint8_t>* out) {
+ FILE* fp = fopen(path.c_str(), "r");
+ if (!fp)
+ return false;
+ out->clear();
+
+ uint8_t buf[16 * 1024];
+ while (true) {
+ size_t bytes_read = fread(buf, 1, sizeof(buf), fp);
+ if (!bytes_read)
+ break;
+ out->insert(out->end(), buf, buf + bytes_read);
+ }
+ bool result = !ferror(fp);
+ fclose(fp);
+ return result;
+}
+
+bool WriteFile(const string& path, vector<uint8_t> contents) {
+ FILE* fp = fopen(path.c_str(), "r");
+ if (!fp)
+ return false;
+ size_t written = fwrite(contents.data(), 1, contents.size(), fp);
+ bool result = written == contents.size() && !ferror(fp);
+ fclose(fp);
+ return result;
+}
+
+ScopedTempFile::ScopedTempFile(const string& pattern) {
+ EXPECT_TRUE(MakeTempFile(pattern, &filename_));
+}
+
+ScopedTempFile::~ScopedTempFile() {
+ if (!filename_.empty() && unlink(filename_.c_str()) < 0) {
+ perror("Unable to remove temporary file");
+ }
+}
+
+bool BsdiffPatchFile::LoadFromFile(const string& filename) {
+ vector<uint8_t> contents;
+ if (!ReadFile(filename, &contents))
+ return false;
+ file_size = contents.size();
+ // Check that the file includes at least the header.
+ TEST_AND_RETURN_FALSE(contents.size() >= kHeaderSize);
+ magic = string(contents.data(), contents.data() + 8);
+ memcpy(&ctrl_len, contents.data() + 8, sizeof(ctrl_len));
+ memcpy(&diff_len, contents.data() + 16, sizeof(diff_len));
+ memcpy(&new_file_len, contents.data() + 24, sizeof(new_file_len));
+
+ // Sanity check before we attempt to parse the bz2 streams.
+ TEST_AND_RETURN_FALSE(ctrl_len >= 0);
+ TEST_AND_RETURN_FALSE(diff_len >= 0);
+
+ // The cast is safe since ctrl_len and diff_len are both positive.
+ TEST_AND_RETURN_FALSE(file_size >=
+ static_cast<uint64_t>(kHeaderSize + ctrl_len + diff_len));
+ extra_len = file_size - kHeaderSize - ctrl_len - diff_len;
+
+ uint8_t* ptr = contents.data() + kHeaderSize;
+ bz2_ctrl = vector<uint8_t>(ptr, ptr + ctrl_len);
+ ptr += ctrl_len;
+ bz2_diff = vector<uint8_t>(ptr, ptr + diff_len);
+ ptr += diff_len;
+ bz2_extra = vector<uint8_t>(ptr, ptr + extra_len);
+
+ return true;
+}
+
+bool BsdiffPatchFile::IsValid() const {
+ TEST_AND_RETURN_FALSE(ctrl_len >= 0);
+ TEST_AND_RETURN_FALSE(diff_len >= 0);
+ TEST_AND_RETURN_FALSE(new_file_len >= 0);
+
+ // TODO(deymo): Test that the length of the decompressed bz2 streams |diff|
+ // plus |extra| are equal to the |new_file_len|.
+ // TODO(deymo): Test that all the |bz2_ctrl| triplets (x, y, z) have a "x"
+ // and "y" value >= 0 ("z" can be negative).
+ return true;
+}
+
+} // namespace test_utils
diff --git a/bsdiff/test_utils.h b/bsdiff/test_utils.h
new file mode 100644
index 0000000..7132fe5
--- /dev/null
+++ b/bsdiff/test_utils.h
@@ -0,0 +1,94 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef _BSDIFF_TEST_UTILS_H_
+#define _BSDIFF_TEST_UTILS_H_
+
+#include <gtest/gtest.h>
+#include <string>
+#include <vector>
+
+#define TEST_AND_RETURN_FALSE(_x) \
+ do { \
+ if (!static_cast<bool>(_x)) { \
+ fprintf(stderr, "%s failed.", #_x); \
+ return false; \
+ } \
+ } while (0)
+
+namespace test_utils {
+
+class BsdiffTestEnvironment : public ::testing::Environment {
+ public:
+ virtual void SetUp();
+};
+
+// Reads all the contents of the file |path| into |out|. Returns whether it
+// read up to the end of file.
+bool ReadFile(const std::string& path, std::vector<uint8_t>* out);
+
+// Overrides the file |path| with the contents passed in |out|. Returns whether
+// the operation succeeded.
+bool WriteFile(const std::string& path, std::vector<uint8_t> contents);
+
+// Utility class to create and delete a temp file.
+class ScopedTempFile {
+ public:
+ // Creates a temp file with the passed |pattern|. The pattern should end with
+ // "XXXXXX", that will be replaced with a random string. The file will be
+ // removed when this instance is destroyed.
+ explicit ScopedTempFile(const std::string& pattern);
+ ~ScopedTempFile();
+
+ std::string filename() const { return filename_; }
+ const char* c_str() const { return filename_.c_str(); }
+
+ // Releases the temporary file. It will not be deleted when this instance is
+ // destroyed.
+ void release() { filename_.clear(); }
+
+ private:
+ std::string filename_;
+};
+
+// This struct representes a parsed BSDIFF40 file.
+struct BsdiffPatchFile {
+ static const size_t kHeaderSize = 32;
+
+ // Parses a BSDIFF40 file and stores the contents in the local methods.
+ bool LoadFromFile(const std::string& filename);
+
+ // Returns wheter the patch file is valid.
+ bool IsValid() const;
+
+ // The magic string in the header file. Normally "BSDIFF40".
+ std::string magic;
+
+ // The length of the first (ctrl) bzip2 stream. Negative values are invalid.
+ int64_t ctrl_len = -1;
+
+ // The length of the first (diff) bzip2 stream. Negative values are invalid.
+ int64_t diff_len = -1;
+
+ // The length of the first (diff) bzip2 stream. This value is not stored in
+ // the file, but generated based on the |file_size|.
+ uint64_t extra_len = 0;
+
+ // The length of the new file after applying the patch. Negative values are
+ // invalid.
+ int64_t new_file_len = -1;
+
+ // The three compressed streams.
+ std::vector<uint8_t> bz2_ctrl;
+ std::vector<uint8_t> bz2_diff;
+ std::vector<uint8_t> bz2_extra;
+
+ uint64_t file_size = 0;
+};
+
+
+} // namespace test_utils
+
+
+#endif // _BSDIFF_TEST_UTILS_H_
diff --git a/bsdiff/testrunner.cc b/bsdiff/testrunner.cc
new file mode 100644
index 0000000..8b598e2
--- /dev/null
+++ b/bsdiff/testrunner.cc
@@ -0,0 +1,13 @@
+// Copyright 2015 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "test_utils.h"
+
+#include <gtest/gtest.h>
+
+int main(int argc, char** argv) {
+ ::testing::InitGoogleTest(&argc, argv);
+ ::testing::AddGlobalTestEnvironment(new test_utils::BsdiffTestEnvironment);
+ return RUN_ALL_TESTS();
+}
