diff options
Diffstat (limited to 'usr.bin/bsdiff')
| -rw-r--r-- | usr.bin/bsdiff/Makefile | 3 | ||||
| -rw-r--r-- | usr.bin/bsdiff/Makefile.inc | 1 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bsdiff/Makefile | 16 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bsdiff/Makefile.depend | 16 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bsdiff/bsdiff.1 | 86 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bsdiff/bsdiff.c | 336 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bsdiff/config.h | 81 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bsdiff/divsufsort64.h | 180 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bspatch/Makefile | 5 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bspatch/Makefile.depend | 16 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bspatch/bspatch.1 | 85 | ||||
| -rw-r--r-- | usr.bin/bsdiff/bspatch/bspatch.c | 302 |
12 files changed, 1127 insertions, 0 deletions
diff --git a/usr.bin/bsdiff/Makefile b/usr.bin/bsdiff/Makefile new file mode 100644 index 000000000000..ed9dd0f8db5a --- /dev/null +++ b/usr.bin/bsdiff/Makefile @@ -0,0 +1,3 @@ +SUBDIR= bsdiff bspatch + +.include <bsd.subdir.mk> diff --git a/usr.bin/bsdiff/Makefile.inc b/usr.bin/bsdiff/Makefile.inc new file mode 100644 index 000000000000..01b5f23410c8 --- /dev/null +++ b/usr.bin/bsdiff/Makefile.inc @@ -0,0 +1 @@ +.include "../Makefile.inc" diff --git a/usr.bin/bsdiff/bsdiff/Makefile b/usr.bin/bsdiff/bsdiff/Makefile new file mode 100644 index 000000000000..7af4fc873e13 --- /dev/null +++ b/usr.bin/bsdiff/bsdiff/Makefile @@ -0,0 +1,16 @@ +PROG= bsdiff + +# libdivsufsort configured with: +# cmake -DCMAKE_BUILD_TYPE="Release" -DBUILD_DIVSUFSORT64=ON +.PATH: ${SRCTOP}/contrib/libdivsufsort/lib +CFLAGS+= -DHAVE_CONFIG_H=1 -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE +CFLAGS+= -D_LARGE_FILES -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS +CFLAGS+= -D__STDC_LIMIT_MACROS -DBUILD_DIVSUFSORT64 +CFLAGS+= -I${SRCTOP}/contrib/libdivsufsort/include -I${.CURDIR} +SRCS= divsufsort.c sssort.c trsort.c utils.c + +SRCS+= bsdiff.c + +LIBADD= bz2 + +.include <bsd.prog.mk> diff --git a/usr.bin/bsdiff/bsdiff/Makefile.depend b/usr.bin/bsdiff/bsdiff/Makefile.depend new file mode 100644 index 000000000000..cc83708e9dfd --- /dev/null +++ b/usr.bin/bsdiff/bsdiff/Makefile.depend @@ -0,0 +1,16 @@ +# Autogenerated - do NOT edit! + +DIRDEPS = \ + include \ + include/xlocale \ + lib/${CSU_DIR} \ + lib/libbz2 \ + lib/libc \ + lib/libcompiler_rt \ + + +.include <dirdeps.mk> + +.if ${DEP_RELDIR} == ${_DEP_RELDIR} +# local dependencies - needed for -jN in clean tree +.endif diff --git a/usr.bin/bsdiff/bsdiff/bsdiff.1 b/usr.bin/bsdiff/bsdiff/bsdiff.1 new file mode 100644 index 000000000000..3e79d9cb89b8 --- /dev/null +++ b/usr.bin/bsdiff/bsdiff/bsdiff.1 @@ -0,0 +1,86 @@ +.\"- +.\" 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. +.\" +.Dd May 18, 2003 +.Dt BSDIFF 1 +.Os +.Sh NAME +.Nm bsdiff +.Nd "generate a patch between two binary files" +.Sh SYNOPSIS +.Nm +.Ar oldfile newfile patchfile +.Sh DESCRIPTION +The +.Nm +utility +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 +The +.Nm +utility +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 +.Ar oldfile . +.Sh SEE ALSO +.Xr bspatch 1 +.Sh AUTHORS +.An Colin Percival Aq Mt cperciva@FreeBSD.org +.Sh BUGS +The +.Nm +utility does not store the hashes of +.Ar oldfile +or +.Ar newfile +in +.Ar patchfile . +As a result, it is possible to apply a patch to the wrong file; this +will usually produce garbage. +It is recommended that users of +.Nm +store the hashes of +.Ar oldfile +and +.Ar newfile +and compare against them before and after applying +.Ar patchfile . diff --git a/usr.bin/bsdiff/bsdiff/bsdiff.c b/usr.bin/bsdiff/bsdiff/bsdiff.c new file mode 100644 index 000000000000..06a8812308c8 --- /dev/null +++ b/usr.bin/bsdiff/bsdiff/bsdiff.c @@ -0,0 +1,336 @@ +/*- + * SPDX-License-Identifier: BSD-2-Clause + * + * 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. + */ + +#include <sys/types.h> + +#include <bzlib.h> +#include <err.h> +#include <errno.h> +#include <fcntl.h> +#include <limits.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#include <sys/mman.h> + +#ifndef O_BINARY +#define O_BINARY 0 +#endif + +#include "divsufsort64.h" +#define saidx_t saidx64_t +#define divsufsort divsufsort64 + +#define MIN(x,y) (((x)<(y)) ? (x) : (y)) + +static off_t matchlen(u_char *old,off_t oldsize,u_char *new,off_t newsize) +{ + off_t i; + + for(i=0;(i<oldsize)&&(i<newsize);i++) + if(old[i]!=new[i]) break; + + return i; +} + +static off_t search(off_t *I,u_char *old,off_t oldsize, + u_char *new,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,newsize); + y=matchlen(old+I[en],oldsize-I[en],new,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,MIN(oldsize-I[x],newsize))<0) { + return search(I,old,oldsize,new,newsize,x,en,pos); + } else { + return search(I,old,oldsize,new,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; +} + +static void +usage(void) +{ + + fprintf(stderr, "usage: bsdiff oldfile newfile patchfile\n"); + exit(1); +} + +int main(int argc,char *argv[]) +{ + int fd; + u_char *old,*new; + off_t oldsize,newsize,xnewsize; + saidx_t *I; + off_t scan,pos,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 (argc != 4) + usage(); + + /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure + that we never try to malloc(0) and get a NULL pointer */ + if(((fd=open(argv[1],O_RDONLY|O_BINARY,0))<0) || + ((oldsize=lseek(fd,0,SEEK_END))==-1)) + err(1, "%s", argv[1]); + + if (oldsize > SSIZE_MAX || + (uintmax_t)oldsize >= SIZE_T_MAX / sizeof(off_t) || + oldsize == OFF_MAX) { + errno = EFBIG; + err(1, "%s", argv[1]); + } + + old = mmap(NULL, oldsize+1, PROT_READ, MAP_SHARED, fd, 0); + if (old == MAP_FAILED || close(fd) == -1) + err(1, "%s", argv[1]); + + if(((I=malloc((oldsize+1)*sizeof(saidx_t)))==NULL)) err(1,NULL); + + if(divsufsort(old, I, oldsize)) err(1, "divsufsort"); + + /* Allocate newsize+1 bytes instead of newsize bytes to ensure + that we never try to malloc(0) and get a NULL pointer */ + if(((fd=open(argv[2],O_RDONLY|O_BINARY,0))<0) || + ((newsize=lseek(fd,0,SEEK_END))==-1)) + err(1, "%s", argv[2]); + + if (newsize > SSIZE_MAX || (uintmax_t)newsize >= SIZE_T_MAX || + newsize == OFF_MAX) { + errno = EFBIG; + err(1, "%s", argv[2]); + } + + new = mmap(NULL, newsize+1, PROT_READ, MAP_SHARED, fd, 0); + if (new == MAP_FAILED || close(fd) == -1) + err(1, "%s", argv[2]); + + if(((db=malloc(newsize+1))==NULL) || + ((eb=malloc(newsize+1))==NULL)) err(1,NULL); + dblen=0; + eblen=0; + + /* Create the patch file */ + if ((pf = fopen(argv[3], "wb")) == NULL) + err(1, "%s", argv[3]); + + /* 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)", argv[3]); + + /* 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;pos=0; + lastscan=0;lastpos=0;lastoffset=0; + while(scan<newsize) { + oldscore=0; + + for(scsc=scan+=len;scan<newsize;scan++) { + len=search(I,old,oldsize,new+scan,newsize-scan, + 0,oldsize-1,&pos); + + for(;scsc<scan+len;scsc++) + if((scsc+lastoffset<oldsize) && + (old[scsc+lastoffset] == new[scsc])) + oldscore++; + + if(((len==oldscore) && (len!=0)) || + (len>oldscore+8)) break; + + if((scan+lastoffset<oldsize) && + (old[scan+lastoffset] == new[scan])) + oldscore--; + } + + if((len!=oldscore) || (scan==newsize)) { + s=0;Sf=0;lenf=0; + for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) { + if(old[lastpos+i]==new[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[pos-i]==new[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[lastscan+lenf-overlap+i]== + old[lastpos+lenf-overlap+i]) s++; + if(new[scan-lenb+i]== + old[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[lastscan+i]-old[lastpos+i]; + for(i=0;i<(scan-lenb)-(lastscan+lenf);i++) + eb[eblen+i]=new[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 ((xnewsize = ftello(pf)) == -1) + err(1, "ftello"); + offtout(xnewsize - 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)", argv[3]); + if (fclose(pf)) + err(1, "fclose"); + + /* Free the memory we used */ + free(db); + free(eb); + free(I); + munmap(old, oldsize+1); + munmap(new, newsize+1); + + return 0; +} diff --git a/usr.bin/bsdiff/bsdiff/config.h b/usr.bin/bsdiff/bsdiff/config.h new file mode 100644 index 000000000000..fb4e71261cd2 --- /dev/null +++ b/usr.bin/bsdiff/bsdiff/config.h @@ -0,0 +1,81 @@ +/* + * config.h for libdivsufsort + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _CONFIG_H +#define _CONFIG_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +/** Define to the version of this package. **/ +#define PROJECT_VERSION_FULL "2.0.1-14-g5f60d6f" + +/** Define to 1 if you have the header files. **/ +#define HAVE_INTTYPES_H 1 +#define HAVE_STDDEF_H 1 +#define HAVE_STDINT_H 1 +#define HAVE_STDLIB_H 1 +#define HAVE_STRING_H 1 +#define HAVE_STRINGS_H 1 +#define HAVE_MEMORY_H 1 +#define HAVE_SYS_TYPES_H 1 + +/** for WinIO **/ +/* #undef HAVE_IO_H */ +/* #undef HAVE_FCNTL_H */ +/* #undef HAVE__SETMODE */ +/* #undef HAVE_SETMODE */ +/* #undef HAVE__FILENO */ +/* #undef HAVE_FOPEN_S */ +/* #undef HAVE__O_BINARY */ +#ifndef HAVE__SETMODE +# if HAVE_SETMODE +# define _setmode setmode +# define HAVE__SETMODE 1 +# endif +# if HAVE__SETMODE && !HAVE__O_BINARY +# define _O_BINARY 0 +# define HAVE__O_BINARY 1 +# endif +#endif + +/** for inline **/ +#ifndef INLINE +# define INLINE inline +#endif + +/** for VC++ warning **/ +#ifdef _MSC_VER +#pragma warning(disable: 4127) +#endif + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _CONFIG_H */ diff --git a/usr.bin/bsdiff/bsdiff/divsufsort64.h b/usr.bin/bsdiff/bsdiff/divsufsort64.h new file mode 100644 index 000000000000..2f1c375ba45e --- /dev/null +++ b/usr.bin/bsdiff/bsdiff/divsufsort64.h @@ -0,0 +1,180 @@ +/* + * divsufsort64.h for libdivsufsort64 + * Copyright (c) 2003-2008 Yuta Mori All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _DIVSUFSORT64_H +#define _DIVSUFSORT64_H 1 + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#include <inttypes.h> + +#ifndef DIVSUFSORT_API +# ifdef DIVSUFSORT_BUILD_DLL +# define DIVSUFSORT_API +# else +# define DIVSUFSORT_API +# endif +#endif + +/*- Datatypes -*/ +#ifndef SAUCHAR_T +#define SAUCHAR_T +typedef uint8_t sauchar_t; +#endif /* SAUCHAR_T */ +#ifndef SAINT_T +#define SAINT_T +typedef int32_t saint_t; +#endif /* SAINT_T */ +#ifndef SAIDX64_T +#define SAIDX64_T +typedef int64_t saidx64_t; +#endif /* SAIDX64_T */ +#ifndef PRIdSAINT_T +#define PRIdSAINT_T PRId32 +#endif /* PRIdSAINT_T */ +#ifndef PRIdSAIDX64_T +#define PRIdSAIDX64_T PRId64 +#endif /* PRIdSAIDX64_T */ + + +/*- Prototypes -*/ + +/** + * Constructs the suffix array of a given string. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The output array of suffixes. + * @param n The length of the given string. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +divsufsort64(const sauchar_t *T, saidx64_t *SA, saidx64_t n); + +/** + * Constructs the burrows-wheeler transformed string of a given string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @return The primary index if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saidx64_t +divbwt64(const sauchar_t *T, sauchar_t *U, saidx64_t *A, saidx64_t n); + +/** + * Returns the version of the divsufsort library. + * @return The version number string. + */ +DIVSUFSORT_API +const char * +divsufsort64_version(void); + + +/** + * Constructs the burrows-wheeler transformed string of a given string and suffix array. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param SA[0..n-1] The suffix array. (can be NULL) + * @param n The length of the given string. + * @param idx The output primary index. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +bw_transform64(const sauchar_t *T, sauchar_t *U, + saidx64_t *SA /* can NULL */, + saidx64_t n, saidx64_t *idx); + +/** + * Inverse BW-transforms a given BWTed string. + * @param T[0..n-1] The input string. + * @param U[0..n-1] The output string. (can be T) + * @param A[0..n-1] The temporary array. (can be NULL) + * @param n The length of the given string. + * @param idx The primary index. + * @return 0 if no error occurred, -1 or -2 otherwise. + */ +DIVSUFSORT_API +saint_t +inverse_bw_transform64(const sauchar_t *T, sauchar_t *U, + saidx64_t *A /* can NULL */, + saidx64_t n, saidx64_t idx); + +/** + * Checks the correctness of a given suffix array. + * @param T[0..n-1] The input string. + * @param SA[0..n-1] The input suffix array. + * @param n The length of the given string. + * @param verbose The verbose mode. + * @return 0 if no error occurred. + */ +DIVSUFSORT_API +saint_t +sufcheck64(const sauchar_t *T, const saidx64_t *SA, saidx64_t n, saint_t verbose); + +/** + * Search for the pattern P in the string T. + * @param T[0..Tsize-1] The input string. + * @param Tsize The length of the given string. + * @param P[0..Psize-1] The input pattern string. + * @param Psize The length of the given pattern string. + * @param SA[0..SAsize-1] The input suffix array. + * @param SAsize The length of the given suffix array. + * @param idx The output index. + * @return The count of matches if no error occurred, -1 otherwise. + */ +DIVSUFSORT_API +saidx64_t +sa_search64(const sauchar_t *T, saidx64_t Tsize, + const sauchar_t *P, saidx64_t Psize, + const saidx64_t *SA, saidx64_t SAsize, + saidx64_t *left); + +/** + * Search for the character c in the string T. + * @param T[0..Tsize-1] The input string. + * @param Tsize The length of the given string. + * @param SA[0..SAsize-1] The input suffix array. + * @param SAsize The length of the given suffix array. + * @param c The input character. + * @param idx The output index. + * @return The count of matches if no error occurred, -1 otherwise. + */ +DIVSUFSORT_API +saidx64_t +sa_simplesearch64(const sauchar_t *T, saidx64_t Tsize, + const saidx64_t *SA, saidx64_t SAsize, + saint_t c, saidx64_t *left); + + +#ifdef __cplusplus +} /* extern "C" */ +#endif /* __cplusplus */ + +#endif /* _DIVSUFSORT64_H */ diff --git a/usr.bin/bsdiff/bspatch/Makefile b/usr.bin/bsdiff/bspatch/Makefile new file mode 100644 index 000000000000..12b67fe97577 --- /dev/null +++ b/usr.bin/bsdiff/bspatch/Makefile @@ -0,0 +1,5 @@ +PROG= bspatch + +LIBADD= bz2 + +.include <bsd.prog.mk> diff --git a/usr.bin/bsdiff/bspatch/Makefile.depend b/usr.bin/bsdiff/bspatch/Makefile.depend new file mode 100644 index 000000000000..cc83708e9dfd --- /dev/null +++ b/usr.bin/bsdiff/bspatch/Makefile.depend @@ -0,0 +1,16 @@ +# Autogenerated - do NOT edit! + +DIRDEPS = \ + include \ + include/xlocale \ + lib/${CSU_DIR} \ + lib/libbz2 \ + lib/libc \ + lib/libcompiler_rt \ + + +.include <dirdeps.mk> + +.if ${DEP_RELDIR} == ${_DEP_RELDIR} +# local dependencies - needed for -jN in clean tree +.endif diff --git a/usr.bin/bsdiff/bspatch/bspatch.1 b/usr.bin/bsdiff/bspatch/bspatch.1 new file mode 100644 index 000000000000..291f9f2be348 --- /dev/null +++ b/usr.bin/bsdiff/bspatch/bspatch.1 @@ -0,0 +1,85 @@ +.\"- +.\" 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. +.\" +.Dd December 22, 2022 +.Dt BSPATCH 1 +.Os +.Sh NAME +.Nm bspatch +.Nd apply a patch built with +.Xr bsdiff 1 +.Sh SYNOPSIS +.Nm +.Ar oldfile newfile patchfile +.Sh DESCRIPTION +The +.Nm +utility +generates +.Ar newfile +from +.Ar oldfile +and +.Ar patchfile +where +.Ar patchfile +is a binary patch built by +.Xr bsdiff 1 . +.Pp +The +.Nm +utility +uses memory equal to the size of +.Ar oldfile +plus 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 Mt cperciva@FreeBSD.org +.Sh BUGS +The +.Nm +utility does not verify that +.Ar oldfile +is the correct source file for +.Ar patchfile . +Attempting to apply a patch to the wrong file will usually produce +garbage; consequently it is strongly recommended that users of +.Nm +verify that +.Ar oldfile +matches the source file from which +.Ar patchfile +was built, by comparing cryptographic hashes, for example. +Users may also wish to verify after running +.Nm +that +.Ar newfile +matches the target file from which +.Ar patchfile +was built. diff --git a/usr.bin/bsdiff/bspatch/bspatch.c b/usr.bin/bsdiff/bspatch/bspatch.c new file mode 100644 index 000000000000..ea43d78b12a1 --- /dev/null +++ b/usr.bin/bsdiff/bspatch/bspatch.c @@ -0,0 +1,302 @@ +/*- + * SPDX-License-Identifier: BSD-2-Clause + * + * 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. + */ + +#include <sys/cdefs.h> +#ifndef WITHOUT_CAPSICUM +#include <sys/capsicum.h> +#endif + +#include <bzlib.h> +#include <err.h> +#include <fcntl.h> +#include <libgen.h> +#include <limits.h> +#include <stdckdint.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> +#include <sys/mman.h> + +#ifndef O_BINARY +#define O_BINARY 0 +#endif +#define HEADER_SIZE 32 + +static char *newfile; +static int dirfd = -1; + +static void +exit_cleanup(void) +{ + + if (dirfd != -1 && newfile != NULL) + if (unlinkat(dirfd, newfile, 0)) + warn("unlinkat"); +} + +static inline off_t +add_off_t(off_t a, off_t b) +{ + off_t result; + + if (ckd_add(&result, a, b)) + errx(1, "Corrupt patch"); + return result; +} + +static off_t offtin(u_char *buf) +{ + off_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); +} + +static void +usage(void) +{ + + fprintf(stderr, "usage: bspatch oldfile newfile patchfile\n"); + exit(1); +} + +int main(int argc, char *argv[]) +{ + FILE *f, *cpf, *dpf, *epf; + BZFILE *cpfbz2, *dpfbz2, *epfbz2; + char *directory, *namebuf; + int cbz2err, dbz2err, ebz2err; + int newfd, oldfd; + off_t oldsize, newsize; + off_t bzctrllen, bzdatalen; + u_char header[HEADER_SIZE], buf[8]; + u_char *old, *new; + off_t oldpos, newpos; + off_t ctrl[3]; + off_t i, lenread, offset; +#ifndef WITHOUT_CAPSICUM + cap_rights_t rights_dir, rights_ro, rights_wr; +#endif + + if (argc != 4) + usage(); + + /* Open patch file */ + if ((f = fopen(argv[3], "rb")) == NULL) + err(1, "fopen(%s)", argv[3]); + /* Open patch file for control block */ + if ((cpf = fopen(argv[3], "rb")) == NULL) + err(1, "fopen(%s)", argv[3]); + /* open patch file for diff block */ + if ((dpf = fopen(argv[3], "rb")) == NULL) + err(1, "fopen(%s)", argv[3]); + /* open patch file for extra block */ + if ((epf = fopen(argv[3], "rb")) == NULL) + err(1, "fopen(%s)", argv[3]); + /* open oldfile */ + if ((oldfd = open(argv[1], O_RDONLY | O_BINARY, 0)) < 0) + err(1, "open(%s)", argv[1]); + /* open directory where we'll write newfile */ + if ((namebuf = strdup(argv[2])) == NULL || + (directory = dirname(namebuf)) == NULL || + (dirfd = open(directory, O_DIRECTORY)) < 0) + err(1, "open %s", argv[2]); + free(namebuf); + if ((newfile = basename(argv[2])) == NULL) + err(1, "basename"); + /* open newfile */ + if ((newfd = openat(dirfd, newfile, + O_CREAT | O_TRUNC | O_WRONLY | O_BINARY, 0666)) < 0) + err(1, "open(%s)", argv[2]); + atexit(exit_cleanup); + +#ifndef WITHOUT_CAPSICUM + if (cap_enter() < 0) + err(1, "failed to enter security sandbox"); + + cap_rights_init(&rights_ro, CAP_READ, CAP_FSTAT, CAP_SEEK, CAP_MMAP_R); + cap_rights_init(&rights_wr, CAP_WRITE); + cap_rights_init(&rights_dir, CAP_UNLINKAT); + + if (cap_rights_limit(fileno(f), &rights_ro) < 0 || + cap_rights_limit(fileno(cpf), &rights_ro) < 0 || + cap_rights_limit(fileno(dpf), &rights_ro) < 0 || + cap_rights_limit(fileno(epf), &rights_ro) < 0 || + cap_rights_limit(oldfd, &rights_ro) < 0 || + cap_rights_limit(newfd, &rights_wr) < 0 || + cap_rights_limit(dirfd, &rights_dir) < 0) + err(1, "cap_rights_limit() failed, could not restrict" + " capabilities"); +#endif + + /* + File format: + 0 8 "BSDIFF40" + 8 8 X + 16 8 Y + 24 8 sizeof(newfile) + 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, HEADER_SIZE, f) < HEADER_SIZE) { + if (feof(f)) + errx(1, "Corrupt patch"); + err(1, "fread(%s)", argv[3]); + } + + /* Check for appropriate magic */ + if (memcmp(header, "BSDIFF40", 8) != 0) + errx(1, "Corrupt patch"); + + /* Read lengths from header */ + bzctrllen = offtin(header + 8); + bzdatalen = offtin(header + 16); + newsize = offtin(header + 24); + if (bzctrllen < 0 || bzctrllen > OFF_MAX - HEADER_SIZE || + bzdatalen < 0 || bzctrllen + HEADER_SIZE > OFF_MAX - bzdatalen || + newsize < 0 || newsize > SSIZE_MAX) + errx(1, "Corrupt patch"); + + /* Close patch file and re-open it via libbzip2 at the right places */ + if (fclose(f)) + err(1, "fclose(%s)", argv[3]); + offset = HEADER_SIZE; + if (fseeko(cpf, offset, SEEK_SET)) + err(1, "fseeko(%s, %jd)", argv[3], (intmax_t)offset); + if ((cpfbz2 = BZ2_bzReadOpen(&cbz2err, cpf, 0, 0, NULL, 0)) == NULL) + errx(1, "BZ2_bzReadOpen, bz2err = %d", cbz2err); + offset = add_off_t(offset, bzctrllen); + if (fseeko(dpf, offset, SEEK_SET)) + err(1, "fseeko(%s, %jd)", argv[3], (intmax_t)offset); + if ((dpfbz2 = BZ2_bzReadOpen(&dbz2err, dpf, 0, 0, NULL, 0)) == NULL) + errx(1, "BZ2_bzReadOpen, bz2err = %d", dbz2err); + offset = add_off_t(offset, bzdatalen); + if (fseeko(epf, offset, SEEK_SET)) + err(1, "fseeko(%s, %jd)", argv[3], (intmax_t)offset); + if ((epfbz2 = BZ2_bzReadOpen(&ebz2err, epf, 0, 0, NULL, 0)) == NULL) + errx(1, "BZ2_bzReadOpen, bz2err = %d", ebz2err); + + if ((oldsize = lseek(oldfd, 0, SEEK_END)) == -1 || + oldsize > SSIZE_MAX) + err(1, "%s", argv[1]); + + old = mmap(NULL, oldsize+1, PROT_READ, MAP_SHARED, oldfd, 0); + if (old == MAP_FAILED || close(oldfd) != 0) + err(1, "%s", argv[1]); + + if ((new = malloc(newsize)) == NULL) + err(1, NULL); + + oldpos = 0; + newpos = 0; + while (newpos < newsize) { + /* Read control data */ + for (i = 0; i <= 2; i++) { + lenread = BZ2_bzRead(&cbz2err, cpfbz2, buf, 8); + if ((lenread < 8) || ((cbz2err != BZ_OK) && + (cbz2err != BZ_STREAM_END))) + errx(1, "Corrupt patch"); + ctrl[i] = offtin(buf); + } + + /* Sanity-check */ + if (ctrl[0] < 0 || ctrl[0] > INT_MAX || + ctrl[1] < 0 || ctrl[1] > INT_MAX) + errx(1, "Corrupt patch"); + + /* Sanity-check */ + if (add_off_t(newpos, ctrl[0]) > newsize) + errx(1, "Corrupt patch"); + + /* Read diff string */ + lenread = BZ2_bzRead(&dbz2err, dpfbz2, new + newpos, ctrl[0]); + if ((lenread < ctrl[0]) || + ((dbz2err != BZ_OK) && (dbz2err != BZ_STREAM_END))) + errx(1, "Corrupt patch"); + + /* Add old data to diff string */ + for (i = 0; i < ctrl[0]; i++) + if (add_off_t(oldpos, i) < oldsize) + new[newpos + i] += old[oldpos + i]; + + /* Adjust pointers */ + newpos = add_off_t(newpos, ctrl[0]); + oldpos = add_off_t(oldpos, ctrl[0]); + + /* Sanity-check */ + if (add_off_t(newpos, ctrl[1]) > newsize) + errx(1, "Corrupt patch"); + + /* Read extra string */ + lenread = BZ2_bzRead(&ebz2err, epfbz2, new + newpos, ctrl[1]); + if ((lenread < ctrl[1]) || + ((ebz2err != BZ_OK) && (ebz2err != BZ_STREAM_END))) + errx(1, "Corrupt patch"); + + /* Adjust pointers */ + newpos = add_off_t(newpos, ctrl[1]); + oldpos = add_off_t(oldpos, ctrl[2]); + } + + /* Clean up the bzip2 reads */ + BZ2_bzReadClose(&cbz2err, cpfbz2); + BZ2_bzReadClose(&dbz2err, dpfbz2); + BZ2_bzReadClose(&ebz2err, epfbz2); + if (fclose(cpf) || fclose(dpf) || fclose(epf)) + err(1, "fclose(%s)", argv[3]); + + /* Write the new file */ + if (write(newfd, new, newsize) != newsize || close(newfd) == -1) + err(1, "%s", argv[2]); + /* Disable atexit cleanup */ + newfile = NULL; + + free(new); + munmap(old, oldsize+1); + + return (0); +} |