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