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