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
256
257
258
259
260
261
#[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 shufti_avx512<const REVERT: bool>(
low: &[u8; 16],
high: &[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(low.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(high.as_ptr().cast()),
haystack,
)
}
}
#[inline(always)]
unsafe fn search512<const REVERT: bool>(
low: __m128i,
high: __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>(low, high, _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>(low, high, _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);
}
}
// Subtract the end address's remainder modulo 64 from len. Then
// ptr + aligned_end is the last 64-byte boundary at or before its end.
let aligned_end = len - (ptr.add(len) as usize & 0b00111111);
while start < aligned_end {
// Load all 64 bytes from the 64-byte-aligned interior position;
// the loop bounds also guarantee a complete vector remains.
let mask = mask64::<REVERT>(low, high, _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;
}
if start == len {
return None;
}
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>(low, high, _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 rshufti_avx512<const REVERT: bool>(
low: &[u8; 16],
high: &[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(low.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(high.as_ptr().cast()),
haystack,
)
}
}
#[inline(always)]
unsafe fn rsearch512<const REVERT: bool>(
low: __m128i,
high: __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>(low, high, _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
};
}
// The end address's remainder modulo 64 is the suffix length after
// the preceding 64-byte boundary. Scan those bytes before the aligned
// loop; enabling only suffix lanes keeps the load inside the slice.
let suffix = ptr.add(len) as usize & 0b00111111;
let mut end = len - suffix;
if suffix != 0 {
let valid = u64::MAX >> (64 - suffix);
// 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>(
low,
high,
_mm512_maskz_loadu_epi8(valid, ptr.add(end).cast()),
);
// Discard positions outside the actual input, including any padding
// whose zero byte happened to satisfy the selected predicate.
mask &= valid;
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 inner mask gives the start address's remainder modulo 64.
// Subtract it from 64 to get the distance to the next boundary.
// The outer mask changes 64 to 0 when ptr is already aligned,
// so the reverse loop stops at the boundary at or after ptr.
let first = (64 - (ptr as usize & 0b00111111)) & 0b00111111;
while end > first {
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>(low, high, _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);
}
}
if end == 0 {
return None;
}
// len >= 64 guarantees a full prefix; the overlap has already failed.
// 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>(low, high, _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>(low: __m128i, high: __m128i, bytes: __m512i) -> u64 {
// SAFETY: the caller has established AVX-512F/BW support.
unsafe {
// set1_epi8 broadcasts 0b00001111 into every byte lane. AND with this
// mask extracts each input byte's low nibble as a table index in 0..16.
let nibble = _mm512_set1_epi8(0b00001111);
// shuffle_epi8 performs the low-table lookup independently in each
// 128-bit lane. The following broadcast supplies an identical table
// to every lane; AND supplies the input bytes' low-nibble indices.
let low = _mm512_shuffle_epi8(
// Replicate the complete 16-byte low table across the wide register;
// this does not merge the shuffle's separate 128-bit lookup domains.
_mm512_broadcast_i32x4(low),
_mm512_and_si512(bytes, nibble),
);
// Look up the high nibble in the high table. andnot(a, b) means
// (~a) & b: clear each byte's low four bits BEFORE shifting the
// 64-bit lanes. This prevents a neighboring byte's low nibble from
// spilling into this byte; the resulting indices are exactly b >> 4.
let high = _mm512_shuffle_epi8(
// Repeat the 16-byte high table in each 128-bit shuffle lane.
_mm512_broadcast_i32x4(high),
_mm512_srli_epi64::<4>(_mm512_andnot_si512(nibble, bytes)),
);
// Intersect the low/high group flags. A nonzero byte is a member.
let member = _mm512_and_si512(low, high);
// 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())
}
}
}