bloomcraft 0.1.1

//! SIMD-accelerated batch hashing for Bloom filters.
//!
//! This module implements [`SimdHasher`], a seedable, thread-safe hasher that
//! uses runtime-detected CPU features (AVX2 on x86-64, NEON on AArch64) to hash
//! multiple `u64` values in parallel. It implements the same [`BloomHasher`] trait
//! as the scalar hashers, making it interchangeable in any filter type.
//!
//! # Architecture Support
//!
//! | Architecture | SIMD  | Width    | Elements/op |
//! |--------------|-------|----------|-------------|
//! | x86-64       | AVX2  | 256-bit  | 4 × u64    |
//! | AArch64      | NEON  | 128-bit  | 2 × u64    |
//! | (fallback)   | scalar| 64-bit   | 1 × u64    |
//!
//! SIMD has fixed setup overhead. The batch methods dispatch to scalar for
//! small inputs and SIMD for batches of 8 or more.
//!
//! # Safety
//!
//! All SIMD intrinsics are gated behind runtime CPU feature detection
//! (`is_x86_feature_detected!`, `is_aarch64_feature_detected!`). No
//! `unsafe` operations are exposed in the public API.
//!
//! # Examples
//!
//! ```
//! # #[cfg(feature = "simd")]
//! # {
//! use bloomcraft::hash::simd::SimdHasher;
//! use bloomcraft::hash::BloomHasher;
//!
//! let hasher = SimdHasher::new();
//!
//! // Batch hashing (≥8 items → SIMD if available)
//! let values = vec![1u64, 2, 3, 4, 5, 6, 7, 8, 9, 10];
//! let hashes = hasher.hash_batch_u64(&values);
//! assert_eq!(hashes.len(), 10);
//!
//! // Single item (scalar path)
//! let hash = hasher.hash_bytes(b"hello");
//! # }
//! ```

#![allow(clippy::cast_possible_truncation)]
#![allow(clippy::module_name_repetitions)]
#![allow(clippy::cast_sign_loss)]
#![allow(clippy::similar_names)]
#![allow(clippy::unreadable_literal)]

use super::hasher::BloomHasher;

#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::*;

#[cfg(target_arch = "aarch64")]
use std::arch::aarch64::*;

/// Prime constants for mixing (chosen for good avalanche properties).
///
/// These are large primes with good bit distribution used in MurmurHash3-style
/// mixing functions.
const PRIME1: u64 = 0x9e3779b97f4a7c15;
const PRIME2: u64 = 0x517cc1b727220a95;
const PRIME3: u64 = 0x85ebca77c2b2ae63;

/// Minimum batch size for SIMD dispatch.
///
/// Below this threshold the scalar path is used directly, avoiding SIMD
/// setup overhead that would outweigh the benefit.
const SIMD_THRESHOLD: usize = 8;

/// Runtime-detected CPU capabilities.
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct CpuFeatures {
    /// AVX2 support (x86-64 only)
    pub has_avx2: bool,
    /// NEON support (ARM64 only, always true on AArch64)
    pub has_neon: bool,
}

impl CpuFeatures {
    /// Detect CPU features at runtime via CPUID (x86-64) or the NEON
    /// feature register (AArch64).
    #[must_use]
    pub fn detect() -> Self {
        #[cfg(target_arch = "x86_64")]
        {
            Self {
                has_avx2: is_x86_feature_detected!("avx2"),
                has_neon: false,
            }
        }

        #[cfg(target_arch = "aarch64")]
        {
            Self {
                has_avx2: false,
                // NEON is mandatory on AArch64, but we check anyway
                has_neon: std::arch::is_aarch64_feature_detected!("neon"),
            }
        }

        #[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
        {
            Self {
                has_avx2: false,
                has_neon: false,
            }
        }
    }

    /// Returns `true` if any SIMD acceleration (AVX2 or NEON) is available.
    #[must_use]
    pub const fn has_simd(self) -> bool {
        self.has_avx2 || self.has_neon
    }
}

/// Seedable, thread-safe batch hasher with SIMD acceleration.
///
/// Automatically selects AVX2, NEON, or scalar fallback based on runtime
/// CPU feature detection. Implements [`BloomHasher`] so it is interchangeable
/// with [`StdHasher`](crate::hash::StdHasher) in any filter type.
///
/// The seed is immutable after construction, making the type `Send + Sync`
/// with no locks or atomics.
///
/// # Examples
///
/// ```
/// # #[cfg(feature = "simd")]
/// # {
/// use bloomcraft::hash::simd::SimdHasher;
/// use bloomcraft::hash::BloomHasher;
///
/// let hasher = SimdHasher::new();
///
/// // Batch hashing (≥8 items → SIMD if available)
/// let values = vec![1u64, 2, 3, 4, 5, 6, 7, 8];
/// let hashes = hasher.hash_batch_u64(&values);
/// assert_eq!(hashes.len(), 8);
///
/// // Single item (scalar)
/// let hash = hasher.hash_bytes(b"test");
/// # }
/// ```
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct SimdHasher {
    seed: u64,
    features: CpuFeatures,
}

impl SimdHasher {
    /// Create a new SIMD hasher with default seed (0).
    ///
    /// Performs runtime CPU feature detection.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "simd")]
    /// # {
    /// use bloomcraft::hash::simd::SimdHasher;
    ///
    /// let hasher = SimdHasher::new();
    /// # }
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self::with_seed(0)
    }

    /// Create a new SIMD hasher with explicit seed.
    ///
    /// Different seeds produce independent hash functions.
    ///
    /// # Arguments
    ///
    /// * `seed` - Seed value
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "simd")]
    /// # {
    /// use bloomcraft::hash::simd::SimdHasher;
    ///
    /// let hasher1 = SimdHasher::with_seed(0);
    /// let hasher2 = SimdHasher::with_seed(42);
    ///
    /// let h1 = hasher1.hash_u64(123);
    /// let h2 = hasher2.hash_u64(123);
    /// assert_ne!(h1, h2);
    /// # }
    /// ```
    #[must_use]
    pub fn with_seed(seed: u64) -> Self {
        Self {
            seed,
            features: CpuFeatures::detect(),
        }
    }

    /// Returns the detected CPU capabilities for this hasher.
    #[must_use]
    pub const fn features(&self) -> CpuFeatures {
        self.features
    }

    /// Hash a single u64 value with three-round multiply-XOR-shift mixing.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "simd")]
    /// # {
    /// use bloomcraft::hash::simd::SimdHasher;
    ///
    /// let hasher = SimdHasher::new();
    /// let hash = hasher.hash_u64(12345);
    /// # }
    /// ```
    #[inline]
    pub fn hash_u64(&self, value: u64) -> u64 {
        let mut h = value ^ self.seed;

        // Round 1
        h = h.wrapping_mul(PRIME1);
        h ^= h >> 33;

        // Round 2
        h = h.wrapping_mul(PRIME2);
        h ^= h >> 29;

        // Round 3
        h = h.wrapping_mul(PRIME3);
        h ^= h >> 32;

        h
    }

    /// Hash a batch of u64 values using the fastest available method.
    ///
    /// Automatically selects:
    /// - Scalar path if batch < 8 (SIMD overhead not worth it)
    /// - AVX2 if available and batch ≥ 8
    /// - NEON if available and batch ≥ 8
    /// - Scalar otherwise
    ///
    /// # Arguments
    ///
    /// * `values` - Slice of u64 values to hash
    ///
    /// # Returns
    ///
    /// Vector of hash values, one per input value.
    ///
    /// # Examples
    ///
    /// ```
    /// # #[cfg(feature = "simd")]
    /// # {
    /// use bloomcraft::hash::simd::SimdHasher;
    ///
    /// let hasher = SimdHasher::new();
    /// let values = vec![1u64, 2, 3, 4, 5, 6, 7, 8];
    /// let hashes = hasher.hash_batch_u64(&values);
    /// assert_eq!(hashes.len(), 8);
    /// # }
    /// ```
    pub fn hash_batch_u64(&self, values: &[u64]) -> Vec<u64> {
        // Small batches: SIMD overhead exceeds benefit
        if values.len() < SIMD_THRESHOLD {
            return self.hash_batch_u64_scalar(values);
        }

        #[cfg(target_arch = "x86_64")]
        {
            if self.features.has_avx2 {
                // SAFETY: We checked has_avx2 via runtime detection
                return unsafe { self.hash_batch_u64_avx2(values) };
            }
        }

        #[cfg(target_arch = "aarch64")]
        {
            if self.features.has_neon {
                // NEON lacks efficient 64-bit multiply, so we use scalar fallback.
                return self.hash_batch_u64_scalar(values);
            }
        }

        // Fallback to scalar
        self.hash_batch_u64_scalar(values)
    }

    // Scalar fallback — 4-way unrolled for ILP.
    fn hash_batch_u64_scalar(&self, values: &[u64]) -> Vec<u64> {
        let mut result = Vec::with_capacity(values.len());

        // Process in chunks of 4 for better ILP
        let mut chunks = values.chunks_exact(4);

        for chunk in &mut chunks {
            // Unrolled loop for better pipelining
            result.push(self.hash_u64(chunk[0]));
            result.push(self.hash_u64(chunk[1]));
            result.push(self.hash_u64(chunk[2]));
            result.push(self.hash_u64(chunk[3]));
        }

        // Process remainder
        for &value in chunks.remainder() {
            result.push(self.hash_u64(value));
        }

        result
    }

    /// AVX2-optimized batch hashing for x86-64.
    ///
    /// Processes 4 u64 values simultaneously using 256-bit SIMD registers.
    ///
    /// # Safety
    ///
    /// Caller must ensure AVX2 is available via runtime detection.
    /// Uses unaligned loads (`_mm256_loadu_si256`) which are safe for any
    /// pointer and avoid the alignment requirements of aligned loads.
    #[cfg(target_arch = "x86_64")]
    #[target_feature(enable = "avx2")]
    unsafe fn hash_batch_u64_avx2(&self, values: &[u64]) -> Vec<u64> {
        let mut result = Vec::with_capacity(values.len());

        // Load constants into SIMD registers
        // SAFETY: AVX2 is guaranteed available by caller check and target_feature
        let seed_vec = _mm256_set1_epi64x(self.seed as i64);
        let prime1_vec = _mm256_set1_epi64x(PRIME1 as i64);
        let prime2_vec = _mm256_set1_epi64x(PRIME2 as i64);
        let prime3_vec = _mm256_set1_epi64x(PRIME3 as i64);

        // Process 4 values at a time
        let mut chunks = values.chunks_exact(4);

        for chunk in &mut chunks {
            // SAFETY: chunk is guaranteed to have exactly 4 elements
            // Use UNALIGNED load - safe for any pointer, minimal perf impact
            let v = _mm256_loadu_si256(chunk.as_ptr().cast::<__m256i>());

            // Round 1: XOR with seed, multiply by PRIME1
            let v = _mm256_xor_si256(v, seed_vec);
            let v = mul_u64x4(v, prime1_vec);
            let v = _mm256_xor_si256(v, _mm256_srli_epi64(v, 33));

            // Round 2: Multiply by PRIME2
            let v = mul_u64x4(v, prime2_vec);
            let v = _mm256_xor_si256(v, _mm256_srli_epi64(v, 29));

            // Round 3: Multiply by PRIME3
            let v = mul_u64x4(v, prime3_vec);
            let v = _mm256_xor_si256(v, _mm256_srli_epi64(v, 32));

            // Store results
            let mut temp = [0u64; 4];
            _mm256_storeu_si256(temp.as_mut_ptr().cast::<__m256i>(), v);
            result.extend_from_slice(&temp);
        }

        // Process remainder with scalar code
        for &value in chunks.remainder() {
            result.push(self.hash_u64(value));
        }

        result
    }
}

/// Multiply four u64 values in parallel (AVX2).
///
/// AVX2 lacks native 64-bit integer multiplication, so we emulate it using
/// 32-bit multiplies. For hash mixing, we only need the low 64 bits of the
/// 128-bit product.
///
/// # Safety
///
/// Requires AVX2 support. Caller must ensure this via feature detection.
///
/// # Implementation Note
///
/// Full 64-bit multiply: (a_lo + a_hi*2^32) * (b_lo + b_hi*2^32)
/// Low 64 bits = a_lo*b_lo + (a_lo*b_hi + a_hi*b_lo)*2^32 (mod 2^64)
#[cfg(target_arch = "x86_64")]
#[inline]
#[target_feature(enable = "avx2")]
unsafe fn mul_u64x4(a: __m256i, b: __m256i) -> __m256i {
    // SAFETY: AVX2 is guaranteed available by caller and target_feature
    // Extract high 32 bits of each u64
    let a_hi = _mm256_srli_epi64(a, 32);
    let b_hi = _mm256_srli_epi64(b, 32);

    // Compute partial products (all use low 32 bits of each 64-bit lane)
    // _mm256_mul_epu32 multiplies lanes 0,2,4,6 (32-bit) -> 64-bit results
    let lo_lo = _mm256_mul_epu32(a, b); // a_lo * b_lo
    let lo_hi = _mm256_mul_epu32(a, b_hi); // a_lo * b_hi
    let hi_lo = _mm256_mul_epu32(a_hi, b); // a_hi * b_lo

    // Cross products contribute to bits 32-95, we need bits 32-63
    // Shift left by 32 and add to get final low 64 bits
    let cross = _mm256_add_epi64(lo_hi, hi_lo);
    let cross_shifted = _mm256_slli_epi64(cross, 32);

    _mm256_add_epi64(lo_lo, cross_shifted)
}

impl Default for SimdHasher {
    fn default() -> Self {
        Self::new()
    }
}

impl BloomHasher for SimdHasher {
    #[inline]
    fn hash_bytes(&self, bytes: &[u8]) -> u64 {
        // FNV-1a: convert bytes to u64 deterministically, then apply SIMD mixing
        const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
        const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;

        let mut state = FNV_OFFSET ^ self.seed;
        for &b in bytes {
            state ^= b as u64;
            state = state.wrapping_mul(FNV_PRIME);
        }

        self.hash_u64(state)
    }

    #[inline]
    fn hash_bytes_with_seed(&self, bytes: &[u8], seed: u64) -> u64 {
        const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
        const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;

        let mut state = FNV_OFFSET ^ self.seed.wrapping_add(seed);
        for &b in bytes {
            state ^= b as u64;
            state = state.wrapping_mul(FNV_PRIME);
        }

        self.hash_u64(state)
    }

    #[inline]
    fn hash_bytes_pair(&self, bytes: &[u8]) -> (u64, u64) {
        let h1 = self.hash_bytes(bytes);
        let h2 = self.hash_bytes_with_seed(bytes, PRIME2);
        (h1, h2)
    }

    #[inline]
    fn name(&self) -> &'static str {
        "SimdHasher"
    }

    #[inline]
    fn instance_token(&self) -> u64 {
        self.seed
    }
}

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

    // --- CPU Feature Detection Tests ---

    #[test]
    fn test_cpu_features_detect() {
        let features = CpuFeatures::detect();

        #[cfg(target_arch = "x86_64")]
        {
            let _ = features.has_avx2;
            assert!(!features.has_neon);
        }

        #[cfg(target_arch = "aarch64")]
        {
            assert!(features.has_neon);
            assert!(!features.has_avx2);
        }
    }

    #[test]
    fn test_cpu_features_has_simd() {
        let features = CpuFeatures::detect();
        let _ = features.has_simd();
    }

    // --- Basic Construction Tests ---

    #[test]
    fn test_hasher_creation() {
        let hasher = SimdHasher::new();
        assert_eq!(hasher.seed, 0);

        let hasher_seeded = SimdHasher::with_seed(42);
        assert_eq!(hasher_seeded.seed, 42);
    }

    #[test]
    fn test_hasher_default() {
        let hasher: SimdHasher = Default::default();
        assert_eq!(hasher.seed, 0);
    }

    #[test]
    fn test_hasher_features() {
        let hasher = SimdHasher::new();
        let features = hasher.features();

        // Just verify we can call it
        let _ = features.has_simd();
    }

    // --- Scalar Hash Tests ---

    #[test]
    fn test_hash_u64_deterministic() {
        let hasher = SimdHasher::new();
        let value = 0x123456789abcdef0;

        let h1 = hasher.hash_u64(value);
        let h2 = hasher.hash_u64(value);

        assert_eq!(h1, h2);
    }

    #[test]
    fn test_hash_u64_different_inputs() {
        let hasher = SimdHasher::new();

        let h1 = hasher.hash_u64(1);
        let h2 = hasher.hash_u64(2);

        assert_ne!(h1, h2);
    }

    #[test]
    fn test_hash_u64_different_seeds() {
        let hasher1 = SimdHasher::with_seed(1);
        let hasher2 = SimdHasher::with_seed(2);

        let h1 = hasher1.hash_u64(42);
        let h2 = hasher2.hash_u64(42);

        assert_ne!(h1, h2);
    }

    // --- Batch Hash Tests ---

    #[test]
    fn test_hash_batch_u64_empty() {
        let hasher = SimdHasher::new();
        let values: Vec<u64> = vec![];

        let hashes = hasher.hash_batch_u64(&values);
        assert_eq!(hashes.len(), 0);
    }

    #[test]
    fn test_hash_batch_u64_small_batch() {
        let hasher = SimdHasher::new();
        let values = vec![1u64, 2, 3, 4]; // < SIMD_THRESHOLD

        let batch_hashes = hasher.hash_batch_u64(&values);

        assert_eq!(batch_hashes.len(), 4);

        // Verify each matches scalar
        for (i, &value) in values.iter().enumerate() {
            assert_eq!(batch_hashes[i], hasher.hash_u64(value));
        }
    }

    #[test]
    fn test_hash_batch_u64_exact_threshold() {
        let hasher = SimdHasher::new();
        let values: Vec<u64> = (0..SIMD_THRESHOLD as u64).collect();

        let batch_hashes = hasher.hash_batch_u64(&values);

        assert_eq!(batch_hashes.len(), SIMD_THRESHOLD);

        for (i, &value) in values.iter().enumerate() {
            assert_eq!(batch_hashes[i], hasher.hash_u64(value));
        }
    }

    #[test]
    fn test_hash_batch_u64_large() {
        let hasher = SimdHasher::new();
        let values: Vec<u64> = (0..1000).collect();

        let hashes = hasher.hash_batch_u64(&values);

        assert_eq!(hashes.len(), 1000);

        // Verify correctness against scalar
        for (i, &value) in values.iter().enumerate() {
            assert_eq!(hashes[i], hasher.hash_u64(value));
        }
    }

    #[test]
    fn test_hash_batch_u64_not_multiple_of_4() {
        let hasher = SimdHasher::new();
        let values: Vec<u64> = (0..17).collect(); // 17 = 4*4 + 1

        let hashes = hasher.hash_batch_u64(&values);

        assert_eq!(hashes.len(), 17);

        for (i, &value) in values.iter().enumerate() {
            assert_eq!(hashes[i], hasher.hash_u64(value));
        }
    }

    // --- Scalar vs SIMD Equivalence Tests ---

    #[test]
    fn test_scalar_matches_simd() {
        let hasher = SimdHasher::new();
        let values: Vec<u64> = (0..100).collect();

        let scalar_result = hasher.hash_batch_u64_scalar(&values);
        let simd_result = hasher.hash_batch_u64(&values);

        assert_eq!(scalar_result, simd_result);
    }

    #[test]
    fn test_scalar_various_sizes() {
        let hasher = SimdHasher::new();

        for size in [0usize, 1, 3, 4, 7, 8, 15, 16, 17, 63, 64, 65, 100] {
            let values: Vec<u64> = (0..size as u64).collect();
            let scalar_result = hasher.hash_batch_u64_scalar(&values);

            assert_eq!(scalar_result.len(), size);

            // Verify correctness
            for (i, &value) in values.iter().enumerate() {
                assert_eq!(scalar_result[i], hasher.hash_u64(value));
            }
        }
    }

    // --- Avalanche Tests ---

    #[test]
    fn test_avalanche_property() {
        let hasher = SimdHasher::new();

        // Single bit flip should affect ~50% of output bits
        let h1 = hasher.hash_u64(0);
        let h2 = hasher.hash_u64(1);

        let diff = h1 ^ h2;
        let changed_bits = diff.count_ones();

        // Expect 20-44 bits changed (32 ± 12)
        assert!(
            (20..=44).contains(&changed_bits),
            "Avalanche check: {} bits changed (expected 20-44)",
            changed_bits
        );
    }

    // --- BloomHasher Trait Tests ---

    #[test]
    fn test_bloom_hasher_hash_bytes() {
        let hasher = SimdHasher::new();

        let h1 = hasher.hash_bytes(b"test");
        let h2 = hasher.hash_bytes(b"test");
        assert_eq!(h1, h2);

        let h3 = hasher.hash_bytes(b"different");
        assert_ne!(h1, h3);
    }

    #[test]
    fn test_bloom_hasher_hash_bytes_pair() {
        let hasher = SimdHasher::new();

        let (h1, h2) = hasher.hash_bytes_pair(b"test");
        assert_ne!(h1, h2, "Pair should be independent");

        let (h1_b, h2_b) = hasher.hash_bytes_pair(b"test");
        assert_eq!(h1, h1_b);
        assert_eq!(h2, h2_b);
    }

    #[test]
    fn test_bloom_hasher_name() {
        let hasher = SimdHasher::new();
        assert_eq!(hasher.name(), "SimdHasher");
    }

    #[test]
    fn test_instance_token_reflects_seed() {
        let h1 = SimdHasher::with_seed(1);
        let h2 = SimdHasher::with_seed(2);
        assert_ne!(h1.instance_token(), h2.instance_token());
        assert_eq!(h1.instance_token(), 1);
        assert_eq!(h2.instance_token(), 2);
    }

    #[test]
    fn test_instance_token_consistent_for_same_seed() {
        assert_eq!(
            SimdHasher::with_seed(42).instance_token(),
            SimdHasher::with_seed(42).instance_token()
        );
    }

    // --- Integration Tests ---

    #[test]
    fn test_integration_with_strategies() {
        use crate::hash::strategies::{DoubleHashing, HashStrategy};

        let hasher = SimdHasher::new();
        let strategy = DoubleHashing;
        let data = b"test";

        let (h1, h2) = hasher.hash_bytes_pair(data);
        let indices = strategy.generate_indices(h1, h2, 0, 7, 1000);

        assert_eq!(indices.len(), 7);
        assert!(indices.iter().all(|&idx| idx < 1000));
    }

    // --- Distribution Tests ---

    #[test]
    fn test_no_collisions_sequential() {
        let hasher = SimdHasher::new();
        let values: Vec<u64> = (0..1000).collect();

        let hashes = hasher.hash_batch_u64(&values);

        // All hashes should be unique
        let unique: std::collections::HashSet<_> = hashes.iter().copied().collect();
        assert_eq!(unique.len(), 1000, "Detected hash collisions");
    }

    // --- Thread Safety Tests ---

    #[test]
    fn test_send_sync() {
        fn assert_send_sync<T: Send + Sync>() {}
        assert_send_sync::<SimdHasher>();
    }

    #[test]
    fn test_copy() {
        let hasher1 = SimdHasher::with_seed(42);
        let hasher2 = hasher1; // Copy

        assert_eq!(hasher1.seed, hasher2.seed);

        let value = 123u64;
        assert_eq!(hasher1.hash_u64(value), hasher2.hash_u64(value));
    }
}