This is an archive of the discontinued Mercurial Phabricator instance.

Differential D2762

xdiff: replace {unsigned ,}long with {u,}int64_t
ClosedPublic

Authored by quark on Mar 9 2018, 5:54 PM.

Details

Reviewers
indygreg
Group Reviewers
hg-reviewers
Commits
rHG882657a9f768: xdiff: replace {unsigned ,}long with {u,}int64_t
rHGe882437cc082: xdiff: replace {unsigned ,}long with {u,}int64_t
Summary

MSVC treats "long" as 4-byte. That could cause overflows since the xdiff
code uses "long" in places where "size_t" or "ssize_t" should be used.
Let's use explicit 8 byte integers to avoid

FWIW git avoids that overflow by limiting diff size to 1GB [1]. After
examining the code, I think the remaining risk (the use of "int") is low
since "int" is only used for return values and hash table size. Although a
wrong hash table size would not affect the correctness of the code, but that
could make the code extremely slow. The next patch will change hash table
size to 8-byte integer so the 1GB limit is unlikely needed.

This patch was done by using sed.

[1]: https://github.com/git/git/commit/dcd1742e56ebb944c4ff62346da4548e1e3be67

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

quark created this revision.Mar 9 2018, 5:54 PM
indygreg accepted this revision.Mar 9 2018, 6:19 PM
This revision is now accepted and ready to land.Mar 9 2018, 6:19 PM
Closed by commit rHGe882437cc082: xdiff: replace {unsigned ,}long with {u,}int64_t (authored by quark). · Explain WhyMar 9 2018, 6:24 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 6806

mercurial/thirdparty/xdiff/xdiff.h

#define XDF_INDENT_HEURISTIC (1 << 23) #define XDF_INDENT_HEURISTIC (1 << 23)
/* emit bdiff-style "matched" (a1, a2, b1, b2) hunks instead of "different" /* emit bdiff-style "matched" (a1, a2, b1, b2) hunks instead of "different"
* (a1, a2 - a1, b1, b2 - b1) hunks */ * (a1, a2 - a1, b1, b2 - b1) hunks */
#define XDL_EMIT_BDIFFHUNK (1 << 4) #define XDL_EMIT_BDIFFHUNK (1 << 4)
typedef struct s_mmfile { typedef struct s_mmfile {
char *ptr; char *ptr;
long size; int64_t size;
} mmfile_t; } mmfile_t;
typedef struct s_mmbuffer { typedef struct s_mmbuffer {
char *ptr; char *ptr;
long size; int64_t size;
} mmbuffer_t; } mmbuffer_t;
typedef struct s_xpparam { typedef struct s_xpparam {
unsigned long flags; uint64_t flags;
} xpparam_t; } xpparam_t;
typedef struct s_xdemitcb { typedef struct s_xdemitcb {
void *priv; void *priv;
} xdemitcb_t; } xdemitcb_t;
typedef int (*xdl_emit_hunk_consume_func_t)(long start_a, long count_a, typedef int (*xdl_emit_hunk_consume_func_t)(int64_t start_a, int64_t count_a,
long start_b, long count_b, int64_t start_b, int64_t count_b,
void *cb_data); void *cb_data);
typedef struct s_xdemitconf { typedef struct s_xdemitconf {
unsigned long flags; uint64_t flags;
xdl_emit_hunk_consume_func_t hunk_func; xdl_emit_hunk_consume_func_t hunk_func;
} xdemitconf_t; } xdemitconf_t;
#define xdl_malloc(x) malloc(x) #define xdl_malloc(x) malloc(x)
#define xdl_free(ptr) free(ptr) #define xdl_free(ptr) free(ptr)
#define xdl_realloc(ptr,x) realloc(ptr,x) #define xdl_realloc(ptr,x) realloc(ptr,x)
void *xdl_mmfile_first(mmfile_t *mmf, long *size); void *xdl_mmfile_first(mmfile_t *mmf, int64_t *size);
long xdl_mmfile_size(mmfile_t *mmf); int64_t xdl_mmfile_size(mmfile_t *mmf);
int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdemitconf_t const *xecfg, xdemitcb_t *ecb); xdemitconf_t const *xecfg, xdemitcb_t *ecb);
#ifdef __cplusplus #ifdef __cplusplus
} }
#endif /* #ifdef __cplusplus */ #endif /* #ifdef __cplusplus */
#endif /* #if !defined(XDIFF_H) */ #endif /* #if !defined(XDIFF_H) */

mercurial/thirdparty/xdiff/xdiffi.h

* *
*/ */
#if !defined(XDIFFI_H) #if !defined(XDIFFI_H)
#define XDIFFI_H #define XDIFFI_H
typedef struct s_diffdata { typedef struct s_diffdata {
long nrec; int64_t nrec;
unsigned long const *ha; uint64_t const *ha;
long *rindex; int64_t *rindex;
char *rchg; char *rchg;
} diffdata_t; } diffdata_t;
typedef struct s_xdalgoenv { typedef struct s_xdalgoenv {
long mxcost; int64_t mxcost;
long snake_cnt; int64_t snake_cnt;
long heur_min; int64_t heur_min;
} xdalgoenv_t; } xdalgoenv_t;
typedef struct s_xdchange { typedef struct s_xdchange {
struct s_xdchange *next; struct s_xdchange *next;
long i1, i2; int64_t i1, i2;
long chg1, chg2; int64_t chg1, chg2;
int ignore; int ignore;
} xdchange_t; } xdchange_t;
int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1, int xdl_recs_cmp(diffdata_t *dd1, int64_t off1, int64_t lim1,
diffdata_t *dd2, long off2, long lim2, diffdata_t *dd2, int64_t off2, int64_t lim2,
long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv); int64_t *kvdf, int64_t *kvdb, int need_min, xdalgoenv_t *xenv);
int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdfenv_t *xe); xdfenv_t *xe);
int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags); int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, int64_t flags);
int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr); int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr);
void xdl_free_script(xdchange_t *xscr); void xdl_free_script(xdchange_t *xscr);
#endif /* #if !defined(XDIFFI_H) */ #endif /* #if !defined(XDIFFI_H) */

mercurial/thirdparty/xdiff/xdiffi.c

/* VC 2008 doesn't know about the inline keyword. */ /* VC 2008 doesn't know about the inline keyword. */
#if defined(_MSC_VER) #if defined(_MSC_VER)
#define inline __forceinline #define inline __forceinline
#endif #endif
typedef struct s_xdpsplit { typedef struct s_xdpsplit {
long i1, i2; int64_t i1, i2;
int min_lo, min_hi; int min_lo, min_hi;
} xdpsplit_t; } xdpsplit_t;
static long xdl_split(unsigned long const *ha1, long off1, long lim1, static int64_t xdl_split(uint64_t const *ha1, int64_t off1, int64_t lim1,
unsigned long const *ha2, long off2, long lim2, uint64_t const *ha2, int64_t off2, int64_t lim2,
long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl, int64_t *kvdf, int64_t *kvdb, int need_min, xdpsplit_t *spl,
xdalgoenv_t *xenv); xdalgoenv_t *xenv);
static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2); static xdchange_t *xdl_add_change(xdchange_t *xscr, int64_t i1, int64_t i2, int64_t chg1, int64_t chg2);
/* /*
* See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers. * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
* Basically considers a "box" (off1, off2, lim1, lim2) and scan from both * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
* the forward diagonal starting from (off1, off2) and the backward diagonal * the forward diagonal starting from (off1, off2) and the backward diagonal
* starting from (lim1, lim2). If the K values on the same diagonal crosses * 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 * 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 * cases using this algorithm is full, so a little bit of heuristic is needed
* to cut the search and to return a suboptimal point. * to cut the search and to return a suboptimal point.
*/ */
static long xdl_split(unsigned long const *ha1, long off1, long lim1, static int64_t xdl_split(uint64_t const *ha1, int64_t off1, int64_t lim1,
unsigned long const *ha2, long off2, long lim2, uint64_t const *ha2, int64_t off2, int64_t lim2,
long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl, int64_t *kvdf, int64_t *kvdb, int need_min, xdpsplit_t *spl,
xdalgoenv_t *xenv) { xdalgoenv_t *xenv) {
long dmin = off1 - lim2, dmax = lim1 - off2; int64_t dmin = off1 - lim2, dmax = lim1 - off2;
long fmid = off1 - off2, bmid = lim1 - lim2; int64_t fmid = off1 - off2, bmid = lim1 - lim2;
long odd = (fmid - bmid) & 1; int64_t odd = (fmid - bmid) & 1;
long fmin = fmid, fmax = fmid; int64_t fmin = fmid, fmax = fmid;
long bmin = bmid, bmax = bmid; int64_t bmin = bmid, bmax = bmid;
long ec, d, i1, i2, prev1, best, dd, v, k; int64_t ec, d, i1, i2, prev1, best, dd, v, k;
/* /*
* Set initial diagonal values for both forward and backward path. * Set initial diagonal values for both forward and backward path.
*/ */
kvdf[fmid] = off1; kvdf[fmid] = off1;
kvdb[bmid] = lim1; kvdb[bmid] = lim1;
for (ec = 1;; ec++) { for (ec = 1;; ec++) {
} }
} }
/* /*
* Enough is enough. We spent too much time here and now we collect * Enough is enough. We spent too much time here and now we collect
* the furthest reaching path using the (i1 + i2) measure. * the furthest reaching path using the (i1 + i2) measure.
*/ */
if (ec >= xenv->mxcost) { if (ec >= xenv->mxcost) {
long fbest, fbest1, bbest, bbest1; int64_t fbest, fbest1, bbest, bbest1;
fbest = fbest1 = -1; fbest = fbest1 = -1;
for (d = fmax; d >= fmin; d -= 2) { for (d = fmax; d >= fmin; d -= 2) {
i1 = XDL_MIN(kvdf[d], lim1); i1 = XDL_MIN(kvdf[d], lim1);
i2 = i1 - d; i2 = i1 - d;
if (lim2 < i2) if (lim2 < i2)
i1 = lim2 + d, i2 = lim2; i1 = lim2 + d, i2 = lim2;
if (fbest < i1 + i2) { if (fbest < i1 + i2) {
} }
/* /*
* Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling * 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) * the box splitting function. Note that the real job (marking changed lines)
* is done in the two boundary reaching checks. * is done in the two boundary reaching checks.
*/ */
int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1, int xdl_recs_cmp(diffdata_t *dd1, int64_t off1, int64_t lim1,
diffdata_t *dd2, long off2, long lim2, diffdata_t *dd2, int64_t off2, int64_t lim2,
long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) { int64_t *kvdf, int64_t *kvdb, int need_min, xdalgoenv_t *xenv) {
unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha; uint64_t const *ha1 = dd1->ha, *ha2 = dd2->ha;
/* /*
* Shrink the box by walking through each diagonal snake (SW and NE). * 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[off1] == ha2[off2]; off1++, off2++);
for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--); 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 * If one dimension is empty, then all records on the other one must
* be obviously changed. * be obviously changed.
*/ */
if (off1 == lim1) { if (off1 == lim1) {
char *rchg2 = dd2->rchg; char *rchg2 = dd2->rchg;
long *rindex2 = dd2->rindex; int64_t *rindex2 = dd2->rindex;
for (; off2 < lim2; off2++) for (; off2 < lim2; off2++)
rchg2[rindex2[off2]] = 1; rchg2[rindex2[off2]] = 1;
} else if (off2 == lim2) { } else if (off2 == lim2) {
char *rchg1 = dd1->rchg; char *rchg1 = dd1->rchg;
long *rindex1 = dd1->rindex; int64_t *rindex1 = dd1->rindex;
for (; off1 < lim1; off1++) for (; off1 < lim1; off1++)
rchg1[rindex1[off1]] = 1; rchg1[rindex1[off1]] = 1;
} else { } else {
xdpsplit_t spl; xdpsplit_t spl;
spl.i1 = spl.i2 = 0; spl.i1 = spl.i2 = 0;
/* /*
} }
return 0; return 0;
} }
int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdfenv_t *xe) { xdfenv_t *xe) {
long ndiags; int64_t ndiags;
long *kvd, *kvdf, *kvdb; int64_t *kvd, *kvdf, *kvdb;
xdalgoenv_t xenv; xdalgoenv_t xenv;
diffdata_t dd1, dd2; diffdata_t dd1, dd2;
if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) { if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
return -1; return -1;
} }
/* /*
* Allocate and setup K vectors to be used by the differential algorithm. * 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. * One is to store the forward path and one to store the backward path.
*/ */
ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3; ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) { if (!(kvd = (int64_t *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {
xdl_free_env(xe); xdl_free_env(xe);
return -1; return -1;
} }
kvdf = kvd; kvdf = kvd;
kvdb = kvdf + ndiags; kvdb = kvdf + ndiags;
kvdf += xe->xdf2.nreff + 1; kvdf += xe->xdf2.nreff + 1;
kvdb += xe->xdf2.nreff + 1; kvdb += xe->xdf2.nreff + 1;
} }
xdl_free(kvd); xdl_free(kvd);
return 0; return 0;
} }
static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) { static xdchange_t *xdl_add_change(xdchange_t *xscr, int64_t i1, int64_t i2, int64_t chg1, int64_t chg2) {
xdchange_t *xch; xdchange_t *xch;
if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t)))) if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t))))
return NULL; return NULL;
xch->next = xscr; xch->next = xscr;
xch->i1 = i1; xch->i1 = i1;
xch->i2 = i2; xch->i2 = i2;
xch->chg1 = chg1; xch->chg1 = chg1;
xch->chg2 = chg2; xch->chg2 = chg2;
xch->ignore = 0; xch->ignore = 0;
return xch; return xch;
} }
static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags) static int recs_match(xrecord_t *rec1, xrecord_t *rec2, int64_t flags)
{ {
return (rec1->ha == rec2->ha && return (rec1->ha == rec2->ha &&
xdl_recmatch(rec1->ptr, rec1->size, xdl_recmatch(rec1->ptr, rec1->size,
rec2->ptr, rec2->size, rec2->ptr, rec2->size,
flags)); flags));
} }
/* /*
* If a line is indented more than this, get_indent() just returns this value. * If a line is indented more than this, get_indent() just returns this value.
* This avoids having to do absurd amounts of work for data that are not * This avoids having to do absurd amounts of work for data that are not
* human-readable text, and also ensures that the output of get_indent fits within * human-readable text, and also ensures that the output of get_indent fits within
* an int. * an int.
*/ */
#define MAX_INDENT 200 #define MAX_INDENT 200
/* /*
* Return the amount of indentation of the specified line, treating TAB as 8 * Return the amount of indentation of the specified line, treating TAB as 8
* columns. Return -1 if line is empty or contains only whitespace. Clamp the * columns. Return -1 if line is empty or contains only whitespace. Clamp the
* output value at MAX_INDENT. * output value at MAX_INDENT.
*/ */
static int get_indent(xrecord_t *rec) static int get_indent(xrecord_t *rec)
{ {
long i; int64_t i;
int ret = 0; int ret = 0;
for (i = 0; i < rec->size; i++) { for (i = 0; i < rec->size; i++) {
char c = rec->ptr[i]; char c = rec->ptr[i];
if (!XDL_ISSPACE(c)) if (!XDL_ISSPACE(c))
return ret; return ret;
else if (c == ' ') else if (c == ' ')
/* Penalty for this split (smaller is preferred). */ /* Penalty for this split (smaller is preferred). */
int penalty; int penalty;
}; };
/* /*
* Fill m with information about a hypothetical split of xdf above line split. * Fill m with information about a hypothetical split of xdf above line split.
*/ */
static void measure_split(const xdfile_t *xdf, long split, static void measure_split(const xdfile_t *xdf, int64_t split,
struct split_measurement *m) struct split_measurement *m)
{ {
long i; int64_t i;
if (split >= xdf->nrec) { if (split >= xdf->nrec) {
m->end_of_file = 1; m->end_of_file = 1;
m->indent = -1; m->indent = -1;
} else { } else {
m->end_of_file = 0; m->end_of_file = 0;
m->indent = get_indent(xdf->recs[split]); m->indent = get_indent(xdf->recs[split]);
} }
* Note that loops that are testing for changed lines in xdf->rchg do not need * Note that loops that are testing for changed lines in xdf->rchg do not need
* index bounding since the array is prepared with a zero at position -1 and N. * index bounding since the array is prepared with a zero at position -1 and N.
*/ */
struct xdlgroup { struct xdlgroup {
/* /*
* The index of the first changed line in the group, or the index of * The index of the first changed line in the group, or the index of
* the unchanged line above which the (empty) group is located. * the unchanged line above which the (empty) group is located.
*/ */
long start; int64_t start;
/* /*
* The index of the first unchanged line after the group. For an empty * The index of the first unchanged line after the group. For an empty
* group, end is equal to start. * group, end is equal to start.
*/ */
long end; int64_t end;
}; };
/* /*
* Initialize g to point at the first group in xdf. * Initialize g to point at the first group in xdf.
*/ */
static void group_init(xdfile_t *xdf, struct xdlgroup *g) static void group_init(xdfile_t *xdf, struct xdlgroup *g)
{ {
g->start = g->end = 0; g->start = g->end = 0;
return 0; return 0;
} }
/* /*
* If g can be slid toward the end of the file, do so, and if it bumps into a * If g can be slid toward the end of the file, do so, and if it bumps into a
* following group, expand this group to include it. Return 0 on success or -1 * following group, expand this group to include it. Return 0 on success or -1
* if g cannot be slid down. * if g cannot be slid down.
*/ */
static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags) static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, int64_t flags)
{ {
if (g->end < xdf->nrec && if (g->end < xdf->nrec &&
recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) { recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) {
xdf->rchg[g->start++] = 0; xdf->rchg[g->start++] = 0;
xdf->rchg[g->end++] = 1; xdf->rchg[g->end++] = 1;
while (xdf->rchg[g->end]) while (xdf->rchg[g->end])
g->end++; g->end++;
return 0; return 0;
} else { } else {
return -1; return -1;
} }
} }
/* /*
* If g can be slid toward the beginning of the file, do so, and if it bumps * If g can be slid toward the beginning of the file, do so, and if it bumps
* into a previous group, expand this group to include it. Return 0 on success * into a previous group, expand this group to include it. Return 0 on success
* or -1 if g cannot be slid up. * or -1 if g cannot be slid up.
*/ */
static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g, long flags) static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g, int64_t flags)
{ {
if (g->start > 0 && if (g->start > 0 &&
recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) { recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) {
xdf->rchg[--g->start] = 1; xdf->rchg[--g->start] = 1;
xdf->rchg[--g->end] = 0; xdf->rchg[--g->end] = 0;
while (xdf->rchg[g->start - 1]) while (xdf->rchg[g->start - 1])
g->start--; g->start--;
*/ */
#define MAX_BORING 100 #define MAX_BORING 100
/* /*
* Move back and forward change groups for a consistent and pretty diff output. * Move back and forward change groups for a consistent and pretty diff output.
* This also helps in finding joinable change groups and reducing the diff * This also helps in finding joinable change groups and reducing the diff
* size. * size.
*/ */
int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, int64_t flags) {
struct xdlgroup g, go; struct xdlgroup g, go;
long earliest_end, end_matching_other; int64_t earliest_end, end_matching_other;
long groupsize; int64_t groupsize;
group_init(xdf, &g); group_init(xdf, &g);
group_init(xdfo, &go); group_init(xdfo, &go);
while (1) { while (1) {
/* If the group is empty in the to-be-compacted file, skip it: */ /* If the group is empty in the to-be-compacted file, skip it: */
if (g.end == g.start) if (g.end == g.start)
goto next; goto next;
* context and the start of the group, and another between * context and the start of the group, and another between
* the end of the group and the beginning of the "after" * the end of the group and the beginning of the "after"
* context. Some splits are aesthetically better and some * context. Some splits are aesthetically better and some
* are worse. We compute a badness "score" for each split, * are worse. We compute a badness "score" for each split,
* and add the scores for the two splits to define a * and add the scores for the two splits to define a
* "score" for each position that the group can be shifted * "score" for each position that the group can be shifted
* to. Then we pick the shift with the lowest score. * to. Then we pick the shift with the lowest score.
*/ */
long shift, best_shift = -1; int64_t shift, best_shift = -1;
struct split_score best_score; struct split_score best_score;
/* /*
* This is O(N * MAX_BLANKS) (N = shift-able lines). * This is O(N * MAX_BLANKS) (N = shift-able lines).
* Even with MAX_BLANKS bounded to a small value, a * Even with MAX_BLANKS bounded to a small value, a
* large N could still make this loop take several * large N could still make this loop take several
* times longer than the main diff algorithm. The * times longer than the main diff algorithm. The
* "boring" value is to help cut down N to something * "boring" value is to help cut down N to something
return 0; return 0;
} }
int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
xdchange_t *cscr = NULL, *xch; xdchange_t *cscr = NULL, *xch;
char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg; char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;
long i1, i2, l1, l2; int64_t i1, i2, l1, l2;
/* /*
* Trivial. Collects "groups" of changes and creates an edit script. * 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--) for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--)
if (rchg1[i1 - 1] || rchg2[i2 - 1]) { if (rchg1[i1 - 1] || rchg2[i2 - 1]) {
for (l1 = i1; rchg1[i1 - 1]; i1--); for (l1 = i1; rchg1[i1 - 1]; i1--);
for (l2 = i2; rchg2[i2 - 1]; i2--); for (l2 = i2; rchg2[i2 - 1]; i2--);
/* /*
* Starting at the passed change atom, find the latest change atom to be included * Starting at the passed change atom, find the latest change atom to be included
* inside the differential hunk according to the specified configuration. * inside the differential hunk according to the specified configuration.
* Also advance xscr if the first changes must be discarded. * Also advance xscr if the first changes must be discarded.
*/ */
xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg) xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg)
{ {
xdchange_t *xch, *xchp, *lxch; xdchange_t *xch, *xchp, *lxch;
long max_common = 0; int64_t max_common = 0;
long max_ignorable = 0; int64_t max_ignorable = 0;
unsigned long ignored = 0; /* number of ignored blank lines */ uint64_t ignored = 0; /* number of ignored blank lines */
/* remove ignorable changes that are too far before other changes */ /* remove ignorable changes that are too far before other changes */
for (xchp = *xscr; xchp && xchp->ignore; xchp = xchp->next) { for (xchp = *xscr; xchp && xchp->ignore; xchp = xchp->next) {
xch = xchp->next; xch = xchp->next;
if (xch == NULL || if (xch == NULL ||
xch->i1 - (xchp->i1 + xchp->chg1) >= max_ignorable) xch->i1 - (xchp->i1 + xchp->chg1) >= max_ignorable)
*xscr = xch; *xscr = xch;
} }
if (*xscr == NULL) if (*xscr == NULL)
return NULL; return NULL;
lxch = *xscr; lxch = *xscr;
for (xchp = *xscr, xch = xchp->next; xch; xchp = xch, xch = xch->next) { for (xchp = *xscr, xch = xchp->next; xch; xchp = xch, xch = xch->next) {
long distance = xch->i1 - (xchp->i1 + xchp->chg1); int64_t distance = xch->i1 - (xchp->i1 + xchp->chg1);
if (distance > max_common) if (distance > max_common)
break; break;
if (distance < max_ignorable && (!xch->ignore || lxch == xchp)) { if (distance < max_ignorable && (!xch->ignore || lxch == xchp)) {
lxch = xch; lxch = xch;
ignored = 0; ignored = 0;
} else if (distance < max_ignorable && xch->ignore) { } else if (distance < max_ignorable && xch->ignore) {
ignored += xch->chg2; ignored += xch->chg2;
return lxch; return lxch;
} }
static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb,
xdemitconf_t const *xecfg) xdemitconf_t const *xecfg)
{ {
long p = xe->nprefix, s = xe->nsuffix; int64_t p = xe->nprefix, s = xe->nsuffix;
xdchange_t *xch, *xche; xdchange_t *xch, *xche;
if (!xecfg->hunk_func) if (!xecfg->hunk_func)
return -1; return -1;
if ((xecfg->flags & XDL_EMIT_BDIFFHUNK) != 0) { if ((xecfg->flags & XDL_EMIT_BDIFFHUNK) != 0) {
long i1 = 0, i2 = 0, n1 = xe->xdf1.nrec, n2 = xe->xdf2.nrec; int64_t i1 = 0, i2 = 0, n1 = xe->xdf1.nrec, n2 = xe->xdf2.nrec;
for (xch = xscr; xch; xch = xche->next) { for (xch = xscr; xch; xch = xche->next) {
xche = xdl_get_hunk(&xch, xecfg); xche = xdl_get_hunk(&xch, xecfg);
if (!xch) if (!xch)
break; break;
if (xch != xche) if (xch != xche)
xdl_bug("xch != xche"); xdl_bug("xch != xche");
xch->i1 += p; xch->i1 += p;
xch->i2 += p; xch->i2 += p;

mercurial/thirdparty/xdiff/xinclude.h

* Davide Libenzi <davidel@xmailserver.org> * Davide Libenzi <davidel@xmailserver.org>
* *
*/ */
#if !defined(XINCLUDE_H) #if !defined(XINCLUDE_H)
#define XINCLUDE_H #define XINCLUDE_H
#include <ctype.h> #include <ctype.h>
#include <stdint.h>
#include <stdio.h> #include <stdio.h>
#include <stdlib.h> #include <stdlib.h>
#include <string.h> #include <string.h>
#include <limits.h> #include <limits.h>
#include "xmacros.h" #include "xmacros.h"
#include "xdiff.h" #include "xdiff.h"
#include "xtypes.h" #include "xtypes.h"
#include "xutils.h" #include "xutils.h"
#include "xprepare.h" #include "xprepare.h"
#include "xdiffi.h" #include "xdiffi.h"
#endif /* #if !defined(XINCLUDE_H) */ #endif /* #if !defined(XINCLUDE_H) */

mercurial/thirdparty/xdiff/xprepare.c

#define XDL_KPDIS_RUN 4 #define XDL_KPDIS_RUN 4
#define XDL_MAX_EQLIMIT 1024 #define XDL_MAX_EQLIMIT 1024
#define XDL_SIMSCAN_WINDOW 100 #define XDL_SIMSCAN_WINDOW 100
#define XDL_GUESS_NLINES1 256 #define XDL_GUESS_NLINES1 256
typedef struct s_xdlclass { typedef struct s_xdlclass {
struct s_xdlclass *next; struct s_xdlclass *next;
unsigned long ha; uint64_t ha;
char const *line; char const *line;
long size; int64_t size;
long idx; int64_t idx;
long len1, len2; int64_t len1, len2;
} xdlclass_t; } xdlclass_t;
typedef struct s_xdlclassifier { typedef struct s_xdlclassifier {
unsigned int hbits; unsigned int hbits;
long hsize; int64_t hsize;
xdlclass_t **rchash; xdlclass_t **rchash;
chastore_t ncha; chastore_t ncha;
xdlclass_t **rcrecs; xdlclass_t **rcrecs;
long alloc; int64_t alloc;
long count; int64_t count;
long flags; int64_t flags;
} xdlclassifier_t; } xdlclassifier_t;
static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags); static int xdl_init_classifier(xdlclassifier_t *cf, int64_t size, int64_t flags);
static void xdl_free_classifier(xdlclassifier_t *cf); static void xdl_free_classifier(xdlclassifier_t *cf);
static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash, static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
unsigned int hbits, xrecord_t *rec); unsigned int hbits, xrecord_t *rec);
static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp, static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, int64_t narec, xpparam_t const *xpp,
xdlclassifier_t *cf, xdfile_t *xdf); xdlclassifier_t *cf, xdfile_t *xdf);
static void xdl_free_ctx(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_clean_mmatch(char const *dis, int64_t i, int64_t s, int64_t e);
static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2); static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2); static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2);
static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2); static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2);
static int xdl_init_classifier(xdlclassifier_t *cf, long size, long flags) { static int xdl_init_classifier(xdlclassifier_t *cf, int64_t size, int64_t flags) {
cf->flags = flags; cf->flags = flags;
cf->hbits = xdl_hashbits((unsigned int) size); cf->hbits = xdl_hashbits((unsigned int) size);
cf->hsize = 1 << cf->hbits; cf->hsize = 1 << cf->hbits;
if (xdl_cha_init(&cf->ncha, sizeof(xdlclass_t), size / 4 + 1) < 0) { if (xdl_cha_init(&cf->ncha, sizeof(xdlclass_t), size / 4 + 1) < 0) {
return -1; return -1;
xdl_free(cf->rcrecs); xdl_free(cf->rcrecs);
xdl_free(cf->rchash); xdl_free(cf->rchash);
xdl_cha_free(&cf->ncha); xdl_cha_free(&cf->ncha);
} }
static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash, static int xdl_classify_record(unsigned int pass, xdlclassifier_t *cf, xrecord_t **rhash,
unsigned int hbits, xrecord_t *rec) { unsigned int hbits, xrecord_t *rec) {
long hi; int64_t hi;
char const *line; char const *line;
xdlclass_t *rcrec; xdlclass_t *rcrec;
xdlclass_t **rcrecs; xdlclass_t **rcrecs;
line = rec->ptr; line = rec->ptr;
hi = (long) XDL_HASHLONG(rec->ha, cf->hbits); hi = (long) XDL_HASHLONG(rec->ha, cf->hbits);
for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next) for (rcrec = cf->rchash[hi]; rcrec; rcrec = rcrec->next)
if (rcrec->ha == rec->ha && if (rcrec->ha == rec->ha &&
/* /*
* Trim common prefix from files. * Trim common prefix from files.
* *
* Note: trimming could affect hunk shifting. But the performance benefit * Note: trimming could affect hunk shifting. But the performance benefit
* outweighs the shift change. A diff result with suboptimal shifting is still * outweighs the shift change. A diff result with suboptimal shifting is still
* valid. * valid.
*/ */
static void xdl_trim_files(mmfile_t *mf1, mmfile_t *mf2, long reserved, static void xdl_trim_files(mmfile_t *mf1, mmfile_t *mf2, int64_t reserved,
xdfenv_t *xe, mmfile_t *out_mf1, mmfile_t *out_mf2) { xdfenv_t *xe, mmfile_t *out_mf1, mmfile_t *out_mf2) {
mmfile_t msmall, mlarge; mmfile_t msmall, mlarge;
/* prefix lines, prefix bytes, suffix lines, suffix bytes */ /* prefix lines, prefix bytes, suffix lines, suffix bytes */
long plines = 0, pbytes = 0, slines = 0, sbytes = 0, i; int64_t plines = 0, pbytes = 0, slines = 0, sbytes = 0, i;
/* prefix char pointer for msmall and mlarge */ /* prefix char pointer for msmall and mlarge */
const char *pp1, *pp2; const char *pp1, *pp2;
/* suffix char pointer for msmall and mlarge */ /* suffix char pointer for msmall and mlarge */
const char *ps1, *ps2; const char *ps1, *ps2;
/* reserved must >= 0 for the line boundary adjustment to work */ /* reserved must >= 0 for the line boundary adjustment to work */
if (reserved < 0) if (reserved < 0)
reserved = 0; reserved = 0;
xe->nsuffix = slines; xe->nsuffix = slines;
out_mf1->ptr = mf1->ptr + pbytes; out_mf1->ptr = mf1->ptr + pbytes;
out_mf1->size = mf1->size - pbytes - sbytes; out_mf1->size = mf1->size - pbytes - sbytes;
out_mf2->ptr = mf2->ptr + pbytes; out_mf2->ptr = mf2->ptr + pbytes;
out_mf2->size = mf2->size - pbytes - sbytes; out_mf2->size = mf2->size - pbytes - sbytes;
} }
static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_t const *xpp, static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, int64_t narec, xpparam_t const *xpp,
xdlclassifier_t *cf, xdfile_t *xdf) { xdlclassifier_t *cf, xdfile_t *xdf) {
unsigned int hbits; unsigned int hbits;
long nrec, hsize, bsize; int64_t nrec, hsize, bsize;
unsigned long hav; uint64_t hav;
char const *blk, *cur, *top, *prev; char const *blk, *cur, *top, *prev;
xrecord_t *crec; xrecord_t *crec;
xrecord_t **recs, **rrecs; xrecord_t **recs, **rrecs;
xrecord_t **rhash; xrecord_t **rhash;
unsigned long *ha; uint64_t *ha;
char *rchg; char *rchg;
long *rindex; int64_t *rindex;
ha = NULL; ha = NULL;
rindex = NULL; rindex = NULL;
rchg = NULL; rchg = NULL;
rhash = NULL; rhash = NULL;
recs = NULL; recs = NULL;
if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)
goto abort; goto abort;
} }
} }
if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char))))
goto abort; goto abort;
memset(rchg, 0, (nrec + 2) * sizeof(char)); memset(rchg, 0, (nrec + 2) * sizeof(char));
if (!(rindex = (long *) xdl_malloc((nrec + 1) * sizeof(long)))) if (!(rindex = (int64_t *) xdl_malloc((nrec + 1) * sizeof(long))))
goto abort; goto abort;
if (!(ha = (unsigned long *) xdl_malloc((nrec + 1) * sizeof(unsigned long)))) if (!(ha = (uint64_t *) xdl_malloc((nrec + 1) * sizeof(unsigned long))))
goto abort; goto abort;
xdf->nrec = nrec; xdf->nrec = nrec;
xdf->recs = recs; xdf->recs = recs;
xdf->hbits = hbits; xdf->hbits = hbits;
xdf->rhash = rhash; xdf->rhash = rhash;
xdf->rchg = rchg + 1; xdf->rchg = rchg + 1;
xdf->rindex = rindex; xdf->rindex = rindex;
xdl_cha_free(&xdf->rcha); xdl_cha_free(&xdf->rcha);
} }
/* Reserved lines for trimming, to leave room for shifting */ /* Reserved lines for trimming, to leave room for shifting */
#define TRIM_RESERVED_LINES 100 #define TRIM_RESERVED_LINES 100
int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdfenv_t *xe) { xdfenv_t *xe) {
long enl1, enl2, sample; int64_t enl1, enl2, sample;
mmfile_t tmf1, tmf2; mmfile_t tmf1, tmf2;
xdlclassifier_t cf; xdlclassifier_t cf;
memset(&cf, 0, sizeof(cf)); memset(&cf, 0, sizeof(cf));
sample = XDL_GUESS_NLINES1; sample = XDL_GUESS_NLINES1;
enl1 = xdl_guess_lines(mf1, sample) + 1; enl1 = xdl_guess_lines(mf1, sample) + 1;
void xdl_free_env(xdfenv_t *xe) { void xdl_free_env(xdfenv_t *xe) {
xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf2);
xdl_free_ctx(&xe->xdf1); xdl_free_ctx(&xe->xdf1);
} }
static int xdl_clean_mmatch(char const *dis, long i, long s, long e) { static int xdl_clean_mmatch(char const *dis, int64_t i, int64_t s, int64_t e) {
long r, rdis0, rpdis0, rdis1, rpdis1; int64_t r, rdis0, rpdis0, rdis1, rpdis1;
/* /*
* Limits the window the is examined during the similar-lines * Limits the window the is examined during the similar-lines
* scan. The loops below stops when dis[i - r] == 1 (line that * scan. The loops below stops when dis[i - r] == 1 (line that
* has no match), but there are corner cases where the loop * has no match), but there are corner cases where the loop
* proceed all the way to the extremities by causing huge * proceed all the way to the extremities by causing huge
* performance penalties in case of big files. * performance penalties in case of big files.
*/ */
/* /*
* Try to reduce the problem complexity, discard records that have no * Try to reduce the problem complexity, discard records that have no
* matches on the other file. Also, lines that have multiple matches * matches on the other file. Also, lines that have multiple matches
* might be potentially discarded if they happear in a run of discardable. * might be potentially discarded if they happear in a run of discardable.
*/ */
static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) { static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
long i, nm, nreff, mlim; int64_t i, nm, nreff, mlim;
xrecord_t **recs; xrecord_t **recs;
xdlclass_t *rcrec; xdlclass_t *rcrec;
char *dis, *dis1, *dis2; char *dis, *dis1, *dis2;
if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) { if (!(dis = (char *) xdl_malloc(xdf1->nrec + xdf2->nrec + 2))) {
return -1; return -1;
} }
return 0; return 0;
} }
/* /*
* Early trim initial and terminal matching records. * Early trim initial and terminal matching records.
*/ */
static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) { static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
long i, lim; int64_t i, lim;
xrecord_t **recs1, **recs2; xrecord_t **recs1, **recs2;
recs1 = xdf1->recs; recs1 = xdf1->recs;
recs2 = xdf2->recs; recs2 = xdf2->recs;
for (i = 0, lim = XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim; for (i = 0, lim = XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim;
i++, recs1++, recs2++) i++, recs1++, recs2++)
if ((*recs1)->ha != (*recs2)->ha) if ((*recs1)->ha != (*recs2)->ha)
break; break;

mercurial/thirdparty/xdiff/xtypes.h

#if !defined(XTYPES_H) #if !defined(XTYPES_H)
#define XTYPES_H #define XTYPES_H
typedef struct s_chanode { typedef struct s_chanode {
struct s_chanode *next; struct s_chanode *next;
long icurr; int64_t icurr;
} chanode_t; } chanode_t;
typedef struct s_chastore { typedef struct s_chastore {
chanode_t *head, *tail; chanode_t *head, *tail;
long isize, nsize; int64_t isize, nsize;
chanode_t *ancur; chanode_t *ancur;
chanode_t *sncur; chanode_t *sncur;
long scurr; int64_t scurr;
} chastore_t; } chastore_t;
typedef struct s_xrecord { typedef struct s_xrecord {
struct s_xrecord *next; struct s_xrecord *next;
char const *ptr; char const *ptr;
long size; int64_t size;
unsigned long ha; uint64_t ha;
} xrecord_t; } xrecord_t;
typedef struct s_xdfile { typedef struct s_xdfile {
/* manual memory management */ /* manual memory management */
chastore_t rcha; chastore_t rcha;
/* number of records (lines) */ /* number of records (lines) */
long nrec; int64_t nrec;
/* hash table size /* hash table size
* the maximum hash value in the table is (1 << hbits) */ * the maximum hash value in the table is (1 << hbits) */
unsigned int hbits; unsigned int hbits;
/* hash table, hash value => xrecord_t /* hash table, hash value => xrecord_t
* note: xrecord_t is a linked list. */ * note: xrecord_t is a linked list. */
xrecord_t **rhash; xrecord_t **rhash;
/* range excluding common prefix and suffix /* range excluding common prefix and suffix
* [recs[i] for i in range(0, dstart)] are common prefix. * [recs[i] for i in range(0, dstart)] are common prefix.
* [recs[i] for i in range(dstart, dend + 1 - dstart)] are interesting * [recs[i] for i in range(dstart, dend + 1 - dstart)] are interesting
* lines */ * lines */
long dstart, dend; int64_t dstart, dend;
/* pointer to records (lines) */ /* pointer to records (lines) */
xrecord_t **recs; xrecord_t **recs;
/* record changed, use original "recs" index /* record changed, use original "recs" index
* rchag[i] can be either 0 or 1. 1 means recs[i] (line i) is marked * rchag[i] can be either 0 or 1. 1 means recs[i] (line i) is marked
* "changed". */ * "changed". */
char *rchg; char *rchg;
/* cleaned-up record index => original "recs" index /* cleaned-up record index => original "recs" index
* clean-up means: * clean-up means:
* rule 1. remove common prefix and suffix * rule 1. remove common prefix and suffix
* rule 2. remove records that are only on one side, since they can * rule 2. remove records that are only on one side, since they can
* not match the other side * not match the other side
* rindex[0] is likely dstart, if not removed up by rule 2. * rindex[0] is likely dstart, if not removed up by rule 2.
* rindex[nreff - 1] is likely dend, if not removed by rule 2. * rindex[nreff - 1] is likely dend, if not removed by rule 2.
*/ */
long *rindex; int64_t *rindex;
/* rindex size */ /* rindex size */
long nreff; int64_t nreff;
/* cleaned-up record index => hash value /* cleaned-up record index => hash value
* ha[i] = recs[rindex[i]]->ha */ * ha[i] = recs[rindex[i]]->ha */
unsigned long *ha; uint64_t *ha;
} xdfile_t; } xdfile_t;
typedef struct s_xdfenv { typedef struct s_xdfenv {
xdfile_t xdf1, xdf2; xdfile_t xdf1, xdf2;
/* number of lines for common prefix and suffix that are removed /* number of lines for common prefix and suffix that are removed
* from xdf1 and xdf2 as a preprocessing step */ * from xdf1 and xdf2 as a preprocessing step */
long nprefix, nsuffix; int64_t nprefix, nsuffix;
} xdfenv_t; } xdfenv_t;
#endif /* #if !defined(XTYPES_H) */ #endif /* #if !defined(XTYPES_H) */

mercurial/thirdparty/xdiff/xutils.h

* *
*/ */
#if !defined(XUTILS_H) #if !defined(XUTILS_H)
#define XUTILS_H #define XUTILS_H
long xdl_bogosqrt(long n); int64_t xdl_bogosqrt(int64_t n);
int xdl_cha_init(chastore_t *cha, long isize, long icount); int xdl_cha_init(chastore_t *cha, int64_t isize, int64_t icount);
void xdl_cha_free(chastore_t *cha); void xdl_cha_free(chastore_t *cha);
void *xdl_cha_alloc(chastore_t *cha); void *xdl_cha_alloc(chastore_t *cha);
long xdl_guess_lines(mmfile_t *mf, long sample); int64_t xdl_guess_lines(mmfile_t *mf, int64_t sample);
int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags); int xdl_recmatch(const char *l1, int64_t s1, const char *l2, int64_t s2, int64_t flags);
unsigned long xdl_hash_record(char const **data, char const *top, long flags); uint64_t xdl_hash_record(char const **data, char const *top, int64_t flags);
unsigned int xdl_hashbits(unsigned int size); unsigned int xdl_hashbits(unsigned int size);
#endif /* #if !defined(XUTILS_H) */ #endif /* #if !defined(XUTILS_H) */

mercurial/thirdparty/xdiff/xutils.c

#include <limits.h> #include <limits.h>
#include <assert.h> #include <assert.h>
#include "xinclude.h" #include "xinclude.h"
long xdl_bogosqrt(long n) { int64_t xdl_bogosqrt(int64_t n) {
long i; int64_t i;
/* /*
* Classical integer square root approximation using shifts. * Classical integer square root approximation using shifts.
*/ */
for (i = 1; n > 0; n >>= 2) for (i = 1; n > 0; n >>= 2)
i <<= 1; i <<= 1;
return i; return i;
} }
void *xdl_mmfile_first(mmfile_t *mmf, long *size) void *xdl_mmfile_first(mmfile_t *mmf, int64_t *size)
{ {
*size = mmf->size; *size = mmf->size;
return mmf->ptr; return mmf->ptr;
} }
long xdl_mmfile_size(mmfile_t *mmf) int64_t xdl_mmfile_size(mmfile_t *mmf)
{ {
return mmf->size; return mmf->size;
} }
int xdl_cha_init(chastore_t *cha, long isize, long icount) { int xdl_cha_init(chastore_t *cha, int64_t isize, int64_t icount) {
cha->head = cha->tail = NULL; cha->head = cha->tail = NULL;
cha->isize = isize; cha->isize = isize;
cha->nsize = icount * isize; cha->nsize = icount * isize;
cha->ancur = cha->sncur = NULL; cha->ancur = cha->sncur = NULL;
cha->scurr = 0; cha->scurr = 0;
return 0; return 0;
} }
data = (char *) ancur + sizeof(chanode_t) + ancur->icurr; data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
ancur->icurr += cha->isize; ancur->icurr += cha->isize;
return data; return data;
} }
long xdl_guess_lines(mmfile_t *mf, long sample) { int64_t xdl_guess_lines(mmfile_t *mf, int64_t sample) {
long nl = 0, size, tsize = 0; int64_t nl = 0, size, tsize = 0;
char const *data, *cur, *top; char const *data, *cur, *top;
if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) { if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
for (top = data + size; nl < sample && cur < top; ) { for (top = data + size; nl < sample && cur < top; ) {
nl++; nl++;
if (!(cur = memchr(cur, '\n', top - cur))) if (!(cur = memchr(cur, '\n', top - cur)))
cur = top; cur = top;
else else
cur++; cur++;
} }
tsize += (long) (cur - data); tsize += (long) (cur - data);
} }
if (nl && tsize) if (nl && tsize)
nl = xdl_mmfile_size(mf) / (tsize / nl); nl = xdl_mmfile_size(mf) / (tsize / nl);
return nl + 1; return nl + 1;
} }
int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) int xdl_recmatch(const char *l1, int64_t s1, const char *l2, int64_t s2, int64_t flags)
{ {
if (s1 == s2 && !memcmp(l1, l2, s1)) if (s1 == s2 && !memcmp(l1, l2, s1))
return 1; return 1;
return 0; return 0;
} }
unsigned long xdl_hash_record(char const **data, char const *top, long flags) { uint64_t xdl_hash_record(char const **data, char const *top, int64_t flags) {
unsigned long ha = 5381; uint64_t ha = 5381;
char const *ptr = *data; char const *ptr = *data;
for (; ptr < top && *ptr != '\n'; ptr++) { for (; ptr < top && *ptr != '\n'; ptr++) {
ha += (ha << 5); ha += (ha << 5);
ha ^= (unsigned long) *ptr; ha ^= (unsigned long) *ptr;
} }
*data = ptr < top ? ptr + 1: ptr; *data = ptr < top ? ptr + 1: ptr;