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.
376 /** @brief Tailoring for Word_Break */
377 unicode_property_tailor *word_break;
380 /** @brief Initialize an internal private iterator
382 * @param s Start of string
383 * @param ns Length of string
384 * @param n Absolute position
386 static void utf32__iterator_init(utf32_iterator it,
387 const uint32_t *s, size_t ns, size_t n) {
391 it->last[0] = it->last[1] = -1;
393 utf32_iterator_set(it, n);
396 /** @brief Create a new iterator pointing at the start of a string
397 * @param s Start of string
398 * @param ns Length of string
399 * @return New iterator
401 utf32_iterator utf32_iterator_new(const uint32_t *s, size_t ns) {
402 utf32_iterator it = xmalloc(sizeof *it);
403 utf32__iterator_init(it, s, ns, 0);
407 /** @brief Tailor this iterator's interpretation of the Word_Break property.
409 * @param pt Property tailor function or NULL
411 * After calling this the iterator will call @p pt to determine the Word_Break
412 * property of each code point. If it returns -1 the default value will be
413 * used otherwise the returned value will be used.
415 * @p pt can be NULL to revert to the default value of the property.
417 * It is safe to call this function at any time; the iterator's internal state
418 * will be reset to suit the new tailoring.
420 void utf32_iterator_tailor_word_break(utf32_iterator it,
421 unicode_property_tailor *pt) {
423 utf32_iterator_set(it, it->n);
426 static inline enum unicode_Word_Break utf32__iterator_word_break(utf32_iterator it,
429 return utf32__word_break(c);
431 const int t = it->word_break(c);
434 return utf32__word_break(c);
440 /** @brief Destroy an iterator
443 void utf32_iterator_destroy(utf32_iterator it) {
447 /** @brief Find the current position of an interator
450 size_t utf32_iterator_where(utf32_iterator it) {
454 /** @brief Set an iterator's absolute position
456 * @param n Absolute position
457 * @return 0 on success, non-0 on error
459 * It is an error to position the iterator outside the string (but acceptable
460 * to point it at the hypothetical post-final character). If an invalid value
461 * of @p n is specified then the iterator is not changed.
463 * This function works by backing up and then advancing to reconstruct the
464 * iterator's internal state for position @p n. The worst case will be O(n)
465 * time complexity (with a worse constant factor that utf32_iterator_advance())
466 * but the typical case is essentially constant-time.
468 int utf32_iterator_set(utf32_iterator it, size_t n) {
469 /* We can't just jump to position @p n; the @p last[] values will be wrong.
470 * What we need is to jump a bit behind @p n and then advance forward,
471 * updating @p last[] along the way. How far back? We need to cross two
472 * non-ignorable code points as we advance forwards, so we'd better pass two
473 * such characters on the way back (if such are available).
477 if(n > it->ns) /* range check */
479 /* Walk backwards skipping ignorable code points */
482 && (utf32__boundary_ignorable(utf32__iterator_word_break(it,
485 /* Either m=0 or s[m-1] is not ignorable */
488 /* s[m] is our first non-ignorable code; look for a second in the same
491 && (utf32__boundary_ignorable(utf32__iterator_word_break(it,
494 /* Either m=0 or s[m-1] is not ignorable */
498 it->last[0] = it->last[1] = -1;
500 return utf32_iterator_advance(it, n - m);
503 /** @brief Advance an iterator
505 * @param count Number of code points to advance by
506 * @return 0 on success, non-0 on error
508 * It is an error to advance an iterator beyond the hypothetical post-final
509 * character of the string. If an invalid value of @p n is specified then the
510 * iterator is not changed.
512 * This function has O(n) time complexity: it works by advancing naively
513 * forwards through the string.
515 int utf32_iterator_advance(utf32_iterator it, size_t count) {
516 if(count <= it->ns - it->n) {
518 const uint32_t c = it->s[it->n];
519 const enum unicode_Word_Break wb = utf32__iterator_word_break(it, c);
520 if(it->last[1] == (uint32_t)-1
521 || !utf32__boundary_ignorable(wb)) {
522 it->last[0] = it->last[1];
533 /** @brief Find the current code point
535 * @return Current code point or 0
537 * If the iterator points at the hypothetical post-final character of the
538 * string then 0 is returned. NB that this doesn't mean that there aren't any
539 * 0 code points inside the string!
541 uint32_t utf32_iterator_code(utf32_iterator it) {
548 /** @brief Test for a grapheme boundary
550 * @return Non-0 if pointing just after a grapheme boundary, otherwise 0
552 * This function identifies default grapheme cluster boundaries as described in
553 * UAX #29 s3. It returns non-0 if @p it points at the code point just after a
554 * grapheme cluster boundary (including the hypothetical code point just after
555 * the end of the string).
557 int utf32_iterator_grapheme_boundary(utf32_iterator it) {
558 uint32_t before, after;
559 enum unicode_Grapheme_Break gbbefore, gbafter;
561 if(it->n == 0 || it->n == it->ns)
563 /* Now we know that s[n-1] and s[n] are safe to inspect */
565 before = it->s[it->n-1];
566 after = it->s[it->n];
567 if(before == 0x000D && after == 0x000A)
569 gbbefore = utf32__grapheme_break(before);
570 gbafter = utf32__grapheme_break(after);
572 if(gbbefore == unicode_Grapheme_Break_Control
577 if(gbafter == unicode_Grapheme_Break_Control
582 if(gbbefore == unicode_Grapheme_Break_L
583 && (gbafter == unicode_Grapheme_Break_L
584 || gbafter == unicode_Grapheme_Break_V
585 || gbafter == unicode_Grapheme_Break_LV
586 || gbafter == unicode_Grapheme_Break_LVT))
589 if((gbbefore == unicode_Grapheme_Break_LV
590 || gbbefore == unicode_Grapheme_Break_V)
591 && (gbafter == unicode_Grapheme_Break_V
592 || gbafter == unicode_Grapheme_Break_T))
595 if((gbbefore == unicode_Grapheme_Break_LVT
596 || gbbefore == unicode_Grapheme_Break_T)
597 && gbafter == unicode_Grapheme_Break_T)
600 if(gbafter == unicode_Grapheme_Break_Extend)
607 /** @brief Test for a word boundary
609 * @return Non-0 if pointing just after a word boundary, otherwise 0
611 * This function identifies default word boundaries as described in UAX #29 s4.
612 * It returns non-0 if @p it points at the code point just after a word
613 * boundary (including the hypothetical code point just after the end of the
614 * string) and 0 otherwise.
616 int utf32_iterator_word_boundary(utf32_iterator it) {
617 enum unicode_Word_Break twobefore, before, after, twoafter;
621 if(it->n == 0 || it->n == it->ns)
624 if(it->s[it->n-1] == 0x000D && it->s[it->n] == 0x000A)
627 /* (!Sep) x (Extend|Format) as in UAX #29 s6.2 */
628 if(utf32__sentence_break(it->s[it->n-1]) != unicode_Sentence_Break_Sep
629 && utf32__boundary_ignorable(utf32__iterator_word_break(it, it->s[it->n])))
631 /* Gather the property values we'll need for the rest of the test taking the
632 * s6.2 changes into account */
633 /* First we look at the code points after the proposed boundary */
634 nn = it->n; /* <it->ns */
635 after = utf32__iterator_word_break(it, it->s[nn++]);
636 if(!utf32__boundary_ignorable(after)) {
637 /* X (Extend|Format)* -> X */
639 && utf32__boundary_ignorable(utf32__iterator_word_break(it,
643 /* It's possible now that nn=ns */
645 twoafter = utf32__iterator_word_break(it, it->s[nn]);
647 twoafter = unicode_Word_Break_Other;
649 /* We've already recorded the non-ignorable code points before the proposed
651 before = utf32__iterator_word_break(it, it->last[1]);
652 twobefore = utf32__iterator_word_break(it, it->last[0]);
655 if(before == unicode_Word_Break_ALetter
656 && after == unicode_Word_Break_ALetter)
659 if(before == unicode_Word_Break_ALetter
660 && after == unicode_Word_Break_MidLetter
661 && twoafter == unicode_Word_Break_ALetter)
664 if(twobefore == unicode_Word_Break_ALetter
665 && before == unicode_Word_Break_MidLetter
666 && after == unicode_Word_Break_ALetter)
669 if(before == unicode_Word_Break_Numeric
670 && after == unicode_Word_Break_Numeric)
673 if(before == unicode_Word_Break_ALetter
674 && after == unicode_Word_Break_Numeric)
677 if(before == unicode_Word_Break_Numeric
678 && after == unicode_Word_Break_ALetter)
681 if(twobefore == unicode_Word_Break_Numeric
682 && before == unicode_Word_Break_MidNum
683 && after == unicode_Word_Break_Numeric)
686 if(before == unicode_Word_Break_Numeric
687 && after == unicode_Word_Break_MidNum
688 && twoafter == unicode_Word_Break_Numeric)
691 if(before == unicode_Word_Break_Katakana
692 && after == unicode_Word_Break_Katakana)
695 if((before == unicode_Word_Break_ALetter
696 || before == unicode_Word_Break_Numeric
697 || before == unicode_Word_Break_Katakana
698 || before == unicode_Word_Break_ExtendNumLet)
699 && after == unicode_Word_Break_ExtendNumLet)
702 if(before == unicode_Word_Break_ExtendNumLet
703 && (after == unicode_Word_Break_ALetter
704 || after == unicode_Word_Break_Numeric
705 || after == unicode_Word_Break_Katakana))
712 /** @defgroup utf32 Functions that operate on UTF-32 strings */
715 /** @brief Return the length of a 0-terminated UTF-32 string
716 * @param s Pointer to 0-terminated string
717 * @return Length of string in code points (excluding terminator)
719 * Unlike the conversion functions no validity checking is done on the string.
721 size_t utf32_len(const uint32_t *s) {
722 const uint32_t *t = s;
726 return (size_t)(t - s);
729 /** @brief Stably sort [s,s+ns) into descending order of combining class
730 * @param s Start of array
731 * @param ns Number of elements, must be at least 1
732 * @param buffer Buffer of at least @p ns elements
734 static void utf32__sort_ccc(uint32_t *s, size_t ns, uint32_t *buffer) {
735 uint32_t *a, *b, *bp;
739 case 1: /* 1-element array is always sorted */
741 case 2: /* 2-element arrays are trivial to sort */
742 if(utf32__combining_class(s[0]) > utf32__combining_class(s[1])) {
749 /* Partition the array */
754 /* Sort the two halves of the array */
755 utf32__sort_ccc(a, na, buffer);
756 utf32__sort_ccc(b, nb, buffer);
757 /* Merge them back into one, via the buffer */
759 while(na > 0 && nb > 0) {
760 /* We want ascending order of combining class (hence <)
761 * and we want stability within combining classes (hence <=)
763 if(utf32__combining_class(*a) <= utf32__combining_class(*b)) {
779 memcpy(s, buffer, ns * sizeof(uint32_t));
784 /** @brief Put combining characters into canonical order
785 * @param s Pointer to UTF-32 string
786 * @param ns Length of @p s
787 * @return 0 on success, non-0 on error
789 * @p s is modified in-place. See Unicode 5.0 s3.11 for details of the
792 * Currently we only support a maximum of 1024 combining characters after each
793 * base character. If this limit is exceeded then a non-0 value is returned.
795 static int utf32__canonical_ordering(uint32_t *s, size_t ns) {
797 uint32_t buffer[1024];
799 /* The ordering amounts to a stable sort of each contiguous group of
800 * characters with non-0 combining class. */
802 /* Skip non-combining characters */
803 if(utf32__combining_class(*s) == 0) {
808 /* We must now have at least one combining character; see how many
810 for(nc = 1; nc < ns && utf32__combining_class(s[nc]) != 0; ++nc)
815 utf32__sort_ccc(s, nc, buffer);
822 /* Magic numbers from UAX #15 s16 */
830 #define NCount (VCount * TCount)
831 #define SCount (LCount * NCount)
833 /** @brief Guts of the decomposition lookup functions */
834 #define utf32__decompose_one_generic(WHICH) do { \
835 const uint32_t *dc = utf32__decomposition_##WHICH(c); \
837 /* Found a canonical decomposition in the table */ \
839 utf32__decompose_one_##WHICH(d, *dc++); \
840 } else if(c >= SBase && c < SBase + SCount) { \
841 /* Mechanically decomposable Hangul syllable (UAX #15 s16) */ \
842 const uint32_t SIndex = c - SBase; \
843 const uint32_t L = LBase + SIndex / NCount; \
844 const uint32_t V = VBase + (SIndex % NCount) / TCount; \
845 const uint32_t T = TBase + SIndex % TCount; \
846 dynstr_ucs4_append(d, L); \
847 dynstr_ucs4_append(d, V); \
849 dynstr_ucs4_append(d, T); \
851 /* Equal to own canonical decomposition */ \
852 dynstr_ucs4_append(d, c); \
855 /** @brief Recursively compute the canonical decomposition of @p c
856 * @param d Dynamic string to store decomposition in
857 * @param c Code point to decompose (must be a valid!)
858 * @return 0 on success, non-0 on error
860 static void utf32__decompose_one_canon(struct dynstr_ucs4 *d, uint32_t c) {
861 utf32__decompose_one_generic(canon);
864 /** @brief Recursively compute the compatibility decomposition of @p c
865 * @param d Dynamic string to store decomposition in
866 * @param c Code point to decompose (must be a valid!)
867 * @return 0 on success, non-0 on error
869 static void utf32__decompose_one_compat(struct dynstr_ucs4 *d, uint32_t c) {
870 utf32__decompose_one_generic(compat);
873 /** @brief Magic utf32__compositions() return value for Hangul Choseong */
874 static const uint32_t utf32__hangul_L[1];
876 /** @brief Return the list of compositions that @p c starts
877 * @param c Starter code point
878 * @return Composition list or NULL
880 * For Hangul leading (Choseong) jamo we return the special value
881 * utf32__hangul_L. These code points are not listed as the targets of
882 * canonical decompositions (make-unidata checks) so there is no confusion with
883 * real decompositions here.
885 static const uint32_t *utf32__compositions(uint32_t c) {
886 const uint32_t *compositions = utf32__unidata(c)->composed;
890 /* Special-casing for Hangul */
891 switch(utf32__grapheme_break(c)) {
894 case unicode_Grapheme_Break_L:
895 return utf32__hangul_L;
899 /** @brief Composition step
900 * @param s Start of string
901 * @param ns Length of string
902 * @return New length of string
904 * This is called from utf32__decompose_generic() to compose the result string
907 static size_t utf32__compose(uint32_t *s, size_t ns) {
908 const uint32_t *compositions;
909 uint32_t *start = s, *t = s, *tt, cc;
912 uint32_t starter = *s++;
913 int block_starters = 0;
915 /* We don't attempt to compose the following things:
916 * - final characters whatever kind they are
917 * - non-starter characters
918 * - starters that don't take part in a canonical decomposition mapping
921 || utf32__combining_class(starter)
922 || !(compositions = utf32__compositions(starter))) {
926 if(compositions != utf32__hangul_L) {
927 /* Where we'll put the eventual starter */
930 /* See if we can find composition of starter+*s */
931 const uint32_t cchar = *s, *cp = compositions;
932 while((cc = *cp++)) {
933 const uint32_t *decomp = utf32__decomposition_canon(cc);
934 /* We know decomp[0] == starter */
935 if(decomp[1] == cchar)
939 /* Found a composition: cc decomposes to starter,*s */
941 compositions = utf32__compositions(starter);
945 /* No composition found. */
946 const int class = utf32__combining_class(*s);
948 /* Transfer the uncomposable combining character to the output */
951 /* All the combining characters of the same class of the
952 * uncomposable character are blocked by it, but there may be
953 * others of higher class later. We eat the uncomposable and
954 * blocked characters and go back round the loop for that higher
956 while(ns > 0 && utf32__combining_class(*s) == class) {
960 /* Block any subsequent starters */
963 /* The uncombinable character is itself a starter, so we don't
964 * transfer it to the output but instead go back round the main
969 /* Keep going while there are still characters and the starter takes
970 * part in some composition */
971 } while(ns > 0 && compositions
972 && (!block_starters || utf32__combining_class(*s)));
973 /* Store any remaining combining characters */
974 while(ns > 0 && utf32__combining_class(*s)) {
978 /* Store the resulting starter */
981 /* Special-casing for Hangul
983 * If there are combining characters between the L and the V then they
984 * will block the V and so no composition happens. Similarly combining
985 * characters between V and T will block the T and so we only get as far
988 if(utf32__grapheme_break(*s) == unicode_Grapheme_Break_V) {
989 const uint32_t V = *s++;
990 const uint32_t LIndex = starter - LBase;
991 const uint32_t VIndex = V - VBase;
995 && utf32__grapheme_break(*s) == unicode_Grapheme_Break_T) {
996 /* We have an L V T sequence */
997 const uint32_t T = *s++;
1003 /* Compose to LVT or LV as appropriate */
1004 starter = (LIndex * VCount + VIndex) * TCount + TIndex + SBase;
1005 } /* else we only have L or LV and no V or T */
1007 /* There could be some combining characters that belong to the V or T.
1008 * These will be treated as non-starter characters at the top of the loop
1009 * and thuss transferred to the output. */
1015 /** @brief Guts of the composition and decomposition functions
1016 * @param WHICH @c canon or @c compat to choose decomposition
1017 * @param COMPOSE @c 0 or @c 1 to compose
1019 #define utf32__decompose_generic(WHICH, COMPOSE) do { \
1020 struct dynstr_ucs4 d; \
1023 dynstr_ucs4_init(&d); \
1026 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \
1028 utf32__decompose_one_##WHICH(&d, c); \
1031 if(utf32__canonical_ordering(d.vec, d.nvec)) \
1034 d.nvec = utf32__compose(d.vec, d.nvec); \
1035 dynstr_ucs4_terminate(&d); \
1044 /** @brief Canonically decompose @p [s,s+ns)
1045 * @param s Pointer to string
1046 * @param ns Length of string
1047 * @param ndp Where to store length of result
1048 * @return Pointer to result string, or NULL on error
1050 * Computes NFD (Normalization Form D) of the string at @p s. This implies
1051 * performing all canonical decompositions and then normalizing the order of
1052 * combining characters.
1054 * Returns NULL if the string is not valid for either of the following reasons:
1055 * - it codes for a UTF-16 surrogate
1056 * - it codes for a value outside the unicode code space
1059 * - utf32_decompose_compat()
1060 * - utf32_compose_canon()
1062 uint32_t *utf32_decompose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1063 utf32__decompose_generic(canon, 0);
1066 /** @brief Compatibility decompose @p [s,s+ns)
1067 * @param s Pointer to string
1068 * @param ns Length of string
1069 * @param ndp Where to store length of result
1070 * @return Pointer to result string, or NULL on error
1072 * Computes NFKD (Normalization Form KD) of the string at @p s. This implies
1073 * performing all canonical and compatibility decompositions and then
1074 * normalizing the order of combining characters.
1076 * Returns NULL if the string is not valid for either of the following reasons:
1077 * - it codes for a UTF-16 surrogate
1078 * - it codes for a value outside the unicode code space
1081 * - utf32_decompose_canon()
1082 * - utf32_compose_compat()
1084 uint32_t *utf32_decompose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1085 utf32__decompose_generic(compat, 0);
1088 /** @brief Canonically compose @p [s,s+ns)
1089 * @param s Pointer to string
1090 * @param ns Length of string
1091 * @param ndp Where to store length of result
1092 * @return Pointer to result string, or NULL on error
1094 * Computes NFC (Normalization Form C) of the string at @p s. This implies
1095 * performing all canonical decompositions, normalizing the order of combining
1096 * characters and then composing all unblocked primary compositables.
1098 * Returns NULL if the string is not valid for either of the following reasons:
1099 * - it codes for a UTF-16 surrogate
1100 * - it codes for a value outside the unicode code space
1103 * - utf32_compose_compat()
1104 * - utf32_decompose_canon()
1106 uint32_t *utf32_compose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1107 utf32__decompose_generic(canon, 1);
1110 /** @brief Compatibility compose @p [s,s+ns)
1111 * @param s Pointer to string
1112 * @param ns Length of string
1113 * @param ndp Where to store length of result
1114 * @return Pointer to result string, or NULL on error
1116 * Computes NFKC (Normalization Form KC) of the string at @p s. This implies
1117 * performing all canonical and compatibility decompositions, normalizing the
1118 * order of combining characters and then composing all unblocked primary
1121 * Returns NULL if the string is not valid for either of the following reasons:
1122 * - it codes for a UTF-16 surrogate
1123 * - it codes for a value outside the unicode code space
1126 * - utf32_compose_canon()
1127 * - utf32_decompose_compat()
1129 uint32_t *utf32_compose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1130 utf32__decompose_generic(compat, 1);
1133 /** @brief Single-character case-fold and decompose operation */
1134 #define utf32__casefold_one(WHICH) do { \
1135 const uint32_t *cf = utf32__unidata(c)->casefold; \
1137 /* Found a case-fold mapping in the table */ \
1139 utf32__decompose_one_##WHICH(&d, *cf++); \
1141 utf32__decompose_one_##WHICH(&d, c); \
1144 /** @brief Case-fold @p [s,s+ns)
1145 * @param s Pointer to string
1146 * @param ns Length of string
1147 * @param ndp Where to store length of result
1148 * @return Pointer to result string, or NULL on error
1150 * Case-fold the string at @p s according to full default case-folding rules
1151 * (s3.13) for caseless matching. The result will be in NFD.
1153 * Returns NULL if the string is not valid for either of the following reasons:
1154 * - it codes for a UTF-16 surrogate
1155 * - it codes for a value outside the unicode code space
1157 uint32_t *utf32_casefold_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1158 struct dynstr_ucs4 d;
1163 /* If the canonical decomposition of the string includes any combining
1164 * character that case-folds to a non-combining character then we must
1165 * normalize before we fold. In Unicode 5.0.0 this means 0345 COMBINING
1166 * GREEK YPOGEGRAMMENI in its decomposition and the various characters that
1167 * canonically decompose to it. */
1168 for(n = 0; n < ns; ++n)
1169 if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
1172 /* We need a preliminary decomposition */
1173 if(!(ss = utf32_decompose_canon(s, ns, &ns)))
1177 dynstr_ucs4_init(&d);
1180 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)
1182 utf32__casefold_one(canon);
1185 if(utf32__canonical_ordering(d.vec, d.nvec))
1187 dynstr_ucs4_terminate(&d);
1197 /** @brief Compatibility case-fold @p [s,s+ns)
1198 * @param s Pointer to string
1199 * @param ns Length of string
1200 * @param ndp Where to store length of result
1201 * @return Pointer to result string, or NULL on error
1203 * Case-fold the string at @p s according to full default case-folding rules
1204 * (s3.13) for compatibility caseless matching. The result will be in NFKD.
1206 * Returns NULL if the string is not valid for either of the following reasons:
1207 * - it codes for a UTF-16 surrogate
1208 * - it codes for a value outside the unicode code space
1210 uint32_t *utf32_casefold_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1211 struct dynstr_ucs4 d;
1216 for(n = 0; n < ns; ++n)
1217 if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
1220 /* We need a preliminary _canonical_ decomposition */
1221 if(!(ss = utf32_decompose_canon(s, ns, &ns)))
1225 /* This computes NFKD(toCaseFold(s)) */
1226 #define compat_casefold_middle() do { \
1227 dynstr_ucs4_init(&d); \
1230 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \
1232 utf32__casefold_one(compat); \
1235 if(utf32__canonical_ordering(d.vec, d.nvec)) \
1238 /* Do the inner (NFKD o toCaseFold) */
1239 compat_casefold_middle();
1240 /* We can do away with the NFD'd copy of the input now */
1244 /* Do the outer (NFKD o toCaseFold) */
1245 compat_casefold_middle();
1247 dynstr_ucs4_terminate(&d);
1257 /** @brief Order a pair of UTF-32 strings
1258 * @param a First 0-terminated string
1259 * @param b Second 0-terminated string
1260 * @return -1, 0 or 1 for a less than, equal to or greater than b
1262 * "Comparable to strcmp() at its best."
1264 int utf32_cmp(const uint32_t *a, const uint32_t *b) {
1265 while(*a && *b && *a == *b) {
1269 return *a < *b ? -1 : (*a > *b ? 1 : 0);
1272 /** @brief Identify a grapheme cluster boundary
1273 * @param s Start of string (must be NFD)
1274 * @param ns Length of string
1275 * @param n Index within string (in [0,ns].)
1276 * @return 1 at a grapheme cluster boundary, 0 otherwise
1278 * This function identifies default grapheme cluster boundaries as described in
1279 * UAX #29 s3. It returns non-0 if @p n points at the code point just after a
1280 * grapheme cluster boundary (including the hypothetical code point just after
1281 * the end of the string).
1283 * This function uses utf32_iterator_set() internally; see that function for
1284 * remarks on performance.
1286 int utf32_is_grapheme_boundary(const uint32_t *s, size_t ns, size_t n) {
1287 struct utf32_iterator_data it[1];
1289 utf32__iterator_init(it, s, ns, n);
1290 return utf32_iterator_grapheme_boundary(it);
1293 /** @brief Identify a word boundary
1294 * @param s Start of string (must be NFD)
1295 * @param ns Length of string
1296 * @param n Index within string (in [0,ns].)
1297 * @return 1 at a word boundary, 0 otherwise
1299 * This function identifies default word boundaries as described in UAX #29 s4.
1300 * It returns non-0 if @p n points at the code point just after a word boundary
1301 * (including the hypothetical code point just after the end of the string).
1303 * This function uses utf32_iterator_set() internally; see that function for
1304 * remarks on performance.
1306 int utf32_is_word_boundary(const uint32_t *s, size_t ns, size_t n) {
1307 struct utf32_iterator_data it[1];
1309 utf32__iterator_init(it, s, ns, n);
1310 return utf32_iterator_word_boundary(it);
1313 /** @brief Split [s,ns) into multiple words
1314 * @param s Pointer to start of string
1315 * @param ns Length of string
1316 * @param nwp Where to store word count, or NULL
1317 * @param wbreak Word_Break property tailor, or NULL
1318 * @return Pointer to array of pointers to words
1320 * The returned array is terminated by a NULL pointer and individual
1321 * strings are 0-terminated.
1323 uint32_t **utf32_word_split(const uint32_t *s, size_t ns, size_t *nwp,
1324 unicode_property_tailor *wbreak) {
1325 struct utf32_iterator_data it[1];
1326 size_t b1 = 0, b2 = 0 ,i;
1328 struct vector32 v32[1];
1332 utf32__iterator_init(it, s, ns, 0);
1333 it->word_break = wbreak;
1334 /* Work our way through the string stopping at each word break. */
1336 if(utf32_iterator_word_boundary(it)) {
1337 /* We've found a new boundary */
1340 /*fprintf(stderr, "[%zu, %zu) is a candidate word\n", b1, b2);*/
1341 /* Inspect the characters between the boundary and form an opinion as to
1342 * whether they are a word or not */
1344 for(i = b1; i < b2; ++i) {
1345 switch(utf32__iterator_word_break(it, it->s[i])) {
1346 case unicode_Word_Break_ALetter:
1347 case unicode_Word_Break_Numeric:
1348 case unicode_Word_Break_Katakana:
1355 /* If it's a word add it to the list of results */
1357 w = xcalloc(b2 - b1 + 1, sizeof(uint32_t));
1358 memcpy(w, it->s + b1, (b2 - b1) * sizeof (uint32_t));
1359 vector32_append(v32, w);
1362 } while(!utf32_iterator_advance(it, 1));
1363 vector32_terminate(v32);
1370 /** @defgroup utf8 Functions that operate on UTF-8 strings */
1373 /** @brief Wrapper to transform a UTF-8 string using the UTF-32 function */
1374 #define utf8__transform(FN) do { \
1375 uint32_t *to32 = 0, *decomp32 = 0; \
1376 size_t nto32, ndecomp32; \
1377 char *decomp8 = 0; \
1379 if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error; \
1380 if(!(decomp32 = FN(to32, nto32, &ndecomp32))) goto error; \
1381 decomp8 = utf32_to_utf8(decomp32, ndecomp32, ndp); \
1388 /** @brief Canonically decompose @p [s,s+ns)
1389 * @param s Pointer to string
1390 * @param ns Length of string
1391 * @param ndp Where to store length of result
1392 * @return Pointer to result string, or NULL on error
1394 * Computes NFD (Normalization Form D) of the string at @p s. This implies
1395 * performing all canonical decompositions and then normalizing the order of
1396 * combining characters.
1398 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1402 * - utf32_decompose_canon().
1403 * - utf8_decompose_compat()
1404 * - utf8_compose_canon()
1406 char *utf8_decompose_canon(const char *s, size_t ns, size_t *ndp) {
1407 utf8__transform(utf32_decompose_canon);
1410 /** @brief Compatibility decompose @p [s,s+ns)
1411 * @param s Pointer to string
1412 * @param ns Length of string
1413 * @param ndp Where to store length of result
1414 * @return Pointer to result string, or NULL on error
1416 * Computes NFKD (Normalization Form KD) of the string at @p s. This implies
1417 * performing all canonical and compatibility decompositions and then
1418 * normalizing the order of combining characters.
1420 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1424 * - utf32_decompose_compat().
1425 * - utf8_decompose_canon()
1426 * - utf8_compose_compat()
1428 char *utf8_decompose_compat(const char *s, size_t ns, size_t *ndp) {
1429 utf8__transform(utf32_decompose_compat);
1432 /** @brief Canonically compose @p [s,s+ns)
1433 * @param s Pointer to string
1434 * @param ns Length of string
1435 * @param ndp Where to store length of result
1436 * @return Pointer to result string, or NULL on error
1438 * Computes NFC (Normalization Form C) of the string at @p s. This implies
1439 * performing all canonical decompositions, normalizing the order of combining
1440 * characters and then composing all unblocked primary compositables.
1442 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1446 * - utf32_compose_canon()
1447 * - utf8_compose_compat()
1448 * - utf8_decompose_canon()
1450 char *utf8_compose_canon(const char *s, size_t ns, size_t *ndp) {
1451 utf8__transform(utf32_compose_canon);
1454 /** @brief Compatibility compose @p [s,s+ns)
1455 * @param s Pointer to string
1456 * @param ns Length of string
1457 * @param ndp Where to store length of result
1458 * @return Pointer to result string, or NULL on error
1460 * Computes NFKC (Normalization Form KC) of the string at @p s. This implies
1461 * performing all canonical and compatibility decompositions, normalizing the
1462 * order of combining characters and then composing all unblocked primary
1465 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1469 * - utf32_compose_compat()
1470 * - utf8_compose_canon()
1471 * - utf8_decompose_compat()
1473 char *utf8_compose_compat(const char *s, size_t ns, size_t *ndp) {
1474 utf8__transform(utf32_compose_compat);
1477 /** @brief Case-fold @p [s,s+ns)
1478 * @param s Pointer to string
1479 * @param ns Length of string
1480 * @param ndp Where to store length of result
1481 * @return Pointer to result string, or NULL on error
1483 * Case-fold the string at @p s according to full default case-folding rules
1484 * (s3.13). The result will be in NFD.
1486 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1489 char *utf8_casefold_canon(const char *s, size_t ns, size_t *ndp) {
1490 utf8__transform(utf32_casefold_canon);
1493 /** @brief Compatibility case-fold @p [s,s+ns)
1494 * @param s Pointer to string
1495 * @param ns Length of string
1496 * @param ndp Where to store length of result
1497 * @return Pointer to result string, or NULL on error
1499 * Case-fold the string at @p s according to full default case-folding rules
1500 * (s3.13). The result will be in NFKD.
1502 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1505 char *utf8_casefold_compat(const char *s, size_t ns, size_t *ndp) {
1506 utf8__transform(utf32_casefold_compat);
1509 /** @brief Split [s,ns) into multiple words
1510 * @param s Pointer to start of string
1511 * @param ns Length of string
1512 * @param nwp Where to store word count, or NULL
1513 * @param wbreak Word_Break property tailor, or NULL
1514 * @return Pointer to array of pointers to words
1516 * The returned array is terminated by a NULL pointer and individual
1517 * strings are 0-terminated.
1519 char **utf8_word_split(const char *s, size_t ns, size_t *nwp,
1520 unicode_property_tailor *wbreak) {
1521 uint32_t *to32 = 0, **v32 = 0;
1522 size_t nto32, nv, n;
1523 char **v8 = 0, **ret = 0;
1525 if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error;
1526 if(!(v32 = utf32_word_split(to32, nto32, &nv, wbreak))) goto error;
1527 v8 = xcalloc(sizeof (char *), nv + 1);
1528 for(n = 0; n < nv; ++n)
1529 if(!(v8[n] = utf32_to_utf8(v32[n], utf32_len(v32[n]), 0)))
1533 v8 = 0; /* don't free */
1536 for(n = 0; n < nv; ++n)
1541 for(n = 0; n < nv; ++n)
1557 indent-tabs-mode:nil