2 * This file is part of DisOrder
3 * Copyright (C) 2007 Richard Kettlewell
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.
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.
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
20 /** @file lib/unicode.c
21 * @brief Unicode support functions
23 * Here by UTF-8 and UTF-8 we mean the encoding forms of those names (not the
24 * encoding schemes). The primary encoding form is UTF-32 but convenience
25 * wrappers using UTF-8 are provided for a number of functions.
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
32 * As the code stands this guarantee is not well met!
37 * - @ref utf32iterator
46 #include <stdio.h> /* TODO */
53 /** @defgroup utf32props Unicode Code Point Properties */
56 static const struct unidata *utf32__unidata_hard(uint32_t c);
58 /** @brief Find definition of code point @p c
60 * @return Pointer to @ref unidata structure for @p c
62 * @p c can be any 32-bit value, a sensible value will be returned regardless.
63 * The returned pointer is NOT guaranteed to be unique to @p c.
65 static inline const struct unidata *utf32__unidata(uint32_t c) {
66 /* The bottom half of the table contains almost everything of interest
67 * and we can just return the right thing straight away */
68 if(c < UNICODE_BREAK_START)
69 return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
71 return utf32__unidata_hard(c);
74 /** @brief Find definition of code point @p c
76 * @return Pointer to @ref unidata structure for @p c
78 * @p c can be any 32-bit value, a sensible value will be returned regardless.
79 * The returned pointer is NOT guaranteed to be unique to @p c.
81 * Don't use this function (although it will work fine) - use utf32__unidata()
84 static const struct unidata *utf32__unidata_hard(uint32_t c) {
85 if(c < UNICODE_BREAK_START)
86 return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
87 /* Within the break everything is unassigned */
88 if(c < UNICODE_BREAK_END)
89 return utf32__unidata(0xFFFF); /* guaranteed to be Cn */
90 /* Planes 15 and 16 are (mostly) private use */
91 if((c >= 0xF0000 && c <= 0xFFFFD)
92 || (c >= 0x100000 && c <= 0x10FFFD))
93 return utf32__unidata(0xE000); /* first Co code point */
94 /* Everything else above the break top is unassigned */
95 if(c >= UNICODE_BREAK_TOP)
96 return utf32__unidata(0xFFFF); /* guaranteed to be Cn */
97 /* Currently the rest is language tags and variation selectors */
98 c -= (UNICODE_BREAK_END - UNICODE_BREAK_START);
99 return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
102 /** @brief Return the combining class of @p c
103 * @param c Code point
104 * @return Combining class of @p c
106 * @p c can be any 32-bit value, a sensible value will be returned regardless.
108 static inline int utf32__combining_class(uint32_t c) {
109 return utf32__unidata(c)->ccc;
112 /** @brief Return the General_Category value for @p c
113 * @param c Code point
114 * @return General_Category property value
116 * @p c can be any 32-bit value, a sensible value will be returned regardless.
118 static inline enum unicode_General_Category utf32__general_category(uint32_t c) {
119 return utf32__unidata(c)->general_category;
122 /** @brief Determine Grapheme_Break property
123 * @param c Code point
124 * @return Grapheme_Break property value of @p c
126 * @p c can be any 32-bit value, a sensible value will be returned regardless.
128 static inline enum unicode_Grapheme_Break utf32__grapheme_break(uint32_t c) {
129 return utf32__unidata(c)->grapheme_break;
132 /** @brief Determine Word_Break property
133 * @param c Code point
134 * @return Word_Break property value of @p c
136 * @p c can be any 32-bit value, a sensible value will be returned regardless.
138 static inline enum unicode_Word_Break utf32__word_break(uint32_t c) {
139 return utf32__unidata(c)->word_break;
142 /** @brief Determine Sentence_Break property
143 * @param c Code point
144 * @return Word_Break property value of @p c
146 * @p c can be any 32-bit value, a sensible value will be returned regardless.
148 static inline enum unicode_Sentence_Break utf32__sentence_break(uint32_t c) {
149 return utf32__unidata(c)->sentence_break;
152 /** @brief Return true if @p c is ignorable for boundary specifications
153 * @param wb Word break property value
154 * @return non-0 if @p wb is unicode_Word_Break_Extend or unicode_Word_Break_Format
156 static inline int utf32__boundary_ignorable(enum unicode_Word_Break wb) {
157 return (wb == unicode_Word_Break_Extend
158 || wb == unicode_Word_Break_Format);
161 /** @brief Return the canonical decomposition of @p c
162 * @param c Code point
163 * @return 0-terminated canonical decomposition, or 0
165 static inline const uint32_t *utf32__decomposition_canon(uint32_t c) {
166 const struct unidata *const data = utf32__unidata(c);
167 const uint32_t *const decomp = data->decomp;
169 if(decomp && !(data->flags & unicode_compatibility_decomposition))
175 /** @brief Return the compatibility decomposition of @p c
176 * @param c Code point
177 * @return 0-terminated decomposition, or 0
179 static inline const uint32_t *utf32__decomposition_compat(uint32_t c) {
180 return utf32__unidata(c)->decomp;
184 /** @defgroup utftransform Functions that transform between different Unicode encoding forms */
187 /** @brief Convert UTF-32 to UTF-8
188 * @param s Source string
189 * @param ns Length of source string in code points
190 * @param ndp Where to store length of destination string (or NULL)
191 * @return Newly allocated destination string or NULL on error
193 * If the UTF-32 is not valid then NULL is returned. A UTF-32 code point is
195 * - it codes for a UTF-16 surrogate
196 * - it codes for a value outside the unicode code space
198 * The return value is always 0-terminated. The value returned via @p *ndp
199 * does not include the terminator.
201 char *utf32_to_utf8(const uint32_t *s, size_t ns, size_t *ndp) {
209 dynstr_append(&d, c);
210 else if(c < 0x0800) {
211 dynstr_append(&d, 0xC0 | (c >> 6));
212 dynstr_append(&d, 0x80 | (c & 0x3F));
213 } else if(c < 0x10000) {
214 if(c >= 0xD800 && c <= 0xDFFF)
216 dynstr_append(&d, 0xE0 | (c >> 12));
217 dynstr_append(&d, 0x80 | ((c >> 6) & 0x3F));
218 dynstr_append(&d, 0x80 | (c & 0x3F));
219 } else if(c < 0x110000) {
220 dynstr_append(&d, 0xF0 | (c >> 18));
221 dynstr_append(&d, 0x80 | ((c >> 12) & 0x3F));
222 dynstr_append(&d, 0x80 | ((c >> 6) & 0x3F));
223 dynstr_append(&d, 0x80 | (c & 0x3F));
228 dynstr_terminate(&d);
237 /** @brief Convert UTF-8 to UTF-32
238 * @param s Source string
239 * @param ns Length of source string in code points
240 * @param ndp Where to store length of destination string (or NULL)
241 * @return Newly allocated destination string or NULL on error
243 * The return value is always 0-terminated. The value returned via @p *ndp
244 * does not include the terminator.
246 * If the UTF-8 is not valid then NULL is returned. A UTF-8 sequence
247 * for a code point is invalid if:
248 * - it is not the shortest possible sequence for the code point
249 * - it codes for a UTF-16 surrogate
250 * - it codes for a value outside the unicode code space
252 uint32_t *utf8_to_utf32(const char *s, size_t ns, size_t *ndp) {
253 struct dynstr_ucs4 d;
255 const uint8_t *ss = (const uint8_t *)s;
258 dynstr_ucs4_init(&d);
260 const struct unicode_utf8_row *const r = &unicode_utf8_valid[*ss];
267 if(ss[1] < r->min2 || ss[1] > r->max2)
272 if(ss[1] < r->min2 || ss[1] > r->max2)
277 if(ss[1] < r->min2 || ss[1] > r->max2)
286 for(n = 1; n < r->count; ++n) {
287 if(ss[n] < 0x80 || ss[n] > 0xBF)
289 c32 = (c32 << 6) | (ss[n] & 0x3F);
291 dynstr_ucs4_append(&d, c32);
295 dynstr_ucs4_terminate(&d);
304 /** @brief Test whether [s,s+ns) is valid UTF-8
305 * @param s Start of string
306 * @param ns Length of string
307 * @return non-0 if @p s is valid UTF-8, 0 if it is not valid
309 * This function is intended to be much faster than calling utf8_to_utf32() and
310 * throwing away the result.
312 int utf8_valid(const char *s, size_t ns) {
313 const uint8_t *ss = (const uint8_t *)s;
315 const struct unicode_utf8_row *const r = &unicode_utf8_valid[*ss];
321 if(ss[1] < r->min2 || ss[1] > r->max2)
325 if(ss[1] < r->min2 || ss[1] > r->max2)
327 if(ss[2] < 0x80 || ss[2] > 0xBF)
331 if(ss[1] < r->min2 || ss[1] > r->max2)
333 if(ss[2] < 0x80 || ss[2] > 0xBF)
335 if(ss[3] < 0x80 || ss[3] > 0xBF)
350 /** @defgroup utf32iterator UTF-32 string iterators */
353 struct utf32_iterator_data {
354 /** @brief Start of string */
357 /** @brief Length of string */
360 /** @brief Current position */
363 /** @brief Last two non-ignorable characters or (uint32_t)-1
365 * last[1] is the non-Extend/Format character just before position @p n;
366 * last[0] is the one just before that.
368 * Exception 1: if there is no such non-Extend/Format character then an
369 * Extend/Format character is accepted instead.
371 * Exception 2: if there is no such character even taking that into account
372 * the value is (uint32_t)-1.
377 /** @brief Create a new iterator pointing at the start of a string
378 * @param s Start of string
379 * @param ns Length of string
380 * @return New iterator
382 utf32_iterator utf32_iterator_new(const uint32_t *s, size_t ns) {
383 utf32_iterator it = xmalloc(sizeof *it);
387 it->last[0] = it->last[1] = -1;
391 /** @brief Initialize an internal private iterator
393 * @param s Start of string
394 * @param ns Length of string
395 * @param n Absolute position
397 static void utf32__iterator_init(utf32_iterator it,
398 const uint32_t *s, size_t ns, size_t n) {
402 it->last[0] = it->last[1] = -1;
403 utf32_iterator_set(it, n);
406 /** @brief Destroy an iterator
409 void utf32_iterator_destroy(utf32_iterator it) {
413 /** @brief Find the current position of an interator
416 size_t utf32_iterator_where(utf32_iterator it) {
420 /** @brief Set an iterator's absolute position
422 * @param n Absolute position
423 * @return 0 on success, non-0 on error
425 * It is an error to position the iterator outside the string (but acceptable
426 * to point it at the hypothetical post-final character). If an invalid value
427 * of @p n is specified then the iterator is not changed.
429 * This function works by backing up and then advancing to reconstruct the
430 * iterator's internal state for position @p n. The worst case will be O(n)
431 * time complexity (with a worse constant factor that utf32_iterator_advance())
432 * but the typical case is essentially constant-time.
434 int utf32_iterator_set(utf32_iterator it, size_t n) {
435 /* We can't just jump to position @p n; the @p last[] values will be wrong.
436 * What we need is to jump a bit behind @p n and then advance forward,
437 * updating @p last[] along the way. How far back? We need to cross two
438 * non-ignorable code points as we advance forwards, so we'd better pass two
439 * such characters on the way back (if such are available).
443 if(n > it->ns) /* range check */
445 /* Walk backwards skipping ignorable code points */
447 while(m > 0 && (utf32__boundary_ignorable(utf32__word_break(it->s[m-1]))))
449 /* Either m=0 or s[m-1] is not ignorable */
452 /* s[m] is our first non-ignorable code; look for a second in the same
454 while(m > 0 && (utf32__boundary_ignorable(utf32__word_break(it->s[m-1]))))
456 /* Either m=0 or s[m-1] is not ignorable */
460 it->last[0] = it->last[1] = -1;
462 return utf32_iterator_advance(it, n - m);
465 /** @brief Advance an iterator
467 * @param count Number of code points to advance by
468 * @return 0 on success, non-0 on error
470 * It is an error to advance an iterator beyond the hypothetical post-final
471 * character of the string. If an invalid value of @p n is specified then the
472 * iterator is not changed.
474 * This function has O(n) time complexity: it works by advancing naively
475 * forwards through the string.
477 int utf32_iterator_advance(utf32_iterator it, size_t count) {
478 if(count <= it->ns - it->n) {
480 const uint32_t c = it->s[it->n];
481 const enum unicode_Word_Break wb = utf32__word_break(c);
482 if(it->last[1] == (uint32_t)-1
483 || !utf32__boundary_ignorable(wb)) {
484 it->last[0] = it->last[1];
495 /** @brief Find the current code point
497 * @return Current code point or 0
499 * If the iterator points at the hypothetical post-final character of the
500 * string then 0 is returned. NB that this doesn't mean that there aren't any
501 * 0 code points inside the string!
503 uint32_t utf32_iterator_code(utf32_iterator it) {
510 /** @brief Test for a grapheme boundary
512 * @return Non-0 if pointing just after a grapheme boundary, otherwise 0
514 * This function identifies default grapheme cluster boundaries as described in
515 * UAX #29 s3. It returns non-0 if @p it points at the code point just after a
516 * grapheme cluster boundary (including the hypothetical code point just after
517 * the end of the string).
519 int utf32_iterator_grapheme_boundary(utf32_iterator it) {
520 uint32_t before, after;
521 enum unicode_Grapheme_Break gbbefore, gbafter;
523 if(it->n == 0 || it->n == it->ns)
525 /* Now we know that s[n-1] and s[n] are safe to inspect */
527 before = it->s[it->n-1];
528 after = it->s[it->n];
529 if(before == 0x000D && after == 0x000A)
531 gbbefore = utf32__grapheme_break(before);
532 gbafter = utf32__grapheme_break(after);
534 if(gbbefore == unicode_Grapheme_Break_Control
539 if(gbafter == unicode_Grapheme_Break_Control
544 if(gbbefore == unicode_Grapheme_Break_L
545 && (gbafter == unicode_Grapheme_Break_L
546 || gbafter == unicode_Grapheme_Break_V
547 || gbafter == unicode_Grapheme_Break_LV
548 || gbafter == unicode_Grapheme_Break_LVT))
551 if((gbbefore == unicode_Grapheme_Break_LV
552 || gbbefore == unicode_Grapheme_Break_V)
553 && (gbafter == unicode_Grapheme_Break_V
554 || gbafter == unicode_Grapheme_Break_T))
557 if((gbbefore == unicode_Grapheme_Break_LVT
558 || gbbefore == unicode_Grapheme_Break_T)
559 && gbafter == unicode_Grapheme_Break_T)
562 if(gbafter == unicode_Grapheme_Break_Extend)
569 /** @brief Test for a word boundary
571 * @return Non-0 if pointing just after a word boundary, otherwise 0
573 * This function identifies default word boundaries as described in UAX #29 s4.
574 * It returns non-0 if @p it points at the code point just after a word
575 * boundary (including the hypothetical code point just after the end of the
576 * string) and 0 otherwise.
578 int utf32_iterator_word_boundary(utf32_iterator it) {
579 enum unicode_Word_Break twobefore, before, after, twoafter;
583 if(it->n == 0 || it->n == it->ns)
586 if(it->s[it->n-1] == 0x000D && it->s[it->n] == 0x000A)
589 /* (!Sep) x (Extend|Format) as in UAX #29 s6.2 */
590 if(utf32__sentence_break(it->s[it->n-1]) != unicode_Sentence_Break_Sep
591 && utf32__boundary_ignorable(utf32__word_break(it->s[it->n])))
593 /* Gather the property values we'll need for the rest of the test taking the
594 * s6.2 changes into account */
595 /* First we look at the code points after the proposed boundary */
596 nn = it->n; /* <it->ns */
597 after = utf32__word_break(it->s[nn++]);
598 if(!utf32__boundary_ignorable(after)) {
599 /* X (Extend|Format)* -> X */
601 && utf32__boundary_ignorable(utf32__word_break(it->s[nn])))
604 /* It's possible now that nn=ns */
606 twoafter = utf32__word_break(it->s[nn]);
608 twoafter = unicode_Word_Break_Other;
610 /* We've already recorded the non-ignorable code points before the proposed
612 before = utf32__word_break(it->last[1]);
613 twobefore = utf32__word_break(it->last[0]);
616 if(before == unicode_Word_Break_ALetter
617 && after == unicode_Word_Break_ALetter)
620 if(before == unicode_Word_Break_ALetter
621 && after == unicode_Word_Break_MidLetter
622 && twoafter == unicode_Word_Break_ALetter)
625 if(twobefore == unicode_Word_Break_ALetter
626 && before == unicode_Word_Break_MidLetter
627 && after == unicode_Word_Break_ALetter)
630 if(before == unicode_Word_Break_Numeric
631 && after == unicode_Word_Break_Numeric)
634 if(before == unicode_Word_Break_ALetter
635 && after == unicode_Word_Break_Numeric)
638 if(before == unicode_Word_Break_Numeric
639 && after == unicode_Word_Break_ALetter)
642 if(twobefore == unicode_Word_Break_Numeric
643 && before == unicode_Word_Break_MidNum
644 && after == unicode_Word_Break_Numeric)
647 if(before == unicode_Word_Break_Numeric
648 && after == unicode_Word_Break_MidNum
649 && twoafter == unicode_Word_Break_Numeric)
652 if(before == unicode_Word_Break_Katakana
653 && after == unicode_Word_Break_Katakana)
656 if((before == unicode_Word_Break_ALetter
657 || before == unicode_Word_Break_Numeric
658 || before == unicode_Word_Break_Katakana
659 || before == unicode_Word_Break_ExtendNumLet)
660 && after == unicode_Word_Break_ExtendNumLet)
663 if(before == unicode_Word_Break_ExtendNumLet
664 && (after == unicode_Word_Break_ALetter
665 || after == unicode_Word_Break_Numeric
666 || after == unicode_Word_Break_Katakana))
673 /** @defgroup utf32 Functions that operate on UTF-32 strings */
676 /** @brief Return the length of a 0-terminated UTF-32 string
677 * @param s Pointer to 0-terminated string
678 * @return Length of string in code points (excluding terminator)
680 * Unlike the conversion functions no validity checking is done on the string.
682 size_t utf32_len(const uint32_t *s) {
683 const uint32_t *t = s;
687 return (size_t)(t - s);
690 /** @brief Stably sort [s,s+ns) into descending order of combining class
691 * @param s Start of array
692 * @param ns Number of elements, must be at least 1
693 * @param buffer Buffer of at least @p ns elements
695 static void utf32__sort_ccc(uint32_t *s, size_t ns, uint32_t *buffer) {
696 uint32_t *a, *b, *bp;
700 case 1: /* 1-element array is always sorted */
702 case 2: /* 2-element arrays are trivial to sort */
703 if(utf32__combining_class(s[0]) > utf32__combining_class(s[1])) {
710 /* Partition the array */
715 /* Sort the two halves of the array */
716 utf32__sort_ccc(a, na, buffer);
717 utf32__sort_ccc(b, nb, buffer);
718 /* Merge them back into one, via the buffer */
720 while(na > 0 && nb > 0) {
721 /* We want ascending order of combining class (hence <)
722 * and we want stability within combining classes (hence <=)
724 if(utf32__combining_class(*a) <= utf32__combining_class(*b)) {
740 memcpy(s, buffer, ns * sizeof(uint32_t));
745 /** @brief Put combining characters into canonical order
746 * @param s Pointer to UTF-32 string
747 * @param ns Length of @p s
748 * @return 0 on success, non-0 on error
750 * @p s is modified in-place. See Unicode 5.0 s3.11 for details of the
753 * Currently we only support a maximum of 1024 combining characters after each
754 * base character. If this limit is exceeded then a non-0 value is returned.
756 static int utf32__canonical_ordering(uint32_t *s, size_t ns) {
758 uint32_t buffer[1024];
760 /* The ordering amounts to a stable sort of each contiguous group of
761 * characters with non-0 combining class. */
763 /* Skip non-combining characters */
764 if(utf32__combining_class(*s) == 0) {
769 /* We must now have at least one combining character; see how many
771 for(nc = 1; nc < ns && utf32__combining_class(s[nc]) != 0; ++nc)
776 utf32__sort_ccc(s, nc, buffer);
783 /* Magic numbers from UAX #15 s16 */
791 #define NCount (VCount * TCount)
792 #define SCount (LCount * NCount)
794 /** @brief Guts of the decomposition lookup functions */
795 #define utf32__decompose_one_generic(WHICH) do { \
796 const uint32_t *dc = utf32__decomposition_##WHICH(c); \
798 /* Found a canonical decomposition in the table */ \
800 utf32__decompose_one_##WHICH(d, *dc++); \
801 } else if(c >= SBase && c < SBase + SCount) { \
802 /* Mechanically decomposable Hangul syllable (UAX #15 s16) */ \
803 const uint32_t SIndex = c - SBase; \
804 const uint32_t L = LBase + SIndex / NCount; \
805 const uint32_t V = VBase + (SIndex % NCount) / TCount; \
806 const uint32_t T = TBase + SIndex % TCount; \
807 dynstr_ucs4_append(d, L); \
808 dynstr_ucs4_append(d, V); \
810 dynstr_ucs4_append(d, T); \
812 /* Equal to own canonical decomposition */ \
813 dynstr_ucs4_append(d, c); \
816 /** @brief Recursively compute the canonical decomposition of @p c
817 * @param d Dynamic string to store decomposition in
818 * @param c Code point to decompose (must be a valid!)
819 * @return 0 on success, non-0 on error
821 static void utf32__decompose_one_canon(struct dynstr_ucs4 *d, uint32_t c) {
822 utf32__decompose_one_generic(canon);
825 /** @brief Recursively compute the compatibility decomposition of @p c
826 * @param d Dynamic string to store decomposition in
827 * @param c Code point to decompose (must be a valid!)
828 * @return 0 on success, non-0 on error
830 static void utf32__decompose_one_compat(struct dynstr_ucs4 *d, uint32_t c) {
831 utf32__decompose_one_generic(compat);
834 /** @brief Magic utf32__compositions() return value for Hangul Choseong */
835 static const uint32_t utf32__hangul_L[1];
837 /** @brief Return the list of compositions that @p c starts
838 * @param c Starter code point
839 * @return Composition list or NULL
841 * For Hangul leading (Choseong) jamo we return the special value
842 * utf32__hangul_L. These code points are not listed as the targets of
843 * canonical decompositions (make-unidata checks) so there is no confusion with
844 * real decompositions here.
846 static const uint32_t *utf32__compositions(uint32_t c) {
847 const uint32_t *compositions = utf32__unidata(c)->composed;
851 /* Special-casing for Hangul */
852 switch(utf32__grapheme_break(c)) {
855 case unicode_Grapheme_Break_L:
856 return utf32__hangul_L;
860 /** @brief Composition step
861 * @param s Start of string
862 * @param ns Length of string
863 * @return New length of string
865 * This is called from utf32__decompose_generic() to compose the result string
868 static size_t utf32__compose(uint32_t *s, size_t ns) {
869 const uint32_t *compositions;
870 uint32_t *start = s, *t = s, *tt, cc;
873 uint32_t starter = *s++;
874 int block_starters = 0;
876 /* We don't attempt to compose the following things:
877 * - final characters whatever kind they are
878 * - non-starter characters
879 * - starters that don't take part in a canonical decomposition mapping
882 || utf32__combining_class(starter)
883 || !(compositions = utf32__compositions(starter))) {
887 if(compositions != utf32__hangul_L) {
888 /* Where we'll put the eventual starter */
891 /* See if we can find composition of starter+*s */
892 const uint32_t cchar = *s, *cp = compositions;
893 while((cc = *cp++)) {
894 const uint32_t *decomp = utf32__decomposition_canon(cc);
895 /* We know decomp[0] == starter */
896 if(decomp[1] == cchar)
900 /* Found a composition: cc decomposes to starter,*s */
902 compositions = utf32__compositions(starter);
906 /* No composition found. */
907 const int class = utf32__combining_class(*s);
909 /* Transfer the uncomposable combining character to the output */
912 /* All the combining characters of the same class of the
913 * uncomposable character are blocked by it, but there may be
914 * others of higher class later. We eat the uncomposable and
915 * blocked characters and go back round the loop for that higher
917 while(ns > 0 && utf32__combining_class(*s) == class) {
921 /* Block any subsequent starters */
924 /* The uncombinable character is itself a starter, so we don't
925 * transfer it to the output but instead go back round the main
930 /* Keep going while there are still characters and the starter takes
931 * part in some composition */
932 } while(ns > 0 && compositions
933 && (!block_starters || utf32__combining_class(*s)));
934 /* Store any remaining combining characters */
935 while(ns > 0 && utf32__combining_class(*s)) {
939 /* Store the resulting starter */
942 /* Special-casing for Hangul
944 * If there are combining characters between the L and the V then they
945 * will block the V and so no composition happens. Similarly combining
946 * characters between V and T will block the T and so we only get as far
949 if(utf32__grapheme_break(*s) == unicode_Grapheme_Break_V) {
950 const uint32_t V = *s++;
951 const uint32_t LIndex = starter - LBase;
952 const uint32_t VIndex = V - VBase;
956 && utf32__grapheme_break(*s) == unicode_Grapheme_Break_T) {
957 /* We have an L V T sequence */
958 const uint32_t T = *s++;
964 /* Compose to LVT or LV as appropriate */
965 starter = (LIndex * VCount + VIndex) * TCount + TIndex + SBase;
966 } /* else we only have L or LV and no V or T */
968 /* There could be some combining characters that belong to the V or T.
969 * These will be treated as non-starter characters at the top of the loop
970 * and thuss transferred to the output. */
976 /** @brief Guts of the composition and decomposition functions
977 * @param WHICH @c canon or @c compat to choose decomposition
978 * @param COMPOSE @c 0 or @c 1 to compose
980 #define utf32__decompose_generic(WHICH, COMPOSE) do { \
981 struct dynstr_ucs4 d; \
984 dynstr_ucs4_init(&d); \
987 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \
989 utf32__decompose_one_##WHICH(&d, c); \
992 if(utf32__canonical_ordering(d.vec, d.nvec)) \
995 d.nvec = utf32__compose(d.vec, d.nvec); \
996 dynstr_ucs4_terminate(&d); \
1005 /** @brief Canonically decompose @p [s,s+ns)
1006 * @param s Pointer to string
1007 * @param ns Length of string
1008 * @param ndp Where to store length of result
1009 * @return Pointer to result string, or NULL on error
1011 * Computes NFD (Normalization Form D) of the string at @p s. This implies
1012 * performing all canonical decompositions and then normalizing the order of
1013 * combining characters.
1015 * Returns NULL if the string is not valid for either of the following reasons:
1016 * - it codes for a UTF-16 surrogate
1017 * - it codes for a value outside the unicode code space
1020 * - utf32_decompose_compat()
1021 * - utf32_compose_canon()
1023 uint32_t *utf32_decompose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1024 utf32__decompose_generic(canon, 0);
1027 /** @brief Compatibility decompose @p [s,s+ns)
1028 * @param s Pointer to string
1029 * @param ns Length of string
1030 * @param ndp Where to store length of result
1031 * @return Pointer to result string, or NULL on error
1033 * Computes NFKD (Normalization Form KD) of the string at @p s. This implies
1034 * performing all canonical and compatibility decompositions and then
1035 * normalizing the order of combining characters.
1037 * Returns NULL if the string is not valid for either of the following reasons:
1038 * - it codes for a UTF-16 surrogate
1039 * - it codes for a value outside the unicode code space
1042 * - utf32_decompose_canon()
1043 * - utf32_compose_compat()
1045 uint32_t *utf32_decompose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1046 utf32__decompose_generic(compat, 0);
1049 /** @brief Canonically compose @p [s,s+ns)
1050 * @param s Pointer to string
1051 * @param ns Length of string
1052 * @param ndp Where to store length of result
1053 * @return Pointer to result string, or NULL on error
1055 * Computes NFC (Normalization Form C) of the string at @p s. This implies
1056 * performing all canonical decompositions, normalizing the order of combining
1057 * characters and then composing all unblocked primary compositables.
1059 * Returns NULL if the string is not valid for either of the following reasons:
1060 * - it codes for a UTF-16 surrogate
1061 * - it codes for a value outside the unicode code space
1064 * - utf32_compose_compat()
1065 * - utf32_decompose_canon()
1067 uint32_t *utf32_compose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1068 utf32__decompose_generic(canon, 1);
1071 /** @brief Compatibility compose @p [s,s+ns)
1072 * @param s Pointer to string
1073 * @param ns Length of string
1074 * @param ndp Where to store length of result
1075 * @return Pointer to result string, or NULL on error
1077 * Computes NFKC (Normalization Form KC) of the string at @p s. This implies
1078 * performing all canonical and compatibility decompositions, normalizing the
1079 * order of combining characters and then composing all unblocked primary
1082 * Returns NULL if the string is not valid for either of the following reasons:
1083 * - it codes for a UTF-16 surrogate
1084 * - it codes for a value outside the unicode code space
1087 * - utf32_compose_canon()
1088 * - utf32_decompose_compat()
1090 uint32_t *utf32_compose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1091 utf32__decompose_generic(compat, 1);
1094 /** @brief Single-character case-fold and decompose operation */
1095 #define utf32__casefold_one(WHICH) do { \
1096 const uint32_t *cf = utf32__unidata(c)->casefold; \
1098 /* Found a case-fold mapping in the table */ \
1100 utf32__decompose_one_##WHICH(&d, *cf++); \
1102 utf32__decompose_one_##WHICH(&d, c); \
1105 /** @brief Case-fold @p [s,s+ns)
1106 * @param s Pointer to string
1107 * @param ns Length of string
1108 * @param ndp Where to store length of result
1109 * @return Pointer to result string, or NULL on error
1111 * Case-fold the string at @p s according to full default case-folding rules
1112 * (s3.13) for caseless matching. The result will be in NFD.
1114 * Returns NULL if the string is not valid for either of the following reasons:
1115 * - it codes for a UTF-16 surrogate
1116 * - it codes for a value outside the unicode code space
1118 uint32_t *utf32_casefold_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1119 struct dynstr_ucs4 d;
1124 /* If the canonical decomposition of the string includes any combining
1125 * character that case-folds to a non-combining character then we must
1126 * normalize before we fold. In Unicode 5.0.0 this means 0345 COMBINING
1127 * GREEK YPOGEGRAMMENI in its decomposition and the various characters that
1128 * canonically decompose to it. */
1129 for(n = 0; n < ns; ++n)
1130 if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
1133 /* We need a preliminary decomposition */
1134 if(!(ss = utf32_decompose_canon(s, ns, &ns)))
1138 dynstr_ucs4_init(&d);
1141 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)
1143 utf32__casefold_one(canon);
1146 if(utf32__canonical_ordering(d.vec, d.nvec))
1148 dynstr_ucs4_terminate(&d);
1158 /** @brief Compatibility case-fold @p [s,s+ns)
1159 * @param s Pointer to string
1160 * @param ns Length of string
1161 * @param ndp Where to store length of result
1162 * @return Pointer to result string, or NULL on error
1164 * Case-fold the string at @p s according to full default case-folding rules
1165 * (s3.13) for compatibility caseless matching. The result will be in NFKD.
1167 * Returns NULL if the string is not valid for either of the following reasons:
1168 * - it codes for a UTF-16 surrogate
1169 * - it codes for a value outside the unicode code space
1171 uint32_t *utf32_casefold_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1172 struct dynstr_ucs4 d;
1177 for(n = 0; n < ns; ++n)
1178 if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
1181 /* We need a preliminary _canonical_ decomposition */
1182 if(!(ss = utf32_decompose_canon(s, ns, &ns)))
1186 /* This computes NFKD(toCaseFold(s)) */
1187 #define compat_casefold_middle() do { \
1188 dynstr_ucs4_init(&d); \
1191 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \
1193 utf32__casefold_one(compat); \
1196 if(utf32__canonical_ordering(d.vec, d.nvec)) \
1199 /* Do the inner (NFKD o toCaseFold) */
1200 compat_casefold_middle();
1201 /* We can do away with the NFD'd copy of the input now */
1205 /* Do the outer (NFKD o toCaseFold) */
1206 compat_casefold_middle();
1208 dynstr_ucs4_terminate(&d);
1218 /** @brief Order a pair of UTF-32 strings
1219 * @param a First 0-terminated string
1220 * @param b Second 0-terminated string
1221 * @return -1, 0 or 1 for a less than, equal to or greater than b
1223 * "Comparable to strcmp() at its best."
1225 int utf32_cmp(const uint32_t *a, const uint32_t *b) {
1226 while(*a && *b && *a == *b) {
1230 return *a < *b ? -1 : (*a > *b ? 1 : 0);
1233 /** @brief Identify a grapheme cluster boundary
1234 * @param s Start of string (must be NFD)
1235 * @param ns Length of string
1236 * @param n Index within string (in [0,ns].)
1237 * @return 1 at a grapheme cluster boundary, 0 otherwise
1239 * This function identifies default grapheme cluster boundaries as described in
1240 * UAX #29 s3. It returns non-0 if @p n points at the code point just after a
1241 * grapheme cluster boundary (including the hypothetical code point just after
1242 * the end of the string).
1244 * This function uses utf32_iterator_set() internally; see that function for
1245 * remarks on performance.
1247 int utf32_is_grapheme_boundary(const uint32_t *s, size_t ns, size_t n) {
1248 struct utf32_iterator_data it[1];
1250 utf32__iterator_init(it, s, ns, n);
1251 return utf32_iterator_grapheme_boundary(it);
1254 /** @brief Identify a word boundary
1255 * @param s Start of string (must be NFD)
1256 * @param ns Length of string
1257 * @param n Index within string (in [0,ns].)
1258 * @return 1 at a word boundary, 0 otherwise
1260 * This function identifies default word boundaries as described in UAX #29 s4.
1261 * It returns non-0 if @p n points at the code point just after a word boundary
1262 * (including the hypothetical code point just after the end of the string).
1264 * This function uses utf32_iterator_set() internally; see that function for
1265 * remarks on performance.
1267 int utf32_is_word_boundary(const uint32_t *s, size_t ns, size_t n) {
1268 struct utf32_iterator_data it[1];
1270 utf32__iterator_init(it, s, ns, n);
1271 return utf32_iterator_word_boundary(it);
1275 /** @defgroup utf8 Functions that operate on UTF-8 strings */
1278 /** @brief Wrapper to transform a UTF-8 string using the UTF-32 function */
1279 #define utf8__transform(FN) do { \
1280 uint32_t *to32 = 0, *decomp32 = 0; \
1281 size_t nto32, ndecomp32; \
1282 char *decomp8 = 0; \
1284 if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error; \
1285 if(!(decomp32 = FN(to32, nto32, &ndecomp32))) goto error; \
1286 decomp8 = utf32_to_utf8(decomp32, ndecomp32, ndp); \
1293 /** @brief Canonically decompose @p [s,s+ns)
1294 * @param s Pointer to string
1295 * @param ns Length of string
1296 * @param ndp Where to store length of result
1297 * @return Pointer to result string, or NULL on error
1299 * Computes NFD (Normalization Form D) of the string at @p s. This implies
1300 * performing all canonical decompositions and then normalizing the order of
1301 * combining characters.
1303 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1307 * - utf32_decompose_canon().
1308 * - utf8_decompose_compat()
1309 * - utf8_compose_canon()
1311 char *utf8_decompose_canon(const char *s, size_t ns, size_t *ndp) {
1312 utf8__transform(utf32_decompose_canon);
1315 /** @brief Compatibility decompose @p [s,s+ns)
1316 * @param s Pointer to string
1317 * @param ns Length of string
1318 * @param ndp Where to store length of result
1319 * @return Pointer to result string, or NULL on error
1321 * Computes NFKD (Normalization Form KD) of the string at @p s. This implies
1322 * performing all canonical and compatibility decompositions and then
1323 * normalizing the order of combining characters.
1325 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1329 * - utf32_decompose_compat().
1330 * - utf8_decompose_canon()
1331 * - utf8_compose_compat()
1333 char *utf8_decompose_compat(const char *s, size_t ns, size_t *ndp) {
1334 utf8__transform(utf32_decompose_compat);
1337 /** @brief Canonically compose @p [s,s+ns)
1338 * @param s Pointer to string
1339 * @param ns Length of string
1340 * @param ndp Where to store length of result
1341 * @return Pointer to result string, or NULL on error
1343 * Computes NFC (Normalization Form C) of the string at @p s. This implies
1344 * performing all canonical decompositions, normalizing the order of combining
1345 * characters and then composing all unblocked primary compositables.
1347 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1351 * - utf32_compose_canon()
1352 * - utf8_compose_compat()
1353 * - utf8_decompose_canon()
1355 char *utf8_compose_canon(const char *s, size_t ns, size_t *ndp) {
1356 utf8__transform(utf32_compose_canon);
1359 /** @brief Compatibility compose @p [s,s+ns)
1360 * @param s Pointer to string
1361 * @param ns Length of string
1362 * @param ndp Where to store length of result
1363 * @return Pointer to result string, or NULL on error
1365 * Computes NFKC (Normalization Form KC) of the string at @p s. This implies
1366 * performing all canonical and compatibility decompositions, normalizing the
1367 * order of combining characters and then composing all unblocked primary
1370 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1374 * - utf32_compose_compat()
1375 * - utf8_compose_canon()
1376 * - utf8_decompose_compat()
1378 char *utf8_compose_compat(const char *s, size_t ns, size_t *ndp) {
1379 utf8__transform(utf32_compose_compat);
1382 /** @brief Case-fold @p [s,s+ns)
1383 * @param s Pointer to string
1384 * @param ns Length of string
1385 * @param ndp Where to store length of result
1386 * @return Pointer to result string, or NULL on error
1388 * Case-fold the string at @p s according to full default case-folding rules
1389 * (s3.13). The result will be in NFD.
1391 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1394 char *utf8_casefold_canon(const char *s, size_t ns, size_t *ndp) {
1395 utf8__transform(utf32_casefold_canon);
1398 /** @brief Compatibility case-fold @p [s,s+ns)
1399 * @param s Pointer to string
1400 * @param ns Length of string
1401 * @param ndp Where to store length of result
1402 * @return Pointer to result string, or NULL on error
1404 * Case-fold the string at @p s according to full default case-folding rules
1405 * (s3.13). The result will be in NFKD.
1407 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1410 char *utf8_casefold_compat(const char *s, size_t ns, size_t *ndp) {
1411 utf8__transform(utf32_casefold_compat);
1421 indent-tabs-mode:nil