| 1 |
use super::bitmask::BitMask; |
| 2 |
use super::EMPTY; |
| 3 |
use core::{mem, ptr}; |
| 4 |
|
| 5 |
// Use the native word size as the group size. Using a 64-bit group size on |
| 6 |
// a 32-bit architecture will just end up being more expensive because |
| 7 |
// shifts and multiplies will need to be emulated. |
| 8 |
#[cfg(any( |
| 9 |
target_pointer_width = "64", |
| 10 |
target_arch = "aarch64", |
| 11 |
target_arch = "x86_64", |
| 12 |
target_arch = "wasm32", |
| 13 |
))] |
| 14 |
type GroupWord = u64; |
| 15 |
#[cfg(all( |
| 16 |
target_pointer_width = "32", |
| 17 |
not(target_arch = "aarch64"), |
| 18 |
not(target_arch = "x86_64"), |
| 19 |
not(target_arch = "wasm32"), |
| 20 |
))] |
| 21 |
type GroupWord = u32; |
| 22 |
|
| 23 |
pub type BitMaskWord = GroupWord; |
| 24 |
pub const BITMASK_STRIDE: usize = 8; |
| 25 |
// We only care about the highest bit of each byte for the mask. |
| 26 |
#[allow(clippy::cast_possible_truncation, clippy::unnecessary_cast)] |
| 27 |
pub const BITMASK_MASK: BitMaskWord = 0x8080_8080_8080_8080_u64 as GroupWord; |
| 28 |
|
| 29 |
/// Helper function to replicate a byte across a `GroupWord`. |
| 30 |
#[inline] |
| 31 |
fn repeat(byte: u8) -> GroupWord { |
| 32 |
GroupWord::from_ne_bytes([byte; Group::WIDTH]) |
| 33 |
} |
| 34 |
|
| 35 |
/// Abstraction over a group of control bytes which can be scanned in |
| 36 |
/// parallel. |
| 37 |
/// |
| 38 |
/// This implementation uses a word-sized integer. |
| 39 |
#[derive(Copy, Clone)] |
| 40 |
pub struct Group(GroupWord); |
| 41 |
|
| 42 |
// We perform all operations in the native endianness, and convert to |
| 43 |
// little-endian just before creating a BitMask. The can potentially |
| 44 |
// enable the compiler to eliminate unnecessary byte swaps if we are |
| 45 |
// only checking whether a BitMask is empty. |
| 46 |
#[allow(clippy::use_self)] |
| 47 |
impl Group { |
| 48 |
/// Number of bytes in the group. |
| 49 |
pub const WIDTH: usize = mem::size_of::<Self>(); |
| 50 |
|
| 51 |
/// Returns a full group of empty bytes, suitable for use as the initial |
| 52 |
/// value for an empty hash table. |
| 53 |
/// |
| 54 |
/// This is guaranteed to be aligned to the group size. |
| 55 |
#[inline] |
| 56 |
pub const fn static_empty() -> &'static [u8; Group::WIDTH] { |
| 57 |
#[repr(C)] |
| 58 |
struct AlignedBytes { |
| 59 |
_align: [Group; 0], |
| 60 |
bytes: [u8; Group::WIDTH], |
| 61 |
} |
| 62 |
const ALIGNED_BYTES: AlignedBytes = AlignedBytes { |
| 63 |
_align: [], |
| 64 |
bytes: [EMPTY; Group::WIDTH], |
| 65 |
}; |
| 66 |
&ALIGNED_BYTES.bytes |
| 67 |
} |
| 68 |
|
| 69 |
/// Loads a group of bytes starting at the given address. |
| 70 |
#[inline] |
| 71 |
#[allow(clippy::cast_ptr_alignment)] // unaligned load |
| 72 |
pub unsafe fn load(ptr: *const u8) -> Self { |
| 73 |
Group(ptr::read_unaligned(ptr.cast())) |
| 74 |
} |
| 75 |
|
| 76 |
/// Loads a group of bytes starting at the given address, which must be |
| 77 |
/// aligned to `mem::align_of::<Group>()`. |
| 78 |
#[inline] |
| 79 |
#[allow(clippy::cast_ptr_alignment)] |
| 80 |
pub unsafe fn load_aligned(ptr: *const u8) -> Self { |
| 81 |
// FIXME: use align_offset once it stabilizes |
| 82 |
debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0); |
| 83 |
Group(ptr::read(ptr.cast())) |
| 84 |
} |
| 85 |
|
| 86 |
/// Stores the group of bytes to the given address, which must be |
| 87 |
/// aligned to `mem::align_of::<Group>()`. |
| 88 |
#[inline] |
| 89 |
#[allow(clippy::cast_ptr_alignment)] |
| 90 |
pub unsafe fn store_aligned(self, ptr: *mut u8) { |
| 91 |
// FIXME: use align_offset once it stabilizes |
| 92 |
debug_assert_eq!(ptr as usize & (mem::align_of::<Self>() - 1), 0); |
| 93 |
ptr::write(ptr.cast(), self.0); |
| 94 |
} |
| 95 |
|
| 96 |
/// Returns a `BitMask` indicating all bytes in the group which *may* |
| 97 |
/// have the given value. |
| 98 |
/// |
| 99 |
/// This function may return a false positive in certain cases where |
| 100 |
/// the byte in the group differs from the searched value only in its |
| 101 |
/// lowest bit. This is fine because: |
| 102 |
/// - This never happens for `EMPTY` and `DELETED`, only full entries. |
| 103 |
/// - The check for key equality will catch these. |
| 104 |
/// - This only happens if there is at least 1 true match. |
| 105 |
/// - The chance of this happening is very low (< 1% chance per byte). |
| 106 |
#[inline] |
| 107 |
pub fn match_byte(self, byte: u8) -> BitMask { |
| 108 |
// This algorithm is derived from |
| 109 |
// https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord |
| 110 |
let cmp = self.0 ^ repeat(byte); |
| 111 |
BitMask((cmp.wrapping_sub(repeat(0x01)) & !cmp & repeat(0x80)).to_le()) |
| 112 |
} |
| 113 |
|
| 114 |
/// Returns a `BitMask` indicating all bytes in the group which are |
| 115 |
/// `EMPTY`. |
| 116 |
#[inline] |
| 117 |
pub fn match_empty(self) -> BitMask { |
| 118 |
// If the high bit is set, then the byte must be either: |
| 119 |
// 1111_1111 (EMPTY) or 1000_0000 (DELETED). |
| 120 |
// So we can just check if the top two bits are 1 by ANDing them. |
| 121 |
BitMask((self.0 & (self.0 << 1) & repeat(0x80)).to_le()) |
| 122 |
} |
| 123 |
|
| 124 |
/// Returns a `BitMask` indicating all bytes in the group which are |
| 125 |
/// `EMPTY` or `DELETED`. |
| 126 |
#[inline] |
| 127 |
pub fn match_empty_or_deleted(self) -> BitMask { |
| 128 |
// A byte is EMPTY or DELETED iff the high bit is set |
| 129 |
BitMask((self.0 & repeat(0x80)).to_le()) |
| 130 |
} |
| 131 |
|
| 132 |
/// Returns a `BitMask` indicating all bytes in the group which are full. |
| 133 |
#[inline] |
| 134 |
pub fn match_full(self) -> BitMask { |
| 135 |
self.match_empty_or_deleted().invert() |
| 136 |
} |
| 137 |
|
| 138 |
/// Performs the following transformation on all bytes in the group: |
| 139 |
/// - `EMPTY => EMPTY` |
| 140 |
/// - `DELETED => EMPTY` |
| 141 |
/// - `FULL => DELETED` |
| 142 |
#[inline] |
| 143 |
pub fn convert_special_to_empty_and_full_to_deleted(self) -> Self { |
| 144 |
// Map high_bit = 1 (EMPTY or DELETED) to 1111_1111 |
| 145 |
// and high_bit = 0 (FULL) to 1000_0000 |
| 146 |
// |
| 147 |
// Here's this logic expanded to concrete values: |
| 148 |
// let full = 1000_0000 (true) or 0000_0000 (false) |
| 149 |
// !1000_0000 + 1 = 0111_1111 + 1 = 1000_0000 (no carry) |
| 150 |
// !0000_0000 + 0 = 1111_1111 + 0 = 1111_1111 (no carry) |
| 151 |
let full = !self.0 & repeat(0x80); |
| 152 |
Group(!full + (full >> 7)) |
| 153 |
} |
| 154 |
} |