bijou-encoding

An arbitrary precision, canonical by construction variable length encoding for integers and Unicode strings, inspired by Ink & Switch's bijou64.

About

Most variable length integer encodings let the same number be written more than one way. LEB128 encodes zero as 0x00, and also as 0x80 0x00, and also as 0x80 0x80 0x00. Decoders are supposed to reject the longer forms, but that rejection is a separate if statement: delete it and every round trip test still passes. Only adversarial input notices. For anything content addressed or signed, that is a security problem, because two different byte strings hash differently while meaning the same thing.

bijou64, designed by Brooklyn Zelenka at Ink & Switch, removes the check by removing the ambiguity. Each length tier subtracts a different cumulative offset before writing its payload, so the tiers cover disjoint ranges of values. An "overlong" encoding does not decode to the same number; it decodes to a different number. There is nothing left to reject.

This package applies that idea to values of any size, and adds Unicode strings.

bijou64 specification: https://github.com/inkandswitch/bijou/blob/main/bijou64/SPEC.md Article: https://www.inkandswitch.com/tangents/bijou64/

Key Features

• Canonical by construction: every value has exactly one encoding, enforced by the arithmetic rather than by a check a decoder could omit
• Arbitrary precision: integers of any magnitude, not just 64 bits
• Length from the first byte: total size is known after one byte, so values can be skipped without decoding
• Sorts correctly: for unsigned values, comparing encoded bytes lexicographically gives the same order as comparing the numbers
• Eight bits per byte: payloads are contiguous big-endian bytes with no continuation bits, which makes large integers about 12% smaller than a 7 bit encoding
• Compact negatives: signed integers use ZigZag, so small negative values still fit in one byte
• Streamable: values can be decoded one at a time from any offset

Installation

npm install bijou-encoding

Usage

import _bijouEncoding from 'bijou-encoding';

{
    const encodedBigInt = _bijouEncoding.encodeBigInt(123456789n),
        encodedNumber = _bijouEncoding.encodeNumber(-42),
        encodedString = _bijouEncoding.encodeString('Hello, 世界! 🌍'),

        decodedBigInt = _bijouEncoding.decodeBigInt(encodedBigInt),
        decodedNumber = _bijouEncoding.decodeNumber(encodedNumber),
        decodedString = _bijouEncoding.decodeString(encodedString),

        // Auto-detect type and encode
        encoded = _bijouEncoding.encode('Hello'),
        encoded2 = _bijouEncoding.encode(12345),
        encoded3 = _bijouEncoding.encode(999n),

        // Encode iterables of numbers or BigInts
        numbers = [1, 2, 3, 100, 1000],
        encodedArray = _bijouEncoding.encodeIterable(numbers),
        decodedArray = _bijouEncoding.decodeNumberArray(encodedArray);
}

Format

Tag byte

The first byte of every value decides everything that follows.

| First byte | Meaning | | --- | --- | | 0x00 – 0xF6 | The byte is the value, 0 through 246. Nothing follows. | | 0xF7 – 0xFE | A tier tag. tag - 246 gives the number of payload bytes, 1 through 8. | | 0xFF | Escape. A payload length follows, itself bijou encoded and offset by 9, then that many payload bytes. |

Payload bytes are a big-endian unsigned integer. The decoded value is the payload plus that tier's offset.

Offsets

Each tier's offset is the first value the previous tiers cannot reach:

OFFSET[0] = 0
OFFSET[1] = 247
OFFSET[n] = OFFSET[n - 1] + 256 ^ (n - 1)

| Tier | Total bytes | Covers | | --- | --- | --- | | 0 | 1 | 0 – 246 | | 1 | 2 | 247 – 502 | | 2 | 3 | 503 – 66,038 | | 3 | 4 | 66,039 – 16,843,254 | | 4 | 5 | 16,843,255 – 4,311,810,550 | | 5 | 6 | 4,311,810,551 – 1,103,823,438,326 | | 6 | 7 | 1,103,823,438,327 – 282,578,800,148,982 | | 7 | 8 | 282,578,800,148,983 – 72,340,172,838,076,918 | | 8 | 9 | 72,340,172,838,076,919 – 18,519,084,246,547,628,534 | | 9 and up | 2 + tier | everything larger, through the escape |

In hexadecimal the offsets form a staircase: 0xF7, 0x01F7, 0x0101F7, 0x010101F7, and so on.

Why there is nothing to check

Because tier ranges are disjoint, writing a value in the wrong tier does not produce a longer encoding of the same number. It produces a different number, which fails immediately against any round trip or hash. bijou64 itself has one extra check, because its top tier can express values past u64::MAX and has to clip them. Arbitrary precision removes even that: there is no ceiling to clip against, so the escape tier needs no bounds test.

Signed integers

Integers are mapped to unsigned values with ZigZag before encoding, so that small magnitudes of either sign stay small:

zigzag(v) = v >= 0 ? 2v : -2v - 1

0 becomes 0, -1 becomes 1, 1 becomes 2, and so on. Values from −124 through 123 fit in a single byte. This costs nothing structurally: ZigZag is itself a bijection, so canonicality is preserved.

Strings

Strings are encoded one Unicode code point at a time, each as an unsigned value with no ZigZag. Applying ZigZag would halve the single byte range and make text noticeably larger.

| Code points | Bytes | | --- | --- | | U+0000 – U+00F6 | 1 | | U+00F7 – U+01F6 | 2 | | U+01F7 – U+101F6 | 3 | | U+101F7 – U+10FFFF | 4 |

Because integers are ZigZagged and code points are not, encodeNumber(97) and encodeString('a') do not produce the same bytes. Each mapping is optimal for its own job.

Unpaired surrogates are permitted, so decodeString(encodeString(value)) returns value for every possible JavaScript string.

API Reference

Encoding

encode(value)

Encodes based on type: BigInt, number, string, or an iterable of BigInts and numbers.

encodeBigInt(value) / encodeNumber(value)

Encodes a signed integer of any magnitude. encodeNumber throws if the value is not an integer.

encodeString(value)

Encodes a Unicode string.

encodeIterable(value)

Encodes an iterable of BigInts and numbers into one concatenated sequence. Types may be mixed freely.

encodedByteLength(value)

Returns the byte count value would occupy without allocating it. Accepts a BigInt, number, or string. Iterables are not accepted, because measuring one would consume it.

Decoding

decodeBigInt(bytes) / decodeNumber(bytes)

Decodes exactly one value. Throws if the data is empty, truncated, or holds anything after the value.

decodeNumber throws if the result falls outside the safe integer range; use decodeBigInt for larger magnitudes.

decodeString(bytes)

Decodes an entire buffer as a sequence of characters.

decodeBigIntArray(bytes) / decodeNumberArray(bytes)

Decodes an entire buffer into an array. Empty input gives an empty array.

decodeBigIntIterable(bytes) / decodeNumberIterable(bytes)

Lazy generator versions, useful for large buffers and for stopping early.

decodeBigIntAt(bytes, byteIndex = 0) / decodeNumberAt(bytes, byteIndex = 0)

Decodes one value starting at byteIndex and returns {byteIndex, value}, where the returned index is the position just past the value. This is the primitive for framed messages.

Input Formats

• Uint8Array and Buffer (used directly, without copying)
• Any other ArrayBuffer view, such as DataView or Int8Array, reinterpreted as bytes over the same memory
• ArrayBuffer and SharedArrayBuffer
• Arrays and array-likes of byte values

Errors

Every error is an isotropic-error with a name, a message, and a details object.

| name | message | | --- | --- | | TypeError | Value must be a bigint, number, string, or iterable | | TypeError | Value must be a bigint | | TypeError | Value must be a string | | TypeError | Value must be a bigint, number, or string | | TypeError | Number value must be an integer | | TypeError | Iterable value must be a bigint or number | | SyntaxError | Incomplete bijou sequence | | SyntaxError | Unexpected data after bijou value | | RangeError | Value is outside safe integer range | | RangeError | Value is not a valid code point | | RangeError | Byte index is outside the bounds of the data | | RangeError | Encoded payload length is too large |

Note what is absent: there is no "invalid encoding" or "overlong sequence" error, because those states cannot be represented.

Sorting without decoding

For unsigned values, encoded byte order equals numeric order, so encoded keys can be sorted or binary searched directly. Note that this property applies to code points and to raw unsigned values; the signed integer functions apply ZigZag first, which interleaves negatives and positives.

Relationship to bijou64

This is not wire compatible with bijou64, and is not meant to be. bijou64 uses a tag threshold of 248 and stops at u64; this library uses 247 so that 0xFF is free to act as a length escape. The bijou family already treats the threshold as a per-variant choice. bijou32 uses 252 and bijou128 uses 240. None of them are wire compatible with each other. Treat this as another member of that family, with an unbounded value range. Values 0 through 246 are byte identical across all of them.

Attribution

The tier and offset design is from bijou64 by Brooklyn Zelenka at Ink & Switch, whose specification is licensed CC BY-SA 4.0; bijou64 in turn credits VARU64 by Aljoscha Meyer for its tag byte framing, and Git's pack offset encoding and SQLite4's varint for the offset idea. This implementation and its documentation are independent work and copy no text from those specifications.

License

zlib/libpng license. See LICENSE.md for details.

Contributing

Issues and pull requests are welcome! Please ensure all tests pass and add new tests for any new functionality.

See Also

• bijou64 article
• bijou64 specification