Guide

From a number to a wire

Nine chapters, in the order a packet meets them: the octets a number becomes, the five rules that decide how, and what each reader does when the bytes run out. Every snippet compiles against the packages as they ship, and every output below was printed by the code above it.

01Install, and the first four octets

One package per encoding, so you add the module and import what you need.

moon add moonbitstack/moonvar

import {
  "moonbitstack/moonvar/fixed",
}

A number going onto a wire is a run of octets, and the rest of this guide prints them as hex. This helper is the only thing in the guide that is not from the library; it stays the same throughout.

/// Octets as hex, two digits each.
fn hex(b : BytesView) -> String {
  let digits = "0123456789abcdef"
  let out = StringBuilder()
  for i = 0; i < b.length(); i = i + 1 {
    let octet = b[i].to_int()
    out.write_char(digits[octet >> 4].unsafe_to_char())
    out.write_char(digits[octet & 0xf].unsafe_to_char())
  }
  out.to_string()
}

A thirty-two-bit value, written and read back:

let buf = Buffer()
@fixed.write_u32(buf, 0x12345678)
let wire = buf.to_bytes()
println(hex(wire[:]))
println(@fixed.read_u32(wire[:]))

Eight hex digits, one per nibble, most significant first. That order is the default and it is big-endian, which is what RFC 1700 calls network byte order.

02Fixed widths, and the order to read them in

Every reader takes at~, the octet it starts from, and order~, which way round the octets go. Every writer takes a Buffer and appends.

let buf = Buffer()
@fixed.write_u16(buf, 513)
@fixed.write_u16(buf, 513, order=Little)
@fixed.write_u24(buf, 0x010203)
let wire = buf.to_bytes()
println(hex(wire[:]))
println(@fixed.read_u16(wire[:]))
println(@fixed.read_u16(wire[:], at=2, order=Little))
println(@fixed.read_u24(wire[:], at=4))
println(@fixed.read_u32(wire[:], at=14))

513 is 0x0201; four octets carry it either way round. The 24-bit width is the one TLS writes a handshake message in and HTTP/2 writes a frame in, so it is here even though no machine has a 24-bit register.

The last line asks for four octets at offset 14 in a seven-octet view. There is no such value, and the answer is None rather than a wrapped offset or a read past the end. Every reader in this package is built the same way.

03Widths the caller carries

Some protocols spell their own width — int<3>, a three-octet DNS length — and the caller only learns it at run time. read_uint and write_uint take that width as an argument and work for one to eight octets.

let buf = Buffer()
@fixed.write_uint(buf, 0x010203UL, size=3)
@fixed.write_f64(buf, 1.5)
@fixed.write_i16(buf, -2)
let wire = buf.to_bytes()
println(hex(wire[:]))
println(@fixed.read_uint(wire[:], size=3))
println(@fixed.read_f64(wire[:], at=3))
println(@fixed.read_i16(wire[:], at=11))
println(@fixed.size(0x010203UL))

1.5 is the IEEE-754 double 3ff8000000000000, written through write_f64 and read back by reinterpreting the bits rather than converting them, which is what a wire format means by a float. -2 is two's complement, and size says three octets are enough for 0x010203 — no writing, just the width.

04QUIC: two bits say how wide

RFC 9000 §16 puts the width in the first two bits: 00 is one octet with six bits of value, 01 two octets with fourteen, 10 four with thirty, 11 eight with sixty-two. Everything else is the value, big-endian.

println(hex(@quic.encode(1337UL)[:]))
println(hex(@quic.encode(1UL)[:]))
println(hex(@quic.encode(1UL << 30)[:]))
println(@quic.size(1UL << 30))
println(@quic.decode(b"\x45\x39"[:]))
println(@quic.decode(b"\x45"[:]))
println(@quic.max)

0x45 is 0100 0101: prefix 01 for two octets, then the top six bits of the value. 1337 is 0x539, which needs those six bits and the second octet.

The second decode is handed one octet of a value that declares two. None — the reader will not invent the missing octet. max is the ceiling the two-bit prefix allows: sixty-two bits.

05HPACK: a value in the low N bits

RFC 7541 §5.1 packs a value into the low bits of the first octet and lets it continue into further octets when it does not fit. The bits above the prefix belong to the field, and you pass them in as flags.

println(hex(@prefix.encode(10, prefix=5)[:]))
println(hex(@prefix.encode(1337, prefix=5)[:]))
println(hex(@prefix.encode(1337, prefix=5, flags=0x80)[:]))
println(@prefix.size(1337, prefix=5))
println(@prefix.decode(b"\x9f\x9a\x0a"[:], prefix=5))
println(@prefix.flagged(b"\x9f\x9a\x0a"[:]))
println(@prefix.limit)

Ten fits: 0x0a is the value itself. 1337 does not, so the first octet saturates at the five-bit ceiling (31) and the remainder follows in seven-bit continuation octets. flags=0x80 sets the high bit of the first octet — in HPACK that bit says the string after the length is Huffman-coded — and decode masks it off, which is why the same three octets read back as 1337 both times.

flagged reads that one bit without decoding anything, for the case where the caller only needs to know. limit is the ceiling of the reader here, a positive Int; §5.1 leaves the ceiling to the implementation and asks for a decoding error past it.

06LEB128: seven bits an octet

The encoding protobuf calls base 128 varints, and DWARF calls unsigned LEB128: seven bits per octet, least significant group first, with the eighth bit set on every octet except the last.

println(hex(@leb128.encode(1UL)[:]))
println(hex(@leb128.encode(150UL)[:]))
println(hex(@leb128.encode(0xffffffffffffffffUL)[:]))
println(@leb128.size(150UL))
println(@leb128.decode(b"\x96\x01"[:]))
println(@leb128.limit)

150 is 0x96 0x01: 0x96 carries the low seven bits with the continuation bit set, 0x01 the next seven with it clear. A sixty-four-bit value takes ten octets, and limit is ten, which is what stops a reader following continuation bits for as long as a peer cares to send them.

Signed values are folded onto unsigned ones first, so a small negative number stays short. Without it, -1 would sign-extend to sixty-four bits and take all ten octets.

println(@leb128.zigzag(-2L))
println(@leb128.unzigzag(3UL))

zigzag maps 0 to 0, -1 to 1, 1 to 2, -2 to 3. unzigzag undoes it with a logical shift, so the top half of the signed range comes back intact instead of with its sign smeared.

07MySQL: a marker octet

MySQL's length-encoded integer spends one octet on anything below 251. Above that, the first octet is a marker saying how many little-endian octets follow: 0xfc two, 0xfd three, 0xfe eight.

println(hex(@lenenc.encode(250UL)[:]))
println(hex(@lenenc.encode(251UL)[:]))
println(hex(@lenenc.encode(65536UL)[:]))
println(hex(@lenenc.encode(1UL << 24)[:]))
println(@lenenc.decode(b"\xfc\x39\x05"[:]))
println(@lenenc.size(65536UL))

250 is still bare, so 0xfb and everything above it is free to mean something else. 251 needs the marker and two octets: fc fb 00, little end. 1337 arrives as fc 39 05 — 0x0539, low octet first.

This is the one encoding in the module that writes its payload little-endian, and it says so by where the marker sits rather than by an order argument.

08Failure is a value

The fixed readers answer None. The variable-length readers raise Refused, a suberror each package declares, because a truncation and a value past the ceiling are different faults and a caller often wants to tell them apart.

try {
  let (v, n) = @leb128.decode(b"\x80"[:])
  println("\{v} in \{n} octets")
} catch {
  Truncated(m) => println("truncated: " + m)
  Exceeded(limit~, got~) => println("past \{limit} octets: \{got}")
}

0x80 sets the continuation bit and then stops, so the value continues past the end of the view. The same message comes with the fault attached: the error's Show prints Truncated(the value continues past the end), which is what you want in a log line.

A first octet the protocol reserves is its own fault. 0xfb is NULL in a row and 0xff begins an error packet; neither is a length, and a reader that took one for a length would be off by however much followed.

try {
  let (v, _) = @lenenc.decode(b"\xfb"[:])
  println(v)
} catch {
  Truncated(m) => println("truncated: " + m)
  Reserved(got~) => println("reserved first octet: \{got}")
}

09Putting it together: a frame

A length in front of a payload is the shape most protocols actually send. The length's own width depends on the length, which is why size exists and why a two-bit width prefix earns its keep.

fn frame(payload : BytesView) -> Bytes {
  let buf = Buffer()
  buf.write_bytes(@quic.encode(payload.length().to_uint64()))
  buf.write_bytes(payload.to_owned())
  buf.to_bytes()
}

fn unframe(b : BytesView) -> Bytes? {
  match @quic.decode(b) {
    Some((len, n)) =>
      if b.length() - n >= len.to_int() {
        Some(b[n:n + len.to_int()].to_owned())
      } else {
        None
      }
    None => None
  }
}

let framed = frame(b"\x01\x02\x03\x04\x05"[:])
println(hex(framed[:]))
match unframe(framed[:]) {
  Some(payload) => println(hex(payload[:]))
  None => println("nothing")
}
println(unframe(b"\x05\x01\x02"[:]))
println(hex(frame(Bytes::make(70000, b'\x00'))[:3]))

Five octets of payload, one octet of length. The second frame claims five octets and brings two, so unframe answers None instead of returning half a payload.

The last line is a seventy-thousand octet payload. Its length no longer fits in six bits, so the first octet becomes 0x80 — prefix 10, four octets of length — and 800111 is the first three of them. Nothing in the writer had to say how wide it was going to be.

Where the guide stops

That is the whole surface: five encodings, each a package, each with an encoder, a reader, a size and its own idea of what a bad input is. The reference has every signature; the bit lab shows the same octets one bit at a time.