vecstasy/

hashvec.rs

use std::hash::{Hash, Hasher};

use crate::{SIMD_LANECOUNT, veclike::VecLike};

/// A wrapper type for `&[f32]` slices that provides
/// stable hashing and equality based on the IEEE‑754 bit patterns.
///
/// `HashVec` compares floats by their raw bit representation
/// and writes each element’s `to_bits()` into the hasher.
/// This ensures that `0.0` and `-0.0` are distinguished,
/// and that `NaN` values only compare equal if their bit patterns match.
///
/// Implements `VecLike` by delegating to the slice implementation,
/// allowing distance, dot‑product, and normalization operations.
///
/// Since
///
/// # Example
///
/// ```
/// use std::collections::hash_map::DefaultHasher;
/// use std::hash::{Hash, Hasher};
/// use vecstasy::HashVec;
/// use vecstasy::VecLike;
///
/// let data: &[f32] = &[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0]; // len needs to be a multiple of 8
/// let hv = HashVec::from(data);
///
/// // Hash computation
/// let mut hasher = DefaultHasher::new();
/// hv.hash(&mut hasher);
/// let hash_value = hasher.finish();
///
/// // VecLike operations
/// let normed: Vec<f32> = hv.normalized();
/// ```
#[derive(Debug, Clone)]
pub struct HashVec<'a> {
    internal: &'a [f32],
}

impl<'a> From<&'a [f32]> for HashVec<'a> {
    fn from(value: &'a [f32]) -> Self {
        debug_assert!(
            value.len() % SIMD_LANECOUNT == 0,
            "You provided a vector that doesn't play nicely with SIMD"
        );
        HashVec { internal: value }
    }
}

// hashing is done bit-wise, blocks of 32 bits at a time
impl<'a> Hash for HashVec<'a> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        for &val in self.internal {
            state.write_u32(val.to_bits());
        }
    }
}

// equality of two vectors is defined bitwise.
// this means that vectors like [-0.0] and [0.0] are NOT considered equal
// for our purposes, even though the individual elements are.
impl<'a> PartialEq for HashVec<'a> {
    fn eq(&self, other: &Self) -> bool {
        self.internal.len() == other.internal.len()
            && self
                .internal
                .iter()
                .zip(other.internal)
                .all(|(a, b)| a.to_bits() == b.to_bits())
    }
}

// vector equality is also reflexive (for all a, a == a), we can tell that to the compiler:
impl<'a> Eq for HashVec<'a> {}

// HashVec provides linear algebra ops, we just have to delegate to the internal slice.
// the inline tags enable cross-crate inlining, which is a big deal here.
impl<'a> VecLike for HashVec<'a> {
    type Owned = Vec<f32>;

    /// Computes the squared L2 (Euclidean) distance between `self` and `othr`.
    ///
    /// Operates on fixed‐size chunks; any trailing elements when the slice length
    /// is not a multiple of the chunk size will be silently ignored in release mode.
    ///
    /// # Panics
    /// - In debug mode, if `self.len() != othr.len()`.
    /// - In debug mode, if the slice length is not a multiple of the internal chunk size.
    #[inline]
    fn l2_dist_squared(&self, other: &Self) -> f32 {
        self.internal.l2_dist_squared(&other.internal)
    }

    /// Computes the dot product of `self` and `othr`.
    ///
    /// Operates on fixed‐size chunks; any trailing elements when the slice length
    /// is not a multiple of the chunk size will be silently ignored in release mode.
    ///
    /// # Panics
    /// - In debug mode, if `self.len() != othr.len()`.
    /// - In debug mode, if the slice length is not a multiple of the internal chunk size.
    #[inline]
    fn dot(&self, other: &Self) -> f32 {
        self.internal.dot(&other.internal)
    }

    /// Returns a normalized copy of the input slice.
    ///
    /// Operates on fixed‐size chunks; any trailing elements when the slice length
    /// is not a multiple of the chunk size will be silently ignored in release mode.
    ///
    /// If the input norm is zero, returns a zero vector of the same length.
    ///
    /// # Panics
    /// - In debug mode, if the slice length is not a multiple of the internal chunk size.
    #[inline]
    fn normalized(&self) -> Self::Owned {
        self.internal.normalized()
    }
}

#[cfg(test)]
mod tests {
    use std::vec;

    use super::*;
    use quickcheck::{QuickCheck, TestResult};

    const TOLERANCE: f32 = 1e-6;

    fn close(actual: f32, target: f32) -> bool {
        (target - actual).abs() < TOLERANCE
    }

    fn is_valid_l2(suspect: f32) -> bool {
        suspect.is_finite() && suspect >= 0.0
    }

    fn l2_spec<'a>(v1: HashVec<'a>, v2: HashVec<'a>) -> f32 {
        v1.internal
            .iter()
            .zip(v2.internal.iter())
            .map(|(&x, &y)| {
                let diff = x - y;
                diff * diff
            })
            .sum()
    }

    #[test]
    fn self_sim_is_zero() {
        fn qc_self_sim_is_zero(totest: Vec<f32>) -> TestResult {
            let usable_length = totest.len() / 8 * 8;
            if totest[0..usable_length].iter().any(|x| !x.is_finite()) {
                return TestResult::discard();
            }
            let testvec = HashVec {
                internal: &totest[0..usable_length],
            };
            let selfsim = testvec.l2_dist_squared(&testvec).sqrt();
            let to_check = is_valid_l2(selfsim) && close(selfsim, 0.0);
            return TestResult::from_bool(to_check);
        }

        QuickCheck::new()
            .tests(10_000)
            // force that less than 90% of tests are discarded due to precondition violations
            // i.e. at least 10% of inputs should be valid so that we cover a good range
            .min_tests_passed(500)
            .quickcheck(qc_self_sim_is_zero as fn(Vec<f32>) -> TestResult);
    }

    #[test]
    // verifies the claim in the documentation of l2_dist_squared
    // i.e. dist(u,v) < dist(w, x) ⇔ dist(u,v) ** 2 < dist(w,x) ** 2
    fn squared_invariant() {
        fn qc_squared_invariant(u: Vec<f32>, v: Vec<f32>, w: Vec<f32>, x: Vec<f32>) -> TestResult {
            let all_vecs = [u, v, w, x]; //no need to check for NaNs in this case
            let min_length = all_vecs.iter().map(|x| x.len()).min().unwrap() / 8 * 8;
            let all_vectors: Vec<HashVec> = all_vecs
                .iter()
                .map(|vec| HashVec::from(&vec[..min_length]))
                .collect();

            let d1_squared = all_vectors[0].l2_dist_squared(&all_vectors[1]);
            let d2_squared = all_vectors[2].l2_dist_squared(&all_vectors[3]);

            let d1_root = all_vectors[0].l2_dist_squared(&all_vectors[1]).sqrt();
            let d2_root = all_vectors[2].l2_dist_squared(&all_vectors[3]).sqrt();

            let sanity_check1 = (d1_squared < d2_squared) == (d1_root < d2_root);
            let sanity_check2 = (d1_squared <= d2_squared) == (d1_root <= d2_root);
            TestResult::from_bool(sanity_check1 && sanity_check2)
        }

        QuickCheck::new()
            .tests(10_000)
            .min_tests_passed(500)
            .quickcheck(
                qc_squared_invariant as fn(Vec<f32>, Vec<f32>, Vec<f32>, Vec<f32>) -> TestResult,
            );
    }

    #[test]
    fn simd_matches_spec() {
        fn qc_simd_matches_spec(u: Vec<f32>, v: Vec<f32>) -> TestResult {
            let min_length = u.len().min(v.len()) / 8 * 8;
            let (u_f32v, v_f32v) = (
                HashVec::from(&u[0..min_length]),
                HashVec::from(&v[0..min_length]),
            );
            let simd = u_f32v.l2_dist_squared(&v_f32v);
            let spec = l2_spec(u_f32v, v_f32v);

            if simd.is_infinite() {
                TestResult::from_bool(spec.is_infinite())
            } else if simd.is_nan() {
                TestResult::from_bool(spec.is_nan())
            } else {
                TestResult::from_bool(close(simd, spec))
            }
        }

        QuickCheck::new()
            .tests(10_000)
            .min_tests_passed(500)
            .quickcheck(qc_simd_matches_spec as fn(Vec<f32>, Vec<f32>) -> TestResult);
    }

    #[test]
    fn normalization_gives_unit_l2_norm() {
        fn qc_normalized(vec: Vec<f32>) -> TestResult {
            if vec.len() < 8 {
                return TestResult::discard();
            }
            let usable = vec.len() / 8 * 8;
            let vec: Vec<f32> = vec[..usable]
                .iter()
                .cloned()
                .map(|x| x.clamp(-1e6, 1e6))
                .collect();

            if vec.iter().any(|x| !x.is_finite()) {
                return TestResult::discard();
            }

            let hv = HashVec::from(vec.as_slice());
            let norm = hv.normalized();
            let normhv = HashVec::from(norm.as_slice());
            let self_dot = normhv.dot(&normhv);

            if vec.iter().all(|&x| x == 0.0) {
                TestResult::from_bool(close(self_dot, 0.0))
            } else {
                TestResult::from_bool(close(self_dot, 1.0))
            }
        }

        QuickCheck::new()
            .tests(10_000)
            .min_tests_passed(500)
            .quickcheck(qc_normalized as fn(Vec<f32>) -> TestResult);

        assert!(!qc_normalized(vec![0.0; 8]).is_failure());
    }

    #[test]
    fn dot_product_matches_spec() {
        fn qc_dot_matches_spec(u: Vec<f32>, v: Vec<f32>) -> TestResult {
            let usable = u.len().min(v.len()) / 8 * 8;
            if usable == 0 {
                return TestResult::discard();
            }

            let u: Vec<f32> = u[..usable].iter().map(|x| x.clamp(-1e3, 1e3)).collect();
            let v: Vec<f32> = v[..usable].iter().map(|x| x.clamp(-1e3, 1e3)).collect();

            if u.iter().any(|x| !x.is_finite()) || v.iter().any(|x| !x.is_finite()) {
                return TestResult::discard();
            }

            let uv = HashVec::from(u.as_slice());
            let vv = HashVec::from(v.as_slice());

            let spec_dot: f32 = u.iter().zip(&v).map(|(&a, &b)| a * b).sum::<f32>().abs();
            let impl_dot = uv.dot(&vv).abs();

            TestResult::from_bool(0.99 * spec_dot <= impl_dot && impl_dot <= 1.01 * spec_dot)
        }

        QuickCheck::new()
            .tests(10_000)
            .min_tests_passed(500)
            .quickcheck(qc_dot_matches_spec as fn(Vec<f32>, Vec<f32>) -> TestResult);
    }

    #[test]
    fn hash_consistent_for_equal_inputs() {
        use std::collections::hash_map::DefaultHasher;

        fn hash_of(v: &[f32]) -> u64 {
            let mut hasher = DefaultHasher::new();
            HashVec::from(v).hash(&mut hasher);
            hasher.finish()
        }

        fn qc_equal_vecs_hash_same(v: Vec<f32>) -> TestResult {
            let usable = v.len() / 8 * 8;
            let v = &v[..usable];

            if v.iter().any(|x| !x.is_finite()) {
                return TestResult::discard();
            }

            let h1 = hash_of(v);
            let h2 = hash_of(v);
            TestResult::from_bool(h1 == h2)
        }

        QuickCheck::new()
            .tests(10_000)
            .min_tests_passed(500)
            .quickcheck(qc_equal_vecs_hash_same as fn(Vec<f32>) -> TestResult);
    }

    #[test]
    fn different_vectors_likely_hash_differently() {
        use std::collections::hash_map::DefaultHasher;

        fn hash_of(v: &[f32]) -> u64 {
            let mut hasher = DefaultHasher::new();
            HashVec::from(v).hash(&mut hasher);
            hasher.finish()
        }

        let a = vec![1.0_f32; 8];
        let mut b = vec![1.0_f32; 8];
        b[0] = 2.0;
        let ha = hash_of(&a);
        let hb = hash_of(&b);
        assert_ne!(ha, hb);
    }

    #[test]
    fn equality_works_as_expected() {
        fn qc_eq_correctness(v: Vec<f32>) -> TestResult {
            let usable = v.len() / 8 * 8;
            if usable == 0 || v[..usable].iter().any(|x| !x.is_finite()) {
                return TestResult::discard();
            }

            let slice = &v[..usable];
            let hv1 = HashVec::from(slice);
            let hv2 = HashVec::from(slice);

            // Reflexivity
            let reflexivity = hv1 == hv1;

            // Symmetry
            let symmetry = hv1 == hv2 && hv2 == hv1;

            // Inequality after mutation
            let mut modified = slice.to_vec();
            modified[0] = f32::from_bits(modified[0].to_bits().wrapping_add(1)); // bit-level tweak
            let hv3 = HashVec::from(modified.as_slice());

            let unequal = hv1 != hv3;
            TestResult::from_bool(unequal && reflexivity && symmetry)
        }

        QuickCheck::new()
            .tests(10_000)
            .min_tests_passed(500)
            .quickcheck(qc_eq_correctness as fn(Vec<f32>) -> TestResult);
    }
}