bsdiff-portable

util.c (5924B)

---

 /*-
  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
  *
  * Copyright 2003-2005 Colin Percival
  * Copyright 2011-2012 Thieu Le
  * Copyright 2012      Matthew Endsley
  * Copyright 2020      Stephen Gregoratto
  * 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 <sys/stat.h>
 
 #if HAVE_ERR
 #include <err.h>
 #endif
 #include <fcntl.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.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 = 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 = 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;
 
 	y = x < 0 ? -x : x;
 
 	for (size_t i = 0; i <= 6; i++) {
 		buf[i] = y % 256;
 		y -= buf[i];
 		y /= 256;
 	}
 	buf[7] = y % 256;
 
 	if (x < 0)
 		buf[7] |= 0x80;
 }
 
 off_t
 offtin(uint8_t *buf)
 {
 	off_t y;
 
 	y = buf[7] & 0x7F;
 	for (int i = 6; i >= 0; i--) {
 		y *= 256;
 		y += buf[i];
 	}
 
 	if (buf[7] & 0x80)
 		y = -y;
 
 	return y;
 }
 
 void
 usage(void)
 {
 	fprintf(stderr, "usage: %s oldfile newfile patchfile\n", getprogname());
 
 	exit(1);
 }
 
 uint8_t *
 readfile(char *path, off_t *size, struct stat *st)
 {
 	uint8_t *buf = NULL;
 	int fd;
 
 	if ((path == NULL || *path == '\0') ||
 	    size == NULL || st == NULL)
 		errx(1, "readfile: bad args");
 
 	if ((fd = open(path, O_RDONLY, 0)) == -1)
 		err(1, "%s: open", path);
 	if (fstat(fd, st) == -1)
 		err(1, "%s: fstat", path);
 	/*
 	 * Allocate size + 1 bytes to ensure that we never
 	 * try to malloc(0) and get a NULL pointer.
 	 */
 	*size = st->st_size;
 	if ((buf = reallocarray(NULL, *size + 1, 1)) == NULL)
 		err(1, "%s: reallocarray", path);
 
 	if (read(fd, buf, *size) == -1)
 		err(1, "%s: read", path);
 	if (close(fd) == -1)
 		err(1, "%s: close", path);
 
 	return buf;
 }