crates/gunnar-bitmap/tests/words.rs
//! What the four set operations mean, pinned against hand-written expectations.
//!
//! `src/words.rs` is the one definition of `or` / `and-not` / `and` / `xor` for
//! this crate; every loop routes through `Op::apply`. That makes it a good place
//! for a single quiet mistake, because a differential test against a second
//! implementation cannot see two implementations agreeing on a wrong meaning.
//! So these assertions name the answers outright.
//!
//! # Why `AndNot` gets the attention
//!
//! It is the exclusion half of a fetch, and it is the one operation that is not
//! symmetric: `dst & !src` and `!dst & src` are both plausible readings and both
//! produce a bitmap of exactly the right shape made of the wrong objects. That
//! is the failure `crate::pack_order` warns about in the position space, one
//! layer down.
//!
//! # Seen red
//!
//! While an AVX2 backend existed here (written, measured slower on the real
//! path, and removed — `src/words.rs` carries the numbers), this file also ran
//! both backends over every length and compared them. That sweep was proved red
//! by computing `Op::Or` as `_mm256_and_si256`: it fired at length 4 and **not**
//! at 0..=3, the boundary where a vector register first fills. The assertions
//! that survived the revert were red in the same session by swapping `AndNot`'s
//! operands.
use gunnar_bitmap::words::{apply, Op};
/// Each variant computes what its name says, on values chosen so that all four
/// answers differ from each other and from both inputs.
#[test]
fn the_operations_mean_what_they_are_called() {
let (d, s) = (0b1100u64, 0b1010u64);
assert_eq!(Op::Or.apply(d, s), 0b1110);
assert_eq!(Op::And.apply(d, s), 0b1000);
assert_eq!(Op::Xor.apply(d, s), 0b0110);
assert_eq!(Op::AndNot.apply(d, s), 0b0100);
// The four answers must be four answers. Without this, a bug that collapsed
// two variants into one would still pass every line above if the constants
// happened to agree.
let all = [Op::Or, Op::And, Op::Xor, Op::AndNot].map(|op| op.apply(d, s));
let mut sorted = all.to_vec();
sorted.sort_unstable();
sorted.dedup();
assert_eq!(
sorted.len(),
4,
"two operations returned the same answer: {all:?}"
);
// The backwards reading of and-not, named so a future edit cannot land it by
// accident and so this line fails if someone "simplifies" the operands.
assert_ne!(Op::AndNot.apply(d, s), !d & s);
}
/// The slice form agrees with the scalar form lane for lane, at lengths either
/// side of anything a vectoriser would treat specially.
#[test]
fn the_slice_form_agrees_with_the_scalar_form() {
let mut compared = 0usize;
for len in [0usize, 1, 3, 4, 5, 8, 15, 16, 31, 64, 133] {
let src: Vec<u64> = (0..len as u64).map(splitmix).collect();
let base: Vec<u64> = (0..len as u64).map(|i| splitmix(i ^ 0xA5A5_A5A5)).collect();
for op in [Op::Or, Op::AndNot, Op::And, Op::Xor] {
let want: Vec<u64> = base
.iter()
.zip(&src)
.map(|(&d, &s)| op.apply(d, s))
.collect();
let mut got = base.clone();
apply(op, &mut got, &src);
assert_eq!(got, want, "{op:?} at length {len}");
compared += 1;
}
}
// A sweep that compared nothing would pass. 11 lengths x 4 operations.
assert_eq!(
compared, 44,
"the sweep did not run the comparisons it claims"
);
}
/// `apply` stops at the shorter slice and leaves the rest of `dst` alone.
///
/// Not a hypothetical shape: `Bitmap::and_not_with` deliberately does not grow,
/// so it hands a longer `dst` to a shorter `src` on every fetch whose haves
/// cover fewer objects than its wants. Writing past `min(len)` there would
/// clear bits nothing asked about.
#[test]
fn apply_stops_at_the_shorter_slice() {
let mut compared = 0usize;
for dst_len in [0usize, 1, 4, 7, 16, 33, 64] {
for src_len in [0usize, 1, 4, 7, 16, 33, 64] {
let src: Vec<u64> = (0..src_len as u64).map(splitmix).collect();
for op in [Op::Or, Op::AndNot, Op::And, Op::Xor] {
let base: Vec<u64> = (0..dst_len as u64)
.map(|i| splitmix(i ^ 0x0BAD_F00D))
.collect();
let mut got = base.clone();
apply(op, &mut got, &src);
let n = dst_len.min(src_len);
for i in 0..n {
assert_eq!(got[i], op.apply(base[i], src[i]), "{op:?} lane {i}");
}
assert_eq!(
&got[n..],
&base[n..],
"{op:?} dst={dst_len} src={src_len} wrote past min(len)"
);
compared += 1;
}
}
}
assert_eq!(
compared, 196,
"the sweep did not run the comparisons it claims"
);
}
/// splitmix64. Deterministic from the test source alone, so a failure is
/// reproducible without a `rand` dependency this crate must not grow (D21).
fn splitmix(i: u64) -> u64 {
let mut z = i
.wrapping_mul(0x9E37_79B9_7F4A_7C15)
.wrapping_add(0x9E37_79B9_7F4A_7C15);
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}