hashbrown/control/group/
neon.rs

1use super::super::{BitMask, Tag};
2use core::arch::aarch64 as neon;
3use core::mem;
4use core::num::NonZeroU64;
5
6pub(crate) type BitMaskWord = u64;
7pub(crate) type NonZeroBitMaskWord = NonZeroU64;
8pub(crate) const BITMASK_STRIDE: usize = 8;
9pub(crate) const BITMASK_ITER_MASK: BitMaskWord = 0x8080_8080_8080_8080;
10
11/// Abstraction over a group of control tags which can be scanned in
12/// parallel.
13///
14/// This implementation uses a 64-bit NEON value.
15#[derive(Copy, Clone)]
16pub(crate) struct Group(neon::uint8x8_t);
17
18#[expect(clippy::use_self)]
19impl Group {
20    /// Number of bytes in the group.
21    pub(crate) const WIDTH: usize = mem::size_of::<Self>();
22
23    /// Returns a full group of empty tags, suitable for use as the initial
24    /// value for an empty hash table.
25    ///
26    /// This is guaranteed to be aligned to the group size.
27    #[inline]
28    pub(crate) const fn static_empty() -> &'static [Tag; Group::WIDTH] {
29        #[repr(C)]
30        struct AlignedTags {
31            _align: [Group; 0],
32            tags: [Tag; Group::WIDTH],
33        }
34        const ALIGNED_TAGS: AlignedTags = AlignedTags {
35            _align: [],
36            tags: [Tag::EMPTY; Group::WIDTH],
37        };
38        &ALIGNED_TAGS.tags
39    }
40
41    /// Loads a group of tags starting at the given address.
42    #[inline]
43    pub(crate) unsafe fn load(ptr: *const Tag) -> Self {
44        unsafe { Group(neon::vld1_u8(ptr.cast())) }
45    }
46
47    /// Loads a group of tags starting at the given address, which must be
48    /// aligned to `mem::align_of::<Group>()`.
49    #[inline]
50    pub(crate) unsafe fn load_aligned(ptr: *const Tag) -> Self {
51        debug_assert_eq!(ptr.align_offset(mem::align_of::<Self>()), 0);
52        unsafe { Group(neon::vld1_u8(ptr.cast())) }
53    }
54
55    /// Stores the group of tags to the given address, which must be
56    /// aligned to `mem::align_of::<Group>()`.
57    #[inline]
58    pub(crate) unsafe fn store_aligned(self, ptr: *mut Tag) {
59        debug_assert_eq!(ptr.align_offset(mem::align_of::<Self>()), 0);
60        unsafe {
61            neon::vst1_u8(ptr.cast(), self.0);
62        }
63    }
64
65    /// Returns a `BitMask` indicating all tags in the group which *may*
66    /// have the given value.
67    #[inline]
68    pub(crate) fn match_tag(self, tag: Tag) -> BitMask {
69        unsafe {
70            let cmp = neon::vceq_u8(self.0, neon::vdup_n_u8(tag.0));
71            BitMask(neon::vget_lane_u64(neon::vreinterpret_u64_u8(cmp), 0))
72        }
73    }
74
75    /// Returns a `BitMask` indicating all tags in the group which are
76    /// `EMPTY`.
77    #[inline]
78    pub(crate) fn match_empty(self) -> BitMask {
79        self.match_tag(Tag::EMPTY)
80    }
81
82    /// Returns a `BitMask` indicating all tags in the group which are
83    /// `EMPTY` or `DELETED`.
84    #[inline]
85    pub(crate) fn match_empty_or_deleted(self) -> BitMask {
86        unsafe {
87            let cmp = neon::vcltz_s8(neon::vreinterpret_s8_u8(self.0));
88            BitMask(neon::vget_lane_u64(neon::vreinterpret_u64_u8(cmp), 0))
89        }
90    }
91
92    /// Returns a `BitMask` indicating all tags in the group which are full.
93    #[inline]
94    pub(crate) fn match_full(self) -> BitMask {
95        unsafe {
96            let cmp = neon::vcgez_s8(neon::vreinterpret_s8_u8(self.0));
97            BitMask(neon::vget_lane_u64(neon::vreinterpret_u64_u8(cmp), 0))
98        }
99    }
100
101    /// Performs the following transformation on all tags in the group:
102    /// - `EMPTY => EMPTY`
103    /// - `DELETED => EMPTY`
104    /// - `FULL => DELETED`
105    #[inline]
106    pub(crate) fn convert_special_to_empty_and_full_to_deleted(self) -> Self {
107        // Map high_bit = 1 (EMPTY or DELETED) to 1111_1111
108        // and high_bit = 0 (FULL) to 1000_0000
109        //
110        // Here's this logic expanded to concrete values:
111        //   let special = 0 > tag = 1111_1111 (true) or 0000_0000 (false)
112        //   1111_1111 | 1000_0000 = 1111_1111
113        //   0000_0000 | 1000_0000 = 1000_0000
114        unsafe {
115            let special = neon::vcltz_s8(neon::vreinterpret_s8_u8(self.0));
116            Group(neon::vorr_u8(special, neon::vdup_n_u8(0x80)))
117        }
118    }
119}
hashbrown/control/group/neon.rs

hashbrown/control/group/
neon.rs
