1 use super::bitmask::BitMask;
2 use super::EMPTY;
3 use core::mem;
4 
5 #[cfg(target_arch = "x86")]
6 use core::arch::x86;
7 #[cfg(target_arch = "x86_64")]
8 use core::arch::x86_64 as x86;
9 
10 pub type BitMaskWord = u16;
11 pub const BITMASK_STRIDE: usize = 1;
12 pub const BITMASK_MASK: BitMaskWord = 0xffff;
13 
14 /// Abstraction over a group of control bytes which can be scanned in
15 /// parallel.
16 ///
17 /// This implementation uses a 128-bit SSE value.
18 #[derive(Copy, Clone)]
19 pub struct Group(x86::__m128i);
20 
21 // FIXME: https://github.com/rust-lang/rust-clippy/issues/3859
22 #[allow(clippy::use_self)]
23 impl Group {
24     /// Number of bytes in the group.
25     pub const WIDTH: usize = mem::size_of::<Self>();
26 
27     /// Returns a full group of empty bytes, suitable for use as the initial
28     /// value for an empty hash table.
29     ///
30     /// This is guaranteed to be aligned to the group size.
31     #[inline]
32     #[allow(clippy::items_after_statements)]
static_empty() -> &'static [u8; Group::WIDTH]33     pub const fn static_empty() -> &'static [u8; Group::WIDTH] {
34         #[repr(C)]
35         struct AlignedBytes {
36             _align: [Group; 0],
37             bytes: [u8; Group::WIDTH],
38         }
39         const ALIGNED_BYTES: AlignedBytes = AlignedBytes {
40             _align: [],
41             bytes: [EMPTY; Group::WIDTH],
42         };
43         &ALIGNED_BYTES.bytes
44     }
45 
46     /// Loads a group of bytes starting at the given address.
47     #[inline]
48     #[allow(clippy::cast_ptr_alignment)] // unaligned load
load(ptr: *const u8) -> Self49     pub unsafe fn load(ptr: *const u8) -> Self {
50         Group(x86::_mm_loadu_si128(ptr.cast()))
51     }
52 
53     /// Loads a group of bytes starting at the given address, which must be
54     /// aligned to `mem::align_of::<Group>()`.
55     #[inline]
56     #[allow(clippy::cast_ptr_alignment)]
load_aligned(ptr: *const u8) -> Self57     pub unsafe fn load_aligned(ptr: *const u8) -> Self {
58         // FIXME: use align_offset once it stabilizes
59         debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
60         Group(x86::_mm_load_si128(ptr.cast()))
61     }
62 
63     /// Stores the group of bytes to the given address, which must be
64     /// aligned to `mem::align_of::<Group>()`.
65     #[inline]
66     #[allow(clippy::cast_ptr_alignment)]
store_aligned(self, ptr: *mut u8)67     pub unsafe fn store_aligned(self, ptr: *mut u8) {
68         // FIXME: use align_offset once it stabilizes
69         debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
70         x86::_mm_store_si128(ptr.cast(), self.0);
71     }
72 
73     /// Returns a `BitMask` indicating all bytes in the group which have
74     /// the given value.
75     #[inline]
match_byte(self, byte: u8) -> BitMask76     pub fn match_byte(self, byte: u8) -> BitMask {
77         #[allow(
78             clippy::cast_possible_wrap, // byte: u8 as i8
79             // byte: i32 as u16
80             //   note: _mm_movemask_epi8 returns a 16-bit mask in a i32, the
81             //   upper 16-bits of the i32 are zeroed:
82             clippy::cast_sign_loss,
83             clippy::cast_possible_truncation
84         )]
85         unsafe {
86             let cmp = x86::_mm_cmpeq_epi8(self.0, x86::_mm_set1_epi8(byte as i8));
87             BitMask(x86::_mm_movemask_epi8(cmp) as u16)
88         }
89     }
90 
91     /// Returns a `BitMask` indicating all bytes in the group which are
92     /// `EMPTY`.
93     #[inline]
match_empty(self) -> BitMask94     pub fn match_empty(self) -> BitMask {
95         self.match_byte(EMPTY)
96     }
97 
98     /// Returns a `BitMask` indicating all bytes in the group which are
99     /// `EMPTY` or `DELETED`.
100     #[inline]
match_empty_or_deleted(self) -> BitMask101     pub fn match_empty_or_deleted(self) -> BitMask {
102         #[allow(
103             // byte: i32 as u16
104             //   note: _mm_movemask_epi8 returns a 16-bit mask in a i32, the
105             //   upper 16-bits of the i32 are zeroed:
106             clippy::cast_sign_loss,
107             clippy::cast_possible_truncation
108         )]
109         unsafe {
110             // A byte is EMPTY or DELETED iff the high bit is set
111             BitMask(x86::_mm_movemask_epi8(self.0) as u16)
112         }
113     }
114 
115     /// Returns a `BitMask` indicating all bytes in the group which are full.
116     #[inline]
match_full(&self) -> BitMask117     pub fn match_full(&self) -> BitMask {
118         self.match_empty_or_deleted().invert()
119     }
120 
121     /// Performs the following transformation on all bytes in the group:
122     /// - `EMPTY => EMPTY`
123     /// - `DELETED => EMPTY`
124     /// - `FULL => DELETED`
125     #[inline]
convert_special_to_empty_and_full_to_deleted(self) -> Self126     pub fn convert_special_to_empty_and_full_to_deleted(self) -> Self {
127         // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111
128         // and high_bit = 0 (FULL) to 1000_0000
129         //
130         // Here's this logic expanded to concrete values:
131         //   let special = 0 > byte = 1111_1111 (true) or 0000_0000 (false)
132         //   1111_1111 | 1000_0000 = 1111_1111
133         //   0000_0000 | 1000_0000 = 1000_0000
134         #[allow(
135             clippy::cast_possible_wrap, // byte: 0x80_u8 as i8
136         )]
137         unsafe {
138             let zero = x86::_mm_setzero_si128();
139             let special = x86::_mm_cmpgt_epi8(zero, self.0);
140             Group(x86::_mm_or_si128(
141                 special,
142                 x86::_mm_set1_epi8(0x80_u8 as i8),
143             ))
144         }
145     }
146 }
147