1 /*
2 * Copright 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 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29 #include "lint.h"
30 #include "file64.h"
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <stddef.h>
34 #include <string.h>
35 #include <wchar.h>
36 #include <errno.h>
37 #include <unistd.h>
38 #include <ctype.h>
39 #include <unistd.h>
40 #include <fcntl.h>
41 #include <assert.h>
42 #include <sys/stat.h>
43 #include <sys/mman.h>
44
45 #include "collate.h"
46 #include "setlocale.h"
47 #include "ldpart.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 static collate_subst_t *subst_table[COLL_WEIGHTS_MAX];
57 static collate_char_t *char_pri_table;
58 static collate_large_t *large_pri_table;
59 static collate_chain_t *chain_pri_table;
60 static char *cache = NULL;
61 static size_t cachesz;
62 static char collate_encoding[ENCODING_LEN + 1];
63
64 /* Exposed externally to other parts of libc. */
65 collate_info_t *_collate_info;
66 int _collate_load_error = 1;
67
68
69 int
70 _collate_load_tables(const char *encoding)
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
80 /* 'encoding' must be already checked. */
81 if (strcmp(encoding, "C") == 0 || strcmp(encoding, "POSIX") == 0) {
82 _collate_load_error = 1;
83 return (_LDP_CACHE);
84 }
85
86 /*
87 * If the locale name is the same as our cache, use the cache.
88 */
89 if (cache && (strncmp(encoding, collate_encoding, ENCODING_LEN) == 0)) {
90 _collate_load_error = 0;
91 return (_LDP_CACHE);
92 }
93
94 /*
95 * Slurp the locale file into the cache.
96 */
97
98 (void) snprintf(buf, sizeof (buf), "%s/%s/LC_COLLATE/LCL_DATA",
99 _PathLocale, encoding);
100
101 if ((fd = open(buf, O_RDONLY)) < 0)
102 return (_LDP_ERROR);
103 if (fstat(fd, &sbuf) < 0) {
104 (void) close(fd);
105 return (_LDP_ERROR);
106 }
107 if (sbuf.st_size < (COLLATE_STR_LEN + sizeof (info))) {
108 (void) close(fd);
109 errno = EINVAL;
110 return (_LDP_ERROR);
111 }
112 map = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
113 (void) close(fd);
114 if ((TMP = map) == NULL) {
115 return (_LDP_ERROR);
116 }
117
118 if (strncmp(TMP, COLLATE_VERSION, COLLATE_STR_LEN) != 0) {
119 (void) munmap(map, sbuf.st_size);
120 errno = EINVAL;
121 return (_LDP_ERROR);
122 }
123 TMP += COLLATE_STR_LEN;
124
125 info = (void *)TMP;
126 TMP += sizeof (*info);
127
128 if ((info->directive_count < 1) ||
129 (info->directive_count >= COLL_WEIGHTS_MAX) ||
130 ((chains = info->chain_count) < 0)) {
131 (void) munmap(map, sbuf.st_size);
132 errno = EINVAL;
133 return (_LDP_ERROR);
134 }
135
136 i = (sizeof (collate_char_t) * (UCHAR_MAX + 1)) +
137 (sizeof (collate_chain_t) * chains) +
138 (sizeof (collate_large_t) * info->large_count);
139 for (z = 0; z < (info->directive_count); z++) {
140 i += sizeof (collate_subst_t) * info->subst_count[z];
141 }
142 if (i != (sbuf.st_size - (TMP - map))) {
143 (void) munmap(map, sbuf.st_size);
144 errno = EINVAL;
145 return (_LDP_ERROR);
146 }
147
148 char_pri_table = (void *)TMP;
149 TMP += sizeof (collate_char_t) * (UCHAR_MAX + 1);
150
151 for (z = 0; z < info->directive_count; z++) {
152 if (info->subst_count[z] > 0) {
153 subst_table[z] = (void *)TMP;
154 TMP += info->subst_count[z] * sizeof (collate_subst_t);
155 } else {
156 subst_table[z] = NULL;
157 }
158 }
159
160 if (chains > 0) {
161 chain_pri_table = (void *)TMP;
162 TMP += chains * sizeof (collate_chain_t);
163 } else
164 chain_pri_table = NULL;
165 if (info->large_count > 0)
166 large_pri_table = (void *)TMP;
167 else
168 large_pri_table = NULL;
169
170 (void) strlcpy(collate_encoding, encoding, ENCODING_LEN);
171 _collate_info = info;
172
173 if (cache)
174 (void) munmap(cache, cachesz);
175
176 cache = map;
177 cachesz = sbuf.st_size;
178 _collate_load_error = 0;
179
180 return (_LDP_LOADED);
181 }
182
183 static int32_t *
184 substsearch(const wchar_t key, int pass)
185 {
186 collate_subst_t *p;
187 int n = _collate_info->subst_count[pass];
188
189 if (n == 0)
190 return (NULL);
191
192 if (pass >= _collate_info->directive_count)
193 return (NULL);
194
195 if (!(key & COLLATE_SUBST_PRIORITY))
196 return (NULL);
197
198 p = subst_table[pass] + (key & ~COLLATE_SUBST_PRIORITY);
199 assert(p->key == key);
200 return (p->pri);
201 }
202
203 /*
204 * Note: for performance reasons, we have expanded bsearch here. This avoids
205 * function call overhead with each comparison.
206 */
207
208 static collate_chain_t *
209 chainsearch(const wchar_t *key, int *len)
210 {
211 int low;
212 int high;
213 int next, compar, l;
214 collate_chain_t *p;
215 collate_chain_t *tab;
216
217 if (_collate_info->chain_count == 0)
218 return (NULL);
219
220 low = 0;
221 high = _collate_info->chain_count - 1;
222 tab = chain_pri_table;
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 wchar_t key)
246 {
247 int low = 0;
248 int high = _collate_info->large_count - 1;
249 int next, compar;
250 collate_large_t *p;
251 collate_large_t *tab = large_pri_table;
252
253 if (_collate_info->large_count == 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 wchar_t *t, int *len, int *pri, int which, int **state)
272 {
273 collate_chain_t *p2;
274 collate_large_t *match;
275 collate_info_t *info = _collate_info;
276 int p, l;
277 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 >= info->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 *state = *sptr ? sptr : NULL;
298 *len = 0;
299 return;
300 }
301
302 /* No active substitutions */
303 *len = 1;
304
305 /*
306 * Check for composites such as dipthongs that collate as a
307 * single element (aka chains or collating-elements).
308 */
309 if (((p2 = chainsearch(t, &l)) != NULL) &&
310 ((p = p2->pri[which]) >= 0)) {
311
312 *len = l;
313 *pri = p;
314
315 } else if (*t <= UCHAR_MAX) {
316
317 /*
318 * Character is a small (8-bit) character.
319 * We just look these up directly for speed.
320 */
321 *pri = char_pri_table[*t].pri[which];
322
323 } else if ((info->large_count > 0) &&
324 ((match = largesearch(*t)) != NULL)) {
325
326 /*
327 * Character was found in the extended table.
328 */
329 *pri = match->pri.pri[which];
330
331 } else {
332 /*
333 * Character lacks a specific definition.
334 */
335 if (info->directive[which] & DIRECTIVE_UNDEFINED) {
336 /* Mask off sign bit to prevent ordering confusion. */
337 *pri = (*t & COLLATE_MAX_PRIORITY);
338 } else {
339 *pri = info->undef_pri[which];
340 }
341 /* No substitutions for undefined characters! */
342 return;
343 }
344
345 /*
346 * Try substituting (expanding) the character. We are
347 * currently doing this *after* the chain compression. I
348 * think it should not matter, but this way might be slightly
349 * faster.
350 *
351 * We do this after the priority search, as this will help us
352 * to identify a single key value. In order for this to work,
353 * its important that the priority assigned to a given element
354 * to be substituted be unique for that level. The localedef
355 * code ensures this for us.
356 */
357 if ((sptr = substsearch(*pri, which)) != NULL) {
358 if ((*pri = *sptr) != 0) {
359 sptr++;
360 *state = *sptr ? sptr : NULL;
361 }
362 }
363
364 }
365
366 /*
367 * This is the meaty part of wcsxfrm & strxfrm. Note that it does
368 * NOT NULL terminate. That is left to the caller.
369 */
370 size_t
371 _collate_wxfrm(const wchar_t *src, wchar_t *xf, size_t room)
372 {
373 int pri;
374 int len;
375 const wchar_t *t;
376 wchar_t *tr = NULL;
377 int direc;
378 int pass;
379 int32_t *state;
380 size_t want = 0;
381 size_t need = 0;
382
383 assert(src);
384
385 for (pass = 0; pass <= _collate_info->directive_count; pass++) {
386
387 state = NULL;
388
389 if (pass != 0) {
390 /* insert level separator from the previous pass */
391 if (room) {
392 *xf++ = 1;
393 room--;
394 }
395 want++;
396 }
397
398 /* special pass for undefined */
399 if (pass == _collate_info->directive_count) {
400 direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
401 } else {
402 direc = _collate_info->directive[pass];
403 }
404
405 t = src;
406
407 if (direc & DIRECTIVE_BACKWARD) {
408 wchar_t *bp, *fp, c;
409 if (tr)
410 free(tr);
411 if ((tr = wcsdup(t)) == NULL) {
412 errno = ENOMEM;
413 goto fail;
414 }
415 bp = tr;
416 fp = tr + wcslen(tr) - 1;
417 while (bp < fp) {
418 c = *bp;
419 *bp++ = *fp;
420 *fp-- = c;
421 }
422 t = (const wchar_t *)tr;
423 }
424
425 if (direc & DIRECTIVE_POSITION) {
426 while (*t || state) {
427 _collate_lookup(t, &len, &pri, pass, &state);
428 t += len;
429 if (pri <= 0) {
430 if (pri < 0) {
431 errno = EINVAL;
432 goto fail;
433 }
434 pri = COLLATE_MAX_PRIORITY;
435 }
436 if (room) {
437 *xf++ = pri;
438 room--;
439 }
440 want++;
441 need = want;
442 }
443 } else {
444 while (*t || state) {
445 _collate_lookup(t, &len, &pri, pass, &state);
446 t += len;
447 if (pri <= 0) {
448 if (pri < 0) {
449 errno = EINVAL;
450 goto fail;
451 }
452 continue;
453 }
454 if (room) {
455 *xf++ = pri;
456 room--;
457 }
458 want++;
459 need = want;
460 }
461 }
462 }
463
464 end:
465 if (tr)
466 free(tr);
467 return (need);
468
469 fail:
470 if (tr)
471 free(tr);
472 return ((size_t)(-1));
473 }
474
475 /*
476 * In the non-POSIX case, we transform each character into a string of
477 * characters representing the character's priority. Since char is usually
478 * signed, we are limited by 7 bits per byte. To avoid zero, we need to add
479 * XFRM_OFFSET, so we can't use a full 7 bits. For simplicity, we choose 6
480 * bits per byte.
481 *
482 * It turns out that we sometimes have real priorities that are
483 * 31-bits wide. (But: be careful using priorities where the high
484 * order bit is set -- i.e. the priority is negative. The sort order
485 * may be surprising!)
486 *
487 * TODO: This would be a good area to optimize somewhat. It turns out
488 * that real prioririties *except for the last UNDEFINED pass* are generally
489 * very small. We need the localedef code to precalculate the max
490 * priority for us, and ideally also give us a mask, and then we could
491 * severely limit what we expand to.
492 */
493 #define XFRM_BYTES 6
494 #define XFRM_OFFSET ('0') /* make all printable characters */
495 #define XFRM_SHIFT 6
496 #define XFRM_MASK ((1 << XFRM_SHIFT) - 1)
497 #define XFRM_SEP ('.') /* chosen to be less than XFRM_OFFSET */
498
499 static int
500 xfrm(unsigned char *p, int pri, int pass)
501 {
502 /* we use unsigned to ensure zero fill on right shift */
503 uint32_t val = (uint32_t)_collate_info->pri_count[pass];
504 int nc = 0;
505
506 while (val) {
507 *p = (pri & XFRM_MASK) + XFRM_OFFSET;
508 pri >>= XFRM_SHIFT;
509 val >>= XFRM_SHIFT;
510 p++;
511 nc++;
512 }
513 return (nc);
514 }
515
516 size_t
517 _collate_sxfrm(const wchar_t *src, char *xf, size_t room)
518 {
519 int pri;
520 int len;
521 const wchar_t *t;
522 wchar_t *tr = NULL;
523 int direc;
524 int pass;
525 int32_t *state;
526 size_t want = 0;
527 size_t need = 0;
528 int b;
529 uint8_t buf[XFRM_BYTES];
530
531 assert(src);
532
533 for (pass = 0; pass <= _collate_info->directive_count; pass++) {
534
535 state = NULL;
536
537 if (pass != 0) {
538 /* insert level separator from the previous pass */
539 if (room) {
540 *xf++ = XFRM_SEP;
541 room--;
542 }
543 want++;
544 }
545
546 /* special pass for undefined */
547 if (pass == _collate_info->directive_count) {
548 direc = DIRECTIVE_FORWARD | DIRECTIVE_UNDEFINED;
549 } else {
550 direc = _collate_info->directive[pass];
551 }
552
553 t = src;
554
555 if (direc & DIRECTIVE_BACKWARD) {
556 wchar_t *bp, *fp, c;
557 if (tr)
558 free(tr);
559 if ((tr = wcsdup(t)) == NULL) {
560 errno = ENOMEM;
561 goto fail;
562 }
563 bp = tr;
564 fp = tr + wcslen(tr) - 1;
565 while (bp < fp) {
566 c = *bp;
567 *bp++ = *fp;
568 *fp-- = c;
569 }
570 t = (const wchar_t *)tr;
571 }
572
573 if (direc & DIRECTIVE_POSITION) {
574 while (*t || state) {
575
576 _collate_lookup(t, &len, &pri, pass, &state);
577 t += len;
578 if (pri <= 0) {
579 if (pri < 0) {
580 errno = EINVAL;
581 goto fail;
582 }
583 pri = COLLATE_MAX_PRIORITY;
584 }
585
586 b = xfrm(buf, pri, pass);
587 want += b;
588 if (room) {
589 while (b) {
590 b--;
591 if (room) {
592 *xf++ = buf[b];
593 room--;
594 }
595 }
596 }
597 need = want;
598 }
599 } else {
600 while (*t || state) {
601 _collate_lookup(t, &len, &pri, pass, &state);
602 t += len;
603 if (pri <= 0) {
604 if (pri < 0) {
605 errno = EINVAL;
606 goto fail;
607 }
608 continue;
609 }
610
611 b = xfrm(buf, pri, pass);
612 want += b;
613 if (room) {
614
615 while (b) {
616 b--;
617 if (room) {
618 *xf++ = buf[b];
619 room--;
620 }
621 }
622 }
623 need = want;
624 }
625 }
626 }
627
628 end:
629 if (tr)
630 free(tr);
631 return (need);
632
633 fail:
634 if (tr)
635 free(tr);
636 return ((size_t)(-1));
637 }