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