kim-encoding

A JavaScript implementation of Douglas Crockford's Kim encoding specification - a simple and efficient encoding that delivers 7 bits per byte.

About Kim Encoding

Kim (Keep It Minimal) encoding is a variable-length encoding scheme invented by Douglas Crockford. It efficiently encodes integers and Unicode strings while maintaining simplicity. The encoding uses 7 bits per byte, with the high bit used as a continuation flag.

Original Specification: https://www.crockford.com/kim.html

Key Features

• Efficient: Uses 7 bits per byte with minimal overhead
• Simple: Straightforward encoding/decoding algorithm
• Versatile: Handles BigInts, numbers, and Unicode strings
• Compact: Variable-length encoding adapts to value size
• Unicode-aware: Properly handles all Unicode characters including surrogate pairs
• Strict: Rejects aliased, overlong, and truncated encodings rather than guessing
• Streamable: Values can be decoded one at a time from anywhere in a buffer

Installation

npm install kim-encoding

Usage

import _kimEncoding from 'kim-encoding';

{
    // Encode various types
    const encodedBigInt = _kimEncoding.encodeBigInt(123456789n),
        encodedNumber = _kimEncoding.encodeNumber(42),
        encodedString = _kimEncoding.encodeString('Hello, 世界! 🌍'),

        // Decode back to original values
        decodedBigInt = _kimEncoding.decodeBigInt(encodedBigInt),
        decodedNumber = _kimEncoding.decodeNumber(encodedNumber),
        decodedString = _kimEncoding.decodeString(encodedString),

        // Auto-detect type and encode
        encoded = _kimEncoding.encode('Hello'), // Encodes a string
        encoded2 = _kimEncoding.encode(12345), // Encodes a number
        encoded3 = _kimEncoding.encode(999n), // Encodes a BigInt

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

API Reference

Every function returning encoded bytes returns a Uint8Array.

Encoding Functions

encode(value)

Automatically encodes based on the value type: BigInt, number, string, or an iterable of BigInts and numbers.

encodeBigInt(value)

Encodes a BigInt of any magnitude. Throws if the value is not a BigInt.

encodeNumber(value)

Encodes an integer number. Throws if the value is not an integer.

encodeString(value)

Encodes a Unicode string. Throws if the value is not a string.

encodeIterable(value)

Encodes an iterable of BigInts and numbers into a single concatenated sequence. Values may be freely mixed.

encodedByteLength(value)

Returns the number of bytes value would occupy, without allocating the encoded result. Accepts a BigInt, number, or string. This is intended for sizing buffers and for writing length prefixes; iterables are not accepted because measuring one would consume it.

Decoding Functions

Decoding functions accept any of the input formats below.

decodeBigInt(bytes) / decodeNumber(bytes)

Decodes exactly one value. Throws if the data is empty, truncated, or contains anything after the value. To read one value from a larger buffer, use decodeBigIntAt / decodeNumberAt.

decodeNumber throws if the value falls outside Number.MIN_SAFE_INTEGER through Number.MAX_SAFE_INTEGER; use decodeBigInt for larger magnitudes.

decodeString(bytes)

Decodes an entire buffer as a sequence of Unicode characters.

decodeBigIntArray(bytes) / decodeNumberArray(bytes)

Decodes an entire buffer into an array of values. An empty buffer produces an empty array.

decodeBigIntIterable(bytes) / decodeNumberIterable(bytes)

The same as the array functions, but returns a generator that decodes lazily. Useful for large buffers, for stopping early, and for composing with iterator helpers.

for (const value of _kimEncoding.decodeNumberIterable(data)) {
    if (value === 0) {
        break; // remaining bytes are never decoded
    }
}

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

Decodes a single value beginning at byteIndex and returns {byteIndex, value}, where the returned byteIndex is the position immediately following the value. This is the primitive for reading framed messages. Throws if byteIndex is not an integer within the bounds of the data.

Input Formats

The decoding functions accept:

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

A Uint8Array created with subarray is honored, so a value can be decoded out of the middle of a larger buffer without copying it first.

Errors

Every error is an isotropic-error carrying a name, a message, and a details object describing the offending input.

| 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 Kim sequence | | SyntaxError | Invalid negative Kim encoding | | SyntaxError | Invalid Kim character encoding | | SyntaxError | Unexpected data after Kim 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 |

SyntaxError always means the bytes are not valid Kim data. RangeError means the bytes are valid but the value cannot be represented as requested.

Examples

Encoding Numbers and BigInts

// Small positive numbers use minimal bytes
_kimEncoding.encode(127); // 1 byte
_kimEncoding.encode(128); // 2 bytes

// Negative numbers are supported
_kimEncoding.encode(-42); // 2 bytes

// BigInts for values outside safe integer range
_kimEncoding.encode(2n ** 60n); // BigInt encoding

Encoding Strings

// ASCII characters use 1 byte each
_kimEncoding.encodeString('Hello');

// Unicode characters use 2-3 bytes
_kimEncoding.encodeString('你好'); // Chinese
_kimEncoding.encodeString('مرحبا'); // Arabic
_kimEncoding.encodeString('🚀🌟'); // Emoji

// Complex Unicode is handled correctly
_kimEncoding.encodeString('café'); // Combined characters
_kimEncoding.encodeString('👨‍👩‍👧‍👦'); // Multi-codepoint emoji

Working with Iterables

const data = [1, 100, 1000, 10000],
    encoded = _kimEncoding.encodeIterable(data),

    decoded = _kimEncoding.decodeNumberArray(encoded),

    // BigInts and numbers may be mixed freely
    mixed = [123n, 456, 789n],
    encodedMixed = _kimEncoding.encodeIterable(mixed),

    decodedMixed = _kimEncoding.decodeBigIntArray(encodedMixed);

Length Prefixed Framing

Kim is self-delimiting for individual integers but not for strings, so a string is normally written as a byte length followed by its characters. encodedByteLength sizes the prefix and decodeNumberAt walks the result.

const writeMessage = strings => {
        const parts = [];

        for (const value of strings) {
            parts.push(_kimEncoding.encodeNumber(_kimEncoding.encodedByteLength(value)), _kimEncoding.encodeString(value));
        }

        const message = new Uint8Array(parts.reduce((byteLength, part) => byteLength + part.length, 0));

        let byteIndex = 0;

        for (const part of parts) {
            message.set(part, byteIndex);
            byteIndex += part.length;
        }

        return message;
    },
    readMessage = message => {
        const strings = [];

        let byteIndex = 0;

        while (byteIndex < message.length) {
            const header = _kimEncoding.decodeNumberAt(message, byteIndex);

            strings.push(_kimEncoding.decodeString(message.subarray(header.byteIndex, header.byteIndex + header.value)));
            byteIndex = header.byteIndex + header.value;
        }

        return strings;
    };

Error Handling

try {
    // Non-integer numbers throw
    _kimEncoding.encodeNumber(3.14);
} catch (error) {
    console.error(error.name, error.message); // TypeError Number value must be an integer
}

try {
    // Values outside safe range throw when decoding to number
    _kimEncoding.decodeNumber(_kimEncoding.encodeBigInt(2n ** 60n));
} catch (error) {
    console.error(error.name, error.message); // RangeError Value is outside safe integer range
}

How Kim Encoding Works

Kim encoding uses a variable-length scheme where:

• Each byte contributes 7 bits of data
• The high bit of each byte indicates continuation:
  • 1 = more bytes follow
  • 0 = this is the last byte
• Values are encoded most significant group first
• Negative numbers are prefixed with a 0x80 byte representing the minus sign
• Strings are encoded one Unicode code point at a time, each code point encoded as an integer

Because a code point never exceeds U+10FFFF, a character occupies at most three bytes. Integers have no such limit; encodeBigInt will encode a value of any size.

Validation and Canonical Form

The decoders accept only canonical encodings, so a given value has exactly one valid byte sequence. Specifically:

• A leading 0x80 marks a negative number and must not be followed by 0x80 or by 0x00, per the specification. Both would be aliases for values that are already representable another way.
• Within a string, no character may begin with 0x80. That byte contributes seven zero bits, so it could only ever produce an overlong alias of a shorter encoding.
• Within a string, no character may occupy more than three bytes, and no character may exceed U+10FFFF.
• A sequence whose final byte still has the continuation bit set is truncated and is rejected rather than silently completed.

Unpaired surrogates are permitted. JavaScript strings are sequences of UTF-16 code units and may legitimately contain them, so decodeString(encodeString(value)) returns value for every possible JavaScript string.

Migrating from 1.x

The following behaviors changed. All of them replace a silent or misleading result with an explicit error.

• decodeBigInt and decodeNumber now throw Unexpected data after Kim value when the buffer holds more than one value. Previously the first value was returned and the rest were discarded. Use decodeBigIntAt / decodeNumberAt to read one value from a larger buffer, or the array and iterable functions to read them all.
• decodeBigInt and decodeNumber now throw Incomplete Kim sequence for empty input rather than returning 0. Zero encodes as a single 0x00 byte; an empty buffer is not an encoding of anything. The array, iterable, and string decoders still accept empty input and return empty results.
• decodeString now rejects characters beginning with 0x80, characters longer than three bytes, and code points above U+10FFFF. These previously produced a native RangeError from String.fromCodePoint, or in some cases a negative code point.
• encodeString, encodeBigInt, and encodeNumber now validate their argument type. In particular encodeString given a non-string previously returned an empty Uint8Array.
• Invalid negative Kim encoding and Incomplete Kim sequence errors now carry the name SyntaxError. Previously their name was undefined.
• Passing a DataView or other non-Uint8Array view to a decoder now reads the underlying bytes. Previously a DataView silently decoded as 0.
• decodeString no longer overflows the call stack on large inputs.

Attribution

Kim encoding was invented by Douglas Crockford. This is an independent implementation of his specification.

License

This implementation is licensed under the 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

• Original Kim Specification