2 * This file is part of DisOrder
3 * Copyright (C) 2007, 2009 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 3 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU 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, see <http://www.gnu.org/licenses/>.
18 /** @file lib/unicode.c
19 * @brief Unicode support functions
21 * Here by UTF-8 and UTF-8 we mean the encoding forms of those names (not the
22 * encoding schemes). The primary encoding form is UTF-32 but convenience
23 * wrappers using UTF-8 are provided for a number of functions.
25 * The idea is that all the strings that hit the database will be in a
26 * particular normalization form, and for the search and tags database
27 * in case-folded form, so they can be naively compared within the
30 * As the code stands this guarantee is not well met!
35 * - @ref utf32iterator
47 /** @defgroup utf32props Unicode Code Point Properties */
50 static const struct unidata *utf32__unidata_hard(uint32_t c);
52 /** @brief Find definition of code point @p c
54 * @return Pointer to @ref unidata structure for @p c
56 * @p c can be any 32-bit value, a sensible value will be returned regardless.
57 * The returned pointer is NOT guaranteed to be unique to @p c.
59 static inline const struct unidata *utf32__unidata(uint32_t c) {
60 /* The bottom half of the table contains almost everything of interest
61 * and we can just return the right thing straight away */
62 if(c < UNICODE_BREAK_START)
63 return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
65 return utf32__unidata_hard(c);
68 /** @brief Find definition of code point @p c
70 * @return Pointer to @ref unidata structure for @p c
72 * @p c can be any 32-bit value, a sensible value will be returned regardless.
73 * The returned pointer is NOT guaranteed to be unique to @p c.
75 * Don't use this function (although it will work fine) - use utf32__unidata()
78 static const struct unidata *utf32__unidata_hard(uint32_t c) {
79 if(c < UNICODE_BREAK_START)
80 return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
81 /* Within the break everything is unassigned */
82 if(c < UNICODE_BREAK_END)
83 return utf32__unidata(0xFFFF); /* guaranteed to be Cn */
84 /* Planes 15 and 16 are (mostly) private use */
85 if((c >= 0xF0000 && c <= 0xFFFFD)
86 || (c >= 0x100000 && c <= 0x10FFFD))
87 return utf32__unidata(0xE000); /* first Co code point */
88 /* Everything else above the break top is unassigned */
89 if(c >= UNICODE_BREAK_TOP)
90 return utf32__unidata(0xFFFF); /* guaranteed to be Cn */
91 /* Currently the rest is language tags and variation selectors */
92 c -= (UNICODE_BREAK_END - UNICODE_BREAK_START);
93 return &unidata[c / UNICODE_MODULUS][c % UNICODE_MODULUS];
96 /** @brief Return the combining class of @p c
98 * @return Combining class of @p c
100 * @p c can be any 32-bit value, a sensible value will be returned regardless.
102 static inline int utf32__combining_class(uint32_t c) {
103 return utf32__unidata(c)->ccc;
106 /** @brief Return the combining class of @p c
107 * @param c Code point
108 * @return Combining class of @p c
110 * @p c can be any 32-bit value, a sensible value will be returned regardless.
112 int utf32_combining_class(uint32_t c) {
113 return utf32__combining_class(c);
116 /** @brief Return the General_Category value for @p c
117 * @param c Code point
118 * @return General_Category property value
120 * @p c can be any 32-bit value, a sensible value will be returned regardless.
122 static inline enum unicode_General_Category utf32__general_category(uint32_t c) {
123 return utf32__unidata(c)->general_category;
126 /** @brief Determine Grapheme_Break property
127 * @param c Code point
128 * @return Grapheme_Break property value of @p c
130 * @p c can be any 32-bit value, a sensible value will be returned regardless.
132 static inline enum unicode_Grapheme_Break utf32__grapheme_break(uint32_t c) {
133 return utf32__unidata(c)->grapheme_break;
136 /** @brief Determine Word_Break property
137 * @param c Code point
138 * @return Word_Break property value of @p c
140 * @p c can be any 32-bit value, a sensible value will be returned regardless.
142 static inline enum unicode_Word_Break utf32__word_break(uint32_t c) {
143 return utf32__unidata(c)->word_break;
146 /** @brief Determine Sentence_Break property
147 * @param c Code point
148 * @return Word_Break property value of @p c
150 * @p c can be any 32-bit value, a sensible value will be returned regardless.
152 static inline enum unicode_Sentence_Break utf32__sentence_break(uint32_t c) {
153 return utf32__unidata(c)->sentence_break;
156 /** @brief Return true if @p c is ignorable for boundary specifications
157 * @param wb Word break property value
158 * @return non-0 if @p wb is unicode_Word_Break_Extend or unicode_Word_Break_Format
160 static inline int utf32__boundary_ignorable(enum unicode_Word_Break wb) {
161 return (wb == unicode_Word_Break_Extend
162 || wb == unicode_Word_Break_Format);
165 /** @brief Return the canonical decomposition of @p c
166 * @param c Code point
167 * @return 0-terminated canonical decomposition, or 0
169 static inline const uint32_t *utf32__decomposition_canon(uint32_t c) {
170 const struct unidata *const data = utf32__unidata(c);
171 const uint32_t *const decomp = data->decomp;
173 if(decomp && !(data->flags & unicode_compatibility_decomposition))
179 /** @brief Return the compatibility decomposition of @p c
180 * @param c Code point
181 * @return 0-terminated decomposition, or 0
183 static inline const uint32_t *utf32__decomposition_compat(uint32_t c) {
184 return utf32__unidata(c)->decomp;
188 /** @defgroup utftransform Functions that transform between different Unicode encoding forms */
191 /** @brief Convert UTF-32 to UTF-8
192 * @param s Source string
193 * @param ns Length of source string in code points
194 * @param ndp Where to store length of destination string (or NULL)
195 * @return Newly allocated destination string or NULL on error
197 * If the UTF-32 is not valid then NULL is returned. A UTF-32 code point is
199 * - it codes for a UTF-16 surrogate
200 * - it codes for a value outside the unicode code space
202 * The return value is always 0-terminated. The value returned via @p *ndp
203 * does not include the terminator.
205 char *utf32_to_utf8(const uint32_t *s, size_t ns, size_t *ndp) {
213 dynstr_append(&d, c);
214 else if(c < 0x0800) {
215 dynstr_append(&d, 0xC0 | (c >> 6));
216 dynstr_append(&d, 0x80 | (c & 0x3F));
217 } else if(c < 0x10000) {
218 if(c >= 0xD800 && c <= 0xDFFF)
220 dynstr_append(&d, 0xE0 | (c >> 12));
221 dynstr_append(&d, 0x80 | ((c >> 6) & 0x3F));
222 dynstr_append(&d, 0x80 | (c & 0x3F));
223 } else if(c < 0x110000) {
224 dynstr_append(&d, 0xF0 | (c >> 18));
225 dynstr_append(&d, 0x80 | ((c >> 12) & 0x3F));
226 dynstr_append(&d, 0x80 | ((c >> 6) & 0x3F));
227 dynstr_append(&d, 0x80 | (c & 0x3F));
232 dynstr_terminate(&d);
241 /** @brief Convert UTF-8 to UTF-32
242 * @param s Source string
243 * @param ns Length of source string in code points
244 * @param ndp Where to store length of destination string (or NULL)
245 * @return Newly allocated destination string or NULL on error
247 * The return value is always 0-terminated. The value returned via @p *ndp
248 * does not include the terminator.
250 * If the UTF-8 is not valid then NULL is returned. A UTF-8 sequence
251 * for a code point is invalid if:
252 * - it is not the shortest possible sequence for the code point
253 * - it codes for a UTF-16 surrogate
254 * - it codes for a value outside the unicode code space
256 uint32_t *utf8_to_utf32(const char *s, size_t ns, size_t *ndp) {
257 struct dynstr_ucs4 d;
259 const uint8_t *ss = (const uint8_t *)s;
262 dynstr_ucs4_init(&d);
264 const struct unicode_utf8_row *const r = &unicode_utf8_valid[*ss];
271 if(ss[1] < r->min2 || ss[1] > r->max2)
276 if(ss[1] < r->min2 || ss[1] > r->max2)
281 if(ss[1] < r->min2 || ss[1] > r->max2)
290 for(n = 1; n < r->count; ++n) {
291 if(ss[n] < 0x80 || ss[n] > 0xBF)
293 c32 = (c32 << 6) | (ss[n] & 0x3F);
295 dynstr_ucs4_append(&d, c32);
299 dynstr_ucs4_terminate(&d);
308 /** @brief Test whether [s,s+ns) is valid UTF-8
309 * @param s Start of string
310 * @param ns Length of string
311 * @return non-0 if @p s is valid UTF-8, 0 if it is not valid
313 * This function is intended to be much faster than calling utf8_to_utf32() and
314 * throwing away the result.
316 int utf8_valid(const char *s, size_t ns) {
317 const uint8_t *ss = (const uint8_t *)s;
319 const struct unicode_utf8_row *const r = &unicode_utf8_valid[*ss];
325 if(ss[1] < r->min2 || ss[1] > r->max2)
329 if(ss[1] < r->min2 || ss[1] > r->max2)
331 if(ss[2] < 0x80 || ss[2] > 0xBF)
335 if(ss[1] < r->min2 || ss[1] > r->max2)
337 if(ss[2] < 0x80 || ss[2] > 0xBF)
339 if(ss[3] < 0x80 || ss[3] > 0xBF)
354 /** @defgroup utf32iterator UTF-32 string iterators */
357 struct utf32_iterator_data {
358 /** @brief Start of string */
361 /** @brief Length of string */
364 /** @brief Current position */
367 /** @brief Last two non-ignorable characters or (uint32_t)-1
369 * last[1] is the non-Extend/Format character just before position @p n;
370 * last[0] is the one just before that.
372 * Exception 1: if there is no such non-Extend/Format character then an
373 * Extend/Format character is accepted instead.
375 * Exception 2: if there is no such character even taking that into account
376 * the value is (uint32_t)-1.
380 /** @brief Tailoring for Word_Break */
381 unicode_property_tailor *word_break;
384 /** @brief Initialize an internal private iterator
386 * @param s Start of string
387 * @param ns Length of string
388 * @param n Absolute position
390 static void utf32__iterator_init(utf32_iterator it,
391 const uint32_t *s, size_t ns, size_t n) {
395 it->last[0] = it->last[1] = -1;
397 utf32_iterator_set(it, n);
400 /** @brief Create a new iterator pointing at the start of a string
401 * @param s Start of string
402 * @param ns Length of string
403 * @return New iterator
405 utf32_iterator utf32_iterator_new(const uint32_t *s, size_t ns) {
406 utf32_iterator it = xmalloc(sizeof *it);
407 utf32__iterator_init(it, s, ns, 0);
411 /** @brief Tailor this iterator's interpretation of the Word_Break property.
413 * @param pt Property tailor function or NULL
415 * After calling this the iterator will call @p pt to determine the Word_Break
416 * property of each code point. If it returns -1 the default value will be
417 * used otherwise the returned value will be used.
419 * @p pt can be NULL to revert to the default value of the property.
421 * It is safe to call this function at any time; the iterator's internal state
422 * will be reset to suit the new tailoring.
424 void utf32_iterator_tailor_word_break(utf32_iterator it,
425 unicode_property_tailor *pt) {
427 utf32_iterator_set(it, it->n);
430 static inline enum unicode_Word_Break utf32__iterator_word_break(utf32_iterator it,
433 return utf32__word_break(c);
435 const int t = it->word_break(c);
438 return utf32__word_break(c);
444 /** @brief Destroy an iterator
447 void utf32_iterator_destroy(utf32_iterator it) {
451 /** @brief Find the current position of an interator
454 size_t utf32_iterator_where(utf32_iterator it) {
458 /** @brief Set an iterator's absolute position
460 * @param n Absolute position
461 * @return 0 on success, non-0 on error
463 * It is an error to position the iterator outside the string (but acceptable
464 * to point it at the hypothetical post-final character). If an invalid value
465 * of @p n is specified then the iterator is not changed.
467 * This function works by backing up and then advancing to reconstruct the
468 * iterator's internal state for position @p n. The worst case will be O(n)
469 * time complexity (with a worse constant factor that utf32_iterator_advance())
470 * but the typical case is essentially constant-time.
472 int utf32_iterator_set(utf32_iterator it, size_t n) {
473 /* We can't just jump to position @p n; the @p last[] values will be wrong.
474 * What we need is to jump a bit behind @p n and then advance forward,
475 * updating @p last[] along the way. How far back? We need to cross two
476 * non-ignorable code points as we advance forwards, so we'd better pass two
477 * such characters on the way back (if such are available).
481 if(n > it->ns) /* range check */
483 /* Walk backwards skipping ignorable code points */
486 && (utf32__boundary_ignorable(utf32__iterator_word_break(it,
489 /* Either m=0 or s[m-1] is not ignorable */
492 /* s[m] is our first non-ignorable code; look for a second in the same
495 && (utf32__boundary_ignorable(utf32__iterator_word_break(it,
498 /* Either m=0 or s[m-1] is not ignorable */
502 it->last[0] = it->last[1] = -1;
504 return utf32_iterator_advance(it, n - m);
507 /** @brief Advance an iterator
509 * @param count Number of code points to advance by
510 * @return 0 on success, non-0 on error
512 * It is an error to advance an iterator beyond the hypothetical post-final
513 * character of the string. If an invalid value of @p n is specified then the
514 * iterator is not changed.
516 * This function has O(n) time complexity: it works by advancing naively
517 * forwards through the string.
519 int utf32_iterator_advance(utf32_iterator it, size_t count) {
520 if(count <= it->ns - it->n) {
522 const uint32_t c = it->s[it->n];
523 const enum unicode_Word_Break wb = utf32__iterator_word_break(it, c);
524 if(it->last[1] == (uint32_t)-1
525 || !utf32__boundary_ignorable(wb)) {
526 it->last[0] = it->last[1];
537 /** @brief Find the current code point
539 * @return Current code point or 0
541 * If the iterator points at the hypothetical post-final character of the
542 * string then 0 is returned. NB that this doesn't mean that there aren't any
543 * 0 code points inside the string!
545 uint32_t utf32_iterator_code(utf32_iterator it) {
552 /** @brief Test for a grapheme boundary
554 * @return Non-0 if pointing just after a grapheme boundary, otherwise 0
556 * This function identifies default grapheme cluster boundaries as described in
557 * UAX #29 s3. It returns non-0 if @p it points at the code point just after a
558 * grapheme cluster boundary (including the hypothetical code point just after
559 * the end of the string).
561 int utf32_iterator_grapheme_boundary(utf32_iterator it) {
562 uint32_t before, after;
563 enum unicode_Grapheme_Break gbbefore, gbafter;
565 if(it->n == 0 || it->n == it->ns)
567 /* Now we know that s[n-1] and s[n] are safe to inspect */
569 before = it->s[it->n-1];
570 after = it->s[it->n];
571 if(before == 0x000D && after == 0x000A)
573 gbbefore = utf32__grapheme_break(before);
574 gbafter = utf32__grapheme_break(after);
576 if(gbbefore == unicode_Grapheme_Break_Control
581 if(gbafter == unicode_Grapheme_Break_Control
586 if(gbbefore == unicode_Grapheme_Break_L
587 && (gbafter == unicode_Grapheme_Break_L
588 || gbafter == unicode_Grapheme_Break_V
589 || gbafter == unicode_Grapheme_Break_LV
590 || gbafter == unicode_Grapheme_Break_LVT))
593 if((gbbefore == unicode_Grapheme_Break_LV
594 || gbbefore == unicode_Grapheme_Break_V)
595 && (gbafter == unicode_Grapheme_Break_V
596 || gbafter == unicode_Grapheme_Break_T))
599 if((gbbefore == unicode_Grapheme_Break_LVT
600 || gbbefore == unicode_Grapheme_Break_T)
601 && gbafter == unicode_Grapheme_Break_T)
604 if(gbafter == unicode_Grapheme_Break_Extend)
607 if(gbafter == unicode_Grapheme_Break_SpacingMark)
610 if(gbbefore == unicode_Grapheme_Break_Prepend)
617 /** @brief Test for a word boundary
619 * @return Non-0 if pointing just after a word boundary, otherwise 0
621 * This function identifies default word boundaries as described in UAX #29 s4.
622 * It returns non-0 if @p it points at the code point just after a word
623 * boundary (including the hypothetical code point just after the end of the
624 * string) and 0 otherwise.
626 int utf32_iterator_word_boundary(utf32_iterator it) {
627 enum unicode_Word_Break twobefore, before, after, twoafter;
631 if(it->n == 0 || it->n == it->ns)
634 if(it->s[it->n-1] == 0x000D && it->s[it->n] == 0x000A)
637 if(utf32__iterator_word_break(it, it->s[it->n-1]) == unicode_Word_Break_Newline
638 || it->s[it->n-1] == 0x000D
639 || it->s[it->n-1] == 0x000A)
642 if(utf32__iterator_word_break(it, it->s[it->n]) == unicode_Word_Break_Newline
643 || it->s[it->n] == 0x000D
644 || it->s[it->n] == 0x000A)
647 /* (!Sep) x (Extend|Format) as in UAX #29 s6.2 */
648 if(utf32__sentence_break(it->s[it->n-1]) != unicode_Sentence_Break_Sep
649 && utf32__boundary_ignorable(utf32__iterator_word_break(it, it->s[it->n])))
651 /* Gather the property values we'll need for the rest of the test taking the
652 * s6.2 changes into account */
653 /* First we look at the code points after the proposed boundary */
654 nn = it->n; /* <it->ns */
655 after = utf32__iterator_word_break(it, it->s[nn++]);
656 if(!utf32__boundary_ignorable(after)) {
657 /* X (Extend|Format)* -> X */
659 && utf32__boundary_ignorable(utf32__iterator_word_break(it,
663 /* It's possible now that nn=ns */
665 twoafter = utf32__iterator_word_break(it, it->s[nn]);
667 twoafter = unicode_Word_Break_Other;
669 /* We've already recorded the non-ignorable code points before the proposed
671 before = utf32__iterator_word_break(it, it->last[1]);
672 twobefore = utf32__iterator_word_break(it, it->last[0]);
675 if(before == unicode_Word_Break_ALetter
676 && after == unicode_Word_Break_ALetter)
679 if(before == unicode_Word_Break_ALetter
680 && (after == unicode_Word_Break_MidLetter
681 || after == unicode_Word_Break_MidNumLet)
682 && twoafter == unicode_Word_Break_ALetter)
685 if(twobefore == unicode_Word_Break_ALetter
686 && (before == unicode_Word_Break_MidLetter
687 || before == unicode_Word_Break_MidNumLet)
688 && after == unicode_Word_Break_ALetter)
691 if(before == unicode_Word_Break_Numeric
692 && after == unicode_Word_Break_Numeric)
695 if(before == unicode_Word_Break_ALetter
696 && after == unicode_Word_Break_Numeric)
699 if(before == unicode_Word_Break_Numeric
700 && after == unicode_Word_Break_ALetter)
703 if(twobefore == unicode_Word_Break_Numeric
704 && (before == unicode_Word_Break_MidNum
705 || before == unicode_Word_Break_MidNumLet)
706 && after == unicode_Word_Break_Numeric)
709 if(before == unicode_Word_Break_Numeric
710 && (after == unicode_Word_Break_MidNum
711 || after == unicode_Word_Break_MidNumLet)
712 && twoafter == unicode_Word_Break_Numeric)
715 if(before == unicode_Word_Break_Katakana
716 && after == unicode_Word_Break_Katakana)
719 if((before == unicode_Word_Break_ALetter
720 || before == unicode_Word_Break_Numeric
721 || before == unicode_Word_Break_Katakana
722 || before == unicode_Word_Break_ExtendNumLet)
723 && after == unicode_Word_Break_ExtendNumLet)
726 if(before == unicode_Word_Break_ExtendNumLet
727 && (after == unicode_Word_Break_ALetter
728 || after == unicode_Word_Break_Numeric
729 || after == unicode_Word_Break_Katakana))
736 /** @defgroup utf32 Functions that operate on UTF-32 strings */
739 /** @brief Return the length of a 0-terminated UTF-32 string
740 * @param s Pointer to 0-terminated string
741 * @return Length of string in code points (excluding terminator)
743 * Unlike the conversion functions no validity checking is done on the string.
745 size_t utf32_len(const uint32_t *s) {
746 const uint32_t *t = s;
750 return (size_t)(t - s);
753 /** @brief Stably sort [s,s+ns) into descending order of combining class
754 * @param s Start of array
755 * @param ns Number of elements, must be at least 1
756 * @param buffer Buffer of at least @p ns elements
758 static void utf32__sort_ccc(uint32_t *s, size_t ns, uint32_t *buffer) {
759 uint32_t *a, *b, *bp;
763 case 1: /* 1-element array is always sorted */
765 case 2: /* 2-element arrays are trivial to sort */
766 if(utf32__combining_class(s[0]) > utf32__combining_class(s[1])) {
773 /* Partition the array */
778 /* Sort the two halves of the array */
779 utf32__sort_ccc(a, na, buffer);
780 utf32__sort_ccc(b, nb, buffer);
781 /* Merge them back into one, via the buffer */
783 while(na > 0 && nb > 0) {
784 /* We want ascending order of combining class (hence <)
785 * and we want stability within combining classes (hence <=)
787 if(utf32__combining_class(*a) <= utf32__combining_class(*b)) {
803 memcpy(s, buffer, ns * sizeof(uint32_t));
808 /** @brief Put combining characters into canonical order
809 * @param s Pointer to UTF-32 string
810 * @param ns Length of @p s
811 * @return 0 on success, non-0 on error
813 * @p s is modified in-place. See Unicode 5.0 s3.11 for details of the
816 * Currently we only support a maximum of 1024 combining characters after each
817 * base character. If this limit is exceeded then a non-0 value is returned.
819 static int utf32__canonical_ordering(uint32_t *s, size_t ns) {
821 uint32_t buffer[1024];
823 /* The ordering amounts to a stable sort of each contiguous group of
824 * characters with non-0 combining class. */
826 /* Skip non-combining characters */
827 if(utf32__combining_class(*s) == 0) {
832 /* We must now have at least one combining character; see how many
834 for(nc = 1; nc < ns && utf32__combining_class(s[nc]) != 0; ++nc)
839 utf32__sort_ccc(s, nc, buffer);
846 /* Magic numbers from UAX #15 s16 */
854 #define NCount (VCount * TCount)
855 #define SCount (LCount * NCount)
857 /** @brief Guts of the decomposition lookup functions */
858 #define utf32__decompose_one_generic(WHICH) do { \
859 const uint32_t *dc = utf32__decomposition_##WHICH(c); \
861 /* Found a canonical decomposition in the table */ \
863 utf32__decompose_one_##WHICH(d, *dc++); \
864 } else if(c >= SBase && c < SBase + SCount) { \
865 /* Mechanically decomposable Hangul syllable (UAX #15 s16) */ \
866 const uint32_t SIndex = c - SBase; \
867 const uint32_t L = LBase + SIndex / NCount; \
868 const uint32_t V = VBase + (SIndex % NCount) / TCount; \
869 const uint32_t T = TBase + SIndex % TCount; \
870 dynstr_ucs4_append(d, L); \
871 dynstr_ucs4_append(d, V); \
873 dynstr_ucs4_append(d, T); \
875 /* Equal to own canonical decomposition */ \
876 dynstr_ucs4_append(d, c); \
879 /** @brief Recursively compute the canonical decomposition of @p c
880 * @param d Dynamic string to store decomposition in
881 * @param c Code point to decompose (must be a valid!)
882 * @return 0 on success, non-0 on error
884 static void utf32__decompose_one_canon(struct dynstr_ucs4 *d, uint32_t c) {
885 utf32__decompose_one_generic(canon);
888 /** @brief Recursively compute the compatibility decomposition of @p c
889 * @param d Dynamic string to store decomposition in
890 * @param c Code point to decompose (must be a valid!)
891 * @return 0 on success, non-0 on error
893 static void utf32__decompose_one_compat(struct dynstr_ucs4 *d, uint32_t c) {
894 utf32__decompose_one_generic(compat);
897 /** @brief Magic utf32__compositions() return value for Hangul Choseong */
898 static const uint32_t utf32__hangul_L[1];
900 /** @brief Return the list of compositions that @p c starts
901 * @param c Starter code point
902 * @return Composition list or NULL
904 * For Hangul leading (Choseong) jamo we return the special value
905 * utf32__hangul_L. These code points are not listed as the targets of
906 * canonical decompositions (make-unidata checks) so there is no confusion with
907 * real decompositions here.
909 static const uint32_t *utf32__compositions(uint32_t c) {
910 const uint32_t *compositions = utf32__unidata(c)->composed;
914 /* Special-casing for Hangul */
915 switch(utf32__grapheme_break(c)) {
918 case unicode_Grapheme_Break_L:
919 return utf32__hangul_L;
923 /** @brief Composition step
924 * @param s Start of string
925 * @param ns Length of string
926 * @return New length of string
928 * This is called from utf32__decompose_generic() to compose the result string
931 static size_t utf32__compose(uint32_t *s, size_t ns) {
932 const uint32_t *compositions;
933 uint32_t *start = s, *t = s, *tt, cc;
936 uint32_t starter = *s++;
937 int block_starters = 0;
939 /* We don't attempt to compose the following things:
940 * - final characters whatever kind they are
941 * - non-starter characters
942 * - starters that don't take part in a canonical decomposition mapping
945 || utf32__combining_class(starter)
946 || !(compositions = utf32__compositions(starter))) {
950 if(compositions != utf32__hangul_L) {
951 /* Where we'll put the eventual starter */
954 /* See if we can find composition of starter+*s */
955 const uint32_t cchar = *s, *cp = compositions;
956 while((cc = *cp++)) {
957 const uint32_t *decomp = utf32__decomposition_canon(cc);
958 /* We know decomp[0] == starter */
959 if(decomp[1] == cchar)
963 /* Found a composition: cc decomposes to starter,*s */
965 compositions = utf32__compositions(starter);
969 /* No composition found. */
970 const int class = utf32__combining_class(*s);
972 /* Transfer the uncomposable combining character to the output */
975 /* All the combining characters of the same class of the
976 * uncomposable character are blocked by it, but there may be
977 * others of higher class later. We eat the uncomposable and
978 * blocked characters and go back round the loop for that higher
980 while(ns > 0 && utf32__combining_class(*s) == class) {
984 /* Block any subsequent starters */
987 /* The uncombinable character is itself a starter, so we don't
988 * transfer it to the output but instead go back round the main
993 /* Keep going while there are still characters and the starter takes
994 * part in some composition */
995 } while(ns > 0 && compositions
996 && (!block_starters || utf32__combining_class(*s)));
997 /* Store any remaining combining characters */
998 while(ns > 0 && utf32__combining_class(*s)) {
1002 /* Store the resulting starter */
1005 /* Special-casing for Hangul
1007 * If there are combining characters between the L and the V then they
1008 * will block the V and so no composition happens. Similarly combining
1009 * characters between V and T will block the T and so we only get as far
1012 if(utf32__grapheme_break(*s) == unicode_Grapheme_Break_V) {
1013 const uint32_t V = *s++;
1014 const uint32_t LIndex = starter - LBase;
1015 const uint32_t VIndex = V - VBase;
1019 && utf32__grapheme_break(*s) == unicode_Grapheme_Break_T) {
1020 /* We have an L V T sequence */
1021 const uint32_t T = *s++;
1027 /* Compose to LVT or LV as appropriate */
1028 starter = (LIndex * VCount + VIndex) * TCount + TIndex + SBase;
1029 } /* else we only have L or LV and no V or T */
1031 /* There could be some combining characters that belong to the V or T.
1032 * These will be treated as non-starter characters at the top of the loop
1033 * and thuss transferred to the output. */
1039 /** @brief Guts of the composition and decomposition functions
1040 * @param WHICH @c canon or @c compat to choose decomposition
1041 * @param COMPOSE @c 0 or @c 1 to compose
1043 #define utf32__decompose_generic(WHICH, COMPOSE) do { \
1044 struct dynstr_ucs4 d; \
1047 dynstr_ucs4_init(&d); \
1050 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \
1052 utf32__decompose_one_##WHICH(&d, c); \
1055 if(utf32__canonical_ordering(d.vec, d.nvec)) \
1058 d.nvec = utf32__compose(d.vec, d.nvec); \
1059 dynstr_ucs4_terminate(&d); \
1068 /** @brief Canonically decompose @p [s,s+ns)
1069 * @param s Pointer to string
1070 * @param ns Length of string
1071 * @param ndp Where to store length of result
1072 * @return Pointer to result string, or NULL on error
1074 * Computes NFD (Normalization Form D) of the string at @p s. This implies
1075 * performing all canonical decompositions and then normalizing the order of
1076 * combining characters.
1078 * Returns NULL if the string is not valid for either of the following reasons:
1079 * - it codes for a UTF-16 surrogate
1080 * - it codes for a value outside the unicode code space
1083 * - utf32_decompose_compat()
1084 * - utf32_compose_canon()
1086 uint32_t *utf32_decompose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1087 utf32__decompose_generic(canon, 0);
1090 /** @brief Compatibility decompose @p [s,s+ns)
1091 * @param s Pointer to string
1092 * @param ns Length of string
1093 * @param ndp Where to store length of result
1094 * @return Pointer to result string, or NULL on error
1096 * Computes NFKD (Normalization Form KD) of the string at @p s. This implies
1097 * performing all canonical and compatibility decompositions and then
1098 * normalizing the order of combining characters.
1100 * Returns NULL if the string is not valid for either of the following reasons:
1101 * - it codes for a UTF-16 surrogate
1102 * - it codes for a value outside the unicode code space
1105 * - utf32_decompose_canon()
1106 * - utf32_compose_compat()
1108 uint32_t *utf32_decompose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1109 utf32__decompose_generic(compat, 0);
1112 /** @brief Canonically compose @p [s,s+ns)
1113 * @param s Pointer to string
1114 * @param ns Length of string
1115 * @param ndp Where to store length of result
1116 * @return Pointer to result string, or NULL on error
1118 * Computes NFC (Normalization Form C) of the string at @p s. This implies
1119 * performing all canonical decompositions, normalizing the order of combining
1120 * characters and then composing all unblocked primary compositables.
1122 * Returns NULL if the string is not valid for either of the following reasons:
1123 * - it codes for a UTF-16 surrogate
1124 * - it codes for a value outside the unicode code space
1127 * - utf32_compose_compat()
1128 * - utf32_decompose_canon()
1130 uint32_t *utf32_compose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1131 utf32__decompose_generic(canon, 1);
1134 /** @brief Compatibility compose @p [s,s+ns)
1135 * @param s Pointer to string
1136 * @param ns Length of string
1137 * @param ndp Where to store length of result
1138 * @return Pointer to result string, or NULL on error
1140 * Computes NFKC (Normalization Form KC) of the string at @p s. This implies
1141 * performing all canonical and compatibility decompositions, normalizing the
1142 * order of combining characters and then composing all unblocked primary
1145 * Returns NULL if the string is not valid for either of the following reasons:
1146 * - it codes for a UTF-16 surrogate
1147 * - it codes for a value outside the unicode code space
1150 * - utf32_compose_canon()
1151 * - utf32_decompose_compat()
1153 uint32_t *utf32_compose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1154 utf32__decompose_generic(compat, 1);
1157 /** @brief Single-character case-fold and decompose operation */
1158 #define utf32__casefold_one(WHICH) do { \
1159 const uint32_t *cf = utf32__unidata(c)->casefold; \
1161 /* Found a case-fold mapping in the table */ \
1163 utf32__decompose_one_##WHICH(&d, *cf++); \
1165 utf32__decompose_one_##WHICH(&d, c); \
1168 /** @brief Case-fold @p [s,s+ns)
1169 * @param s Pointer to string
1170 * @param ns Length of string
1171 * @param ndp Where to store length of result
1172 * @return Pointer to result string, or NULL on error
1174 * Case-fold the string at @p s according to full default case-folding rules
1175 * (s3.13) for caseless matching. The result will be in NFD.
1177 * Returns NULL if the string is not valid for either of the following reasons:
1178 * - it codes for a UTF-16 surrogate
1179 * - it codes for a value outside the unicode code space
1181 uint32_t *utf32_casefold_canon(const uint32_t *s, size_t ns, size_t *ndp) {
1182 struct dynstr_ucs4 d;
1187 /* If the canonical decomposition of the string includes any combining
1188 * character that case-folds to a non-combining character then we must
1189 * normalize before we fold. In Unicode 5.0.0 this means 0345 COMBINING
1190 * GREEK YPOGEGRAMMENI in its decomposition and the various characters that
1191 * canonically decompose to it. */
1192 for(n = 0; n < ns; ++n)
1193 if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
1196 /* We need a preliminary decomposition */
1197 if(!(ss = utf32_decompose_canon(s, ns, &ns)))
1201 dynstr_ucs4_init(&d);
1204 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)
1206 utf32__casefold_one(canon);
1209 if(utf32__canonical_ordering(d.vec, d.nvec))
1211 dynstr_ucs4_terminate(&d);
1221 /** @brief Compatibility case-fold @p [s,s+ns)
1222 * @param s Pointer to string
1223 * @param ns Length of string
1224 * @param ndp Where to store length of result
1225 * @return Pointer to result string, or NULL on error
1227 * Case-fold the string at @p s according to full default case-folding rules
1228 * (s3.13) for compatibility caseless matching. The result will be in NFKD.
1230 * Returns NULL if the string is not valid for either of the following reasons:
1231 * - it codes for a UTF-16 surrogate
1232 * - it codes for a value outside the unicode code space
1234 uint32_t *utf32_casefold_compat(const uint32_t *s, size_t ns, size_t *ndp) {
1235 struct dynstr_ucs4 d;
1240 for(n = 0; n < ns; ++n)
1241 if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
1244 /* We need a preliminary _canonical_ decomposition */
1245 if(!(ss = utf32_decompose_canon(s, ns, &ns)))
1249 /* This computes NFKD(toCaseFold(s)) */
1250 #define compat_casefold_middle() do { \
1251 dynstr_ucs4_init(&d); \
1254 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \
1256 utf32__casefold_one(compat); \
1259 if(utf32__canonical_ordering(d.vec, d.nvec)) \
1262 /* Do the inner (NFKD o toCaseFold) */
1263 compat_casefold_middle();
1264 /* We can do away with the NFD'd copy of the input now */
1268 /* Do the outer (NFKD o toCaseFold) */
1269 compat_casefold_middle();
1271 dynstr_ucs4_terminate(&d);
1281 /** @brief Order a pair of UTF-32 strings
1282 * @param a First 0-terminated string
1283 * @param b Second 0-terminated string
1284 * @return -1, 0 or 1 for a less than, equal to or greater than b
1286 * "Comparable to strcmp() at its best."
1288 int utf32_cmp(const uint32_t *a, const uint32_t *b) {
1289 while(*a && *b && *a == *b) {
1293 return *a < *b ? -1 : (*a > *b ? 1 : 0);
1296 /** @brief Identify a grapheme cluster boundary
1297 * @param s Start of string (must be NFD)
1298 * @param ns Length of string
1299 * @param n Index within string (in [0,ns].)
1300 * @return 1 at a grapheme cluster boundary, 0 otherwise
1302 * This function identifies default grapheme cluster boundaries as described in
1303 * UAX #29 s3. It returns non-0 if @p n points at the code point just after a
1304 * grapheme cluster boundary (including the hypothetical code point just after
1305 * the end of the string).
1307 * This function uses utf32_iterator_set() internally; see that function for
1308 * remarks on performance.
1310 int utf32_is_grapheme_boundary(const uint32_t *s, size_t ns, size_t n) {
1311 struct utf32_iterator_data it[1];
1313 utf32__iterator_init(it, s, ns, n);
1314 return utf32_iterator_grapheme_boundary(it);
1317 /** @brief Identify a word boundary
1318 * @param s Start of string (must be NFD)
1319 * @param ns Length of string
1320 * @param n Index within string (in [0,ns].)
1321 * @return 1 at a word boundary, 0 otherwise
1323 * This function identifies default word boundaries as described in UAX #29 s4.
1324 * It returns non-0 if @p n points at the code point just after a word boundary
1325 * (including the hypothetical code point just after the end of the string).
1327 * This function uses utf32_iterator_set() internally; see that function for
1328 * remarks on performance.
1330 int utf32_is_word_boundary(const uint32_t *s, size_t ns, size_t n) {
1331 struct utf32_iterator_data it[1];
1333 utf32__iterator_init(it, s, ns, n);
1334 return utf32_iterator_word_boundary(it);
1337 /** @brief Split [s,ns) into multiple words
1338 * @param s Pointer to start of string
1339 * @param ns Length of string
1340 * @param nwp Where to store word count, or NULL
1341 * @param wbreak Word_Break property tailor, or NULL
1342 * @return Pointer to array of pointers to words
1344 * The returned array is terminated by a NULL pointer and individual
1345 * strings are 0-terminated.
1347 uint32_t **utf32_word_split(const uint32_t *s, size_t ns, size_t *nwp,
1348 unicode_property_tailor *wbreak) {
1349 struct utf32_iterator_data it[1];
1350 size_t b1 = 0, b2 = 0 ,i;
1352 struct vector32 v32[1];
1356 utf32__iterator_init(it, s, ns, 0);
1357 it->word_break = wbreak;
1358 /* Work our way through the string stopping at each word break. */
1360 if(utf32_iterator_word_boundary(it)) {
1361 /* We've found a new boundary */
1364 /*fprintf(stderr, "[%zu, %zu) is a candidate word\n", b1, b2);*/
1365 /* Inspect the characters between the boundary and form an opinion as to
1366 * whether they are a word or not */
1368 for(i = b1; i < b2; ++i) {
1369 switch(utf32__iterator_word_break(it, it->s[i])) {
1370 case unicode_Word_Break_ALetter:
1371 case unicode_Word_Break_Numeric:
1372 case unicode_Word_Break_Katakana:
1379 /* If it's a word add it to the list of results */
1381 const size_t len = b2 - b1;
1382 w = xcalloc_noptr(len + 1, sizeof(uint32_t));
1383 memcpy(w, it->s + b1, len * sizeof (uint32_t));
1385 vector32_append(v32, w);
1388 } while(!utf32_iterator_advance(it, 1));
1389 vector32_terminate(v32);
1396 /** @defgroup utf8 Functions that operate on UTF-8 strings */
1399 /** @brief Wrapper to transform a UTF-8 string using the UTF-32 function */
1400 #define utf8__transform(FN) do { \
1401 uint32_t *to32 = 0, *decomp32 = 0; \
1402 size_t nto32, ndecomp32; \
1403 char *decomp8 = 0; \
1405 if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error; \
1406 if(!(decomp32 = FN(to32, nto32, &ndecomp32))) goto error; \
1407 decomp8 = utf32_to_utf8(decomp32, ndecomp32, ndp); \
1414 /** @brief Canonically decompose @p [s,s+ns)
1415 * @param s Pointer to string
1416 * @param ns Length of string
1417 * @param ndp Where to store length of result
1418 * @return Pointer to result string, or NULL on error
1420 * Computes NFD (Normalization Form D) of the string at @p s. This implies
1421 * performing all canonical decompositions and then normalizing the order of
1422 * combining characters.
1424 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1428 * - utf32_decompose_canon().
1429 * - utf8_decompose_compat()
1430 * - utf8_compose_canon()
1432 char *utf8_decompose_canon(const char *s, size_t ns, size_t *ndp) {
1433 utf8__transform(utf32_decompose_canon);
1436 /** @brief Compatibility decompose @p [s,s+ns)
1437 * @param s Pointer to string
1438 * @param ns Length of string
1439 * @param ndp Where to store length of result
1440 * @return Pointer to result string, or NULL on error
1442 * Computes NFKD (Normalization Form KD) of the string at @p s. This implies
1443 * performing all canonical and compatibility decompositions and then
1444 * normalizing the order of combining characters.
1446 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1450 * - utf32_decompose_compat().
1451 * - utf8_decompose_canon()
1452 * - utf8_compose_compat()
1454 char *utf8_decompose_compat(const char *s, size_t ns, size_t *ndp) {
1455 utf8__transform(utf32_decompose_compat);
1458 /** @brief Canonically compose @p [s,s+ns)
1459 * @param s Pointer to string
1460 * @param ns Length of string
1461 * @param ndp Where to store length of result
1462 * @return Pointer to result string, or NULL on error
1464 * Computes NFC (Normalization Form C) of the string at @p s. This implies
1465 * performing all canonical decompositions, normalizing the order of combining
1466 * characters and then composing all unblocked primary compositables.
1468 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1472 * - utf32_compose_canon()
1473 * - utf8_compose_compat()
1474 * - utf8_decompose_canon()
1476 char *utf8_compose_canon(const char *s, size_t ns, size_t *ndp) {
1477 utf8__transform(utf32_compose_canon);
1480 /** @brief Compatibility compose @p [s,s+ns)
1481 * @param s Pointer to string
1482 * @param ns Length of string
1483 * @param ndp Where to store length of result
1484 * @return Pointer to result string, or NULL on error
1486 * Computes NFKC (Normalization Form KC) of the string at @p s. This implies
1487 * performing all canonical and compatibility decompositions, normalizing the
1488 * order of combining characters and then composing all unblocked primary
1491 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1495 * - utf32_compose_compat()
1496 * - utf8_compose_canon()
1497 * - utf8_decompose_compat()
1499 char *utf8_compose_compat(const char *s, size_t ns, size_t *ndp) {
1500 utf8__transform(utf32_compose_compat);
1503 /** @brief Case-fold @p [s,s+ns)
1504 * @param s Pointer to string
1505 * @param ns Length of string
1506 * @param ndp Where to store length of result
1507 * @return Pointer to result string, or NULL on error
1509 * Case-fold the string at @p s according to full default case-folding rules
1510 * (s3.13). The result will be in NFD.
1512 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1515 char *utf8_casefold_canon(const char *s, size_t ns, size_t *ndp) {
1516 utf8__transform(utf32_casefold_canon);
1519 /** @brief Compatibility case-fold @p [s,s+ns)
1520 * @param s Pointer to string
1521 * @param ns Length of string
1522 * @param ndp Where to store length of result
1523 * @return Pointer to result string, or NULL on error
1525 * Case-fold the string at @p s according to full default case-folding rules
1526 * (s3.13). The result will be in NFKD.
1528 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1531 char *utf8_casefold_compat(const char *s, size_t ns, size_t *ndp) {
1532 utf8__transform(utf32_casefold_compat);
1535 /** @brief Split [s,ns) into multiple words
1536 * @param s Pointer to start of string
1537 * @param ns Length of string
1538 * @param nwp Where to store word count, or NULL
1539 * @param wbreak Word_Break property tailor, or NULL
1540 * @return Pointer to array of pointers to words
1542 * The returned array is terminated by a NULL pointer and individual
1543 * strings are 0-terminated.
1545 char **utf8_word_split(const char *s, size_t ns, size_t *nwp,
1546 unicode_property_tailor *wbreak) {
1547 uint32_t *to32 = 0, **v32 = 0;
1548 size_t nto32, nv, n;
1549 char **v8 = 0, **ret = 0;
1551 if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error;
1552 if(!(v32 = utf32_word_split(to32, nto32, &nv, wbreak))) goto error;
1553 v8 = xcalloc(sizeof (char *), nv + 1);
1554 for(n = 0; n < nv; ++n)
1555 if(!(v8[n] = utf32_to_utf8(v32[n], utf32_len(v32[n]), 0)))
1559 v8 = 0; /* don't free */
1562 for(n = 0; n < nv; ++n)
1567 for(n = 0; n < nv; ++n)
1583 indent-tabs-mode:nil