Length-Prefixed Records

Binary File Formats in Practice

Chapter 8 · Length-Prefixed and TLV Records

Fixed layouts only go so far. A name, a comment or an embedded image has no size known in advance, so a format has to say how long each piece is. The standard answer is to write the length first and the data after it. Stacking that idea gives type-length-value (TLV) records, the shape behind a great many real formats, and letting a record's value hold more records gives nesting. This chapter builds all three and shows why a length is both the key to reading and the first thing that can go wrong. It uses the struct tools from Binary File Formats in Practice 3 and the byte-order rules from Binary File Formats in Practice 2.

What was run

Every snippet and solution in this chapter was executed, and the output shown in the comments is what Python printed. Everything is done in memory, so nothing is left behind.

The Length Prefix

A length-prefixed field is a count followed by exactly that many bytes. The reader never has to search for an end marker; it reads the count, then takes that many bytes. Here a 2-byte little-endian length comes before a UTF-8 string:

import struct

def pack_str(s):
    data = s.encode("utf-8")
    return struct.pack("<H", len(data)) + data

def read_str(buf, pos):
    (n,) = struct.unpack_from("<H", buf, pos)
    pos += 2
    return buf[pos:pos + n].decode("utf-8"), pos + n

blob = pack_str("hello") + pack_str("café")
print(blob.hex(" "))
# 05 00 68 65 6c 6c 6f 05 00 63 61 66 c3 a9
s1, pos = read_str(blob, 0)
s2, pos = read_str(blob, pos)
print(s1, s2, pos, len(blob))               # hello café 14 14
print(len("café"), len("café".encode("utf-8")))   # 4 5
    

Two habits are worth noticing. The reader returns the new position along with the value, so the next read starts where this one ended; that is how you walk through a file of mixed fields. And the length counts bytes, not characters: "café" is four characters but five bytes, because the accented letter takes two bytes in UTF-8. Measure the encoded bytes, never the string.

How Big Should the Length Be?

The width of the length field is a design decision that limits the format forever:

Length field	Largest value	Cost
1 byte	255	Cheap, but short names or blobs overflow it
2 bytes	65,535	A common compromise
4 bytes	about 4.29 billion	Roomy, but 4 bytes on every tiny field
Variable (varint)	Effectively unlimited	Small values are small; slightly more code

A varint spends one byte on small numbers and more on big ones. The scheme used by several well-known formats (Protocol Buffers, DWARF and others use variants of it) (check) stores seven bits per byte, lowest bits first, and sets the top bit of a byte to mean "another byte follows":

def enc_varint(n):
    out = bytearray()
    while True:
        low = n & 0x7F
        n >>= 7
        if n:
            out.append(low | 0x80)
        else:
            out.append(low)
            return bytes(out)

def dec_varint(buf, pos):
    result = shift = 0
    while True:
        b = buf[pos]
        pos += 1
        result |= (b & 0x7F) << shift
        if not b & 0x80:
            return result, pos
        shift += 7

for n in (0, 1, 127, 128, 300, 16384):
    e = enc_varint(n)
    print(n, e.hex(" "), dec_varint(e, 0))
# 0 00 (0, 1)
# 1 01 (1, 1)
# 127 7f (127, 1)
# 128 80 01 (128, 2)
# 300 ac 02 (300, 2)
# 16384 80 80 01 (16384, 3)
    

Read 300 by hand: ac 02 means the first byte contributes its low seven bits (0x2c, 44) and says more follows; the second contributes 2 << 7, which is 256. Total 300. This reader has a flaw we return to below: it trusts the input to end. A stream of bytes that all have the top bit set would make it run until it falls off the data, and in a language without bounds checks, past it.

Type-Length-Value

A length prefix tells you how much; it does not tell you what. A TLV record adds a type tag in front: one byte saying what the record means, a length, then the value. A file becomes a sequence of such records. The header here is one type byte and a 2-byte little-endian length, so struct.Struct("<BH") describes it and its size is 3:

HEADER = struct.Struct("<BH")      # type, length

def pack_tlv(t, value):
    return HEADER.pack(t, len(value)) + value

def iter_tlv(buf):
    pos = 0
    while pos < len(buf):
        if len(buf) - pos < HEADER.size:
            raise ValueError(f"truncated header at offset {pos}")
        t, n = HEADER.unpack_from(buf, pos)
        start = pos + HEADER.size
        if start + n > len(buf):
            raise ValueError(f"record at {pos} wants {n} bytes, {len(buf) - start} left")
        yield t, buf[start:start + n]
        pos = start + n

data = pack_tlv(1, b"Ada") + pack_tlv(2, bytes([36])) + pack_tlv(99, b"??") + pack_tlv(1, b"")
print(data.hex(" "))
# 01 03 00 41 64 61 02 01 00 24 63 02 00 3f 3f 01 00 00
for t, v in iter_tlv(data):
    print(t, v)
# 1 b'Ada'
# 2 b'$'
# 99 b'??'
# 1 b''
    

The last record has length 0, which is perfectly valid: an empty value is still a record. Notice that the iterator never needs to know what any type means. It splits the bytes into records by length alone, and a second layer decides what each type is for.

Why TLV Ages Well: Skipping the Unknown

That separation is the point. Suppose a newer program starts writing type 99 and an older one has never heard of it. Because every record states its own length, the old reader can step over the unknown record and carry on with the rest:

KNOWN = {1: "name", 2: "age"}
for t, v in iter_tlv(data):
    print(KNOWN.get(t, f"unknown-{t}"), len(v))
# name 3
# age 1
# unknown-99 2
# name 0
    

Compare that with the fixed layouts of earlier chapters, where an unexpected extra field shifts everything after it and ruins the read.

Idea	Fixed layout (struct)	TLV records
Field positions	Known in advance	Found by walking the lengths
Random access	Jump straight to a field	Must scan from the start (or keep an index)
New field added	Breaks old readers	Old readers can skip it
Optional fields	Wasted space or flags	Just leave the record out
Overhead	None	Type and length on every record

Trusting the Length Is the Danger

The length is read from the file, so it is whatever the file says. The iterator above checks it against the bytes that remain before slicing. Slicing alone would not catch a lie, because Python quietly returns a shorter slice when the end is too close. Two kinds of damage show up:

for bad in (data[:14], data[:-1]):
    try:
        list(iter_tlv(bad))
    except ValueError as e:
        print(e)
# record at 10 wants 2 bytes, 1 left
# truncated header at offset 15
    

The first is a value cut short; the second is a header cut short. Both are reported with the offset, which makes a corrupt file far easier to diagnose than an anonymous failure. Binary File Formats in Practice 9 turns this into a full checklist for untrusted input.

Nested Records

If a record's value is itself a run of TLV records, you have a tree. Mark certain types as containers: when the reader meets one, it runs the same iterator over that record's value. The key point is that the inner reader is handed only the value's bytes, so a child can never read beyond its parent.

PERSON, NAME, AGE, TAG = 0x10, 1, 2, 3
CONTAINERS = {PERSON}

def parse(buf, depth=0):
    if depth > 8:
        raise ValueError("nested too deeply")
    out = []
    for t, v in iter_tlv(buf):
        if t in CONTAINERS:
            out.append((t, parse(v, depth + 1)))
        else:
            out.append((t, v))
    return out

person = pack_tlv(PERSON, pack_tlv(NAME, b"Ada") + pack_tlv(AGE, bytes([36])) + pack_tlv(TAG, b"x"))
doc = pack_tlv(PERSON, pack_tlv(NAME, b"Bo") + person) + pack_tlv(NAME, b"top")
print(doc.hex(" "))
# 10 16 00 01 02 00 42 6f 10 0e 00 01 03 00 41 64 61 02 01 00 24 03 01 00 78 01 03 00 74 6f 70
print(parse(doc))
# [(16, [(1, b'Bo'), (16, [(1, b'Ada'), (2, b'$'), (3, b'x')])]), (1, b'top')]
    

Read the hex: the outer 10 16 00 is a person of 22 bytes; inside it comes a name, then another 10 0e 00 person of 14 bytes. Each length covers everything inside it, including the headers of its children, so lengths nest like brackets. The depth limit matters: a hostile file can nest records thousands deep, and unchecked recursion would exhaust the stack.

Writing Nested Data: Lengths Come Last

Writing has the opposite problem to reading. A container's length is only known once its children are built, so the simple approach is to build the value first and wrap it afterwards, as pack_tlv does. (A writer streaming straight to a file would write a placeholder, then seek back and patch it, using the file-position skills from Binary File Formats in Practice 1.)

Design Choices to Make on Purpose

Does the length include its own header? Some formats count the whole record, others only the value. Here it counts only the value. Pick one and document it; mixing them causes off-by-header bugs.
Padding. Some formats pad values to an even size, as the RIFF chunks in Binary File Formats in Practice 6 do. If so, the pad byte is not counted in the length.
Byte order. Every multi-byte length needs a stated endianness; this chapter uses little-endian.
Duplicates and order. Can a type appear twice? Does order matter? A reader should not have to guess.
Unknown types. Skip them, keep them, or reject them. Skipping and keeping give the best compatibility; rejecting is stricter.

Challenges

Exercise 1

Write pack_strings(items) and unpack_strings(buf) for a list of strings: a varint count, then each string as a varint byte length followed by its UTF-8 bytes. The reader must bound the varint to five bytes, check every length against the bytes remaining, and reject trailing bytes. Show a round trip of a list containing an empty string, an accented string and a 128-character string, the size of the result and the first twelve bytes in hex, the prefix for 127 and 128, four failures (cut short, trailing byte, endless varint, empty input), and an unencodable string being refused.

📄 View solution

Exercise 2

Write a TLV encoder and decoder for a record with a name (type 1, UTF-8), an age (type 2, one byte) and a score (type 3, little-endian 32-bit float), using a 1-byte type and a 2-byte length. The decoder must keep unknown records so that re-encoding gives the same bytes back. Show the encoded hex, a file with an unknown record added, that re-encoding it matches, that the record order does not matter, and three failures (wrong value size, cut value, cut header). The encoder must refuse a value longer than the length field allows.

📄 View solution

Exercise 3

Model a small directory tree as nested TLV: a folder record holds its name and its children; a file record holds a name and a 4-byte size. Write build(tree) and parse(buf), a function that prints the tree indented, and prove that parsing a built tree returns the original. Show a nesting-depth failure, a child whose length overruns its parent, and a truncated file.

📄 View solution

Quick Reference

Length prefix: count first, then exactly that many bytes; the count is in bytes, not characters
Walking a buffer: read a value, return the new position, carry on from there
Varint: 7 bits per byte, low bits first, top bit set means more follows; bound its length when reading
TLV: type, length, value; a file is a run of records; struct.Struct("<BH") for a 1-byte type and 2-byte length
Forward compatibility: skip or keep unknown types using their length
Check before slicing: compare every length with the bytes that remain; report the offset in the error
Nesting: run the iterator on a container's value only, and limit the depth
Writing: build the value, then wrap it with its length

Coming next

Binary File Formats in Practice 9 collects the defences this chapter began: truncation, lying lengths, size limits and other ways to handle untrusted input without crashing or hanging.