nordisk/znippy-zoomies

lgz/tests/simd_filter.rs

//! Every CPU version of the bit-level candidate filter returns exactly the
//! portable version's bitmasks: on random words, and over the real layers
//! (`LGZ_LAYERS`). A version the CPU lacks is skipped (and says so).

use lgz::bitsplit::simd::{self, Impl};

fn xorshift(x: &mut u64) -> u64 {
    *x ^= *x << 13;
    *x ^= *x >> 7;
    *x ^= *x << 17;
    *x
}

fn available() -> Vec<Impl> {
    static SAY: std::sync::Once = std::sync::Once::new();
    SAY.call_once(|| {
        for i in Impl::ALL {
            if !i.available() {
                eprintln!("{i:?}: not on this CPU, skipped");
            }
        }
    });
    Impl::ALL
        .iter()
        .copied()
        .filter(|i| i.available())
        .collect()
}

#[test]
fn every_version_matches_portable_on_random_words() {
    let mut x = 0x9e37_79b9_7f4a_7c15u64;
    for _ in 0..200_000 {
        let mut w = [0u64; simd::WORDS];
        for v in &mut w {
            *v = xorshift(&mut x);
            // DEFLATE-like density of zero runs, so candidates actually occur
            if x & 3 == 0 {
                *v &= xorshift(&mut x);
            }
        }
        let want = simd::masks_with(Impl::Portable, &w);
        for i in available() {
            assert_eq!(simd::masks_with(i, &w), want, "{i:?} on {w:x?}");
        }
    }
}

#[test]
fn portable_matches_the_one_window_reference() {
    // the lane masks equal candidates64 over the 128-bit window at each lane
    let mut x = 0x2545_f491_4f6c_dd1du64;
    for _ in 0..50_000 {
        let mut w = [0u64; simd::WORDS];
        for v in &mut w {
            *v = xorshift(&mut x);
        }
        let m = simd::masks_with(Impl::Portable, &w);
        for (j, &mj) in m.iter().enumerate() {
            let win = w[j] as u128 | (w[j + 1] as u128) << 64;
            assert_eq!(mj, lgz::bitsplit::candidates64(win), "lane {j}");
        }
    }
}

#[test]
fn every_version_matches_portable_on_the_real_layers() {
    let Some(dir) = std::env::var_os("LGZ_LAYERS") else {
        eprintln!("LGZ_LAYERS unset: skipped");
        return;
    };
    let impls = available();
    for e in std::fs::read_dir(dir).unwrap() {
        let p = e.unwrap().path();
        if p.extension().is_none_or(|x| x != "gz") {
            continue;
        }
        let d = std::fs::read(&p).unwrap();
        let step = simd::WORDS * 8;
        let mut off = 0;
        while off + step <= d.len() {
            let mut w = [0u64; simd::WORDS];
            for (k, v) in w.iter_mut().enumerate() {
                *v = u64::from_le_bytes(d[off + 8 * k..off + 8 * k + 8].try_into().unwrap());
            }
            let want = simd::masks_with(Impl::Portable, &w);
            for &i in &impls {
                assert_eq!(
                    simd::masks_with(i, &w),
                    want,
                    "{i:?} at {} byte {off}",
                    p.display()
                );
            }
            off += step * 7; // a stride, not every byte: the layers are big
        }
    }
}

#[test]
fn the_dispatched_version_finds_the_same_block_starts() {
    // the full search, per forced version, gives the portable answer
    let mut x = 77u64;
    let data: Vec<u8> = {
        let mut v = Vec::new();
        while v.len() < 8 << 20 {
            let r = xorshift(&mut x);
            let piece: Vec<u8> = match r % 5 {
                0 => b"usr/lib/python3.12/".to_vec(),
                1 => b"site-packages\n".to_vec(),
                2 => b"share/locale/".to_vec(),
                3 => b"bin/".to_vec(),
                _ => vec![(r >> 8) as u8, (r >> 16) as u8],
            };
            v.extend_from_slice(&piece);
        }
        v
    };
    let deflate = miniz_oxide::deflate::compress_to_vec(&data, 6);
    let bits = deflate.len() * 8;
    let want: Vec<Option<usize>> = (1..12)
        .map(|k| {
            lgz::bitsplit::find_block_start_with(Impl::Portable, &deflate, bits * k / 12 + 5, bits)
        })
        .collect();
    assert!(want.iter().filter(|w| w.is_some()).count() > 8);
    for i in available() {
        let got: Vec<Option<usize>> = (1..12)
            .map(|k| lgz::bitsplit::find_block_start_with(i, &deflate, bits * k / 12 + 5, bits))
            .collect();
        assert_eq!(got, want, "{i:?}");
    }
}