git.sur5r.net Git - openldap/blob - libraries/liblunicode/ucdata/ucgendat.c

   1 /* $OpenLDAP$ */
   2 /*
   3  * Copyright 2001 Computing Research Labs, New Mexico State University
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in
  13  * all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE COMPUTING RESEARCH LAB OR NEW MEXICO STATE UNIVERSITY BE LIABLE FOR ANY
  19  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
  20  * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
  21  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22  */
  23 /* $Id: ucgendat.c,v 1.4 2001/01/02 18:46:20 mleisher Exp $" */
  24
  25 #include "portable.h"
  26 #include "ldap_config.h"
  27
  28 #include <stdio.h>
  29 #include <ac/stdlib.h>
  30 #include <ac/string.h>
  31 #include <ac/unistd.h>
  32
  33 #undef ishdigit
  34 #define ishdigit(cc) (((cc) >= '0' && (cc) <= '9') ||\
  35                       ((cc) >= 'A' && (cc) <= 'F') ||\
  36                       ((cc) >= 'a' && (cc) <= 'f'))
  37
  38 /*
  39  * A header written to the output file with the byte-order-mark and the number
  40  * of property nodes.
  41  */
  42 static unsigned short hdr[2] = {0xfeff, 0};
  43
  44 #define NUMPROPS 50
  45 #define NEEDPROPS (NUMPROPS + (4 - (NUMPROPS & 3)))
  46
  47 typedef struct {
  48     char *name;
  49     int len;
  50 } _prop_t;
  51
  52 /*
  53  * List of properties expected to be found in the Unicode Character Database
  54  * including some implementation specific properties.
  55  *
  56  * The implementation specific properties are:
  57  * Cm = Composed (can be decomposed)
  58  * Nb = Non-breaking
  59  * Sy = Symmetric (has left and right forms)
  60  * Hd = Hex digit
  61  * Qm = Quote marks
  62  * Mr = Mirroring
  63  * Ss = Space, other
  64  * Cp = Defined character
  65  */
  66 static _prop_t props[NUMPROPS] = {
  67     {"Mn", 2}, {"Mc", 2}, {"Me", 2}, {"Nd", 2}, {"Nl", 2}, {"No", 2},
  68     {"Zs", 2}, {"Zl", 2}, {"Zp", 2}, {"Cc", 2}, {"Cf", 2}, {"Cs", 2},
  69     {"Co", 2}, {"Cn", 2}, {"Lu", 2}, {"Ll", 2}, {"Lt", 2}, {"Lm", 2},
  70     {"Lo", 2}, {"Pc", 2}, {"Pd", 2}, {"Ps", 2}, {"Pe", 2}, {"Po", 2},
  71     {"Sm", 2}, {"Sc", 2}, {"Sk", 2}, {"So", 2}, {"L",  1}, {"R",  1},
  72     {"EN", 2}, {"ES", 2}, {"ET", 2}, {"AN", 2}, {"CS", 2}, {"B",  1},
  73     {"S",  1}, {"WS", 2}, {"ON", 2},
  74     {"Cm", 2}, {"Nb", 2}, {"Sy", 2}, {"Hd", 2}, {"Qm", 2}, {"Mr", 2},
  75     {"Ss", 2}, {"Cp", 2}, {"Pi", 2}, {"Pf", 2}, {"AL", 2}
  76 };
  77
  78 typedef struct {
  79     unsigned long *ranges;
  80     unsigned short used;
  81     unsigned short size;
  82 } _ranges_t;
  83
  84 static _ranges_t proptbl[NUMPROPS];
  85
  86 /*
  87  * Make sure this array is sized to be on a 4-byte boundary at compile time.
  88  */
  89 static unsigned short propcnt[NEEDPROPS];
  90
  91 /*
  92  * Array used to collect a decomposition before adding it to the decomposition
  93  * table.
  94  */
  95 static unsigned long dectmp[64];
  96 static unsigned long dectmp_size;
  97
  98 typedef struct {
  99     unsigned long code;
 100     unsigned short size;
 101     unsigned short used;
 102     unsigned long *decomp;
 103 } _decomp_t;
 104
 105 /*
 106  * List of decomposition.  Created and expanded in order as the characters are
 107  * encountered.
 108  */
 109 static _decomp_t *decomps;
 110 static unsigned long decomps_used;
 111 static unsigned long decomps_size;
 112
 113 /*
 114  * Composition exclusion table stuff.
 115  */
 116 #define COMPEX_SET(c) (compexs[(c) >> 5] |= (1 << ((c) & 31)))
 117 #define COMPEX_TEST(c) (compexs[(c) >> 5] & (1 << ((c) & 31)))
 118 static unsigned long compexs[2048];
 119
 120 /*
 121  * Struct for holding a composition pair, and array of composition pairs
 122  */
 123 typedef struct {
 124     unsigned long comp;
 125     unsigned long count;
 126     unsigned long code1;
 127     unsigned long code2;
 128 } _comp_t;
 129
 130 static _comp_t *comps;
 131 static unsigned long comps_used;
 132
 133 /*
 134  * Types and lists for handling lists of case mappings.
 135  */
 136 typedef struct {
 137     unsigned long key;
 138     unsigned long other1;
 139     unsigned long other2;
 140 } _case_t;
 141
 142 static _case_t *upper;
 143 static _case_t *lower;
 144 static _case_t *title;
 145 static unsigned long upper_used;
 146 static unsigned long upper_size;
 147 static unsigned long lower_used;
 148 static unsigned long lower_size;
 149 static unsigned long title_used;
 150 static unsigned long title_size;
 151
 152 /*
 153  * Array used to collect case mappings before adding them to a list.
 154  */
 155 static unsigned long cases[3];
 156
 157 /*
 158  * An array to hold ranges for combining classes.
 159  */
 160 static unsigned long *ccl;
 161 static unsigned long ccl_used;
 162 static unsigned long ccl_size;
 163
 164 /*
 165  * Structures for handling numbers.
 166  */
 167 typedef struct {
 168     unsigned long code;
 169     unsigned long idx;
 170 } _codeidx_t;
 171
 172 typedef struct {
 173     short numerator;
 174     short denominator;
 175 } _num_t;
 176
 177 /*
 178  * Arrays to hold the mapping of codes to numbers.
 179  */
 180 static _codeidx_t *ncodes;
 181 static unsigned long ncodes_used;
 182 static unsigned long ncodes_size;
 183
 184 static _num_t *nums;
 185 static unsigned long nums_used;
 186 static unsigned long nums_size;
 187
 188 /*
 189  * Array for holding numbers.
 190  */
 191 static _num_t *nums;
 192 static unsigned long nums_used;
 193 static unsigned long nums_size;
 194
 195 static void
 196 add_range(unsigned long start, unsigned long end, char *p1, char *p2)
 197 {
 198     int i, j, k, len;
 199     _ranges_t *rlp;
 200     char *name;
 201
 202     for (k = 0; k < 2; k++) {
 203         if (k == 0) {
 204             name = p1;
 205             len = 2;
 206         } else {
 207             if (p2 == 0)
 208               break;
 209
 210             name = p2;
 211             len = 1;
 212         }
 213
 214         for (i = 0; i < NUMPROPS; i++) {
 215             if (props[i].len == len && memcmp(props[i].name, name, len) == 0)
 216               break;
 217         }
 218
 219         if (i == NUMPROPS)
 220           continue;
 221
 222         rlp = &proptbl[i];
 223
 224         /*
 225          * Resize the range list if necessary.
 226          */
 227         if (rlp->used == rlp->size) {
 228             if (rlp->size == 0)
 229               rlp->ranges = (unsigned long *)
 230                   malloc(sizeof(unsigned long) << 3);
 231             else
 232               rlp->ranges = (unsigned long *)
 233                   realloc((char *) rlp->ranges,
 234                           sizeof(unsigned long) * (rlp->size + 8));
 235             rlp->size += 8;
 236         }
 237
 238         /*
 239          * If this is the first code for this property list, just add it
 240          * and return.
 241          */
 242         if (rlp->used == 0) {
 243             rlp->ranges[0] = start;
 244             rlp->ranges[1] = end;
 245             rlp->used += 2;
 246             continue;
 247         }
 248
 249         /*
 250          * Optimize the case of adding the range to the end.
 251          */
 252         j = rlp->used - 1;
 253         if (start > rlp->ranges[j]) {
 254             j = rlp->used;
 255             rlp->ranges[j++] = start;
 256             rlp->ranges[j++] = end;
 257             rlp->used = j;
 258             continue;
 259         }
 260
 261         /*
 262          * Need to locate the insertion point.
 263          */
 264         for (i = 0;
 265              i < rlp->used && start > rlp->ranges[i + 1] + 1; i += 2) ;
 266
 267         /*
 268          * If the start value lies in the current range, then simply set the
 269          * new end point of the range to the end value passed as a parameter.
 270          */
 271         if (rlp->ranges[i] <= start && start <= rlp->ranges[i + 1] + 1) {
 272             rlp->ranges[i + 1] = end;
 273             return;
 274         }
 275
 276         /*
 277          * Shift following values up by two.
 278          */
 279         for (j = rlp->used; j > i; j -= 2) {
 280             rlp->ranges[j] = rlp->ranges[j - 2];
 281             rlp->ranges[j + 1] = rlp->ranges[j - 1];
 282         }
 283
 284         /*
 285          * Add the new range at the insertion point.
 286          */
 287         rlp->ranges[i] = start;
 288         rlp->ranges[i + 1] = end;
 289         rlp->used += 2;
 290     }
 291 }
 292
 293 static void
 294 ordered_range_insert(unsigned long c, char *name, int len)
 295 {
 296     int i, j;
 297     unsigned long s, e;
 298     _ranges_t *rlp;
 299
 300     if (len == 0)
 301       return;
 302
 303     /*
 304      * Deal with directionality codes introduced in Unicode 3.0.
 305      */
 306     if ((len == 2 && memcmp(name, "BN", 2) == 0) ||
 307         (len == 3 &&
 308          (memcmp(name, "NSM", 3) == 0 || memcmp(name, "PDF", 3) == 0 ||
 309           memcmp(name, "LRE", 3) == 0 || memcmp(name, "LRO", 3) == 0 ||
 310           memcmp(name, "RLE", 3) == 0 || memcmp(name, "RLO", 3) == 0))) {
 311         /*
 312          * Mark all of these as Other Neutral to preserve compatibility with
 313          * older versions.
 314          */
 315         len = 2;
 316         name = "ON";
 317     }
 318
 319     for (i = 0; i < NUMPROPS; i++) {
 320         if (props[i].len == len && memcmp(props[i].name, name, len) == 0)
 321           break;
 322     }
 323
 324     if (i == NUMPROPS)
 325       return;
 326
 327     /*
 328      * Have a match, so insert the code in order.
 329      */
 330     rlp = &proptbl[i];
 331
 332     /*
 333      * Resize the range list if necessary.
 334      */
 335     if (rlp->used == rlp->size) {
 336         if (rlp->size == 0)
 337           rlp->ranges = (unsigned long *)
 338               malloc(sizeof(unsigned long) << 3);
 339         else
 340           rlp->ranges = (unsigned long *)
 341               realloc((char *) rlp->ranges,
 342                       sizeof(unsigned long) * (rlp->size + 8));
 343         rlp->size += 8;
 344     }
 345
 346     /*
 347      * If this is the first code for this property list, just add it
 348      * and return.
 349      */
 350     if (rlp->used == 0) {
 351         rlp->ranges[0] = rlp->ranges[1] = c;
 352         rlp->used += 2;
 353         return;
 354     }
 355
 356     /*
 357      * Optimize the cases of extending the last range and adding new ranges to
 358      * the end.
 359      */
 360     j = rlp->used - 1;
 361     e = rlp->ranges[j];
 362     s = rlp->ranges[j - 1];
 363
 364     if (c == e + 1) {
 365         /*
 366          * Extend the last range.
 367          */
 368         rlp->ranges[j] = c;
 369         return;
 370     }
 371
 372     if (c > e + 1) {
 373         /*
 374          * Start another range on the end.
 375          */
 376         j = rlp->used;
 377         rlp->ranges[j] = rlp->ranges[j + 1] = c;
 378         rlp->used += 2;
 379         return;
 380     }
 381
 382     if (c >= s)
 383       /*
 384        * The code is a duplicate of a code in the last range, so just return.
 385        */
 386       return;
 387
 388     /*
 389      * The code should be inserted somewhere before the last range in the
 390      * list.  Locate the insertion point.
 391      */
 392     for (i = 0;
 393          i < rlp->used && c > rlp->ranges[i + 1] + 1; i += 2) ;
 394
 395     s = rlp->ranges[i];
 396     e = rlp->ranges[i + 1];
 397
 398     if (c == e + 1)
 399       /*
 400        * Simply extend the current range.
 401        */
 402       rlp->ranges[i + 1] = c;
 403     else if (c < s) {
 404         /*
 405          * Add a new entry before the current location.  Shift all entries
 406          * before the current one up by one to make room.
 407          */
 408         for (j = rlp->used; j > i; j -= 2) {
 409             rlp->ranges[j] = rlp->ranges[j - 2];
 410             rlp->ranges[j + 1] = rlp->ranges[j - 1];
 411         }
 412         rlp->ranges[i] = rlp->ranges[i + 1] = c;
 413
 414         rlp->used += 2;
 415     }
 416 }
 417
 418 static void
 419 add_decomp(unsigned long code)
 420 {
 421     unsigned long i, j, size;
 422
 423     /*
 424      * Add the code to the composite property.
 425      */
 426     ordered_range_insert(code, "Cm", 2);
 427
 428     /*
 429      * Locate the insertion point for the code.
 430      */
 431     for (i = 0; i < decomps_used && code > decomps[i].code; i++) ;
 432
 433     /*
 434      * Allocate space for a new decomposition.
 435      */
 436     if (decomps_used == decomps_size) {
 437         if (decomps_size == 0)
 438           decomps = (_decomp_t *) malloc(sizeof(_decomp_t) << 3);
 439         else
 440           decomps = (_decomp_t *)
 441               realloc((char *) decomps,
 442                       sizeof(_decomp_t) * (decomps_size + 8));
 443         (void) memset((char *) (decomps + decomps_size), '\0',
 444                       sizeof(_decomp_t) << 3);
 445         decomps_size += 8;
 446     }
 447
 448     if (i < decomps_used && code != decomps[i].code) {
 449         /*
 450          * Shift the decomps up by one if the codes don't match.
 451          */
 452         for (j = decomps_used; j > i; j--)
 453           (void) AC_MEMCPY((char *) &decomps[j], (char *) &decomps[j - 1],
 454                         sizeof(_decomp_t));
 455     }
 456
 457     /*
 458      * Insert or replace a decomposition.
 459      */
 460     size = dectmp_size + (4 - (dectmp_size & 3));
 461     if (decomps[i].size < size) {
 462         if (decomps[i].size == 0)
 463           decomps[i].decomp = (unsigned long *)
 464               malloc(sizeof(unsigned long) * size);
 465         else
 466           decomps[i].decomp = (unsigned long *)
 467               realloc((char *) decomps[i].decomp,
 468                       sizeof(unsigned long) * size);
 469         decomps[i].size = size;
 470     }
 471
 472     if (decomps[i].code != code)
 473       decomps_used++;
 474
 475     decomps[i].code = code;
 476     decomps[i].used = dectmp_size;
 477     (void) AC_MEMCPY((char *) decomps[i].decomp, (char *) dectmp,
 478                   sizeof(unsigned long) * dectmp_size);
 479
 480     /*
 481      * NOTICE: This needs changing later so it is more general than simply
 482      * pairs.  This calculation is done here to simplify allocation elsewhere.
 483      */
 484     if (dectmp_size == 2)
 485       comps_used++;
 486 }
 487
 488 static void
 489 add_title(unsigned long code)
 490 {
 491     unsigned long i, j;
 492
 493     /*
 494      * Always map the code to itself.
 495      */
 496     cases[2] = code;
 497
 498     if (title_used == title_size) {
 499         if (title_size == 0)
 500           title = (_case_t *) malloc(sizeof(_case_t) << 3);
 501         else
 502           title = (_case_t *) realloc((char *) title,
 503                                       sizeof(_case_t) * (title_size + 8));
 504         title_size += 8;
 505     }
 506
 507     /*
 508      * Locate the insertion point.
 509      */
 510     for (i = 0; i < title_used && code > title[i].key; i++) ;
 511
 512     if (i < title_used) {
 513         /*
 514          * Shift the array up by one.
 515          */
 516         for (j = title_used; j > i; j--)
 517           (void) AC_MEMCPY((char *) &title[j], (char *) &title[j - 1],
 518                         sizeof(_case_t));
 519     }
 520
 521     title[i].key = cases[2];    /* Title */
 522     title[i].other1 = cases[0]; /* Upper */
 523     title[i].other2 = cases[1]; /* Lower */
 524
 525     title_used++;
 526 }
 527
 528 static void
 529 add_upper(unsigned long code)
 530 {
 531     unsigned long i, j;
 532
 533     /*
 534      * Always map the code to itself.
 535      */
 536     cases[0] = code;
 537
 538     /*
 539      * If the title case character is not present, then make it the same as
 540      * the upper case.
 541      */
 542     if (cases[2] == 0)
 543       cases[2] = code;
 544
 545     if (upper_used == upper_size) {
 546         if (upper_size == 0)
 547           upper = (_case_t *) malloc(sizeof(_case_t) << 3);
 548         else
 549           upper = (_case_t *) realloc((char *) upper,
 550                                       sizeof(_case_t) * (upper_size + 8));
 551         upper_size += 8;
 552     }
 553
 554     /*
 555      * Locate the insertion point.
 556      */
 557     for (i = 0; i < upper_used && code > upper[i].key; i++) ;
 558
 559     if (i < upper_used) {
 560         /*
 561          * Shift the array up by one.
 562          */
 563         for (j = upper_used; j > i; j--)
 564           (void) AC_MEMCPY((char *) &upper[j], (char *) &upper[j - 1],
 565                         sizeof(_case_t));
 566     }
 567
 568     upper[i].key = cases[0];    /* Upper */
 569     upper[i].other1 = cases[1]; /* Lower */
 570     upper[i].other2 = cases[2]; /* Title */
 571
 572     upper_used++;
 573 }
 574
 575 static void
 576 add_lower(unsigned long code)
 577 {
 578     unsigned long i, j;
 579
 580     /*
 581      * Always map the code to itself.
 582      */
 583     cases[1] = code;
 584
 585     /*
 586      * If the title case character is empty, then make it the same as the
 587      * upper case.
 588      */
 589     if (cases[2] == 0)
 590       cases[2] = cases[0];
 591
 592     if (lower_used == lower_size) {
 593         if (lower_size == 0)
 594           lower = (_case_t *) malloc(sizeof(_case_t) << 3);
 595         else
 596           lower = (_case_t *) realloc((char *) lower,
 597                                       sizeof(_case_t) * (lower_size + 8));
 598         lower_size += 8;
 599     }
 600
 601     /*
 602      * Locate the insertion point.
 603      */
 604     for (i = 0; i < lower_used && code > lower[i].key; i++) ;
 605
 606     if (i < lower_used) {
 607         /*
 608          * Shift the array up by one.
 609          */
 610         for (j = lower_used; j > i; j--)
 611           (void) AC_MEMCPY((char *) &lower[j], (char *) &lower[j - 1],
 612                         sizeof(_case_t));
 613     }
 614
 615     lower[i].key = cases[1];    /* Lower */
 616     lower[i].other1 = cases[0]; /* Upper */
 617     lower[i].other2 = cases[2]; /* Title */
 618
 619     lower_used++;
 620 }
 621
 622 static void
 623 ordered_ccl_insert(unsigned long c, unsigned long ccl_code)
 624 {
 625     unsigned long i, j;
 626
 627     if (ccl_used == ccl_size) {
 628         if (ccl_size == 0)
 629           ccl = (unsigned long *) malloc(sizeof(unsigned long) * 24);
 630         else
 631           ccl = (unsigned long *)
 632               realloc((char *) ccl, sizeof(unsigned long) * (ccl_size + 24));
 633         ccl_size += 24;
 634     }
 635
 636     /*
 637      * Optimize adding the first item.
 638      */
 639     if (ccl_used == 0) {
 640         ccl[0] = ccl[1] = c;
 641         ccl[2] = ccl_code;
 642         ccl_used += 3;
 643         return;
 644     }
 645
 646     /*
 647      * Handle the special case of extending the range on the end.  This
 648      * requires that the combining class codes are the same.
 649      */
 650     if (ccl_code == ccl[ccl_used - 1] && c == ccl[ccl_used - 2] + 1) {
 651         ccl[ccl_used - 2] = c;
 652         return;
 653     }
 654
 655     /*
 656      * Handle the special case of adding another range on the end.
 657      */
 658     if (c > ccl[ccl_used - 2] + 1 ||
 659         (c == ccl[ccl_used - 2] + 1 && ccl_code != ccl[ccl_used - 1])) {
 660         ccl[ccl_used++] = c;
 661         ccl[ccl_used++] = c;
 662         ccl[ccl_used++] = ccl_code;
 663         return;
 664     }
 665
 666     /*
 667      * Locate either the insertion point or range for the code.
 668      */
 669     for (i = 0; i < ccl_used && c > ccl[i + 1] + 1; i += 3) ;
 670
 671     if (ccl_code == ccl[i + 2] && c == ccl[i + 1] + 1) {
 672         /*
 673          * Extend an existing range.
 674          */
 675         ccl[i + 1] = c;
 676         return;
 677     } else if (c < ccl[i]) {
 678         /*
 679          * Start a new range before the current location.
 680          */
 681         for (j = ccl_used; j > i; j -= 3) {
 682             ccl[j] = ccl[j - 3];
 683             ccl[j - 1] = ccl[j - 4];
 684             ccl[j - 2] = ccl[j - 5];
 685         }
 686         ccl[i] = ccl[i + 1] = c;
 687         ccl[i + 2] = ccl_code;
 688     }
 689 }
 690
 691 /*
 692  * Adds a number if it does not already exist and returns an index value
 693  * multiplied by 2.
 694  */
 695 static unsigned long
 696 make_number(short num, short denom)
 697 {
 698     unsigned long n;
 699
 700     /*
 701      * Determine if the number already exists.
 702      */
 703     for (n = 0; n < nums_used; n++) {
 704         if (nums[n].numerator == num && nums[n].denominator == denom)
 705           return n << 1;
 706     }
 707
 708     if (nums_used == nums_size) {
 709         if (nums_size == 0)
 710           nums = (_num_t *) malloc(sizeof(_num_t) << 3);
 711         else
 712           nums = (_num_t *) realloc((char *) nums,
 713                                     sizeof(_num_t) * (nums_size + 8));
 714         nums_size += 8;
 715     }
 716
 717     n = nums_used++;
 718     nums[n].numerator = num;
 719     nums[n].denominator = denom;
 720
 721     return n << 1;
 722 }
 723
 724 static void
 725 add_number(unsigned long code, short num, short denom)
 726 {
 727     unsigned long i, j;
 728
 729     /*
 730      * Insert the code in order.
 731      */
 732     for (i = 0; i < ncodes_used && code > ncodes[i].code; i++) ;
 733
 734     /*
 735      * Handle the case of the codes matching and simply replace the number
 736      * that was there before.
 737      */
 738     if (ncodes_used > 0 && code == ncodes[i].code) {
 739         ncodes[i].idx = make_number(num, denom);
 740         return;
 741     }
 742
 743     /*
 744      * Resize the array if necessary.
 745      */
 746     if (ncodes_used == ncodes_size) {
 747         if (ncodes_size == 0)
 748           ncodes = (_codeidx_t *) malloc(sizeof(_codeidx_t) << 3);
 749         else
 750           ncodes = (_codeidx_t *)
 751               realloc((char *) ncodes, sizeof(_codeidx_t) * (ncodes_size + 8));
 752
 753         ncodes_size += 8;
 754     }
 755
 756     /*
 757      * Shift things around to insert the code if necessary.
 758      */
 759     if (i < ncodes_used) {
 760         for (j = ncodes_used; j > i; j--) {
 761             ncodes[j].code = ncodes[j - 1].code;
 762             ncodes[j].idx = ncodes[j - 1].idx;
 763         }
 764     }
 765     ncodes[i].code = code;
 766     ncodes[i].idx = make_number(num, denom);
 767
 768     ncodes_used++;
 769 }
 770
 771 /*
 772  * This routine assumes that the line is a valid Unicode Character Database
 773  * entry.
 774  */
 775 static void
 776 read_cdata(FILE *in)
 777 {
 778     unsigned long i, lineno, skip, code, ccl_code;
 779     short wnum, neg, number[2];
 780     char line[512], *s, *e;
 781
 782     lineno = skip = 0;
 783     while (fscanf(in, "%[^\n]\n", line) != EOF) {
 784         lineno++;
 785
 786         /*
 787          * Skip blank lines and lines that start with a '#'.
 788          */
 789         if (line[0] == 0 || line[0] == '#')
 790           continue;
 791
 792         /*
 793          * If lines need to be skipped, do it here.
 794          */
 795         if (skip) {
 796             skip--;
 797             continue;
 798         }
 799
 800         /*
 801          * Collect the code.  The code can be up to 6 hex digits in length to
 802          * allow surrogates to be specified.
 803          */
 804         for (s = line, i = code = 0; *s != ';' && i < 6; i++, s++) {
 805             code <<= 4;
 806             if (*s >= '0' && *s <= '9')
 807               code += *s - '0';
 808             else if (*s >= 'A' && *s <= 'F')
 809               code += (*s - 'A') + 10;
 810             else if (*s >= 'a' && *s <= 'f')
 811               code += (*s - 'a') + 10;
 812         }
 813
 814         /*
 815          * Handle the following special cases:
 816          * 1. 4E00-9FA5 CJK Ideographs.
 817          * 2. AC00-D7A3 Hangul Syllables.
 818          * 3. D800-DFFF Surrogates.
 819          * 4. E000-F8FF Private Use Area.
 820          * 5. F900-FA2D Han compatibility.
 821          */
 822         switch (code) {
 823           case 0x4e00:
 824             /*
 825              * The Han ideographs.
 826              */
 827             add_range(0x4e00, 0x9fff, "Lo", "L");
 828
 829             /*
 830              * Add the characters to the defined category.
 831              */
 832             add_range(0x4e00, 0x9fa5, "Cp", 0);
 833
 834             skip = 1;
 835             break;
 836           case 0xac00:
 837             /*
 838              * The Hangul syllables.
 839              */
 840             add_range(0xac00, 0xd7a3, "Lo", "L");
 841
 842             /*
 843              * Add the characters to the defined category.
 844              */
 845             add_range(0xac00, 0xd7a3, "Cp", 0);
 846
 847             skip = 1;
 848             break;
 849           case 0xd800:
 850             /*
 851              * Make a range of all surrogates and assume some default
 852              * properties.
 853              */
 854             add_range(0x010000, 0x10ffff, "Cs", "L");
 855             skip = 5;
 856             break;
 857           case 0xe000:
 858             /*
 859              * The Private Use area.  Add with a default set of properties.
 860              */
 861             add_range(0xe000, 0xf8ff, "Co", "L");
 862             skip = 1;
 863             break;
 864           case 0xf900:
 865             /*
 866              * The CJK compatibility area.
 867              */
 868             add_range(0xf900, 0xfaff, "Lo", "L");
 869
 870             /*
 871              * Add the characters to the defined category.
 872              */
 873             add_range(0xf900, 0xfaff, "Cp", 0);
 874
 875             skip = 1;
 876         }
 877
 878         if (skip)
 879           continue;
 880
 881         /*
 882          * Add the code to the defined category.
 883          */
 884         ordered_range_insert(code, "Cp", 2);
 885
 886         /*
 887          * Locate the first character property field.
 888          */
 889         for (i = 0; *s != 0 && i < 2; s++) {
 890             if (*s == ';')
 891               i++;
 892         }
 893         for (e = s; *e && *e != ';'; e++) ;
 894
 895         ordered_range_insert(code, s, e - s);
 896
 897         /*
 898          * Locate the combining class code.
 899          */
 900         for (s = e; *s != 0 && i < 3; s++) {
 901             if (*s == ';')
 902               i++;
 903         }
 904
 905         /*
 906          * Convert the combining class code from decimal.
 907          */
 908         for (ccl_code = 0, e = s; *e && *e != ';'; e++)
 909           ccl_code = (ccl_code * 10) + (*e - '0');
 910
 911         /*
 912          * Add the code if it not 0.
 913          */
 914         if (ccl_code != 0)
 915           ordered_ccl_insert(code, ccl_code);
 916
 917         /*
 918          * Locate the second character property field.
 919          */
 920         for (s = e; *s != 0 && i < 4; s++) {
 921             if (*s == ';')
 922               i++;
 923         }
 924         for (e = s; *e && *e != ';'; e++) ;
 925
 926         ordered_range_insert(code, s, e - s);
 927
 928         /*
 929          * Check for a decomposition.
 930          */
 931         s = ++e;
 932         if (*s != ';' && *s != '<') {
 933             /*
 934              * Collect the codes of the decomposition.
 935              */
 936             for (dectmp_size = 0; *s != ';'; ) {
 937                 /*
 938                  * Skip all leading non-hex digits.
 939                  */
 940                 while (!ishdigit(*s))
 941                   s++;
 942
 943                 for (dectmp[dectmp_size] = 0; ishdigit(*s); s++) {
 944                     dectmp[dectmp_size] <<= 4;
 945                     if (*s >= '0' && *s <= '9')
 946                       dectmp[dectmp_size] += *s - '0';
 947                     else if (*s >= 'A' && *s <= 'F')
 948                       dectmp[dectmp_size] += (*s - 'A') + 10;
 949                     else if (*s >= 'a' && *s <= 'f')
 950                       dectmp[dectmp_size] += (*s - 'a') + 10;
 951                 }
 952                 dectmp_size++;
 953             }
 954
 955             /*
 956              * If there are any codes in the temporary decomposition array,
 957              * then add the character with its decomposition.
 958              */
 959             if (dectmp_size > 0)
 960               add_decomp(code);
 961         }
 962
 963         /*
 964          * Skip to the number field.
 965          */
 966         for (i = 0; i < 3 && *s; s++) {
 967             if (*s == ';')
 968               i++;
 969         }
 970
 971         /*
 972          * Scan the number in.
 973          */
 974         number[0] = number[1] = 0;
 975         for (e = s, neg = wnum = 0; *e && *e != ';'; e++) {
 976             if (*e == '-') {
 977                 neg = 1;
 978                 continue;
 979             }
 980
 981             if (*e == '/') {
 982                 /*
 983                  * Move the the denominator of the fraction.
 984                  */
 985                 if (neg)
 986                   number[wnum] *= -1;
 987                 neg = 0;
 988                 e++;
 989                 wnum++;
 990             }
 991             number[wnum] = (number[wnum] * 10) + (*e - '0');
 992         }
 993
 994         if (e > s) {
 995             /*
 996              * Adjust the denominator in case of integers and add the number.
 997              */
 998             if (wnum == 0)
 999               number[1] = number[0];
1000
1001             add_number(code, number[0], number[1]);
1002         }
1003
1004         /*
1005          * Skip to the start of the possible case mappings.
1006          */
1007         for (s = e, i = 0; i < 4 && *s; s++) {
1008             if (*s == ';')
1009               i++;
1010         }
1011
1012         /*
1013          * Collect the case mappings.
1014          */
1015         cases[0] = cases[1] = cases[2] = 0;
1016         for (i = 0; i < 3; i++) {
1017             while (ishdigit(*s)) {
1018                 cases[i] <<= 4;
1019                 if (*s >= '0' && *s <= '9')
1020                   cases[i] += *s - '0';
1021                 else if (*s >= 'A' && *s <= 'F')
1022                   cases[i] += (*s - 'A') + 10;
1023                 else if (*s >= 'a' && *s <= 'f')
1024                   cases[i] += (*s - 'a') + 10;
1025                 s++;
1026             }
1027             if (*s == ';')
1028               s++;
1029         }
1030         if (cases[0] && cases[1])
1031           /*
1032            * Add the upper and lower mappings for a title case character.
1033            */
1034           add_title(code);
1035         else if (cases[1])
1036           /*
1037            * Add the lower and title case mappings for the upper case
1038            * character.
1039            */
1040           add_upper(code);
1041         else if (cases[0])
1042           /*
1043            * Add the upper and title case mappings for the lower case
1044            * character.
1045            */
1046           add_lower(code);
1047     }
1048 }
1049
1050 static _decomp_t *
1051 find_decomp(unsigned long code)
1052 {
1053     long l, r, m;
1054
1055     l = 0;
1056     r = decomps_used - 1;
1057     while (l <= r) {
1058         m = (l + r) >> 1;
1059         if (code > decomps[m].code)
1060           l = m + 1;
1061         else if (code < decomps[m].code)
1062           r = m - 1;
1063         else
1064           return &decomps[m];
1065     }
1066     return 0;
1067 }
1068
1069 static void
1070 decomp_it(_decomp_t *d)
1071 {
1072     unsigned long i;
1073     _decomp_t *dp;
1074
1075     for (i = 0; i < d->used; i++) {
1076         if ((dp = find_decomp(d->decomp[i])) != 0)
1077           decomp_it(dp);
1078         else
1079           dectmp[dectmp_size++] = d->decomp[i];
1080     }
1081 }
1082
1083 /*
1084  * Expand all decompositions by recursively decomposing each character
1085  * in the decomposition.
1086  */
1087 static void
1088 expand_decomp(void)
1089 {
1090     unsigned long i;
1091
1092     for (i = 0; i < decomps_used; i++) {
1093         dectmp_size = 0;
1094         decomp_it(&decomps[i]);
1095         if (dectmp_size > 0)
1096           add_decomp(decomps[i].code);
1097     }
1098 }
1099
1100 static int
1101 cmpcomps(_comp_t *comp1, _comp_t *comp2)
1102 {
1103     long diff = comp1->code1 - comp2->code1;
1104
1105     if (!diff)
1106         diff = comp1->code2 - comp2->code2;
1107     return (int) diff;
1108 }
1109
1110 /*
1111  * Load composition exclusion data
1112  */
1113 static void
1114 read_compexdata(FILE *in)
1115 {
1116     unsigned short i, code;
1117     char line[512], *s;
1118
1119     (void) memset((char *) compexs, 0, sizeof(unsigned long) << 11);
1120
1121     while (fscanf(in, "%[^\n]\n", line) != EOF) {
1122         /*
1123          * Skip blank lines and lines that start with a '#'.
1124          */
1125         if (line[0] == 0 || line[0] == '#')
1126             continue;
1127
1128         /*
1129          * Collect the code.  Assume max 4 digits
1130          */
1131
1132         for (s = line, i = code = 0; *s != '#' && i < 4; i++, s++) {
1133             code <<= 4;
1134             if (*s >= '0' && *s <= '9')
1135                 code += *s - '0';
1136             else if (*s >= 'A' && *s <= 'F')
1137                 code += (*s - 'A') + 10;
1138             else if (*s >= 'a' && *s <= 'f')
1139                 code += (*s - 'a') + 10;
1140         }
1141         COMPEX_SET(code);
1142     }
1143 }
1144
1145 /*
1146  * Creates array of compositions from decomposition array
1147  */
1148 static void
1149 create_comps(void)
1150 {
1151     unsigned long i, cu;
1152
1153     comps = (_comp_t *) malloc(comps_used * sizeof(_comp_t));
1154
1155     for (i = cu = 0; i < decomps_used; i++) {
1156         if (decomps[i].used != 2 || COMPEX_TEST(decomps[i].code))
1157             continue;
1158         comps[cu].comp = decomps[i].code;
1159         comps[cu].count = 2;
1160         comps[cu].code1 = decomps[i].decomp[0];
1161         comps[cu].code2 = decomps[i].decomp[1];
1162         cu++;
1163     }
1164     comps_used = cu;
1165     qsort(comps, comps_used, sizeof(_comp_t),
1166           (int (*)(const void *, const void *)) cmpcomps);
1167 }
1168
1169 static void
1170 write_cdata(char *opath)
1171 {
1172     FILE *out;
1173     unsigned long i, idx, bytes, nprops;
1174     unsigned short casecnt[2];
1175     char path[BUFSIZ];
1176
1177     /*****************************************************************
1178      *
1179      * Generate the ctype data.
1180      *
1181      *****************************************************************/
1182
1183     /*
1184      * Open the ctype.dat file.
1185      */
1186     sprintf(path, "%s%sctype.dat", opath, LDAP_DIRSEP);
1187     if ((out = fopen(path, "wb")) == 0)
1188       return;
1189
1190     /*
1191      * Collect the offsets for the properties.  The offsets array is
1192      * on a 4-byte boundary to keep things efficient for architectures
1193      * that need such a thing.
1194      */
1195     for (i = idx = 0; i < NUMPROPS; i++) {
1196         propcnt[i] = (proptbl[i].used != 0) ? idx : 0xffff;
1197         idx += proptbl[i].used;
1198     }
1199
1200     /*
1201      * Add the sentinel index which is used by the binary search as the upper
1202      * bound for a search.
1203      */
1204     propcnt[i] = idx;
1205
1206     /*
1207      * Record the actual number of property lists.  This may be different than
1208      * the number of offsets actually written because of aligning on a 4-byte
1209      * boundary.
1210      */
1211     hdr[1] = NUMPROPS;
1212
1213     /*
1214      * Calculate the byte count needed and pad the property counts array to a
1215      * 4-byte boundary.
1216      */
1217     if ((bytes = sizeof(unsigned short) * (NUMPROPS + 1)) & 3)
1218       bytes += 4 - (bytes & 3);
1219     nprops = bytes / sizeof(unsigned short);
1220     bytes += sizeof(unsigned long) * idx;
1221
1222     /*
1223      * Write the header.
1224      */
1225     fwrite((char *) hdr, sizeof(unsigned short), 2, out);
1226
1227     /*
1228      * Write the byte count.
1229      */
1230     fwrite((char *) &bytes, sizeof(unsigned long), 1, out);
1231
1232     /*
1233      * Write the property list counts.
1234      */
1235     fwrite((char *) propcnt, sizeof(unsigned short), nprops, out);
1236
1237     /*
1238      * Write the property lists.
1239      */
1240     for (i = 0; i < NUMPROPS; i++) {
1241         if (proptbl[i].used > 0)
1242           fwrite((char *) proptbl[i].ranges, sizeof(unsigned long),
1243                  proptbl[i].used, out);
1244     }
1245
1246     fclose(out);
1247
1248     /*****************************************************************
1249      *
1250      * Generate the case mapping data.
1251      *
1252      *****************************************************************/
1253
1254     /*
1255      * Open the case.dat file.
1256      */
1257     sprintf(path, "%s%scase.dat", opath, LDAP_DIRSEP);
1258     if ((out = fopen(path, "wb")) == 0)
1259       return;
1260
1261     /*
1262      * Write the case mapping tables.
1263      */
1264     hdr[1] = upper_used + lower_used + title_used;
1265     casecnt[0] = upper_used;
1266     casecnt[1] = lower_used;
1267
1268     /*
1269      * Write the header.
1270      */
1271     fwrite((char *) hdr, sizeof(unsigned short), 2, out);
1272
1273     /*
1274      * Write the upper and lower case table sizes.
1275      */
1276     fwrite((char *) casecnt, sizeof(unsigned short), 2, out);
1277
1278     if (upper_used > 0)
1279       /*
1280        * Write the upper case table.
1281        */
1282       fwrite((char *) upper, sizeof(_case_t), upper_used, out);
1283
1284     if (lower_used > 0)
1285       /*
1286        * Write the lower case table.
1287        */
1288       fwrite((char *) lower, sizeof(_case_t), lower_used, out);
1289
1290     if (title_used > 0)
1291       /*
1292        * Write the title case table.
1293        */
1294       fwrite((char *) title, sizeof(_case_t), title_used, out);
1295
1296     fclose(out);
1297
1298     /*****************************************************************
1299      *
1300      * Generate the composition data.
1301      *
1302      *****************************************************************/
1303
1304     /*
1305      * Create compositions from decomposition data
1306      */
1307     create_comps();
1308
1309     /*
1310      * Open the comp.dat file.
1311      */
1312     sprintf(path, "%s%scomp.dat", opath, LDAP_DIRSEP);
1313     if ((out = fopen(path, "wb")) == 0)
1314         return;
1315
1316     /*
1317      * Write the header.
1318      */
1319     hdr[1] = (unsigned short) comps_used * 4;
1320     fwrite((char *) hdr, sizeof(unsigned short), 2, out);
1321
1322     /*
1323      * Write out the byte count to maintain header size.
1324      */
1325     bytes = comps_used * sizeof(_comp_t);
1326     fwrite((char *) &bytes, sizeof(unsigned long), 1, out);
1327
1328     /*
1329      * Now, if comps exist, write them out.
1330      */
1331     if (comps_used > 0)
1332         fwrite((char *) comps, sizeof(_comp_t), comps_used, out);
1333
1334     fclose(out);
1335
1336     /*****************************************************************
1337      *
1338      * Generate the decomposition data.
1339      *
1340      *****************************************************************/
1341
1342     /*
1343      * Fully expand all decompositions before generating the output file.
1344      */
1345     expand_decomp();
1346
1347     /*
1348      * Open the decomp.dat file.
1349      */
1350     sprintf(path, "%s%sdecomp.dat", opath, LDAP_DIRSEP);
1351     if ((out = fopen(path, "wb")) == 0)
1352       return;
1353
1354     hdr[1] = decomps_used;
1355
1356     /*
1357      * Write the header.
1358      */
1359     fwrite((char *) hdr, sizeof(unsigned short), 2, out);
1360
1361     /*
1362      * Write a temporary byte count which will be calculated as the
1363      * decompositions are written out.
1364      */
1365     bytes = 0;
1366     fwrite((char *) &bytes, sizeof(unsigned long), 1, out);
1367
1368     if (decomps_used) {
1369         /*
1370          * Write the list of decomp nodes.
1371          */
1372         for (i = idx = 0; i < decomps_used; i++) {
1373             fwrite((char *) &decomps[i].code, sizeof(unsigned long), 1, out);
1374             fwrite((char *) &idx, sizeof(unsigned long), 1, out);
1375             idx += decomps[i].used;
1376         }
1377
1378         /*
1379          * Write the sentinel index as the last decomp node.
1380          */
1381         fwrite((char *) &idx, sizeof(unsigned long), 1, out);
1382
1383         /*
1384          * Write the decompositions themselves.
1385          */
1386         for (i = 0; i < decomps_used; i++)
1387           fwrite((char *) decomps[i].decomp, sizeof(unsigned long),
1388                  decomps[i].used, out);
1389
1390         /*
1391          * Seek back to the beginning and write the byte count.
1392          */
1393         bytes = (sizeof(unsigned long) * idx) +
1394             (sizeof(unsigned long) * ((hdr[1] << 1) + 1));
1395         fseek(out, sizeof(unsigned short) << 1, 0L);
1396         fwrite((char *) &bytes, sizeof(unsigned long), 1, out);
1397
1398         fclose(out);
1399     }
1400
1401     /*****************************************************************
1402      *
1403      * Generate the combining class data.
1404      *
1405      *****************************************************************/
1406
1407     /*
1408      * Open the cmbcl.dat file.
1409      */
1410     sprintf(path, "%s%scmbcl.dat", opath, LDAP_DIRSEP);
1411     if ((out = fopen(path, "wb")) == 0)
1412       return;
1413
1414     /*
1415      * Set the number of ranges used.  Each range has a combining class which
1416      * means each entry is a 3-tuple.
1417      */
1418     hdr[1] = ccl_used / 3;
1419
1420     /*
1421      * Write the header.
1422      */
1423     fwrite((char *) hdr, sizeof(unsigned short), 2, out);
1424
1425     /*
1426      * Write out the byte count to maintain header size.
1427      */
1428     bytes = ccl_used * sizeof(unsigned long);
1429     fwrite((char *) &bytes, sizeof(unsigned long), 1, out);
1430
1431     if (ccl_used > 0)
1432       /*
1433        * Write the combining class ranges out.
1434        */
1435       fwrite((char *) ccl, sizeof(unsigned long), ccl_used, out);
1436
1437     fclose(out);
1438
1439     /*****************************************************************
1440      *
1441      * Generate the number data.
1442      *
1443      *****************************************************************/
1444
1445     /*
1446      * Open the num.dat file.
1447      */
1448     sprintf(path, "%s%snum.dat", opath, LDAP_DIRSEP);
1449     if ((out = fopen(path, "wb")) == 0)
1450       return;
1451
1452     /*
1453      * The count part of the header will be the total number of codes that
1454      * have numbers.
1455      */
1456     hdr[1] = (unsigned short) (ncodes_used << 1);
1457     bytes = (ncodes_used * sizeof(_codeidx_t)) + (nums_used * sizeof(_num_t));
1458
1459     /*
1460      * Write the header.
1461      */
1462     fwrite((char *) hdr, sizeof(unsigned short), 2, out);
1463
1464     /*
1465      * Write out the byte count to maintain header size.
1466      */
1467     fwrite((char *) &bytes, sizeof(unsigned long), 1, out);
1468
1469     /*
1470      * Now, if number mappings exist, write them out.
1471      */
1472     if (ncodes_used > 0) {
1473         fwrite((char *) ncodes, sizeof(_codeidx_t), ncodes_used, out);
1474         fwrite((char *) nums, sizeof(_num_t), nums_used, out);
1475     }
1476
1477     fclose(out);
1478 }
1479
1480 static void
1481 usage(char *prog)
1482 {
1483     fprintf(stderr,
1484             "Usage: %s [-o output-directory|-x composition-exclusions]", prog);
1485     fprintf(stderr, " datafile1 datafile2 ...\n\n");
1486     fprintf(stderr,
1487             "-o output-directory\n\t\tWrite the output files to a different");
1488     fprintf(stderr, " directory (default: .).\n");
1489     fprintf(stderr,
1490             "-x composition-exclusion\n\t\tFile of composition codes");
1491     fprintf(stderr, " that should be excluded.\n");
1492     exit(1);
1493 }
1494
1495 int
1496 main(int argc, char *argv[])
1497 {
1498     FILE *in;
1499     char *prog, *opath;
1500
1501     if ((prog = strrchr(argv[0], *LDAP_DIRSEP)) != 0)
1502       prog++;
1503     else
1504       prog = argv[0];
1505
1506     opath = 0;
1507     in = stdin;
1508
1509     argc--;
1510     argv++;
1511
1512     while (argc > 0) {
1513         if (argv[0][0] == '-') {
1514             switch (argv[0][1]) {
1515               case 'o':
1516                 argc--;
1517                 argv++;
1518                 opath = argv[0];
1519                 break;
1520               case 'x':
1521                 argc--;
1522                 argv++;
1523                 if ((in = fopen(argv[0], "rb")) == 0)
1524                   fprintf(stderr,
1525                           "%s: unable to open composition exclusion file %s\n",
1526                           prog, argv[0]);
1527                 else {
1528                     read_compexdata(in);
1529                     fclose(in);
1530                     in = 0;
1531                 }
1532                 break;
1533               default:
1534                 usage(prog);
1535             }
1536         } else {
1537             if (in != stdin && in != NULL)
1538               fclose(in);
1539             if ((in = fopen(argv[0], "rb")) == 0)
1540               fprintf(stderr, "%s: unable to open ctype file %s\n",
1541                       prog, argv[0]);
1542             else {
1543                 read_cdata(in);
1544                 fclose(in);
1545                 in = 0;
1546             }
1547         }
1548         argc--;
1549         argv++;
1550     }
1551
1552     if (opath == 0)
1553       opath = ".";
1554     write_cdata(opath);
1555
1556     return 0;
1557 }