string/strcoll_l.c

   1 /* Copyright (C) 1995-2021 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3    Written by Ulrich Drepper <drepper@gnu.org>, 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, see
  17    <https://www.gnu.org/licenses/>.  */
  18
  19
  20 #include <assert.h>
  21 #include <langinfo.h>
  22 #include <locale.h>
  23 #include <stddef.h>
  24 #include <stdint.h>
  25 #include <string.h>
  26 #include <sys/param.h>
  27 #include <libc-diag.h>
  28
  29 #ifndef STRING_TYPE
  30 # define STRING_TYPE char
  31 # define USTRING_TYPE unsigned char
  32 # define STRCOLL __strcoll_l
  33 # define STRCMP strcmp
  34 # define WEIGHT_H "../locale/weight.h"
  35 # define SUFFIX MB
  36 # define L(arg) arg
  37 #endif
  38
  39 #define CONCAT(a,b) CONCAT1(a,b)
  40 #define CONCAT1(a,b) a##b
  41
  42 #include "../locale/localeinfo.h"
  43 #include WEIGHT_H
  44
  45 /* Track status while looking for sequences in a string.  */
  46 typedef struct
  47 {
  48   int len;                      /* Length of the current sequence.  */
  49   size_t val;                   /* Position of the sequence relative to the
  50                                    previous non-ignored sequence.  */
  51   size_t idxmax;                /* Maximum index in sequences.  */
  52   size_t idxcnt;                /* Current count of indices.  */
  53   size_t backw;                 /* Current Backward sequence index.  */
  54   size_t backw_stop;            /* Index where the backward sequences stop.  */
  55   const USTRING_TYPE *us;       /* The string.  */
  56   unsigned char rule;           /* Saved rule for the first sequence.  */
  57   int32_t idx;                  /* Index to weight of the current sequence.  */
  58   int32_t save_idx;             /* Save looked up index of a forward
  59                                    sequence after the last backward
  60                                    sequence.  */
  61   const USTRING_TYPE *back_us;  /* Beginning of the backward sequence.  */
  62 } coll_seq;
  63
  64 /* Get next sequence.  Traverse the string as required.  */
  65 static __always_inline void
  66 get_next_seq (coll_seq *seq, int nrules, const unsigned char *rulesets,
  67               const USTRING_TYPE *weights, const int32_t *table,
  68               const USTRING_TYPE *extra, const int32_t *indirect,
  69               int pass)
  70 {
  71   size_t val = seq->val = 0;
  72   int len = seq->len;
  73   size_t backw_stop = seq->backw_stop;
  74   size_t backw = seq->backw;
  75   size_t idxcnt = seq->idxcnt;
  76   size_t idxmax = seq->idxmax;
  77   int32_t idx = seq->idx;
  78   const USTRING_TYPE *us = seq->us;
  79
  80   while (len == 0)
  81     {
  82       ++val;
  83       if (backw_stop != ~0ul)
  84         {
  85           /* There is something pushed.  */
  86           if (backw == backw_stop)
  87             {
  88               /* The last pushed character was handled.  Continue
  89                  with forward characters.  */
  90               if (idxcnt < idxmax)
  91                 {
  92                   idx = seq->save_idx;
  93                   backw_stop = ~0ul;
  94                 }
  95               else
  96                 {
  97                   /* Nothing anymore.  The backward sequence ended with
  98                      the last sequence in the string.  Note that len is
  99                      still zero.  */
 100                   idx = 0;
 101                   break;
 102                 }
 103             }
 104           else
 105             {
 106               /* XXX Traverse BACKW sequences from the beginning of
 107                  BACKW_STOP to get the next sequence.  Is ther a quicker way
 108                  to do this?  */
 109               size_t i = backw_stop;
 110               us = seq->back_us;
 111               while (i < backw)
 112                 {
 113                   int32_t tmp = findidx (table, indirect, extra, &us, -1);
 114                   idx = tmp & 0xffffff;
 115                   i++;
 116                 }
 117               --backw;
 118               us = seq->us;
 119             }
 120         }
 121       else
 122         {
 123           backw_stop = idxmax;
 124           int32_t prev_idx = idx;
 125
 126           while (*us != L('\0'))
 127             {
 128               int32_t tmp = findidx (table, indirect, extra, &us, -1);
 129               unsigned char rule = tmp >> 24;
 130               prev_idx = idx;
 131               idx = tmp & 0xffffff;
 132               idxcnt = idxmax++;
 133
 134               /* Save the rule for the first sequence.  */
 135               if (__glibc_unlikely (idxcnt == 0))
 136                 seq->rule = rule;
 137
 138               if ((rulesets[rule * nrules + pass]
 139                    & sort_backward) == 0)
 140                 /* No more backward characters to push.  */
 141                 break;
 142               ++idxcnt;
 143             }
 144
 145           if (backw_stop >= idxcnt)
 146             {
 147               /* No sequence at all or just one.  */
 148               if (idxcnt == idxmax || backw_stop > idxcnt)
 149                 /* Note that len is still zero.  */
 150                 break;
 151
 152               backw_stop = ~0ul;
 153             }
 154           else
 155             {
 156               /* We pushed backward sequences.  If the stream ended with the
 157                  backward sequence, then we process the last sequence we
 158                  found.  Otherwise we process the sequence before the last
 159                  one since the last one was a forward sequence.  */
 160               seq->back_us = seq->us;
 161               seq->us = us;
 162               backw = idxcnt;
 163               if (idxmax > idxcnt)
 164                 {
 165                   backw--;
 166                   seq->save_idx = idx;
 167                   idx = prev_idx;
 168                 }
 169               if (backw > backw_stop)
 170                 backw--;
 171             }
 172         }
 173
 174       /* With GCC 5.3 when compiling with -Os the compiler complains
 175          that idx, taken from seq->idx (seq1 or seq2 from STRCOLL) may
 176          be used uninitialized.  In general this can't possibly be true
 177          since seq1.idx and seq2.idx are initialized to zero in the
 178          outer function.  Only one case where seq->idx is restored from
 179          seq->save_idx might result in an uninitialized idx value, but
 180          it is guarded by a sequence of checks against backw_stop which
 181          ensures that seq->save_idx was saved to first and contains a
 182          valid value.  */
 183       DIAG_PUSH_NEEDS_COMMENT;
 184       DIAG_IGNORE_Os_NEEDS_COMMENT (5, "-Wmaybe-uninitialized");
 185       len = weights[idx++];
 186       DIAG_POP_NEEDS_COMMENT;
 187       /* Skip over indices of previous levels.  */
 188       for (int i = 0; i < pass; i++)
 189         {
 190           idx += len;
 191           len = weights[idx];
 192           idx++;
 193         }
 194     }
 195
 196   /* Update the structure.  */
 197   seq->val = val;
 198   seq->len = len;
 199   seq->backw_stop = backw_stop;
 200   seq->backw = backw;
 201   seq->idxcnt = idxcnt;
 202   seq->idxmax = idxmax;
 203   seq->us = us;
 204   seq->idx = idx;
 205 }
 206
 207 /* Compare two sequences.  */
 208 static __always_inline int
 209 do_compare (coll_seq *seq1, coll_seq *seq2, int position,
 210             const USTRING_TYPE *weights)
 211 {
 212   int seq1len = seq1->len;
 213   int seq2len = seq2->len;
 214   size_t val1 = seq1->val;
 215   size_t val2 = seq2->val;
 216   int idx1 = seq1->idx;
 217   int idx2 = seq2->idx;
 218   int result = 0;
 219
 220   /* Test for position if necessary.  */
 221   if (position && val1 != val2)
 222     {
 223       result = val1 > val2 ? 1 : -1;
 224       goto out;
 225     }
 226
 227   /* Compare the two sequences.  */
 228   do
 229     {
 230       if (weights[idx1] != weights[idx2])
 231         {
 232           /* The sequences differ.  */
 233           result = weights[idx1] - weights[idx2];
 234           goto out;
 235         }
 236
 237       /* Increment the offsets.  */
 238       ++idx1;
 239       ++idx2;
 240
 241       --seq1len;
 242       --seq2len;
 243     }
 244   while (seq1len > 0 && seq2len > 0);
 245
 246   if (position && seq1len != seq2len)
 247     result = seq1len - seq2len;
 248
 249 out:
 250   seq1->len = seq1len;
 251   seq2->len = seq2len;
 252   seq1->idx = idx1;
 253   seq2->idx = idx2;
 254   return result;
 255 }
 256
 257 int
 258 STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, locale_t l)
 259 {
 260   struct __locale_data *current = l->__locales[LC_COLLATE];
 261   uint_fast32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
 262   /* We don't assign the following values right away since it might be
 263      unnecessary in case there are no rules.  */
 264   const unsigned char *rulesets;
 265   const int32_t *table;
 266   const USTRING_TYPE *weights;
 267   const USTRING_TYPE *extra;
 268   const int32_t *indirect;
 269
 270   if (nrules == 0)
 271     return STRCMP (s1, s2);
 272
 273   /* Catch empty strings.  */
 274   if (__glibc_unlikely (*s1 == '\0') || __glibc_unlikely (*s2 == '\0'))
 275     return (*s1 != '\0') - (*s2 != '\0');
 276
 277   rulesets = (const unsigned char *)
 278     current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
 279   table = (const int32_t *)
 280     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
 281   weights = (const USTRING_TYPE *)
 282     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
 283   extra = (const USTRING_TYPE *)
 284     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
 285   indirect = (const int32_t *)
 286     current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
 287
 288   assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
 289   assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
 290   assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
 291   assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
 292
 293   int result = 0, rule = 0;
 294
 295   /* With GCC 7 when compiling with -Os the compiler warns that
 296      seq1.back_us and seq2.back_us might be used uninitialized.
 297      Sometimes this warning appears at locations in locale/weightwc.h
 298      where the actual use is, but on architectures other than x86_64,
 299      x86 and s390x, a warning appears at the definitions of seq1 and
 300      seq2.  This uninitialized use is impossible for the same reason
 301      as described in comments in locale/weightwc.h.  */
 302   DIAG_PUSH_NEEDS_COMMENT;
 303   DIAG_IGNORE_Os_NEEDS_COMMENT (7, "-Wmaybe-uninitialized");
 304   coll_seq seq1, seq2;
 305   DIAG_POP_NEEDS_COMMENT;
 306   seq1.len = 0;
 307   seq1.idxmax = 0;
 308   seq1.rule = 0;
 309   seq2.len = 0;
 310   seq2.idxmax = 0;
 311
 312   for (int pass = 0; pass < nrules; ++pass)
 313     {
 314       seq1.idxcnt = 0;
 315       seq1.idx = 0;
 316       seq2.idx = 0;
 317       seq1.backw_stop = ~0ul;
 318       seq1.backw = ~0ul;
 319       seq2.idxcnt = 0;
 320       seq2.backw_stop = ~0ul;
 321       seq2.backw = ~0ul;
 322
 323       /* We need the elements of the strings as unsigned values since they
 324          are used as indices.  */
 325       seq1.us = (const USTRING_TYPE *) s1;
 326       seq2.us = (const USTRING_TYPE *) s2;
 327
 328       /* We assume that if a rule has defined `position' in one section
 329          this is true for all of them.  Please note that the localedef programs
 330          makes sure that `position' is not used at the first level.  */
 331
 332       int position = rulesets[rule * nrules + pass] & sort_position;
 333
 334       while (1)
 335         {
 336           get_next_seq (&seq1, nrules, rulesets, weights, table,
 337                                     extra, indirect, pass);
 338           get_next_seq (&seq2, nrules, rulesets, weights, table,
 339                                     extra, indirect, pass);
 340           /* See whether any or both strings are empty.  */
 341           if (seq1.len == 0 || seq2.len == 0)
 342             {
 343               if (seq1.len == seq2.len)
 344                 {
 345                   /* Both strings ended and are equal at this level.  Do a
 346                      byte-level comparison to ensure that we don't waste time
 347                      going through multiple passes for totally equal strings
 348                      before proceeding to subsequent passes.  */
 349                   if (pass == 0 && STRCMP (s1, s2) == 0)
 350                     return result;
 351                   else
 352                     break;
 353                 }
 354
 355               /* This means one string is shorter than the other.  Find out
 356                  which one and return an appropriate value.  */
 357               return seq1.len == 0 ? -1 : 1;
 358             }
 359
 360           result = do_compare (&seq1, &seq2, position, weights);
 361           if (result != 0)
 362             return result;
 363         }
 364
 365       rule = seq1.rule;
 366     }
 367
 368   return result;
 369 }
 370 libc_hidden_def (STRCOLL)
 371
 372 #ifndef WIDE_CHAR_VERSION
 373 weak_alias (__strcoll_l, strcoll_l)
 374 #endif