Delta / Variable-Byte Encoding

Why Delta / Variable-Byte Encoding Matters

A search index stores the document IDs containing a term. A list such as $[1000,1001,1002,1003]$ repeats almost the same magnitude four times. Storing four unsigned 32-bit integers takes $16$ bytes. Replacing each ID by its difference from the preceding ID produces $[1000,1,1,1]$; a byte-oriented integer code can store those gaps in $5$ bytes, excluding any list metadata.

Two operations cooperate here. Delta encoding changes a nondecreasing sequence into nonnegative gaps. Variable-byte encoding gives each gap as many bytes as it needs. Delta encoding alone still produces one number per input number; its benefit comes from making those numbers small enough for the following integer code.

You will define an exact byte format, trace its encoding and decoding bit by bit, implement both layers in Python, C++, and Java, and prove the round trip. The decoder will distinguish a valid zero gap from an unfinished number and reject malformed or overflowing data. This matters for postings lists, ordered integer columns, monotonically increasing event positions, and other sequences with small differences.

The examples assume familiarity with shifts and masks. Hashing knowledge helps place postings and indexes in context, but the codec itself uses no hash table. The word delta here means differences between neighboring values; it is distinct from the separate universal integer code called Elias delta coding.

Core Concepts and Terminology

Input and output contract. The combined codec accepts a finite nondecreasing sequence $X=(x_0,\ldots,x_{n-1})$ of integers in $[0,M]$, where $M=2^{32}-1$. Repeated values and an initial zero are allowed. The encoder returns a sequence of byte values in $[0,255]$. Empty input produces an empty byte sequence. No count or header is embedded; the enclosing application supplies the end of the list.

Set the initial previous value to $x_{-1}=0$ and define $$ d_i=x_i-x_{i-1}\qquad(0\le i\lt n). $$ Nondecreasing order ensures $d_i\ge0$. Reconstruct with $$ x_i=\sum_{j=0}^{i}d_j. $$ If a real format uses a different initial base, both ends must know it. The programs fix that base at zero.

Exact variable-byte convention. Each byte has one high stop bit and seven low payload bits. Write the integer's base-128 digits most-significant first. Every byte except the last has stop bit $0$; the last has stop bit $1$. This is the information-retrieval convention described in Introduction to Information Retrieval: variable byte codes. Other formats use different conventions, so the phrase “varint” alone does not identify these bytes.

For an integer $d$, let its digits be $a_0,\ldots,a_{k-1}$, each in $[0,127]$, with $$ d=\sum_{j=0}^{k-1}a_j128^{k-1-j}. $$ The transmitted bytes are $a_0,\ldots,a_{k-2},a_{k-1}+128$. For $d=0$, use a single zero payload with its stop bit set: hexadecimal 80. For positive numbers, the first payload is nonzero. This shortest representation is called canonical.

For example, $128=1\cdot128+0$, so its payload groups are 0000001 and 0000000. Add the stop bits to obtain 00000001 10000000, or hex 01 80. A zero payload in a later group is perfectly valid; only a redundant leading zero group is rejected. Gap $127$ is one byte, FF. Gap $16384=128^2$ is three bytes, 01 00 80.

The decoded value is built using the recurrence $v\leftarrow128v+p$, where $p$ is the current byte's payload. On a stop bit, emit $v$, reset the integer accumulator, and begin a new code. Emitting a gap does not reset the cumulative original value; that state belongs to the delta layer.

How Delta / Variable-Byte Encoding Works, Step by Step

Encoding the delta layer. Start with previous = 0. For each input value, verify it is in range and no smaller than the previous one. Emit value - previous, then update previous. Sorting an unordered input silently changes its meaning, so this codec rejects decreasing input instead of sorting it.

Encoding one gap. Extract the low seven bits with number & 127 and shift right by seven until no higher bits remain. Extraction discovers the least-significant digit first, so reverse the collected digits before transmission. Set 128 on the last transmitted digit only. Always extract at least one digit, including when the original gap is zero.

For gap $128$, extraction gives remainders $0$ and $1$; reversal gives $1,0$; the wire bytes are 01 80. For gap $16384$, extraction gives $0,0,1$, which becomes 01 00 80. Concatenate codes directly: the stop bits already mark the integer boundaries.

Decoding the variable-byte layer. Maintain an integer accumulator $v=0$ and a payload-group count $g=0$. For each input byte:

1. Check that the byte is an integer in $[0,255]$. Separate payload $p=b\bmod128$ from stop flag $s=\lfloor b/128\rfloor$.
2. If this is the first group and $p=0$ with $s=0$, reject a noncanonical leading zero. A single final zero byte 80 remains valid.
3. Before multiplying, check

$$ v\le\left\lfloor\frac{M-p}{128}\right\rfloor. $$ If the condition fails, reject integer overflow. Otherwise assign $v\leftarrow128v+p$ and increase $g$. 4. If $s=1$, emit $v$ as one gap and reset $v=g=0$. If $s=0$ and $g=5$, reject: a 32-bit unsigned value has no valid sixth group. 5. At end of input, require $g=0$. A nonzero group count means the last integer never received a stop byte.

The flowchart below describes this decoder. The encoder uses the inverse digit extraction described above.

Decoding the delta layer. Start its previous value at zero. For each decoded gap, check $d\le M-\text{previous}$ before adding it. This is a second, separate overflow check: valid individual gaps can have an invalid sum. For example, gaps $[M,1]$ each fit in range but would reconstruct $M+1$.

These programs expose the two layers separately for inspection. The combined decode first parses all gaps, then checks their prefix sums. An error raises an exception; the call returns no partially decoded list and does not mutate the input. A streaming interface that emits results earlier would need its own policy for partially consumed invalid data.

A raw byte stream ending at a code boundary is structurally complete, but that alone does not establish that it contains every originally intended item. Removing one entire final code leaves a valid shorter stream. A surrounding count, length, and integrity mechanism are separate format decisions.

flowchart TD
    A["Set accumulator and group count to zero"] --> B{"Another byte?"}
    B -->|"No"| C{"Group count zero?"}
    C -->|"Yes"| Z["Return decoded gaps"]
    C -->|"No"| T["Reject truncated integer"]
    B -->|"Yes"| D["Validate byte; extract payload and stop bit"]
    D --> E{"Byte and leading group valid?"}
    E -->|"No"| R["Reject malformed input"]
    E -->|"Yes"| F{"Accumulator can grow within 32 bits?"}
    F -->|"No"| O["Reject overflow"]
    F -->|"Yes"| G["Accumulate base 128; increase group count"]
    G --> H{"Stop bit is one?"}
    H -->|"Yes"| I["Emit gap and reset integer state"]
    I --> B
    H -->|"No"| J{"Five groups already?"}
    J -->|"Yes"| L["Reject missing stop within limit"]
    J -->|"No"| B

Worked Example with a Full Trace

Use the six values $$ X=[0,127,255,255,16639,4294967295]. $$ The previous-value sequence is $[0,0,127,255,255,16639]$, so the gaps are $$ D=[0,127,128,0,16384,4294950656]. $$ The repeated $255$ contributes a gap of zero and must still produce an output code.

Every encoding step.

1. $0-0=0$: one zero payload, with stop bit set, gives 80.
2. $127-0=127$: one payload $127$, with stop bit set, gives FF.
3. $255-127=128$: base-128 digits $(1,0)$ give 01 80.
4. $255-255=0$: another 80, preserving the duplicate.
5. $16639-255=16384$: digits $(1,0,0)$ give 01 00 80.
6. $4294967295-16639=4294950656$: digits $(15,127,126,126,0)$ give 0F 7F 7E 7E 80.

One way to verify the final digit decomposition is $$ 4294950656 =15\cdot128^4+127\cdot128^3+126\cdot128^2+126\cdot128. $$ All bytes are hexadecimal in the following concatenation: 80 FF 01 80 80 01 00 80 0F 7F 7E 7E 80. The codes occupy the half-open byte ranges $[0,1)$, $[1,2)$, $[2,4)$, $[4,5)$, $[5,8)$, and $[8,13)$.

Every byte of the decode. Each emitted gap resets the base-128 accumulator to zero. The cumulative absolute value changes only when a gap is emitted.

• Offset $0$, 80: payload $0$, accumulator $0$, stop; emit gap $0$, reconstruct value $0$.
• Offset $1$, FF: payload $127$, accumulator $127$, stop; emit gap $127$, reconstruct $127$.
• Offset $2$, 01: payload $1$, accumulator $1$, continue; cumulative value remains $127$.
• Offset $3$, 80: payload $0$, accumulator $1\cdot128=128$, stop; emit gap $128$, reconstruct $255$.
• Offset $4$, 80: payload $0$, accumulator $0$, stop; emit gap $0$, reconstruct another $255$.
• Offset $5$, 01: accumulator $1$, continue; cumulative value remains $255$.
• Offset $6$, 00: accumulator $128$, continue; cumulative value remains $255$.
• Offset $7$, 80: accumulator $16384$, stop; emit that gap, reconstruct $16639$.
• Offset $8$, 0F: accumulator $15$, continue.
• Offset $9$, 7F: accumulator $15\cdot128+127=2047$, continue.
• Offset $10$, 7E: accumulator $2047\cdot128+126=262142$, continue.
• Offset $11$, 7E: accumulator $262142\cdot128+126=33554302$, continue.
• Offset $12$, 80: accumulator $33554302\cdot128=4294950656$, stop; add to $16639$ and reconstruct $4294967295$.

The final integer state is reset, so end-of-stream is valid. The reconstructed list equals the input, including the duplicate and the maximum value. The encoded payload is $13$ bytes compared with $6\cdot4=24$ fixed-width bytes: an $11$-byte saving, about $45.8\%$, before framing. This calculation counts logical wire bytes. The demonstration's integer containers have their own memory costs.

The large final gap takes five bytes, one more than its four-byte fixed-width representation would need. Compression is a property of the entire value distribution; this method does not promise to shrink each gap.

Implementation in Python, C++, and Java

Each panel is one standalone program with the same sample input, exact bytes, round-trip checks, and error demonstrations. Use Python 3, C++17, or Java 8+; save the Java program as Main.java. No random choices or external packages are involved.

The public operations are delta_encode and delta_decode for numeric transforms; vb_encode and vb_decode for arbitrary sequences of unsigned 32-bit integers; and encode / decode for their composition on nondecreasing absolute values. The primitive vb_encode does not require its numbers to be ordered. The combined encoder does. The primitive decoder can accept gaps whose sum exceeds the absolute-value range; the combined decoder rejects that sum.

All numeric values fit the unsigned 32-bit range $[0,2^{32}-1]$, but C++ stores them in int64_t and Java stores them in long so that all three languages expose the same nonnegative API. Encoded bytes are returned as integer containers with elements $0$ through $255$. This makes validation and printed output clear; a C++ vector<int> or Java int[] is not itself packed one-byte storage. Java internally writes packed bytes and masks them back to nonnegative integers when producing the public array. To write an actual packed stream in Python, convert the returned list with bytes(encoded); in other languages, write each validated element as one octet.

Python accepts lists or tuples for numeric inputs and additionally accepts bytes or bytearray for byte inputs. It rejects Boolean and floating-point elements. Java rejects null arrays; C++ receives vectors through its static types. No function mutates its input.

Malformed inputs raise ValueError, invalid_argument, or IllegalArgumentException with the same diagnostic labels:

• VALUE: a numeric element lies outside the supported range, or a Python numeric input has the wrong type.
• ORDER: absolute values decrease.
• BYTE: a byte element is outside $[0,255]$ or has an invalid Python type; Java also uses it for a null byte array.
• NONCANONICAL: the first group has zero payload but does not terminate the integer.
• OVERFLOW: the next base-128 step would exceed $M$.
• TOO_LONG: five groups have arrived without a stop bit.
• TRUNCATED: input ends with an incomplete integer of fewer than five groups.
• SUM_OVERFLOW: individually valid gaps would reconstruct a value greater than $M$.

Checks run in the order shown in the decoder, so a stream with several defects reports the first detected one. For example, a leading 00 is rejected as noncanonical immediately, even if the stream also lacks a final stop byte. The Python and C++ sample assertions check the round trip; Java uses explicit checks so they also run when Java assertions are disabled.

MAX_VALUE = (1 << 32) - 1


def check_numbers(values):
    if not isinstance(values, (list, tuple)):
        raise ValueError("VALUE")
    if any(type(x) is not int or not 0 <= x <= MAX_VALUE for x in values):
        raise ValueError("VALUE")


def delta_encode(values):
    check_numbers(values)
    previous, gaps = 0, []
    for value in values:
        if value < previous:
            raise ValueError("ORDER")
        gaps.append(value - previous)
        previous = value
    return gaps


def delta_decode(gaps):
    check_numbers(gaps)
    previous, values = 0, []
    for gap in gaps:
        if gap > MAX_VALUE - previous:
            raise ValueError("SUM_OVERFLOW")
        previous += gap
        values.append(previous)
    return values


def vb_encode(numbers):
    check_numbers(numbers)
    data = []
    for number in numbers:
        digits = [number & 127]
        number >>= 7
        while number:
            digits.append(number & 127)
            number >>= 7
        digits.reverse()
        digits[-1] |= 128
        data.extend(digits)
    return data


def vb_decode(data):
    if not isinstance(data, (list, tuple, bytes, bytearray)):
        raise ValueError("BYTE")
    numbers, value, groups = [], 0, 0
    for byte in data:
        if type(byte) is not int or not 0 <= byte <= 255:
            raise ValueError("BYTE")
        payload, final = byte & 127, (byte & 128) != 0
        if groups == 0 and payload == 0 and not final:
            raise ValueError("NONCANONICAL")
        if value > (MAX_VALUE - payload) // 128:
            raise ValueError("OVERFLOW")
        value = 128 * value + payload
        groups += 1
        if final:
            numbers.append(value)
            value, groups = 0, 0
        elif groups == 5:
            raise ValueError("TOO_LONG")
    if groups:
        raise ValueError("TRUNCATED")
    return numbers


def encode(values):
    return vb_encode(delta_encode(values))


def decode(data):
    return delta_decode(vb_decode(data))


def vector(values):
    return "[" + ",".join(map(str, values)) + "]"


if __name__ == "__main__":
    original = [0, 127, 255, 255, 16639, MAX_VALUE]
    encoded = encode(original)
    decoded = decode(encoded)
    assert decoded == original
    assert vb_encode(vb_decode(encoded)) == encoded
    print("values=" + vector(original))
    print("gaps=" + vector(delta_encode(original)))
    print("hex=" + " ".join(f"{b:02X}" for b in encoded))
    print("decoded=" + vector(decoded))
    print(f"bytes={len(encoded)} fixed32={4 * len(original)}")
    bad = [
        ("truncated", [1]),
        ("noncanonical", [0, 128]),
        ("sum-overflow", vb_encode([MAX_VALUE, 1])),
    ]
    for label, data in bad:
        try:
            decode(data)
        except ValueError as error:
            print(label + "=" + str(error))
        else:
            raise AssertionError("malformed stream accepted")

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
using namespace std;

constexpr int64_t MAX_VALUE = (int64_t(1) << 32) - 1;

void check_numbers(const vector<int64_t>& values) {
    for (int64_t x : values)
        if (x < 0 || x > MAX_VALUE) throw invalid_argument("VALUE");
}
vector<int64_t> delta_encode(const vector<int64_t>& values) {
    check_numbers(values);
    int64_t previous = 0;
    vector<int64_t> gaps;
    for (int64_t value : values) {
        if (value < previous) throw invalid_argument("ORDER");
        gaps.push_back(value - previous);
        previous = value;
    }
    return gaps;
}
vector<int64_t> delta_decode(const vector<int64_t>& gaps) {
    check_numbers(gaps);
    int64_t previous = 0;
    vector<int64_t> values;
    for (int64_t gap : gaps) {
        if (gap > MAX_VALUE - previous) throw invalid_argument("SUM_OVERFLOW");
        previous += gap;
        values.push_back(previous);
    }
    return values;
}
vector<int> vb_encode(const vector<int64_t>& numbers) {
    check_numbers(numbers);
    vector<int> data;
    for (int64_t number : numbers) {
        vector<int> digits;
        digits.push_back(int(number & 127));
        number >>= 7;
        while (number) {
            digits.push_back(int(number & 127));
            number >>= 7;
        }
        reverse(digits.begin(), digits.end());
        digits.back() |= 128;
        data.insert(data.end(), digits.begin(), digits.end());
    }
    return data;
}
vector<int64_t> vb_decode(const vector<int>& data) {
    vector<int64_t> numbers;
    int64_t value = 0;
    int groups = 0;
    for (int byte : data) {
        if (byte < 0 || byte > 255) throw invalid_argument("BYTE");
        int payload = byte & 127;
        bool final = (byte & 128) != 0;
        if (groups == 0 && payload == 0 && !final)
            throw invalid_argument("NONCANONICAL");
        if (value > (MAX_VALUE - payload) / 128)
            throw invalid_argument("OVERFLOW");
        value = 128 * value + payload;
        ++groups;
        if (final) {
            numbers.push_back(value);
            value = 0; groups = 0;
        } else if (groups == 5) throw invalid_argument("TOO_LONG");
    }
    if (groups) throw invalid_argument("TRUNCATED");
    return numbers;
}
vector<int> encode(const vector<int64_t>& values) {
    return vb_encode(delta_encode(values));
}
vector<int64_t> decode(const vector<int>& data) {
    return delta_decode(vb_decode(data));
}
string show_vector(const vector<int64_t>& values) {
    ostringstream s; s << '[';
    for (size_t i = 0; i < values.size(); ++i) {
        if (i) s << ',';
        s << values[i];
    }
    s << ']'; return s.str();
}
int main() {
    vector<int64_t> original = {0, 127, 255, 255, 16639, MAX_VALUE};
    auto encoded = encode(original);
    auto decoded = decode(encoded);
    assert(decoded == original);
    assert(vb_encode(vb_decode(encoded)) == encoded);
    cout << "values=" << show_vector(original) << '\n';
    cout << "gaps=" << show_vector(delta_encode(original)) << '\n';
    cout << "hex=";
    for (size_t i = 0; i < encoded.size(); ++i) {
        if (i) cout << ' ';
        cout << uppercase << hex << setw(2) << setfill('0') << encoded[i];
    }
    cout << dec << '\n' << "decoded=" << show_vector(decoded) << '\n';
    cout << "bytes=" << encoded.size() << " fixed32=" << 4 * original.size() << '\n';
    vector<pair<string, vector<int>>> bad;
    bad.emplace_back("truncated", vector<int>{1});
    bad.emplace_back("noncanonical", vector<int>{0, 128});
    bad.emplace_back("sum-overflow", vb_encode({MAX_VALUE, 1}));
    for (const auto& test : bad) {
        try { decode(test.second); throw logic_error("malformed stream accepted"); }
        catch (const invalid_argument& error) {
            cout << test.first << '=' << error.what() << '\n';
        }
    }
    return 0;
}

import java.io.ByteArrayOutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final long MAX_VALUE = (1L << 32) - 1;

    static void check_numbers(long[] values) {
        if (values == null) throw new IllegalArgumentException("VALUE");
        for (long x : values)
            if (x < 0 || x > MAX_VALUE) throw new IllegalArgumentException("VALUE");
    }
    static long[] delta_encode(long[] values) {
        check_numbers(values);
        long previous = 0;
        long[] gaps = new long[values.length];
        for (int i = 0; i < values.length; ++i) {
            if (values[i] < previous) throw new IllegalArgumentException("ORDER");
            gaps[i] = values[i] - previous;
            previous = values[i];
        }
        return gaps;
    }
    static long[] delta_decode(long[] gaps) {
        check_numbers(gaps);
        long previous = 0;
        long[] values = new long[gaps.length];
        for (int i = 0; i < gaps.length; ++i) {
            if (gaps[i] > MAX_VALUE - previous)
                throw new IllegalArgumentException("SUM_OVERFLOW");
            previous += gaps[i];
            values[i] = previous;
        }
        return values;
    }
    static int[] vb_encode(long[] numbers) {
        check_numbers(numbers);
        ByteArrayOutputStream out = new ByteArrayOutputStream();
        for (long number : numbers) {
            int[] digits = new int[5];
            int count = 0;
            do {
                digits[count++] = (int)(number & 127);
                number >>= 7;
            } while (number != 0);
            for (int j = count - 1; j >= 0; --j)
                out.write(digits[j] | (j == 0 ? 128 : 0));
        }
        byte[] packed = out.toByteArray();
        int[] data = new int[packed.length];
        for (int i = 0; i < packed.length; ++i) data[i] = packed[i] & 255;
        return data;
    }
    static long[] vb_decode(int[] data) {
        if (data == null) throw new IllegalArgumentException("BYTE");
        List<Long> numbers = new ArrayList<>();
        long value = 0;
        int groups = 0;
        for (int b : data) {
            if (b < 0 || b > 255) throw new IllegalArgumentException("BYTE");
            int payload = b & 127;
            boolean last = (b & 128) != 0;
            if (groups == 0 && payload == 0 && !last)
                throw new IllegalArgumentException("NONCANONICAL");
            if (value > (MAX_VALUE - payload) / 128)
                throw new IllegalArgumentException("OVERFLOW");
            value = 128 * value + payload;
            ++groups;
            if (last) {
                numbers.add(value);
                value = 0; groups = 0;
            } else if (groups == 5) throw new IllegalArgumentException("TOO_LONG");
        }
        if (groups != 0) throw new IllegalArgumentException("TRUNCATED");
        long[] result = new long[numbers.size()];
        for (int i = 0; i < result.length; ++i) result[i] = numbers.get(i);
        return result;
    }
    static int[] encode(long[] values) {
        return vb_encode(delta_encode(values));
    }
    static long[] decode(int[] data) {
        return delta_decode(vb_decode(data));
    }
    static String vector(long[] values) {
        StringBuilder s = new StringBuilder("[");
        for (int i = 0; i < values.length; ++i) {
            if (i != 0) s.append(',');
            s.append(values[i]);
        }
        return s.append(']').toString();
    }
    public static void main(String[] args) {
        long[] original = {0, 127, 255, 255, 16639, MAX_VALUE};
        int[] encoded = encode(original);
        long[] decoded = decode(encoded);
        if (!Arrays.equals(decoded, original)
                || !Arrays.equals(vb_encode(vb_decode(encoded)), encoded))
            throw new AssertionError("round trip failed");
        System.out.println("values=" + vector(original));
        System.out.println("gaps=" + vector(delta_encode(original)));
        StringBuilder hex = new StringBuilder();
        for (int b : encoded) {
            if (hex.length() != 0) hex.append(' ');
            hex.append("0123456789ABCDEF".charAt(b >>> 4));
            hex.append("0123456789ABCDEF".charAt(b & 15));
        }
        System.out.println("hex=" + hex);
        System.out.println("decoded=" + vector(decoded));
        System.out.println("bytes=" + encoded.length + " fixed32=" + 4L * original.length);
        String[] labels = {"truncated", "noncanonical", "sum-overflow"};
        int[][] bad = new int[3][];
        bad[0] = new int[]{1};
        bad[1] = new int[]{0, 128};
        bad[2] = vb_encode(new long[]{MAX_VALUE, 1});
        for (int i = 0; i < bad.length; ++i) {
            try {
                decode(bad[i]);
                throw new AssertionError("malformed stream accepted");
            } catch (IllegalArgumentException error) {
                System.out.println(labels[i] + "=" + error.getMessage());
            }
        }
    }
}

Expected standard output, identical in all three languages:

• values=[0,127,255,255,16639,4294967295]
• gaps=[0,127,128,0,16384,4294950656]
• hex=80 FF 01 80 80 01 00 80 0F 7F 7E 7E 80
• decoded=[0,127,255,255,16639,4294967295]
• bytes=13 fixed32=24
• truncated=TRUNCATED
• noncanonical=NONCANONICAL
• sum-overflow=SUM_OVERFLOW

Complexity, Correctness, and Invariants

Let $n$ be the number of values, $B$ the number of encoded bytes, and $\ell(d)$ the canonical byte length of one gap. Then $$ \ell(0)=1,\qquad \ell(d)=1+\lfloor\log_{128}d\rfloor\quad(d\gt0),\qquad B=\sum_{i=0}^{n-1}\ell(d_i). $$ For the documented unsigned 32-bit range, each gap takes one through five bytes. Hence $n\le B\le5n$ for nonempty input. The bound is safe but need not be tight for every length under the additional prefix-sum constraint. Exact thresholds are: one byte through $127$, two through $16383$, three through $2097151$, four through $268435455$, and five through $4294967295$.

The delta transform and its inverse each take $\Theta(n)$ time. Variable-byte encoding takes $\Theta(n+B)$ time and decoding a valid stream takes $\Theta(B)$ time. Under the fixed 32-bit contract, $B\le5n$, so the combined valid-input operations are $\Theta(n)$ in the best, average, and worst cases, with different byte counts and constants. No input distribution is assumed for an average compression ratio. Empty input costs constant work. A malformed stream is rejected after a prefix of its bytes has been examined.

The implementations materialize intermediate lists. Encoding retains $n$ gaps and the output of $B$ logical bytes; decoding retains decoded gaps and absolute values. Total extra storage including output is $O(n+B)$, and the intermediate numeric array alone costs $O(n)$. The per-integer digit buffer has at most five entries. A fused or streaming implementation could avoid the gap list and keep $O(1)$ state besides its output buffers under this fixed-width contract. A more general $W$-bit integer version needs up to $\lceil W/7\rceil$ groups per number; bit operations cease to be constant-time on arbitrarily large integers.

Correctness of the difference transform. With previous base zero, summing differences telescopes: $$ \sum_{j=0}^{i}(x_j-x_{j-1})=x_i-x_{-1}=x_i. $$ The encoder checks order so every difference is nonnegative. The decoder checks the sum before each update, so every reconstructed value stays in range. Zero differences preserve duplicates rather than dropping them.

Correctness of integer coding. After extracting $k$ low base-128 digits $r_0,\ldots,r_{k-1}$, the original integer $N$ satisfies $$ N=q128^k+\sum_{j=0}^{k-1}r_j128^j, $$ where $q$ is the unprocessed quotient. Division reduces $q$ until it reaches zero; reversing the remainders recovers the standard most-significant-first representation. A final stop bit changes only the boundary marker, which the decoder removes before accumulation.

After reading $r$ payload groups of one code, the decoder invariant is $$ v=\sum_{j=0}^{r-1}a_j128^{r-1-j}. $$ The update $128v+a_r$ establishes the same formula for the next group. A stop bit therefore emits exactly the encoded integer, after which resetting only the integer state starts an independent code. Every integer has one accepted shortest representation: nonzero integers cannot begin with zero payload, and zero has the single byte 80.

Composition and completeness. Integer stop bits uniquely partition a valid stream into complete codes; base-128 decoding recovers the exact gaps; prefix sums recover the exact absolute values. Thus decode(encode(X)) == X for every supported list. Conversely, every byte stream accepted by the combined decoder has canonical gap codes and valid prefix sums, so re-encoding its decoded list produces exactly the same bytes. This second property explains why the decoder rejects redundant leading groups rather than silently normalizing them.

Neither proof supplies corruption detection or application-level list completeness. A changed payload may still form a valid code, and removing whole codes may still leave a valid list. Those require framing and integrity checks outside this codec.

Variants, Pitfalls, and Optimizations

Wire conventions are part of the algorithm. In this lesson, gap $128$ is 01 80: high group first, high bit $1$ means final. Protobuf's unsigned base-128 varints use low group first and high bit $1$ means another byte follows; the same integer is 80 01. Changing just the high-bit test or just the group order does not convert one format into the other. The programs implement the stated IR convention, not a Protobuf parser.

Canonical encodings and zero. Skipping zero gaps loses duplicate values and may lose an initial zero. Treating every zero-payload byte as an error would also reject legitimate internal groups such as 01 00 80. The forbidden case is specifically a zero first payload with no stop bit. Some formats accept redundant encodings; this decoder deliberately rejects them. That acceptance policy is part of its contract.

Signed values and unsorted sequences. Differences can be negative when values decrease. A different codec can map signed differences to nonnegative integers with ZigZag: $$ z(d)= \begin{cases} 2d,&d\ge0,\\ -2d-1,&d\lt0. \end{cases} $$ For example, $0,-1,1,-2,2$ map to $0,1,2,3,4$. Such an extension must define the signed input width, the mapped output width, and overflow checks. It is not a reason to send negative numbers to these functions. A difference between two arbitrary unsigned 32-bit values may need more than a signed 32-bit range, and its ZigZag image can exceed the current unsigned 32-bit gap limit.

Delta-of-delta. Regular timestamps can have large absolute values but nearly constant differences. Encoding changes in those differences can make the second-order values small. They can be negative, so their signed mapping, initial timestamp, and initial difference need explicit storage. This is a different format with more reconstruction state.

Random access and restart points. Self-delimiting integers allow a sequential scan without separate per-integer lengths. They do not give the byte offset or absolute value of item $i$ directly. A checkpoint can store the byte offset of gap $d_i$ and the preceding absolute value $x_{i-1}$, plus its item index. A decoder starts at that known code boundary and prefix-sums from the stored base. Alternatively, independently encoded blocks may each restart from zero, with external block offsets and counts. Raw concatenation of two independently delta-encoded blocks does not preserve this restart: the second block's first value would be treated as another gap from the first block's last value.

Storage and speed. Byte-by-byte branches are simple and portable, but a fast implementation may reserve output capacity, fuse gap generation with encoding, fuse decoding with prefix sums, or use block codecs and SIMD. Keep a clear reference codec and compare exact outputs or decoded values as appropriate; a block codec has its own wire format. The sample's integer arrays are pedagogical containers, so their in-memory size does not equal the logical compressed byte count.

Expansion, framing, and validation. One large gap can occupy five bytes while a raw 32-bit value takes four. Measure total bytes, headers, decoding cost, and expected access pattern. Validate length and count at the application level, bound allocations for the workload, and add a checksum or authenticated envelope when detecting accidental corruption or tampering is required. This codec alone neither detects all alterations nor protects confidentiality.

Common language errors. Java byte and some C++ char types are signed: read an octet as a nonnegative value before checking marker bits or doing arithmetic. Use masks and sufficiently wide accumulators. Do not add before checking prefix-sum overflow, and do not accept end-of-input as an implicit stop. An integer accumulator equal to zero is not the general completion test; the decoder tracks whether a code is open.

Practice Problems and Real-World Use

Start with values near powers of $128$, where byte lengths change. Verify both round-trip identities: decoding an encoded supported list recovers the list, and re-encoding any accepted canonical stream recovers its exact bytes. Include duplicates, an initial zero, empty input, and the maximum value. A test suite that only round-trips through the same encoder and decoder can miss a shared convention bug; compare with a separately constructed byte oracle.

The implementations were checked on $7562$ shared operation inputs: $5889$ accepted and $1673$ rejected. The suite covers all length-zero-through-four sequences over $\{0,1,2,3\}$ for the numeric operations, every single-byte input, selected two-byte combinations, $94$ numeric boundary values, randomized valid lists, and malformed streams. The independent byte oracle builds seven-bit groups from padded binary strings; the independent parser splits at final markers and interprets concatenated payload bits. C++ and Java matched Python's complete results and diagnostic labels on every shared input, and C++ ran with address and undefined-behavior sanitizers. Additional Python-only checks reject Boolean, floating-point, and invalid container inputs.

When applying the method to a real postings list, first establish whether IDs are sorted and whether duplicates have meaning. If the source promises strictly increasing IDs, duplicates may be a data-quality error even though this codec supports them. Preserve those application rules separately from the byte-format rules. For a production format, record its convention, integer width, list framing, restart strategy, and integrity policy so another implementation can decode it without guessing.