1use super::bitmask::BitMask;
2use super::EMPTY;
3use core::{mem, ptr};
4
5// Use the native word size as the group size. Using a 64-bit group size on
6// a 32-bit architecture will just end up being more expensive because
7// shifts and multiplies will need to be emulated.
8#[cfg(any(
9 target_pointer_width = "64",
10 target_arch = "aarch64",
11 target_arch = "x86_64",
12 target_arch = "wasm32",
13))]
14type GroupWord = u64;
15#[cfg(all(
16 target_pointer_width = "32",
17 not(target_arch = "aarch64"),
18 not(target_arch = "x86_64"),
19 not(target_arch = "wasm32"),
20))]
21type GroupWord = u32;
22
23pub type BitMaskWord = GroupWord;
24pub const BITMASK_STRIDE: usize = 8;
25// We only care about the highest bit of each byte for the mask.
26#[allow(clippy::cast_possible_truncation, clippy::unnecessary_cast)]
27pub const BITMASK_MASK: BitMaskWord = 0x8080_8080_8080_8080_u64 as GroupWord;
28
29/// Helper function to replicate a byte across a `GroupWord`.
30#[inline]
31fn repeat(byte: u8) -> GroupWord {
32 GroupWord::from_ne_bytes([byte; Group::WIDTH])
33}
34
35/// Abstraction over a group of control bytes which can be scanned in
36/// parallel.
37///
38/// This implementation uses a word-sized integer.
39#[derive(Copy, Clone)]
40pub struct Group(GroupWord);
41
42// We perform all operations in the native endianness, and convert to
43// little-endian just before creating a BitMask. The can potentially
44// enable the compiler to eliminate unnecessary byte swaps if we are
45// only checking whether a BitMask is empty.
46#[allow(clippy::use_self)]
47impl Group {
48 /// Number of bytes in the group.
49 pub const WIDTH: usize = mem::size_of::<Self>();
50
51 /// Returns a full group of empty bytes, suitable for use as the initial
52 /// value for an empty hash table.
53 ///
54 /// This is guaranteed to be aligned to the group size.
55 #[inline]
56 pub const fn static_empty() -> &'static [u8; Group::WIDTH] {
57 #[repr(C)]
58 struct AlignedBytes {
59 _align: [Group; 0],
60 bytes: [u8; Group::WIDTH],
61 }
62 const ALIGNED_BYTES: AlignedBytes = AlignedBytes {
63 _align: [],
64 bytes: [EMPTY; Group::WIDTH],
65 };
66 &ALIGNED_BYTES.bytes
67 }
68
69 /// Loads a group of bytes starting at the given address.
70 #[inline]
71 #[allow(clippy::cast_ptr_alignment)] // unaligned load
72 pub unsafe fn load(ptr: *const u8) -> Self {
73 Group(ptr::read_unaligned(ptr.cast()))
74 }
75
76 /// Loads a group of bytes starting at the given address, which must be
77 /// aligned to `mem::align_of::<Group>()`.
78 #[inline]
79 #[allow(clippy::cast_ptr_alignment)]
80 pub unsafe fn load_aligned(ptr: *const u8) -> Self {
81 // FIXME: use align_offset once it stabilizes
82 debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
83 Group(ptr::read(ptr.cast()))
84 }
85
86 /// Stores the group of bytes to the given address, which must be
87 /// aligned to `mem::align_of::<Group>()`.
88 #[inline]
89 #[allow(clippy::cast_ptr_alignment)]
90 pub unsafe fn store_aligned(self, ptr: *mut u8) {
91 // FIXME: use align_offset once it stabilizes
92 debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
93 ptr::write(ptr.cast(), self.0);
94 }
95
96 /// Returns a `BitMask` indicating all bytes in the group which *may*
97 /// have the given value.
98 ///
99 /// This function may return a false positive in certain cases where
100 /// the byte in the group differs from the searched value only in its
101 /// lowest bit. This is fine because:
102 /// - This never happens for `EMPTY` and `DELETED`, only full entries.
103 /// - The check for key equality will catch these.
104 /// - This only happens if there is at least 1 true match.
105 /// - The chance of this happening is very low (< 1% chance per byte).
106 #[inline]
107 pub fn match_byte(self, byte: u8) -> BitMask {
108 // This algorithm is derived from
109 // https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
110 let cmp = self.0 ^ repeat(byte);
111 BitMask((cmp.wrapping_sub(repeat(0x01)) & !cmp & repeat(0x80)).to_le())
112 }
113
114 /// Returns a `BitMask` indicating all bytes in the group which are
115 /// `EMPTY`.
116 #[inline]
117 pub fn match_empty(self) -> BitMask {
118 // If the high bit is set, then the byte must be either:
119 // 1111_1111 (EMPTY) or 1000_0000 (DELETED).
120 // So we can just check if the top two bits are 1 by ANDing them.
121 BitMask((self.0 & (self.0 << 1) & repeat(0x80)).to_le())
122 }
123
124 /// Returns a `BitMask` indicating all bytes in the group which are
125 /// `EMPTY` or `DELETED`.
126 #[inline]
127 pub fn match_empty_or_deleted(self) -> BitMask {
128 // A byte is EMPTY or DELETED iff the high bit is set
129 BitMask((self.0 & repeat(0x80)).to_le())
130 }
131
132 /// Returns a `BitMask` indicating all bytes in the group which are full.
133 #[inline]
134 pub fn match_full(self) -> BitMask {
135 self.match_empty_or_deleted().invert()
136 }
137
138 /// Performs the following transformation on all bytes in the group:
139 /// - `EMPTY => EMPTY`
140 /// - `DELETED => EMPTY`
141 /// - `FULL => DELETED`
142 #[inline]
143 pub fn convert_special_to_empty_and_full_to_deleted(self) -> Self {
144 // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111
145 // and high_bit = 0 (FULL) to 1000_0000
146 //
147 // Here's this logic expanded to concrete values:
148 // let full = 1000_0000 (true) or 0000_0000 (false)
149 // !1000_0000 + 1 = 0111_1111 + 1 = 1000_0000 (no carry)
150 // !0000_0000 + 0 = 1111_1111 + 0 = 1111_1111 (no carry)
151 let full = !self.0 & repeat(0x80);
152 Group(!full + (full >> 7))
153 }
154}
155