path: root/libpatch_rewrite_diff2.c

/* See LICENSE file for copyright and license details. */
#include "common.h"


#define REPETITION_MAX ((1U << (sizeof(int) * CHAR_BIT - CHAR_BIT)) - 1U)


static int
allocate(struct libpatch_diff2 **diff, size_t *difflen, size_t *r, size_t *w, int change)
{
#define GROWTH 32U

	void *new;
	size_t size;

	if (*w == *r) {
		if (GROWTH > SIZE_MAX / sizeof(**diff) - *difflen) {
			errno = ENOMEM;
			return -1;
		}
		size = (*difflen + GROWTH) * sizeof(**diff);
		new = realloc(*diff, size);
		if (!new)
			return -1;
		*diff = new;
		memmove(&(*diff)[*r + GROWTH], &(*diff)[*r], *difflen - *r);
		*difflen += GROWTH;
		*r += GROWTH;
	}

	(*diff)[*w].change = (unsigned char)change;
	(*diff)[*w].repetition = 0;
	*w += 1;
	return 0;
}


static int
putchange(struct libpatch_diff2 **diff, size_t *difflen, size_t *r, size_t *w, int change, size_t count)
{
	if (!count)
		return 0;
	if (*w && (*diff)[*w - 1].change == change && (*diff)[*w - 1].repetition < REPETITION_MAX)
		goto start;
	do {
		if (allocate(diff, difflen, r, w, change))
			return -1;
	start:
		if (count > (size_t)(REPETITION_MAX - (*diff)[*w - 1].repetition)) {
			count -= (size_t)(REPETITION_MAX - (*diff)[*w - 1].repetition);
			(*diff)[*w - 1].repetition = REPETITION_MAX;
		} else {
			(*diff)[*w - 1].repetition += count;
			break;
		}
	} while (count);
	return 0;
}


static int
put(struct libpatch_diff2 **diff, size_t *difflen,
    const struct libpatch_diff2_spec *spec, size_t *r, size_t *w,
    size_t common, size_t onlyfile1, size_t onlyfile2, size_t changed)
{
	int a, b;
	size_t an, bn, i;
	size_t context, a_context, z_context;

	if (common) {
		if (spec->full_context) {
			return putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, common);
		} else if (*w > 0 && *r < *difflen) {
			context = MAX(spec->context_after + spec->context_before, spec->context_between);
			if (common <= context)
				return putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, common);
			common -= a_context = MIN(spec->context_after, common);
			common -= z_context = MIN(spec->context_before, common);
			return -(putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, a_context) ||
			         putchange(diff, difflen, r, w, LIBPATCH_DIFF2_SKIP, common) ||
			         putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, z_context));
		} else if (*w > 0) {
			common -= context = MIN(spec->context_after, common);
			return -(putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, context) ||
			         putchange(diff, difflen, r, w, LIBPATCH_DIFF2_SKIP, common));
		} else if (*r < *difflen) {
			common -= context = MIN(spec->context_before, common);
			return -(putchange(diff, difflen, r, w, LIBPATCH_DIFF2_SKIP, common) ||
			         putchange(diff, difflen, r, w, LIBPATCH_DIFF2_CONTEXT, context));
		} else {
			return putchange(diff, difflen, r, w, LIBPATCH_DIFF2_SKIP, common);
		}

	} else {
		if (!spec->keep_split_changes) {
			changed += MIN(onlyfile1, onlyfile2);
			onlyfile1 -= changed;
			onlyfile2 -= changed;
		}

		if (spec->single_file_change_order == LIBPATCH_DIFF2_FILE1_ONLY_FIRST) {
			a = LIBPATCH_DIFF2_FILE1_ONLY;
			an = onlyfile1;
			b = LIBPATCH_DIFF2_FILE2_ONLY;
			bn = onlyfile2;
		} else {
			a = LIBPATCH_DIFF2_FILE2_ONLY;
			an = onlyfile2;
			b = LIBPATCH_DIFF2_FILE1_ONLY;
			bn = onlyfile1;
		}

		if (spec->two_file_change_order == LIBPATCH_DIFF2_TWO_FILE_CHANGES_BEFORE_SINGLE_FILE)
			if (putchange(diff, difflen, r, w, LIBPATCH_DIFF2_TWO_FILE_CHANGE, changed))
				return -1;

		if (putchange(diff, difflen, r, w, a, an))
			return -1;

		if (spec->two_file_change_order == LIBPATCH_DIFF2_NO_TWO_FILE_CHANGES) {
			if (putchange(diff, difflen, r, w, a, changed))
				return -1;
			if (putchange(diff, difflen, r, w, b, changed))
				return -1;
		} else if (spec->two_file_change_order == LIBPATCH_DIFF2_NO_TWO_FILE_CHANGES_INTERLEAVE) {
			for (i = 0; i < changed; i++) {
				if (putchange(diff, difflen, r, w, a, 1))
					return -1;
				if (putchange(diff, difflen, r, w, b, 1))
					return -1;
			}
		}

		if (spec->two_file_change_order == LIBPATCH_DIFF2_TWO_FILE_CHANGES_BETWEEN_SINGLE_FILE)
			if (putchange(diff, difflen, r, w, LIBPATCH_DIFF2_TWO_FILE_CHANGE, changed))
				return -1;

		if (putchange(diff, difflen, r, w, b, bn))
			return -1;

		if (spec->two_file_change_order == LIBPATCH_DIFF2_TWO_FILE_CHANGES_AFTER_SINGLE_FILE)
			if (putchange(diff, difflen, r, w, LIBPATCH_DIFF2_TWO_FILE_CHANGE, changed))
				return -1;

		return 0;
	}
}


int
libpatch_rewrite_diff2(struct libpatch_diff2 **diff, size_t *difflen,
                       const struct libpatch_diff2_spec *spec)
{
	size_t r, w = 0;
	size_t saved0 = 0, saved1 = 0, saved2 = 0, saved3 = 0;

	for (r = 0; r < *difflen; r++) {
		if ((*diff)[r].change == LIBPATCH_DIFF2_SKIP ||
		    (*diff)[r].change == LIBPATCH_DIFF2_CONTEXT) {
			if (saved1 || saved2) {
				if (put(diff, difflen, spec, &r, &w, saved0, saved1, saved2, saved3))
					return -1;
				saved1 = 0;
				saved2 = 0;
				saved3 = 0;
			}
			saved0 += (size_t)(*diff)[r].repetition;
		} else {
			if (saved0) {
				if (put(diff, difflen, spec, &r, &w, saved0, saved1, saved2, saved3))
					return -1;
				saved0 = 0;
			}
			if (spec->keep_split_changes) {
				if ((*diff)[r].change == LIBPATCH_DIFF2_FILE1_ONLY)
					saved1 += (size_t)(*diff)[r].repetition;
				else if ((*diff)[r].change == LIBPATCH_DIFF2_FILE2_ONLY)
					saved2 += (size_t)(*diff)[r].repetition;
				else
					saved3 += (size_t)(*diff)[r].repetition;
			} else {
				if ((*diff)[r].change != LIBPATCH_DIFF2_FILE2_ONLY)
					saved1 += (size_t)(*diff)[r].repetition;
				if ((*diff)[r].change != LIBPATCH_DIFF2_FILE1_ONLY)
					saved2 += (size_t)(*diff)[r].repetition;
			}
		}
	}

	if (put(diff, difflen, spec, &r, &w, saved0, saved1, saved2, saved3))
		return -1;

	*difflen = w;
	return 0;
}