Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
normalization.cpp
Go to the documentation of this file.
2#include "table_store.hpp"
4
5#include <cstdint>
6
7namespace ada::idna {
8
9// See
10// https://github.com/uni-algo/uni-algo/blob/c612968c5ed3ace39bde4c894c24286c5f2c7fe2/include/uni_algo/impl/impl_norm.h#L467
11constexpr char32_t hangul_sbase = 0xAC00;
12constexpr char32_t hangul_tbase = 0x11A7;
13constexpr char32_t hangul_vbase = 0x1161;
14constexpr char32_t hangul_lbase = 0x1100;
15constexpr char32_t hangul_lcount = 19;
16constexpr char32_t hangul_vcount = 21;
17constexpr char32_t hangul_tcount = 28;
18constexpr char32_t hangul_ncount = hangul_vcount * hangul_tcount;
19constexpr char32_t hangul_scount =
21
22// Canonical decomposition length (0 if none / compatibility-only / Hangul
23// syllable). Length 1 means a singleton mapping (character is not NFC form).
24// Length >= 2 means a primary composite that is already the NFC form of its
25// decomposition (e.g. U+00E9 LATIN SMALL LETTER E WITH ACUTE).
26static size_t canonical_decomp_length(char32_t current_character) noexcept {
27 if (current_character >= hangul_sbase &&
28 current_character < hangul_sbase + hangul_scount) {
29 // Hangul precomposed syllables are NFC.
30 return 0;
31 }
32 if (current_character >= 0x110000) {
33 return 0;
34 }
35 const uint8_t di = decomposition_index[current_character >> 8];
36 const uint16_t* const decomposition =
37 decomposition_block_row(di) + (current_character % 256);
38 size_t decomposition_length =
39 (decomposition[1] >> 2) - (decomposition[0] >> 2);
40 if ((decomposition_length > 0) && (decomposition[0] & 1)) {
41 decomposition_length = 0; // compatibility-only: ignored for NFC
42 }
43 return decomposition_length;
44}
45
46std::pair<bool, size_t> compute_decomposition_length(
47 const std::u32string_view input) noexcept {
48 bool decomposition_needed{false};
49 size_t additional_elements{0};
50 for (char32_t current_character : input) {
51 size_t decomposition_length{0};
52
53 if (current_character >= hangul_sbase &&
54 current_character < hangul_sbase + hangul_scount) {
55 // Full NFD-style Hangul decomp for the decompose() step.
56 decomposition_length = 2;
57 if ((current_character - hangul_sbase) % hangul_tcount) {
58 decomposition_length = 3;
59 }
60 } else if (current_character < 0x110000) {
61 const uint8_t di = decomposition_index[current_character >> 8];
62 const uint16_t* const decomposition =
63 decomposition_block_row(di) + (current_character % 256);
64 decomposition_length = (decomposition[1] >> 2) - (decomposition[0] >> 2);
65 if ((decomposition_length > 0) && (decomposition[0] & 1)) {
66 decomposition_length = 0;
67 }
68 }
69 if (decomposition_length != 0) {
70 decomposition_needed = true;
71 additional_elements += decomposition_length - 1;
72 }
73 }
74 return {decomposition_needed, additional_elements};
75}
76
77void decompose(std::u32string& input, size_t additional_elements) {
78 input.resize(input.size() + additional_elements);
79 for (size_t descending_idx = input.size(),
80 input_count = descending_idx - additional_elements;
81 input_count--;) {
82 if (input[input_count] >= hangul_sbase &&
83 input[input_count] < hangul_sbase + hangul_scount) {
84 // Hangul decomposition.
85 char32_t s_index = input[input_count] - hangul_sbase;
86 if (s_index % hangul_tcount != 0) {
87 input[--descending_idx] = hangul_tbase + s_index % hangul_tcount;
88 }
89 input[--descending_idx] =
91 input[--descending_idx] = hangul_lbase + s_index / hangul_ncount;
92 } else if (input[input_count] < 0x110000) {
93 const uint16_t* decomposition =
95 decomposition_index[input[input_count] >> 8]) +
96 (input[input_count] % 256);
97 uint16_t decomposition_length =
98 (decomposition[1] >> 2) - (decomposition[0] >> 2);
99 if (decomposition_length > 0 && (decomposition[0] & 1)) {
100 decomposition_length = 0;
101 }
102 if (decomposition_length > 0) {
103 const size_t base = static_cast<size_t>(decomposition[0] >> 2);
104 if (base + decomposition_length > decomposition_data_size) {
105 input[--descending_idx] = input[input_count];
106 } else {
107 while (decomposition_length-- > 0) {
108 input[--descending_idx] =
109 decomposition_data[base + decomposition_length];
110 }
111 }
112 } else {
113 input[--descending_idx] = input[input_count];
114 }
115 } else {
116 input[--descending_idx] = input[input_count];
117 }
118 }
119}
120
121uint8_t get_ccc(char32_t c) noexcept {
122 if (c >= 0x110000) {
123 return 0;
124 }
125 return ccc_block_row(ccc_index[c >> 8])[c % 256];
126}
127
128void sort_marks(std::u32string& input) {
129 for (size_t idx = 1; idx < input.size(); idx++) {
130 uint8_t ccc = get_ccc(input[idx]);
131 if (ccc == 0) {
132 continue;
133 }
134 auto current_character = input[idx];
135 size_t back_idx = idx;
136 while (back_idx != 0 && get_ccc(input[back_idx - 1]) > ccc) {
137 input[back_idx] = input[back_idx - 1];
138 back_idx--;
139 }
140 input[back_idx] = current_character;
141 }
142}
143
144void decompose_nfc(std::u32string& input) {
149 auto [decomposition_needed, additional_elements] =
151 if (decomposition_needed) {
152 decompose(input, additional_elements);
153 }
154 sort_marks(input);
155}
156
157// Returns true if the composition row of a starter has a pair with `second`.
158static bool has_composition(const uint16_t* composition,
159 char32_t second) noexcept {
160 int left = composition[0];
161 int right = composition[1];
162 if (left < 0 || right <= left ||
163 static_cast<size_t>(right) > composition_data_size) {
164 return false;
165 }
166 while (left + 2 < right) {
167 int middle = left + (((right - left) >> 1) & ~1);
168 if (composition_data[static_cast<size_t>(middle)] <= second) {
169 left = middle;
170 }
171 if (composition_data[static_cast<size_t>(middle)] >= second) {
172 right = middle;
173 }
174 }
175 return static_cast<size_t>(left + 1) < composition_data_size &&
176 composition_data[static_cast<size_t>(left)] == second;
177}
178
179// Returns true if a composition step would change the string.
180static bool would_compose(std::u32string_view input) noexcept {
181 for (size_t input_count = 0; input_count < input.size();) {
182 const char32_t current = input[input_count];
183 if (current >= hangul_lbase && current < hangul_lbase + hangul_lcount) {
184 if (input_count + 1 < input.size() &&
185 input[input_count + 1] >= hangul_vbase &&
186 input[input_count + 1] < hangul_vbase + hangul_vcount) {
187 return true;
188 }
189 ++input_count;
190 continue;
191 }
192 if (current >= hangul_sbase && current < hangul_sbase + hangul_scount) {
193 if ((current - hangul_sbase) % hangul_tcount == 0 &&
194 input_count + 1 < input.size() &&
195 input[input_count + 1] > hangul_tbase &&
196 input[input_count + 1] < hangul_tbase + hangul_tcount) {
197 return true;
198 }
199 ++input_count;
200 continue;
201 }
202 if (current < 0x110000) {
203 const uint16_t* composition =
205 (current % 256);
206 int32_t previous_ccc = -1;
207 size_t j = input_count;
208 for (; j + 1 < input.size(); ++j) {
209 uint8_t ccc = get_ccc(input[j + 1]);
210 if (composition[1] != composition[0] && previous_ccc < ccc &&
211 has_composition(composition, input[j + 1])) {
212 return true;
213 }
214 if (ccc == 0) {
215 break;
216 }
217 previous_ccc = ccc;
218 }
219 input_count = j + 1;
220 continue;
221 }
222 ++input_count;
223 }
224 return false;
225}
226
227// Trailing canonical combining class of a character: the combining class of the
228// last code point of its canonical decomposition, or the character's own class
229// when it has none. A precomposed starter such as U+00E1 (a + U+0301, class
230// 230) has class 0 but a nonzero trailing class, so a following mark of lower
231// class reorders past the hidden mark during normalization.
232static uint8_t trailing_ccc(char32_t c) noexcept {
233 const size_t length = canonical_decomp_length(c);
234 if (length == 0) {
235 return get_ccc(c);
236 }
237 const uint16_t* const decomposition =
238 decomposition_block_row(decomposition_index[c >> 8]) + (c % 256);
239 const size_t base = decomposition[0] >> 2;
240 return get_ccc(decomposition_data[base + length - 1]);
241}
242
243void compose(std::u32string& input);
244
245// A character that has a canonical decomposition is in NFC form only if that
246// decomposition composes back to exactly it. Singletons never do (e.g. U+212B
247// ANGSTROM SIGN). Composition exclusions do not either: their decomposition
248// composes to a different primary composite (e.g. U+1F71 -> U+03B1 U+0301 ->
249// U+03AC) or does not compose at all (e.g. U+0958 DEVANAGARI LETTER QA ->
250// U+0915 U+093C), and non-starter decompositions such as U+0344 -> U+0308
251// U+0301 stay decomposed. All are NFC_Quick_Check=No and must be normalized.
252// Since Unicode 16 the first code point of a decomposition can also compose
253// with the preceding character: U+16121 is U+1611E U+1611E, so U+1611E U+16121
254// normalizes to U+16121 U+1611E.
255static bool decomposition_is_not_nfc(char32_t previous, char32_t c) noexcept {
256 if (c >= hangul_sbase && c < hangul_sbase + hangul_scount) {
257 return false;
258 }
259 if (c >= 0x110000) {
260 return false;
261 }
262 const uint16_t* const decomposition =
263 decomposition_block_row(decomposition_index[c >> 8]) + (c % 256);
264 const size_t length = (decomposition[1] >> 2) - (decomposition[0] >> 2);
265 if (length == 0 || (decomposition[0] & 1)) {
266 return false; // no canonical decomposition (or compatibility-only)
267 }
268 if (length == 1) {
269 return true; // singleton
270 }
271 const size_t base = decomposition[0] >> 2;
272 if (base + length > decomposition_data_size) {
273 return false;
274 }
275 // Recompose the canonical decomposition; if it does not collapse back to c,
276 // then c is an exclusion / non-starter decomposition and is not NFC.
277 std::u32string decomposed(decomposition_data + base,
278 decomposition_data + base + length);
279 compose(decomposed);
280 if (!(decomposed.size() == 1 && decomposed[0] == c)) {
281 return true;
282 }
283 return previous < 0x110000 &&
286 (previous % 256),
288}
289
290bool is_already_nfc(std::u32string_view input) noexcept {
291 if (input.empty()) {
292 return true;
293 }
294 if (!tables_are_ready() && !ensure_tables()) {
295 return false;
296 }
297 // 1) A character whose canonical decomposition does not compose back to it is
298 // not NFC: singletons (e.g. U+212B), composition exclusions (e.g. U+0958)
299 // and non-starter decompositions (e.g. U+0344), or one whose
300 // decomposition starts with a code point that composes with the previous
301 // character (e.g. U+1611E U+16121).
302 char32_t previous = 0x110000; // none
303 for (char32_t c : input) {
304 if (decomposition_is_not_nfc(previous, c)) {
305 return false;
306 }
307 previous = c;
308 }
309 // 2) Combining marks already in canonical order. prev_ccc carries the
310 // trailing class of the previous character's canonical decomposition so a
311 // composite starter followed by a lower-class mark is caught.
312 uint8_t prev_ccc = 0;
313 for (char32_t c : input) {
314 uint8_t ccc = get_ccc(c);
315 if (ccc != 0 && prev_ccc > ccc) {
316 return false;
317 }
318 prev_ccc = trailing_ccc(c);
319 }
320 // 3) No pairwise composition would apply (including Hangul L+V / LV+T).
321 return !would_compose(input);
322}
323
324void compose(std::u32string& input) {
329 size_t input_count{0};
330 size_t composition_count{0};
331 for (; input_count < input.size(); input_count++, composition_count++) {
332 input[composition_count] = input[input_count];
333 if (input[input_count] >= hangul_lbase &&
334 input[input_count] < hangul_lbase + hangul_lcount) {
335 if (input_count + 1 < input.size() &&
336 input[input_count + 1] >= hangul_vbase &&
337 input[input_count + 1] < hangul_vbase + hangul_vcount) {
338 input[composition_count] =
340 ((input[input_count] - hangul_lbase) * hangul_vcount +
341 input[input_count + 1] - hangul_vbase) *
343 input_count++;
344 if (input_count + 1 < input.size() &&
345 input[input_count + 1] > hangul_tbase &&
346 input[input_count + 1] < hangul_tbase + hangul_tcount) {
347 input[composition_count] += input[++input_count] - hangul_tbase;
348 }
349 }
350 } else if (input[input_count] >= hangul_sbase &&
351 input[input_count] < hangul_sbase + hangul_scount) {
352 if ((input[input_count] - hangul_sbase) % hangul_tcount == 0 &&
353 input_count + 1 < input.size() &&
354 input[input_count + 1] > hangul_tbase &&
355 input[input_count + 1] < hangul_tbase + hangul_tcount) {
356 input[composition_count] += input[++input_count] - hangul_tbase;
357 }
358 } else if (input[input_count] < 0x110000) {
359 const uint16_t* composition =
360 composition_block_row(composition_index[input[input_count] >> 8]) +
361 (input[input_count] % 256);
362 size_t initial_composition_count = composition_count;
363 for (int32_t previous_ccc = -1; input_count + 1 < input.size();
364 input_count++) {
365 uint8_t ccc = get_ccc(input[input_count + 1]);
366
367 if (composition[1] != composition[0] && previous_ccc < ccc) {
368 int left = composition[0];
369 int right = composition[1];
370 if (left < 0 || right < left ||
371 static_cast<size_t>(right) > composition_data_size) {
372 break;
373 }
374 while (left + 2 < right) {
375 int middle = left + (((right - left) >> 1) & ~1);
376 if (composition_data[static_cast<size_t>(middle)] <=
377 input[input_count + 1]) {
378 left = middle;
379 }
380 if (composition_data[static_cast<size_t>(middle)] >=
381 input[input_count + 1]) {
382 right = middle;
383 }
384 }
385 if (static_cast<size_t>(left + 1) < composition_data_size &&
386 composition_data[static_cast<size_t>(left)] ==
387 input[input_count + 1]) {
388 char32_t composed = composition_data[static_cast<size_t>(left + 1)];
389 input[initial_composition_count] = composed;
390 composition =
392 (composed % 256);
393 continue;
394 }
395 }
396
397 if (ccc == 0) {
398 break;
399 }
400 previous_ccc = ccc;
401 input[++composition_count] = input[input_count + 1];
402 }
403 }
404 }
405
406 if (composition_count < input_count) {
407 input.resize(composition_count);
408 }
409}
410
411bool normalize(std::u32string& input) {
416 if (!ensure_tables() || decomposition_index == nullptr ||
417 composition_index == nullptr) {
418 return false;
419 }
420 if (is_already_nfc(input)) {
421 return true;
422 }
423 decompose_nfc(input);
424 compose(input);
425 return true;
426}
427
428} // namespace ada::idna
bool tables_are_ready() noexcept
void compose(std::u32string &input)
constexpr char32_t hangul_tcount
constexpr int32_t base
void decompose(std::u32string &input, size_t additional_elements)
const uint8_t * ccc_block_row(uint8_t bi) noexcept
const uint8_t * ccc_index
void decompose_nfc(std::u32string &input)
const char32_t * decomposition_data
const uint8_t * decomposition_index
constexpr char32_t hangul_ncount
static bool decomposition_is_not_nfc(char32_t previous, char32_t c) noexcept
constexpr char32_t hangul_lbase
static bool has_composition(const uint16_t *composition, char32_t second) noexcept
void sort_marks(std::u32string &input)
constexpr char32_t hangul_lcount
constexpr char32_t hangul_scount
constexpr char32_t hangul_sbase
constexpr char32_t hangul_vbase
bool normalize(std::u32string &input)
uint8_t get_ccc(char32_t c) noexcept
const char32_t * composition_data
bool ensure_tables() noexcept
const uint8_t * composition_index
static bool would_compose(std::u32string_view input) noexcept
constexpr size_t decomposition_data_size
const uint16_t * decomposition_block_row(uint8_t bi) noexcept
static uint8_t trailing_ccc(char32_t c) noexcept
bool is_already_nfc(std::u32string_view input) noexcept
std::pair< bool, size_t > compute_decomposition_length(const std::u32string_view input) noexcept
constexpr char32_t hangul_vcount
constexpr char32_t hangul_tbase
const uint16_t * composition_block_row(uint8_t bi) noexcept
static size_t canonical_decomp_length(char32_t current_character) noexcept
constexpr size_t composition_data_size