delta-apply.c 2.58 KB
Newer Older
1
#include "common.h"
2
#include "git2/odb.h"
3
#include "delta-apply.h"
4 5 6 7 8 9 10 11

/*
 * This file was heavily cribbed from BinaryDelta.java in JGit, which
 * itself was heavily cribbed from <code>patch-delta.c</code> in the
 * GIT project.   The original delta patching code was written by
 * Nicolas Pitre <nico@cam.org>.
 */

12 13
static int hdr_sz(
	size_t *size,
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
	const unsigned char **delta,
	const unsigned char *end)
{
	const unsigned char *d = *delta;
	size_t r = 0;
	unsigned int c, shift = 0;

	do {
		if (d == end)
			return -1;
		c = *d++;
		r |= (c & 0x7f) << shift;
		shift += 7;
	} while (c & 0x80);
	*delta = d;
29 30
	*size = r;
	return 0;
31 32 33
}

int git__delta_apply(
34
	git_rawobj *out,
35 36 37 38 39 40
	const unsigned char *base,
	size_t base_len,
	const unsigned char *delta,
	size_t delta_len)
{
	const unsigned char *delta_end = delta + delta_len;
41
	size_t base_sz, res_sz;
42 43 44 45 46 47
	unsigned char *res_dp;

	/* Check that the base size matches the data we were given;
	 * if not we would underflow while accessing data from the
	 * base object, resulting in data corruption or segfault.
	 */
48
	if ((hdr_sz(&base_sz, &delta, delta_end) < 0) || (base_sz != base_len))
49
		return git__throw(GIT_ERROR, "Failed to apply delta. Base size does not match given data");
50 51

	if (hdr_sz(&res_sz, &delta, delta_end) < 0)
52
		return git__throw(GIT_ERROR, "Failed to apply delta. Base size does not match given data");
53

54
	if ((res_dp = git__malloc(res_sz + 1)) == NULL)
55
		return GIT_ENOMEM;
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
	res_dp[res_sz] = '\0';
	out->data = res_dp;
	out->len = res_sz;

	while (delta < delta_end) {
		unsigned char cmd = *delta++;
		if (cmd & 0x80) {
			/* cmd is a copy instruction; copy from the base.
			 */
			size_t off = 0, len = 0;

			if (cmd & 0x01) off  = *delta++;
			if (cmd & 0x02) off |= *delta++ <<  8;
			if (cmd & 0x04) off |= *delta++ << 16;
			if (cmd & 0x08) off |= *delta++ << 24;

			if (cmd & 0x10) len  = *delta++;
			if (cmd & 0x20) len |= *delta++ <<  8;
			if (cmd & 0x40) len |= *delta++ << 16;
			if (!len)       len  = 0x10000;

			if (base_len < off + len || res_sz < len)
				goto fail;
			memcpy(res_dp, base + off, len);
			res_dp += len;
			res_sz -= len;

		} else if (cmd) {
			/* cmd is a literal insert instruction; copy from
			 * the delta stream itself.
			 */
			if (delta_end - delta < cmd || res_sz < cmd)
				goto fail;
			memcpy(res_dp, delta, cmd);
			delta  += cmd;
			res_dp += cmd;
			res_sz -= cmd;

		} else {
			/* cmd == 0 is reserved for future encodings.
			 */
			goto fail;
		}
	}

	if (delta != delta_end || res_sz)
		goto fail;
	return GIT_SUCCESS;

fail:
	free(out->data);
	out->data = NULL;
108
	return git__throw(GIT_ERROR, "Failed to apply delta");
109
}