string/strxfrm.c

   1 /* Copyright (C) 1995, 1996 Free Software Foundation, Inc.
   2 This file is part of the GNU C Library.
   3 Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 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
  17 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18 Boston, MA 02111-1307, USA.  */
  19
  20 #include <stddef.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #ifndef WIDE_VERSION
  25 # define STRING_TYPE char
  26 # define USTRING_TYPE unsigned char
  27 # define L_(Ch) Ch
  28 # define STRXFRM strxfrm
  29 # define STRLEN strlen
  30 # define STPNCPY __stpncpy
  31 #endif
  32
  33 /* Include the shared helper functions.  `strxfrm'/`wcsxfrm' also use
  34    these functions.  */
  35 #include "../locale/weight.h"
  36
  37
  38 #ifndef WIDE_VERSION
  39 /* Write 32 bit value UTF-8 encoded but only if enough space is left.  */
  40 static __inline size_t
  41 print_val (u_int32_t value, char *dest, size_t max, size_t act)
  42 {
  43   char tmp[6];
  44   int idx = 0;
  45
  46   if (value < 0x80)
  47     tmp[idx++] = (char) value;
  48   else
  49     {
  50       tmp[idx++] = '\x80' + (char) (value & 0x3f);
  51       value >>= 6;
  52
  53       if (value < 0x20)
  54         tmp[idx++] = '\xc0' + (char) value;
  55       else
  56         {
  57           tmp[idx++] = '\x80' + (char) (value & 0x3f);
  58           value >>= 6;
  59
  60           if (value < 0x10)
  61             tmp[idx++] = '\xe0' + (char) value;
  62           else
  63             {
  64               tmp[idx++] = '\x80' + (char) (value & 0x3f);
  65               value >>= 6;
  66
  67               if (value < 0x08)
  68                 tmp[idx++] = '\xf0' + (char) value;
  69               else
  70                 {
  71                   tmp[idx++] = '\x80' + (char) (value & 0x3f);
  72                   value >>= 6;
  73
  74                   if (value < 0x04)
  75                     tmp[idx++] = '\xf8' + (char) value;
  76                   else
  77                     {
  78                       tmp[idx++] = '\x80' + (char) (value & 0x3f);
  79                       tmp[idx++] = '\xfc' + (char) (value >> 6);
  80                     }
  81                 }
  82             }
  83         }
  84     }
  85
  86   while (idx-- > 0)
  87     {
  88       if (act < max)
  89         dest[act] = tmp[idx];
  90       ++act;
  91     }
  92
  93   return act;
  94 }
  95 #else
  96 static __inline size_t
  97 print_val (u_int32_t value, wchar_t *dest, size_t max, size_t act)
  98 {
  99   /* We cannot really assume wchar_t is 32 bits wide.  But it is for
 100      GCC and so we don't do much optimization for the other case.  */
 101   if (sizeof (wchar_t) == 4)
 102     {
 103       if (act < max)
 104         dest[act] = (wchar_t) value;
 105       ++act;
 106     }
 107   else
 108     {
 109       wchar_t tmp[3];
 110       size_t idx = 0;
 111
 112       if (value < 0x8000)
 113         tmp[idx++] = (wchar_t) act;
 114       else
 115         {
 116           tmp[idx++] = (wchar_t) (0x8000 + (value & 0x3fff));
 117           value >>= 14;
 118           if (value < 0x2000)
 119             tmp[idx++] = (wchar_t) (0xc000 + value);
 120           else
 121             {
 122               tmp[idx++] = (wchar_t) (0x8000 + (value & 0x3fff));
 123               value >>= 14;
 124               tmp[idx++] = (wchar_t) (0xe000 + value);
 125             }
 126         }
 127       while (idx-- > 0)
 128         {
 129           if (act < max)
 130             dest[act] = tmp[idx];
 131           ++act;
 132         }
 133     }
 134   return act;
 135 }
 136 #endif
 137
 138
 139 /* Transform SRC into a form such that the result of strcmp
 140    on two strings that have been transformed by strxfrm is
 141    the same as the result of strcoll on the two strings before
 142    their transformation.  The transformed string is put in at
 143    most N characters of DEST and its length is returned.  */
 144 size_t
 145 STRXFRM (STRING_TYPE *dest, const STRING_TYPE *src, size_t n)
 146 {
 147   weight_t *forw = NULL;
 148   weight_t *backw = NULL;
 149   size_t pass;
 150   size_t written;
 151
 152   /* If the current locale does not specify locale data we use normal
 153      8-bit string comparison.  */
 154   if (collate_nrules == 0)
 155     {
 156       if (n != 0)
 157         STPNCPY (dest, src, n);
 158
 159       return STRLEN (src);
 160     }
 161
 162   /* Get full information about the string.  This means we get
 163      information for all passes in a special data structure.  */
 164   get_string (src, forw, backw);
 165
 166   /* Now we have all the information.  In at most the given number of
 167      passes we can finally decide about the order.  */
 168   written = 0;
 169   for (pass = 0; pass < collate_nrules; ++pass)
 170     {
 171       int forward = (collate_rules[pass] & sort_forward) != 0;
 172       const weight_t *run = forward ? forw : backw;
 173       int idx = forward ? 0 : run->data[pass].number - 1;
 174
 175       do
 176         {
 177           int ignore = 0;
 178           u_int32_t w;
 179
 180           /* Here we have to check for IGNORE entries.  If these are
 181              found we count them and go on witht he next value.  */
 182           while ((w = run->data[pass].value[idx]) == IGNORE_CHAR)
 183             {
 184               ++ignore;
 185               if ((forward && ++idx >= run->data[pass].number)
 186                   || (!forward && --idx < 0))
 187                 {
 188                   weight_t *nextp = forward ? run->next : run->prev;
 189                   if (nextp == NULL)
 190                     {
 191                       w = 0;
 192                       break;
 193                     }
 194                   run = nextp;
 195                   idx = forward ? 0 : run->data[pass].number - 1;
 196                 }
 197             }
 198
 199           /* Now we have information of the number of ignored weights
 200              and the value of the next weight.  We have to add 2
 201              because 0 means EOS and 1 is the intermediate string end.  */
 202           if ((collate_rules[pass] & sort_position) != 0)
 203             written = print_val (ignore + 2, dest, n, written);
 204
 205           if (w != 0)
 206             written = print_val (w, dest, n, written);
 207
 208           /* We have to increment the index counters.  */
 209           if ((forward && ++idx >= run->data[pass].number)
 210               || (!forward && --idx < 0))
 211             if (forward)
 212               {
 213                 run = run->next;
 214                 idx = 0;
 215               }
 216             else
 217               {
 218                 run = run->prev;
 219                 if (run != NULL)
 220                   idx = run->data[pass].number - 1;
 221               }
 222         }
 223       while (run != NULL);
 224
 225       /* Write marker for end of word.  */
 226       if (pass + 1 < collate_nrules)
 227         written = print_val (1, dest, n, written);
 228     }
 229
 230   /* Terminate string.  */
 231   if (written < n)
 232     dest[written] = L_('\0');
 233
 234   /* Return length without counting the terminating '\0'.  */
 235   return written;
 236 }