Skip to content

Variable Length Quantity

Encode numbers as variable-length quantities, seven bits to a byte with the high bit marking that more follow, and decode them back.

Adapted from Exercism’s problem specification (MIT). Listed under Encoding & Ciphers.

// FILE: variable_length_quantity.nomi
//# Variable-length quantities: each number written as base-128 digits, one
//# per byte, with the high bit set on every byte but the number's last.

/// The bytes of `integers`, each written as its variable-length quantity.
pub fn encode(integers: List<Int>) -> List<Byte>
    integers
    |> Iter.flat_map(encode_one)
    |> Iter.to_list()
end

/// The base-128 digits of `n`, most significant first, with the high bit set
/// on all but the last.
fn encode_one(n: Int) -> List<Byte>
    // A quantity is never negative.
    digits = Int.to_digits(NonNegativeInt.try_from(n)!, 128)
    last = Iter.count(digits) - 1

    digits
    |> Iter.with_index()
    |> Iter.map(fn (i, digit) ->
        byte = Int.to_byte(digit)!
        if i == last then byte else byte ||| 0x80
    end)
    |> Iter.to_list()
end

/// The numbers `bytes` encode, or an error when the last number's final byte
/// is missing.
pub fn decode(bytes: List<Byte>) -> Result<List<Int>, String>
    (pending, values) =
        bytes
        |> Iter.map_reduce(None, fn pending: Maybe<Int>, byte ->
            value = Maybe.with_default(pending, 0) <<< 7 ||| Byte.to_int(byte &&& 0x7F)

            if byte &&& 0x80 == 0 then
                (None, Some(value))
            else
                (Some(value), None)
            end
        end)

    if pending is Some(_) then return Err("incomplete sequence")

    values
    |> Maybe.values()
    |> Iter.to_list()
    |> Ok()
end

// FILE: variable_length_quantity_test.nomi
import variable_length_quantity

test "encode a series of integers, producing a series of bytes"
    cases: List<(String, List<Int>, List<Byte>)> = [
        ("zero",                         [0x0],              [0x0]),
        ("arbitrary single byte",        [0x40],             [0x40]),
        ("asymmetric single byte",       [0x53],             [0x53]),
        ("largest single byte",          [0x7F],             [0x7F]),
        ("smallest double byte",         [0x80],             [0x81, 0x0]),
        ("arbitrary double byte",        [0x2000],           [0xC0, 0x0]),
        ("asymmetric double byte",       [0xAD],             [0x81, 0x2D]),
        ("largest double byte",          [0x3FFF],           [0xFF, 0x7F]),
        ("smallest triple byte",         [0x4000],           [0x81, 0x80, 0x0]),
        ("arbitrary triple byte",        [0x100000],         [0xC0, 0x80, 0x0]),
        ("asymmetric triple byte",       [0x1D59C],          [0x87, 0xAB, 0x1C]),
        ("largest triple byte",          [0x1FFFFF],         [0xFF, 0xFF, 0x7F]),
        ("smallest quadruple byte",      [0x200000],         [0x81, 0x80, 0x80, 0x0]),
        ("arbitrary quadruple byte",     [0x8000000],        [0xC0, 0x80, 0x80, 0x0]),
        ("asymmetric quadruple byte",    [0x357704],         [0x81, 0xD5, 0xEE, 0x4]),
        ("largest quadruple byte",       [0xFFFFFFF],        [0xFF, 0xFF, 0xFF, 0x7F]),
        ("smallest quintuple byte",      [0x10000000],       [0x81, 0x80, 0x80, 0x80, 0x0]),
        ("arbitrary quintuple byte",     [0xFF000000],       [0x8F, 0xF8, 0x80, 0x80, 0x0]),
        ("asymmetric quintuple byte",    [0x86656105],       [0x88, 0xB3, 0x95, 0xC2, 0x5]),
        ("maximum 32-bit integer input", [0xFFFFFFFF],       [0x8F, 0xFF, 0xFF, 0xFF, 0x7F]),
        ("two single-byte values",       [0x40, 0x7F],       [0x40, 0x7F]),
        ("two multi-byte values",        [0x4000, 0x123456], [0x81, 0x80, 0x0, 0xC8, 0xE8, 0x56]),
        (
            "many multi-byte values",
            [0x2000, 0x123456, 0xFFFFFFF, 0x0, 0x3FFF, 0x4000],
            [
                0xC0, 0x0, 0xC8, 0xE8, 0x56, 0xFF, 0xFF, 0xFF, 0x7F, 0x0, 0xFF, 0x7F, 0x81, 0x80,
                0x0,
            ],
        ),
    ]

    subtests cases, (description, integers, expected), description
        assert variable_length_quantity.encode(integers) == expected
    end
end

test "decode a series of bytes, producing a series of integers"
    cases: List<(String, List<Byte>, Result<List<Int>, String>)> = [
        ("one byte", [0x7F], Ok([0x7F])),
        ("two bytes", [0xC0, 0x0], Ok([0x2000])),
        ("three bytes", [0xFF, 0xFF, 0x7F], Ok([0x1FFFFF])),
        ("four bytes", [0x81, 0x80, 0x80, 0x0], Ok([0x200000])),
        ("maximum 32-bit integer", [0x8F, 0xFF, 0xFF, 0xFF, 0x7F], Ok([0xFFFFFFFF])),
        ("incomplete sequence causes error", [0xFF], Err("incomplete sequence")),
        (
            "incomplete sequence causes error, even if value is zero",
            [0x80],
            Err("incomplete sequence"),
        ),
        (
            "multiple values",
            [
                0xC0, 0x0, 0xC8, 0xE8, 0x56, 0xFF, 0xFF, 0xFF, 0x7F, 0x0, 0xFF, 0x7F, 0x81, 0x80,
                0x0,
            ],
            Ok([0x2000, 0x123456, 0xFFFFFFF, 0x0, 0x3FFF, 0x4000]),
        ),
    ]

    subtests cases, (description, bytes, expected), description
        assert variable_length_quantity.decode(bytes) == expected
    end
end
  • A number’s bytes are its base-128 digits from Int.to_digits(n, 128), with the high bit set on every digit but the last, byte ||| 0x80. No loop shifts seven bits at a time.
  • Decoding reads seven bits at a time, value <<< 7 ||| Byte.to_int(byte &&& 0x7F), and a byte’s continuation bit is byte &&& 0x80. The shifts and &&& bind like * and ||| like +, as in Go, so neither needs parentheses.
  • decode is one Iter.map_reduce whose state is the number read so far, Some while its bytes continue and None between numbers, and whose output is Some(value) at each number’s last byte. Maybe.values keeps those, and a state still Some at the end is the incomplete sequence.
  • The one error is Err("incomplete sequence"), the canonical message, as grains does: an Error enum would add a type for one variant.
  • Bytes are List<Byte>, as the canonical List<u8> is, written in hex in the tests (0x7F), as the canonical data’s comments ask of a track’s tests. An Int literal where a Byte is expected is one, so the tables’ types are written once on cases and every byte is a plain literal. Encoding turns each digit, always below 128, into a Byte with Int.to_byte(digit)!; decoding reads a byte’s bits back with Byte.to_int.
  • The encode and decode groups are one subtests table each, named by the description column.