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
endok encode a series of integers, producing a series of bytes (23 cases)
ok decode a series of bytes, producing a series of integers (8 cases)
test result: ok. 31 passed, 0 failed
How it’s written
Section titled “How it’s written”- 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 isbyte &&& 0x80. The shifts and&&&bind like*and|||like+, as in Go, so neither needs parentheses. decodeis oneIter.map_reducewhose state is the number read so far,Somewhile its bytes continue andNonebetween numbers, and whose output isSome(value)at each number’s last byte.Maybe.valueskeeps those, and a state stillSomeat the end is the incomplete sequence.- The one error is
Err("incomplete sequence"), the canonical message, as grains does: anErrorenum would add a type for one variant. - Bytes are
List<Byte>, as the canonicalList<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 aByteis expected is one, so the tables’ types are written once oncasesand every byte is a plain literal. Encoding turns each digit, always below 128, into a Byte withInt.to_byte(digit)!; decoding reads a byte’s bits back withByte.to_int. - The encode and decode groups are one
subteststable each, named by the description column.