Milestone 3 of 11

Build the canonical integer stream

Implement the published shortest variable-byte representation and an offset decoder that rejects truncation, overflow, and non-canonical forms.

The integer codec has one local canonical rule. Its continuation bit is not a convention to guess from another textbook; the supplied rule decides every byte.

Goal

Implement offset-based canonical variable-byte encoding and decoding for non-negative integers, prove shortest encodings, and reject malformed, excessive, and out-of-bounds streams.

Inputs

Use the validated bounds and gap values. Each byte carries a value group from 0 through 127; groups are least-significant first. Add 128 when another byte follows, leave the final byte below 128, and encode zero as the single byte b"\x00".

The decoder accepts a byte sequence and offset, returns one integer and the next unread offset, and never treats later fields as trailing bytes for the current integer. Every valid integer has one shortest encoding.

Deliverables

Implement src/varint.py with an encoder and offset-based decoder. Produce output/varint_trace.csv containing source integers, encoded byte groups, offsets, decoded values, and next offsets for hand-check and corpus cases.

Checks

Check zero, one-byte values, multi-byte values, maximum configured values, and values at group boundaries. Prove encode/decode round trips and shortest encodings. Reject an absent first byte, unterminated integer, multi-byte integer whose final value group is zero, decoded value above the configured maximum, encoded byte count above its bound, and any read beyond the declared payload.

Check that a decoder stops at the integer's final byte and returns the exact next unread offset. Reject non-canonical alternatives rather than accepting multiple encodings for one value.

Workspace

Keep integer coding and its checks in src/varint.py. Write the trace only; do not encode text fields or compose the index payload yet.

Hints

HintSeparate value groups from continuation

Mask off the value group, then use the continuation marker only to decide whether another byte is required. The final group must be below 128.

HintCarry the offset

Decode from the supplied offset and return the first unread offset. Do not consume a byte belonging to the next field.

HintCanonical means shortest

A final zero group in a multi-byte integer represents a longer spelling of a value. Reject it instead of trimming or normalizing the stream.

Review

Trace zero and one value that needs two bytes. Which byte has continuation set, and what proves the two-byte form is canonical rather than padded?

How to check your work

Checks compare encoded groups, offsets, decoded values, and rejection reasons with the fixtures. The supplied fixture uses the local continuation-bit rule even when another codec would assign the high bit differently.