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 combining class of @p c
113 * @param c Code point
114 * @return Combining class of @p c
116 * @p c can be any 32-bit value, a sensible value will be returned regardless.
118 int utf32_combining_class(uint32_t c
) {
119 return utf32__combining_class(c
);
122 /** @brief Return the General_Category value for @p c
123 * @param c Code point
124 * @return General_Category property value
126 * @p c can be any 32-bit value, a sensible value will be returned regardless.
128 static inline enum unicode_General_Category
utf32__general_category(uint32_t c
) {
129 return utf32__unidata(c
)->general_category
;
132 /** @brief Determine Grapheme_Break property
133 * @param c Code point
134 * @return Grapheme_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_Grapheme_Break
utf32__grapheme_break(uint32_t c
) {
139 return utf32__unidata(c
)->grapheme_break
;
142 /** @brief Determine Word_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_Word_Break
utf32__word_break(uint32_t c
) {
149 return utf32__unidata(c
)->word_break
;
152 /** @brief Determine Sentence_Break property
153 * @param c Code point
154 * @return Word_Break property value of @p c
156 * @p c can be any 32-bit value, a sensible value will be returned regardless.
158 static inline enum unicode_Sentence_Break
utf32__sentence_break(uint32_t c
) {
159 return utf32__unidata(c
)->sentence_break
;
162 /** @brief Return true if @p c is ignorable for boundary specifications
163 * @param wb Word break property value
164 * @return non-0 if @p wb is unicode_Word_Break_Extend or unicode_Word_Break_Format
166 static inline int utf32__boundary_ignorable(enum unicode_Word_Break wb
) {
167 return (wb
== unicode_Word_Break_Extend
168 || wb
== unicode_Word_Break_Format
);
171 /** @brief Return the canonical decomposition of @p c
172 * @param c Code point
173 * @return 0-terminated canonical decomposition, or 0
175 static inline const uint32_t *utf32__decomposition_canon(uint32_t c
) {
176 const struct unidata
*const data
= utf32__unidata(c
);
177 const uint32_t *const decomp
= data
->decomp
;
179 if(decomp
&& !(data
->flags
& unicode_compatibility_decomposition
))
185 /** @brief Return the compatibility decomposition of @p c
186 * @param c Code point
187 * @return 0-terminated decomposition, or 0
189 static inline const uint32_t *utf32__decomposition_compat(uint32_t c
) {
190 return utf32__unidata(c
)->decomp
;
194 /** @defgroup utftransform Functions that transform between different Unicode encoding forms */
197 /** @brief Convert UTF-32 to UTF-8
198 * @param s Source string
199 * @param ns Length of source string in code points
200 * @param ndp Where to store length of destination string (or NULL)
201 * @return Newly allocated destination string or NULL on error
203 * If the UTF-32 is not valid then NULL is returned. A UTF-32 code point is
205 * - it codes for a UTF-16 surrogate
206 * - it codes for a value outside the unicode code space
208 * The return value is always 0-terminated. The value returned via @p *ndp
209 * does not include the terminator.
211 char *utf32_to_utf8(const uint32_t *s
, size_t ns
, size_t *ndp
) {
219 dynstr_append(&d
, c
);
220 else if(c
< 0x0800) {
221 dynstr_append(&d
, 0xC0 | (c
>> 6));
222 dynstr_append(&d
, 0x80 | (c
& 0x3F));
223 } else if(c
< 0x10000) {
224 if(c
>= 0xD800 && c
<= 0xDFFF)
226 dynstr_append(&d
, 0xE0 | (c
>> 12));
227 dynstr_append(&d
, 0x80 | ((c
>> 6) & 0x3F));
228 dynstr_append(&d
, 0x80 | (c
& 0x3F));
229 } else if(c
< 0x110000) {
230 dynstr_append(&d
, 0xF0 | (c
>> 18));
231 dynstr_append(&d
, 0x80 | ((c
>> 12) & 0x3F));
232 dynstr_append(&d
, 0x80 | ((c
>> 6) & 0x3F));
233 dynstr_append(&d
, 0x80 | (c
& 0x3F));
238 dynstr_terminate(&d
);
247 /** @brief Convert UTF-8 to UTF-32
248 * @param s Source string
249 * @param ns Length of source string in code points
250 * @param ndp Where to store length of destination string (or NULL)
251 * @return Newly allocated destination string or NULL on error
253 * The return value is always 0-terminated. The value returned via @p *ndp
254 * does not include the terminator.
256 * If the UTF-8 is not valid then NULL is returned. A UTF-8 sequence
257 * for a code point is invalid if:
258 * - it is not the shortest possible sequence for the code point
259 * - it codes for a UTF-16 surrogate
260 * - it codes for a value outside the unicode code space
262 uint32_t *utf8_to_utf32(const char *s
, size_t ns
, size_t *ndp
) {
263 struct dynstr_ucs4 d
;
265 const uint8_t *ss
= (const uint8_t *)s
;
268 dynstr_ucs4_init(&d
);
270 const struct unicode_utf8_row
*const r
= &unicode_utf8_valid
[*ss
];
277 if(ss
[1] < r
->min2
|| ss
[1] > r
->max2
)
282 if(ss
[1] < r
->min2
|| ss
[1] > r
->max2
)
287 if(ss
[1] < r
->min2
|| ss
[1] > r
->max2
)
296 for(n
= 1; n
< r
->count
; ++n
) {
297 if(ss
[n
] < 0x80 || ss
[n
] > 0xBF)
299 c32
= (c32
<< 6) | (ss
[n
] & 0x3F);
301 dynstr_ucs4_append(&d
, c32
);
305 dynstr_ucs4_terminate(&d
);
314 /** @brief Test whether [s,s+ns) is valid UTF-8
315 * @param s Start of string
316 * @param ns Length of string
317 * @return non-0 if @p s is valid UTF-8, 0 if it is not valid
319 * This function is intended to be much faster than calling utf8_to_utf32() and
320 * throwing away the result.
322 int utf8_valid(const char *s
, size_t ns
) {
323 const uint8_t *ss
= (const uint8_t *)s
;
325 const struct unicode_utf8_row
*const r
= &unicode_utf8_valid
[*ss
];
331 if(ss
[1] < r
->min2
|| ss
[1] > r
->max2
)
335 if(ss
[1] < r
->min2
|| ss
[1] > r
->max2
)
337 if(ss
[2] < 0x80 || ss
[2] > 0xBF)
341 if(ss
[1] < r
->min2
|| ss
[1] > r
->max2
)
343 if(ss
[2] < 0x80 || ss
[2] > 0xBF)
345 if(ss
[3] < 0x80 || ss
[3] > 0xBF)
360 /** @defgroup utf32iterator UTF-32 string iterators */
363 struct utf32_iterator_data
{
364 /** @brief Start of string */
367 /** @brief Length of string */
370 /** @brief Current position */
373 /** @brief Last two non-ignorable characters or (uint32_t)-1
375 * last[1] is the non-Extend/Format character just before position @p n;
376 * last[0] is the one just before that.
378 * Exception 1: if there is no such non-Extend/Format character then an
379 * Extend/Format character is accepted instead.
381 * Exception 2: if there is no such character even taking that into account
382 * the value is (uint32_t)-1.
386 /** @brief Tailoring for Word_Break */
387 unicode_property_tailor
*word_break
;
390 /** @brief Initialize an internal private iterator
392 * @param s Start of string
393 * @param ns Length of string
394 * @param n Absolute position
396 static void utf32__iterator_init(utf32_iterator it
,
397 const uint32_t *s
, size_t ns
, size_t n
) {
401 it
->last
[0] = it
->last
[1] = -1;
403 utf32_iterator_set(it
, n
);
406 /** @brief Create a new iterator pointing at the start of a string
407 * @param s Start of string
408 * @param ns Length of string
409 * @return New iterator
411 utf32_iterator
utf32_iterator_new(const uint32_t *s
, size_t ns
) {
412 utf32_iterator it
= xmalloc(sizeof *it
);
413 utf32__iterator_init(it
, s
, ns
, 0);
417 /** @brief Tailor this iterator's interpretation of the Word_Break property.
419 * @param pt Property tailor function or NULL
421 * After calling this the iterator will call @p pt to determine the Word_Break
422 * property of each code point. If it returns -1 the default value will be
423 * used otherwise the returned value will be used.
425 * @p pt can be NULL to revert to the default value of the property.
427 * It is safe to call this function at any time; the iterator's internal state
428 * will be reset to suit the new tailoring.
430 void utf32_iterator_tailor_word_break(utf32_iterator it
,
431 unicode_property_tailor
*pt
) {
433 utf32_iterator_set(it
, it
->n
);
436 static inline enum unicode_Word_Break
utf32__iterator_word_break(utf32_iterator it
,
439 return utf32__word_break(c
);
441 const int t
= it
->word_break(c
);
444 return utf32__word_break(c
);
450 /** @brief Destroy an iterator
453 void utf32_iterator_destroy(utf32_iterator it
) {
457 /** @brief Find the current position of an interator
460 size_t utf32_iterator_where(utf32_iterator it
) {
464 /** @brief Set an iterator's absolute position
466 * @param n Absolute position
467 * @return 0 on success, non-0 on error
469 * It is an error to position the iterator outside the string (but acceptable
470 * to point it at the hypothetical post-final character). If an invalid value
471 * of @p n is specified then the iterator is not changed.
473 * This function works by backing up and then advancing to reconstruct the
474 * iterator's internal state for position @p n. The worst case will be O(n)
475 * time complexity (with a worse constant factor that utf32_iterator_advance())
476 * but the typical case is essentially constant-time.
478 int utf32_iterator_set(utf32_iterator it
, size_t n
) {
479 /* We can't just jump to position @p n; the @p last[] values will be wrong.
480 * What we need is to jump a bit behind @p n and then advance forward,
481 * updating @p last[] along the way. How far back? We need to cross two
482 * non-ignorable code points as we advance forwards, so we'd better pass two
483 * such characters on the way back (if such are available).
487 if(n
> it
->ns
) /* range check */
489 /* Walk backwards skipping ignorable code points */
492 && (utf32__boundary_ignorable(utf32__iterator_word_break(it
,
495 /* Either m=0 or s[m-1] is not ignorable */
498 /* s[m] is our first non-ignorable code; look for a second in the same
501 && (utf32__boundary_ignorable(utf32__iterator_word_break(it
,
504 /* Either m=0 or s[m-1] is not ignorable */
508 it
->last
[0] = it
->last
[1] = -1;
510 return utf32_iterator_advance(it
, n
- m
);
513 /** @brief Advance an iterator
515 * @param count Number of code points to advance by
516 * @return 0 on success, non-0 on error
518 * It is an error to advance an iterator beyond the hypothetical post-final
519 * character of the string. If an invalid value of @p n is specified then the
520 * iterator is not changed.
522 * This function has O(n) time complexity: it works by advancing naively
523 * forwards through the string.
525 int utf32_iterator_advance(utf32_iterator it
, size_t count
) {
526 if(count
<= it
->ns
- it
->n
) {
528 const uint32_t c
= it
->s
[it
->n
];
529 const enum unicode_Word_Break wb
= utf32__iterator_word_break(it
, c
);
530 if(it
->last
[1] == (uint32_t)-1
531 || !utf32__boundary_ignorable(wb
)) {
532 it
->last
[0] = it
->last
[1];
543 /** @brief Find the current code point
545 * @return Current code point or 0
547 * If the iterator points at the hypothetical post-final character of the
548 * string then 0 is returned. NB that this doesn't mean that there aren't any
549 * 0 code points inside the string!
551 uint32_t utf32_iterator_code(utf32_iterator it
) {
558 /** @brief Test for a grapheme boundary
560 * @return Non-0 if pointing just after a grapheme boundary, otherwise 0
562 * This function identifies default grapheme cluster boundaries as described in
563 * UAX #29 s3. It returns non-0 if @p it points at the code point just after a
564 * grapheme cluster boundary (including the hypothetical code point just after
565 * the end of the string).
567 int utf32_iterator_grapheme_boundary(utf32_iterator it
) {
568 uint32_t before
, after
;
569 enum unicode_Grapheme_Break gbbefore
, gbafter
;
571 if(it
->n
== 0 || it
->n
== it
->ns
)
573 /* Now we know that s[n-1] and s[n] are safe to inspect */
575 before
= it
->s
[it
->n
-1];
576 after
= it
->s
[it
->n
];
577 if(before
== 0x000D && after
== 0x000A)
579 gbbefore
= utf32__grapheme_break(before
);
580 gbafter
= utf32__grapheme_break(after
);
582 if(gbbefore
== unicode_Grapheme_Break_Control
587 if(gbafter
== unicode_Grapheme_Break_Control
592 if(gbbefore
== unicode_Grapheme_Break_L
593 && (gbafter
== unicode_Grapheme_Break_L
594 || gbafter
== unicode_Grapheme_Break_V
595 || gbafter
== unicode_Grapheme_Break_LV
596 || gbafter
== unicode_Grapheme_Break_LVT
))
599 if((gbbefore
== unicode_Grapheme_Break_LV
600 || gbbefore
== unicode_Grapheme_Break_V
)
601 && (gbafter
== unicode_Grapheme_Break_V
602 || gbafter
== unicode_Grapheme_Break_T
))
605 if((gbbefore
== unicode_Grapheme_Break_LVT
606 || gbbefore
== unicode_Grapheme_Break_T
)
607 && gbafter
== unicode_Grapheme_Break_T
)
610 if(gbafter
== unicode_Grapheme_Break_Extend
)
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 /* (!Sep) x (Extend|Format) as in UAX #29 s6.2 */
638 if(utf32__sentence_break(it
->s
[it
->n
-1]) != unicode_Sentence_Break_Sep
639 && utf32__boundary_ignorable(utf32__iterator_word_break(it
, it
->s
[it
->n
])))
641 /* Gather the property values we'll need for the rest of the test taking the
642 * s6.2 changes into account */
643 /* First we look at the code points after the proposed boundary */
644 nn
= it
->n
; /* <it->ns */
645 after
= utf32__iterator_word_break(it
, it
->s
[nn
++]);
646 if(!utf32__boundary_ignorable(after
)) {
647 /* X (Extend|Format)* -> X */
649 && utf32__boundary_ignorable(utf32__iterator_word_break(it
,
653 /* It's possible now that nn=ns */
655 twoafter
= utf32__iterator_word_break(it
, it
->s
[nn
]);
657 twoafter
= unicode_Word_Break_Other
;
659 /* We've already recorded the non-ignorable code points before the proposed
661 before
= utf32__iterator_word_break(it
, it
->last
[1]);
662 twobefore
= utf32__iterator_word_break(it
, it
->last
[0]);
665 if(before
== unicode_Word_Break_ALetter
666 && after
== unicode_Word_Break_ALetter
)
669 if(before
== unicode_Word_Break_ALetter
670 && after
== unicode_Word_Break_MidLetter
671 && twoafter
== unicode_Word_Break_ALetter
)
674 if(twobefore
== unicode_Word_Break_ALetter
675 && before
== unicode_Word_Break_MidLetter
676 && after
== unicode_Word_Break_ALetter
)
679 if(before
== unicode_Word_Break_Numeric
680 && after
== unicode_Word_Break_Numeric
)
683 if(before
== unicode_Word_Break_ALetter
684 && after
== unicode_Word_Break_Numeric
)
687 if(before
== unicode_Word_Break_Numeric
688 && after
== unicode_Word_Break_ALetter
)
691 if(twobefore
== unicode_Word_Break_Numeric
692 && before
== unicode_Word_Break_MidNum
693 && after
== unicode_Word_Break_Numeric
)
696 if(before
== unicode_Word_Break_Numeric
697 && after
== unicode_Word_Break_MidNum
698 && twoafter
== unicode_Word_Break_Numeric
)
701 if(before
== unicode_Word_Break_Katakana
702 && after
== unicode_Word_Break_Katakana
)
705 if((before
== unicode_Word_Break_ALetter
706 || before
== unicode_Word_Break_Numeric
707 || before
== unicode_Word_Break_Katakana
708 || before
== unicode_Word_Break_ExtendNumLet
)
709 && after
== unicode_Word_Break_ExtendNumLet
)
712 if(before
== unicode_Word_Break_ExtendNumLet
713 && (after
== unicode_Word_Break_ALetter
714 || after
== unicode_Word_Break_Numeric
715 || after
== unicode_Word_Break_Katakana
))
722 /** @defgroup utf32 Functions that operate on UTF-32 strings */
725 /** @brief Return the length of a 0-terminated UTF-32 string
726 * @param s Pointer to 0-terminated string
727 * @return Length of string in code points (excluding terminator)
729 * Unlike the conversion functions no validity checking is done on the string.
731 size_t utf32_len(const uint32_t *s
) {
732 const uint32_t *t
= s
;
736 return (size_t)(t
- s
);
739 /** @brief Stably sort [s,s+ns) into descending order of combining class
740 * @param s Start of array
741 * @param ns Number of elements, must be at least 1
742 * @param buffer Buffer of at least @p ns elements
744 static void utf32__sort_ccc(uint32_t *s
, size_t ns
, uint32_t *buffer
) {
745 uint32_t *a
, *b
, *bp
;
749 case 1: /* 1-element array is always sorted */
751 case 2: /* 2-element arrays are trivial to sort */
752 if(utf32__combining_class(s
[0]) > utf32__combining_class(s
[1])) {
759 /* Partition the array */
764 /* Sort the two halves of the array */
765 utf32__sort_ccc(a
, na
, buffer
);
766 utf32__sort_ccc(b
, nb
, buffer
);
767 /* Merge them back into one, via the buffer */
769 while(na
> 0 && nb
> 0) {
770 /* We want ascending order of combining class (hence <)
771 * and we want stability within combining classes (hence <=)
773 if(utf32__combining_class(*a
) <= utf32__combining_class(*b
)) {
789 memcpy(s
, buffer
, ns
* sizeof(uint32_t));
794 /** @brief Put combining characters into canonical order
795 * @param s Pointer to UTF-32 string
796 * @param ns Length of @p s
797 * @return 0 on success, non-0 on error
799 * @p s is modified in-place. See Unicode 5.0 s3.11 for details of the
802 * Currently we only support a maximum of 1024 combining characters after each
803 * base character. If this limit is exceeded then a non-0 value is returned.
805 static int utf32__canonical_ordering(uint32_t *s
, size_t ns
) {
807 uint32_t buffer
[1024];
809 /* The ordering amounts to a stable sort of each contiguous group of
810 * characters with non-0 combining class. */
812 /* Skip non-combining characters */
813 if(utf32__combining_class(*s
) == 0) {
818 /* We must now have at least one combining character; see how many
820 for(nc
= 1; nc
< ns
&& utf32__combining_class(s
[nc
]) != 0; ++nc
)
825 utf32__sort_ccc(s
, nc
, buffer
);
832 /* Magic numbers from UAX #15 s16 */
840 #define NCount (VCount * TCount)
841 #define SCount (LCount * NCount)
843 /** @brief Guts of the decomposition lookup functions */
844 #define utf32__decompose_one_generic(WHICH) do { \
845 const uint32_t *dc = utf32__decomposition_##WHICH(c); \
847 /* Found a canonical decomposition in the table */ \
849 utf32__decompose_one_##WHICH(d, *dc++); \
850 } else if(c >= SBase && c < SBase + SCount) { \
851 /* Mechanically decomposable Hangul syllable (UAX #15 s16) */ \
852 const uint32_t SIndex = c - SBase; \
853 const uint32_t L = LBase + SIndex / NCount; \
854 const uint32_t V = VBase + (SIndex % NCount) / TCount; \
855 const uint32_t T = TBase + SIndex % TCount; \
856 dynstr_ucs4_append(d, L); \
857 dynstr_ucs4_append(d, V); \
859 dynstr_ucs4_append(d, T); \
861 /* Equal to own canonical decomposition */ \
862 dynstr_ucs4_append(d, c); \
865 /** @brief Recursively compute the canonical decomposition of @p c
866 * @param d Dynamic string to store decomposition in
867 * @param c Code point to decompose (must be a valid!)
868 * @return 0 on success, non-0 on error
870 static void utf32__decompose_one_canon(struct dynstr_ucs4
*d
, uint32_t c
) {
871 utf32__decompose_one_generic(canon
);
874 /** @brief Recursively compute the compatibility decomposition of @p c
875 * @param d Dynamic string to store decomposition in
876 * @param c Code point to decompose (must be a valid!)
877 * @return 0 on success, non-0 on error
879 static void utf32__decompose_one_compat(struct dynstr_ucs4
*d
, uint32_t c
) {
880 utf32__decompose_one_generic(compat
);
883 /** @brief Magic utf32__compositions() return value for Hangul Choseong */
884 static const uint32_t utf32__hangul_L
[1];
886 /** @brief Return the list of compositions that @p c starts
887 * @param c Starter code point
888 * @return Composition list or NULL
890 * For Hangul leading (Choseong) jamo we return the special value
891 * utf32__hangul_L. These code points are not listed as the targets of
892 * canonical decompositions (make-unidata checks) so there is no confusion with
893 * real decompositions here.
895 static const uint32_t *utf32__compositions(uint32_t c
) {
896 const uint32_t *compositions
= utf32__unidata(c
)->composed
;
900 /* Special-casing for Hangul */
901 switch(utf32__grapheme_break(c
)) {
904 case unicode_Grapheme_Break_L
:
905 return utf32__hangul_L
;
909 /** @brief Composition step
910 * @param s Start of string
911 * @param ns Length of string
912 * @return New length of string
914 * This is called from utf32__decompose_generic() to compose the result string
917 static size_t utf32__compose(uint32_t *s
, size_t ns
) {
918 const uint32_t *compositions
;
919 uint32_t *start
= s
, *t
= s
, *tt
, cc
;
922 uint32_t starter
= *s
++;
923 int block_starters
= 0;
925 /* We don't attempt to compose the following things:
926 * - final characters whatever kind they are
927 * - non-starter characters
928 * - starters that don't take part in a canonical decomposition mapping
931 || utf32__combining_class(starter
)
932 || !(compositions
= utf32__compositions(starter
))) {
936 if(compositions
!= utf32__hangul_L
) {
937 /* Where we'll put the eventual starter */
940 /* See if we can find composition of starter+*s */
941 const uint32_t cchar
= *s
, *cp
= compositions
;
942 while((cc
= *cp
++)) {
943 const uint32_t *decomp
= utf32__decomposition_canon(cc
);
944 /* We know decomp[0] == starter */
945 if(decomp
[1] == cchar
)
949 /* Found a composition: cc decomposes to starter,*s */
951 compositions
= utf32__compositions(starter
);
955 /* No composition found. */
956 const int class = utf32__combining_class(*s
);
958 /* Transfer the uncomposable combining character to the output */
961 /* All the combining characters of the same class of the
962 * uncomposable character are blocked by it, but there may be
963 * others of higher class later. We eat the uncomposable and
964 * blocked characters and go back round the loop for that higher
966 while(ns
> 0 && utf32__combining_class(*s
) == class) {
970 /* Block any subsequent starters */
973 /* The uncombinable character is itself a starter, so we don't
974 * transfer it to the output but instead go back round the main
979 /* Keep going while there are still characters and the starter takes
980 * part in some composition */
981 } while(ns
> 0 && compositions
982 && (!block_starters
|| utf32__combining_class(*s
)));
983 /* Store any remaining combining characters */
984 while(ns
> 0 && utf32__combining_class(*s
)) {
988 /* Store the resulting starter */
991 /* Special-casing for Hangul
993 * If there are combining characters between the L and the V then they
994 * will block the V and so no composition happens. Similarly combining
995 * characters between V and T will block the T and so we only get as far
998 if(utf32__grapheme_break(*s
) == unicode_Grapheme_Break_V
) {
999 const uint32_t V
= *s
++;
1000 const uint32_t LIndex
= starter
- LBase
;
1001 const uint32_t VIndex
= V
- VBase
;
1005 && utf32__grapheme_break(*s
) == unicode_Grapheme_Break_T
) {
1006 /* We have an L V T sequence */
1007 const uint32_t T
= *s
++;
1013 /* Compose to LVT or LV as appropriate */
1014 starter
= (LIndex
* VCount
+ VIndex
) * TCount
+ TIndex
+ SBase
;
1015 } /* else we only have L or LV and no V or T */
1017 /* There could be some combining characters that belong to the V or T.
1018 * These will be treated as non-starter characters at the top of the loop
1019 * and thuss transferred to the output. */
1025 /** @brief Guts of the composition and decomposition functions
1026 * @param WHICH @c canon or @c compat to choose decomposition
1027 * @param COMPOSE @c 0 or @c 1 to compose
1029 #define utf32__decompose_generic(WHICH, COMPOSE) do { \
1030 struct dynstr_ucs4 d; \
1033 dynstr_ucs4_init(&d); \
1036 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \
1038 utf32__decompose_one_##WHICH(&d, c); \
1041 if(utf32__canonical_ordering(d.vec, d.nvec)) \
1044 d.nvec = utf32__compose(d.vec, d.nvec); \
1045 dynstr_ucs4_terminate(&d); \
1054 /** @brief Canonically decompose @p [s,s+ns)
1055 * @param s Pointer to string
1056 * @param ns Length of string
1057 * @param ndp Where to store length of result
1058 * @return Pointer to result string, or NULL on error
1060 * Computes NFD (Normalization Form D) of the string at @p s. This implies
1061 * performing all canonical decompositions and then normalizing the order of
1062 * combining characters.
1064 * Returns NULL if the string is not valid for either of the following reasons:
1065 * - it codes for a UTF-16 surrogate
1066 * - it codes for a value outside the unicode code space
1069 * - utf32_decompose_compat()
1070 * - utf32_compose_canon()
1072 uint32_t *utf32_decompose_canon(const uint32_t *s
, size_t ns
, size_t *ndp
) {
1073 utf32__decompose_generic(canon
, 0);
1076 /** @brief Compatibility decompose @p [s,s+ns)
1077 * @param s Pointer to string
1078 * @param ns Length of string
1079 * @param ndp Where to store length of result
1080 * @return Pointer to result string, or NULL on error
1082 * Computes NFKD (Normalization Form KD) of the string at @p s. This implies
1083 * performing all canonical and compatibility decompositions and then
1084 * normalizing the order of combining characters.
1086 * Returns NULL if the string is not valid for either of the following reasons:
1087 * - it codes for a UTF-16 surrogate
1088 * - it codes for a value outside the unicode code space
1091 * - utf32_decompose_canon()
1092 * - utf32_compose_compat()
1094 uint32_t *utf32_decompose_compat(const uint32_t *s
, size_t ns
, size_t *ndp
) {
1095 utf32__decompose_generic(compat
, 0);
1098 /** @brief Canonically compose @p [s,s+ns)
1099 * @param s Pointer to string
1100 * @param ns Length of string
1101 * @param ndp Where to store length of result
1102 * @return Pointer to result string, or NULL on error
1104 * Computes NFC (Normalization Form C) of the string at @p s. This implies
1105 * performing all canonical decompositions, normalizing the order of combining
1106 * characters and then composing all unblocked primary compositables.
1108 * Returns NULL if the string is not valid for either of the following reasons:
1109 * - it codes for a UTF-16 surrogate
1110 * - it codes for a value outside the unicode code space
1113 * - utf32_compose_compat()
1114 * - utf32_decompose_canon()
1116 uint32_t *utf32_compose_canon(const uint32_t *s
, size_t ns
, size_t *ndp
) {
1117 utf32__decompose_generic(canon
, 1);
1120 /** @brief Compatibility compose @p [s,s+ns)
1121 * @param s Pointer to string
1122 * @param ns Length of string
1123 * @param ndp Where to store length of result
1124 * @return Pointer to result string, or NULL on error
1126 * Computes NFKC (Normalization Form KC) of the string at @p s. This implies
1127 * performing all canonical and compatibility decompositions, normalizing the
1128 * order of combining characters and then composing all unblocked primary
1131 * Returns NULL if the string is not valid for either of the following reasons:
1132 * - it codes for a UTF-16 surrogate
1133 * - it codes for a value outside the unicode code space
1136 * - utf32_compose_canon()
1137 * - utf32_decompose_compat()
1139 uint32_t *utf32_compose_compat(const uint32_t *s
, size_t ns
, size_t *ndp
) {
1140 utf32__decompose_generic(compat
, 1);
1143 /** @brief Single-character case-fold and decompose operation */
1144 #define utf32__casefold_one(WHICH) do { \
1145 const uint32_t *cf = utf32__unidata(c)->casefold; \
1147 /* Found a case-fold mapping in the table */ \
1149 utf32__decompose_one_##WHICH(&d, *cf++); \
1151 utf32__decompose_one_##WHICH(&d, c); \
1154 /** @brief Case-fold @p [s,s+ns)
1155 * @param s Pointer to string
1156 * @param ns Length of string
1157 * @param ndp Where to store length of result
1158 * @return Pointer to result string, or NULL on error
1160 * Case-fold the string at @p s according to full default case-folding rules
1161 * (s3.13) for caseless matching. The result will be in NFD.
1163 * Returns NULL if the string is not valid for either of the following reasons:
1164 * - it codes for a UTF-16 surrogate
1165 * - it codes for a value outside the unicode code space
1167 uint32_t *utf32_casefold_canon(const uint32_t *s
, size_t ns
, size_t *ndp
) {
1168 struct dynstr_ucs4 d
;
1173 /* If the canonical decomposition of the string includes any combining
1174 * character that case-folds to a non-combining character then we must
1175 * normalize before we fold. In Unicode 5.0.0 this means 0345 COMBINING
1176 * GREEK YPOGEGRAMMENI in its decomposition and the various characters that
1177 * canonically decompose to it. */
1178 for(n
= 0; n
< ns
; ++n
)
1179 if(utf32__unidata(s
[n
])->flags
& unicode_normalize_before_casefold
)
1182 /* We need a preliminary decomposition */
1183 if(!(ss
= utf32_decompose_canon(s
, ns
, &ns
)))
1187 dynstr_ucs4_init(&d
);
1190 if((c
>= 0xD800 && c
<= 0xDFFF) || c
> 0x10FFFF)
1192 utf32__casefold_one(canon
);
1195 if(utf32__canonical_ordering(d
.vec
, d
.nvec
))
1197 dynstr_ucs4_terminate(&d
);
1207 /** @brief Compatibility case-fold @p [s,s+ns)
1208 * @param s Pointer to string
1209 * @param ns Length of string
1210 * @param ndp Where to store length of result
1211 * @return Pointer to result string, or NULL on error
1213 * Case-fold the string at @p s according to full default case-folding rules
1214 * (s3.13) for compatibility caseless matching. The result will be in NFKD.
1216 * Returns NULL if the string is not valid for either of the following reasons:
1217 * - it codes for a UTF-16 surrogate
1218 * - it codes for a value outside the unicode code space
1220 uint32_t *utf32_casefold_compat(const uint32_t *s
, size_t ns
, size_t *ndp
) {
1221 struct dynstr_ucs4 d
;
1226 for(n
= 0; n
< ns
; ++n
)
1227 if(utf32__unidata(s
[n
])->flags
& unicode_normalize_before_casefold
)
1230 /* We need a preliminary _canonical_ decomposition */
1231 if(!(ss
= utf32_decompose_canon(s
, ns
, &ns
)))
1235 /* This computes NFKD(toCaseFold(s)) */
1236 #define compat_casefold_middle() do { \
1237 dynstr_ucs4_init(&d); \
1240 if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF) \
1242 utf32__casefold_one(compat); \
1245 if(utf32__canonical_ordering(d.vec, d.nvec)) \
1248 /* Do the inner (NFKD o toCaseFold) */
1249 compat_casefold_middle();
1250 /* We can do away with the NFD'd copy of the input now */
1254 /* Do the outer (NFKD o toCaseFold) */
1255 compat_casefold_middle();
1257 dynstr_ucs4_terminate(&d
);
1267 /** @brief Order a pair of UTF-32 strings
1268 * @param a First 0-terminated string
1269 * @param b Second 0-terminated string
1270 * @return -1, 0 or 1 for a less than, equal to or greater than b
1272 * "Comparable to strcmp() at its best."
1274 int utf32_cmp(const uint32_t *a
, const uint32_t *b
) {
1275 while(*a
&& *b
&& *a
== *b
) {
1279 return *a
< *b ?
-1 : (*a
> *b ?
1 : 0);
1282 /** @brief Identify a grapheme cluster boundary
1283 * @param s Start of string (must be NFD)
1284 * @param ns Length of string
1285 * @param n Index within string (in [0,ns].)
1286 * @return 1 at a grapheme cluster boundary, 0 otherwise
1288 * This function identifies default grapheme cluster boundaries as described in
1289 * UAX #29 s3. It returns non-0 if @p n points at the code point just after a
1290 * grapheme cluster boundary (including the hypothetical code point just after
1291 * the end of the string).
1293 * This function uses utf32_iterator_set() internally; see that function for
1294 * remarks on performance.
1296 int utf32_is_grapheme_boundary(const uint32_t *s
, size_t ns
, size_t n
) {
1297 struct utf32_iterator_data it
[1];
1299 utf32__iterator_init(it
, s
, ns
, n
);
1300 return utf32_iterator_grapheme_boundary(it
);
1303 /** @brief Identify a word boundary
1304 * @param s Start of string (must be NFD)
1305 * @param ns Length of string
1306 * @param n Index within string (in [0,ns].)
1307 * @return 1 at a word boundary, 0 otherwise
1309 * This function identifies default word boundaries as described in UAX #29 s4.
1310 * It returns non-0 if @p n points at the code point just after a word boundary
1311 * (including the hypothetical code point just after the end of the string).
1313 * This function uses utf32_iterator_set() internally; see that function for
1314 * remarks on performance.
1316 int utf32_is_word_boundary(const uint32_t *s
, size_t ns
, size_t n
) {
1317 struct utf32_iterator_data it
[1];
1319 utf32__iterator_init(it
, s
, ns
, n
);
1320 return utf32_iterator_word_boundary(it
);
1323 /** @brief Split [s,ns) into multiple words
1324 * @param s Pointer to start of string
1325 * @param ns Length of string
1326 * @param nwp Where to store word count, or NULL
1327 * @param wbreak Word_Break property tailor, or NULL
1328 * @return Pointer to array of pointers to words
1330 * The returned array is terminated by a NULL pointer and individual
1331 * strings are 0-terminated.
1333 uint32_t **utf32_word_split(const uint32_t *s
, size_t ns
, size_t *nwp
,
1334 unicode_property_tailor
*wbreak
) {
1335 struct utf32_iterator_data it
[1];
1336 size_t b1
= 0, b2
= 0 ,i
;
1338 struct vector32 v32
[1];
1342 utf32__iterator_init(it
, s
, ns
, 0);
1343 it
->word_break
= wbreak
;
1344 /* Work our way through the string stopping at each word break. */
1346 if(utf32_iterator_word_boundary(it
)) {
1347 /* We've found a new boundary */
1350 /*fprintf(stderr, "[%zu, %zu) is a candidate word\n", b1, b2);*/
1351 /* Inspect the characters between the boundary and form an opinion as to
1352 * whether they are a word or not */
1354 for(i
= b1
; i
< b2
; ++i
) {
1355 switch(utf32__iterator_word_break(it
, it
->s
[i
])) {
1356 case unicode_Word_Break_ALetter
:
1357 case unicode_Word_Break_Numeric
:
1358 case unicode_Word_Break_Katakana
:
1365 /* If it's a word add it to the list of results */
1367 w
= xcalloc(b2
- b1
+ 1, sizeof(uint32_t));
1368 memcpy(w
, it
->s
+ b1
, (b2
- b1
) * sizeof (uint32_t));
1369 vector32_append(v32
, w
);
1372 } while(!utf32_iterator_advance(it
, 1));
1373 vector32_terminate(v32
);
1380 /** @defgroup utf8 Functions that operate on UTF-8 strings */
1383 /** @brief Wrapper to transform a UTF-8 string using the UTF-32 function */
1384 #define utf8__transform(FN) do { \
1385 uint32_t *to32 = 0, *decomp32 = 0; \
1386 size_t nto32, ndecomp32; \
1387 char *decomp8 = 0; \
1389 if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error; \
1390 if(!(decomp32 = FN(to32, nto32, &ndecomp32))) goto error; \
1391 decomp8 = utf32_to_utf8(decomp32, ndecomp32, ndp); \
1398 /** @brief Canonically decompose @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 * Computes NFD (Normalization Form D) of the string at @p s. This implies
1405 * performing all canonical decompositions and then normalizing the order of
1406 * combining characters.
1408 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1412 * - utf32_decompose_canon().
1413 * - utf8_decompose_compat()
1414 * - utf8_compose_canon()
1416 char *utf8_decompose_canon(const char *s
, size_t ns
, size_t *ndp
) {
1417 utf8__transform(utf32_decompose_canon
);
1420 /** @brief Compatibility decompose @p [s,s+ns)
1421 * @param s Pointer to string
1422 * @param ns Length of string
1423 * @param ndp Where to store length of result
1424 * @return Pointer to result string, or NULL on error
1426 * Computes NFKD (Normalization Form KD) of the string at @p s. This implies
1427 * performing all canonical and compatibility decompositions and then
1428 * normalizing the order of combining characters.
1430 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1434 * - utf32_decompose_compat().
1435 * - utf8_decompose_canon()
1436 * - utf8_compose_compat()
1438 char *utf8_decompose_compat(const char *s
, size_t ns
, size_t *ndp
) {
1439 utf8__transform(utf32_decompose_compat
);
1442 /** @brief Canonically compose @p [s,s+ns)
1443 * @param s Pointer to string
1444 * @param ns Length of string
1445 * @param ndp Where to store length of result
1446 * @return Pointer to result string, or NULL on error
1448 * Computes NFC (Normalization Form C) of the string at @p s. This implies
1449 * performing all canonical decompositions, normalizing the order of combining
1450 * characters and then composing all unblocked primary compositables.
1452 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1456 * - utf32_compose_canon()
1457 * - utf8_compose_compat()
1458 * - utf8_decompose_canon()
1460 char *utf8_compose_canon(const char *s
, size_t ns
, size_t *ndp
) {
1461 utf8__transform(utf32_compose_canon
);
1464 /** @brief Compatibility compose @p [s,s+ns)
1465 * @param s Pointer to string
1466 * @param ns Length of string
1467 * @param ndp Where to store length of result
1468 * @return Pointer to result string, or NULL on error
1470 * Computes NFKC (Normalization Form KC) of the string at @p s. This implies
1471 * performing all canonical and compatibility decompositions, normalizing the
1472 * order of combining characters and then composing all unblocked primary
1475 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1479 * - utf32_compose_compat()
1480 * - utf8_compose_canon()
1481 * - utf8_decompose_compat()
1483 char *utf8_compose_compat(const char *s
, size_t ns
, size_t *ndp
) {
1484 utf8__transform(utf32_compose_compat
);
1487 /** @brief Case-fold @p [s,s+ns)
1488 * @param s Pointer to string
1489 * @param ns Length of string
1490 * @param ndp Where to store length of result
1491 * @return Pointer to result string, or NULL on error
1493 * Case-fold the string at @p s according to full default case-folding rules
1494 * (s3.13). The result will be in NFD.
1496 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1499 char *utf8_casefold_canon(const char *s
, size_t ns
, size_t *ndp
) {
1500 utf8__transform(utf32_casefold_canon
);
1503 /** @brief Compatibility 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 NFKD.
1512 * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1515 char *utf8_casefold_compat(const char *s
, size_t ns
, size_t *ndp
) {
1516 utf8__transform(utf32_casefold_compat
);
1519 /** @brief Split [s,ns) into multiple words
1520 * @param s Pointer to start of string
1521 * @param ns Length of string
1522 * @param nwp Where to store word count, or NULL
1523 * @param wbreak Word_Break property tailor, or NULL
1524 * @return Pointer to array of pointers to words
1526 * The returned array is terminated by a NULL pointer and individual
1527 * strings are 0-terminated.
1529 char **utf8_word_split(const char *s
, size_t ns
, size_t *nwp
,
1530 unicode_property_tailor
*wbreak
) {
1531 uint32_t *to32
= 0, **v32
= 0;
1532 size_t nto32
, nv
, n
;
1533 char **v8
= 0, **ret
= 0;
1535 if(!(to32
= utf8_to_utf32(s
, ns
, &nto32
))) goto error
;
1536 if(!(v32
= utf32_word_split(to32
, nto32
, &nv
, wbreak
))) goto error
;
1537 v8
= xcalloc(sizeof (char *), nv
+ 1);
1538 for(n
= 0; n
< nv
; ++n
)
1539 if(!(v8
[n
] = utf32_to_utf8(v32
[n
], utf32_len(v32
[n
]), 0)))
1543 v8
= 0; /* don't free */
1546 for(n
= 0; n
< nv
; ++n
)
1551 for(n
= 0; n
< nv
; ++n
)
1567 indent-tabs-mode:nil