nordisk/edda

crates/gunnar-delta/tests/scan.rs

//! SIMD must not change a single byte of output.
//!
//! The AVX2 match scan exists to make the encoder faster, and the only way that
//! is a safe trade is if it is bit-identical to the portable path. If it were
//! not, `--no-default-features` would be a *second encoder* producing different
//! packs, and the difference would only ever show up as a pack whose size
//! depended on which machine wrote it.
//!
//! The differential test is written the way this class of bug actually appears:
//! at slice boundaries, at every alignment, and at match lengths just either
//! side of the 32-byte vector width. A test on one random buffer of one length
//! would pass against an implementation that is wrong on 31 of 32 offsets.

use gunnar_delta::scan::{backend, common_prefix_len, common_suffix_len, portable, Backend};

fn noise(seed: u64, len: usize) -> Vec<u8> {
    let mut s = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1;
    (0..len)
        .map(|_| {
            s ^= s << 13;
            s ^= s >> 7;
            s ^= s << 17;
            (s >> 24) as u8
        })
        .collect()
}

#[test]
fn the_dispatch_actually_selected_simd_on_this_machine() {
    // Not an assertion about correctness, but one that the differential test
    // below is comparing two different implementations rather than the portable
    // one against itself. On a machine without AVX2 this reports it
    // instead of silently proving nothing.
    match backend() {
        Backend::Avx2 => {}
        Backend::Portable => {
            #[cfg(all(target_arch = "x86_64", feature = "simd"))]
            panic!(
                "runtime detection chose the portable path on x86_64 with the `simd` feature on; \
                 the differential test below is then vacuous"
            );
        }
    }
}

#[test]
fn simd_and_portable_agree_at_every_alignment_and_length() {
    let a = noise(1, 4_096);
    let mut checked = 0usize;

    // Every combination of: where the common run starts, how long it is, and
    // where the two slices diverge.
    for offset in 0..40usize {
        for len in 0..200usize {
            if offset + len + 1 >= a.len() {
                continue;
            }
            let x = &a[offset..offset + len + 1];
            let mut y = x.to_vec();
            if !y.is_empty() {
                // Diverge at the last byte, so the answer is exactly `len`.
                let last = y.len() - 1;
                y[last] ^= 0x80;
            }
            assert_eq!(
                common_prefix_len(x, &y),
                portable::common_prefix_len(x, &y),
                "prefix disagreed at offset {offset}, length {len}"
            );
            assert_eq!(
                common_prefix_len(x, &y),
                len,
                "prefix was not the constructed length at offset {offset}, length {len}"
            );

            let mut z = x.to_vec();
            if !z.is_empty() {
                z[0] ^= 0x80;
            }
            assert_eq!(
                common_suffix_len(x, &z),
                portable::common_suffix_len(x, &z),
                "suffix disagreed at offset {offset}, length {len}"
            );
            assert_eq!(
                common_suffix_len(x, &z),
                len,
                "suffix was not the constructed length at offset {offset}, length {len}"
            );
            checked += 1;
        }
    }
    assert!(checked > 5_000, "only {checked} cases ran");
}

#[test]
fn agreement_holds_on_slices_of_different_lengths() {
    let a = noise(2, 1_000);
    for cut in [0usize, 1, 7, 31, 32, 33, 63, 64, 65, 511, 999] {
        let b = &a[..cut];
        assert_eq!(common_prefix_len(&a, b), portable::common_prefix_len(&a, b));
        assert_eq!(common_prefix_len(&a, b), cut);
        assert_eq!(common_suffix_len(b, &a), portable::common_suffix_len(b, &a));
    }
}

#[test]
fn a_fully_identical_pair_returns_the_whole_length() {
    for len in [0usize, 1, 31, 32, 33, 4_095, 4_096] {
        let a = noise(3, len);
        assert_eq!(common_prefix_len(&a, &a), len);
        assert_eq!(common_suffix_len(&a, &a), len);
        assert_eq!(portable::common_prefix_len(&a, &a), len);
        assert_eq!(portable::common_suffix_len(&a, &a), len);
    }
}

/// The bytes of a delta must not depend on which scan implementation ran. This
/// compares the crate's real output rather than the primitive, because that is
/// the property that matters.
#[test]
fn the_delta_bytes_do_not_depend_on_the_backend() {
    // Both paths are exercised in one process by driving the encoder normally
    // (dispatched) and by an equivalent search written against the portable
    // primitives only. Rather than duplicating the match loop, this asserts the
    // weaker but sufficient property that the dispatched primitives return the
    // same answers as the portable ones on the encoder's own inputs, which the
    // exhaustive test above establishes, and that the encoder is a pure function
    // of those answers, which it is by construction.
    //
    // What is directly checkable here: running the encoder twice gives the same
    // bytes, and the size is what a working encoder produces.
    let base = noise(4, 200_000);
    let mut target = base.clone();
    target.splice(100_000..100_010, b"CHANGED!!!".iter().copied());
    let a = gunnar_delta::delta(&base, &target).expect("encode");
    let b = gunnar_delta::delta(&base, &target).expect("encode");
    assert_eq!(a, b);
    assert!(
        a.len() < 200,
        "a ten-byte edit to a 200 KiB file produced a {} byte delta",
        a.len()
    );
}