Add more alignment checks.
[kopensolaris-gnu/glibc.git] / string / strcoll.c
1 /* Copyright (C) 1995, 96, 97, 98, 99, 2000 Free Software Foundation, Inc.
2    This file is part of the GNU C Library.
3    Written by Ulrich Drepper <drepper@cygnus.com>, 1995.
4
5    The GNU C Library is free software; you can redistribute it and/or
6    modify it under the terms of the GNU Library General Public License as
7    published by the Free Software Foundation; either version 2 of the
8    License, or (at your option) any later version.
9
10    The GNU C Library is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    Library General Public License for more details.
14
15    You should have received a copy of the GNU Library General Public
16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18    Boston, MA 02111-1307, USA.  */
19
20 #include <assert.h>
21 #include <langinfo.h>
22 #include <stddef.h>
23 #include <stdint.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #ifndef STRING_TYPE
28 # define STRING_TYPE char
29 # define USTRING_TYPE unsigned char
30 # ifdef USE_IN_EXTENDED_LOCALE_MODEL
31 #  define STRCOLL __strcoll_l
32 # else
33 #  define STRCOLL strcoll
34 # endif
35 # define STRCMP strcmp
36 # define STRLEN strlen
37 # define WEIGHT_H "../locale/weight.h"
38 # define SUFFIX MB
39 # define L(arg) arg
40 #endif
41
42 #define CONCAT(a,b) CONCAT1(a,b)
43 #define CONCAT1(a,b) a##b
44
45 #include "../locale/localeinfo.h"
46
47 #ifndef USE_IN_EXTENDED_LOCALE_MODEL
48 int
49 STRCOLL (s1, s2)
50      const STRING_TYPE *s1;
51      const STRING_TYPE *s2;
52 #else
53 int
54 STRCOLL (s1, s2, l)
55      const STRING_TYPE *s1;
56      const STRING_TYPE *s2;
57      __locale_t l;
58 #endif
59 {
60 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
61   struct locale_data *current = l->__locales[LC_COLLATE];
62   uint_fast32_t nrules = *((uint32_t *) current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].string);
63 #else
64   uint_fast32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
65 #endif
66   /* We don't assign the following values right away since it might be
67      unnecessary in case there are no rules.  */
68   const unsigned char *rulesets;
69   const int32_t *table;
70   const USTRING_TYPE *weights;
71   const USTRING_TYPE *extra;
72   const int32_t *indirect;
73   uint_fast32_t pass;
74   int result = 0;
75   const USTRING_TYPE *us1;
76   const USTRING_TYPE *us2;
77   size_t s1len;
78   size_t s2len;
79   int32_t *idx1arr;
80   int32_t *idx2arr;
81   unsigned char *rule1arr;
82   unsigned char *rule2arr;
83   size_t idx1max;
84   size_t idx2max;
85   size_t idx1cnt;
86   size_t idx2cnt;
87   size_t idx1now;
88   size_t idx2now;
89   size_t backw1_stop;
90   size_t backw2_stop;
91   size_t backw1;
92   size_t backw2;
93   int val1;
94   int val2;
95   int position;
96   int seq1len;
97   int seq2len;
98   int use_malloc;
99 #ifdef WIDE_CHAR_VERSION
100   size_t size;
101   size_t layers;
102   const wint_t *names;
103 #endif
104
105 #include WEIGHT_H
106
107   if (nrules == 0)
108     return STRCMP (s1, s2);
109
110 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
111   rulesets = (const unsigned char *)
112     current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
113   table = (const int32_t *)
114     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
115   weights = (const USTRING_TYPE *)
116     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
117   extra = (const USTRING_TYPE *)
118     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
119   indirect = (const int32_t *)
120     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
121 # ifdef WIDE_CHAR_VERSION
122   names = (const wint_t *)
123     current->values[_NL_ITEM_INDEX (_NL_COLLATE_NAMES)].string;
124   size = current->values[_NL_ITEM_INDEX (_NL_COLLATE_HASH_SIZE)].word;
125   layers = current->values[_NL_ITEM_INDEX (_NL_COLLATE_HASH_LAYERS)].word;
126 # endif
127 #else
128   rulesets = (const unsigned char *)
129     _NL_CURRENT (LC_COLLATE, _NL_COLLATE_RULESETS);
130   table = (const int32_t *)
131     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_TABLE,SUFFIX));
132   weights = (const USTRING_TYPE *)
133     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_WEIGHT,SUFFIX));
134   extra = (const USTRING_TYPE *)
135     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_EXTRA,SUFFIX));
136   indirect = (const int32_t *)
137     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_INDIRECT,SUFFIX));
138 # ifdef WIDE_CHAR_VERSION
139   names = (const wint_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_NAMES);
140   size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_HASH_SIZE);
141   layers = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_HASH_LAYERS);
142 # endif
143 #endif
144   use_malloc = 0;
145
146   assert (((uintptr_t) table) % sizeof (table[0]) == 0);
147   assert (((uintptr_t) weights) % sizeof (weights[0]) == 0);
148   assert (((uintptr_t) weights) % sizeof (weights[0]) == 0);
149   assert (((uintptr_t) extra) % sizeof (extra[0]) == 0);
150   assert (((uintptr_t) indirect) % sizeof (indirect[0]) == 0);
151 #ifdef WIDE_CHAR_VERSION
152   assert (((uintptr_t) names) % sizeof (names[0]) == 0);
153 #endif
154
155   /* We need this a few times.  */
156   s1len = STRLEN (s1);
157   s2len = STRLEN (s2);
158
159   /* We need the elements of the strings as unsigned values since they
160      are used as indeces.  */
161   us1 = (const USTRING_TYPE *) s1;
162   us2 = (const USTRING_TYPE *) s2;
163
164   /* Perform the first pass over the string and while doing this find
165      and store the weights for each character.  Since we want this to
166      be as fast as possible we are using `alloca' to store the temporary
167      values.  But since there is no limit on the length of the string
168      we have to use `malloc' if the string is too long.  We should be
169      very conservative here.
170
171      Please note that the localedef programs makes sure that `position'
172      is not used at the first level.  */
173   if (s1len + s2len >= 16384)
174     {
175       idx1arr = (int32_t *) malloc ((s1len + s2len) * (sizeof (int32_t) + 1));
176       idx2arr = &idx1arr[s2len];
177       rule1arr = (unsigned char *) &idx2arr[s2len];
178       rule2arr = &rule1arr[s1len];
179
180       if (idx1arr == NULL)
181         /* No memory.  Well, go with the stack then.
182
183            XXX Once this implementation is stable we will handle this
184            differently.  Instead of precomputing the indeces we will
185            do this in time.  This means, though, that this happens for
186            every pass again.  */
187         goto try_stack;
188       use_malloc = 1;
189     }
190   else
191     {
192     try_stack:
193       idx1arr = (int32_t *) alloca (s1len * sizeof (int32_t));
194       idx2arr = (int32_t *) alloca (s2len * sizeof (int32_t));
195       rule1arr = (unsigned char *) alloca (s2len);
196       rule2arr = (unsigned char *) alloca (s2len);
197     }
198
199   idx1cnt = 0;
200   idx2cnt = 0;
201   idx1max = 0;
202   idx2max = 0;
203   idx1now = 0;
204   idx2now = 0;
205   backw1_stop = ~0ul;
206   backw2_stop = ~0ul;
207   backw1 = ~0ul;
208   backw2 = ~0ul;
209   seq1len = 0;
210   seq2len = 0;
211   position = rulesets[0] & sort_position;
212   while (1)
213     {
214       val1 = 0;
215       val2 = 0;
216
217       /* Get the next non-IGNOREd element for string `s1'.  */
218       if (seq1len == 0)
219         do
220           {
221             ++val1;
222
223             if (backw1_stop != ~0ul)
224               {
225                 /* The is something pushed.  */
226                 if (backw1 == backw1_stop)
227                   {
228                     /* The last pushed character was handled.  Continue
229                        with forward characters.  */
230                     if (idx1cnt < idx1max)
231                       idx1now = idx1cnt;
232                     else
233                       /* Nothing anymore.  The backward sequence ended with
234                          the last sequence in the string.  Note that seq1len
235                          is still zero.  */
236                       break;
237                   }
238                 else
239                   idx1now = --backw1;
240               }
241             else
242               {
243                 backw1_stop = idx1max;
244
245                 while (*us1 != L('\0'))
246                   {
247                     int32_t tmp = findidx (&us1);
248                     rule1arr[idx1max] = tmp >> 24;
249                     idx1arr[idx1max] = tmp & 0xffffff;
250                     idx1cnt = idx1max++;
251
252                     if ((rulesets[rule1arr[idx1cnt] * nrules]
253                          & sort_backward) == 0)
254                       /* No more backward characters to push.  */
255                       break;
256                     ++idx1cnt;
257                   }
258
259                 if (backw1_stop >= idx1cnt)
260                   {
261                     /* No sequence at all or just one.  */
262                     if (idx1cnt == idx1max || backw1_stop > idx1cnt)
263                       /* Note that seq1len is still zero.  */
264                       break;
265
266                     backw1_stop = ~0ul;
267                     idx1now = idx1cnt;
268                   }
269                 else
270                   /* We pushed backward sequences.  */
271                   idx1now = backw1 = idx1cnt - 1;
272               }
273           }
274         while ((seq1len = weights[idx1arr[idx1now]++]) == 0);
275
276       /* And the same for string `s2'.  */
277       if (seq2len == 0)
278         do
279           {
280             ++val2;
281
282             if (backw2_stop != ~0ul)
283               {
284                 /* The is something pushed.  */
285                 if (backw2 == backw2_stop)
286                   {
287                     /* The last pushed character was handled.  Continue
288                        with forward characters.  */
289                     if (idx2cnt < idx2max)
290                       idx2now = idx2cnt;
291                     else
292                       /* Nothing anymore.  The backward sequence ended with
293                          the last sequence in the string.  Note that seq2len
294                          is still zero.  */
295                       break;
296                   }
297                 else
298                   idx2now = --backw2;
299               }
300             else
301               {
302                 backw2_stop = idx2max;
303
304                 while (*us2 != L('\0'))
305                   {
306                     int32_t tmp = findidx (&us2);
307                     rule2arr[idx2max] = tmp >> 24;
308                     idx2arr[idx2max] = tmp & 0xffffff;
309                     idx2cnt = idx2max++;
310
311                     if ((rulesets[rule2arr[idx2cnt] * nrules]
312                          & sort_backward) == 0)
313                       /* No more backward characters to push.  */
314                       break;
315                     ++idx2cnt;
316                   }
317
318                 if (backw2_stop >= idx2cnt)
319                   {
320                     /* No sequence at all or just one.  */
321                     if (idx2cnt == idx2max || backw2_stop > idx2cnt)
322                       /* Note that seq1len is still zero.  */
323                       break;
324
325                     backw2_stop = ~0ul;
326                     idx2now = idx2cnt;
327                   }
328                 else
329                   /* We pushed backward sequences.  */
330                   idx2now = backw2 = idx2cnt - 1;
331               }
332           }
333         while ((seq2len = weights[idx2arr[idx2now]++]) == 0);
334
335       /* See whether any or both strings are empty.  */
336       if (seq1len == 0 || seq2len == 0)
337         {
338           if (seq1len == seq2len)
339             /* Both ended.  So far so good, both strings are equal at the
340                first level.  */
341             break;
342
343           /* This means one string is shorter than the other.  Find out
344              which one and return an appropriate value.  */
345           result = seq1len == 0 ? -1 : 1;
346           goto free_and_return;
347         }
348
349       /* Test for position if necessary.  */
350       if (position && val1 != val2)
351         {
352           result = val1 - val2;
353           goto free_and_return;
354         }
355
356       /* Compare the two sequences.  */
357       do
358         {
359           if (weights[idx1arr[idx1now]] != weights[idx2arr[idx2now]])
360             {
361               /* The sequences differ.  */
362               result = weights[idx1arr[idx1now]] - weights[idx2arr[idx2now]];
363               goto free_and_return;
364             }
365
366           /* Increment the offsets.  */
367           ++idx1arr[idx1now];
368           ++idx2arr[idx2now];
369
370           --seq1len;
371           --seq2len;
372         }
373       while (seq1len > 0 && seq2len > 0);
374
375       if (position && seq1len != seq2len)
376         {
377           result = seq1len - seq2len;
378           goto free_and_return;
379         }
380     }
381
382   /* Now the remaining passes over the weights.  We now use the
383      indeces we found before.  */
384   for (pass = 1; pass < nrules; ++pass)
385     {
386       /* We assume that if a rule has defined `position' in one section
387          this is true for all of them.  */
388       idx1cnt = 0;
389       idx2cnt = 0;
390       backw1_stop = ~0ul;
391       backw2_stop = ~0ul;
392       backw1 = ~0ul;
393       backw2 = ~0ul;
394       position = rulesets[rule1arr[0] * nrules + pass] & sort_position;
395
396       while (1)
397         {
398           val1 = 0;
399           val2 = 0;
400
401           /* Get the next non-IGNOREd element for string `s1'.  */
402           if (seq1len == 0)
403             do
404               {
405                 ++val1;
406
407                 if (backw1_stop != ~0ul)
408                   {
409                     /* The is something pushed.  */
410                     if (backw1 == backw1_stop)
411                       {
412                         /* The last pushed character was handled.  Continue
413                            with forward characters.  */
414                         if (idx1cnt < idx1max)
415                           idx1now = idx1cnt;
416                         else
417                           {
418                             /* Nothing anymore.  The backward sequence
419                                ended with the last sequence in the string.  */
420                             idx1now = ~0ul;
421                             break;
422                           }
423                       }
424                     else
425                       idx1now = --backw1;
426                   }
427                 else
428                   {
429                     backw1_stop = idx1cnt;
430
431                     while (idx1cnt < idx1max)
432                       {
433                         if ((rulesets[rule1arr[idx1cnt] * nrules + pass]
434                              & sort_backward) == 0)
435                           /* No more backward characters to push.  */
436                           break;
437                         ++idx1cnt;
438                       }
439
440                     if (backw1_stop == idx1cnt)
441                       {
442                         /* No sequence at all or just one.  */
443                         if (idx1cnt == idx1max)
444                           /* Note that seq2len is still zero.  */
445                           break;
446
447                         backw1_stop = ~0ul;
448                         idx1now = idx1cnt++;
449                       }
450                     else
451                       /* We pushed backward sequences.  */
452                       idx1now = backw1 = idx1cnt - 1;
453                   }
454               }
455             while ((seq1len = weights[idx1arr[idx1now]++]) == 0);
456
457           /* And the same for string `s2'.  */
458           if (seq2len == 0)
459             do
460               {
461                 ++val2;
462
463                 if (backw2_stop != ~0ul)
464                   {
465                     /* The is something pushed.  */
466                     if (backw2 == backw2_stop)
467                       {
468                         /* The last pushed character was handled.  Continue
469                            with forward characters.  */
470                         if (idx2cnt < idx2max)
471                           idx2now = idx2cnt;
472                         else
473                           {
474                             /* Nothing anymore.  The backward sequence
475                                ended with the last sequence in the string.  */
476                             idx2now = ~0ul;
477                             break;
478                           }
479                       }
480                     else
481                       idx2now = --backw2;
482                   }
483                 else
484                   {
485                     backw2_stop = idx2cnt;
486
487                     while (idx2cnt < idx2max)
488                       {
489                         if ((rulesets[rule2arr[idx2cnt] * nrules + pass]
490                              & sort_backward) == 0)
491                           /* No more backward characters to push.  */
492                           break;
493                         ++idx2cnt;
494                       }
495
496                     if (backw2_stop == idx2cnt)
497                       {
498                         /* No sequence at all or just one.  */
499                         if (idx2cnt == idx2max)
500                           /* Note that seq2len is still zero.  */
501                           break;
502
503                         backw2_stop = ~0ul;
504                         idx2now = idx2cnt++;
505                       }
506                     else
507                       /* We pushed backward sequences.  */
508                       idx2now = backw2 = idx2cnt - 1;
509                   }
510               }
511             while ((seq2len = weights[idx2arr[idx2now]++]) == 0);
512
513           /* See whether any or both strings are empty.  */
514           if (seq1len == 0 || seq2len == 0)
515             {
516               if (seq1len == seq2len)
517                 /* Both ended.  So far so good, both strings are equal
518                    at this level.  */
519                 break;
520
521               /* This means one string is shorter than the other.  Find out
522                  which one and return an appropriate value.  */
523               result = seq1len == 0 ? -1 : 1;
524               goto free_and_return;
525             }
526
527           /* Test for position if necessary.  */
528           if (position && val1 != val2)
529             {
530               result = val1 - val2;
531               goto free_and_return;
532             }
533
534           /* Compare the two sequences.  */
535           do
536             {
537               if (weights[idx1arr[idx1now]] != weights[idx2arr[idx2now]])
538                 {
539                   /* The sequences differ.  */
540                   result = (weights[idx1arr[idx1now]]
541                             - weights[idx2arr[idx2now]]);
542                   goto free_and_return;
543                 }
544
545               /* Increment the offsets.  */
546               ++idx1arr[idx1now];
547               ++idx2arr[idx2now];
548
549               --seq1len;
550               --seq2len;
551             }
552           while (seq1len > 0 && seq2len > 0);
553
554           if (position && seq1len != seq2len)
555             {
556               result = seq1len - seq2len;
557               goto free_and_return;
558             }
559         }
560     }
561
562   /* Free the memory if needed.  */
563  free_and_return:
564   if (use_malloc)
565     free (idx1arr);
566
567   return result;
568 }