threads / patch / 12995

patchUpdate, and clear up the pack format documentation a bit

Subject: [PATCH] Update, and clear up the pack format documentation a bit

## tl;dr

4 messages between Apr 5, 2008 and Apr 6, 2008. Diffs are folded; open one to read it.

replies: 3people: 3as markdown or json

Peter Eriksen· Apr 5, 2008, 18:07 UTC · lore

The current documentation does not mention the ofs_delta pack object type. This patch is also supposed to make the text a bit more readable, since it moves the object entry header description earlier.

I fixes one error in these lines:
        If it is DELTA, then
          20-byte base object name SHA1 (the size above is the
                size of the delta data that follows).

The size given in the object header is actually the inflated size of the delta data that follows, since the call chain goes like this:

For delta objects:
unpack_entry()
    unpack_object_header()
    unpack_delta_entry()
        unpack_compressed_entry()
For non-delta objects:
unpack_entry()
    unpack_object_header()
    unpack_compressed_entry()

unpack_compressed_entry() allocates a buffer of the size given in its last argument, and inflates the data into this buffer.

So all objects have in fact their inflated size given in the packed object header.

Signed-off-by: Peter Eriksen <s022018@student.dtu.dk>
---
 Documentation/technical/pack-format.txt |   43
++++++++++++++++--------------
 1 files changed, 23 insertions(+), 20 deletions(-)

Did I understand this right especially the part with what the length field in the packed objects headers mean?

Show changes to Documentation/technical/pack-format.txt +23 −20
diff --git a/Documentation/technical/pack-format.txt
b/Documentation/technical/pack-format.txt
index aa87756..35ee01d 100644
--- a/Documentation/technical/pack-format.txt
+++ b/Documentation/technical/pack-format.txt
@@ -19,15 +19,34 @@ GIT pack format
 
    - The header is followed by number of object entries, each of
      which looks like this:
+     
+     An n-byte header encoding the
+         type of the object
+         length of the object before compression
+          
+     The format of the header:
+	1-byte size extension bit (MSB)
+	       type (next 3 bit)
+	       size0 (lower 4-bit)
+        n-byte sizeN (as long as MSB is set, each 7-bit)
+		size0..sizeN form 4+7+7+..+7 bit integer, size0
+		is the least significant part, and sizeN is the
+		most significant part.
+
 
-     (undeltified representation)
-     n-byte type and length (3-bit type, (n-1)*7+4-bit length)
+     The header is followed by:
+
+     (for object types: commit, tree, blob, and tag)
      compressed data
 
-     (deltified representation)
-     n-byte type and length (3-bit type, (n-1)*7+4-bit length)
+     (for object type ref_delta)
      20-byte base object name
      compressed delta data
+ 
+     (for object type ofs_delta)
+     n-byte offset (n*7-bit as above, but with size0 being 7 bit)     
+     compressed delta data
+
 
      Observation: length of each object is encoded in a variable
      length format and is not constrained to 32-bit or anything.
@@ -92,22 +111,6 @@ trailer	  | | packfile checksum              |
                   |
 Pack file entry: <+
 
-     packed object header:
-	1-byte size extension bit (MSB)
-	       type (next 3 bit)
-	       size0 (lower 4-bit)
-        n-byte sizeN (as long as MSB is set, each 7-bit)
-		size0..sizeN form 4+7+7+..+7 bit integer, size0
-		is the least significant part, and sizeN is the
-		most significant part.
-     packed object data:
-        If it is not DELTA, then deflated bytes (the size above
-		is the size before compression).
-	If it is DELTA, then
-	  20-byte base object name SHA1 (the size above is the
-		size of the delta data that follows).
-          delta data, deflated.
-
 
 = Version 2 pack-*.idx files support packs larger than 4 GiB, and
   have some other reorganizations.  They have the format:

-- 
1.5.5-rc3.GIT
Junio C Hamano· Apr 5, 2008, 23:58 UTC · re: Peter Eriksen · lore

Re: [PATCH] Update, and clear up the pack format documentation a bit

"Peter Eriksen" <s022018@student.dtu.dk> writes:
Show 13 quoted lines
> The current documentation does not mention the ofs_delta pack
> object type. This patch is also supposed to make the text a bit
> more readable, since it moves the object entry header
> description earlier.
>
> I fixes one error in these lines:
>
>         If it is DELTA, then
>           20-byte base object name SHA1 (the size above is the
>                 size of the delta data that follows).
>
> The size given in the object header is actually the inflated size
> of the delta data that follows,...

Your understanding is correct. Throughout the pack-objects program, delta_size is always expressed in uncompressed number of bytes. The original description you quoted above does not even say "the size of the delta data (compressed)", so in that sense I do not think the original description is really an error; if the update makes the description clearer that would be good.

Show 5 quoted lines
>     - The header is followed by number of object entries, each of
>       which looks like this:
> +     
> +     An n-byte header encoding the
> +         type of the object
Hmm.

This is just terminology, but I think calling ref-delta and ofs-delta "type of object", is confusing. This "type" field is about object representation in the pack.

There are "undeltified" representations (4 object types), "ref-delta" and "ofs-delta" representations.

> +         length of the object before compression
And this is the length of the representation specific data.
 - for undeltified representations of the four object types, this
   size is the size of the _object_;
 - for deltified representations, this is _NOT_ the size of the _object_
   (i.e. final object data after applying the delta).  This is the size of
   the delta data to be applied to the delta base, and does not include
   the base object name (for ref-delta) nor size to represent the offset
   (for ofs-delta).
Show 15 quoted lines
> +          
> +     The format of the header:
> +	1-byte size extension bit (MSB)
> +	       type (next 3 bit)
> +	       size0 (lower 4-bit)
> +        n-byte sizeN (as long as MSB is set, each 7-bit)
> +		size0..sizeN form 4+7+7+..+7 bit integer, size0
> +		is the least significant part, and sizeN is the
> +		most significant part.
> +
>  
> +     The header is followed by:
> +
> +     (for object types: commit, tree, blob, and tag)
>       compressed data
Correct.
Show 7 quoted lines
> +     (for object type ref_delta)
>       20-byte base object name
>       compressed delta data
> + 
> +     (for object type ofs_delta)
> +     n-byte offset (n*7-bit as above, but with size0 being 7 bit)     
> +     compressed delta data
Correct.
Shawn O. Pearce· Apr 6, 2008, 04:51 UTC · re: Peter Eriksen · lore

Re: [PATCH] Update, and clear up the pack format documentation a bit

Peter Eriksen <s022018@student.dtu.dk> wrote:
> The current documentation does not mention the ofs_delta pack
> object type. This patch is also supposed to make the text a bit
> more readable, since it moves the object entry header
> description earlier.
...
Show 11 quoted lines
> diff --git a/Documentation/technical/pack-format.txt
> b/Documentation/technical/pack-format.txt
> index aa87756..35ee01d 100644
> --- a/Documentation/technical/pack-format.txt
> +++ b/Documentation/technical/pack-format.txt
>       compressed delta data
> + 
> +     (for object type ofs_delta)
> +     n-byte offset (n*7-bit as above, but with size0 being 7 bit)     
> +     compressed delta data
> +

That is not correct. The ofs_delta is encoded as an n-byte offset that is subtracted from the current object's first byte (the byte holding the type/representation field and first 4 bits of length).

The n-byte encoding for an ofs_delta is different then the one used for the length. We add 1 for each byte where the MSB is 1. We also store the data in big-endian form (the most significant byte is first and the least significant byte is last).

See get_delta_base in sha1_file.c for the details of this.

In pack v4 I planned on using this particular encoding in more of the format than just here.

-- 
Shawn.
Junio C Hamano· Apr 6, 2008, 06:16 UTC · re: Shawn O. Pearce · lore

Re: [PATCH] Update, and clear up the pack format documentation a bit

"Shawn O. Pearce" <spearce@spearce.org> writes:
Show 10 quoted lines
> Peter Eriksen <s022018@student.dtu.dk> wrote:
> ...
>> +     (for object type ofs_delta)
>> +     n-byte offset (n*7-bit as above, but with size0 being 7 bit)     
>> +     compressed delta data
>> +
>
> That is not correct.  The ofs_delta is encoded as an n-byte offset
> that is subtracted from the current object's first byte (the byte
> holding the type/representation field and first 4 bits of length).

Right. Saying just "n-byte offset" can be mistaken as the offset from the beginning of the file, and making it clear that it is relative is good.

> The n-byte encoding for an ofs_delta is different then the one
> used for the length.  We add 1 for each byte where the MSB is 1.
> We also store the data in big-endian form (the most significant
> byte is first and the least significant byte is last).
Ah, I forgot about that one.

← back to recent threads