//! The registered watermark scheme of the second marking layer, `wai-mark:tent64`
//! (extensions/synthesis.md §7.5).
//!
//! An imperceptible mark in the luma of RGB8 frames, embedded by a pinned integer
//! derivation and read back with no key:
//!
//! - **Grid.** Each frame is cut into 64 × 64 cells by the edges `⌊i·W/64⌋` and `⌊j·H/64⌋`,
//!   so the grid follows the picture through any rescale or change of aspect.
//! - **Pattern.** In each cell a separable **tent** checkerboard: a weight `ω` that is the
//!   product of a horizontal and a vertical tent, positive on one half of the cell and
//!   negative on the other in each direction, zero-mean, so a change of brightness leaves
//!   the cell's statistic `s = Σ ω·Y` unchanged and a change of contrast scales it.
//! - **Layout.** A public stream (SHA-256 of a fixed label and a counter) shuffles the 4096
//!   cells, gives each a sign, and draws a mask over the code's 248 bits; bit `j` is carried
//!   by 16 cells scattered over the frame.
//! - **Code.** The 8-byte payload is a codeword of the binary BCH code of length 255 and
//!   designed distance 59 (it corrects 29 errors), shortened to 248 bits.
//! - **Embedding.** For each bit, the least amplitude `a ≤ 8` whose pattern gives the bit's
//!   statistic the sign the masked codeword asks for, with a margin of 3/2 of the bit's
//!   weight mass; the same delta is added to R, G and B, clamped. Integer throughout, so the
//!   marked frames are a pure function of the unmarked frames and the payload.
//! - **Detection.** For each of the 8 orientations (the quarter turns and mirrors), the bits'
//!   statistics summed over the frames are read as signs, unmasked and decoded; the first
//!   orientation that decodes to a payload whose first byte is a class code (0 to 3) gives it.

use serde_json::{json, Value};
use sha2::{Digest, Sha256};
use std::sync::OnceLock;

use crate::jcs::jcs;

pub mod sync;

/// The scheme's term (§7.4).
pub const SCHEME: &str = "wai-mark:tent64";
/// Cells along each side of a frame.
pub const GRID: usize = 64;
/// Cells in a frame.
pub const CELLS: usize = GRID * GRID;
/// The code's length, and so the bits a frame carries.
pub const CODE_BITS: usize = 248;
/// The parity bits of the code.
pub const PARITY_BITS: usize = CODE_BITS - 64;
/// Cells that carry each bit.
pub const CELLS_PER_BIT: usize = 16;
/// The errors the code corrects.
pub const CORRECTS: usize = 29;
/// The largest amplitude the embedding uses, in luma levels at a cell's peak.
pub const AMPLITUDE: i64 = 12;
/// The margin a bit's statistic is given, as a fraction of its weight mass.
pub const MARGIN: (i64, i64) = (3, 2);
/// The least width and height of a frame.
pub const MIN_SIDE: u64 = 128;
/// The most bytes one frame holds.
pub const MAX_FRAME_BYTES: u64 = 1 << 28;
/// The orientations the detector tries.
pub const ORIENTATIONS: u8 = 8;
/// The largest code a payload's first byte holds (the class codes of §7.2).
pub const CLASS_MAX: u8 = 3;
/// The label of the layout's stream.
pub const STREAM_LABEL: &[u8] = b"wai-mark:tent64 stream";
/// The code's generator polynomial, the coefficient of `x^184` first, in hexadecimal.
pub const GENERATOR_HEX: &str = "140a722a1a468d36d87a25364e685922a1e56fd1a478c1d";

/// The scheme's definition (§7.5): the parameters its text pins, as a JSON value.
pub fn definition() -> Value {
    json!({
        "scheme": SCHEME,
        "specification": "extensions/synthesis.md section 7.5",
        "media": ["image", "video"],
        "sample": "RGB8",
        "min_width": MIN_SIDE,
        "min_height": MIN_SIDE,
        "max_frame_bytes": MAX_FRAME_BYTES,
        "luma": [77, 150, 29, 128, 8],
        "grid": GRID,
        "pattern": "tent",
        "stream": std::str::from_utf8(STREAM_LABEL).expect("ASCII"),
        "field": "11d",
        "code": [255, 71, CORRECTS],
        "length": CODE_BITS,
        "generator": GENERATOR_HEX,
        "cells_per_bit": CELLS_PER_BIT,
        "amplitude": AMPLITUDE,
        "margin": [MARGIN.0, MARGIN.1],
        "orientations": ORIENTATIONS,
        "class_max": CLASS_MAX,
    })
}

/// The definition's bytes: its JCS text.
pub fn definition_text() -> String {
    jcs(&definition()).expect("a definition in the subset")
}

/// The scheme's digest: SHA-256 of its definition's bytes (§7.2's `scheme_digest`).
pub fn digest() -> [u8; 32] {
    Sha256::digest(definition_text().as_bytes()).into()
}

// ---------------------------------------------------------------------------------------
// The layout: the stream, the shuffle, the signs and the mask
// ---------------------------------------------------------------------------------------

/// The public layout every frame shares.
pub struct Layout {
    /// `perm[16·j + n]` is the `n`-th cell of bit `j`; the last 128 entries carry nothing.
    pub perm: Vec<u16>,
    /// Each cell's sign, +1 or −1.
    pub sign: Vec<i64>,
    /// The mask over the code's bits.
    pub mask: [u8; CODE_BITS],
    /// The bit a cell carries, or `None`.
    pub bit_of_cell: Vec<Option<u16>>,
}

/// The stream's 32-bit words: SHA-256 of the label and a big-endian `u32` counter, from 0,
/// each digest read as eight big-endian words.
pub fn stream() -> impl Iterator<Item = u32> {
    stream_of(STREAM_LABEL)
}

/// A scheme's stream under its own label (§7.5.3, §7.9.2).
pub fn stream_of(label: &'static [u8]) -> impl Iterator<Item = u32> {
    (0u32..).flat_map(move |i| {
        let d: [u8; 32] = Sha256::new().chain_update(label).chain_update(i.to_be_bytes()).finalize().into();
        (0..8).map(move |o| u32::from_be_bytes(d[o * 4..o * 4 + 4].try_into().expect("four bytes")))
    })
}

/// The layout, built once.
pub fn layout() -> &'static Layout {
    static L: OnceLock<Layout> = OnceLock::new();
    L.get_or_init(|| {
        let mut r = stream();
        let mut perm: Vec<u16> = (0..CELLS as u16).collect();
        for i in (1..CELLS).rev() {
            let j = r.next().expect("an endless stream") as usize % (i + 1);
            perm.swap(i, j);
        }
        let sign: Vec<i64> = (0..CELLS).map(|_| if r.next().expect("an endless stream") & 1 == 0 { 1 } else { -1 }).collect();
        let mut mask = [0u8; CODE_BITS];
        for m in mask.iter_mut() {
            *m = (r.next().expect("an endless stream") & 1) as u8;
        }
        let mut bit_of_cell = vec![None; CELLS];
        for j in 0..CODE_BITS {
            for n in 0..CELLS_PER_BIT {
                bit_of_cell[perm[CELLS_PER_BIT * j + n] as usize] = Some(j as u16);
            }
        }
        Layout { perm, sign, mask, bit_of_cell }
    })
}

// ---------------------------------------------------------------------------------------
// The code: BCH(255, 71) over GF(2^8), shortened to (248, 64)
// ---------------------------------------------------------------------------------------

struct Gf {
    exp: [u8; 510],
    log: [u16; 256],
}

fn gf() -> &'static Gf {
    static G: OnceLock<Gf> = OnceLock::new();
    G.get_or_init(|| {
        let mut exp = [0u8; 510];
        let mut log = [0u16; 256];
        let mut x: u16 = 1;
        for (i, e) in exp.iter_mut().take(255).enumerate() {
            *e = x as u8;
            log[x as usize] = i as u16;
            x <<= 1;
            if x & 0x100 != 0 {
                x ^= 0x11d;
            }
        }
        let (lo, hi) = exp.split_at_mut(255);
        hi.copy_from_slice(lo);
        Gf { exp, log }
    })
}

fn mul(a: u8, b: u8) -> u8 {
    if a == 0 || b == 0 {
        return 0;
    }
    let g = gf();
    g.exp[g.log[a as usize] as usize + g.log[b as usize] as usize]
}

/// `α^e` for any integer `e`.
fn alpha(e: i64) -> u8 {
    gf().exp[e.rem_euclid(255) as usize]
}

/// The generator polynomial as computed from its definition: the least common multiple of
/// the minimal polynomials of `α^1 … α^58` over GF(2). Bit `d` is the coefficient of `x^d`.
pub fn generator_bits() -> Vec<u8> {
    let mut g: Vec<u8> = vec![1];
    let mut seen: Vec<Vec<usize>> = Vec::new();
    for i in 1..=2 * CORRECTS {
        let mut coset = Vec::new();
        let mut j = i % 255;
        while !coset.contains(&j) {
            coset.push(j);
            j = (2 * j) % 255;
        }
        let mut key = coset.clone();
        key.sort_unstable();
        if seen.contains(&key) {
            continue;
        }
        seen.push(key);
        // The minimal polynomial: the product of (x − α^j) over the coset.
        let mut p: Vec<u8> = vec![1];
        for &j in &coset {
            let r = alpha(j as i64);
            let mut q = vec![0u8; p.len() + 1];
            for (d, &c) in p.iter().enumerate() {
                q[d + 1] ^= c;
                q[d] ^= mul(c, r);
            }
            p = q;
        }
        assert!(p.iter().all(|&c| c <= 1), "a minimal polynomial is binary");
        let mut out = vec![0u8; g.len() + p.len() - 1];
        for (a, &ga) in g.iter().enumerate() {
            for (b, &pb) in p.iter().enumerate() {
                out[a + b] ^= ga & pb;
            }
        }
        g = out;
    }
    g
}

fn generator() -> &'static [u8] {
    static G: OnceLock<Vec<u8>> = OnceLock::new();
    G.get_or_init(|| {
        let g = generator_bits();
        assert_eq!(g.len(), PARITY_BITS + 1);
        g
    })
}

/// The codeword of a payload: bit `j` is the coefficient of `x^(247 − j)`; bits 0 to 63
/// are the payload's, the most significant bit of its first byte first, and the rest the
/// remainder of `m(x)·x^184` divided by the generator.
pub fn encode(payload: &[u8; 8]) -> [u8; CODE_BITS] {
    let g = generator();
    let mut word = [0u8; CODE_BITS];
    for (j, w) in word.iter_mut().take(64).enumerate() {
        *w = (payload[j / 8] >> (7 - j % 8)) & 1;
    }
    let mut r = word;
    for j in 0..64 {
        if r[j] == 1 {
            // Subtract g(x)·x^(183 − j): its x^184 coefficient sits at bit j.
            for d in 0..=PARITY_BITS {
                r[j + PARITY_BITS - d] ^= g[d];
            }
        }
    }
    word[64..].copy_from_slice(&r[64..]);
    word
}

/// Bounded-distance decoding: the payload of the codeword within 29 bits of `word`, and
/// the bits that differ, or `None` where there is none or its first byte is above 3.
pub fn decode(word: &[u8; CODE_BITS]) -> Option<([u8; 8], usize)> {
    let mut c = *word;
    let syndromes = |c: &[u8; CODE_BITS]| -> Vec<u8> {
        (1..=2 * CORRECTS as i64)
            .map(|i| c.iter().enumerate().filter(|&(_, &b)| b == 1).fold(0u8, |s, (j, _)| s ^ alpha(i * (CODE_BITS - 1 - j) as i64)))
            .collect()
    };
    let s = syndromes(&c);
    let mut errors = 0;
    if s.iter().any(|&x| x != 0) {
        // The error locator Λ: the shortest linear recurrence the syndromes satisfy.
        let g = gf();
        let (mut lam, mut b) = (vec![1u8], vec![1u8]);
        let (mut l, mut m, mut bd) = (0usize, 1usize, 1u8);
        for n in 0..2 * CORRECTS {
            let mut d = s[n];
            for i in 1..=l.min(lam.len() - 1) {
                d ^= mul(lam[i], s[n - i]);
            }
            if d == 0 {
                m += 1;
                continue;
            }
            let coef = mul(d, g.exp[(255 - g.log[bd as usize] as usize) % 255]);
            let prev = lam.clone();
            if lam.len() < b.len() + m {
                lam.resize(b.len() + m, 0);
            }
            for (i, &bv) in b.iter().enumerate() {
                lam[i + m] ^= mul(coef, bv);
            }
            if 2 * l <= n {
                l = n + 1 - l;
                b = prev;
                bd = d;
                m = 1;
            } else {
                m += 1;
            }
        }
        while lam.len() > 1 && lam[lam.len() - 1] == 0 {
            lam.pop();
        }
        if lam.len() - 1 != l || l > CORRECTS {
            return None;
        }
        // The locator's roots: Λ(α^−e) = 0 marks an error at x^e.
        let roots: Vec<usize> = (0..255)
            .filter(|&e| lam.iter().enumerate().fold(0u8, |v, (i, &co)| v ^ mul(co, alpha(-(e as i64) * i as i64))) == 0)
            .collect();
        if roots.len() != l || roots.iter().any(|&e| e >= CODE_BITS) {
            return None;
        }
        for e in roots {
            c[CODE_BITS - 1 - e] ^= 1;
        }
        if syndromes(&c).iter().any(|&x| x != 0) {
            return None;
        }
        errors = l;
    }
    let mut payload = [0u8; 8];
    for j in 0..64 {
        payload[j / 8] |= c[j] << (7 - j % 8);
    }
    (payload[0] <= CLASS_MAX).then_some((payload, errors))
}

// ---------------------------------------------------------------------------------------
// Frames, the grid and the pattern
// ---------------------------------------------------------------------------------------

/// Whether the scheme admits frames of this size and count (§7.5.1).
pub fn admits(width: u64, height: u64, frames: u64) -> bool {
    width >= MIN_SIDE
        && height >= MIN_SIDE
        && frames >= 1
        && width.checked_mul(height).and_then(|p| p.checked_mul(3)).is_some_and(|b| b <= MAX_FRAME_BYTES)
        && (width * height * 3).checked_mul(frames).is_some_and(|b| b <= crate::jcs::MAX_INTEGER)
}

/// `(77·R + 150·G + 29·B + 128) >> 8`.
pub fn luma(r: u8, g: u8, b: u8) -> i64 {
    (77 * r as i64 + 150 * g as i64 + 29 * b as i64 + 128) >> 8
}

/// The tent over a span of `l` samples at position `u`: `sgn(c)·(l − |2|c| − l|)` with
/// `c = 2u + 1 − l`.
pub fn tent(u: i64, l: i64) -> i64 {
    let c = 2 * u + 1 - l;
    c.signum() * (l - (2 * c.abs() - l).abs())
}

/// One axis of the grid: for each sample, its cell's index, the tent there and the
/// cell's length.
struct Axis {
    cell: Vec<usize>,
    tent: Vec<i64>,
    len: Vec<i64>,
    edges: Vec<usize>,
}

impl Axis {
    fn new(n: usize) -> Axis {
        let edges: Vec<usize> = (0..=GRID).map(|i| i * n / GRID).collect();
        let (mut cell, mut tentv, mut len) = (Vec::with_capacity(n), Vec::with_capacity(n), Vec::with_capacity(n));
        for i in 0..GRID {
            let l = (edges[i + 1] - edges[i]) as i64;
            for x in edges[i]..edges[i + 1] {
                cell.push(i);
                tentv.push(tent((x - edges[i]) as i64, l));
                len.push(l);
            }
        }
        Axis { cell, tent: tentv, len, edges }
    }
}

/// The statistics of each cell of one luma plane of `w` × `h`: `s = Σ ω·Y`.
fn cell_statistics(y: &[i64], w: usize, h: usize) -> Vec<i64> {
    let (ax, ay) = (Axis::new(w), Axis::new(h));
    let mut s = vec![0i64; CELLS];
    for row in 0..h {
        let (cy, fy) = (ay.cell[row], ay.tent[row]);
        // Each row's sums per column cell first, then weighted by the row's tent.
        let mut acc = [0i64; GRID];
        for col in 0..w {
            acc[ax.cell[col]] += ax.tent[col] * y[row * w + col];
        }
        for (cx, a) in acc.iter().enumerate() {
            s[cy * GRID + cx] += fy * a;
        }
    }
    s
}

/// The bits' statistics of one luma plane: `T_j = Σ ε_k·s_k` over bit `j`'s cells.
fn bit_statistics(lay: &Layout, y: &[i64], w: usize, h: usize) -> [i64; CODE_BITS] {
    let s = cell_statistics(y, w, h);
    let mut t = [0i64; CODE_BITS];
    for (j, tj) in t.iter_mut().enumerate() {
        for n in 0..CELLS_PER_BIT {
            let k = lay.perm[CELLS_PER_BIT * j + n] as usize;
            *tj += lay.sign[k] * s[k];
        }
    }
    t
}

fn luma_plane(rgb: &[u8]) -> Vec<i64> {
    rgb.as_chunks::<3>().0.iter().map(|p| luma(p[0], p[1], p[2])).collect()
}

/// The delta at a pixel of weight `z` (the pattern's sign times `ω`) in a cell of area `nu`
/// at amplitude `a`: `a·z/ν` rounded to the nearest integer, halves away from zero.
pub fn delta(a: i64, z: i64, nu: i64) -> i64 {
    z.signum() * ((2 * a * z.abs() + nu) / (2 * nu))
}

/// What embedding one frame did.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct FrameReport {
    /// Bits whose margin the largest amplitude did not reach.
    pub short: usize,
    /// The amplitude of each bit.
    pub amplitudes: Vec<u8>,
}

/// The marked frames of `frames` frames of `w` × `h` RGB8 under `payload` (§7.5.4), and
/// what embedding each frame did. The caller checks [`admits`].
pub fn embed(unmarked: &[u8], w: usize, h: usize, frames: usize, payload: &[u8; 8]) -> (Vec<u8>, Vec<FrameReport>) {
    embed_with(layout(), unmarked, w, h, frames, payload)
}

/// §7.5.4's embedding under a layout: the cells of each bit, their signs and the mask.
pub fn embed_with(lay: &Layout, unmarked: &[u8], w: usize, h: usize, frames: usize, payload: &[u8; 8]) -> (Vec<u8>, Vec<FrameReport>) {
    let code = encode(payload);
    let sigma: Vec<i64> = (0..CODE_BITS).map(|j| if code[j] ^ lay.mask[j] == 1 { 1 } else { -1 }).collect();
    let (ax, ay) = (Axis::new(w), Axis::new(h));
    let fb = w * h * 3;
    let mut out = unmarked.to_vec();
    let mut reports = Vec::with_capacity(frames);
    for f in 0..frames {
        let frame = &unmarked[f * fb..(f + 1) * fb];
        let dst = &mut out[f * fb..(f + 1) * fb];
        let mut report = FrameReport { short: 0, amplitudes: Vec::with_capacity(CODE_BITS) };
        for (j, &sg) in sigma.iter().enumerate() {
            let cells: Vec<usize> = (0..CELLS_PER_BIT).map(|n| lay.perm[CELLS_PER_BIT * j + n] as usize).collect();
            // The bit's weight mass and its statistic at amplitude a.
            let mut q = 0i64;
            for &k in &cells {
                let (cx, cy) = (k % GRID, k / GRID);
                for row in ay.edges[cy]..ay.edges[cy + 1] {
                    for col in ax.edges[cx]..ax.edges[cx + 1] {
                        q += (ax.tent[col] * ay.tent[row]).abs();
                    }
                }
            }
            let at = |a: i64, apply: Option<&mut [u8]>| -> i64 {
                let mut t = 0i64;
                let mut apply = apply;
                for &k in &cells {
                    let (cx, cy) = (k % GRID, k / GRID);
                    let eps = lay.sign[k];
                    for row in ay.edges[cy]..ay.edges[cy + 1] {
                        for col in ax.edges[cx]..ax.edges[cx + 1] {
                            let omega = ax.tent[col] * ay.tent[row];
                            let d = delta(a, sg * eps * omega, ax.len[col] * ay.len[row]);
                            let p = (row * w + col) * 3;
                            let px = [0, 1, 2].map(|c| (frame[p + c] as i64 + d).clamp(0, 255) as u8);
                            t += eps * omega * luma(px[0], px[1], px[2]);
                            if let Some(dst) = apply.as_deref_mut() {
                                dst[p..p + 3].copy_from_slice(&px);
                            }
                        }
                    }
                }
                t
            };
            let chosen = (0..=AMPLITUDE).find(|&a| MARGIN.1 * sg * at(a, None) >= MARGIN.0 * q);
            if chosen.is_none() {
                report.short += 1;
            }
            let a = chosen.unwrap_or(AMPLITUDE);
            at(a, Some(dst));
            report.amplitudes.push(a as u8);
        }
        reports.push(report);
    }
    (out, reports)
}

/// The luma plane of a frame seen in orientation `o` (§7.5.5): transposed when `o & 4`,
/// then its rows reversed when `o & 2`, then its columns reversed when `o & 1`. Returns the
/// plane and its width and height.
pub fn orient(y: &[i64], w: usize, h: usize, o: u8) -> (Vec<i64>, usize, usize) {
    let (ow, oh) = if o & 4 != 0 { (h, w) } else { (w, h) };
    let mut out = vec![0i64; w * h];
    for oy in 0..oh {
        for ox in 0..ow {
            let x1 = if o & 1 != 0 { ow - 1 - ox } else { ox };
            let y1 = if o & 2 != 0 { oh - 1 - oy } else { oy };
            let (sx, sy) = if o & 4 != 0 { (y1, x1) } else { (x1, y1) };
            out[oy * ow + ox] = y[sy * w + sx];
        }
    }
    (out, ow, oh)
}

/// What the detector read.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Detected {
    pub payload: [u8; 8],
    /// The orientation it decoded in.
    pub orientation: u8,
    /// The bits the code corrected.
    pub errors: usize,
}

/// The word the detector reads in one orientation: the sign of each bit's statistic summed
/// over the frames, unmasked.
pub fn read_word(samples: &[u8], w: usize, h: usize, frames: usize, o: u8) -> [u8; CODE_BITS] {
    read_word_with(layout(), samples, w, h, frames, o)
}

/// [`read_word`] under a layout.
pub fn read_word_with(lay: &Layout, samples: &[u8], w: usize, h: usize, frames: usize, o: u8) -> [u8; CODE_BITS] {
    let fb = w * h * 3;
    let mut t = [0i64; CODE_BITS];
    for f in 0..frames {
        let (y, ow, oh) = orient(&luma_plane(&samples[f * fb..(f + 1) * fb]), w, h, o);
        let ft = bit_statistics(lay, &y, ow, oh);
        for j in 0..CODE_BITS {
            t[j] += ft[j];
        }
    }
    let mut word = [0u8; CODE_BITS];
    for j in 0..CODE_BITS {
        word[j] = (t[j] > 0) as u8 ^ lay.mask[j];
    }
    word
}

/// The key-free detector (§7.5.5): the payload of the first orientation that decodes, or
/// `None`. Frames the scheme does not admit carry no mark.
pub fn detect(samples: &[u8], w: usize, h: usize, frames: usize) -> Option<Detected> {
    if !admits(w as u64, h as u64, frames as u64) || samples.len() != w * h * 3 * frames {
        return None;
    }
    (0..ORIENTATIONS).find_map(|o| decode(&read_word(samples, w, h, frames, o)).map(|(payload, errors)| Detected { payload, orientation: o, errors }))
}

/// The sum of squared differences the embedding can make in one frame at most: every
/// carrying cell at the largest amplitude, in all three channels, with no clamp (§7.5.6).
pub fn floor_sse(w: usize, h: usize) -> u64 {
    floor_sse_with(layout(), w, h)
}

/// [`floor_sse`] under a layout.
pub fn floor_sse_with(lay: &Layout, w: usize, h: usize) -> u64 {
    let (ax, ay) = (Axis::new(w), Axis::new(h));
    let mut sse = 0u64;
    for row in 0..h {
        for col in 0..w {
            if lay.bit_of_cell[ay.cell[row] * GRID + ax.cell[col]].is_none() {
                continue;
            }
            let d = delta(AMPLITUDE, ax.tent[col] * ay.tent[row], ax.len[col] * ay.len[row]);
            sse += 3 * (d * d) as u64;
        }
    }
    sse
}

/// SHA-256 of a buffer.
pub fn sha256(b: &[u8]) -> [u8; 32] {
    Sha256::digest(b).into()
}

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

    fn hexs(b: &[u8]) -> String {
        b.iter().map(|x| format!("{x:02x}")).collect()
    }

    #[test]
    fn the_generator_is_the_definitions() {
        let g = generator_bits();
        assert_eq!(g.len(), 185, "degree 184: k = 71");
        let mut v: u128 = 0;
        let mut hi: u128 = 0;
        for (d, &b) in g.iter().enumerate() {
            if d < 128 {
                v |= (b as u128) << d;
            } else {
                hi |= (b as u128) << (d - 128);
            }
        }
        let hex = format!("{hi:x}{v:032x}");
        assert_eq!(hex, GENERATOR_HEX);
    }

    #[test]
    fn the_code_corrects_29_errors_and_no_more_is_claimed() {
        let mut r = stream();
        for trial in 0..64 {
            let mut p = [0u8; 8];
            for b in p.iter_mut() {
                *b = r.next().unwrap() as u8;
            }
            p[0] &= 3;
            let c = encode(&p);
            assert_eq!(decode(&c), Some((p, 0)));
            let mut e = c;
            let n = trial % 30;
            let mut flipped = Vec::new();
            while flipped.len() < n {
                let pos = r.next().unwrap() as usize % CODE_BITS;
                if !flipped.contains(&pos) {
                    flipped.push(pos);
                    e[pos] ^= 1;
                }
            }
            assert_eq!(decode(&e), Some((p, n)), "trial {trial}: {n} errors");
        }
    }

    #[test]
    fn a_class_above_3_is_no_payload() {
        let p = [4u8, 1, 2, 3, 4, 5, 6, 7];
        assert_eq!(decode(&encode(&p)), None);
    }

    #[test]
    fn the_mask_and_its_complement_decode_to_nothing() {
        let lay = layout();
        assert_eq!(decode(&lay.mask), None);
        let mut c = lay.mask;
        for b in c.iter_mut() {
            *b ^= 1;
        }
        assert_eq!(decode(&c), None);
    }

    #[test]
    fn the_layout_is_a_permutation() {
        let lay = layout();
        let mut p = lay.perm.clone();
        p.sort_unstable();
        assert!(p.iter().enumerate().all(|(i, &v)| v as usize == i));
        assert_eq!(lay.bit_of_cell.iter().filter(|b| b.is_none()).count(), CELLS - CODE_BITS * CELLS_PER_BIT);
    }

    #[test]
    fn the_tent_is_odd_and_bounded() {
        for l in 2..40i64 {
            let v: Vec<i64> = (0..l).map(|u| tent(u, l)).collect();
            assert_eq!(v.iter().sum::<i64>(), 0, "zero-mean over {l}");
            assert!(v.iter().all(|x| x.abs() <= l));
            for u in 0..l as usize {
                assert_eq!(v[u], -v[l as usize - 1 - u]);
            }
        }
    }

    /// A frame of smooth structure and texture, from the stream.
    fn picture(w: usize, h: usize, seed: u32) -> Vec<u8> {
        let mut r = stream().skip(seed as usize * 7);
        let mut px = Vec::with_capacity(w * h * 3);
        let a = r.next().unwrap() as i64 % 7 + 3;
        for y in 0..h {
            for x in 0..w {
                let base = ((x as i64 * a + y as i64 * 3) % 200) + 20;
                for c in 0..3 {
                    let n = (r.next().unwrap() % 9) as i64 - 4;
                    px.push((base + n + c as i64 * 5).clamp(0, 255) as u8);
                }
            }
        }
        px
    }

    #[test]
    fn a_marked_frame_carries_its_payload_and_only_the_derivation_changes_it() {
        let (w, h) = (200, 136);
        let unmarked = picture(w, h, 1);
        let payload = [3u8, 0xde, 0xad, 0xbe, 0xef, 0x01, 0x02, 0x03];
        let (marked, rep) = embed(&unmarked, w, h, 1, &payload);
        assert_eq!(rep.len(), 1);
        let d = detect(&marked, w, h, 1).expect("a mark");
        assert_eq!((d.payload, d.orientation), (payload, 0));
        // The embedding is a function: the same inputs give the same bytes.
        assert_eq!(embed(&unmarked, w, h, 1, &payload).0, marked);
        // No pixel moved further than the amplitude.
        assert!(unmarked.iter().zip(&marked).all(|(a, b)| (*a as i64 - *b as i64).abs() <= AMPLITUDE));
        // Unmarked, it reads nothing.
        assert_eq!(detect(&unmarked, w, h, 1), None);
    }

    #[test]
    fn every_orientation_is_read() {
        let (w, h) = (160, 128);
        let payload = [3u8, 9, 8, 7, 6, 5, 4, 3];
        let (marked, _) = embed(&picture(w, h, 2), w, h, 1, &payload);
        for o in 0..ORIENTATIONS {
            // The content that orientation o turns back into the marked frame: content
            // pixel S(x, y) is the frame's (x, y), S as `orient` reads it.
            let (ow, oh) = if o & 4 != 0 { (h, w) } else { (w, h) };
            let mut c = vec![0u8; w * h * 3];
            for y in 0..h {
                for x in 0..w {
                    let x1 = if o & 1 != 0 { w - 1 - x } else { x };
                    let y1 = if o & 2 != 0 { h - 1 - y } else { y };
                    let (sx, sy) = if o & 4 != 0 { (y1, x1) } else { (x1, y1) };
                    c[(sy * ow + sx) * 3..(sy * ow + sx) * 3 + 3].copy_from_slice(&marked[(y * w + x) * 3..(y * w + x) * 3 + 3]);
                }
            }
            let d = detect(&c, ow, oh, 1).unwrap_or_else(|| panic!("orientation {o}"));
            assert_eq!(d.payload, payload, "orientation {o}");
            assert_eq!(d.orientation, o);
        }
    }

    #[test]
    fn the_definition_is_stable() {
        assert_eq!(hexs(&digest()).len(), 64);
        assert!(definition_text().starts_with("{\"amplitude\":12,"));
    }
}
