chiark - git - mdw - disorder/blob - lib/unicode.c

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