C++ Measured

Writing Git Packfiles in C++: Deltas, Indexes, and the Streaming Win

The Python mini-git guide writes a one-object pack and stops at deltas. This tutorial does the two things it leaves out: three objects in one pack, and a hand-encoded delta that Git accepts and reconstructs byte for byte.

Written November 8, 2026 · Tested with GCC 13.3.0 · 17 min read

By the end of this guide
  • Three objects, one pack
  • The index: what index-pack writes
  • Hand-encoded REFDELTA
  • Streaming write

Edited November 18, 2026

What this tutorial builds

The Python mini-git guide writes a one-object v2 packfile in Python and states its limit plainly: it does not hand-encode a delta, and it writes one object per pack. This tutorial is the extension that guide names. It builds a C++ program, packwriter, that writes a three-object pack in one file, hand-encodes a REF_DELTA entry that real Git accepts, and streams a 5 MB blob through chunked deflate without ever holding the pack in memory.

The program is not a port of the Python write_pack function. A straight port would write the same one-object pack in a different language and prove nothing. The three measured edges over that guide are: multi-object packing in one file, hand-encoded deltas, and streaming writes at lower peak memory. The toolchain is g++ 13.3.0, Git 2.43.0, and Python 3.12.3 for the comparison harness, all on Ubuntu 24.04. Build it with:

Bash
g++ -std=c++17 -O2 -Wall -Wextra -o packwriter packwriter.cpp -lz -lcrypto

That build exits 0 and prints deprecation warnings for the OpenSSL low-level SHA-1 calls. The warnings are a build wart, covered near the end of this tutorial; the output is unaffected.

The three objects in the pack are the same fixture set the Python guide uses: a blob holding hello minigit, a tree holding that blob, and a commit pointing at the tree. Their ids are aafd11ee, 37617524, and c8cd1de1 in short form, identical to the Python guide's fixture, so the two programs can be compared object for object.

Three objects, one pack

A v2 packfile is a header, one entry per object, and a trailer. The header is 12 bytes: the four ASCII bytes PACK, a 4-byte version number (2), and a 4-byte object count, both counts in network byte order. Each undeltified entry is a varint type-and-length header followed by zlib data. Packed objects carry no type-and-size prefix; the object id is still computed with one. The trailer is the SHA-1 of everything before it, 20 bytes. The program writes the header, then one entry per object, then the trailer, with a running SHA-1 over the bytes as they go out:

C++
void write(const void* p, size_t n) {
    if (n == 0) return;
    SHA1_Update(&ctx, p, n);
    if (std::fwrite(p, 1, n, f) != n) { std::perror("fwrite pack"); std::exit(1); }
    bytes += n;
}

The type-and-length header packs the 3-bit type and the low 4 bits of the size into the first byte, then 7 bits of size per continuation byte while the high bit is set:

C++
void type_size(int type, uint64_t size) {
    unsigned char first = (unsigned char)((type << 4) | (size & 0x0F));
    size >>= 4;
    if (size) first |= 0x80;
    write(&first, 1);
    while (size) {
        unsigned char b = (unsigned char)(size & 0x7F);
        size >>= 7;
        if (size) b |= 0x80;
        write(&b, 1);
    }
}

Running ./packwriter pack3 pack3.pack prints:

Output
blob aafd11ee7c1bd00d6a4e757a23e44e5258b05321 size=14
tree 37617524013aeed75fd0429d497f239c5454fc01 size=37
commit c8cd1de1e07b89514e132d8606b24b0aa91d0e80 size=167
entry blob offset=12 compressed=22
entry tree offset=35 compressed=45
entry commit offset=82 compressed=117
pack bytes=221 (header 12 + trailer 20 + entry bytes 189)

The entry table, with the header sizes Git reports back:

Object Size Compressed Header bytes Offset Packed size
blob 14 22 1 12 23
tree 37 45 2 35 47
commit 167 117 2 82 119

The three packed sizes add to 189, which is the entry-bytes total in the pack: 12 header plus 189 entries plus 20 trailer equals 221. The comparison is against the Python guide's approach of one pack per object. Three separate one-object Python packs measure 55, 79, and 151 bytes, 285 in total. The single three-object pack is 64 bytes smaller, 22.5 percent, because the second and third objects stop paying for their own 32-byte header-plus-trailer overhead. Verification is by real Git, in a fresh repository:

Bash
git init -q -b main packrepo
cp pack3.pack packrepo/.git/objects/pack/
git --git-dir=packrepo/.git index-pack packrepo/.git/objects/pack/pack3.pack
git --git-dir=packrepo/.git verify-pack -v packrepo/.git/objects/pack/pack3.idx
git --git-dir=packrepo/.git cat-file -p aafd11ee7c1bd00d6a4e757a23e44e5258b05321
git --git-dir=packrepo/.git cat-file -p 37617524013aeed75fd0429d497f239c5454fc01
git --git-dir=packrepo/.git cat-file -p c8cd1de1e07b89514e132d8606b24b0aa91d0e80
git --git-dir=packrepo/.git fsck --strict

Every command exits 0. index-pack prints the pack id aaa03858. verify-pack reports non delta: 3 objects and pack3.pack: ok. The three cat-file calls print the blob content, the tree line, and the commit text. fsck --strict prints nothing and exits 0.

The index: what index-pack writes

A pack without an index is a file Git can read only by scanning. git index-pack writes the v2 index, and for this 221-byte pack it is 1156 bytes, more than five times the pack itself. The layout is fixed: 8 bytes of magic plus version, a 1024-byte fanout table, then the object names, CRC32 values, and offsets, then a 40-byte trailer. Reading the index back field by field:

Output
idx bytes: 1156
idx magic: b'\xfftOc' version: 2
idx fanout[255] (total objects): 3
idx fanout[0x37] (tree 37..): 1
idx fanout[0xaa] (blob aa..): 2
idx fanout[0xc8] (commit c8..): 3
idx trailer pack sha == pack sha: True

The fanout table is cumulative: fanout[0x37] is 1 because only the tree id starts with a byte at or below 0x37; fanout[0xaa] is 2 because the tree and the blob both qualify; fanout[0xc8] is 3 because all three do. The size formula checks out exactly: 8 plus 1024 fanout plus 60 for three 20-byte names plus 12 for three CRC32 values plus 12 for three offsets plus 40 trailer equals 1156. The trailer holds the pack checksum, and it matches the last 20 bytes of the pack file. index-pack also writes a 64-byte reverse index file, pack3.rev, which maps offsets back to index positions.

That 1156-byte index is the honest cost of the pack at this scale, and it leads to the first negative result in this tutorial. The three loose objects total 207 bytes on disk. The pack is 221 bytes, 14 bytes larger, 6.8 percent. Packing does not save space at toy scale. The saving at this scale is structure, one file plus an index instead of three files, not bytes. The byte saving comes from deltas, which is the next section, and from scale, where the per-pack overhead stops mattering.

Hand-encoded REF_DELTA

A deltified entry stores a base object reference followed by zlib-compressed delta data. For REF_DELTA, the reference is the full 20-byte base object id; for OFS_DELTA, it is a negative offset from the entry. The delta data starts with the base size and the target size in the size encoding, then a sequence of instructions. There are two instructions: copy a byte range from the base, and insert literal bytes. A copy instruction is one header byte plus optional offset and size bytes in little-endian order, with the header bits saying which bytes are present. An insert instruction is one length byte, 1 to 127, plus the raw bytes.

The program encodes both instructions directly:

C++
static void size_encode(std::vector<unsigned char>& out, uint64_t v) {
    do {
        unsigned char b = (unsigned char)(v & 0x7F);
        v >>= 7;
        if (v) b |= 0x80;
        out.push_back(b);
    } while (v);
}

static void emit_copy(std::vector<unsigned char>& out, uint64_t off, uint64_t len) {
    int need_o = 0, need_s = 0;
    for (int i = 3; i >= 0; i--) if ((off >> (8 * i)) & 0xFF) { need_o = i + 1; break; }
    for (int i = 2; i >= 0; i--) if ((len >> (8 * i)) & 0xFF) { need_s = i + 1; break; }
    unsigned char hdr = 0x80;
    for (int i = 0; i < need_o; i++) hdr |= (1 << i);
    for (int i = 0; i < need_s; i++) hdr |= (1 << (4 + i));
    out.push_back(hdr);
    for (int i = 0; i < need_o; i++) out.push_back((unsigned char)((off >> (8 * i)) & 0xFF));
    for (int i = 0; i < need_s; i++) out.push_back((unsigned char)((len >> (8 * i)) & 0xFF));
}

static void emit_insert(std::vector<unsigned char>& out, const unsigned char* p, size_t n) {
    while (n) {
        size_t chunk = n > 127 ? 127 : n;
        out.push_back((unsigned char)chunk);
        out.insert(out.end(), p, p + chunk);
        p += chunk;
        n -= chunk;
    }
}

A delta is the two size headers plus the instruction stream for a list of copy and insert segments. The REF_DELTA entry itself is a type 7 header whose size is the uncompressed delta size, then the 20 raw bytes of the base id, then the compressed delta:

C++
pw.type_size(7, delta.size());
std::string base_raw = sha1_raw("blob " + std::to_string(base.size()) + '\0' + base);
pw.write(base_raw.data(), base_raw.size());
// ... compress delta with zlib, then write the compressed bytes

Two fixtures test the encoding, each as a base-full plus REF_DELTA pack against the same two blobs both stored full. The text fixture is 60 repeated lines, 4800 bytes; the target replaces line 50 and appends one line, 4829 bytes. The random fixture is 4096 pseudo-random bytes from a fixed seed; the target changes 200 bytes at offset 1000. The delta instruction stream for the text fixture is 123 bytes: two size headers, a copy of the first 4000 bytes, an insert of the 74-byte edited line, a copy of the remaining 720 bytes, and an insert of the 35-byte appended line. For the random fixture it is 214 bytes: two size headers, a copy of 1000 bytes, a 200-byte insert split into 127-byte and 73-byte chunks, and a copy of the remaining 2896 bytes.

Fixture Delta pack Both-full pack Saved Delta entry vs full entry
text, 4800 to 4829 bytes 417 588 171 bytes, 29.1% 116 vs 306, 2.64x smaller
random, 4096 bytes, 200 changed 4389 8252 3863 bytes, 46.8% 225 vs 4107, 18.25x smaller

Both packs pass real Git. git index-pack exits 0 for each. git cat-file -s on the target returns 4829 for the text fixture and 4096 for the random fixture. git verify-pack -v reports chain length = 1: 1 object for each. The reconstruction check is the strict one: the target read back out of Git is compared byte for byte against an independently generated copy of the expected target, and cmp exits 0 for both fixtures. A hand-encoded delta that Git accepts and reconstructs exactly is the bar the Python guide sets for this extension, and both fixtures clear it.

The two fixtures also show where the saving comes from. The text saving is modest, 29.1 percent, because zlib already crushes repetitive text: the full target compresses to 306 bytes on its own, so the delta entry at 116 bytes is only 2.64 times smaller. The random fixture is the opposite shape. Random bytes do not compress, so the full target costs 4107 bytes, while the delta costs 225 bytes, 18.25 times smaller, because the delta only carries the 200 changed bytes plus the copy instructions for the rest. The large delta win needs data that is similar but incompressible. On repetitive text, most of the win is already in the compression.

Streaming write

The third edge is memory, not bytes. The Python guide builds the whole pack in memory before writing it. The C++ program streams: it reads the input file in 64 KiB chunks, feeds each chunk through a running deflate stream, and writes the compressed output as it is produced, with the running SHA-1 updated on the way out. The pack never exists whole in memory. The in-flight state is two 64 KiB buffers plus the deflate state:

C++
uint64_t stream_blob(FILE* in, uint64_t size) {
    type_size(3, size);
    z_stream zs;
    std::memset(&zs, 0, sizeof zs);
    if (deflateInit(&zs, Z_DEFAULT_COMPRESSION) != Z_OK) {
        std::fprintf(stderr, "deflateInit failed\n");
        std::exit(1);
    }
    std::vector<unsigned char> inbuf(65536), outbuf(65536);
    uint64_t comp_total = 0;
    int flush = Z_NO_FLUSH;
    do {
        size_t n = std::fread(inbuf.data(), 1, inbuf.size(), in);
        if (n == 0) flush = Z_FINISH;
        zs.next_in = inbuf.data();
        zs.avail_in = static_cast<uInt>(n);
        int ret;
        do {
            zs.next_out = outbuf.data();
            zs.avail_out = static_cast<uInt>(outbuf.size());
            ret = deflate(&zs, flush);
            size_t have = outbuf.size() - zs.avail_out;
            if (have) { write(outbuf.data(), have); comp_total += have; }
        } while (zs.avail_out == 0);
        if (ret == Z_STREAM_END) break;
    } while (flush != Z_FINISH || !std::feof(in));
    deflateEnd(&zs);
    return comp_total;
}

The test blob is 5,242,880 random bytes from /dev/urandom, so its hash changes on every run while its size does not. Both writers produce a pack of exactly 5,244,522 bytes, byte-count identical, and the blob id agrees between the two writers. The C++ pack verifies: git index-pack exits 0, git cat-file -s returns 5242880, and the reconstructed blob hashes to the same SHA-256 as the input file. Peak child memory, measured with the process resource usage call after each child exits:

Writer Pack bytes Peak child RSS
C++ streaming 5,244,522 12,384 KiB
Python in-memory 5,244,522 36,348 KiB

The C++ peak is 2.94 times lower, 23,964 KiB less, for identical output. The Python peak is roughly the input plus the pack plus the compressed buffers held at once; the C++ peak is the two 64 KiB buffers plus interpreter-free process overhead. The ratio is measured at 5 MB only. The gap should grow with the input, because the streaming side holds two 64 KiB buffers whatever the file size, while the in-memory side grows with the file, but that growth was not measured here.

The tamper test

A pack that Git accepts is only half the story; a pack that Git rejects when damaged is the other half. Flipping one byte at pack offset 20, inside the first entry's zlib stream, and feeding the result to git index-pack --stdin gives:

Output
error: inflate: data stream error (invalid distance too far back)
fatal: pack has bad object at offset 12: inflate returned -3

The exit code is 128. The undamaged pack fed through the same command exits 0 and prints the pack id aaa03858. The trailer checksum is what catches a flip in the trailer itself; a flip inside an entry is caught by the zlib stream failing to inflate, before the checksum is even reached.

How to run it

The probe program has four modes. Each mode prints its object ids, entry offsets, and pack size, so the output is the measurement and the verification at once:

Bash
./packwriter pack3 pack3.pack
./packwriter delta text delta-text.pack
./packwriter delta rand delta-rand.pack
./packwriter full2 text full2-text.pack
./packwriter full2 rand full2-rand.pack
head -c 5242880 /dev/urandom > big.bin
./packwriter big big.bin big-cpp.pack

The comparison harness is a small Python script that replicates the Python guide's write_pack for the three one-object packs and the big blob, and a second script that reports peak child memory from the resource usage call. The delta fixtures are deterministic: the text fixture is built from fixed lines and the random fixture from a fixed seed, so the 417, 588, 4389, and 8252 byte figures reproduce exactly on every run. The big blob is random per run, so its hash changes, but the 5,244,522-byte pack size and the memory figures reproduce: the pack size is set by the input size, not its content, because random bytes do not compress.

What this does not cover

The toy-scale pack is bigger than the loose objects it replaces, 221 bytes against 207, and the index adds 1156 bytes on top. At this scale packing buys structure, not bytes. Do not quote the 22.5 percent multi-object saving as a general packing saving; it is the saving against three separate one-object packs, which is the Python guide's shape, not against loose objects.

The text-delta saving is modest for the reason given above: zlib already compresses repetitive text, so the delta only wins 29.1 percent there. The 46.8 percent figure belongs to the random fixture, similar but incompressible data, and that is the shape to look for when deciding whether deltas will pay.

OFS_DELTA was not attempted. Everything here is REF_DELTA, which carries the full 20-byte base id. OFS_DELTA replaces that with a negative offset from the entry and saves 20 bytes per deltified entry, but its offset encoding was not executed, so this tutorial claims nothing about it.

The build prints OpenSSL 3.0 deprecation warnings for the low-level SHA-1 calls, SHA1_Init, SHA1_Update, and SHA1_Final. The build exits 0 and the output is unaffected. The fix is to move the hashing to the EVP interface; the warnings are carried here as a build wart rather than fixed, because the hashing code is the probe's, not the tutorial's subject, and changing it would mean re-verifying every hash in the tables.

One method note, kept because the first run got it wrong. The first random-fixture reconstruction check failed at byte 2. The cause was the probe harness, not the C++ delta: the Python expected-file generator fed the xorshift product back as the next state instead of the post-xor state, so its second output byte diverged from the C++ generator. The first byte matched by luck, since it depends only on the low byte. The generator was fixed, the run repeated, and both fixtures now compare byte-exact. If a reconstruction check fails at an early byte while the pack verifies, suspect the expected file before suspecting the delta.

FAQ

Why REF_DELTA and not OFS_DELTA?

REF_DELTA names the base object by its full id, so the entry is self-describing and the encoding has one less moving part to get wrong. OFS_DELTA saves 20 bytes per entry by naming the base as a negative offset, but the offset encoding was not executed here, so this tutorial does not claim it. The choice is a scope decision, not a performance one.

Does packing always save space?

No, and this tutorial measures the counterexample. Three small objects pack to 221 bytes against 207 loose, and the index adds 1156 bytes. Packing saves space when deltas apply or when the per-object file overhead dominates, which is at real repository scale, not at three toy objects.

Do I need C++ to write packfiles?

No. The Python guide writes a valid one-object pack in stdlib Python. The C++ program here earns its place on capability, not language: multi-object packs, hand-encoded deltas, and streaming writes at lower peak memory. The same three capabilities are writable in any language with zlib and SHA-1.

What about SHA-256 repositories?

Out of scope. Everything here targets SHA-1, the format Git 2.43.0 uses by default, and the same format the Python guide targets. The pack layout is the same shape under SHA-256 with 32-byte ids; the code would need the id length changed throughout.

Sources

Summary
  • A multi-object pack shares one header and one trailer across its objects. Three one-object packs cost 285 bytes; one three-object pack costs 221.
  • A hand-encoded REF_DELTA is two size headers plus copy and insert instructions, and Git accepts it when the encoding is exact. Both fixtures reconstruct byte for byte.
  • The delta win depends on the data shape. Similar and incompressible wins big, 46.8 percent here. Repetitive text wins little, 29.1 percent, because zlib already did the work.
  • Streaming writes trade code for memory. Identical 5,244,522-byte output at 2.94 times lower peak memory at 5 MB.
  • At toy scale, packing costs bytes. A 221-byte pack plus a 1156-byte index replaces 207 bytes of loose objects. Pack for structure and deltas, not for small-file savings.

Keep Exploring