Define nZERO and nINF.
[kopensolaris-gnu/glibc.git] / string / strxfrm.c
1 /* Copyright (C) 1995-1999,2000,2001 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 <locale.h>
23 #include <stddef.h>
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <sys/param.h>
28
29 #ifndef STRING_TYPE
30 # define STRING_TYPE char
31 # define USTRING_TYPE unsigned char
32 # ifdef USE_IN_EXTENDED_LOCALE_MODEL
33 #  define STRXFRM __strxfrm_l
34 # else
35 #  define STRXFRM strxfrm
36 # endif
37 # define STRCMP strcmp
38 # define STRLEN strlen
39 # define STPNCPY __stpncpy
40 # define WEIGHT_H "../locale/weight.h"
41 # define SUFFIX MB
42 # define L(arg) arg
43 #endif
44
45 #define CONCAT(a,b) CONCAT1(a,b)
46 #define CONCAT1(a,b) a##b
47
48 #include "../locale/localeinfo.h"
49
50
51 #ifndef WIDE_CHAR_VERSION
52
53 /* We need UTF-8 encoding of numbers.  */
54 static inline int
55 utf8_encode (char *buf, int val)
56 {
57   int retval;
58
59   if (val < 0x80)
60     {
61       *buf++ = (char) val;
62       retval = 1;
63     }
64   else
65     {
66       int step;
67
68       for (step = 2; step < 6; ++step)
69         if ((val & (~(uint32_t)0 << (5 * step + 1))) == 0)
70           break;
71       retval = step;
72
73       *buf = (unsigned char) (~0xff >> step);
74       --step;
75       do
76         {
77           buf[step] = 0x80 | (val & 0x3f);
78           val >>= 6;
79         }
80       while (--step > 0);
81       *buf |= val;
82     }
83
84   return retval;
85 }
86 #endif
87
88
89 #ifndef USE_IN_EXTENDED_LOCALE_MODEL
90 size_t
91 STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n)
92 #else
93 size_t
94 STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n, __locale_t l)
95 #endif
96 {
97 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
98   struct locale_data *current = l->__locales[LC_COLLATE];
99   uint_fast32_t nrules = *((const uint32_t *) current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].string);
100 #else
101   uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
102 #endif
103   /* We don't assign the following values right away since it might be
104      unnecessary in case there are no rules.  */
105   const unsigned char *rulesets;
106   const int32_t *table;
107   const USTRING_TYPE *weights;
108   const USTRING_TYPE *extra;
109   const int32_t *indirect;
110   uint_fast32_t pass;
111   size_t needed;
112   const USTRING_TYPE *usrc;
113   size_t srclen = STRLEN (src);
114   int32_t *idxarr;
115   unsigned char *rulearr;
116   size_t idxmax;
117   size_t idxcnt;
118   int use_malloc;
119
120 #include WEIGHT_H
121
122   if (nrules == 0)
123     {
124       if (n != 0)
125         STPNCPY (dest, src, MIN (srclen + 1, n));
126
127       return srclen;
128     }
129
130 #ifdef USE_IN_EXTENDED_LOCALE_MODEL
131   rulesets = (const unsigned char *)
132     current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
133   table = (const int32_t *)
134     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
135   weights = (const USTRING_TYPE *)
136     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
137   extra = (const USTRING_TYPE *)
138     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
139   indirect = (const int32_t *)
140     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
141 #else
142   rulesets = (const unsigned char *)
143     _NL_CURRENT (LC_COLLATE, _NL_COLLATE_RULESETS);
144   table = (const int32_t *)
145     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_TABLE,SUFFIX));
146   weights = (const USTRING_TYPE *)
147     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_WEIGHT,SUFFIX));
148   extra = (const USTRING_TYPE *)
149     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_EXTRA,SUFFIX));
150   indirect = (const int32_t *)
151     _NL_CURRENT (LC_COLLATE, CONCAT(_NL_COLLATE_INDIRECT,SUFFIX));
152 #endif
153   use_malloc = 0;
154
155   assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
156   assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
157   assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
158   assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
159
160   /* Handle an empty string as a special case.  */
161   if (srclen == 0)
162     {
163       if (n != 0)
164         *dest = L('\0');
165       return 1;
166     }
167
168   /* We need the elements of the string as unsigned values since they
169      are used as indeces.  */
170   usrc = (const USTRING_TYPE *) src;
171
172   /* Perform the first pass over the string and while doing this find
173      and store the weights for each character.  Since we want this to
174      be as fast as possible we are using `alloca' to store the temporary
175      values.  But since there is no limit on the length of the string
176      we have to use `malloc' if the string is too long.  We should be
177      very conservative here.  */
178   if (srclen >= 16384)
179     {
180       idxarr = (int32_t *) malloc (srclen * (sizeof (int32_t) + 1));
181       rulearr = (unsigned char *) &idxarr[srclen];
182
183       if (idxarr == NULL)
184         /* No memory.  Well, go with the stack then.
185
186            XXX Once this implementation is stable we will handle this
187            differently.  Instead of precomputing the indeces we will
188            do this in time.  This means, though, that this happens for
189            every pass again.  */
190         goto try_stack;
191       use_malloc = 1;
192     }
193   else
194     {
195     try_stack:
196       idxarr = (int32_t *) alloca (srclen * sizeof (int32_t));
197       rulearr = (unsigned char *) alloca (srclen);
198     }
199
200   idxmax = 0;
201   do
202     {
203       int32_t tmp = findidx (&usrc);
204       rulearr[idxmax] = tmp >> 24;
205       idxarr[idxmax] = tmp & 0xffffff;
206
207       ++idxmax;
208     }
209   while (*usrc != L('\0'));
210
211   /* Now the passes over the weights.  We now use the indeces we found
212      before.  */
213   needed = 0;
214   for (pass = 0; pass < nrules; ++pass)
215     {
216       size_t backw_stop = ~0ul;
217       int rule = rulesets[rulearr[0] * nrules + pass];
218       /* We assume that if a rule has defined `position' in one section
219          this is true for all of them.  */
220       int position = rule & sort_position;
221
222       if (position == 0)
223         {
224           for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
225             {
226               if ((rule & sort_forward) != 0)
227                 {
228                   size_t len;
229
230                   if (backw_stop != ~0ul)
231                     {
232                       /* Handle the pushed elements now.  */
233                       size_t backw;
234
235                       for (backw = idxcnt - 1; backw >= backw_stop; --backw)
236                         {
237                           len = weights[idxarr[backw]++];
238
239                           if (needed + len < n)
240                             while (len-- > 0)
241                               dest[needed++] = weights[idxarr[backw]++];
242                           else
243                             {
244                                 /* No more characters fit into the buffer.  */
245                               needed += len;
246                               idxarr[backw] += len;
247                             }
248                         }
249
250                       backw_stop = ~0ul;
251                     }
252
253                   /* Now handle the forward element.  */
254                   len = weights[idxarr[idxcnt]++];
255                   if (needed + len < n)
256                     while (len-- > 0)
257                       dest[needed++] = weights[idxarr[idxcnt]++];
258                   else
259                     {
260                       /* No more characters fit into the buffer.  */
261                       needed += len;
262                       idxarr[idxcnt] += len;
263                     }
264                 }
265               else
266                 {
267                   /* Remember where the backwards series started.  */
268                   if (backw_stop == ~0ul)
269                     backw_stop = idxcnt;
270                 }
271
272               rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
273             }
274
275
276           if (backw_stop != ~0ul)
277             {
278               /* Handle the pushed elements now.  */
279               size_t backw;
280
281               backw = idxcnt;
282               while (backw > backw_stop)
283                 {
284                   size_t len = weights[idxarr[--backw]++];
285
286                   if (needed + len < n)
287                     while (len-- > 0)
288                       dest[needed++] = weights[idxarr[backw]++];
289                   else
290                     {
291                       /* No more characters fit into the buffer.  */
292                       needed += len;
293                       idxarr[backw] += len;
294                     }
295                 }
296             }
297         }
298       else
299         {
300           int val = 1;
301 #ifndef WIDE_CHAR_VERSION
302           char buf[7];
303           size_t buflen;
304 #endif
305           size_t i;
306
307           for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
308             {
309               if ((rule & sort_forward) != 0)
310                 {
311                   size_t len;
312
313                   if (backw_stop != ~0ul)
314                     {
315                      /* Handle the pushed elements now.  */
316                       size_t backw;
317
318                       for (backw = idxcnt - 1; backw >= backw_stop; --backw)
319                         {
320                           len = weights[idxarr[backw]++];
321                           if (len != 0)
322                             {
323 #ifdef WIDE_CHAR_VERSION
324                               if (needed + 1 + len < n)
325                                 {
326                                   dest[needed] = val;
327                                   for (i = 0; i < len; ++i)
328                                     dest[needed + 1 + i] =
329                                       weights[idxarr[backw] + i];
330                                 }
331                               needed += 1 + len;
332 #else
333                               buflen = utf8_encode (buf, val);
334                               if (needed + buflen + len < n)
335                                 {
336                                   for (i = 0; i < buflen; ++i)
337                                     dest[needed + i] = buf[i];
338                                   for (i = 0; i < len; ++i)
339                                     dest[needed + buflen + i] =
340                                       weights[idxarr[backw] + i];
341                                 }
342                               needed += buflen + len;
343 #endif
344                               idxarr[backw] += len;
345                               val = 1;
346                             }
347                           else
348                             ++val;
349                         }
350
351                       backw_stop = ~0ul;
352                     }
353
354                   /* Now handle the forward element.  */
355                   len = weights[idxarr[idxcnt]++];
356                   if (len != 0)
357                     {
358 #ifdef WIDE_CHAR_VERSION
359                       if (needed + 1+ len < n)
360                         {
361                           dest[needed] = val;
362                           for (i = 0; i < len; ++i)
363                             dest[needed + 1 + i] =
364                               weights[idxarr[idxcnt] + i];
365                         }
366                       needed += 1 + len;
367 #else
368                       buflen = utf8_encode (buf, val);
369                       if (needed + buflen + len < n)
370                         {
371                           for (i = 0; i < buflen; ++i)
372                             dest[needed + i] = buf[i];
373                           for (i = 0; i < len; ++i)
374                             dest[needed + buflen + i] =
375                               weights[idxarr[idxcnt] + i];
376                         }
377                       needed += buflen + len;
378 #endif
379                       idxarr[idxcnt] += len;
380                       val = 1;
381                     }
382                   else
383                     /* Note that we don't have to increment `idxarr[idxcnt]'
384                        since the length is zero.  */
385                     ++val;
386                 }
387               else
388                 {
389                   /* Remember where the backwards series started.  */
390                   if (backw_stop == ~0ul)
391                     backw_stop = idxcnt;
392                 }
393
394               rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
395             }
396
397           if (backw_stop != ~0ul)
398             {
399               /* Handle the pushed elements now.  */
400               size_t backw;
401
402               backw = idxmax - 1;
403               while (backw > backw_stop)
404                 {
405                   size_t len = weights[idxarr[--backw]++];
406                   if (len != 0)
407                     {
408 #ifdef WIDE_CHAR_VERSION
409                       if (needed + 1 + len < n)
410                         {
411                           dest[needed] = val;
412                           for (i = 0; i < len; ++i)
413                             dest[needed + 1 + i] =
414                               weights[idxarr[backw] + i];
415                         }
416                       needed += 1 + len;
417 #else
418                       buflen = utf8_encode (buf, val);
419                       if (needed + buflen + len < n)
420                         {
421                           for (i = 0; i < buflen; ++i)
422                             dest[needed + i] = buf[i];
423                           for (i = 0; i < len; ++i)
424                             dest[needed + buflen + i] =
425                               weights[idxarr[backw] + i];
426                         }
427                       needed += buflen + len;
428 #endif
429                       idxarr[backw] += len;
430                       val = 1;
431                     }
432                   else
433                     ++val;
434                 }
435             }
436         }
437
438       /* Finally store the byte to separate the passes or terminate
439          the string.  */
440       if (needed < n)
441         dest[needed] = pass + 1 < nrules ? L('\1') : L('\0');
442       ++needed;
443     }
444
445   /* This is a little optimization: many collation specifications have
446      a `position' rule at the end and if no non-ignored character
447      is found the last \1 byte is immediately followed by a \0 byte
448      signalling this.  We can avoid the \1 byte(s).  */
449   if (needed <= n && needed > 2 && dest[needed - 2] == L('\1'))
450     {
451       /* Remove the \1 byte.  */
452       --needed;
453       dest[needed - 1] = L('\0');
454     }
455
456   /* Free the memory if needed.  */
457   if (use_malloc)
458     free (idxarr);
459
460   /* Return the number of bytes/words we need, but don't count the NUL
461      byte/word at the end.  */
462   return needed - 1;
463 }