Re: Confused over packfile and index design

[Shawn Pearce <spearce@spearce.org>]

On Fri, Apr 8, 2011 at 19:58, Steven E. Harris <seh@panix.com> wrote:
> I was reading the Git Book discussion¹ on the packfile and index formats,
> and there's a confusing set of assertions concerning the design choices
> that sound contradictory.

Its not.

> First, near the end of the section about the index format, we find the
> following paragraph:
>
> ,----
> | Importantly, packfile indexes are /not/ neccesary to extract objects
> | from a packfile, they are simply used to quickly retrieve individual
> | objects from a pack. The packfile format is used in upload-pack and
> | receieve-pack programs (push and fetch protocols) to transfer objects
> | and there is no index used then - it can be built after the fact by
> | scanning the packfile.
> `----
>
> That suggests that it's possible to read the packfile linearly and
> deduce where the various objects start and end, without the index
> available.

It is possible to do this.

Applications can scan the pack file by reading the 12 byte fixed
header and getting the object count from the 2nd word. Then enter a
loop that reads that many objects from the stream, before reading the
trailer SHA-1 checksum.

To read an object, the object header is consumed, reading the inflated
length from the variable length field. If the type code indicates the
object is a delta, the delta base reference is also read. Then
remaining bytes are shoved into a libz inflate() routine until libz
says the stream is over. As Peff mentioned elsewhere in the thread,
libz maintains its own markers and checksum to know when the object's
stream is over. As a safety measure, the inflated length from the
object header is checked against the number of bytes returned by libz.
Any remaining data that libz didn't consume is the next object's
header and data.

> Later, in the section on the packfile format, we find this:
>
> ,----
> | It is important to note that the size specified in the header data is
> | not the size of the data that actually follows, but the size of that
> | data /when expanded/. This is why the offsets in the packfile index are
> | so useful, otherwise you have to expand every object just to tell when
> | the next header starts.
> `----
>
> Now that makes it sound like without the index, even if one knows where
> a packed object starts, reading its header tells its /inflated/ size,
> /not/ the number of remaining payload bytes representing the object.

Yes.

> I imagine that if the format is meant to record the size of the deflated
> payload,

Its not. Its meant to tell us how many bytes to malloc() in order to
hold the result of the libz inflate() call when the object is being
read from the packfile. That way we don't under or over allocate the
result buffer.

-- 
Shawn.