mercurial/mpatch.c
author Augie Fackler <augie@google.com>
Thu, 28 May 2020 16:16:13 -0400
changeset 44872 aa790f7c967a
parent 41336 763b45bc4483
child 46819 d4ba4d51f85f
permissions -rw-r--r--
filemerge: add __bytes__ for absentfilectx This will at _least_ aid some upcoming debugging. Differential Revision: https://phab.mercurial-scm.org/D8592
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     1
/*
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     2
 mpatch.c - efficient binary patching for Mercurial
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     3
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     4
 This implements a patch algorithm that's O(m + nlog n) where m is the
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     5
 size of the output and n is the number of patches.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     6
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     7
 Given a list of binary patches, it unpacks each into a hunk list,
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     8
 then combines the hunk lists with a treewise recursion to form a
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     9
 single hunk list. This hunk list is then applied to the original
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    10
 text.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    11
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    12
 The text (or binary) fragments are copied directly from their source
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    13
 Python objects into a preallocated output string to avoid the
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    14
 allocation of intermediate Python objects. Working memory is about 2x
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    15
 the total number of hunks.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    16
2859
345bac2bc4ec update copyrights.
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2543
diff changeset
    17
 Copyright 2005, 2006 Matt Mackall <mpm@selenic.com>
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    18
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    19
 This software may be used and distributed according to the terms
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    20
 of the GNU General Public License, incorporated herein by reference.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    21
*/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    22
38190
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    23
#include <limits.h>
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    24
#include <stdlib.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    25
#include <string.h>
2468
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    26
29444
284d742e5611 internals: move the bitmanipulation routines into its own file
Maciej Fijalkowski <fijall@gmail.com>
parents: 28782
diff changeset
    27
#include "bitmanipulation.h"
29691
e9a0bcc9314d mpatch: change Py_ssize_t to ssize_t in places that will be later copied
Maciej Fijalkowski <fijall@gmail.com>
parents: 29444
diff changeset
    28
#include "compat.h"
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
    29
#include "mpatch.h"
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    30
38190
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    31
/* VC9 doesn't include bool and lacks stdbool.h based on cext/util.h */
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    32
#if defined(_MSC_VER) || __STDC_VERSION__ < 199901L
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    33
#define true 1
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    34
#define false 0
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    35
typedef unsigned char bool;
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    36
#else
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    37
#include <stdbool.h>
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    38
#endif
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    39
29741
9a1685c70db4 mpatch: change lalloc() to local function
Yuya Nishihara <yuya@tcha.org>
parents: 29740
diff changeset
    40
static struct mpatch_flist *lalloc(ssize_t size)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    41
{
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
    42
	struct mpatch_flist *a = NULL;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    43
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
    44
	if (size < 1) {
3138
cc856c4d91ca mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents: 2859
diff changeset
    45
		size = 1;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
    46
	}
3138
cc856c4d91ca mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents: 2859
diff changeset
    47
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
    48
	a = (struct mpatch_flist *)malloc(sizeof(struct mpatch_flist));
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    49
	if (a) {
34633
347c0f4232e1 mpatch: re-wrap wide line with clang-format
Augie Fackler <augie@google.com>
parents: 29749
diff changeset
    50
		a->base = (struct mpatch_frag *)malloc(
347c0f4232e1 mpatch: re-wrap wide line with clang-format
Augie Fackler <augie@google.com>
parents: 29749
diff changeset
    51
		    sizeof(struct mpatch_frag) * size);
2048
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    52
		if (a->base) {
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    53
			a->head = a->tail = a->base;
2048
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    54
			return a;
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    55
		}
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    56
		free(a);
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    57
	}
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
    58
	return NULL;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    59
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    60
29693
b9b9f9a92481 mpatch: split mpatch into two files
Maciej Fijalkowski <fijall@gmail.com>
parents: 29692
diff changeset
    61
void mpatch_lfree(struct mpatch_flist *a)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    62
{
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    63
	if (a) {
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    64
		free(a->base);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    65
		free(a);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    66
	}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    67
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    68
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
    69
static ssize_t lsize(struct mpatch_flist *a)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    70
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    71
	return a->tail - a->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    72
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    73
38190
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    74
/* add helper to add src and *dest iff it won't overflow */
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    75
static inline bool safeadd(int src, int *dest)
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    76
{
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    77
	if ((src > 0) == (*dest > 0)) {
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    78
		if (*dest > 0) {
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    79
			if (src > (INT_MAX - *dest)) {
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    80
				return false;
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    81
			}
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    82
		} else {
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    83
			if (src < (INT_MIN - *dest)) {
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    84
				return false;
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    85
			}
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    86
		}
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    87
	}
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    88
	*dest += src;
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    89
	return true;
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    90
}
1ec4cb8cbc87 mpatch: introduce a safeadd() helper to work around UB int overflow
Augie Fackler <augie@google.com>
parents: 38189
diff changeset
    91
38191
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
    92
/* subtract src from dest and store result in dest */
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
    93
static inline bool safesub(int src, int *dest)
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
    94
{
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
    95
	if (((src > 0) && (*dest < INT_MIN + src)) ||
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
    96
	    ((src < 0) && (*dest > INT_MAX + src))) {
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
    97
		return false;
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
    98
	}
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
    99
	*dest -= src;
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
   100
	return true;
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
   101
}
b8b253aec953 mpatch: introduce a safesub() helper as well
Augie Fackler <augie@google.com>
parents: 38190
diff changeset
   102
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   103
/* move hunks in source that are less cut to dest, compensating
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   104
   for changes in offset. the last hunk may be split if necessary.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   105
*/
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   106
static int gather(struct mpatch_flist *dest, struct mpatch_flist *src, int cut,
34800
761355833867 mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents: 34634
diff changeset
   107
                  int offset)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   108
{
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   109
	struct mpatch_frag *d = dest->tail, *s = src->head;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   110
	int postend, c, l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   111
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   112
	while (s != src->tail) {
38192
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   113
		int soffset = s->start;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   114
		if (!safeadd(offset, &soffset)) {
38192
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   115
			break; /* add would overflow, oh well */
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   116
		}
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   117
		if (soffset >= cut) {
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   118
			break; /* we've gone far enough */
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   119
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   120
38192
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   121
		postend = offset;
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   122
		if (!safeadd(s->start, &postend) ||
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   123
		    !safeadd(s->len, &postend)) {
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   124
			break;
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   125
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   126
		if (postend <= cut) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   127
			/* save this hunk */
38192
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   128
			int tmp = s->start;
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   129
			if (!safesub(s->end, &tmp)) {
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   130
				break;
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   131
			}
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   132
			if (!safeadd(s->len, &tmp)) {
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   133
				break;
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   134
			}
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   135
			if (!safeadd(tmp, &offset)) {
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   136
				break; /* add would overflow, oh well */
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   137
			}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   138
			*d++ = *s++;
34634
2e08b69bcd29 mpatch: reflow two oddly formatted else blocks with clang-format
Augie Fackler <augie@google.com>
parents: 34633
diff changeset
   139
		} else {
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   140
			/* break up this hunk */
38192
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   141
			c = cut;
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   142
			if (!safesub(offset, &c)) {
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   143
				break;
0b208c13781c mpatch: fix UB in int overflows in gather() (SEC)
Augie Fackler <augie@google.com>
parents: 38191
diff changeset
   144
			}
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   145
			if (s->end < c) {
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   146
				c = s->end;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   147
			}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   148
			l = cut - offset - s->start;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   149
			if (s->len < l) {
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   150
				l = s->len;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   151
			}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   152
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   153
			offset += s->start + l - c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   154
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   155
			d->start = s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   156
			d->end = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   157
			d->len = l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   158
			d->data = s->data;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   159
			d++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   160
			s->start = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   161
			s->len = s->len - l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   162
			s->data = s->data + l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   163
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   164
			break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   165
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   166
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   167
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   168
	dest->tail = d;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   169
	src->head = s;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   170
	return offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   171
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   172
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   173
/* like gather, but with no output list */
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   174
static int discard(struct mpatch_flist *src, int cut, int offset)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   175
{
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   176
	struct mpatch_frag *s = src->head;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   177
	int postend, c, l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   178
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   179
	while (s != src->tail) {
38193
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   180
		int cmpcut = s->start;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   181
		if (!safeadd(offset, &cmpcut)) {
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   182
			break;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   183
		}
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   184
		if (cmpcut >= cut) {
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   185
			break;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   186
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   187
38193
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   188
		postend = offset;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   189
		if (!safeadd(s->start, &postend)) {
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   190
			break;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   191
		}
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   192
		if (!safeadd(s->len, &postend)) {
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   193
			break;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   194
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   195
		if (postend <= cut) {
38193
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   196
			/* do the subtraction first to avoid UB integer overflow
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   197
			 */
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   198
			int tmp = s->start;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   199
			if (!safesub(s->end, &tmp)) {
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   200
				break;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   201
			}
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   202
			if (!safeadd(s->len, &tmp)) {
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   203
				break;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   204
			}
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   205
			if (!safeadd(tmp, &offset)) {
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   206
				break;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   207
			}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   208
			s++;
34634
2e08b69bcd29 mpatch: reflow two oddly formatted else blocks with clang-format
Augie Fackler <augie@google.com>
parents: 34633
diff changeset
   209
		} else {
38193
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   210
			c = cut;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   211
			if (!safesub(offset, &c)) {
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   212
				break;
7f22ef3c0ee7 mpatch: fix UB integer overflows in discard() (SEC)
Augie Fackler <augie@google.com>
parents: 38192
diff changeset
   213
			}
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   214
			if (s->end < c) {
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   215
				c = s->end;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   216
			}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   217
			l = cut - offset - s->start;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   218
			if (s->len < l) {
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   219
				l = s->len;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   220
			}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   221
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   222
			offset += s->start + l - c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   223
			s->start = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   224
			s->len = s->len - l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   225
			s->data = s->data + l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   226
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   227
			break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   228
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   229
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   230
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   231
	src->head = s;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   232
	return offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   233
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   234
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   235
/* combine hunk lists a and b, while adjusting b for offset changes in a/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   236
   this deletes a and b and returns the resultant list. */
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   237
static struct mpatch_flist *combine(struct mpatch_flist *a,
34800
761355833867 mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents: 34634
diff changeset
   238
                                    struct mpatch_flist *b)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   239
{
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   240
	struct mpatch_flist *c = NULL;
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   241
	struct mpatch_frag *bh, *ct;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   242
	int offset = 0, post;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   243
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   244
	if (a && b) {
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   245
		c = lalloc((lsize(a) + lsize(b)) * 2);
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   246
	}
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   247
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   248
	if (c) {
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   249
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   250
		for (bh = b->head; bh != b->tail; bh++) {
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   251
			/* save old hunks */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   252
			offset = gather(c, a, bh->start, offset);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   253
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   254
			/* discard replaced hunks */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   255
			post = discard(a, bh->end, offset);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   256
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   257
			/* insert new hunk */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   258
			ct = c->tail;
38195
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   259
			ct->start = bh->start;
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   260
			ct->end = bh->end;
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   261
			if (!safesub(offset, &(ct->start)) ||
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   262
			    !safesub(post, &(ct->end))) {
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   263
				/* It was already possible to exit
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   264
				 * this function with a return value
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   265
				 * of NULL before the safesub()s were
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   266
				 * added, so this should be fine. */
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   267
				mpatch_lfree(c);
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   268
				c = NULL;
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   269
				goto done;
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   270
			}
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   271
			ct->len = bh->len;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   272
			ct->data = bh->data;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   273
			c->tail++;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   274
			offset = post;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   275
		}
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   276
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   277
		/* hold on to tail from a */
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   278
		memcpy(c->tail, a->head, sizeof(struct mpatch_frag) * lsize(a));
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   279
		c->tail += lsize(a);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   280
	}
38195
9c5ced5276d6 mpatch: avoid integer overflow in combine() (SEC)
Augie Fackler <augie@google.com>
parents: 38194
diff changeset
   281
done:
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   282
	mpatch_lfree(a);
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   283
	mpatch_lfree(b);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   284
	return c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   285
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   286
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   287
/* decode a binary patch into a hunk list */
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   288
int mpatch_decode(const char *bin, ssize_t len, struct mpatch_flist **res)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   289
{
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   290
	struct mpatch_flist *l;
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   291
	struct mpatch_frag *lt;
20167
09e41ac6289d mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents: 16758
diff changeset
   292
	int pos = 0;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   293
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   294
	/* assume worst case size, we won't have many of these lists */
28656
b6ed2505d6cf parsers: fix list sizing rounding error (SEC)
Matt Mackall <mpm@selenic.com>
parents: 20167
diff changeset
   295
	l = lalloc(len / 12 + 1);
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   296
	if (!l) {
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   297
		return MPATCH_ERR_NO_MEM;
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   298
	}
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   299
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   300
	lt = l->tail;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   301
38187
90a274965de7 mpatch: be more careful about parsing binary patch data (SEC)
Augie Fackler <augie@google.com>
parents: 34801
diff changeset
   302
	/* We check against len-11 to ensure we have at least 12 bytes
90a274965de7 mpatch: be more careful about parsing binary patch data (SEC)
Augie Fackler <augie@google.com>
parents: 34801
diff changeset
   303
	   left in the patch so we can read our three be32s out of it. */
90a274965de7 mpatch: be more careful about parsing binary patch data (SEC)
Augie Fackler <augie@google.com>
parents: 34801
diff changeset
   304
	while (pos >= 0 && pos < (len - 11)) {
20167
09e41ac6289d mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents: 16758
diff changeset
   305
		lt->start = getbe32(bin + pos);
09e41ac6289d mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents: 16758
diff changeset
   306
		lt->end = getbe32(bin + pos + 4);
09e41ac6289d mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents: 16758
diff changeset
   307
		lt->len = getbe32(bin + pos + 8);
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   308
		if (lt->start < 0 || lt->start > lt->end || lt->len < 0) {
28657
b9714d958e89 parsers: detect short records (SEC)
Matt Mackall <mpm@selenic.com>
parents: 28656
diff changeset
   309
			break; /* sanity check */
41336
763b45bc4483 cleanup: use clang-tidy to add missing {} around one-line statements
Augie Fackler <augie@google.com>
parents: 38195
diff changeset
   310
		}
38194
59837a16896d mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents: 38193
diff changeset
   311
		if (!safeadd(12, &pos)) {
59837a16896d mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents: 38193
diff changeset
   312
			break;
59837a16896d mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents: 38193
diff changeset
   313
		}
59837a16896d mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents: 38193
diff changeset
   314
		lt->data = bin + pos;
59837a16896d mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents: 38193
diff changeset
   315
		if (!safeadd(lt->len, &pos)) {
59837a16896d mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents: 38193
diff changeset
   316
			break;
59837a16896d mpatch: avoid integer overflow in mpatch_decode (SEC)
Augie Fackler <augie@google.com>
parents: 38193
diff changeset
   317
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   318
		lt++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   319
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   320
20167
09e41ac6289d mpatch: rewrite pointer overflow checks
Matt Mackall <mpm@selenic.com>
parents: 16758
diff changeset
   321
	if (pos != len) {
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   322
		mpatch_lfree(l);
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   323
		return MPATCH_ERR_CANNOT_BE_DECODED;
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   324
	}
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   325
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   326
	l->tail = lt;
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   327
	*res = l;
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   328
	return 0;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   329
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   330
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   331
/* calculate the size of resultant text */
29693
b9b9f9a92481 mpatch: split mpatch into two files
Maciej Fijalkowski <fijall@gmail.com>
parents: 29692
diff changeset
   332
ssize_t mpatch_calcsize(ssize_t len, struct mpatch_flist *l)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   333
{
29691
e9a0bcc9314d mpatch: change Py_ssize_t to ssize_t in places that will be later copied
Maciej Fijalkowski <fijall@gmail.com>
parents: 29444
diff changeset
   334
	ssize_t outlen = 0, last = 0;
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   335
	struct mpatch_frag *f = l->head;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   336
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   337
	while (f != l->tail) {
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   338
		if (f->start < last || f->end > len) {
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   339
			return MPATCH_ERR_INVALID_PATCH;
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   340
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   341
		outlen += f->start - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   342
		last = f->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   343
		outlen += f->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   344
		f++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   345
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   346
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   347
	outlen += len - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   348
	return outlen;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   349
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   350
29693
b9b9f9a92481 mpatch: split mpatch into two files
Maciej Fijalkowski <fijall@gmail.com>
parents: 29692
diff changeset
   351
int mpatch_apply(char *buf, const char *orig, ssize_t len,
34800
761355833867 mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents: 34634
diff changeset
   352
                 struct mpatch_flist *l)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   353
{
29692
6b3a8d034b69 mpatch: provide things that will be exported later with a prefixed name
Maciej Fijalkowski <fijall@gmail.com>
parents: 29691
diff changeset
   354
	struct mpatch_frag *f = l->head;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   355
	int last = 0;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   356
	char *p = buf;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   357
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   358
	while (f != l->tail) {
38189
faa924469635 mpatch: ensure fragment start isn't past the end of orig (SEC)
Augie Fackler <augie@google.com>
parents: 38188
diff changeset
   359
		if (f->start < last || f->start > len || f->end > len ||
faa924469635 mpatch: ensure fragment start isn't past the end of orig (SEC)
Augie Fackler <augie@google.com>
parents: 38188
diff changeset
   360
		    last < 0) {
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   361
			return MPATCH_ERR_INVALID_PATCH;
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   362
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   363
		memcpy(p, orig + last, f->start - last);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   364
		p += f->start - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   365
		memcpy(p, f->data, f->len);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   366
		last = f->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   367
		p += f->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   368
		f++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   369
	}
38188
1acfc35d478c mpatch: protect against underflow in mpatch_apply (SEC)
Augie Fackler <augie@google.com>
parents: 38187
diff changeset
   370
	if (last < 0) {
1acfc35d478c mpatch: protect against underflow in mpatch_apply (SEC)
Augie Fackler <augie@google.com>
parents: 38187
diff changeset
   371
		return MPATCH_ERR_INVALID_PATCH;
1acfc35d478c mpatch: protect against underflow in mpatch_apply (SEC)
Augie Fackler <augie@google.com>
parents: 38187
diff changeset
   372
	}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   373
	memcpy(p, orig + last, len - last);
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   374
	return 0;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   375
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   376
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   377
/* recursively generate a patch of all bins between start and end */
34800
761355833867 mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents: 34634
diff changeset
   378
struct mpatch_flist *
761355833867 mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents: 34634
diff changeset
   379
mpatch_fold(void *bins, struct mpatch_flist *(*get_next_item)(void *, ssize_t),
761355833867 mpatch: reformat function prototypes with clang-format
Augie Fackler <augie@google.com>
parents: 34634
diff changeset
   380
            ssize_t start, ssize_t end)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   381
{
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   382
	ssize_t len;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   383
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   384
	if (start + 1 == end) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   385
		/* trivial case, output a decoded list */
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   386
		return get_next_item(bins, start);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   387
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   388
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   389
	/* divide and conquer, memory management is elsewhere */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   390
	len = (end - start) / 2;
29694
55dd12204b8e mpatch: remove dependency on Python.h in mpatch.c
Maciej Fijalkowski <fijall@gmail.com>
parents: 29693
diff changeset
   391
	return combine(mpatch_fold(bins, get_next_item, start, start + len),
34801
1f4249c764f1 mpatch: switch alignment of wrapped line from tab to spaces with clang-format
Augie Fackler <augie@google.com>
parents: 34800
diff changeset
   392
	               mpatch_fold(bins, get_next_item, start + len, end));
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   393
}