1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
#[cfg(target_arch = "x86")]
use core::arch::x86::*;
#[cfg(target_arch = "x86_64")]
use core::arch::x86_64::*;
// Requires avx512bw, valid table arrays, any slice length.
#[target_feature(enable = "avx512bw")]
pub(in super::super) fn truffle_avx512<const REVERT: bool>(
lower: &[u8; 16],
upper: &[u8; 16],
haystack: &[u8],
) -> Option<usize> {
// SAFETY: array loads stay within their initialized storage; dispatch
// validates CPU support; short inputs are handled before full input loads.
unsafe {
search512::<REVERT>(
// Load the 16 initialized table entries into one register; the
// array has byte alignment, so use the unaligned load intrinsic.
_mm_loadu_si128(lower.as_ptr().cast()),
// Load the 16 initialized table entries into one register; the
// array has byte alignment, so use the unaligned load intrinsic.
_mm_loadu_si128(upper.as_ptr().cast()),
haystack,
)
}
}
#[inline(always)]
unsafe fn search512<const REVERT: bool>(
lower: __m128i,
upper: __m128i,
haystack: &[u8],
) -> Option<usize> {
// SAFETY: the entry point establishes AVX-512F/BW support. Masked loads
// access only enabled bytes; all full loads below stay inside haystack.
unsafe {
let ptr = haystack.as_ptr();
let len = haystack.len();
// Masked loads let AVX-512 process a short slice without touching
// adjacent bytes. Masking the classification result is also necessary:
// inactive lanes contain zero, which may itself belong to the needle.
if len <= 64 {
let valid = u64::MAX.checked_shr((64 - len) as u32).unwrap_or(0);
// Masked 64-byte load: bit i of valid enables memory byte i;
// disabled lanes are zero-filled. No 64-byte alignment is required.
// Classification is masked again below so zero-filled lanes cannot
// be reported even if byte value zero matches the needle.
let mut mask =
mask64::<REVERT>(lower, upper, _mm512_maskz_loadu_epi8(valid, ptr.cast()));
// Discard positions outside the actual input, including any padding
// whose zero byte happened to satisfy the selected predicate.
mask &= valid;
return if mask != 0 {
// The lowest set bit identifies the first selected lane.
Some(mask.trailing_zeros() as usize)
} else {
None
};
}
let mut start = 0;
// The low six address bits give the remainder modulo 64. When it is
// nonzero, 64 - remainder is the distance to the next 64-byte boundary.
// Scan that prefix first; an aligned ptr starts the main loop at 0.
let misalignment = ptr as usize & 0b00111111;
if misalignment != 0 {
start = 64 - misalignment;
let valid = u64::MAX >> (64 - start);
// Masked 64-byte load: bit i of valid enables memory byte i;
// disabled lanes are zero-filled. No 64-byte alignment is required.
// Classification is masked again below so zero-filled lanes cannot
// be reported even if byte value zero matches the needle.
let mut mask =
mask64::<REVERT>(lower, upper, _mm512_maskz_loadu_epi8(valid, ptr.cast()));
// Discard positions outside the actual input, including any padding
// whose zero byte happened to satisfy the selected predicate.
mask &= valid;
if mask != 0 {
// The lowest set bit identifies the first selected lane.
return Some(mask.trailing_zeros() as usize);
}
}
let last = len - 64;
while start < last {
// Load all 64 bytes from the 64-byte-aligned interior position;
// the loop bounds also guarantee a complete vector remains.
let mask = mask64::<REVERT>(lower, upper, _mm512_load_si512(ptr.add(start).cast()));
if mask != 0 {
// The lowest set bit identifies the first selected lane.
// Add this block's start to return a position in the original input.
return Some(start + mask.trailing_zeros() as usize);
}
start += 64;
}
// Load all 64 bytes at this address without an alignment requirement.
// The full-vector path keeps the entire read inside haystack.
let mask = mask64::<REVERT>(lower, upper, _mm512_loadu_si512(ptr.add(last).cast()));
if mask != 0 {
// The lowest set bit identifies the first selected lane.
// Add this block's start to return a position in the original input.
Some(last + mask.trailing_zeros() as usize)
} else {
None
}
}
}
// Reverse entry point. Requires avx512bw, any slice length.
#[target_feature(enable = "avx512bw")]
pub(in super::super) fn rtruffle_avx512<const REVERT: bool>(
lower: &[u8; 16],
upper: &[u8; 16],
haystack: &[u8],
) -> Option<usize> {
// SAFETY: array loads stay within their initialized storage; dispatch
// validates CPU support; short inputs are handled before full input loads.
unsafe {
rsearch512::<REVERT>(
// Load the 16 initialized table entries into one register; the
// array has byte alignment, so use the unaligned load intrinsic.
_mm_loadu_si128(lower.as_ptr().cast()),
// Load the 16 initialized table entries into one register; the
// array has byte alignment, so use the unaligned load intrinsic.
_mm_loadu_si128(upper.as_ptr().cast()),
haystack,
)
}
}
#[inline(always)]
unsafe fn rsearch512<const REVERT: bool>(
lower: __m128i,
upper: __m128i,
haystack: &[u8],
) -> Option<usize> {
// SAFETY: the entry point establishes AVX-512F/BW support. Masked loads
// touch only enabled bytes; each full load is preceded by a width check.
unsafe {
let ptr = haystack.as_ptr();
let len = haystack.len();
if len < 64 {
let valid = u64::MAX.checked_shr((64 - len) as u32).unwrap_or(0);
// Masked 64-byte load: bit i of valid enables memory byte i;
// disabled lanes are zero-filled. No 64-byte alignment is required.
// Classification is masked again below so zero-filled lanes cannot
// be reported even if byte value zero matches the needle.
let mut mask =
mask64::<REVERT>(lower, upper, _mm512_maskz_loadu_epi8(valid, ptr.cast()));
// Inactive zero-filled lanes must not appear in either search.
// Discard positions outside the actual input, including any padding
// whose zero byte happened to satisfy the selected predicate.
mask &= valid;
return if mask != 0 {
// 63 - leading_zeros locates the highest set bit in this u64,
// which identifies the last selected byte lane.
Some((63 - mask.leading_zeros()) as usize)
} else {
None
};
}
// rtruffleExec checks a full unaligned suffix before rounding the end
// down. Unlike rshuftiExec, it does not peel a masked partial suffix.
let last = len - 64;
// Load all 64 bytes at this address without an alignment requirement.
// The full-vector path keeps the entire read inside haystack.
let mask = mask64::<REVERT>(lower, upper, _mm512_loadu_si512(ptr.add(last).cast()));
if mask != 0 {
// 63 - leading_zeros locates the highest set bit in this u64,
// which identifies the last selected byte lane.
// Add this block's start to return a position in the original input.
return Some(last + (63 - mask.leading_zeros()) as usize);
}
// The end address's low six bits give its remainder modulo 64.
// Subtract that remainder from len to round ptr + end down to a
// 64-byte boundary. The initial suffix scan covered the skipped bytes.
let mut end = len - (ptr.add(len) as usize & 0b00111111);
while end > 64 {
end -= 64;
// Load all 64 bytes from the 64-byte-aligned interior position;
// the loop bounds also guarantee a complete vector remains.
let mask = mask64::<REVERT>(lower, upper, _mm512_load_si512(ptr.add(end).cast()));
if mask != 0 {
// 63 - leading_zeros locates the highest set bit in this u64,
// which identifies the last selected byte lane.
// Add this block's start to return a position in the original input.
return Some(end + (63 - mask.leading_zeros()) as usize);
}
}
// The final full prefix is also read when it overlaps an earlier block.
// Load all 64 bytes at this address without an alignment requirement.
// The full-vector path keeps the entire read inside haystack.
let mask = mask64::<REVERT>(lower, upper, _mm512_loadu_si512(ptr.cast()));
if mask != 0 {
// 63 - leading_zeros locates the highest set bit in this u64,
// which identifies the last selected byte lane.
Some((63 - mask.leading_zeros()) as usize)
} else {
None
}
}
}
// Bit i selects byte i: members for find, nonmembers when REVERT is true.
#[inline(always)]
unsafe fn mask64<const REVERT: bool>(lower: __m128i, upper: __m128i, bytes: __m512i) -> u64 {
// SAFETY: the caller has established AVX-512F/BW support.
unsafe {
// set1_epi8(0b10000000u8 as i8) repeats the bit pattern 0b10000000 in every byte.
// This is the shuffle index's zeroing bit, not a signed comparison.
let top = _mm512_set1_epi8(0b10000000u8 as i8);
// Pack [1 << 0, ..., 1 << 7] in x86 little-endian byte order.
// Broadcasting the packed u64 gives each 16-byte shuffle lane two
// copies of the table; index h returns 1 << (h & 0b00000111).
let bits = _mm512_set1_epi64(u64::from_le_bytes([
1 << 0,
1 << 1,
1 << 2,
1 << 3,
1 << 4,
1 << 5,
1 << 6,
1 << 7,
]) as i64);
// PSHUFB selects table[byte & 0b00001111] unless index bit 7 is set,
// in which case it returns zero. Thus this lookup contributes only
// for bytes below 128. On wide vectors, broadcast repeats the full
// 16-byte table in each independent 128-bit shuffle lane.
let lower = _mm512_shuffle_epi8(_mm512_broadcast_i32x4(lower), bytes);
// XOR with 0b10000000 toggles only the index's top bit, preserving the
// low-nibble table index. This shuffle now contributes only for
// bytes at least 128; exactly one of lower/upper can be nonzero.
let upper =
_mm512_shuffle_epi8(_mm512_broadcast_i32x4(upper), _mm512_xor_si512(bytes, top));
// srli_epi64 shifts 64-bit lanes, not individual bytes. Its low
// four output bits still equal this byte's high nibble; higher bits
// may come from the next byte. andnot(top, shifted) clears bit 7
// to prevent accidental PSHUFB zeroing; PSHUFB ignores bits 4..6.
let index = _mm512_andnot_si512(top, _mm512_srli_epi64::<4>(bytes));
// Shuffle the repeated powers of two by the high nibble. This
// produces the membership bit 1 << ((byte >> 4) & 0b00000111) in every lane.
// For 0b11000001 the upper table supplies entry 1 and selected is 0b00010000.
let selected = _mm512_shuffle_epi8(bits, index);
// OR joins the active table flags; AND tests the selected bit.
// A nonzero result means this byte belongs to the needle.
let member = _mm512_and_si512(_mm512_or_si512(lower, upper), selected);
// AVX-512 compares directly into a 64-bit predicate mask. Select
// equality for nonmembers or inequality for members; neither needs
// a separate movemask or inversion. REVERT is a compile-time choice.
if REVERT {
_mm512_cmpeq_epi8_mask(member, _mm512_setzero_si512())
} else {
_mm512_cmpneq_epi8_mask(member, _mm512_setzero_si512())
}
}
}