ccan/ccan/bdelta/bdelta.c

/*
 * Copyright (C) 2011 Joseph Adams <joeyadams3.14159@gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include "bdelta.h"

#include <assert.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
	unsigned char *cur;    /* End of string; insertion point for new bytes */
	unsigned char *end;    /* End of buffer */
	unsigned char *start;  /* Beginning of string */
} SB;

/* sb is evaluated multiple times in these macros. */
#define sb_size(sb)  ((size_t)((sb)->cur - (sb)->start))
#define sb_avail(sb) ((size_t)((sb)->end - (sb)->cur))

/* sb and need may be evaluated multiple times. */
#define sb_need(sb, need) do {           \
		if (sb_avail(sb) < (need))       \
			if (sb_grow(sb, need) != 0)  \
				goto out_of_memory;      \
	} while (0)

static int sb_init(SB *sb)
{
	sb->start = malloc(17);
	if (sb->start == NULL)
		return -1;
	sb->cur = sb->start;
	sb->end = sb->start + 16;
	return 0;
}

static int sb_grow(SB *sb, size_t need)
{
	size_t length = sb->cur - sb->start;
	size_t alloc = sb->end - sb->start;
	unsigned char *tmp;
	
	do {
		alloc *= 2;
	} while (alloc < length + need);
	
	tmp = realloc(sb->start, alloc + 1);
	if (tmp == NULL)
		return -1;
	sb->start = tmp;
	sb->cur = tmp + length;
	sb->end = tmp + alloc;
	return 0;
}

static int sb_putc(SB *sb, unsigned char c)
{
	sb_need(sb, 1);
	*sb->cur++ = c;
	return 0;

out_of_memory:
	return -1;
}

static int sb_write(SB *sb, const void *data, size_t size)
{
	sb_need(sb, size);
	memcpy(sb->cur, data, size);
	sb->cur += size;
	return 0;
	
out_of_memory:
	return -1;
}

static void sb_return(SB *sb, void **data_out, size_t *length_out)
{
	*sb->cur = 0;
	if (data_out)
		*data_out = sb->start;
	else
		free(sb->start);
	if (length_out)
		*length_out = sb->cur - sb->start;
}

static void sb_discard(SB *sb, void **data_out, size_t *length_out)
{
	free(sb->start);
	if (data_out)
		*data_out = NULL;
	if (length_out)
		*length_out = 0;
}

/*
 * The first byte in a patch is the "patch type", which indicates how the
 * patch is formatted.  This keeps the patch format flexible while retaining
 * backward compatibility.  Patches produced with an older version of
 * the library can be applied with a newer version.
 *
 * PT_LITERAL
 *     Contains nothing more than the content of the new text.
 *
 * PT_CSI32
 *     A string of copy, skip, and insert instructions for generating the new
 *     string from the old.
 *
 *         copy(size):   Copy @size bytes from old to new.
 *         skip(size):   Skip @size bytes of old.
 *         insert(text): Insert @text into new.
 *
 *     The syntax is as follows:
 *
 *         copy:   instruction_byte(1) size
 *         skip:   instruction_byte(2) size
 *         insert: instruction_byte(3) size $size*OCTET
 *
 *         0 <= size_param_length <= 4
 *         instruction_byte(op) = op | size_param_length << 2
 *         size: $size_param_length*OCTET
 *               -- size is an unsigned integer encoded in big endian.
 *               -- However, if size_param_length is 0, the operation size is 1.
 *
 *     Simply put, an instruction starts with an opcode and operation size.
 *     An insert instruction is followed by the bytes to be inserted.
 */
#define PT_LITERAL   10
#define PT_CSI32     11

#define OP_COPY      1
#define OP_SKIP      2
#define OP_INSERT    3

static unsigned int bytes_needed_for_size(uint32_t size)
{
	if (size == 1)
		return 0;
	else if (size <= 0xFF)
		return 1;
	else if (size <= 0xFFFF)
		return 2;
	else if (size <= 0xFFFFFF)
		return 3;
	else
		return 4;
}

/*
 * Return values:
 *
 *  BDELTA_OK:      Success
 *  BDELTA_MEMORY:  Memory allocation failed
 */
static BDELTAcode csi32_emit_op(SB *patch_out, int op, uint32_t size, const char **new_)
{
	unsigned int i;
	unsigned int size_param_length;
	size_t need;
	uint32_t tmp;
	
	assert(op >= 1 && op <= 3);
	
	if (size == 0)
		return BDELTA_OK;
	size_param_length = bytes_needed_for_size(size);
	
	need = 1 + size_param_length;
	if (op == OP_INSERT)
		need += size;
	sb_need(patch_out, need);
	
	*patch_out->cur++ = (unsigned int)op | size_param_length << 2;
	for (i = size_param_length, tmp = size; i-- > 0; tmp >>= 8)
		patch_out->cur[i] = tmp & 0xFF;
	patch_out->cur += size_param_length;
	
	switch (op) {
		case OP_COPY:
			*new_ += size;
			break;
		case OP_SKIP:
			break;
		case OP_INSERT:
			memcpy(patch_out->cur, *new_, size);
			patch_out->cur += size;
			*new_ += size;
			break;
		default:
			assert(0);
	}
	
	return BDELTA_OK;

out_of_memory:
	return BDELTA_MEMORY;
}

/*
 * On success, returns 1, advances *sp past the parsed text, and sets *op_out and *size_out.
 * On error or EOF, returns 0.
 */
static int csi32_parse_op(
	const unsigned char **sp, const unsigned char *e,
	int *op_out, uint32_t *size_out)
{
	const unsigned char *s = *sp;
	int op;
	unsigned int i;
	unsigned int size_param_length;
	uint32_t size;
	
	if (s >= e)
		return 0;
	op = *s & 3;
	size_param_length = *s >> 2;
	s++;
	if (op == 0 || size_param_length > 4)
		return 0;
	
	if (size_param_length == 0) {
		size = 1;
	} else {
		if ((size_t)(e - s) < size_param_length)
			return 0;
		size = 0;
		for (i = 0; i < size_param_length; i++) {
			size <<= 8;
			size |= *s++ & 0xFF;
		}
	}
	
	/* Make sure insert data fits in the patch, but don't consume it. */
	if (op == OP_INSERT && (size_t)(e - s) < size)
		return 0;
	
	*op_out = op;
	*size_out = size;
	*sp = s;
	return 1;
}

/*
 * bdelta uses the algorithm described in:
 *
 *     Myers, E. (1986). An O(ND) Difference Algorithm and Its Variations.
 *     Retrieved from http://www.xmailserver.org/diff2.pdf
 *
 * The pseudocode in Myers' paper (Figure 2) uses an array called V,
 * where (V[k], V[k] - k) is the endpoint of the furthest-reaching
 * D-path ending on diagonal k.
 *
 * The structure below holds the V array for every iteration of the outer loop.
 * Because each iteration produces D+1 values, a triangle is formed:
 *
 *                      k
 *        -5 -4 -3 -2 -1  0  1  2  3  4  5
 *      ----------------------------------
 *    0 |                 0                (copy 0)
 *      |                   \              skip 1
 *    1 |              0     1
 *      |                      \           skip 1, then copy 1
 *    2 |           2     2     3
 *  D   |                      /           insert 1, then copy 2
 *    3 |        3     4     5     5
 *      |                     \            skip 1, then copy 1
 *    4 |     3     4     5     7     7
 *      |                      /           insert 1
 *    5 |  3     4     5     7     -     -
 *
 * @data will literally contain: 0 0 1 2 2 3 3 4 5 5 3 4 5 7 7 3 4 5 7
 *
 * To convert this to an edit script, we first climb back to the top,
 * using the same procedure as was used when the triangle was generated:
 *
 *     If k = -D, climb right (the only way we can go).
 *     If k = +D, climb left  (the only way we can go).
 *     Otherwise, favor the greater number.
 *     If the numbers are the same, climb left.
 *
 * Finally, we convert the descent to the solution to a patch script:
 *
 *     The top number n corresponds to:
 *         copy   n
 *
 *     A descent left from a to b corresponds to:
 *         insert 1
 *         copy   b-a
 *
 *     A descent right from a to b corresponds to:
 *         skip   1
 *         copy   b-a-1
 */
typedef struct
{
	uint32_t *data;
	int solution_d;
	int solution_k;
	uint32_t *solution_ptr;
} Triangle;

/*
 * Return values:
 *
 *  BDELTA_OK:                      Success
 *  BDELTA_MEMORY:                  Memory allocation failed
 *  BDELTA_INTERNAL_DMAX_EXCEEDED:  d_max exceeded (strings are too different)
 */
static BDELTAcode build_triangle(
	const char *old,  uint32_t old_size,
	const char *new_, uint32_t new_size,
	int d_max,
	Triangle *triangle_out)
{
	int d, k;
	uint32_t x, y;
	uint32_t *data;
	uint32_t *vprev; /* position within previous row */
	uint32_t *v;     /* position within current row */
	uint32_t *vcur;  /* beginning of current row */
	size_t data_alloc = 16;
	
	memset(triangle_out, 0, sizeof(*triangle_out));
	
	data = malloc(data_alloc * sizeof(*data));
	if (data == NULL)
		return BDELTA_MEMORY;
	
	/* Allow dmax < 0 to mean "no limit". */
	if (d_max < 0)
		d_max = old_size + new_size;
	
	/*
	 * Compute the farthest-reaching 0-path so the loop after this
	 * will have a "previous" row to start with.
	 */
	for (x = 0; x < old_size && x < new_size && old[x] == new_[x]; )
		x++;
	*data = x;
	if (x >= old_size && x >= new_size) {
		/* Strings are equal, so return a triangle with one row (a dot). */
		assert(x == old_size && x == new_size);
		triangle_out->data = data;
		triangle_out->solution_d = 0;
		triangle_out->solution_k = 0;
		triangle_out->solution_ptr = data;
		return BDELTA_OK;
	}
	vprev = data;
	vcur = v = data + 1;
	
	/*
	 * Here is the core of the Myers diff algorithm.
	 *
	 * This is a direct translation of the pseudocode in Myers' paper,
	 * with implementation-specific adaptations:
	 *
	 *  * Every V array is preserved per iteration of the outer loop.
	 *    This is necessary so we can determine the actual patch, not just
	 *    the length of the shortest edit string.  See the coment above
	 *    the definition of Triangle for an in-depth explanation.
	 *
	 *  * Array items are stored consecutively so as to not waste space.
	 *
	 *  * The buffer holding the V arrays is expanded dynamically.
	 */
	for (d = 1; d <= d_max; d++, vprev = vcur, vcur = v) {
		/* Ensure that the buffer has enough room for this row. */
		if ((size_t)(v - data + d + 1) > data_alloc) {
			size_t vprev_idx = vprev - data;
			size_t v_idx     = v     - data;
			size_t vcur_idx  = vcur  - data;
			uint32_t *tmp;
			
			do {
				data_alloc *= 2;
			} while ((size_t)(v - data + d + 1) > data_alloc);
			
			tmp = realloc(data, data_alloc * sizeof(*data));
			if (tmp == NULL) {
				free(data);
				return BDELTA_MEMORY;
			}
			data = tmp;
			
			/* Relocate pointers to the buffer we just expanded. */
			vprev = data + vprev_idx;
			v     = data + v_idx;
			vcur  = data + vcur_idx;
		}
		
		for (k = -d; k <= d; k += 2, vprev++) {
			if (k == -d || (k != d && vprev[-1] < vprev[0]))
				x = vprev[0];
			else
				x = vprev[-1] + 1;
			y = x - k;
			while (x < old_size && y < new_size && old[x] == new_[y])
				x++, y++;
			*v++ = x;
			if (x >= old_size && y >= new_size) {
				/* Shortest edit string found. */
				assert(x == old_size && y == new_size);
				triangle_out->data = data;
				triangle_out->solution_d = d;
				triangle_out->solution_k = k;
				triangle_out->solution_ptr = v - 1;
				return BDELTA_OK;
			}
		}
	}
	
	free(data);
	return BDELTA_INTERNAL_DMAX_EXCEEDED;
}

/*
 * Trace a solution back to the top, returning a string of instructions
 * for descending from the top to the solution.
 *
 * An instruction is one of the following:
 *
 *  -1: Descend left.
 *  +1: Descend right.
 *   0: Finished.  You should be at the solution now.
 *
 * If memory allocation fails, this function will return NULL.
 */
static signed char *climb_triangle(const Triangle *triangle)
{
	signed char *descent;
	int d, k;
	uint32_t *p;
	
	assert(triangle->solution_d >= 0);
	
	descent = malloc(triangle->solution_d + 1);
	if (descent == NULL)
		return NULL;
	d = triangle->solution_d;
	k = triangle->solution_k;
	p = triangle->solution_ptr;
	descent[d] = 0;
	
	while (d > 0) {
		if (k == -d || (k != d && *(p-d-1) < *(p-d))) {
			/* Climb right */
			k++;
			p = p - d;
			descent[--d] = -1;
		} else {
			/* Climb left */
			k--;
			p = p - d - 1;
			descent[--d] = 1;
		}
	}
	
	return descent;
}

/*
 * Generate the actual patch, given data produced by build_triangle and
 * climb_triangle.  new_ is needed for the content of the insertions.
 *
 * See the comment above the definition of Triangle.  It concisely documents
 * how a descent down the triangle corresponds to a patch script.
 *
 * The resulting patch, including the patch type byte, is appended to patch_out.
 *
 * Return values:
 *
 *  BDELTA_OK:      Success
 *  BDELTA_MEMORY:  Memory allocation failed
 */
static BDELTAcode descent_to_patch(
	const signed char *descent,
	const Triangle *triangle,
	const char *new_, uint32_t new_size,
	SB *patch_out)
{
	const char *new_end = new_ + new_size;
	uint32_t *p = triangle->data;
	uint32_t *p2;
	int d = 0;
	int k = 0;
	int pending_op = 0;
	int current_op;
	uint32_t pending_length = 0;
	uint32_t copy_length;
	
	if (sb_putc(patch_out, PT_CSI32) != 0)
		return BDELTA_MEMORY;
	
	if (*p > 0) {
		if (csi32_emit_op(patch_out, OP_COPY, *p, &new_) != BDELTA_OK)
			return BDELTA_MEMORY;
	}
	
	for (; *descent != 0; descent++, p = p2) {
		if (*descent < 0) {
			/* Descend left. */
			d++;
			k--;
			p2 = p + d;
			current_op = OP_INSERT;
			assert(*p2 >= *p);
			copy_length = *p2 - *p;
		} else {
			/* Descend right. */
			d++;
			k++;
			p2 = p + d + 1;
			current_op = OP_SKIP;
			assert(*p2 > *p);
			copy_length = *p2 - *p - 1;
		}
		
		if (pending_op == current_op) {
			pending_length++;
		} else {
			if (pending_op != 0) {
				if (csi32_emit_op(patch_out, pending_op, pending_length, &new_) != BDELTA_OK)
					return BDELTA_MEMORY;
			}
			pending_op = current_op;
			pending_length = 1;
		}
		
		if (copy_length > 0) {
			if (csi32_emit_op(patch_out, pending_op, pending_length, &new_) != BDELTA_OK)
				return BDELTA_MEMORY;
			pending_op = 0;
			if (csi32_emit_op(patch_out, OP_COPY, copy_length, &new_) != BDELTA_OK)
				return BDELTA_MEMORY;
		}
	}
	assert(d == triangle->solution_d);
	assert(k == triangle->solution_k);
	assert(p == triangle->solution_ptr);
	
	/* Emit the last pending op, unless it's a skip. */
	if (pending_op != 0 && pending_op != OP_SKIP) {
		if (csi32_emit_op(patch_out, pending_op, pending_length, &new_) != BDELTA_OK)
			return BDELTA_MEMORY;
	}
	
	assert(new_ == new_end);
	return BDELTA_OK;
}

/*
 * Generate a patch using Myers' O(ND) algorithm.
 *
 * The patch is appended to @patch_out, which must be initialized before calling.
 *
 * Return values:
 *
 *  BDELTA_OK:                         Success
 *  BDELTA_MEMORY:                     Memory allocation failed
 *  BDELTA_INTERNAL_INPUTS_TOO_LARGE:  Input sizes are too large
 *  BDELTA_INTERNAL_DMAX_EXCEEDED:     d_max exceeded (strings are too different)
 */
static BDELTAcode diff_myers(
	const char *old,  size_t old_size,
	const char *new_, size_t new_size,
	SB *patch_out)
{
	Triangle triangle;
	signed char *descent;
	BDELTAcode rc;
	
	/* Make sure old_size + new_size does not overflow int or uint32_t. */
	if (old_size >= UINT32_MAX ||
	    new_size >= UINT32_MAX - old_size ||
	    old_size >= (unsigned int)INT_MAX ||
	    new_size >= (unsigned int)INT_MAX - old_size)
		return BDELTA_INTERNAL_INPUTS_TOO_LARGE;
	
	rc = build_triangle(old, old_size, new_, new_size, 1000, &triangle);
	if (rc != BDELTA_OK)
		return rc;
	
	descent = climb_triangle(&triangle);
	if (descent == NULL)
		goto oom1;
	
	if (descent_to_patch(descent, &triangle, new_, new_size, patch_out) != BDELTA_OK)
		goto oom2;
	
	free(descent);
	free(triangle.data);
	return BDELTA_OK;
	
oom2:
	free(descent);
oom1:
	free(triangle.data);
	return BDELTA_MEMORY;
}

BDELTAcode bdelta_diff(
	const void  *old,       size_t  old_size,
	const void  *new_,      size_t  new_size,
	void       **patch_out, size_t *patch_size_out)
{
	SB patch;
	
	if (sb_init(&patch) != 0)
		goto out_of_memory;
	
	if (new_size == 0)
		goto emit_new_literally;
	
	if (diff_myers(old, old_size, new_, new_size, &patch) != BDELTA_OK)
		goto emit_new_literally;
	
	if (sb_size(&patch) > new_size) {
		/*
		 * A literal copy of new is no longer than this patch.
		 * All that for nothing.
		 */
		goto emit_new_literally;
	}
	
	/*
	 * Verify that patch, when applied to old, produces the correct text.
	 * If it doesn't, it's a bug, but fall back to a simple emit
	 * to avert data corruption.
	 */
	{
		void *result;
		size_t result_size;
		BDELTAcode rc;
		int correct;
		
		rc = bdelta_patch(
			old, old_size,
			patch.start, patch.cur - patch.start,
			&result, &result_size
		);
		
		switch (rc) {
			case BDELTA_OK:
				correct = (result_size == new_size &&
				           memcmp(result, new_, new_size) == 0);
				free(result);
				break;
			
			case BDELTA_MEMORY:
				goto out_of_memory;
			
			default:
				correct = 0;
				break;
		}
		
		if (!correct) {
			assert(0);
			goto emit_new_literally;
		}
	}
	
	sb_return(&patch, patch_out, patch_size_out);
	return BDELTA_OK;

emit_new_literally:
	if (patch.cur != patch.start) {
		free(patch.start);
		if (sb_init(&patch) != 0)
			goto out_of_memory;
	}
	if (sb_putc(&patch, PT_LITERAL) != 0 || sb_write(&patch, new_, new_size) != 0)
		goto out_of_memory;
	sb_return(&patch, patch_out, patch_size_out);
	return BDELTA_OK;

out_of_memory:
	sb_discard(&patch, patch_out, patch_size_out);
	return BDELTA_MEMORY;
}

/*
 * Return values:
 *
 *  BDELTA_OK:              Success
 *  BDELTA_PATCH_INVALID:   Patch is malformed
 *  BDELTA_PATCH_MISMATCH:  Old string is too small
 *  BDELTA_MEMORY:          Memory allocation failed
 */
static BDELTAcode patch_csi32(
	const unsigned char *o, const unsigned char *oe,
	const unsigned char *p, const unsigned char *pe,
	SB *new_out)
{
	int op;
	uint32_t size;
	
	while (csi32_parse_op(&p, pe, &op, &size)) {
		if ((op == OP_COPY || op == OP_SKIP) && (size_t)(oe - o) < size) {
			/* Copy or skip instruction exceeds length of old string. */
			return BDELTA_PATCH_MISMATCH;
		}
		if (op == OP_COPY || op == OP_INSERT)
			sb_need(new_out, size);
		
		switch (op) {
			case OP_COPY:  /* Copy @size bytes from old string. */
				memcpy(new_out->cur, o, size);
				new_out->cur += size;
				o += size;
				break;
			
			case OP_SKIP:  /* Skip @size bytes of old string. */
				o += size;
				break;
			
			case OP_INSERT:  /* Insert @size new bytes (from the patch script). */
				memcpy(new_out->cur, p, size);
				new_out->cur += size;
				p += size;
				break;
			
			default:
				assert(0);
		}
	}
	if (p != pe)
		return BDELTA_PATCH_INVALID;
	
	return BDELTA_OK;

out_of_memory:
	return BDELTA_MEMORY;
}

BDELTAcode bdelta_patch(
	const void  *old,     size_t  old_size,
	const void  *patch,   size_t  patch_size,
	void       **new_out, size_t *new_size_out)
{
	const unsigned char *o = old;
	const unsigned char *oe = o + old_size;
	const unsigned char *p = patch;
	const unsigned char *pe = p + patch_size;
	SB result;
	BDELTAcode rc;
	
	if (sb_init(&result) != 0) {
		rc = BDELTA_MEMORY;
		goto discard;
	}
	
	if (p >= pe) {
		rc = BDELTA_PATCH_INVALID;
		goto discard;
	}
	
	switch (*p++) {
		case PT_LITERAL:
			if (sb_write(&result, p, pe - p) != 0) {
				rc = BDELTA_MEMORY;
				goto discard;
			}
			break;
		
		case PT_CSI32:
			rc = patch_csi32(o, oe, p, pe, &result);
			if (rc != BDELTA_OK)
				goto discard;
			break;
		
		default:
			rc = BDELTA_PATCH_INVALID;
			goto discard;
	}
	
	sb_return(&result, new_out, new_size_out);
	return BDELTA_OK;

discard:
	sb_discard(&result, new_out, new_size_out);
	return rc;
}

const char *bdelta_strerror(BDELTAcode code)
{
	switch (code) {
		case BDELTA_OK:
			return "Success";
		case BDELTA_MEMORY:
			return "Could not allocate memory";
		case BDELTA_PATCH_INVALID:
			return "Patch is invalid";
		case BDELTA_PATCH_MISMATCH:
			return "Patch applied to wrong data";
		
		case BDELTA_INTERNAL_DMAX_EXCEEDED:
			return "Difference threshold exceeded (internal error)";
		case BDELTA_INTERNAL_INPUTS_TOO_LARGE:
			return "Inputs are too large (internal error)";
		
		default:
			return "Invalid error code";
	}
}

void bdelta_perror(const char *s, BDELTAcode code)
{
	if (s != NULL && *s != '\0')
		fprintf(stderr, "%s: %s\n", s, bdelta_strerror(code));
	else
		fprintf(stderr, "%s\n", bdelta_strerror(code));
}