Standard graphs

Every graph of GR_standardGraphs (IDs 1 to 90, registry/graphs.rs) is implemented. This page records what each one decides; the engine that runs them is in compression graphs. Graph IDs below are the registry’s numbering. Implementations live in compressor::core::graphs (one file per family) and stay byte-identical with the reference: tests/standard_graphs.rs runs every graph the C library accepts over serial, struct, numeric and string inputs at several levels and format versions and compares the frames.

Kinds

classDiagram
    class GraphDef {
        name
        kind GraphKind
        inputs type masks
        last_variable
        custom_graphs
        custom_nodes
        params
    }
    class GraphKind {
        <<enum>>
        Store
        Static
        Selector
        Function
        Segmenter
    }
    class GraphFn {
        <<trait>>
        run(GraphCx, edges)
    }
    class SelectFn {
        <<trait>>
        select(SelectorCx, stream, successors) GraphId
    }
    class SegmentFn {
        <<trait>>
        segment(SegmenterCx)
        serial_chunk(params, graphs)
    }
    GraphDef --> GraphKind
    GraphKind ..> GraphFn : Function
    GraphKind ..> SelectFn : Selector
    GraphKind ..> SegmentFn : Segmenter

• Static: one node followed by fixed successors (node_graph!).
• Selector: looks at one stream and returns the successor graph.
• Function: runs nodes and assigns every output edge a destination.
• Segmenter: cuts the whole input into chunks, each run through a successor.

Without a Cargo feature a graph that needs its codec aliases UNPORTED_FUNCTION / UNPORTED_SELECTOR (ExecError::Unported), which only exists for feature-off builds and tests: field_lz and its private graphs need field-lz + entropy, lz needs lz + entropy, partition_bitpack needs partition, merge_sorted needs merge-sorted, and the five entropy graphs need entropy.

Routing and stores

flowchart TD
    CG["compress_generic 13"] -->|each input| C1["compress1 34"]
    C1 -->|serial| SC["serial_compress 35"] --> Z["zstd 9"]
    C1 -->|struct| STC["struct_compress 36"] --> FLZ["field_lz 12"]
    C1 -->|numeric| NC["numeric_compress 37"] --> SN["select_numeric 16"]
    C1 -->|string| SSC["string_compress 38"] --> SSP["string_separate_compress 39"]
    SN -->|"level below 7"| STC
    SN -->|"level 7 or more"| TN1["transformer_numeric1 90"]
    SSP -->|"node 26 splits"| SSP2["content to 35, lengths to 37"]
    Z --> ST["serial_store 1"]

Segmenters

Entropy and packing graphs

partition_bitpack (23)

flowchart TD
    A[numeric input] --> W{width 2 or 4?}
    W -- no --> E[error]
    W -- yes --> N{"fewer than 10 elements?"}
    N -- yes --> S[store]
    N -- no --> H["bucket histogram: 16-value buckets below 2^16, then one per power of two; sampled by 3, widened when not optimal"]
    H --> P["greedy split to 16 then 32 partitions by gain; iterative improvement from 10000 elements; optimal mode (param 0 = 1) is a DP"]
    P --> G{"saves under 1 percent?"}
    G -- yes --> T{"trivial partitioning narrows the numbers?"}
    T -- yes --> BP[bitpack 10]
    T -- no --> S
    G -- no --> PN["partition node 48: start 0, sizes in copy parameter 121"]
    PN --> O0["bucket ids to bitpack 10"]
    PN --> O1["offsets to store"]

Cost model: 24 + count * ceil(log2(bucket size)) bits per partition plus ceil(log2(partitions)) bits per element; at most 256 partitions.

compress_small_lengths (69)

The overflow-lengths stream of the lz graph: mostly tiny values, a few large ones.

flowchart TD
    I[numeric lengths] --> A{"fewer than 50 elements?"}
    A -- yes --> ST[store]
    A -- no --> B{"width 1?"}
    B -- yes --> HU[huffman 4]
    B -- no --> C{"sentinel_byte node supported?"}
    C -- no --> CG[compress_generic]
    C -- yes --> SB["sentinel_byte 50: small values below 255, large values"]
    SB --> HU2["small stream to huffman 4"]
    SB --> L{"large stream"}
    L -- "under 100 elements" --> ST2[store]
    L -- "width 2 and partition supported" --> PB[partition_bitpack 23]
    L -- "width 4" --> Q["quantize_lengths 44: codes to fse 3, extra bits to store"]
    L -- otherwise --> CG2[compress_generic]

Structure graphs

Numeric static pipelines

Static node-plus-successor graphs the Transformer reaches; see transformer.

LZ graphs

lz4 (22) is a static node graph; field_lz (12), field_lz_literals (45), the channel selector (46) and lz (28) are covered in LZ.

Known gaps

• ExecError::Unported is no longer reachable with every codec feature on; with a feature off a graph that needs it fails like any disabled codec.
• Custom (user) graphs are expressed through graph::Selector, FunctionGraph and Segmenter; a failing user graph is reported as GraphError.