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