diff options
Diffstat (limited to 'xdiff/xutils.c')
| -rw-r--r-- | xdiff/xutils.c | 200 |
1 files changed, 139 insertions, 61 deletions
diff --git a/xdiff/xutils.c b/xdiff/xutils.c index ab6503460f..9504eaecb8 100644 --- a/xdiff/xutils.c +++ b/xdiff/xutils.c @@ -20,14 +20,12 @@ * */ +#include <limits.h> +#include <assert.h> #include "xinclude.h" -#define XDL_GUESS_NLINES 256 - - - long xdl_bogosqrt(long n) { long i; @@ -71,12 +69,6 @@ void *xdl_mmfile_first(mmfile_t *mmf, long *size) } -void *xdl_mmfile_next(mmfile_t *mmf, long *size) -{ - return NULL; -} - - long xdl_mmfile_size(mmfile_t *mmf) { return mmf->size; @@ -130,47 +122,12 @@ 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 xdl_guess_lines(mmfile_t *mf, long sample) { 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; - } + for (top = data + size; nl < sample && cur < top; ) { nl++; if (!(cur = memchr(cur, '\n', top - cur))) cur = top; @@ -292,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; @@ -309,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; @@ -340,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; @@ -402,3 +449,34 @@ int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, return 0; } + +int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, + int line1, int count1, int line2, int count2) +{ + /* + * This probably does not work outside Git, since + * we have a very simple mmfile structure. + * + * Note: ideally, we would reuse the prepared environment, but + * the libxdiff interface does not (yet) allow for diffing only + * ranges of lines instead of the whole files. + */ + mmfile_t subfile1, subfile2; + xdfenv_t env; + + subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr; + subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr + + diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr; + subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr; + subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr + + diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr; + if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0) + return -1; + + memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1); + memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2); + + xdl_free_env(&env); + + return 0; +} |