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 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 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 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 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 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 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 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 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 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 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 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
