src/tools/unicode-table-generator/src/range_search.rs

   1 #[inline(always)]
   2 fn bitset_search<
   3     const N: usize,
   4     const CHUNK_SIZE: usize,
   5     const N1: usize,
   6     const CANONICAL: usize,
   7     const CANONICALIZED: usize,
   8 >(
   9     needle: u32,
  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],
  14 ) -> bool {
  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) {
  19         v
  20     } else {
  21         return false;
  22     };
  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) {
  25         *word
  26     } else {
  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;
  30         if should_invert {
  31             word = !word;
  32         }
  33         // Lower 6 bits
  34         let quantity = mapping & ((1 << 6) - 1);
  35         if mapping & (1 << 7) != 0 {
  36             // shift
  37             word >>= quantity as u64;
  38         } else {
  39             word = word.rotate_left(quantity as u32);
  40         }
  41         word
  42     };
  43     (word & (1 << (needle % 64) as u64)) != 0
  44 }
  45
  46 fn decode_prefix_sum(short_offset_run_header: u32) -> u32 {
  47     short_offset_run_header & ((1 << 21) - 1)
  48 }
  49
  50 fn decode_length(short_offset_run_header: u32) -> usize {
  51     (short_offset_run_header >> 21) as usize
  52 }
  53
  54 #[inline(always)]
  55 fn skip_search<const SOR: usize, const OFFSETS: usize>(
  56     needle: u32,
  57     short_offset_runs: &[u32; SOR],
  58     offsets: &[u8; OFFSETS],
  59 ) -> bool {
  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).
  62     //
  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.
  65     //
  66     // This means that we can avoid bounds checking for the accesses below, too.
  67     let last_idx =
  68         match short_offset_runs.binary_search_by_key(&(needle << 11), |header| header << 11) {
  69             Ok(idx) => idx + 1,
  70             Err(idx) => idx,
  71         };
  72
  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
  76     } else {
  77         offsets.len() - offset_idx
  78     };
  79     let prev =
  80         last_idx.checked_sub(1).map(|prev| decode_prefix_sum(short_offset_runs[prev])).unwrap_or(0);
  81
  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 {
  88             break;
  89         }
  90         offset_idx += 1;
  91     }
  92     offset_idx % 2 == 1
  93 }