| /* |
| ******************************************************************************* |
| * Copyright (C) 2013-2014, International Business Machines |
| * Corporation and others. All Rights Reserved. |
| ******************************************************************************* |
| * collationfastlatin.cpp |
| * |
| * created on: 2013aug18 |
| * created by: Markus W. Scherer |
| */ |
| |
| #include "unicode/utypes.h" |
| |
| #if !UCONFIG_NO_COLLATION |
| |
| #include "unicode/ucol.h" |
| #include "collationdata.h" |
| #include "collationfastlatin.h" |
| #include "collationsettings.h" |
| #include "putilimp.h" // U_ALIGN_CODE |
| #include "uassert.h" |
| |
| U_NAMESPACE_BEGIN |
| |
| int32_t |
| CollationFastLatin::getOptions(const CollationData *data, const CollationSettings &settings, |
| uint16_t *primaries, int32_t capacity) { |
| const uint16_t *table = data->fastLatinTable; |
| if(table == NULL) { return -1; } |
| U_ASSERT(capacity == LATIN_LIMIT); |
| if(capacity != LATIN_LIMIT) { return -1; } |
| |
| uint32_t miniVarTop; |
| if((settings.options & CollationSettings::ALTERNATE_MASK) == 0) { |
| // No mini primaries are variable, set a variableTop just below the |
| // lowest long mini primary. |
| miniVarTop = MIN_LONG - 1; |
| } else { |
| uint32_t v1 = settings.variableTop >> 24; |
| int32_t headerLength = *table & 0xff; |
| int32_t i = headerLength - 1; |
| if(i <= 0 || v1 > (table[i] & 0x7f)) { |
| return -1; // variableTop >= digits, should not occur |
| } |
| while(i > 1 && v1 <= (table[i - 1] & 0x7f)) { --i; } |
| // In the table header, the miniVarTop is in bits 15..7, with 4 zero bits 19..16 implied. |
| // Shift right to make it comparable with long mini primaries in bits 15..3. |
| miniVarTop = (table[i] & 0xff80) >> 4; |
| } |
| |
| const uint8_t *reorderTable = settings.reorderTable; |
| if(reorderTable != NULL) { |
| const uint16_t *scripts = data->scripts; |
| int32_t length = data->scriptsLength; |
| uint32_t prevLastByte = 0; |
| for(int32_t i = 0; i < length;) { |
| // reordered last byte of the group |
| uint32_t lastByte = reorderTable[scripts[i] & 0xff]; |
| if(lastByte < prevLastByte) { |
| // The permutation affects the groups up to Latin. |
| return -1; |
| } |
| if(scripts[i + 2] == USCRIPT_LATIN) { break; } |
| i = i + 2 + scripts[i + 1]; |
| prevLastByte = lastByte; |
| } |
| } |
| |
| table += (table[0] & 0xff); // skip the header |
| for(UChar32 c = 0; c < LATIN_LIMIT; ++c) { |
| uint32_t p = table[c]; |
| if(p >= MIN_SHORT) { |
| p &= SHORT_PRIMARY_MASK; |
| } else if(p > miniVarTop) { |
| p &= LONG_PRIMARY_MASK; |
| } else { |
| p = 0; |
| } |
| primaries[c] = (uint16_t)p; |
| } |
| if((settings.options & CollationSettings::NUMERIC) != 0) { |
| // Bail out for digits. |
| for(UChar32 c = 0x30; c <= 0x39; ++c) { primaries[c] = 0; } |
| } |
| |
| // Shift the miniVarTop above other options. |
| return ((int32_t)miniVarTop << 16) | settings.options; |
| } |
| |
| int32_t |
| CollationFastLatin::compareUTF16(const uint16_t *table, const uint16_t *primaries, int32_t options, |
| const UChar *left, int32_t leftLength, |
| const UChar *right, int32_t rightLength) { |
| // This is a modified copy of CollationCompare::compareUpToQuaternary(), |
| // optimized for common Latin text. |
| // Keep them in sync! |
| // Keep compareUTF16() and compareUTF8() in sync very closely! |
| |
| U_ASSERT((table[0] >> 8) == VERSION); |
| table += (table[0] & 0xff); // skip the header |
| uint32_t variableTop = (uint32_t)options >> 16; // see getOptions() |
| options &= 0xffff; // needed for CollationSettings::getStrength() to work |
| |
| // Check for supported characters, fetch mini CEs, and compare primaries. |
| U_ALIGN_CODE(16); |
| int32_t leftIndex = 0, rightIndex = 0; |
| /** |
| * Single mini CE or a pair. |
| * The current mini CE is in the lower 16 bits, the next one is in the upper 16 bits. |
| * If there is only one, then it is in the lower bits, and the upper bits are 0. |
| */ |
| uint32_t leftPair = 0, rightPair = 0; |
| for(;;) { |
| // We fetch CEs until we get a non-ignorable primary or reach the end. |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| if(c <= LATIN_MAX) { |
| leftPair = primaries[c]; |
| if(leftPair != 0) { break; } |
| if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) { |
| return BAIL_OUT_RESULT; |
| } |
| leftPair = table[c]; |
| } else if(PUNCT_START <= c && c < PUNCT_LIMIT) { |
| leftPair = table[c - PUNCT_START + LATIN_LIMIT]; |
| } else { |
| leftPair = lookup(table, c); |
| } |
| if(leftPair >= MIN_SHORT) { |
| leftPair &= SHORT_PRIMARY_MASK; |
| break; |
| } else if(leftPair > variableTop) { |
| leftPair &= LONG_PRIMARY_MASK; |
| break; |
| } else { |
| leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength); |
| if(leftPair == BAIL_OUT) { return BAIL_OUT_RESULT; } |
| leftPair = getPrimaries(variableTop, leftPair); |
| } |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| if(c <= LATIN_MAX) { |
| rightPair = primaries[c]; |
| if(rightPair != 0) { break; } |
| if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) { |
| return BAIL_OUT_RESULT; |
| } |
| rightPair = table[c]; |
| } else if(PUNCT_START <= c && c < PUNCT_LIMIT) { |
| rightPair = table[c - PUNCT_START + LATIN_LIMIT]; |
| } else { |
| rightPair = lookup(table, c); |
| } |
| if(rightPair >= MIN_SHORT) { |
| rightPair &= SHORT_PRIMARY_MASK; |
| break; |
| } else if(rightPair > variableTop) { |
| rightPair &= LONG_PRIMARY_MASK; |
| break; |
| } else { |
| rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength); |
| if(rightPair == BAIL_OUT) { return BAIL_OUT_RESULT; } |
| rightPair = getPrimaries(variableTop, rightPair); |
| } |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftPrimary = leftPair & 0xffff; |
| uint32_t rightPrimary = rightPair & 0xffff; |
| if(leftPrimary != rightPrimary) { |
| // Return the primary difference. |
| return (leftPrimary < rightPrimary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| // In the following, we need to re-fetch each character because we did not buffer the CEs, |
| // but we know that the string is well-formed and |
| // only contains supported characters and mappings. |
| |
| // We might skip the secondary level but continue with the case level |
| // which is turned on separately. |
| if(CollationSettings::getStrength(options) >= UCOL_SECONDARY) { |
| leftIndex = rightIndex = 0; |
| leftPair = rightPair = 0; |
| for(;;) { |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| if(c <= LATIN_MAX) { |
| leftPair = table[c]; |
| } else if(PUNCT_START <= c && c < PUNCT_LIMIT) { |
| leftPair = table[c - PUNCT_START + LATIN_LIMIT]; |
| } else { |
| leftPair = lookup(table, c); |
| } |
| if(leftPair >= MIN_SHORT) { |
| leftPair = getSecondariesFromOneShortCE(leftPair); |
| break; |
| } else if(leftPair > variableTop) { |
| leftPair = COMMON_SEC_PLUS_OFFSET; |
| break; |
| } else { |
| leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength); |
| leftPair = getSecondaries(variableTop, leftPair); |
| } |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| if(c <= LATIN_MAX) { |
| rightPair = table[c]; |
| } else if(PUNCT_START <= c && c < PUNCT_LIMIT) { |
| rightPair = table[c - PUNCT_START + LATIN_LIMIT]; |
| } else { |
| rightPair = lookup(table, c); |
| } |
| if(rightPair >= MIN_SHORT) { |
| rightPair = getSecondariesFromOneShortCE(rightPair); |
| break; |
| } else if(rightPair > variableTop) { |
| rightPair = COMMON_SEC_PLUS_OFFSET; |
| break; |
| } else { |
| rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength); |
| rightPair = getSecondaries(variableTop, rightPair); |
| } |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftSecondary = leftPair & 0xffff; |
| uint32_t rightSecondary = rightPair & 0xffff; |
| if(leftSecondary != rightSecondary) { |
| if((options & CollationSettings::BACKWARD_SECONDARY) != 0) { |
| // Full support for backwards secondary requires backwards contraction matching |
| // and moving backwards between merge separators. |
| return BAIL_OUT_RESULT; |
| } |
| return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| } |
| |
| if((options & CollationSettings::CASE_LEVEL) != 0) { |
| UBool strengthIsPrimary = CollationSettings::getStrength(options) == UCOL_PRIMARY; |
| leftIndex = rightIndex = 0; |
| leftPair = rightPair = 0; |
| for(;;) { |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| leftPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c); |
| if(leftPair < MIN_LONG) { |
| leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength); |
| } |
| leftPair = getCases(variableTop, strengthIsPrimary, leftPair); |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| rightPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c); |
| if(rightPair < MIN_LONG) { |
| rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength); |
| } |
| rightPair = getCases(variableTop, strengthIsPrimary, rightPair); |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftCase = leftPair & 0xffff; |
| uint32_t rightCase = rightPair & 0xffff; |
| if(leftCase != rightCase) { |
| if((options & CollationSettings::UPPER_FIRST) == 0) { |
| return (leftCase < rightCase) ? UCOL_LESS : UCOL_GREATER; |
| } else { |
| return (leftCase < rightCase) ? UCOL_GREATER : UCOL_LESS; |
| } |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| } |
| if(CollationSettings::getStrength(options) <= UCOL_SECONDARY) { return UCOL_EQUAL; } |
| |
| // Remove the case bits from the tertiary weight when caseLevel is on or caseFirst is off. |
| UBool withCaseBits = CollationSettings::isTertiaryWithCaseBits(options); |
| |
| leftIndex = rightIndex = 0; |
| leftPair = rightPair = 0; |
| for(;;) { |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| leftPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c); |
| if(leftPair < MIN_LONG) { |
| leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength); |
| } |
| leftPair = getTertiaries(variableTop, withCaseBits, leftPair); |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| rightPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c); |
| if(rightPair < MIN_LONG) { |
| rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength); |
| } |
| rightPair = getTertiaries(variableTop, withCaseBits, rightPair); |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftTertiary = leftPair & 0xffff; |
| uint32_t rightTertiary = rightPair & 0xffff; |
| if(leftTertiary != rightTertiary) { |
| if(CollationSettings::sortsTertiaryUpperCaseFirst(options)) { |
| // Pass through EOS and MERGE_WEIGHT |
| // and keep real tertiary weights larger than the MERGE_WEIGHT. |
| // Tertiary CEs (secondary ignorables) are not supported in fast Latin. |
| if(leftTertiary > MERGE_WEIGHT) { |
| leftTertiary ^= CASE_MASK; |
| } |
| if(rightTertiary > MERGE_WEIGHT) { |
| rightTertiary ^= CASE_MASK; |
| } |
| } |
| return (leftTertiary < rightTertiary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| if(CollationSettings::getStrength(options) <= UCOL_TERTIARY) { return UCOL_EQUAL; } |
| |
| leftIndex = rightIndex = 0; |
| leftPair = rightPair = 0; |
| for(;;) { |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| leftPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c); |
| if(leftPair < MIN_LONG) { |
| leftPair = nextPair(table, c, leftPair, left, NULL, leftIndex, leftLength); |
| } |
| leftPair = getQuaternaries(variableTop, leftPair); |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| rightPair = (c <= LATIN_MAX) ? table[c] : lookup(table, c); |
| if(rightPair < MIN_LONG) { |
| rightPair = nextPair(table, c, rightPair, right, NULL, rightIndex, rightLength); |
| } |
| rightPair = getQuaternaries(variableTop, rightPair); |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftQuaternary = leftPair & 0xffff; |
| uint32_t rightQuaternary = rightPair & 0xffff; |
| if(leftQuaternary != rightQuaternary) { |
| return (leftQuaternary < rightQuaternary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| return UCOL_EQUAL; |
| } |
| |
| int32_t |
| CollationFastLatin::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) { |
| // Keep compareUTF16() and compareUTF8() in sync very closely! |
| |
| U_ASSERT((table[0] >> 8) == VERSION); |
| table += (table[0] & 0xff); // skip the header |
| uint32_t variableTop = (uint32_t)options >> 16; // see RuleBasedCollator::getFastLatinOptions() |
| options &= 0xffff; // needed for CollationSettings::getStrength() to work |
| |
| // Check for supported characters, fetch mini CEs, and compare primaries. |
| U_ALIGN_CODE(16); |
| int32_t leftIndex = 0, rightIndex = 0; |
| /** |
| * Single mini CE or a pair. |
| * The current mini CE is in the lower 16 bits, the next one is in the upper 16 bits. |
| * If there is only one, then it is in the lower bits, and the upper bits are 0. |
| */ |
| uint32_t leftPair = 0, rightPair = 0; |
| // Note: There is no need to assemble the code point. |
| // We only need to look up the table entry for the character, |
| // and nextPair() looks for whether c==0. |
| for(;;) { |
| // We fetch CEs until we get a non-ignorable primary or reach the end. |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| uint8_t t; |
| if(c <= 0x7f) { |
| leftPair = primaries[c]; |
| if(leftPair != 0) { break; } |
| if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) { |
| return BAIL_OUT_RESULT; |
| } |
| leftPair = table[c]; |
| } else if(c <= LATIN_MAX_UTF8_LEAD && 0xc2 <= c && leftIndex != leftLength && |
| 0x80 <= (t = left[leftIndex]) && t <= 0xbf) { |
| ++leftIndex; |
| c = ((c - 0xc2) << 6) + t; |
| leftPair = primaries[c]; |
| if(leftPair != 0) { break; } |
| leftPair = table[c]; |
| } else { |
| leftPair = lookupUTF8(table, c, left, leftIndex, leftLength); |
| } |
| if(leftPair >= MIN_SHORT) { |
| leftPair &= SHORT_PRIMARY_MASK; |
| break; |
| } else if(leftPair > variableTop) { |
| leftPair &= LONG_PRIMARY_MASK; |
| break; |
| } else { |
| leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength); |
| if(leftPair == BAIL_OUT) { return BAIL_OUT_RESULT; } |
| leftPair = getPrimaries(variableTop, leftPair); |
| } |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| uint8_t t; |
| if(c <= 0x7f) { |
| rightPair = primaries[c]; |
| if(rightPair != 0) { break; } |
| if(c <= 0x39 && c >= 0x30 && (options & CollationSettings::NUMERIC) != 0) { |
| return BAIL_OUT_RESULT; |
| } |
| rightPair = table[c]; |
| } else if(c <= LATIN_MAX_UTF8_LEAD && 0xc2 <= c && rightIndex != rightLength && |
| 0x80 <= (t = right[rightIndex]) && t <= 0xbf) { |
| ++rightIndex; |
| c = ((c - 0xc2) << 6) + t; |
| rightPair = primaries[c]; |
| if(rightPair != 0) { break; } |
| rightPair = table[c]; |
| } else { |
| rightPair = lookupUTF8(table, c, right, rightIndex, rightLength); |
| } |
| if(rightPair >= MIN_SHORT) { |
| rightPair &= SHORT_PRIMARY_MASK; |
| break; |
| } else if(rightPair > variableTop) { |
| rightPair &= LONG_PRIMARY_MASK; |
| break; |
| } else { |
| rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength); |
| if(rightPair == BAIL_OUT) { return BAIL_OUT_RESULT; } |
| rightPair = getPrimaries(variableTop, rightPair); |
| } |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftPrimary = leftPair & 0xffff; |
| uint32_t rightPrimary = rightPair & 0xffff; |
| if(leftPrimary != rightPrimary) { |
| // Return the primary difference. |
| return (leftPrimary < rightPrimary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| // In the following, we need to re-fetch each character because we did not buffer the CEs, |
| // but we know that the string is well-formed and |
| // only contains supported characters and mappings. |
| |
| // We might skip the secondary level but continue with the case level |
| // which is turned on separately. |
| if(CollationSettings::getStrength(options) >= UCOL_SECONDARY) { |
| leftIndex = rightIndex = 0; |
| leftPair = rightPair = 0; |
| for(;;) { |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| if(c <= 0x7f) { |
| leftPair = table[c]; |
| } else if(c <= LATIN_MAX_UTF8_LEAD) { |
| leftPair = table[((c - 0xc2) << 6) + left[leftIndex++]]; |
| } else { |
| leftPair = lookupUTF8Unsafe(table, c, left, leftIndex); |
| } |
| if(leftPair >= MIN_SHORT) { |
| leftPair = getSecondariesFromOneShortCE(leftPair); |
| break; |
| } else if(leftPair > variableTop) { |
| leftPair = COMMON_SEC_PLUS_OFFSET; |
| break; |
| } else { |
| leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength); |
| leftPair = getSecondaries(variableTop, leftPair); |
| } |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| if(c <= 0x7f) { |
| rightPair = table[c]; |
| } else if(c <= LATIN_MAX_UTF8_LEAD) { |
| rightPair = table[((c - 0xc2) << 6) + right[rightIndex++]]; |
| } else { |
| rightPair = lookupUTF8Unsafe(table, c, right, rightIndex); |
| } |
| if(rightPair >= MIN_SHORT) { |
| rightPair = getSecondariesFromOneShortCE(rightPair); |
| break; |
| } else if(rightPair > variableTop) { |
| rightPair = COMMON_SEC_PLUS_OFFSET; |
| break; |
| } else { |
| rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength); |
| rightPair = getSecondaries(variableTop, rightPair); |
| } |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftSecondary = leftPair & 0xffff; |
| uint32_t rightSecondary = rightPair & 0xffff; |
| if(leftSecondary != rightSecondary) { |
| if((options & CollationSettings::BACKWARD_SECONDARY) != 0) { |
| // Full support for backwards secondary requires backwards contraction matching |
| // and moving backwards between merge separators. |
| return BAIL_OUT_RESULT; |
| } |
| return (leftSecondary < rightSecondary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| } |
| |
| if((options & CollationSettings::CASE_LEVEL) != 0) { |
| UBool strengthIsPrimary = CollationSettings::getStrength(options) == UCOL_PRIMARY; |
| leftIndex = rightIndex = 0; |
| leftPair = rightPair = 0; |
| for(;;) { |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex); |
| if(leftPair < MIN_LONG) { |
| leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength); |
| } |
| leftPair = getCases(variableTop, strengthIsPrimary, leftPair); |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex); |
| if(rightPair < MIN_LONG) { |
| rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength); |
| } |
| rightPair = getCases(variableTop, strengthIsPrimary, rightPair); |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftCase = leftPair & 0xffff; |
| uint32_t rightCase = rightPair & 0xffff; |
| if(leftCase != rightCase) { |
| if((options & CollationSettings::UPPER_FIRST) == 0) { |
| return (leftCase < rightCase) ? UCOL_LESS : UCOL_GREATER; |
| } else { |
| return (leftCase < rightCase) ? UCOL_GREATER : UCOL_LESS; |
| } |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| } |
| if(CollationSettings::getStrength(options) <= UCOL_SECONDARY) { return UCOL_EQUAL; } |
| |
| // Remove the case bits from the tertiary weight when caseLevel is on or caseFirst is off. |
| UBool withCaseBits = CollationSettings::isTertiaryWithCaseBits(options); |
| |
| leftIndex = rightIndex = 0; |
| leftPair = rightPair = 0; |
| for(;;) { |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex); |
| if(leftPair < MIN_LONG) { |
| leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength); |
| } |
| leftPair = getTertiaries(variableTop, withCaseBits, leftPair); |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex); |
| if(rightPair < MIN_LONG) { |
| rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength); |
| } |
| rightPair = getTertiaries(variableTop, withCaseBits, rightPair); |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftTertiary = leftPair & 0xffff; |
| uint32_t rightTertiary = rightPair & 0xffff; |
| if(leftTertiary != rightTertiary) { |
| if(CollationSettings::sortsTertiaryUpperCaseFirst(options)) { |
| // Pass through EOS and MERGE_WEIGHT |
| // and keep real tertiary weights larger than the MERGE_WEIGHT. |
| // Tertiary CEs (secondary ignorables) are not supported in fast Latin. |
| if(leftTertiary > MERGE_WEIGHT) { |
| leftTertiary ^= CASE_MASK; |
| } |
| if(rightTertiary > MERGE_WEIGHT) { |
| rightTertiary ^= CASE_MASK; |
| } |
| } |
| return (leftTertiary < rightTertiary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| if(CollationSettings::getStrength(options) <= UCOL_TERTIARY) { return UCOL_EQUAL; } |
| |
| leftIndex = rightIndex = 0; |
| leftPair = rightPair = 0; |
| for(;;) { |
| while(leftPair == 0) { |
| if(leftIndex == leftLength) { |
| leftPair = EOS; |
| break; |
| } |
| UChar32 c = left[leftIndex++]; |
| leftPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, left, leftIndex); |
| if(leftPair < MIN_LONG) { |
| leftPair = nextPair(table, c, leftPair, NULL, left, leftIndex, leftLength); |
| } |
| leftPair = getQuaternaries(variableTop, leftPair); |
| } |
| |
| while(rightPair == 0) { |
| if(rightIndex == rightLength) { |
| rightPair = EOS; |
| break; |
| } |
| UChar32 c = right[rightIndex++]; |
| rightPair = (c <= 0x7f) ? table[c] : lookupUTF8Unsafe(table, c, right, rightIndex); |
| if(rightPair < MIN_LONG) { |
| rightPair = nextPair(table, c, rightPair, NULL, right, rightIndex, rightLength); |
| } |
| rightPair = getQuaternaries(variableTop, rightPair); |
| } |
| |
| if(leftPair == rightPair) { |
| if(leftPair == EOS) { break; } |
| leftPair = rightPair = 0; |
| continue; |
| } |
| uint32_t leftQuaternary = leftPair & 0xffff; |
| uint32_t rightQuaternary = rightPair & 0xffff; |
| if(leftQuaternary != rightQuaternary) { |
| return (leftQuaternary < rightQuaternary) ? UCOL_LESS : UCOL_GREATER; |
| } |
| if(leftPair == EOS) { break; } |
| leftPair >>= 16; |
| rightPair >>= 16; |
| } |
| return UCOL_EQUAL; |
| } |
| |
| uint32_t |
| CollationFastLatin::lookup(const uint16_t *table, UChar32 c) { |
| U_ASSERT(c > LATIN_MAX); |
| if(PUNCT_START <= c && c < PUNCT_LIMIT) { |
| return table[c - PUNCT_START + LATIN_LIMIT]; |
| } else if(c == 0xfffe) { |
| return MERGE_WEIGHT; |
| } else if(c == 0xffff) { |
| return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER; |
| } else { |
| return BAIL_OUT; |
| } |
| } |
| |
| uint32_t |
| CollationFastLatin::lookupUTF8(const uint16_t *table, UChar32 c, |
| const uint8_t *s8, int32_t &sIndex, int32_t sLength) { |
| // The caller handled ASCII and valid/supported Latin. |
| U_ASSERT(c > 0x7f); |
| int32_t i2 = sIndex + 1; |
| if(i2 < sLength || sLength < 0) { |
| uint8_t t1 = s8[sIndex]; |
| uint8_t t2 = s8[i2]; |
| sIndex += 2; |
| if(c == 0xe2 && t1 == 0x80 && 0x80 <= t2 && t2 <= 0xbf) { |
| return table[(LATIN_LIMIT - 0x80) + t2]; // 2000..203F -> 0180..01BF |
| } else if(c == 0xef && t1 == 0xbf) { |
| if(t2 == 0xbe) { |
| return MERGE_WEIGHT; // U+FFFE |
| } else if(t2 == 0xbf) { |
| return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER; // U+FFFF |
| } |
| } |
| } |
| return BAIL_OUT; |
| } |
| |
| uint32_t |
| CollationFastLatin::lookupUTF8Unsafe(const uint16_t *table, UChar32 c, |
| const uint8_t *s8, int32_t &sIndex) { |
| // The caller handled ASCII. |
| // The string is well-formed and contains only supported characters. |
| U_ASSERT(c > 0x7f); |
| if(c <= LATIN_MAX_UTF8_LEAD) { |
| return table[((c - 0xc2) << 6) + s8[sIndex++]]; // 0080..017F |
| } |
| uint8_t t2 = s8[sIndex + 1]; |
| sIndex += 2; |
| if(c == 0xe2) { |
| return table[(LATIN_LIMIT - 0x80) + t2]; // 2000..203F -> 0180..01BF |
| } else if(t2 == 0xbe) { |
| return MERGE_WEIGHT; // U+FFFE |
| } else { |
| return MAX_SHORT | COMMON_SEC | LOWER_CASE | COMMON_TER; // U+FFFF |
| } |
| } |
| |
| uint32_t |
| CollationFastLatin::nextPair(const uint16_t *table, UChar32 c, uint32_t ce, |
| const UChar *s16, const uint8_t *s8, int32_t &sIndex, int32_t &sLength) { |
| if(ce >= MIN_LONG || ce < CONTRACTION) { |
| return ce; // simple or special mini CE |
| } else if(ce >= EXPANSION) { |
| int32_t index = NUM_FAST_CHARS + (ce & INDEX_MASK); |
| return ((uint32_t)table[index + 1] << 16) | table[index]; |
| } else /* ce >= CONTRACTION */ { |
| if(c == 0 && sLength < 0) { |
| sLength = sIndex - 1; |
| return EOS; |
| } |
| // Contraction list: Default mapping followed by |
| // 0 or more single-character contraction suffix mappings. |
| int32_t index = NUM_FAST_CHARS + (ce & INDEX_MASK); |
| if(sIndex != sLength) { |
| // Read the next character. |
| int32_t c2; |
| int32_t nextIndex = sIndex; |
| if(s16 != NULL) { |
| c2 = s16[nextIndex++]; |
| if(c2 > LATIN_MAX) { |
| if(PUNCT_START <= c2 && c2 < PUNCT_LIMIT) { |
| c2 = c2 - PUNCT_START + LATIN_LIMIT; // 2000..203F -> 0180..01BF |
| } else if(c2 == 0xfffe || c2 == 0xffff) { |
| c2 = -1; // U+FFFE & U+FFFF cannot occur in contractions. |
| } else { |
| return BAIL_OUT; |
| } |
| } |
| } else { |
| c2 = s8[nextIndex++]; |
| if(c2 > 0x7f) { |
| uint8_t t; |
| if(c2 <= 0xc5 && 0xc2 <= c2 && nextIndex != sLength && |
| 0x80 <= (t = s8[nextIndex]) && t <= 0xbf) { |
| c2 = ((c2 - 0xc2) << 6) + t; // 0080..017F |
| ++nextIndex; |
| } else { |
| int32_t i2 = nextIndex + 1; |
| if(i2 < sLength || sLength < 0) { |
| if(c2 == 0xe2 && s8[nextIndex] == 0x80 && |
| 0x80 <= (t = s8[i2]) && t <= 0xbf) { |
| c2 = (LATIN_LIMIT - 0x80) + t; // 2000..203F -> 0180..01BF |
| } else if(c2 == 0xef && s8[nextIndex] == 0xbf && |
| ((t = s8[i2]) == 0xbe || t == 0xbf)) { |
| c2 = -1; // U+FFFE & U+FFFF cannot occur in contractions. |
| } else { |
| return BAIL_OUT; |
| } |
| } else { |
| return BAIL_OUT; |
| } |
| nextIndex += 2; |
| } |
| } |
| } |
| if(c2 == 0 && sLength < 0) { |
| sLength = sIndex; |
| c2 = -1; |
| } |
| // Look for the next character in the contraction suffix list, |
| // which is in ascending order of single suffix characters. |
| int32_t i = index; |
| int32_t head = table[i]; // first skip the default mapping |
| int32_t x; |
| do { |
| i += head >> CONTR_LENGTH_SHIFT; |
| head = table[i]; |
| x = head & CONTR_CHAR_MASK; |
| } while(x < c2); |
| if(x == c2) { |
| index = i; |
| sIndex = nextIndex; |
| } |
| } |
| // Return the CE or CEs for the default or contraction mapping. |
| int32_t length = table[index] >> CONTR_LENGTH_SHIFT; |
| if(length == 1) { |
| return BAIL_OUT; |
| } |
| ce = table[index + 1]; |
| if(length == 2) { |
| return ce; |
| } else { |
| return ((uint32_t)table[index + 2] << 16) | ce; |
| } |
| } |
| } |
| |
| uint32_t |
| CollationFastLatin::getSecondaries(uint32_t variableTop, uint32_t pair) { |
| if(pair <= 0xffff) { |
| // one mini CE |
| if(pair >= MIN_SHORT) { |
| pair = getSecondariesFromOneShortCE(pair); |
| } else if(pair > variableTop) { |
| pair = COMMON_SEC_PLUS_OFFSET; |
| } else if(pair >= MIN_LONG) { |
| pair = 0; // variable |
| } |
| // else special mini CE |
| } else { |
| uint32_t ce = pair & 0xffff; |
| if(ce >= MIN_SHORT) { |
| pair = (pair & TWO_SECONDARIES_MASK) + TWO_SEC_OFFSETS; |
| } else if(ce > variableTop) { |
| pair = TWO_COMMON_SEC_PLUS_OFFSET; |
| } else { |
| U_ASSERT(ce >= MIN_LONG); |
| pair = 0; // variable |
| } |
| } |
| return pair; |
| } |
| |
| uint32_t |
| CollationFastLatin::getCases(uint32_t variableTop, UBool strengthIsPrimary, uint32_t pair) { |
| // Primary+caseLevel: Ignore case level weights of primary ignorables. |
| // Otherwise: Ignore case level weights of secondary ignorables. |
| // For details see the comments in the CollationCompare class. |
| // Tertiary CEs (secondary ignorables) are not supported in fast Latin. |
| if(pair <= 0xffff) { |
| // one mini CE |
| if(pair >= MIN_SHORT) { |
| // A high secondary weight means we really have two CEs, |
| // a primary CE and a secondary CE. |
| uint32_t ce = pair; |
| pair &= CASE_MASK; // explicit weight of primary CE |
| if(!strengthIsPrimary && (ce & SECONDARY_MASK) >= MIN_SEC_HIGH) { |
| pair |= LOWER_CASE << 16; // implied weight of secondary CE |
| } |
| } else if(pair > variableTop) { |
| pair = LOWER_CASE; |
| } else if(pair >= MIN_LONG) { |
| pair = 0; // variable |
| } |
| // else special mini CE |
| } else { |
| // two mini CEs, same primary groups, neither expands like above |
| uint32_t ce = pair & 0xffff; |
| if(ce >= MIN_SHORT) { |
| if(strengthIsPrimary && (pair & (SHORT_PRIMARY_MASK << 16)) == 0) { |
| pair &= CASE_MASK; |
| } else { |
| pair &= TWO_CASES_MASK; |
| } |
| } else if(ce > variableTop) { |
| pair = TWO_LOWER_CASES; |
| } else { |
| U_ASSERT(ce >= MIN_LONG); |
| pair = 0; // variable |
| } |
| } |
| return pair; |
| } |
| |
| uint32_t |
| CollationFastLatin::getTertiaries(uint32_t variableTop, UBool withCaseBits, uint32_t pair) { |
| if(pair <= 0xffff) { |
| // one mini CE |
| if(pair >= MIN_SHORT) { |
| // A high secondary weight means we really have two CEs, |
| // a primary CE and a secondary CE. |
| uint32_t ce = pair; |
| if(withCaseBits) { |
| pair = (pair & CASE_AND_TERTIARY_MASK) + TER_OFFSET; |
| if((ce & SECONDARY_MASK) >= MIN_SEC_HIGH) { |
| pair |= (LOWER_CASE | COMMON_TER_PLUS_OFFSET) << 16; |
| } |
| } else { |
| pair = (pair & TERTIARY_MASK) + TER_OFFSET; |
| if((ce & SECONDARY_MASK) >= MIN_SEC_HIGH) { |
| pair |= COMMON_TER_PLUS_OFFSET << 16; |
| } |
| } |
| } else if(pair > variableTop) { |
| pair = (pair & TERTIARY_MASK) + TER_OFFSET; |
| if(withCaseBits) { |
| pair |= LOWER_CASE; |
| } |
| } else if(pair >= MIN_LONG) { |
| pair = 0; // variable |
| } |
| // else special mini CE |
| } else { |
| // two mini CEs, same primary groups, neither expands like above |
| uint32_t ce = pair & 0xffff; |
| if(ce >= MIN_SHORT) { |
| if(withCaseBits) { |
| pair &= TWO_CASES_MASK | TWO_TERTIARIES_MASK; |
| } else { |
| pair &= TWO_TERTIARIES_MASK; |
| } |
| pair += TWO_TER_OFFSETS; |
| } else if(ce > variableTop) { |
| pair = (pair & TWO_TERTIARIES_MASK) + TWO_TER_OFFSETS; |
| if(withCaseBits) { |
| pair |= TWO_LOWER_CASES; |
| } |
| } else { |
| U_ASSERT(ce >= MIN_LONG); |
| pair = 0; // variable |
| } |
| } |
| return pair; |
| } |
| |
| uint32_t |
| CollationFastLatin::getQuaternaries(uint32_t variableTop, uint32_t pair) { |
| // Return the primary weight of a variable CE, |
| // or the maximum primary weight for a non-variable, not-completely-ignorable CE. |
| if(pair <= 0xffff) { |
| // one mini CE |
| if(pair >= MIN_SHORT) { |
| // A high secondary weight means we really have two CEs, |
| // a primary CE and a secondary CE. |
| if((pair & SECONDARY_MASK) >= MIN_SEC_HIGH) { |
| pair = TWO_SHORT_PRIMARIES_MASK; |
| } else { |
| pair = SHORT_PRIMARY_MASK; |
| } |
| } else if(pair > variableTop) { |
| pair = SHORT_PRIMARY_MASK; |
| } else if(pair >= MIN_LONG) { |
| pair &= LONG_PRIMARY_MASK; // variable |
| } |
| // else special mini CE |
| } else { |
| // two mini CEs, same primary groups, neither expands like above |
| uint32_t ce = pair & 0xffff; |
| if(ce > variableTop) { |
| pair = TWO_SHORT_PRIMARIES_MASK; |
| } else { |
| U_ASSERT(ce >= MIN_LONG); |
| pair &= TWO_LONG_PRIMARIES_MASK; // variable |
| } |
| } |
| return pair; |
| } |
| |
| U_NAMESPACE_END |
| |
| #endif // !UCONFIG_NO_COLLATION |
