4 const CHUNK_SIZE: usize,
6 const CANONICAL: usize,
7 const CANONICALIZED: usize,
10 chunk_idx_map: &[u8; N],
11 bitset_chunk_idx: &[[u8; CHUNK_SIZE]; N1],
12 bitset_canonical: &[u64; CANONICAL],
13 bitset_canonicalized: &[(u8, u8); CANONICALIZED],
15 let bucket_idx = (needle / 64) as usize;
16 let chunk_map_idx = bucket_idx / CHUNK_SIZE;
17 let chunk_piece = bucket_idx % CHUNK_SIZE;
18 let chunk_idx = if let Some(&v) = chunk_idx_map.get(chunk_map_idx) {
23 let idx = bitset_chunk_idx[chunk_idx as usize][chunk_piece] as usize;
24 let word = if let Some(word) = bitset_canonical.get(idx) {
27 let (real_idx, mapping) = bitset_canonicalized[idx - bitset_canonical.len()];
28 let mut word = bitset_canonical[real_idx as usize];
29 let should_invert = mapping & (1 << 6) != 0;
34 let quantity = mapping & ((1 << 6) - 1);
35 if mapping & (1 << 7) != 0 {
37 word >>= quantity as u64;
39 word = word.rotate_left(quantity as u32);
43 (word & (1 << (needle % 64) as u64)) != 0
46 fn decode_prefix_sum(short_offset_run_header: u32) -> u32 {
47 short_offset_run_header & ((1 << 21) - 1)
50 fn decode_length(short_offset_run_header: u32) -> usize {
51 (short_offset_run_header >> 21) as usize
55 fn skip_search<const SOR: usize, const OFFSETS: usize>(
57 short_offset_runs: &[u32; SOR],
58 offsets: &[u8; OFFSETS],
60 // Note that this *cannot* be past the end of the array, as the last
61 // element is greater than std::char::MAX (the largest possible needle).
63 // So, we cannot have found it (i.e. Ok(idx) + 1 != length) and the correct
64 // location cannot be past it, so Err(idx) != length either.
66 // This means that we can avoid bounds checking for the accesses below, too.
68 match short_offset_runs.binary_search_by_key(&(needle << 11), |header| header << 11) {
73 let mut offset_idx = decode_length(short_offset_runs[last_idx]);
74 let length = if let Some(next) = short_offset_runs.get(last_idx + 1) {
75 decode_length(*next) - offset_idx
77 offsets.len() - offset_idx
80 last_idx.checked_sub(1).map(|prev| decode_prefix_sum(short_offset_runs[prev])).unwrap_or(0);
82 let total = needle - prev;
83 let mut prefix_sum = 0;
84 for _ in 0..(length - 1) {
85 let offset = offsets[offset_idx];
86 prefix_sum += offset as u32;
87 if prefix_sum > total {