summaryrefslogtreecommitdiff
path: root/diff-delta.c
AgeCommit message (Collapse)AuthorFilesLines
2006-05-10fix diff-delta bad memory accessLibravatar Nicolas Pitre1-5/+0
It cannot be assumed that the given buffer will never be moved when shrinking the allocated memory size with realloc(). So let's ignore that optimization for now. This patch makes Electric Fence happy on Linux. Signed-off-by: Nicolas Pitre <nico@cam.org> Acked-by: Linus Torvalds <torvalds@osdl.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-05-02improve diff-delta with sparse and/or repetitive dataLibravatar Nicolas Pitre1-13/+27
It is useless to preserve multiple hash entries for consecutive blocks with the same hash. Keeping only the first one will allow for matching the longest string of identical bytes while subsequent blocks will only allow for shorter matches. The backward matching code will match the end of it as necessary. This improves both performances (no repeated string compare with long successions of identical bytes, or even small group of bytes), as well as compression (less likely to need random hash bucket entry culling), especially with sparse files. With well behaved data sets this patch doesn't change much. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-05-02tiny optimization to diff-deltaLibravatar Nicolas Pitre1-3/+2
This is my assembly freak side looking at generated code again. And since create_delta() is certainly pretty high on the radar every bits count. In this case shorter code is generated if hash_mask is not copied to a local variable. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-04-28replace adler32 with Rabin's polynomial in diff-deltaLibravatar Nicolas Pitre1-34/+150
This brings another small repacking speedup for sensibly the same pack size. On the Linux kernel repo, git-repack -a -f is 3.7% faster for a 0.4% larger pack. Credits to Geert Bosch who brought the Rabin's polynomial idea to my attention. This also eliminate the issue of adler32() reading past the data buffer, as noticed by Johannes Schindelin. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-04-24split the diff-delta interfaceLibravatar Nicolas Pitre1-83/+85
This patch splits the diff-delta interface into index creation and delta generation. A wrapper is provided to preserve the diff-delta() call. This will allow for an optimization in pack-objects.c where the source object could be fixed and a full window of objects tentatively tried against that same source object without recomputing the source index each time. This patch only restructure things, plus a couple cleanups for good measure. There is no performance change yet. Signed-off-by: Nicolas Pitre <nico@cam.org>
2006-03-173% tighter packs for freeLibravatar Nicolas Pitre1-1/+16
This patch makes for 3.4% smaller pack with the git repository, and a bit more than 3% smaller pack with the kernel repository. And so with _no_ measurable CPU difference. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-03-09diff-delta: bound hash list length to avoid O(m*n) behaviorLibravatar Nicolas Pitre1-30/+71
The diff-delta code can exhibit O(m*n) behavior with some patological data set where most hash entries end up in the same hash bucket. To prevent this, a limit is imposed to the number of entries that can exist in the same hash bucket. Because of the above the code is a tiny bit more expensive on average, even if some small optimizations were added as well to atenuate the overhead. But the problematic samples used to diagnoze the issue are now orders of magnitude less expensive to process with only a slight loss in compression. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-02-22diff-delta: big code simplificationLibravatar Nicolas Pitre1-146/+85
This is much smaller and hopefully clearer code now. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-02-22diff-delta: fold two special tests into one plus cleanupsLibravatar Nicolas Pitre1-10/+14
Testing for realloc and size limit can be done with only one test per loop. Make it so and fix a theoretical off-by-one comparison error in the process. The output buffer memory allocation is also bounded by max_size when specified. Finally make some variable unsigned to allow the handling of files up to 4GB in size instead of 2GB. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-02-05Use adler32() from zlib instead of defining our own.Libravatar Peter Eriksen1-38/+1
Since we already depend on zlib, we don't need to define our own adler32(). Spotted by oprofile. Signed-off-by: Peter Eriksen <s022018@student.dtu.dk> Signed-off-by: Junio C Hamano <junkio@cox.net>
2005-12-15small cleanup for diff-delta.cLibravatar Nicolas Pitre1-22/+12
This patch removes unused remnants of the original xdiff source. No functional change. Possible tiny speed improvement. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
2005-12-12Revert "diff-delta.c: allow delta with empty blob."Libravatar Junio C Hamano1-1/+1
This reverts 962537a3eb03a118cf27d9d0da365a3216ed1caa commit to play safe.
2005-12-12diff-delta.c: allow delta with empty blob.Libravatar Junio C Hamano1-1/+1
Delta computation with an empty blob used to punt and returned NULL. This commit allows creation with empty blob; all combination of empty->empty, empty->something, and something->empty are allowed. Signed-off-by: Junio C Hamano <junkio@cox.net>
2005-06-29[PATCH] assorted delta code cleanupLibravatar Nicolas Pitre1-1/+2
This is a wrap-up patch including all the cleanups I've done to the delta code and its usage. The most important change is the factorization of the delta header handling code. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-28[PATCH] denser delta header encodingLibravatar Nicolas Pitre1-20/+14
Since the delta data format is not tied to any actual git object anymore, now is the time to add a small improvement to the delta data header as it is been done for packed object header. This patch allows for reducing the delta header of about 2 bytes and makes for simpler code. Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-06-25Add a "max_size" parameter to diff_delta()Libravatar Linus Torvalds1-1/+7
Anything that generates a delta to see if two objects are close usually isn't interested in the delta ends up being bigger than some specified size, and this allows us to stop delta generation early when that happens.
2005-05-19[PATCH] Deltification library work by Nicolas Pitre.Libravatar Nicolas Pitre1-0/+333
This patch adds the basic library functions to create and replay delta information. Also included is a test-delta utility to validate the code. diff-delta was based on LibXDiff written by Davide Libenzi Signed-off-by: Nicolas Pitre <nico@cam.org> Signed-off-by: Davide Libenzi <davidel@xmailserver.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>