More small optimizations for x86-64 strlen.
[glibc.git] / string / strxfrm_l.c
blob20f2f149bdea97134b6db5360aa4c74564847247
1 /* Copyright (C) 1995, 1996, 1997, 2002, 2004, 2005, 2006
2 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Written by Ulrich Drepper <drepper@gnu.org>, 1995.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19 02111-1307 USA. */
21 #include <assert.h>
22 #include <langinfo.h>
23 #include <locale.h>
24 #include <stddef.h>
25 #include <stdint.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <sys/param.h>
30 #ifndef STRING_TYPE
31 # define STRING_TYPE char
32 # define USTRING_TYPE unsigned char
33 # define STRXFRM __strxfrm_l
34 # define STRCMP strcmp
35 # define STRLEN strlen
36 # define STPNCPY __stpncpy
37 # define WEIGHT_H "../locale/weight.h"
38 # define SUFFIX MB
39 # define L(arg) arg
40 #endif
42 #define CONCAT(a,b) CONCAT1(a,b)
43 #define CONCAT1(a,b) a##b
45 #include "../locale/localeinfo.h"
48 #ifndef WIDE_CHAR_VERSION
50 /* We need UTF-8 encoding of numbers. */
51 static int
52 utf8_encode (char *buf, int val)
54 int retval;
56 if (val < 0x80)
58 *buf++ = (char) val;
59 retval = 1;
61 else
63 int step;
65 for (step = 2; step < 6; ++step)
66 if ((val & (~(uint32_t)0 << (5 * step + 1))) == 0)
67 break;
68 retval = step;
70 *buf = (unsigned char) (~0xff >> step);
71 --step;
74 buf[step] = 0x80 | (val & 0x3f);
75 val >>= 6;
77 while (--step > 0);
78 *buf |= val;
81 return retval;
83 #endif
86 size_t
87 STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n, __locale_t l)
89 struct locale_data *current = l->__locales[LC_COLLATE];
90 uint_fast32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
91 /* We don't assign the following values right away since it might be
92 unnecessary in case there are no rules. */
93 const unsigned char *rulesets;
94 const int32_t *table;
95 const USTRING_TYPE *weights;
96 const USTRING_TYPE *extra;
97 const int32_t *indirect;
98 uint_fast32_t pass;
99 size_t needed;
100 size_t last_needed;
101 const USTRING_TYPE *usrc;
102 size_t srclen = STRLEN (src);
103 int32_t *idxarr;
104 unsigned char *rulearr;
105 size_t idxmax;
106 size_t idxcnt;
107 int use_malloc;
109 #include WEIGHT_H
111 if (nrules == 0)
113 if (n != 0)
114 STPNCPY (dest, src, MIN (srclen + 1, n));
116 return srclen;
119 rulesets = (const unsigned char *)
120 current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
121 table = (const int32_t *)
122 current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
123 weights = (const USTRING_TYPE *)
124 current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
125 extra = (const USTRING_TYPE *)
126 current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
127 indirect = (const int32_t *)
128 current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
129 use_malloc = 0;
131 assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
132 assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
133 assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
134 assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
136 /* Handle an empty string as a special case. */
137 if (srclen == 0)
139 if (n != 0)
140 *dest = L('\0');
141 return 0;
144 /* We need the elements of the string as unsigned values since they
145 are used as indeces. */
146 usrc = (const USTRING_TYPE *) src;
148 /* Perform the first pass over the string and while doing this find
149 and store the weights for each character. Since we want this to
150 be as fast as possible we are using `alloca' to store the temporary
151 values. But since there is no limit on the length of the string
152 we have to use `malloc' if the string is too long. We should be
153 very conservative here. */
154 if (! __libc_use_alloca (srclen))
156 idxarr = (int32_t *) malloc ((srclen + 1) * (sizeof (int32_t) + 1));
157 rulearr = (unsigned char *) &idxarr[srclen];
159 if (idxarr == NULL)
160 /* No memory. Well, go with the stack then.
162 XXX Once this implementation is stable we will handle this
163 differently. Instead of precomputing the indeces we will
164 do this in time. This means, though, that this happens for
165 every pass again. */
166 goto try_stack;
167 use_malloc = 1;
169 else
171 try_stack:
172 idxarr = (int32_t *) alloca (srclen * sizeof (int32_t));
173 rulearr = (unsigned char *) alloca (srclen + 1);
176 idxmax = 0;
179 int32_t tmp = findidx (&usrc);
180 rulearr[idxmax] = tmp >> 24;
181 idxarr[idxmax] = tmp & 0xffffff;
183 ++idxmax;
185 while (*usrc != L('\0'));
187 /* This element is only read, the value never used but to determine
188 another value which then is ignored. */
189 rulearr[idxmax] = '\0';
191 /* Now the passes over the weights. We now use the indeces we found
192 before. */
193 needed = 0;
194 for (pass = 0; pass < nrules; ++pass)
196 size_t backw_stop = ~0ul;
197 int rule = rulesets[rulearr[0] * nrules + pass];
198 /* We assume that if a rule has defined `position' in one section
199 this is true for all of them. */
200 int position = rule & sort_position;
202 last_needed = needed;
203 if (position == 0)
205 for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
207 if ((rule & sort_forward) != 0)
209 size_t len;
211 if (backw_stop != ~0ul)
213 /* Handle the pushed elements now. */
214 size_t backw;
216 for (backw = idxcnt; backw > backw_stop; )
218 --backw;
219 len = weights[idxarr[backw]++];
221 if (needed + len < n)
222 while (len-- > 0)
223 dest[needed++] = weights[idxarr[backw]++];
224 else
226 /* No more characters fit into the buffer. */
227 needed += len;
228 idxarr[backw] += len;
232 backw_stop = ~0ul;
235 /* Now handle the forward element. */
236 len = weights[idxarr[idxcnt]++];
237 if (needed + len < n)
238 while (len-- > 0)
239 dest[needed++] = weights[idxarr[idxcnt]++];
240 else
242 /* No more characters fit into the buffer. */
243 needed += len;
244 idxarr[idxcnt] += len;
247 else
249 /* Remember where the backwards series started. */
250 if (backw_stop == ~0ul)
251 backw_stop = idxcnt;
254 rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
258 if (backw_stop != ~0ul)
260 /* Handle the pushed elements now. */
261 size_t backw;
263 backw = idxcnt;
264 while (backw > backw_stop)
266 size_t len = weights[idxarr[--backw]++];
268 if (needed + len < n)
269 while (len-- > 0)
270 dest[needed++] = weights[idxarr[backw]++];
271 else
273 /* No more characters fit into the buffer. */
274 needed += len;
275 idxarr[backw] += len;
280 else
282 int val = 1;
283 #ifndef WIDE_CHAR_VERSION
284 char buf[7];
285 size_t buflen;
286 #endif
287 size_t i;
289 for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
291 if ((rule & sort_forward) != 0)
293 size_t len;
295 if (backw_stop != ~0ul)
297 /* Handle the pushed elements now. */
298 size_t backw;
300 for (backw = idxcnt; backw > backw_stop; )
302 --backw;
303 len = weights[idxarr[backw]++];
304 if (len != 0)
306 #ifdef WIDE_CHAR_VERSION
307 if (needed + 1 + len < n)
309 dest[needed] = val;
310 for (i = 0; i < len; ++i)
311 dest[needed + 1 + i] =
312 weights[idxarr[backw] + i];
314 needed += 1 + len;
315 #else
316 buflen = utf8_encode (buf, val);
317 if (needed + buflen + len < n)
319 for (i = 0; i < buflen; ++i)
320 dest[needed + i] = buf[i];
321 for (i = 0; i < len; ++i)
322 dest[needed + buflen + i] =
323 weights[idxarr[backw] + i];
325 needed += buflen + len;
326 #endif
327 idxarr[backw] += len;
328 val = 1;
330 else
331 ++val;
334 backw_stop = ~0ul;
337 /* Now handle the forward element. */
338 len = weights[idxarr[idxcnt]++];
339 if (len != 0)
341 #ifdef WIDE_CHAR_VERSION
342 if (needed + 1+ len < n)
344 dest[needed] = val;
345 for (i = 0; i < len; ++i)
346 dest[needed + 1 + i] =
347 weights[idxarr[idxcnt] + i];
349 needed += 1 + len;
350 #else
351 buflen = utf8_encode (buf, val);
352 if (needed + buflen + len < n)
354 for (i = 0; i < buflen; ++i)
355 dest[needed + i] = buf[i];
356 for (i = 0; i < len; ++i)
357 dest[needed + buflen + i] =
358 weights[idxarr[idxcnt] + i];
360 needed += buflen + len;
361 #endif
362 idxarr[idxcnt] += len;
363 val = 1;
365 else
366 /* Note that we don't have to increment `idxarr[idxcnt]'
367 since the length is zero. */
368 ++val;
370 else
372 /* Remember where the backwards series started. */
373 if (backw_stop == ~0ul)
374 backw_stop = idxcnt;
377 rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
380 if (backw_stop != ~0ul)
382 /* Handle the pushed elements now. */
383 size_t backw;
385 backw = idxmax - 1;
386 while (backw > backw_stop)
388 size_t len = weights[idxarr[--backw]++];
389 if (len != 0)
391 #ifdef WIDE_CHAR_VERSION
392 if (needed + 1 + len < n)
394 dest[needed] = val;
395 for (i = 0; i < len; ++i)
396 dest[needed + 1 + i] =
397 weights[idxarr[backw] + i];
399 needed += 1 + len;
400 #else
401 buflen = utf8_encode (buf, val);
402 if (needed + buflen + len < n)
404 for (i = 0; i < buflen; ++i)
405 dest[needed + i] = buf[i];
406 for (i = 0; i < len; ++i)
407 dest[needed + buflen + i] =
408 weights[idxarr[backw] + i];
410 needed += buflen + len;
411 #endif
412 idxarr[backw] += len;
413 val = 1;
415 else
416 ++val;
421 /* Finally store the byte to separate the passes or terminate
422 the string. */
423 if (needed < n)
424 dest[needed] = pass + 1 < nrules ? L('\1') : L('\0');
425 ++needed;
428 /* This is a little optimization: many collation specifications have
429 a `position' rule at the end and if no non-ignored character
430 is found the last \1 byte is immediately followed by a \0 byte
431 signalling this. We can avoid the \1 byte(s). */
432 if (needed > 2 && needed == last_needed + 1)
434 /* Remove the \1 byte. */
435 if (--needed <= n)
436 dest[needed - 1] = L('\0');
439 /* Free the memory if needed. */
440 if (use_malloc)
441 free (idxarr);
443 /* Return the number of bytes/words we need, but don't count the NUL
444 byte/word at the end. */
445 return needed - 1;
447 libc_hidden_def (STRXFRM)
449 #ifndef WIDE_CHAR_VERSION
450 weak_alias (__strxfrm_l, strxfrm_l)
451 #endif