string/strxfrm_l.c

   1 /* Copyright (C) 1995-1997,2002,2004-2006,2010,2011
   2    Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4    Written by Ulrich Drepper <drepper@gnu.org>, 1995.
   5
   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.
  10
  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.
  15
  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.  */
  20
  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>
  29
  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
  41
  42 #define CONCAT(a,b) CONCAT1(a,b)
  43 #define CONCAT1(a,b) a##b
  44
  45 #include "../locale/localeinfo.h"
  46
  47
  48 #ifndef WIDE_CHAR_VERSION
  49
  50 /* We need UTF-8 encoding of numbers.  */
  51 static int
  52 utf8_encode (char *buf, int val)
  53 {
  54   int retval;
  55
  56   if (val < 0x80)
  57     {
  58       *buf++ = (char) val;
  59       retval = 1;
  60     }
  61   else
  62     {
  63       int step;
  64
  65       for (step = 2; step < 6; ++step)
  66         if ((val & (~(uint32_t)0 << (5 * step + 1))) == 0)
  67           break;
  68       retval = step;
  69
  70       *buf = (unsigned char) (~0xff >> step);
  71       --step;
  72       do
  73         {
  74           buf[step] = 0x80 | (val & 0x3f);
  75           val >>= 6;
  76         }
  77       while (--step > 0);
  78       *buf |= val;
  79     }
  80
  81   return retval;
  82 }
  83 #endif
  84
  85
  86 size_t
  87 STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n, __locale_t l)
  88 {
  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;
 108
 109 #include WEIGHT_H
 110
 111   if (nrules == 0)
 112     {
 113       if (n != 0)
 114         STPNCPY (dest, src, MIN (srclen + 1, n));
 115
 116       return srclen;
 117     }
 118
 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;
 130
 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);
 135
 136   /* Handle an empty string as a special case.  */
 137   if (srclen == 0)
 138     {
 139       if (n != 0)
 140         *dest = L('\0');
 141       return 0;
 142     }
 143
 144   /* We need the elements of the string as unsigned values since they
 145      are used as indeces.  */
 146   usrc = (const USTRING_TYPE *) src;
 147
 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 + 1) * (sizeof (int32_t) + 1)))
 155     {
 156       idxarr = (int32_t *) malloc ((srclen + 1) * (sizeof (int32_t) + 1));
 157       rulearr = (unsigned char *) &idxarr[srclen];
 158
 159       if (idxarr == NULL)
 160         /* No memory.  Well, go with the stack then.
 161
 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;
 168     }
 169   else
 170     {
 171     try_stack:
 172       idxarr = (int32_t *) alloca (srclen * sizeof (int32_t));
 173       rulearr = (unsigned char *) alloca (srclen + 1);
 174     }
 175
 176   idxmax = 0;
 177   do
 178     {
 179       int32_t tmp = findidx (&usrc, -1);
 180       rulearr[idxmax] = tmp >> 24;
 181       idxarr[idxmax] = tmp & 0xffffff;
 182
 183       ++idxmax;
 184     }
 185   while (*usrc != L('\0'));
 186
 187   /* This element is only read, the value never used but to determine
 188      another value which then is ignored.  */
 189   rulearr[idxmax] = '\0';
 190
 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)
 195     {
 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;
 201
 202       last_needed = needed;
 203       if (position == 0)
 204         {
 205           for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
 206             {
 207               if ((rule & sort_forward) != 0)
 208                 {
 209                   size_t len;
 210
 211                   if (backw_stop != ~0ul)
 212                     {
 213                       /* Handle the pushed elements now.  */
 214                       size_t backw;
 215
 216                       for (backw = idxcnt; backw > backw_stop; )
 217                         {
 218                           --backw;
 219                           len = weights[idxarr[backw]++];
 220
 221                           if (needed + len < n)
 222                             while (len-- > 0)
 223                               dest[needed++] = weights[idxarr[backw]++];
 224                           else
 225                             {
 226                                 /* No more characters fit into the buffer.  */
 227                               needed += len;
 228                               idxarr[backw] += len;
 229                             }
 230                         }
 231
 232                       backw_stop = ~0ul;
 233                     }
 234
 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
 241                     {
 242                       /* No more characters fit into the buffer.  */
 243                       needed += len;
 244                       idxarr[idxcnt] += len;
 245                     }
 246                 }
 247               else
 248                 {
 249                   /* Remember where the backwards series started.  */
 250                   if (backw_stop == ~0ul)
 251                     backw_stop = idxcnt;
 252                 }
 253
 254               rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
 255             }
 256
 257
 258           if (backw_stop != ~0ul)
 259             {
 260               /* Handle the pushed elements now.  */
 261               size_t backw;
 262
 263               backw = idxcnt;
 264               while (backw > backw_stop)
 265                 {
 266                   size_t len = weights[idxarr[--backw]++];
 267
 268                   if (needed + len < n)
 269                     while (len-- > 0)
 270                       dest[needed++] = weights[idxarr[backw]++];
 271                   else
 272                     {
 273                       /* No more characters fit into the buffer.  */
 274                       needed += len;
 275                       idxarr[backw] += len;
 276                     }
 277                 }
 278             }
 279         }
 280       else
 281         {
 282           int val = 1;
 283 #ifndef WIDE_CHAR_VERSION
 284           char buf[7];
 285           size_t buflen;
 286 #endif
 287           size_t i;
 288
 289           for (idxcnt = 0; idxcnt < idxmax; ++idxcnt)
 290             {
 291               if ((rule & sort_forward) != 0)
 292                 {
 293                   size_t len;
 294
 295                   if (backw_stop != ~0ul)
 296                     {
 297                      /* Handle the pushed elements now.  */
 298                       size_t backw;
 299
 300                       for (backw = idxcnt; backw > backw_stop; )
 301                         {
 302                           --backw;
 303                           len = weights[idxarr[backw]++];
 304                           if (len != 0)
 305                             {
 306 #ifdef WIDE_CHAR_VERSION
 307                               if (needed + 1 + len < n)
 308                                 {
 309                                   dest[needed] = val;
 310                                   for (i = 0; i < len; ++i)
 311                                     dest[needed + 1 + i] =
 312                                       weights[idxarr[backw] + i];
 313                                 }
 314                               needed += 1 + len;
 315 #else
 316                               buflen = utf8_encode (buf, val);
 317                               if (needed + buflen + len < n)
 318                                 {
 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];
 324                                 }
 325                               needed += buflen + len;
 326 #endif
 327                               idxarr[backw] += len;
 328                               val = 1;
 329                             }
 330                           else
 331                             ++val;
 332                         }
 333
 334                       backw_stop = ~0ul;
 335                     }
 336
 337                   /* Now handle the forward element.  */
 338                   len = weights[idxarr[idxcnt]++];
 339                   if (len != 0)
 340                     {
 341 #ifdef WIDE_CHAR_VERSION
 342                       if (needed + 1+ len < n)
 343                         {
 344                           dest[needed] = val;
 345                           for (i = 0; i < len; ++i)
 346                             dest[needed + 1 + i] =
 347                               weights[idxarr[idxcnt] + i];
 348                         }
 349                       needed += 1 + len;
 350 #else
 351                       buflen = utf8_encode (buf, val);
 352                       if (needed + buflen + len < n)
 353                         {
 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];
 359                         }
 360                       needed += buflen + len;
 361 #endif
 362                       idxarr[idxcnt] += len;
 363                       val = 1;
 364                     }
 365                   else
 366                     /* Note that we don't have to increment `idxarr[idxcnt]'
 367                        since the length is zero.  */
 368                     ++val;
 369                 }
 370               else
 371                 {
 372                   /* Remember where the backwards series started.  */
 373                   if (backw_stop == ~0ul)
 374                     backw_stop = idxcnt;
 375                 }
 376
 377               rule = rulesets[rulearr[idxcnt + 1] * nrules + pass];
 378             }
 379
 380           if (backw_stop != ~0ul)
 381             {
 382               /* Handle the pushed elements now.  */
 383               size_t backw;
 384
 385               backw = idxmax - 1;
 386               while (backw > backw_stop)
 387                 {
 388                   size_t len = weights[idxarr[--backw]++];
 389                   if (len != 0)
 390                     {
 391 #ifdef WIDE_CHAR_VERSION
 392                       if (needed + 1 + len < n)
 393                         {
 394                           dest[needed] = val;
 395                           for (i = 0; i < len; ++i)
 396                             dest[needed + 1 + i] =
 397                               weights[idxarr[backw] + i];
 398                         }
 399                       needed += 1 + len;
 400 #else
 401                       buflen = utf8_encode (buf, val);
 402                       if (needed + buflen + len < n)
 403                         {
 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];
 409                         }
 410                       needed += buflen + len;
 411 #endif
 412                       idxarr[backw] += len;
 413                       val = 1;
 414                     }
 415                   else
 416                     ++val;
 417                 }
 418             }
 419         }
 420
 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;
 426     }
 427
 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)
 433     {
 434       /* Remove the \1 byte.  */
 435       if (--needed <= n)
 436         dest[needed - 1] = L('\0');
 437     }
 438
 439   /* Free the memory if needed.  */
 440   if (use_malloc)
 441     free (idxarr);
 442
 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;
 446 }
 447 libc_hidden_def (STRXFRM)
 448
 449 #ifndef WIDE_CHAR_VERSION
 450 weak_alias (__strxfrm_l, strxfrm_l)
 451 #endif