lib/libc/locale/collate.c

   1 /*
   2  * Copright 2010 Nexenta Systems, Inc.  All rights reserved.
   3  * Copyright (c) 1995 Alex Tatmanjants <alex@elvisti.kiev.ua>
   4  *              at Electronni Visti IA, Kiev, Ukraine.
   5  *                      All rights reserved.
   6  *
   7  * Copyright (c) 2011 The FreeBSD Foundation
   8  * All rights reserved.
   9  * Portions of this software were developed by David Chisnall
  10  * under sponsorship from the FreeBSD Foundation.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  * Adapted to xlocale by John Marino <draco@marino.st>
  34  */
  35
  36 #include "namespace.h"
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40 #include <wchar.h>
  41 #include <errno.h>
  42 #include <unistd.h>
  43 #include <fcntl.h>
  44 #include <sys/types.h>
  45 #include <sys/stat.h>
  46 #include <sys/mman.h>
  47 #include "un-namespace.h"
  48
  49 #include "collate.h"
  50 #include "setlocale.h"
  51 #include "ldpart.h"
  52
  53 struct xlocale_collate __xlocale_global_collate = {
  54         {{0}, "C"}, 1, 0, 0, 0
  55 };
  56
  57 struct xlocale_collate __xlocale_C_collate = {
  58         {{0}, "C"}, 1, 0, 0, 0
  59 };
  60
  61 #include "libc_private.h"
  62
  63 int
  64 __collate_load_tables_l(const char *encoding, struct xlocale_collate *table);
  65
  66 static void
  67 destruct_collate(void *t)
  68 {
  69         struct xlocale_collate *table = t;
  70         if (table->map && (table->maplen > 0)) {
  71                 (void) munmap(table->map, table->maplen);
  72         }
  73         free(t);
  74 }
  75
  76 void *
  77 __collate_load(const char *encoding, __unused locale_t unused)
  78 {
  79         if (strcmp(encoding, "C") == 0 || strcmp(encoding, "POSIX") == 0) {
  80                 return &__xlocale_C_collate;
  81         }
  82         struct xlocale_collate *table = calloc(sizeof(struct xlocale_collate), 1);
  83         table->header.header.destructor = destruct_collate;
  84         // FIXME: Make sure that _LDP_CACHE is never returned.  We should be doing
  85         // the caching outside of this section
  86         if (__collate_load_tables_l(encoding, table) != _LDP_LOADED) {
  87                 xlocale_release(table);
  88                 return NULL;
  89         }
  90         return table;
  91 }
  92
  93 /**
  94  * Load the collation tables for the specified encoding into the global table.
  95  */
  96 int
  97 __collate_load_tables(const char *encoding)
  98 {
  99         int ret = __collate_load_tables_l(encoding, &__xlocale_global_collate);
 100         return ret;
 101 }
 102
 103 int
 104 __collate_load_tables_l(const char *encoding, struct xlocale_collate *table)
 105 {
 106         int i, chains, z;
 107         char buf[PATH_MAX];
 108         char *TMP;
 109         char *map;
 110         collate_info_t *info;
 111         struct stat sbuf;
 112         int fd;
 113
 114         /* 'encoding' must be already checked. */
 115         if (strcmp(encoding, "C") == 0 || strcmp(encoding, "POSIX") == 0) {
 116                 table->__collate_load_error = 1;
 117                 return (_LDP_CACHE);
 118         }
 119
 120         (void) snprintf(buf, sizeof (buf), "%s/%s/LC_COLLATE",
 121             _PathLocale, encoding);
 122
 123         if ((fd = _open(buf, O_RDONLY)) < 0)
 124                 return (_LDP_ERROR);
 125         if (_fstat(fd, &sbuf) < 0) {
 126                 (void) _close(fd);
 127                 return (_LDP_ERROR);
 128         }
 129         if (sbuf.st_size < (COLLATE_STR_LEN + sizeof (info))) {
 130                 (void) _close(fd);
 131                 errno = EINVAL;
 132                 return (_LDP_ERROR);
 133         }
 134         map = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
 135         (void) _close(fd);
 136         if ((TMP = map) == NULL) {
 137                 return (_LDP_ERROR);
 138         }
 139
 140         if (strncmp(TMP, COLLATE_VERSION, COLLATE_STR_LEN) != 0) {
 141                 (void) munmap(map, sbuf.st_size);
 142                 errno = EINVAL;
 143                 return (_LDP_ERROR);
 144         }
 145         TMP += COLLATE_STR_LEN;
 146
 147         info = (void *)TMP;
 148         TMP += sizeof (*info);
 149
 150         if ((info->directive_count < 1) ||
 151             (info->directive_count >= COLL_WEIGHTS_MAX) ||
 152             ((chains = info->chain_count) < 0)) {
 153                 (void) munmap(map, sbuf.st_size);
 154                 errno = EINVAL;
 155                 return (_LDP_ERROR);
 156         }
 157
 158         i = (sizeof (collate_char_t) * (UCHAR_MAX + 1)) +
 159             (sizeof (collate_chain_t) * chains) +
 160             (sizeof (collate_large_t) * info->large_count);
 161         for (z = 0; z < (info->directive_count); z++) {
 162                 i += sizeof (collate_subst_t) * info->subst_count[z];
 163         }
 164         if (i != (sbuf.st_size - (TMP - map))) {
 165                 (void) munmap(map, sbuf.st_size);
 166                 errno = EINVAL;
 167                 return (_LDP_ERROR);
 168         }
 169
 170         table->char_pri_table = (void *)TMP;
 171         TMP += sizeof (collate_char_t) * (UCHAR_MAX + 1);
 172
 173         for (z = 0; z < info->directive_count; z++) {
 174                 if (info->subst_count[z] > 0) {
 175                         table->subst_table[z] = (void *)TMP;
 176                         TMP += info->subst_count[z] * sizeof (collate_subst_t);
 177                 } else {
 178                         table->subst_table[z] = NULL;
 179                 }
 180         }
 181
 182         if (chains > 0) {
 183                 table->chain_pri_table = (void *)TMP;
 184                 TMP += chains * sizeof (collate_chain_t);
 185         } else
 186                 table->chain_pri_table = NULL;
 187         if (info->large_count > 0)
 188                 table->large_pri_table = (void *)TMP;
 189         else
 190                 table->large_pri_table = NULL;
 191
 192         table->info = info;
 193         table->__collate_load_error = 0;
 194
 195         return (_LDP_LOADED);
 196 }
 197
 198 /*
 199  * Note: for performance reasons, we have expanded bsearch here.  This avoids
 200  * function call overhead with each comparison.
 201  */
 202
 203 static int32_t *
 204 substsearch(struct xlocale_collate *table, const wchar_t key, int pass)
 205 {
 206         collate_subst_t *p;
 207         int n = table->info->subst_count[pass];
 208
 209         if (n == 0)
 210                 return (NULL);
 211
 212         if (pass >= table->info->directive_count)
 213                 return (NULL);
 214
 215         if (!(key & COLLATE_SUBST_PRIORITY))
 216                 return (NULL);
 217
 218         p = table->subst_table[pass] + (key & ~COLLATE_SUBST_PRIORITY);
 219         return (p->pri);
 220 }
 221
 222 static collate_chain_t *
 223 chainsearch(struct xlocale_collate *table, const wchar_t *key, int *len)
 224 {
 225         int low;
 226         int high;
 227         int next, compar, l;
 228         collate_chain_t *p;
 229         collate_chain_t *tab;
 230
 231         if (table->info->chain_count == 0)
 232                 return (NULL);
 233
 234         low = 0;
 235         high = table->info->chain_count - 1;
 236         tab = table->chain_pri_table;
 237
 238         while (low <= high) {
 239                 next = (low + high) / 2;
 240                 p = tab + next;
 241                 compar = *key - *p->str;
 242                 if (compar == 0) {
 243                         l = wcsnlen(p->str, COLLATE_STR_LEN);
 244                         compar = wcsncmp(key, p->str, l);
 245                         if (compar == 0) {
 246                                 *len = l;
 247                                 return (p);
 248                         }
 249                 }
 250                 if (compar > 0)
 251                         low = next + 1;
 252                 else
 253                         high = next - 1;
 254         }
 255         return (NULL);
 256 }
 257
 258 static collate_large_t *
 259 largesearch(struct xlocale_collate *table, const wchar_t key)
 260 {
 261         int low = 0;
 262         int high = table->info->large_count - 1;
 263         int next, compar;
 264         collate_large_t *p;
 265         collate_large_t *tab = table->large_pri_table;
 266
 267         if (table->info->large_count == 0)
 268                 return (NULL);
 269
 270         while (low <= high) {
 271                 next = (low + high) / 2;
 272                 p = tab + next;
 273                 compar = key - p->val;
 274                 if (compar == 0)
 275                         return (p);
 276                 if (compar > 0)
 277                         low = next + 1;
 278                 else
 279                         high = next - 1;
 280         }
 281         return (NULL);
 282 }
 283
 284 void
 285 _collate_lookup(struct xlocale_collate *table, const wchar_t *t, int *len,
 286     int *pri, int which, const int **state)
 287 {
 288         collate_chain_t *p2;
 289         collate_large_t *match;
 290         int p, l;
 291         const int *sptr;
 292
 293         /*
 294          * If this is the "last" pass for the UNDEFINED, then
 295          * we just return the priority itself.
 296          */
 297         if (which >= table->info->directive_count) {
 298                 *pri = *t;
 299                 *len = 1;
 300                 *state = NULL;
 301                 return;
 302         }
 303
 304         /*
 305          * If we have remaining substitution data from a previous
 306          * call, consume it first.
 307          */
 308         if ((sptr = *state) != NULL) {
 309                 *pri = *sptr;
 310                 sptr++;
 311                 *state = *sptr ? sptr : NULL;
 312                 *len = 0;
 313                 return;
 314         }
 315
 316         /* No active substitutions */
 317         *len = 1;
 318
 319         /*
 320          * Check for composites such as dipthongs that collate as a
 321          * single element (aka chains or collating-elements).
 322          */
 323         if (((p2 = chainsearch(table, t, &l)) != NULL) &&
 324             ((p = p2->pri[which]) >= 0)) {
 325
 326                 *len = l;
 327                 *pri = p;
 328
 329         } else if (*t <= UCHAR_MAX) {
 330
 331                 /*
 332                  * Character is a small (8-bit) character.
 333                  * We just look these up directly for speed.
 334                  */
 335                 *pri = table->char_pri_table[*t].pri[which];
 336
 337         } else if ((table->info->large_count > 0) &&
 338             ((match = largesearch(table, *t)) != NULL)) {
 339
 340                 /*
 341                  * Character was found in the extended table.
 342                  */
 343                 *pri = match->pri.pri[which];
 344
 345         } else {
 346                 /*
 347                  * Character lacks a specific definition.
 348                  */
 349                 if (table->info->directive[which] & DIRECTIVE_UNDEFINED) {
 350                         /* Mask off sign bit to prevent ordering confusion. */
 351                         *pri = (*t & COLLATE_MAX_PRIORITY);
 352                 } else {
 353                         *pri = table->info->undef_pri[which];
 354                 }
 355                 /* No substitutions for undefined characters! */
 356                 return;
 357         }
 358
 359         /*
 360          * Try substituting (expanding) the character.  We are
 361          * currently doing this *after* the chain compression.  I
 362          * think it should not matter, but this way might be slightly
 363          * faster.
 364          *
 365          * We do this after the priority search, as this will help us
 366          * to identify a single key value.  In order for this to work,
 367          * its important that the priority assigned to a given element
 368          * to be substituted be unique for that level.  The localedef
 369          * code ensures this for us.
 370          */
 371         if ((sptr = substsearch(table, *pri, which)) != NULL) {
 372                 if ((*pri = *sptr) != 0) {
 373                         sptr++;
 374                         *state = *sptr ? sptr : NULL;
 375                 }
 376         }
 377
 378 }
 379
 380 /*
 381  * This is the meaty part of wcsxfrm & strxfrm.  Note that it does
 382  * NOT NULL terminate.  That is left to the caller.
 383  */
 384 size_t
 385 _collate_wxfrm(struct xlocale_collate *table, const wchar_t *src, wchar_t *xf,
 386     size_t room)
 387 {
 388         int             pri;
 389         int             len;
 390         const wchar_t   *t;
 391         wchar_t         *tr = NULL;
 392         int             direc;
 393         int             pass;
 394         const int32_t   *state;
 395         size_t          want = 0;
 396         size_t          need = 0;
 397
 398         for (pass = 0; pass <= table->info->directive_count; pass++) {
 399
 400                 state = NULL;
 401
 402                 if (pass != 0) {
 403                         /* insert level separator from the previous pass */
 404                         if (room) {
 405                                 *xf++ = 1;
 406                                 room--;
 407                         }
 408                         want++;
 409                 }
 410
 411                 /* special pass for undefined */
 412                 if (pass == table->info->directive_count) {
 413                         direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
 414                 } else {
 415                         direc = table->info->directive[pass];
 416                 }
 417
 418                 t = src;
 419
 420                 if (direc & DIRECTIVE_BACKWARD) {
 421                         wchar_t *bp, *fp, c;
 422                         if (tr)
 423                                 free(tr);
 424                         if ((tr = wcsdup(t)) == NULL) {
 425                                 errno = ENOMEM;
 426                                 goto fail;
 427                         }
 428                         bp = tr;
 429                         fp = tr + wcslen(tr) - 1;
 430                         while (bp < fp) {
 431                                 c = *bp;
 432                                 *bp++ = *fp;
 433                                 *fp-- = c;
 434                         }
 435                         t = (const wchar_t *)tr;
 436                 }
 437
 438                 if (direc & DIRECTIVE_POSITION) {
 439                         while (*t || state) {
 440                                 _collate_lookup(table, t, &len, &pri, pass, &state);
 441                                 t += len;
 442                                 if (pri <= 0) {
 443                                         if (pri < 0) {
 444                                                 errno = EINVAL;
 445                                                 goto fail;
 446                                         }
 447                                         pri = COLLATE_MAX_PRIORITY;
 448                                 }
 449                                 if (room) {
 450                                         *xf++ = pri;
 451                                         room--;
 452                                 }
 453                                 want++;
 454                                 need = want;
 455                         }
 456                 } else {
 457                         while (*t || state) {
 458                                 _collate_lookup(table, t, &len, &pri, pass, &state);
 459                                 t += len;
 460                                 if (pri <= 0) {
 461                                         if (pri < 0) {
 462                                                 errno = EINVAL;
 463                                                 goto fail;
 464                                         }
 465                                         continue;
 466                                 }
 467                                 if (room) {
 468                                         *xf++ = pri;
 469                                         room--;
 470                                 }
 471                                 want++;
 472                                 need = want;
 473                         }
 474                 }
 475         }
 476         if (tr)
 477                 free(tr);
 478         return (need);
 479
 480 fail:
 481         if (tr)
 482                 free(tr);
 483         return ((size_t)(-1));
 484 }
 485
 486 /*
 487  * In the non-POSIX case, we transform each character into a string of
 488  * characters representing the character's priority.  Since char is usually
 489  * signed, we are limited by 7 bits per byte.  To avoid zero, we need to add
 490  * XFRM_OFFSET, so we can't use a full 7 bits.  For simplicity, we choose 6
 491  * bits per byte.
 492  *
 493  * It turns out that we sometimes have real priorities that are
 494  * 31-bits wide.  (But: be careful using priorities where the high
 495  * order bit is set -- i.e. the priority is negative.  The sort order
 496  * may be surprising!)
 497  *
 498  * TODO: This would be a good area to optimize somewhat.  It turns out
 499  * that real prioririties *except for the last UNDEFINED pass* are generally
 500  * very small.  We need the localedef code to precalculate the max
 501  * priority for us, and ideally also give us a mask, and then we could
 502  * severely limit what we expand to.
 503  */
 504 #define XFRM_BYTES      6
 505 #define XFRM_OFFSET     ('0')   /* make all printable characters */
 506 #define XFRM_SHIFT      6
 507 #define XFRM_MASK       ((1 << XFRM_SHIFT) - 1)
 508 #define XFRM_SEP        ('.')   /* chosen to be less than XFRM_OFFSET */
 509
 510 static int
 511 xfrm(struct xlocale_collate *table, unsigned char *p, int pri, int pass)
 512 {
 513         /* we use unsigned to ensure zero fill on right shift */
 514         uint32_t val = (uint32_t)table->info->pri_count[pass];
 515         int nc = 0;
 516
 517         while (val) {
 518                 *p = (pri & XFRM_MASK) + XFRM_OFFSET;
 519                 pri >>= XFRM_SHIFT;
 520                 val >>= XFRM_SHIFT;
 521                 p++;
 522                 nc++;
 523         }
 524         return (nc);
 525 }
 526
 527 size_t
 528 _collate_sxfrm(struct xlocale_collate *table, const wchar_t *src, char *xf,
 529     size_t room)
 530 {
 531         int             pri;
 532         int             len;
 533         const wchar_t   *t;
 534         wchar_t         *tr = NULL;
 535         int             direc;
 536         int             pass;
 537         const int32_t   *state;
 538         size_t          want = 0;
 539         size_t          need = 0;
 540         int             b;
 541         uint8_t         buf[XFRM_BYTES];
 542
 543         for (pass = 0; pass <= table->info->directive_count; pass++) {
 544
 545                 state = NULL;
 546
 547                 if (pass != 0) {
 548                         /* insert level separator from the previous pass */
 549                         if (room) {
 550                                 *xf++ = XFRM_SEP;
 551                                 room--;
 552                         }
 553                         want++;
 554                 }
 555
 556                 /* special pass for undefined */
 557                 if (pass == table->info->directive_count) {
 558                         direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
 559                 } else {
 560                         direc = table->info->directive[pass];
 561                 }
 562
 563                 t = src;
 564
 565                 if (direc & DIRECTIVE_BACKWARD) {
 566                         wchar_t *bp, *fp, c;
 567                         if (tr)
 568                                 free(tr);
 569                         if ((tr = wcsdup(t)) == NULL) {
 570                                 errno = ENOMEM;
 571                                 goto fail;
 572                         }
 573                         bp = tr;
 574                         fp = tr + wcslen(tr) - 1;
 575                         while (bp < fp) {
 576                                 c = *bp;
 577                                 *bp++ = *fp;
 578                                 *fp-- = c;
 579                         }
 580                         t = (const wchar_t *)tr;
 581                 }
 582
 583                 if (direc & DIRECTIVE_POSITION) {
 584                         while (*t || state) {
 585
 586                                 _collate_lookup(table, t, &len, &pri, pass, &state);
 587                                 t += len;
 588                                 if (pri <= 0) {
 589                                         if (pri < 0) {
 590                                                 errno = EINVAL;
 591                                                 goto fail;
 592                                         }
 593                                         pri = COLLATE_MAX_PRIORITY;
 594                                 }
 595
 596                                 b = xfrm(table, buf, pri, pass);
 597                                 want += b;
 598                                 if (room) {
 599                                         while (b) {
 600                                                 b--;
 601                                                 if (room) {
 602                                                         *xf++ = buf[b];
 603                                                         room--;
 604                                                 }
 605                                         }
 606                                 }
 607                                 need = want;
 608                         }
 609                 } else {
 610                         while (*t || state) {
 611                                 _collate_lookup(table, t, &len, &pri, pass, &state);
 612                                 t += len;
 613                                 if (pri <= 0) {
 614                                         if (pri < 0) {
 615                                                 errno = EINVAL;
 616                                                 goto fail;
 617                                         }
 618                                         continue;
 619                                 }
 620
 621                                 b = xfrm(table, buf, pri, pass);
 622                                 want += b;
 623                                 if (room) {
 624
 625                                         while (b) {
 626                                                 b--;
 627                                                 if (room) {
 628                                                         *xf++ = buf[b];
 629                                                         room--;
 630                                                 }
 631                                         }
 632                                 }
 633                                 need = want;
 634                         }
 635                 }
 636         }
 637         if (tr)
 638                 free(tr);
 639         return (need);
 640
 641 fail:
 642         if (tr)
 643                 free(tr);
 644         return ((size_t)(-1));
 645 }