##// END OF EJS Templates
Fix array overflow bug in bdiff...
"Wallace, Eric S" -
r827:a61728b5 default
parent child Browse files
Show More
@@ -1,349 +1,350
1 1 /*
2 2 bdiff.c - efficient binary diff extension for Mercurial
3 3
4 4 Copyright 2005 Matt Mackall <mpm@selenic.com>
5 5
6 6 This software may be used and distributed according to the terms of
7 7 the GNU General Public License, incorporated herein by reference.
8 8
9 9 Based roughly on Python difflib
10 10 */
11 11
12 12 #include <Python.h>
13 13 #include <stdlib.h>
14 14 #include <string.h>
15 15 #ifdef _WIN32
16 16 #ifdef _MSC_VER
17 17 #define inline __inline
18 18 typedef unsigned long uint32_t;
19 19 #else
20 20 #include <stdint.h>
21 21 #endif
22 22 static uint32_t htonl(uint32_t x)
23 23 {
24 24 return ((x & 0x000000ffUL) << 24) |
25 25 ((x & 0x0000ff00UL) << 8) |
26 26 ((x & 0x00ff0000UL) >> 8) |
27 27 ((x & 0xff000000UL) >> 24);
28 28 }
29 29 #else
30 30 #include <sys/types.h>
31 31 #include <arpa/inet.h>
32 32 #endif
33 33
34 34 struct line {
35 35 int h, len, n, e;
36 36 const char *l;
37 37 };
38 38
39 39 struct pos {
40 40 int pos, len;
41 41 };
42 42
43 43 struct hunk {
44 44 int a1, a2, b1, b2;
45 45 };
46 46
47 47 struct hunklist {
48 48 struct hunk *base, *head;
49 49 };
50 50
51 51 static __inline uint32_t rol32(uint32_t word, unsigned int shift)
52 52 {
53 53 return (word << shift) | (word >> (32 - shift));
54 54 }
55 55
56 56 int splitlines(const char *a, int len, struct line **lr)
57 57 {
58 58 int h, i;
59 59 const char *p, *b = a;
60 60 struct line *l;
61 61
62 62 /* count the lines */
63 63 i = 1; /* extra line for sentinel */
64 64 for (p = a; p < a + len; p++)
65 65 if (*p == '\n' || p == a + len - 1)
66 66 i++;
67 67
68 68 *lr = l = malloc(sizeof(struct line) * i);
69 69 if (!l)
70 70 return -1;
71 71
72 72 /* build the line array and calculate hashes */
73 73 h = 0;
74 74 for (p = a; p < a + len; p++) {
75 75 h = *p + rol32(h, 7); /* a simple hash from GNU diff */
76 76 if (*p == '\n' || p == a + len - 1) {
77 77 l->len = p - b + 1;
78 78 l->h = h * l->len;
79 79 l->l = b;
80 80 l->n = -1;
81 81 l++;
82 82 b = p + 1;
83 83 h = 0;
84 84 }
85 85 }
86 86
87 87 /* set up a sentinel */
88 88 l->h = l->len = 0;
89 89 l->l = a + len;
90 90 return i - 1;
91 91 }
92 92
93 93 int inline cmp(struct line *a, struct line *b)
94 94 {
95 95 return a->h != b->h || a->len != b->len || memcmp(a->l, b->l, a->len);
96 96 }
97 97
98 98 static int equatelines(struct line *a, int an, struct line *b, int bn)
99 99 {
100 100 int i, j, buckets = 1, t;
101 101 struct pos *h;
102 102
103 103 /* build a hash table of the next highest power of 2 */
104 104 while (buckets < bn + 1)
105 105 buckets *= 2;
106 106
107 107 h = malloc(buckets * sizeof(struct pos));
108 108 buckets = buckets - 1;
109 109 if (!h)
110 110 return 0;
111 111
112 112 /* clear the hash table */
113 113 for (i = 0; i <= buckets; i++) {
114 114 h[i].pos = -1;
115 115 h[i].len = 0;
116 116 }
117 117
118 118 /* add lines to the hash table chains */
119 119 for (i = bn - 1; i >= 0; i--) {
120 120 /* find the equivalence class */
121 121 for (j = b[i].h & buckets; h[j].pos != -1;
122 122 j = (j + 1) & buckets)
123 123 if (!cmp(b + i, b + h[j].pos))
124 124 break;
125 125
126 126 /* add to the head of the equivalence class */
127 127 b[i].n = h[j].pos;
128 128 b[i].e = j;
129 129 h[j].pos = i;
130 130 h[j].len++; /* keep track of popularity */
131 131 }
132 132
133 133 /* compute popularity threshold */
134 134 t = (bn >= 200) ? bn / 100 : bn + 1;
135 135
136 136 /* match items in a to their equivalence class in b */
137 137 for (i = 0; i < an; i++) {
138 138 /* find the equivalence class */
139 139 for (j = a[i].h & buckets; h[j].pos != -1;
140 140 j = (j + 1) & buckets)
141 141 if (!cmp(a + i, b + h[j].pos))
142 142 break;
143 143
144 144 a[i].e = j; /* use equivalence class for quick compare */
145 145 if(h[j].len <= t)
146 146 a[i].n = h[j].pos; /* point to head of match list */
147 147 else
148 148 a[i].n = -1; /* too popular */
149 149 }
150 150
151 151 /* discard hash tables */
152 152 free(h);
153 153 return 1;
154 154 }
155 155
156 156 static int longest_match(struct line *a, struct line *b, struct pos *pos,
157 157 int a1, int a2, int b1, int b2, int *omi, int *omj)
158 158 {
159 159 int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k;
160 160
161 161 for (i = a1; i < a2; i++) {
162 162 /* skip things before the current block */
163 163 for (j = a[i].n; j != -1 && j < b1; j = b[j].n)
164 164 ;
165 165
166 166 /* loop through all lines match a[i] in b */
167 167 for (; j != -1 && j < b2; j = b[j].n) {
168 168 /* does this extend an earlier match? */
169 169 if (i > a1 && j > b1 && pos[j - 1].pos == i - 1)
170 170 k = pos[j - 1].len + 1;
171 171 else
172 172 k = 1;
173 173 pos[j].pos = i;
174 174 pos[j].len = k;
175 175
176 176 /* best match so far? */
177 177 if (k > mk) {
178 178 mi = i;
179 179 mj = j;
180 180 mk = k;
181 181 }
182 182 }
183 183 }
184 184
185 185 if (mk) {
186 186 mi = mi - mk + 1;
187 187 mj = mj - mk + 1;
188 188 }
189 189
190 190 /* expand match to include neighboring popular lines */
191 191 while (mi - mb > a1 && mj - mb > b1 &&
192 192 a[mi - mb - 1].e == b[mj - mb - 1].e)
193 193 mb++;
194 194 while (mi + mk < a2 && mj + mk < b2 &&
195 195 a[mi + mk].e == b[mj + mk].e)
196 196 mk++;
197 197
198 198 *omi = mi - mb;
199 199 *omj = mj - mb;
200 200 return mk + mb;
201 201 }
202 202
203 203 static void recurse(struct line *a, struct line *b, struct pos *pos,
204 204 int a1, int a2, int b1, int b2, struct hunklist *l)
205 205 {
206 206 int i, j, k;
207 207
208 208 /* find the longest match in this chunk */
209 209 k = longest_match(a, b, pos, a1, a2, b1, b2, &i, &j);
210 210 if (!k)
211 211 return;
212 212
213 213 /* and recurse on the remaining chunks on either side */
214 214 recurse(a, b, pos, a1, i, b1, j, l);
215 215 l->head->a1 = i;
216 216 l->head->a2 = i + k;
217 217 l->head->b1 = j;
218 218 l->head->b2 = j + k;
219 219 l->head++;
220 220 recurse(a, b, pos, i + k, a2, j + k, b2, l);
221 221 }
222 222
223 223 static struct hunklist diff(struct line *a, int an, struct line *b, int bn)
224 224 {
225 225 struct hunklist l;
226 226 struct pos *pos;
227 227 int t;
228 228
229 229 /* allocate and fill arrays */
230 230 t = equatelines(a, an, b, bn);
231 231 pos = calloc(bn, sizeof(struct pos));
232 l.head = l.base = malloc(sizeof(struct hunk) * ((an + bn) / 4 + 2));
232 /* we can't have more matches than lines in the shorter file */
233 l.head = l.base = malloc(sizeof(struct hunk) * ((an<bn ? an:bn) + 1));
233 234
234 235 if (pos && l.base && t) {
235 236 /* generate the matching block list */
236 237 recurse(a, b, pos, 0, an, 0, bn, &l);
237 238 l.head->a1 = an;
238 239 l.head->b1 = bn;
239 240 l.head++;
240 241 }
241 242
242 243 free(pos);
243 244 return l;
244 245 }
245 246
246 247 static PyObject *blocks(PyObject *self, PyObject *args)
247 248 {
248 249 PyObject *sa, *sb, *rl = NULL, *m;
249 250 struct line *a, *b;
250 251 struct hunklist l;
251 252 struct hunk *h;
252 253 int an, bn, pos = 0;
253 254
254 255 if (!PyArg_ParseTuple(args, "SS:bdiff", &sa, &sb))
255 256 return NULL;
256 257
257 258 an = splitlines(PyString_AsString(sa), PyString_Size(sa), &a);
258 259 bn = splitlines(PyString_AsString(sb), PyString_Size(sb), &b);
259 260 if (!a || !b)
260 261 goto nomem;
261 262
262 263 l = diff(a, an, b, bn);
263 264 rl = PyList_New(l.head - l.base);
264 265 if (!l.head || !rl)
265 266 goto nomem;
266 267
267 268 for(h = l.base; h != l.head; h++) {
268 269 m = Py_BuildValue("iiii", h->a1, h->a2, h->b1, h->b2);
269 270 PyList_SetItem(rl, pos, m);
270 271 pos++;
271 272 }
272 273
273 274 nomem:
274 275 free(a);
275 276 free(b);
276 277 free(l.base);
277 278 return rl ? rl : PyErr_NoMemory();
278 279 }
279 280
280 281 static PyObject *bdiff(PyObject *self, PyObject *args)
281 282 {
282 283 PyObject *sa, *sb, *result = NULL;
283 284 struct line *al, *bl;
284 285 struct hunklist l;
285 286 struct hunk *h;
286 287 char encode[12], *rb;
287 288 int an, bn, len = 0, la = 0, lb = 0;
288 289
289 290 if (!PyArg_ParseTuple(args, "SS:bdiff", &sa, &sb))
290 291 return NULL;
291 292
292 293 an = splitlines(PyString_AsString(sa), PyString_Size(sa), &al);
293 294 bn = splitlines(PyString_AsString(sb), PyString_Size(sb), &bl);
294 295 if (!al || !bl)
295 296 goto nomem;
296 297
297 298 l = diff(al, an, bl, bn);
298 299 if (!l.head)
299 300 goto nomem;
300 301
301 302 /* calculate length of output */
302 303 for(h = l.base; h != l.head; h++) {
303 304 if (h->a1 != la || h->b1 != lb)
304 305 len += 12 + bl[h->b1].l - bl[lb].l;
305 306 la = h->a2;
306 307 lb = h->b2;
307 308 }
308 309
309 310 result = PyString_FromStringAndSize(NULL, len);
310 311 if (!result)
311 312 goto nomem;
312 313
313 314 /* build binary patch */
314 315 rb = PyString_AsString(result);
315 316 la = lb = 0;
316 317
317 318 for(h = l.base; h != l.head; h++) {
318 319 if (h->a1 != la || h->b1 != lb) {
319 320 len = bl[h->b1].l - bl[lb].l;
320 321 *(uint32_t *)(encode) = htonl(al[la].l - al->l);
321 322 *(uint32_t *)(encode + 4) = htonl(al[h->a1].l - al->l);
322 323 *(uint32_t *)(encode + 8) = htonl(len);
323 324 memcpy(rb, encode, 12);
324 325 memcpy(rb + 12, bl[lb].l, len);
325 326 rb += 12 + len;
326 327 }
327 328 la = h->a2;
328 329 lb = h->b2;
329 330 }
330 331
331 332 nomem:
332 333 free(al);
333 334 free(bl);
334 335 free(l.base);
335 336 return result ? result : PyErr_NoMemory();
336 337 }
337 338
338 339 static char mdiff_doc[] = "Efficient binary diff.";
339 340
340 341 static PyMethodDef methods[] = {
341 342 {"bdiff", bdiff, METH_VARARGS, "calculate a binary diff\n"},
342 343 {"blocks", blocks, METH_VARARGS, "find a list of matching lines\n"},
343 344 {NULL, NULL}
344 345 };
345 346
346 347 PyMODINIT_FUNC initbdiff(void)
347 348 {
348 349 Py_InitModule3("bdiff", methods, mdiff_doc);
349 350 }
General Comments 0
You need to be logged in to leave comments. Login now