Block-level compression: LZ77 parsing, GLO / GHI / RAW encoding, and the chunk-wrapper entry point. More...

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

Functions
static uint32_t	zxc_hash_func (const uint64_t val, const int use_hash5)
	Computes a hash value for either a 4-byte or 5-byte sequence.

static uint8_t	zxc_hash_tag (const uint32_t val4)
	8-bit rejection tag: XOR fold of the first four bytes at a position.

static uint32_t	zxc_epoch_pos (const uint32_t head, const uint32_t offset_mask, const uint32_t epoch_mark)
	Decodes a hash-table slot into a block position, 0 if it is stale.

static uint16_t	zxc_chain_delta (const uint32_t cur_pos, const uint32_t prev_idx)
	Chain link from a position back to the one the hash slot held.

static size_t	zxc_write_varint (uint8_t *dst, const uint32_t val)
	Pair-equality mask for the RLE lookahead: element i is set when p[i] == p[i+1].

static int	zxc_emit_extra (uint8_t extras, size_t used, const uint32_t val, const uint32_t mask)
	Appends a saturated token field's excess to the extras stream.

static int	zxc_glo_put_seq (uint8_t buf_tokens, uint16_t buf_offsets, uint8_t buf_extras, uint32_t seq_c, size_t extras_sz, uint16_t max_offset, const uint32_t ll, const uint32_t ml, const uint16_t off_biased)
	Emits one GLO sequence (token, offset, LL/ML escapes) and updates `max_offset`, the block's widest biased offset.

static void	zxc_extras_move (uint8_t extras, size_t w, size_t r, const uint8_t to)
	Moves extras[r, to) down to extras[w] (w <= r), advancing both.

static void	zxc_varint_keep (uint8_t extras, size_t w, size_t r, const uint8_t end)
	Keeps the varint at extras[r]: moves it down to extras[w].

static uint32_t	zxc_glo_split_pieces (const uint32_t code)
	Inline pieces a match of length code `code` splits into: ceil(length / 19).

static uint32_t	zxc_glo_split_piece (const uint32_t code)
	Next piece of a match of length code `code` above the inline reach: the longest inline one that leaves at least a minimum match.

static int	zxc_glo_split_analyze (const uint8_t tokens, const uint32_t n_seq, zxc_glo_split_hist_t hist_buf, uint8_t ctx_bad, uint8_t side)
	Predictability of the block's ML-escape branch, for the split decision.

static uint32_t	zxc_glo_split_block (uint8_t tokens, uint16_t offsets, uint8_t extras, size_t extras_sz, uint8_t side, zxc_glo_split_hist_t hist_buf, const uint32_t n_seq, const uint8_t cap)
	Per-block match splitting: escaped matches re-emitted as inline pieces.

static void	zxc_flush_literals (uint8_t literals, size_t lit_c, const uint8_t anchor, const uint32_t ll, const uint8_t iend)
	Stages a run of literals into the literal stream.

static int	zxc_match_reaches (const uint8_t cur, const uint8_t ref, uint32_t from, const uint32_t need, const uint8_t *iend)
	Tells whether a match reaches a given length, without measuring it.

static int	zxc_lazy_probe (const uint8_t src, const uint8_t lp, const uint8_t iend, const uint32_t need, const uint32_t hash_table, const uint8_t hash_tags, const uint16_t chain_table, const uint32_t epoch_mark, const uint32_t offset_mask, const int use_hash5, const zxc_lz77_params_t p)
	Tells whether `lp` holds a match of at least `need` bytes, within the lazy search budget.

static zxc_match_t	zxc_lz77_find_best_match (const uint8_t src, const uint8_t ip, const uint8_t iend, const uint8_t search_limit, const uint8_t anchor, uint32_t hash_table, uint8_t hash_tags, uint16_t chain_table, const uint32_t epoch_mark, const uint32_t offset_mask, const int level, const zxc_lz77_params_t p, const uint32_t last_off)
	Finds the best matching sequence for LZ77 compression.

static void	zxc_opt_relax (uint32_t dp, uint16_t parent_len, uint16_t *parent_off, const size_t p, const size_t L, const uint32_t nxt, const uint16_t off_biased)
	Relaxes dp[p + L] with a match of length `L` costing `nxt` in total.

static size_t	zxc_opt_dp_update_const_cost (uint32_t dp, uint16_t parent_len, uint16_t *parent_off, const size_t p, size_t L, const size_t L_end, const uint32_t nxt, const uint16_t off_biased)
	Update dp[p + L_start .

static uint32_t	zxc_opt_estimate_lit_bits (const uint8_t src, const size_t src_sz, void scratch)
	Estimate per-block literal cost from a sampled histogram passed through the actual length-limited Huffman builder.

static int	zxc_lz77_optimal_parse_glo (zxc_cctx_t ctx, const uint8_t src, const size_t src_sz, uint32_t hash_table, uint8_t hash_tags, uint16_t chain_table, const uint32_t epoch_mark, const uint32_t offset_mask, const int level, uint8_t literals, uint8_t buf_tokens, uint16_t buf_offsets, uint8_t buf_extras, uint32_t seq_c_out, size_t lit_c_out, size_t extras_sz_out, uint16_t *max_offset_out)
	Static price-based optimal LZ77 parser for level 6.

static void	zxc_lz_seed_dict (const uint8_t src, const size_t dict_size, uint32_t hash_table, uint8_t hash_tags, uint16_t chain_table, const uint32_t epoch_mark, const uint32_t offset_mask, const int level)
	Seeds the hash/chain tables from dictionary content prepended to `src`.

static int	zxc_encode_block_glo (zxc_cctx_t ctx, const uint8_t src, const size_t src_sz, uint8_t dst, size_t dst_cap, size_t out_sz)
	Encodes one block in the GLO format (levels 3 and up).

static int	zxc_encode_block_ghi (zxc_cctx_t ctx, const uint8_t src, const size_t src_sz, uint8_t dst, const size_t dst_cap, size_t const out_sz)
	Encodes one block in the GHI format (levels 1 and 2, the speed path).

static int	zxc_encode_block_raw (const uint8_t src, const size_t src_sz, uint8_t const dst, const size_t dst_cap, size_t *const out_sz)
	Encodes a RAW (stored) block: header plus a verbatim copy.

int	zxc_compress_chunk_wrapper (zxc_cctx_t ctx, const uint8_t chunk, const size_t src_sz, uint8_t *dst, const size_t dst_cap, const uint64_t block_index)
	Compresses one chunk into a single ZXC block (the compression hot path).

Detailed Description

Block-level compression: LZ77 parsing, GLO / GHI / RAW encoding, and the chunk-wrapper entry point.

Compiled multiple times with different ZXC_FUNCTION_SUFFIX values to produce AVX2, AVX-512, NEON, and scalar variants dispatched at runtime by zxc_dispatch.c.

Definition in file zxc_compress.c.

Function Documentation

◆ zxc_chain_delta()

static uint16_t zxc_chain_delta	(	const uint32_t	cur_pos,
		const uint32_t	prev_idx
	)

inlinestatic

Chain link from a position back to the one the hash slot held.

Branchless: a missing predecessor, or one beyond the window, gives 0, which the chain walk reads as end of chain.

Definition at line 82 of file zxc_compress.c.

References ZXC_LZ_WINDOW_SIZE.

Referenced by zxc_encode_block_glo(), zxc_lz77_find_best_match(), and zxc_lz_seed_dict().

◆ zxc_compress_chunk_wrapper()

int zxc_compress_chunk_wrapper	(	zxc_cctx_t *	ctx,
		const uint8_t *	chunk,
		const size_t	src_sz,
		uint8_t *	dst,
		const size_t	dst_cap,
		const uint64_t	block_index
	)

Compresses one chunk into a single ZXC block (the compression hot path).

Compresses one chunk through the runtime ISA dispatch.

Selects the GHI encoder at level <= 2, otherwise GLO; falls back to a RAW block when the coded form would not shrink the data. When ctx->dict_size is > 0, chunk is the [dict | block] concat and only the block tail counts toward the expansion check. Appends the checksum when enabled, seeded with block_index.

Definition at line 2217 of file zxc_compress.c.

References ZXC_BLOCK_CHECKSUM_SIZE, ZXC_BLOCK_HEADER_SIZE, zxc_checksum(), ZXC_CHECKSUM_RAPIDHASH, zxc_encode_block_ghi(), zxc_encode_block_glo(), zxc_encode_block_raw(), ZXC_ERROR_DST_TOO_SMALL, ZXC_ERROR_OVERFLOW, ZXC_OK, and zxc_store_le32().

Referenced by zxc_stream_process(), and zxc_train_dict_huf().

◆ zxc_emit_extra()

static int zxc_emit_extra	(	uint8_t *	extras,
		size_t *	used,
		const uint32_t	val,
		const uint32_t	mask
	)

inlinestatic

Appends a saturated token field's excess to the extras stream.

A field holds values below its mask; a larger one stores the mask in the token and the excess here as a varint. Returns 0 if it does not fit one.

Definition at line 232 of file zxc_compress.c.

References zxc_write_varint().

Referenced by zxc_encode_block_ghi(), and zxc_glo_put_seq().

◆ zxc_encode_block_ghi()

static int zxc_encode_block_ghi	(	zxc_cctx_t *	ctx,
		const uint8_t *	src,
		const size_t	src_sz,
		uint8_t *	dst,
		const size_t	dst_cap,
		size_t *const	out_sz
	)

static

Encodes one block in the GHI format (levels 1 and 2, the speed path).

What sets GHI apart is the sequence record. GLO packs a 1-byte token (4-bit literal length, 4-bit match length) and escapes anything longer through a varint; GHI spends a fixed 4 bytes instead - 8-bit LL, 8-bit ML (both escaping at 255) and a 16-bit offset covering the whole 64 KB window. Lengths between 16 and 255 are common, and this keeps them out of the varint reader, which is what the decoder actually pays for.

Parameters

[in,out]	ctx	Compression context: hash and chain tables, buffers, level.
[in]	src	Input, prefixed by the dictionary content when one is active.
[in]	src_sz	Size of `src`, that prefix included.
[out]	dst	Destination buffer.
[in]	dst_cap	Capacity of `dst`.
[out]	out_sz	Receives the number of bytes written.

Returns: ZXC_OK, or a negative zxc_error_t, typically ZXC_ERROR_DST_TOO_SMALL.

Definition at line 2017 of file zxc_compress.c.

References zxc_block_header_t::block_type, zxc_block_header_t::comp_size, zxc_lz77_params_t::min_offset, zxc_gnr_header_t::n_sequences, zxc_lz77_params_t::step_base, zxc_lz77_params_t::step_shift, ZXC_BLOCK_HEADER_SIZE, zxc_block_is_short_dist_bound(), ZXC_BLOCK_LIT_SLACK, ZXC_CACHE_LINE_SIZE, zxc_emit_extra(), ZXC_ERROR_DST_TOO_SMALL, ZXC_ERROR_OVERFLOW, zxc_flush_literals(), zxc_get_lz77_params(), zxc_hash_func(), zxc_le64(), zxc_lz77_find_best_match(), ZXC_LZ_HASH_SIZE, ZXC_LZ_MIN_MATCH_LEN, ZXC_LZ_OFFSET_BIAS, ZXC_LZ_SEARCH_MARGIN, zxc_lz_seed_dict(), ZXC_OK, ZXC_SEQ_LL_MASK, ZXC_SEQ_ML_BITS, ZXC_SEQ_ML_MASK, ZXC_SEQ_OFF_BITS, ZXC_SEQ_OFF_MASK, zxc_store_le32(), zxc_write_block_header(), and zxc_write_ghi_header().

Referenced by zxc_compress_chunk_wrapper().

◆ zxc_encode_block_glo()

static int zxc_encode_block_glo	(	zxc_cctx_t *	ctx,
		const uint8_t *	src,
		const size_t	src_sz,
		uint8_t *	dst,
		size_t	dst_cap,
		size_t *	out_sz
	)

static

Encodes one block in the GLO format (levels 3 and up).

Two parsers feed the same serialiser. Levels 6 and 7 hand the whole parse to zxc_lz77_optimal_parse_glo() and rejoin at parse_done; levels 3 to 5 run the lazy loop here, with the search depth, lazy attempts and hash step taken from zxc_get_lz77_params(). Either way the parse yields a literal run plus token, offset and extras streams.

The tail then picks an encoding per section - RAW against RLE for the literals, plus a Huffman candidate from level 6 - sizes the sequence streams, and writes the header, its descriptors and the payload.

Parameters

[in,out]	ctx	Compression context: hash and chain tables, buffers, level.
[in]	src	Input, prefixed by the dictionary content when one is active.
[in]	src_sz	Size of `src`, that prefix included.
[out]	dst	Destination buffer.
[in]	dst_cap	Capacity of `dst`.
[out]	out_sz	Receives the number of bytes written.

Returns: ZXC_OK, or a negative zxc_error_t, typically ZXC_ERROR_DST_TOO_SMALL.

Definition at line 1416 of file zxc_compress.c.

References zxc_block_header_t::block_type, zxc_block_header_t::comp_size, zxc_lz77_params_t::min_offset, zxc_gnr_header_t::n_sequences, zxc_lz77_params_t::split_max, zxc_lz77_params_t::step_base, zxc_lz77_params_t::step_shift, ZXC_BLOCK_HEADER_SIZE, zxc_block_is_short_dist_bound(), ZXC_BLOCK_LIT_SLACK, zxc_chain_delta(), zxc_ctz32(), zxc_ctz64(), zxc_epoch_pos(), ZXC_ERROR_DST_TOO_SMALL, ZXC_ERROR_OVERFLOW, zxc_flush_literals(), zxc_get_lz77_params(), zxc_glo_put_seq(), zxc_glo_split_block(), zxc_hash_func(), zxc_hash_tag(), zxc_huf_build_code_lengths(), zxc_huf_calc_size(), zxc_huf_calc_size_dict(), zxc_huf_enc_max_code_len(), zxc_huf_encode_section(), zxc_huf_encode_section_dict(), ZXC_HUF_MIN_LITERALS, zxc_huf_nudge_code_lengths(), ZXC_HUF_NUM_SYMBOLS, zxc_le64(), ZXC_LEVEL_BALANCED, ZXC_LEVEL_DENSITY, ZXC_LEVEL_ULTRA, ZXC_LIT_RLE_FLAG, zxc_lz77_find_best_match(), zxc_lz77_optimal_parse_glo(), ZXC_LZ_HASH_SIZE, ZXC_LZ_MIN_MATCH_LEN, ZXC_LZ_OFFSET_BIAS, ZXC_LZ_SEARCH_MARGIN, zxc_lz_seed_dict(), ZXC_LZ_WINDOW_MASK, ZXC_OK, zxc_ss_prem_huf_q8(), zxc_ss_prem_rle_q8(), ZXC_SS_TAX, zxc_store_le16(), zxc_write_block_header(), and zxc_write_glo_header_and_desc().

Referenced by zxc_compress_chunk_wrapper().

◆ zxc_encode_block_raw()

static int zxc_encode_block_raw	(	const uint8_t *	src,
		const size_t	src_sz,
		uint8_t *const	dst,
		const size_t	dst_cap,
		size_t *const	out_sz
	)

static

Encodes a RAW (stored) block: header plus a verbatim copy.

Any block checksum is appended by the caller, not here.

Parameters

[in]	src	Pointer to the source data to encode.
[in]	src_sz	Size of the source data in bytes.
[out]	dst	Pointer to the destination buffer.
[in]	dst_cap	Maximum capacity of the destination buffer.
[out]	out_sz	Pointer to a variable receiving the total written size (header + data).

Returns: ZXC_OK on success, or a negative zxc_error_t code (e.g., ZXC_ERROR_DST_TOO_SMALL) if the destination buffer capacity is insufficient.

Definition at line 2186 of file zxc_compress.c.

References zxc_block_header_t::block_flags, zxc_block_header_t::block_type, zxc_block_header_t::comp_size, zxc_block_header_t::reserved, ZXC_BLOCK_HEADER_SIZE, ZXC_ERROR_DST_TOO_SMALL, ZXC_OK, and zxc_write_block_header().

Referenced by zxc_compress_chunk_wrapper().

◆ zxc_epoch_pos()

static uint32_t zxc_epoch_pos	(	const uint32_t	head,
		const uint32_t	offset_mask,
		const uint32_t	epoch_mark
	)

inlinestatic

Decodes a hash-table slot into a block position, 0 if it is stale.

Slots carry the epoch above offset_mask, so an entry left from an earlier block reads as "no match" and the table never needs clearing.

Definition at line 71 of file zxc_compress.c.

Referenced by zxc_encode_block_glo(), zxc_lazy_probe(), zxc_lz77_find_best_match(), and zxc_lz_seed_dict().

◆ zxc_extras_move()

static void zxc_extras_move	(	uint8_t *	extras,
		size_t *	w,
		size_t *	r,
		const uint8_t *	to
	)

inlinestatic

Moves extras[*r, to) down to extras[*w] (w <= r), advancing both.

Definition at line 276 of file zxc_compress.c.

Referenced by zxc_glo_split_block(), and zxc_varint_keep().

◆ zxc_flush_literals()

static void zxc_flush_literals	(	uint8_t *	literals,
		size_t *	lit_c,
		const uint8_t *	anchor,
		const uint32_t	ll,
		const uint8_t *	iend
	)

inlinestatic

Stages a run of literals into the literal stream.

One 32-byte wild copy covers the common short run. Within 32 bytes of the block end that copy would read past it, so the tail takes an exact copy.

Definition at line 442 of file zxc_compress.c.

References zxc_copy32(), and ZXC_PAD_SIZE.

Referenced by zxc_encode_block_ghi(), and zxc_encode_block_glo().

◆ zxc_glo_put_seq()

static int zxc_glo_put_seq	(	uint8_t *	buf_tokens,
		uint16_t *	buf_offsets,
		uint8_t *	buf_extras,
		uint32_t *	seq_c,
		size_t *	extras_sz,
		uint16_t *	max_offset,
		const uint32_t	ll,
		const uint32_t	ml,
		const uint16_t	off_biased
	)

inlinestatic

Emits one GLO sequence (token, offset, LL/ML escapes) and updates max_offset, the block's widest biased offset.

Parameters

[out]	buf_tokens	Token stream; the token goes at index `*seq_c`.
[out]	buf_offsets	Offset stream, same index.
[out]	buf_extras	Extras stream, for the LL/ML excess varints.
[in,out]	seq_c	Sequence count, advanced on success.
[in,out]	extras_sz	Bytes used in `buf_extras`.
[in,out]	max_offset	Widest biased offset so far.
[in]	ll	Literal length (raw).
[in]	ml	Match length minus ZXC_LZ_MIN_MATCH_LEN.
[in]	off_biased	Offset minus ZXC_LZ_OFFSET_BIAS.

Returns: 1, or 0 when a length exceeds ZXC_MAX_VARINT_VALUE. The extras buffer is sized by the layout, not checked here.

Definition at line 257 of file zxc_compress.c.

References zxc_emit_extra(), ZXC_TOKEN_LIT_BITS, ZXC_TOKEN_LL_MASK, and ZXC_TOKEN_ML_MASK.

Referenced by zxc_encode_block_glo(), and zxc_lz77_optimal_parse_glo().

◆ zxc_glo_split_analyze()

static int zxc_glo_split_analyze	(	const uint8_t *	tokens,
		const uint32_t	n_seq,
		zxc_glo_split_hist_t *	hist_buf,
		uint8_t *	ctx_bad,
		uint8_t *	side
	)

static

Predictability of the block's ML-escape branch, for the split decision.

Contexts are the last order escape bits; side records each sequence's. ctx_bad marks the contexts where an escape is the minority outcome: the decoder's predictor guesses "no escape" and misses. Four rotating histogram lanes keep an inline run off one store-forwarding chain.

Returns: 1 when the minority counts, a static predictor's misses, reach ZXC_GLO_SPLIT_MIN_MISPREDICT_PCT of the escapes and some escape sits in a bad context, so that a split can happen; else 0.

Definition at line 313 of file zxc_compress.c.

References ZXC_GLO_SPLIT_CTX_BITS, ZXC_GLO_SPLIT_MIN_MISPREDICT_PCT, and ZXC_TOKEN_ML_MASK.

Referenced by zxc_glo_split_block().

◆ zxc_glo_split_block()

static uint32_t zxc_glo_split_block	(	uint8_t *	tokens,
		uint16_t *	offsets,
		uint8_t *	extras,
		size_t *	extras_sz,
		uint8_t *	side,
		zxc_glo_split_hist_t *	hist_buf,
		const uint32_t	n_seq,
		const uint8_t	cap
	)

static

Per-block match splitting: escaped matches re-emitted as inline pieces.

A match whose length code exceeds the inline reach but not cap becomes a chain of inline matches at the same offset: the decoder never takes its ML escape. Each extra piece costs a token and an offset, less the varint it replaces.

Two gates (zxc_glo_split_analyze): the block must look mispredicted, which leaves regular data whole, then only escapes of mispredicted contexts split.

In place: pass 1 turns side from each sequence's context into its length code to split (0 = keep) and compacts the kept extras forward; pass 2 expands tokens and offsets backward, each write at or past its read. A piece consumes at least ZXC_LZ_MIN_MATCH_LEN input bytes, so the count fits the block's sequence buffers.

Parameters

[in,out]	tokens	The block's tokens, rewritten in place.
[in,out]	offsets	Its offsets, rewritten in place.
[in,out]	extras	Its extras, compacted in place.
[in,out]	extras_sz	Bytes used in `extras`.
[out]	side	Scratch, one byte per sequence (zxc_cctx_t::buf_split).
[out]	hist_buf	Scratch (zxc_cctx_t::buf_split_hist).
[in]	n_seq	Sequence count of the block.
[in]	cap	zxc_lz77_params_t::split_max.

Returns: The new sequence count (unchanged when the block is not split).

Definition at line 374 of file zxc_compress.c.

References zxc_extras_move(), ZXC_GLO_INLINE_ML_CODE, zxc_glo_split_analyze(), ZXC_GLO_SPLIT_CTX_BITS, zxc_glo_split_piece(), zxc_glo_split_pieces(), ZXC_LZ_MIN_MATCH_LEN, zxc_read_varint(), ZXC_TOKEN_LIT_BITS, ZXC_TOKEN_LL_MASK, ZXC_TOKEN_ML_MASK, and zxc_varint_keep().

Referenced by zxc_encode_block_glo().

◆ zxc_glo_split_piece()

static uint32_t zxc_glo_split_piece ( const uint32_t code )

inlinestatic

Next piece of a match of length code code above the inline reach: the longest inline one that leaves at least a minimum match.

Definition at line 296 of file zxc_compress.c.

References ZXC_GLO_INLINE_ML_CODE, and ZXC_LZ_MIN_MATCH_LEN.

Referenced by zxc_glo_split_block().

◆ zxc_glo_split_pieces()

static uint32_t zxc_glo_split_pieces ( const uint32_t code )

inlinestatic

Inline pieces a match of length code code splits into: ceil(length / 19).

Definition at line 290 of file zxc_compress.c.

References ZXC_GLO_MAX_INLINE_ML, and ZXC_LZ_MIN_MATCH_LEN.

Referenced by zxc_glo_split_block().

◆ zxc_hash_func()

static uint32_t zxc_hash_func	(	const uint64_t	val,
		const int	use_hash5
	)

inlinestatic

Computes a hash value for either a 4-byte or 5-byte sequence.

Parameters

[in]	val	The 64-bit integer sequence (e.g., 8 bytes read from input stream).
[in]	use_hash5	Non-zero to use the 5-byte xorshift64* hash (Marsaglia/Vigna), zero for 4-byte Marsaglia hash.

Returns: uint32_t A hash value suitable for indexing the match table.

Definition at line 45 of file zxc_compress.c.

References ZXC_HASH_MULT32, ZXC_HASH_XORSHIFT64, and ZXC_LZ_HASH_BITS.

Referenced by zxc_encode_block_ghi(), zxc_encode_block_glo(), zxc_lazy_probe(), zxc_lz77_find_best_match(), and zxc_lz_seed_dict().

◆ zxc_hash_tag()

static uint8_t zxc_hash_tag ( const uint32_t val4 )

inlinestatic

8-bit rejection tag: XOR fold of the first four bytes at a position.

One tag per hash slot, so a mismatching head is rejected without touching the referenced data.

Definition at line 61 of file zxc_compress.c.

Referenced by zxc_encode_block_glo(), zxc_lazy_probe(), zxc_lz77_find_best_match(), and zxc_lz_seed_dict().

◆ zxc_lazy_probe()

static int zxc_lazy_probe	(	const uint8_t *	src,
		const uint8_t *	lp,
		const uint8_t *	iend,
		const uint32_t	need,
		const uint32_t *	hash_table,
		const uint8_t *	hash_tags,
		const uint16_t *	chain_table,
		const uint32_t	epoch_mark,
		const uint32_t	offset_mask,
		const int	use_hash5,
		const zxc_lz77_params_t	p
	)

inlinestatic

Tells whether lp holds a match of at least need bytes, within the lazy search budget.

Read-only; 8 bytes at lp must be readable.

Candidates are gated on the last 4 of the need bytes, [need-4, need), and the first to reach need settles it.

Definition at line 506 of file zxc_compress.c.

References zxc_lz77_params_t::lazy_attempts, zxc_lz77_params_t::min_offset, zxc_epoch_pos(), zxc_hash_func(), zxc_hash_tag(), zxc_le32(), zxc_le64(), ZXC_LZ_MAX_DIST, ZXC_LZ_WINDOW_MASK, and zxc_match_reaches().

Referenced by zxc_lz77_find_best_match().

◆ zxc_lz77_find_best_match()

static zxc_match_t zxc_lz77_find_best_match	(	const uint8_t *	src,
		const uint8_t *	ip,
		const uint8_t *	iend,
		const uint8_t *	search_limit,
		const uint8_t *	anchor,
		uint32_t *	hash_table,
		uint8_t *	hash_tags,
		uint16_t *	chain_table,
		const uint32_t	epoch_mark,
		const uint32_t	offset_mask,
		const int	level,
		const zxc_lz77_params_t	p,
		const uint32_t	last_off
	)

inlinestatic

Finds the best matching sequence for LZ77 compression.

Uses a split hash table layout:

hash_table[h] : uint32_t position + epoch (128 KB for 15-bit hash)
hash_tags[h] : uint8_t tag for fast rejection (32 KB, L1-resident)

Parameters

[in]	src	Pointer to the start of the source buffer.
[in]	ip	Current input position pointer.
[in]	iend	Pointer to the end of the input buffer.
[in]	search_limit	Pointer to the match finding limit.
[in]	anchor	Pointer to the current anchor position.
[in,out]	hash_table	Pointer to the position table for match finding.
[in,out]	hash_tags	Pointer to the tag table for fast rejection.
[in,out]	chain_table	Pointer to the chain table for collision handling.
[in]	epoch_mark	Current epoch marker for hash table invalidation.
[in]	offset_mask	Mask isolating the position bits in chain/table entries.
[in]	level	Compression level (selects search depth and matcher behaviour).
[in]	p	LZ77 parameters controlling search depth, lazy matching, and stepping.
[in]	last_off	Most recently accepted match offset, used as a repeat-offset seed probed before the hash-chain walk. Pass 0 to disable (all callers except the level-6 optimal parser do so).

Returns: zxc_match_t Structure containing the best match information (reference pointer, length of the match, and backtrack distance).

Definition at line 567 of file zxc_compress.c.

References zxc_lz77_params_t::lazy_len_threshold, zxc_lz77_params_t::min_offset, zxc_lz77_params_t::search_depth, zxc_lz77_params_t::sufficient_len, zxc_lz77_params_t::use_lazy, zxc_chain_delta(), zxc_ctz32(), zxc_ctz64(), zxc_epoch_pos(), zxc_hash_func(), zxc_hash_tag(), zxc_lazy_probe(), zxc_le32(), zxc_le64(), ZXC_LEVEL_BALANCED, ZXC_LEVEL_FAST, ZXC_LZ_MAX_DIST, ZXC_LZ_MIN_MATCH_LEN, and ZXC_LZ_WINDOW_MASK.

Referenced by zxc_encode_block_ghi(), zxc_encode_block_glo(), and zxc_lz77_optimal_parse_glo().

◆ zxc_lz77_optimal_parse_glo()

static int zxc_lz77_optimal_parse_glo	(	zxc_cctx_t *	ctx,
		const uint8_t *	src,
		const size_t	src_sz,
		uint32_t *	hash_table,
		uint8_t *	hash_tags,
		uint16_t *	chain_table,
		const uint32_t	epoch_mark,
		const uint32_t	offset_mask,
		const int	level,
		uint8_t *	literals,
		uint8_t *	buf_tokens,
		uint16_t *	buf_offsets,
		uint8_t *	buf_extras,
		uint32_t *	seq_c_out,
		size_t *	lit_c_out,
		size_t *	extras_sz_out,
		uint16_t *	max_offset_out
	)

static

Static price-based optimal LZ77 parser for level 6.

Forward DP over the block's positions: dp[p] = min bit cost to encode src[0..p). Per-position transitions are

literal: dp[p+1] = min(dp[p+1], dp[p] + lit_cost
match : dp[p+L] = min(dp[p+L], dp[p] + match_cost(L)) for L in [MIN_MATCH, max_L] where max_L is the longest match found by zxc_lz77_find_best_match at p (with lazy disabled, the DP itself handles position-based optimization). Backtracking from dp[src_sz] reconstructs the optimal token sequence.

Complexity guard: ZXC_OPT_LONG_MATCH_SKIP causes zxc_lz77_find_best_match to be skipped at positions strictly inside a long match, without this guard, highly repetitive data (e.g. Lorem-loop with multi-MB matches at every offset) makes the parser quadratic and unit tests run for minutes. The inner sub-length update visits every L from MIN_MATCH to max_L, except at a covered position (see the loop), which relaxes at most two cells; the skip threshold means each long-match region only pays its O(L) cost once at the starting position, keeping total work O(N).

Parameters

[in,out]	ctx	Compression context. The lazy-allocated `opt_scratch` field provides the DP arrays; it is grown on first use and reused on subsequent blocks.
[in]	src	Source buffer to parse.
[in]	src_sz	Length of `src` in bytes.
[in,out]	hash_table	LZ77 hash table (epoch \| position entries).
[in,out]	hash_tags	8-bit fast-rejection tags paired with `hash_table`.
[in,out]	chain_table	Hash-chain link table (ring buffer).
[in]	epoch_mark	Current epoch shifted into the high bits.
[in]	offset_mask	Mask isolating the position bits in chain entries.
[in]	level	Compression level (used to size the matcher).
[out]	literals	Buffer receiving the gathered literal bytes.
[out]	buf_tokens	Buffer receiving the per-sequence token bytes.
[out]	buf_offsets	Buffer receiving the per-sequence offsets.
[out]	buf_extras	Buffer receiving variable-length overflow data.
[out]	seq_c_out	Number of emitted sequences.
[out]	lit_c_out	Number of literal bytes written into `literals`.
[out]	extras_sz_out	Number of bytes written into `buf_extras`.
[out]	max_offset_out	Largest biased offset emitted (used by the caller to choose 1-byte vs 2-byte offset encoding).

Returns: ZXC_OK on success, or a negative zxc_error_t.

Definition at line 1106 of file zxc_compress.c.

References zxc_lz77_params_t::use_lazy, ZXC_BITMAP_WORDS, zxc_ctz64(), ZXC_ERROR_OVERFLOW, zxc_get_lz77_params(), zxc_glo_put_seq(), zxc_lz77_find_best_match(), ZXC_LZ_MIN_MATCH_LEN, ZXC_LZ_OFFSET_BIAS, ZXC_LZ_SEARCH_MARGIN, ZXC_LZ_WINDOW_SIZE, zxc_opt_dp_sizes(), zxc_opt_dp_update_const_cost(), zxc_opt_estimate_lit_bits(), ZXC_OPT_LONG_MATCH_SKIP, ZXC_OPT_MATCH_COST_BASE, zxc_opt_relax(), and ZXC_TOKEN_ML_MASK.

Referenced by zxc_encode_block_glo().

◆ zxc_lz_seed_dict()

static void zxc_lz_seed_dict	(	const uint8_t *	src,
		const size_t	dict_size,
		uint32_t *	hash_table,
		uint8_t *	hash_tags,
		uint16_t *	chain_table,
		const uint32_t	epoch_mark,
		const uint32_t	offset_mask,
		const int	level
	)

static

Seeds the hash/chain tables from dictionary content prepended to src.

When a dictionary is active, src is laid out as [dict_content | block_data]. This function inserts hash entries for dictionary positions [0, dict_size) so the match finder can reference them during block encoding.

Parameters

[in]	src	Source buffer starting with dictionary content.
[in]	dict_size	Size of the dictionary prefix in bytes.
[in,out]	hash_table	Hash table to seed with dictionary positions.
[in,out]	hash_tags	Tag table for fast match rejection.
[in,out]	chain_table	Chain table for collision resolution.
[in]	epoch_mark	Current epoch marker for hash table entries.
[in]	offset_mask	Position mask for epoch/offset encoding.
[in]	level	Compression level (controls hash function variant).

Definition at line 1360 of file zxc_compress.c.

References zxc_chain_delta(), zxc_epoch_pos(), zxc_hash_func(), zxc_hash_tag(), zxc_le64(), ZXC_LZ_MIN_MATCH_LEN, and ZXC_LZ_WINDOW_MASK.

Referenced by zxc_encode_block_ghi(), and zxc_encode_block_glo().

◆ zxc_match_reaches()

static int zxc_match_reaches	(	const uint8_t *	cur,
		const uint8_t *	ref,
		uint32_t	from,
		const uint32_t	need,
		const uint8_t *	iend
	)

inlinestatic

Tells whether a match reaches a given length, without measuring it.

The lazy evaluation only needs a yes or no, so the compare stops at need or at the first difference. Bytes below from are taken as already equal.

Parameters

[in]	cur	Position being matched.
[in]	ref	Candidate, earlier in the same buffer.
[in]	from	Bytes already known to match.
[in]	need	Length to reach; at most `iend` - `cur`.
[in]	iend	End of the input buffer.

Returns: 1 if cur[from, need) equals ref[from, need), else 0.

Definition at line 484 of file zxc_compress.c.

References zxc_ctz64(), and zxc_le64().

Referenced by zxc_lazy_probe().

◆ zxc_opt_dp_update_const_cost()

static size_t zxc_opt_dp_update_const_cost	(	uint32_t *	dp,
		uint16_t *	parent_len,
		uint16_t *	parent_off,
		const size_t	p,
		size_t	L,
		const size_t	L_end,
		const uint32_t	nxt,
		const uint16_t	off_biased
	)

inlinestatic

Update dp[p + L_start .

. p + L_end) with a constant transition cost, in parallel where the target ISA allows.

For each L in [L_start, L_end), if nxt is strictly less than the current dp[p+L], rewrite dp/parent_len/parent_off in lockstep: same semantics as the scalar update inside zxc_lz77_optimal_parse_glo. Caller guarantees nxt is independent of L (the cost of the L-th transition does not vary across the requested span).

Vectorized prologue per ISA, falling through to a scalar tail:

AVX-512 BW + VL : 16-wide via vpcmpud + vmask{store,storeu}. Falls back to AVX2 if VL is absent.
AVX2 : 8-wide via biased vpcmpgt + vpblendvb (no 32-bit unsigned cmpgt before AVX-512). parent_off is updated with a packed 8x16 mask + 128-bit blend.
NEON64 / NEON32 : 4-wide via vcgtq_u32 + vbslq_u32, with vmovn_u32 to narrow the mask for the 4x16 parent_off update.

Parameters

[in,out]	dp	DP cost array; dp[p + L] is relaxed when `nxt` < dp[p + L].
[in,out]	parent_len	Backtrack length array, written in lockstep with `dp`; receives the L of the relaxing transition.
[in,out]	parent_off	Backtrack offset array, written in lockstep; receives `off_biased` on relaxation.
[in]	p	Source DP position the transitions originate from. Indexing into the three arrays is `p + L`.
[in]	L	Initial L value (start of the span, inclusive).
[in]	L_end	End of the span (exclusive). Must satisfy `L_end` <= UINT16_MAX so every written length fits in `parent_len's` `uint16_t` cells.
[in]	nxt	Constant successor cost `dp[p] + transition`, shared across the [L, L_end) span.
[in]	off_biased	Match offset minus ZXC_LZ_OFFSET_BIAS, the value stored when a transition wins.

Returns: The first L value not processed (i.e., L_end on success).

Definition at line 904 of file zxc_compress.c.

References zxc_opt_relax().

Referenced by zxc_lz77_optimal_parse_glo().

◆ zxc_opt_estimate_lit_bits()

static uint32_t zxc_opt_estimate_lit_bits	(	const uint8_t *	src,
		const size_t	src_sz,
		void *	scratch
	)

static

Estimate per-block literal cost from a sampled histogram passed through the actual length-limited Huffman builder.

Strategy: build a strided sample of src (4096 entries), run the same length-limited Huffman code construction the encoder uses, and report the sample-weighted average code length. This is the predicted bits/byte for Huffman-encoded literals on this distribution: no calibration constants, no per-corpus tuning. The cap at 8 reflects that RAW is always available at exactly that cost; if Huffman doesn't beat 8 on the sample, the encoder will pick RAW and 8 is the right price.

Parameters

[in]	src	Source buffer for the block.
[in]	src_sz	Length of `src` in bytes.
[in]	scratch	Package-merge scratch (pre-allocated in the cctx for level >= 6). May be `NULL`, in which case the builder allocates its own working memory.

Returns: Estimated literal cost in bits, in [1, 8].

Definition at line 1029 of file zxc_compress.c.

References zxc_huf_build_code_lengths(), ZXC_HUF_MAX_CODE_LEN_DENSITY, ZXC_HUF_NUM_SYMBOLS, ZXC_OK, and ZXC_OPT_LIT_SAMPLE_MIN.

Referenced by zxc_lz77_optimal_parse_glo().

◆ zxc_opt_relax()

static void zxc_opt_relax	(	uint32_t *	dp,
		uint16_t *	parent_len,
		uint16_t *	parent_off,
		const size_t	p,
		const size_t	L,
		const uint32_t	nxt,
		const uint16_t	off_biased
	)

inlinestatic

Relaxes dp[p + L] with a match of length L costing nxt in total.

Strict comparison: on a tie the earlier transition keeps the cell.

Definition at line 853 of file zxc_compress.c.

Referenced by zxc_lz77_optimal_parse_glo(), and zxc_opt_dp_update_const_cost().

◆ zxc_varint_keep()

static void zxc_varint_keep	(	uint8_t *	extras,
		size_t *	w,
		size_t *	r,
		const uint8_t *	end
	)

inlinestatic

Keeps the varint at extras[*r]: moves it down to extras[*w].

Definition at line 282 of file zxc_compress.c.

References zxc_extras_move(), and zxc_read_varint().

Referenced by zxc_glo_split_block().

◆ zxc_write_varint()

static size_t zxc_write_varint	(	uint8_t *	dst,
		const uint32_t	val
	)

inlinestatic

Pair-equality mask for the RLE lookahead: element i is set when p[i] == p[i+1].

The only thing that differs between vector widths; the scan that consumes it is written once. ZXC_RLE_WIN is the bytes examined per step and ZXC_RLE_BPB the mask bits each byte occupies (4 on NEON, which has no byte-movemask). 32-bit NEON has no cheap equivalent and keeps its own scan.

Writes a value in Prefix Varint form.

Unary prefix bits in the first byte give the total length (1 to 5 bytes), so the reader learns the size before it reads the payload:

Format:

0xxxxxxx (1 byte)
10xxxxxx ... (2 bytes)
110xxxxx ... (3 bytes) ...

Parameters

[out]	dst	Pointer to the destination buffer where the encoded value will be written.
[in]	val	The 32-bit unsigned integer value to encode.

Returns: The number of bytes written to the destination buffer.

Definition at line 197 of file zxc_compress.c.

References ZXC_MAX_VARINT_VALUE.

Referenced by zxc_emit_extra().

Functions

Detailed Description

Function Documentation

◆ zxc_chain_delta()

◆ zxc_compress_chunk_wrapper()

◆ zxc_emit_extra()

◆ zxc_encode_block_ghi()

◆ zxc_encode_block_glo()

◆ zxc_encode_block_raw()

◆ zxc_epoch_pos()

◆ zxc_extras_move()

◆ zxc_flush_literals()

◆ zxc_glo_put_seq()

◆ zxc_glo_split_analyze()

◆ zxc_glo_split_block()

◆ zxc_glo_split_piece()

◆ zxc_glo_split_pieces()

◆ zxc_hash_func()

◆ zxc_hash_tag()

◆ zxc_lazy_probe()

◆ zxc_lz77_find_best_match()

◆ zxc_lz77_optimal_parse_glo()

◆ zxc_lz_seed_dict()

◆ zxc_match_reaches()

◆ zxc_opt_dp_update_const_cost()

◆ zxc_opt_estimate_lit_bits()

◆ zxc_opt_relax()

◆ zxc_varint_keep()

◆ zxc_write_varint()