//! Deltas: an object as copies from an earlier version of it and the bytes
//! that are new, in git's delta format (`git::apply_delta` reads them).
//!
//! A host keeps what landings make this way: a landing writes each folder on
//! its paths again, and the new tree is the old one with an entry or two
//! changed, so its delta is tens of bytes where the tree is kilobytes.

use std::collections::HashMap;

/// Bytes matched at a time: shorter runs in common aren't worth a copy.
const BLOCK: usize = 16;

/// A delta making `target` from `base`, when it's under half the size of
/// `target` (None otherwise: keeping the object whole is as good).
pub fn encode(base: &[u8], target: &[u8]) -> Option<Vec<u8>> {
    if target.len() < 2 * BLOCK || base.len() < BLOCK || base.len() > u32::MAX as usize {
        return None;
    }
    // Where each block of the base starts, by its bytes' hash.
    let mut starts: HashMap<u64, u32> = HashMap::with_capacity(base.len() / BLOCK + 1);
    for off in (0..=base.len() - BLOCK).step_by(BLOCK) {
        starts.entry(hash(&base[off..off + BLOCK])).or_insert(off as u32);
    }
    let mut out = Vec::with_capacity(target.len() / 4 + 16);
    size(&mut out, base.len());
    size(&mut out, target.len());
    let limit = target.len() / 2;
    // Target bytes not copied yet start at `pending`.
    let mut pending = 0;
    let mut at = 0;
    while at + BLOCK <= target.len() {
        let found = starts.get(&hash(&target[at..at + BLOCK])).map(|&o| o as usize).filter(|&o| base[o..o + BLOCK] == target[at..at + BLOCK]);
        let Some(off) = found else {
            at += 1;
            continue;
        };
        // The run in common, as far as it goes both ways.
        let (mut start, mut from) = (at, off);
        while start > pending && from > 0 && base[from - 1] == target[start - 1] {
            start -= 1;
            from -= 1;
        }
        let (mut end, mut to) = (at + BLOCK, off + BLOCK);
        while end < target.len() && to < base.len() && base[to] == target[end] {
            end += 1;
            to += 1;
        }
        insert(&mut out, &target[pending..start]);
        copy(&mut out, from, end - start);
        if out.len() >= limit {
            return None;
        }
        pending = end;
        at = end;
    }
    insert(&mut out, &target[pending..]);
    (out.len() < limit).then_some(out)
}

fn hash(block: &[u8]) -> u64 {
    let a = u64::from_le_bytes(block[..8].try_into().unwrap());
    let b = u64::from_le_bytes(block[8..16].try_into().unwrap());
    (a.wrapping_mul(0x9e37_79b9_7f4a_7c15) ^ b).wrapping_mul(0xc2b2_ae3d_27d4_eb4f)
}

fn size(out: &mut Vec<u8>, mut n: usize) {
    loop {
        let byte = (n & 0x7f) as u8;
        n >>= 7;
        if n == 0 {
            out.push(byte);
            return;
        }
        out.push(byte | 0x80);
    }
}

fn insert(out: &mut Vec<u8>, bytes: &[u8]) {
    for part in bytes.chunks(127) {
        out.push(part.len() as u8);
        out.extend_from_slice(part);
    }
}

fn copy(out: &mut Vec<u8>, mut off: usize, mut len: usize) {
    while len > 0 {
        let n = len.min(0xff_ffff);
        let mut op = 0x80u8;
        let at = out.len();
        out.push(0);
        for i in 0..4 {
            let b = ((off >> (8 * i)) & 0xff) as u8;
            if b != 0 {
                op |= 1 << i;
                out.push(b);
            }
        }
        for i in 0..3 {
            let b = ((n >> (8 * i)) & 0xff) as u8;
            if b != 0 {
                op |= 0x10 << i;
                out.push(b);
            }
        }
        out[at] = op;
        off += n;
        len -= n;
    }
}

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

    struct Rng(u64);
    impl Rng {
        fn next(&mut self) -> u64 {
            self.0 ^= self.0 >> 12;
            self.0 ^= self.0 << 25;
            self.0 ^= self.0 >> 27;
            self.0.wrapping_mul(0x2545f4914f6cdd1d)
        }
        fn below(&mut self, n: usize) -> usize {
            (self.next() % n.max(1) as u64) as usize
        }
        fn bytes(&mut self, n: usize) -> Vec<u8> {
            (0..n).map(|_| self.next() as u8).collect()
        }
    }

    fn check(base: &[u8], target: &[u8]) -> Option<usize> {
        let delta = encode(base, target)?;
        assert_eq!(apply_delta(base, &delta, target.len()).unwrap(), target);
        assert!(delta.len() < target.len() / 2);
        Some(delta.len())
    }

    #[test]
    fn a_folder_with_one_entry_changed_is_a_few_bytes() {
        let entry = |i: usize, v: u8| [vec![1u8, 12, 0], format!("file-{i:06}.rs").into_bytes(), vec![v; 32]].concat();
        let base: Vec<u8> = (0..200).flat_map(|i| entry(i, i as u8)).collect();
        let mut target = base.clone();
        let one = entry(77, 0xee);
        let at = 77 * one.len();
        target[at..at + one.len()].copy_from_slice(&one);
        let n = check(&base, &target).unwrap();
        assert!(n < 64, "{n} bytes for {}", target.len());
        // An entry added in the middle, and one taken out further on.
        let mut moved = base[..at].to_vec();
        moved.extend(entry(1_000_000, 9));
        moved.extend(&base[at..150 * one.len()]);
        moved.extend(&base[151 * one.len()..]);
        assert!(check(&base, &moved).unwrap() < 96);
    }

    #[test]
    fn edits_anywhere_come_back_exactly() {
        let mut rng = Rng(0x1234_5678_9abc_def1);
        let mut made = 0;
        for _ in 0..3000 {
            let n = rng.below(5000);
            let base = if rng.below(3) == 0 { rng.bytes(n) } else { (0..n).map(|i| b"abcdefghij\n"[i % 11]).collect() };
            let mut target = base.clone();
            for _ in 0..rng.below(6) {
                let at = rng.below(target.len() + 1);
                match rng.below(3) {
                    0 => {
                        let n = rng.below(80);
                        let new = rng.bytes(n);
                        target.splice(at..at, new);
                    }
                    1 => {
                        let end = (at + rng.below(200)).min(target.len());
                        target.drain(at..end);
                    }
                    _ => {
                        let end = (at + rng.below(40)).min(target.len());
                        for b in &mut target[at..end] {
                            *b = rng.next() as u8;
                        }
                    }
                }
            }
            if check(&base, &target).is_some() {
                made += 1;
            }
        }
        // Most small edits make a delta.
        assert!(made > 1500, "{made}");
    }

    #[test]
    fn unrelated_or_tiny_objects_stay_whole() {
        let mut rng = Rng(7);
        assert_eq!(encode(&rng.bytes(4000), &rng.bytes(4000)), None);
        assert_eq!(encode(b"short", b"shorter"), None);
        assert_eq!(encode(&[], &rng.bytes(100)), None);
    }
}