zxc_huffman.c File Reference

Canonical, length-limited Huffman codec in the PivCo layout (GLO entropy sections, wire values enc 2/3). More...

#include "../../include/zxc_error.h"
#include "zxc_internal.h"
#include "zxc_pivco_tables.h"

Go to the source code of this file.

Macros
#define	ZXC_VARIANT_PRIMARY   1
#define	ITEM(k, i)   items[(size_t)(k) * (size_t)max_per_level + (size_t)(i)]
#define	ZXC_NUDGE_DP_IDX(k, s)   ((size_t)(k) * (size_t)(m + 1) + (size_t)(s))
#define	ZXC_PIVCO_MERGE_STEP(w, pc)
	Advances the merge cursors past one fixed-width step.

Typedefs
typedef zxc_huf_pm_item_t	pm_item_t
typedef zxc_huf_pm_leaf_t	pm_leaf_t
typedef zxc_huf_pm_frame_t	frame_t

Functions
static void	pm_leaves_sort (pm_leaf_t *leaves, const int n)
	Sort pm_leaf_t array by ascending weight, ties broken by ascending symbol.
int	zxc_huf_build_code_lengths (const uint32_t *freq, uint8_t *code_len, void *scratch, const int max_code_len)
	Build length-limited canonical Huffman code lengths.
static int	zxc_huf_nudge_classes (const uint8_t *code_len, uint32_t *blc)
	Per-length class counts of a code-length vector.
static void	zxc_huf_nudge_pf_canonical (const uint8_t *code_len, const uint32_t *freq, const uint32_t *blc, uint64_t *pf)
	Frequency prefix sums over the leaves in canonical (length, symbol) order: pf[i] = mass of the first i leaves of the code space.
static void	zxc_huf_nudge_eval (const uint32_t *blc, const uint64_t *pf, zxc_huf_nudge_cost_t *out)
	Modeled (bits, level-touches) of one class-count histogram.
static uint64_t	zxc_huf_nudge_j (const zxc_huf_nudge_cost_t *c)
	Candidate cost J = 256*bits + lambda*touches (Q8 bit units).
static uint32_t	zxc_huf_nudge_clamp (const uint32_t want, const uint32_t s, const uint32_t n_rem, const int l, const int cap)
	Clamp a desired class count into the feasible set at one walk level.
static void	zxc_huf_nudge_complete (uint32_t *blc, const int l, uint32_t s, uint32_t n_rem, const uint32_t *blc0, const int cap)
	Baseline-following completion: fill levels l+1..cap with the baseline class counts clamped into feasibility.
static void	zxc_huf_nudge_walk (const uint32_t *blc0, const uint64_t *pf_rank, const int n, const int cap, uint32_t *out_blc)
	Greedy shallow-to-deep walk over the slot ledger.
static uint64_t	zxc_huf_nudge_dp_run_j (const int lu, const int lc, const int g_log2, const uint32_t s, const uint32_t c, const uint64_t *pfg, const uint32_t k)
	Exact rank-weighted J of one leaf run placed at coarse level lc.
static int	zxc_huf_nudge_dp_solve (zxc_huf_nudge_ws_t *ws, const uint64_t *pfg, const int m, const int cap_c, const int lu, const int g_log2, uint32_t *out_cblc)
	Slot-ledger dynamic program: optimal class counts for the model.
static void	zxc_huf_nudge_assign (const uint32_t *blc, const int16_t *sym_order, uint8_t *cand_len)
	Assign a class-count multiset to symbols: frequency rank r takes the r-th shortest slot (rearrangement-optimal, deterministic).
void	zxc_huf_nudge_cost (const uint8_t *code_len, const uint32_t *freq, uint64_t *bits, uint64_t *touches)
	Modeled (bits, level-touches) decode cost of one code-length vector.
int	zxc_huf_nudge_code_lengths (const uint32_t *freq, uint8_t *code_len, void *scratch, const size_t scratch_cap, const int max_code_len)
	Optionally reshape freshly built code lengths for faster PivCo decode.
void	zxc_huf_pack_lengths (const uint8_t *code_len, uint8_t *out)
	Pack per-symbol code lengths into the 128-byte (4-bit nibble) header.
int	zxc_huf_unpack_lengths (const uint8_t *in, uint8_t *code_len)
	Unpack and structurally validate a 128-byte packed lengths header.
static int	zxc_pivco_popcnt32 (const uint32_t v)
static int	zxc_pivco_popcnt64 (const uint64_t v)
static int	zxc_pivco_leaves (const zxc_pivco_tree_t *t, const int d)
	Leaves at depth d.
static int	zxc_pivco_flat_leaves (const zxc_pivco_tree_t *t, const int g, const int d, const int D)
	syms index of flat root g's first leaf: its prefix, then D zero bits.
static void	zxc_pivco_bitrev_permute (uint8_t *s, const int D)
	Reorders s[0, 2^D) by bit-reversed index (an involution).
static int	zxc_pivco_tree_build (const uint8_t *code_len, zxc_pivco_tree_t *t)
	Build the canonical code tree from per-symbol lengths.
static void	zxc_pivco_counts (const zxc_pivco_tree_t *t, const uint32_t *freq, uint32_t *count)
	Per-node symbol counts from the histogram (encoder / size estimate).
static void	zxc_pivco_codes (const zxc_pivco_tree_t *t, uint32_t *codes)
	Code of every leaf: the prefix of its slot (see zxc_pivco_tree_t).
static size_t	zxc_pivco_run_bytes (const uint32_t count, const uint8_t flat_d)
	Byte size of one PivCo node's on-wire bit run.
static size_t	zxc_pivco_layout (const zxc_pivco_tree_t *t, const uint32_t *count, uint32_t *cur)
	Payload size, and each run's first bit as a cursor if cur is set.
size_t	zxc_huf_calc_size (const uint32_t *freq, const uint8_t *code_len, const int with_header)
	Exact encoded size (bytes) of a PivCo section for this histogram and code lengths; includes the 128-byte lengths header when with_header.
size_t	zxc_huf_calc_size_dict (const uint32_t *freq, const uint8_t *code_len, const zxc_pivco_tree_t *tree)
	Sizing core shared with zxc_huf_calc_size: exact payload size of one PivCo section for a prebuilt tree (tree-at-attach dict sections call it directly; they carry no inline lengths header).
static int	zxc_pivco_encode_core (const uint8_t *literals, const size_t n_literals, const uint32_t *freq, const uint8_t *code_len, const zxc_pivco_tree_t *t, const uint32_t *codes, uint8_t *dst, const size_t dst_cap, const int with_header)
	Shared PivCo section encoder body.
int	zxc_huf_encode_section (const uint8_t *literals, const size_t n_literals, const uint32_t *freq, const uint8_t *code_len, uint8_t *dst, const size_t dst_cap)
	Encode a literal/token section (PivCo layout, inline lengths header).
int	zxc_huf_encode_section_dict (const uint8_t *literals, const size_t n_literals, const uint32_t *freq, const uint8_t *code_len, const zxc_pivco_tree_t *tree, const uint32_t *codes, uint8_t *dst, const size_t dst_cap)
	Encode a literal section against a shared dictionary table.
int	zxc_huf_dict_tree_build (const uint8_t *packed_lengths, zxc_pivco_tree_t *tree, uint32_t *codes, uint8_t *code_len)
	Prebuild a dict table's decode/encode state (tree-at-attach).
static void	zxc_pivco_merge (uint8_t *out, const uint8_t *src, const size_t nl, const size_t nr, const uint8_t *bits)
	Merge two adjacent child sequences under control bits.
static void	zxc_pivco_unpack_flat (uint8_t *out, const size_t n, const int D, const uint8_t *bits, const uint8_t *c2s)
	Decode a flat subtree's packed D-bit code run into symbols.
static void	zxc_pivco_emit_leaf_pair (uint8_t *out, const size_t n, const uint8_t sym0, const uint8_t sym1, const uint8_t *bits)
	Direct emission for a node whose two children are BOTH leaves.
static int	zxc_pivco_decode_core (const uint8_t *payload, const size_t payload_size, uint8_t *dst, const size_t n, const zxc_pivco_tree_t *t, uint8_t *scratch)
	Shared PivCo section decoder body (code lengths already unpacked).
int	zxc_huf_decode_section (const uint8_t *payload, const size_t payload_size, uint8_t *dst, const size_t n, uint8_t *scratch)
	Decode a literal/token section (PivCo layout, inline lengths header).
int	zxc_huf_decode_section_dict (const uint8_t *payload, const size_t payload_size, uint8_t *dst, const size_t n, const zxc_pivco_tree_t *tree, uint8_t *scratch)
	Decode a shared-dictionary literal section (no inline header).

Detailed Description

Canonical, length-limited Huffman codec in the PivCo layout (GLO entropy sections, wire values enc 2/3).

Covers the whole entropy pipeline for GLO literal sections (level >= 6) and level-7 token sections:

• boundary package-merge -> optimal length-limited code lengths (<= ZXC_HUF_MAX_CODE_LEN_DENSITY at level 6, <= _ULTRA at level 7);
• 128-byte packed lengths header (4-bit nibbles) pack/unpack + validation;
• exact section sizing for the encoder's space-speed selection (zxc_huf_calc_size returns SIZE_MAX for unencodable candidates);
• PivCo section encode/decode: the code is classical canonical Huffman, only the bit LAYOUT differs – bits are grouped by tree level into per-node branch runs (see the section banner below and FORMAT.md section 5.2.1), so decoding runs data-parallel list merges (NEON TBL / SSSE3 pshufb / AVX-512-VBMI2 vpexpandb kernels, plus flat subtree unpacking and a leaf-pair fast path) instead of a serial bit chain.

Public declarations live in zxc_internal.h; the shuffle-index tables live in zxc_pivco_tables.c (single TU, shared by all variants); the rest is private to this translation unit.

Definition in file zxc_huffman.c.

Macro Definition Documentation

ZXC_PIVCO_MERGE_STEP

#define ZXC_PIVCO_MERGE_STEP	(		w,
			pc
	)

Value:

    do {                            \
        rp += (size_t)(pc);         \
        lp += (size_t)((w) - (pc)); \
        i += (w);                   \
    } while (0)

Advances the merge cursors past one fixed-width step.

Every fixed-width arm closes the same way: the step took pc bytes from the right child and the rest from the left. Operates on the enclosing loop's lp, rp and i, and expands pc twice, so pass a named value.

Definition at line 1360 of file zxc_huffman.c.

ZXC_VARIANT_PRIMARY

#define ZXC_VARIANT_PRIMARY   1

Definition at line 67 of file zxc_huffman.c.

Typedef Documentation

frame_t

typedef zxc_huf_pm_frame_t frame_t

Definition at line 89 of file zxc_huffman.c.

pm_item_t

typedef zxc_huf_pm_item_t pm_item_t

Definition at line 85 of file zxc_huffman.c.

pm_leaf_t

typedef zxc_huf_pm_leaf_t pm_leaf_t

Definition at line 87 of file zxc_huffman.c.

Function Documentation

pm_leaves_sort()

static void pm_leaves_sort ( pm_leaf_t *  leaves, const int  n  )

static

Sort pm_leaf_t array by ascending weight, ties broken by ascending symbol.

Bucket sort on floor(log2(weight)) (32 buckets), with insertion sort inside each bucket. Replaces a libc qsort call: the comparator's indirect call dominated, and frequency distributions cluster naturally across ~10-14 magnitude buckets, so intra-bucket lists stay short and insertion sort is branch-friendly. Deterministic tie-break on sym is applied inside the insertion sort.

Precondition: all weights are > 0 (zero-frequency symbols are filtered by the caller before this runs).

Parameters

[in,out]	leaves	Leaf array, sorted in place (ascending weight, then ascending sym on ties).
[in]	n	Number of leaves; n < 2 is effectively a no-op.

Definition at line 108 of file zxc_huffman.c.

References zxc_huf_pm_leaf_t::sym, zxc_huf_pm_leaf_t::w, ZXC_HUF_NUM_SYMBOLS, and zxc_log2_u32().

Referenced by zxc_huf_build_code_lengths(), and zxc_huf_nudge_code_lengths().

zxc_huf_build_code_lengths()

int zxc_huf_build_code_lengths	(	const uint32_t *	freq,
		uint8_t *	code_len,
		void *	scratch,
		const int	max_code_len
	)

Build length-limited canonical Huffman code lengths.

Build length-limited canonical Huffman code lengths from a frequency table.

Runs the boundary package-merge algorithm capped at ZXC_HUF_MAX_CODE_LEN_ULTRA. Symbols with freq[i] == 0 get code_len[i] == 0; every other symbol receives a length in [1, ZXC_HUF_MAX_CODE_LEN_ULTRA]. The single-present-symbol case is handled as a degenerate code of length 1.

Definition at line 163 of file zxc_huffman.c.

References zxc_huf_pm_frame_t::idx, zxc_huf_pm_item_t::left, zxc_huf_pm_frame_t::lvl, pm_leaves_sort(), zxc_huf_pm_item_t::right, zxc_huf_pm_item_t::sym, zxc_huf_pm_leaf_t::sym, zxc_huf_pm_leaf_t::w, ZXC_CALLOC, ZXC_ERROR_CORRUPT_DATA, ZXC_ERROR_MEMORY, ZXC_FREE, ZXC_HUF_MAX_CODE_LEN_ULTRA, ZXC_HUF_NUM_SYMBOLS, ZXC_HUF_PM_LEVEL_BOUND, ZXC_MALLOC, and ZXC_OK.

Referenced by zxc_huf_nudge_code_lengths().

zxc_huf_calc_size()

size_t zxc_huf_calc_size	(	const uint32_t *	freq,
		const uint8_t *	code_len,
		const int	with_header
	)

Exact encoded size (bytes) of a PivCo section for this histogram and code lengths; includes the 128-byte lengths header when with_header.

Exact encoded size (bytes) of a PivCo section for this histogram and code lengths; includes the 128-byte lengths header when with_header.

Definition at line 1201 of file zxc_huffman.c.

References zxc_huf_calc_size_dict(), ZXC_HUF_TABLE_SIZE, and zxc_pivco_tree_build().

zxc_huf_calc_size_dict()

size_t zxc_huf_calc_size_dict	(	const uint32_t *	freq,
		const uint8_t *	code_len,
		const zxc_pivco_tree_t *	tree
	)

Sizing core shared with zxc_huf_calc_size: exact payload size of one PivCo section for a prebuilt tree (tree-at-attach dict sections call it directly; they carry no inline lengths header).

zxc_huf_calc_size for a dict section: prebuilt tree, no header.

Definition at line 1215 of file zxc_huffman.c.

References ZXC_HUF_NUM_SYMBOLS, zxc_pivco_counts(), zxc_pivco_layout(), and ZXC_PIVCO_NODE_SLOTS.

Referenced by zxc_huf_calc_size().

zxc_huf_decode_section()

int zxc_huf_decode_section	(	const uint8_t *	payload,
		const size_t	payload_size,
		uint8_t *	dst,
		const size_t	n,
		uint8_t *	scratch
	)

Decode a literal/token section (PivCo layout, inline lengths header).

Decode a PivCo literal section into dst (exactly n bytes).

Unpacks and validates the 128-byte code-length header, then runs the bottom-up merge decoder.

Parameters

[in]	payload	Section bytes (header + node runs).
[in]	payload_size	Section size in bytes.
[out]	dst	Receives the n decoded symbols; needs ZXC_PAD_SIZE bytes of write slack past n.
[in]	n	Expected symbol count.
[in]	scratch	Level ping-pong buffer with at least n + ZXC_PIVCO_SCRATCH_PAD bytes.

Returns

ZXC_OK or ZXC_ERROR_CORRUPT_DATA.

Definition at line 2281 of file zxc_huffman.c.

References ZXC_ERROR_CORRUPT_DATA, ZXC_HUF_NUM_SYMBOLS, ZXC_HUF_TABLE_SIZE, zxc_huf_unpack_lengths(), ZXC_OK, zxc_pivco_decode_core(), and zxc_pivco_tree_build().

zxc_huf_decode_section_dict()

int zxc_huf_decode_section_dict	(	const uint8_t *	payload,
		const size_t	payload_size,
		uint8_t *	dst,
		const size_t	n,
		const zxc_pivco_tree_t *	tree,
		uint8_t *	scratch
	)

Decode a shared-dictionary literal section (no inline header).

Decode a PivCo dict section against a prebuilt dict tree.

Same as zxc_huf_decode_section, but against the dictionary's PivCo tree, prebuilt ONCE at attach time by zxc_huf_dict_tree_build (wire value enc_lit = 3): no per-block unpack or tree rebuild.

Definition at line 2300 of file zxc_huffman.c.

References zxc_pivco_decode_core().

zxc_huf_dict_tree_build()

int zxc_huf_dict_tree_build	(	const uint8_t *	packed_lengths,
		zxc_pivco_tree_t *	tree,
		uint32_t *	codes,
		uint8_t *	code_len
	)

Prebuild a dict table's decode/encode state (tree-at-attach).

Unpack a dict table's packed lengths and prebuild its tree, codes and code lengths, once per frame.

Unpacks the packed lengths and builds the tree and codes once, for every block to reuse.

Definition at line 1343 of file zxc_huffman.c.

References ZXC_ERROR_CORRUPT_DATA, zxc_huf_unpack_lengths(), ZXC_OK, zxc_pivco_codes(), and zxc_pivco_tree_build().

Referenced by zxc_cctx_attach_dict_huf().

zxc_huf_encode_section()

int zxc_huf_encode_section	(	const uint8_t *	literals,
		const size_t	n_literals,
		const uint32_t *	freq,
		const uint8_t *	code_len,
		uint8_t *	dst,
		const size_t	dst_cap
	)

Encode a literal/token section (PivCo layout, inline lengths header).

Encode a PivCo literal section (128-byte lengths header + payload).

Emits the 128-byte packed code-length header followed by the per-node branch runs. The caller supplies the histogram and code lengths it already built for the selection step.

Parameters

[in]	literals	Symbols to encode (n_literals bytes).
[in]	n_literals	Symbol count (> 0).
[in]	freq	Symbol histogram of literals.
[in]	code_len	Per-symbol code lengths (every symbol with freq != 0 must have a code).
[out]	dst	Destination buffer.
[in]	dst_cap	Destination capacity in bytes.

Returns

Encoded size in bytes, or a negative ZXC_ERROR_* value (ZXC_ERROR_DST_TOO_SMALL, ZXC_ERROR_CORRUPT_DATA).

Definition at line 1307 of file zxc_huffman.c.

References ZXC_ERROR_CORRUPT_DATA, ZXC_HUF_NUM_SYMBOLS, zxc_pivco_codes(), zxc_pivco_encode_core(), and zxc_pivco_tree_build().

zxc_huf_encode_section_dict()

int zxc_huf_encode_section_dict	(	const uint8_t *	literals,
		const size_t	n_literals,
		const uint32_t *	freq,
		const uint8_t *	code_len,
		const zxc_pivco_tree_t *	tree,
		const uint32_t *	codes,
		uint8_t *	dst,
		const size_t	dst_cap
	)

Encode a literal section against a shared dictionary table.

Encode a PivCo section against a prebuilt dict tree/codes (no header).

Same payload as zxc_huf_encode_section with the 128-byte lengths header omitted: code_len / tree / codes come from the dictionary's shared literal table, prebuilt ONCE at attach by zxc_huf_dict_tree_build (wire value enc_lit = 3).

Definition at line 1325 of file zxc_huffman.c.

References zxc_pivco_encode_core().

zxc_huf_nudge_assign()

static void zxc_huf_nudge_assign ( const uint32_t *  blc, const int16_t *  sym_order, uint8_t *  cand_len  )

static

Assign a class-count multiset to symbols: frequency rank r takes the r-th shortest slot (rearrangement-optimal, deterministic).

Parameters

[in]	blc	Class counts to realize (sum = number of ranks).
[in]	sym_order	Symbols by descending frequency (rank 0 first).
[out]	cand_len	Resulting per-symbol code lengths, written in full.

Definition at line 770 of file zxc_huffman.c.

References ZXC_HUF_MAX_CODE_LEN_ULTRA, and ZXC_HUF_NUM_SYMBOLS.

Referenced by zxc_huf_nudge_code_lengths().

zxc_huf_nudge_clamp()

static uint32_t zxc_huf_nudge_clamp ( const uint32_t  want, const uint32_t  s, const uint32_t  n_rem, const int  l, const int  cap  )

static

Clamp a desired class count into the feasible set at one walk level.

A count c is feasible iff a Kraft-exact completion within cap still exists: either c == n_rem == s (a finishing level fills every slot), or, continuing with i = s - c internal nodes, i >= 1 and 2*i <= n_rem - c <= i << (cap - l). Under the walk invariant (s <= n_rem <= s << (cap - l)) the continuing window [max(0, 2s - n_rem), min(s-1, n_rem-1, (s*M - n_rem)/(M-1))] is nonempty whenever n_rem > s, and n_rem == s forces the finishing count (continuing would need both c >= s and c <= s-1).

Parameters

[in]	want	Desired class count at this level.
[in]	s	Open slots at level l.
[in]	n_rem	Symbols left to place (including this level's).
[in]	l	Current level.
[in]	cap	Code-length cap of the walk.

Returns

The nearest feasible count to want.

Definition at line 472 of file zxc_huffman.c.

Referenced by zxc_huf_nudge_complete(), and zxc_huf_nudge_walk().

zxc_huf_nudge_classes()

static int zxc_huf_nudge_classes ( const uint8_t *  code_len, uint32_t *  blc  )

static

Per-length class counts of a code-length vector.

Parameters

[in]	code_len	Per-symbol code lengths (0 = absent symbol).
[out]	blc	Class counts indexed by length, entries 0..ZXC_HUF_MAX_CODE_LEN_ULTRA (entry 0 stays 0).

Returns

Number of present symbols (nonzero lengths).

Definition at line 344 of file zxc_huffman.c.

References ZXC_HUF_MAX_CODE_LEN_ULTRA, and ZXC_HUF_NUM_SYMBOLS.

Referenced by zxc_huf_nudge_code_lengths(), and zxc_huf_nudge_cost().

zxc_huf_nudge_code_lengths()

int zxc_huf_nudge_code_lengths	(	const uint32_t *	freq,
		uint8_t *	code_len,
		void *	scratch,
		size_t	scratch_cap,
		int	max_code_len
	)

Optionally reshape freshly built code lengths for faster PivCo decode.

Explores a small set of Kraft-exact alternatives to code_len (a greedy slot-ledger walk toward power-of-two class counts, package-merge rebuilds at reduced depth caps, and the slot-ledger dynamic program at a coarse granularity picked from the alphabet size) and prices each against the modeled decode cost of zxc_pivco_decode_core. The cheapest candidate that clears the adoption guard (<= +ZXC_HUF_NUDGE_BITS_PERMIL ratio cost AND <= ZXC_HUF_NUDGE_MERGE_Q8 modeled level-touches) replaces code_len; otherwise the array is left byte-for-byte untouched, so a rejected nudge emits an archive identical to the unadjusted encoder. Coarse-DP candidates may pad the tree with zero-frequency "ghost" leaves on unused byte values; the wire carries them as empty runs.

Encoder policy only: any adopted output is canonical, Kraft-exact and capped at max_code_len, so the wire format and every deployed decoder are unaffected. Compiled once in the primary variant (ISA-independent decision code), guaranteeing cross-ISA identical archives. Cost is a few hundred microseconds per table at most (DP plane sizes are capped by the coarse granularity), which the ULTRA-only and trainer call sites absorb.

Parameters

[in]	freq	Frequency table of length ZXC_HUF_NUM_SYMBOLS.
[in,out]	code_len	Lengths from zxc_huf_build_code_lengths.
[in]	scratch	Optional: the rebuilds' region, plus the workspace when scratch_cap reaches ZXC_HUF_NUDGE_SCRATCH_SIZE (else the workspace is allocated for the call).
[in]	scratch_cap	Bytes at scratch.
[in]	max_code_len	Cap the caller built with (level cap).

Returns

1 if code_len was adjusted, 0 if kept.

Definition at line 790 of file zxc_huffman.c.

References zxc_huf_nudge_ws_t::cand, zxc_huf_nudge_ws_t::leaves, zxc_huf_nudge_ws_t::pf, zxc_huf_nudge_ws_t::pf_rank, zxc_huf_nudge_ws_t::pfg, pm_leaves_sort(), zxc_huf_pm_leaf_t::sym, zxc_huf_nudge_ws_t::sym_order, zxc_huf_pm_leaf_t::w, ZXC_FREE, zxc_huf_build_code_lengths(), ZXC_HUF_MAX_CODE_LEN_ULTRA, zxc_huf_nudge_assign(), ZXC_HUF_NUDGE_BITS_PERMIL, zxc_huf_nudge_classes(), ZXC_HUF_NUDGE_DP_M, zxc_huf_nudge_dp_solve(), zxc_huf_nudge_eval(), zxc_huf_nudge_j(), ZXC_HUF_NUDGE_MERGE_Q8, zxc_huf_nudge_pf_canonical(), ZXC_HUF_NUDGE_SCRATCH_OFF, ZXC_HUF_NUDGE_SCRATCH_SIZE, zxc_huf_nudge_walk(), ZXC_HUF_NUM_SYMBOLS, ZXC_MALLOC, and ZXC_OK.

Referenced by zxc_encode_block_glo(), and zxc_train_dict_huf().

zxc_huf_nudge_complete()

static void zxc_huf_nudge_complete ( uint32_t *  blc, const int  l, uint32_t  s, uint32_t  n_rem, const uint32_t *  blc0, const int  cap  )

static

Baseline-following completion: fill levels l+1..cap with the baseline class counts clamped into feasibility.

Parameters

[in,out]	blc	Candidate histogram; levels above l are written.
[in]	l	Last level already fixed by the caller.
[in]	s	Open slots at level l+1.
[in]	n_rem	Symbols still to place.
[in]	blc0	Baseline class counts to follow.
[in]	cap	Code-length cap of the walk.

Definition at line 495 of file zxc_huffman.c.

References zxc_huf_nudge_clamp().

Referenced by zxc_huf_nudge_walk().

zxc_huf_nudge_cost()

void zxc_huf_nudge_cost	(	const uint8_t *	code_len,
		const uint32_t *	freq,
		uint64_t *	bits,
		uint64_t *	touches
	)

Modeled (bits, level-touches) decode cost of one code-length vector.

Introspection hook for the nudge's cost model (exact, canonical-order frequency weighting); the unit tests cross-check it against the real tree built by the decoder. code_len must be structurally valid.

Definition at line 778 of file zxc_huffman.c.

References ZXC_HUF_MAX_CODE_LEN_ULTRA, zxc_huf_nudge_classes(), zxc_huf_nudge_eval(), zxc_huf_nudge_pf_canonical(), and ZXC_HUF_NUM_SYMBOLS.

zxc_huf_nudge_dp_run_j()

static uint64_t zxc_huf_nudge_dp_run_j ( const int  lu, const int  lc, const int  g_log2, const uint32_t  s, const uint32_t  c, const uint64_t *  pfg, const uint32_t  k  )

static

Exact rank-weighted J of one leaf run placed at coarse level lc.

The DP prices in REAL units through a coarse lens: one coarse slot stands for a complete depth-g_log2 subtree of 2^g_log2 frequency-adjacent leaves, so a coarse buddy block of 2^d slots is a real block of depth d + g_log2 whose leaves have real length lc + g_log2. Because canonical codes fill the code space left to right, a ledger state with s open slots pins the run start at 2^lu - s * 2^(lu - lc): the cost of taking c slots here depends only on (lc, s, c, rank interval) – which is what makes the level costs additive and the DP exact for this model.

Parameters

[in]	lu	Coarse code-space scale (ZXC_HUF_MAX_CODE_LEN_ULTRA - g_log2).
[in]	lc	Coarse level the run is placed at.
[in]	g_log2	Granularity: one coarse slot = 2^g_log2 real leaves.
[in]	s	Open coarse slots at level lc.
[in]	c	Coarse slots taken as leaves at this level.
[in]	pfg	Group-mass prefix sums in frequency-rank order.
[in]	k	Groups already placed (rank of the run's first group).

Returns

J contribution of the run (Q8 bits + lambda * touches).

Definition at line 618 of file zxc_huffman.c.

References ZXC_HUF_NUDGE_DEEP_FLAT_PENALTY, ZXC_HUF_NUDGE_LAMBDA_Q8, zxc_log2_u32(), and ZXC_PIVCO_UNPACK_FLAT_SIMD_MAX.

Referenced by zxc_huf_nudge_dp_solve().

zxc_huf_nudge_dp_solve()

static int zxc_huf_nudge_dp_solve ( zxc_huf_nudge_ws_t *  ws, const uint64_t *  pfg, const int  m, const int  cap_c, const int  lu, const int  g_log2, uint32_t *  out_cblc  )

static

Slot-ledger dynamic program: optimal class counts for the model.

States are (symbols placed, open slots) per level – the (k, s) plane of pivco-huffman #20 – relaxed level by level with the exact per-run cost above; a state with s == remaining symbols is a forced finishing level (continuing needs both c >= s and c <= s - 1). The finishing transition adds the pass-loop overhead for the resulting max depth. Backtracking the per-level arrival choices reconstructs the coarse class counts.

Iteration order and strict-improvement relaxation are fixed, so the result is deterministic.

Parameters

[in]	ws	Workspace for the DP planes.
[in]	pfg	Group-mass prefix sums in frequency-rank order.
[in]	m	Number of coarse symbols (groups), >= 2.
[in]	cap_c	Coarse code-length cap (real cap - g_log2).
[in]	lu	Coarse code-space scale (see zxc_huf_nudge_dp_run_j).
[in]	g_log2	Granularity exponent.
[out]	out_cblc	Optimal coarse class counts (indexed by coarse level).

Returns

1 on success; 0 on no feasible finish (callers then simply keep their other candidates).

Definition at line 674 of file zxc_huffman.c.

References zxc_huf_nudge_ws_t::arrive, zxc_huf_nudge_ws_t::jcur, zxc_huf_nudge_ws_t::jnxt, ZXC_HUF_MAX_CODE_LEN_ULTRA, ZXC_HUF_NUDGE_DP_M, zxc_huf_nudge_dp_run_j(), ZXC_HUF_NUDGE_LAMBDA_Q8, and ZXC_HUF_NUDGE_LEVEL_COST.

Referenced by zxc_huf_nudge_code_lengths().

zxc_huf_nudge_eval()

static void zxc_huf_nudge_eval ( const uint32_t *  blc, const uint64_t *  pf, zxc_huf_nudge_cost_t *  out  )

static

Modeled (bits, level-touches) of one class-count histogram.

The buddy decomposition of each same-depth leaf run mirrors zxc_pivco_decode_core row by row: a lone leaf at depth l is memset once and merged l times (l+1 touches); a leaf pair is emitted by its parent's XOR-blend (l touches); a flat root at depth t = l-D is unpacked once and merged t times (t+1 touches, plus a penalty past the SIMD unpackers); each pass adds a fixed overhead term.

Parameters

[in]	blc	Class counts of the candidate (Kraft-exact by construction).
[in]	pf	Frequency prefix sums of the leaves in code order (pf[0] = 0): canonical (length, symbol)-order sums give exact costs; frequency-rank sums give the cheap scores used inside the walk (bits are identical either way, only the within-run mass split differs).
[out]	out	Modeled bits and level-touches.

Definition at line 401 of file zxc_huffman.c.

References ZXC_HUF_MAX_CODE_LEN_ULTRA, ZXC_HUF_NUDGE_DEEP_FLAT_PENALTY, ZXC_HUF_NUDGE_LEVEL_COST, zxc_log2_u32(), and ZXC_PIVCO_UNPACK_FLAT_SIMD_MAX.

Referenced by zxc_huf_nudge_code_lengths(), zxc_huf_nudge_cost(), and zxc_huf_nudge_walk().

zxc_huf_nudge_j()

static uint64_t zxc_huf_nudge_j ( const zxc_huf_nudge_cost_t *  c )

inlinestatic

Candidate cost J = 256*bits + lambda*touches (Q8 bit units).

Parameters

[in]

c

Modeled cost from zxc_huf_nudge_eval.

Returns

Scalar cost; lower is better.

Definition at line 449 of file zxc_huffman.c.

References ZXC_HUF_NUDGE_LAMBDA_Q8.

Referenced by zxc_huf_nudge_code_lengths(), and zxc_huf_nudge_walk().

zxc_huf_nudge_pf_canonical()

static void zxc_huf_nudge_pf_canonical ( const uint8_t *  code_len, const uint32_t *  freq, const uint32_t *  blc, uint64_t *  pf  )

static

Frequency prefix sums over the leaves in canonical (length, symbol) order: pf[i] = mass of the first i leaves of the code space.

Parameters

[in]	code_len	Per-symbol code lengths.
[in]	freq	Frequency table indexed by symbol.
[in]	blc	Class counts of code_len (from zxc_huf_nudge_classes).
[out]	pf	Prefix sums, n_present + 1 entries with pf[0] = 0.

Definition at line 365 of file zxc_huffman.c.

References ZXC_HUF_MAX_CODE_LEN_ULTRA, and ZXC_HUF_NUM_SYMBOLS.

Referenced by zxc_huf_nudge_code_lengths(), and zxc_huf_nudge_cost().

zxc_huf_nudge_walk()

static void zxc_huf_nudge_walk ( const uint32_t *  blc0, const uint64_t *  pf_rank, const int  n, const int  cap, uint32_t *  out_blc  )

static

Greedy shallow-to-deep walk over the slot ledger.

At each level, up to six feasible class counts are tried: follow the baseline; make the internal-node count the nearest power of two (down/up) or a two-bit value (power-of-two internal-node counts keep the run boundaries aligned, which is what lets deeper runs decompose into large flat blocks); or finish the whole remainder as uniform-depth subtrees. Each count is expanded into a full candidate histogram and scored with the rank-order evaluator; the cheapest count is fixed and the walk descends. Fixed candidate order + strict improvement keeps the result deterministic. A chosen uniform-depth finish needs no lock: at the next level it reappears as the (c = 0, D-1) finish candidate, so the greedy can hold or drop it.

Parameters

[in]	blc0	Baseline class counts (package-merge output).
[in]	pf_rank	Frequency-rank prefix sums (rank 0 = most frequent).
[in]	n	Number of present symbols (>= 4).
[in]	cap	Code-length cap.
[out]	out_blc	Chosen class counts (Kraft-exact by construction).

Definition at line 525 of file zxc_huffman.c.

References ZXC_HUF_MAX_CODE_LEN_ULTRA, zxc_huf_nudge_clamp(), zxc_huf_nudge_complete(), zxc_huf_nudge_eval(), zxc_huf_nudge_j(), and zxc_log2_u32().

Referenced by zxc_huf_nudge_code_lengths().

zxc_huf_pack_lengths()

void zxc_huf_pack_lengths	(	const uint8_t *	code_len,
		uint8_t *	out
	)

Pack per-symbol code lengths into the 128-byte (4-bit nibble) header.

Nibble order follows the byte: code_len[2*i] low, code_len[2*i + 1] high. Lengths above 15 are silently truncated, so the caller must have capped at ZXC_HUF_MAX_CODE_LEN_ULTRA (<= 15) first.

Parameters

[in]	code_len	Per-symbol lengths, ZXC_HUF_NUM_SYMBOLS entries.
[out]	out	ZXC_HUF_TABLE_SIZE bytes of packed header.

Pack per-symbol code lengths into the 128-byte (4-bit nibble) header.

Un-suffixed entry forwarding to zxc_huf_pack_lengths_default; full contract in zxc_internal.h.

Definition at line 949 of file zxc_huffman.c.

References ZXC_HUF_NUM_SYMBOLS.

Referenced by zxc_pivco_encode_core().

zxc_huf_unpack_lengths()

int zxc_huf_unpack_lengths	(	const uint8_t *	in,
		uint8_t *	code_len
	)

Unpack and structurally validate a 128-byte packed lengths header.

Inverts zxc_huf_pack_lengths and checks the two structural invariants: no length above ZXC_HUF_MAX_CODE_LEN_ULTRA, and at least one symbol present. Kraft consistency is not checked here; the tree build does that later.

Parameters

[in]	in	128-byte packed header.
[out]	code_len	Per-symbol lengths, ZXC_HUF_NUM_SYMBOLS entries.

Returns

ZXC_OK, or ZXC_ERROR_CORRUPT_DATA if a length is too large or the table is empty.

Unpack and structurally validate a 128-byte packed lengths header.

Un-suffixed entry forwarding to zxc_huf_unpack_lengths_default; full contract in zxc_internal.h.

Definition at line 957 of file zxc_huffman.c.

References ZXC_ERROR_CORRUPT_DATA, ZXC_HUF_MAX_CODE_LEN_ULTRA, ZXC_HUF_NUM_SYMBOLS, and ZXC_OK.

Referenced by zxc_huf_decode_section(), and zxc_huf_dict_tree_build().

zxc_pivco_bitrev_permute()

static void zxc_pivco_bitrev_permute ( uint8_t *  s, const int  D  )

static

Reorders s[0, 2^D) by bit-reversed index (an involution).

Definition at line 1024 of file zxc_huffman.c.

Referenced by zxc_pivco_tree_build().

zxc_pivco_codes()

static void zxc_pivco_codes ( const zxc_pivco_tree_t *  t, uint32_t *  codes  )

static

Code of every leaf: the prefix of its slot (see zxc_pivco_tree_t).

Definition at line 1150 of file zxc_huffman.c.

References zxc_pivco_leaves().

Referenced by zxc_huf_dict_tree_build(), and zxc_huf_encode_section().

zxc_pivco_counts()

static void zxc_pivco_counts ( const zxc_pivco_tree_t *  t, const uint32_t *  freq, uint32_t *  count  )

static

Per-node symbol counts from the histogram (encoder / size estimate).

Bottom-up; the slot counts 0. Covered nodes are counted too: callers skip them by flat_d.

Definition at line 1135 of file zxc_huffman.c.

References zxc_pivco_leaves().

Referenced by zxc_huf_calc_size_dict(), and zxc_pivco_encode_core().

zxc_pivco_decode_core()

static int zxc_pivco_decode_core ( const uint8_t *  payload, const size_t  payload_size, uint8_t *  dst, const size_t  n, const zxc_pivco_tree_t *  t, uint8_t *  scratch  )

static

Shared PivCo section decoder body (code lengths already unpacked).

Pass 1 (sizing) walks the wire order once: each internal node's bit run is located, bounds-checked and popcounted, which yields both children's symbol counts. Pass 2 rebuilds sequences bottom-up, one level at a time, ping-ponging between dst (even depths, depth 0 = final output) and scratch (odd depths); a level's writes never alias its reads. A flat root's leaves, stored in packed-code order, are its code -> symbol table.

Definition at line 2158 of file zxc_huffman.c.

References ZXC_ERROR_CORRUPT_DATA, ZXC_HUF_MAX_CODE_LEN_ULTRA, ZXC_OK, zxc_pivco_emit_leaf_pair(), zxc_pivco_flat_leaves(), zxc_pivco_leaves(), zxc_pivco_merge(), ZXC_PIVCO_NODE_SLOTS, zxc_pivco_run_bytes(), and zxc_pivco_unpack_flat().

Referenced by zxc_huf_decode_section(), and zxc_huf_decode_section_dict().

zxc_pivco_emit_leaf_pair()

static void zxc_pivco_emit_leaf_pair ( uint8_t *  out, const size_t  n, const uint8_t  sym0, const uint8_t  sym1, const uint8_t *  bits  )

inlinestatic

Direct emission for a node whose two children are BOTH leaves.

out[k] = bit_k ? sym1 : sym0, i.e. sym0 ^ (delta & mask(bit_k)). Skips materialising the two child runs entirely (idea from the PivCo reference implementation: sequential stores + bit-test/XOR-blend beat a table merge of two constant runs by 2-3x).

Definition at line 2053 of file zxc_huffman.c.

Referenced by zxc_pivco_decode_core().

zxc_pivco_encode_core()

static int zxc_pivco_encode_core ( const uint8_t *  literals, const size_t  n_literals, const uint32_t *  freq, const uint8_t *  code_len, const zxc_pivco_tree_t *  t, const uint32_t *  codes, uint8_t *  dst, const size_t  dst_cap, const int  with_header  )

static

Shared PivCo section encoder body.

Walks each input symbol root-to-leaf once, appending its branch bit to the per-node write cursor; runs land in wire order, byte-aligned. The depth-d node of a code is its d-bit prefix.

Definition at line 1234 of file zxc_huffman.c.

References ZXC_ERROR_CORRUPT_DATA, ZXC_ERROR_DST_TOO_SMALL, ZXC_HUF_NUM_SYMBOLS, zxc_huf_pack_lengths(), ZXC_HUF_TABLE_SIZE, zxc_pivco_counts(), zxc_pivco_layout(), ZXC_PIVCO_MAX_NODES, and ZXC_PIVCO_NODE_SLOTS.

Referenced by zxc_huf_encode_section(), and zxc_huf_encode_section_dict().

zxc_pivco_flat_leaves()

static int zxc_pivco_flat_leaves ( const zxc_pivco_tree_t *  t, const int  g, const int  d, const int  D  )

inlinestatic

syms index of flat root g's first leaf: its prefix, then D zero bits.

Definition at line 1017 of file zxc_huffman.c.

Referenced by zxc_pivco_decode_core(), and zxc_pivco_tree_build().

zxc_pivco_layout()

static size_t zxc_pivco_layout ( const zxc_pivco_tree_t *  t, const uint32_t *  count, uint32_t *  cur  )

static

Payload size, and each run's first bit as a cursor if cur is set.

Runs: every uncovered internal node, in wire order. Estimator and encoder share this walk, so their sizes cannot drift.

Definition at line 1188 of file zxc_huffman.c.

References ZXC_PIVCO_COVERED, zxc_pivco_leaves(), and zxc_pivco_run_bytes().

Referenced by zxc_huf_calc_size_dict(), and zxc_pivco_encode_core().

zxc_pivco_leaves()

static int zxc_pivco_leaves ( const zxc_pivco_tree_t *  t, const int  d  )

inlinestatic

Leaves at depth d.

Definition at line 1012 of file zxc_huffman.c.

Referenced by zxc_pivco_codes(), zxc_pivco_counts(), zxc_pivco_decode_core(), zxc_pivco_layout(), and zxc_pivco_tree_build().

zxc_pivco_merge()

static void zxc_pivco_merge ( uint8_t *  out, const uint8_t *  src, const size_t  nl, const size_t  nr, const uint8_t *  bits  )

inlinestatic

Merge two adjacent child sequences under control bits.

src[0..nl) is the left sequence, src[nl..nl+nr) the right one (children are contiguous by construction). Control bits are LSB-first; bit 0 takes the next left element, bit 1 the next right one. Speculative 16-byte loads read up to 15 bytes past each cursor: callers guarantee read slack after the level buffers. Writes stay within out[0..nl+nr).

Definition at line 1376 of file zxc_huffman.c.

References ZXC_PIVCO_MERGE_STEP.

Referenced by zxc_pivco_decode_core().

zxc_pivco_popcnt32()

static int zxc_pivco_popcnt32 ( const uint32_t  v )

inlinestatic

Definition at line 1007 of file zxc_huffman.c.

zxc_pivco_popcnt64()

static int zxc_pivco_popcnt64 ( const uint64_t  v )

inlinestatic

Definition at line 1009 of file zxc_huffman.c.

zxc_pivco_run_bytes()

static size_t zxc_pivco_run_bytes ( const uint32_t  count, const uint8_t  flat_d  )

inlinestatic

Byte size of one PivCo node's on-wire bit run.

A wire-visible node emits one of two run kinds, both bit-packed then rounded up to whole bytes:

• Flat root (flat_d > 0): a complete subtree of depth flat_d, storing count packed codes of flat_d bits each: ceil(count * flat_d / 8).
• Merge node (flat_d == 0): one partition bit per symbol routed through the node: ceil(count / 8).

This is THE wire run-boundary rule. It is the single definition shared by the size estimator (zxc_huf_calc_size), the encoder (zxc_pivco_encode_core), and the decoder's pass-1 pointer walk (zxc_pivco_decode_core), so the three cannot drift: the encoder asserts bytes-written == estimate, and the decoder advances from run to run by this exact arithmetic.

Parameters

[in]	count	Number of symbols the node covers (packed codes if flat, else partition bits).
[in]	flat_d	Flat-subtree depth (bits per packed code), or 0 for a merge node.

Returns

Byte length of the node's run (0 when count is 0).

Definition at line 1178 of file zxc_huffman.c.

Referenced by zxc_pivco_decode_core(), zxc_pivco_layout(), and zxc_pivco_unpack_flat().

zxc_pivco_tree_build()

static int zxc_pivco_tree_build ( const uint8_t *  code_len, zxc_pivco_tree_t *  t  )

static

Build the canonical code tree from per-symbol lengths.

Accepts Kraft-tight lengths within the ceiling, or a lone length-1 symbol.

Parameters

[in]	code_len	Per-symbol code lengths (0 = absent).
[out]	t	Tree, over the ranges zxc_pivco_tree_t documents.

Returns

0 on success, -1 on malformed lengths.

Definition at line 1048 of file zxc_huffman.c.

References ZXC_HUF_MAX_CODE_LEN_ULTRA, ZXC_HUF_NUM_SYMBOLS, zxc_pivco_bitrev_permute(), ZXC_PIVCO_COVERED, zxc_pivco_flat_leaves(), and zxc_pivco_leaves().

Referenced by zxc_huf_calc_size(), zxc_huf_decode_section(), zxc_huf_dict_tree_build(), and zxc_huf_encode_section().

zxc_pivco_unpack_flat()

static void zxc_pivco_unpack_flat ( uint8_t *  out, const size_t  n, const int  D, const uint8_t *  bits, const uint8_t *  c2s  )

static

Decode a flat subtree's packed D-bit code run into symbols.

codes are packed LSB-first, D in [2, ZXC_HUF_MAX_CODE_LEN_ULTRA]; c2s maps a packed path to its leaf symbol. SIMD paths cover D = 2..6 (in-register unpack, then one table lookup over the subtree's 2^D entries); the scalar bit-reader handles every D.

Definition at line 1555 of file zxc_huffman.c.

References zxc_le32(), zxc_le64(), and zxc_pivco_run_bytes().

Referenced by zxc_pivco_decode_core().