Module describe 

Integer-sequence description-length codec (the MDL primitive)

A pure, self-contained engine that describes an &[i64] by the shortest program in a fixed menu of closed-form generators — affine (base + i·stride), geometric (base · ratioⁱ), a degree-≤4 polynomial (finite-difference seeds), a periodic block, a sparse dominant-value form, a sandboxed GenExpr generator, and the columnar fallbacks (delta, delta-of-delta, frame-of-reference bit-pack, run-length, dictionary, raw byte column, plain zig-zag varint). Each candidate is a complete self-delimiting byte string; consider keeps the smallest, so the result is never larger than plain varint.

describe_int_seq is a computable upper bound on the Kolmogorov complexity of the sequence over this description language, and decode_int_seq is its exact inverse — decode reproduces the sequence bit-for-bit, so the encoded bytes are a re-checkable witness for that bound.

This is the same codec the wire layer (logicaffeine_compile’s marshal) uses for its WireStructure::Auto int columns; it lives here in the leaf crate so both the wire codec and the proof layer share one implementation of the format. The crate has no I/O and no receiver policy, so the DoS bound (max_elements) is a parameter, supplied by each caller.

Structs

AnnihilatorWitness

A re-checkable annihilator witness: coeffs is the ANF (over [monomials](n_vars, degree)) of a nonzero g of degree degree that vanishes on C’s support (annihilates_complement = false) or on C’s zero-set (= true, i.e. g annihilates C ⊕ 1).

CorrelationAttack

The certified result of a correlation attack on one target LFSR: the recovered initial state and the statistical edge it carries. The init_state is a re-checkable witness — regenerate the LFSR from it and it reproduces the register the keystream leaks.

Gf2

GF(2) — a single bit.

Gf256

GF(2⁸) — the Rijndael/AES field (reduction polynomial x⁸+x⁴+x³+x²+1), one byte per element.

Enums

GenCmp

GenExpr

A restricted, pure, TOTAL expression over the element index i. Every op is total (div/mod by zero is 0, wrapping i64 arithmetic), and a malformed/hostile tree is bounded at decode by a node budget + depth cap, so evaluation can never panic, diverge, overflow, or escape.

PolySolveResult

The outcome of an XL solve over GF(2).

Constants

MAX_GEN_DEPTH

…or this deep — bounds both decode recursion and eval.

MAX_GEN_NODES

A hostile/garbage GenExpr tree is rejected past this many nodes.

MAX_POLY_DEGREE

The highest polynomial degree the generator detector will fit (degree 1 is the affine case).

MAX_RECUR_ORDER

The highest constant-coefficient linear-recurrence order the detector will fit. Order 2 already covers Fibonacci / Lucas / Pell and any LFSR of that length (this is Berlekamp–Massey over ℤ).

T_BYTES

T_GEN

T_INTS

T_INTS_AFFINE

T_INTS_DELTA

T_INTS_DICT

T_INTS_DOD

T_INTS_FCSR

T_INTS_FOR

T_INTS_GEOMETRIC

T_INTS_LFSR

T_INTS_LRECUR

T_INTS_PERIODIC

T_INTS_POLY

T_INTS_RLE

T_INTS_SPARSE

Traits

FieldElem

The minimal field interface Berlekamp–Massey needs.

Functions

algebraic_complexity

The algebraic complexity of a bit sequence at maximal degree max_degree: the smallest order l for which detect_algebraic_recurrence recovers a degree-≤ max_degree feedback, together with the ANF coefficient count M (the true description size — O(lᵈ), not the 2^l truth table). None if no order ≤ bits.len()/2 admits such a feedback at that degree.

algebraic_degree

The algebraic degree of a Boolean function: the largest number of variables in any monomial present in its ANF (0 for a constant, 1 for affine, up to n). None for a malformed table.

algebraic_filter_attack

Recover the initial state of a filter generator by the algebraic attack: a length-l LFSR with feedback taps drives a filter C (truth table filter_truth over its m = log₂ inputs, read as m CONSECUTIVE state bits), emitting keystream[t] = C(seq[t], …, seq[t+m−1]). Using a min-degree annihilator g of C, each applicable keystream bit becomes g(⟨r_t,s₀⟩, …) = 0, a degree-AI equation in the initial state s₀; expanding over s₀-monomials of degree ≤ AI and solving the GF(2) system recovers s₀. Returns the l-bit initial state (verified by regeneration), or None if there is no low-AI annihilator, the system is underdetermined, or l > 64.

algebraic_generate

Replay a degree-d, order-l algebraic feedback register from ANF coefficients over [monomials](l, d) and an l-bit seed: s[i] = ⊕ₘ coeffsₘ · monomialₘ(s[i-1],…,s[i-l]). The inverse of detect_algebraic_recurrence.

algebraic_immunity

The algebraic immunity of a Boolean function given as its 2ⁿ truth table: the minimum degree of a nonzero annihilator of C or of C ⊕ 1, together with a re-checkable witness. Searching degrees ascending, the first hit is the minimum (no lower-degree annihilator exists, or an earlier degree would have found it). None for a malformed table. AI ≤ ⌈n/2⌉ always.

anf

The algebraic normal form (ANF) of a Boolean function: coefficients over the 2ⁿ monomials ∏_{i∈S} xᵢ (S a variable bitmask), via the binary Möbius transform — the GF(2) dual of the Walsh–Hadamard butterfly, and its own inverse over GF(2) (applying it to the ANF returns the truth table). anf[S] is true iff the monomial ∏_{i∈S} xᵢ is present. None for a malformed table.

attack_shrinking_generator

Attack the shrinking generator: recover the initial states of both the clock register A (feedback a_taps) and the data register S (feedback s_taps) from output alone, by divide-and-conquer on the clock. Each of the 2^{L_A} clock states is tried; a guess fixes the emit positions, turning every output bit into a linear equation ⟨r_{iₖ}, s₀⟩ = output[k] in S’s initial state, solved over GF(2) and verified by regeneration. Returns (a_state, s_state) for the first guess that reproduces the output, or None (clock register too large — L_A > 22 — or no consistent state). Exponential in L_A only, not L_A + L_S.

autocorrelation

The autocorrelation spectrum of a Boolean function: r_f(a) = Σ_x (−1)^{f(x) ⊕ f(x⊕a)}, the correlation of f with its shift by a. Computed by Wiener–Khinchin — the Walsh transform of the squared Walsh spectrum, scaled by 2ⁿ — so it costs one extra butterfly over walsh_spectrum. r_f(0) = 2ⁿ always; |r_f(a)| = 2ⁿ exactly when the derivative f(x⊕a) ⊕ f(x) is CONSTANT — i.e. a is a linear structure. None for a malformed table.

berlekamp_massey_field

Berlekamp–Massey over a field. Returns (L, taps) where L is the linear complexity and taps are the connection-polynomial coefficients c₁..c_L; the recurrence is s[i] = -Σⱼ c_{j+1}·s[i-1-j].

berlekamp_massey_gf2

Berlekamp–Massey over GF(2) — the shortest bit-LFSR. Thin wrapper over berlekamp_massey_field (see it for the full semantics). For an LFSR keystream L is the register length; for random ≈ n/2.

best_linear_approximation

The best linear approximation of a Boolean function: the mask w maximizing |Ŵ(w)|, with its bias |Pr[C(x)=⟨w,x⟩] − ½| = |Ŵ(w)| / 2^{n+1}. When skip_zero, the trivial constant mask w = 0 (which measures C’s own imbalance) is excluded. Returns (mask, bias), or None for a malformed table.

bitpack

Pack vals LSB-first at width bits each (1..=64). The inverse of bitunpack.

bits_to_bytes

Pack an LSB-first bit sequence back into bytes (the inverse of bytes_to_bits); a trailing partial group is zero-padded.

bitunpack

Read count LSB-first width-bit values from bytes. None if bytes is too short. The inverse of bitpack.

bytes_to_bits

Expand a byte column to its LSB-first bit sequence (bit j of byte i is (byte_i >> j) & 1).

consider

Keep cand if it is smaller than the current best — the MDL argmin over candidate encodings.

correlation_attack

Siegenthaler’s basic correlation attack: recover the initial state of the length-L LFSR with feedback taps that best correlates with keystream, by exhaustive search over the 2^L − 1 nonzero initial states (each scored by agreement with the keystream). Returns the best state with its bias — significant only when bias clears spurious_bias_floor(L, n). Cost O(2^L·n); returns None for an empty register, a register longer than the keystream, or L > 20 (past the exhaustive cap — the domain of the fast-correlation attack, its scaling successor).

correlation_immunity_order

The correlation-immunity order of a Boolean function (Xiao–Massey): the largest m such that every Walsh coefficient at a mask of Hamming weight 1..=m vanishes. Order ≥ 1 ⇒ IMMUNE to the first-order correlation attack (Rung E finds nothing) — yet a higher-weight coefficient may still leak, which best_linear_approximation surfaces. None for a malformed table.

decode_int_column_body

Decode one int column whose tag byte has already been read as tag. The inverse of emit_best_int_column; returns None for a non-int tag or a corrupt/hostile body. max_elements caps generator expansion; depth bounds the periodic-block recursion.

decode_int_seq

Decode a full describe_int_seq byte string back to the exact sequence. Requires the whole buffer to be consumed (a clean round-trip witness). Uses a default element cap.

delta_encode

Delta: first value then zig-zag successive differences. Wins on monotone columns.

describe_int_seq

The computable upper bound on Kolmogorov complexity of v over this description language: the shortest self-delimiting program (from the generator menu) that reproduces v. The returned bytes are a re-checkable witness — decode_int_seq reproduces v exactly.

deserialize_gen

Parse a generator under a node budget and depth cap — a garbage/hostile tree returns None.

detect_affine

If v is an exact affine progression base + stride·i, return (base, stride).

detect_algebraic_recurrence

Recover the algebraic normal form of a degree-≤ d, order-l nonlinear feedback: the ANF coefficient vector over [monomials](l, d) such that replaying s[i] = ⊕ₘ cₘ · monomialₘ(window) reproduces bits exactly. Returns None if no such low-degree feedback fits (the GF(2) system is inconsistent, or the recovered coefficients fail to regenerate the sequence). This is the degree-d generalization of berlekamp_massey_gf2 (which is the d = 1 case): it compresses low-degree nonlinear generators that fool the linear, 2-adic, and maximal-order tests.

detect_geometric

If v is an exact geometric progression base · ratioⁱ (≥3 elements, confirmed by replaying the decoder’s wrapping arithmetic), return (base, ratio).

detect_linear_recurrence

Recognize v as a constant-coefficient linear recurrence v[i] = Σⱼ cⱼ·v[i-1-j] of minimal order k ≤ [MAX_RECUR_ORDER] with integer coefficients, and return (coeffs, seeds) — k coefficients + the first k values. This is exactly Berlekamp–Massey over ℤ: it captures Fibonacci, Lucas, Pell, and any linear-feedback sequence — none of which the polynomial detector can reach (their finite differences never settle). The coefficients are solved exactly (Cramer over i128) from the smallest 2k terms and then CONFIRMED by replaying the recurrence with the SAME wrapping arithmetic the decoder uses, so a match certifies a bit-exact reconstruction.

detect_modular_affine

Recognize v[i] = a + b·(i mod p) for a small period p and synthesize the generator.

detect_period

If v is an exact cyclic repetition of a minimal block of period 2 ≤ p ≤ min(len/2, cap), return p.

detect_poly_generator

Recognize v as a polynomial column (degree ≤ MAX_POLY_DEGREE) via finite differences and return (degree, seeds) — the k+1 leading-edge seeds, confirmed by exact reconstruction.

detect_sparse

If one value dominates the column (covers ≥ ¾), return it and the sorted (index, value) exceptions.

dict_encode

Dictionary: distinct values (first-seen order) then a bit-packed index column. Wins on low-cardinality columns.

dod_encode

Delta-of-delta: first value, first delta, then zig-zag second differences. Wins on near-linear progressions (timestamps with jitter).

emit_best_int_column

Build every applicable column encoding and append the smallest to out. The plain-varint baseline is always a candidate, so the result is never larger than the varint form.

fast_correlation_attack

Meier–Staffelbach fast correlation attack: recover the initial state of the length-L LFSR with feedback taps from a noisy keystream keystream (a z = a ⊕ noise binary symmetric channel), by iterative bit-flip decoding against the low-weight parity checks the feedback recurrence and its Frobenius squares generate. Returns the recovered L-bit initial state when decoding converges to a valid LFSR output that agrees with the keystream noticeably better than chance, else None (too much noise or too few low-weight checks — the register resists). Polynomial in L — no 2^L search.

fast_walsh_hadamard

The Walsh–Hadamard transform in place (the ±1 butterfly), on a slice whose length is a power of 2. a[w] becomes Σₓ a[x]·(−1)^{⟨w,x⟩}.

fcsr_generate

Generate n bits of the FCSR keystream for p/q (q odd) — the 2-adic expansion, by repeated 2-adic division. The inverse of two_adic_reconstruct.

for_encode

Frame-of-reference: subtract the column minimum, bit-pack the residuals. Wins on clustered columns (a small range around any base).

gen_eval

Evaluate a generator at index i. TOTAL: div/mod by zero is 0; all arithmetic wraps.

leb128_encode

The plain baseline column (T_INTS): an adaptive-sign header ((n << 1) | signed) then a varint per element — zig-zag when any value is negative, plain LEB128 otherwise.

lfsr_generate

Replay a GF(2) LFSR: s[i] = ⊕ⱼ tapsⱼ · s[i-1-j]. The inverse of berlekamp_massey_gf2.

lfsr_generate_field

Replay a field LFSR: emit seed, then s[i] = -Σⱼ tapsⱼ·s[i-1-j] (the connection recurrence).

maximal_order_complexity

The maximal order complexity (Jansen) of a bit sequence: the length of the shortest feedback shift register — linear OR nonlinear — that generates it, i.e. the smallest L such that every length-L window has a unique successor (s[i] = f(s[i-1],…,s[i-L]) for some feedback function f). It is the TOP of the FSR complexity hierarchy — MOC ≤ 2-adic complexity and MOC ≤ linear complexity — so it catches nonlinear generators (NFSRs, algebraic combiners with memory) that fool both Berlekamp–Massey and the 2-adic Rational Approximation. Low relative to n ⇒ a short-register generator; ≈ n/2 for a random sequence. Consistency is monotone in L, so we binary-search it.

nonlinearity

The nonlinearity of a Boolean function: 2^{n-1} − ½·maxₘ|Ŵ(w)| — its Hamming distance to the nearest affine function. High ⇒ resistant to linear approximation; maximal (bent, n even) ⇒ 2^{n-1} − 2^{n/2−1}. None for a malformed table.

read_uvarint

Read a LEB128 unsigned varint. None on an overlong/overflowing encoding or a short buffer.

reconstruct_poly

Replay a polynomial column from its finite-difference seeds via a difference engine.

rle_encode

Run-length: (value, run-length) pairs. Wins on columns of repeated runs.

serialize_gen

Serialize a generator pre-order: a 1-byte node tag, then children. Self-delimiting.

shrinking_generator

The shrinking generator: clock register A (feedback a_taps, seed a_seed) gates data register S (feedback s_taps, seed s_seed), emitting S’s bit exactly when A’s bit is 1, until out_len bits are produced. Its output is a data-dependent decimation of S with very high linear complexity.

solve_polynomial_system_gf2

Solve a Boolean polynomial system over GF(2) by XL (eXtended Linearization). Each equation is an XOR of monomials (bitmasks over the n_vars variables, x²=x; mask 0 is the constant) that must be 0. For each operating degree d = 1..=max_degree, every equation is multiplied by all monomials of degree ≤ d − deg(eq), the enlarged system is linearized over the degree-≤ d monomials (with the constant pinned to 1) and solved: an inconsistency proves the system unsatisfiable (Refuted), a solution whose degree-1 part satisfies the original equations is returned (Solved), otherwise the degree is raised. This solves systems the plain degree-d linearization cannot, and refutes ones it cannot see contradictory.

spurious_bias_floor

The spurious-bias floor: the expected maximum |agreement − ½| when the best of 2^register_len uncorrelated states is chosen on n samples — ≈ √(L·ln2 / 2n), from the tail of the maximum of 2^L centered binomials. A recovered CorrelationAttack::bias well above this floor is a genuine correlation (a certified combiner leak); at or below it, the register does not measurably leak.

two_adic_complexity

The 2-adic complexity of a bit sequence: ≈ log₂ max(|p|,|q|) for its FCSR rational p/q. Low ⇒ a carry-based keystream (an FCSR / add-with-carry generator); ≈ n/2 for a random sequence.

two_adic_reconstruct

Rational reconstruction of a bit sequence as a 2-adic number. Returns (p, q) with q odd and positive and p/q ≡ Σ sᵢ2ⁱ (mod 2ⁿ) — the shortest FCSR generating the sequence. None when no odd-denominator rational fits (an algorithmically-random sequence has no small FCSR).

unzigzag

The inverse of zigzag.

uvarint_byte_len

The number of bytes write_uvarint would emit for x.

verify_annihilator

Re-check an AnnihilatorWitness against a truth table with zero trust in the producer: the witness is nonzero and vanishes on the required set (support of C, or of C ⊕ 1). Confirms the algebraic-immunity claim independently.

walsh_spectrum

The Walsh spectrum of a Boolean function given as its 2ⁿ-entry truth table: Ŵ(w) = Σₓ (−1)^{C(x) ⊕ ⟨w,x⟩}, the signed correlation of C with every linear function ⟨w,x⟩. Index w is the linear mask (bit i selects variable i). None if the length is not a positive power of two.

write_uvarint

LEB128 unsigned varint: 7 bits per byte, high bit = continuation.

zigzag

Map a signed integer to an unsigned one with small magnitudes near zero (for varint).