delta/git.git/diff-delta.c, branch ks/status-initial-commit

create_delta_index: simplify condition always evaluating to true

2013-08-18T19:56:23+00:00

The code sequence  ' (1u << i) < hsize && i < 31 ' is a multi step
process, whose first step requires that 'i' is already less that 31,
otherwise the result (1u << i)  is undefined (and  'undef_val < hsize'
can therefore be assumed to be 'false'), and so the later test  i < 31
can always be optimized away as dead code ('i' is already less than 31,
or the short circuit 'and' applies).

So we need to get rid of that code. One way would be to exchange the
order of the conditions, so the expression 'i < 31 && (1u << i) < hsize'
would remove that optimized unstable code already.

However when checking the previous lines in that function, we can deduce
that 'hsize' must always be smaller than (1u<<31), since 506049c7df2c6
(fix >4GiB source delta assertion failure), because 'entries' is
capped at an upper bound of 0xfffffffeU, so 'hsize' contains a maximum
value of 0x3fffffff, which is smaller than (1u<<31), so the value of
'i' will never be larger than 31 and we can remove that condition
entirely.

Signed-off-by: Stefan Beller 
Acked-by: Nicolas Pitre 
Acked-by: Philip Oakley 
Signed-off-by: Junio C Hamano

fix >4GiB source delta assertion failure

2010-08-22T06:53:26+00:00

When people try insane things such as delta-compressing 4GiB files, they
get this assertion:

diff-delta.c:285: create_delta_index: Assertion `packed_entry - (struct index_entry *)mem == entries' failed.

This happens because:

1) the 'entries' variable is an unsigned int

2) it is assigned with entries = (bufsize - 1) / RABIN_WINDOW
   (that itself is not a problem unless bufsize > 4G * RABIN_WINDOW)

3) the buffer is indexed from top to bottom starting at
   "data = buffer + entries * RABIN_WINDOW" and the multiplication
   here does indeed overflows, making the resulting top of the buffer
   much lower than expected.

This makes the number of actually produced index entries smaller than
what was computed initially, hence the assertion.

Furthermore, the current delta encoding format cannot represent offsets
into a reference buffer with more than 32 bits anyway.  So let's just
limit the number of entries to what the delta format can encode.

Reported-by: Ilari Liusvaara 
Signed-off-by: Nicolas Pitre 
Signed-off-by: Junio C Hamano

Nicolas Pitre has a new email address

2009-09-14T09:23:36+00:00

Due to problems at cam.org, my nico@cam.org email address is no longer
valid.  From now on, nico@fluxnic.net should be used instead.

Signed-off-by: Nicolas Pitre 
Signed-off-by: Junio C Hamano

fix style of a few comments in diff-delta.c

2007-12-18T23:22:28+00:00

Signed-off-by: Nicolas Pitre 
Signed-off-by: Junio C Hamano

Fix segfault in diff-delta.c when FLEX_ARRAY is 1

2007-12-18T05:59:26+00:00

aka don't do pointer arithmetics on structs that have a FLEX_ARRAY member,
or you'll end up believing your array is 1 cell off its real address.

Signed-off-by: Pierre Habouzit 
Signed-off-by: Junio C Hamano

diff-delta.c: Rationalize culling of hash buckets

2007-09-10T00:16:49+00:00

The previous hash bucket culling resulted in a somewhat unpredictable
number of hash bucket entries in the order of magnitude of HASH_LIMIT.

Replace this with a Bresenham-like algorithm leaving us with exactly
HASH_LIMIT entries by uniform culling.

Signed-off-by: David Kastrup 
Acked-by: Nicolas Pitre 
Signed-off-by: Junio C Hamano

diff-delta.c: pack the index structure

2007-09-10T00:16:49+00:00

In normal use cases, the performance wins are not overly impressive:
we get something like 5-10% due to the slightly better locality of
memory accesses using the packed structure.

However, since the data structure for index entries saves 33% of
memory on 32-bit platforms and 40% on 64-bit platforms, the behavior
when memory gets limited should be nicer.

This is a rather well-contained change.  One obvious improvement would
be sorting the elements in one bucket according to their hash, then
using binary probing to find the elements with the right hash value.

As it stands, the output should be strictly the same as previously
unless one uses the option for limiting the amount of used memory, in
which case the created packs might be better.

Signed-off-by: David Kastrup 
Acked-by: Nicolas Pitre 
Signed-off-by: Junio C Hamano

diff-delta.c: Fix broken skip calculation.

2007-08-23T07:04:10+00:00

A particularly bad case was HASH_LIMIT <= hash_count[i] < 2*HASH_LIMIT:
in that case, only a single hash survived.  For larger cases,
2*HASH_LIMIT was the actual limiting value after pruning.

Signed-off-by: David Kastrup 
Acked-by: Nicolas Pitre 
Signed-off-by: Junio C Hamano

Support fetching the memory usage of a delta index

2007-07-12T21:32:35+00:00

Delta indices, at least on 64-bit platforms, tend to be larger than
the actual uncompressed data.  As such, keeping track of this storage
is important if you want to successfully limit the memory size of your
pack window.

Squirrel away the total allocation size inside the delta_index struct,
and add an accessor "sizeof_delta_index" to access it.

Signed-off-by: Brian Downing 
Acked-by: Nicolas Pitre 
Signed-off-by: Junio C Hamano

diff-delta: use realloc instead of xrealloc

2007-05-31T07:15:18+00:00

Commit 83572c1a914d3f7a8dd66d954c11bbc665b7b923 changed many
realloc to xrealloc. This change was made in diff-delta.c too,
although the code can handle an out of memory failure.

This patch reverts this change in diff-delta.c.

Signed-off-by: Martin Koegler 
Signed-off-by: Junio C Hamano