turbocow 0.3.0-beta.2

Compact, clone-on-write vectors, strings, maps and sets with inline + referenced storage — a superset of ecow.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

//! SIMD-accelerated h2 byte matching for inline map lookups.
//!
//! The h2 value is the top 7 bits of a hash, used as a quick pre-filter
//! before full key comparison. [`match_h2`] scans an h2 sidecar array and
//! returns a [`BitMask`] of matching positions.
//!
//! Platform support:
//! - **x86_64**: SSE2 `_mm_cmpeq_epi8` + `_mm_movemask_epi8` when N ≥ 16
//! - **All platforms**: scalar fallback (auto-vectorised by LLVM)

use core::hash::{BuildHasher, Hash};

/// Extract h2 (top 7 bits) from a 64-bit hash.
#[inline]
pub(super) fn h2(hash: u64) -> u8 {
    (hash >> 57) as u8
}

/// Sentinel for empty slots (never a valid h2 since h2 ∈ 0..128).
pub(super) const H2_EMPTY: u8 = 0xFF;

/// Compute the full u64 hash of a value.
#[inline]
pub(super) fn make_hash<Q: Hash + ?Sized, S: BuildHasher>(
    hash_builder: &S,
    val: &Q,
) -> u64 {
    hash_builder.hash_one(val)
}

/// Bitmask of matching positions in an h2 sidecar.
#[derive(Clone, Copy)]
pub(super) struct BitMask(u32);

impl Iterator for BitMask {
    type Item = usize;

    #[inline]
    fn next(&mut self) -> Option<usize> {
        if self.0 == 0 {
            None
        } else {
            let pos = self.0.trailing_zeros() as usize;
            self.0 &= self.0 - 1;
            Some(pos)
        }
    }
}

/// Scan `h2_bytes[0..len]` for positions equal to `needle`.
///
/// The const generic `N` is the array capacity (≥ `len`). It determines
/// whether SIMD intrinsics are used: N ≥ 16 on x86_64 enables SSE2 for
/// the first 16 entries; any remainder uses scalar.
///
/// # Safety
/// `h2_bytes` must point to at least `N` readable bytes.
#[inline]
pub(super) unsafe fn match_h2<const N: usize>(
    h2_bytes: *const u8,
    len: usize,
    needle: u8,
) -> BitMask {
    unsafe {
        debug_assert!(len <= N);
        debug_assert!(len <= 32);

        #[cfg(target_arch = "x86_64")]
        if N >= 16 {
            return match_h2_sse2(h2_bytes, len, needle);
        }

        match_h2_scalar(h2_bytes, len, needle)
    }
}

#[inline]
unsafe fn match_h2_scalar(h2_bytes: *const u8, len: usize, needle: u8) -> BitMask {
    unsafe {
        let mut mask = 0u32;
        for i in 0..len {
            if *h2_bytes.add(i) == needle {
                mask |= 1 << i;
            }
        }
        BitMask(mask)
    }
}

#[cfg(target_arch = "x86_64")]
#[inline]
unsafe fn match_h2_sse2(h2_bytes: *const u8, len: usize, needle: u8) -> BitMask {
    unsafe {
        use core::arch::x86_64::*;

        let needle_v = _mm_set1_epi8(needle as i8);
        // First 16 bytes — safe because N ≥ 16.
        let g1 = _mm_loadu_si128(h2_bytes as *const __m128i);
        let mut mask = _mm_movemask_epi8(_mm_cmpeq_epi8(g1, needle_v)) as u32;
        // Second 16 bytes for N ≥ 32 (avoids scalar fallback).
        if len > 16 {
            let g2 = _mm_loadu_si128(h2_bytes.add(16) as *const __m128i);
            mask |= (_mm_movemask_epi8(_mm_cmpeq_epi8(g2, needle_v)) as u32) << 16;
        }
        BitMask(mask & len_mask(len))
    }
}

#[inline]
const fn len_mask(len: usize) -> u32 {
    if len >= 32 { u32::MAX } else { (1u32 << len) - 1 }
}