Show More
@@ -0,0 +1,20 b'' | |||
|
1 | #ifndef _HG_MPATCH_H_ | |
|
2 | #define _HG_MPATCH_H_ | |
|
3 | ||
|
4 | struct mpatch_frag { | |
|
5 | int start, end, len; | |
|
6 | const char *data; | |
|
7 | }; | |
|
8 | ||
|
9 | struct mpatch_flist { | |
|
10 | struct mpatch_frag *base, *head, *tail; | |
|
11 | }; | |
|
12 | ||
|
13 | int mpatch_decode(const char *bin, ssize_t len, struct mpatch_flist** res); | |
|
14 | ssize_t mpatch_calcsize(ssize_t len, struct mpatch_flist *l); | |
|
15 | void mpatch_lfree(struct mpatch_flist *a); | |
|
16 | int mpatch_apply(char *buf, const char *orig, ssize_t len, | |
|
17 | struct mpatch_flist *l); | |
|
18 | struct mpatch_flist *mpatch_fold(void *bins, ssize_t start, ssize_t end); | |
|
19 | ||
|
20 | #endif |
@@ -41,7 +41,7 b' struct mpatch_flist {' | |||
|
41 | 41 | struct mpatch_frag *base, *head, *tail; |
|
42 | 42 | }; |
|
43 | 43 | |
|
44 |
|
|
|
44 | struct mpatch_flist *lalloc(ssize_t size) | |
|
45 | 45 | { |
|
46 | 46 | struct mpatch_flist *a = NULL; |
|
47 | 47 | |
@@ -63,7 +63,7 b' static struct mpatch_flist *lalloc(ssize' | |||
|
63 | 63 | return NULL; |
|
64 | 64 | } |
|
65 | 65 | |
|
66 |
|
|
|
66 | void mpatch_lfree(struct mpatch_flist *a) | |
|
67 | 67 | { |
|
68 | 68 | if (a) { |
|
69 | 69 | free(a->base); |
@@ -202,7 +202,7 b' static struct mpatch_flist *combine(stru' | |||
|
202 | 202 | } |
|
203 | 203 | |
|
204 | 204 | /* decode a binary patch into a hunk list */ |
|
205 |
|
|
|
205 | struct mpatch_flist *mpatch_decode(const char *bin, ssize_t len) | |
|
206 | 206 | { |
|
207 | 207 | struct mpatch_flist *l; |
|
208 | 208 | struct mpatch_frag *lt; |
@@ -238,7 +238,7 b' static struct mpatch_flist *mpatch_decod' | |||
|
238 | 238 | } |
|
239 | 239 | |
|
240 | 240 | /* calculate the size of resultant text */ |
|
241 |
|
|
|
241 | ssize_t mpatch_calcsize(ssize_t len, struct mpatch_flist *l) | |
|
242 | 242 | { |
|
243 | 243 | ssize_t outlen = 0, last = 0; |
|
244 | 244 | struct mpatch_frag *f = l->head; |
@@ -260,7 +260,7 b' static ssize_t mpatch_calcsize(ssize_t l' | |||
|
260 | 260 | return outlen; |
|
261 | 261 | } |
|
262 | 262 | |
|
263 |
|
|
|
263 | int mpatch_apply(char *buf, const char *orig, ssize_t len, | |
|
264 | 264 | struct mpatch_flist *l) |
|
265 | 265 | { |
|
266 | 266 | struct mpatch_frag *f = l->head; |
@@ -286,7 +286,7 b' static int mpatch_apply(char *buf, const' | |||
|
286 | 286 | } |
|
287 | 287 | |
|
288 | 288 | /* recursively generate a patch of all bins between start and end */ |
|
289 |
|
|
|
289 | struct mpatch_flist *mpatch_fold(PyObject *bins, ssize_t start, | |
|
290 | 290 | ssize_t end) |
|
291 | 291 | { |
|
292 | 292 | ssize_t len, blen; |
@@ -308,121 +308,3 b' static struct mpatch_flist *mpatch_fold(' | |||
|
308 | 308 | mpatch_fold(bins, start + len, end)); |
|
309 | 309 | } |
|
310 | 310 | |
|
311 | static PyObject * | |
|
312 | patches(PyObject *self, PyObject *args) | |
|
313 | { | |
|
314 | PyObject *text, *bins, *result; | |
|
315 | struct mpatch_flist *patch; | |
|
316 | const char *in; | |
|
317 | char *out; | |
|
318 | Py_ssize_t len, outlen, inlen; | |
|
319 | ||
|
320 | if (!PyArg_ParseTuple(args, "OO:mpatch", &text, &bins)) | |
|
321 | return NULL; | |
|
322 | ||
|
323 | len = PyList_Size(bins); | |
|
324 | if (!len) { | |
|
325 | /* nothing to do */ | |
|
326 | Py_INCREF(text); | |
|
327 | return text; | |
|
328 | } | |
|
329 | ||
|
330 | if (PyObject_AsCharBuffer(text, &in, &inlen)) | |
|
331 | return NULL; | |
|
332 | ||
|
333 | patch = mpatch_fold(bins, 0, len); | |
|
334 | if (!patch) | |
|
335 | return NULL; | |
|
336 | ||
|
337 | outlen = mpatch_calcsize(inlen, patch); | |
|
338 | if (outlen < 0) { | |
|
339 | result = NULL; | |
|
340 | goto cleanup; | |
|
341 | } | |
|
342 | result = PyBytes_FromStringAndSize(NULL, outlen); | |
|
343 | if (!result) { | |
|
344 | result = NULL; | |
|
345 | goto cleanup; | |
|
346 | } | |
|
347 | out = PyBytes_AsString(result); | |
|
348 | if (!mpatch_apply(out, in, inlen, patch)) { | |
|
349 | Py_DECREF(result); | |
|
350 | result = NULL; | |
|
351 | } | |
|
352 | cleanup: | |
|
353 | mpatch_lfree(patch); | |
|
354 | return result; | |
|
355 | } | |
|
356 | ||
|
357 | /* calculate size of a patched file directly */ | |
|
358 | static PyObject * | |
|
359 | patchedsize(PyObject *self, PyObject *args) | |
|
360 | { | |
|
361 | long orig, start, end, len, outlen = 0, last = 0, pos = 0; | |
|
362 | Py_ssize_t patchlen; | |
|
363 | char *bin; | |
|
364 | ||
|
365 | if (!PyArg_ParseTuple(args, "ls#", &orig, &bin, &patchlen)) | |
|
366 | return NULL; | |
|
367 | ||
|
368 | while (pos >= 0 && pos < patchlen) { | |
|
369 | start = getbe32(bin + pos); | |
|
370 | end = getbe32(bin + pos + 4); | |
|
371 | len = getbe32(bin + pos + 8); | |
|
372 | if (start > end) | |
|
373 | break; /* sanity check */ | |
|
374 | pos += 12 + len; | |
|
375 | outlen += start - last; | |
|
376 | last = end; | |
|
377 | outlen += len; | |
|
378 | } | |
|
379 | ||
|
380 | if (pos != patchlen) { | |
|
381 | if (!PyErr_Occurred()) | |
|
382 | PyErr_SetString(mpatch_Error, "patch cannot be decoded"); | |
|
383 | return NULL; | |
|
384 | } | |
|
385 | ||
|
386 | outlen += orig - last; | |
|
387 | return Py_BuildValue("l", outlen); | |
|
388 | } | |
|
389 | ||
|
390 | static PyMethodDef methods[] = { | |
|
391 | {"patches", patches, METH_VARARGS, "apply a series of patches\n"}, | |
|
392 | {"patchedsize", patchedsize, METH_VARARGS, "calculed patched size\n"}, | |
|
393 | {NULL, NULL} | |
|
394 | }; | |
|
395 | ||
|
396 | #ifdef IS_PY3K | |
|
397 | static struct PyModuleDef mpatch_module = { | |
|
398 | PyModuleDef_HEAD_INIT, | |
|
399 | "mpatch", | |
|
400 | mpatch_doc, | |
|
401 | -1, | |
|
402 | methods | |
|
403 | }; | |
|
404 | ||
|
405 | PyMODINIT_FUNC PyInit_mpatch(void) | |
|
406 | { | |
|
407 | PyObject *m; | |
|
408 | ||
|
409 | m = PyModule_Create(&mpatch_module); | |
|
410 | if (m == NULL) | |
|
411 | return NULL; | |
|
412 | ||
|
413 | mpatch_Error = PyErr_NewException("mercurial.mpatch.mpatchError", | |
|
414 | NULL, NULL); | |
|
415 | Py_INCREF(mpatch_Error); | |
|
416 | PyModule_AddObject(m, "mpatchError", mpatch_Error); | |
|
417 | ||
|
418 | return m; | |
|
419 | } | |
|
420 | #else | |
|
421 | PyMODINIT_FUNC | |
|
422 | initmpatch(void) | |
|
423 | { | |
|
424 | Py_InitModule3("mpatch", methods, mpatch_doc); | |
|
425 | mpatch_Error = PyErr_NewException("mercurial.mpatch.mpatchError", | |
|
426 | NULL, NULL); | |
|
427 | } | |
|
428 | #endif |
@@ -28,286 +28,11 b'' | |||
|
28 | 28 | #include "util.h" |
|
29 | 29 | #include "bitmanipulation.h" |
|
30 | 30 | #include "compat.h" |
|
31 | #include "mpatch.h" | |
|
31 | 32 | |
|
32 | 33 | static char mpatch_doc[] = "Efficient binary patching."; |
|
33 | 34 | static PyObject *mpatch_Error; |
|
34 | 35 | |
|
35 | struct mpatch_frag { | |
|
36 | int start, end, len; | |
|
37 | const char *data; | |
|
38 | }; | |
|
39 | ||
|
40 | struct mpatch_flist { | |
|
41 | struct mpatch_frag *base, *head, *tail; | |
|
42 | }; | |
|
43 | ||
|
44 | static struct mpatch_flist *lalloc(ssize_t size) | |
|
45 | { | |
|
46 | struct mpatch_flist *a = NULL; | |
|
47 | ||
|
48 | if (size < 1) | |
|
49 | size = 1; | |
|
50 | ||
|
51 | a = (struct mpatch_flist *)malloc(sizeof(struct mpatch_flist)); | |
|
52 | if (a) { | |
|
53 | a->base = (struct mpatch_frag *)malloc(sizeof(struct mpatch_frag) * size); | |
|
54 | if (a->base) { | |
|
55 | a->head = a->tail = a->base; | |
|
56 | return a; | |
|
57 | } | |
|
58 | free(a); | |
|
59 | a = NULL; | |
|
60 | } | |
|
61 | if (!PyErr_Occurred()) | |
|
62 | PyErr_NoMemory(); | |
|
63 | return NULL; | |
|
64 | } | |
|
65 | ||
|
66 | static void mpatch_lfree(struct mpatch_flist *a) | |
|
67 | { | |
|
68 | if (a) { | |
|
69 | free(a->base); | |
|
70 | free(a); | |
|
71 | } | |
|
72 | } | |
|
73 | ||
|
74 | static ssize_t lsize(struct mpatch_flist *a) | |
|
75 | { | |
|
76 | return a->tail - a->head; | |
|
77 | } | |
|
78 | ||
|
79 | /* move hunks in source that are less cut to dest, compensating | |
|
80 | for changes in offset. the last hunk may be split if necessary. | |
|
81 | */ | |
|
82 | static int gather(struct mpatch_flist *dest, struct mpatch_flist *src, int cut, | |
|
83 | int offset) | |
|
84 | { | |
|
85 | struct mpatch_frag *d = dest->tail, *s = src->head; | |
|
86 | int postend, c, l; | |
|
87 | ||
|
88 | while (s != src->tail) { | |
|
89 | if (s->start + offset >= cut) | |
|
90 | break; /* we've gone far enough */ | |
|
91 | ||
|
92 | postend = offset + s->start + s->len; | |
|
93 | if (postend <= cut) { | |
|
94 | /* save this hunk */ | |
|
95 | offset += s->start + s->len - s->end; | |
|
96 | *d++ = *s++; | |
|
97 | } | |
|
98 | else { | |
|
99 | /* break up this hunk */ | |
|
100 | c = cut - offset; | |
|
101 | if (s->end < c) | |
|
102 | c = s->end; | |
|
103 | l = cut - offset - s->start; | |
|
104 | if (s->len < l) | |
|
105 | l = s->len; | |
|
106 | ||
|
107 | offset += s->start + l - c; | |
|
108 | ||
|
109 | d->start = s->start; | |
|
110 | d->end = c; | |
|
111 | d->len = l; | |
|
112 | d->data = s->data; | |
|
113 | d++; | |
|
114 | s->start = c; | |
|
115 | s->len = s->len - l; | |
|
116 | s->data = s->data + l; | |
|
117 | ||
|
118 | break; | |
|
119 | } | |
|
120 | } | |
|
121 | ||
|
122 | dest->tail = d; | |
|
123 | src->head = s; | |
|
124 | return offset; | |
|
125 | } | |
|
126 | ||
|
127 | /* like gather, but with no output list */ | |
|
128 | static int discard(struct mpatch_flist *src, int cut, int offset) | |
|
129 | { | |
|
130 | struct mpatch_frag *s = src->head; | |
|
131 | int postend, c, l; | |
|
132 | ||
|
133 | while (s != src->tail) { | |
|
134 | if (s->start + offset >= cut) | |
|
135 | break; | |
|
136 | ||
|
137 | postend = offset + s->start + s->len; | |
|
138 | if (postend <= cut) { | |
|
139 | offset += s->start + s->len - s->end; | |
|
140 | s++; | |
|
141 | } | |
|
142 | else { | |
|
143 | c = cut - offset; | |
|
144 | if (s->end < c) | |
|
145 | c = s->end; | |
|
146 | l = cut - offset - s->start; | |
|
147 | if (s->len < l) | |
|
148 | l = s->len; | |
|
149 | ||
|
150 | offset += s->start + l - c; | |
|
151 | s->start = c; | |
|
152 | s->len = s->len - l; | |
|
153 | s->data = s->data + l; | |
|
154 | ||
|
155 | break; | |
|
156 | } | |
|
157 | } | |
|
158 | ||
|
159 | src->head = s; | |
|
160 | return offset; | |
|
161 | } | |
|
162 | ||
|
163 | /* combine hunk lists a and b, while adjusting b for offset changes in a/ | |
|
164 | this deletes a and b and returns the resultant list. */ | |
|
165 | static struct mpatch_flist *combine(struct mpatch_flist *a, | |
|
166 | struct mpatch_flist *b) | |
|
167 | { | |
|
168 | struct mpatch_flist *c = NULL; | |
|
169 | struct mpatch_frag *bh, *ct; | |
|
170 | int offset = 0, post; | |
|
171 | ||
|
172 | if (a && b) | |
|
173 | c = lalloc((lsize(a) + lsize(b)) * 2); | |
|
174 | ||
|
175 | if (c) { | |
|
176 | ||
|
177 | for (bh = b->head; bh != b->tail; bh++) { | |
|
178 | /* save old hunks */ | |
|
179 | offset = gather(c, a, bh->start, offset); | |
|
180 | ||
|
181 | /* discard replaced hunks */ | |
|
182 | post = discard(a, bh->end, offset); | |
|
183 | ||
|
184 | /* insert new hunk */ | |
|
185 | ct = c->tail; | |
|
186 | ct->start = bh->start - offset; | |
|
187 | ct->end = bh->end - post; | |
|
188 | ct->len = bh->len; | |
|
189 | ct->data = bh->data; | |
|
190 | c->tail++; | |
|
191 | offset = post; | |
|
192 | } | |
|
193 | ||
|
194 | /* hold on to tail from a */ | |
|
195 | memcpy(c->tail, a->head, sizeof(struct mpatch_frag) * lsize(a)); | |
|
196 | c->tail += lsize(a); | |
|
197 | } | |
|
198 | ||
|
199 | mpatch_lfree(a); | |
|
200 | mpatch_lfree(b); | |
|
201 | return c; | |
|
202 | } | |
|
203 | ||
|
204 | /* decode a binary patch into a hunk list */ | |
|
205 | static struct mpatch_flist *mpatch_decode(const char *bin, ssize_t len) | |
|
206 | { | |
|
207 | struct mpatch_flist *l; | |
|
208 | struct mpatch_frag *lt; | |
|
209 | int pos = 0; | |
|
210 | ||
|
211 | /* assume worst case size, we won't have many of these lists */ | |
|
212 | l = lalloc(len / 12 + 1); | |
|
213 | if (!l) | |
|
214 | return NULL; | |
|
215 | ||
|
216 | lt = l->tail; | |
|
217 | ||
|
218 | while (pos >= 0 && pos < len) { | |
|
219 | lt->start = getbe32(bin + pos); | |
|
220 | lt->end = getbe32(bin + pos + 4); | |
|
221 | lt->len = getbe32(bin + pos + 8); | |
|
222 | lt->data = bin + pos + 12; | |
|
223 | pos += 12 + lt->len; | |
|
224 | if (lt->start > lt->end || lt->len < 0) | |
|
225 | break; /* sanity check */ | |
|
226 | lt++; | |
|
227 | } | |
|
228 | ||
|
229 | if (pos != len) { | |
|
230 | if (!PyErr_Occurred()) | |
|
231 | PyErr_SetString(mpatch_Error, "patch cannot be decoded"); | |
|
232 | mpatch_lfree(l); | |
|
233 | return NULL; | |
|
234 | } | |
|
235 | ||
|
236 | l->tail = lt; | |
|
237 | return l; | |
|
238 | } | |
|
239 | ||
|
240 | /* calculate the size of resultant text */ | |
|
241 | static ssize_t mpatch_calcsize(ssize_t len, struct mpatch_flist *l) | |
|
242 | { | |
|
243 | ssize_t outlen = 0, last = 0; | |
|
244 | struct mpatch_frag *f = l->head; | |
|
245 | ||
|
246 | while (f != l->tail) { | |
|
247 | if (f->start < last || f->end > len) { | |
|
248 | if (!PyErr_Occurred()) | |
|
249 | PyErr_SetString(mpatch_Error, | |
|
250 | "invalid patch"); | |
|
251 | return -1; | |
|
252 | } | |
|
253 | outlen += f->start - last; | |
|
254 | last = f->end; | |
|
255 | outlen += f->len; | |
|
256 | f++; | |
|
257 | } | |
|
258 | ||
|
259 | outlen += len - last; | |
|
260 | return outlen; | |
|
261 | } | |
|
262 | ||
|
263 | static int mpatch_apply(char *buf, const char *orig, ssize_t len, | |
|
264 | struct mpatch_flist *l) | |
|
265 | { | |
|
266 | struct mpatch_frag *f = l->head; | |
|
267 | int last = 0; | |
|
268 | char *p = buf; | |
|
269 | ||
|
270 | while (f != l->tail) { | |
|
271 | if (f->start < last || f->end > len) { | |
|
272 | if (!PyErr_Occurred()) | |
|
273 | PyErr_SetString(mpatch_Error, | |
|
274 | "invalid patch"); | |
|
275 | return 0; | |
|
276 | } | |
|
277 | memcpy(p, orig + last, f->start - last); | |
|
278 | p += f->start - last; | |
|
279 | memcpy(p, f->data, f->len); | |
|
280 | last = f->end; | |
|
281 | p += f->len; | |
|
282 | f++; | |
|
283 | } | |
|
284 | memcpy(p, orig + last, len - last); | |
|
285 | return 1; | |
|
286 | } | |
|
287 | ||
|
288 | /* recursively generate a patch of all bins between start and end */ | |
|
289 | static struct mpatch_flist *mpatch_fold(PyObject *bins, ssize_t start, | |
|
290 | ssize_t end) | |
|
291 | { | |
|
292 | ssize_t len, blen; | |
|
293 | const char *buffer; | |
|
294 | ||
|
295 | if (start + 1 == end) { | |
|
296 | /* trivial case, output a decoded list */ | |
|
297 | PyObject *tmp = PyList_GetItem(bins, start); | |
|
298 | if (!tmp) | |
|
299 | return NULL; | |
|
300 | if (PyObject_AsCharBuffer(tmp, &buffer, &blen)) | |
|
301 | return NULL; | |
|
302 | return mpatch_decode(buffer, blen); | |
|
303 | } | |
|
304 | ||
|
305 | /* divide and conquer, memory management is elsewhere */ | |
|
306 | len = (end - start) / 2; | |
|
307 | return combine(mpatch_fold(bins, start, start + len), | |
|
308 | mpatch_fold(bins, start + len, end)); | |
|
309 | } | |
|
310 | ||
|
311 | 36 | static PyObject * |
|
312 | 37 | patches(PyObject *self, PyObject *args) |
|
313 | 38 | { |
@@ -561,7 +561,8 b' extmodules = [' | |||
|
561 | 561 | depends=common_depends + ['mercurial/bdiff.h']), |
|
562 | 562 | Extension('mercurial.diffhelpers', ['mercurial/diffhelpers.c'], |
|
563 | 563 | depends=common_depends), |
|
564 |
Extension('mercurial.mpatch', ['mercurial/mpatch.c' |
|
|
564 | Extension('mercurial.mpatch', ['mercurial/mpatch.c', | |
|
565 | 'mercurial/mpatch_module.c'], | |
|
565 | 566 | depends=common_depends), |
|
566 | 567 | Extension('mercurial.parsers', ['mercurial/dirs.c', |
|
567 | 568 | 'mercurial/manifest.c', |
General Comments 0
You need to be logged in to leave comments.
Login now