Compressed On-Disk Storage

You can hash an object and you can parse one. Now it has to live somewhere. Git's loose-object store is as simple as storage gets: one file per object, filed under its own hash, with the whole object wrapped in a zlib stream. After this lesson your program writes a file that real git accepts and reads one back, checking every byte of the wrapper.

Where the file goes

An object named 95d09f2b10159347eece71399a7e2e907ea3df4f lives at

.git/objects/95/d09f2b10159347eece71399a7e2e907ea3df4f
             --  ---------------------------------------
             first 2 hex digits   remaining 38 digits

Splitting off two digits gives 256 subdirectories (00 to ff) so that no single directory holds hundreds of thousands of files. Given a hash the path is pure string work, with no lookup. That is content addressing paying rent again.

What is inside: a zlib stream

The file holds the complete object, <type> <size> NUL <payload>, wrapped in the zlib format (RFC 1950). Order of operations is a design decision: git hashes the uncompressed bytes, so the name never depends on compression settings, and then stores the compressed form. A zlib stream has three parts:

2 bytes   header:   CMF FLG          (usually 78 01, 78 9c or 78 da)
n bytes   deflate:  one or more blocks (RFC 1951)
4 bytes   trailer:  Adler-32 of the uncompressed bytes, big-endian

The header says "deflate, 32 KB window" (CMF = 78) and carries a check value: CMF times 256 plus FLG must be a multiple of 31. The second digit of 78 9c is the compression level hint, nothing more.

Stored blocks: deflate with compression switched off

Real git normally writes compressed blocks, which need a Huffman decoder. But deflate also has a block that stores bytes verbatim, and git -c core.compression=0 writes only those. A stored block is

1 byte    bit 0 = "this is the last block", bits 1-2 = 00 for stored
2 bytes   LEN,  little-endian, number of data bytes (at most 65535)
2 bytes   NLEN, little-endian, the bitwise complement of LEN
LEN bytes the data

Worked example, the empty tree, whose inflated bytes are tree 0 and a zero byte (7 bytes):

78 01                  zlib header
01                     last block, stored
07 00  f8 ff           LEN = 7, NLEN = 0xfff8
74 72 65 65 20 30 00   the 7 bytes
0a 2c 02 01            Adler-32

Block flags are bits, not a byte value: 01 means last, 00 means more blocks follow. A file can legally hold several stored blocks, and a reader must loop until it sees the last one.

Adler-32

Two running sums over the bytes, both modulo 65521. Start with a = 1 and b = 0; for each byte add it to a, then add a to b. The checksum is b shifted left 16 bits, ORed with a, written big-endian. For the three bytes abc: a goes 98, 196, 295 and b goes 98, 294, 589, so the value is 0x024d0127. Reading must recompute it from what it inflated and compare.

Common mistakes

• Hashing the compressed bytes. The name is the SHA-1 of the inflated object.
• Writing LEN and NLEN big-endian. Deflate integers are little-endian, while the Adler-32 trailer is big-endian.
• Forgetting that a stored block's header byte is 01 only for the last block.
• Trusting a file without checking the trailer. A mismatch means the disk lied, and refusing loudly is git's whole corruption story for loose objects.
• Assuming one block. A reader that stops after the first block drops data from a multi-block stream.

Your exercise

The starter reads commands, builds object headers and hashes for you. You write the three pieces of the wrapper: the Adler-32 checksum, wrap_stored (bytes in, zlib stream out) and unwrap_stored (zlib stream in, bytes or an error out). Your files must be byte for byte what git -c core.compression=0 writes, and your reader must reject each kind of damage with the exact message the exercise lists.