aboutsummaryrefslogtreecommitdiff
path: root/xdiff
diff options
context:
space:
mode:
Diffstat (limited to 'xdiff')
-rw-r--r--xdiff/xdiff.h98
-rw-r--r--xdiff/xdiffi.c569
-rw-r--r--xdiff/xdiffi.h59
-rw-r--r--xdiff/xemit.c197
-rw-r--r--xdiff/xemit.h34
-rw-r--r--xdiff/xinclude.h43
-rw-r--r--xdiff/xmacros.h54
-rw-r--r--xdiff/xprepare.c469
-rw-r--r--xdiff/xprepare.h35
-rw-r--r--xdiff/xtypes.h68
-rw-r--r--xdiff/xutils.c340
-rw-r--r--xdiff/xutils.h48
12 files changed, 2014 insertions, 0 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h
new file mode 100644
index 000000000..c9f817818
--- /dev/null
+++ b/xdiff/xdiff.h
@@ -0,0 +1,98 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#if !defined(XDIFF_H)
+#define XDIFF_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif /* #ifdef __cplusplus */
+
+
+#define XDF_NEED_MINIMAL (1 << 1)
+#define XDF_IGNORE_WHITESPACE (1 << 2)
+#define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3)
+#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE)
+
+#define XDL_PATCH_NORMAL '-'
+#define XDL_PATCH_REVERSE '+'
+#define XDL_PATCH_MODEMASK ((1 << 8) - 1)
+#define XDL_PATCH_IGNOREBSPACE (1 << 8)
+
+#define XDL_EMIT_FUNCNAMES (1 << 0)
+#define XDL_EMIT_COMMON (1 << 1)
+
+#define XDL_MMB_READONLY (1 << 0)
+
+#define XDL_MMF_ATOMIC (1 << 0)
+
+#define XDL_BDOP_INS 1
+#define XDL_BDOP_CPY 2
+#define XDL_BDOP_INSB 3
+
+
+typedef struct s_mmfile {
+ char *ptr;
+ long size;
+} mmfile_t;
+
+typedef struct s_mmbuffer {
+ char *ptr;
+ long size;
+} mmbuffer_t;
+
+typedef struct s_xpparam {
+ unsigned long flags;
+} xpparam_t;
+
+typedef struct s_xdemitcb {
+ void *priv;
+ int (*outf)(void *, mmbuffer_t *, int);
+} xdemitcb_t;
+
+typedef struct s_xdemitconf {
+ long ctxlen;
+ unsigned long flags;
+} xdemitconf_t;
+
+typedef struct s_bdiffparam {
+ long bsize;
+} bdiffparam_t;
+
+
+#define xdl_malloc(x) malloc(x)
+#define xdl_free(ptr) free(ptr)
+#define xdl_realloc(ptr,x) realloc(ptr,x)
+
+void *xdl_mmfile_first(mmfile_t *mmf, long *size);
+void *xdl_mmfile_next(mmfile_t *mmf, long *size);
+long xdl_mmfile_size(mmfile_t *mmf);
+
+int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+ xdemitconf_t const *xecfg, xdemitcb_t *ecb);
+
+#ifdef __cplusplus
+}
+#endif /* #ifdef __cplusplus */
+
+#endif /* #if !defined(XDIFF_H) */
+
diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
new file mode 100644
index 000000000..d76e76a0e
--- /dev/null
+++ b/xdiff/xdiffi.c
@@ -0,0 +1,569 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#include "xinclude.h"
+
+
+
+#define XDL_MAX_COST_MIN 256
+#define XDL_HEUR_MIN_COST 256
+#define XDL_LINE_MAX (long)((1UL << (8 * sizeof(long) - 1)) - 1)
+#define XDL_SNAKE_CNT 20
+#define XDL_K_HEUR 4
+
+
+
+typedef struct s_xdpsplit {
+ long i1, i2;
+ int min_lo, min_hi;
+} xdpsplit_t;
+
+
+
+
+static long 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);
+static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2);
+static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags);
+
+
+
+
+
+/*
+ * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
+ * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
+ * the forward diagonal starting from (off1, off2) and the backward diagonal
+ * starting from (lim1, lim2). If the K values on the same diagonal crosses
+ * returns the furthest point of reach. We might end up having to expensive
+ * cases using this algorithm is full, so a little bit of heuristic is needed
+ * to cut the search and to return a suboptimal point.
+ */
+static long 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) {
+ long dmin = off1 - lim2, dmax = lim1 - off2;
+ long fmid = off1 - off2, bmid = lim1 - lim2;
+ long odd = (fmid - bmid) & 1;
+ long fmin = fmid, fmax = fmid;
+ long bmin = bmid, bmax = bmid;
+ long ec, d, i1, i2, prev1, best, dd, v, k;
+
+ /*
+ * Set initial diagonal values for both forward and backward path.
+ */
+ kvdf[fmid] = off1;
+ kvdb[bmid] = lim1;
+
+ for (ec = 1;; ec++) {
+ int got_snake = 0;
+
+ /*
+ * We need to extent the diagonal "domain" by one. If the next
+ * values exits the box boundaries we need to change it in the
+ * opposite direction because (max - min) must be a power of two.
+ * Also we initialize the external K value to -1 so that we can
+ * avoid extra conditions check inside the core loop.
+ */
+ if (fmin > dmin)
+ kvdf[--fmin - 1] = -1;
+ else
+ ++fmin;
+ if (fmax < dmax)
+ kvdf[++fmax + 1] = -1;
+ else
+ --fmax;
+
+ for (d = fmax; d >= fmin; d -= 2) {
+ if (kvdf[d - 1] >= kvdf[d + 1])
+ i1 = kvdf[d - 1] + 1;
+ else
+ i1 = kvdf[d + 1];
+ prev1 = i1;
+ i2 = i1 - d;
+ for (; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++, i2++);
+ if (i1 - prev1 > xenv->snake_cnt)
+ got_snake = 1;
+ kvdf[d] = i1;
+ if (odd && bmin <= d && d <= bmax && kvdb[d] <= i1) {
+ spl->i1 = i1;
+ spl->i2 = i2;
+ spl->min_lo = spl->min_hi = 1;
+ return ec;
+ }
+ }
+
+ /*
+ * We need to extent the diagonal "domain" by one. If the next
+ * values exits the box boundaries we need to change it in the
+ * opposite direction because (max - min) must be a power of two.
+ * Also we initialize the external K value to -1 so that we can
+ * avoid extra conditions check inside the core loop.
+ */
+ if (bmin > dmin)
+ kvdb[--bmin - 1] = XDL_LINE_MAX;
+ else
+ ++bmin;
+ if (bmax < dmax)
+ kvdb[++bmax + 1] = XDL_LINE_MAX;
+ else
+ --bmax;
+
+ for (d = bmax; d >= bmin; d -= 2) {
+ if (kvdb[d - 1] < kvdb[d + 1])
+ i1 = kvdb[d - 1];
+ else
+ i1 = kvdb[d + 1] - 1;
+ prev1 = i1;
+ i2 = i1 - d;
+ for (; i1 > off1 && i2 > off2 && ha1[i1 - 1] == ha2[i2 - 1]; i1--, i2--);
+ if (prev1 - i1 > xenv->snake_cnt)
+ got_snake = 1;
+ kvdb[d] = i1;
+ if (!odd && fmin <= d && d <= fmax && i1 <= kvdf[d]) {
+ spl->i1 = i1;
+ spl->i2 = i2;
+ spl->min_lo = spl->min_hi = 1;
+ return ec;
+ }
+ }
+
+ if (need_min)
+ continue;
+
+ /*
+ * If the edit cost is above the heuristic trigger and if
+ * we got a good snake, we sample current diagonals to see
+ * if some of the, have reached an "interesting" path. Our
+ * measure is a function of the distance from the diagonal
+ * corner (i1 + i2) penalized with the distance from the
+ * mid diagonal itself. If this value is above the current
+ * edit cost times a magic factor (XDL_K_HEUR) we consider
+ * it interesting.
+ */
+ if (got_snake && ec > xenv->heur_min) {
+ for (best = 0, d = fmax; d >= fmin; d -= 2) {
+ dd = d > fmid ? d - fmid: fmid - d;
+ i1 = kvdf[d];
+ i2 = i1 - d;
+ v = (i1 - off1) + (i2 - off2) - dd;
+
+ if (v > XDL_K_HEUR * ec && v > best &&
+ off1 + xenv->snake_cnt <= i1 && i1 < lim1 &&
+ off2 + xenv->snake_cnt <= i2 && i2 < lim2) {
+ for (k = 1; ha1[i1 - k] == ha2[i2 - k]; k++)
+ if (k == xenv->snake_cnt) {
+ best = v;
+ spl->i1 = i1;
+ spl->i2 = i2;
+ break;
+ }
+ }
+ }
+ if (best > 0) {
+ spl->min_lo = 1;
+ spl->min_hi = 0;
+ return ec;
+ }
+
+ for (best = 0, d = bmax; d >= bmin; d -= 2) {
+ dd = d > bmid ? d - bmid: bmid - d;
+ i1 = kvdb[d];
+ i2 = i1 - d;
+ v = (lim1 - i1) + (lim2 - i2) - dd;
+
+ if (v > XDL_K_HEUR * ec && v > best &&
+ off1 < i1 && i1 <= lim1 - xenv->snake_cnt &&
+ off2 < i2 && i2 <= lim2 - xenv->snake_cnt) {
+ for (k = 0; ha1[i1 + k] == ha2[i2 + k]; k++)
+ if (k == xenv->snake_cnt - 1) {
+ best = v;
+ spl->i1 = i1;
+ spl->i2 = i2;
+ break;
+ }
+ }
+ }
+ if (best > 0) {
+ spl->min_lo = 0;
+ spl->min_hi = 1;
+ return ec;
+ }
+ }
+
+ /*
+ * Enough is enough. We spent too much time here and now we collect
+ * the furthest reaching path using the (i1 + i2) measure.
+ */
+ if (ec >= xenv->mxcost) {
+ long fbest, fbest1, bbest, bbest1;
+
+ fbest = fbest1 = -1;
+ for (d = fmax; d >= fmin; d -= 2) {
+ i1 = XDL_MIN(kvdf[d], lim1);
+ i2 = i1 - d;
+ if (lim2 < i2)
+ i1 = lim2 + d, i2 = lim2;
+ if (fbest < i1 + i2) {
+ fbest = i1 + i2;
+ fbest1 = i1;
+ }
+ }
+
+ bbest = bbest1 = XDL_LINE_MAX;
+ for (d = bmax; d >= bmin; d -= 2) {
+ i1 = XDL_MAX(off1, kvdb[d]);
+ i2 = i1 - d;
+ if (i2 < off2)
+ i1 = off2 + d, i2 = off2;
+ if (i1 + i2 < bbest) {
+ bbest = i1 + i2;
+ bbest1 = i1;
+ }
+ }
+
+ if ((lim1 + lim2) - bbest < fbest - (off1 + off2)) {
+ spl->i1 = fbest1;
+ spl->i2 = fbest - fbest1;
+ spl->min_lo = 1;
+ spl->min_hi = 0;
+ } else {
+ spl->i1 = bbest1;
+ spl->i2 = bbest - bbest1;
+ spl->min_lo = 0;
+ spl->min_hi = 1;
+ }
+ return ec;
+ }
+ }
+
+ return -1;
+}
+
+
+/*
+ * Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling
+ * the box splitting function. Note that the real job (marking changed lines)
+ * is done in the two boundary reaching checks.
+ */
+int 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) {
+ unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha;
+
+ /*
+ * Shrink the box by walking through each diagonal snake (SW and NE).
+ */
+ for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++);
+ for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--);
+
+ /*
+ * If one dimension is empty, then all records on the other one must
+ * be obviously changed.
+ */
+ if (off1 == lim1) {
+ char *rchg2 = dd2->rchg;
+ long *rindex2 = dd2->rindex;
+
+ for (; off2 < lim2; off2++)
+ rchg2[rindex2[off2]] = 1;
+ } else if (off2 == lim2) {
+ char *rchg1 = dd1->rchg;
+ long *rindex1 = dd1->rindex;
+
+ for (; off1 < lim1; off1++)
+ rchg1[rindex1[off1]] = 1;
+ } else {
+ long ec;
+ xdpsplit_t spl;
+ spl.i1 = spl.i2 = 0;
+
+ /*
+ * Divide ...
+ */
+ if ((ec = xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb,
+ need_min, &spl, xenv)) < 0) {
+
+ return -1;
+ }
+
+ /*
+ * ... et Impera.
+ */
+ if (xdl_recs_cmp(dd1, off1, spl.i1, dd2, off2, spl.i2,
+ kvdf, kvdb, spl.min_lo, xenv) < 0 ||
+ xdl_recs_cmp(dd1, spl.i1, lim1, dd2, spl.i2, lim2,
+ kvdf, kvdb, spl.min_hi, xenv) < 0) {
+
+ return -1;
+ }
+ }
+
+ return 0;
+}
+
+
+int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+ xdfenv_t *xe) {
+ long ndiags;
+ long *kvd, *kvdf, *kvdb;
+ xdalgoenv_t xenv;
+ diffdata_t dd1, dd2;
+
+ if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
+
+ return -1;
+ }
+
+ /*
+ * Allocate and setup K vectors to be used by the differential algorithm.
+ * One is to store the forward path and one to store the backward path.
+ */
+ ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
+ if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {
+
+ xdl_free_env(xe);
+ return -1;
+ }
+ kvdf = kvd;
+ kvdb = kvdf + ndiags;
+ kvdf += xe->xdf2.nreff + 1;
+ kvdb += xe->xdf2.nreff + 1;
+
+ xenv.mxcost = xdl_bogosqrt(ndiags);
+ if (xenv.mxcost < XDL_MAX_COST_MIN)
+ xenv.mxcost = XDL_MAX_COST_MIN;
+ xenv.snake_cnt = XDL_SNAKE_CNT;
+ xenv.heur_min = XDL_HEUR_MIN_COST;
+
+ dd1.nrec = xe->xdf1.nreff;
+ dd1.ha = xe->xdf1.ha;
+ dd1.rchg = xe->xdf1.rchg;
+ dd1.rindex = xe->xdf1.rindex;
+ dd2.nrec = xe->xdf2.nreff;
+ dd2.ha = xe->xdf2.ha;
+ dd2.rchg = xe->xdf2.rchg;
+ dd2.rindex = xe->xdf2.rindex;
+
+ if (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec,
+ kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) {
+
+ xdl_free(kvd);
+ xdl_free_env(xe);
+ return -1;
+ }
+
+ xdl_free(kvd);
+
+ return 0;
+}
+
+
+static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) {
+ xdchange_t *xch;
+
+ if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t))))
+ return NULL;
+
+ xch->next = xscr;
+ xch->i1 = i1;
+ xch->i2 = i2;
+ xch->chg1 = chg1;
+ xch->chg2 = chg2;
+
+ return xch;
+}
+
+
+static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
+ long ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;
+ char *rchg = xdf->rchg, *rchgo = xdfo->rchg;
+ xrecord_t **recs = xdf->recs;
+
+ /*
+ * This is the same of what GNU diff does. Move back and forward
+ * change groups for a consistent and pretty diff output. This also
+ * helps in finding joinable change groups and reduce the diff size.
+ */
+ for (ix = ixo = 0;;) {
+ /*
+ * Find the first changed line in the to-be-compacted file.
+ * We need to keep track of both indexes, so if we find a
+ * changed lines group on the other file, while scanning the
+ * to-be-compacted file, we need to skip it properly. Note
+ * that loops that are testing for changed lines on rchg* do
+ * not need index bounding since the array is prepared with
+ * a zero at position -1 and N.
+ */
+ for (; ix < nrec && !rchg[ix]; ix++)
+ while (rchgo[ixo++]);
+ if (ix == nrec)
+ break;
+
+ /*
+ * Record the start of a changed-group in the to-be-compacted file
+ * and find the end of it, on both to-be-compacted and other file
+ * indexes (ix and ixo).
+ */
+ ixs = ix;
+ for (ix++; rchg[ix]; ix++);
+ for (; rchgo[ixo]; ixo++);
+
+ do {
+ grpsiz = ix - ixs;
+
+ /*
+ * If the line before the current change group, is equal to
+ * the last line of the current change group, shift backward
+ * the group.
+ */
+ while (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&
+ xdl_recmatch(recs[ixs - 1]->ptr, recs[ixs - 1]->size, recs[ix - 1]->ptr, recs[ix - 1]->size, flags)) {
+ rchg[--ixs] = 1;
+ rchg[--ix] = 0;
+
+ /*
+ * This change might have joined two change groups,
+ * so we try to take this scenario in account by moving
+ * the start index accordingly (and so the other-file
+ * end-of-group index).
+ */
+ for (; rchg[ixs - 1]; ixs--);
+ while (rchgo[--ixo]);
+ }
+
+ /*
+ * Record the end-of-group position in case we are matched
+ * with a group of changes in the other file (that is, the
+ * change record before the enf-of-group index in the other
+ * file is set).
+ */
+ ixref = rchgo[ixo - 1] ? ix: nrec;
+
+ /*
+ * If the first line of the current change group, is equal to
+ * the line next of the current change group, shift forward
+ * the group.
+ */
+ while (ix < nrec && recs[ixs]->ha == recs[ix]->ha &&
+ xdl_recmatch(recs[ixs]->ptr, recs[ixs]->size, recs[ix]->ptr, recs[ix]->size, flags)) {
+ rchg[ixs++] = 0;
+ rchg[ix++] = 1;
+
+ /*
+ * This change might have joined two change groups,
+ * so we try to take this scenario in account by moving
+ * the start index accordingly (and so the other-file
+ * end-of-group index). Keep tracking the reference
+ * index in case we are shifting together with a
+ * corresponding group of changes in the other file.
+ */
+ for (; rchg[ix]; ix++);
+ while (rchgo[++ixo])
+ ixref = ix;
+ }
+ } while (grpsiz != ix - ixs);
+
+ /*
+ * Try to move back the possibly merged group of changes, to match
+ * the recorded postion in the other file.
+ */
+ while (ixref < ix) {
+ rchg[--ixs] = 1;
+ rchg[--ix] = 0;
+ while (rchgo[--ixo]);
+ }
+ }
+
+ return 0;
+}
+
+
+int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
+ xdchange_t *cscr = NULL, *xch;
+ char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;
+ long i1, i2, l1, l2;
+
+ /*
+ * Trivial. Collects "groups" of changes and creates an edit script.
+ */
+ for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
+ if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
+ for (l1 = i1; rchg1[i1 - 1]; i1--);
+ for (l2 = i2; rchg2[i2 - 1]; i2--);
+
+ if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) {
+ xdl_free_script(cscr);
+ return -1;
+ }
+ cscr = xch;
+ }
+
+ *xscr = cscr;
+
+ return 0;
+}
+
+
+void xdl_free_script(xdchange_t *xscr) {
+ xdchange_t *xch;
+
+ while ((xch = xscr) != NULL) {
+ xscr = xscr->next;
+ xdl_free(xch);
+ }
+}
+
+
+int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+ xdemitconf_t const *xecfg, xdemitcb_t *ecb) {
+ xdchange_t *xscr;
+ xdfenv_t xe;
+
+ if (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) {
+
+ return -1;
+ }
+ if (xdl_change_compact(&xe.xdf1, &xe.xdf2, xpp->flags) < 0 ||
+ xdl_change_compact(&xe.xdf2, &xe.xdf1, xpp->flags) < 0 ||
+ xdl_build_script(&xe, &xscr) < 0) {
+
+ xdl_free_env(&xe);
+ return -1;
+ }
+ if (xscr) {
+ if (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) {
+
+ xdl_free_script(xscr);
+ xdl_free_env(&xe);
+ return -1;
+ }
+ xdl_free_script(xscr);
+ }
+ xdl_free_env(&xe);
+
+ return 0;
+}
+
diff --git a/xdiff/xdiffi.h b/xdiff/xdiffi.h
new file mode 100644
index 000000000..d3b72716b
--- /dev/null
+++ b/xdiff/xdiffi.h
@@ -0,0 +1,59 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#if !defined(XDIFFI_H)
+#define XDIFFI_H
+
+
+typedef struct s_diffdata {
+ long nrec;
+ unsigned long const *ha;
+ long *rindex;
+ char *rchg;
+} diffdata_t;
+
+typedef struct s_xdalgoenv {
+ long mxcost;
+ long snake_cnt;
+ long heur_min;
+} xdalgoenv_t;
+
+typedef struct s_xdchange {
+ struct s_xdchange *next;
+ long i1, i2;
+ long chg1, chg2;
+} xdchange_t;
+
+
+
+int 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);
+int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+ xdfenv_t *xe);
+int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);
+void xdl_free_script(xdchange_t *xscr);
+int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
+ xdemitconf_t const *xecfg);
+
+#endif /* #if !defined(XDIFFI_H) */
+
diff --git a/xdiff/xemit.c b/xdiff/xemit.c
new file mode 100644
index 000000000..07995ec33
--- /dev/null
+++ b/xdiff/xemit.c
@@ -0,0 +1,197 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#include "xinclude.h"
+
+
+
+
+static long xdl_get_rec(xdfile_t *xdf, long ri, char const **rec);
+static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *ecb);
+static xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg);
+
+
+
+
+static long xdl_get_rec(xdfile_t *xdf, long ri, char const **rec) {
+
+ *rec = xdf->recs[ri]->ptr;
+
+ return xdf->recs[ri]->size;
+}
+
+
+static int xdl_emit_record(xdfile_t *xdf, long ri, char const *pre, xdemitcb_t *ecb) {
+ long size, psize = strlen(pre);
+ char const *rec;
+
+ size = xdl_get_rec(xdf, ri, &rec);
+ if (xdl_emit_diffrec(rec, size, pre, psize, ecb) < 0) {
+
+ return -1;
+ }
+
+ return 0;
+}
+
+
+/*
+ * Starting at the passed change atom, find the latest change atom to be included
+ * inside the differential hunk according to the specified configuration.
+ */
+static xdchange_t *xdl_get_hunk(xdchange_t *xscr, xdemitconf_t const *xecfg) {
+ xdchange_t *xch, *xchp;
+
+ for (xchp = xscr, xch = xscr->next; xch; xchp = xch, xch = xch->next)
+ if (xch->i1 - (xchp->i1 + xchp->chg1) > 2 * xecfg->ctxlen)
+ break;
+
+ return xchp;
+}
+
+
+static void xdl_find_func(xdfile_t *xf, long i, char *buf, long sz, long *ll) {
+
+ /*
+ * Be quite stupid about this for now. Find a line in the old file
+ * before the start of the hunk (and context) which starts with a
+ * plausible character.
+ */
+
+ const char *rec;
+ long len;
+
+ *ll = 0;
+ while (i-- > 0) {
+ len = xdl_get_rec(xf, i, &rec);
+ if (len > 0 &&
+ (isalpha((unsigned char)*rec) || /* identifier? */
+ *rec == '_' || /* also identifier? */
+ *rec == '$')) { /* mysterious GNU diff's invention */
+ if (len > sz)
+ len = sz;
+ while (0 < len && isspace((unsigned char)rec[len - 1]))
+ len--;
+ memcpy(buf, rec, len);
+ *ll = len;
+ return;
+ }
+ }
+}
+
+
+int xdl_emit_common(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
+ xdemitconf_t const *xecfg) {
+ xdfile_t *xdf = &xe->xdf1;
+ const char *rchg = xdf->rchg;
+ long ix;
+
+ for (ix = 0; ix < xdf->nrec; ix++) {
+ if (rchg[ix])
+ continue;
+ if (xdl_emit_record(xdf, ix, "", ecb))
+ return -1;
+ }
+ return 0;
+}
+
+int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
+ xdemitconf_t const *xecfg) {
+ long s1, s2, e1, e2, lctx;
+ xdchange_t *xch, *xche;
+ char funcbuf[40];
+ long funclen = 0;
+
+ if (xecfg->flags & XDL_EMIT_COMMON)
+ return xdl_emit_common(xe, xscr, ecb, xecfg);
+
+ for (xch = xche = xscr; xch; xch = xche->next) {
+ xche = xdl_get_hunk(xch, xecfg);
+
+ s1 = XDL_MAX(xch->i1 - xecfg->ctxlen, 0);
+ s2 = XDL_MAX(xch->i2 - xecfg->ctxlen, 0);
+
+ lctx = xecfg->ctxlen;
+ lctx = XDL_MIN(lctx, xe->xdf1.nrec - (xche->i1 + xche->chg1));
+ lctx = XDL_MIN(lctx, xe->xdf2.nrec - (xche->i2 + xche->chg2));
+
+ e1 = xche->i1 + xche->chg1 + lctx;
+ e2 = xche->i2 + xche->chg2 + lctx;
+
+ /*
+ * Emit current hunk header.
+ */
+
+ if (xecfg->flags & XDL_EMIT_FUNCNAMES) {
+ xdl_find_func(&xe->xdf1, s1, funcbuf,
+ sizeof(funcbuf), &funclen);
+ }
+ if (xdl_emit_hunk_hdr(s1 + 1, e1 - s1, s2 + 1, e2 - s2,
+ funcbuf, funclen, ecb) < 0)
+ return -1;
+
+ /*
+ * Emit pre-context.
+ */
+ for (; s1 < xch->i1; s1++)
+ if (xdl_emit_record(&xe->xdf1, s1, " ", ecb) < 0)
+ return -1;
+
+ for (s1 = xch->i1, s2 = xch->i2;; xch = xch->next) {
+ /*
+ * Merge previous with current change atom.
+ */
+ for (; s1 < xch->i1 && s2 < xch->i2; s1++, s2++)
+ if (xdl_emit_record(&xe->xdf1, s1, " ", ecb) < 0)
+ return -1;
+
+ /*
+ * Removes lines from the first file.
+ */
+ for (s1 = xch->i1; s1 < xch->i1 + xch->chg1; s1++)
+ if (xdl_emit_record(&xe->xdf1, s1, "-", ecb) < 0)
+ return -1;
+
+ /*
+ * Adds lines from the second file.
+ */
+ for (s2 = xch->i2; s2 < xch->i2 + xch->chg2; s2++)
+ if (xdl_emit_record(&xe->xdf2, s2, "+", ecb) < 0)
+ return -1;
+
+ if (xch == xche)
+ break;
+ s1 = xch->i1 + xch->chg1;
+ s2 = xch->i2 + xch->chg2;
+ }
+
+ /*
+ * Emit post-context.
+ */
+ for (s1 = xche->i1 + xche->chg1; s1 < e1; s1++)
+ if (xdl_emit_record(&xe->xdf1, s1, " ", ecb) < 0)
+ return -1;
+ }
+
+ return 0;
+}
+
diff --git a/xdiff/xemit.h b/xdiff/xemit.h
new file mode 100644
index 000000000..e629417dd
--- /dev/null
+++ b/xdiff/xemit.h
@@ -0,0 +1,34 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#if !defined(XEMIT_H)
+#define XEMIT_H
+
+
+
+int xdl_emit_diff(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
+ xdemitconf_t const *xecfg);
+
+
+
+#endif /* #if !defined(XEMIT_H) */
+
diff --git a/xdiff/xinclude.h b/xdiff/xinclude.h
new file mode 100644
index 000000000..04a9da82c
--- /dev/null
+++ b/xdiff/xinclude.h
@@ -0,0 +1,43 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#if !defined(XINCLUDE_H)
+#define XINCLUDE_H
+
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <string.h>
+#include <limits.h>
+
+#include "xmacros.h"
+#include "xdiff.h"
+#include "xtypes.h"
+#include "xutils.h"
+#include "xprepare.h"
+#include "xdiffi.h"
+#include "xemit.h"
+
+
+#endif /* #if !defined(XINCLUDE_H) */
+
diff --git a/xdiff/xmacros.h b/xdiff/xmacros.h
new file mode 100644
index 000000000..e2cd2023b
--- /dev/null
+++ b/xdiff/xmacros.h
@@ -0,0 +1,54 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#if !defined(XMACROS_H)
+#define XMACROS_H
+
+
+
+
+#define XDL_MIN(a, b) ((a) < (b) ? (a): (b))
+#define XDL_MAX(a, b) ((a) > (b) ? (a): (b))
+#define XDL_ABS(v) ((v) >= 0 ? (v): -(v))
+#define XDL_ISDIGIT(c) ((c) >= '0' && (c) <= '9')
+#define XDL_ADDBITS(v,b) ((v) + ((v) >> (b)))
+#define XDL_MASKBITS(b) ((1UL << (b)) - 1)
+#define XDL_HASHLONG(v,b) (XDL_ADDBITS((unsigned long)(v), b) & XDL_MASKBITS(b))
+#define XDL_PTRFREE(p) do { if (p) { xdl_free(p); (p) = NULL; } } while (0)
+#define XDL_LE32_PUT(p, v) \
+do { \
+ unsigned char *__p = (unsigned char *) (p); \
+ *__p++ = (unsigned char) (v); \
+ *__p++ = (unsigned char) ((v) >> 8); \
+ *__p++ = (unsigned char) ((v) >> 16); \
+ *__p = (unsigned char) ((v) >> 24); \
+} while (0)
+#define XDL_LE32_GET(p, v) \
+do { \
+ unsigned char const *__p = (unsigned char const *) (p); \
+ (v) = (unsigned long) __p[0] | ((unsigned long) __p[1]) << 8 | \
+ ((unsigned long) __p[2]) << 16 | ((unsigned long) __p[3]) << 24; \
+} while (0)
+
+
+#endif /* #if !defined(XMACROS_H) */
+
diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
new file mode 100644
index 000000000..1be7b3195
--- /dev/null
+++ b/xdiff/xprepare.c
@@ -0,0 +1,469 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#include "xinclude.h"
+
+
+
+#define XDL_KPDIS_RUN 4
+#define XDL_MAX_EQLIMIT 1024
+
+
+
+typedef struct s_xdlclass {
+ struct s_xdlclass *next;
+ unsigned long ha;
+ char const *line;
+ long size;
+ long idx;
+} xdlclass_t;
+
+typedef struct s_xdlclassifier {
+ unsigned int hbits;
+ long hsize;
+ xdlclass_t **rchash;
+ chastore_t ncha;
+ long count;
+ long flags;
+} xdlclassifier_t;
+
+
+
+
+static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags);
+static void xdl_free_classifier(xdlclassifier_t *cf);
+static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
+ xrecord_t *rec);
+static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
+ xdlclassifier_t *cf, xdfile_t *xdf);
+static void xdl_free_ctx(xdfile_t *xdf);
+static int xdl_clean_mmatch(char const *dis, long i, long s, long e);
+static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2);
+static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);
+static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2);
+
+
+
+
+static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) {
+ long i;
+
+ cf->flags = flags;
+
+ cf->hbits = xdl_hashbits((unsigned int) size);
+ cf->hsize = 1 << cf->hbits;
+
+ if (xdl_cha_init(&cf->ncha, sizeof(xdlclass_t), size / 4 + 1) < 0) {
+
+ return -1;
+ }
+ if (!(cf->rchash = (xdlclass_t **) xdl_malloc(cf->hsize * sizeof(xdlclass_t *)))) {
+
+ xdl_cha_free(&cf->ncha);
+ return -1;
+ }
+ for (i = 0; i < cf->hsize; i++)
+ cf->rchash[i] = NULL;
+
+ cf->count = 0;
+
+ return 0;
+}
+
+
+static void xdl_free_classifier(xdlclassifier_t *cf) {
+
+ xdl_free(cf->rchash);
+ xdl_cha_free(&cf->ncha);
+}
+
+
+static int xdl_classify_record(xdlclassifier_t *cf, xrecord_t **rhash, unsigned int hbits,
+ xrecord_t *rec) {
+ long hi;
+ char const *line;
+ xdlclass_t *rcrec;
+
+ line = rec->ptr;
+ hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
+ for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)
+ if (rcrec->ha == rec->ha &&
+ xdl_recmatch(rcrec->line, rcrec->size,
+ rec->ptr, rec->size, cf->flags))
+ break;
+
+ if (!rcrec) {
+ if (!(rcrec = xdl_cha_alloc(&cf->ncha))) {
+
+ return -1;
+ }
+ rcrec->idx = cf->count++;
+ rcrec->line = line;
+ rcrec->size = rec->size;
+ rcrec->ha = rec->ha;
+ rcrec->next = cf->rchash[hi];
+ cf->rchash[hi] = rcrec;
+ }
+
+ rec->ha = (unsigned long) rcrec->idx;
+
+ hi = (long) XDL_HASHLONG(rec->ha, hbits);
+ rec->next = rhash[hi];
+ rhash[hi] = rec;
+
+ return 0;
+}
+
+
+static int xdl_prepare_ctx(mmfile_t *mf, long narec, xpparam_t const *xpp,
+ xdlclassifier_t *cf, xdfile_t *xdf) {
+ unsigned int hbits;
+ long i, nrec, hsize, bsize;
+ unsigned long hav;
+ char const *blk, *cur, *top, *prev;
+ xrecord_t *crec;
+ xrecord_t **recs, **rrecs;
+ xrecord_t **rhash;
+ unsigned long *ha;
+ char *rchg;
+ long *rindex;
+
+ if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) {
+
+ return -1;
+ }
+ if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) {
+
+ xdl_cha_free(&xdf->rcha);
+ return -1;
+ }
+
+ hbits = xdl_hashbits((unsigned int) narec);
+ hsize = 1 << hbits;
+ if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) {
+
+ xdl_free(recs);
+ xdl_cha_free(&xdf->rcha);
+ return -1;
+ }
+ for (i = 0; i < hsize; i++)
+ rhash[i] = NULL;
+
+ nrec = 0;
+ if ((cur = blk = xdl_mmfile_first(mf, &bsize)) != NULL) {
+ for (top = blk + bsize;;) {
+ if (cur >= top) {
+ if (!(cur = blk = xdl_mmfile_next(mf, &bsize)))
+ break;
+ top = blk + bsize;
+ }
+ prev = cur;
+ hav = xdl_hash_record(&cur, top, xpp->flags);
+ if (nrec >= narec) {
+ narec *= 2;
+ if (!(rrecs = (xrecord_t **) xdl_realloc(recs, narec * sizeof(xrecord_t *)))) {
+
+ xdl_free(rhash);
+ xdl_free(recs);
+ xdl_cha_free(&xdf->rcha);
+ return -1;
+ }
+ recs = rrecs;
+ }
+ if (!(crec = xdl_cha_alloc(&xdf->rcha))) {
+
+ xdl_free(rhash);
+ xdl_free(recs);
+ xdl_cha_free(&xdf->rcha);
+ return -1;
+ }
+ crec->ptr = prev;
+ crec->size = (long) (cur - prev);
+ crec->ha = hav;
+ recs[nrec++] = crec;
+
+ if (xdl_classify_record(cf, rhash, hbits, crec) < 0) {
+
+ xdl_free(rhash);
+ xdl_free(recs);
+ xdl_cha_free(&xdf->rcha);
+ return -1;
+ }
+ }
+ }
+
+ if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) {
+
+ xdl_free(rhash);
+ xdl_free(recs);
+ xdl_cha_free(&xdf->rcha);
+ return -1;
+ }
+ memset(rchg, 0, (nrec + 2) * sizeof(char));
+
+ if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long)))) {
+
+ xdl_free(rchg);
+ xdl_free(rhash);
+ xdl_free(recs);
+ xdl_cha_free(&xdf->rcha);
+ return -1;
+ }
+ if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long)))) {
+
+ xdl_free(rindex);
+ xdl_free(rchg);
+ xdl_free(rhash);
+ xdl_free(recs);
+ xdl_cha_free(&xdf->rcha);
+ return -1;
+ }
+
+ xdf->nrec = nrec;
+ xdf->recs = recs;
+ xdf->hbits = hbits;
+ xdf->rhash = rhash;
+ xdf->rchg = rchg + 1;
+ xdf->rindex = rindex;
+ xdf->nreff = 0;
+ xdf->ha = ha;
+ xdf->dstart = 0;
+ xdf->dend = nrec - 1;
+
+ return 0;
+}
+
+
+static void xdl_free_ctx(xdfile_t *xdf) {
+
+ xdl_free(xdf->rhash);
+ xdl_free(xdf->rindex);
+ xdl_free(xdf->rchg - 1);
+ xdl_free(xdf->ha);
+ xdl_free(xdf->recs);
+ xdl_cha_free(&xdf->rcha);
+}
+
+
+int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+ xdfenv_t *xe) {
+ long enl1, enl2;
+ xdlclassifier_t cf;
+
+ enl1 = xdl_guess_lines(mf1) + 1;
+ enl2 = xdl_guess_lines(mf2) + 1;
+
+ if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) {
+
+ return -1;
+ }
+
+ if (xdl_prepare_ctx(mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
+
+ xdl_free_classifier(&cf);
+ return -1;
+ }
+ if (xdl_prepare_ctx(mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {
+
+ xdl_free_ctx(&xe->xdf1);
+ xdl_free_classifier(&cf);
+ return -1;
+ }
+
+ xdl_free_classifier(&cf);
+
+ if (xdl_optimize_ctxs(&xe->xdf1, &xe->xdf2) < 0) {
+
+ xdl_free_ctx(&xe->xdf2);
+ xdl_free_ctx(&xe->xdf1);
+ return -1;
+ }
+
+ return 0;
+}
+
+
+void xdl_free_env(xdfenv_t *xe) {
+
+ xdl_free_ctx(&xe->xdf2);
+ xdl_free_ctx(&xe->xdf1);
+}
+
+
+static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
+ long r, rdis0, rpdis0, rdis1, rpdis1;
+
+ /*
+ * Scans the lines before 'i' to find a run of lines that either
+ * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).
+ * Note that we always call this function with dis[i] > 1, so the
+ * current line (i) is already a multimatch line.
+ */
+ for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
+ if (!dis[i - r])
+ rdis0++;
+ else if (dis[i - r] == 2)
+ rpdis0++;
+ else
+ break;
+ }
+ /*
+ * If the run before the line 'i' found only multimatch lines, we
+ * return 0 and hence we don't make the current line (i) discarded.
+ * We want to discard multimatch lines only when they appear in the
+ * middle of runs with nomatch lines (dis[j] == 0).
+ */
+ if (rdis0 == 0)
+ return 0;
+ for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
+ if (!dis[i + r])
+ rdis1++;
+ else if (dis[i + r] == 2)
+ rpdis1++;
+ else
+ break;
+ }
+ /*
+ * If the run after the line 'i' found only multimatch lines, we
+ * return 0 and hence we don't make the current line (i) discarded.
+ */
+ if (rdis1 == 0)
+ return 0;
+ rdis1 += rdis0;
+ rpdis1 += rpdis0;
+
+ return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
+}
+
+
+/*
+ * Try to reduce the problem complexity, discard records that have no
+ * matches on the other file. Also, lines that have multiple matches
+ * might be potentially discarded if they happear in a run of discardable.
+ */
+static int xdl_cleanup_records(xdfile_t *xdf1, xdfile_t *xdf2) {
+ long i, nm, rhi, nreff, mlim;
+ unsigned long hav;
+ xrecord_t **recs;
+ xrecord_t *rec;
+ char *dis, *dis1, *dis2;
+
+ if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
+
+ return -1;
+ }
+ memset(dis, 0, xdf1->nrec + xdf2->nrec + 2);
+ dis1 = dis;
+ dis2 = dis1 + xdf1->nrec + 1;
+
+ if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
+ mlim = XDL_MAX_EQLIMIT;
+ for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
+ hav = (*recs)->ha;
+ rhi = (long) XDL_HASHLONG(hav, xdf2->hbits);
+ for (nm = 0, rec = xdf2->rhash[rhi]; rec; rec = rec->next)
+ if (rec->ha == hav && ++nm == mlim)
+ break;
+ dis1[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
+ }
+
+ if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
+ mlim = XDL_MAX_EQLIMIT;
+ for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
+ hav = (*recs)->ha;
+ rhi = (long) XDL_HASHLONG(hav, xdf1->hbits);
+ for (nm = 0, rec = xdf1->rhash[rhi]; rec; rec = rec->next)
+ if (rec->ha == hav && ++nm == mlim)
+ break;
+ dis2[i] = (nm == 0) ? 0: (nm >= mlim) ? 2: 1;
+ }
+
+ for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
+ i <= xdf1->dend; i++, recs++) {
+ if (dis1[i] == 1 ||
+ (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) {
+ xdf1->rindex[nreff] = i;
+ xdf1->ha[nreff] = (*recs)->ha;
+ nreff++;
+ } else
+ xdf1->rchg[i] = 1;
+ }
+ xdf1->nreff = nreff;
+
+ for (nreff = 0, i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart];
+ i <= xdf2->dend; i++, recs++) {
+ if (dis2[i] == 1 ||
+ (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) {
+ xdf2->rindex[nreff] = i;
+ xdf2->ha[nreff] = (*recs)->ha;
+ nreff++;
+ } else
+ xdf2->rchg[i] = 1;
+ }
+ xdf2->nreff = nreff;
+
+ xdl_free(dis);
+
+ return 0;
+}
+
+
+/*
+ * Early trim initial and terminal matching records.
+ */
+static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
+ long i, lim;
+ xrecord_t **recs1, **recs2;
+
+ recs1 = xdf1->recs;
+ recs2 = xdf2->recs;
+ for (i = 0, lim = XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim;
+ i++, recs1++, recs2++)
+ if ((*recs1)->ha != (*recs2)->ha)
+ break;
+
+ xdf1->dstart = xdf2->dstart = i;
+
+ recs1 = xdf1->recs + xdf1->nrec - 1;
+ recs2 = xdf2->recs + xdf2->nrec - 1;
+ for (lim -= i, i = 0; i < lim; i++, recs1--, recs2--)
+ if ((*recs1)->ha != (*recs2)->ha)
+ break;
+
+ xdf1->dend = xdf1->nrec - i - 1;
+ xdf2->dend = xdf2->nrec - i - 1;
+
+ return 0;
+}
+
+
+static int xdl_optimize_ctxs(xdfile_t *xdf1, xdfile_t *xdf2) {
+
+ if (xdl_trim_ends(xdf1, xdf2) < 0 ||
+ xdl_cleanup_records(xdf1, xdf2) < 0) {
+
+ return -1;
+ }
+
+ return 0;
+}
+
diff --git a/xdiff/xprepare.h b/xdiff/xprepare.h
new file mode 100644
index 000000000..344c569e8
--- /dev/null
+++ b/xdiff/xprepare.h
@@ -0,0 +1,35 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#if !defined(XPREPARE_H)
+#define XPREPARE_H
+
+
+
+int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+ xdfenv_t *xe);
+void xdl_free_env(xdfenv_t *xe);
+
+
+
+#endif /* #if !defined(XPREPARE_H) */
+
diff --git a/xdiff/xtypes.h b/xdiff/xtypes.h
new file mode 100644
index 000000000..3593a664f
--- /dev/null
+++ b/xdiff/xtypes.h
@@ -0,0 +1,68 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#if !defined(XTYPES_H)
+#define XTYPES_H
+
+
+
+typedef struct s_chanode {
+ struct s_chanode *next;
+ long icurr;
+} chanode_t;
+
+typedef struct s_chastore {
+ chanode_t *head, *tail;
+ long isize, nsize;
+ chanode_t *ancur;
+ chanode_t *sncur;
+ long scurr;
+} chastore_t;
+
+typedef struct s_xrecord {
+ struct s_xrecord *next;
+ char const *ptr;
+ long size;
+ unsigned long ha;
+} xrecord_t;
+
+typedef struct s_xdfile {
+ chastore_t rcha;
+ long nrec;
+ unsigned int hbits;
+ xrecord_t **rhash;
+ long dstart, dend;
+ xrecord_t **recs;
+ char *rchg;
+ long *rindex;
+ long nreff;
+ unsigned long *ha;
+} xdfile_t;
+
+typedef struct s_xdfenv {
+ xdfile_t xdf1, xdf2;
+} xdfenv_t;
+
+
+
+#endif /* #if !defined(XTYPES_H) */
+
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
new file mode 100644
index 000000000..9e4bb47ee
--- /dev/null
+++ b/xdiff/xutils.c
@@ -0,0 +1,340 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#include "xinclude.h"
+
+
+
+#define XDL_GUESS_NLINES 256
+
+
+
+
+long xdl_bogosqrt(long n) {
+ long i;
+
+ /*
+ * Classical integer square root approximation using shifts.
+ */
+ for (i = 1; n > 0; n >>= 2)
+ i <<= 1;
+
+ return i;
+}
+
+
+int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
+ xdemitcb_t *ecb) {
+ int i = 2;
+ mmbuffer_t mb[3];
+
+ mb[0].ptr = (char *) pre;
+ mb[0].size = psize;
+ mb[1].ptr = (char *) rec;
+ mb[1].size = size;
+ if (size > 0 && rec[size - 1] != '\n') {
+ mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
+ mb[2].size = strlen(mb[2].ptr);
+ i++;
+ }
+ if (ecb->outf(ecb->priv, mb, i) < 0) {
+
+ return -1;
+ }
+
+ return 0;
+}
+
+void *xdl_mmfile_first(mmfile_t *mmf, long *size)
+{
+ *size = mmf->size;
+ return mmf->ptr;
+}
+
+
+void *xdl_mmfile_next(mmfile_t *mmf, long *size)
+{
+ return NULL;
+}
+
+
+long xdl_mmfile_size(mmfile_t *mmf)
+{
+ return mmf->size;
+}
+
+
+int xdl_cha_init(chastore_t *cha, long isize, long icount) {
+
+ cha->head = cha->tail = NULL;
+ cha->isize = isize;
+ cha->nsize = icount * isize;
+ cha->ancur = cha->sncur = NULL;
+ cha->scurr = 0;
+
+ return 0;
+}
+
+
+void xdl_cha_free(chastore_t *cha) {
+ chanode_t *cur, *tmp;
+
+ for (cur = cha->head; (tmp = cur) != NULL;) {
+ cur = cur->next;
+ xdl_free(tmp);
+ }
+}
+
+
+void *xdl_cha_alloc(chastore_t *cha) {
+ chanode_t *ancur;
+ void *data;
+
+ if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
+ if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {
+
+ return NULL;
+ }
+ ancur->icurr = 0;
+ ancur->next = NULL;
+ if (cha->tail)
+ cha->tail->next = ancur;
+ if (!cha->head)
+ cha->head = ancur;
+ cha->tail = ancur;
+ cha->ancur = ancur;
+ }
+
+ data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
+ ancur->icurr += cha->isize;
+
+ return data;
+}
+
+
+void *xdl_cha_first(chastore_t *cha) {
+ chanode_t *sncur;
+
+ if (!(cha->sncur = sncur = cha->head))
+ return NULL;
+
+ cha->scurr = 0;
+
+ return (char *) sncur + sizeof(chanode_t) + cha->scurr;
+}
+
+
+void *xdl_cha_next(chastore_t *cha) {
+ chanode_t *sncur;
+
+ if (!(sncur = cha->sncur))
+ return NULL;
+ cha->scurr += cha->isize;
+ if (cha->scurr == sncur->icurr) {
+ if (!(sncur = cha->sncur = sncur->next))
+ return NULL;
+ cha->scurr = 0;
+ }
+
+ return (char *) sncur + sizeof(chanode_t) + cha->scurr;
+}
+
+
+long xdl_guess_lines(mmfile_t *mf) {
+ long nl = 0, size, tsize = 0;
+ char const *data, *cur, *top;
+
+ if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
+ for (top = data + size; nl < XDL_GUESS_NLINES;) {
+ if (cur >= top) {
+ tsize += (long) (cur - data);
+ if (!(cur = data = xdl_mmfile_next(mf, &size)))
+ break;
+ top = data + size;
+ }
+ nl++;
+ if (!(cur = memchr(cur, '\n', top - cur)))
+ cur = top;
+ else
+ cur++;
+ }
+ tsize += (long) (cur - data);
+ }
+
+ if (nl && tsize)
+ nl = xdl_mmfile_size(mf) / (tsize / nl);
+
+ return nl + 1;
+}
+
+int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
+{
+ int i1, i2;
+
+ if (flags & XDF_IGNORE_WHITESPACE) {
+ for (i1 = i2 = 0; i1 < s1 && i2 < s2; ) {
+ if (isspace(l1[i1]))
+ while (isspace(l1[i1]) && i1 < s1)
+ i1++;
+ if (isspace(l2[i2]))
+ while (isspace(l2[i2]) && i2 < s2)
+ i2++;
+ if (i1 < s1 && i2 < s2 && l1[i1++] != l2[i2++])
+ return 0;
+ }
+ return (i1 >= s1 && i2 >= s2);
+ } else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
+ for (i1 = i2 = 0; i1 < s1 && i2 < s2; ) {
+ if (isspace(l1[i1])) {
+ if (!isspace(l2[i2]))
+ return 0;
+ while (isspace(l1[i1]) && i1 < s1)
+ i1++;
+ while (isspace(l2[i2]) && i2 < s2)
+ i2++;
+ } else if (l1[i1++] != l2[i2++])
+ return 0;
+ }
+ return (i1 >= s1 && i2 >= s2);
+ } else
+ return s1 == s2 && !memcmp(l1, l2, s1);
+
+ return 0;
+}
+
+unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
+ unsigned long ha = 5381;
+ char const *ptr = *data;
+
+ for (; ptr < top && *ptr != '\n'; ptr++) {
+ if (isspace(*ptr) && (flags & XDF_WHITESPACE_FLAGS)) {
+ while (ptr + 1 < top && isspace(ptr[1])
+ && ptr[1] != '\n')
+ ptr++;
+ if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
+ ha += (ha << 5);
+ ha ^= (unsigned long) ' ';
+ }
+ continue;
+ }
+ ha += (ha << 5);
+ ha ^= (unsigned long) *ptr;
+ }
+ *data = ptr < top ? ptr + 1: ptr;
+
+ return ha;
+}
+
+
+unsigned int xdl_hashbits(unsigned int size) {
+ unsigned int val = 1, bits = 0;
+
+ for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
+ return bits ? bits: 1;
+}
+
+
+int xdl_num_out(char *out, long val) {
+ char *ptr, *str = out;
+ char buf[32];
+
+ ptr = buf + sizeof(buf) - 1;
+ *ptr = '\0';
+ if (val < 0) {
+ *--ptr = '-';
+ val = -val;
+ }
+ for (; val && ptr > buf; val /= 10)
+ *--ptr = "0123456789"[val % 10];
+ if (*ptr)
+ for (; *ptr; ptr++, str++)
+ *str = *ptr;
+ else
+ *str++ = '0';
+ *str = '\0';
+
+ return str - out;
+}
+
+
+long xdl_atol(char const *str, char const **next) {
+ long val, base;
+ char const *top;
+
+ for (top = str; XDL_ISDIGIT(*top); top++);
+ if (next)
+ *next = top;
+ for (val = 0, base = 1, top--; top >= str; top--, base *= 10)
+ val += base * (long)(*top - '0');
+ return val;
+}
+
+
+int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
+ const char *func, long funclen, xdemitcb_t *ecb) {
+ int nb = 0;
+ mmbuffer_t mb;
+ char buf[128];
+
+ memcpy(buf, "@@ -", 4);
+ nb += 4;
+
+ nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1);
+
+ if (c1 != 1) {
+ memcpy(buf + nb, ",", 1);
+ nb += 1;
+
+ nb += xdl_num_out(buf + nb, c1);
+ }
+
+ memcpy(buf + nb, " +", 2);
+ nb += 2;
+
+ nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1);
+
+ if (c2 != 1) {
+ memcpy(buf + nb, ",", 1);
+ nb += 1;
+
+ nb += xdl_num_out(buf + nb, c2);
+ }
+
+ memcpy(buf + nb, " @@", 3);
+ nb += 3;
+ if (func && funclen) {
+ buf[nb++] = ' ';
+ if (funclen > sizeof(buf) - nb - 1)
+ funclen = sizeof(buf) - nb - 1;
+ memcpy(buf + nb, func, funclen);
+ nb += funclen;
+ }
+ buf[nb++] = '\n';
+
+ mb.ptr = buf;
+ mb.size = nb;
+ if (ecb->outf(ecb->priv, &mb, 1) < 0)
+ return -1;
+
+ return 0;
+}
+
diff --git a/xdiff/xutils.h b/xdiff/xutils.h
new file mode 100644
index 000000000..70d8b9838
--- /dev/null
+++ b/xdiff/xutils.h
@@ -0,0 +1,48 @@
+/*
+ * LibXDiff by Davide Libenzi ( File Differential Library )
+ * Copyright (C) 2003 Davide Libenzi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#if !defined(XUTILS_H)
+#define XUTILS_H
+
+
+
+long xdl_bogosqrt(long n);
+int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
+ xdemitcb_t *ecb);
+int xdl_cha_init(chastore_t *cha, long isize, long icount);
+void xdl_cha_free(chastore_t *cha);
+void *xdl_cha_alloc(chastore_t *cha);
+void *xdl_cha_first(chastore_t *cha);
+void *xdl_cha_next(chastore_t *cha);
+long xdl_guess_lines(mmfile_t *mf);
+int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);
+unsigned long xdl_hash_record(char const **data, char const *top, long flags);
+unsigned int xdl_hashbits(unsigned int size);
+int xdl_num_out(char *out, long val);
+long xdl_atol(char const *str, char const **next);
+int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
+ const char *func, long funclen, xdemitcb_t *ecb);
+
+
+
+#endif /* #if !defined(XUTILS_H) */
+
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-13 22:36:18 +0000