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