lib/libc/locale/collate.c

   1 /*
   2  * Copyright 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 <assert.h>
  45 #include <sys/types.h>
  46 #include <sys/stat.h>
  47 #include <sys/mman.h>
  48 #include "un-namespace.h"
  49
  50 #include "collate.h"
  51 #include "setlocale.h"
  52 #include "ldpart.h"
  53
  54 struct xlocale_collate __xlocale_global_collate = {
  55         {{0}, "C"}, 1, 0, 0, 0
  56 };
  57
  58 struct xlocale_collate __xlocale_C_collate = {
  59         {{0}, "C"}, 1, 0, 0, 0
  60 };
  61
  62 #include "libc_private.h"
  63
  64 int
  65 __collate_load_tables_l(const char *encoding, struct xlocale_collate *table);
  66
  67 static void
  68 destruct_collate(void *t)
  69 {
  70         struct xlocale_collate *table = t;
  71         if (table->map && (table->maplen > 0)) {
  72                 (void) munmap(table->map, table->maplen);
  73         }
  74         free(t);
  75 }
  76
  77 void *
  78 __collate_load(const char *encoding, __unused locale_t unused)
  79 {
  80         if (strcmp(encoding, "C") == 0 || strcmp(encoding, "POSIX") == 0) {
  81                 return &__xlocale_C_collate;
  82         }
  83         struct xlocale_collate *table = calloc(sizeof(struct xlocale_collate), 1);
  84         table->header.header.destructor = destruct_collate;
  85         // FIXME: Make sure that _LDP_CACHE is never returned.  We should be doing
  86         // the caching outside of this section
  87         if (__collate_load_tables_l(encoding, table) != _LDP_LOADED) {
  88                 xlocale_release(table);
  89                 return NULL;
  90         }
  91         return table;
  92 }
  93
  94 /**
  95  * Load the collation tables for the specified encoding into the global table.
  96  */
  97 int
  98 __collate_load_tables(const char *encoding)
  99 {
 100         int ret = __collate_load_tables_l(encoding, &__xlocale_global_collate);
 101         return ret;
 102 }
 103
 104 int
 105 __collate_load_tables_l(const char *encoding, struct xlocale_collate *table)
 106 {
 107         int i, chains, z;
 108         char buf[PATH_MAX];
 109         char *TMP;
 110         char *map;
 111         collate_info_t *info;
 112         struct stat sbuf;
 113         int fd;
 114
 115         table->__collate_load_error = 1;
 116
 117         /* 'encoding' must be already checked. */
 118         if (strcmp(encoding, "C") == 0 || strcmp(encoding, "POSIX") == 0) {
 119                 return (_LDP_CACHE);
 120         }
 121
 122         (void) snprintf(buf, sizeof (buf), "%s/%s/LC_COLLATE",
 123             _PathLocale, encoding);
 124
 125         if ((fd = _open(buf, O_RDONLY)) < 0)
 126                 return (_LDP_ERROR);
 127         if (_fstat(fd, &sbuf) < 0) {
 128                 (void) _close(fd);
 129                 return (_LDP_ERROR);
 130         }
 131         if (sbuf.st_size < (COLLATE_STR_LEN + sizeof (info))) {
 132                 (void) _close(fd);
 133                 errno = EINVAL;
 134                 return (_LDP_ERROR);
 135         }
 136         map = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
 137         (void) _close(fd);
 138         if ((TMP = map) == NULL) {
 139                 return (_LDP_ERROR);
 140         }
 141
 142         if (strncmp(TMP, COLLATE_VERSION, COLLATE_STR_LEN) != 0) {
 143                 (void) munmap(map, sbuf.st_size);
 144                 errno = EINVAL;
 145                 return (_LDP_ERROR);
 146         }
 147         TMP += COLLATE_STR_LEN;
 148
 149         info = (void *)TMP;
 150         TMP += sizeof (*info);
 151
 152         if ((info->directive_count < 1) ||
 153             (info->directive_count >= COLL_WEIGHTS_MAX) ||
 154             ((chains = info->chain_count) < 0)) {
 155                 (void) munmap(map, sbuf.st_size);
 156                 errno = EINVAL;
 157                 return (_LDP_ERROR);
 158         }
 159
 160         i = (sizeof (collate_char_t) * (UCHAR_MAX + 1)) +
 161             (sizeof (collate_chain_t) * chains) +
 162             (sizeof (collate_large_t) * info->large_count);
 163         for (z = 0; z < info->directive_count; z++) {
 164                 i += sizeof (collate_subst_t) * info->subst_count[z];
 165         }
 166         if (i != (sbuf.st_size - (TMP - map))) {
 167                 (void) munmap(map, sbuf.st_size);
 168                 errno = EINVAL;
 169                 return (_LDP_ERROR);
 170         }
 171
 172         table->info = info;
 173         table->char_pri_table = (void *)TMP;
 174         TMP += sizeof (collate_char_t) * (UCHAR_MAX + 1);
 175
 176         for (z = 0; z < info->directive_count; z++) {
 177                 if (info->subst_count[z] > 0) {
 178                         table->subst_table[z] = (void *)TMP;
 179                         TMP += info->subst_count[z] * sizeof (collate_subst_t);
 180                 } else {
 181                         table->subst_table[z] = NULL;
 182                 }
 183         }
 184
 185         if (chains > 0) {
 186                 table->chain_pri_table = (void *)TMP;
 187                 TMP += chains * sizeof (collate_chain_t);
 188         } else
 189                 table->chain_pri_table = NULL;
 190         if (info->large_count > 0)
 191                 table->large_pri_table = (void *)TMP;
 192         else
 193                 table->large_pri_table = NULL;
 194
 195         table->__collate_load_error = 0;
 196         return (_LDP_LOADED);
 197 }
 198
 199 static const int32_t *
 200 substsearch(struct xlocale_collate *table, const wchar_t key, int pass)
 201 {
 202         const collate_subst_t *p;
 203         int n = table->info->subst_count[pass];
 204
 205         if (n == 0)
 206                 return (NULL);
 207
 208         if (pass >= table->info->directive_count)
 209                 return (NULL);
 210
 211         if (!(key & COLLATE_SUBST_PRIORITY))
 212                 return (NULL);
 213
 214         p = table->subst_table[pass] + (key & ~COLLATE_SUBST_PRIORITY);
 215         assert(p->key == key);
 216         return (p->pri);
 217 }
 218
 219 /*
 220  * Note: for performance reasons, we have expanded bsearch here.  This avoids
 221  * function call overhead with each comparison.
 222  */
 223
 224 static collate_chain_t *
 225 chainsearch(struct xlocale_collate *table, const wchar_t *key, int *len)
 226 {
 227         int low;
 228         int high;
 229         int next, compar, l;
 230         collate_chain_t *p;
 231         collate_chain_t *tab;
 232
 233         if (table->info->chain_count == 0)
 234                 return (NULL);
 235
 236         low = 0;
 237         high = table->info->chain_count - 1;
 238         tab = table->chain_pri_table;
 239
 240         while (low <= high) {
 241                 next = (low + high) / 2;
 242                 p = tab + next;
 243                 compar = *key - *p->str;
 244                 if (compar == 0) {
 245                         l = wcsnlen(p->str, COLLATE_STR_LEN);
 246                         compar = wcsncmp(key, p->str, l);
 247                         if (compar == 0) {
 248                                 *len = l;
 249                                 return (p);
 250                         }
 251                 }
 252                 if (compar > 0)
 253                         low = next + 1;
 254                 else
 255                         high = next - 1;
 256         }
 257         return (NULL);
 258 }
 259
 260 static collate_large_t *
 261 largesearch(struct xlocale_collate *table, const wchar_t key)
 262 {
 263         int low = 0;
 264         int high = table->info->large_count - 1;
 265         int next, compar;
 266         collate_large_t *p;
 267         collate_large_t *tab = table->large_pri_table;
 268
 269         if (table->info->large_count == 0)
 270                 return (NULL);
 271
 272         while (low <= high) {
 273                 next = (low + high) / 2;
 274                 p = tab + next;
 275                 compar = key - p->val;
 276                 if (compar == 0)
 277                         return (p);
 278                 if (compar > 0)
 279                         low = next + 1;
 280                 else
 281                         high = next - 1;
 282         }
 283         return (NULL);
 284 }
 285
 286 void
 287 _collate_lookup(struct xlocale_collate *table, const wchar_t *t, int *len,
 288     int *pri, int which, const int **state)
 289 {
 290         collate_chain_t *p2;
 291         collate_large_t *match;
 292         int p, l;
 293         const int *sptr;
 294
 295         /*
 296          * If this is the "last" pass for the UNDEFINED, then
 297          * we just return the priority itself.
 298          */
 299         if (which >= table->info->directive_count) {
 300                 *pri = *t;
 301                 *len = 1;
 302                 *state = NULL;
 303                 return;
 304         }
 305
 306         /*
 307          * If we have remaining substitution data from a previous
 308          * call, consume it first.
 309          */
 310         if ((sptr = *state) != NULL) {
 311                 *pri = *sptr;
 312                 sptr++;
 313                 *state = *sptr ? sptr : NULL;
 314                 *len = 0;
 315                 return;
 316         }
 317
 318         /* No active substitutions */
 319         *len = 1;
 320
 321         /*
 322          * Check for composites such as dipthongs that collate as a
 323          * single element (aka chains or collating-elements).
 324          */
 325         if (((p2 = chainsearch(table, t, &l)) != NULL) &&
 326             ((p = p2->pri[which]) >= 0)) {
 327
 328                 *len = l;
 329                 *pri = p;
 330
 331         } else if (*t <= UCHAR_MAX) {
 332
 333                 /*
 334                  * Character is a small (8-bit) character.
 335                  * We just look these up directly for speed.
 336                  */
 337                 *pri = table->char_pri_table[*t].pri[which];
 338
 339         } else if ((table->info->large_count > 0) &&
 340             ((match = largesearch(table, *t)) != NULL)) {
 341
 342                 /*
 343                  * Character was found in the extended table.
 344                  */
 345                 *pri = match->pri.pri[which];
 346
 347         } else {
 348                 /*
 349                  * Character lacks a specific definition.
 350                  */
 351                 if (table->info->directive[which] & DIRECTIVE_UNDEFINED) {
 352                         /* Mask off sign bit to prevent ordering confusion. */
 353                         *pri = (*t & COLLATE_MAX_PRIORITY);
 354                 } else {
 355                         *pri = table->info->undef_pri[which];
 356                 }
 357                 /* No substitutions for undefined characters! */
 358                 return;
 359         }
 360
 361         /*
 362          * Try substituting (expanding) the character.  We are
 363          * currently doing this *after* the chain compression.  I
 364          * think it should not matter, but this way might be slightly
 365          * faster.
 366          *
 367          * We do this after the priority search, as this will help us
 368          * to identify a single key value.  In order for this to work,
 369          * its important that the priority assigned to a given element
 370          * to be substituted be unique for that level.  The localedef
 371          * code ensures this for us.
 372          */
 373         if ((sptr = substsearch(table, *pri, which)) != NULL) {
 374                 if ((*pri = *sptr) != 0) {
 375                         sptr++;
 376                         *state = *sptr ? sptr : NULL;
 377                 }
 378         }
 379
 380 }
 381
 382 /*
 383  * This is the meaty part of wcsxfrm & strxfrm.  Note that it does
 384  * NOT NULL terminate.  That is left to the caller.
 385  */
 386 size_t
 387 _collate_wxfrm(struct xlocale_collate *table, const wchar_t *src, wchar_t *xf,
 388     size_t room)
 389 {
 390         int             pri;
 391         int             len;
 392         const wchar_t   *t;
 393         wchar_t         *tr = NULL;
 394         int             direc;
 395         int             pass;
 396         const int32_t   *state;
 397         size_t          want = 0;
 398         size_t          need = 0;
 399         int             ndir = table->info->directive_count;
 400
 401         assert(src);
 402
 403         for (pass = 0; pass <= ndir; pass++) {
 404
 405                 state = NULL;
 406
 407                 if (pass != 0) {
 408                         /* insert level separator from the previous pass */
 409                         if (room) {
 410                                 *xf++ = 1;
 411                                 room--;
 412                         }
 413                         want++;
 414                 }
 415
 416                 /* special pass for undefined */
 417                 if (pass == ndir) {
 418                         direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
 419                 } else {
 420                         direc = table->info->directive[pass];
 421                 }
 422
 423                 t = src;
 424
 425                 if (direc & DIRECTIVE_BACKWARD) {
 426                         wchar_t *bp, *fp, c;
 427                         if (tr)
 428                                 free(tr);
 429                         if ((tr = wcsdup(t)) == NULL) {
 430                                 errno = ENOMEM;
 431                                 goto fail;
 432                         }
 433                         bp = tr;
 434                         fp = tr + wcslen(tr) - 1;
 435                         while (bp < fp) {
 436                                 c = *bp;
 437                                 *bp++ = *fp;
 438                                 *fp-- = c;
 439                         }
 440                         t = (const wchar_t *)tr;
 441                 }
 442
 443                 if (direc & DIRECTIVE_POSITION) {
 444                         while (*t || state) {
 445                                 _collate_lookup(table, t, &len, &pri, pass, &state);
 446                                 t += len;
 447                                 if (pri <= 0) {
 448                                         if (pri < 0) {
 449                                                 errno = EINVAL;
 450                                                 goto fail;
 451                                         }
 452                                         pri = COLLATE_MAX_PRIORITY;
 453                                 }
 454                                 if (room) {
 455                                         *xf++ = pri;
 456                                         room--;
 457                                 }
 458                                 want++;
 459                                 need = want;
 460                         }
 461                 } else {
 462                         while (*t || state) {
 463                                 _collate_lookup(table, t, &len, &pri, pass, &state);
 464                                 t += len;
 465                                 if (pri <= 0) {
 466                                         if (pri < 0) {
 467                                                 errno = EINVAL;
 468                                                 goto fail;
 469                                         }
 470                                         continue;
 471                                 }
 472                                 if (room) {
 473                                         *xf++ = pri;
 474                                         room--;
 475                                 }
 476                                 want++;
 477                                 need = want;
 478                         }
 479                 }
 480         }
 481         free(tr);
 482         return (need);
 483
 484 fail:
 485         free(tr);
 486         return ((size_t)(-1));
 487 }
 488
 489 /*
 490  * In the non-POSIX case, we transform each character into a string of
 491  * characters representing the character's priority.  Since char is usually
 492  * signed, we are limited by 7 bits per byte.  To avoid zero, we need to add
 493  * XFRM_OFFSET, so we can't use a full 7 bits.  For simplicity, we choose 6
 494  * bits per byte.
 495  *
 496  * It turns out that we sometimes have real priorities that are
 497  * 31-bits wide.  (But: be careful using priorities where the high
 498  * order bit is set -- i.e. the priority is negative.  The sort order
 499  * may be surprising!)
 500  *
 501  * TODO: This would be a good area to optimize somewhat.  It turns out
 502  * that real prioririties *except for the last UNDEFINED pass* are generally
 503  * very small.  We need the localedef code to precalculate the max
 504  * priority for us, and ideally also give us a mask, and then we could
 505  * severely limit what we expand to.
 506  */
 507 #define XFRM_BYTES      6
 508 #define XFRM_OFFSET     ('0')   /* make all printable characters */
 509 #define XFRM_SHIFT      6
 510 #define XFRM_MASK       ((1 << XFRM_SHIFT) - 1)
 511 #define XFRM_SEP        ('.')   /* chosen to be less than XFRM_OFFSET */
 512
 513 static int
 514 xfrm(struct xlocale_collate *table, unsigned char *p, int pri, int pass)
 515 {
 516         /* we use unsigned to ensure zero fill on right shift */
 517         uint32_t val = (uint32_t)table->info->pri_count[pass];
 518         int nc = 0;
 519
 520         while (val) {
 521                 *p = (pri & XFRM_MASK) + XFRM_OFFSET;
 522                 pri >>= XFRM_SHIFT;
 523                 val >>= XFRM_SHIFT;
 524                 p++;
 525                 nc++;
 526         }
 527         return (nc);
 528 }
 529
 530 size_t
 531 _collate_sxfrm(struct xlocale_collate *table, const wchar_t *src, char *xf,
 532     size_t room)
 533 {
 534         int             pri;
 535         int             len;
 536         const wchar_t   *t;
 537         wchar_t         *tr = NULL;
 538         int             direc;
 539         int             pass;
 540         const int32_t   *state;
 541         size_t          want = 0;
 542         size_t          need = 0;
 543         int             b;
 544         uint8_t         buf[XFRM_BYTES];
 545         int             ndir = table->info->directive_count;
 546
 547         assert(src);
 548
 549         for (pass = 0; pass <= ndir; pass++) {
 550
 551                 state = NULL;
 552
 553                 if (pass != 0) {
 554                         /* insert level separator from the previous pass */
 555                         if (room) {
 556                                 *xf++ = XFRM_SEP;
 557                                 room--;
 558                         }
 559                         want++;
 560                 }
 561
 562                 /* special pass for undefined */
 563                 if (pass == ndir) {
 564                         direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
 565                 } else {
 566                         direc = table->info->directive[pass];
 567                 }
 568
 569                 t = src;
 570
 571                 if (direc & DIRECTIVE_BACKWARD) {
 572                         wchar_t *bp, *fp, c;
 573                         if (tr)
 574                                 free(tr);
 575                         if ((tr = wcsdup(t)) == NULL) {
 576                                 errno = ENOMEM;
 577                                 goto fail;
 578                         }
 579                         bp = tr;
 580                         fp = tr + wcslen(tr) - 1;
 581                         while (bp < fp) {
 582                                 c = *bp;
 583                                 *bp++ = *fp;
 584                                 *fp-- = c;
 585                         }
 586                         t = (const wchar_t *)tr;
 587                 }
 588
 589                 if (direc & DIRECTIVE_POSITION) {
 590                         while (*t || state) {
 591
 592                                 _collate_lookup(table, t, &len, &pri, pass, &state);
 593                                 t += len;
 594                                 if (pri <= 0) {
 595                                         if (pri < 0) {
 596                                                 errno = EINVAL;
 597                                                 goto fail;
 598                                         }
 599                                         pri = COLLATE_MAX_PRIORITY;
 600                                 }
 601
 602                                 b = xfrm(table, buf, pri, pass);
 603                                 want += b;
 604                                 if (room) {
 605                                         while (b) {
 606                                                 b--;
 607                                                 if (room) {
 608                                                         *xf++ = buf[b];
 609                                                         room--;
 610                                                 }
 611                                         }
 612                                 }
 613                                 need = want;
 614                         }
 615                 } else {
 616                         while (*t || state) {
 617                                 _collate_lookup(table, t, &len, &pri, pass, &state);
 618                                 t += len;
 619                                 if (pri <= 0) {
 620                                         if (pri < 0) {
 621                                                 errno = EINVAL;
 622                                                 goto fail;
 623                                         }
 624                                         continue;
 625                                 }
 626
 627                                 b = xfrm(table, buf, pri, pass);
 628                                 want += b;
 629                                 if (room) {
 630
 631                                         while (b) {
 632                                                 b--;
 633                                                 if (room) {
 634                                                         *xf++ = buf[b];
 635                                                         room--;
 636                                                 }
 637                                         }
 638                                 }
 639                                 need = want;
 640                         }
 641                 }
 642         }
 643         free(tr);
 644         return (need);
 645
 646 fail:
 647         free(tr);
 648         return ((size_t)(-1));
 649 }
 650
 651 /*
 652  * __collate_equiv_value returns the primary collation value for the given
 653  * collating symbol specified by str and len.  Zero or negative is returned
 654  * if the collating symbol was not found.  This function is used by bracket
 655  * code in the TRE regex library.
 656  */
 657 int
 658 __collate_equiv_value(locale_t locale, const wchar_t *str, size_t len)
 659 {
 660         int32_t e;
 661
 662         if (len < 1 || len >= COLLATE_STR_LEN)
 663                 return (-1);
 664
 665         FIX_LOCALE(locale);
 666         struct xlocale_collate *table =
 667                 (struct xlocale_collate*)locale->components[XLC_COLLATE];
 668
 669         if (table->__collate_load_error)
 670                 return ((len == 1 && *str <= UCHAR_MAX) ? *str : -1);
 671
 672         if (len == 1) {
 673                 e = -1;
 674                 if (*str <= UCHAR_MAX)
 675                         e = table->char_pri_table[*str].pri[0];
 676                 else if (table->info->large_count > 0) {
 677                         collate_large_t *match_large;
 678                         match_large = largesearch(table, *str);
 679                         if (match_large)
 680                                 e = match_large->pri.pri[0];
 681                 }
 682                 if (e == 0)
 683                         return (1);
 684                 return (e > 0 ? e : 0);
 685         }
 686         if (table->info->chain_count > 0) {
 687                 wchar_t name[COLLATE_STR_LEN];
 688                 collate_chain_t *match_chain;
 689                 int clen;
 690
 691                 wcsncpy (name, str, len);
 692                 name[len] = 0;
 693                 match_chain = chainsearch(table, name, &clen);
 694                 if (match_chain) {
 695                         e = match_chain->pri[0];
 696                         if (e == 0)
 697                                 return (1);
 698                         return (e < 0 ? -e : e);
 699                 }
 700         }
 701         return (0);
 702 }