hashbrown/control/group/
sse2.rs

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

hashbrown/control/group/
sse2.rs
