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(); +}