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;
 226   const uint8_t *ss = (const uint8_t *)s;
 227   int n;
 228
 229   dynstr_ucs4_init(&d);
 230   while(ns > 0) {
 231     const struct unicode_utf8_row *const r = &unicode_utf8_valid[*ss];
 232     if(r->count <= ns) {
 233       switch(r->count) {
 234       case 1:
 235         c32 = *ss;
 236         break;
 237       case 2:
 238         if(ss[1] < r->min2 || ss[1] > r->max2)
 239           goto error;
 240         c32 = *ss & 0x1F;
 241         break;
 242       case 3:
 243         if(ss[1] < r->min2 || ss[1] > r->max2)
 244           goto error;
 245         c32 = *ss & 0x0F;
 246         break;
 247       case 4:
 248         if(ss[1] < r->min2 || ss[1] > r->max2)
 249           goto error;
 250         c32 = *ss & 0x07;
 251         break;
 252       default:
 253         goto error;
 254       }
 255     } else
 256       goto error;
 257     for(n = 1; n < r->count; ++n) {
 258       if(ss[n] < 0x80 || ss[n] > 0xBF)
 259         goto error;
 260       c32 = (c32 << 6) | (ss[n] & 0x3F);
 261     }
 262     dynstr_ucs4_append(&d, c32);
 263     ss += r->count;
 264     ns -= r->count;
 265   }
 266   dynstr_ucs4_terminate(&d);
 267   if(ndp)
 268     *ndp = d.nvec;
 269   return d.vec;
 270 error:
 271   xfree(d.vec);
 272   return 0;
 273 }
 274
 275 /** @brief Test whether [s,s+ns) is valid UTF-8
 276  * @param s Start of string
 277  * @param ns Length of string
 278  * @return non-0 if @p s is valid UTF-8, 0 if it is not valid
 279  *
 280  * This function is intended to be much faster than calling utf8_to_utf32() and
 281  * throwing away the result.
 282  */
 283 int utf8_valid(const char *s, size_t ns) {
 284   const uint8_t *ss = (const uint8_t *)s;
 285   while(ns > 0) {
 286     const struct unicode_utf8_row *const r = &unicode_utf8_valid[*ss];
 287     if(r->count <= ns) {
 288       switch(r->count) {
 289       case 1:
 290         break;
 291       case 2:
 292         if(ss[1] < r->min2 || ss[1] > r->max2)
 293           return 0;
 294         break;
 295       case 3:
 296         if(ss[1] < r->min2 || ss[1] > r->max2)
 297           return 0;
 298         if(ss[2] < 0x80 || ss[2] > 0xBF)
 299           return 0;
 300         break;
 301       case 4:
 302         if(ss[1] < r->min2 || ss[1] > r->max2)
 303           return 0;
 304         if(ss[2] < 0x80 || ss[2] > 0xBF)
 305           return 0;
 306         if(ss[3] < 0x80 || ss[3] > 0xBF)
 307           return 0;
 308         break;
 309       default:
 310         return 0;
 311       }
 312     } else
 313       return 0;
 314     ss += r->count;
 315     ns -= r->count;
 316   }
 317   return 1;
 318 }
 319
 320 /*@}*/
 321 /** @defgroup utf32iterator UTF-32 string iterators */
 322 /*@{*/
 323
 324 struct utf32_iterator_data {
 325   /** @brief Start of string */
 326   const uint32_t *s;
 327
 328   /** @brief Length of string */
 329   size_t ns;
 330
 331   /** @brief Current position */
 332   size_t n;
 333
 334   /** @brief Last two non-ignorable characters or (uint32_t)-1
 335    *
 336    * last[1] is the non-Extend/Format character just before position @p n;
 337    * last[0] is the one just before that.
 338    *
 339    * Exception 1: if there is no such non-Extend/Format character then an
 340    * Extend/Format character is accepted instead.
 341    *
 342    * Exception 2: if there is no such character even taking that into account
 343    * the value is (uint32_t)-1.
 344    */
 345   uint32_t last[2];
 346 };
 347
 348 /** @brief Create a new iterator pointing at the start of a string
 349  * @param s Start of string
 350  * @param ns Length of string
 351  * @return New iterator
 352  */
 353 utf32_iterator utf32_iterator_new(const uint32_t *s, size_t ns) {
 354   utf32_iterator it = xmalloc(sizeof *it);
 355   it->s = s;
 356   it->ns = ns;
 357   it->n = 0;
 358   it->last[0] = it->last[1] = -1;
 359   return it;
 360 }
 361
 362 /** @brief Initialize an internal private iterator
 363  * @param it Iterator
 364  * @param s Start of string
 365  * @param ns Length of string
 366  * @param n Absolute position
 367  */
 368 static void utf32__iterator_init(utf32_iterator it,
 369                                  const uint32_t *s, size_t ns, size_t n) {
 370   it->s = s;
 371   it->ns = ns;
 372   it->n = 0;
 373   it->last[0] = it->last[1] = -1;
 374   utf32_iterator_advance(it, n);
 375 }
 376
 377 /** @brief Destroy an iterator
 378  * @param it Iterator
 379  */
 380 void utf32_iterator_destroy(utf32_iterator it) {
 381   xfree(it);
 382 }
 383
 384 /** @brief Find the current position of an interator
 385  * @param it Iterator
 386  */
 387 size_t utf32_iterator_where(utf32_iterator it) {
 388   return it->n;
 389 }
 390
 391 /** @brief Set an iterator's absolute position
 392  * @param it Iterator
 393  * @param n Absolute position
 394  * @return 0 on success, non-0 on error
 395  *
 396  * It is an error to position the iterator outside the string (but acceptable
 397  * to point it at the hypothetical post-final character).  If an invalid value
 398  * of @p n is specified then the iterator is not changed.
 399  */
 400 int utf32_iterator_set(utf32_iterator it, size_t n) {
 401   /* TODO figure out how far we must back up to be able to re-synchronize; see
 402    * UAX #29 s6.4. */
 403   if(n > it->ns)
 404     return -1;
 405   if(n >= it->n)
 406     n -= it->n;
 407   else {
 408     it->n = 0;
 409     it->last[0] = it->last[1] = -1;
 410   }
 411   return utf32_iterator_advance(it, n);
 412 }
 413
 414 /** @brief Advance an iterator
 415  * @param it Iterator
 416  * @param count Number of code points to advance by
 417  * @return 0 on success, non-0 on error
 418  *
 419  * It is an error to advance an iterator beyond the hypothetical post-final
 420  * character of the string.  If an invalid value of @p n is specified then the
 421  * iterator is not changed.
 422  *
 423  * This function has O(n) time complexity: it works by advancing naively
 424  * forwards through the string.
 425  */
 426 int utf32_iterator_advance(utf32_iterator it, size_t count) {
 427   if(count <= it->ns - it->n) {
 428     while(count > 0) {
 429       const uint32_t c = it->s[it->n];
 430       const enum unicode_Word_Break wb = utf32__word_break(c);
 431       if(it->last[1] == (uint32_t)-1
 432          || !utf32__boundary_ignorable(wb)) {
 433         it->last[0] = it->last[1];
 434         it->last[1] = c;
 435       }
 436       ++it->n;
 437       --count;
 438     }
 439     return 0;
 440   } else
 441     return -1;
 442 }
 443
 444 /** @brief Find the current code point
 445  * @param it Iterator
 446  * @return Current code point or 0
 447  *
 448  * If the iterator points at the hypothetical post-final character of the
 449  * string then 0 is returned.  NB that this doesn't mean that there aren't any
 450  * 0 code points inside the string!
 451  */
 452 uint32_t utf32_iterator_code(utf32_iterator it) {
 453   if(it->n < it->ns)
 454     return it->s[it->n];
 455   else
 456     return 0;
 457 }
 458
 459 /** @brief Test for a grapheme boundary
 460  * @param it Iterator
 461  * @return Non-0 if pointing just after a grapheme boundary, otherwise 0
 462  */
 463 int utf32_iterator_grapheme_boundary(utf32_iterator it) {
 464   uint32_t before, after;
 465   enum unicode_Grapheme_Break gbbefore, gbafter;
 466   /* GB1 and GB2 */
 467   if(it->n == 0 || it->n == it->ns)
 468     return 1;
 469   /* Now we know that s[n-1] and s[n] are safe to inspect */
 470   /* GB3 */
 471   before = it->s[it->n-1];
 472   after = it->s[it->n];
 473   if(before == 0x000D && after == 0x000A)
 474     return 0;
 475   gbbefore = utf32__grapheme_break(before);
 476   gbafter = utf32__grapheme_break(after);
 477   /* GB4 */
 478   if(gbbefore == unicode_Grapheme_Break_Control
 479      || before == 0x000D
 480      || before == 0x000A)
 481     return 1;
 482   /* GB5 */
 483   if(gbafter == unicode_Grapheme_Break_Control
 484      || after == 0x000D
 485      || after == 0x000A)
 486     return 1;
 487   /* GB6 */
 488   if(gbbefore == unicode_Grapheme_Break_L
 489      && (gbafter == unicode_Grapheme_Break_L
 490          || gbafter == unicode_Grapheme_Break_V
 491          || gbafter == unicode_Grapheme_Break_LV
 492          || gbafter == unicode_Grapheme_Break_LVT))
 493     return 0;
 494   /* GB7 */
 495   if((gbbefore == unicode_Grapheme_Break_LV
 496       || gbbefore == unicode_Grapheme_Break_V)
 497      && (gbafter == unicode_Grapheme_Break_V
 498          || gbafter == unicode_Grapheme_Break_T))
 499     return 0;
 500   /* GB8 */
 501   if((gbbefore == unicode_Grapheme_Break_LVT
 502       || gbbefore == unicode_Grapheme_Break_T)
 503      && gbafter == unicode_Grapheme_Break_T)
 504     return 0;
 505   /* GB9 */
 506   if(gbafter == unicode_Grapheme_Break_Extend)
 507     return 0;
 508   /* GB10 */
 509   return 1;
 510
 511 }
 512
 513 /** @brief Test for a word boundary
 514  * @param it Iterator
 515  * @return Non-0 if pointing just after a word boundary, otherwise 0
 516  */
 517 int utf32_iterator_word_boundary(utf32_iterator it) {
 518   enum unicode_Word_Break twobefore, before, after, twoafter;
 519   size_t nn;
 520
 521   /* WB1 and WB2 */
 522   if(it->n == 0 || it->n == it->ns)
 523     return 1;
 524   /* WB3 */
 525   if(it->s[it->n-1] == 0x000D && it->s[it->n] == 0x000A)
 526     return 0;
 527   /* WB4 */
 528   /* (!Sep) x (Extend|Format) as in UAX #29 s6.2 */
 529   if(utf32__sentence_break(it->s[it->n-1]) != unicode_Sentence_Break_Sep
 530      && utf32__boundary_ignorable(utf32__word_break(it->s[it->n])))
 531     return 0;
 532   /* Gather the property values we'll need for the rest of the test taking the
 533    * s6.2 changes into account */
 534   /* First we look at the code points after the proposed boundary */
 535   nn = it->n;                           /* <it->ns */
 536   after = utf32__word_break(it->s[nn++]);
 537   if(!utf32__boundary_ignorable(after)) {
 538     /* X (Extend|Format)* -> X */
 539     while(nn < it->ns
 540           && utf32__boundary_ignorable(utf32__word_break(it->s[nn])))
 541       ++nn;
 542   }
 543   /* It's possible now that nn=ns */
 544   if(nn < it->ns)
 545     twoafter = utf32__word_break(it->s[nn]);
 546   else
 547     twoafter = unicode_Word_Break_Other;
 548
 549   /* We've already recorded the non-ignorable code points before the proposed
 550    * boundary */
 551   before = utf32__word_break(it->last[1]);
 552   twobefore = utf32__word_break(it->last[0]);
 553
 554   /* WB5 */
 555   if(before == unicode_Word_Break_ALetter
 556      && after == unicode_Word_Break_ALetter)
 557     return 0;
 558   /* WB6 */
 559   if(before == unicode_Word_Break_ALetter
 560      && after == unicode_Word_Break_MidLetter
 561      && twoafter == unicode_Word_Break_ALetter)
 562     return 0;
 563   /* WB7 */
 564   if(twobefore == unicode_Word_Break_ALetter
 565      && before == unicode_Word_Break_MidLetter
 566      && after == unicode_Word_Break_ALetter)
 567     return 0;
 568   /* WB8 */
 569   if(before == unicode_Word_Break_Numeric
 570      && after == unicode_Word_Break_Numeric)
 571     return 0;
 572   /* WB9 */
 573   if(before == unicode_Word_Break_ALetter
 574      && after == unicode_Word_Break_Numeric)
 575     return 0;
 576   /* WB10 */
 577   if(before == unicode_Word_Break_Numeric
 578      && after == unicode_Word_Break_ALetter)
 579     return 0;
 580    /* WB11 */
 581   if(twobefore == unicode_Word_Break_Numeric
 582      && before == unicode_Word_Break_MidNum
 583      && after == unicode_Word_Break_Numeric)
 584     return 0;
 585   /* WB12 */
 586   if(before == unicode_Word_Break_Numeric
 587      && after == unicode_Word_Break_MidNum
 588      && twoafter == unicode_Word_Break_Numeric)
 589     return 0;
 590   /* WB13 */
 591   if(before == unicode_Word_Break_Katakana
 592      && after == unicode_Word_Break_Katakana)
 593     return 0;
 594   /* WB13a */
 595   if((before == unicode_Word_Break_ALetter
 596       || before == unicode_Word_Break_Numeric
 597       || before == unicode_Word_Break_Katakana
 598       || before == unicode_Word_Break_ExtendNumLet)
 599      && after == unicode_Word_Break_ExtendNumLet)
 600     return 0;
 601   /* WB13b */
 602   if(before == unicode_Word_Break_ExtendNumLet
 603      && (after == unicode_Word_Break_ALetter
 604          || after == unicode_Word_Break_Numeric
 605          || after == unicode_Word_Break_Katakana))
 606     return 0;
 607   /* WB14 */
 608   return 1;
 609 }
 610
 611 /*@}*/
 612 /** @defgroup utf32 Functions that operate on UTF-32 strings */
 613 /*@{*/
 614
 615 /** @brief Return the length of a 0-terminated UTF-32 string
 616  * @param s Pointer to 0-terminated string
 617  * @return Length of string in code points (excluding terminator)
 618  *
 619  * Unlike the conversion functions no validity checking is done on the string.
 620  */
 621 size_t utf32_len(const uint32_t *s) {
 622   const uint32_t *t = s;
 623
 624   while(*t)
 625     ++t;
 626   return (size_t)(t - s);
 627 }
 628
 629 /** @brief Stably sort [s,s+ns) into descending order of combining class
 630  * @param s Start of array
 631  * @param ns Number of elements, must be at least 1
 632  * @param buffer Buffer of at least @p ns elements
 633  */
 634 static void utf32__sort_ccc(uint32_t *s, size_t ns, uint32_t *buffer) {
 635   uint32_t *a, *b, *bp;
 636   size_t na, nb;
 637
 638   switch(ns) {
 639   case 1:                       /* 1-element array is always sorted */
 640     return;
 641   case 2:                       /* 2-element arrays are trivial to sort */
 642     if(utf32__combining_class(s[0]) > utf32__combining_class(s[1])) {
 643       uint32_t tmp = s[0];
 644       s[0] = s[1];
 645       s[1] = tmp;
 646     }
 647     return;
 648   default:
 649     /* Partition the array */
 650     na = ns / 2;
 651     nb = ns - na;
 652     a = s;
 653     b = s + na;
 654     /* Sort the two halves of the array */
 655     utf32__sort_ccc(a, na, buffer);
 656     utf32__sort_ccc(b, nb, buffer);
 657     /* Merge them back into one, via the buffer */
 658     bp = buffer;
 659     while(na > 0 && nb > 0) {
 660       /* We want descending order of combining class (hence <)
 661        * and we want stability within combining classes (hence <=)
 662        */
 663       if(utf32__combining_class(*a) <= utf32__combining_class(*b)) {
 664         *bp++ = *a++;
 665         --na;
 666       } else {
 667         *bp++ = *b++;
 668         --nb;
 669       }
 670     }
 671     while(na > 0) {
 672       *bp++ = *a++;
 673       --na;
 674     }
 675     while(nb > 0) {
 676       *bp++ = *b++;
 677       --nb;
 678     }
 679     memcpy(s, buffer,  ns * sizeof(uint32_t));
 680     return;
 681   }
 682 }
 683
 684 /** @brief Put combining characters into canonical order
 685  * @param s Pointer to UTF-32 string
 686  * @param ns Length of @p s
 687  * @return 0 on success, -1 on error
 688  *
 689  * @p s is modified in-place.  See Unicode 5.0 s3.11 for details of the
 690  * ordering.
 691  *
 692  * Currently we only support a maximum of 1024 combining characters after each
 693  * base character.  If this limit is exceeded then -1 is returned.
 694  */
 695 static int utf32__canonical_ordering(uint32_t *s, size_t ns) {
 696   size_t nc;
 697   uint32_t buffer[1024];
 698
 699   /* The ordering amounts to a stable sort of each contiguous group of
 700    * characters with non-0 combining class. */
 701   while(ns > 0) {
 702     /* Skip non-combining characters */
 703     if(utf32__combining_class(*s) == 0) {
 704       ++s;
 705       --ns;
 706       continue;
 707     }
 708     /* We must now have at least one combining character; see how many
 709      * there are */
 710     for(nc = 1; nc < ns && utf32__combining_class(s[nc]) != 0; ++nc)
 711       ;
 712     if(nc > 1024)
 713       return -1;
 714     /* Sort the array */
 715     utf32__sort_ccc(s, nc, buffer);
 716     s += nc;
 717     ns -= nc;
 718   }
 719   return 0;
 720 }
 721
 722 /* Magic numbers from UAX #15 s16 */
 723 #define SBase 0xAC00
 724 #define LBase 0x1100
 725 #define VBase 0x1161
 726 #define TBase 0x11A7
 727 #define LCount 19
 728 #define VCount 21
 729 #define TCount 28
 730 #define NCount (VCount * TCount)
 731 #define SCount (LCount * NCount)
 732
 733 /** @brief Guts of the decomposition lookup functions */
 734 #define utf32__decompose_one_generic(WHICH) do {                        \
 735   const uint32_t *dc = utf32__unidata(c)->WHICH;                        \
 736   if(dc) {                                                              \
 737     /* Found a canonical decomposition in the table */                  \
 738     while(*dc)                                                          \
 739       utf32__decompose_one_##WHICH(d, *dc++);                           \
 740   } else if(c >= SBase && c < SBase + SCount) {                         \
 741     /* Mechanically decomposable Hangul syllable (UAX #15 s16) */       \
 742     const uint32_t SIndex = c - SBase;                                  \
 743     const uint32_t L = LBase + SIndex / NCount;                         \
 744     const uint32_t V = VBase + (SIndex % NCount) / TCount;              \
 745     const uint32_t T = TBase + SIndex % TCount;                         \
 746     dynstr_ucs4_append(d, L);                                           \
 747     dynstr_ucs4_append(d, V);                                           \
 748     if(T != TBase)                                                      \
 749       dynstr_ucs4_append(d, T);                                         \
 750   } else                                                                \
 751     /* Equal to own canonical decomposition */                          \
 752     dynstr_ucs4_append(d, c);                                           \
 753 } while(0)
 754
 755 /** @brief Recursively compute the canonical decomposition of @p c
 756  * @param d Dynamic string to store decomposition in
 757  * @param c Code point to decompose (must be a valid!)
 758  * @return 0 on success, -1 on error
 759  */
 760 static void utf32__decompose_one_canon(struct dynstr_ucs4 *d, uint32_t c) {
 761   utf32__decompose_one_generic(canon);
 762 }
 763
 764 /** @brief Recursively compute the compatibility decomposition of @p c
 765  * @param d Dynamic string to store decomposition in
 766  * @param c Code point to decompose (must be a valid!)
 767  * @return 0 on success, -1 on error
 768  */
 769 static void utf32__decompose_one_compat(struct dynstr_ucs4 *d, uint32_t c) {
 770   utf32__decompose_one_generic(compat);
 771 }
 772
 773 /** @brief Guts of the decomposition functions */
 774 #define utf32__decompose_generic(WHICH) do {            \
 775   struct dynstr_ucs4 d;                                 \
 776   uint32_t c;                                           \
 777                                                         \
 778   dynstr_ucs4_init(&d);                                 \
 779   while(ns) {                                           \
 780     c = *s++;                                           \
 781     if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)    \
 782       goto error;                                       \
 783     utf32__decompose_one_##WHICH(&d, c);                \
 784     --ns;                                               \
 785   }                                                     \
 786   if(utf32__canonical_ordering(d.vec, d.nvec))          \
 787     goto error;                                         \
 788   dynstr_ucs4_terminate(&d);                            \
 789   if(ndp)                                               \
 790     *ndp = d.nvec;                                      \
 791   return d.vec;                                         \
 792 error:                                                  \
 793   xfree(d.vec);                                         \
 794   return 0;                                             \
 795 } while(0)
 796
 797 /** @brief Canonically decompose @p [s,s+ns)
 798  * @param s Pointer to string
 799  * @param ns Length of string
 800  * @param ndp Where to store length of result
 801  * @return Pointer to result string, or NULL
 802  *
 803  * Computes the canonical decomposition of a string and stably sorts combining
 804  * characters into canonical order.  The result is in Normalization Form D and
 805  * (at the time of writing!) passes the NFD tests defined in Unicode 5.0's
 806  * NormalizationTest.txt.
 807  *
 808  * Returns NULL if the string is not valid for either of the following reasons:
 809  * - it codes for a UTF-16 surrogate
 810  * - it codes for a value outside the unicode code space
 811  */
 812 uint32_t *utf32_decompose_canon(const uint32_t *s, size_t ns, size_t *ndp) {
 813   utf32__decompose_generic(canon);
 814 }
 815
 816 /** @brief Compatibility decompose @p [s,s+ns)
 817  * @param s Pointer to string
 818  * @param ns Length of string
 819  * @param ndp Where to store length of result
 820  * @return Pointer to result string, or NULL
 821  *
 822  * Computes the compatibility decomposition of a string and stably sorts
 823  * combining characters into canonical order.  The result is in Normalization
 824  * Form KD and (at the time of writing!) passes the NFKD tests defined in
 825  * Unicode 5.0's NormalizationTest.txt.
 826  *
 827  * Returns NULL if the string is not valid for either of the following reasons:
 828  * - it codes for a UTF-16 surrogate
 829  * - it codes for a value outside the unicode code space
 830  */
 831 uint32_t *utf32_decompose_compat(const uint32_t *s, size_t ns, size_t *ndp) {
 832   utf32__decompose_generic(compat);
 833 }
 834
 835 /** @brief Single-character case-fold and decompose operation */
 836 #define utf32__casefold_one(WHICH) do {                                 \
 837   const uint32_t *cf = utf32__unidata(c)->casefold;                     \
 838   if(cf) {                                                              \
 839     /* Found a case-fold mapping in the table */                        \
 840     while(*cf)                                                          \
 841       utf32__decompose_one_##WHICH(&d, *cf++);                          \
 842   } else                                                                \
 843     utf32__decompose_one_##WHICH(&d, c);                                \
 844 } while(0)
 845
 846 /** @brief Case-fold @p [s,s+ns)
 847  * @param s Pointer to string
 848  * @param ns Length of string
 849  * @param ndp Where to store length of result
 850  * @return Pointer to result string, or NULL
 851  *
 852  * Case-fold the string at @p s according to full default case-folding rules
 853  * (s3.13) for caseless matching.  The result will be in NFD.
 854  *
 855  * Returns NULL if the string is not valid for either of the following reasons:
 856  * - it codes for a UTF-16 surrogate
 857  * - it codes for a value outside the unicode code space
 858  */
 859 uint32_t *utf32_casefold_canon(const uint32_t *s, size_t ns, size_t *ndp) {
 860   struct dynstr_ucs4 d;
 861   uint32_t c;
 862   size_t n;
 863   uint32_t *ss = 0;
 864
 865   /* If the canonical decomposition of the string includes any combining
 866    * character that case-folds to a non-combining character then we must
 867    * normalize before we fold.  In Unicode 5.0.0 this means 0345 COMBINING
 868    * GREEK YPOGEGRAMMENI in its decomposition and the various characters that
 869    * canonically decompose to it. */
 870   for(n = 0; n < ns; ++n)
 871     if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
 872       break;
 873   if(n < ns) {
 874     /* We need a preliminary decomposition */
 875     if(!(ss = utf32_decompose_canon(s, ns, &ns)))
 876       return 0;
 877     s = ss;
 878   }
 879   dynstr_ucs4_init(&d);
 880   while(ns) {
 881     c = *s++;
 882     if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)
 883       goto error;
 884     utf32__casefold_one(canon);
 885     --ns;
 886   }
 887   if(utf32__canonical_ordering(d.vec, d.nvec))
 888     goto error;
 889   dynstr_ucs4_terminate(&d);
 890   if(ndp)
 891     *ndp = d.nvec;
 892   return d.vec;
 893 error:
 894   xfree(d.vec);
 895   xfree(ss);
 896   return 0;
 897 }
 898
 899 /** @brief Compatibilit case-fold @p [s,s+ns)
 900  * @param s Pointer to string
 901  * @param ns Length of string
 902  * @param ndp Where to store length of result
 903  * @return Pointer to result string, or NULL
 904  *
 905  * Case-fold the string at @p s according to full default case-folding rules
 906  * (s3.13) for compatibility caseless matching.  The result will be in NFKD.
 907  *
 908  * Returns NULL if the string is not valid for either of the following reasons:
 909  * - it codes for a UTF-16 surrogate
 910  * - it codes for a value outside the unicode code space
 911  */
 912 uint32_t *utf32_casefold_compat(const uint32_t *s, size_t ns, size_t *ndp) {
 913   struct dynstr_ucs4 d;
 914   uint32_t c;
 915   size_t n;
 916   uint32_t *ss = 0;
 917
 918   for(n = 0; n < ns; ++n)
 919     if(utf32__unidata(s[n])->flags & unicode_normalize_before_casefold)
 920       break;
 921   if(n < ns) {
 922     /* We need a preliminary _canonical_ decomposition */
 923     if(!(ss = utf32_decompose_canon(s, ns, &ns)))
 924       return 0;
 925     s = ss;
 926   }
 927   /* This computes NFKD(toCaseFold(s)) */
 928 #define compat_casefold_middle() do {                   \
 929   dynstr_ucs4_init(&d);                                 \
 930   while(ns) {                                           \
 931     c = *s++;                                           \
 932     if((c >= 0xD800 && c <= 0xDFFF) || c > 0x10FFFF)    \
 933       goto error;                                       \
 934     utf32__casefold_one(compat);                        \
 935     --ns;                                               \
 936   }                                                     \
 937   if(utf32__canonical_ordering(d.vec, d.nvec))          \
 938     goto error;                                         \
 939 } while(0)
 940   /* Do the inner (NFKD o toCaseFold) */
 941   compat_casefold_middle();
 942   /* We can do away with the NFD'd copy of the input now */
 943   xfree(ss);
 944   s = ss = d.vec;
 945   ns = d.nvec;
 946   /* Do the outer (NFKD o toCaseFold) */
 947   compat_casefold_middle();
 948   /* That's all */
 949   dynstr_ucs4_terminate(&d);
 950   if(ndp)
 951     *ndp = d.nvec;
 952   return d.vec;
 953 error:
 954   xfree(d.vec);
 955   xfree(ss);
 956   return 0;
 957 }
 958
 959 /** @brief Order a pair of UTF-32 strings
 960  * @param a First 0-terminated string
 961  * @param b Second 0-terminated string
 962  * @return -1, 0 or 1 for a less than, equal to or greater than b
 963  *
 964  * "Comparable to strcmp() at its best."
 965  */
 966 int utf32_cmp(const uint32_t *a, const uint32_t *b) {
 967   while(*a && *b && *a == *b) {
 968     ++a;
 969     ++b;
 970   }
 971   return *a < *b ? -1 : (*a > *b ? 1 : 0);
 972 }
 973
 974 /** @brief Identify a grapheme cluster boundary
 975  * @param s Start of string (must be NFD)
 976  * @param ns Length of string
 977  * @param n Index within string (in [0,ns].)
 978  * @return 1 at a grapheme cluster boundary, 0 otherwise
 979  *
 980  * This function identifies default grapheme cluster boundaries as described in
 981  * UAX #29 s3.  It returns 1 if @p n points at the code point just after a
 982  * grapheme cluster boundary (including the hypothetical code point just after
 983  * the end of the string).
 984  */
 985 int utf32_is_grapheme_boundary(const uint32_t *s, size_t ns, size_t n) {
 986   struct utf32_iterator_data it[1];
 987
 988   utf32__iterator_init(it, s, ns, n);
 989   return utf32_iterator_grapheme_boundary(it);
 990 }
 991
 992 /** @brief Identify a word boundary
 993  * @param s Start of string (must be NFD)
 994  * @param ns Length of string
 995  * @param n Index within string (in [0,ns].)
 996  * @return 1 at a word boundary, 0 otherwise
 997  *
 998  * This function identifies default word boundaries as described in UAX #29 s4.
 999  * It returns 1 if @p n points at the code point just after a word boundary
1000  * (including the hypothetical code point just after the end of the string).
1001  */
1002 int utf32_is_word_boundary(const uint32_t *s, size_t ns, size_t n) {
1003   struct utf32_iterator_data it[1];
1004
1005   utf32__iterator_init(it, s, ns, n);
1006   return utf32_iterator_word_boundary(it);
1007 }
1008
1009 /*@}*/
1010 /** @defgroup utf8 Functions that operate on UTF-8 strings */
1011 /*@{*/
1012
1013 /** @brief Wrapper to transform a UTF-8 string using the UTF-32 function */
1014 #define utf8__transform(FN) do {                                \
1015   uint32_t *to32 = 0, *decomp32 = 0;                            \
1016   size_t nto32, ndecomp32;                                      \
1017   char *decomp8 = 0;                                            \
1018                                                                 \
1019   if(!(to32 = utf8_to_utf32(s, ns, &nto32))) goto error;        \
1020   if(!(decomp32 = FN(to32, nto32, &ndecomp32))) goto error;     \
1021   decomp8 = utf32_to_utf8(decomp32, ndecomp32, ndp);            \
1022 error:                                                          \
1023   xfree(to32);                                                  \
1024   xfree(decomp32);                                              \
1025   return decomp8;                                               \
1026 } while(0)
1027
1028 /** @brief Canonically decompose @p [s,s+ns)
1029  * @param s Pointer to string
1030  * @param ns Length of string
1031  * @param ndp Where to store length of result
1032  * @return Pointer to result string, or NULL
1033  *
1034  * Computes the canonical decomposition of a string and stably sorts combining
1035  * characters into canonical order.  The result is in Normalization Form D and
1036  * (at the time of writing!) passes the NFD tests defined in Unicode 5.0's
1037  * NormalizationTest.txt.
1038  *
1039  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1040  * this might be.
1041  *
1042  * See also utf32_decompose_canon().
1043  */
1044 char *utf8_decompose_canon(const char *s, size_t ns, size_t *ndp) {
1045   utf8__transform(utf32_decompose_canon);
1046 }
1047
1048 /** @brief Compatibility decompose @p [s,s+ns)
1049  * @param s Pointer to string
1050  * @param ns Length of string
1051  * @param ndp Where to store length of result
1052  * @return Pointer to result string, or NULL
1053  *
1054  * Computes the compatibility decomposition of a string and stably sorts
1055  * combining characters into canonical order.  The result is in Normalization
1056  * Form KD and (at the time of writing!) passes the NFKD tests defined in
1057  * Unicode 5.0's NormalizationTest.txt.
1058  *
1059  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1060  * this might be.
1061  *
1062  * See also utf32_decompose_compat().
1063  */
1064 char *utf8_decompose_compat(const char *s, size_t ns, size_t *ndp) {
1065   utf8__transform(utf32_decompose_compat);
1066 }
1067
1068 /** @brief Case-fold @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
1073  *
1074  * Case-fold the string at @p s according to full default case-folding rules
1075  * (s3.13).  The result will be in NFD.
1076  *
1077  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1078  * this might be.
1079  */
1080 char *utf8_casefold_canon(const char *s, size_t ns, size_t *ndp) {
1081   utf8__transform(utf32_casefold_canon);
1082 }
1083
1084 /** @brief Compatibility case-fold @p [s,s+ns)
1085  * @param s Pointer to string
1086  * @param ns Length of string
1087  * @param ndp Where to store length of result
1088  * @return Pointer to result string, or NULL
1089  *
1090  * Case-fold the string at @p s according to full default case-folding rules
1091  * (s3.13).  The result will be in NFKD.
1092  *
1093  * Returns NULL if the string is not valid; see utf8_to_utf32() for reasons why
1094  * this might be.
1095  */
1096 char *utf8_casefold_compat(const char *s, size_t ns, size_t *ndp) {
1097   utf8__transform(utf32_casefold_compat);
1098 }
1099
1100 /*@}*/
1101
1102 /*
1103 Local Variables:
1104 c-basic-offset:2
1105 comment-column:40
1106 fill-column:79
1107 indent-tabs-mode:nil
1108 End:
1109 */