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