Mercurial > hg
annotate mercurial/mpatch.c @ 8564:6b9ec23b09fc
named branches: improve pre-push logic (issue736)
Each named branch is considered separately, and the push is allowed if
no new branch heads are created for any named branch to be pushed.
Due to some tests's use of --debug, their output will change after this
addition. This has been fixed as well.
Co-contributor: Henrik Stuart <henrik.stuart@edlund.dk>
author | Sune Foldager <cryo@cyanite.org> |
---|---|
date | Sat, 23 May 2009 17:04:31 +0200 |
parents | bfad9865b1dc |
children | 08a0f04b56bd |
rev | line source |
---|---|
72 | 1 /* |
2 mpatch.c - efficient binary patching for Mercurial | |
3 | |
4 This implements a patch algorithm that's O(m + nlog n) where m is the | |
5 size of the output and n is the number of patches. | |
6 | |
7 Given a list of binary patches, it unpacks each into a hunk list, | |
8 then combines the hunk lists with a treewise recursion to form a | |
9 single hunk list. This hunk list is then applied to the original | |
10 text. | |
11 | |
12 The text (or binary) fragments are copied directly from their source | |
13 Python objects into a preallocated output string to avoid the | |
14 allocation of intermediate Python objects. Working memory is about 2x | |
15 the total number of hunks. | |
16 | |
2859 | 17 Copyright 2005, 2006 Matt Mackall <mpm@selenic.com> |
72 | 18 |
19 This software may be used and distributed according to the terms | |
20 of the GNU General Public License, incorporated herein by reference. | |
21 */ | |
22 | |
23 #include <Python.h> | |
24 #include <stdlib.h> | |
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 |
5459
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
27 /* Definitions to get compatibility with python 2.4 and earlier which |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
28 does not have Py_ssize_t. See also PEP 353. |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
29 Note: msvc (8 or earlier) does not have ssize_t, so we use Py_ssize_t. |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
30 */ |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
31 #if PY_VERSION_HEX < 0x02050000 && !defined(PY_SSIZE_T_MIN) |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
32 typedef int Py_ssize_t; |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
33 #define PY_SSIZE_T_MAX INT_MAX |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
34 #define PY_SSIZE_T_MIN INT_MIN |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
35 #endif |
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
36 |
410
7c678976df3e
Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents:
384
diff
changeset
|
37 #ifdef _WIN32 |
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
|
38 # ifdef _MSC_VER |
1ac0574f1768
mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents:
2083
diff
changeset
|
39 /* msvc 6.0 has problems */ |
1ac0574f1768
mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents:
2083
diff
changeset
|
40 # define inline __inline |
551 | 41 typedef unsigned long uint32_t; |
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
|
42 # else |
1ac0574f1768
mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents:
2083
diff
changeset
|
43 # include <stdint.h> |
1ac0574f1768
mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents:
2083
diff
changeset
|
44 # endif |
411
9e9f7ab43ce2
Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents:
410
diff
changeset
|
45 static uint32_t ntohl(uint32_t x) |
9e9f7ab43ce2
Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents:
410
diff
changeset
|
46 { |
9e9f7ab43ce2
Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents:
410
diff
changeset
|
47 return ((x & 0x000000ffUL) << 24) | |
9e9f7ab43ce2
Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents:
410
diff
changeset
|
48 ((x & 0x0000ff00UL) << 8) | |
9e9f7ab43ce2
Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents:
410
diff
changeset
|
49 ((x & 0x00ff0000UL) >> 8) | |
9e9f7ab43ce2
Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents:
410
diff
changeset
|
50 ((x & 0xff000000UL) >> 24); |
410
7c678976df3e
Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents:
384
diff
changeset
|
51 } |
7c678976df3e
Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents:
384
diff
changeset
|
52 #else |
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
|
53 /* not windows */ |
1ac0574f1768
mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents:
2083
diff
changeset
|
54 # include <sys/types.h> |
7036
bfad9865b1dc
allow Mercurial to compile on Haiku
Scott McCreary <scottmc2@gmail.com>
parents:
5460
diff
changeset
|
55 # if defined __BEOS__ && !defined __HAIKU__ |
4073
95ffa36d1d2a
BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents:
3138
diff
changeset
|
56 # include <ByteOrder.h> |
95ffa36d1d2a
BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents:
3138
diff
changeset
|
57 # else |
95ffa36d1d2a
BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents:
3138
diff
changeset
|
58 # include <arpa/inet.h> |
95ffa36d1d2a
BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents:
3138
diff
changeset
|
59 # endif |
2543
860e9c83fc59
Include inttypes.h instead of stdint.h (fixes issue299)
Thomas Arendsen Hein <thomas@intevation.de>
parents:
2468
diff
changeset
|
60 # include <inttypes.h> |
410
7c678976df3e
Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents:
384
diff
changeset
|
61 #endif |
72 | 62 |
63 static char mpatch_doc[] = "Efficient binary patching."; | |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
64 static PyObject *mpatch_Error; |
72 | 65 |
66 struct frag { | |
67 int start, end, len; | |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
68 const char *data; |
72 | 69 }; |
70 | |
71 struct flist { | |
72 struct frag *base, *head, *tail; | |
73 }; | |
74 | |
75 static struct flist *lalloc(int size) | |
76 { | |
128 | 77 struct flist *a = NULL; |
72 | 78 |
3138
cc856c4d91ca
mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents:
2859
diff
changeset
|
79 if (size < 1) |
cc856c4d91ca
mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents:
2859
diff
changeset
|
80 size = 1; |
cc856c4d91ca
mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents:
2859
diff
changeset
|
81 |
1978
10606ee61107
do proper typecasting on malloc() and calloc() calls
TK Soh <teekaysoh@yahoo.com>
parents:
1746
diff
changeset
|
82 a = (struct flist *)malloc(sizeof(struct flist)); |
128 | 83 if (a) { |
1978
10606ee61107
do proper typecasting on malloc() and calloc() calls
TK Soh <teekaysoh@yahoo.com>
parents:
1746
diff
changeset
|
84 a->base = (struct frag *)malloc(sizeof(struct 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
|
85 if (a->base) { |
128 | 86 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
|
87 return a; |
8f9660c568b8
Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1978
diff
changeset
|
88 } |
8f9660c568b8
Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1978
diff
changeset
|
89 free(a); |
8f9660c568b8
Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1978
diff
changeset
|
90 a = NULL; |
128 | 91 } |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
92 if (!PyErr_Occurred()) |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
93 PyErr_NoMemory(); |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
94 return NULL; |
72 | 95 } |
96 | |
97 static void lfree(struct flist *a) | |
98 { | |
128 | 99 if (a) { |
100 free(a->base); | |
101 free(a); | |
102 } | |
72 | 103 } |
104 | |
105 static int lsize(struct flist *a) | |
106 { | |
107 return a->tail - a->head; | |
108 } | |
109 | |
110 /* move hunks in source that are less cut to dest, compensating | |
111 for changes in offset. the last hunk may be split if necessary. | |
112 */ | |
113 static int gather(struct flist *dest, struct flist *src, int cut, int offset) | |
114 { | |
115 struct frag *d = dest->tail, *s = src->head; | |
116 int postend, c, l; | |
117 | |
118 while (s != src->tail) { | |
119 if (s->start + offset >= cut) | |
82 | 120 break; /* we've gone far enough */ |
72 | 121 |
122 postend = offset + s->start + s->len; | |
123 if (postend <= cut) { | |
124 /* save this hunk */ | |
125 offset += s->start + s->len - s->end; | |
126 *d++ = *s++; | |
127 } | |
128 else { | |
129 /* break up this hunk */ | |
130 c = cut - offset; | |
131 if (s->end < c) | |
132 c = s->end; | |
133 l = cut - offset - s->start; | |
134 if (s->len < l) | |
135 l = s->len; | |
136 | |
137 offset += s->start + l - c; | |
138 | |
139 d->start = s->start; | |
140 d->end = c; | |
141 d->len = l; | |
142 d->data = s->data; | |
143 d++; | |
144 s->start = c; | |
145 s->len = s->len - l; | |
146 s->data = s->data + l; | |
147 | |
82 | 148 break; |
72 | 149 } |
150 } | |
151 | |
152 dest->tail = d; | |
153 src->head = s; | |
154 return offset; | |
155 } | |
156 | |
157 /* like gather, but with no output list */ | |
158 static int discard(struct flist *src, int cut, int offset) | |
159 { | |
160 struct frag *s = src->head; | |
161 int postend, c, l; | |
162 | |
163 while (s != src->tail) { | |
164 if (s->start + offset >= cut) | |
82 | 165 break; |
72 | 166 |
167 postend = offset + s->start + s->len; | |
168 if (postend <= cut) { | |
169 offset += s->start + s->len - s->end; | |
170 s++; | |
171 } | |
172 else { | |
173 c = cut - offset; | |
174 if (s->end < c) | |
175 c = s->end; | |
176 l = cut - offset - s->start; | |
177 if (s->len < l) | |
178 l = s->len; | |
179 | |
180 offset += s->start + l - c; | |
181 s->start = c; | |
182 s->len = s->len - l; | |
183 s->data = s->data + l; | |
184 | |
82 | 185 break; |
72 | 186 } |
187 } | |
188 | |
189 src->head = s; | |
190 return offset; | |
191 } | |
192 | |
193 /* combine hunk lists a and b, while adjusting b for offset changes in a/ | |
194 this deletes a and b and returns the resultant list. */ | |
195 static struct flist *combine(struct flist *a, struct flist *b) | |
196 { | |
128 | 197 struct flist *c = NULL; |
198 struct frag *bh, *ct; | |
72 | 199 int offset = 0, post; |
200 | |
128 | 201 if (a && b) |
202 c = lalloc((lsize(a) + lsize(b)) * 2); | |
203 | |
204 if (c) { | |
72 | 205 |
128 | 206 for (bh = b->head; bh != b->tail; bh++) { |
207 /* save old hunks */ | |
208 offset = gather(c, a, bh->start, offset); | |
72 | 209 |
128 | 210 /* discard replaced hunks */ |
211 post = discard(a, bh->end, offset); | |
72 | 212 |
128 | 213 /* insert new hunk */ |
214 ct = c->tail; | |
215 ct->start = bh->start - offset; | |
216 ct->end = bh->end - post; | |
217 ct->len = bh->len; | |
218 ct->data = bh->data; | |
219 c->tail++; | |
220 offset = post; | |
221 } | |
222 | |
223 /* hold on to tail from a */ | |
224 memcpy(c->tail, a->head, sizeof(struct frag) * lsize(a)); | |
225 c->tail += lsize(a); | |
72 | 226 } |
227 | |
228 lfree(a); | |
229 lfree(b); | |
230 return c; | |
231 } | |
232 | |
233 /* decode a binary patch into a hunk list */ | |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
234 static struct flist *decode(const char *bin, int len) |
72 | 235 { |
236 struct flist *l; | |
237 struct frag *lt; | |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
238 const char *data = bin + 12, *end = bin + len; |
384
a29decbf7475
mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents:
282
diff
changeset
|
239 char decode[12]; /* for dealing with alignment issues */ |
72 | 240 |
241 /* assume worst case size, we won't have many of these lists */ | |
242 l = lalloc(len / 12); | |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
243 if (!l) |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
244 return NULL; |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
245 |
72 | 246 lt = l->tail; |
247 | |
4358
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
248 while (data <= end) { |
384
a29decbf7475
mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents:
282
diff
changeset
|
249 memcpy(decode, bin, 12); |
a29decbf7475
mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents:
282
diff
changeset
|
250 lt->start = ntohl(*(uint32_t *)decode); |
a29decbf7475
mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents:
282
diff
changeset
|
251 lt->end = ntohl(*(uint32_t *)(decode + 4)); |
a29decbf7475
mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents:
282
diff
changeset
|
252 lt->len = ntohl(*(uint32_t *)(decode + 8)); |
4358
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
253 if (lt->start > lt->end) |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
254 break; /* sanity check */ |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
255 bin = data + lt->len; |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
256 if (bin < data) |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
257 break; /* big data + big (bogus) len can wrap around */ |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
258 lt->data = data; |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
259 data = bin + 12; |
72 | 260 lt++; |
261 } | |
262 | |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
263 if (bin != end) { |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
264 if (!PyErr_Occurred()) |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
265 PyErr_SetString(mpatch_Error, "patch cannot be decoded"); |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
266 lfree(l); |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
267 return NULL; |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
268 } |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
269 |
72 | 270 l->tail = lt; |
271 return l; | |
272 } | |
273 | |
274 /* calculate the size of resultant text */ | |
275 static int calcsize(int len, struct flist *l) | |
276 { | |
277 int outlen = 0, last = 0; | |
278 struct frag *f = l->head; | |
279 | |
280 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
|
281 if (f->start < last || f->end > len) { |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
282 if (!PyErr_Occurred()) |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
283 PyErr_SetString(mpatch_Error, |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
284 "invalid patch"); |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
285 return -1; |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
286 } |
72 | 287 outlen += f->start - last; |
288 last = f->end; | |
289 outlen += f->len; | |
290 f++; | |
291 } | |
292 | |
293 outlen += len - last; | |
294 return outlen; | |
295 } | |
296 | |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
297 static int apply(char *buf, const char *orig, int len, struct flist *l) |
72 | 298 { |
299 struct frag *f = l->head; | |
300 int last = 0; | |
301 char *p = buf; | |
302 | |
303 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
|
304 if (f->start < last || f->end > len) { |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
305 if (!PyErr_Occurred()) |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
306 PyErr_SetString(mpatch_Error, |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
307 "invalid patch"); |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
308 return 0; |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
309 } |
72 | 310 memcpy(p, orig + last, f->start - last); |
311 p += f->start - last; | |
312 memcpy(p, f->data, f->len); | |
313 last = f->end; | |
314 p += f->len; | |
315 f++; | |
316 } | |
317 memcpy(p, orig + last, len - last); | |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
318 return 1; |
72 | 319 } |
320 | |
321 /* recursively generate a patch of all bins between start and end */ | |
322 static struct flist *fold(PyObject *bins, int start, int end) | |
323 { | |
324 int len; | |
5459
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
325 Py_ssize_t blen; |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
326 const char *buffer; |
72 | 327 |
328 if (start + 1 == end) { | |
329 /* trivial case, output a decoded list */ | |
330 PyObject *tmp = PyList_GetItem(bins, start); | |
128 | 331 if (!tmp) |
332 return NULL; | |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
333 if (PyObject_AsCharBuffer(tmp, &buffer, &blen)) |
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
334 return NULL; |
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
335 return decode(buffer, blen); |
72 | 336 } |
337 | |
338 /* divide and conquer, memory management is elsewhere */ | |
339 len = (end - start) / 2; | |
340 return combine(fold(bins, start, start + len), | |
341 fold(bins, start + len, end)); | |
342 } | |
343 | |
344 static PyObject * | |
345 patches(PyObject *self, PyObject *args) | |
346 { | |
347 PyObject *text, *bins, *result; | |
348 struct flist *patch; | |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
349 const char *in; |
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
350 char *out; |
72 | 351 int len, outlen; |
5459
b0e5f44fdeb3
mpatch: Define Py_ssize_t for old pythons and use it instead of ssize_t.
Shun-ichi GOTO <shunichi.goto@gmail.com>
parents:
5444
diff
changeset
|
352 Py_ssize_t inlen; |
72 | 353 |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
354 if (!PyArg_ParseTuple(args, "OO:mpatch", &text, &bins)) |
72 | 355 return NULL; |
356 | |
357 len = PyList_Size(bins); | |
358 if (!len) { | |
359 /* nothing to do */ | |
360 Py_INCREF(text); | |
361 return text; | |
362 } | |
363 | |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
364 if (PyObject_AsCharBuffer(text, &in, &inlen)) |
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
365 return NULL; |
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
366 |
72 | 367 patch = fold(bins, 0, len); |
128 | 368 if (!patch) |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
369 return NULL; |
128 | 370 |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
371 outlen = calcsize(inlen, patch); |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
372 if (outlen < 0) { |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
373 result = NULL; |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
374 goto cleanup; |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
375 } |
72 | 376 result = PyString_FromStringAndSize(NULL, outlen); |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
377 if (!result) { |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
378 result = NULL; |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
379 goto cleanup; |
128 | 380 } |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
381 out = PyString_AsString(result); |
5444
a0952e4e52eb
mpatch: allow buffer objects for input
Matt Mackall <mpm@selenic.com>
parents:
4377
diff
changeset
|
382 if (!apply(out, in, inlen, patch)) { |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
383 Py_DECREF(result); |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
384 result = NULL; |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
385 } |
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
386 cleanup: |
72 | 387 lfree(patch); |
388 return result; | |
389 } | |
390 | |
2078
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
391 /* calculate size of a patched file directly */ |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
392 static PyObject * |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
393 patchedsize(PyObject *self, PyObject *args) |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
394 { |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
395 long orig, start, end, len, outlen = 0, last = 0; |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
396 int patchlen; |
4358
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
397 char *bin, *binend, *data; |
2078
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
398 char decode[12]; /* for dealing with alignment issues */ |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
399 |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
400 if (!PyArg_ParseTuple(args, "ls#", &orig, &bin, &patchlen)) |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
401 return NULL; |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
402 |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
403 binend = bin + patchlen; |
4358
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
404 data = bin + 12; |
2078
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
405 |
4358
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
406 while (data <= binend) { |
2078
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
407 memcpy(decode, bin, 12); |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
408 start = ntohl(*(uint32_t *)decode); |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
409 end = ntohl(*(uint32_t *)(decode + 4)); |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
410 len = ntohl(*(uint32_t *)(decode + 8)); |
4358
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
411 if (start > end) |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
412 break; /* sanity check */ |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
413 bin = data + len; |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
414 if (bin < data) |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
415 break; /* big data + big (bogus) len can wrap around */ |
11dc22eb8e8d
Fix segfaults when parsing bdiff hunks in mpatch.decode() and .patchedsize()
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3138
diff
changeset
|
416 data = bin + 12; |
2078
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
417 outlen += start - last; |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
418 last = end; |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
419 outlen += len; |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
420 } |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
421 |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
422 if (bin != binend) { |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
423 if (!PyErr_Occurred()) |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
424 PyErr_SetString(mpatch_Error, "patch cannot be decoded"); |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
425 return NULL; |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
426 } |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
427 |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
428 outlen += orig - last; |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
429 return Py_BuildValue("l", outlen); |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
430 } |
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
431 |
72 | 432 static PyMethodDef methods[] = { |
433 {"patches", patches, METH_VARARGS, "apply a series of patches\n"}, | |
2078
441ea218414e
Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents:
1978
diff
changeset
|
434 {"patchedsize", patchedsize, METH_VARARGS, "calculed patched size\n"}, |
72 | 435 {NULL, NULL} |
436 }; | |
437 | |
438 PyMODINIT_FUNC | |
439 initmpatch(void) | |
440 { | |
441 Py_InitModule3("mpatch", methods, mpatch_doc); | |
1722
681c5c211b92
catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
597
diff
changeset
|
442 mpatch_Error = PyErr_NewException("mpatch.mpatchError", NULL, NULL); |
72 | 443 } |
444 |