entropyfs 0.1.0

//! Entropy universes: versioned deterministic materialization functions.
//!
//! `E = Universe(version, seed/state, coordinate, requested_range)`.
//! A decoder with the descriptor alone must regenerate the same bytes
//! forever: no network, no hidden corpus, no RNG, no CPU-dependent
//! floating point, no nondeterministic threading. The universe
//! specification is part of the format version
//! (`docs/theory/entropy-medium.md`).
//!
//! v1 ships exactly one control universe: [`UniformXofV1`] — the negative
//! control establishing that a random implicit dictionary cannot create
//! free compression once selector cost is included (ADR-0005 §9).

#![forbid(unsafe_code)]

use crate::core::candidate::{Candidate, CandidateContext, Encoder};
use crate::core::cost::ByteSplit;
use crate::core::representation::UniverseId;
use crate::core::representation::{Representation, Residual};
use crate::entropy::residual::{derive_residuals, residual_data_bytes};

/// Domain separation prefix for the v1 XOF universe (format-part).
const XOF_DOMAIN: &[u8] = b"ENTROPYFS-XOF-V1\0";
/// XOF block size: one BLAKE3-256 output (32 bytes) per counter value.
const XOF_BLOCK: u64 = 32;

/// `UniformXofV1`: a deterministic BLAKE3-based expander.
///
/// ```text
/// stream = concat_i BLAKE3(domain ‖ universe_id ‖ seed ‖ coordinate ‖ i)
/// ```
/// for `i = 0, 1, 2, ...`, each block 32 bytes (one BLAKE3-256 output).
/// `materialize_range` returns `stream[start..end]`.
///
/// This universe is a **negative control**: for arbitrary/random input the
/// residual is ~full size and RAW wins; it wins only when the input is
/// exactly (or almost exactly) the generated stream — honest, exact, and
/// rare. Brute-force seed search is prohibited.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct UniformXofV1;

impl UniformXofV1 {
    /// Universe id.
    pub const ID: UniverseId = UniverseId::UniformXofV1;

    /// Materialize `range` bytes of the stream for `(seed, coordinate)`.
    pub fn materialize_range(
        seed: [u8; 16],
        coordinate: u64,
        range: std::ops::Range<u64>,
    ) -> Vec<u8> {
        assert!(range.start <= range.end, "inverted range");
        let len = range.end - range.start;
        let mut out = Vec::with_capacity(len as usize);
        let first_block = range.start / XOF_BLOCK;
        let skip = (range.start % XOF_BLOCK) as usize;
        let mut block = first_block;
        let mut offset = skip;
        while out.len() < len as usize {
            let b = Self::block(seed, coordinate, block);
            let take = XOF_BLOCK as usize - offset;
            let want = (len as usize - out.len()).min(take);
            out.extend_from_slice(&b[offset..offset + want]);
            offset = 0;
            block += 1;
        }
        out
    }

    /// Compute one XOF block (a single BLAKE3-256 output).
    fn block(seed: [u8; 16], coordinate: u64, index: u64) -> [u8; 32] {
        let mut h = blake3::Hasher::new();
        h.update(XOF_DOMAIN);
        h.update(&[UniverseId::UniformXofV1.tag()]);
        h.update(&seed);
        h.update(&coordinate.to_le_bytes());
        h.update(&index.to_le_bytes());
        *h.finalize().as_bytes()
    }

    /// Generate the full stream of `len` bytes (helper for tests).
    pub fn generate(seed: [u8; 16], coordinate: u64, len: u64) -> Vec<u8> {
        Self::materialize_range(seed, coordinate, 0..len)
    }
}

/// The entropy-reference candidate family: the v1 **negative control**.
///
/// Proposes `ENTROPY_REF { universe: UniformXofV1, seed, coordinate: 0 }`
/// with an exact XOR residual. The seed is derived deterministically from
/// the chunk's content id (no seed search — brute-force over astronomical
/// seed spaces is prohibited, ADR-0005). For arbitrary/random input the
/// residual is ~full size and RAW wins; the candidate wins only when the
/// input is (almost) the generated stream. Every byte of the residual is
/// accounted, so no "free compression" is possible
/// (`docs/theory/entropy-medium.md` §3).
#[derive(Debug, Default)]
pub struct UniverseEncoder;

impl Encoder for UniverseEncoder {
    fn name(&self) -> &'static str {
        "ENTROPY_REF"
    }

    fn encode(&self, input: &[u8], ctx: &CandidateContext<'_>) -> Vec<Candidate> {
        let n = input.len() as u64;
        if n == 0 || n > ctx.limits.max_chunk_size {
            return Vec::new();
        }
        // Deterministic seed derivation from the content id (first 16 bytes)
        // — stored in the descriptor, so the decoder needs nothing else.
        let cid = ctx.content_id;
        let seed: [u8; 16] = cid.as_bytes()[..16].try_into().expect("32 > 16");
        let coordinate: u64 = 0;
        let generated = UniformXofV1::materialize_range(seed, coordinate, 0..n);
        let mut residuals = derive_residuals(input, &generated, ctx.limits.max_fanout);
        // Keep only residuals that are actually small: for random input the
        // diff count is ~n which exceeds the fanout cap or the cost, so the
        // family self-limits. Keep the empty (exact match) residual too.
        residuals.retain(|r| match r {
            Residual::XorSparse { edits, .. } => edits.len() as u64 <= ctx.limits.max_fanout as u64,
            Residual::RangeReplace { .. } => false, // v1: entropy-ref uses XOR only
            Residual::RansCoded { .. } => false,
        });
        let mut out = Vec::new();
        for residual in residuals {
            let rep = Representation::EntropyRef {
                universe: UniverseId::UniformXofV1,
                seed,
                coordinate,
                transform: crate::core::representation::TransformId::Identity,
                residual: residual.clone(),
                len: n,
            };
            if rep.validate(ctx.limits).is_err() {
                continue;
            }
            let split = ByteSplit {
                residual: residual_data_bytes(&residual),
                seed_state: 16 + 8,
                ..Default::default()
            };
            let cost = crate::core::cost::estimate(&rep, &split, 0);
            out.push(Candidate {
                representation: rep,
                objects: Vec::new(),
                cost,
                content_id: ctx.content_id,
            });
        }
        out
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn deterministic() {
        let seed = [7u8; 16];
        let a = UniformXofV1::generate(seed, 42, 100_000);
        let b = UniformXofV1::generate(seed, 42, 100_000);
        assert_eq!(a, b);
    }

    #[test]
    fn range_matches_full() {
        let seed = [3u8; 16];
        let full = UniformXofV1::generate(seed, 9, 100_000);
        // a sub-range must equal the same slice of the full stream
        let sub = UniformXofV1::materialize_range(seed, 9, 10_000..20_000);
        assert_eq!(&full[10_000..20_000], &sub[..]);
        // cross-block boundary: start at a non-multiple of 8192
        let cross = UniformXofV1::materialize_range(seed, 9, 8_000..10_000);
        assert_eq!(&full[8_000..10_000], &cross[..]);
    }

    #[test]
    fn differs_across_coordinates_and_seeds() {
        let s1 = [1u8; 16];
        let s2 = [2u8; 16];
        let a = UniformXofV1::generate(s1, 0, 256);
        let b = UniformXofV1::generate(s1, 1, 256);
        let c = UniformXofV1::generate(s2, 0, 256);
        assert_ne!(a, b);
        assert_ne!(a, c);
    }
}