vendor/hashbrown-0.11.2/src/raw/sse2.rs

   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     #[allow(clippy::items_after_statements)]
  32     pub const fn static_empty() -> &'static [u8; Group::WIDTH] {
  33         #[repr(C)]
  34         struct AlignedBytes {
  35             _align: [Group; 0],
  36             bytes: [u8; Group::WIDTH],
  37         }
  38         const ALIGNED_BYTES: AlignedBytes = AlignedBytes {
  39             _align: [],
  40             bytes: [EMPTY; Group::WIDTH],
  41         };
  42         &ALIGNED_BYTES.bytes
  43     }
  44
  45     /// Loads a group of bytes starting at the given address.
  46     #[inline]
  47     #[allow(clippy::cast_ptr_alignment)] // unaligned load
  48     pub unsafe fn load(ptr: *const u8) -> Self {
  49         Group(x86::_mm_loadu_si128(ptr.cast()))
  50     }
  51
  52     /// Loads a group of bytes starting at the given address, which must be
  53     /// aligned to `mem::align_of::<Group>()`.
  54     #[inline]
  55     #[allow(clippy::cast_ptr_alignment)]
  56     pub unsafe fn load_aligned(ptr: *const u8) -> Self {
  57         // FIXME: use align_offset once it stabilizes
  58         debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
  59         Group(x86::_mm_load_si128(ptr.cast()))
  60     }
  61
  62     /// Stores the group of bytes to the given address, which must be
  63     /// aligned to `mem::align_of::<Group>()`.
  64     #[inline]
  65     #[allow(clippy::cast_ptr_alignment)]
  66     pub unsafe fn store_aligned(self, ptr: *mut u8) {
  67         // FIXME: use align_offset once it stabilizes
  68         debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0);
  69         x86::_mm_store_si128(ptr.cast(), self.0);
  70     }
  71
  72     /// Returns a `BitMask` indicating all bytes in the group which have
  73     /// the given value.
  74     #[inline]
  75     pub fn match_byte(self, byte: u8) -> BitMask {
  76         #[allow(
  77             clippy::cast_possible_wrap, // byte: u8 as i8
  78             // byte: i32 as u16
  79             //   note: _mm_movemask_epi8 returns a 16-bit mask in a i32, the
  80             //   upper 16-bits of the i32 are zeroed:
  81             clippy::cast_sign_loss,
  82             clippy::cast_possible_truncation
  83         )]
  84         unsafe {
  85             let cmp = x86::_mm_cmpeq_epi8(self.0, x86::_mm_set1_epi8(byte as i8));
  86             BitMask(x86::_mm_movemask_epi8(cmp) as u16)
  87         }
  88     }
  89
  90     /// Returns a `BitMask` indicating all bytes in the group which are
  91     /// `EMPTY`.
  92     #[inline]
  93     pub fn match_empty(self) -> BitMask {
  94         self.match_byte(EMPTY)
  95     }
  96
  97     /// Returns a `BitMask` indicating all bytes in the group which are
  98     /// `EMPTY` or `DELETED`.
  99     #[inline]
 100     pub fn match_empty_or_deleted(self) -> BitMask {
 101         #[allow(
 102             // byte: i32 as u16
 103             //   note: _mm_movemask_epi8 returns a 16-bit mask in a i32, the
 104             //   upper 16-bits of the i32 are zeroed:
 105             clippy::cast_sign_loss,
 106             clippy::cast_possible_truncation
 107         )]
 108         unsafe {
 109             // A byte is EMPTY or DELETED iff the high bit is set
 110             BitMask(x86::_mm_movemask_epi8(self.0) as u16)
 111         }
 112     }
 113
 114     /// Returns a `BitMask` indicating all bytes in the group which are full.
 115     #[inline]
 116     pub fn match_full(&self) -> BitMask {
 117         self.match_empty_or_deleted().invert()
 118     }
 119
 120     /// Performs the following transformation on all bytes in the group:
 121     /// - `EMPTY => EMPTY`
 122     /// - `DELETED => EMPTY`
 123     /// - `FULL => DELETED`
 124     #[inline]
 125     pub fn convert_special_to_empty_and_full_to_deleted(self) -> Self {
 126         // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111
 127         // and high_bit = 0 (FULL) to 1000_0000
 128         //
 129         // Here's this logic expanded to concrete values:
 130         //   let special = 0 > byte = 1111_1111 (true) or 0000_0000 (false)
 131         //   1111_1111 | 1000_0000 = 1111_1111
 132         //   0000_0000 | 1000_0000 = 1000_0000
 133         #[allow(
 134             clippy::cast_possible_wrap, // byte: 0x80_u8 as i8
 135         )]
 136         unsafe {
 137             let zero = x86::_mm_setzero_si128();
 138             let special = x86::_mm_cmpgt_epi8(zero, self.0);
 139             Group(x86::_mm_or_si128(
 140                 special,
 141                 x86::_mm_set1_epi8(0x80_u8 as i8),
 142             ))
 143         }
 144     }
 145 }