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