X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=diff-delta.c;h=faf96e47130e3a2af26f55fc1173874f078617fc;hb=cfabd6eee1745cfec58cfcb794ce8847e43b888a;hp=9f998d0a73e0127d3a68a7caecb3727569149871;hpb=5f5dbd719d0d8ec136f32a0a56674902bd85f72f;p=git.git diff --git a/diff-delta.c b/diff-delta.c index 9f998d0a7..faf96e471 100644 --- a/diff-delta.c +++ b/diff-delta.c @@ -1,21 +1,14 @@ /* * diff-delta.c: generate a delta between two buffers * - * Many parts of this file have been lifted from LibXDiff version 0.10. - * http://www.xmailserver.org/xdiff-lib.html + * This code was greatly inspired by parts of LibXDiff from Davide Libenzi + * http://www.xmailserver.org/xdiff-lib.html * - * LibXDiff was written by Davide Libenzi - * Copyright (C) 2003 Davide Libenzi + * Rewritten for GIT by Nicolas Pitre , (C) 2005-2007 * - * Many mods for GIT usage by Nicolas Pitre , (C) 2005. - * - * This file 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. - * - * Use of this within git automatically means that the LGPL - * licensing gets turned into GPLv2 within this project. + * This code is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. */ #include "git-compat-util.h" @@ -246,7 +239,7 @@ create_delta(const struct delta_index *index, const void *trg_buf, unsigned long trg_size, unsigned long *delta_size, unsigned long max_size) { - unsigned int i, outpos, outsize, val; + unsigned int i, outpos, outsize, moff, msize, val; int inscnt; const unsigned char *ref_data, *ref_top, *data, *top; unsigned char *out; @@ -291,30 +284,33 @@ create_delta(const struct delta_index *index, } inscnt = i; + moff = 0; + msize = 0; while (data < top) { - unsigned int moff = 0, msize = 0; - struct index_entry *entry; - val ^= U[data[-RABIN_WINDOW]]; - val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT]; - i = val & index->hash_mask; - for (entry = index->hash[i]; entry; entry = entry->next) { - const unsigned char *ref = entry->ptr; - const unsigned char *src = data; - unsigned int ref_size = ref_top - ref; - if (entry->val != val) - continue; - if (ref_size > top - src) - ref_size = top - src; - if (ref_size > 0x10000) - ref_size = 0x10000; - if (ref_size <= msize) - break; - while (ref_size-- && *src++ == *ref) - ref++; - if (msize < ref - entry->ptr) { - /* this is our best match so far */ - msize = ref - entry->ptr; - moff = entry->ptr - ref_data; + if (msize < 4096) { + struct index_entry *entry; + val ^= U[data[-RABIN_WINDOW]]; + val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT]; + i = val & index->hash_mask; + for (entry = index->hash[i]; entry; entry = entry->next) { + const unsigned char *ref = entry->ptr; + const unsigned char *src = data; + unsigned int ref_size = ref_top - ref; + if (entry->val != val) + continue; + if (ref_size > top - src) + ref_size = top - src; + if (ref_size <= msize) + break; + while (ref_size-- && *src++ == *ref) + ref++; + if (msize < ref - entry->ptr) { + /* this is our best match so far */ + msize = ref - entry->ptr; + moff = entry->ptr - ref_data; + if (msize >= 4096) /* good enough */ + break; + } } } @@ -327,27 +323,13 @@ create_delta(const struct delta_index *index, out[outpos - inscnt - 1] = inscnt; inscnt = 0; } + msize = 0; } else { + unsigned int left; unsigned char *op; - if (msize >= RABIN_WINDOW) { - const unsigned char *sk; - sk = data + msize - RABIN_WINDOW; - val = 0; - for (i = 0; i < RABIN_WINDOW; i++) - val = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT]; - } else { - const unsigned char *sk = data + 1; - for (i = 1; i < msize; i++) { - val ^= U[sk[-RABIN_WINDOW]]; - val = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT]; - } - } - if (inscnt) { while (moff && ref_data[moff-1] == data[-1]) { - if (msize == 0x10000) - break; /* we can match one byte back */ msize++; moff--; @@ -363,23 +345,40 @@ create_delta(const struct delta_index *index, inscnt = 0; } - data += msize; + /* A copy op is currently limited to 64KB (pack v2) */ + left = (msize < 0x10000) ? 0 : (msize - 0x10000); + msize -= left; + op = out + outpos++; i = 0x80; - if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; } - moff >>= 8; - if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; } - moff >>= 8; - if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; } - moff >>= 8; - if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; } + if (moff & 0x000000ff) + out[outpos++] = moff >> 0, i |= 0x01; + if (moff & 0x0000ff00) + out[outpos++] = moff >> 8, i |= 0x02; + if (moff & 0x00ff0000) + out[outpos++] = moff >> 16, i |= 0x04; + if (moff & 0xff000000) + out[outpos++] = moff >> 24, i |= 0x08; - if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; } - msize >>= 8; - if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; } + if (msize & 0x00ff) + out[outpos++] = msize >> 0, i |= 0x10; + if (msize & 0xff00) + out[outpos++] = msize >> 8, i |= 0x20; *op = i; + + data += msize; + moff += msize; + msize = left; + + if (msize < 4096) { + int j; + val = 0; + for (j = -RABIN_WINDOW; j < 0; j++) + val = ((val << 8) | data[j]) + ^ T[val >> RABIN_SHIFT]; + } } if (outpos >= outsize - MAX_OP_SIZE) { @@ -389,7 +388,7 @@ create_delta(const struct delta_index *index, outsize = max_size + MAX_OP_SIZE + 1; if (max_size && outpos > max_size) break; - out = xrealloc(out, outsize); + out = realloc(out, outsize); if (!out) { free(tmp); return NULL;