unicode

Branch: main

Switch branches or tags

Branch: main
Go to file t

413 files indexed

History
Code

tools/ucd/normalization_scan.mbt
1///|2/// The scan table covers 32 BMP code points per block, like the norm16 trie.3const NormalizationScanShift : Int32 = 545///|6/// Supplementary groups with flags store them in blocks of 16 code points.7const NormalizationPairShift : Int32 = 489///|10/// Scan flag of a leading surrogate; Quick_Check bits stay below it.11const NormalizationScanLeadSurrogate : Int32 = 0x801213///|14/// Reduce packed properties to the byte the UTF-16 scan tests: bit 0 marks a15/// nonzero CCC and bits 1..6 are the Quick_Check bits 8..13. A properties mask16/// `255 | quick_check_bits` therefore becomes a scan mask by shifting right 7.17fn normalization_scan_flags(properties : Int32) -> Int32 {18  let quick_check = properties >> 8 << 119  if (properties & 255) != 0 {20    quick_check | 121  } else {22    quick_check23  }24}2526///|27/// Emit private UTF-16 scan data next to the normalizer's hot loops. The28/// published lookup functions are not inlined across packages, so the scan29/// reads these one-byte flags itself and asks for full properties only where30/// it stops.31pub fn emit_normalization_scan(32  data : UnicodeData,33  derived_properties : String,34) -> String raise {35  let values = normalization_values(data.ccc, derived_properties).map(36    normalization_scan_flags,37  )38  let lead_flags = Array::make(1024, 0)39  for cp in NormalizationBmpLimit..<=@emitter.MaxCodePoint {40    let lead = (cp - NormalizationBmpLimit) >> 1041    lead_flags[lead] = lead_flags[lead] | values[cp]42  }43  for cp in 0xD800..<0xE000 {44    guard values[cp] == 0 else {45      fail("Surrogate code points must have default normalization properties")46    }47  }48  let mut last = @emitter.MaxCodePoint49  while last >= NormalizationBmpLimit && values[last] == 0 {50    last -= 151  }52  // The scan needs only CCC/Quick_Check flags, not decomposition/composition53  // record indices. All code points at or above this limit are safe starters.54  let limit = last + 155  let lead_limit = (limit - NormalizationBmpLimit + 1023) >> 1056  let tail_lead = (limit - NormalizationBmpLimit) >> 1057  let tail_trail = 0xDC00 + ((limit - NormalizationBmpLimit) & 1023)58  for cp in NormalizationBmpLimit..<=@emitter.MaxCodePoint {59    let lead = (cp - NormalizationBmpLimit) >> 1060    let trail = 0xDC00 + (cp & 1023)61    let default_tail = lead > tail_lead ||62      (lead == tail_lead && trail >= tail_trail)63    guard default_tail == (cp >= limit) else {64      fail("Normalization UTF-16 boundary mismatch at code point \{cp}")65    }66    if default_tail {67      guard values[cp] == 0 else {68        fail("Nonzero normalization scan tail at code point \{cp}")69      }70    } else {71      guard lead >= 0 && lead < lead_limit else {72        fail("Normalization lead index out of bounds at code point \{cp}")73      }74      guard (lead_flags[lead] & values[cp]) == values[cp] else {75        fail("Lead surrogate summary lost properties at code point \{cp}")76      }77    }78  }79  // Leading surrogates have no flags of their own. Marking them lets the scan80  // find a pair with the lookup it does for every other BMP code unit.81  let bmp_values = values[:NormalizationBmpLimit].to_owned()82  for cp in 0xD800..<0xDC00 {83    bmp_values[cp] = NormalizationScanLeadSurrogate84  }85  let block_size = 1 << NormalizationScanShift86  let bmp = @emitter.deduplicate_blocks(bmp_values, block_size)87  guard bmp.ids.all(id => id >= 0 && id < 256) else {88    fail("Normalization scan block indices exceed their encoded width")89  }90  // The scan reads both tables unchecked for every UTF-16 code unit.91  for cp in 0..<NormalizationBmpLimit {92    let index = (93        bmp.ids[cp >> NormalizationScanShift] << NormalizationScanShift94      ) |95      (cp & (block_size - 1))96    guard index < bmp.blocks.length() else {97      fail("Normalization scan index out of bounds at code point \{cp}")98    }99    guard bmp.blocks[index] == bmp_values[cp] else {100      fail("Normalization scan flags mismatch at code point \{cp}")101    }102  }103  // Only a few groups of 1024 supplementary code points have flags. Give each104  // a slot holding its own flags, so the scan never has to ask for the full105  // properties of a pair. Slot 0 is clear and serves every other group.106  let pair_block_size = 1 << NormalizationPairShift107  let pair_blocks_per_group = 1024 / pair_block_size108  let lead_slots = Array::make(lead_limit, 0)109  let pair_values = Array::make(1024, 0)110  for lead in 0..<lead_limit {111    if lead_flags[lead] != 0 {112      lead_slots[lead] = pair_values.length() / 1024113      let start = NormalizationBmpLimit + (lead << 10)114      pair_values.append(values[start:start + 1024])115    }116  }117  let pairs = @emitter.deduplicate_blocks(pair_values, pair_block_size)118  guard lead_slots.all(slot => slot < 256) &&119    pairs.ids.all(id => id >= 0 && id < 256) else {120    fail("Normalization pair indices exceed their encoded width")121  }122  // The scan reads these tables unchecked for every pair below the tail.123  for lead in 0..<lead_limit {124    for trail in 0..<1024 {125      let cp = NormalizationBmpLimit + (lead << 10) + trail126      let block_index = lead_slots[lead] * pair_blocks_per_group +127        (trail >> NormalizationPairShift)128      guard block_index < pairs.ids.length() else {129        fail("Normalization pair block out of bounds at code point \{cp}")130      }131      let index = (pairs.ids[block_index] << NormalizationPairShift) |132        (trail & (pair_block_size - 1))133      guard index < pairs.blocks.length() else {134        fail("Normalization pair index out of bounds at code point \{cp}")135      }136      guard pairs.blocks[index] == values[cp] else {137        fail("Normalization pair flags mismatch at code point \{cp}")138      }139    }140  }141  let out = @emitter.Emitter::new()142  out.write_file_header(143    "UTF-16 normalization scan summaries", "UnicodeData.txt and DerivedNormalizationProps.txt",144  )145  out.write_byte_array(146    "BMP scan block indices (\{block_size} code points per block)",147    "normalization_scan_index",148    bmp.ids,149  )150  out.write_byte_array(151    "BMP scan flags. Bit 0: CCC is nonzero; bits 1..6: Quick_Check bits 8..13 of the packed properties; bit 7: leading surrogate",152    "normalization_scan_flags",153    bmp.blocks,154  )155  out.write_byte_array(156    "ORed scan flags for each group of 1024 supplementary code points",157    "normalization_lead_flags",158    lead_flags[:lead_limit].to_owned(),159  )160  out.write_byte_array(161    "Slot of each group of 1024 supplementary code points; slot 0 has no flags",162    "normalization_lead_slots", lead_slots,163  )164  out.write_byte_array(165    "Pair block indices (\{pair_blocks_per_group} blocks of \{pair_block_size} code points per slot)",166    "normalization_pair_index",167    pairs.ids,168  )169  out.write_byte_array(170    "Scan flags of supplementary code points, laid out like the BMP ones",171    "normalization_pair_flags",172    pairs.blocks,173  )174  out.write(175    (176      $|///|177      $|const NormalizationPairShift : Int = \{NormalizationPairShift}178      $|179      $|///|180      $|const NormalizationPairBlockMask : Int = \{pair_block_size - 1}181      $|182      $|///|183      $|const NormalizationScanShift : Int = \{NormalizationScanShift}184      $|185      $|///|186      $|const NormalizationScanBlockMask : Int = \{block_size - 1}187      $|188      $|///|189      $|const NormalizationScanLeadSurrogate : Int = \{NormalizationScanLeadSurrogate}190      $|191    ),192  )193  out.write(194    (195      $|///|196      $|// The all-zero property tail begins at this UTF-16 pair. No decoding or197      $|// table access is needed there; earlier pairs use the summaries above.198      $|const NormalizationTailLeadIndex : Int = \{tail_lead}199      $|200      $|///|201      $|const NormalizationTailTrail : Int = \{tail_trail}202      $|203    ),204  )205  out.finish()206}207