Compact "Best Size" Encoding/Decoding — Design Research

[SeanTAllen]

Research and design notes for implementing issue #1 — compact "best size" encoding and decoding methods.

Background

The MessagePack spec says: "If an object can be represented in multiple possible output formats, serializers SHOULD use the format which represents the data in the smallest number of bytes."

Currently, callers must manually choose the wire format (uint_8, uint_16, etc.). Every other popular msgpack implementation (Python, Ruby, Java, C, Go, C#, Rust) provides unified encode/decode methods that automatically select the smallest format. The format-specific methods remain for callers who want explicit control.

Research Findings

How Other Implementations Handle This

Seven implementations were surveyed: msgpack-python, msgpack-ruby, msgpack-java, msgpack-c, vmihailenco/msgpack (Go), tinylib/msgp (Go), MessagePack-CSharp, and rmp (Rust).

Encoding: All provide a single "pack int" / "pack string" method that auto-selects the most compact format. Some (like rmp for integers) also expose format-specific writers alongside the auto-selecting ones.

Decoding: Every implementation has a single unified decode method per type family. No implementation exposes format-level details on the decoder. A string is a string regardless of whether it was encoded as fixstr, str_8, str_16, or str_32. The same applies to integers, arrays, maps, and binary data.

Our library is the outlier by having format-specific decoder methods (fixstr() vs str(), fixarray() vs array_16() vs array_32(), etc.).

Signed/Unsigned Integer Encoding

The spec treats all integer formats (positive fixint, negative fixint, int 8/16/32/64, uint 8/16/32/64) as one "int format family." Standard practice across implementations is to encode positive signed values using unsigned formats when they're smaller. For example, int(5) encodes as positive_fixint (1 byte), not int_8 (2 bytes). This means the int() decoder must handle unsigned format bytes too.

No Breaking Changes

All changes are purely additive:

• New encoder methods add new API surface without affecting existing methods.
• New decoder methods add new API surface.
• The one modified method (str() decoder, extended to handle fixstr) only becomes more permissive — cases that previously errored now succeed.

Design

Compact Encoder Methods (on MessagePackEncoder)

New methods alongside existing format-specific ones:

uint(b: Writer, v: U64) — non-partial, selects smallest unsigned format:

Value range	Format	Bytes
0–127	positive_fixint	1
128–255	uint_8	2
256–65535	uint_16	3
65536–2^32-1	uint_32	5
2^32–U64.max	uint_64	9

int(b: Writer, v: I64) — non-partial, positive values use unsigned formats per spec:

Value range	Format	Bytes
0 to 127	positive_fixint	1
-32 to -1	negative_fixint	1
128 to 255	uint_8	2
-128 to -33	int_8	2
256 to 65535	uint_16	3
-32768 to -129	int_16	3
65536 to 2^32-1	uint_32	5
-2^31 to -32769	int_32	5
2^32 to I64.max	uint_64	9
I64.min to -(2^31)-1	int_64	9

str(b: Writer, v: ByteSeq) ? — selects fixstr/str_8/str_16/str_32 by size.

bin(b: Writer, v: ByteSeq) ? — selects bin_8/bin_16/bin_32 by size.

array(b: Writer, s: U32) — non-partial, selects fixarray/array_16/array_32.

map(b: Writer, s: U32) — non-partial, selects fixmap/map_16/map_32.

ext(b: Writer, t: U8, v: ByteSeq) ? — prefers fixext for matching sizes (1/2/4/8/16 bytes), falls back to ext_8/ext_16/ext_32.

timestamp(b: Writer, sec: I64, nsec: U32) ? — selects timestamp_32 (when nsec==0 and sec fits U32), timestamp_64 (when sec fits 34-bit unsigned), or timestamp_96.

Compact Decoder Methods (on MessagePackDecoder)

uint(b: Reader ref): U64 ? — peeks at format byte, handles positive_fixint + uint_8/16/32/64. Returns U64.

int(b: Reader ref): I64 ? — peeks at format byte, handles all integer formats (positive/negative fixint + all int/uint formats). Errors if uint_64 value exceeds I64.max. Returns I64.

str() extended — the existing str() method is extended to also handle fixstr format bytes (0xA0–0xBF). Previously only handled str_8/16/32.

array(b: Reader ref): U32 ? — peeks at format byte, handles fixarray + array_16 + array_32. Returns U32.

map(b: Reader ref): U32 ? — peeks at format byte, handles fixmap + map_16 + map_32. Returns U32.

No changes needed for byte_array(), ext(), or timestamp() — they already handle all their format variants.

Streaming Decoder

No changes needed. It already returns a union type (MessagePackValue) that handles any wire format transparently.

Test Strategy

• Boundary unit tests: Verify the correct format byte is selected at each size boundary (e.g., 127 → positive_fixint, 128 → uint_8).
• Roundtrip unit tests: Compact-encode then compact-decode at each boundary, verify value preservation.
• Property-based roundtrip tests: For any U64/I64/String, compact-encode then compact-decode returns the original value.

[SeanTAllen]

Done in #60