icuSources/i18n/collationfastlatin.cpp

   1 /*
   2 *******************************************************************************
   3 * Copyright (C) 2013-2015, International Business Machines
   4 * Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 * collationfastlatin.cpp
   7 *
   8 * created on: 2013aug18
   9 * created by: Markus W. Scherer
  10 */
  11
  12 #include "unicode/utypes.h"
  13
  14 #if !UCONFIG_NO_COLLATION
  15
  16 #include "unicode/ucol.h"
  17 #include "collationdata.h"
  18 #include "collationfastlatin.h"
  19 #include "collationsettings.h"
  20 #include "putilimp.h"  // U_ALIGN_CODE
  21 #include "uassert.h"
  22
  23 U_NAMESPACE_BEGIN
  24
  25 int32_t
  26 CollationFastLatin::getOptions(const CollationData *data, const CollationSettings &settings,
  27                                uint16_t *primaries, int32_t capacity) {
  28     const uint16_t *table = data->fastLatinTable;
  29     if(table == NULL) { return -1; }
  30     U_ASSERT(capacity == LATIN_LIMIT);
  31     if(capacity != LATIN_LIMIT) { return -1; }
  32
  33     uint32_t miniVarTop;
  34     if((settings.options & CollationSettings::ALTERNATE_MASK) == 0) {
  35         // No mini primaries are variable, set a variableTop just below the
  36         // lowest long mini primary.
  37         miniVarTop = MIN_LONG - 1;
  38     } else {
  39         int32_t headerLength = *table & 0xff;
  40         int32_t i = 1 + settings.getMaxVariable();
  41         if(i >= headerLength) {
  42             return -1;  // variableTop >= digits, should not occur
  43         }
  44         miniVarTop = table[i];
  45     }
  46
  47     UBool digitsAreReordered = FALSE;
  48     if(settings.hasReordering()) {
  49         uint32_t prevStart = 0;
  50         uint32_t beforeDigitStart = 0;
  51         uint32_t digitStart = 0;
  52         uint32_t afterDigitStart = 0;
  53         for(int32_t group = UCOL_REORDER_CODE_FIRST;
  54                 group < UCOL_REORDER_CODE_FIRST + CollationData::MAX_NUM_SPECIAL_REORDER_CODES;
  55                 ++group) {
  56             uint32_t start = data->getFirstPrimaryForGroup(group);
  57             start = settings.reorder(start);
  58             if(group == UCOL_REORDER_CODE_DIGIT) {
  59                 beforeDigitStart = prevStart;
  60                 digitStart = start;
  61             } else if(start != 0) {
  62                 if(start < prevStart) {
  63                     // The permutation affects the groups up to Latin.
  64                     return -1;
  65                 }
  66                 // In the future, there might be a special group between digits & Latin.
  67                 if(digitStart != 0 && afterDigitStart == 0 && prevStart == beforeDigitStart) {
  68                     afterDigitStart = start;
  69                 }
  70                 prevStart = start;
  71             }
  72         }
  73         uint32_t latinStart = data->getFirstPrimaryForGroup(USCRIPT_LATIN);
  74         latinStart = settings.reorder(latinStart);
  75         if(latinStart < prevStart) {
  76             return -1;
  77         }
  78         if(afterDigitStart == 0) {
  79             afterDigitStart = latinStart;
  80         }
  81         if(!(beforeDigitStart < digitStart && digitStart < afterDigitStart)) {
  82             digitsAreReordered = TRUE;
  83         }
  84     }
  85
  86     table += (table[0] & 0xff);  // skip the header
  87     for(UChar32 c = 0; c < LATIN_LIMIT; ++c) {
  88         uint32_t p = table[c];
  89         if(p >= MIN_SHORT) {
  90             p &= SHORT_PRIMARY_MASK;
  91         } else if(p > miniVarTop) {
  92             p &= LONG_PRIMARY_MASK;
  93         } else {
  94             p = 0;
  95         }
  96         primaries[c] = (uint16_t)p;
  97     }
  98     if(digitsAreReordered || (settings.options & CollationSettings::NUMERIC) != 0) {
  99         // Bail out for digits.
 100         for(UChar32 c = 0x30; c <= 0x39; ++c) { primaries[c] = 0; }
 101     }
 102
 103     // Shift the miniVarTop above other options.
 104     return ((int32_t)miniVarTop << 16) | settings.options;
 105 }
 106
 107 int32_t
 108 CollationFastLatin::compareUTF16(const uint16_t *table, const uint16_t *primaries, int32_t options,
 109                                  const UChar *left, int32_t leftLength,
 110                                  const UChar *right, int32_t rightLength) {
 111     // This is a modified copy of CollationCompare::compareUpToQuaternary(),
 112     // optimized for common Latin text.
 113     // Keep them in sync!
 114     // Keep compareUTF16() and compareUTF8() in sync very closely!
 115
 116     U_ASSERT((table[0] >> 8) == VERSION);
 117     table += (table[0] & 0xff);  // skip the header
 118     uint32_t variableTop = (uint32_t)options >> 16;  // see getOptions()
 119     options &= 0xffff;  // needed for CollationSettings::getStrength() to work
 120
 121     // Check for supported characters, fetch mini CEs, and compare primaries.
 122     U_ALIGN_CODE(16);
 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
 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     U_ALIGN_CODE(16);
 460     int32_t leftIndex = 0, rightIndex = 0;
 461     /**
 462      * Single mini CE or a pair.
 463      * The current mini CE is in the lower 16 bits, the next one is in the upper 16 bits.
 464      * If there is only one, then it is in the lower bits, and the upper bits are 0.
 465      */
 466     uint32_t leftPair = 0, rightPair = 0;
 467     // Note: There is no need to assemble the code point.
 468     // We only need to look up the table entry for the character,
 469     // and nextPair() looks for whether c==0.
 470     for(;;) {
 471         // We fetch CEs until we get a non-ignorable primary or reach the end.
 472         while(leftPair == 0) {
 473             if(leftIndex == leftLength) {
 474                 leftPair = EOS;
 475                 break;
 476             }
 477             UChar32 c = left[leftIndex++];
 478             uint8_t t;
 479             if(c <= 0x7f) {
 480                 leftPair = primaries[c];
 481                 if(leftPair != 0) { break; }
 482                 if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) {
 483                     return BAIL_OUT_RESULT;
 484                 }
 485                 leftPair = table[c];
 486             } else if(c <= LATIN_MAX_UTF8_LEAD && 0xc2 <= c && leftIndex != leftLength &&
 487                     0x80 <= (t = left[leftIndex]) && t <= 0xbf) {
 488                 ++leftIndex;
 489                 c = ((c - 0xc2) << 6) + t;
 490                 leftPair = primaries[c];
 491                 if(leftPair != 0) { break; }
 492                 leftPair = table[c];
 493             } else {
 494                 leftPair = lookupUTF8(table, c, left, leftIndex, leftLength);
 495             }
 496             if(leftPair >= MIN_SHORT) {
 497                 leftPair &= SHORT_PRIMARY_MASK;
 498                 break;
 499             } else if(leftPair > variableTop) {
 500                 leftPair &= LONG_PRIMARY_MASK;
 501                 break;
 502             } else {
 503                 leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
 504                 if(leftPair == BAIL_OUT) { return BAIL_OUT_RESULT; }
 505                 leftPair = getPrimaries(variableTop, leftPair);
 506             }
 507         }
 508
 509         while(rightPair == 0) {
 510             if(rightIndex == rightLength) {
 511                 rightPair = EOS;
 512                 break;
 513             }
 514             UChar32 c = right[rightIndex++];
 515             uint8_t t;
 516             if(c <= 0x7f) {
 517                 rightPair = primaries[c];
 518                 if(rightPair != 0) { break; }
 519                 if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) {
 520                     return BAIL_OUT_RESULT;
 521                 }
 522                 rightPair = table[c];
 523             } else if(c <= LATIN_MAX_UTF8_LEAD && 0xc2 <= c && rightIndex != rightLength &&
 524                     0x80 <= (t = right[rightIndex]) && t <= 0xbf) {
 525                 ++rightIndex;
 526                 c = ((c - 0xc2) << 6) + t;
 527                 rightPair = primaries[c];
 528                 if(rightPair != 0) { break; }
 529                 rightPair = table[c];
 530             } else {
 531                 rightPair = lookupUTF8(table, c, right, rightIndex, rightLength);
 532             }
 533             if(rightPair >= MIN_SHORT) {
 534                 rightPair &= SHORT_PRIMARY_MASK;
 535                 break;
 536             } else if(rightPair > variableTop) {
 537                 rightPair &= LONG_PRIMARY_MASK;
 538                 break;
 539             } else {
 540                 rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
 541                 if(rightPair == BAIL_OUT) { return BAIL_OUT_RESULT; }
 542                 rightPair = getPrimaries(variableTop, rightPair);
 543             }
 544         }
 545
 546         if(leftPair == rightPair) {
 547             if(leftPair == EOS) { break; }
 548             leftPair = rightPair = 0;
 549             continue;
 550         }
 551         uint32_t leftPrimary = leftPair & 0xffff;
 552         uint32_t rightPrimary = rightPair & 0xffff;
 553         if(leftPrimary != rightPrimary) {
 554             // Return the primary difference.
 555             return (leftPrimary < rightPrimary) ? UCOL_LESS : UCOL_GREATER;
 556         }
 557         if(leftPair == EOS) { break; }
 558         leftPair >>= 16;
 559         rightPair >>= 16;
 560     }
 561     // In the following, we need to re-fetch each character because we did not buffer the CEs,
 562     // but we know that the string is well-formed and
 563     // only contains supported characters and mappings.
 564
 565     // We might skip the secondary level but continue with the case level
 566     // which is turned on separately.
 567     if(CollationSettings::getStrength(options) >= UCOL_SECONDARY) {
 568         leftIndex = rightIndex = 0;
 569         leftPair = rightPair = 0;
 570         for(;;) {
 571             while(leftPair == 0) {
 572                 if(leftIndex == leftLength) {
 573                     leftPair = EOS;
 574                     break;
 575                 }
 576                 UChar32 c = left[leftIndex++];
 577                 if(c <= 0x7f) {
 578                     leftPair = table[c];
 579                 } else if(c <= LATIN_MAX_UTF8_LEAD) {
 580                     leftPair = table[((c - 0xc2) << 6) + left[leftIndex++]];
 581                 } else {
 582                     leftPair = lookupUTF8Unsafe(table, c, left, leftIndex);
 583                 }
 584                 if(leftPair >= MIN_SHORT) {
 585                     leftPair = getSecondariesFromOneShortCE(leftPair);
 586                     break;
 587                 } else if(leftPair > variableTop) {
 588                     leftPair = COMMON_SEC_PLUS_OFFSET;
 589                     break;
 590                 } else {
 591                     leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
 592                     leftPair = getSecondaries(variableTop, leftPair);
 593                 }
 594             }
 595
 596             while(rightPair == 0) {
 597                 if(rightIndex == rightLength) {
 598                     rightPair = EOS;
 599                     break;
 600                 }
 601                 UChar32 c = right[rightIndex++];
 602                 if(c <= 0x7f) {
 603                     rightPair = table[c];
 604                 } else if(c <= LATIN_MAX_UTF8_LEAD) {
 605                     rightPair = table[((c - 0xc2) << 6) + right[rightIndex++]];
 606                 } else {
 607                     rightPair = lookupUTF8Unsafe(table, c, right, rightIndex);
 608                 }
 609                 if(rightPair >= MIN_SHORT) {
 610                     rightPair = getSecondariesFromOneShortCE(rightPair);
 611                     break;
 612                 } else if(rightPair > variableTop) {
 613                     rightPair = COMMON_SEC_PLUS_OFFSET;
 614                     break;
 615                 } else {
 616                     rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
 617                     rightPair = getSecondaries(variableTop, rightPair);
 618                 }
 619             }
 620
 621             if(leftPair == rightPair) {
 622                 if(leftPair == EOS) { break; }
 623                 leftPair = rightPair = 0;
 624                 continue;
 625             }
 626             uint32_t leftSecondary = leftPair & 0xffff;
 627             uint32_t rightSecondary = rightPair & 0xffff;
 628             if(leftSecondary != rightSecondary) {
 629                 if((options & CollationSettings::BACKWARD_SECONDARY) != 0) {
 630                     // Full support for backwards secondary requires backwards contraction matching
 631                     // and moving backwards between merge separators.
 632                     return BAIL_OUT_RESULT;
 633                 }
 634                 return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER;
 635             }
 636             if(leftPair == EOS) { break; }
 637             leftPair >>= 16;
 638             rightPair >>= 16;
 639         }
 640     }
 641
 642     if((options & CollationSettings::CASE_LEVEL) != 0) {
 643         UBool strengthIsPrimary = CollationSettings::getStrength(options) == UCOL_PRIMARY;
 644         leftIndex = rightIndex = 0;
 645         leftPair = rightPair = 0;
 646         for(;;) {
 647             while(leftPair == 0) {
 648                 if(leftIndex == leftLength) {
 649                     leftPair = EOS;
 650                     break;
 651                 }
 652                 UChar32 c = left[leftIndex++];
 653                 leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex);
 654                 if(leftPair < MIN_LONG) {
 655                     leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
 656                 }
 657                 leftPair = getCases(variableTop, strengthIsPrimary, leftPair);
 658             }
 659
 660             while(rightPair == 0) {
 661                 if(rightIndex == rightLength) {
 662                     rightPair = EOS;
 663                     break;
 664                 }
 665                 UChar32 c = right[rightIndex++];
 666                 rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex);
 667                 if(rightPair < MIN_LONG) {
 668                     rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
 669                 }
 670                 rightPair = getCases(variableTop, strengthIsPrimary, rightPair);
 671             }
 672
 673             if(leftPair == rightPair) {
 674                 if(leftPair == EOS) { break; }
 675                 leftPair = rightPair = 0;
 676                 continue;
 677             }
 678             uint32_t leftCase = leftPair & 0xffff;
 679             uint32_t rightCase = rightPair & 0xffff;
 680             if(leftCase != rightCase) {
 681                 if((options & CollationSettings::UPPER_FIRST) == 0) {
 682                     return (leftCase < rightCase) ? UCOL_LESS : UCOL_GREATER;
 683                 } else {
 684                     return (leftCase < rightCase) ? UCOL_GREATER : UCOL_LESS;
 685                 }
 686             }
 687             if(leftPair == EOS) { break; }
 688             leftPair >>= 16;
 689             rightPair >>= 16;
 690         }
 691     }
 692     if(CollationSettings::getStrength(options) <= UCOL_SECONDARY) { return UCOL_EQUAL; }
 693
 694     // Remove the case bits from the tertiary weight when caseLevel is on or caseFirst is off.
 695     UBool withCaseBits = CollationSettings::isTertiaryWithCaseBits(options);
 696
 697     leftIndex = rightIndex = 0;
 698     leftPair = rightPair = 0;
 699     for(;;) {
 700         while(leftPair == 0) {
 701             if(leftIndex == leftLength) {
 702                 leftPair = EOS;
 703                 break;
 704             }
 705             UChar32 c = left[leftIndex++];
 706             leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex);
 707             if(leftPair < MIN_LONG) {
 708                 leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
 709             }
 710             leftPair = getTertiaries(variableTop, withCaseBits, leftPair);
 711         }
 712
 713         while(rightPair == 0) {
 714             if(rightIndex == rightLength) {
 715                 rightPair = EOS;
 716                 break;
 717             }
 718             UChar32 c = right[rightIndex++];
 719             rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex);
 720             if(rightPair < MIN_LONG) {
 721                 rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
 722             }
 723             rightPair = getTertiaries(variableTop, withCaseBits, rightPair);
 724         }
 725
 726         if(leftPair == rightPair) {
 727             if(leftPair == EOS) { break; }
 728             leftPair = rightPair = 0;
 729             continue;
 730         }
 731         uint32_t leftTertiary = leftPair & 0xffff;
 732         uint32_t rightTertiary = rightPair & 0xffff;
 733         if(leftTertiary != rightTertiary) {
 734             if(CollationSettings::sortsTertiaryUpperCaseFirst(options)) {
 735                 // Pass through EOS and MERGE_WEIGHT
 736                 // and keep real tertiary weights larger than the MERGE_WEIGHT.
 737                 // Tertiary CEs (secondary ignorables) are not supported in fast Latin.
 738                 if(leftTertiary > MERGE_WEIGHT) {
 739                     leftTertiary ^= CASE_MASK;
 740                 }
 741                 if(rightTertiary > MERGE_WEIGHT) {
 742                     rightTertiary ^= CASE_MASK;
 743                 }
 744             }
 745             return (leftTertiary < rightTertiary) ? UCOL_LESS : UCOL_GREATER;
 746         }
 747         if(leftPair == EOS) { break; }
 748         leftPair >>= 16;
 749         rightPair >>= 16;
 750     }
 751     if(CollationSettings::getStrength(options) <= UCOL_TERTIARY) { return UCOL_EQUAL; }
 752
 753     leftIndex = rightIndex = 0;
 754     leftPair = rightPair = 0;
 755     for(;;) {
 756         while(leftPair == 0) {
 757             if(leftIndex == leftLength) {
 758                 leftPair = EOS;
 759                 break;
 760             }
 761             UChar32 c = left[leftIndex++];
 762             leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex);
 763             if(leftPair < MIN_LONG) {
 764                 leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength);
 765             }
 766             leftPair = getQuaternaries(variableTop, leftPair);
 767         }
 768
 769         while(rightPair == 0) {
 770             if(rightIndex == rightLength) {
 771                 rightPair = EOS;
 772                 break;
 773             }
 774             UChar32 c = right[rightIndex++];
 775             rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex);
 776             if(rightPair < MIN_LONG) {
 777                 rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength);
 778             }
 779             rightPair = getQuaternaries(variableTop, rightPair);
 780         }
 781
 782         if(leftPair == rightPair) {
 783             if(leftPair == EOS) { break; }
 784             leftPair = rightPair = 0;
 785             continue;
 786         }
 787         uint32_t leftQuaternary = leftPair & 0xffff;
 788         uint32_t rightQuaternary = rightPair & 0xffff;
 789         if(leftQuaternary != rightQuaternary) {
 790             return (leftQuaternary < rightQuaternary) ? UCOL_LESS : UCOL_GREATER;
 791         }
 792         if(leftPair == EOS) { break; }
 793         leftPair >>= 16;
 794         rightPair >>= 16;
 795     }
 796     return UCOL_EQUAL;
 797 }
 798
 799 uint32_t
 800 CollationFastLatin::lookup(const uint16_t *table, UChar32 c) {
 801     U_ASSERT(c > LATIN_MAX);
 802     if(PUNCT_START <= c && c < PUNCT_LIMIT) {
 803         return table[c - PUNCT_START + LATIN_LIMIT];
 804     } else if(c == 0xfffe) {
 805         return MERGE_WEIGHT;
 806     } else if(c == 0xffff) {
 807         return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER;
 808     } else {
 809         return BAIL_OUT;
 810     }
 811 }
 812
 813 uint32_t
 814 CollationFastLatin::lookupUTF8(const uint16_t *table, UChar32 c,
 815                                const uint8_t *s8, int32_t &sIndex, int32_t sLength) {
 816     // The caller handled ASCII and valid/supported Latin.
 817     U_ASSERT(c > 0x7f);
 818     int32_t i2 = sIndex + 1;
 819     if(i2 < sLength || sLength < 0) {
 820         uint8_t t1 = s8[sIndex];
 821         uint8_t t2 = s8[i2];
 822         sIndex += 2;
 823         if(c == 0xe2 && t1 == 0x80 && 0x80 <= t2 && t2 <= 0xbf) {
 824             return table[(LATIN_LIMIT - 0x80) + t2];  // 2000..203F -> 0180..01BF
 825         } else if(c == 0xef && t1 == 0xbf) {
 826             if(t2 == 0xbe) {
 827                 return MERGE_WEIGHT;  // U+FFFE
 828             } else if(t2 == 0xbf) {
 829                 return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER;  // U+FFFF
 830             }
 831         }
 832     }
 833     return BAIL_OUT;
 834 }
 835
 836 uint32_t
 837 CollationFastLatin::lookupUTF8Unsafe(const uint16_t *table, UChar32 c,
 838                                      const uint8_t *s8, int32_t &sIndex) {
 839     // The caller handled ASCII.
 840     // The string is well-formed and contains only supported characters.
 841     U_ASSERT(c > 0x7f);
 842     if(c <= LATIN_MAX_UTF8_LEAD) {
 843         return table[((c - 0xc2) << 6) + s8[sIndex++]];  // 0080..017F
 844     }
 845     uint8_t t2 = s8[sIndex + 1];
 846     sIndex += 2;
 847     if(c == 0xe2) {
 848         return table[(LATIN_LIMIT - 0x80) + t2];  // 2000..203F -> 0180..01BF
 849     } else if(t2 == 0xbe) {
 850         return MERGE_WEIGHT;  // U+FFFE
 851     } else {
 852         return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER;  // U+FFFF
 853     }
 854 }
 855
 856 uint32_t
 857 CollationFastLatin::nextPair(const uint16_t *table, UChar32 c, uint32_t ce,
 858                              const UChar *s16, const uint8_t *s8, int32_t &sIndex, int32_t &sLength) {
 859     if(ce >= MIN_LONG || ce < CONTRACTION) {
 860         return ce;  // simple or special mini CE
 861     } else if(ce >= EXPANSION) {
 862         int32_t index = NUM_FAST_CHARS + (ce & INDEX_MASK);
 863         return ((uint32_t)table[index + 1] << 16) | table[index];
 864     } else /* ce >= CONTRACTION */ {
 865         if(c == 0 && sLength < 0) {
 866             sLength = sIndex - 1;
 867             return EOS;
 868         }
 869         // Contraction list: Default mapping followed by
 870         // 0 or more single-character contraction suffix mappings.
 871         int32_t index = NUM_FAST_CHARS + (ce & INDEX_MASK);
 872         if(sIndex != sLength) {
 873             // Read the next character.
 874             int32_t c2;
 875             int32_t nextIndex = sIndex;
 876             if(s16 != NULL) {
 877                 c2 = s16[nextIndex++];
 878                 if(c2 > LATIN_MAX) {
 879                     if(PUNCT_START <= c2 && c2 < PUNCT_LIMIT) {
 880                         c2 = c2 - PUNCT_START + LATIN_LIMIT;  // 2000..203F -> 0180..01BF
 881                     } else if(c2 == 0xfffe || c2 == 0xffff) {
 882                         c2 = -1;  // U+FFFE & U+FFFF cannot occur in contractions.
 883                     } else {
 884                         return BAIL_OUT;
 885                     }
 886                 }
 887             } else {
 888                 c2 = s8[nextIndex++];
 889                 if(c2 > 0x7f) {
 890                     uint8_t t;
 891                     if(c2 <= 0xc5 && 0xc2 <= c2 && nextIndex != sLength &&
 892                             0x80 <= (t = s8[nextIndex]) && t <= 0xbf) {
 893                         c2 = ((c2 - 0xc2) << 6) + t;  // 0080..017F
 894                         ++nextIndex;
 895                     } else {
 896                         int32_t i2 = nextIndex + 1;
 897                         if(i2 < sLength || sLength < 0) {
 898                             if(c2 == 0xe2 && s8[nextIndex] == 0x80 &&
 899                                     0x80 <= (t = s8[i2]) && t <= 0xbf) {
 900                                 c2 = (LATIN_LIMIT - 0x80) + t;  // 2000..203F -> 0180..01BF
 901                             } else if(c2 == 0xef && s8[nextIndex] == 0xbf &&
 902                                     ((t = s8[i2]) == 0xbe || t == 0xbf)) {
 903                                 c2 = -1;  // U+FFFE & U+FFFF cannot occur in contractions.
 904                             } else {
 905                                 return BAIL_OUT;
 906                             }
 907                         } else {
 908                             return BAIL_OUT;
 909                         }
 910                         nextIndex += 2;
 911                     }
 912                 }
 913             }
 914             if(c2 == 0 && sLength < 0) {
 915                 sLength = sIndex;
 916                 c2 = -1;
 917             }
 918             // Look for the next character in the contraction suffix list,
 919             // which is in ascending order of single suffix characters.
 920             int32_t i = index;
 921             int32_t head = table[i];  // first skip the default mapping
 922             int32_t x;
 923             do {
 924                 i += head >> CONTR_LENGTH_SHIFT;
 925                 head = table[i];
 926                 x = head & CONTR_CHAR_MASK;
 927             } while(x < c2);
 928             if(x == c2) {
 929                 index = i;
 930                 sIndex = nextIndex;
 931             }
 932         }
 933         // Return the CE or CEs for the default or contraction mapping.
 934         int32_t length = table[index] >> CONTR_LENGTH_SHIFT;
 935         if(length == 1) {
 936             return BAIL_OUT;
 937         }
 938         ce = table[index + 1];
 939         if(length == 2) {
 940             return ce;
 941         } else {
 942             return ((uint32_t)table[index + 2] << 16) | ce;
 943         }
 944     }
 945 }
 946
 947 uint32_t
 948 CollationFastLatin::getSecondaries(uint32_t variableTop, uint32_t pair) {
 949     if(pair <= 0xffff) {
 950         // one mini CE
 951         if(pair >= MIN_SHORT) {
 952             pair = getSecondariesFromOneShortCE(pair);
 953         } else if(pair > variableTop) {
 954             pair = COMMON_SEC_PLUS_OFFSET;
 955         } else if(pair >= MIN_LONG) {
 956             pair = 0;  // variable
 957         }
 958         // else special mini CE
 959     } else {
 960         uint32_t ce = pair & 0xffff;
 961         if(ce >= MIN_SHORT) {
 962             pair = (pair & TWO_SECONDARIES_MASK) + TWO_SEC_OFFSETS;
 963         } else if(ce > variableTop) {
 964             pair = TWO_COMMON_SEC_PLUS_OFFSET;
 965         } else {
 966             U_ASSERT(ce >= MIN_LONG);
 967             pair = 0;  // variable
 968         }
 969     }
 970     return pair;
 971 }
 972
 973 uint32_t
 974 CollationFastLatin::getCases(uint32_t variableTop, UBool strengthIsPrimary, uint32_t pair) {
 975     // Primary+caseLevel: Ignore case level weights of primary ignorables.
 976     // Otherwise: Ignore case level weights of secondary ignorables.
 977     // For details see the comments in the CollationCompare class.
 978     // Tertiary CEs (secondary ignorables) are not supported in fast Latin.
 979     if(pair <= 0xffff) {
 980         // one mini CE
 981         if(pair >= MIN_SHORT) {
 982             // A high secondary weight means we really have two CEs,
 983             // a primary CE and a secondary CE.
 984             uint32_t ce = pair;
 985             pair &= CASE_MASK;  // explicit weight of primary CE
 986             if(!strengthIsPrimary && (ce & SECONDARY_MASK) >= MIN_SEC_HIGH) {
 987                 pair |= LOWER_CASE << 16;  // implied weight of secondary CE
 988             }
 989         } else if(pair > variableTop) {
 990             pair = LOWER_CASE;
 991         } else if(pair >= MIN_LONG) {
 992             pair = 0;  // variable
 993         }
 994         // else special mini CE
 995     } else {
 996         // two mini CEs, same primary groups, neither expands like above
 997         uint32_t ce = pair & 0xffff;
 998         if(ce >= MIN_SHORT) {
 999             if(strengthIsPrimary && (pair & (SHORT_PRIMARY_MASK << 16)) == 0) {
1000                 pair &= CASE_MASK;
1001             } else {
1002                 pair &= TWO_CASES_MASK;
1003             }
1004         } else if(ce > variableTop) {
1005             pair = TWO_LOWER_CASES;
1006         } else {
1007             U_ASSERT(ce >= MIN_LONG);
1008             pair = 0;  // variable
1009         }
1010     }
1011     return pair;
1012 }
1013
1014 uint32_t
1015 CollationFastLatin::getTertiaries(uint32_t variableTop, UBool withCaseBits, uint32_t pair) {
1016     if(pair <= 0xffff) {
1017         // one mini CE
1018         if(pair >= MIN_SHORT) {
1019             // A high secondary weight means we really have two CEs,
1020             // a primary CE and a secondary CE.
1021             uint32_t ce = pair;
1022             if(withCaseBits) {
1023                 pair = (pair & CASE_AND_TERTIARY_MASK) + TER_OFFSET;
1024                 if((ce & SECONDARY_MASK) >= MIN_SEC_HIGH) {
1025                     pair |= (LOWER_CASE | COMMON_TER_PLUS_OFFSET) << 16;
1026                 }
1027             } else {
1028                 pair = (pair & TERTIARY_MASK) + TER_OFFSET;
1029                 if((ce & SECONDARY_MASK) >= MIN_SEC_HIGH) {
1030                     pair |= COMMON_TER_PLUS_OFFSET << 16;
1031                 }
1032             }
1033         } else if(pair > variableTop) {
1034             pair = (pair & TERTIARY_MASK) + TER_OFFSET;
1035             if(withCaseBits) {
1036                 pair |= LOWER_CASE;
1037             }
1038         } else if(pair >= MIN_LONG) {
1039             pair = 0;  // variable
1040         }
1041         // else special mini CE
1042     } else {
1043         // two mini CEs, same primary groups, neither expands like above
1044         uint32_t ce = pair & 0xffff;
1045         if(ce >= MIN_SHORT) {
1046             if(withCaseBits) {
1047                 pair &= TWO_CASES_MASK | TWO_TERTIARIES_MASK;
1048             } else {
1049                 pair &= TWO_TERTIARIES_MASK;
1050             }
1051             pair += TWO_TER_OFFSETS;
1052         } else if(ce > variableTop) {
1053             pair = (pair & TWO_TERTIARIES_MASK) + TWO_TER_OFFSETS;
1054             if(withCaseBits) {
1055                 pair |= TWO_LOWER_CASES;
1056             }
1057         } else {
1058             U_ASSERT(ce >= MIN_LONG);
1059             pair = 0;  // variable
1060         }
1061     }
1062     return pair;
1063 }
1064
1065 uint32_t
1066 CollationFastLatin::getQuaternaries(uint32_t variableTop, uint32_t pair) {
1067     // Return the primary weight of a variable CE,
1068     // or the maximum primary weight for a non-variable, not-completely-ignorable CE.
1069     if(pair <= 0xffff) {
1070         // one mini CE
1071         if(pair >= MIN_SHORT) {
1072             // A high secondary weight means we really have two CEs,
1073             // a primary CE and a secondary CE.
1074             if((pair & SECONDARY_MASK) >= MIN_SEC_HIGH) {
1075                 pair = TWO_SHORT_PRIMARIES_MASK;
1076             } else {
1077                 pair = SHORT_PRIMARY_MASK;
1078             }
1079         } else if(pair > variableTop) {
1080             pair = SHORT_PRIMARY_MASK;
1081         } else if(pair >= MIN_LONG) {
1082             pair &= LONG_PRIMARY_MASK;  // variable
1083         }
1084         // else special mini CE
1085     } else {
1086         // two mini CEs, same primary groups, neither expands like above
1087         uint32_t ce = pair & 0xffff;
1088         if(ce > variableTop) {
1089             pair = TWO_SHORT_PRIMARIES_MASK;
1090         } else {
1091             U_ASSERT(ce >= MIN_LONG);
1092             pair &= TWO_LONG_PRIMARIES_MASK;  // variable
1093         }
1094     }
1095     return pair;
1096 }
1097
1098 U_NAMESPACE_END
1099
1100 #endif  // !UCONFIG_NO_COLLATION