tools/ucd/normalization_scan.mbt1///|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
///|
/// The scan table covers 32 BMP code points per block, like the norm16 trie.
const NormalizationScanShift : Int32 = 5
///|
/// Supplementary groups with flags store them in blocks of 16 code points.
const NormalizationPairShift : Int32 = 4
///|
/// Scan flag of a leading surrogate; Quick_Check bits stay below it.
const NormalizationScanLeadSurrogate : Int32 = 0x80
///|
/// Reduce packed properties to the byte the UTF-16 scan tests: bit 0 marks a
/// nonzero CCC and bits 1..6 are the Quick_Check bits 8..13. A properties mask
/// `255 | quick_check_bits` therefore becomes a scan mask by shifting right 7.
fn normalization_scan_flags(properties : Int32) -> Int32 {
let quick_check = properties >> 8 << 1
if (properties & 255) != 0 {
quick_check | 1
} else {
quick_check
}
}
///|
/// Emit private UTF-16 scan data next to the normalizer's hot loops. The
/// published lookup functions are not inlined across packages, so the scan
/// reads these one-byte flags itself and asks for full properties only where
/// it stops.
pub fn emit_normalization_scan(
data : UnicodeData,
derived_properties : String,
) -> String raise {
let values = normalization_values(data.ccc, derived_properties).map(
normalization_scan_flags,
)
let lead_flags = Array::make(1024, 0)
for cp in NormalizationBmpLimit..<=@emitter.MaxCodePoint {
let lead = (cp - NormalizationBmpLimit) >> 10
lead_flags[lead] = lead_flags[lead] | values[cp]
}
for cp in 0xD800..<0xE000 {
guard values[cp] == 0 else {
fail("Surrogate code points must have default normalization properties")
}
}
let mut last = @emitter.MaxCodePoint
while last >= NormalizationBmpLimit && values[last] == 0 {
last -= 1
}
// The scan needs only CCC/Quick_Check flags, not decomposition/composition
// record indices. All code points at or above this limit are safe starters.
let limit = last + 1
let lead_limit = (limit - NormalizationBmpLimit + 1023) >> 10
let tail_lead = (limit - NormalizationBmpLimit) >> 10
let tail_trail = 0xDC00 + ((limit - NormalizationBmpLimit) & 1023)
for cp in NormalizationBmpLimit..<=@emitter.MaxCodePoint {
let lead = (cp - NormalizationBmpLimit) >> 10
let trail = 0xDC00 + (cp & 1023)
let default_tail = lead > tail_lead ||
(lead == tail_lead && trail >= tail_trail)
guard default_tail == (cp >= limit) else {
fail("Normalization UTF-16 boundary mismatch at code point \{cp}")
}
if default_tail {
guard values[cp] == 0 else {
fail("Nonzero normalization scan tail at code point \{cp}")
}
} else {
guard lead >= 0 && lead < lead_limit else {
fail("Normalization lead index out of bounds at code point \{cp}")
}
guard (lead_flags[lead] & values[cp]) == values[cp] else {
fail("Lead surrogate summary lost properties at code point \{cp}")
}
}
}
// Leading surrogates have no flags of their own. Marking them lets the scan
// find a pair with the lookup it does for every other BMP code unit.
let bmp_values = values[:NormalizationBmpLimit].to_owned()
for cp in 0xD800..<0xDC00 {
bmp_values[cp] = NormalizationScanLeadSurrogate
}
let block_size = 1 << NormalizationScanShift
let bmp = @emitter.deduplicate_blocks(bmp_values, block_size)
guard bmp.ids.all(id => id >= 0 && id < 256) else {
fail("Normalization scan block indices exceed their encoded width")
}
// The scan reads both tables unchecked for every UTF-16 code unit.
for cp in 0..<NormalizationBmpLimit {
let index = (
bmp.ids[cp >> NormalizationScanShift] << NormalizationScanShift
) |
(cp & (block_size - 1))
guard index < bmp.blocks.length() else {
fail("Normalization scan index out of bounds at code point \{cp}")
}
guard bmp.blocks[index] == bmp_values[cp] else {
fail("Normalization scan flags mismatch at code point \{cp}")
}
}
// Only a few groups of 1024 supplementary code points have flags. Give each
// a slot holding its own flags, so the scan never has to ask for the full
// properties of a pair. Slot 0 is clear and serves every other group.
let pair_block_size = 1 << NormalizationPairShift
let pair_blocks_per_group = 1024 / pair_block_size
let lead_slots = Array::make(lead_limit, 0)
let pair_values = Array::make(1024, 0)
for lead in 0..<lead_limit {
if lead_flags[lead] != 0 {
lead_slots[lead] = pair_values.length() / 1024
let start = NormalizationBmpLimit + (lead << 10)
pair_values.append(values[start:start + 1024])
}
}
let pairs = @emitter.deduplicate_blocks(pair_values, pair_block_size)
guard lead_slots.all(slot => slot < 256) &&
pairs.ids.all(id => id >= 0 && id < 256) else {
fail("Normalization pair indices exceed their encoded width")
}
// The scan reads these tables unchecked for every pair below the tail.
for lead in 0..<lead_limit {
for trail in 0..<1024 {
let cp = NormalizationBmpLimit + (lead << 10) + trail
let block_index = lead_slots[lead] * pair_blocks_per_group +
(trail >> NormalizationPairShift)
guard block_index < pairs.ids.length() else {
fail("Normalization pair block out of bounds at code point \{cp}")
}
let index = (pairs.ids[block_index] << NormalizationPairShift) |
(trail & (pair_block_size - 1))
guard index < pairs.blocks.length() else {
fail("Normalization pair index out of bounds at code point \{cp}")
}
guard pairs.blocks[index] == values[cp] else {
fail("Normalization pair flags mismatch at code point \{cp}")
}
}
}
let out = @emitter.Emitter::new()
out.write_file_header(
"UTF-16 normalization scan summaries", "UnicodeData.txt and DerivedNormalizationProps.txt",
)
out.write_byte_array(
"BMP scan block indices (\{block_size} code points per block)",
"normalization_scan_index",
bmp.ids,
)
out.write_byte_array(
"BMP scan flags. Bit 0: CCC is nonzero; bits 1..6: Quick_Check bits 8..13 of the packed properties; bit 7: leading surrogate",
"normalization_scan_flags",
bmp.blocks,
)
out.write_byte_array(
"ORed scan flags for each group of 1024 supplementary code points",
"normalization_lead_flags",
lead_flags[:lead_limit].to_owned(),
)
out.write_byte_array(
"Slot of each group of 1024 supplementary code points; slot 0 has no flags",
"normalization_lead_slots", lead_slots,
)
out.write_byte_array(
"Pair block indices (\{pair_blocks_per_group} blocks of \{pair_block_size} code points per slot)",
"normalization_pair_index",
pairs.ids,
)
out.write_byte_array(
"Scan flags of supplementary code points, laid out like the BMP ones",
"normalization_pair_flags",
pairs.blocks,
)
out.write(
(
$|///|
$|const NormalizationPairShift : Int = \{NormalizationPairShift}
$|
$|///|
$|const NormalizationPairBlockMask : Int = \{pair_block_size - 1}
$|
$|///|
$|const NormalizationScanShift : Int = \{NormalizationScanShift}
$|
$|///|
$|const NormalizationScanBlockMask : Int = \{block_size - 1}
$|
$|///|
$|const NormalizationScanLeadSurrogate : Int = \{NormalizationScanLeadSurrogate}
$|
),
)
out.write(
(
$|///|
$|// The all-zero property tail begins at this UTF-16 pair. No decoding or
$|// table access is needed there; earlier pairs use the summaries above.
$|const NormalizationTailLeadIndex : Int = \{tail_lead}
$|
$|///|
$|const NormalizationTailTrail : Int = \{tail_trail}
$|
),
)
out.finish()
}