Line data Source code
1 : #include "xdiff.h"
2 :
3 : typedef struct s_xdpsplit {
4 : long i1,i2;
5 : int min_lo,min_hi;
6 : } xdpsplit_t;
7 :
8 : /**
9 : * @brief Splits difference algorithm search space recursively
10 : *
11 : * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
12 : * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
13 : * the forward diagonal starting from (off1, off2) and the backward diagonal
14 : * starting from (lim1, lim2). If the K values on the same diagonal crosses
15 : * returns the furthest point of reach. We might end up having to expensive
16 : * cases using this algorithm is full, so a little bit of heuristic is needed
17 : * to cut the search and to return a suboptimal point.
18 : */
19 0 : static long xdl_split(
20 : unsigned long const *ha1,
21 : long off1,
22 : long lim1,
23 : unsigned long const *ha2,
24 : long off2,
25 : long lim2,
26 : long *kvdf,
27 : long *kvdb,
28 : int need_min,
29 : xdpsplit_t *spl,
30 : xdalgoenv_t *xenv)
31 : {
32 0 : long dmin = off1 - lim2,dmax = lim1 - off2;
33 0 : long fmid = off1 - off2,bmid = lim1 - lim2;
34 0 : long odd = (fmid - bmid) & 1;
35 0 : long fmin = fmid,fmax = fmid;
36 0 : long bmin = bmid,bmax = bmid;
37 : long ec,d,i1,i2,prev1,best,dd,v,k;
38 :
39 : /*
40 : * Set initial diagonal values for both forward and backward path.
41 : */
42 0 : kvdf[fmid] = off1;
43 0 : kvdb[bmid] = lim1;
44 :
45 0 : for(ec = 1;; ec++)
46 0 : {
47 0 : int got_snake = 0;
48 :
49 : /*
50 : * We need to extent the diagonal "domain" by one. If the next
51 : * values exits the box boundaries we need to change it in the
52 : * opposite direction because (max - min) must be a power of two.
53 : * Also we initialize the external K value to -1 so that we can
54 : * avoid extra conditions check inside the core loop.
55 : */
56 0 : if(fmin > dmin)
57 : {
58 0 : kvdf[--fmin - 1] = -1;
59 : } else {
60 0 : ++fmin;
61 : }
62 :
63 0 : if(fmax < dmax)
64 : {
65 0 : kvdf[++fmax + 1] = -1;
66 : } else {
67 0 : --fmax;
68 : }
69 :
70 0 : for(d = fmax; d >= fmin; d -= 2)
71 : {
72 0 : if(kvdf[d - 1] >= kvdf[d + 1])
73 : {
74 0 : i1 = kvdf[d - 1] + 1;
75 : } else {
76 0 : i1 = kvdf[d + 1];
77 : }
78 0 : prev1 = i1;
79 0 : i2 = i1 - d;
80 :
81 0 : for(; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++,i2++)
82 : {
83 : ;
84 : }
85 :
86 0 : if(i1 - prev1 > xenv->snake_cnt)
87 : {
88 0 : got_snake = 1;
89 : }
90 0 : kvdf[d] = i1;
91 :
92 0 : if(odd && bmin <= d && d <= bmax && kvdb[d] <= i1)
93 : {
94 0 : spl->i1 = i1;
95 0 : spl->i2 = i2;
96 0 : spl->min_lo = spl->min_hi = 1;
97 0 : return ec;
98 : }
99 : }
100 :
101 : /*
102 : * We need to extent the diagonal "domain" by one. If the next
103 : * values exits the box boundaries we need to change it in the
104 : * opposite direction because (max - min) must be a power of two.
105 : * Also we initialize the external K value to -1 so that we can
106 : * avoid extra conditions check inside the core loop.
107 : */
108 0 : if(bmin > dmin)
109 : {
110 0 : kvdb[--bmin - 1] = XDL_LINE_MAX;
111 : } else {
112 0 : ++bmin;
113 : }
114 :
115 0 : if(bmax < dmax)
116 : {
117 0 : kvdb[++bmax + 1] = XDL_LINE_MAX;
118 : } else {
119 0 : --bmax;
120 : }
121 :
122 0 : for(d = bmax; d >= bmin; d -= 2)
123 : {
124 0 : if(kvdb[d - 1] < kvdb[d + 1])
125 : {
126 0 : i1 = kvdb[d - 1];
127 : } else {
128 0 : i1 = kvdb[d + 1] - 1;
129 : }
130 0 : prev1 = i1;
131 0 : i2 = i1 - d;
132 :
133 0 : for(; i1 > off1 && i2 > off2 && ha1[i1 - 1] == ha2[i2 - 1];
134 0 : i1--,i2--)
135 : {
136 : ;
137 : }
138 :
139 0 : if(prev1 - i1 > xenv->snake_cnt)
140 : {
141 0 : got_snake = 1;
142 : }
143 0 : kvdb[d] = i1;
144 :
145 0 : if(!odd && fmin <= d && d <= fmax && i1 <= kvdf[d])
146 : {
147 0 : spl->i1 = i1;
148 0 : spl->i2 = i2;
149 0 : spl->min_lo = spl->min_hi = 1;
150 0 : return ec;
151 : }
152 : }
153 :
154 0 : if(need_min)
155 : {
156 0 : continue;
157 : }
158 :
159 : /*
160 : * If the edit cost is above the heuristic trigger and if
161 : * we got a good snake, we sample current diagonals to see
162 : * if some of the, have reached an "interesting" path. Our
163 : * measure is a function of the distance from the diagonal
164 : * corner (i1 + i2) penalized with the distance from the
165 : * mid diagonal itself. If this value is above the current
166 : * edit cost times a magic factor (XDL_K_HEUR) we consider
167 : * it interesting.
168 : */
169 0 : if(got_snake && ec > xenv->heur_min)
170 : {
171 0 : for(best = 0,d = fmax; d >= fmin; d -= 2)
172 : {
173 0 : dd = d > fmid ? d - fmid : fmid - d;
174 0 : i1 = kvdf[d];
175 0 : i2 = i1 - d;
176 0 : v = (i1 - off1) + (i2 - off2) - dd;
177 :
178 0 : if(v > XDL_K_HEUR * ec && v > best &&
179 0 : off1 + xenv->snake_cnt <= i1 && i1 < lim1 &&
180 0 : off2 + xenv->snake_cnt <= i2 && i2 < lim2)
181 : {
182 0 : for(k = 1; ha1[i1 - k] == ha2[i2 - k]; k++)
183 : {
184 0 : if(k == xenv->snake_cnt)
185 : {
186 0 : best = v;
187 0 : spl->i1 = i1;
188 0 : spl->i2 = i2;
189 0 : break;
190 : }
191 : }
192 : }
193 : }
194 :
195 0 : if(best > 0)
196 : {
197 0 : spl->min_lo = 1;
198 0 : spl->min_hi = 0;
199 0 : return ec;
200 : }
201 :
202 0 : for(best = 0,d = bmax; d >= bmin; d -= 2)
203 : {
204 0 : dd = d > bmid ? d - bmid : bmid - d;
205 0 : i1 = kvdb[d];
206 0 : i2 = i1 - d;
207 0 : v = (lim1 - i1) + (lim2 - i2) - dd;
208 :
209 0 : if(v > XDL_K_HEUR * ec && v > best && off1 < i1 &&
210 0 : i1 <= lim1 - xenv->snake_cnt && off2 < i2 &&
211 0 : i2 <= lim2 - xenv->snake_cnt)
212 : {
213 0 : for(k = 0; ha1[i1 + k] == ha2[i2 + k]; k++)
214 : {
215 0 : if(k == xenv->snake_cnt - 1)
216 : {
217 0 : best = v;
218 0 : spl->i1 = i1;
219 0 : spl->i2 = i2;
220 0 : break;
221 : }
222 : }
223 : }
224 : }
225 :
226 0 : if(best > 0)
227 : {
228 0 : spl->min_lo = 0;
229 0 : spl->min_hi = 1;
230 0 : return ec;
231 : }
232 : }
233 :
234 : /*
235 : * Enough is enough. We spent too much time here and now we collect
236 : * the furthest reaching path using the (i1 + i2) measure.
237 : */
238 0 : if(ec >= xenv->mxcost)
239 : {
240 0 : long fbest,fbest1 = 0,bbest,bbest1 = 0;
241 :
242 0 : fbest = -1;
243 :
244 0 : for(d = fmax; d >= fmin; d -= 2)
245 : {
246 0 : i1 = XDL_MIN(kvdf[d],lim1);
247 0 : i2 = i1 - d;
248 :
249 0 : if(lim2 < i2)
250 : {
251 0 : i1 = lim2 + d,i2 = lim2;
252 : }
253 :
254 0 : if(fbest < i1 + i2)
255 : {
256 0 : fbest = i1 + i2;
257 0 : fbest1 = i1;
258 : }
259 : }
260 :
261 0 : bbest = XDL_LINE_MAX;
262 :
263 0 : for(d = bmax; d >= bmin; d -= 2)
264 : {
265 0 : i1 = XDL_MAX(off1,kvdb[d]);
266 0 : i2 = i1 - d;
267 :
268 0 : if(i2 < off2)
269 : {
270 0 : i1 = off2 + d,i2 = off2;
271 : }
272 :
273 0 : if(i1 + i2 < bbest)
274 : {
275 0 : bbest = i1 + i2;
276 0 : bbest1 = i1;
277 : }
278 : }
279 :
280 0 : if((lim1 + lim2) - bbest < fbest - (off1 + off2))
281 : {
282 0 : spl->i1 = fbest1;
283 0 : spl->i2 = fbest - fbest1;
284 0 : spl->min_lo = 1;
285 0 : spl->min_hi = 0;
286 : } else {
287 0 : spl->i1 = bbest1;
288 0 : spl->i2 = bbest - bbest1;
289 0 : spl->min_lo = 0;
290 0 : spl->min_hi = 1;
291 : }
292 0 : return ec;
293 : }
294 : }
295 :
296 : return -1;
297 : }
298 :
299 : /**
300 : * @brief Compares records between two sequences to find differences
301 : *
302 : * Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling
303 : * the box splitting function. Note that the real job (marking changed lines)
304 : * is done in the two boundary reaching checks.
305 : */
306 8 : int xdl_recs_cmp(
307 : diffdata_t *dd1,
308 : long off1,
309 : long lim1,
310 : diffdata_t *dd2,
311 : long off2,
312 : long lim2,
313 : long *kvdf,
314 : long *kvdb,
315 : int need_min,
316 : xdalgoenv_t *xenv)
317 : {
318 8 : unsigned long const *ha1 = dd1->ha,*ha2 = dd2->ha;
319 :
320 : /*
321 : * Shrink the box by walking through each diagonal snake (SW and NE).
322 : */
323 364 : for(; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++,off2++)
324 : {
325 : ;
326 : }
327 :
328 8 : for(; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1];
329 0 : lim1--,lim2--)
330 : {
331 : ;
332 : }
333 :
334 : /*
335 : * If one dimension is empty, then all records on the other one must
336 : * be obviously changed.
337 : */
338 8 : if(off1 == lim1)
339 : {
340 8 : char *rchg2 = dd2->rchg;
341 8 : long *rindex2 = dd2->rindex;
342 :
343 14 : for(; off2 < lim2; off2++)
344 : {
345 6 : rchg2[rindex2[off2]] = 1;
346 : }
347 0 : } else if(off2 == lim2){
348 0 : char *rchg1 = dd1->rchg;
349 0 : long *rindex1 = dd1->rindex;
350 :
351 0 : for(; off1 < lim1; off1++)
352 : {
353 0 : rchg1[rindex1[off1]] = 1;
354 : }
355 : } else {
356 : xdpsplit_t spl;
357 :
358 : /*
359 : * Divide ...
360 : */
361 0 : if(xdl_split(
362 : ha1,
363 : off1,
364 : lim1,
365 : ha2,
366 : off2,
367 : lim2,
368 : kvdf,
369 : kvdb,
370 : need_min,
371 : &spl,
372 : xenv) < 0)
373 : {
374 0 : return -1;
375 : }
376 :
377 : /*
378 : * ... et Impera.
379 : */
380 0 : if(xdl_recs_cmp(
381 : dd1,
382 : off1,
383 : spl.i1,
384 : dd2,
385 : off2,
386 : spl.i2,
387 : kvdf,
388 : kvdb,
389 : spl.min_lo,
390 0 : xenv) < 0 ||
391 0 : xdl_recs_cmp(
392 : dd1,
393 : spl.i1,
394 : lim1,
395 : dd2,
396 : spl.i2,
397 : lim2,
398 : kvdf,
399 : kvdb,
400 : spl.min_hi,
401 : xenv) < 0)
402 : {
403 0 : return -1;
404 : }
405 : }
406 :
407 8 : return 0;
408 : }
409 :
410 : /**
411 : * @brief Performs the main difference algorithm between two files
412 : *
413 : * @param mf1 First mmfile structure
414 : * @param mf2 Second mmfile structure
415 : * @param xpp Algorithm parameters
416 : * @param xe Environment structure to store results
417 : * @return int Returns 0 on success, -1 on error
418 : */
419 8 : int xdl_do_diff(
420 : mmfile_t *mf1,
421 : mmfile_t *mf2,
422 : xpparam_t const *xpp,
423 : xdfenv_t *xe)
424 : {
425 : long ndiags;
426 : long *kvd,*kvdf,*kvdb;
427 : xdalgoenv_t xenv;
428 : diffdata_t dd1,dd2;
429 :
430 8 : if(xdl_prepare_env(mf1,mf2,xe) < 0)
431 : {
432 0 : return -1;
433 : }
434 :
435 : /*
436 : * Allocate and setup K vectors to be used by the differential algorithm.
437 : * One is to store the forward path and one to store the backward path.
438 : */
439 8 : ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
440 :
441 8 : if(!(kvd = (long *)malloc((2 * ndiags + 2) * sizeof(long))))
442 : {
443 :
444 0 : xdl_free_env(xe);
445 0 : return -1;
446 : }
447 8 : kvdf = kvd;
448 8 : kvdb = kvdf + ndiags;
449 8 : kvdf += xe->xdf2.nreff + 1;
450 8 : kvdb += xe->xdf2.nreff + 1;
451 :
452 8 : xenv.mxcost = xdl_bogosqrt(ndiags);
453 :
454 8 : if(xenv.mxcost < XDL_MAX_COST_MIN)
455 : {
456 8 : xenv.mxcost = XDL_MAX_COST_MIN;
457 : }
458 8 : xenv.snake_cnt = XDL_SNAKE_CNT;
459 8 : xenv.heur_min = XDL_HEUR_MIN_COST;
460 :
461 8 : dd1.nrec = xe->xdf1.nreff;
462 8 : dd1.ha = xe->xdf1.ha;
463 8 : dd1.rchg = xe->xdf1.rchg;
464 8 : dd1.rindex = xe->xdf1.rindex;
465 8 : dd2.nrec = xe->xdf2.nreff;
466 8 : dd2.ha = xe->xdf2.ha;
467 8 : dd2.rchg = xe->xdf2.rchg;
468 8 : dd2.rindex = xe->xdf2.rindex;
469 :
470 8 : if(xdl_recs_cmp(
471 : &dd1,
472 : 0,
473 : dd1.nrec,
474 : &dd2,
475 : 0,
476 : dd2.nrec,
477 : kvdf,
478 : kvdb,
479 8 : (xpp->flags & XDF_NEED_MINIMAL) != 0,
480 : &xenv) < 0)
481 : {
482 :
483 0 : free(kvd);
484 0 : xdl_free_env(xe);
485 0 : return -1;
486 : }
487 :
488 8 : free(kvd);
489 :
490 8 : return 0;
491 : }
492 :
493 : /**
494 : * @brief Adds a change record to the change script
495 : *
496 : * @param xscr Current change script
497 : * @param i1 Line number in first file
498 : * @param i2 Line number in second file
499 : * @param chg1 Number of lines changed in first file
500 : * @param chg2 Number of lines changed in second file
501 : * @return xdchange_t* Returns pointer to new change record or NULL on error
502 : */
503 : static xdchange_t *
504 36 : xdl_add_change(
505 : xdchange_t *xscr,
506 : long i1,
507 : long i2,
508 : long chg1,
509 : long chg2)
510 : {
511 : xdchange_t *xch;
512 :
513 36 : if(!(xch = (xdchange_t *)malloc(sizeof(xdchange_t))))
514 : {
515 0 : return NULL;
516 : }
517 :
518 36 : xch->next = xscr;
519 36 : xch->i1 = i1;
520 36 : xch->i2 = i2;
521 36 : xch->chg1 = chg1;
522 36 : xch->chg2 = chg2;
523 :
524 36 : return xch;
525 : }
526 :
527 : /**
528 : * @brief Compacts and optimizes change records for better output
529 : *
530 : * @param xdf Main file diff structure
531 : * @param xdfo Other file diff structure for comparison
532 : * @return int Returns 0 on success, -1 on error
533 : */
534 16 : static int xdl_change_compact(
535 : xdfile_t *xdf,
536 : xdfile_t *xdfo)
537 : {
538 16 : long ix,ixo,ixref,grpsiz,nrec = xdf->nrec;
539 16 : char *rchg = xdf->rchg,*rchgo = xdfo->rchg;
540 16 : xrecord_t **recs = xdf->recs;
541 :
542 : /*
543 : * This is the same of what GNU diff does. Move back and forward
544 : * change groups for a consistent and pretty diff output. This also
545 : * helps in finding joineable change groups and reduce the diff size.
546 : */
547 16 : for(ix = ixo = 0;;)
548 56 : {
549 : /*
550 : * Find the first changed line in the to-be-compacted file.
551 : * We need to keep track of both indexes, so if we find a
552 : * changed lines group on the other file, while scanning the
553 : * to-be-compacted file, we need to skip it properly. Note
554 : * that loops that are testing for changed lines on rchg* do
555 : * not need index bounding since the array is prepared with
556 : * a zero at position -1 and N.
557 : */
558 932 : for(; ix < nrec && !rchg[ix]; ix++)
559 : {
560 878 : while(rchgo[ixo++])
561 : {
562 : ;
563 : }
564 : }
565 :
566 72 : if(ix == nrec)
567 : {
568 16 : break;
569 : }
570 :
571 : /*
572 : * Record the start of a changed-group in the to-be-compacted file
573 : * and find the end of it, on both to-be-compacted and other file
574 : * indexes (ix and ixo).
575 : */
576 56 : long ixs = ix;
577 :
578 114 : for(ix++; rchg[ix]; ix++)
579 : {
580 : ;
581 : }
582 :
583 152 : for(; rchgo[ixo]; ixo++)
584 : {
585 : ;
586 : }
587 :
588 : do
589 : {
590 56 : grpsiz = ix - ixs;
591 :
592 : /*
593 : * If the line before the current change group, is equal to
594 : * the last line of the current change group, shift backward
595 : * the group.
596 : */
597 56 : while(ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
598 0 : XDL_RECMATCH(recs[ixs - 1],recs[ix - 1]))
599 : {
600 0 : rchg[--ixs] = 1;
601 0 : rchg[--ix] = 0;
602 :
603 : /*
604 : * This change might have joined two change groups,
605 : * so we try to take this scenario in account by moving
606 : * the start index accordingly (and so the other-file
607 : * end-of-group index).
608 : */
609 0 : for(; rchg[ixs - 1]; ixs--)
610 : {
611 : ;
612 : }
613 :
614 0 : while(rchgo[--ixo])
615 : {
616 : ;
617 : }
618 : }
619 :
620 : /*
621 : * Record the end-of-group position in case we are matched
622 : * with a group of changes in the other file (that is, the
623 : * change record before the enf-of-group index in the other
624 : * file is set).
625 : */
626 56 : ixref = rchgo[ixo - 1] ? ix : nrec;
627 :
628 : /*
629 : * If the first line of the current change group, is equal to
630 : * the line next of the current change group, shift forward
631 : * the group.
632 : */
633 56 : while(ix < nrec && recs[ixs]->ha == recs[ix]->ha &&
634 0 : XDL_RECMATCH(recs[ixs],recs[ix]))
635 : {
636 0 : rchg[ixs++] = 0;
637 0 : rchg[ix++] = 1;
638 :
639 : /*
640 : * This change might have joined two change groups,
641 : * so we try to take this scenario in account by moving
642 : * the start index accordingly (and so the other-file
643 : * end-of-group index). Keep tracking the reference
644 : * index in case we are shifting together with a
645 : * corresponding group of changes in the other file.
646 : */
647 0 : for(; rchg[ix]; ix++)
648 : {
649 : ;
650 : }
651 :
652 0 : while(rchgo[++ixo])
653 : {
654 0 : ixref = ix;
655 : }
656 : }
657 56 : } while(grpsiz != ix - ixs);
658 :
659 : /*
660 : * Try to move back the possibly merged group of changes, to match
661 : * the recorded position in the other file.
662 : */
663 56 : while(ixref < ix)
664 : {
665 0 : rchg[--ixs] = 1;
666 0 : rchg[--ix] = 0;
667 :
668 0 : while(rchgo[--ixo])
669 : {
670 : ;
671 : }
672 : }
673 : }
674 :
675 16 : return 0;
676 : }
677 :
678 : /**
679 : * @brief Builds the change script from comparison results
680 : *
681 : * @param xe Diff environment containing comparison data
682 : * @param xscr Pointer to receive the generated change script
683 : * @return int Returns 0 on success, -1 on error
684 : */
685 8 : int xdl_build_script(
686 : xdfenv_t *xe,
687 : xdchange_t **xscr)
688 : {
689 8 : xdchange_t *cscr = NULL,*xch;
690 8 : char *rchg1 = xe->xdf1.rchg,*rchg2 = xe->xdf2.rchg;
691 : long i1,i2,l1,l2;
692 :
693 : /*
694 : * Trivial. Collects "groups" of changes and creates an edit script.
695 : */
696 446 : for(i1 = xe->xdf1.nrec,i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--,i2--)
697 : {
698 438 : if(rchg1[i1 - 1] || rchg2[i2 - 1])
699 : {
700 88 : for(l1 = i1; rchg1[i1 - 1]; i1--)
701 : {
702 : ;
703 : }
704 :
705 98 : for(l2 = i2; rchg2[i2 - 1]; i2--)
706 : {
707 : ;
708 : }
709 :
710 36 : if(!(xch = xdl_add_change(cscr,i1,i2,l1 - i1,l2 - i2)))
711 : {
712 0 : xdl_free_script(cscr);
713 0 : return -1;
714 : }
715 36 : cscr = xch;
716 : }
717 : }
718 :
719 8 : *xscr = cscr;
720 :
721 8 : return 0;
722 : }
723 :
724 : /**
725 : * @brief Frees memory used by a change script
726 : *
727 : * @param xscr Change script to free
728 : */
729 8 : void xdl_free_script(xdchange_t *xscr)
730 : {
731 : xdchange_t *xch;
732 :
733 44 : while((xch = xscr) != NULL)
734 : {
735 36 : xscr = xscr->next;
736 36 : free(xch);
737 : }
738 8 : }
739 :
740 : /**
741 : * @brief Main entry point for diff generation between two files
742 : *
743 : * @param mf1 First file
744 : * @param mf2 Second file
745 : * @param xpp Diff algorithm parameters
746 : * @param xecfg Output configuration
747 : * @param ecb Output callback functions
748 : * @return int Returns 0 on success, -1 on error
749 : */
750 8 : int xdl_diff(
751 : mmfile_t *mf1,
752 : mmfile_t *mf2,
753 : xpparam_t const *xpp,
754 : xdemitconf_t const *xecfg,
755 : xdemitcb_t *ecb)
756 : {
757 : xdchange_t *xscr;
758 : xdfenv_t xe;
759 :
760 8 : if(xdl_do_diff(mf1,mf2,xpp,&xe) < 0)
761 : {
762 0 : return -1;
763 : }
764 :
765 16 : if(xdl_change_compact(&xe.xdf1,&xe.xdf2) < 0 ||
766 16 : xdl_change_compact(&xe.xdf2,&xe.xdf1) < 0 ||
767 8 : xdl_build_script(&xe,&xscr) < 0)
768 : {
769 :
770 0 : xdl_free_env(&xe);
771 0 : return -1;
772 : }
773 :
774 8 : if(xscr)
775 : {
776 8 : if(xdl_emit_diff(&xe,xscr,ecb,xecfg) < 0)
777 : {
778 :
779 0 : xdl_free_script(xscr);
780 0 : xdl_free_env(&xe);
781 0 : return -1;
782 : }
783 8 : xdl_free_script(xscr);
784 : }
785 8 : xdl_free_env(&xe);
786 :
787 8 : return 0;
788 : }
789 :
790 : /**
791 : * @brief Wrapper for standard malloc function
792 : *
793 : * @param priv Private data pointer (unused)
794 : * @param size Number of bytes to allocate
795 : * @return void* Returns allocated memory pointer
796 : */
797 : #if 0
798 : void *wrap_malloc(
799 : void *priv,
800 : unsigned int size)
801 : {
802 : return malloc(size);
803 : }
804 : #endif
805 :
806 : /**
807 : * @brief Wrapper for standard free function
808 : *
809 : * @param priv Private data pointer (unused)
810 : * @param ptr Pointer to memory to free
811 : */
812 : #if 0
813 : void wrap_free(
814 : void *priv,
815 : void *ptr)
816 : {
817 : free(ptr);
818 : }
819 : #endif
820 :
821 : /**
822 : * @brief Wrapper for standard realloc function
823 : *
824 : * @param priv Private data pointer (unused)
825 : * @param ptr Pointer to existing memory block
826 : * @param size New size in bytes
827 : * @return void* Returns reallocated memory pointer
828 : */
829 : #if 0
830 : void *wrap_realloc(
831 : void *priv,
832 : void *ptr,
833 : unsigned int size)
834 : {
835 :
836 : return realloc(ptr,size);
837 : }
838 : #endif
839 :
840 : /**
841 : * @brief Gets record data at specified index
842 : *
843 : * @param xdf Diff file structure
844 : * @param ri Record index
845 : * @param rec Pointer to receive record data
846 : * @return long Returns record size
847 : */
848 114 : static long xdl_get_rec(
849 : xdfile_t *xdf,
850 : long ri,
851 : char const **rec)
852 : {
853 :
854 114 : *rec = xdf->recs[ri]->ptr;
855 :
856 114 : return xdf->recs[ri]->size;
857 : }
858 :
859 : /**
860 : * @brief Emits a single record with prefix to output
861 : *
862 : * @param xdf Diff file structure
863 : * @param ri Record index
864 : * @param pre Prefix string to prepend
865 : * @param ecb Output callback
866 : * @return int Returns 0 on success, -1 on error
867 : */
868 : static int
869 114 : xdl_emit_record(
870 : xdfile_t *xdf,
871 : long ri,
872 : char const *pre,
873 : xdemitcb_t *ecb)
874 : {
875 114 : long size,psize = strlen(pre);
876 : char const *rec;
877 :
878 114 : size = xdl_get_rec(xdf,ri,&rec);
879 :
880 114 : if(xdl_emit_diffrec(rec,size,pre,psize,ecb) < 0)
881 : {
882 0 : return -1;
883 : }
884 :
885 114 : return 0;
886 : }
887 :
888 : /**
889 : * @brief Finds the latest change atom for inclusion in diff hunk
890 : *
891 : * @param xscr Current change script
892 : * @param xecfg Emit configuration
893 : * @return xdchange_t* Returns pointer to last change in hunk
894 : *
895 : * Starting at the passed change atom, find the latest change atom to be
896 : * included inside the differential hunk according to the specified
897 : * configuration.
898 : */
899 : static xdchange_t *xdl_get_hunk(
900 : xdchange_t *,
901 : xdemitconf_t const *) __attribute__((pure));
902 :
903 36 : static xdchange_t *xdl_get_hunk(
904 : xdchange_t *xscr,
905 : xdemitconf_t const *xecfg)
906 : {
907 :
908 : xdchange_t *xch,*xchp;
909 :
910 36 : for(xchp = xscr,xch = xscr->next; xch; xchp = xch,xch = xch->next)
911 : {
912 28 : if(xch->i1 - (xchp->i1 + xchp->chg1) > 2 * xecfg->ctxlen)
913 : {
914 28 : break;
915 : }
916 : }
917 :
918 36 : return xchp;
919 : }
920 :
921 : /**
922 : * @brief Emits the complete diff output
923 : *
924 : * @param xe Diff environment
925 : * @param xscr Change script
926 : * @param ecb Output callback
927 : * @param xecfg Emit configuration
928 : * @return int Returns 0 on success, -1 on error
929 : */
930 8 : int xdl_emit_diff(
931 : xdfenv_t *xe,
932 : xdchange_t *xscr,
933 : xdemitcb_t *ecb,
934 : xdemitconf_t const *xecfg)
935 : {
936 : long s1,s2,e1,e2,lctx;
937 : xdchange_t *xch,*xche;
938 :
939 44 : for(xch = xche = xscr; xch; xch = xche->next)
940 : {
941 36 : xche = xdl_get_hunk(xch,xecfg);
942 :
943 36 : s1 = XDL_MAX(xch->i1 - xecfg->ctxlen,0);
944 36 : s2 = XDL_MAX(xch->i2 - xecfg->ctxlen,0);
945 :
946 36 : lctx = xecfg->ctxlen;
947 36 : lctx = XDL_MIN(lctx,xe->xdf1.nrec - (xche->i1 + xche->chg1));
948 36 : lctx = XDL_MIN(lctx,xe->xdf2.nrec - (xche->i2 + xche->chg2));
949 :
950 36 : e1 = xche->i1 + xche->chg1 + lctx;
951 36 : e2 = xche->i2 + xche->chg2 + lctx;
952 :
953 : /*
954 : * Emit current hunk header.
955 : */
956 36 : if(xecfg->str_meta && xdl_emit_hunk_hdr(s1 + 1,e1 - s1,s2 + 1,e2 - s2,ecb) < 0)
957 : {
958 0 : return -1;
959 : }
960 :
961 : /*
962 : * Emit pre-context.
963 : */
964 36 : for(; s1 < xch->i1; s1++)
965 : {
966 0 : if(xdl_emit_record(&xe->xdf1,s1," ",ecb) < 0)
967 : {
968 0 : return -1;
969 : }
970 : }
971 :
972 36 : for(s1 = xch->i1,s2 = xch->i2;; xch = xch->next)
973 : {
974 : /*
975 : * Merge previous with current change atom.
976 : */
977 36 : for(; s1 < xch->i1 && s2 < xch->i2; s1++,s2++)
978 : {
979 0 : if(xdl_emit_record(&xe->xdf1,s1," ",ecb) < 0)
980 : {
981 0 : return -1;
982 : }
983 : }
984 :
985 : /*
986 : * Removes lines from the first file.
987 : */
988 88 : for(s1 = xch->i1; s1 < xch->i1 + xch->chg1; s1++)
989 : {
990 52 : if(xdl_emit_record(&xe->xdf1,s1,"-",ecb) < 0)
991 : {
992 0 : return -1;
993 : }
994 : }
995 :
996 : /*
997 : * Adds lines from the second file.
998 : */
999 98 : for(s2 = xch->i2; s2 < xch->i2 + xch->chg2; s2++)
1000 : {
1001 62 : if(xdl_emit_record(&xe->xdf2,s2,"+",ecb) < 0)
1002 : {
1003 0 : return -1;
1004 : }
1005 : }
1006 :
1007 36 : if(xch == xche)
1008 : {
1009 36 : break;
1010 : }
1011 0 : s1 = xch->i1 + xch->chg1;
1012 0 : s2 = xch->i2 + xch->chg2;
1013 : }
1014 :
1015 : /*
1016 : * Emit post-context.
1017 : */
1018 36 : for(s1 = xche->i1 + xche->chg1; s1 < e1; s1++)
1019 : {
1020 0 : if(xdl_emit_record(&xe->xdf1,s1," ",ecb) < 0)
1021 : {
1022 0 : return -1;
1023 : }
1024 : }
1025 : }
1026 :
1027 8 : return 0;
1028 : }
1029 :
1030 : typedef struct s_xdlclass {
1031 : struct s_xdlclass *next;
1032 : unsigned long ha;
1033 : char const *line;
1034 : long size;
1035 : long idx;
1036 : } xdlclass_t;
1037 :
1038 : typedef struct s_xdlclassifier {
1039 : unsigned int hbits;
1040 : long hsize;
1041 : xdlclass_t **rchash;
1042 : chastore_t ncha;
1043 : long count;
1044 : } xdlclassifier_t;
1045 :
1046 8 : static int xdl_init_classifier(
1047 : xdlclassifier_t *cf,
1048 : long size)
1049 : {
1050 : long i;
1051 :
1052 8 : cf->hbits = xdl_hashbits((unsigned int)size);
1053 8 : cf->hsize = 1 << cf->hbits;
1054 :
1055 8 : if(xdl_cha_init(&cf->ncha,sizeof(xdlclass_t),size / 4 + 1) < 0)
1056 : {
1057 0 : return -1;
1058 : }
1059 :
1060 8 : if(!(cf->rchash =
1061 8 : (xdlclass_t **)malloc(cf->hsize * sizeof(xdlclass_t *))))
1062 : {
1063 :
1064 0 : xdl_cha_free(&cf->ncha);
1065 0 : return -1;
1066 : }
1067 :
1068 1544 : for(i = 0; i < cf->hsize; i++)
1069 : {
1070 1536 : cf->rchash[i] = NULL;
1071 : }
1072 :
1073 8 : cf->count = 0;
1074 :
1075 8 : return 0;
1076 : }
1077 :
1078 8 : static void xdl_free_classifier(xdlclassifier_t *cf)
1079 : {
1080 8 : free(cf->rchash);
1081 8 : xdl_cha_free(&cf->ncha);
1082 8 : }
1083 :
1084 974 : static int xdl_classify_record(
1085 : xdlclassifier_t *cf,
1086 : xrecord_t **rhash,
1087 : unsigned int hbits,
1088 : xrecord_t *rec)
1089 : {
1090 : long hi;
1091 : char const *line;
1092 : xdlclass_t *rcrec;
1093 :
1094 974 : line = rec->ptr;
1095 974 : hi = (long)XDL_HASHLONG(rec->ha,cf->hbits);
1096 :
1097 1106 : for(rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)
1098 : {
1099 570 : if(rcrec->ha == rec->ha && rcrec->size == rec->size &&
1100 438 : !memcmp(line,rcrec->line,rec->size))
1101 : {
1102 438 : break;
1103 : }
1104 : }
1105 :
1106 974 : if(!rcrec)
1107 : {
1108 536 : if(!(rcrec = xdl_cha_alloc(&cf->ncha)))
1109 : {
1110 0 : return -1;
1111 : }
1112 536 : rcrec->idx = cf->count++;
1113 536 : rcrec->line = line;
1114 536 : rcrec->size = rec->size;
1115 536 : rcrec->ha = rec->ha;
1116 536 : rcrec->next = cf->rchash[hi];
1117 536 : cf->rchash[hi] = rcrec;
1118 : }
1119 :
1120 974 : rec->ha = (unsigned long)rcrec->idx;
1121 :
1122 974 : hi = (long)XDL_HASHLONG(rec->ha,hbits);
1123 974 : rec->next = rhash[hi];
1124 974 : rhash[hi] = rec;
1125 :
1126 974 : return 0;
1127 : }
1128 :
1129 16 : static int xdl_prepare_ctx(
1130 : mmfile_t *mf,
1131 : long narec,
1132 : xdlclassifier_t *cf,
1133 : xdfile_t *xdf)
1134 : {
1135 : unsigned int hbits;
1136 : long i,nrec,hsize,bsize;
1137 : unsigned long hav;
1138 : char const *blk,*cur,*top,*prev;
1139 : xrecord_t *crec;
1140 : xrecord_t **recs,**rrecs;
1141 : xrecord_t **rhash;
1142 : unsigned long *ha;
1143 : char *rchg;
1144 : long *rindex;
1145 :
1146 16 : if(xdl_cha_init(&xdf->rcha,sizeof(xrecord_t),narec / 4 + 1) < 0)
1147 : {
1148 0 : return -1;
1149 : }
1150 :
1151 16 : if(!(recs = (xrecord_t **)malloc(narec * sizeof(xrecord_t *))))
1152 : {
1153 :
1154 0 : xdl_cha_free(&xdf->rcha);
1155 0 : return -1;
1156 : }
1157 :
1158 16 : hbits = xdl_hashbits((unsigned int)narec);
1159 16 : hsize = 1 << hbits;
1160 :
1161 16 : if(!(rhash = (xrecord_t **)malloc(hsize * sizeof(xrecord_t *))))
1162 : {
1163 :
1164 0 : free(recs);
1165 0 : xdl_cha_free(&xdf->rcha);
1166 0 : return -1;
1167 : }
1168 :
1169 1552 : for(i = 0; i < hsize; i++)
1170 : {
1171 1536 : rhash[i] = NULL;
1172 : }
1173 :
1174 16 : nrec = 0;
1175 :
1176 16 : if((cur = blk = xdl_mmfile_first(mf,&bsize)) != NULL)
1177 : {
1178 16 : for(top = blk + bsize;;)
1179 : {
1180 990 : if(cur >= top)
1181 : {
1182 16 : if(!(cur = blk = xdl_mmfile_next(mf,&bsize)))
1183 : {
1184 16 : break;
1185 : }
1186 0 : top = blk + bsize;
1187 : }
1188 974 : prev = cur;
1189 974 : hav = xdl_hash_record(&cur,top);
1190 :
1191 974 : if(nrec >= narec)
1192 : {
1193 0 : narec *= 2;
1194 :
1195 0 : if(!(rrecs = (xrecord_t **)realloc(
1196 : recs,narec * sizeof(xrecord_t *))))
1197 : {
1198 :
1199 0 : free(rhash);
1200 0 : free(recs);
1201 0 : xdl_cha_free(&xdf->rcha);
1202 0 : return -1;
1203 : }
1204 0 : recs = rrecs;
1205 : }
1206 :
1207 974 : if(!(crec = xdl_cha_alloc(&xdf->rcha)))
1208 : {
1209 :
1210 0 : free(rhash);
1211 0 : free(recs);
1212 0 : xdl_cha_free(&xdf->rcha);
1213 0 : return -1;
1214 : }
1215 974 : crec->ptr = prev;
1216 974 : crec->size = (long)(cur - prev);
1217 974 : crec->ha = hav;
1218 974 : recs[nrec++] = crec;
1219 :
1220 974 : if(xdl_classify_record(cf,rhash,hbits,crec) < 0)
1221 : {
1222 :
1223 0 : free(rhash);
1224 0 : free(recs);
1225 0 : xdl_cha_free(&xdf->rcha);
1226 0 : return -1;
1227 : }
1228 : }
1229 : }
1230 :
1231 16 : if(!(rchg = (char *)malloc(nrec + 2)))
1232 : {
1233 :
1234 0 : free(rhash);
1235 0 : free(recs);
1236 0 : xdl_cha_free(&xdf->rcha);
1237 0 : return -1;
1238 : }
1239 16 : memset(rchg,0,nrec + 2);
1240 :
1241 16 : if(!(rindex = (long *)malloc((nrec + 1) * sizeof(long))))
1242 : {
1243 :
1244 0 : free(rchg);
1245 0 : free(rhash);
1246 0 : free(recs);
1247 0 : xdl_cha_free(&xdf->rcha);
1248 0 : return -1;
1249 : }
1250 :
1251 16 : if(!(ha = (unsigned long *)malloc((nrec + 1) * sizeof(unsigned long))))
1252 : {
1253 :
1254 0 : free(rindex);
1255 0 : free(rchg);
1256 0 : free(rhash);
1257 0 : free(recs);
1258 0 : xdl_cha_free(&xdf->rcha);
1259 0 : return -1;
1260 : }
1261 :
1262 16 : xdf->nrec = nrec;
1263 16 : xdf->recs = recs;
1264 16 : xdf->hbits = hbits;
1265 16 : xdf->rhash = rhash;
1266 16 : xdf->rchg = rchg + 1;
1267 16 : xdf->rindex = rindex;
1268 16 : xdf->nreff = 0;
1269 16 : xdf->ha = ha;
1270 16 : xdf->dstart = 0;
1271 16 : xdf->dend = nrec - 1;
1272 :
1273 16 : return 0;
1274 : }
1275 :
1276 16 : static void xdl_free_ctx(xdfile_t *xdf)
1277 : {
1278 16 : free(xdf->rhash);
1279 16 : free(xdf->rindex);
1280 16 : free(xdf->rchg - 1);
1281 16 : free(xdf->ha);
1282 16 : free(xdf->recs);
1283 16 : xdl_cha_free(&xdf->rcha);
1284 16 : }
1285 :
1286 0 : static int xdl_clean_mmatch(
1287 : char const *dis,
1288 : long i,
1289 : long s,
1290 : long e)
1291 : {
1292 : long r,rdis0,rpdis0,rdis1,rpdis1;
1293 :
1294 : /*
1295 : * Limits the window the is examined during the similar-lines
1296 : * scan. The loops below stops when dis[i - r] == 1 (line that
1297 : * has no match), but there are corner cases where the loop
1298 : * proceed all the way to the extremities by causing huge
1299 : * performance penalties in case of big files.
1300 : */
1301 0 : if(i - s > XDL_SIMSCAN_WINDOW)
1302 : {
1303 0 : s = i - XDL_SIMSCAN_WINDOW;
1304 : }
1305 :
1306 0 : if(e - i > XDL_SIMSCAN_WINDOW)
1307 : {
1308 0 : e = i + XDL_SIMSCAN_WINDOW;
1309 : }
1310 :
1311 : /*
1312 : * Scans the lines before 'i' to find a run of lines that either
1313 : * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).
1314 : * Note that we always call this function with dis[i] > 1, so the
1315 : * current line (i) is already a multimatch line.
1316 : */
1317 0 : for(r = 1,rdis0 = 0,rpdis0 = 1; (i - r) >= s; r++)
1318 : {
1319 0 : if(!dis[i - r])
1320 : {
1321 0 : rdis0++;
1322 0 : } else if(dis[i - r] == 2){
1323 0 : rpdis0++;
1324 : } else {
1325 0 : break;
1326 : }
1327 : }
1328 :
1329 : /*
1330 : * If the run before the line 'i' found only multimatch lines, we
1331 : * return 0 and hence we don't make the current line (i) discarded.
1332 : * We want to discard multimatch lines only when they appear in the
1333 : * middle of runs with nomatch lines (dis[j] == 0).
1334 : */
1335 0 : if(rdis0 == 0)
1336 : {
1337 0 : return 0;
1338 : }
1339 :
1340 0 : for(r = 1,rdis1 = 0,rpdis1 = 1; (i + r) <= e; r++)
1341 : {
1342 0 : if(!dis[i + r])
1343 : {
1344 0 : rdis1++;
1345 0 : } else if(dis[i + r] == 2){
1346 0 : rpdis1++;
1347 : } else {
1348 0 : break;
1349 : }
1350 : }
1351 :
1352 : /*
1353 : * If the run after the line 'i' found only multimatch lines, we
1354 : * return 0 and hence we don't make the current line (i) discarded.
1355 : */
1356 0 : if(rdis1 == 0)
1357 : {
1358 0 : return 0;
1359 : }
1360 0 : rdis1 += rdis0;
1361 0 : rpdis1 += rpdis0;
1362 :
1363 0 : return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
1364 : }
1365 :
1366 : /*
1367 : * Try to reduce the problem complexity, discard records that have no
1368 : * matches on the other file. Also, lines that have multiple matches
1369 : * might be potentially discarded if they appear in a run of discardable.
1370 : */
1371 8 : static int xdl_cleanup_records(
1372 : xdfile_t *xdf1,
1373 : xdfile_t *xdf2)
1374 : {
1375 : long i,nm,rhi,nreff,mlim;
1376 : unsigned long hav;
1377 : xrecord_t **recs;
1378 : xrecord_t *rec;
1379 : char *dis,*dis1,*dis2;
1380 :
1381 8 : if(!(dis = (char *)malloc(xdf1->nrec + xdf2->nrec + 2)))
1382 : {
1383 0 : return -1;
1384 : }
1385 8 : memset(dis,0,xdf1->nrec + xdf2->nrec + 2);
1386 8 : dis1 = dis;
1387 8 : dis2 = dis1 + xdf1->nrec + 1;
1388 :
1389 8 : if((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
1390 : {
1391 0 : mlim = XDL_MAX_EQLIMIT;
1392 : }
1393 :
1394 416 : for(i = xdf1->dstart,recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend;
1395 408 : i++,recs++)
1396 : {
1397 408 : hav = (*recs)->ha;
1398 408 : rhi = (long)XDL_HASHLONG(hav,xdf2->hbits);
1399 :
1400 776 : for(nm = 0,rec = xdf2->rhash[rhi]; rec; rec = rec->next)
1401 : {
1402 368 : if(rec->ha == hav && ++nm == mlim)
1403 : {
1404 0 : break;
1405 : }
1406 : }
1407 408 : dis1[i] = (nm == 0) ? 0 : (nm >= mlim) ? 2 : 1;
1408 : }
1409 :
1410 8 : if((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
1411 : {
1412 0 : mlim = XDL_MAX_EQLIMIT;
1413 : }
1414 :
1415 426 : for(i = xdf2->dstart,recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend;
1416 418 : i++,recs++)
1417 : {
1418 418 : hav = (*recs)->ha;
1419 418 : rhi = (long)XDL_HASHLONG(hav,xdf1->hbits);
1420 :
1421 794 : for(nm = 0,rec = xdf1->rhash[rhi]; rec; rec = rec->next)
1422 : {
1423 376 : if(rec->ha == hav && ++nm == mlim)
1424 : {
1425 0 : break;
1426 : }
1427 : }
1428 418 : dis2[i] = (nm == 0) ? 0 : (nm >= mlim) ? 2 : 1;
1429 : }
1430 :
1431 8 : for(nreff = 0,i = xdf1->dstart,recs = &xdf1->recs[xdf1->dstart];
1432 416 : i <= xdf1->dend;
1433 408 : i++,recs++)
1434 : {
1435 408 : if(dis1[i] == 1 ||
1436 52 : (dis1[i] == 2 &&
1437 0 : !xdl_clean_mmatch(dis1,i,xdf1->dstart,xdf1->dend)))
1438 : {
1439 356 : xdf1->rindex[nreff] = i;
1440 356 : xdf1->ha[nreff] = (*recs)->ha;
1441 356 : nreff++;
1442 : } else {
1443 52 : xdf1->rchg[i] = 1;
1444 : }
1445 : }
1446 8 : xdf1->nreff = nreff;
1447 :
1448 8 : for(nreff = 0,i = xdf2->dstart,recs = &xdf2->recs[xdf2->dstart];
1449 426 : i <= xdf2->dend;
1450 418 : i++,recs++)
1451 : {
1452 418 : if(dis2[i] == 1 ||
1453 56 : (dis2[i] == 2 &&
1454 0 : !xdl_clean_mmatch(dis2,i,xdf2->dstart,xdf2->dend)))
1455 : {
1456 362 : xdf2->rindex[nreff] = i;
1457 362 : xdf2->ha[nreff] = (*recs)->ha;
1458 362 : nreff++;
1459 : } else {
1460 56 : xdf2->rchg[i] = 1;
1461 : }
1462 : }
1463 8 : xdf2->nreff = nreff;
1464 :
1465 8 : free(dis);
1466 :
1467 8 : return 0;
1468 : }
1469 :
1470 : /*
1471 : * Early trim initial and terminal matching records.
1472 : */
1473 8 : static int xdl_trim_ends(
1474 : xdfile_t *xdf1,
1475 : xdfile_t *xdf2)
1476 : {
1477 : long i,lim;
1478 : xrecord_t **recs1,**recs2;
1479 :
1480 8 : recs1 = xdf1->recs;
1481 8 : recs2 = xdf2->recs;
1482 :
1483 66 : for(i = 0,lim = XDL_MIN(xdf1->nrec,xdf2->nrec); i < lim;
1484 58 : i++,recs1++,recs2++)
1485 : {
1486 66 : if((*recs1)->ha != (*recs2)->ha)
1487 : {
1488 8 : break;
1489 : }
1490 : }
1491 :
1492 8 : xdf1->dstart = xdf2->dstart = i;
1493 :
1494 8 : recs1 = xdf1->recs + xdf1->nrec - 1;
1495 8 : recs2 = xdf2->recs + xdf2->nrec - 1;
1496 :
1497 24 : for(lim -= i,i = 0; i < lim; i++,recs1--,recs2--)
1498 : {
1499 24 : if((*recs1)->ha != (*recs2)->ha)
1500 : {
1501 8 : break;
1502 : }
1503 : }
1504 :
1505 8 : xdf1->dend = xdf1->nrec - i - 1;
1506 8 : xdf2->dend = xdf2->nrec - i - 1;
1507 :
1508 8 : return 0;
1509 : }
1510 :
1511 8 : static int xdl_optimize_ctxs(
1512 : xdfile_t *xdf1,
1513 : xdfile_t *xdf2)
1514 : {
1515 8 : if(xdl_trim_ends(xdf1,xdf2) < 0 || xdl_cleanup_records(xdf1,xdf2) < 0)
1516 : {
1517 0 : return -1;
1518 : }
1519 :
1520 8 : return 0;
1521 : }
1522 :
1523 8 : int xdl_prepare_env(
1524 : mmfile_t *mf1,
1525 : mmfile_t *mf2,
1526 : xdfenv_t *xe)
1527 : {
1528 : long enl1,enl2;
1529 : xdlclassifier_t cf;
1530 :
1531 8 : enl1 = xdl_guess_lines(mf1) + 1;
1532 8 : enl2 = xdl_guess_lines(mf2) + 1;
1533 :
1534 8 : if(xdl_init_classifier(&cf,enl1 + enl2 + 1) < 0)
1535 : {
1536 0 : return -1;
1537 : }
1538 :
1539 8 : if(xdl_prepare_ctx(mf1,enl1,&cf,&xe->xdf1) < 0)
1540 : {
1541 :
1542 0 : xdl_free_classifier(&cf);
1543 0 : return -1;
1544 : }
1545 :
1546 8 : if(xdl_prepare_ctx(mf2,enl2,&cf,&xe->xdf2) < 0)
1547 : {
1548 :
1549 0 : xdl_free_ctx(&xe->xdf1);
1550 0 : xdl_free_classifier(&cf);
1551 0 : return -1;
1552 : }
1553 :
1554 8 : xdl_free_classifier(&cf);
1555 :
1556 8 : if(xdl_optimize_ctxs(&xe->xdf1,&xe->xdf2) < 0)
1557 : {
1558 :
1559 0 : xdl_free_ctx(&xe->xdf2);
1560 0 : xdl_free_ctx(&xe->xdf1);
1561 0 : return -1;
1562 : }
1563 :
1564 8 : return 0;
1565 : }
1566 :
1567 8 : void xdl_free_env(xdfenv_t *xe)
1568 : {
1569 8 : xdl_free_ctx(&xe->xdf2);
1570 8 : xdl_free_ctx(&xe->xdf1);
1571 8 : }
1572 :
1573 0 : int xdlt_load_mmfile(
1574 : char const *fname,
1575 : mmfile_t *mf)
1576 : {
1577 : int fd;
1578 : long size;
1579 : char *blk;
1580 :
1581 0 : if(xdl_init_mmfile(mf,XDLT_STD_BLKSIZE,XDL_MMF_ATOMIC) < 0)
1582 : {
1583 0 : return -1;
1584 : }
1585 :
1586 0 : if((fd = open(fname,O_RDONLY)) == -1)
1587 : {
1588 0 : perror(fname);
1589 0 : xdl_free_mmfile(mf);
1590 0 : return -1;
1591 : }
1592 0 : size = lseek(fd,0,SEEK_END);
1593 0 : lseek(fd,0,SEEK_SET);
1594 :
1595 0 : if(!(blk = (char *)xdl_mmfile_writeallocate(mf,size)))
1596 : {
1597 0 : xdl_free_mmfile(mf);
1598 0 : close(fd);
1599 0 : return -1;
1600 : }
1601 :
1602 0 : if(read(fd,blk,(size_t)size) != (ssize_t)size)
1603 : {
1604 0 : perror(fname);
1605 0 : xdl_free_mmfile(mf);
1606 0 : close(fd);
1607 0 : return -1;
1608 : }
1609 0 : close(fd);
1610 :
1611 0 : return 0;
1612 : }
1613 :
1614 24 : long xdl_bogosqrt(long n)
1615 : {
1616 : long i;
1617 :
1618 : /*
1619 : * Classical integer square root approximation using shifts.
1620 : */
1621 110 : for(i = 1; n > 0; n >>= 2)
1622 : {
1623 86 : i <<= 1;
1624 : }
1625 :
1626 24 : return i;
1627 : }
1628 :
1629 114 : int xdl_emit_diffrec(
1630 : char const *rec,
1631 : long size,
1632 : char const *pre,
1633 : long psize,
1634 : xdemitcb_t *ecb)
1635 : {
1636 114 : int i = 2;
1637 : mmbuffer_t mb[3];
1638 :
1639 114 : mb[0].ptr = (char *)pre;
1640 114 : mb[0].size = psize;
1641 114 : mb[1].ptr = (char *)rec;
1642 114 : mb[1].size = size;
1643 :
1644 114 : if(size > 0 && rec[size - 1] != '\n')
1645 : {
1646 0 : mb[2].ptr = (char *)"\n\\ No newline at end of file\n";
1647 0 : mb[2].size = strlen(mb[2].ptr);
1648 0 : i++;
1649 : }
1650 :
1651 114 : if(ecb->outf(ecb->priv,mb,i) < 0)
1652 : {
1653 0 : return -1;
1654 : }
1655 :
1656 114 : return 0;
1657 : }
1658 :
1659 16 : int xdl_init_mmfile(
1660 : mmfile_t *mmf,
1661 : long bsize,
1662 : unsigned long flags)
1663 : {
1664 :
1665 16 : mmf->flags = flags;
1666 16 : mmf->head = mmf->tail = NULL;
1667 16 : mmf->bsize = bsize;
1668 16 : mmf->fsize = 0;
1669 16 : mmf->rcur = mmf->wcur = NULL;
1670 16 : mmf->rpos = 0;
1671 :
1672 16 : return 0;
1673 : }
1674 :
1675 16 : void xdl_free_mmfile(mmfile_t *mmf)
1676 : {
1677 : mmblock_t *cur,*tmp;
1678 :
1679 32 : for(cur = mmf->head; (tmp = cur) != NULL;)
1680 : {
1681 16 : cur = cur->next;
1682 16 : free(tmp);
1683 : }
1684 16 : }
1685 :
1686 16 : void *xdl_mmfile_writeallocate(
1687 : mmfile_t *mmf,
1688 : long size)
1689 : {
1690 : long bsize;
1691 : mmblock_t *wcur;
1692 : char *blk;
1693 :
1694 16 : if(!(wcur = mmf->wcur) || wcur->size + size > wcur->bsize)
1695 : {
1696 16 : bsize = XDL_MAX(mmf->bsize,size);
1697 :
1698 16 : if(!(wcur = (mmblock_t *)malloc(sizeof(mmblock_t) + bsize)))
1699 : {
1700 0 : return NULL;
1701 : }
1702 16 : wcur->flags = 0;
1703 16 : wcur->ptr = (char *)wcur + sizeof(mmblock_t);
1704 16 : wcur->size = 0;
1705 16 : wcur->bsize = bsize;
1706 16 : wcur->next = NULL;
1707 :
1708 16 : if(!mmf->head)
1709 : {
1710 16 : mmf->head = wcur;
1711 : }
1712 :
1713 16 : if(mmf->tail)
1714 : {
1715 0 : mmf->tail->next = wcur;
1716 : }
1717 16 : mmf->tail = wcur;
1718 16 : mmf->wcur = wcur;
1719 : }
1720 :
1721 16 : blk = wcur->ptr + wcur->size;
1722 16 : wcur->size += size;
1723 16 : mmf->fsize += size;
1724 :
1725 16 : return blk;
1726 : }
1727 :
1728 32 : void *xdl_mmfile_first(
1729 : mmfile_t *mmf,
1730 : long *size)
1731 : {
1732 :
1733 32 : if(!(mmf->rcur = mmf->head))
1734 : {
1735 0 : return NULL;
1736 : }
1737 :
1738 32 : *size = mmf->rcur->size;
1739 :
1740 32 : return mmf->rcur->ptr;
1741 : }
1742 :
1743 32 : void *xdl_mmfile_next(
1744 : mmfile_t *mmf,
1745 : long *size)
1746 : {
1747 :
1748 32 : if(!mmf->rcur || !(mmf->rcur = mmf->rcur->next))
1749 : {
1750 32 : return NULL;
1751 : }
1752 :
1753 0 : *size = mmf->rcur->size;
1754 :
1755 0 : return mmf->rcur->ptr;
1756 : }
1757 :
1758 16 : long xdl_mmfile_size(mmfile_t *mmf)
1759 : {
1760 16 : return mmf->fsize;
1761 : }
1762 :
1763 24 : int xdl_cha_init(
1764 : chastore_t *cha,
1765 : long isize,
1766 : long icount)
1767 : {
1768 :
1769 24 : cha->head = cha->tail = NULL;
1770 24 : cha->isize = isize;
1771 24 : cha->nsize = icount * isize;
1772 24 : cha->ancur = cha->sncur = NULL;
1773 24 : cha->scurr = 0;
1774 :
1775 24 : return 0;
1776 : }
1777 :
1778 24 : void xdl_cha_free(chastore_t *cha)
1779 : {
1780 : chanode_t *cur,*tmp;
1781 :
1782 106 : for(cur = cha->head; (tmp = cur) != NULL;)
1783 : {
1784 82 : cur = cur->next;
1785 82 : free(tmp);
1786 : }
1787 24 : }
1788 :
1789 1510 : void *xdl_cha_alloc(chastore_t *cha)
1790 : {
1791 : chanode_t *ancur;
1792 : void *data;
1793 :
1794 1510 : if(!(ancur = cha->ancur) || ancur->icurr == cha->nsize)
1795 : {
1796 82 : if(!(ancur = (chanode_t *)malloc(sizeof(chanode_t) + cha->nsize)))
1797 : {
1798 0 : return NULL;
1799 : }
1800 82 : ancur->icurr = 0;
1801 82 : ancur->next = NULL;
1802 :
1803 82 : if(cha->tail)
1804 : {
1805 58 : cha->tail->next = ancur;
1806 : }
1807 :
1808 82 : if(!cha->head)
1809 : {
1810 24 : cha->head = ancur;
1811 : }
1812 82 : cha->tail = ancur;
1813 82 : cha->ancur = ancur;
1814 : }
1815 :
1816 1510 : data = (char *)ancur + sizeof(chanode_t) + ancur->icurr;
1817 1510 : ancur->icurr += cha->isize;
1818 :
1819 1510 : return data;
1820 : }
1821 :
1822 16 : long xdl_guess_lines(mmfile_t *mf)
1823 : {
1824 16 : long nl = 0,size,tsize = 0;
1825 : char const *data,*cur,*top;
1826 :
1827 16 : if((cur = data = xdl_mmfile_first(mf,&size)) != NULL)
1828 : {
1829 990 : for(top = data + size; nl < XDL_GUESS_NLINES;)
1830 : {
1831 990 : if(cur >= top)
1832 : {
1833 16 : tsize += (long)(cur - data);
1834 :
1835 16 : if(!(cur = data = xdl_mmfile_next(mf,&size)))
1836 : {
1837 16 : break;
1838 : }
1839 0 : top = data + size;
1840 : }
1841 974 : nl++;
1842 :
1843 974 : if(!(cur = memchr(cur,'\n',top - cur)))
1844 : {
1845 16 : cur = top;
1846 : } else {
1847 958 : cur++;
1848 : }
1849 : }
1850 16 : tsize += (long)(cur - data);
1851 : }
1852 :
1853 16 : if(nl && tsize)
1854 : {
1855 16 : nl = xdl_mmfile_size(mf) / (tsize / nl);
1856 : }
1857 :
1858 16 : return nl + 1;
1859 : }
1860 :
1861 974 : unsigned long xdl_hash_record(
1862 : char const **data,
1863 : char const *top)
1864 : {
1865 974 : unsigned long ha = 5381;
1866 974 : char const *ptr = *data;
1867 :
1868 58416 : for(; ptr < top && *ptr != '\n'; ptr++)
1869 : {
1870 57442 : ha += (ha << 5);
1871 57442 : ha ^= (unsigned long)*ptr;
1872 : }
1873 974 : *data = ptr < top ? ptr + 1 : ptr;
1874 :
1875 974 : return ha;
1876 : }
1877 :
1878 24 : unsigned int xdl_hashbits(unsigned int size)
1879 : {
1880 24 : unsigned int val = 1,bits = 0;
1881 :
1882 188 : for(; val < size && bits < CHAR_BIT * sizeof(unsigned int);
1883 164 : val <<= 1,bits++)
1884 : {
1885 : ;
1886 : }
1887 24 : return bits ? bits : 1;
1888 : }
1889 :
1890 0 : int xdl_num_out(
1891 : char *out,
1892 : long val)
1893 : {
1894 0 : char *ptr,*str = out;
1895 : char buf[32];
1896 :
1897 0 : ptr = buf + sizeof(buf) - 1;
1898 0 : *ptr = '\0';
1899 :
1900 0 : if(val < 0)
1901 : {
1902 0 : *--ptr = '-';
1903 0 : val = -val;
1904 : }
1905 :
1906 0 : for(; val && ptr > buf; val /= 10)
1907 : {
1908 0 : *--ptr = "0123456789"[val % 10];
1909 : }
1910 :
1911 0 : if(*ptr)
1912 : {
1913 0 : for(; *ptr; ptr++,str++)
1914 : {
1915 0 : *str = *ptr;
1916 : }
1917 : } else {
1918 0 : *str++ = '0';
1919 : }
1920 0 : *str = '\0';
1921 :
1922 0 : return str - out;
1923 : }
1924 :
1925 0 : int xdl_emit_hunk_hdr(
1926 : long s1,
1927 : long c1,
1928 : long s2,
1929 : long c2,
1930 : xdemitcb_t *ecb)
1931 : {
1932 0 : int nb = 0;
1933 : mmbuffer_t mb;
1934 : char buf[128];
1935 :
1936 0 : memcpy(buf,"@@ -",4);
1937 0 : nb += 4;
1938 :
1939 0 : nb += xdl_num_out(buf + nb,c1 ? s1 : s1 - 1);
1940 :
1941 0 : memcpy(buf + nb,",",1);
1942 0 : nb += 1;
1943 :
1944 0 : nb += xdl_num_out(buf + nb,c1);
1945 :
1946 0 : memcpy(buf + nb," +",2);
1947 0 : nb += 2;
1948 :
1949 0 : nb += xdl_num_out(buf + nb,c2 ? s2 : s2 - 1);
1950 :
1951 0 : memcpy(buf + nb,",",1);
1952 0 : nb += 1;
1953 :
1954 0 : nb += xdl_num_out(buf + nb,c2);
1955 :
1956 0 : memcpy(buf + nb," @@\n",4);
1957 0 : nb += 4;
1958 :
1959 0 : mb.ptr = buf;
1960 0 : mb.size = nb;
1961 :
1962 0 : if(ecb->outf(ecb->priv,&mb,1) < 0)
1963 : {
1964 0 : return -1;
1965 : }
1966 :
1967 0 : return 0;
1968 : }
1969 :
1970 : #if 0
1971 : int main(
1972 : int argc,
1973 : char *argv[])
1974 : {
1975 : int i = 1,ctxlen = 3;
1976 : mmfile_t mf1,mf2;
1977 : xpparam_t xpp;
1978 : xdemitconf_t xecfg;
1979 : xdemitcb_t ecb;
1980 :
1981 : if(!strcmp(argv[i],"--diff"))
1982 : {
1983 : i++;
1984 :
1985 : for(; i < argc; i++)
1986 : {
1987 : if(strcmp(argv[i],"-C") == 0)
1988 : {
1989 : if(++i < argc)
1990 : {
1991 : ctxlen = atoi(argv[i]);
1992 : }
1993 : } else {
1994 : break;
1995 : }
1996 : }
1997 : }
1998 :
1999 : xpp.flags = 0;
2000 : xecfg.ctxlen = ctxlen;
2001 :
2002 : if(xdlt_load_mmfile(argv[i],&mf1) < 0)
2003 : {
2004 : return 2;
2005 : }
2006 :
2007 : if(xdlt_load_mmfile(argv[i + 1],&mf2) < 0)
2008 : {
2009 : xdl_free_mmfile(&mf1);
2010 : return 2;
2011 : }
2012 :
2013 : ecb.priv = stdout;
2014 :
2015 : if(xdl_diff(&mf1,&mf2,&xpp,&xecfg,&ecb) < 0)
2016 : {
2017 : xdl_free_mmfile(&mf2);
2018 : xdl_free_mmfile(&mf1);
2019 : return 3;
2020 : }
2021 :
2022 : xdl_free_mmfile(&mf2);
2023 : xdl_free_mmfile(&mf1);
2024 :
2025 : return 0;
2026 : }
2027 : #endif
|
