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 *
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 *
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 static collate_chain_t *
213 chainsearch(const struct lc_collate *lcc, const wchar_t *key, int *len)
214 {
215 int low = 0;
216 int high = lcc->lc_info->chain_count - 1;
217 int next, compar, l;
218 collate_chain_t *p;
219 collate_chain_t *tab = lcc->lc_chain_table;
220
221 if (high < 0)
222 return (NULL);
223
224 while (low <= high) {
225 next = (low + high) / 2;
226 p = tab + next;
227 compar = *key - *p->str;
228 if (compar == 0) {
229 l = wcsnlen(p->str, COLLATE_STR_LEN);
230 compar = wcsncmp(key, p->str, l);
231 if (compar == 0) {
232 *len = l;
233 return (p);
234 }
235 }
236 if (compar > 0)
237 low = next + 1;
238 else
239 high = next - 1;
240 }
241 return (NULL);
242 }
243
244 static collate_large_t *
245 largesearch(const struct lc_collate *lcc, const wchar_t key)
246 {
247 int low = 0;
248 int high = lcc->lc_info->large_count - 1;
249 int next, compar;
250 collate_large_t *p;
251 collate_large_t *tab = lcc->lc_large_table;
252
253 if (high < 0)
254 return (NULL);
255
256 while (low <= high) {
257 next = (low + high) / 2;
258 p = tab + next;
259 compar = key - p->val;
260 if (compar == 0)
261 return (p);
262 if (compar > 0)
263 low = next + 1;
264 else
265 high = next - 1;
266 }
267 return (NULL);
268 }
269
270 void
271 _collate_lookup(const struct lc_collate *lcc, const wchar_t *t,
272 int *len, int *pri, int which, const int **state)
273 {
274 collate_chain_t *p2;
275 collate_large_t *match;
276 int p, l;
277 const int *sptr;
278
279 /*
280 * If this is the "last" pass for the UNDEFINED, then
281 * we just return the priority itself.
282 */
283 if (which >= lcc->lc_directive_count) {
284 *pri = *t;
285 *len = 1;
286 *state = NULL;
287 return;
288 }
289
290 /*
291 * If we have remaining substitution data from a previous
292 * call, consume it first.
293 */
294 if ((sptr = *state) != NULL) {
295 *pri = *sptr;
296 sptr++;
297 if ((sptr == *state) || (sptr == NULL))
298 *state = NULL;
299 else
300 *state = sptr;
301 *len = 0;
302 return;
303 }
304
305 /* No active substitutions */
306 *len = 1;
307
308 /*
309 * Check for composites such as dipthongs that collate as a
310 * single element (aka chains or collating-elements).
311 */
312 if (((p2 = chainsearch(lcc, t, &l)) != NULL) &&
313 ((p = p2->pri[which]) >= 0)) {
314
315 *len = l;
316 *pri = p;
317
318 } else if (*t <= UCHAR_MAX) {
319
320 /*
321 * Character is a small (8-bit) character.
322 * We just look these up directly for speed.
323 */
324 *pri = lcc->lc_char_table[*t].pri[which];
325
326 } else if ((lcc->lc_info->large_count > 0) &&
327 ((match = largesearch(lcc, *t)) != NULL)) {
328
329 /*
330 * Character was found in the extended table.
331 */
332 *pri = match->pri.pri[which];
333
334 } else {
335 /*
336 * Character lacks a specific definition.
337 */
338 if (lcc->lc_directive[which] & DIRECTIVE_UNDEFINED) {
339 /* Mask off sign bit to prevent ordering confusion. */
340 *pri = (*t & COLLATE_MAX_PRIORITY);
341 } else {
342 *pri = lcc->lc_undef_pri[which];
343 }
344 /* No substitutions for undefined characters! */
345 return;
346 }
347
348 /*
349 * Try substituting (expanding) the character. We are
350 * currently doing this *after* the chain compression. I
351 * think it should not matter, but this way might be slightly
352 * faster.
353 *
354 * We do this after the priority search, as this will help us
355 * to identify a single key value. In order for this to work,
356 * its important that the priority assigned to a given element
357 * to be substituted be unique for that level. The localedef
358 * code ensures this for us.
359 */
360 if ((sptr = substsearch(lcc, *pri, which)) != NULL) {
361 if ((*pri = *sptr) > 0) {
362 sptr++;
363 *state = *sptr ? sptr : NULL;
364 }
365 }
366
367 }
368
369 /*
370 * This is the meaty part of wcsxfrm & strxfrm. Note that it does
371 * NOT NULL terminate. That is left to the caller.
372 */
373 size_t
374 _collate_wxfrm(const struct lc_collate *lcc, const wchar_t *src, wchar_t *xf,
375 size_t room)
376 {
377 int pri;
378 int len;
379 const wchar_t *t;
380 wchar_t *tr = NULL;
381 int direc;
382 int pass;
383 const int32_t *state;
384 size_t want = 0;
385 size_t need = 0;
386 int ndir = lcc->lc_directive_count;
387
388 assert(src);
389
390 for (pass = 0; pass <= ndir; pass++) {
391
392 state = NULL;
393
394 if (pass != 0) {
395 /* insert level separator from the previous pass */
396 if (room) {
397 *xf++ = 1;
398 room--;
399 }
400 want++;
401 }
402
403 /* special pass for undefined */
404 if (pass == ndir) {
405 direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
406 } else {
407 direc = lcc->lc_directive[pass];
408 }
409
410 t = src;
411
412 if (direc & DIRECTIVE_BACKWARD) {
413 wchar_t *bp, *fp, c;
414 if (tr)
415 free(tr);
416 if ((tr = wcsdup(t)) == NULL) {
417 errno = ENOMEM;
418 goto fail;
419 }
420 bp = tr;
421 fp = tr + wcslen(tr) - 1;
422 while (bp < fp) {
423 c = *bp;
424 *bp++ = *fp;
425 *fp-- = c;
426 }
427 t = (const wchar_t *)tr;
428 }
429
430 if (direc & DIRECTIVE_POSITION) {
431 while (*t || state) {
432 _collate_lookup(lcc, t, &len, &pri, pass,
433 &state);
434 t += len;
435 if (pri <= 0) {
436 if (pri < 0) {
437 errno = EINVAL;
438 goto fail;
439 }
440 state = NULL;
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 state = NULL;
461 continue;
462 }
463 if (room) {
464 *xf++ = pri;
465 room--;
466 }
467 want++;
468 need = want;
469 }
470 }
471 }
472
473 end:
474 if (tr)
475 free(tr);
476 return (need);
477
478 fail:
479 if (tr)
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(locale_t loc, 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)loc->collate->lc_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(const wchar_t *src, char *xf, size_t room, locale_t loc)
527 {
528 int pri;
529 int len;
530 const wchar_t *t;
531 wchar_t *tr = NULL;
532 int direc;
533 int pass;
534 const int32_t *state;
535 size_t want = 0;
536 size_t need = 0;
537 int b;
538 uint8_t buf[XFRM_BYTES];
539 const struct lc_collate *lcc = loc->collate;
540 int ndir = lcc->lc_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 = lcc->lc_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(lcc, t, &len, &pri, pass,
588 &state);
589 t += len;
590 if (pri <= 0) {
591 if (pri < 0) {
592 errno = EINVAL;
593 goto fail;
594 }
595 state = NULL;
596 pri = COLLATE_MAX_PRIORITY;
597 }
598
599 b = xfrm(loc, buf, pri, pass);
600 want += b;
601 if (room) {
602 while (b) {
603 b--;
604 if (room) {
605 *xf++ = buf[b];
606 room--;
607 }
608 }
609 }
610 need = want;
611 }
612 } else {
613 while (*t || state) {
614 _collate_lookup(lcc, t, &len, &pri, pass,
615 &state);
616 t += len;
617 if (pri <= 0) {
618 if (pri < 0) {
619 errno = EINVAL;
620 goto fail;
621 }
622 state = NULL;
623 continue;
624 }
625
626 b = xfrm(loc, buf, pri, pass);
627 want += b;
628 if (room) {
629
630 while (b) {
631 b--;
632 if (room) {
633 *xf++ = buf[b];
634 room--;
635 }
636 }
637 }
638 need = want;
639 }
640 }
641 }
642
643 end:
644 if (tr)
645 free(tr);
646 return (need);
647
648 fail:
649 if (tr)
650 free(tr);
651 return ((size_t)(-1));
652 }