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

   1 use crate::fmt_list;
   2 use crate::raw_emitter::RawEmitter;
   3 use std::convert::TryInto;
   4 use std::fmt::Write as _;
   5 use std::ops::Range;
   6
   7 /// This will get packed into a single u32 before inserting into the data set.
   8 #[derive(Debug, PartialEq)]
   9 struct ShortOffsetRunHeader {
  10     /// Note, we only allow for 21 bits here.
  11     prefix_sum: u32,
  12
  13     /// Note, we actually only allow for 11 bits here. This should be enough --
  14     /// our largest sets are around ~1400 offsets long.
  15     start_idx: u16,
  16 }
  17
  18 impl ShortOffsetRunHeader {
  19     fn pack(&self) -> u32 {
  20         assert!(self.start_idx < (1 << 11));
  21         assert!(self.prefix_sum < (1 << 21));
  22
  23         (self.start_idx as u32) << 21 | self.prefix_sum
  24     }
  25 }
  26
  27 impl RawEmitter {
  28     pub fn emit_skiplist(&mut self, ranges: &[Range<u32>]) {
  29         let mut offsets = Vec::<u32>::new();
  30         let points = ranges.iter().flat_map(|r| vec![r.start, r.end]).collect::<Vec<u32>>();
  31         let mut offset = 0;
  32         for pt in points {
  33             let delta = pt - offset;
  34             offsets.push(delta);
  35             offset = pt;
  36         }
  37         // Guaranteed to terminate, as it's impossible to subtract a value this
  38         // large from a valid char.
  39         offsets.push(std::char::MAX as u32 + 1);
  40         let mut coded_offsets: Vec<u8> = Vec::new();
  41         let mut short_offset_runs: Vec<ShortOffsetRunHeader> = vec![];
  42         let mut iter = offsets.iter().cloned();
  43         let mut prefix_sum = 0;
  44         loop {
  45             let mut any_elements = false;
  46             let mut inserted = false;
  47             let start = coded_offsets.len();
  48             for offset in iter.by_ref() {
  49                 any_elements = true;
  50                 prefix_sum += offset;
  51                 if let Ok(offset) = offset.try_into() {
  52                     coded_offsets.push(offset);
  53                 } else {
  54                     short_offset_runs.push(ShortOffsetRunHeader {
  55                         start_idx: start.try_into().unwrap(),
  56                         prefix_sum,
  57                     });
  58                     // This is just needed to maintain indices even/odd
  59                     // correctly.
  60                     coded_offsets.push(0);
  61                     inserted = true;
  62                     break;
  63                 }
  64             }
  65             if !any_elements {
  66                 break;
  67             }
  68             // We always append the huge char::MAX offset to the end which
  69             // should never be able to fit into the u8 offsets.
  70             assert!(inserted);
  71         }
  72
  73         writeln!(
  74             &mut self.file,
  75             "static SHORT_OFFSET_RUNS: [u32; {}] = [{}];",
  76             short_offset_runs.len(),
  77             fmt_list(short_offset_runs.iter().map(|v| v.pack()))
  78         )
  79         .unwrap();
  80         self.bytes_used += 4 * short_offset_runs.len();
  81         writeln!(
  82             &mut self.file,
  83             "static OFFSETS: [u8; {}] = [{}];",
  84             coded_offsets.len(),
  85             fmt_list(&coded_offsets)
  86         )
  87         .unwrap();
  88         self.bytes_used += coded_offsets.len();
  89
  90         writeln!(&mut self.file, "pub fn lookup(c: char) -> bool {{").unwrap();
  91         writeln!(&mut self.file, "    super::skip_search(",).unwrap();
  92         writeln!(&mut self.file, "        c as u32,").unwrap();
  93         writeln!(&mut self.file, "        &SHORT_OFFSET_RUNS,").unwrap();
  94         writeln!(&mut self.file, "        &OFFSETS,").unwrap();
  95         writeln!(&mut self.file, "    )").unwrap();
  96         writeln!(&mut self.file, "}}").unwrap();
  97     }
  98 }