| use super::bitmask::BitMask; |
| use super::EMPTY; |
| use core::mem; |
| |
| #[cfg(target_arch = "x86")] |
| use core::arch::x86; |
| #[cfg(target_arch = "x86_64")] |
| use core::arch::x86_64 as x86; |
| |
| pub type BitMaskWord = u16; |
| pub const BITMASK_STRIDE: usize = 1; |
| pub const BITMASK_MASK: BitMaskWord = 0xffff; |
| |
| /// Abstraction over a group of control bytes which can be scanned in |
| /// parallel. |
| /// |
| /// This implementation uses a 128-bit SSE value. |
| #[derive(Copy, Clone)] |
| pub struct Group(x86::__m128i); |
| |
| // FIXME: https://github.com/rust-lang/rust-clippy/issues/3859 |
| #[allow(clippy::use_self)] |
| impl Group { |
| /// Number of bytes in the group. |
| pub const WIDTH: usize = mem::size_of::<Self>(); |
| |
| /// Returns a full group of empty bytes, suitable for use as the initial |
| /// value for an empty hash table. |
| /// |
| /// This is guaranteed to be aligned to the group size. |
| #[inline] |
| #[allow(clippy::items_after_statements)] |
| pub const fn static_empty() -> &'static [u8; Group::WIDTH] { |
| #[repr(C)] |
| struct AlignedBytes { |
| _align: [Group; 0], |
| bytes: [u8; Group::WIDTH], |
| } |
| const ALIGNED_BYTES: AlignedBytes = AlignedBytes { |
| _align: [], |
| bytes: [EMPTY; Group::WIDTH], |
| }; |
| &ALIGNED_BYTES.bytes |
| } |
| |
| /// Loads a group of bytes starting at the given address. |
| #[inline] |
| #[allow(clippy::cast_ptr_alignment)] // unaligned load |
| pub unsafe fn load(ptr: *const u8) -> Self { |
| Group(x86::_mm_loadu_si128(ptr.cast())) |
| } |
| |
| /// Loads a group of bytes starting at the given address, which must be |
| /// aligned to `mem::align_of::<Group>()`. |
| #[inline] |
| #[allow(clippy::cast_ptr_alignment)] |
| pub unsafe fn load_aligned(ptr: *const u8) -> Self { |
| // FIXME: use align_offset once it stabilizes |
| debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0); |
| Group(x86::_mm_load_si128(ptr.cast())) |
| } |
| |
| /// Stores the group of bytes to the given address, which must be |
| /// aligned to `mem::align_of::<Group>()`. |
| #[inline] |
| #[allow(clippy::cast_ptr_alignment)] |
| pub unsafe fn store_aligned(self, ptr: *mut u8) { |
| // FIXME: use align_offset once it stabilizes |
| debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0); |
| x86::_mm_store_si128(ptr.cast(), self.0); |
| } |
| |
| /// Returns a `BitMask` indicating all bytes in the group which have |
| /// the given value. |
| #[inline] |
| pub fn match_byte(self, byte: u8) -> BitMask { |
| #[allow( |
| clippy::cast_possible_wrap, // byte: u8 as i8 |
| // byte: i32 as u16 |
| // note: _mm_movemask_epi8 returns a 16-bit mask in a i32, the |
| // upper 16-bits of the i32 are zeroed: |
| clippy::cast_sign_loss, |
| clippy::cast_possible_truncation |
| )] |
| unsafe { |
| let cmp = x86::_mm_cmpeq_epi8(self.0, x86::_mm_set1_epi8(byte as i8)); |
| BitMask(x86::_mm_movemask_epi8(cmp) as u16) |
| } |
| } |
| |
| /// Returns a `BitMask` indicating all bytes in the group which are |
| /// `EMPTY`. |
| #[inline] |
| pub fn match_empty(self) -> BitMask { |
| self.match_byte(EMPTY) |
| } |
| |
| /// Returns a `BitMask` indicating all bytes in the group which are |
| /// `EMPTY` or `DELETED`. |
| #[inline] |
| pub fn match_empty_or_deleted(self) -> BitMask { |
| #[allow( |
| // byte: i32 as u16 |
| // note: _mm_movemask_epi8 returns a 16-bit mask in a i32, the |
| // upper 16-bits of the i32 are zeroed: |
| clippy::cast_sign_loss, |
| clippy::cast_possible_truncation |
| )] |
| unsafe { |
| // A byte is EMPTY or DELETED iff the high bit is set |
| BitMask(x86::_mm_movemask_epi8(self.0) as u16) |
| } |
| } |
| |
| /// Returns a `BitMask` indicating all bytes in the group which are full. |
| #[inline] |
| pub fn match_full(&self) -> BitMask { |
| self.match_empty_or_deleted().invert() |
| } |
| |
| /// Performs the following transformation on all bytes in the group: |
| /// - `EMPTY => EMPTY` |
| /// - `DELETED => EMPTY` |
| /// - `FULL => DELETED` |
| #[inline] |
| pub fn convert_special_to_empty_and_full_to_deleted(self) -> Self { |
| // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111 |
| // and high_bit = 0 (FULL) to 1000_0000 |
| // |
| // Here's this logic expanded to concrete values: |
| // let special = 0 > byte = 1111_1111 (true) or 0000_0000 (false) |
| // 1111_1111 | 1000_0000 = 1111_1111 |
| // 0000_0000 | 1000_0000 = 1000_0000 |
| #[allow( |
| clippy::cast_possible_wrap, // byte: 0x80_u8 as i8 |
| )] |
| unsafe { |
| let zero = x86::_mm_setzero_si128(); |
| let special = x86::_mm_cmpgt_epi8(zero, self.0); |
| Group(x86::_mm_or_si128( |
| special, |
| x86::_mm_set1_epi8(0x80_u8 as i8), |
| )) |
| } |
| } |
| } |