Module Name: othersrc
Committed By: agc
Date: Thu Apr 28 05:21:31 UTC 2016
Added Files:
othersrc/external/bsd/delta: Makefile README
othersrc/external/bsd/delta/bin: 1 2 3 4 Makefile
othersrc/external/bsd/delta/dist: Makefile delta.1 delta.c delta.h
libdelta.3 libdelta.c main.c
othersrc/external/bsd/delta/lib: Makefile shlib_version
Log Message:
Add the delta library and utility program, providing
space-efficient binary diff/patch functionality.
delta is a library (and an associated utility) which allow
us to perform binary diff and patching in an efficient way. It
is similar in function to xdelta and vcdiff (RFC 3284), but more
(space-)efficient.
-rw-r--r-- 1 agc users 10107 Apr 14 10:41 1
-rw-r--r-- 1 agc users 206 Apr 19 16:50 1.bsd
-rw-r--r-- 1 agc users 109 Apr 27 22:11 1.diff
-rw-r--r-- 1 agc users 222 Apr 19 16:48 1.xd
-rw-r--r-- 1 agc users 158 Apr 19 17:48 1.xd3
-rw-r--r-- 1 agc users 10113 Apr 14 10:41 2
-rw-r--r-- 1 agc users 10113 Apr 27 22:11 2.new
The delta(1) utility takes 3 arguments - oldfile, newfile and
patchfile - and creates the patchfile from the binary difference of
the old and new files. There's an optional -d or -p to diff and
to patch, respectively. The default is to patch.
% delta -d 2 1 2.diff
% delta -p 2 1.new 2.diff
% diff 1 1.new
%
The patchfile uses bzip2, and is more efficient than both xdelta (v1
and v3) by Josh MacDonald, and bsdiff from Colin Percival, dated 2005.
It also uses zigzag encoding for the numbers stored internally, in
order to be space-efficient.
I also tried using xz/lzma compression, but the results were not good
- around 160 bytes for a delta file where bzip2 ended up with 109
bytes.
To generate a diff of this commit:
cvs rdiff -u -r0 -r1.1 othersrc/external/bsd/delta/Makefile \
othersrc/external/bsd/delta/README
cvs rdiff -u -r0 -r1.1 othersrc/external/bsd/delta/bin/1 \
othersrc/external/bsd/delta/bin/2 othersrc/external/bsd/delta/bin/3 \
othersrc/external/bsd/delta/bin/4 \
othersrc/external/bsd/delta/bin/Makefile
cvs rdiff -u -r0 -r1.1 othersrc/external/bsd/delta/dist/Makefile \
othersrc/external/bsd/delta/dist/delta.1 \
othersrc/external/bsd/delta/dist/delta.c \
othersrc/external/bsd/delta/dist/delta.h \
othersrc/external/bsd/delta/dist/libdelta.3 \
othersrc/external/bsd/delta/dist/libdelta.c \
othersrc/external/bsd/delta/dist/main.c
cvs rdiff -u -r0 -r1.1 othersrc/external/bsd/delta/lib/Makefile \
othersrc/external/bsd/delta/lib/shlib_version
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Added files:
Index: othersrc/external/bsd/delta/Makefile
diff -u /dev/null othersrc/external/bsd/delta/Makefile:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/Makefile Thu Apr 28 05:21:31 2016
@@ -0,0 +1,9 @@
+# $NetBSD: Makefile,v 1.1 2016/04/28 05:21:31 agc Exp $
+
+SUBDIR= lib .WAIT
+SUBDIR+= bin
+
+.include <bsd.subdir.mk>
+
+t:
+ cd bin && ${MAKE} t
Index: othersrc/external/bsd/delta/README
diff -u /dev/null othersrc/external/bsd/delta/README:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/README Thu Apr 28 05:21:31 2016
@@ -0,0 +1,31 @@
+delta is a library (and an associated utility) which allow
+us to perform binary diff and patching in an efficient way. It
+is similar in function to xdelta and vcdiff (RFC 3284), but more
+(space-)efficient.
+
+ -rw-r--r-- 1 agc users 10107 Apr 14 10:41 1
+ -rw-r--r-- 1 agc users 206 Apr 19 16:50 1.bsd
+ -rw-r--r-- 1 agc users 109 Apr 27 22:11 1.diff
+ -rw-r--r-- 1 agc users 222 Apr 19 16:48 1.xd
+ -rw-r--r-- 1 agc users 158 Apr 19 17:48 1.xd3
+ -rw-r--r-- 1 agc users 10113 Apr 14 10:41 2
+ -rw-r--r-- 1 agc users 10113 Apr 27 22:11 2.new
+
+The delta(1) utility takes 3 arguments - oldfile, newfile and
+patchfile - and creates the patchfile from the binary difference of
+the old and new files. There's an optional -d or -p to diff and
+to patch, respectively. The default is to patch.
+
+ % delta -d 2 1 2.diff
+ % delta -p 2 1.new 2.diff
+ % diff 1 1.new
+ %
+
+The patchfile uses bzip2, and is more efficient than both xdelta (v1
+and v3) by Josh MacDonald, and bsdiff from Colin Percival, dated 2005.
+It also uses zigzag encoding for the numbers stored internally, in
+order to be space-efficient.
+
+I also tried using xz/lzma compression, but the results were not good
+- around 160 bytes for a delta file where bzip2 ended up with 111
+bytes.
Index: othersrc/external/bsd/delta/bin/1
diff -u /dev/null othersrc/external/bsd/delta/bin/1:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/bin/1 Thu Apr 28 05:21:31 2016
@@ -0,0 +1,404 @@
+/*-
+ * 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 <sys/types.h>
+
+#include <bzlib.h>
+#include <err.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#define MIN(x,y) (((x)<(y)) ? (x) : (y))
+
+static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h)
+{
+ off_t i,j,k,x,tmp,jj,kk;
+
+ if(len<16) {
+ for(k=start;k<start+len;k+=j) {
+ j=1;x=V[I[k]+h];
+ for(i=1;k+i<start+len;i++) {
+ if(V[I[k+i]+h]<x) {
+ x=V[I[k+i]+h];
+ j=0;
+ };
+ if(V[I[k+i]+h]==x) {
+ tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
+ j++;
+ };
+ };
+ for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
+ if(j==1) I[k]=-1;
+ };
+ return;
+ };
+
+ x=V[I[start+len/2]+h];
+ jj=0;kk=0;
+ for(i=start;i<start+len;i++) {
+ if(V[I[i]+h]<x) jj++;
+ if(V[I[i]+h]==x) kk++;
+ };
+ jj+=start;kk+=jj;
+
+ i=start;j=0;k=0;
+ while(i<jj) {
+ if(V[I[i]+h]<x) {
+ i++;
+ } else if(V[I[i]+h]==x) {
+ tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
+ j++;
+ } else {
+ tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
+ k++;
+ };
+ };
+
+ while(jj+j<kk) {
+ if(V[I[jj+j]+h]==x) {
+ j++;
+ } else {
+ tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
+ k++;
+ };
+ };
+
+ if(jj>start) split(I,V,start,jj-start,h);
+
+ for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
+ if(jj==kk-1) I[jj]=-1;
+
+ if(start+len>kk) split(I,V,kk,start+len-kk,h);
+}
+
+static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize)
+{
+ off_t buckets[256];
+ off_t i,h,len;
+
+ for(i=0;i<256;i++) buckets[i]=0;
+ for(i=0;i<oldsize;i++) buckets[old[i]]++;
+ for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
+ for(i=255;i>0;i--) buckets[i]=buckets[i-1];
+ buckets[0]=0;
+
+ for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
+ I[0]=oldsize;
+ for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
+ V[oldsize]=0;
+ for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
+ I[0]=-1;
+
+ for(h=1;I[0]!=-(oldsize+1);h+=h) {
+ len=0;
+ for(i=0;i<oldsize+1;) {
+ if(I[i]<0) {
+ len-=I[i];
+ i-=I[i];
+ } else {
+ if(len) I[i-len]=-len;
+ len=V[I[i]]+1-i;
+ split(I,V,i,len,h);
+ i+=len;
+ len=0;
+ };
+ };
+ if(len) I[i-len]=-len;
+ };
+
+ for(i=0;i<oldsize+1;i++) I[V[i]]=i;
+}
+
+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;
+}
+
+int main(int argc,char *argv[])
+{
+ int fd;
+ u_char *old,*new;
+ off_t oldsize,newsize;
+ off_t *I,*V;
+ 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) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);
+
+ /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
+ that we never try to malloc(0) and get a NULL pointer */
+ if(((fd=open(argv[1],O_RDONLY,0))<0) ||
+ ((oldsize=lseek(fd,0,SEEK_END))==-1) ||
+ ((old=malloc(oldsize+1))==NULL) ||
+ (lseek(fd,0,SEEK_SET)!=0) ||
+ (read(fd,old,oldsize)!=oldsize) ||
+ (close(fd)==-1)) err(1,"%s",argv[1]);
+
+ if(((I=malloc((oldsize+1)*sizeof(off_t)))==NULL) ||
+ ((V=malloc((oldsize+1)*sizeof(off_t)))==NULL)) err(1,NULL);
+
+ qsufsort(I,V,old,oldsize);
+
+ free(V);
+
+ /* Allocate newsize+1 bytes instead of newsize bytes to ensure
+ that we never try to malloc(0) and get a NULL pointer */
+ if(((fd=open(argv[2],O_RDONLY,0))<0) ||
+ ((newsize=lseek(fd,0,SEEK_END))==-1) ||
+ ((new=malloc(newsize+1))==NULL) ||
+ (lseek(fd,0,SEEK_SET)!=0) ||
+ (read(fd,new,newsize)!=newsize) ||
+ (close(fd)==-1)) err(1,"%s",argv[2]);
+
+ 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], "w")) == 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;
+ 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,&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 ((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)", argv[3]);
+ if (fclose(pf))
+ err(1, "fclose");
+
+ /* Free the memory we used */
+ free(db);
+ free(eb);
+ free(I);
+ free(old);
+ free(new);
+
+ return 0;
+}
Index: othersrc/external/bsd/delta/bin/2
diff -u /dev/null othersrc/external/bsd/delta/bin/2:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/bin/2 Thu Apr 28 05:21:31 2016
@@ -0,0 +1,404 @@
+/*-
+ * 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:
+ * 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.
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 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 <sys/types.h>
+
+#include <bzlib.h>
+#include <err.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#define MIN(x,y) (((x)<(y)) ? (x) : (y))
+
+static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h)
+{
+ off_t i,j,k,x,tmp,jj,kk;
+
+ if(len<=15) {
+ for(k=start;k<start+len;k+=j) {
+ j=1;x=V[I[k]+h];
+ for(i=1;k+i<start+len;i++) {
+ if(V[I[k+i]+h]<x) {
+ x=V[I[k+i]+h];
+ j=0;
+ };
+ if(V[I[k+i]+h]==x) {
+ tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
+ j++;
+ };
+ };
+ for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
+ if(j==1) I[k]=-1;
+ };
+ return;
+ };
+
+ x=V[I[start+len/2]+h];
+ jj=0;kk=0;
+ for(i=start;i<start+len;i++) {
+ if(V[I[i]+h]<x) jj++;
+ if(V[I[i]+h]==x) kk++;
+ };
+ jj+=start;kk+=jj;
+
+ i=start;j=0;k=0;
+ while(i<jj) {
+ if(V[I[i]+h]<x) {
+ i++;
+ } else if(V[I[i]+h]==x) {
+ tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
+ j++;
+ } else {
+ tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
+ k++;
+ };
+ };
+
+ while(jj+j<kk) {
+ if(V[I[jj+j]+h]==x) {
+ j++;
+ } else {
+ tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
+ k++;
+ };
+ };
+
+ if(jj>start) split(I,V,start,jj-start,h);
+
+ for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
+ if(jj==kk-1) I[jj]=-1;
+
+ if(start+len>kk) split(I,V,kk,start+len-kk,h);
+}
+
+static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize)
+{
+ off_t buckets[256];
+ off_t i,h,len;
+
+ for(i=0;i<256;i++) buckets[i]=0;
+ for(i=0;i<oldsize;i++) buckets[old[i]]++;
+ for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
+ for(i=255;i>0;i--) buckets[i]=buckets[i-1];
+ buckets[0]=0;
+
+ for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
+ I[0]=oldsize;
+ for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
+ V[oldsize]=0;
+ for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
+ I[0]=-1;
+
+ for(h=1;I[0]!=-(oldsize+1);h+=h) {
+ len=0;
+ for(i=0;i<oldsize+1;) {
+ if(I[i]<0) {
+ len-=I[i];
+ i-=I[i];
+ } else {
+ if(len) I[i-len]=-len;
+ len=V[I[i]]+1-i;
+ split(I,V,i,len,h);
+ i+=len;
+ len=0;
+ };
+ };
+ if(len) I[i-len]=-len;
+ };
+
+ for(i=0;i<oldsize+1;i++) I[V[i]]=i;
+}
+
+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;
+}
+
+int main(int argc,char *argv[])
+{
+ int fd;
+ u_char *old,*new;
+ off_t oldsize,newsize;
+ off_t *I,*V;
+ 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) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);
+
+ /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
+ that we never try to malloc(0) and get a NULL pointer */
+ if(((fd=open(argv[1],O_RDONLY,0))<0) ||
+ ((oldsize=lseek(fd,0,SEEK_END))==-1) ||
+ ((old=malloc(oldsize+1))==NULL) ||
+ (lseek(fd,0,SEEK_SET)!=0) ||
+ (read(fd,old,oldsize)!=oldsize) ||
+ (close(fd)==-1)) err(1,"%s",argv[1]);
+
+ if(((I=malloc((oldsize+1)*sizeof(off_t)))==NULL) ||
+ ((V=malloc((oldsize+1)*sizeof(off_t)))==NULL)) err(1,NULL);
+
+ qsufsort(I,V,old,oldsize);
+
+ free(V);
+
+ /* Allocate newsize+1 bytes instead of newsize bytes to ensure
+ that we never try to malloc(0) and get a NULL pointer */
+ if(((fd=open(argv[2],O_RDONLY,0))<0) ||
+ ((newsize=lseek(fd,0,SEEK_END))==-1) ||
+ ((new=malloc(newsize+1))==NULL) ||
+ (lseek(fd,0,SEEK_SET)!=0) ||
+ (read(fd,new,newsize)!=newsize) ||
+ (close(fd)==-1)) err(1,"%s",argv[2]);
+
+ 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], "w")) == 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;
+ lastscan=0;lastpos=0;lastoffset=0;
+ while(scan<newsize) {
+ oldscore=0;
+
+ for(scsc=scan+=len;scan<=newsize - 1;scan++) {
+ len=search(I,old,oldsize,new+scan,newsize-scan,
+ 0,oldsize,&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 ((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)", argv[3]);
+ if (fclose(pf))
+ err(1, "fclose");
+
+ /* Free the memory we used */
+ free(db);
+ free(eb);
+ free(I);
+ free(old);
+ free(new);
+
+ return 0;
+}
Index: othersrc/external/bsd/delta/bin/3
diff -u /dev/null othersrc/external/bsd/delta/bin/3:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/bin/3 Thu Apr 28 05:21:31 2016
@@ -0,0 +1,751 @@
+/*-
+ * Copyright 2003-2005 Colin Percival
+ * All rights reserved
+ * Copyright (c) 2016 Alistair Crooks <a...@netbsd.org>
+ * 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 <fcntl.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "bsdiff.h"
+
+/* an output buffer structure */
+typedef struct obuf_t {
+ uint64_t c; /* # of characters used */
+ uint64_t size; /* output buffer size */
+ uint8_t *v; /* the array of chars */
+} obuf_t;
+
+/* the binary diff structure */
+typedef struct bsdiff_t {
+ obuf_t control; /* output buffer for control info */
+ uint8_t *diff; /* diff text */
+ size_t difflen; /* diff text length */
+ uint8_t *extra; /* extra text */
+ size_t extralen; /* extra text length */
+ off_t newsize; /* size of output */
+ uint8_t allocctl; /* ctl was allocated */
+ uint8_t allocdiff; /* diff was allocated */
+ uint8_t allocextra; /* extra was allocated */
+} bsdiff_t;
+
+#ifndef MIN
+#define MIN(x,y) (((x) < (y)) ? (x) : (y))
+#endif
+
+#ifndef ABS
+#define ABS(x) (((x) < 0) ? -(x) : (x))
+#endif
+
+#ifndef howmany
+#define howmany(x, y) (((x)+((y)-1))/(y))
+#endif
+
+/* add the info to the obuf buffer */
+static int
+owrite(obuf_t *obuf, const void *p, size_t size)
+{
+ uint8_t *newv;
+ size_t newsize;
+
+ if (obuf->c + size >= obuf->size) {
+ newsize = howmany(obuf->c + size, 4096) * 4096;
+ newv = realloc(obuf->v, newsize);
+ if (newv == NULL) {
+ return 0;
+ }
+ obuf->size = newsize;
+ obuf->v = newv;
+ }
+ memcpy(&obuf->v[obuf->c], p, size);
+ obuf->c += size;
+ return 1;
+}
+
+static void
+split(off_t *I, off_t *V, off_t start, off_t len, off_t h)
+{
+ off_t i, j, k, x, tmp, jj, kk;
+
+ if (len < 16) {
+ for (k = start; k < start + len; k += j) {
+ j = 1;
+ x = V[I[k] + h];
+ for (i = 1; k + i < start + len; i++) {
+ if (V[I[k + i] + h] < x) {
+ x = V[I[k + i] + h];
+ j = 0;
+ }
+ if (V[I[k + i] + h] == x) {
+ tmp = I[k + j];
+ I[k + j] = I[k + i];
+ I[k + i] = tmp;
+ j++;
+ }
+ }
+ for (i = 0; i < j; i++)
+ V[I[k + i]] = k + j - 1;
+ if (j == 1)
+ I[k] = -1;
+ }
+ return;
+ }
+
+ x = V[I[start + len / 2] + h];
+ jj = 0;
+ kk = 0;
+ for (i = start; i < start + len; i++) {
+ if (V[I[i] + h] < x)
+ jj++;
+ if (V[I[i] + h] == x)
+ kk++;
+ }
+ jj += start;
+ kk += jj;
+
+ j = k = 0;
+ for (i = start; i < jj ; ) {
+ if (V[I[i] + h] < x) {
+ i++;
+ } else if (V[I[i] + h] == x) {
+ tmp = I[i];
+ I[i] = I[jj + j];
+ I[jj + j] = tmp;
+ j++;
+ } else {
+ tmp = I[i];
+ I[i] = I[kk + k];
+ I[kk + k] = tmp;
+ k++;
+ }
+ }
+ while (jj + j < kk) {
+ if (V[I[jj + j] + h] == x) {
+ j++;
+ } else {
+ tmp = I[jj + j];
+ I[jj + j] = I[kk + k];
+ I[kk + k] = tmp;
+ k++;
+ }
+ }
+
+ if (jj > start) {
+ split(I, V, start, jj - start, h);
+ }
+ for (i = 0; i < kk - jj; i++) {
+ V[I[jj + i]] = kk - 1;
+ }
+ if (jj == kk - 1) {
+ I[jj] = -1;
+ }
+ if (start + len > kk) {
+ split(I, V, kk, start + len - kk, h);
+ }
+}
+
+static void
+qsufsort(off_t *I, off_t *V, const uint8_t *old, off_t oldsize)
+{
+ off_t buckets[256];
+ off_t i, h, len;
+
+ memset(buckets, 0x0, sizeof(buckets));
+ for (i = 0; i < oldsize; i++) {
+ buckets[old[i]]++;
+ }
+ for (i = 1; i < 256; i++) {
+ buckets[i] += buckets[i - 1];
+ }
+ for (i = 255; i > 0; i--) {
+ buckets[i] = buckets[i - 1];
+ }
+ buckets[0] = 0;
+
+ for (i = 0; i < oldsize; i++) {
+ I[++buckets[old[i]]] = i;
+ }
+ I[0] = oldsize;
+ for (i = 0; i < oldsize; i++) {
+ V[i] = buckets[old[i]];
+ }
+ V[oldsize] = 0;
+ for (i = 1; i < 256; i++) {
+ if (buckets[i] == buckets[i - 1] + 1) {
+ I[buckets[i]] = -1;
+ }
+ }
+ I[0] = -1;
+
+ for (h = 1; I[0] != -(oldsize + 1); h += h) {
+ for (len = 0, i = 0; i < oldsize + 1;) {
+ if (I[i] < 0) {
+ len -= I[i];
+ i -= I[i];
+ } else {
+ if (len) {
+ I[i - len] = -len;
+ }
+ len = V[I[i]] + 1 - i;
+ split(I, V, i, len, h);
+ i += len;
+ len = 0;
+ }
+ }
+ if (len) {
+ I[i - len] = -len;
+ }
+ }
+
+ for (i = 0; i < oldsize + 1; i++) {
+ I[V[i]] = i;
+ }
+}
+
+static off_t
+matchlen(const uint8_t *old, off_t oldsize, const uint8_t *newv, off_t newsize)
+{
+ off_t i;
+
+ for (i = 0; i < oldsize && i < newsize && old[i] == newv[i] ; i++) {
+ }
+ return i;
+}
+
+static off_t
+search(off_t *I, const uint8_t *old, off_t oldsize,
+ const uint8_t *newv, off_t newsize, off_t st, off_t en, size_t *pos)
+{
+ off_t x, y;
+
+ if (en - st < 2) {
+ x = matchlen(old + I[st], oldsize - I[st], newv, newsize);
+ y = matchlen(old + I[en], oldsize - I[en], newv, 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], newv, MIN(oldsize - I[x], newsize)) < 0) {
+ return search(I, old, oldsize, newv, newsize, x, en, pos);
+ } else {
+ return search(I, old, oldsize, newv, newsize, st, x, pos);
+ }
+}
+
+/* encode in zigzag encoding */
+static int
+put64(off_t x, uint8_t *buf)
+{
+ uint64_t n;
+ uint8_t *b;
+ int len;
+ int i;
+
+ n = (x << 1) ^ (x >> 63);
+ for (len = 0, b = buf, i = 0 ; i < 9 ; i++, b += len) {
+ *b = ((n >> ((9 - i) * 7)) & 0x7f) | 0x80;
+ if (len == 0 && *b != 0x80) {
+ len = 1;
+ }
+ }
+ *b++ = (n & 0x7f);
+ return (int)(b - buf);
+}
+
+/* decode from zigzag encoding */
+static int64_t
+get64(uint8_t *buf, size_t *len)
+{
+ uint64_t n;
+
+ for (n = 0, *len = 0 ; *len < 10 ; *len += 1) {
+ n = (n << 7) + (buf[*len] & 0x7f);
+ if ((buf[*len] & 0x80) == 0) {
+ *len += 1;
+ break;
+ }
+ }
+ return (n >> 1) ^ (-(n & 1));
+}
+
+/* read the file into the array */
+static int
+readfile(const char *f, uint8_t **v, off_t *size)
+{
+ ssize_t cc;
+ ssize_t rc;
+ int fd;
+
+ if (((fd = open(f, O_RDONLY, 0)) < 0) ||
+ ((*size = lseek(fd, 0, SEEK_END)) == -1) ||
+ ((*v = malloc(*size + 1)) == NULL) ||
+ (lseek(fd, 0, SEEK_SET) != 0)) {
+ warn("can't read file '%s'", f);
+ return 0;
+ }
+ for (cc = 0 ; cc < *size ; cc += rc) {
+ if ((rc = read(fd, &(*v)[cc], *size - cc)) < 0) {
+ break;
+ }
+ }
+ close(fd);
+ return cc == *size;
+}
+
+/* write the array to the file */
+static int
+writefile(const char *f, uint8_t *v, off_t size)
+{
+ ssize_t cc;
+ ssize_t wc;
+ int fd;
+
+ /* Write the new file */
+ if ((fd = open(f, O_CREAT | O_TRUNC | O_WRONLY, 0666)) < 0) {
+ warn("can't write file '%s'", f);
+ return 0;
+ }
+ for (cc = 0 ; cc < size ; cc += wc) {
+ if ((wc = write(fd, &v[cc], size - cc)) < 0) {
+ break;
+ }
+ }
+ close(fd);
+ return cc == size;
+}
+
+/***********************************************************************/
+
+/* write the patch file from info held in delta struct */
+int
+bsdiff_write_patch_file(bsdiff_t *delta, const char *patchfile)
+{
+ unsigned zsize;
+ uint8_t buf[10];
+ size_t cc;
+ size_t wc;
+ size_t n;
+ obuf_t o;
+ FILE *fp;
+ char *z;
+
+ if (delta == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&o, 0x0, sizeof(o));
+ owrite(&o, "BSDIFF50", 8);
+ n = put64(delta->control.c, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->difflen, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->extralen, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->newsize, buf);
+ owrite(&o, buf, n);
+ if ((fp = fopen(patchfile, "w")) == NULL) {
+ warn("can't open '%s' for writing", patchfile);
+ return 0;
+ }
+ for (cc = 0 ; cc < o.c ; cc += wc) {
+ if ((wc = fwrite(&o.v[cc], 1, o.c - cc, fp)) == 0) {
+ break;
+ }
+ }
+ o.c = 0;
+ /* control info */
+ owrite(&o, delta->control.v, delta->control.c);
+ /* diff info */
+ owrite(&o, delta->diff, delta->difflen);
+ /* extra info */
+ owrite(&o, delta->extra, delta->extralen);
+ n = delta->control.c + delta->difflen + delta->extralen;
+ zsize = ((n + 128) * 101) / 100;
+ z = calloc(1, zsize);
+ BZ2_bzBuffToBuffCompress(z, &zsize, (char *)o.v, o.c, 9, 0, 0);
+ for (cc = 0 ; cc < zsize ; cc += wc) {
+ if ((wc = fwrite(&z[cc], 1, zsize - cc, fp)) == 0) {
+ break;
+ }
+ }
+ free(z);
+ free(o.v);
+ fclose(fp);
+ return cc == zsize;
+}
+
+/* read the patch file into the delta struct */
+int
+bsdiff_read_patch_file(bsdiff_t *delta, const char *patchfile)
+{
+ unsigned zsize;
+ size_t len;
+ size_t cc;
+ obuf_t o;
+ off_t size;
+ char *z;
+
+ if (delta == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(delta, 0x0, sizeof(*delta));
+ memset(&o, 0x0, sizeof(o));
+ if (!readfile(patchfile, &o.v, &size)) {
+ return 0;
+ }
+ o.c = o.size = size;
+ if (memcmp(o.v, "BSDIFF50", 8) != 0) {
+ warnx("not a patch at offset 0");
+ return 0;
+ }
+ cc = 8;
+ delta->control.c = get64(&o.v[cc], &len);
+ cc += len;
+ delta->difflen = get64(&o.v[cc], &len);
+ cc += len;
+ delta->extralen = get64(&o.v[cc], &len);
+ cc += len;
+ delta->newsize = get64(&o.v[cc], &len);
+ cc += len;
+ zsize = delta->control.c + delta->difflen + delta->extralen;
+ if ((z = calloc(1, zsize)) == NULL ||
+ BZ2_bzBuffToBuffDecompress(z, &zsize, (char *)&o.v[cc], size - cc, 0, 0) != BZ_OK) {
+ warn("resource allocation reading patch file");
+ return 0;
+ }
+ delta->allocctl = 1;
+ delta->control.v = (uint8_t *)z;
+ delta->diff = (uint8_t *)&z[delta->control.c];
+ delta->extra = (uint8_t *)&z[delta->control.c + delta->difflen];
+ free(o.v);
+ return 1;
+}
+
+/* diff 2 areas of memory */
+int
+bsdiff_diff_mem(bsdiff_t *delta, const void *aold, size_t oldsize, const void *anewv, size_t newsize)
+{
+ const uint8_t *old = (const uint8_t *)aold;
+ const uint8_t *newv = (const uint8_t *)anewv;
+ uint8_t buf[10];
+ off_t *I, *V;
+ size_t lastscan;
+ size_t overlap;
+ size_t scan;
+ size_t scsc;
+ size_t lenb;
+ size_t lenf;
+ size_t pos;
+ size_t Sb;
+ size_t Sf;
+ size_t Ss;
+ size_t s;
+ size_t i;
+ off_t len;
+ off_t lastpos, lastoffset;
+ off_t oldscore;
+ off_t lens;
+ int buflen;
+
+ if (delta == NULL || old == NULL || newv == NULL) {
+ return 0;
+ }
+ memset(delta, 0x0, sizeof(*delta));
+ if (((I = malloc((oldsize + 1) * sizeof(*I))) == NULL) ||
+ ((V = malloc((oldsize + 1) * sizeof(*V))) == NULL)) {
+ warn("allocation failure in bsd_diff_mem");
+ return 0;
+ }
+ qsufsort(I, V, old, oldsize);
+ free(V);
+ /*
+ * Allocate newsize+1 bytes instead of newsize bytes to ensure that
+ * we never try to malloc(0) and get a NULL pointer
+ */
+ delta->newsize = newsize;
+ if (((delta->diff = malloc(newsize + 1)) == NULL) ||
+ ((delta->extra = malloc(newsize + 1)) == NULL)) {
+ warn("allocation failure 2 in bsd_diff_mem");
+ return 0;
+ }
+ delta->allocdiff = delta->allocextra = 1;
+ scan = 0;
+ len = 0;
+ lastscan = 0;
+ lastpos = 0;
+ lastoffset = 0;
+ while (scan < newsize) {
+ oldscore = 0;
+ for (scsc = scan += len; scan < newsize; scan++) {
+ len = search(I, old, oldsize, newv + scan, newsize - scan,
+ 0, oldsize, &pos);
+
+ for (; scsc < scan + len; scsc++)
+ if ((scsc + lastoffset < oldsize) &&
+ (old[scsc + lastoffset] == newv[scsc])) {
+ oldscore++;
+ }
+ if (((len == oldscore) && (len != 0)) ||
+ (len > oldscore + 8)) {
+ break;
+ }
+ if ((scan + lastoffset < oldsize) &&
+ (old[scan + lastoffset] == newv[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] == newv[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] == newv[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 (newv[lastscan + lenf - overlap + i] ==
+ old[lastpos + lenf - overlap + i]) {
+ s++;
+ }
+ if (newv[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++) {
+ delta->diff[delta->difflen + i] = newv[lastscan + i] - old[lastpos + i];
+ }
+ for (i = 0; i < (scan - lenb) - (lastscan + lenf); i++) {
+ delta->extra[delta->extralen + i] = newv[lastscan + lenf + i];
+ }
+ delta->difflen += lenf;
+ delta->extralen += (scan - lenb) - (lastscan + lenf);
+
+ buflen = put64(lenf, buf);
+ owrite(&delta->control, buf, buflen);
+
+ buflen = put64((scan - lenb) - (lastscan + lenf), buf);
+ owrite(&delta->control, buf, buflen);
+ buflen = put64((pos - lenb) - (lastpos + lenf), buf);
+ owrite(&delta->control, buf, buflen);
+ lastscan = scan - lenb;
+ lastpos = pos - lenb;
+ lastoffset = pos - scan;
+ }
+ }
+ free(I);
+ return 1;
+}
+
+/* diff two files, putting results in patch file */
+int
+bsdiff_diff_file(const char *oldfile, const char *newfile, const char *patchfile)
+{
+ bsdiff_t delta;
+ uint8_t *oldv;
+ uint8_t *newv;
+ off_t oldsize;
+ off_t newsize;
+ int ok;
+
+ if (oldfile == NULL || newfile == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&delta, 0x0, sizeof(delta));
+ if (!readfile(oldfile, &oldv, &oldsize) ||
+ !readfile(newfile, &newv, &newsize)) {
+ return 0;
+ }
+ if (!bsdiff_diff_mem(&delta, oldv, oldsize, newv, newsize)) {
+ return 0;
+ }
+ ok = bsdiff_write_patch_file(&delta, patchfile);
+ if (!ok) {
+ return 0;
+ }
+ /* Free the memory we used */
+ bsdiff_free(&delta);
+ free(oldv);
+ free(newv);
+ return 1;
+}
+
+/* patch using a binary patch */
+int
+bsdiff_patch_mem(bsdiff_t *delta, const void *aold, size_t oldsize, void *anewv, size_t *newsize)
+{
+ const uint8_t *old = (const uint8_t *)aold;
+ uint8_t **newv = (uint8_t **)anewv;
+ size_t extrac;
+ size_t diffc;
+ size_t ctlc;
+ size_t len;
+ off_t ctrl[3];
+ off_t oldpos;
+ off_t newpos;
+ off_t i;
+
+ if (delta == NULL || old == NULL || newv == NULL) {
+ return 0;
+ }
+ if ((*newv = malloc(delta->newsize + 1)) == NULL) {
+ warn("allocation failure %zu bytes", delta->newsize + 1);
+ return 0;
+ }
+ for (oldpos = newpos = 0, ctlc = diffc = extrac = 0; newpos < delta->newsize ; ) {
+ /* Read control data */
+ for (i = 0; i < 3; i++) {
+ ctrl[i] = get64(&delta->control.v[ctlc], &len);
+ ctlc += len;
+ }
+ /* Sanity-check */
+ if (newpos + ctrl[0] > delta->newsize) {
+ warnx("Corrupt patch 1\n");
+ return 0;
+ }
+ /* Read diff string */
+ memcpy(&(*newv)[newpos], &delta->diff[diffc], ctrl[0]);
+ diffc += ctrl[0];
+ /* Add old data to diff string */
+ for (i = 0; i < ctrl[0]; i++) {
+ if ((oldpos + i >= 0) && (oldpos + i < (off_t)oldsize)) {
+ (*newv)[newpos + i] += old[oldpos + i];
+ }
+ }
+ /* Adjust pointers */
+ newpos += ctrl[0];
+ oldpos += ctrl[0];
+ /* Sanity-check */
+ if (newpos + ctrl[1] > delta->newsize) {
+ warnx("Corrupt patch 2\n");
+ return 0;
+ }
+ /* Read extra string */
+ memcpy(*newv + newpos, &delta->extra[extrac], ctrl[1]);
+ extrac += ctrl[1];
+ /* Adjust pointers */
+ newpos += ctrl[1];
+ oldpos += ctrl[2];
+ }
+ *newsize = delta->newsize;
+ return 1;
+}
+
+/* patch using a binary patch */
+int
+bsdiff_patch_file(const char *oldfile, const char *newfile, const char *patchfile)
+{
+ bsdiff_t delta;
+ ssize_t oldsize;
+ uint8_t *newv;
+ uint8_t *old;
+ size_t newsize;
+
+ if (oldfile == NULL || newfile == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&delta, 0x0, sizeof(delta));
+ if (!bsdiff_read_patch_file(&delta, patchfile)) {
+ return 0;
+ }
+ if (!readfile(oldfile, &old, &oldsize)) {
+ warn("%s", oldfile);
+ return 0;
+ }
+ if (!bsdiff_patch_mem(&delta, old, oldsize, &newv, &newsize)) {
+ return 0;
+ }
+ if (!writefile(newfile, newv, delta.newsize)) {
+ warn("%s", newfile);
+ return 0;
+ }
+ bsdiff_free(&delta);
+ return 1;
+}
+
+/* free resources associated with delta struct */
+void
+bsdiff_free(bsdiff_t *delta)
+{
+ if (delta) {
+ if (delta->allocctl) {
+ free(delta->control.v);
+ }
+ if (delta->allocdiff) {
+ free(delta->diff);
+ }
+ if (delta->allocextra) {
+ free(delta->extra);
+ }
+ }
+}
+
+/* make a new struct */
+bsdiff_t *
+bsdiff_new(void)
+{
+ return calloc(1, sizeof(bsdiff_t));
+}
Index: othersrc/external/bsd/delta/bin/4
diff -u /dev/null othersrc/external/bsd/delta/bin/4:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/bin/4 Thu Apr 28 05:21:31 2016
@@ -0,0 +1,751 @@
+/*-
+ * Copyright 2003-2005 Colin Percival
+ * All rights reserved
+ * Copyright (c) 2016 Alistair Crooks <a...@netbsd.org>
+ * 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 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.
+ * 2. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * 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 <fcntl.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "bsdiff.h"
+
+/* an output buffer structure */
+typedef struct obuf_t {
+ uint64_t c; /* # of characters used */
+ uint64_t size; /* output buffer size */
+ uint8_t *v; /* the array of chars */
+} obuf_t;
+
+/* the binary diff structure */
+typedef struct bsdiff_t {
+ obuf_t control; /* output buffer for control info */
+ uint8_t *diff; /* diff text */
+ size_t difflen; /* diff text length */
+ uint8_t *extra; /* extra text */
+ size_t extralen; /* extra text length */
+ off_t newsize; /* size of output */
+ uint8_t allocctl; /* ctl was allocated */
+ uint8_t allocdiff; /* diff was allocated */
+ uint8_t allocextra; /* extra was allocated */
+} bsdiff_t;
+
+#ifndef MIN
+#define MIN(x,y) (((x) < (y)) ? (x) : (y))
+#endif
+
+#ifndef ABS
+#define ABS(x) (((x) < 0) ? -(x) : (x))
+#endif
+
+#ifndef howmany
+#define howmany(x, y) (((x)+((y)-1))/(y))
+#endif
+
+/* add the info to the obuf buffer */
+static int
+owrite(obuf_t *obuf, const void *p, size_t size)
+{
+ uint8_t *newv;
+ size_t newsize;
+
+ if (obuf->c + size >= obuf->size) {
+ newsize = howmany(obuf->c + size, 4096) * 4096;
+ newv = realloc(obuf->v, newsize);
+ if (newv == NULL) {
+ return 0;
+ }
+ obuf->size = newsize;
+ obuf->v = newv;
+ }
+ memcpy(&obuf->v[obuf->c], p, size);
+ obuf->c += size;
+ return 1;
+}
+
+static void
+split(off_t *I, off_t *V, off_t start, off_t len, off_t h)
+{
+ off_t i, j, k, x, tmp, jj, kk;
+
+ if (len <= 15) {
+ for (k = start; k < start + len; k += j) {
+ j = 1;
+ x = V[I[k] + h];
+ for (i = 1; k + i < start + len; i++) {
+ if (V[I[k + i] + h] < x) {
+ x = V[I[k + i] + h];
+ j = 0;
+ }
+ if (V[I[k + i] + h] == x) {
+ tmp = I[k + j];
+ I[k + j] = I[k + i];
+ I[k + i] = tmp;
+ j++;
+ }
+ }
+ for (i = 0; i < j; i++)
+ V[I[k + i]] = k + j - 1;
+ if (j == 1)
+ I[k] = -1;
+ }
+ return;
+ }
+
+ x = V[I[start + len / 2] + h];
+ jj = 0;
+ kk = 0;
+ for (i = start; i < start + len; i++) {
+ if (V[I[i] + h] < x)
+ jj++;
+ if (V[I[i] + h] == x)
+ kk++;
+ }
+ jj += start;
+ kk += jj;
+
+ j = k = 0;
+ for (i = start; i < jj ; ) {
+ if (V[I[i] + h] < x) {
+ i++;
+ } else if (V[I[i] + h] == x) {
+ tmp = I[i];
+ I[i] = I[jj + j];
+ I[jj + j] = tmp;
+ j++;
+ } else {
+ tmp = I[i];
+ I[i] = I[kk + k];
+ I[kk + k] = tmp;
+ k++;
+ }
+ }
+ while (jj + j < kk) {
+ if (V[I[jj + j] + h] == x) {
+ j++;
+ } else {
+ tmp = I[jj + j];
+ I[jj + j] = I[kk + k];
+ I[kk + k] = tmp;
+ k++;
+ }
+ }
+
+ if (jj > start) {
+ split(I, V, start, jj - start, h);
+ }
+ for (i = 0; i < kk - jj; i++) {
+ V[I[jj + i]] = kk - 1;
+ }
+ if (jj == kk - 1) {
+ I[jj] = -1;
+ }
+ if (start + len > kk) {
+ split(I, V, kk, start + len - kk, h);
+ }
+}
+
+static void
+qsufsort(off_t *I, off_t *V, const uint8_t *old, off_t oldsize)
+{
+ off_t buckets[256];
+ off_t i, h, len;
+
+ memset(buckets, 0x0, sizeof(buckets));
+ for (i = 0; i < oldsize; i++) {
+ buckets[old[i]]++;
+ }
+ for (i = 1; i < 256; i++) {
+ buckets[i] += buckets[i - 1];
+ }
+ for (i = 255; i > 0; i--) {
+ buckets[i] = buckets[i - 1];
+ }
+ buckets[0] = 0;
+
+ for (i = 0; i < oldsize; i++) {
+ I[++buckets[old[i]]] = i;
+ }
+ I[0] = oldsize;
+ for (i = 0; i < oldsize; i++) {
+ V[i] = buckets[old[i]];
+ }
+ V[oldsize] = 0;
+ for (i = 1; i < 256; i++) {
+ if (buckets[i] == buckets[i - 1] + 1) {
+ I[buckets[i]] = -1;
+ }
+ }
+ I[0] = -1;
+
+ for (h = 1; I[0] != -(oldsize + 1); h += h) {
+ for (len = 0, i = 0; i < oldsize + 1;) {
+ if (I[i] < 0) {
+ len -= I[i];
+ i -= I[i];
+ } else {
+ if (len) {
+ I[i - len] = -len;
+ }
+ len = V[I[i]] + 1 - i;
+ split(I, V, i, len, h);
+ i += len;
+ len = 0;
+ }
+ }
+ if (len) {
+ I[i - len] = -len;
+ }
+ }
+
+ for (i = 0; i < oldsize + 1; i++) {
+ I[V[i]] = i;
+ }
+}
+
+static off_t
+matchlen(const uint8_t *old, off_t oldsize, const uint8_t *newv, off_t newsize)
+{
+ off_t i;
+
+ for (i = 0; i < oldsize && i < newsize && old[i] == newv[i] ; i++) {
+ }
+ return i;
+}
+
+static off_t
+search(off_t *I, const uint8_t *old, off_t oldsize,
+ const uint8_t *newv, off_t newsize, off_t st, off_t en, size_t *pos)
+{
+ off_t x, y;
+
+ if (en - st < 2) {
+ x = matchlen(old + I[st], oldsize - I[st], newv, newsize);
+ y = matchlen(old + I[en], oldsize - I[en], newv, 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], newv, MIN(oldsize - I[x], newsize)) < 0) {
+ return search(I, old, oldsize, newv, newsize, x, en, pos);
+ } else {
+ return search(I, old, oldsize, newv, newsize, st, x, pos);
+ }
+}
+
+/* encode in zigzag encoding */
+static int
+put64(off_t x, uint8_t *buf)
+{
+ uint64_t n;
+ uint8_t *b;
+ int len;
+ int i;
+
+ n = (x << 1) ^ (x >> 63);
+ for (len = 0, b = buf, i = 0 ; i < 9 ; i++, b += len) {
+ *b = ((n >> ((9 - i) * 7)) & 0x7f) | 0x80;
+ if (len == 0 && *b != 0x80) {
+ len = 1;
+ }
+ }
+ *b++ = (n & 0x7f);
+ return (int)(b - buf);
+}
+
+/* decode from zigzag encoding */
+static int64_t
+get64(uint8_t *buf, size_t *len)
+{
+ uint64_t n;
+
+ for (n = 0, *len = 0 ; *len < 10 ; *len += 1) {
+ n = (n << 7) + (buf[*len] & 0x7f);
+ if ((buf[*len] & 0x80) == 0) {
+ *len += 1;
+ break;
+ }
+ }
+ return (n >> 1) ^ (-(n & 1));
+}
+
+/* read the file into the array */
+static int
+readfile(const char *f, uint8_t **v, off_t *size)
+{
+ ssize_t cc;
+ ssize_t rc;
+ int fd;
+
+ if (((fd = open(f, O_RDONLY, 0)) < 0) ||
+ ((*size = lseek(fd, 0, SEEK_END)) == -1) ||
+ ((*v = malloc(*size + 1)) == NULL) ||
+ (lseek(fd, 0, SEEK_SET) != 0)) {
+ warn("can't read file '%s'", f);
+ return 0;
+ }
+ for (cc = 0 ; cc < *size ; cc += rc) {
+ if ((rc = read(fd, &(*v)[cc], *size - cc)) < 0) {
+ break;
+ }
+ }
+ close(fd);
+ return cc == *size;
+}
+
+/* write the array to the file */
+static int
+writefile(const char *f, uint8_t *v, off_t size)
+{
+ ssize_t cc;
+ ssize_t wc;
+ int fd;
+
+ /* Write the new file */
+ if ((fd = open(f, O_CREAT | O_TRUNC | O_WRONLY, 0666)) < 0) {
+ warn("can't write file '%s'", f);
+ return 0;
+ }
+ for (cc = 0 ; cc < size ; cc += wc) {
+ if ((wc = write(fd, &v[cc], size - cc)) < 0) {
+ break;
+ }
+ }
+ close(fd);
+ return cc == size;
+}
+
+/***********************************************************************/
+
+/* write the patch file from info held in delta struct */
+int
+bsdiff_write_patch_file(bsdiff_t *delta, const char *patchfile)
+{
+ unsigned zsize;
+ uint8_t buf[10];
+ size_t cc;
+ size_t wc;
+ size_t n;
+ obuf_t o;
+ FILE *fp;
+ char *z;
+
+ if (delta == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&o, 0x0, sizeof(o));
+ owrite(&o, "BSDIFF50", 8);
+ n = put64(delta->control.c, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->difflen, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->extralen, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->newsize, buf);
+ owrite(&o, buf, n);
+ if ((fp = fopen(patchfile, "w")) == NULL) {
+ warn("can't open '%s' for writing", patchfile);
+ return 0;
+ }
+ for (cc = 0 ; cc < o.c ; cc += wc) {
+ if ((wc = fwrite(&o.v[cc], 1, o.c - cc, fp)) == 0) {
+ break;
+ }
+ }
+ o.c = 0;
+ /* control info */
+ owrite(&o, delta->control.v, delta->control.c);
+ /* diff info */
+ owrite(&o, delta->diff, delta->difflen);
+ /* extra info */
+ owrite(&o, delta->extra, delta->extralen);
+ n = delta->control.c + delta->difflen + delta->extralen;
+ zsize = ((n + 128) * 101) / 100;
+ z = calloc(1, zsize);
+ BZ2_bzBuffToBuffCompress(z, &zsize, (char *)o.v, o.c, 9, 0, 0);
+ for (cc = 0 ; cc < zsize ; cc += wc) {
+ if ((wc = fwrite(&z[cc], 1, zsize - cc, fp)) == 0) {
+ break;
+ }
+ }
+ free(z);
+ free(o.v);
+ fclose(fp);
+ return cc == zsize;
+}
+
+/* read the patch file into the delta struct */
+int
+bsdiff_read_patch_file(bsdiff_t *delta, const char *patchfile)
+{
+ unsigned zsize;
+ size_t len;
+ size_t cc;
+ obuf_t o;
+ off_t size;
+ char *z;
+
+ if (delta == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(delta, 0x0, sizeof(*delta));
+ memset(&o, 0x0, sizeof(o));
+ if (!readfile(patchfile, &o.v, &size)) {
+ return 0;
+ }
+ o.c = o.size = size;
+ if (memcmp(o.v, "BSDIFF50", 8) != 0) {
+ warnx("not a patch at offset 0");
+ return 0;
+ }
+ cc = 8;
+ delta->control.c = get64(&o.v[cc], &len);
+ cc += len;
+ delta->difflen = get64(&o.v[cc], &len);
+ cc += len;
+ delta->extralen = get64(&o.v[cc], &len);
+ cc += len;
+ delta->newsize = get64(&o.v[cc], &len);
+ cc += len;
+ zsize = delta->control.c + delta->difflen + delta->extralen;
+ if ((z = calloc(1, zsize)) == NULL ||
+ BZ2_bzBuffToBuffDecompress(z, &zsize, (char *)&o.v[cc], size - cc, 0, 0) != BZ_OK) {
+ warn("resource allocation reading patch file");
+ return 0;
+ }
+ delta->allocctl = 1;
+ delta->control.v = (uint8_t *)z;
+ delta->diff = (uint8_t *)&z[delta->control.c];
+ delta->extra = (uint8_t *)&z[delta->control.c + delta->difflen];
+ free(o.v);
+ return 1;
+}
+
+/* diff 2 areas of memory */
+int
+bsdiff_diff_mem(bsdiff_t *delta, const void *aold, size_t oldsize, const void *anewv, size_t newsize)
+{
+ const uint8_t *old = (const uint8_t *)aold;
+ const uint8_t *newv = (const uint8_t *)anewv;
+ uint8_t buf[10];
+ off_t *I, *V;
+ size_t lastscan;
+ size_t overlap;
+ size_t scan;
+ size_t scsc;
+ size_t lenb;
+ size_t lenf;
+ size_t pos;
+ size_t Sb;
+ size_t Sf;
+ size_t Ss;
+ size_t s;
+ size_t i;
+ off_t len;
+ off_t lastpos, lastoffset;
+ off_t oldscore;
+ off_t lens;
+ int buflen;
+
+ if (delta == NULL || old == NULL || newv == NULL) {
+ return 0;
+ }
+ memset(delta, 0x0, sizeof(*delta));
+ if (((I = malloc((oldsize + 1) * sizeof(*I))) == NULL) ||
+ ((V = malloc((oldsize + 1) * sizeof(*V))) == NULL)) {
+ warn("allocation failure in bsd_diff_mem");
+ return 0;
+ }
+ qsufsort(I, V, old, oldsize);
+ free(V);
+ /*
+ * Allocate newsize+1 bytes instead of newsize bytes to ensure that
+ * we never try to malloc(0) and get a NULL pointer
+ */
+ delta->newsize = newsize;
+ if (((delta->diff = malloc(newsize + 1)) == NULL) ||
+ ((delta->extra = malloc(newsize + 1)) == NULL)) {
+ warn("allocation failure 2 in bsd_diff_mem");
+ return 0;
+ }
+ delta->allocdiff = delta->allocextra = 1;
+ scan = 0;
+ len = 0;
+ lastscan = 0;
+ lastpos = 0;
+ lastoffset = 0;
+ while (scan < newsize) {
+ oldscore = 0;
+ for (scsc = scan += len; scan < newsize; scan++) {
+ len = search(I, old, oldsize, newv + scan, newsize - scan,
+ 0, oldsize, &pos);
+
+ for (; scsc < scan + len; scsc++)
+ if ((scsc + lastoffset < oldsize) &&
+ (old[scsc + lastoffset] == newv[scsc])) {
+ oldscore++;
+ }
+ if (((len == oldscore) && (len != 0)) ||
+ (len > oldscore + 8)) {
+ break;
+ }
+ if ((scan + lastoffset < oldsize) &&
+ (old[scan + lastoffset] == newv[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] == newv[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] == newv[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 (newv[lastscan + lenf - overlap + i] ==
+ old[lastpos + lenf - overlap + i]) {
+ s++;
+ }
+ if (newv[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++) {
+ delta->diff[delta->difflen + i] = newv[lastscan + i] - old[lastpos + i];
+ }
+ for (i = 0; i < (scan - lenb) - (lastscan + lenf); i++) {
+ delta->extra[delta->extralen + i] = newv[lastscan + lenf + i];
+ }
+ delta->difflen += lenf;
+ delta->extralen += (scan - lenb) - (lastscan + lenf);
+
+ buflen = put64(lenf, buf);
+ owrite(&delta->control, buf, buflen);
+
+ buflen = put64((scan - lenb) - (lastscan + lenf), buf);
+ owrite(&delta->control, buf, buflen);
+ buflen = put64((pos - lenb) - (lastpos + lenf), buf);
+ owrite(&delta->control, buf, buflen);
+ lastscan = scan - lenb;
+ lastpos = pos - lenb;
+ lastoffset = pos - scan;
+ }
+ }
+ free(I);
+ return 1;
+}
+
+/* diff two files, putting results in patch file */
+int
+bsdiff_diff_file(const char *oldfile, const char *newfile, const char *patchfile)
+{
+ bsdiff_t delta;
+ uint8_t *oldv;
+ uint8_t *newv;
+ off_t oldsize;
+ off_t newsize;
+ int ok;
+
+ if (oldfile == NULL || newfile == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&delta, 0x0, sizeof(delta));
+ if (!readfile(oldfile, &oldv, &oldsize) ||
+ !readfile(newfile, &newv, &newsize)) {
+ return 0;
+ }
+ if (!bsdiff_diff_mem(&delta, oldv, oldsize, newv, newsize)) {
+ return 0;
+ }
+ ok = bsdiff_write_patch_file(&delta, patchfile);
+ if (!ok) {
+ return 0;
+ }
+ /* Free the memory we used */
+ bsdiff_free(&delta);
+ free(oldv);
+ free(newv);
+ return 1;
+}
+
+/* patch using a binary patch */
+int
+bsdiff_patch_mem(bsdiff_t *delta, const void *aold, size_t oldsize, void *anewv, size_t *newsize)
+{
+ const uint8_t *old = (const uint8_t *)aold;
+ uint8_t **newv = (uint8_t **)anewv;
+ size_t extrac;
+ size_t diffc;
+ size_t ctlc;
+ size_t len;
+ off_t ctrl[3];
+ off_t oldpos;
+ off_t newpos;
+ off_t i;
+
+ if (delta == NULL || old == NULL || newv == NULL) {
+ return 0;
+ }
+ if ((*newv = malloc(delta->newsize + 1)) == NULL) {
+ warn("allocation failure %zu bytes", delta->newsize + 1);
+ return 0;
+ }
+ for (oldpos = newpos = 0, ctlc = diffc = extrac = 0; newpos < delta->newsize ; ) {
+ /* Read control data */
+ for (i = 0; i < 3; i++) {
+ ctrl[i] = get64(&delta->control.v[ctlc], &len);
+ ctlc += len;
+ }
+ /* Sanity-check */
+ if (newpos + ctrl[0] > delta->newsize) {
+ warnx("Corrupt patch 1\n");
+ return 0;
+ }
+ /* Read diff string */
+ memcpy(&(*newv)[newpos], &delta->diff[diffc], ctrl[0]);
+ diffc += ctrl[0];
+ /* Add old data to diff string */
+ for (i = 0; i < ctrl[0]; i++) {
+ if ((oldpos + i >= 0) && (oldpos + i < (off_t)oldsize)) {
+ (*newv)[newpos + i] += old[oldpos + i];
+ }
+ }
+ /* Adjust pointers */
+ newpos += ctrl[0];
+ oldpos += ctrl[0];
+ /* Sanity-check */
+ if (newpos + ctrl[1] > delta->newsize) {
+ warnx("Corrupt patch 2\n");
+ return 0;
+ }
+ /* Read extra string */
+ memcpy(*newv + newpos, &delta->extra[extrac], ctrl[1]);
+ extrac += ctrl[1];
+ /* Adjust pointers */
+ newpos += ctrl[1];
+ oldpos += ctrl[2];
+ }
+ *newsize = delta->newsize;
+ return 1;
+}
+
+/* patch using a binary patch */
+int
+bsdiff_patch_file(const char *oldfile, const char *newfile, const char *patchfile)
+{
+ bsdiff_t delta;
+ ssize_t oldsize;
+ uint8_t *newv;
+ uint8_t *old;
+ size_t newsize;
+
+ if (oldfile == NULL || newfile == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&delta, 0x0, sizeof(delta));
+ if (!bsdiff_read_patch_file(&delta, patchfile)) {
+ warnx("can't read patchfile '%s'", patchfile);
+ return 0;
+ }
+ if (!readfile(oldfile, &old, &oldsize)) {
+ return 0;
+ }
+ if (!bsdiff_patch_mem(&delta, old, oldsize, &newv, &newsize)) {
+ return 0;
+ }
+ if (!writefile(newfile, newv, delta.newsize)) {
+ warn("%s", newfile);
+ return 0;
+ }
+ bsdiff_free(&delta);
+ return 1;
+}
+
+/* free resources associated with delta struct */
+void
+bsdiff_free(bsdiff_t *delta)
+{
+ if (delta) {
+ if (delta->allocctl) {
+ free(delta->control.v);
+ }
+ if (delta->allocextra) {
+ free(delta->extra);
+ }
+ if (delta->allocdiff) {
+ free(delta->diff);
+ }
+ }
+}
+
+/* make a new struct */
+bsdiff_t *
+bsdiff_new(void)
+{
+ return calloc(1, sizeof(bsdiff_t));
+}
Index: othersrc/external/bsd/delta/bin/Makefile
diff -u /dev/null othersrc/external/bsd/delta/bin/Makefile:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/bin/Makefile Thu Apr 28 05:21:31 2016
@@ -0,0 +1,53 @@
+# $NetBSD: Makefile,v 1.1 2016/04/28 05:21:31 agc Exp $
+
+.include <bsd.own.mk>
+
+PROG= delta
+SRCS= main.c
+BINDIR= /usr/bin
+
+CPPFLAGS+= -I${.CURDIR}/../dist/
+
+LIB_DELTA_DIR!= cd ${.CURDIR}/../lib && ${PRINTOBJDIR}
+LDADD+= -L${LIB_DELTA_DIR} -ldelta
+DPADD+= ${LIB_DELTA_DIR}/libdelta.a
+
+.ifndef PRODUCTION
+CPPFLAGS+=-g -O0
+LDFLAGS+=-g -O0
+.endif
+
+MAN= delta.1
+
+WARNS= 5
+
+.PATH: ${.CURDIR}/../dist
+
+.include <bsd.prog.mk>
+
+t:
+ @echo "1. basics"
+ env LD_LIBRARY_PATH=${.CURDIR}/../lib ./${PROG} -d 1 2 2.diff
+ env LD_LIBRARY_PATH=${.CURDIR}/../lib ./${PROG} -p 1 2.new 2.diff
+ diff 2 2.new
+ ls -al 1 2 2.new 2.diff
+ rm -f 2.new 2.diff
+ @echo "2. backwards"
+ env LD_LIBRARY_PATH=${.CURDIR}/../lib ./${PROG} -d 2 1 2.diff
+ env LD_LIBRARY_PATH=${.CURDIR}/../lib ./${PROG} -p 2 1.new 2.diff
+ diff 1 1.new
+ ls -al 1 2 1.new 2.diff
+ rm -f 1.new 2.diff
+ @echo "3. new patch file"
+ env LD_LIBRARY_PATH=${.CURDIR}/../lib ./${PROG} -d 2 1 2.diff
+ env LD_LIBRARY_PATH=${.CURDIR}/../lib ./${PROG} -p 2 1.new 2.diff
+ diff 1 1.new
+ ls -al 1 2 1.new 2.diff
+ rm -f 1.new 2.diff
+ @echo "4. more extensive changes"
+ env LD_LIBRARY_PATH=${.CURDIR}/../lib ./${PROG} -d 4 3 4.diff
+ env LD_LIBRARY_PATH=${.CURDIR}/../lib ./${PROG} -p 4 3.new 4.diff
+ diff 3 3.new
+ hexdump -C 4.diff
+ ls -al 3 4 3.new 4.diff
+ rm -f 3.new 4.diff
Index: othersrc/external/bsd/delta/dist/Makefile
diff -u /dev/null othersrc/external/bsd/delta/dist/Makefile:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/dist/Makefile Thu Apr 28 05:21:31 2016
@@ -0,0 +1,24 @@
+CFLAGS += -O3 -lbz2
+
+PREFIX ?= /usr/local
+INSTALL_PROGRAM ?= ${INSTALL} -c -s -m 555
+INSTALL_MAN ?= ${INSTALL} -c -m 444
+
+all: bsdiff bspatch
+
+bsdiff: bsdiff.c libbsdiff.c
+ ${CC} ${CFLAGS} bsdiff.c libbsdiff.c -o bsdiff
+bspatch: bspatch.c libbsdiff.c
+ ${CC} ${CFLAGS} bspatch.c libbsdiff.c -o bspatch
+
+install:
+ ${INSTALL_PROGRAM} bsdiff bspatch ${PREFIX}/bin
+.ifndef WITHOUT_MAN
+ ${INSTALL_MAN} bsdiff.1 bspatch.1 ${PREFIX}/man/man1
+.endif
+
+t:
+ ./bsdiff 2 1 2.diff
+ ./bspatch 2 1.new 2.diff
+ diff 1 1.new
+ rm -f 1.new 2.diff
Index: othersrc/external/bsd/delta/dist/delta.1
diff -u /dev/null othersrc/external/bsd/delta/dist/delta.1:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/dist/delta.1 Thu Apr 28 05:21:31 2016
@@ -0,0 +1,74 @@
+.\"-
+.\" 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 April 14, 2016
+.Dt DELTA 1
+.Os
+.Sh NAME
+.Nm delta
+.Nd manage deltas between two binary files
+.Sh SYNOPSIS
+.Nm
+.Op Fl dp
+.Ar oldfile newfile patchfile
+.Sh DESCRIPTION
+.Nm
+compares
+.Ao Ar oldfile Ac
+to
+.Ao Ar newfile Ac
+and writes to
+.Ao Ar patchfile Ac
+a binary patch suitable for use by bspatch(1).
+When
+.Ao Ar oldfile Ac
+and
+.Ao Ar newfile Ac
+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
+.Ao Ar oldfile Ac ,
+and requires
+an absolute minimum working set size of 8 times the size of oldfile.
+.Sh SEE ALSO
+.Xr libdelta 3
+.Sh HISTORY
+The
+.Nm
+program was first seen in
+.Nx 8 .
+.Sh AUTHORS
+The
+.Nm
+program was written by
+.An Alistair Crooks Aq Mt a...@netbsd.org .
+It was based on some much earlier code by
+.An Colin Percival .
Index: othersrc/external/bsd/delta/dist/delta.c
diff -u /dev/null othersrc/external/bsd/delta/dist/delta.c:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/dist/delta.c Thu Apr 28 05:21:31 2016
@@ -0,0 +1,47 @@
+/*-
+ * Copyright 2003-2005 Colin Percival
+ * All rights reserved
+ * Copyright (c) 2016 Alistair Crooks <a...@netbsd.org>
+ * 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 <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "delta.h"
+
+int
+main(int argc, char **argv)
+{
+ int i;
+
+ while ((i = getopt(argc, argv, "")) != -1) {
+ }
+ if (argc - optind != 3) {
+ errx(EXIT_FAILURE, "usage: %s oldfile newfile patchfile\n", argv[0]);
+ }
+ return delta_diff_file(argv[optind], argv[optind + 1], argv[optind + 2]) ? EXIT_SUCCESS : EXIT_FAILURE;
+}
Index: othersrc/external/bsd/delta/dist/delta.h
diff -u /dev/null othersrc/external/bsd/delta/dist/delta.h:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/dist/delta.h Thu Apr 28 05:21:31 2016
@@ -0,0 +1,57 @@
+/*-
+ * Copyright (c) 2016 Alistair Crooks <a...@netbsd.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided 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.
+ */
+#ifndef DELTA_H_
+#define DELTA_H_ 20160414
+
+struct delta_t;
+typedef struct delta_t delta_t;
+
+#ifndef __BEGIN_DECLS
+# if defined(__cplusplus)
+# define __BEGIN_DECLS extern "C" {
+# define __END_DECLS }
+# else
+# define __BEGIN_DECLS
+# define __END_DECLS
+# endif
+#endif
+
+__BEGIN_DECLS
+
+delta_t *delta_new(void);
+void delta_free(delta_t */*delta*/);
+
+int delta_diff_mem(delta_t */*delta*/, const void */*old*/, size_t /*oldc*/, const void */*new*/, size_t /*newc*/);
+int delta_patch_mem(delta_t */*delta*/, const void */*old*/, size_t /*oldc*/, void */*newv*/, size_t */*newc*/);
+
+int delta_diff_file(const char */*oldfile*/, const char */*newfile*/, const char */*patchfile*/);
+int delta_patch_file(const char */*oldfile*/, const char */*newfile*/, const char */*patchfile*/);
+
+int delta_read_patch_file(delta_t */*delta*/, const char */*patchfile*/);
+int delta_write_patch_file(delta_t */*delta*/, const char */*patchfile*/);
+
+__END_DECLS
+
+#endif
Index: othersrc/external/bsd/delta/dist/libdelta.3
diff -u /dev/null othersrc/external/bsd/delta/dist/libdelta.3:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/dist/libdelta.3 Thu Apr 28 05:21:31 2016
@@ -0,0 +1,120 @@
+.\" $NetBSD: libdelta.3,v 1.1 2016/04/28 05:21:31 agc Exp $
+.\"
+.\" Copyright (c) 2016 Alistair Crooks <a...@netbsd.org>
+.\" All rights reserved.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided 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 April 14, 2016
+.Dt LIBDELTA 3
+.Os
+.Sh NAME
+.Nm libdelta
+.Nd library providing binary diff and patch functionality
+.Sh LIBRARY
+.Lb libdelta
+.Sh SYNOPSIS
+.In delta.h
+.Ft "delta_t *"
+.Fo delta_new
+.Fa "void"
+.Fc
+.Ft int
+.Fo delta_free
+.Fa "delta_t *delta"
+.Fc
+.Ft int
+.Fo delta_diff_mem
+.Fa "delta_t *delta" "const void *old" "size_t oldc"
+.Fa "const void *new" "size_t newc"
+.Fc
+.Ft int
+.Fo delta_patch_mem
+.Fa "delta_t *delta" "const void *old" "size_t oldc"
+.Fa "void *new" "size_t *newc"
+.Fc
+.Ft int
+.Fo delta_diff_file
+.Fa "const char *oldfile" "const char *newfile" "const char *patchfile"
+.Fc
+.Ft int
+.Fo delta_patch_file
+.Fa "const char *oldfile" "const char *newfile" "const char *patchfile"
+.Fc
+.Ft int
+.Fo delta_read_patch_file
+.Fa "delta_t *delta" "const char *patchfile"
+.Fc
+.Ft int
+.Fo delta_write_patch_file
+.Fa "delta_t *delta" "const char *patchfile"
+.Fc
+.Sh DESCRIPTION
+The
+.Nm
+library is a library interface which provides
+a space-efficient binary diff and patch functionality
+for use by programs and scripts.
+The typical space usage is about half of xdelta version 1.
+.Pp
+A
+.Dv delta_t
+structure is opaque, and is initialised
+using the
+.Fn delta_new
+function, and all resources freed
+with the
+.Fn delta_free
+function.
+.Pp
+Memory can be
+.Dq diffed
+to produce a patch using the
+.Fn delta_diff_mem
+function,
+and the resulting diff can be re-applied to the original file
+to produce the
+.Dq new
+file using the
+.Fn delta_patch_mem
+function.
+.Pp
+There is a similar set of operations at a file level, using the
+.Fn delta_diff_file
+and
+.Fn delta_patch_file
+functions.
+.Pp
+The two functions
+.Fn delta_read_patch_file
+and
+.Fn delta_write_patch_file
+can be used to read and write patch files from memory operations
+which have completed successfully.
+.Sh HISTORY
+The
+.Nm
+library first appeared in
+.Nx 8.0 .
+.Sh AUTHORS
+.An Alistair Crooks Aq Mt a...@netbsd.org
+based on some original code from
+.An Colin Percival
Index: othersrc/external/bsd/delta/dist/libdelta.c
diff -u /dev/null othersrc/external/bsd/delta/dist/libdelta.c:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/dist/libdelta.c Thu Apr 28 05:21:31 2016
@@ -0,0 +1,749 @@
+/*-
+ * Copyright 2003-2005 Colin Percival
+ * All rights reserved
+ * Copyright (c) 2016 Alistair Crooks <a...@netbsd.org>
+ * 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 <fcntl.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "delta.h"
+
+/* an output buffer structure */
+typedef struct obuf_t {
+ uint64_t c; /* # of characters used */
+ uint64_t size; /* output buffer size */
+ uint8_t *v; /* the array of chars */
+} obuf_t;
+
+/* the binary diff structure */
+typedef struct delta_t {
+ obuf_t control; /* output buffer for control info */
+ uint8_t *diff; /* diff text */
+ size_t difflen; /* diff text length */
+ uint8_t *extra; /* extra text */
+ size_t extralen; /* extra text length */
+ off_t newsize; /* size of output */
+ uint8_t allocctl; /* ctl was allocated */
+ uint8_t allocdiff; /* diff was allocated */
+ uint8_t allocextra; /* extra was allocated */
+} delta_t;
+
+#ifndef MIN
+#define MIN(x,y) (((x) < (y)) ? (x) : (y))
+#endif
+
+#ifndef ABS
+#define ABS(x) (((x) < 0) ? -(x) : (x))
+#endif
+
+#ifndef howmany
+#define howmany(x, y) (((x)+((y)-1))/(y))
+#endif
+
+/* add the info to the obuf buffer */
+static int
+owrite(obuf_t *obuf, const void *p, size_t size)
+{
+ uint8_t *newv;
+ size_t newsize;
+
+ if (obuf->c + size >= obuf->size) {
+ newsize = howmany(obuf->c + size, 4096) * 4096;
+ newv = realloc(obuf->v, newsize);
+ if (newv == NULL) {
+ return 0;
+ }
+ obuf->size = newsize;
+ obuf->v = newv;
+ }
+ memcpy(&obuf->v[obuf->c], p, size);
+ obuf->c += size;
+ return 1;
+}
+
+static void
+split(off_t *I, off_t *V, off_t start, off_t len, off_t h)
+{
+ off_t i, j, k, x, tmp, jj, kk;
+
+ if (len < 16) {
+ for (k = start; k < start + len; k += j) {
+ j = 1;
+ x = V[I[k] + h];
+ for (i = 1; k + i < start + len; i++) {
+ if (V[I[k + i] + h] < x) {
+ x = V[I[k + i] + h];
+ j = 0;
+ }
+ if (V[I[k + i] + h] == x) {
+ tmp = I[k + j];
+ I[k + j] = I[k + i];
+ I[k + i] = tmp;
+ j++;
+ }
+ }
+ for (i = 0; i < j; i++)
+ V[I[k + i]] = k + j - 1;
+ if (j == 1)
+ I[k] = -1;
+ }
+ return;
+ }
+
+ x = V[I[start + len / 2] + h];
+ jj = 0;
+ kk = 0;
+ for (i = start; i < start + len; i++) {
+ if (V[I[i] + h] < x)
+ jj++;
+ if (V[I[i] + h] == x)
+ kk++;
+ }
+ jj += start;
+ kk += jj;
+
+ j = k = 0;
+ for (i = start; i < jj ; ) {
+ if (V[I[i] + h] < x) {
+ i++;
+ } else if (V[I[i] + h] == x) {
+ tmp = I[i];
+ I[i] = I[jj + j];
+ I[jj + j] = tmp;
+ j++;
+ } else {
+ tmp = I[i];
+ I[i] = I[kk + k];
+ I[kk + k] = tmp;
+ k++;
+ }
+ }
+ while (jj + j < kk) {
+ if (V[I[jj + j] + h] == x) {
+ j++;
+ } else {
+ tmp = I[jj + j];
+ I[jj + j] = I[kk + k];
+ I[kk + k] = tmp;
+ k++;
+ }
+ }
+
+ if (jj > start) {
+ split(I, V, start, jj - start, h);
+ }
+ for (i = 0; i < kk - jj; i++) {
+ V[I[jj + i]] = kk - 1;
+ }
+ if (jj == kk - 1) {
+ I[jj] = -1;
+ }
+ if (start + len > kk) {
+ split(I, V, kk, start + len - kk, h);
+ }
+}
+
+static void
+qsufsort(off_t *I, off_t *V, const uint8_t *old, off_t oldsize)
+{
+ off_t buckets[256];
+ off_t i, h, len;
+
+ memset(buckets, 0x0, sizeof(buckets));
+ for (i = 0; i < oldsize; i++) {
+ buckets[old[i]]++;
+ }
+ for (i = 1; i < 256; i++) {
+ buckets[i] += buckets[i - 1];
+ }
+ for (i = 255; i > 0; i--) {
+ buckets[i] = buckets[i - 1];
+ }
+ buckets[0] = 0;
+
+ for (i = 0; i < oldsize; i++) {
+ I[++buckets[old[i]]] = i;
+ }
+ I[0] = oldsize;
+ for (i = 0; i < oldsize; i++) {
+ V[i] = buckets[old[i]];
+ }
+ V[oldsize] = 0;
+ for (i = 1; i < 256; i++) {
+ if (buckets[i] == buckets[i - 1] + 1) {
+ I[buckets[i]] = -1;
+ }
+ }
+ I[0] = -1;
+
+ for (h = 1; I[0] != -(oldsize + 1); h += h) {
+ for (len = 0, i = 0; i < oldsize + 1;) {
+ if (I[i] < 0) {
+ len -= I[i];
+ i -= I[i];
+ } else {
+ if (len) {
+ I[i - len] = -len;
+ }
+ len = V[I[i]] + 1 - i;
+ split(I, V, i, len, h);
+ i += len;
+ len = 0;
+ }
+ }
+ if (len) {
+ I[i - len] = -len;
+ }
+ }
+
+ for (i = 0; i < oldsize + 1; i++) {
+ I[V[i]] = i;
+ }
+}
+
+static off_t
+matchlen(const uint8_t *old, off_t oldsize, const uint8_t *newv, off_t newsize)
+{
+ off_t i;
+
+ for (i = 0; i < oldsize && i < newsize && old[i] == newv[i] ; i++) {
+ }
+ return i;
+}
+
+static off_t
+search(off_t *I, const uint8_t *old, off_t oldsize,
+ const uint8_t *newv, 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], newv, newsize);
+ y = matchlen(old + I[en], oldsize - I[en], newv, 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], newv, MIN(oldsize - I[x], newsize)) < 0) {
+ return search(I, old, oldsize, newv, newsize, x, en, pos);
+ } else {
+ return search(I, old, oldsize, newv, newsize, st, x, pos);
+ }
+}
+
+/* encode in zigzag encoding */
+static int
+put64(off_t x, uint8_t *buf)
+{
+ uint64_t n;
+ uint8_t *b;
+ int len;
+ int i;
+
+ n = (x << 1) ^ (x >> 63);
+ for (len = 0, b = buf, i = 0 ; i < 9 ; i++, b += len) {
+ *b = ((n >> ((9 - i) * 7)) & 0x7f) | 0x80;
+ if (len == 0 && *b != 0x80) {
+ len = 1;
+ }
+ }
+ *b++ = (n & 0x7f);
+ return (int)(b - buf);
+}
+
+/* decode from zigzag encoding */
+static int64_t
+get64(uint8_t *buf, size_t *len)
+{
+ uint64_t n;
+
+ for (n = 0, *len = 0 ; *len < 10 ; *len += 1) {
+ n = (n << 7) + (buf[*len] & 0x7f);
+ if ((buf[*len] & 0x80) == 0) {
+ *len += 1;
+ break;
+ }
+ }
+ return (n >> 1) ^ (-(n & 1));
+}
+
+/* read the file into the array */
+static int
+readfile(const char *f, uint8_t **v, off_t *size)
+{
+ ssize_t cc;
+ ssize_t rc;
+ int fd;
+
+ if (((fd = open(f, O_RDONLY, 0)) < 0) ||
+ ((*size = lseek(fd, 0, SEEK_END)) == -1) ||
+ ((*v = malloc(*size + 1)) == NULL) ||
+ (lseek(fd, 0, SEEK_SET) != 0)) {
+ warn("can't read file '%s'", f);
+ return 0;
+ }
+ for (cc = 0 ; cc < *size ; cc += rc) {
+ if ((rc = read(fd, &(*v)[cc], *size - cc)) < 0) {
+ break;
+ }
+ }
+ close(fd);
+ return cc == *size;
+}
+
+/* write the array to the file */
+static int
+writefile(const char *f, uint8_t *v, off_t size)
+{
+ ssize_t cc;
+ ssize_t wc;
+ int fd;
+
+ /* Write the new file */
+ if ((fd = open(f, O_CREAT | O_TRUNC | O_WRONLY, 0666)) < 0) {
+ warn("can't write file '%s'", f);
+ return 0;
+ }
+ for (cc = 0 ; cc < size ; cc += wc) {
+ if ((wc = write(fd, &v[cc], size - cc)) < 0) {
+ break;
+ }
+ }
+ close(fd);
+ return cc == size;
+}
+
+/***********************************************************************/
+
+#define HEADER "/_\\1" /* delta v1 */
+#define HEADERLEN 4
+
+/* write the patch file from info held in delta struct */
+int
+delta_write_patch_file(delta_t *delta, const char *patchfile)
+{
+ unsigned zsize;
+ uint8_t buf[10];
+ size_t cc;
+ size_t wc;
+ size_t n;
+ obuf_t o;
+ FILE *fp;
+ char *z;
+
+ if (delta == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&o, 0x0, sizeof(o));
+ owrite(&o, HEADER, HEADERLEN);
+ n = put64(delta->control.c, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->difflen, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->extralen, buf);
+ owrite(&o, buf, n);
+ n = put64(delta->newsize, buf);
+ owrite(&o, buf, n);
+ if ((fp = fopen(patchfile, "w")) == NULL) {
+ warn("can't open '%s' for writing", patchfile);
+ return 0;
+ }
+ for (cc = 0 ; cc < o.c ; cc += wc) {
+ if ((wc = fwrite(&o.v[cc], 1, o.c - cc, fp)) == 0) {
+ break;
+ }
+ }
+ o.c = 0;
+ /* control info */
+ owrite(&o, delta->control.v, delta->control.c);
+ /* diff info */
+ owrite(&o, delta->diff, delta->difflen);
+ /* extra info */
+ owrite(&o, delta->extra, delta->extralen);
+ n = delta->control.c + delta->difflen + delta->extralen;
+ zsize = ((n + 128) * 101) / 100;
+ z = calloc(1, zsize);
+ BZ2_bzBuffToBuffCompress(z, &zsize, (char *)o.v, o.c, 9, 0, 0);
+ for (cc = 0 ; cc < zsize ; cc += wc) {
+ if ((wc = fwrite(&z[cc], 1, zsize - cc, fp)) == 0) {
+ break;
+ }
+ }
+ free(z);
+ free(o.v);
+ fclose(fp);
+ return cc == zsize;
+}
+
+/* read the patch file into the delta struct */
+int
+delta_read_patch_file(delta_t *delta, const char *patchfile)
+{
+ unsigned zsize;
+ size_t len;
+ size_t cc;
+ obuf_t o;
+ off_t size;
+ char *z;
+
+ if (delta == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(delta, 0x0, sizeof(*delta));
+ memset(&o, 0x0, sizeof(o));
+ if (!readfile(patchfile, &o.v, &size)) {
+ return 0;
+ }
+ o.c = o.size = size;
+ if (memcmp(o.v, HEADER, HEADERLEN) != 0) {
+ warnx("not a patch at offset 0");
+ return 0;
+ }
+ cc = HEADERLEN;
+ delta->control.c = get64(&o.v[cc], &len);
+ cc += len;
+ delta->difflen = get64(&o.v[cc], &len);
+ cc += len;
+ delta->extralen = get64(&o.v[cc], &len);
+ cc += len;
+ delta->newsize = get64(&o.v[cc], &len);
+ cc += len;
+ zsize = delta->control.c + delta->difflen + delta->extralen;
+ if ((z = calloc(1, zsize)) == NULL) {
+ warn("resource allocation reading patch file");
+ return 0;
+ }
+ if (BZ2_bzBuffToBuffDecompress(z, &zsize, (char *)&o.v[cc], size - cc, 0, 0) != BZ_OK) {
+ warn("resource allocation reading patch file");
+ return 0;
+ }
+ delta->allocctl = 1;
+ delta->control.v = (uint8_t *)z;
+ delta->diff = (uint8_t *)&z[delta->control.c];
+ delta->extra = (uint8_t *)&z[delta->control.c + delta->difflen];
+ free(o.v);
+ return 1;
+}
+
+/* diff 2 areas of memory */
+int
+delta_diff_mem(delta_t *delta, const void *aold, size_t oldc, const void *anewv, size_t newc)
+{
+ const uint8_t *old = (const uint8_t *)aold;
+ const uint8_t *newv = (const uint8_t *)anewv;
+ uint8_t buf[10];
+ off_t oldsize = (off_t)oldc;
+ off_t newsize = (off_t)newc;
+ off_t *I, *V;
+ 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;
+ int buflen;
+
+ if (delta == NULL || old == NULL || newv == NULL) {
+ return 0;
+ }
+ memset(delta, 0x0, sizeof(*delta));
+ if (((I = malloc((oldsize + 1) * sizeof(*I))) == NULL) ||
+ ((V = malloc((oldsize + 1) * sizeof(*V))) == NULL)) {
+ warn("allocation failure in bsd_diff_mem");
+ return 0;
+ }
+ qsufsort(I, V, old, oldsize);
+ free(V);
+ /*
+ * Allocate newsize+1 bytes instead of newsize bytes to ensure that
+ * we never try to malloc(0) and get a NULL pointer
+ */
+ delta->newsize = newsize;
+ if (((delta->diff = malloc(newsize + 1)) == NULL) ||
+ ((delta->extra = malloc(newsize + 1)) == NULL)) {
+ warn("allocation failure 2 in bsd_diff_mem");
+ return 0;
+ }
+ delta->allocdiff = delta->allocextra = 1;
+ scan = 0;
+ len = 0;
+ lastscan = 0;
+ lastpos = 0;
+ lastoffset = 0;
+ while (scan < newsize) {
+ oldscore = 0;
+ for (scsc = scan += len; scan < newsize; scan++) {
+ len = search(I, old, oldsize, newv + scan, newsize - scan,
+ 0, oldsize, &pos);
+
+ for (; scsc < scan + len; scsc++)
+ if ((scsc + lastoffset < oldsize) &&
+ (old[scsc + lastoffset] == newv[scsc])) {
+ oldscore++;
+ }
+ if (((len == oldscore) && (len != 0)) ||
+ (len > oldscore + 8)) {
+ break;
+ }
+ if ((scan + lastoffset < oldsize) &&
+ (old[scan + lastoffset] == newv[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] == newv[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] == newv[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 (newv[lastscan + lenf - overlap + i] ==
+ old[lastpos + lenf - overlap + i]) {
+ s++;
+ }
+ if (newv[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++) {
+ delta->diff[delta->difflen + i] = newv[lastscan + i] - old[lastpos + i];
+ }
+ for (i = 0; i < (scan - lenb) - (lastscan + lenf); i++) {
+ delta->extra[delta->extralen + i] = newv[lastscan + lenf + i];
+ }
+ delta->difflen += lenf;
+ delta->extralen += (scan - lenb) - (lastscan + lenf);
+
+ buflen = put64(lenf, buf);
+ owrite(&delta->control, buf, buflen);
+
+ buflen = put64((scan - lenb) - (lastscan + lenf), buf);
+ owrite(&delta->control, buf, buflen);
+ buflen = put64((pos - lenb) - (lastpos + lenf), buf);
+ owrite(&delta->control, buf, buflen);
+ lastscan = scan - lenb;
+ lastpos = pos - lenb;
+ lastoffset = pos - scan;
+ }
+ }
+ free(I);
+ return 1;
+}
+
+/* diff two files, putting results in patch file */
+int
+delta_diff_file(const char *oldfile, const char *newfile, const char *patchfile)
+{
+ delta_t delta;
+ uint8_t *oldv;
+ uint8_t *newv;
+ off_t oldsize;
+ off_t newsize;
+ int ok;
+
+ if (oldfile == NULL || newfile == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&delta, 0x0, sizeof(delta));
+ if (!readfile(oldfile, &oldv, &oldsize) ||
+ !readfile(newfile, &newv, &newsize)) {
+ return 0;
+ }
+ if (!delta_diff_mem(&delta, oldv, oldsize, newv, newsize)) {
+ return 0;
+ }
+ ok = delta_write_patch_file(&delta, patchfile);
+ if (!ok) {
+ return 0;
+ }
+ /* Free the memory we used */
+ delta_free(&delta);
+ free(oldv);
+ free(newv);
+ return 1;
+}
+
+/* patch using a binary patch */
+int
+delta_patch_mem(delta_t *delta, const void *aold, size_t oldsize, void *anewv, size_t *newsize)
+{
+ const uint8_t *old = (const uint8_t *)aold;
+ uint8_t **newv = (uint8_t **)anewv;
+ size_t extrac;
+ size_t diffc;
+ size_t ctlc;
+ size_t len;
+ off_t ctrl[3];
+ off_t oldpos;
+ off_t newpos;
+ off_t i;
+
+ if (delta == NULL || old == NULL || newv == NULL) {
+ return 0;
+ }
+ if ((*newv = malloc(delta->newsize + 1)) == NULL) {
+ warn("allocation failure %zu bytes", delta->newsize + 1);
+ return 0;
+ }
+ for (oldpos = newpos = 0, ctlc = diffc = extrac = 0; newpos < delta->newsize ; ) {
+ /* Read control data */
+ for (i = 0; i < 3; i++) {
+ ctrl[i] = get64(&delta->control.v[ctlc], &len);
+ ctlc += len;
+ }
+ /* Sanity-check */
+ if (newpos + ctrl[0] > delta->newsize) {
+ warnx("Corrupt patch 1\n");
+ return 0;
+ }
+ /* Read diff string */
+ memcpy(&(*newv)[newpos], &delta->diff[diffc], ctrl[0]);
+ diffc += ctrl[0];
+ /* Add old data to diff string */
+ for (i = 0; i < ctrl[0]; i++) {
+ if ((oldpos + i >= 0) && (oldpos + i < (off_t)oldsize)) {
+ (*newv)[newpos + i] += old[oldpos + i];
+ }
+ }
+ /* Adjust pointers */
+ newpos += ctrl[0];
+ oldpos += ctrl[0];
+ /* Sanity-check */
+ if (newpos + ctrl[1] > delta->newsize) {
+ warnx("Corrupt patch 2\n");
+ return 0;
+ }
+ /* Read extra string */
+ memcpy(*newv + newpos, &delta->extra[extrac], ctrl[1]);
+ extrac += ctrl[1];
+ /* Adjust pointers */
+ newpos += ctrl[1];
+ oldpos += ctrl[2];
+ }
+ *newsize = delta->newsize;
+ return 1;
+}
+
+/* patch using a binary patch */
+int
+delta_patch_file(const char *oldfile, const char *newfile, const char *patchfile)
+{
+ delta_t delta;
+ ssize_t oldsize;
+ uint8_t *newv;
+ uint8_t *old;
+ size_t newsize;
+
+ if (oldfile == NULL || newfile == NULL || patchfile == NULL) {
+ return 0;
+ }
+ memset(&delta, 0x0, sizeof(delta));
+ if (!delta_read_patch_file(&delta, patchfile)) {
+ return 0;
+ }
+ if (!readfile(oldfile, &old, &oldsize)) {
+ warn("%s", oldfile);
+ return 0;
+ }
+ if (!delta_patch_mem(&delta, old, oldsize, &newv, &newsize)) {
+ return 0;
+ }
+ if (!writefile(newfile, newv, delta.newsize)) {
+ warn("%s", newfile);
+ return 0;
+ }
+ delta_free(&delta);
+ return 1;
+}
+
+/* free resources associated with delta struct */
+void
+delta_free(delta_t *delta)
+{
+ if (delta) {
+ if (delta->allocctl) {
+ free(delta->control.v);
+ }
+ if (delta->allocdiff) {
+ free(delta->diff);
+ }
+ if (delta->allocextra) {
+ free(delta->extra);
+ }
+ }
+}
+
+/* make a new struct */
+delta_t *
+delta_new(void)
+{
+ return calloc(1, sizeof(delta_t));
+}
Index: othersrc/external/bsd/delta/dist/main.c
diff -u /dev/null othersrc/external/bsd/delta/dist/main.c:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/dist/main.c Thu Apr 28 05:21:31 2016
@@ -0,0 +1,60 @@
+/*-
+ * Copyright (c) 2016 Alistair Crooks <a...@netbsd.org>
+ * 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 <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "delta.h"
+
+int
+main(int argc, char **argv)
+{
+ int dodiff;
+ int ok;
+ int i;
+
+ dodiff = 0;
+ while ((i = getopt(argc, argv, "dp")) != -1) {
+ switch(i) {
+ case 'd':
+ dodiff = 1;
+ break;
+ case 'p':
+ dodiff = 0;
+ break;
+ }
+ }
+ if (argc - optind != 3) {
+ fprintf(stderr, "Usage: %s oldfile newfile patchfile\n", *argv);
+ exit(EXIT_FAILURE);
+ }
+ ok = (dodiff) ?
+ delta_diff_file(argv[optind], argv[optind + 1], argv[optind + 2]) :
+ delta_patch_file(argv[optind], argv[optind + 1], argv[optind + 2]);
+ exit((ok) ? EXIT_SUCCESS : EXIT_FAILURE);
+}
Index: othersrc/external/bsd/delta/lib/Makefile
diff -u /dev/null othersrc/external/bsd/delta/lib/Makefile:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/lib/Makefile Thu Apr 28 05:21:31 2016
@@ -0,0 +1,25 @@
+# $NetBSD: Makefile,v 1.1 2016/04/28 05:21:31 agc Exp $
+
+.include <bsd.own.mk>
+
+DIST= ${.CURDIR}/../dist
+.PATH: ${DIST}
+
+LIB= delta
+SRCS+= libdelta.c
+CPPFLAGS+= -I. -I${DIST}
+MAN= libdelta.3
+
+LIBDPLIBS+= bz2 ${NETBSDSRCDIR}/lib/libbz2
+
+.ifndef PRODUCTION
+CPPFLAGS+=-g -O0
+LDFLAGS+=-g -O0
+.endif
+
+WARNS=5
+
+INCS= delta.h
+INCSDIR= /usr/include
+
+.include <bsd.lib.mk>
Index: othersrc/external/bsd/delta/lib/shlib_version
diff -u /dev/null othersrc/external/bsd/delta/lib/shlib_version:1.1
--- /dev/null Thu Apr 28 05:21:31 2016
+++ othersrc/external/bsd/delta/lib/shlib_version Thu Apr 28 05:21:31 2016
@@ -0,0 +1,2 @@
+major=0
+minor=0
