1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 *******************************************************************************
5 * Copyright (C) 2013-2015, International Business Machines
6 * Corporation and others.  All Rights Reserved.
7 *******************************************************************************
8 * collationfastlatin.cpp
9 *
10 * created on: 2013aug18
11 * created by: Markus W. Scherer
12 */
13 
14 #include "unicode/utypes.h"
15 
16 #if !UCONFIG_NO_COLLATION
17 
18 #include "unicode/ucol.h"
19 #include "collationdata.h"
20 #include "collationfastlatin.h"
21 #include "collationsettings.h"
22 #include "uassert.h"
23 
24 U_NAMESPACE_BEGIN
25 
26 int32_t
getOptions(const CollationData * data,const CollationSettings & settings,uint16_t * primaries,int32_t capacity)27 CollationFastLatin::getOptions(const CollationData *data, const CollationSettings &settings,
28                                uint16_t *primaries, int32_t capacity) {
29     const uint16_t *table = data->fastLatinTable;
30     if(table == NULL) { return -1; }
31     U_ASSERT(capacity == LATIN_LIMIT);
32     if(capacity != LATIN_LIMIT) { return -1; }
33 
34     uint32_t miniVarTop;
35     if((settings.options & CollationSettings::ALTERNATE_MASK) == 0) {
36         // No mini primaries are variable, set a variableTop just below the
37         // lowest long mini primary.
38         miniVarTop = MIN_LONG - 1;
39     } else {
40         int32_t headerLength = *table & 0xff;
41         int32_t i = 1 + settings.getMaxVariable();
42         if(i >= headerLength) {
43             return -1;  // variableTop >= digits, should not occur
44         }
45         miniVarTop = table[i];
46     }
47 
48     UBool digitsAreReordered = FALSE;
49     if(settings.hasReordering()) {
50         uint32_t prevStart = 0;
51         uint32_t beforeDigitStart = 0;
52         uint32_t digitStart = 0;
53         uint32_t afterDigitStart = 0;
54         for(int32_t group = UCOL_REORDER_CODE_FIRST;
55                 group < UCOL_REORDER_CODE_FIRST + CollationData::MAX_NUM_SPECIAL_REORDER_CODES;
56                 ++group) {
57             uint32_t start = data->getFirstPrimaryForGroup(group);
58             start = settings.reorder(start);
59             if(group == UCOL_REORDER_CODE_DIGIT) {
60                 beforeDigitStart = prevStart;
61                 digitStart = start;
62             } else if(start != 0) {
63                 if(start < prevStart) {
64                     // The permutation affects the groups up to Latin.
65                     return -1;
66                 }
67                 // In the future, there might be a special group between digits & Latin.
68                 if(digitStart != 0 && afterDigitStart == 0 && prevStart == beforeDigitStart) {
69                     afterDigitStart = start;
70                 }
71                 prevStart = start;
72             }
73         }
74         uint32_t latinStart = data->getFirstPrimaryForGroup(USCRIPT_LATIN);
75         latinStart = settings.reorder(latinStart);
76         if(latinStart < prevStart) {
77             return -1;
78         }
79         if(afterDigitStart == 0) {
80             afterDigitStart = latinStart;
81         }
82         if(!(beforeDigitStart < digitStart && digitStart < afterDigitStart)) {
83             digitsAreReordered = TRUE;
84         }
85     }
86 
87     table += (table[0] & 0xff);  // skip the header
88     for(UChar32 c = 0; c < LATIN_LIMIT; ++c) {
89         uint32_t p = table[c];
90         if(p >= MIN_SHORT) {
91             p &= SHORT_PRIMARY_MASK;
92         } else if(p > miniVarTop) {
93             p &= LONG_PRIMARY_MASK;
94         } else {
95             p = 0;
96         }
97         primaries[c] = (uint16_t)p;
98     }
99     if(digitsAreReordered || (settings.options & CollationSettings::NUMERIC) != 0) {
100         // Bail out for digits.
101         for(UChar32 c = 0x30; c <= 0x39; ++c) { primaries[c] = 0; }
102     }
103 
104     // Shift the miniVarTop above other options.
105     return ((int32_t)miniVarTop << 16) | settings.options;
106 }
107 
108 int32_t
compareUTF16(const uint16_t * table,const uint16_t * primaries,int32_t options,const UChar * left,int32_t leftLength,const UChar * right,int32_t rightLength)109 CollationFastLatin::compareUTF16(const uint16_t *table, const uint16_t *primaries, int32_t options,
110                                  const UChar *left, int32_t leftLength,
111                                  const UChar *right, int32_t rightLength) {
112     // This is a modified copy of CollationCompare::compareUpToQuaternary(),
113     // optimized for common Latin text.
114     // Keep them in sync!
115     // Keep compareUTF16() and compareUTF8() in sync very closely!
116 
117     U_ASSERT((table[0] >> 8) == VERSION);
118     table += (table[0] & 0xff);  // skip the header
119     uint32_t variableTop = (uint32_t)options >> 16;  // see getOptions()
120     options &= 0xffff;  // needed for CollationSettings::getStrength() to work
121 
122     // Check for supported characters, fetch mini CEs, and compare primaries.
123     int32_t leftIndex = 0, rightIndex = 0;
124     /**
125      * Single mini CE or a pair.
126      * The current mini CE is in the lower 16 bits, the next one is in the upper 16 bits.
127      * If there is only one, then it is in the lower bits, and the upper bits are 0.
128      */
129     uint32_t leftPair = 0, rightPair = 0;
130     for(;;) {
131         // We fetch CEs until we get a non-ignorable primary or reach the end.
132         while(leftPair == 0) {
133             if(leftIndex == leftLength) {
134                 leftPair = EOS;
135                 break;
136             }
137             UChar32 c = left[leftIndex++];
138             if(c <= LATIN_MAX) {
139                 leftPair = primaries[c];
140                 if(leftPair != 0) { break; }
141                 if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) {
142                     return BAIL_OUT_RESULT;
143                 }
144                 leftPair = table[c];
145             } else if(PUNCT_START <= c && c < PUNCT_LIMIT) {
146                 leftPair = table[c - PUNCT_START + LATIN_LIMIT];
147             } else {
148                 leftPair = lookup(table, c);
149             }
150             if(leftPair >= MIN_SHORT) {
151                 leftPair &= SHORT_PRIMARY_MASK;
152                 break;
153             } else if(leftPair > variableTop) {
154                 leftPair &= LONG_PRIMARY_MASK;
155                 break;
156             } else {
157                 leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength);
158                 if(leftPair == BAIL_OUT) { return BAIL_OUT_RESULT; }
159                 leftPair = getPrimaries(variableTop, leftPair);
160             }
161         }
162 
163         while(rightPair == 0) {
164             if(rightIndex == rightLength) {
165                 rightPair = EOS;
166                 break;
167             }
168             UChar32 c = right[rightIndex++];
169             if(c <= LATIN_MAX) {
170                 rightPair = primaries[c];
171                 if(rightPair != 0) { break; }
172                 if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) {
173                     return BAIL_OUT_RESULT;
174                 }
175                 rightPair = table[c];
176             } else if(PUNCT_START <= c && c < PUNCT_LIMIT) {
177                 rightPair = table[c - PUNCT_START + LATIN_LIMIT];
178             } else {
179                 rightPair = lookup(table, c);
180             }
181             if(rightPair >= MIN_SHORT) {
182                 rightPair &= SHORT_PRIMARY_MASK;
183                 break;
184             } else if(rightPair > variableTop) {
185                 rightPair &= LONG_PRIMARY_MASK;
186                 break;
187             } else {
188                 rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength);
189                 if(rightPair == BAIL_OUT) { return BAIL_OUT_RESULT; }
190                 rightPair = getPrimaries(variableTop, rightPair);
191             }
192         }
193 
194         if(leftPair == rightPair) {
195             if(leftPair == EOS) { break; }
196             leftPair = rightPair = 0;
197             continue;
198         }
199         uint32_t leftPrimary = leftPair & 0xffff;
200         uint32_t rightPrimary = rightPair & 0xffff;
201         if(leftPrimary != rightPrimary) {
202             // Return the primary difference.
203             return (leftPrimary < rightPrimary) ? UCOL_LESS : UCOL_GREATER;
204         }
205         if(leftPair == EOS) { break; }
206         leftPair >>= 16;
207         rightPair >>= 16;
208     }
209     // In the following, we need to re-fetch each character because we did not buffer the CEs,
210     // but we know that the string is well-formed and
211     // only contains supported characters and mappings.
212 
213     // We might skip the secondary level but continue with the case level
214     // which is turned on separately.
215     if(CollationSettings::getStrength(options) >= UCOL_SECONDARY) {
216         leftIndex = rightIndex = 0;
217         leftPair = rightPair = 0;
218         for(;;) {
219             while(leftPair == 0) {
220                 if(leftIndex == leftLength) {
221                     leftPair = EOS;
222                     break;
223                 }
224                 UChar32 c = left[leftIndex++];
225                 if(c <= LATIN_MAX) {
226                     leftPair = table[c];
227                 } else if(PUNCT_START <= c && c < PUNCT_LIMIT) {
228                     leftPair = table[c - PUNCT_START + LATIN_LIMIT];
229                 } else {
230                     leftPair = lookup(table, c);
231                 }
232                 if(leftPair >= MIN_SHORT) {
233                     leftPair = getSecondariesFromOneShortCE(leftPair);
234                     break;
235                 } else if(leftPair > variableTop) {
236                     leftPair = COMMON_SEC_PLUS_OFFSET;
237                     break;
238                 } else {
239                     leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength);
240                     leftPair = getSecondaries(variableTop, leftPair);
241                 }
242             }
243 
244             while(rightPair == 0) {
245                 if(rightIndex == rightLength) {
246                     rightPair = EOS;
247                     break;
248                 }
249                 UChar32 c = right[rightIndex++];
250                 if(c <= LATIN_MAX) {
251                     rightPair = table[c];
252                 } else if(PUNCT_START <= c && c < PUNCT_LIMIT) {
253                     rightPair = table[c - PUNCT_START + LATIN_LIMIT];
254                 } else {
255                     rightPair = lookup(table, c);
256                 }
257                 if(rightPair >= MIN_SHORT) {
258                     rightPair = getSecondariesFromOneShortCE(rightPair);
259                     break;
260                 } else if(rightPair > variableTop) {
261                     rightPair = COMMON_SEC_PLUS_OFFSET;
262                     break;
263                 } else {
264                     rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength);
265                     rightPair = getSecondaries(variableTop, rightPair);
266                 }
267             }
268 
269             if(leftPair == rightPair) {
270                 if(leftPair == EOS) { break; }
271                 leftPair = rightPair = 0;
272                 continue;
273             }
274             uint32_t leftSecondary = leftPair & 0xffff;
275             uint32_t rightSecondary = rightPair & 0xffff;
276             if(leftSecondary != rightSecondary) {
277                 if((options & CollationSettings::BACKWARD_SECONDARY) != 0) {
278                     // Full support for backwards secondary requires backwards contraction matching
279                     // and moving backwards between merge separators.
280                     return BAIL_OUT_RESULT;
281                 }
282                 return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER;
283             }
284             if(leftPair == EOS) { break; }
285             leftPair >>= 16;
286             rightPair >>= 16;
287         }
288     }
289 
290     if((options & CollationSettings::CASE_LEVEL) != 0) {
291         UBool strengthIsPrimary = CollationSettings::getStrength(options) == UCOL_PRIMARY;
292         leftIndex = rightIndex = 0;
293         leftPair = rightPair = 0;
294         for(;;) {
295             while(leftPair == 0) {
296                 if(leftIndex == leftLength) {
297                     leftPair = EOS;
298                     break;
299                 }
300                 UChar32 c = left[leftIndex++];
301                 leftPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c);
302                 if(leftPair < MIN_LONG) {
303                     leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength);
304                 }
305                 leftPair = getCases(variableTop, strengthIsPrimary, leftPair);
306             }
307 
308             while(rightPair == 0) {
309                 if(rightIndex == rightLength) {
310                     rightPair = EOS;
311                     break;
312                 }
313                 UChar32 c = right[rightIndex++];
314                 rightPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c);
315                 if(rightPair < MIN_LONG) {
316                     rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength);
317                 }
318                 rightPair = getCases(variableTop, strengthIsPrimary, rightPair);
319             }
320 
321             if(leftPair == rightPair) {
322                 if(leftPair == EOS) { break; }
323                 leftPair = rightPair = 0;
324                 continue;
325             }
326             uint32_t leftCase = leftPair & 0xffff;
327             uint32_t rightCase = rightPair & 0xffff;
328             if(leftCase != rightCase) {
329                 if((options & CollationSettings::UPPER_FIRST) == 0) {
330                     return (leftCase < rightCase) ? UCOL_LESS : UCOL_GREATER;
331                 } else {
332                     return (leftCase < rightCase) ? UCOL_GREATER : UCOL_LESS;
333                 }
334             }
335             if(leftPair == EOS) { break; }
336             leftPair >>= 16;
337             rightPair >>= 16;
338         }
339     }
340     if(CollationSettings::getStrength(options) <= UCOL_SECONDARY) { return UCOL_EQUAL; }
341 
342     // Remove the case bits from the tertiary weight when caseLevel is on or caseFirst is off.
343     UBool withCaseBits = CollationSettings::isTertiaryWithCaseBits(options);
344 
345     leftIndex = rightIndex = 0;
346     leftPair = rightPair = 0;
347     for(;;) {
348         while(leftPair == 0) {
349             if(leftIndex == leftLength) {
350                 leftPair = EOS;
351                 break;
352             }
353             UChar32 c = left[leftIndex++];
354             leftPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c);
355             if(leftPair < MIN_LONG) {
356                 leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength);
357             }
358             leftPair = getTertiaries(variableTop, withCaseBits, leftPair);
359         }
360 
361         while(rightPair == 0) {
362             if(rightIndex == rightLength) {
363                 rightPair = EOS;
364                 break;
365             }
366             UChar32 c = right[rightIndex++];
367             rightPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c);
368             if(rightPair < MIN_LONG) {
369                 rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength);
370             }
371             rightPair = getTertiaries(variableTop, withCaseBits, rightPair);
372         }
373 
374         if(leftPair == rightPair) {
375             if(leftPair == EOS) { break; }
376             leftPair = rightPair = 0;
377             continue;
378         }
379         uint32_t leftTertiary = leftPair & 0xffff;
380         uint32_t rightTertiary = rightPair & 0xffff;
381         if(leftTertiary != rightTertiary) {
382             if(CollationSettings::sortsTertiaryUpperCaseFirst(options)) {
383                 // Pass through EOS and MERGE_WEIGHT
384                 // and keep real tertiary weights larger than the MERGE_WEIGHT.
385                 // Tertiary CEs (secondary ignorables) are not supported in fast Latin.
386                 if(leftTertiary > MERGE_WEIGHT) {
387                     leftTertiary ^= CASE_MASK;
388                 }
389                 if(rightTertiary > MERGE_WEIGHT) {
390                     rightTertiary ^= CASE_MASK;
391                 }
392             }
393             return (leftTertiary < rightTertiary) ? UCOL_LESS : UCOL_GREATER;
394         }
395         if(leftPair == EOS) { break; }
396         leftPair >>= 16;
397         rightPair >>= 16;
398     }
399     if(CollationSettings::getStrength(options) <= UCOL_TERTIARY) { return UCOL_EQUAL; }
400 
401     leftIndex = rightIndex = 0;
402     leftPair = rightPair = 0;
403     for(;;) {
404         while(leftPair == 0) {
405             if(leftIndex == leftLength) {
406                 leftPair = EOS;
407                 break;
408             }
409             UChar32 c = left[leftIndex++];
410             leftPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c);
411             if(leftPair < MIN_LONG) {
412                 leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength);
413             }
414             leftPair = getQuaternaries(variableTop, leftPair);
415         }
416 
417         while(rightPair == 0) {
418             if(rightIndex == rightLength) {
419                 rightPair = EOS;
420                 break;
421             }
422             UChar32 c = right[rightIndex++];
423             rightPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c);
424             if(rightPair < MIN_LONG) {
425                 rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength);
426             }
427             rightPair = getQuaternaries(variableTop, rightPair);
428         }
429 
430         if(leftPair == rightPair) {
431             if(leftPair == EOS) { break; }
432             leftPair = rightPair = 0;
433             continue;
434         }
435         uint32_t leftQuaternary = leftPair & 0xffff;
436         uint32_t rightQuaternary = rightPair & 0xffff;
437         if(leftQuaternary != rightQuaternary) {
438             return (leftQuaternary < rightQuaternary) ? UCOL_LESS : UCOL_GREATER;
439         }
440         if(leftPair == EOS) { break; }
441         leftPair >>= 16;
442         rightPair >>= 16;
443     }
444     return UCOL_EQUAL;
445 }
446 
447 int32_t
compareUTF8(const uint16_t * table,const uint16_t * primaries,int32_t options,const uint8_t * left,int32_t leftLength,const uint8_t * right,int32_t rightLength)448 CollationFastLatin::compareUTF8(const uint16_t *table, const uint16_t *primaries, int32_t options,
449                                  const uint8_t *left, int32_t leftLength,
450                                  const uint8_t *right, int32_t rightLength) {
451     // Keep compareUTF16() and compareUTF8() in sync very closely!
452 
453     U_ASSERT((table[0] >> 8) == VERSION);
454     table += (table[0] & 0xff);  // skip the header
455     uint32_t variableTop = (uint32_t)options >> 16;  // see RuleBasedCollator::getFastLatinOptions()
456     options &= 0xffff;  // needed for CollationSettings::getStrength() to work
457 
458     // Check for supported characters, fetch mini CEs, and compare primaries.
459     int32_t leftIndex = 0, rightIndex = 0;
460     /**
461      * Single mini CE or a pair.
462      * The current mini CE is in the lower 16 bits, the next one is in the upper 16 bits.
463      * If there is only one, then it is in the lower bits, and the upper bits are 0.
464      */
465     uint32_t leftPair = 0, rightPair = 0;
466     // Note: There is no need to assemble the code point.
467     // We only need to look up the table entry for the character,
468     // and nextPair() looks for whether c==0.
469     for(;;) {
470         // We fetch CEs until we get a non-ignorable primary or reach the end.
471         while(leftPair == 0) {
472             if(leftIndex == leftLength) {
473                 leftPair = EOS;
474                 break;
475             }
476             UChar32 c = left[leftIndex++];
477             uint8_t t;
478             if(c <= 0x7f) {
479                 leftPair = primaries[c];
480                 if(leftPair != 0) { break; }
481                 if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) {
482                     return BAIL_OUT_RESULT;
483                 }
484                 leftPair = table[c];
485             } else if(c <= LATIN_MAX_UTF8_LEAD && 0xc2 <= c && leftIndex != leftLength &&
486                     0x80 <= (t = left[leftIndex]) && t <= 0xbf) {
487                 ++leftIndex;
488                 c = ((c - 0xc2) << 6) + t;
489                 leftPair = primaries[c];
490                 if(leftPair != 0) { break; }
491                 leftPair = table[c];
492             } else {
493                 leftPair = lookupUTF8(table, c, left, leftIndex, leftLength);
494             }
495             if(leftPair >= MIN_SHORT) {
496                 leftPair &= SHORT_PRIMARY_MASK;
497                 break;
498             } else if(leftPair > variableTop) {
499                 leftPair &= LONG_PRIMARY_MASK;
500                 break;
501             } else {
502                 leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
503                 if(leftPair == BAIL_OUT) { return BAIL_OUT_RESULT; }
504                 leftPair = getPrimaries(variableTop, leftPair);
505             }
506         }
507 
508         while(rightPair == 0) {
509             if(rightIndex == rightLength) {
510                 rightPair = EOS;
511                 break;
512             }
513             UChar32 c = right[rightIndex++];
514             uint8_t t;
515             if(c <= 0x7f) {
516                 rightPair = primaries[c];
517                 if(rightPair != 0) { break; }
518                 if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) {
519                     return BAIL_OUT_RESULT;
520                 }
521                 rightPair = table[c];
522             } else if(c <= LATIN_MAX_UTF8_LEAD && 0xc2 <= c && rightIndex != rightLength &&
523                     0x80 <= (t = right[rightIndex]) && t <= 0xbf) {
524                 ++rightIndex;
525                 c = ((c - 0xc2) << 6) + t;
526                 rightPair = primaries[c];
527                 if(rightPair != 0) { break; }
528                 rightPair = table[c];
529             } else {
530                 rightPair = lookupUTF8(table, c, right, rightIndex, rightLength);
531             }
532             if(rightPair >= MIN_SHORT) {
533                 rightPair &= SHORT_PRIMARY_MASK;
534                 break;
535             } else if(rightPair > variableTop) {
536                 rightPair &= LONG_PRIMARY_MASK;
537                 break;
538             } else {
539                 rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
540                 if(rightPair == BAIL_OUT) { return BAIL_OUT_RESULT; }
541                 rightPair = getPrimaries(variableTop, rightPair);
542             }
543         }
544 
545         if(leftPair == rightPair) {
546             if(leftPair == EOS) { break; }
547             leftPair = rightPair = 0;
548             continue;
549         }
550         uint32_t leftPrimary = leftPair & 0xffff;
551         uint32_t rightPrimary = rightPair & 0xffff;
552         if(leftPrimary != rightPrimary) {
553             // Return the primary difference.
554             return (leftPrimary < rightPrimary) ? UCOL_LESS : UCOL_GREATER;
555         }
556         if(leftPair == EOS) { break; }
557         leftPair >>= 16;
558         rightPair >>= 16;
559     }
560     // In the following, we need to re-fetch each character because we did not buffer the CEs,
561     // but we know that the string is well-formed and
562     // only contains supported characters and mappings.
563 
564     // We might skip the secondary level but continue with the case level
565     // which is turned on separately.
566     if(CollationSettings::getStrength(options) >= UCOL_SECONDARY) {
567         leftIndex = rightIndex = 0;
568         leftPair = rightPair = 0;
569         for(;;) {
570             while(leftPair == 0) {
571                 if(leftIndex == leftLength) {
572                     leftPair = EOS;
573                     break;
574                 }
575                 UChar32 c = left[leftIndex++];
576                 if(c <= 0x7f) {
577                     leftPair = table[c];
578                 } else if(c <= LATIN_MAX_UTF8_LEAD) {
579                     leftPair = table[((c - 0xc2) << 6) + left[leftIndex++]];
580                 } else {
581                     leftPair = lookupUTF8Unsafe(table, c, left, leftIndex);
582                 }
583                 if(leftPair >= MIN_SHORT) {
584                     leftPair = getSecondariesFromOneShortCE(leftPair);
585                     break;
586                 } else if(leftPair > variableTop) {
587                     leftPair = COMMON_SEC_PLUS_OFFSET;
588                     break;
589                 } else {
590                     leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
591                     leftPair = getSecondaries(variableTop, leftPair);
592                 }
593             }
594 
595             while(rightPair == 0) {
596                 if(rightIndex == rightLength) {
597                     rightPair = EOS;
598                     break;
599                 }
600                 UChar32 c = right[rightIndex++];
601                 if(c <= 0x7f) {
602                     rightPair = table[c];
603                 } else if(c <= LATIN_MAX_UTF8_LEAD) {
604                     rightPair = table[((c - 0xc2) << 6) + right[rightIndex++]];
605                 } else {
606                     rightPair = lookupUTF8Unsafe(table, c, right, rightIndex);
607                 }
608                 if(rightPair >= MIN_SHORT) {
609                     rightPair = getSecondariesFromOneShortCE(rightPair);
610                     break;
611                 } else if(rightPair > variableTop) {
612                     rightPair = COMMON_SEC_PLUS_OFFSET;
613                     break;
614                 } else {
615                     rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
616                     rightPair = getSecondaries(variableTop, rightPair);
617                 }
618             }
619 
620             if(leftPair == rightPair) {
621                 if(leftPair == EOS) { break; }
622                 leftPair = rightPair = 0;
623                 continue;
624             }
625             uint32_t leftSecondary = leftPair & 0xffff;
626             uint32_t rightSecondary = rightPair & 0xffff;
627             if(leftSecondary != rightSecondary) {
628                 if((options & CollationSettings::BACKWARD_SECONDARY) != 0) {
629                     // Full support for backwards secondary requires backwards contraction matching
630                     // and moving backwards between merge separators.
631                     return BAIL_OUT_RESULT;
632                 }
633                 return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER;
634             }
635             if(leftPair == EOS) { break; }
636             leftPair >>= 16;
637             rightPair >>= 16;
638         }
639     }
640 
641     if((options & CollationSettings::CASE_LEVEL) != 0) {
642         UBool strengthIsPrimary = CollationSettings::getStrength(options) == UCOL_PRIMARY;
643         leftIndex = rightIndex = 0;
644         leftPair = rightPair = 0;
645         for(;;) {
646             while(leftPair == 0) {
647                 if(leftIndex == leftLength) {
648                     leftPair = EOS;
649                     break;
650                 }
651                 UChar32 c = left[leftIndex++];
652                 leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex);
653                 if(leftPair < MIN_LONG) {
654                     leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
655                 }
656                 leftPair = getCases(variableTop, strengthIsPrimary, leftPair);
657             }
658 
659             while(rightPair == 0) {
660                 if(rightIndex == rightLength) {
661                     rightPair = EOS;
662                     break;
663                 }
664                 UChar32 c = right[rightIndex++];
665                 rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex);
666                 if(rightPair < MIN_LONG) {
667                     rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
668                 }
669                 rightPair = getCases(variableTop, strengthIsPrimary, rightPair);
670             }
671 
672             if(leftPair == rightPair) {
673                 if(leftPair == EOS) { break; }
674                 leftPair = rightPair = 0;
675                 continue;
676             }
677             uint32_t leftCase = leftPair & 0xffff;
678             uint32_t rightCase = rightPair & 0xffff;
679             if(leftCase != rightCase) {
680                 if((options & CollationSettings::UPPER_FIRST) == 0) {
681                     return (leftCase < rightCase) ? UCOL_LESS : UCOL_GREATER;
682                 } else {
683                     return (leftCase < rightCase) ? UCOL_GREATER : UCOL_LESS;
684                 }
685             }
686             if(leftPair == EOS) { break; }
687             leftPair >>= 16;
688             rightPair >>= 16;
689         }
690     }
691     if(CollationSettings::getStrength(options) <= UCOL_SECONDARY) { return UCOL_EQUAL; }
692 
693     // Remove the case bits from the tertiary weight when caseLevel is on or caseFirst is off.
694     UBool withCaseBits = CollationSettings::isTertiaryWithCaseBits(options);
695 
696     leftIndex = rightIndex = 0;
697     leftPair = rightPair = 0;
698     for(;;) {
699         while(leftPair == 0) {
700             if(leftIndex == leftLength) {
701                 leftPair = EOS;
702                 break;
703             }
704             UChar32 c = left[leftIndex++];
705             leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex);
706             if(leftPair < MIN_LONG) {
707                 leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
708             }
709             leftPair = getTertiaries(variableTop, withCaseBits, leftPair);
710         }
711 
712         while(rightPair == 0) {
713             if(rightIndex == rightLength) {
714                 rightPair = EOS;
715                 break;
716             }
717             UChar32 c = right[rightIndex++];
718             rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex);
719             if(rightPair < MIN_LONG) {
720                 rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
721             }
722             rightPair = getTertiaries(variableTop, withCaseBits, rightPair);
723         }
724 
725         if(leftPair == rightPair) {
726             if(leftPair == EOS) { break; }
727             leftPair = rightPair = 0;
728             continue;
729         }
730         uint32_t leftTertiary = leftPair & 0xffff;
731         uint32_t rightTertiary = rightPair & 0xffff;
732         if(leftTertiary != rightTertiary) {
733             if(CollationSettings::sortsTertiaryUpperCaseFirst(options)) {
734                 // Pass through EOS and MERGE_WEIGHT
735                 // and keep real tertiary weights larger than the MERGE_WEIGHT.
736                 // Tertiary CEs (secondary ignorables) are not supported in fast Latin.
737                 if(leftTertiary > MERGE_WEIGHT) {
738                     leftTertiary ^= CASE_MASK;
739                 }
740                 if(rightTertiary > MERGE_WEIGHT) {
741                     rightTertiary ^= CASE_MASK;
742                 }
743             }
744             return (leftTertiary < rightTertiary) ? UCOL_LESS : UCOL_GREATER;
745         }
746         if(leftPair == EOS) { break; }
747         leftPair >>= 16;
748         rightPair >>= 16;
749     }
750     if(CollationSettings::getStrength(options) <= UCOL_TERTIARY) { return UCOL_EQUAL; }
751 
752     leftIndex = rightIndex = 0;
753     leftPair = rightPair = 0;
754     for(;;) {
755         while(leftPair == 0) {
756             if(leftIndex == leftLength) {
757                 leftPair = EOS;
758                 break;
759             }
760             UChar32 c = left[leftIndex++];
761             leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex);
762             if(leftPair < MIN_LONG) {
763                 leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
764             }
765             leftPair = getQuaternaries(variableTop, leftPair);
766         }
767 
768         while(rightPair == 0) {
769             if(rightIndex == rightLength) {
770                 rightPair = EOS;
771                 break;
772             }
773             UChar32 c = right[rightIndex++];
774             rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex);
775             if(rightPair < MIN_LONG) {
776                 rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
777             }
778             rightPair = getQuaternaries(variableTop, rightPair);
779         }
780 
781         if(leftPair == rightPair) {
782             if(leftPair == EOS) { break; }
783             leftPair = rightPair = 0;
784             continue;
785         }
786         uint32_t leftQuaternary = leftPair & 0xffff;
787         uint32_t rightQuaternary = rightPair & 0xffff;
788         if(leftQuaternary != rightQuaternary) {
789             return (leftQuaternary < rightQuaternary) ? UCOL_LESS : UCOL_GREATER;
790         }
791         if(leftPair == EOS) { break; }
792         leftPair >>= 16;
793         rightPair >>= 16;
794     }
795     return UCOL_EQUAL;
796 }
797 
798 uint32_t
lookup(const uint16_t * table,UChar32 c)799 CollationFastLatin::lookup(const uint16_t *table, UChar32 c) {
800     U_ASSERT(c > LATIN_MAX);
801     if(PUNCT_START <= c && c < PUNCT_LIMIT) {
802         return table[c - PUNCT_START + LATIN_LIMIT];
803     } else if(c == 0xfffe) {
804         return MERGE_WEIGHT;
805     } else if(c == 0xffff) {
806         return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER;
807     } else {
808         return BAIL_OUT;
809     }
810 }
811 
812 uint32_t
lookupUTF8(const uint16_t * table,UChar32 c,const uint8_t * s8,int32_t & sIndex,int32_t sLength)813 CollationFastLatin::lookupUTF8(const uint16_t *table, UChar32 c,
814                                const uint8_t *s8, int32_t &sIndex, int32_t sLength) {
815     // The caller handled ASCII and valid/supported Latin.
816     U_ASSERT(c > 0x7f);
817     int32_t i2 = sIndex + 1;
818     if(i2 < sLength || sLength < 0) {
819         uint8_t t1 = s8[sIndex];
820         uint8_t t2 = s8[i2];
821         sIndex += 2;
822         if(c == 0xe2 && t1 == 0x80 && 0x80 <= t2 && t2 <= 0xbf) {
823             return table[(LATIN_LIMIT - 0x80) + t2];  // 2000..203F -> 0180..01BF
824         } else if(c == 0xef && t1 == 0xbf) {
825             if(t2 == 0xbe) {
826                 return MERGE_WEIGHT;  // U+FFFE
827             } else if(t2 == 0xbf) {
828                 return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER;  // U+FFFF
829             }
830         }
831     }
832     return BAIL_OUT;
833 }
834 
835 uint32_t
lookupUTF8Unsafe(const uint16_t * table,UChar32 c,const uint8_t * s8,int32_t & sIndex)836 CollationFastLatin::lookupUTF8Unsafe(const uint16_t *table, UChar32 c,
837                                      const uint8_t *s8, int32_t &sIndex) {
838     // The caller handled ASCII.
839     // The string is well-formed and contains only supported characters.
840     U_ASSERT(c > 0x7f);
841     if(c <= LATIN_MAX_UTF8_LEAD) {
842         return table[((c - 0xc2) << 6) + s8[sIndex++]];  // 0080..017F
843     }
844     uint8_t t2 = s8[sIndex + 1];
845     sIndex += 2;
846     if(c == 0xe2) {
847         return table[(LATIN_LIMIT - 0x80) + t2];  // 2000..203F -> 0180..01BF
848     } else if(t2 == 0xbe) {
849         return MERGE_WEIGHT;  // U+FFFE
850     } else {
851         return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER;  // U+FFFF
852     }
853 }
854 
855 uint32_t
nextPair(const uint16_t * table,UChar32 c,uint32_t ce,const UChar * s16,const uint8_t * s8,int32_t & sIndex,int32_t & sLength)856 CollationFastLatin::nextPair(const uint16_t *table, UChar32 c, uint32_t ce,
857                              const UChar *s16, const uint8_t *s8, int32_t &sIndex, int32_t &sLength) {
858     if(ce >= MIN_LONG || ce < CONTRACTION) {
859         return ce;  // simple or special mini CE
860     } else if(ce >= EXPANSION) {
861         int32_t index = NUM_FAST_CHARS + (ce & INDEX_MASK);
862         return ((uint32_t)table[index + 1] << 16) | table[index];
863     } else /* ce >= CONTRACTION */ {
864         if(c == 0 && sLength < 0) {
865             sLength = sIndex - 1;
866             return EOS;
867         }
868         // Contraction list: Default mapping followed by
869         // 0 or more single-character contraction suffix mappings.
870         int32_t index = NUM_FAST_CHARS + (ce & INDEX_MASK);
871         if(sIndex != sLength) {
872             // Read the next character.
873             int32_t c2;
874             int32_t nextIndex = sIndex;
875             if(s16 != NULL) {
876                 c2 = s16[nextIndex++];
877                 if(c2 > LATIN_MAX) {
878                     if(PUNCT_START <= c2 && c2 < PUNCT_LIMIT) {
879                         c2 = c2 - PUNCT_START + LATIN_LIMIT;  // 2000..203F -> 0180..01BF
880                     } else if(c2 == 0xfffe || c2 == 0xffff) {
881                         c2 = -1;  // U+FFFE & U+FFFF cannot occur in contractions.
882                     } else {
883                         return BAIL_OUT;
884                     }
885                 }
886             } else {
887                 c2 = s8[nextIndex++];
888                 if(c2 > 0x7f) {
889                     uint8_t t;
890                     if(c2 <= 0xc5 && 0xc2 <= c2 && nextIndex != sLength &&
891                             0x80 <= (t = s8[nextIndex]) && t <= 0xbf) {
892                         c2 = ((c2 - 0xc2) << 6) + t;  // 0080..017F
893                         ++nextIndex;
894                     } else {
895                         int32_t i2 = nextIndex + 1;
896                         if(i2 < sLength || sLength < 0) {
897                             if(c2 == 0xe2 && s8[nextIndex] == 0x80 &&
898                                     0x80 <= (t = s8[i2]) && t <= 0xbf) {
899                                 c2 = (LATIN_LIMIT - 0x80) + t;  // 2000..203F -> 0180..01BF
900                             } else if(c2 == 0xef && s8[nextIndex] == 0xbf &&
901                                     ((t = s8[i2]) == 0xbe || t == 0xbf)) {
902                                 c2 = -1;  // U+FFFE & U+FFFF cannot occur in contractions.
903                             } else {
904                                 return BAIL_OUT;
905                             }
906                         } else {
907                             return BAIL_OUT;
908                         }
909                         nextIndex += 2;
910                     }
911                 }
912             }
913             if(c2 == 0 && sLength < 0) {
914                 sLength = sIndex;
915                 c2 = -1;
916             }
917             // Look for the next character in the contraction suffix list,
918             // which is in ascending order of single suffix characters.
919             int32_t i = index;
920             int32_t head = table[i];  // first skip the default mapping
921             int32_t x;
922             do {
923                 i += head >> CONTR_LENGTH_SHIFT;
924                 head = table[i];
925                 x = head & CONTR_CHAR_MASK;
926             } while(x < c2);
927             if(x == c2) {
928                 index = i;
929                 sIndex = nextIndex;
930             }
931         }
932         // Return the CE or CEs for the default or contraction mapping.
933         int32_t length = table[index] >> CONTR_LENGTH_SHIFT;
934         if(length == 1) {
935             return BAIL_OUT;
936         }
937         ce = table[index + 1];
938         if(length == 2) {
939             return ce;
940         } else {
941             return ((uint32_t)table[index + 2] << 16) | ce;
942         }
943     }
944 }
945 
946 uint32_t
getSecondaries(uint32_t variableTop,uint32_t pair)947 CollationFastLatin::getSecondaries(uint32_t variableTop, uint32_t pair) {
948     if(pair <= 0xffff) {
949         // one mini CE
950         if(pair >= MIN_SHORT) {
951             pair = getSecondariesFromOneShortCE(pair);
952         } else if(pair > variableTop) {
953             pair = COMMON_SEC_PLUS_OFFSET;
954         } else if(pair >= MIN_LONG) {
955             pair = 0;  // variable
956         }
957         // else special mini CE
958     } else {
959         uint32_t ce = pair & 0xffff;
960         if(ce >= MIN_SHORT) {
961             pair = (pair & TWO_SECONDARIES_MASK) + TWO_SEC_OFFSETS;
962         } else if(ce > variableTop) {
963             pair = TWO_COMMON_SEC_PLUS_OFFSET;
964         } else {
965             U_ASSERT(ce >= MIN_LONG);
966             pair = 0;  // variable
967         }
968     }
969     return pair;
970 }
971 
972 uint32_t
getCases(uint32_t variableTop,UBool strengthIsPrimary,uint32_t pair)973 CollationFastLatin::getCases(uint32_t variableTop, UBool strengthIsPrimary, uint32_t pair) {
974     // Primary+caseLevel: Ignore case level weights of primary ignorables.
975     // Otherwise: Ignore case level weights of secondary ignorables.
976     // For details see the comments in the CollationCompare class.
977     // Tertiary CEs (secondary ignorables) are not supported in fast Latin.
978     if(pair <= 0xffff) {
979         // one mini CE
980         if(pair >= MIN_SHORT) {
981             // A high secondary weight means we really have two CEs,
982             // a primary CE and a secondary CE.
983             uint32_t ce = pair;
984             pair &= CASE_MASK;  // explicit weight of primary CE
985             if(!strengthIsPrimary && (ce & SECONDARY_MASK) >= MIN_SEC_HIGH) {
986                 pair |= LOWER_CASE << 16;  // implied weight of secondary CE
987             }
988         } else if(pair > variableTop) {
989             pair = LOWER_CASE;
990         } else if(pair >= MIN_LONG) {
991             pair = 0;  // variable
992         }
993         // else special mini CE
994     } else {
995         // two mini CEs, same primary groups, neither expands like above
996         uint32_t ce = pair & 0xffff;
997         if(ce >= MIN_SHORT) {
998             if(strengthIsPrimary && (pair & (SHORT_PRIMARY_MASK << 16)) == 0) {
999                 pair &= CASE_MASK;
1000             } else {
1001                 pair &= TWO_CASES_MASK;
1002             }
1003         } else if(ce > variableTop) {
1004             pair = TWO_LOWER_CASES;
1005         } else {
1006             U_ASSERT(ce >= MIN_LONG);
1007             pair = 0;  // variable
1008         }
1009     }
1010     return pair;
1011 }
1012 
1013 uint32_t
getTertiaries(uint32_t variableTop,UBool withCaseBits,uint32_t pair)1014 CollationFastLatin::getTertiaries(uint32_t variableTop, UBool withCaseBits, uint32_t pair) {
1015     if(pair <= 0xffff) {
1016         // one mini CE
1017         if(pair >= MIN_SHORT) {
1018             // A high secondary weight means we really have two CEs,
1019             // a primary CE and a secondary CE.
1020             uint32_t ce = pair;
1021             if(withCaseBits) {
1022                 pair = (pair & CASE_AND_TERTIARY_MASK) + TER_OFFSET;
1023                 if((ce & SECONDARY_MASK) >= MIN_SEC_HIGH) {
1024                     pair |= (LOWER_CASE | COMMON_TER_PLUS_OFFSET) << 16;
1025                 }
1026             } else {
1027                 pair = (pair & TERTIARY_MASK) + TER_OFFSET;
1028                 if((ce & SECONDARY_MASK) >= MIN_SEC_HIGH) {
1029                     pair |= COMMON_TER_PLUS_OFFSET << 16;
1030                 }
1031             }
1032         } else if(pair > variableTop) {
1033             pair = (pair & TERTIARY_MASK) + TER_OFFSET;
1034             if(withCaseBits) {
1035                 pair |= LOWER_CASE;
1036             }
1037         } else if(pair >= MIN_LONG) {
1038             pair = 0;  // variable
1039         }
1040         // else special mini CE
1041     } else {
1042         // two mini CEs, same primary groups, neither expands like above
1043         uint32_t ce = pair & 0xffff;
1044         if(ce >= MIN_SHORT) {
1045             if(withCaseBits) {
1046                 pair &= TWO_CASES_MASK | TWO_TERTIARIES_MASK;
1047             } else {
1048                 pair &= TWO_TERTIARIES_MASK;
1049             }
1050             pair += TWO_TER_OFFSETS;
1051         } else if(ce > variableTop) {
1052             pair = (pair & TWO_TERTIARIES_MASK) + TWO_TER_OFFSETS;
1053             if(withCaseBits) {
1054                 pair |= TWO_LOWER_CASES;
1055             }
1056         } else {
1057             U_ASSERT(ce >= MIN_LONG);
1058             pair = 0;  // variable
1059         }
1060     }
1061     return pair;
1062 }
1063 
1064 uint32_t
getQuaternaries(uint32_t variableTop,uint32_t pair)1065 CollationFastLatin::getQuaternaries(uint32_t variableTop, uint32_t pair) {
1066     // Return the primary weight of a variable CE,
1067     // or the maximum primary weight for a non-variable, not-completely-ignorable CE.
1068     if(pair <= 0xffff) {
1069         // one mini CE
1070         if(pair >= MIN_SHORT) {
1071             // A high secondary weight means we really have two CEs,
1072             // a primary CE and a secondary CE.
1073             if((pair & SECONDARY_MASK) >= MIN_SEC_HIGH) {
1074                 pair = TWO_SHORT_PRIMARIES_MASK;
1075             } else {
1076                 pair = SHORT_PRIMARY_MASK;
1077             }
1078         } else if(pair > variableTop) {
1079             pair = SHORT_PRIMARY_MASK;
1080         } else if(pair >= MIN_LONG) {
1081             pair &= LONG_PRIMARY_MASK;  // variable
1082         }
1083         // else special mini CE
1084     } else {
1085         // two mini CEs, same primary groups, neither expands like above
1086         uint32_t ce = pair & 0xffff;
1087         if(ce > variableTop) {
1088             pair = TWO_SHORT_PRIMARIES_MASK;
1089         } else {
1090             U_ASSERT(ce >= MIN_LONG);
1091             pair &= TWO_LONG_PRIMARIES_MASK;  // variable
1092         }
1093     }
1094     return pair;
1095 }
1096 
1097 U_NAMESPACE_END
1098 
1099 #endif  // !UCONFIG_NO_COLLATION
1100