diff options
Diffstat (limited to 'xdiff')
| -rw-r--r-- | xdiff/xdiff.h | 16 | ||||
| -rw-r--r-- | xdiff/xdiffi.c | 21 | ||||
| -rw-r--r-- | xdiff/xhistogram.c | 2 | ||||
| -rw-r--r-- | xdiff/xpatience.c | 2 | ||||
| -rw-r--r-- | xdiff/xprepare.c | 21 | ||||
| -rw-r--r-- | xdiff/xutils.c | 149 | ||||
| -rw-r--r-- | xdiff/xutils.h | 3 |
7 files changed, 144 insertions, 70 deletions
diff --git a/xdiff/xdiff.h b/xdiff/xdiff.h index 00d36c3ac7..219a3bbca6 100644 --- a/xdiff/xdiff.h +++ b/xdiff/xdiff.h @@ -32,14 +32,12 @@ extern "C" { #define XDF_IGNORE_WHITESPACE (1 << 2) #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 3) #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 4) -#define XDF_PATIENCE_DIFF (1 << 5) -#define XDF_HISTOGRAM_DIFF (1 << 6) #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | XDF_IGNORE_WHITESPACE_CHANGE | XDF_IGNORE_WHITESPACE_AT_EOL) -#define XDL_PATCH_NORMAL '-' -#define XDL_PATCH_REVERSE '+' -#define XDL_PATCH_MODEMASK ((1 << 8) - 1) -#define XDL_PATCH_IGNOREBSPACE (1 << 8) +#define XDF_PATIENCE_DIFF (1 << 5) +#define XDF_HISTOGRAM_DIFF (1 << 6) +#define XDF_DIFF_ALGORITHM_MASK (XDF_PATIENCE_DIFF | XDF_HISTOGRAM_DIFF) +#define XDF_DIFF_ALG(x) ((x) & XDF_DIFF_ALGORITHM_MASK) #define XDL_EMIT_FUNCNAMES (1 << 0) #define XDL_EMIT_COMMON (1 << 1) @@ -88,13 +86,17 @@ typedef struct s_xdemitcb { typedef long (*find_func_t)(const char *line, long line_len, char *buffer, long buffer_size, void *priv); +typedef int (*xdl_emit_hunk_consume_func_t)(long start_a, long count_a, + long start_b, long count_b, + void *cb_data); + typedef struct s_xdemitconf { long ctxlen; long interhunkctxlen; unsigned long flags; find_func_t find_func; void *find_func_priv; - void (*emit_func)(); + xdl_emit_hunk_consume_func_t hunk_func; } xdemitconf_t; typedef struct s_bdiffparam { diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c index 75a3922750..1b7012a119 100644 --- a/xdiff/xdiffi.c +++ b/xdiff/xdiffi.c @@ -328,10 +328,10 @@ int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdalgoenv_t xenv; diffdata_t dd1, dd2; - if (xpp->flags & XDF_PATIENCE_DIFF) + if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) return xdl_do_patience_diff(mf1, mf2, xpp, xe); - if (xpp->flags & XDF_HISTOGRAM_DIFF) + if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) return xdl_do_histogram_diff(mf1, mf2, xpp, xe); if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) { @@ -538,13 +538,26 @@ void xdl_free_script(xdchange_t *xscr) { } } +static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, + xdemitconf_t const *xecfg) +{ + xdchange_t *xch, *xche; + + for (xch = xscr; xch; xch = xche->next) { + xche = xdl_get_hunk(xch, xecfg); + if (xecfg->hunk_func(xch->i1, xche->i1 + xche->chg1 - xch->i1, + xch->i2, xche->i2 + xche->chg2 - xch->i2, + ecb->priv) < 0) + return -1; + } + return 0; +} 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; - emit_func_t ef = xecfg->emit_func ? - (emit_func_t)xecfg->emit_func : xdl_emit_diff; + emit_func_t ef = xecfg->hunk_func ? xdl_call_hunk_func : xdl_emit_diff; if (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) { diff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c index 18f6f997c3..bf99787c3e 100644 --- a/xdiff/xhistogram.c +++ b/xdiff/xhistogram.c @@ -252,7 +252,7 @@ static int fall_back_to_classic_diff(struct histindex *index, int line1, int count1, int line2, int count2) { xpparam_t xpp; - xpp.flags = index->xpp->flags & ~XDF_HISTOGRAM_DIFF; + xpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; return xdl_fall_back_diff(index->env, &xpp, line1, count1, line2, count2); diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c index fdd7d0263f..04e1a1ab2a 100644 --- a/xdiff/xpatience.c +++ b/xdiff/xpatience.c @@ -288,7 +288,7 @@ static int fall_back_to_classic_diff(struct hashmap *map, int line1, int count1, int line2, int count2) { xpparam_t xpp; - xpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF; + xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK; return xdl_fall_back_diff(map->env, &xpp, line1, count1, line2, count2); diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c index e419f4f726..63a22c630e 100644 --- a/xdiff/xprepare.c +++ b/xdiff/xprepare.c @@ -181,7 +181,7 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) goto abort; - if (xpp->flags & XDF_HISTOGRAM_DIFF) + if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) hbits = hsize = 0; else { hbits = xdl_hashbits((unsigned int) narec); @@ -209,8 +209,8 @@ static int xdl_prepare_ctx(unsigned int pass, mmfile_t *mf, long narec, xpparam_ crec->ha = hav; recs[nrec++] = crec; - if (!(xpp->flags & XDF_HISTOGRAM_DIFF) && - xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) + if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && + xdl_classify_record(pass, cf, rhash, hbits, crec) < 0) goto abort; } } @@ -273,16 +273,15 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, * (nrecs) will be updated correctly anyway by * xdl_prepare_ctx(). */ - sample = xpp->flags & XDF_HISTOGRAM_DIFF ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1; + sample = (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF + ? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1); enl1 = xdl_guess_lines(mf1, sample) + 1; enl2 = xdl_guess_lines(mf2, sample) + 1; - if (!(xpp->flags & XDF_HISTOGRAM_DIFF) && - xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) { - + if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF && + xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0) return -1; - } if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) { @@ -296,9 +295,9 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, return -1; } - if (!(xpp->flags & XDF_PATIENCE_DIFF) && - !(xpp->flags & XDF_HISTOGRAM_DIFF) && - xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { + if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && + (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && + xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf1); diff --git a/xdiff/xutils.c b/xdiff/xutils.c index 0de084e53f..9504eaecb8 100644 --- a/xdiff/xutils.c +++ b/xdiff/xutils.c @@ -20,6 +20,8 @@ * */ +#include <limits.h> +#include <assert.h> #include "xinclude.h" @@ -120,35 +122,6 @@ void *xdl_cha_alloc(chastore_t *cha) { 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 sample) { long nl = 0, size, tsize = 0; char const *data, *cur, *top; @@ -276,6 +249,109 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data, return ha; } +#ifdef XDL_FAST_HASH + +#define REPEAT_BYTE(x) ((~0ul / 0xff) * (x)) + +#define ONEBYTES REPEAT_BYTE(0x01) +#define NEWLINEBYTES REPEAT_BYTE(0x0a) +#define HIGHBITS REPEAT_BYTE(0x80) + +/* Return the high bit set in the first byte that is a zero */ +static inline unsigned long has_zero(unsigned long a) +{ + return ((a - ONEBYTES) & ~a) & HIGHBITS; +} + +static inline long count_masked_bytes(unsigned long mask) +{ + if (sizeof(long) == 8) { + /* + * Jan Achrenius on G+: microoptimized version of + * the simpler "(mask & ONEBYTES) * ONEBYTES >> 56" + * that works for the bytemasks without having to + * mask them first. + */ + /* + * return mask * 0x0001020304050608 >> 56; + * + * Doing it like this avoids warnings on 32-bit machines. + */ + long a = (REPEAT_BYTE(0x01) / 0xff + 1); + return mask * a >> (sizeof(long) * 7); + } else { + /* Carl Chatfield / Jan Achrenius G+ version for 32-bit */ + /* (000000 0000ff 00ffff ffffff) -> ( 1 1 2 3 ) */ + long a = (0x0ff0001 + mask) >> 23; + /* Fix the 1 for 00 case */ + return a & mask; + } +} + +unsigned long xdl_hash_record(char const **data, char const *top, long flags) +{ + unsigned long hash = 5381; + unsigned long a = 0, mask = 0; + char const *ptr = *data; + char const *end = top - sizeof(unsigned long) + 1; + + if (flags & XDF_WHITESPACE_FLAGS) + return xdl_hash_record_with_whitespace(data, top, flags); + + ptr -= sizeof(unsigned long); + do { + hash += hash << 5; + hash ^= a; + ptr += sizeof(unsigned long); + if (ptr >= end) + break; + a = *(unsigned long *)ptr; + /* Do we have any '\n' bytes in this word? */ + mask = has_zero(a ^ NEWLINEBYTES); + } while (!mask); + + if (ptr >= end) { + /* + * There is only a partial word left at the end of the + * buffer. Because we may work with a memory mapping, + * we have to grab the rest byte by byte instead of + * blindly reading it. + * + * To avoid problems with masking in a signed value, + * we use an unsigned char here. + */ + const char *p; + for (p = top - 1; p >= ptr; p--) + a = (a << 8) + *((const unsigned char *)p); + mask = has_zero(a ^ NEWLINEBYTES); + if (!mask) + /* + * No '\n' found in the partial word. Make a + * mask that matches what we read. + */ + mask = 1UL << (8 * (top - ptr) + 7); + } + + /* The mask *below* the first high bit set */ + mask = (mask - 1) & ~mask; + mask >>= 7; + hash += hash << 5; + hash ^= a & mask; + + /* Advance past the last (possibly partial) word */ + ptr += count_masked_bytes(mask); + + if (ptr < top) { + assert(*ptr == '\n'); + ptr++; + } + + *data = ptr; + + return hash; +} + +#else /* XDL_FAST_HASH */ unsigned long xdl_hash_record(char const **data, char const *top, long flags) { unsigned long ha = 5381; @@ -293,6 +369,7 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) { return ha; } +#endif /* XDL_FAST_HASH */ unsigned int xdl_hashbits(unsigned int size) { unsigned int val = 1, bits = 0; @@ -324,20 +401,6 @@ int xdl_num_out(char *out, long val) { 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; diff --git a/xdiff/xutils.h b/xdiff/xutils.h index 714719a89c..ad1428ed69 100644 --- a/xdiff/xutils.h +++ b/xdiff/xutils.h @@ -31,14 +31,11 @@ int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize, 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, long sample); 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); int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, |