golomb_rice_stage.h File Reference

Chunk-local Golomb-Rice entropy coder — lossless byte-stream compressor. More...

#include "stage/stage.h"
#include "fzm_format.h"
#include "backend/types.h"
#include "fused/common/data_type_of.h"
#include <cstdint>
#include <cstring>
#include <memory>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>

Go to the source code of this file.

Namespaces
namespace	fz

Detailed Description

Chunk-local Golomb-Rice entropy coder — lossless byte-stream compressor.

A genuine entropy coder (variable-length codes sized to each value's magnitude) whose parameter is computed PER 16 KB CHUNK rather than from a global histogram. That is what makes it eligible for the chunk-cooperative fusion path in principle (see the Fusion readiness note below) — the same property that excludes ANS/Huffman (global codebook) from that path today.

Rice coding is the classical choice for Laplacian-distributed values, which is exactly the shape of a predictor's residuals (Lorenzo / AdaptiveLorenzo output): most values near zero, a long thin tail. Encode maps a signed value to unsigned via zigzag, splits it into quotient/remainder by a per-chunk parameter k (q = u >> k, r = u & ((1<<k)-1)), and emits q one bits, a zero stop bit, then k raw bits of r — so small values cost close to k+1 bits and the code gets exponentially more expensive as magnitude grows past 2^k.

k selection is exact, not estimated. For each candidate k in [0, kMaxCandidate()], the encoder computes the EXACT total bit cost the pack step would emit (including the escape below) via a block-wide reduction, and picks the argmin — the same "encoded-size oracle, not a heuristic" discipline used elsewhere in this codebase (see include/stage/fusion.h's EncodingOracleDecl).

Escape for outliers. A per-element unary run is capped at kEscapeQ (24) ones: hitting the cap with no stop bit is unambiguous ("escape") and is followed by the full zigzag value as bitWidth<T>() raw bits instead of an unbounded unary run. This bounds worst-case per-element cost to kEscapeQ + bitWidth<T>() bits regardless of how large one value is, so a single outlier can never blow up a chunk's packed size — the raw-storage fallback below only ever triggers on genuinely incompressible chunks, never on a rare large value.

Output stream layout (identical container convention to RZEStage/RREStage):

[uint32_t: original byte count]
[uint32_t: num_chunks]
[uint32_t × n_chunks: per-chunk compressed sizes (high bit → stored raw)]
[per-chunk data: [uint32_t: k]
                  [uint32_t × kIntervalsPerChunk: restart-interval byte offsets]
                  [packed bits, kIntervalsPerChunk independently byte-aligned
                   segments...] , or raw bytes if flagged]

Decode parallelism via restart intervals. Each chunk's k-selection still uses the whole chunk (no ratio cost), but the packed payload is split into kIntervalsPerChunk segments — one per encode-side warp — each independently rounded up to a byte boundary. Decode launches one WARP per chunk with one lane per restart interval, so kIntervalsPerChunk Rice decode streams run in parallel per chunk instead of one sequential stream for the whole 16 KB chunk. See golomb_rice_stage.cu for the mechanism.

Serialized header (5 bytes): [0..3] chunk_size (uint32_t LE), [4] element DataType (INT16 or INT32) — needed so GolombRice_fromHeader can reconstruct the correct GolombRiceStage<T> template instantiation when replaying an archive whose T is a runtime (not caller-known) fact.

Fusion (compress-only, SHIPPED 2026-09-06)

getFusionSpec()/getFusedOp() declare FusionAccess::SegmentCodec / FusionStrategy::ChunkCooperative (T=int32_t, chunk_size=16384 only — the chunk_fusion.cuh harness's shared buffers are a fixed uint32_t[4096] shape). The device op (GolombRiceCoder in modules/fused/chunk_fusion/chunk_fusion.cuh) reproduces this stage's own golombRiceEncodeKernel byte-for-byte (same k selection, same kIntervalsPerChunk restart-interval offsets, same header layout), so the ordinary unfused inverse below decodes a fused-produced archive unchanged — this coder never gets its own inverse, matching RRE/RARE/RAZE/CLOG/HCLOG (only RZE among the chunk-cooperative coders has a fused inverse today). Proven chain: Quantizer(inplace,zigzag,NOA) -> Difference(plain, same- type int32) -> GolombRice (examples/presets/diffplain_golomb_rice.toml) — Difference must be PLAIN (T==TOut, no fused encode step): this coder zigzags its residuals internally, so an upstream transform that also zigzagged would double-encode (caught by the byte-identity test during development — the fused archive came out smaller than staged, the fingerprint of doubling an always-nonnegative value's magnitude). Byte-identity AND round-trip verified via FusionPlanner.DiffPlainGolombRiceEndToEndFusedMatchesStaged (tests/pipeline/test_fusion_planner.cpp), compute-sanitizer memcheck/racecheck clean. Measured compress win (single fused kernel vs. 3 staged DRAM round-trips), same DAG-throughput metric both times: CLDHGH (25 MB) 131.8 → 142.5 GB/s (+8%); NYX/baryon_density (512 MB) 180.3 → 280.7 GB/s (+56%) — the win grows with field size, as expected for a DRAM-round-trip-elimination fusion (small fields have little round-trip cost to delete). Compressed size matched exactly (byte-identical) on both.

DECODE fusion is still not attempted — see memory/chunk_local_entropy_coder_design.md for why (the decode side is necessarily sequential per chunk, which the existing chunk-cooperative INVERSE runner has not needed to support yet; the standalone decode's own throughput investigation is also there, including why several plausible fixes did not pan out).

Template Parameters

T	Signed integer element type: int16_t or int32_t.