Debian Codegraph @

lib/unistring/uninorm/u-normalize-internal.h

raw
1 /* Decomposition and composition of Unicode strings.
2 Copyright (C) 2009-2026 Free Software Foundation, Inc.
3 Written by Bruno Haible <[email protected]>, 2009.
4
5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation; either version 2.1 of the
8 License, or (at your option) any later version.
9
10 This file is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 UNIT *
19 FUNC (uninorm_t nf, const UNIT *s, size_t n,
20 UNIT *resultbuf, size_t *lengthp)
21 {
22 int (*decomposer) (ucs4_t uc, ucs4_t *decomposition) = nf->decomposer;
23 ucs4_t (*composer) (ucs4_t uc1, ucs4_t uc2) = nf->composer;
24
25 /* The result being accumulated. */
26 UNIT *result;
27 size_t allocated;
28 if (resultbuf == NULL)
29 {
30 result = NULL;
31 allocated = 0;
32 }
33 else
34 {
35 result = resultbuf;
36 allocated = *lengthp;
37 }
38 size_t length = 0;
39
40 /* The buffer for sorting. */
41 #define SORTBUF_PREALLOCATED 64
42 struct ucs4_with_ccc sortbuf_preallocated[2 * SORTBUF_PREALLOCATED];
43 struct ucs4_with_ccc *sortbuf = /* array of size 2 * sortbuf_allocated */
44 sortbuf_preallocated;
45 size_t sortbuf_allocated = SORTBUF_PREALLOCATED;
46 size_t sortbuf_count = 0;
47
48 {
49 const UNIT *s_end = s + n;
50
51 for (;;)
52 {
53 int count;
54 ucs4_t decomposed[UC_DECOMPOSITION_MAX_LENGTH];
55 int decomposed_count;
56
57 if (s < s_end)
58 {
59 /* Fetch the next character. */
60 count = U_MBTOUC_UNSAFE (&decomposed[0], s, s_end - s);
61 decomposed_count = 1;
62
63 /* Decompose it, recursively.
64 It would be possible to precompute the recursive decomposition
65 and store it in a table. But this would significantly increase
66 the size of the decomposition tables, because for example for
67 U+1FC1 the recursive canonical decomposition and the recursive
68 compatibility decomposition are different. */
69 for (int curr = 0; curr < decomposed_count; )
70 {
71 /* Invariant: decomposed[0..curr-1] is fully decomposed, i.e.
72 all elements are atomic. */
73 ucs4_t curr_decomposed[UC_DECOMPOSITION_MAX_LENGTH];
74 int curr_decomposed_count;
75
76 curr_decomposed_count = decomposer (decomposed[curr], curr_decomposed);
77 if (curr_decomposed_count >= 0)
78 {
79 /* Move curr_decomposed[0..curr_decomposed_count-1] over
80 decomposed[curr], making room. It's not worth using
81 memcpy() here, since the counts are so small. */
82 int shift = curr_decomposed_count - 1;
83
84 if (shift < 0)
85 abort ();
86 if (shift > 0)
87 {
88 decomposed_count += shift;
89 if (decomposed_count > UC_DECOMPOSITION_MAX_LENGTH)
90 abort ();
91 for (int j = decomposed_count - 1 - shift; j > curr; j--)
92 decomposed[j + shift] = decomposed[j];
93 }
94 for (; shift >= 0; shift--)
95 decomposed[curr + shift] = curr_decomposed[shift];
96 }
97 else
98 {
99 /* decomposed[curr] is atomic. */
100 curr++;
101 }
102 }
103 }
104 else
105 {
106 count = 0;
107 decomposed_count = 0;
108 }
109
110 int i = 0;
111 for (;;)
112 {
113 ucs4_t uc;
114 int ccc;
115
116 if (s < s_end)
117 {
118 /* Fetch the next character from the decomposition. */
119 if (i == decomposed_count)
120 break;
121 uc = decomposed[i];
122 ccc = uc_combining_class (uc);
123 }
124 else
125 {
126 /* End of string reached. */
127 uc = 0;
128 ccc = 0;
129 }
130
131 if (ccc == 0)
132 {
133 /* Apply the canonical ordering algorithm to the accumulated
134 sequence of characters. */
135 if (sortbuf_count > 1)
136 gl_uninorm_decompose_merge_sort_inplace (sortbuf, sortbuf_count,
137 sortbuf + sortbuf_count);
138
139 if (composer != NULL)
140 {
141 /* Attempt to combine decomposed characters, as specified
142 in the Unicode Standard Annex #15 "Unicode Normalization
143 Forms". We need to check
144 1. whether the first accumulated character is a
145 "starter" (i.e. has ccc = 0). This is usually the
146 case. But when the string starts with a
147 non-starter, the sortbuf also starts with a
148 non-starter. Btw, this check could also be
149 omitted, because the composition table has only
150 entries (code1, code2) for which code1 is a
151 starter; if the first accumulated character is not
152 a starter, no lookup will succeed.
153 2. If the sortbuf has more than one character, check
154 for each of these characters that are not "blocked"
155 from the starter (i.e. have a ccc that is higher
156 than the ccc of the previous character) whether it
157 can be combined with the first character.
158 3. If only one character is left in sortbuf, check
159 whether it can be combined with the next character
160 (also a starter). */
161 if (sortbuf_count > 0 && sortbuf[0].ccc == 0)
162 {
163 for (size_t j = 1; j < sortbuf_count; )
164 {
165 if (sortbuf[j].ccc > sortbuf[j - 1].ccc)
166 {
167 ucs4_t combined =
168 composer (sortbuf[0].code, sortbuf[j].code);
169 if (combined)
170 {
171 sortbuf[0].code = combined;
172 /* sortbuf[0].ccc = 0, still valid. */
173 for (size_t k = j + 1; k < sortbuf_count; k++)
174 sortbuf[k - 1] = sortbuf[k];
175 sortbuf_count--;
176 continue;
177 }
178 }
179 j++;
180 }
181 if (s < s_end && sortbuf_count == 1)
182 {
183 ucs4_t combined =
184 composer (sortbuf[0].code, uc);
185 if (combined)
186 {
187 uc = combined;
188 ccc = 0;
189 /* uc could be further combined with subsequent
190 characters. So don't put it into sortbuf[0] in
191 this round, only in the next round. */
192 sortbuf_count = 0;
193 }
194 }
195 }
196 }
197
198 for (size_t j = 0; j < sortbuf_count; j++)
199 {
200 ucs4_t muc = sortbuf[j].code;
201
202 /* Append muc to the result accumulator. */
203 if (length < allocated)
204 {
205 int ret =
206 U_UCTOMB (result + length, muc, allocated - length);
207 if (ret == -1)
208 {
209 errno = EINVAL;
210 goto fail;
211 }
212 if (ret >= 0)
213 {
214 length += ret;
215 goto done_appending;
216 }
217 }
218 {
219 size_t old_allocated = allocated;
220 size_t new_allocated = 2 * old_allocated;
221 if (new_allocated < 64)
222 new_allocated = 64;
223 if (new_allocated < old_allocated) /* integer overflow? */
224 abort ();
225 {
226 UNIT *larger_result;
227 if (result == NULL)
228 {
229 larger_result =
230 (UNIT *) malloc (new_allocated * sizeof (UNIT));
231 if (larger_result == NULL)
232 {
233 errno = ENOMEM;
234 goto fail;
235 }
236 }
237 else if (result == resultbuf)
238 {
239 larger_result =
240 (UNIT *) malloc (new_allocated * sizeof (UNIT));
241 if (larger_result == NULL)
242 {
243 errno = ENOMEM;
244 goto fail;
245 }
246 U_CPY (larger_result, resultbuf, length);
247 }
248 else
249 {
250 larger_result =
251 (UNIT *) realloc (result, new_allocated * sizeof (UNIT));
252 if (larger_result == NULL)
253 {
254 errno = ENOMEM;
255 goto fail;
256 }
257 }
258 result = larger_result;
259 allocated = new_allocated;
260 {
261 int ret =
262 U_UCTOMB (result + length, muc, allocated - length);
263 if (ret == -1)
264 {
265 errno = EINVAL;
266 goto fail;
267 }
268 if (ret < 0)
269 abort ();
270 length += ret;
271 goto done_appending;
272 }
273 }
274 }
275 done_appending: ;
276 }
277
278 /* sortbuf is now empty. */
279 sortbuf_count = 0;
280 }
281
282 if (!(s < s_end))
283 /* End of string reached. */
284 break;
285
286 /* Append (uc, ccc) to sortbuf. */
287 if (sortbuf_count == sortbuf_allocated)
288 {
289 sortbuf_allocated = 2 * sortbuf_allocated;
290 if (sortbuf_allocated < sortbuf_count) /* integer overflow? */
291 abort ();
292 struct ucs4_with_ccc *new_sortbuf =
293 (struct ucs4_with_ccc *) malloc (2 * sortbuf_allocated * sizeof (struct ucs4_with_ccc));
294 if (new_sortbuf == NULL)
295 {
296 errno = ENOMEM;
297 goto fail;
298 }
299 memcpy (new_sortbuf, sortbuf,
300 sortbuf_count * sizeof (struct ucs4_with_ccc));
301 if (sortbuf != sortbuf_preallocated)
302 free (sortbuf);
303 sortbuf = new_sortbuf;
304 }
305 sortbuf[sortbuf_count].code = uc;
306 sortbuf[sortbuf_count].ccc = ccc;
307 sortbuf_count++;
308
309 i++;
310 }
311
312 if (!(s < s_end))
313 /* End of string reached. */
314 break;
315
316 s += count;
317 }
318 }
319
320 if (length == 0)
321 {
322 if (result == NULL)
323 {
324 /* Return a non-NULL value. NULL means error. */
325 result = (UNIT *) malloc (1);
326 if (result == NULL)
327 {
328 errno = ENOMEM;
329 goto fail;
330 }
331 }
332 }
333 else if (result != resultbuf && length < allocated)
334 {
335 /* Shrink the allocated memory if possible. */
336 UNIT *memory = (UNIT *) realloc (result, length * sizeof (UNIT));
337 if (memory != NULL)
338 result = memory;
339 }
340
341 if (sortbuf_count > 0)
342 abort ();
343 if (sortbuf != sortbuf_preallocated)
344 free (sortbuf);
345
346 *lengthp = length;
347 return result;
348
349 fail:
350 {
351 int saved_errno = errno;
352 if (sortbuf != sortbuf_preallocated)
353 free (sortbuf);
354 if (result != resultbuf)
355 free (result);
356 errno = saved_errno;
357 }
358 return NULL;
359 }