Binary patterns

Most languages parse binary formats with a pile of shifts, masks and offsets that is wrong in one place. Nexium borrows an idea from Erlang: a pattern that describes the bytes, which the compiler turns into the shifts and masks, with every length checked.

import std.bytes

/// The first chunk of a PNG file, as a binary pattern reads it.
struct PngHeader { width: u32, height: u32, depth: u8, color: u8 }

error Png { NotPng, Truncated, BadCrc }

fn parse_png(data: []u8) -> Png!PngHeader {
    match data {
        // the eight-byte signature, then the IHDR chunk: length, type, 13 bytes of fields, crc
        <<0x89, 'P', 'N', 'G', 0x0d, 0x0a, 0x1a, 0x0a,
            len:32/big, 'I', 'H', 'D', 'R',
            width:32/big, height:32/big, depth:8, color:8, compression:8, filter:8, interlace:8,
            crc:32/big, rest:bytes>> => {
            if len != 13 { return error.Truncated }
            // the crc covers the type and the fields: bytes 12 to 29 of the file
            if crc != bytes.crc32(data[12..29]) { return error.BadCrc }
            return PngHeader{ .width = width, .height = height, .depth = depth, .color = color }
        },
        <<0x89, 'P', 'N', 'G', rest:bytes>> => return error.Truncated,
        _ => return error.NotPng,
    }
}

/// A length-prefixed message: the header says how many bytes follow.
fn frames(stream: []u8) -> List([]u8) {
    var out = List([]u8).new()
    var rest = stream
    while rest.len > 0 {
        match rest {
            <<len:16/little, payload:len*8, tail:bytes>> => {
                out.append(payload)
                rest = tail
            },
            _ => break,
        }
    }
    return out
}

fn main() {
    // a 1x1 PNG's first 33 bytes, with a valid crc
    let png = b"\x89PNG\x0d\x0a\x1a\x0a\x00\x00\x00\x0dIHDR\x00\x00\x00\x01\x00\x00\x00\x01\x08\x06\x00\x00\x00\x1f\x15\xc4\x89"
    let h = parse_png(png) catch |e| { println("error: {}", .{@errorName(e)}); return }
    println("{}x{} depth {} color type {}", .{h.width, h.height, h.depth, h.color})
    for bad in ["not a png at all", png[0..20]] {
        _ = parse_png(bad) catch |e| {
            println("{}", .{@errorName(e)})
            continue
        }
    }

    // reading bit fields: an IPv4 header's first byte holds version and header length
    let first: u8 = 0x45
    match [first] {
        <<version:4, ihl:4>> => println("ipv4 version {} header {} words", .{version, ihl}),
        _ => { },
    }

    // construction: the same syntax writes bytes into a buffer
    var buf: [64]u8 = undefined
    let written = <<3:16/little, "abc", 300:16/big, 1:1, 0:3, 5:4>> into buf[..] catch { return }
    println("{} bytes: {}", .{written.len, bytes.hex(written)})

    // framing a stream
    let stream = b"\x03\x00abc\x05\x00hello\x02\x00ok"
    for f, i in frames(stream) { println("frame {}: {}", .{i, f}) }
}

1x1 depth 8 color type 6
NotPng
Truncated
ipv4 version 4 header 5 words
8 bytes: 0300616263012c85
frame 0: abc
frame 1: hello
frame 2: ok

Reading#

    match data {
        <<0x89, 'P', 'N', 'G', 0x0d, 0x0a, 0x1a, 0x0a,
          len:32/big, 'I', 'H', 'D', 'R',
          width:32/big, height:32/big, depth:8, color:8, compression:8, filter:8, interlace:8,
          crc:32/big, rest:bytes>> => { ... }

A binary pattern is a list of segments between << and >>, matched against a []u8 from left to right. A segment is either a literal that must be there (0x89, 'P') or a binding with a size in bits:

• width:32/big binds a 32-bit big-endian unsigned integer. The size decides the type: up to 64 bits is an integer of the smallest fitting width (u8, u16, u32, u64), so width is a u32 and depth:8 a u8, with no cast.
• version:4, ihl:4 split one byte into two four-bit fields; sizes need not be multiples of eight.
• payload:len*8 has a size computed from an earlier binding: length- prefixed data in one line.
• rest:bytes takes everything that is left, as a []u8 view of the input. It is how a pattern says "and more follows"; without it the pattern must consume the input exactly.

The modifiers after / are big (the default), little, native, signed, unsigned, float and utf8. When the input is too short for the pattern, the arm simply does not match and the next one is tried, which is why parse_png can say Truncated for something that has the signature and nothing after it: the second arm needs only the four bytes.

Nothing is copied by a pattern. The integer bindings are read out of the input; payload and rest are views into it.

Writing#

    let written = <<3:16/little, "abc", 300:16/big, 1:1, 0:3, 5:4>> into buf[..] catch { return }

The same syntax constructs bytes. into names a []mut u8 buffer; the result is the prefix that was written, or error.BufferTooSmall. Values larger than their size are an error at compile time when they are literals, and checked when they are not.

Where it pays#

Network protocols, file headers, embedded devices, anything with a wire format. The frames example is the shape of every length-prefixed protocol: match a length and that many bytes, keep the tail, repeat. std.bytes sits beside patterns with hex, base64, crc32 and the endian read/write helpers for the cases where a pattern is more than you need.

Next: compile time.

Exercises#

The compiler grades these: nx topo 12 writes them into a directory, nx topo check runs them. Or do them here: the code is editable, Run runs it with the compiler in the page (it loads on the first run and never sends your code anywhere), Check grades it as nx topo check would, and Reset puts the exercise back. Ctrl+Enter runs.

fn main() {
    let packet = b"\x00\x03hi!\xff"
    match packet {
        <<len:???/big, payload:len*8, rest:bytes>> => println("{} {} {}", .{len, payload, rest.len}),
        _ => println("no match", .{}),
    }
}

3 hi! 1

fn main() {
    let packet = b"\x00\x03hi!\xff"
    match packet {
        <<len:16/big, payload:len*8, rest:bytes>> => println("{} {} {}", .{len, payload, rest.len}),
        _ => println("no match", .{}),
    }
}

fn main() {
    let byte = b"\xa5"
    match byte {
        <<hi:4, lo:4>> => println("{} {}", .{hi, lo}),
        _ => println("?", .{}),
    }
}

10 5