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 "localeimpl.h"
48
49 /* Check file format vs libc runtime. (See collatefile.h) */
50 #if COLL_WEIGHTS_MAX != COLLATE_WEIGHTS_MAX
51 #error "COLL_WEIGHTS_MAX != COLLATE_WEIGHTS_MAX"
52 #endif
53
54 /*
55 * See the comments in usr/src/cmd/localedef/collate.c for further
56 * information. It would also be very helpful to have a copy of the
57 * POSIX standard for collation (in the locale format manual page)
58 * handy (www.opengroup.org).
59 */
60
61 /*
62 * POSIX uses empty tables and falls down to strcmp.
63 */
64 struct lc_collate lc_collate_posix = {
65 .lc_is_posix = 1,
66 };
67
68 struct locdata __posix_collate_locdata = {
69 .l_lname = "C",
70 .l_data = { &lc_collate_posix }
71 };
72
73
74 struct locdata *
__lc_collate_load(const char * locname)75 __lc_collate_load(const char *locname)
76 {
77 int i, chains, z;
78 char buf[PATH_MAX];
79 char *TMP;
80 char *map;
81 collate_info_t *info;
82 struct stat sbuf;
83 int fd;
84 struct locdata *ldata;
85 struct lc_collate *lcc;
86
87 /*
88 * Slurp the locale file into the cache.
89 */
90
91 (void) snprintf(buf, sizeof (buf), "%s/%s/LC_COLLATE/LCL_DATA",
92 _PathLocale, locname);
93
94 if ((fd = open(buf, O_RDONLY)) < 0) {
95 errno = EINVAL;
96 return (NULL);
97 }
98 if (fstat(fd, &sbuf) < 0) {
99 (void) close(fd);
100 errno = EINVAL;
101 return (NULL);
102 }
103 if (sbuf.st_size < (COLLATE_STR_LEN + sizeof (info))) {
104 (void) close(fd);
105 errno = EINVAL;
106 return (NULL);
107 }
108 map = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
109 (void) close(fd);
110 if ((TMP = map) == NULL) {
111 errno = EINVAL;
112 return (NULL);
113 }
114
115 if (strncmp(TMP, COLLATE_VERSION, COLLATE_STR_LEN) != 0) {
116 (void) munmap(map, sbuf.st_size);
117 errno = EINVAL;
118 return (NULL);
119 }
120 TMP += COLLATE_STR_LEN;
121
122 info = (void *)TMP;
123 TMP += sizeof (*info);
124
125 if ((info->directive_count < 1) ||
126 (info->directive_count >= COLL_WEIGHTS_MAX) ||
127 ((chains = info->chain_count) < 0)) {
128 (void) munmap(map, sbuf.st_size);
129 errno = EINVAL;
130 return (NULL);
131 }
132
133 i = (sizeof (collate_char_t) * (UCHAR_MAX + 1)) +
134 (sizeof (collate_chain_t) * chains) +
135 (sizeof (collate_large_t) * info->large_count);
136 for (z = 0; z < info->directive_count; z++) {
137 i += sizeof (collate_subst_t) * info->subst_count[z];
138 }
139 if (i != (sbuf.st_size - (TMP - map))) {
140 (void) munmap(map, sbuf.st_size);
141 errno = EINVAL;
142 return (NULL);
143 }
144
145
146 if ((ldata = __locdata_alloc(locname, sizeof (*lcc))) == NULL) {
147 (void) munmap(map, sbuf.st_size);
148 return (NULL);
149 }
150 lcc = ldata->l_data[0];
151 ldata->l_map = map;
152 ldata->l_map_len = sbuf.st_size;
153
154 lcc->lc_info = info;
155 lcc->lc_directive_count = info->directive_count;
156 lcc->lc_large_count = info->large_count;
157
158 for (z = 0; z < COLL_WEIGHTS_MAX; z++) {
159 lcc->lc_directive[z] = info->directive[z];
160 lcc->lc_subst_count[z] = info->subst_count[z];
161 lcc->lc_pri_count[z] = info->pri_count[z];
162 lcc->lc_undef_pri[z] = info->undef_pri[z];
163 }
164
165 lcc->lc_char_table = (void *)TMP;
166 TMP += sizeof (collate_char_t) * (UCHAR_MAX + 1);
167
168 for (z = 0; z < lcc->lc_directive_count; z++) {
169 int count;
170 if ((count = lcc->lc_subst_count[z]) > 0) {
171 lcc->lc_subst_table[z] = (void *)TMP;
172 TMP += count * sizeof (collate_subst_t);
173 } else {
174 lcc->lc_subst_table[z] = NULL;
175 }
176 }
177
178 if (chains > 0) {
179 lcc->lc_chain_table = (void *)TMP;
180 TMP += chains * sizeof (collate_chain_t);
181 } else
182 lcc->lc_chain_table = NULL;
183 lcc->lc_chain_count = chains;
184 if (lcc->lc_large_count > 0)
185 lcc->lc_large_table = (void *)TMP;
186 else
187 lcc->lc_large_table = NULL;
188
189 return (ldata);
190 }
191
192 static const int32_t *
substsearch(const struct lc_collate * lcc,const wchar_t key,int pass)193 substsearch(const struct lc_collate *lcc, const wchar_t key, int pass)
194 {
195 const collate_subst_t *p;
196 int n = lcc->lc_subst_count[pass];
197
198 if (n == 0)
199 return (NULL);
200
201 if (pass >= lcc->lc_directive_count)
202 return (NULL);
203
204 if (!(key & COLLATE_SUBST_PRIORITY))
205 return (NULL);
206
207 p = lcc->lc_subst_table[pass] + (key & ~COLLATE_SUBST_PRIORITY);
208 assert(p->key == key);
209 return (p->pri);
210 }
211
212 /*
213 * Note: for performance reasons, we have expanded bsearch here. This avoids
214 * function call overhead with each comparison.
215 */
216
217 static collate_chain_t *
chainsearch(const struct lc_collate * lcc,const wchar_t * key,int * len)218 chainsearch(const struct lc_collate *lcc, const wchar_t *key, int *len)
219 {
220 int low;
221 int high;
222 int next, compar, l;
223 collate_chain_t *p;
224 collate_chain_t *tab;
225
226 if (lcc->lc_info->chain_count == 0)
227 return (NULL);
228
229 low = 0;
230 high = lcc->lc_info->chain_count - 1;
231 tab = lcc->lc_chain_table;
232
233 while (low <= high) {
234 next = (low + high) / 2;
235 p = tab + next;
236 compar = *key - *p->str;
237 if (compar == 0) {
238 l = wcsnlen(p->str, COLLATE_STR_LEN);
239 compar = wcsncmp(key, p->str, l);
240 if (compar == 0) {
241 *len = l;
242 return (p);
243 }
244 }
245 if (compar > 0)
246 low = next + 1;
247 else
248 high = next - 1;
249 }
250 return (NULL);
251 }
252
253 static collate_large_t *
largesearch(const struct lc_collate * lcc,const wchar_t key)254 largesearch(const struct lc_collate *lcc, const wchar_t key)
255 {
256 int low = 0;
257 int high = lcc->lc_info->large_count - 1;
258 int next, compar;
259 collate_large_t *p;
260 collate_large_t *tab = lcc->lc_large_table;
261
262 if (lcc->lc_info->large_count == 0)
263 return (NULL);
264
265 while (low <= high) {
266 next = (low + high) / 2;
267 p = tab + next;
268 compar = key - p->val;
269 if (compar == 0)
270 return (p);
271 if (compar > 0)
272 low = next + 1;
273 else
274 high = next - 1;
275 }
276 return (NULL);
277 }
278
279 void
_collate_lookup(const struct lc_collate * lcc,const wchar_t * t,int * len,int * pri,int which,const int ** state)280 _collate_lookup(const struct lc_collate *lcc, const wchar_t *t,
281 int *len, int *pri, int which, const int **state)
282 {
283 collate_chain_t *p2;
284 collate_large_t *match;
285 int p, l;
286 const int *sptr;
287
288 /*
289 * If this is the "last" pass for the UNDEFINED, then
290 * we just return the priority itself.
291 */
292 if (which >= lcc->lc_directive_count) {
293 *pri = *t;
294 *len = 1;
295 *state = NULL;
296 return;
297 }
298
299 /*
300 * If we have remaining substitution data from a previous
301 * call, consume it first.
302 */
303 if ((sptr = *state) != NULL) {
304 *pri = *sptr;
305 sptr++;
306 *state = *sptr ? sptr : NULL;
307 *len = 0;
308 return;
309 }
310
311 /* No active substitutions */
312 *len = 1;
313
314 /*
315 * Check for composites such as dipthongs that collate as a
316 * single element (aka chains or collating-elements).
317 */
318 if (((p2 = chainsearch(lcc, 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 = lcc->lc_char_table[*t].pri[which];
331
332 } else if ((lcc->lc_info->large_count > 0) &&
333 ((match = largesearch(lcc, *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 (lcc->lc_directive[which] & DIRECTIVE_UNDEFINED) {
345 /* Mask off sign bit to prevent ordering confusion. */
346 *pri = (*t & COLLATE_MAX_PRIORITY);
347 } else {
348 *pri = lcc->lc_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(lcc, *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
_collate_wxfrm(const struct lc_collate * lcc,const wchar_t * src,wchar_t * xf,size_t room)380 _collate_wxfrm(const struct lc_collate *lcc, 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 = lcc->lc_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 = lcc->lc_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(lcc, t, &len, &pri, pass,
439 &state);
440 t += len;
441 if (pri <= 0) {
442 if (pri < 0) {
443 errno = EINVAL;
444 goto fail;
445 }
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(lcc, t, &len, &pri, pass,
458 &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
477 end:
478 if (tr)
479 free(tr);
480 return (need);
481
482 fail:
483 if (tr)
484 free(tr);
485 return ((size_t)(-1));
486 }
487
488 /*
489 * In the non-POSIX case, we transform each character into a string of
490 * characters representing the character's priority. Since char is usually
491 * signed, we are limited by 7 bits per byte. To avoid zero, we need to add
492 * XFRM_OFFSET, so we can't use a full 7 bits. For simplicity, we choose 6
493 * bits per byte.
494 *
495 * It turns out that we sometimes have real priorities that are
496 * 31-bits wide. (But: be careful using priorities where the high
497 * order bit is set -- i.e. the priority is negative. The sort order
498 * may be surprising!)
499 *
500 * TODO: This would be a good area to optimize somewhat. It turns out
501 * that real prioririties *except for the last UNDEFINED pass* are generally
502 * very small. We need the localedef code to precalculate the max
503 * priority for us, and ideally also give us a mask, and then we could
504 * severely limit what we expand to.
505 */
506 #define XFRM_BYTES 6
507 #define XFRM_OFFSET ('0') /* make all printable characters */
508 #define XFRM_SHIFT 6
509 #define XFRM_MASK ((1 << XFRM_SHIFT) - 1)
510 #define XFRM_SEP ('.') /* chosen to be less than XFRM_OFFSET */
511
512 static int
xfrm(locale_t loc,unsigned char * p,int pri,int pass)513 xfrm(locale_t loc, unsigned char *p, int pri, int pass)
514 {
515 /* we use unsigned to ensure zero fill on right shift */
516 uint32_t val = (uint32_t)loc->collate->lc_pri_count[pass];
517 int nc = 0;
518
519 while (val) {
520 *p = (pri & XFRM_MASK) + XFRM_OFFSET;
521 pri >>= XFRM_SHIFT;
522 val >>= XFRM_SHIFT;
523 p++;
524 nc++;
525 }
526 return (nc);
527 }
528
529 size_t
_collate_sxfrm(const wchar_t * src,char * xf,size_t room,locale_t loc)530 _collate_sxfrm(const wchar_t *src, char *xf, size_t room, locale_t loc)
531 {
532 int pri;
533 int len;
534 const wchar_t *t;
535 wchar_t *tr = NULL;
536 int direc;
537 int pass;
538 const int32_t *state;
539 size_t want = 0;
540 size_t need = 0;
541 int b;
542 uint8_t buf[XFRM_BYTES];
543 const struct lc_collate *lcc = loc->collate;
544 int ndir = lcc->lc_directive_count;
545
546 assert(src);
547
548 for (pass = 0; pass <= ndir; pass++) {
549
550 state = NULL;
551
552 if (pass != 0) {
553 /* insert level separator from the previous pass */
554 if (room) {
555 *xf++ = XFRM_SEP;
556 room--;
557 }
558 want++;
559 }
560
561 /* special pass for undefined */
562 if (pass == ndir) {
563 direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
564 } else {
565 direc = lcc->lc_directive[pass];
566 }
567
568 t = src;
569
570 if (direc & DIRECTIVE_BACKWARD) {
571 wchar_t *bp, *fp, c;
572 if (tr)
573 free(tr);
574 if ((tr = wcsdup(t)) == NULL) {
575 errno = ENOMEM;
576 goto fail;
577 }
578 bp = tr;
579 fp = tr + wcslen(tr) - 1;
580 while (bp < fp) {
581 c = *bp;
582 *bp++ = *fp;
583 *fp-- = c;
584 }
585 t = (const wchar_t *)tr;
586 }
587
588 if (direc & DIRECTIVE_POSITION) {
589 while (*t || state) {
590
591 _collate_lookup(lcc, t, &len, &pri, pass,
592 &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(loc, 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(lcc, t, &len, &pri, pass,
618 &state);
619 t += len;
620 if (pri <= 0) {
621 if (pri < 0) {
622 errno = EINVAL;
623 goto fail;
624 }
625 continue;
626 }
627
628 b = xfrm(loc, buf, pri, pass);
629 want += b;
630 if (room) {
631
632 while (b) {
633 b--;
634 if (room) {
635 *xf++ = buf[b];
636 room--;
637 }
638 }
639 }
640 need = want;
641 }
642 }
643 }
644
645 end:
646 if (tr)
647 free(tr);
648 return (need);
649
650 fail:
651 if (tr)
652 free(tr);
653 return ((size_t)(-1));
654 }
655