Commit | Line | Data |
---|---|---|
e5a5a138 RK |
1 | /* |
2 | * This file is part of DisOrder | |
3 | * Copyright (C) 2007 Richard Kettlewell | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or modify | |
6 | * it under the terms of the GNU General Public License as published by | |
7 | * the Free Software Foundation; either version 2 of the License, or | |
8 | * (at your option) any later version. | |
9 | * | |
10 | * This program is distributed in the hope that it will be useful, but | |
11 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | * General Public License for more details. | |
14 | * | |
15 | * You should have received a copy of the GNU General Public License | |
16 | * along with this program; if not, write to the Free Software | |
17 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 | |
18 | * USA | |
19 | */ | |
20 | /** @file lib/unicode.c | |
21 | * @brief Unicode support functions | |
22 | * | |
23 | * Here by UTF-8 and UTF-8 we mean the encoding forms of those names (not the | |
35b651f0 RK |
24 | * encoding schemes). The primary encoding form is UTF-32 but convenience |
25 | * wrappers using UTF-8 are provided for a number of functions. | |
e5a5a138 RK |
26 | * |
27 | * The idea is that all the strings that hit the database will be in a | |
28 | * particular normalization form, and for the search and tags database | |
29 | * in case-folded form, so they can be naively compared within the | |
30 | * database code. | |
31 | * | |
32 | * As the code stands this guarantee is not well met! | |
33 | */ | |
34 | ||
35 | #include <config.h> | |
36 | #include "types.h" | |
37 | ||
38 | #include <string.h> | |
39 | #include <stdio.h> /* TODO */ | |
40 | ||
41 | #include "mem.h" | |
42 | #include "vector.h" | |
43 | #include "unicode.h" | |
44 | #include "unidata.h" | |
45 | ||
46 | /** @defgroup utftransform Functions that transform between different Unicode encoding forms */ | |
47 | /*@{*/ | |
48 | ||
49 | /** @brief Convert UTF-32 to UTF-8 | |
50 | * @param s Source string | |
51 | * @param ns Length of source string in code points | |
52 | * @param ndp Where to store length of destination string (or NULL) | |
53 | * @return Newly allocated destination string or NULL on error | |
54 | * | |
56fd389c RK |
55 | * If the UTF-32 is not valid then NULL is returned. A UTF-32 code point is |
56 | * invalid if: | |
e5a5a138 RK |
57 | * - it codes for a UTF-16 surrogate |
58 | * - it codes for a value outside the unicode code space | |
59 | * | |
56fd389c RK |
60 | * The return value is always 0-terminated. The value returned via @p *ndp |
61 | * does not include the terminator. | |
e5a5a138 RK |
62 | */ |
63 | char *utf32_to_utf8(const uint32_t *s, size_t ns, size_t *ndp) { | |
64 | struct dynstr d; | |
65 | uint32_t c; | |
66 | ||
67 | dynstr_init(&d); | |
68 | while(ns > 0) { | |
69 | c = *s++; | |
70 | if(c < 0x80) | |
71 | dynstr_append(&d, c); | |
72 | else if(c < 0x0800) { | |
73 | dynstr_append(&d, 0xC0 | (c >> 6)); | |
74 | dynstr_append(&d, 0x80 | (c & 0x3F)); | |
75 | } else if(c < 0x10000) { | |
56fd389c | 76 | if(c >= 0xD800 && c <= 0xDFFF) |
e5a5a138 RK |
77 | goto error; |
78 | dynstr_append(&d, 0xE0 | (c >> 12)); | |
79 | dynstr_append(&d, 0x80 | ((c >> 6) & 0x3F)); | |
80 | dynstr_append(&d, 0x80 | (c & 0x3F)); | |
81 | } else if(c < 0x110000) { | |
82 | dynstr_append(&d, 0xF0 | (c >> 18)); | |
83 | dynstr_append(&d, 0x80 | ((c >> 12) & 0x3F)); | |
84 | dynstr_append(&d, 0x80 | ((c >> 6) & 0x3F)); | |
85 | dynstr_append(&d, 0x80 | (c & 0x3F)); | |
86 | } else | |
87 | goto error; | |
88 | --ns; | |
89 | } | |
90 | dynstr_terminate(&d); | |
91 | if(ndp) | |
92 | *ndp = d.nvec; | |
93 | return d.vec; | |
94 | error: | |
95 | xfree(d.vec); | |
96 | return 0; | |
97 | } | |
98 | ||
99 | /** @brief Convert UTF-8 to UTF-32 | |
100 | * @param s Source string | |
101 | * @param ns Length of source string in code points | |
102 | * @param ndp Where to store length of destination string (or NULL) | |
103 | * @return Newly allocated destination string or NULL | |
104 | * | |
56fd389c RK |
105 | * The return value is always 0-terminated. The value returned via @p *ndp |
106 | * does not include the terminator. | |
e5a5a138 RK |
107 | * |
108 | * If the UTF-8 is not valid then NULL is returned. A UTF-8 sequence | |
109 | * for a code point is invalid if: | |
110 | * - it is not the shortest possible sequence for the code point | |
111 | * - it codes for a UTF-16 surrogate | |
112 | * - it codes for a value outside the unicode code space | |
113 | */ | |
114 | uint32_t *utf8_to_utf32(const char *s, size_t ns, size_t *ndp) { | |
115 | struct dynstr_ucs4 d; | |
116 | uint32_t c32, c; | |
117 | const uint8_t *ss = (const uint8_t *)s; | |
118 | ||
119 | dynstr_ucs4_init(&d); | |
120 | while(ns > 0) { | |
121 | c = *ss++; | |
122 | --ns; | |
56fd389c RK |
123 | /* Acceptable UTF-8 is that which codes for Unicode Scalar Values |
124 | * (Unicode 5.0.0 s3.9 D76) | |
e5a5a138 RK |
125 | * |
126 | * 0xxxxxxx | |
127 | * 7 data bits gives 0x00 - 0x7F and all are acceptable | |
128 | * | |
129 | * 110xxxxx 10xxxxxx | |
130 | * 11 data bits gives 0x0000 - 0x07FF but only 0x0080 - 0x07FF acceptable | |
131 | * | |
132 | * 1110xxxx 10xxxxxx 10xxxxxx | |
133 | * 16 data bits gives 0x0000 - 0xFFFF but only 0x0800 - 0xFFFF acceptable | |
134 | * (and UTF-16 surrogates are not acceptable) | |
135 | * | |
136 | * 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx | |
137 | * 21 data bits gives 0x00000000 - 0x001FFFFF | |
138 | * but only 0x00010000 - 0x0010FFFF are acceptable | |
139 | * | |
56fd389c RK |
140 | * It is NOT always the case that the data bits in the first byte are |
141 | * always non-0 for the acceptable values, so we do a separate check after | |
142 | * decoding. | |
e5a5a138 RK |
143 | */ |
144 | if(c < 0x80) | |
145 | c32 = c; | |
146 | else if(c <= 0xDF) { | |
147 | if(ns < 1) goto error; | |
148 | c32 = c & 0x1F; | |
149 | c = *ss++; | |
150 | if((c & 0xC0) != 0x80) goto error; | |
151 | c32 = (c32 << 6) | (c & 0x3F); | |
152 | if(c32 < 0x80) goto error; | |
153 | } else if(c <= 0xEF) { | |
154 | if(ns < 2) goto error; | |
155 | c32 = c & 0x0F; | |
156 | c = *ss++; | |
157 | if((c & 0xC0) != 0x80) goto error; | |
158 | c32 = (c32 << 6) | (c & 0x3F); | |
159 | c = *ss++; | |
160 | if((c & 0xC0) != 0x80) goto error; | |
161 | c32 = (c32 << 6) | (c & 0x3F); | |
162 | if(c32 < 0x0800 || (c32 >= 0xD800 && c32 <= 0xDFFF)) goto error; | |
163 | } else if(c <= 0xF7) { | |
164 | if(ns < 3) goto error; | |
165 | c32 = c & 0x07; | |
166 | c = *ss++; | |
167 | if((c & 0xC0) != 0x80) goto error; | |
168 | c32 = (c32 << 6) | (c & 0x3F); | |
169 | c = *ss++; | |
170 | if((c & 0xC0) != 0x80) goto error; | |
171 | c32 = (c32 << 6) | (c & 0x3F); | |
172 | c = *ss++; | |
173 | if((c & 0xC0) != 0x80) goto error; | |
174 | c32 = (c32 << 6) | (c & 0x3F); | |
175 | if(c32 < 0x00010000 || c32 > 0x0010FFFF) goto error; | |
176 | } else | |
177 | goto error; | |
178 | dynstr_ucs4_append(&d, c32); | |
179 | } | |
180 | dynstr_ucs4_terminate(&d); | |
181 | if(ndp) | |
182 | *ndp = d.nvec; | |
183 | return d.vec; | |
184 | error: | |
185 | xfree(d.vec); | |
186 | return 0; | |
187 | } | |
188 | ||
189 | /*@}*/ | |
190 | /** @defgroup utf32 Functions that operate on UTF-32 strings */ | |
191 | /*@{*/ | |
192 | ||
193 | /** @brief Return the length of a 0-terminated UTF-32 string | |
194 | * @param s Pointer to 0-terminated string | |
195 | * @return Length of string in code points (excluding terminator) | |
196 | * | |
56fd389c | 197 | * Unlike the conversion functions no validity checking is done on the string. |
e5a5a138 RK |
198 | */ |
199 | size_t utf32_len(const uint32_t *s) { | |
200 | const uint32_t *t = s; | |
201 | ||
202 | while(*t) | |
203 | ++t; | |
204 | return (size_t)(t - s); | |
205 | } | |
206 | ||
bcf9ed7f RK |
207 | /** @brief Return the @ref unidata structure for code point @p c |
208 | * | |
209 | * @p c can be any 32-bit value, a sensible value will be returned regardless. | |
210 | */ | |
211 | static const struct unidata *utf32__unidata(uint32_t c) { | |
212 | if(c < UNICODE_NCHARS) | |
213 | return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS]; | |
214 | else if((c >= 0xF0000 && c <= 0xFFFFD) | |
215 | || (c >= 0x100000 && c <= 0x10FFFD)) | |
216 | return utf32__unidata(0xE000); /* Co */ | |
217 | else | |
218 | return utf32__unidata(0xFFFF); /* Cn */ | |
219 | } | |
220 | ||
e5a5a138 RK |
221 | /** @brief Return the combining class of @p c |
222 | * @param c Code point | |
223 | * @return Combining class of @p c | |
224 | */ | |
225 | static inline int utf32__combining_class(uint32_t c) { | |
bcf9ed7f | 226 | return utf32__unidata(c)->ccc; |
e5a5a138 RK |
227 | } |
228 | ||
229 | /** @brief Stably sort [s,s+ns) into descending order of combining class | |
230 | * @param s Start of array | |
231 | * @param ns Number of elements, must be at least 1 | |
232 | * @param buffer Buffer of at least @p ns elements | |
233 | */ | |
234 | static void utf32__sort_ccc(uint32_t *s, size_t ns, uint32_t *buffer) { | |
235 | uint32_t *a, *b, *bp; | |
236 | size_t na, nb; | |
237 | ||
238 | switch(ns) { | |
239 | case 1: /* 1-element array is always sorted */ | |
240 | return; | |
241 | case 2: /* 2-element arrays are trivial to sort */ | |
242 | if(utf32__combining_class(s[0]) > utf32__combining_class(s[1])) { | |
243 | uint32_t tmp = s[0]; | |
244 | s[0] = s[1]; | |
245 | s[1] = tmp; | |
246 | } | |
247 | return; | |
248 | default: | |
249 | /* Partition the array */ | |
250 | na = ns / 2; | |
251 | nb = ns - na; | |
252 | a = s; | |
253 | b = s + na; | |
254 | /* Sort the two halves of the array */ | |
255 | utf32__sort_ccc(a, na, buffer); | |
256 | utf32__sort_ccc(b, nb, buffer); | |
257 | /* Merge them back into one, via the buffer */ | |
258 | bp = buffer; | |
259 | while(na > 0 && nb > 0) { | |
260 | /* We want descending order of combining class (hence <) | |
261 | * and we want stability within combining classes (hence <=) | |
262 | */ | |
263 | if(utf32__combining_class(*a) <= utf32__combining_class(*b)) { | |
264 | *bp++ = *a++; | |
265 | --na; | |
266 | } else { | |
267 | *bp++ = *b++; | |
268 | --nb; | |
269 | } | |
270 | } | |
271 | while(na > 0) { | |
272 | *bp++ = *a++; | |
273 | --na; | |
274 | } | |
275 | while(nb > 0) { | |
276 | *bp++ = *b++; | |
277 | --nb; | |
278 | } | |
279 | memcpy(s, buffer, ns * sizeof(uint32_t)); | |
280 | return; | |
281 | } | |
282 | } | |
283 | ||
284 | /** @brief Put combining characters into canonical order | |
285 | * @param s Pointer to UTF-32 string | |
286 | * @param ns Length of @p s | |
287 | * @return 0 on success, -1 on error | |
288 | * | |
56fd389c RK |
289 | * @p s is modified in-place. See Unicode 5.0 s3.11 for details of the |
290 | * ordering. | |
e5a5a138 | 291 | * |
56fd389c RK |
292 | * Currently we only support a maximum of 1024 combining characters after each |
293 | * base character. If this limit is exceeded then -1 is returned. | |
e5a5a138 RK |
294 | */ |
295 | static int utf32__canonical_ordering(uint32_t *s, size_t ns) { | |
296 | size_t nc; | |
297 | uint32_t buffer[1024]; | |
298 | ||
299 | /* The ordering amounts to a stable sort of each contiguous group of | |
300 | * characters with non-0 combining class. */ | |
301 | while(ns > 0) { | |
302 | /* Skip non-combining characters */ | |
303 | if(utf32__combining_class(*s) == 0) { | |
304 | ++s; | |
305 | --ns; | |
306 | continue; | |
307 | } | |
308 | /* We must now have at least one combining character; see how many | |
309 | * there are */ | |
310 | for(nc = 1; nc < ns && utf32__combining_class(s[nc]) != 0; ++nc) | |
311 | ; | |
312 | if(nc > 1024) | |
313 | return -1; | |
314 | /* Sort the array */ | |
315 | utf32__sort_ccc(s, nc, buffer); | |
316 | s += nc; | |
317 | ns -= nc; | |
318 | } | |
319 | return 0; | |
320 | } | |
321 | ||
322 | /* Magic numbers from UAX #15 s16 */ | |
323 | #define SBase 0xAC00 | |
324 | #define LBase 0x1100 | |
325 | #define VBase 0x1161 | |
326 | #define TBase 0x11A7 | |
327 | #define LCount 19 | |
328 | #define VCount 21 | |
329 | #define TCount 28 | |
330 | #define NCount (VCount * TCount) | |
331 | #define SCount (LCount * NCount) | |
332 | ||
333 | /** @brief Guts of the decomposition lookup functions */ | |
334 | #define utf32__decompose_one_generic(WHICH) do { \ | |
bcf9ed7f | 335 | const uint32_t *dc = utf32__unidata(c)->WHICH; \ |
e5a5a138 RK |
336 | if(dc) { \ |
337 | /* Found a canonical decomposition in the table */ \ | |
338 | while(*dc) \ | |
339 | utf32__decompose_one_##WHICH(d, *dc++); \ | |
340 | } else if(c >= SBase && c < SBase + SCount) { \ | |
341 | /* Mechanically decomposable Hangul syllable (UAX #15 s16) */ \ | |
342 | const uint32_t SIndex = c - SBase; \ | |
343 | const uint32_t L = LBase + SIndex / NCount; \ | |
344 | const uint32_t V = VBase + (SIndex % NCount) / TCount; \ | |
345 | const uint32_t T = TBase + SIndex % TCount; \ | |
346 | dynstr_ucs4_append(d, L); \ | |
347 | dynstr_ucs4_append(d, V); \ | |
348 | if(T != TBase) \ | |
349 | dynstr_ucs4_append(d, T); \ | |
350 | } else \ | |
351 | /* Equal to own canonical decomposition */ \ | |
352 | dynstr_ucs4_append(d, c); \ | |
353 | } while(0) | |
354 | ||
355 | /** @brief Recursively compute the canonical decomposition of @p c | |
356 | * @param d Dynamic string to store decomposition in | |
357 | * @param c Code point to decompose (must be a valid!) | |
358 | * @return 0 on success, -1 on error | |
359 | */ | |
360 | static void utf32__decompose_one_canon(struct dynstr_ucs4 *d, uint32_t c) { | |
361 | utf32__decompose_one_generic(canon); | |
362 | } | |
363 | ||
364 | /** @brief Recursively compute the compatibility decomposition of @p c | |
365 | * @param d Dynamic string to store decomposition in | |
366 | * @param c Code point to decompose (must be a valid!) | |
367 | * @return 0 on success, -1 on error | |
368 | */ | |
369 | static void utf32__decompose_one_compat(struct dynstr_ucs4 *d, uint32_t c) { | |
370 | utf32__decompose_one_generic(compat); | |
371 | } | |
372 | ||
373 | /** @brief Guts of the decomposition functions */ | |
374 | #define utf32__decompose_generic(WHICH) do { \ | |
375 | struct dynstr_ucs4 d; \ | |
376 | uint32_t c; \ | |
377 | \ | |
378 | dynstr_ucs4_init(&d); \ | |
379 | while(ns) { \ | |
380 | c = *s++; \ | |
56fd389c | 381 | if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \ |
e5a5a138 RK |
382 | goto error; \ |
383 | utf32__decompose_one_##WHICH(&d, c); \ | |
384 | --ns; \ | |
385 | } \ | |
386 | if(utf32__canonical_ordering(d.vec, d.nvec)) \ | |
387 | goto error; \ | |
388 | dynstr_ucs4_terminate(&d); \ | |
389 | if(ndp) \ | |
390 | *ndp = d.nvec; \ | |
391 | return d.vec; \ | |
392 | error: \ | |
393 | xfree(d.vec); \ | |
394 | return 0; \ | |
395 | } while(0) | |
396 | ||
397 | /** @brief Canonically decompose @p [s,s+ns) | |
398 | * @param s Pointer to string | |
399 | * @param ns Length of string | |
400 | * @param ndp Where to store length of result | |
401 | * @return Pointer to result string, or NULL | |
402 | * | |
403 | * Computes the canonical decomposition of a string and stably sorts combining | |
404 | * characters into canonical order. The result is in Normalization Form D and | |
405 | * (at the time of writing!) passes the NFD tests defined in Unicode 5.0's | |
406 | * NormalizationTest.txt. | |
407 | * | |
56fd389c | 408 | * Returns NULL if the string is not valid for either of the following reasons: |
e5a5a138 RK |
409 | * - it codes for a UTF-16 surrogate |
410 | * - it codes for a value outside the unicode code space | |
411 | */ | |
412 | uint32_t *utf32_decompose_canon(const uint32_t *s, size_t ns, size_t *ndp) { | |
413 | utf32__decompose_generic(canon); | |
414 | } | |
415 | ||
416 | /** @brief Compatibility decompose @p [s,s+ns) | |
417 | * @param s Pointer to string | |
418 | * @param ns Length of string | |
419 | * @param ndp Where to store length of result | |
420 | * @return Pointer to result string, or NULL | |
421 | * | |
422 | * Computes the compatibility decomposition of a string and stably sorts | |
423 | * combining characters into canonical order. The result is in Normalization | |
424 | * Form KD and (at the time of writing!) passes the NFKD tests defined in | |
425 | * Unicode 5.0's NormalizationTest.txt. | |
426 | * | |
56fd389c | 427 | * Returns NULL if the string is not valid for either of the following reasons: |
e5a5a138 RK |
428 | * - it codes for a UTF-16 surrogate |
429 | * - it codes for a value outside the unicode code space | |
430 | */ | |
431 | uint32_t *utf32_decompose_compat(const uint32_t *s, size_t ns, size_t *ndp) { | |
432 | utf32__decompose_generic(compat); | |
433 | } | |
434 | ||
56fd389c RK |
435 | /** @brief Single-character case-fold and decompose operation */ |
436 | #define utf32__casefold_one(WHICH) do { \ | |
bcf9ed7f | 437 | const uint32_t *cf = utf32__unidata(c)->casefold; \ |
56fd389c RK |
438 | if(cf) { \ |
439 | /* Found a case-fold mapping in the table */ \ | |
440 | while(*cf) \ | |
441 | utf32__decompose_one_##WHICH(&d, *cf++); \ | |
442 | } else \ | |
443 | utf32__decompose_one_##WHICH(&d, c); \ | |
444 | } while(0) | |
e5a5a138 RK |
445 | |
446 | /** @brief Case-fold @p [s,s+ns) | |
447 | * @param s Pointer to string | |
448 | * @param ns Length of string | |
449 | * @param ndp Where to store length of result | |
450 | * @return Pointer to result string, or NULL | |
451 | * | |
452 | * Case-fold the string at @p s according to full default case-folding rules | |
56fd389c | 453 | * (s3.13) for caseless matching. The result will be in NFD. |
e5a5a138 | 454 | * |
56fd389c | 455 | * Returns NULL if the string is not valid for either of the following reasons: |
e5a5a138 RK |
456 | * - it codes for a UTF-16 surrogate |
457 | * - it codes for a value outside the unicode code space | |
458 | */ | |
459 | uint32_t *utf32_casefold_canon(const uint32_t *s, size_t ns, size_t *ndp) { | |
460 | struct dynstr_ucs4 d; | |
461 | uint32_t c; | |
462 | size_t n; | |
463 | uint32_t *ss = 0; | |
464 | ||
465 | /* If the canonical decomposition of the string includes any combining | |
466 | * character that case-folds to a non-combining character then we must | |
467 | * normalize before we fold. In Unicode 5.0.0 this means 0345 COMBINING | |
468 | * GREEK YPOGEGRAMMENI in its decomposition and the various characters that | |
469 | * canonically decompose to it. */ | |
bcf9ed7f RK |
470 | for(n = 0; n < ns; ++n) |
471 | if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold) | |
e5a5a138 | 472 | break; |
e5a5a138 RK |
473 | if(n < ns) { |
474 | /* We need a preliminary decomposition */ | |
475 | if(!(ss = utf32_decompose_canon(s, ns, &ns))) | |
476 | return 0; | |
477 | s = ss; | |
478 | } | |
479 | dynstr_ucs4_init(&d); | |
480 | while(ns) { | |
481 | c = *s++; | |
56fd389c | 482 | if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) |
e5a5a138 | 483 | goto error; |
56fd389c | 484 | utf32__casefold_one(canon); |
e5a5a138 RK |
485 | --ns; |
486 | } | |
487 | if(utf32__canonical_ordering(d.vec, d.nvec)) | |
488 | goto error; | |
489 | dynstr_ucs4_terminate(&d); | |
490 | if(ndp) | |
491 | *ndp = d.nvec; | |
492 | return d.vec; | |
493 | error: | |
494 | xfree(d.vec); | |
495 | xfree(ss); | |
496 | return 0; | |
497 | } | |
498 | ||
56fd389c RK |
499 | /** @brief Compatibilit case-fold @p [s,s+ns) |
500 | * @param s Pointer to string | |
501 | * @param ns Length of string | |
502 | * @param ndp Where to store length of result | |
503 | * @return Pointer to result string, or NULL | |
504 | * | |
505 | * Case-fold the string at @p s according to full default case-folding rules | |
506 | * (s3.13) for compatibility caseless matching. The result will be in NFKD. | |
507 | * | |
508 | * Returns NULL if the string is not valid for either of the following reasons: | |
509 | * - it codes for a UTF-16 surrogate | |
510 | * - it codes for a value outside the unicode code space | |
511 | */ | |
512 | uint32_t *utf32_casefold_compat(const uint32_t *s, size_t ns, size_t *ndp) { | |
513 | struct dynstr_ucs4 d; | |
514 | uint32_t c; | |
515 | size_t n; | |
516 | uint32_t *ss = 0; | |
517 | ||
bcf9ed7f RK |
518 | for(n = 0; n < ns; ++n) |
519 | if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold) | |
56fd389c | 520 | break; |
56fd389c RK |
521 | if(n < ns) { |
522 | /* We need a preliminary _canonical_ decomposition */ | |
523 | if(!(ss = utf32_decompose_canon(s, ns, &ns))) | |
524 | return 0; | |
525 | s = ss; | |
526 | } | |
527 | /* This computes NFKD(toCaseFold(s)) */ | |
528 | #define compat_casefold_middle() do { \ | |
529 | dynstr_ucs4_init(&d); \ | |
530 | while(ns) { \ | |
531 | c = *s++; \ | |
532 | if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \ | |
533 | goto error; \ | |
534 | utf32__casefold_one(compat); \ | |
535 | --ns; \ | |
536 | } \ | |
537 | if(utf32__canonical_ordering(d.vec, d.nvec)) \ | |
538 | goto error; \ | |
539 | } while(0) | |
540 | /* Do the inner (NFKD o toCaseFold) */ | |
541 | compat_casefold_middle(); | |
542 | /* We can do away with the NFD'd copy of the input now */ | |
543 | xfree(ss); | |
544 | s = ss = d.vec; | |
545 | ns = d.nvec; | |
546 | /* Do the outer (NFKD o toCaseFold) */ | |
547 | compat_casefold_middle(); | |
548 | /* That's all */ | |
549 | dynstr_ucs4_terminate(&d); | |
550 | if(ndp) | |
551 | *ndp = d.nvec; | |
552 | return d.vec; | |
553 | error: | |
554 | xfree(d.vec); | |
555 | xfree(ss); | |
556 | return 0; | |
557 | } | |
558 | ||
e5a5a138 RK |
559 | /** @brief Order a pair of UTF-32 strings |
560 | * @param a First 0-terminated string | |
561 | * @param b Second 0-terminated string | |
562 | * @return -1, 0 or 1 for a less than, equal to or greater than b | |
563 | * | |
564 | * "Comparable to strcmp() at its best." | |
565 | */ | |
566 | int utf32_cmp(const uint32_t *a, const uint32_t *b) { | |
567 | while(*a && *b && *a == *b) { | |
568 | ++a; | |
569 | ++b; | |
570 | } | |
571 | return *a < *b ? -1 : (*a > *b ? 1 : 0); | |
572 | } | |
573 | ||
35b651f0 RK |
574 | /** @brief Return the General_Category value for @p c |
575 | * @param Code point | |
576 | * @return General_Category property value | |
577 | */ | |
14523635 | 578 | static inline enum unicode_General_Category utf32__general_category(uint32_t c) { |
bcf9ed7f | 579 | return utf32__unidata(c)->general_category; |
35b651f0 RK |
580 | } |
581 | ||
582 | /** @brief Check Grapheme_Cluster_Break property | |
583 | * @param c Code point | |
584 | * @return 0 if it is as described, 1 otherwise | |
585 | */ | |
586 | static int utf32__is_control_or_cr_or_lf(uint32_t c) { | |
587 | switch(utf32__general_category(c)) { | |
588 | default: | |
589 | return 0; | |
14523635 RK |
590 | case unicode_General_Category_Zl: |
591 | case unicode_General_Category_Zp: | |
592 | case unicode_General_Category_Cc: | |
35b651f0 | 593 | return 1; |
14523635 | 594 | case unicode_General_Category_Cf: |
35b651f0 RK |
595 | if(c == 0x200C || c == 0x200D) |
596 | return 0; | |
597 | return 1; | |
598 | } | |
599 | } | |
600 | ||
601 | #define Hangul_Syllable_Type_NA 0 | |
602 | #define Hangul_Syllable_Type_L 0x1100 | |
603 | #define Hangul_Syllable_Type_V 0x1160 | |
604 | #define Hangul_Syllable_Type_T 0x11A8 | |
605 | #define Hangul_Syllable_Type_LV 0xAC00 | |
606 | #define Hangul_Syllable_Type_LVT 0xAC01 | |
607 | ||
608 | /** @brief Determine Hangul_Syllable_Type of @p c | |
609 | * @param c Code point | |
610 | * @return Equivalance class of @p c, or Hangul_Syllable_Type_NA | |
611 | * | |
612 | * If this is a Hangul character then a representative member of its | |
613 | * equivalence class is returned. Otherwise Hangul_Syllable_Type_NA is | |
614 | * returned. | |
615 | */ | |
616 | static uint32_t utf32__hangul_syllable_type(uint32_t c) { | |
617 | /* Dispose of the bulk of the non-Hangul code points first */ | |
618 | if(c < 0x1100) return Hangul_Syllable_Type_NA; | |
619 | if(c > 0x1200 && c < 0xAC00) return Hangul_Syllable_Type_NA; | |
620 | if(c >= 0xD800) return Hangul_Syllable_Type_NA; | |
621 | /* Now we pick out the assigned Hangul code points */ | |
622 | if((c >= 0x1100 && c <= 0x1159) || c == 0x115F) return Hangul_Syllable_Type_L; | |
623 | if(c >= 0x1160 && c <= 0x11A2) return Hangul_Syllable_Type_V; | |
624 | if(c >= 0x11A8 && c <= 0x11F9) return Hangul_Syllable_Type_T; | |
625 | if(c >= 0xAC00 && c <= 0xD7A3) { | |
626 | if(c % 28 == 16) | |
627 | return Hangul_Syllable_Type_LV; | |
628 | else | |
629 | return Hangul_Syllable_Type_LVT; | |
630 | } | |
631 | return Hangul_Syllable_Type_NA; | |
632 | } | |
633 | ||
0b7052da RK |
634 | /** @brief Determine Word_Break property |
635 | * @param c Code point | |
636 | * @return Word_Break property value of @p c | |
637 | */ | |
638 | static enum unicode_Word_Break utf32__word_break(uint32_t c) { | |
bcf9ed7f RK |
639 | if(c < 0xAC00 || c > 0xD7A3) |
640 | return utf32__unidata(c)->word_break; | |
641 | else | |
0b7052da RK |
642 | return unicode_Word_Break_ALetter; |
643 | } | |
644 | ||
35b651f0 RK |
645 | /** @brief Identify a grapheme cluster boundary |
646 | * @param s Start of string (must be NFD) | |
647 | * @param ns Length of string | |
648 | * @param n Index within string (in [0,ns].) | |
649 | * @return 1 at a grapheme cluster boundary, 0 otherwise | |
650 | * | |
651 | * This function identifies default grapheme cluster boundaries as described in | |
652 | * UAX #29 s3. It returns 1 if @p n points at the code point just after a | |
653 | * grapheme cluster boundary (including the hypothetical code point just after | |
654 | * the end of the string). | |
35b651f0 RK |
655 | */ |
656 | int utf32_is_gcb(const uint32_t *s, size_t ns, size_t n) { | |
657 | uint32_t before, after; | |
658 | uint32_t hbefore, hafter; | |
659 | /* GB1 and GB2 */ | |
660 | if(n == 0 || n == ns) | |
661 | return 1; | |
662 | /* Now we know that s[n-1] and s[n] are safe to inspect */ | |
663 | /* GB3 */ | |
664 | before = s[n-1]; | |
665 | after = s[n]; | |
666 | if(before == 0x000D && after == 0x000A) | |
667 | return 0; | |
668 | /* GB4 and GB5 */ | |
669 | if(utf32__is_control_or_cr_or_lf(before) | |
670 | || utf32__is_control_or_cr_or_lf(after)) | |
671 | return 1; | |
672 | hbefore = utf32__hangul_syllable_type(before); | |
673 | hafter = utf32__hangul_syllable_type(after); | |
674 | /* GB6 */ | |
675 | if(hbefore == Hangul_Syllable_Type_L | |
e2452add RK |
676 | && (hafter == Hangul_Syllable_Type_L |
677 | || hafter == Hangul_Syllable_Type_V | |
678 | || hafter == Hangul_Syllable_Type_LV | |
679 | || hafter == Hangul_Syllable_Type_LVT)) | |
35b651f0 RK |
680 | return 0; |
681 | /* GB7 */ | |
682 | if((hbefore == Hangul_Syllable_Type_LV | |
683 | || hbefore == Hangul_Syllable_Type_V) | |
684 | && (hafter == Hangul_Syllable_Type_V | |
685 | || hafter == Hangul_Syllable_Type_T)) | |
686 | return 0; | |
687 | /* GB8 */ | |
688 | if((hbefore == Hangul_Syllable_Type_LVT | |
689 | || hbefore == Hangul_Syllable_Type_T) | |
690 | && hafter == Hangul_Syllable_Type_T) | |
691 | return 0; | |
692 | /* GB9 */ | |
0b7052da | 693 | if(utf32__word_break(after) == unicode_Word_Break_Extend) |
35b651f0 RK |
694 | return 0; |
695 | /* GB10 */ | |
696 | return 1; | |
697 | } | |
698 | ||
bb48024f RK |
699 | /** @brief Return true if @p c is ignorable for boundary specifications */ |
700 | static inline int utf32__boundary_ignorable(enum unicode_Word_Break wb) { | |
701 | return (wb == unicode_Word_Break_Extend | |
702 | || wb == unicode_Word_Break_Format); | |
0b7052da RK |
703 | } |
704 | ||
705 | /** @brief Identify a word boundary | |
706 | * @param s Start of string (must be NFD) | |
707 | * @param ns Length of string | |
708 | * @param n Index within string (in [0,ns].) | |
709 | * @return 1 at a word boundary, 0 otherwise | |
710 | * | |
711 | * This function identifies default word boundaries as described in UAX #29 s4. | |
712 | * It returns 1 if @p n points at the code point just after a word boundary | |
713 | * (including the hypothetical code point just after the end of the string). | |
714 | */ | |
715 | int utf32_is_word_boundary(const uint32_t *s, size_t ns, size_t n) { | |
716 | enum unicode_Word_Break twobefore, before, after, twoafter; | |
717 | size_t nn; | |
718 | ||
719 | /* WB1 and WB2 */ | |
720 | if(n == 0 || n == ns) | |
721 | return 1; | |
722 | /* WB3 */ | |
723 | if(s[n-1] == 0x000D && s[n] == 0x000A) | |
724 | return 0; | |
725 | /* WB4 */ | |
bb48024f RK |
726 | /* (!Sep) x (Extend|Format) as in UAX #29 s6.2 */ |
727 | switch(s[n-1]) { /* bit of a bodge */ | |
728 | case 0x000A: | |
729 | case 0x000D: | |
730 | case 0x0085: | |
731 | case 0x2028: | |
732 | case 0x2029: | |
733 | break; | |
734 | default: | |
735 | if(utf32__boundary_ignorable(utf32__word_break(s[n]))) | |
736 | return 0; | |
737 | break; | |
0b7052da | 738 | } |
bb48024f RK |
739 | /* Gather the property values we'll need for the rest of the test taking the |
740 | * s6.2 changes into account */ | |
741 | /* First we look at the code points after the proposed boundary */ | |
742 | nn = n; /* <ns */ | |
743 | after = utf32__word_break(s[nn++]); | |
744 | if(!utf32__boundary_ignorable(after)) { | |
745 | /* X (Extend|Format)* -> X */ | |
746 | while(nn < ns && utf32__boundary_ignorable(utf32__word_break(s[nn]))) | |
747 | ++nn; | |
748 | } | |
749 | /* It's possible now that nn=ns */ | |
750 | if(nn < ns) | |
751 | twoafter = utf32__word_break(s[nn]); | |
752 | else | |
753 | twoafter = unicode_Word_Break_Other; | |
754 | ||
755 | /* Next we look at the code points before the proposed boundary. This is a | |
756 | * bit fiddlier. */ | |
757 | nn = n; | |
758 | while(nn > 0 && utf32__boundary_ignorable(utf32__word_break(s[nn - 1]))) | |
759 | --nn; | |
760 | if(nn == 0) { | |
761 | /* s[nn] must be ignorable */ | |
762 | before = utf32__word_break(s[nn]); | |
763 | twobefore = unicode_Word_Break_Other; | |
764 | } else { | |
765 | /* s[nn] is ignorable or after the proposed boundary; but s[nn-1] is not | |
766 | * ignorable. */ | |
767 | before = utf32__word_break(s[nn - 1]); | |
768 | --nn; | |
769 | /* Repeat the exercise */ | |
770 | while(nn > 0 && utf32__boundary_ignorable(utf32__word_break(s[nn - 1]))) | |
771 | --nn; | |
772 | if(nn == 0) | |
773 | twobefore = utf32__word_break(s[nn]); | |
774 | else | |
775 | twobefore = utf32__word_break(s[nn - 1]); | |
0b7052da | 776 | } |
bb48024f | 777 | |
0b7052da RK |
778 | /* WB5 */ |
779 | if(before == unicode_Word_Break_ALetter | |
780 | && after == unicode_Word_Break_ALetter) | |
781 | return 0; | |
782 | /* WB6 */ | |
783 | if(before == unicode_Word_Break_ALetter | |
784 | && after == unicode_Word_Break_MidLetter | |
785 | && twoafter == unicode_Word_Break_ALetter) | |
786 | return 0; | |
787 | /* WB7 */ | |
788 | if(twobefore == unicode_Word_Break_ALetter | |
789 | && before == unicode_Word_Break_MidLetter | |
790 | && after == unicode_Word_Break_ALetter) | |
791 | return 0; | |
792 | /* WB8 */ | |
793 | if(before == unicode_Word_Break_Numeric | |
794 | && after == unicode_Word_Break_Numeric) | |
795 | return 0; | |
796 | /* WB9 */ | |
797 | if(before == unicode_Word_Break_ALetter | |
798 | && after == unicode_Word_Break_Numeric) | |
799 | return 0; | |
800 | /* WB10 */ | |
801 | if(before == unicode_Word_Break_Numeric | |
802 | && after == unicode_Word_Break_ALetter) | |
803 | return 0; | |
804 | /* WB11 */ | |
805 | if(twobefore == unicode_Word_Break_Numeric | |
806 | && before == unicode_Word_Break_MidNum | |
807 | && after == unicode_Word_Break_Numeric) | |
808 | return 0; | |
809 | /* WB12 */ | |
810 | if(before == unicode_Word_Break_Numeric | |
811 | && after == unicode_Word_Break_MidNum | |
812 | && twoafter == unicode_Word_Break_Numeric) | |
813 | return 0; | |
814 | /* WB13 */ | |
815 | if(before == unicode_Word_Break_Katakana | |
816 | && after == unicode_Word_Break_Katakana) | |
817 | return 0; | |
818 | /* WB13a */ | |
819 | if((before == unicode_Word_Break_ALetter | |
820 | || before == unicode_Word_Break_Numeric | |
821 | || before == unicode_Word_Break_Katakana | |
822 | || before == unicode_Word_Break_ExtendNumLet) | |
823 | && after == unicode_Word_Break_ExtendNumLet) | |
824 | return 0; | |
825 | /* WB13b */ | |
826 | if(before == unicode_Word_Break_ExtendNumLet | |
827 | && (after == unicode_Word_Break_ALetter | |
828 | || after == unicode_Word_Break_Numeric | |
829 | || after == unicode_Word_Break_Katakana)) | |
830 | return 0; | |
831 | /* WB14 */ | |
832 | return 1; | |
833 | } | |
834 | ||
e5a5a138 | 835 | /*@}*/ |
349b7b74 | 836 | /** @defgroup utf8 Functions that operate on UTF-8 strings */ |
e5a5a138 RK |
837 | /*@{*/ |
838 | ||
839 | /** @brief Wrapper to transform a UTF-8 string using the UTF-32 function */ | |
840 | #define utf8__transform(FN) do { \ | |
841 | uint32_t *to32 = 0, *decomp32 = 0; \ | |
842 | size_t nto32, ndecomp32; \ | |
843 | char *decomp8 = 0; \ | |
844 | \ | |
845 | if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error; \ | |
846 | if(!(decomp32 = FN(to32, nto32, &ndecomp32))) goto error; \ | |
847 | decomp8 = utf32_to_utf8(decomp32, ndecomp32, ndp); \ | |
848 | error: \ | |
849 | xfree(to32); \ | |
850 | xfree(decomp32); \ | |
851 | return decomp8; \ | |
852 | } while(0) | |
853 | ||
854 | /** @brief Canonically decompose @p [s,s+ns) | |
855 | * @param s Pointer to string | |
856 | * @param ns Length of string | |
857 | * @param ndp Where to store length of result | |
858 | * @return Pointer to result string, or NULL | |
859 | * | |
860 | * Computes the canonical decomposition of a string and stably sorts combining | |
861 | * characters into canonical order. The result is in Normalization Form D and | |
862 | * (at the time of writing!) passes the NFD tests defined in Unicode 5.0's | |
863 | * NormalizationTest.txt. | |
864 | * | |
865 | * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why | |
866 | * this might be. | |
867 | * | |
868 | * See also utf32_decompose_canon(). | |
869 | */ | |
870 | char *utf8_decompose_canon(const char *s, size_t ns, size_t *ndp) { | |
871 | utf8__transform(utf32_decompose_canon); | |
872 | } | |
873 | ||
874 | /** @brief Compatibility decompose @p [s,s+ns) | |
875 | * @param s Pointer to string | |
876 | * @param ns Length of string | |
877 | * @param ndp Where to store length of result | |
878 | * @return Pointer to result string, or NULL | |
879 | * | |
880 | * Computes the compatibility decomposition of a string and stably sorts | |
881 | * combining characters into canonical order. The result is in Normalization | |
882 | * Form KD and (at the time of writing!) passes the NFKD tests defined in | |
883 | * Unicode 5.0's NormalizationTest.txt. | |
884 | * | |
885 | * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why | |
886 | * this might be. | |
887 | * | |
888 | * See also utf32_decompose_compat(). | |
889 | */ | |
890 | char *utf8_decompose_compat(const char *s, size_t ns, size_t *ndp) { | |
891 | utf8__transform(utf32_decompose_compat); | |
892 | } | |
893 | ||
894 | /** @brief Case-fold @p [s,s+ns) | |
895 | * @param s Pointer to string | |
896 | * @param ns Length of string | |
897 | * @param ndp Where to store length of result | |
898 | * @return Pointer to result string, or NULL | |
899 | * | |
900 | * Case-fold the string at @p s according to full default case-folding rules | |
901 | * (s3.13). The result will be in NFD. | |
902 | * | |
903 | * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why | |
904 | * this might be. | |
905 | */ | |
906 | char *utf8_casefold_canon(const char *s, size_t ns, size_t *ndp) { | |
907 | utf8__transform(utf32_casefold_canon); | |
908 | } | |
909 | ||
910 | /** @brief Compatibility case-fold @p [s,s+ns) | |
911 | * @param s Pointer to string | |
912 | * @param ns Length of string | |
913 | * @param ndp Where to store length of result | |
914 | * @return Pointer to result string, or NULL | |
915 | * | |
916 | * Case-fold the string at @p s according to full default case-folding rules | |
917 | * (s3.13). The result will be in NFKD. | |
918 | * | |
919 | * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why | |
920 | * this might be. | |
921 | */ | |
e5a5a138 RK |
922 | char *utf8_casefold_compat(const char *s, size_t ns, size_t *ndp) { |
923 | utf8__transform(utf32_casefold_compat); | |
924 | } | |
e5a5a138 RK |
925 | |
926 | /*@}*/ | |
927 | ||
928 | /* | |
929 | Local Variables: | |
930 | c-basic-offset:2 | |
931 | comment-column:40 | |
932 | fill-column:79 | |
933 | indent-tabs-mode:nil | |
934 | End: | |
935 | */ |