commit ba1e25b338eb74f8c40bc91682da3ea2e02e5725
parent 8d1171b4cb333e3bad8961d7815a81605cb0fbfc
Author: Stephen Gregoratto <dev@sgregoratto.me>
Date: Wed, 23 Sep 2020 17:21:48 +1000
Move most logic to util.c, add usage function
Diffstat:
| M | Makefile | | | 10 | +++++----- |
| M | bsdiff.c | | | 213 | +------------------------------------------------------------------------------ |
| M | bsdiff.h | | | 7 | +++++++ |
| M | bspatch.c | | | 29 | +---------------------------- |
| A | util.c | | | 276 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
5 files changed, 291 insertions(+), 244 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,14 +1,14 @@
include Makefile.configure
-OBJS = bsdiff.o bspatch.o compats.o
+OBJS = bsdiff.o bspatch.o util.o compats.o
all: bsdiff bspatch
-bsdiff: bsdiff.o compats.o
- $(CC) -o $@ -lbz2 $(LDFLAGS) bsdiff.o compats.o
+bsdiff: bsdiff.o util.o compats.o
+ $(CC) -o $@ -lbz2 $(LDFLAGS) bsdiff.o util.o compats.o
-bspatch: bspatch.o compats.o
- $(CC) -o $@ -lbz2 $(LDFLAGS) bspatch.o compats.o
+bspatch: bspatch.o util.o compats.o
+ $(CC) -o $@ -lbz2 $(LDFLAGS) bspatch.o util.o compats.o
install:
${INSTALL_PROGRAM} bsdiff bspatch ${DESTDIR}${PREFIX}/bin
diff --git a/bsdiff.c b/bsdiff.c
@@ -43,217 +43,8 @@ __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c,v 1.1 2005/08/06 01:59:05
#include "bsdiff.h"
-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);
-}
-
-void
-qsufsort(off_t *I, off_t *V, uint8_t *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;
-}
-
-off_t
-matchlen(uint8_t *old, off_t oldsize, uint8_t *new, off_t newsize)
-{
- off_t i;
-
- for (i = 0; (i < oldsize) && (i < newsize); i++)
- if (old[i] != new[i])
- break;
-
- return i;
-}
-
-off_t
-search(off_t *I, uint8_t *old, off_t oldsize, uint8_t *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);
- }
-}
-
-void
-offtout(off_t x, uint8_t *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[])
+main(int argc, char **argv)
{
int fd;
uint8_t *old, *new;
@@ -274,7 +65,7 @@ main(int argc, char *argv[])
int bz2err;
if (argc != 4)
- errx(1, "usage: %s oldfile newfile patchfile\n", argv[0]);
+ usage();
/* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
that we never try to malloc(0) and get a NULL pointer */
diff --git a/bsdiff.h b/bsdiff.h
@@ -27,6 +27,12 @@
* POSSIBILITY OF SUCH DAMAGE.
*/
+#ifdef __GNUC__
+#define DEAD __attribute__ ((noreturn))
+#else
+#define DEAD
+#endif
+
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
void split(off_t *, off_t *, off_t, off_t, off_t);
@@ -37,4 +43,5 @@ off_t search(off_t *, uint8_t *, off_t, uint8_t *, off_t, off_t,
void offtout(off_t, uint8_t *);
off_t offtin(uint8_t *buf);
uint8_t * readfile(char *, off_t *);
+DEAD void usage(void);
#endif /* BSDIFF_H */
diff --git a/bspatch.c b/bspatch.c
@@ -41,33 +41,6 @@ __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bspatch/bspatch.c,v 1.1 2005/08/06 01:59:
#include "bsdiff.h"
-off_t
-offtin(u_char *buf)
-{
- off_t y;
-
- y = buf[7] & 0x7F;
- y = y * 256;
- y += buf[6];
- y = y * 256;
- y += buf[5];
- y = y * 256;
- y += buf[4];
- y = y * 256;
- y += buf[3];
- y = y * 256;
- y += buf[2];
- y = y * 256;
- y += buf[1];
- y = y * 256;
- y += buf[0];
-
- if (buf[7] & 0x80)
- y = -y;
-
- return y;
-}
-
int
main(int argc, char *argv[])
{
@@ -85,7 +58,7 @@ main(int argc, char *argv[])
off_t i;
if (argc != 4)
- errx(1, "usage: %s oldfile newfile patchfile\n", argv[0]);
+ usage();
/* Open patch file */
if ((f = fopen(argv[3], "r")) == NULL)
diff --git a/util.c b/util.c
@@ -0,0 +1,276 @@
+/*-
+ * Copyright 2003-2005 Colin Percival
+ * All rights reserved
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted providing that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+ * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "bsdiff.h"
+
+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);
+}
+
+void
+qsufsort(off_t *I, off_t *V, uint8_t *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;
+}
+
+off_t
+matchlen(uint8_t *old, off_t oldsize, uint8_t *new, off_t newsize)
+{
+ off_t i;
+
+ for (i = 0; (i < oldsize) && (i < newsize); i++)
+ if (old[i] != new[i])
+ break;
+
+ return i;
+}
+
+off_t
+search(off_t *I, uint8_t *old, off_t oldsize, uint8_t *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);
+}
+
+void
+offtout(off_t x, uint8_t *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;
+}
+
+off_t
+offtin(u_char *buf)
+{
+ off_t y;
+
+ y = buf[7] & 0x7F;
+ y = y * 256;
+ y += buf[6];
+ y = y * 256;
+ y += buf[5];
+ y = y * 256;
+ y += buf[4];
+ y = y * 256;
+ y += buf[3];
+ y = y * 256;
+ y += buf[2];
+ y = y * 256;
+ y += buf[1];
+ y = y * 256;
+ y += buf[0];
+
+ if (buf[7] & 0x80)
+ y = -y;
+
+ return y;
+}
+
+void
+usage(void)
+{
+ fprintf(stderr, "usage: %s oldfile newfile patchfile\n", getprogname());
+
+ exit(1);
+}