1 /*
2 * LibXDiff by Davide Libenzi ( File Differential Library )
3 * Copyright (C) 2003 Davide Libenzi
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 *
19 * Davide Libenzi <davidel@xmailserver.org>
20 *
21 */
22
23 #include "xinclude.h"
24
25
26
27 #define XDL_MAX_COST_MIN 256
28 #define XDL_HEUR_MIN_COST 256
29 #define XDL_LINE_MAX (long)((1UL << (8 * sizeof(long) - 1)) - 1)
30 #define XDL_SNAKE_CNT 20
31 #define XDL_K_HEUR 4
32
33
34
35 typedef struct s_xdpsplit {
36 long i1, i2;
37 int min_lo, min_hi;
38 } xdpsplit_t;
39
40
41
42 /*
43 * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
44 * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
45 * the forward diagonal starting from (off1, off2) and the backward diagonal
46 * starting from (lim1, lim2). If the K values on the same diagonal crosses
47 * returns the furthest point of reach. We might end up having to expensive
48 * cases using this algorithm is full, so a little bit of heuristic is needed
49 * to cut the search and to return a suboptimal point.
50 */
xdl_split(unsigned long const * ha1,long off1,long lim1,unsigned long const * ha2,long off2,long lim2,long * kvdf,long * kvdb,int need_min,xdpsplit_t * spl,xdalgoenv_t * xenv)51 static long xdl_split(unsigned long const *ha1, long off1, long lim1,
52 unsigned long const *ha2, long off2, long lim2,
53 long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,
54 xdalgoenv_t *xenv) {
55 long dmin = off1 - lim2, dmax = lim1 - off2;
56 long fmid = off1 - off2, bmid = lim1 - lim2;
57 long odd = (fmid - bmid) & 1;
58 long fmin = fmid, fmax = fmid;
59 long bmin = bmid, bmax = bmid;
60 long ec, d, i1, i2, prev1, best, dd, v, k;
61
62 /*
63 * Set initial diagonal values for both forward and backward path.
64 */
65 kvdf[fmid] = off1;
66 kvdb[bmid] = lim1;
67
68 for (ec = 1;; ec++) {
69 int got_snake = 0;
70
71 /*
72 * We need to extent the diagonal "domain" by one. If the next
73 * values exits the box boundaries we need to change it in the
74 * opposite direction because (max - min) must be a power of two.
75 * Also we initialize the extenal K value to -1 so that we can
76 * avoid extra conditions check inside the core loop.
77 */
78 if (fmin > dmin)
79 kvdf[--fmin - 1] = -1;
80 else
81 ++fmin;
82 if (fmax < dmax)
83 kvdf[++fmax + 1] = -1;
84 else
85 --fmax;
86
87 for (d = fmax; d >= fmin; d -= 2) {
88 if (kvdf[d - 1] >= kvdf[d + 1])
89 i1 = kvdf[d - 1] + 1;
90 else
91 i1 = kvdf[d + 1];
92 prev1 = i1;
93 i2 = i1 - d;
94 for (; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++, i2++);
95 if (i1 - prev1 > xenv->snake_cnt)
96 got_snake = 1;
97 kvdf[d] = i1;
98 if (odd && bmin <= d && d <= bmax && kvdb[d] <= i1) {
99 spl->i1 = i1;
100 spl->i2 = i2;
101 spl->min_lo = spl->min_hi = 1;
102 return ec;
103 }
104 }
105
106 /*
107 * We need to extent the diagonal "domain" by one. If the next
108 * values exits the box boundaries we need to change it in the
109 * opposite direction because (max - min) must be a power of two.
110 * Also we initialize the extenal K value to -1 so that we can
111 * avoid extra conditions check inside the core loop.
112 */
113 if (bmin > dmin)
114 kvdb[--bmin - 1] = XDL_LINE_MAX;
115 else
116 ++bmin;
117 if (bmax < dmax)
118 kvdb[++bmax + 1] = XDL_LINE_MAX;
119 else
120 --bmax;
121
122 for (d = bmax; d >= bmin; d -= 2) {
123 if (kvdb[d - 1] < kvdb[d + 1])
124 i1 = kvdb[d - 1];
125 else
126 i1 = kvdb[d + 1] - 1;
127 prev1 = i1;
128 i2 = i1 - d;
129 for (; i1 > off1 && i2 > off2 && ha1[i1 - 1] == ha2[i2 - 1]; i1--, i2--);
130 if (prev1 - i1 > xenv->snake_cnt)
131 got_snake = 1;
132 kvdb[d] = i1;
133 if (!odd && fmin <= d && d <= fmax && i1 <= kvdf[d]) {
134 spl->i1 = i1;
135 spl->i2 = i2;
136 spl->min_lo = spl->min_hi = 1;
137 return ec;
138 }
139 }
140
141 if (need_min)
142 continue;
143
144 /*
145 * If the edit cost is above the heuristic trigger and if
146 * we got a good snake, we sample current diagonals to see
147 * if some of the, have reached an "interesting" path. Our
148 * measure is a function of the distance from the diagonal
149 * corner (i1 + i2) penalized with the distance from the
150 * mid diagonal itself. If this value is above the current
151 * edit cost times a magic factor (XDL_K_HEUR) we consider
152 * it interesting.
153 */
154 if (got_snake && ec > xenv->heur_min) {
155 for (best = 0, d = fmax; d >= fmin; d -= 2) {
156 dd = d > fmid ? d - fmid: fmid - d;
157 i1 = kvdf[d];
158 i2 = i1 - d;
159 v = (i1 - off1) + (i2 - off2) - dd;
160
161 if (v > XDL_K_HEUR * ec && v > best &&
162 off1 + xenv->snake_cnt <= i1 && i1 < lim1 &&
163 off2 + xenv->snake_cnt <= i2 && i2 < lim2) {
164 for (k = 1; ha1[i1 - k] == ha2[i2 - k]; k++)
165 if (k == xenv->snake_cnt) {
166 best = v;
167 spl->i1 = i1;
168 spl->i2 = i2;
169 break;
170 }
171 }
172 }
173 if (best > 0) {
174 spl->min_lo = 1;
175 spl->min_hi = 0;
176 return ec;
177 }
178
179 for (best = 0, d = bmax; d >= bmin; d -= 2) {
180 dd = d > bmid ? d - bmid: bmid - d;
181 i1 = kvdb[d];
182 i2 = i1 - d;
183 v = (lim1 - i1) + (lim2 - i2) - dd;
184
185 if (v > XDL_K_HEUR * ec && v > best &&
186 off1 < i1 && i1 <= lim1 - xenv->snake_cnt &&
187 off2 < i2 && i2 <= lim2 - xenv->snake_cnt) {
188 for (k = 0; ha1[i1 + k] == ha2[i2 + k]; k++)
189 if (k == xenv->snake_cnt - 1) {
190 best = v;
191 spl->i1 = i1;
192 spl->i2 = i2;
193 break;
194 }
195 }
196 }
197 if (best > 0) {
198 spl->min_lo = 0;
199 spl->min_hi = 1;
200 return ec;
201 }
202 }
203
204 /*
205 * Enough is enough. We spent too much time here and now we collect
206 * the furthest reaching path using the (i1 + i2) measure.
207 */
208 if (ec >= xenv->mxcost) {
209 long fbest, fbest1, bbest, bbest1;
210
211 fbest = -1;
212 for (d = fmax; d >= fmin; d -= 2) {
213 i1 = XDL_MIN(kvdf[d], lim1);
214 i2 = i1 - d;
215 if (lim2 < i2)
216 i1 = lim2 + d, i2 = lim2;
217 if (fbest < i1 + i2) {
218 fbest = i1 + i2;
219 fbest1 = i1;
220 }
221 }
222
223 bbest = XDL_LINE_MAX;
224 for (d = bmax; d >= bmin; d -= 2) {
225 i1 = XDL_MAX(off1, kvdb[d]);
226 i2 = i1 - d;
227 if (i2 < off2)
228 i1 = off2 + d, i2 = off2;
229 if (i1 + i2 < bbest) {
230 bbest = i1 + i2;
231 bbest1 = i1;
232 }
233 }
234
235 if ((lim1 + lim2) - bbest < fbest - (off1 + off2)) {
236 spl->i1 = fbest1;
237 spl->i2 = fbest - fbest1;
238 spl->min_lo = 1;
239 spl->min_hi = 0;
240 } else {
241 spl->i1 = bbest1;
242 spl->i2 = bbest - bbest1;
243 spl->min_lo = 0;
244 spl->min_hi = 1;
245 }
246 return ec;
247 }
248 }
249
250 return -1;
251 }
252
253
254 /*
255 * Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling
256 * the box splitting function. Note that the real job (marking changed lines)
257 * is done in the two boundary reaching checks.
258 */
xdl_recs_cmp(diffdata_t * dd1,long off1,long lim1,diffdata_t * dd2,long off2,long lim2,long * kvdf,long * kvdb,int need_min,xdalgoenv_t * xenv)259 int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1,
260 diffdata_t *dd2, long off2, long lim2,
261 long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) {
262 unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha;
263
264 /*
265 * Shrink the box by walking through each diagonal snake (SW and NE).
266 */
267 for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++);
268 for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--);
269
270 /*
271 * If one dimension is empty, then all records on the other one must
272 * be obviously changed.
273 */
274 if (off1 == lim1) {
275 char *rchg2 = dd2->rchg;
276 long *rindex2 = dd2->rindex;
277
278 for (; off2 < lim2; off2++)
279 rchg2[rindex2[off2]] = 1;
280 } else if (off2 == lim2) {
281 char *rchg1 = dd1->rchg;
282 long *rindex1 = dd1->rindex;
283
284 for (; off1 < lim1; off1++)
285 rchg1[rindex1[off1]] = 1;
286 } else {
287 long ec;
288 xdpsplit_t spl;
289
290 /*
291 * Divide ...
292 */
293 if ((ec = xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,
294 need_min, &spl, xenv)) < 0) {
295
296 return -1;
297 }
298
299 /*
300 * ... et Impera.
301 */
302 if (xdl_recs_cmp(dd1, off1, spl.i1, dd2, off2, spl.i2,
303 kvdf, kvdb, spl.min_lo, xenv) < 0 ||
304 xdl_recs_cmp(dd1, spl.i1, lim1, dd2, spl.i2, lim2,
305 kvdf, kvdb, spl.min_hi, xenv) < 0) {
306
307 return -1;
308 }
309 }
310
311 return 0;
312 }
313
314
xdl_do_diff(mmfile_t * mf1,mmfile_t * mf2,xpparam_t const * xpp,xdfenv_t * xe)315 int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
316 xdfenv_t *xe) {
317 long ndiags;
318 long *kvd, *kvdf, *kvdb;
319 xdalgoenv_t xenv;
320 diffdata_t dd1, dd2;
321
322 if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
323
324 return -1;
325 }
326
327 /*
328 * Allocate and setup K vectors to be used by the differential algorithm.
329 * One is to store the forward path and one to store the backward path.
330 */
331 ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
332 if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {
333
334 xdl_free_env(xe);
335 return -1;
336 }
337 kvdf = kvd;
338 kvdb = kvdf + ndiags;
339 kvdf += xe->xdf2.nreff + 1;
340 kvdb += xe->xdf2.nreff + 1;
341
342 xenv.mxcost = xdl_bogosqrt(ndiags);
343 if (xenv.mxcost < XDL_MAX_COST_MIN)
344 xenv.mxcost = XDL_MAX_COST_MIN;
345 xenv.snake_cnt = XDL_SNAKE_CNT;
346 xenv.heur_min = XDL_HEUR_MIN_COST;
347
348 dd1.nrec = xe->xdf1.nreff;
349 dd1.ha = xe->xdf1.ha;
350 dd1.rchg = xe->xdf1.rchg;
351 dd1.rindex = xe->xdf1.rindex;
352 dd2.nrec = xe->xdf2.nreff;
353 dd2.ha = xe->xdf2.ha;
354 dd2.rchg = xe->xdf2.rchg;
355 dd2.rindex = xe->xdf2.rindex;
356
357 if (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
358 kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) {
359
360 xdl_free(kvd);
361 xdl_free_env(xe);
362 return -1;
363 }
364
365 xdl_free(kvd);
366
367 return 0;
368 }
369
370
xdl_add_change(xdchange_t * xscr,long i1,long i2,long chg1,long chg2)371 static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) {
372 xdchange_t *xch;
373
374 if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t))))
375 return NULL;
376
377 xch->next = xscr;
378 xch->i1 = i1;
379 xch->i2 = i2;
380 xch->chg1 = chg1;
381 xch->chg2 = chg2;
382
383 return xch;
384 }
385
386
xdl_change_compact(xdfile_t * xdf,xdfile_t * xdfo)387 static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo) {
388 long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
389 char *rchg = xdf->rchg, *rchgo = xdfo->rchg;
390 xrecord_t **recs = xdf->recs;
391
392 /*
393 * This is the same of what GNU diff does. Move back and forward
394 * change groups for a consistent and pretty diff output. This also
395 * helps in finding joineable change groups and reduce the diff size.
396 */
397 for (ix = ixo = 0;;) {
398 /*
399 * Find the first changed line in the to-be-compacted file.
400 * We need to keep track of both indexes, so if we find a
401 * changed lines group on the other file, while scanning the
402 * to-be-compacted file, we need to skip it properly. Note
403 * that loops that are testing for changed lines on rchg* do
404 * not need index bounding since the array is prepared with
405 * a zero at position -1 and N.
406 */
407 for (; ix < nrec && !rchg[ix]; ix++)
408 while (rchgo[ixo++]);
409 if (ix == nrec)
410 break;
411
412 /*
413 * Record the start of a changed-group in the to-be-compacted file
414 * and find the end of it, on both to-be-compacted and other file
415 * indexes (ix and ixo).
416 */
417 ixs = ix;
418 for (ix++; rchg[ix]; ix++);
419 for (; rchgo[ixo]; ixo++);
420
421 do {
422 grpsiz = ix - ixs;
423
424 /*
425 * If the line before the current change group, is equal to
426 * the last line of the current change group, shift backward
427 * the group.
428 */
429 while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
430 XDL_RECMATCH(recs[ixs - 1], recs[ix - 1])) {
431 rchg[--ixs] = 1;
432 rchg[--ix] = 0;
433
434 /*
435 * This change might have joined two change groups,
436 * so we try to take this scenario in account by moving
437 * the start index accordingly (and so the other-file
438 * end-of-group index).
439 */
440 for (; rchg[ixs - 1]; ixs--);
441 while (rchgo[--ixo]);
442 }
443
444 /*
445 * Record the end-of-group position in case we are matched
446 * with a group of changes in the other file (that is, the
447 * change record before the enf-of-group index in the other
448 * file is set).
449 */
450 ixref = rchgo[ixo - 1] ? ix: nrec;
451
452 /*
453 * If the first line of the current change group, is equal to
454 * the line next of the current change group, shift forward
455 * the group.
456 */
457 while (ix < nrec && recs[ixs]->ha == recs[ix]->ha &&
458 XDL_RECMATCH(recs[ixs], recs[ix])) {
459 rchg[ixs++] = 0;
460 rchg[ix++] = 1;
461
462 /*
463 * This change might have joined two change groups,
464 * so we try to take this scenario in account by moving
465 * the start index accordingly (and so the other-file
466 * end-of-group index). Keep tracking the reference
467 * index in case we are shifting together with a
468 * corresponding group of changes in the other file.
469 */
470 for (; rchg[ix]; ix++);
471 while (rchgo[++ixo])
472 ixref = ix;
473 }
474 } while (grpsiz != ix - ixs);
475
476 /*
477 * Try to move back the possibly merged group of changes, to match
478 * the recorded postion in the other file.
479 */
480 while (ixref < ix) {
481 rchg[--ixs] = 1;
482 rchg[--ix] = 0;
483 while (rchgo[--ixo]);
484 }
485 }
486
487 return 0;
488 }
489
490
xdl_build_script(xdfenv_t * xe,xdchange_t ** xscr)491 int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
492 xdchange_t *cscr = NULL, *xch;
493 char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;
494 long i1, i2, l1, l2;
495
496 /*
497 * Trivial. Collects "groups" of changes and creates an edit script.
498 */
499 for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
500 if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
501 for (l1 = i1; rchg1[i1 - 1]; i1--);
502 for (l2 = i2; rchg2[i2 - 1]; i2--);
503
504 if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
505 xdl_free_script(cscr);
506 return -1;
507 }
508 cscr = xch;
509 }
510
511 *xscr = cscr;
512
513 return 0;
514 }
515
516
xdl_free_script(xdchange_t * xscr)517 void xdl_free_script(xdchange_t *xscr) {
518 xdchange_t *xch;
519
520 while ((xch = xscr) != NULL) {
521 xscr = xscr->next;
522 xdl_free(xch);
523 }
524 }
525
526
xdl_diff(mmfile_t * mf1,mmfile_t * mf2,xpparam_t const * xpp,xdemitconf_t const * xecfg,xdemitcb_t * ecb)527 int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
528 xdemitconf_t const *xecfg, xdemitcb_t *ecb) {
529 xdchange_t *xscr;
530 xdfenv_t xe;
531
532 if (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) {
533
534 return -1;
535 }
536 if (xdl_change_compact(&xe.xdf1, &xe.xdf2) < 0 ||
537 xdl_change_compact(&xe.xdf2, &xe.xdf1) < 0 ||
538 xdl_build_script(&xe, &xscr) < 0) {
539
540 xdl_free_env(&xe);
541 return -1;
542 }
543 if (xscr) {
544 if (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) {
545
546 xdl_free_script(xscr);
547 xdl_free_env(&xe);
548 return -1;
549 }
550 xdl_free_script(xscr);
551 }
552 xdl_free_env(&xe);
553
554 return 0;
555 }
556
557