annotate mercurial/mpatch.c @ 43679:7cf332318f62

encoding: make getcols() raise exception explicitly This helps pytype. File "mercurial/encoding.py", line 329, in getcols: bad option in return type [bad-return-type] Expected: bytes Actually returned: None
author Yuya Nishihara <yuya@tcha.org>
date Sat, 16 Nov 2019 15:43:21 +0900
parents 763b45bc4483
children d4ba4d51f85f
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
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 }