Binary Trie Flags

Relevant source files

The following files were used as context for generating this wiki page:

• src/internal/bin-trie-flags.ts
• scripts/trie/encode-trie.ts
• src/decode.ts
• scripts/trie/README.md
• scripts/write-decode-map.ts
• scripts/trie/compact-run.spec.ts

Binary Trie Flags represent a compact bitwise encoding scheme used within the entities library to efficiently store and traverse HTML/XML named character references. By mapping a trie structure into a Uint16Array, the project reduces memory consumption from approximately 8.5MB to 250KB while maintaining high performance during decoding. Sources: scripts/trie/README.md:6-14

The core of this system is a 16-bit header word for every node in the trie. This header uses specific bit ranges to store value lengths, branch metadata, and flags for optimizations like compact runs and implicit semicolon handling. Sources: src/internal/bin-trie-flags.ts:3-13, scripts/trie/README.md:36-41

Bit Layout and Masks

The bit layout of the 16-bit header word is partitioned into four primary segments. These segments determine how the decoder interprets the current node and any subsequent data in the Uint16Array.

Bit Range	Mask Name	Description
15..14	VALUE_LENGTH	Encodes the length of the result value using a "+1" scheme (0 = no value).
13	FLAG13	Dual-use flag: Semicolon-required (if value exists) OR Compact Run flag (if no value).
12..7	BRANCH_LENGTH	Stores the branch count, jump table span, or run length.
6..0	JUMP_TABLE	Stores the jump table offset, single-branch char, or first run character.

Sources: src/internal/bin-trie-flags.ts:5-13, scripts/trie/README.md:43-48

Value Length Encoding

The VALUE_LENGTH field (bits 15-14) uses a 2-bit value to determine where the entity's replacement character(s) are stored. HTML named character references in this project are at most two code points. Sources: scripts/trie/README.md:50-58

• 0: No value is present on this node.
• 1: Single code unit value inlined directly in bits 13..0 of the header.
• 2: One code unit value stored in the next array element.
• 3: Two code unit values stored in the next two array elements.

Feature Optimizations

Semicolon Handling

HTML defines "strict" entities requiring a semicolon and "legacy" entities where it is optional. The trie handles this via FLAG13. If valueLength > 0 and FLAG13 is set, the entity is strict and the decoder implicitly handles the semicolon without storing an explicit ';' branch. Sources: scripts/trie/README.md:66-73, src/decode.ts:506-512

Compact Runs

When a node has no value (valueLength == 0) and leads into a linear chain of at least three single-child nodes, the encoder collapses the path into a "compact run." Sources: scripts/trie/README.md:78-82

• The Run Flag (FLAG13) is set.
• Run Length (bits 12..7) stores the number of characters (1–63).
• First Character is in bits 6..0.
• Subsequent characters are packed two per uint16 word (low/high byte) following the header. Sources: scripts/trie/README.md:84-88, scripts/trie/encode-trie.ts:79-106

Branching Logic

Nodes with branches follow the header (and any packed run data). The trie supports three branch types: Sources: scripts/trie/README.md:95-97

1. Single Branch: If one child exists and isn't cached, BRANCH_LENGTH is 0 and the char code is in JUMP_TABLE bits. Sources: scripts/trie/README.md:100-103
2. Jump Table: Used for dense key ranges. JUMP_TABLE stores the minimum key offset, and BRANCH_LENGTH stores the span. A table of destination indices follows. Sources: scripts/trie/README.md:104-106, src/decode.ts:635-645
3. Dictionary (Sparse): For far-apart keys, keys are packed two-per-word, followed by a destination array of raw indices. Sources: scripts/trie/README.md:107-111, src/decode.ts:648-675

Data Flow Architecture

The following diagram illustrates how the EntityDecoder utilizes the Binary Trie Flags to navigate the encoded array during a named entity lookup.

Implementation Details

Node Traversal

The determineBranch function is the primary mechanism for navigating the trie. It uses the masks defined in bin-trie-flags.ts to decode the branch type and calculate the next nodeIndex.

// src/decode.ts:630-634
export function determineBranch(
    decodeTree: Uint16Array,
    current: number,
    nodeIndex: number,
    char: number,
): number {
    const branchCount = (current & BinTrieFlags.BRANCH_LENGTH) >> 7;
    const jumpOffset = current & BinTrieFlags.JUMP_TABLE;
    // ... logic for Single, Jump Table, and Dictionary branches
}

Sources: src/decode.ts:630-634, src/internal/bin-trie-flags.ts:5-13

Compact Run Decoding

During a compact run, the decoder consumes characters from the input string and compares them against the packed characters in the trie without performing new branch lookups for every character.

// src/decode.ts:488-500
const charIndexInPacked = this.runConsumed - 1;
const packedWord = decodeTree[
    this.treeIndex + 1 + (charIndexInPacked >> 1)
];
const expectedChar =
    ((charIndexInPacked & 1) === 0
        ? packedWord
        : packedWord >> 8) & 0xff;

if (input.charCodeAt(offset) !== expectedChar) {
    return this.emitLegacyOrReject(input.charCodeAt(offset), 0);
}

Sources: src/decode.ts:488-500, scripts/trie/compact-run.spec.ts:28-36

Binary Trie Flags provide a highly optimized, bit-packed representation of entity mapping data. By utilizing specific bit-fields within a Uint16Array for value metadata, structural optimizations like compact runs, and diverse branching strategies, the system achieves significant memory savings and high-speed decoding necessary for processing large volumes of HTML/XML entities.