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 | struct mpatch_frag *base, *head, *tail; |
|
41 | struct mpatch_frag *base, *head, *tail; | |
42 | }; |
|
42 | }; | |
43 |
|
43 | |||
44 |
|
|
44 | struct mpatch_flist *lalloc(ssize_t size) | |
45 | { |
|
45 | { | |
46 | struct mpatch_flist *a = NULL; |
|
46 | struct mpatch_flist *a = NULL; | |
47 |
|
47 | |||
@@ -63,7 +63,7 b' static struct mpatch_flist *lalloc(ssize' | |||||
63 | return NULL; |
|
63 | return NULL; | |
64 | } |
|
64 | } | |
65 |
|
65 | |||
66 |
|
|
66 | void mpatch_lfree(struct mpatch_flist *a) | |
67 | { |
|
67 | { | |
68 | if (a) { |
|
68 | if (a) { | |
69 | free(a->base); |
|
69 | free(a->base); | |
@@ -202,7 +202,7 b' static struct mpatch_flist *combine(stru' | |||||
202 | } |
|
202 | } | |
203 |
|
203 | |||
204 | /* decode a binary patch into a hunk list */ |
|
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 | struct mpatch_flist *l; |
|
207 | struct mpatch_flist *l; | |
208 | struct mpatch_frag *lt; |
|
208 | struct mpatch_frag *lt; | |
@@ -238,7 +238,7 b' static struct mpatch_flist *mpatch_decod' | |||||
238 | } |
|
238 | } | |
239 |
|
239 | |||
240 | /* calculate the size of resultant text */ |
|
240 | /* calculate the size of resultant text */ | |
241 |
|
|
241 | ssize_t mpatch_calcsize(ssize_t len, struct mpatch_flist *l) | |
242 | { |
|
242 | { | |
243 | ssize_t outlen = 0, last = 0; |
|
243 | ssize_t outlen = 0, last = 0; | |
244 | struct mpatch_frag *f = l->head; |
|
244 | struct mpatch_frag *f = l->head; | |
@@ -260,7 +260,7 b' static ssize_t mpatch_calcsize(ssize_t l' | |||||
260 | return outlen; |
|
260 | return outlen; | |
261 | } |
|
261 | } | |
262 |
|
262 | |||
263 |
|
|
263 | int mpatch_apply(char *buf, const char *orig, ssize_t len, | |
264 | struct mpatch_flist *l) |
|
264 | struct mpatch_flist *l) | |
265 | { |
|
265 | { | |
266 | struct mpatch_frag *f = l->head; |
|
266 | struct mpatch_frag *f = l->head; | |
@@ -286,7 +286,7 b' static int mpatch_apply(char *buf, const' | |||||
286 | } |
|
286 | } | |
287 |
|
287 | |||
288 | /* recursively generate a patch of all bins between start and end */ |
|
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 | ssize_t end) |
|
290 | ssize_t end) | |
291 | { |
|
291 | { | |
292 | ssize_t len, blen; |
|
292 | ssize_t len, blen; | |
@@ -308,121 +308,3 b' static struct mpatch_flist *mpatch_fold(' | |||||
308 | mpatch_fold(bins, start + len, end)); |
|
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 | #include "util.h" |
|
28 | #include "util.h" | |
29 | #include "bitmanipulation.h" |
|
29 | #include "bitmanipulation.h" | |
30 | #include "compat.h" |
|
30 | #include "compat.h" | |
|
31 | #include "mpatch.h" | |||
31 |
|
32 | |||
32 | static char mpatch_doc[] = "Efficient binary patching."; |
|
33 | static char mpatch_doc[] = "Efficient binary patching."; | |
33 | static PyObject *mpatch_Error; |
|
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 | static PyObject * |
|
36 | static PyObject * | |
312 | patches(PyObject *self, PyObject *args) |
|
37 | patches(PyObject *self, PyObject *args) | |
313 | { |
|
38 | { |
@@ -561,7 +561,8 b' extmodules = [' | |||||
561 | depends=common_depends + ['mercurial/bdiff.h']), |
|
561 | depends=common_depends + ['mercurial/bdiff.h']), | |
562 | Extension('mercurial.diffhelpers', ['mercurial/diffhelpers.c'], |
|
562 | Extension('mercurial.diffhelpers', ['mercurial/diffhelpers.c'], | |
563 | depends=common_depends), |
|
563 | depends=common_depends), | |
564 |
Extension('mercurial.mpatch', ['mercurial/mpatch.c' |
|
564 | Extension('mercurial.mpatch', ['mercurial/mpatch.c', | |
|
565 | 'mercurial/mpatch_module.c'], | |||
565 | depends=common_depends), |
|
566 | depends=common_depends), | |
566 | Extension('mercurial.parsers', ['mercurial/dirs.c', |
|
567 | Extension('mercurial.parsers', ['mercurial/dirs.c', | |
567 | 'mercurial/manifest.c', |
|
568 | 'mercurial/manifest.c', |
General Comments 0
You need to be logged in to leave comments.
Login now