//! What holds of the bytes whatever they are (media-identify §7, §8): the signatures found inside
//! them, how their values are spread, and the lags at which they repeat. All of it is integer
//! arithmetic, so that it is the same on every machine.

use super::{MAX_EMBEDDED, SCAN};
use serde_json::{json, Value};

/// The bytes the search for a repeat sees.
pub const PERIOD_SAMPLE: usize = 256 << 10;
/// The longest repeat searched for.
pub const PERIOD_MAX_LAG: usize = 4096;
/// The window whose values are tested for a uniform spread.
pub const WINDOW: usize = 4096;
/// A 4096-byte window is called uniform when the sum of its counts squared is at most this: its
/// chi-square against a uniform spread is then at most 310, the 99th percentile for 255 degrees
/// of freedom (§8.2).
pub const UNIFORM_SUM: u64 = 70_496;
/// The z a lag must reach (§8.3).
pub const PERIOD_Z: u64 = 8;
/// How many times its lags' median absolute excess a lag's excess must reach (§8.4). Data that
/// repeats exactly is not independent from lag to lag, and its noise is many times what `z` assumes;
/// the median measures what it is. For a normal spread this is about 5.3 standard deviations.
pub const PERIOD_MEDIANS: i128 = 8;
/// The lags reported.
pub const MAX_PERIODS: usize = 8;

/// A signature long enough to mean something where it is found by chance, inside a file of
/// [`SCAN`] bytes (§7). `back` is where the structure it belongs to begins, before the bytes.
struct Embed {
    id: &'static str,
    bytes: &'static [u8],
    back: usize,
}

const EMBEDS: &[Embed] = &[
    Embed { id: "png", bytes: b"\x89PNG\r\n\x1a\n", back: 0 },
    Embed { id: "jp2", bytes: b"\x00\x00\x00\x0cjP  \x0d\x0a\x87\x0a", back: 0 },
    Embed { id: "jpegxl", bytes: b"\x00\x00\x00\x0cJXL \x0d\x0a\x87\x0a", back: 0 },
    Embed { id: "mxf", bytes: b"\x06\x0e\x2b\x34\x02\x05\x01\x01\x0d\x01\x02", back: 0 },
    Embed { id: "asf", bytes: b"\x30\x26\xb2\x75\x8e\x66\xcf\x11\xa6\xd9\x00\xaa\x00\x62\xce\x6c", back: 0 },
    Embed { id: "ogg", bytes: b"OggS\x00\x02\x00\x00\x00\x00\x00\x00\x00\x00", back: 0 },
    Embed { id: "flac", bytes: b"fLaC\x00\x00\x00\x22", back: 0 },
    Embed { id: "flac", bytes: b"fLaC\x80\x00\x00\x22", back: 0 },
    Embed { id: "isobmff", bytes: b"ftypisom", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypiso2", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypiso5", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypiso6", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypmp41", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypmp42", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypM4A ", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypM4V ", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypqt  ", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypavif", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypheic", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypcmfc", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypdash", back: 4 },
    Embed { id: "isobmff", bytes: b"ftypmsdh", back: 4 },
];

pub(crate) fn embeds() -> Vec<(&'static str, &'static [u8], usize)> {
    EMBEDS.iter().map(|e| (e.id, e.bytes, e.back)).collect()
}

/// The signatures found inside `scan`, past its beginning, in the order of their offsets; and
/// whether more were found than are reported.
pub fn embedded(scan: &[u8]) -> (Vec<Value>, bool) {
    debug_assert!(scan.len() <= SCAN);
    let mut first = [false; 256];
    for e in EMBEDS {
        first[e.bytes[0] as usize] = true;
    }
    let mut out = Vec::new();
    for i in 0..scan.len() {
        if !first[scan[i] as usize] {
            continue;
        }
        for e in EMBEDS {
            if i > e.back && scan[i..].starts_with(e.bytes) {
                if out.len() == MAX_EMBEDDED {
                    return (out, true);
                }
                out.push(json!({"at": (i - e.back) as u64, "id": e.id}));
            }
        }
    }
    (out, false)
}

fn histogram(b: &[u8]) -> [u64; 256] {
    let mut h = [0u64; 256];
    for &c in b {
        h[c as usize] += 1;
    }
    h
}

fn sum_squares(h: &[u64; 256]) -> u128 {
    h.iter().map(|&c| (c as u128) * (c as u128)).sum()
}

fn isqrt(n: u128) -> u128 {
    if n < 2 {
        return n;
    }
    let mut x = 1u128 << (u128::BITS - n.leading_zeros()).div_ceil(2);
    loop {
        let y = (x + n / x) / 2;
        if y >= x {
            return x;
        }
        x = y;
    }
}

/// The floor of the chi-square of `n` bytes against a uniform spread, from the sum of their counts
/// squared: `256 * sum / n - n`.
pub fn chi_square(sum: u128, n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    (256 * sum / n as u128).saturating_sub(n as u128) as u64
}

/// Whether `b` is text: valid UTF-8, a sequence the scan cut short at its end allowed, with no
/// control character but tab, line feed, form feed and carriage return.
fn is_text(b: &[u8]) -> bool {
    if b.is_empty() {
        return false;
    }
    let valid = match std::str::from_utf8(b) {
        Ok(_) => true,
        Err(e) => e.error_len().is_none(),
    };
    valid && !b.iter().any(|&c| (c < 0x20 && !matches!(c, 9 | 10 | 12 | 13)) || c == 0x7f)
}

/// The lags at which `sample` repeats (§8.3), shortest first.
pub fn periods(sample: &[u8]) -> Vec<Value> {
    let n = sample.len();
    // Four repeats at least, and each neighbour of a lag measured.
    let longest = PERIOD_MAX_LAG.min(n / 4);
    if longest < 2 {
        return Vec::new();
    }
    let sum = sum_squares(&histogram(sample));
    let n2 = (n as u128) * (n as u128);
    // Index by lag: excess[l] is the matches at lag l beyond those its spread of values predicts.
    let mut excess = vec![0i128; longest + 2];
    let mut z = vec![0u64; longest + 2];
    for lag in 1..=longest + 1 {
        let m = n - lag;
        let matches = sample[..m].iter().zip(&sample[lag..]).filter(|(a, b)| a == b).count() as u128;
        let expected = (m as u128 * sum / n2).max(1);
        let e = matches as i128 - expected as i128;
        excess[lag] = e;
        if e > 0 {
            z[lag] = isqrt((e as u128) * (e as u128) / expected) as u64;
        }
    }
    let mut sizes: Vec<i128> = excess[1..].iter().map(|e| e.abs()).collect();
    sizes.sort_unstable();
    let floor = PERIOD_MEDIANS * sizes[sizes.len() / 2];
    let mut out: Vec<usize> = Vec::new();
    for lag in 2..=longest {
        if z[lag] < PERIOD_Z || excess[lag] < floor || excess[lag] <= 2 * excess[lag - 1].max(excess[lag + 1]).max(0) {
            continue;
        }
        // A repeat holds at its double too; a lag beyond what was measured is not asked.
        if 2 * lag <= longest + 1 && z[2 * lag] < PERIOD_Z {
            continue;
        }
        if out.iter().any(|&p| lag % p == 0) {
            continue;
        }
        out.push(lag);
        if out.len() == MAX_PERIODS {
            break;
        }
    }
    out.into_iter().map(|lag| json!({"lag": lag as u64, "z": z[lag]})).collect()
}

/// §8: over the first [`SCAN`] bytes, and for the repeat the first [`PERIOD_SAMPLE`].
pub fn measures(scan: &[u8]) -> Value {
    let h = histogram(scan);
    let sum = sum_squares(&h);
    let (mut windows, mut uniform) = (0u64, 0u64);
    for w in scan.as_chunks::<WINDOW>().0 {
        windows += 1;
        if sum_squares(&histogram(w)) <= UNIFORM_SUM as u128 {
            uniform += 1;
        }
    }
    json!({
        "scanned": scan.len() as u64,
        "distinct_bytes": h.iter().filter(|&&c| c > 0).count() as u64,
        "zero_bytes": h[0],
        "chi_square": chi_square(sum, scan.len() as u64),
        "windows": windows,
        "uniform_windows": uniform,
        "text": is_text(scan),
        "periods": periods(&scan[..scan.len().min(PERIOD_SAMPLE)]),
    })
}

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

    fn noise(n: usize, mut x: u64) -> Vec<u8> {
        (0..n)
            .map(|_| {
                x ^= x << 13;
                x ^= x >> 7;
                x ^= x << 17;
                (x >> 24) as u8
            })
            .collect()
    }

    #[test]
    fn isqrt_is_the_floor() {
        for n in [0u128, 1, 2, 3, 4, 15, 16, 17, 1 << 40, (1 << 80) - 1, u64::MAX as u128 * u64::MAX as u128] {
            let r = isqrt(n);
            assert!(r * r <= n && (r + 1).checked_mul(r + 1).is_none_or(|s| s > n), "{n}");
        }
    }

    #[test]
    fn noise_has_no_period_and_its_windows_are_uniform() {
        let b = noise(64 * WINDOW, 0x9e37_79b9_7f4a_7c15);
        let m = measures(&b);
        assert_eq!(m["periods"], json!([]), "{m}");
        assert!(m["uniform_windows"].as_u64().unwrap() >= 60, "{m}");
        assert_eq!(m["text"], false);
        assert_eq!(m["distinct_bytes"], 256);
    }

    #[test]
    fn a_sync_byte_in_noise_gives_its_period() {
        let mut b = noise(188 * 1000, 0x1234_5678_9abc_def1);
        for p in b.chunks_mut(188) {
            p[0] = 0x47;
        }
        let v = periods(&b);
        assert_eq!(v.len(), 1, "{v:?}");
        assert_eq!(v[0]["lag"], 188);
    }

    #[test]
    fn data_that_repeats_exactly_gives_its_period_and_no_chance_lag() {
        let b = noise(4096, 0xfeed_face_cafe_beef).repeat(64);
        let v = periods(&b);
        assert_eq!(v.len(), 1, "{v:?}");
        assert_eq!(v[0]["lag"], 4096);
    }

    #[test]
    fn a_constant_file_has_no_peak() {
        assert_eq!(periods(&vec![7u8; 100_000]), Vec::<Value>::new());
    }

    #[test]
    fn a_repeated_structure_is_reported_once_not_at_each_multiple() {
        let mut b = noise(512 * 200, 77);
        for p in b.chunks_mut(512) {
            p[..4].copy_from_slice(b"HDR!");
        }
        let v = periods(&b);
        assert_eq!(v.iter().filter(|p| p["lag"].as_u64().unwrap() % 512 == 0).count(), 1, "{v:?}");
    }

    #[test]
    fn text_allows_a_sequence_cut_at_the_end_but_not_a_control_character() {
        assert!(is_text("héllo\n".as_bytes()));
        let cut = "é".as_bytes();
        assert!(is_text(&[b"abc".as_slice(), &cut[..1]].concat()));
        assert!(!is_text(b"abc\x00def"));
        assert!(!is_text(b"\xff\xfe"));
        assert!(!is_text(b""));
    }

    #[test]
    fn an_embedded_signature_is_found_past_the_beginning_and_not_at_it() {
        let mut b = b"\x89PNG\r\n\x1a\n".to_vec();
        b.extend_from_slice(&[0; 20]);
        let at = b.len();
        b.extend_from_slice(b"\x00\x00\x00\x18ftypmp42");
        let (v, capped) = embedded(&b);
        assert!(!capped);
        assert_eq!(v, vec![json!({"at": at as u64, "id": "isobmff"})]);
    }

    #[test]
    fn the_embedded_list_says_when_it_is_cut() {
        let b = b"xxxx\x89PNG\r\n\x1a\n".repeat(MAX_EMBEDDED + 1);
        let (v, capped) = embedded(&b);
        assert_eq!(v.len(), MAX_EMBEDDED);
        assert!(capped);
    }
}
