[PATCH] denser delta header encoding

[PATCH] denser delta header encoding

[Nicolas Pitre]

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>

diff --git a/count-delta.c b/count-delta.c
--- a/count-delta.c
+++ b/count-delta.c
@@ -11,16 +11,13 @@
 static unsigned long get_hdr_size(const unsigned char **datap)
 {
 	const unsigned char *data = *datap;
-	unsigned long size;
-	unsigned char cmd;
-	int i;
-	size = i = 0;
-	cmd = *data++;
-	while (cmd) {
-		if (cmd & 1)
-			size |= *data++ << i;
-		i += 8;
-		cmd >>= 1;
+	unsigned char cmd = *data++;
+	unsigned long size = cmd & ~0x80;
+	int i = 7;
+	while (cmd & 0x80) {
+		cmd = *data++;
+		size |= (cmd & ~0x80) << i;
+		i += 7;
 	}
 	*datap = data;
 	return size;
@@ -47,8 +44,8 @@ int count_delta(void *delta_buf, unsigne
 	unsigned char cmd;
 	unsigned long src_size, dst_size, out;
 
-	/* the smallest delta size possible is 6 bytes */
-	if (delta_size < 6)
+	/* the smallest delta size possible is 4 bytes */
+	if (delta_size < 4)
 		return -1;
 
 	data = delta_buf;
diff --git a/diff-delta.c b/diff-delta.c
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -228,28 +228,22 @@ void *diff_delta(void *from_buf, unsigne
 	top = to_buf + to_size;
 
 	/* store reference buffer size */
-	orig = out + outpos++;
-	*orig = i = 0;
-	do {
-		if (from_size & 0xff) {
-			*orig |= (1 << i);
-			out[outpos++] = from_size;
-		}
-		i++;
-		from_size >>= 8;
-	} while (from_size);
+	out[outpos++] = from_size;
+	from_size >>= 7;
+	while (from_size) {
+		out[outpos - 1] |= 0x80;
+		out[outpos++] = from_size;
+		from_size >>= 7;
+	}
 
 	/* store target buffer size */
-	orig = out + outpos++;
-	*orig = i = 0;
-	do {
-		if (to_size & 0xff) {
-			*orig |= (1 << i);
-			out[outpos++] = to_size;
-		}
-		i++;
-		to_size >>= 8;
-	} while (to_size);
+	out[outpos++] = to_size;
+	to_size >>= 7;
+	while (to_size) {
+		out[outpos - 1] |= 0x80;
+		out[outpos++] = to_size;
+		to_size >>= 7;
+	}
 
 	inscnt = 0;
 	moff = 0;
diff --git a/patch-delta.c b/patch-delta.c
--- a/patch-delta.c
+++ b/patch-delta.c
@@ -22,33 +22,33 @@ void *patch_delta(void *src_buf, unsigne
 	unsigned long size;
 	int i;
 
-	/* the smallest delta size possible is 6 bytes */
-	if (delta_size < 6)
+	/* the smallest delta size possible is 4 bytes */
+	if (delta_size < 4)
 		return NULL;
 
 	data = delta_buf;
 	top = delta_buf + delta_size;
 
 	/* make sure the orig file size matches what we expect */
-	size = i = 0;
 	cmd = *data++;
-	while (cmd) {
-		if (cmd & 1)
-			size |= *data++ << i;
-		i += 8;
-		cmd >>= 1;
+	size = cmd & ~0x80;
+	i = 7;
+	while (cmd & 0x80) {
+		cmd = *data++;
+		size |= (cmd & ~0x80) << i;
+		i += 7;
 	}
 	if (size != src_size)
 		return NULL;
 
 	/* now the result size */
-	size = i = 0;
 	cmd = *data++;
-	while (cmd) {
-		if (cmd & 1)
-			size |= *data++ << i;
-		i += 8;
-		cmd >>= 1;
+	size = cmd & ~0x80;
+	i = 7;
+	while (cmd & 0x80) {
+		cmd = *data++;
+		size |= (cmd & ~0x80) << i;
+		i += 7;
 	}
 	dst_buf = malloc(size);
 	if (!dst_buf)

Re: [PATCH] denser delta header encoding

[Junio C Hamano]

Linus, please do not apply this as is.

There are code other than what Nico updated with this patch in
sha1_file.c that also need updating, that count the number of
bytes in the delta-patch result by reading from the delta
header.

I wonder if we can have a helper function in delta suite
somewhere (maybe in diff-delta.c):

    int look_at_delta_header(void **delta_data, ulong delta_size,
    	                     ulong *src_size, ulong *dst_size)

that:

    - checks delta size and barf if it is small;
    - reads the header and fills src_size and dst_size;
    - advances *delta_data pointer;

and have count-delta, patch-delta and sha1_file.c users use it
consistently.  Nico, what do you think?

Re: [PATCH] denser delta header encoding

[Linus Torvalds]

On Tue, 28 Jun 2005, Junio C Hamano wrote:
>
> Linus, please do not apply this as is.

Argh. Too late.

> There are code other than what Nico updated with this patch in
> sha1_file.c that also need updating, that count the number of
> bytes in the delta-patch result by reading from the delta
> header.

Hmm.. I tested this (along with my change to make the pack object also 
use the little-endian size encoding) with "gitk" on a packed git archive, 
and with git-unpack-objects. So it can't break _too_ seriously. Is it the 
"git-cat-file -s" thing that gets the wrong answer?

Ahh. I see it. "packed_delta_info()". And it looks like "diff" uses it 
too. Oh, for the copy and rename detection. I don't think I tested that 
part, nope.

> I wonder if we can have a helper function in delta suite
> somewhere (maybe in diff-delta.c):
> 
>     int look_at_delta_header(void **delta_data, ulong delta_size,
>     	                     ulong *src_size, ulong *dst_size)
> 
> that:
> 
>     - checks delta size and barf if it is small;
>     - reads the header and fills src_size and dst_size;
>     - advances *delta_data pointer;
> 
> and have count-delta, patch-delta and sha1_file.c users use it
> consistently.  Nico, what do you think?

Sounds like a good idea.

		Linus

Re: [PATCH] denser delta header encoding

[Junio C Hamano]

>>>>> "LT" == Linus Torvalds <torvalds@osdl.org> writes:

LT> Ahh. I see it. "packed_delta_info()". And it looks like "diff" uses it 
LT> too. Oh, for the copy and rename detection. I don't think I tested that 
LT> part, nope.

OK, not too much damage done.  I'll fix the rest up.

Re: [PATCH] denser delta header encoding

[Linus Torvalds]

On Tue, 28 Jun 2005, Junio C Hamano wrote:
> 
> OK, not too much damage done.  I'll fix the rest up.

Actually, I already did, and pushed out. And this time I verified it by 
doing a "git-cat-file -s" on every object on a packed repo.

		Linus

Re: [PATCH] denser delta header encoding

[Nicolas Pitre]

On Tue, 28 Jun 2005, Linus Torvalds wrote:

> 
> 
> On Tue, 28 Jun 2005, Junio C Hamano wrote:
> > 
> > OK, not too much damage done.  I'll fix the rest up.
> 
> Actually, I already did, and pushed out. And this time I verified it by 
> doing a "git-cat-file -s" on every object on a packed repo.

Damn!

And just when I was about to send a new patch with the thing nicely 
abstracted to fix the dammage.

OK... let me pull again to see what's left then.


Nicolas

Re: [PATCH] denser delta header encoding

[Junio C Hamano]

>>>>> "NP" == Nicolas Pitre <nico@cam.org> writes:

NP> On Tue, 28 Jun 2005, Linus Torvalds wrote:
>> 
>> 
>> On Tue, 28 Jun 2005, Junio C Hamano wrote:
>> > 
>> > OK, not too much damage done.  I'll fix the rest up.
>> 
>> Actually, I already did, and pushed out. And this time I verified it by 
>> doing a "git-cat-file -s" on every object on a packed repo.

NP> Damn!

NP> And just when I was about to send a new patch with the thing nicely 
NP> abstracted to fix the dammage.

Double Damn!!  Three people working on the same piece of code.

And Linus head still breaks with t5300.  Triple damn X-<.

Re: [PATCH] denser delta header encoding

[Linus Torvalds]

On Tue, 28 Jun 2005, Junio C Hamano wrote:
> 
> Double Damn!!  Three people working on the same piece of code.

The good news is that I'm pushing out a linux-2.6.13-rc1 release, and will 
go to bed after that, so I'm done for the day. No more races with me ;)

		Linus

[PATCH] Adjust t5300 test for unpack-objects change

[Junio C Hamano]

It now always read from standard input and rejects non-flag
arguments.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
cd /opt/packrat/playpen/public/in-place/git/git.junio/
jit-diff
# - linus: Fix packed_delta_info() that was broken by the delta header packing change
# + (working tree)
diff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh
--- a/t/t5300-pack-object.sh
+++ b/t/t5300-pack-object.sh
@@ -45,7 +45,8 @@ test_expect_success \
     'GIT_OBJECT_DIRECTORY=.git2/objects &&
      export GIT_OBJECT_DIRECTORY &&
      git-init-db &&
-     git-unpack-objects test-1'
+     git-unpack-objects -n <test-1.pack &&
+     git-unpack-objects <test-1.pack'
 
 unset GIT_OBJECT_DIRECTORY
 cd $TRASH/.git2
@@ -75,7 +76,8 @@ test_expect_success \
     'GIT_OBJECT_DIRECTORY=.git2/objects &&
      export GIT_OBJECT_DIRECTORY &&
      git-init-db &&
-     git-unpack-objects test-2'
+     git-unpack-objects -n <test-2.pack &&
+     git-unpack-objects <test-2.pack'
 
 unset GIT_OBJECT_DIRECTORY
 cd $TRASH/.git2

Compilation finished at Tue Jun 28 23:06:08