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. */ |
45 | typedef 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. */ |
64 | static __always_inline void |
65 | get_next_seq (coll_seq *seq, int nrules, const unsigned char *rulesets, |
66 | const USTRING_TYPE *weights, const int32_t *table, |
67 | const USTRING_TYPE *, 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. */ |
195 | static __always_inline int |
196 | do_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 | |
236 | out: |
237 | seq1->len = seq1len; |
238 | seq2->len = seq2len; |
239 | seq1->idx = idx1; |
240 | seq2->idx = idx2; |
241 | return result; |
242 | } |
243 | |
244 | int |
245 | STRCOLL (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 *; |
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 | } |
347 | libc_hidden_def (STRCOLL) |
348 | |
349 | #ifndef WIDE_CHAR_VERSION |
350 | weak_alias (__strcoll_l, strcoll_l) |
351 | #endif |
352 | |