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