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 Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the 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    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, write to the Free
  17    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  18    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 = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
 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 0;
 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 }