/*
*******************************************************************************
-* Copyright (C) 2012-2014, International Business Machines
+* Copyright (C) 2012-2015, International Business Machines
* Corporation and others. All Rights Reserved.
*******************************************************************************
* collationdata.cpp
#include "collationdata.h"
#include "uassert.h"
#include "utrie2.h"
+#include "uvectr32.h"
U_NAMESPACE_BEGIN
return ce32;
}
+int64_t
+CollationData::getSingleCE(UChar32 c, UErrorCode &errorCode) const {
+ if(U_FAILURE(errorCode)) { return 0; }
+ // Keep parallel with CollationDataBuilder::getSingleCE().
+ const CollationData *d;
+ uint32_t ce32 = getCE32(c);
+ if(ce32 == Collation::FALLBACK_CE32) {
+ d = base;
+ ce32 = base->getCE32(c);
+ } else {
+ d = this;
+ }
+ while(Collation::isSpecialCE32(ce32)) {
+ switch(Collation::tagFromCE32(ce32)) {
+ case Collation::LATIN_EXPANSION_TAG:
+ case Collation::BUILDER_DATA_TAG:
+ case Collation::PREFIX_TAG:
+ case Collation::CONTRACTION_TAG:
+ case Collation::HANGUL_TAG:
+ case Collation::LEAD_SURROGATE_TAG:
+ errorCode = U_UNSUPPORTED_ERROR;
+ return 0;
+ case Collation::FALLBACK_TAG:
+ case Collation::RESERVED_TAG_3:
+ errorCode = U_INTERNAL_PROGRAM_ERROR;
+ return 0;
+ case Collation::LONG_PRIMARY_TAG:
+ return Collation::ceFromLongPrimaryCE32(ce32);
+ case Collation::LONG_SECONDARY_TAG:
+ return Collation::ceFromLongSecondaryCE32(ce32);
+ case Collation::EXPANSION32_TAG:
+ if(Collation::lengthFromCE32(ce32) == 1) {
+ ce32 = d->ce32s[Collation::indexFromCE32(ce32)];
+ break;
+ } else {
+ errorCode = U_UNSUPPORTED_ERROR;
+ return 0;
+ }
+ case Collation::EXPANSION_TAG: {
+ if(Collation::lengthFromCE32(ce32) == 1) {
+ return d->ces[Collation::indexFromCE32(ce32)];
+ } else {
+ errorCode = U_UNSUPPORTED_ERROR;
+ return 0;
+ }
+ }
+ case Collation::DIGIT_TAG:
+ // Fetch the non-numeric-collation CE32 and continue.
+ ce32 = d->ce32s[Collation::indexFromCE32(ce32)];
+ break;
+ case Collation::U0000_TAG:
+ U_ASSERT(c == 0);
+ // Fetch the normal ce32 for U+0000 and continue.
+ ce32 = d->ce32s[0];
+ break;
+ case Collation::OFFSET_TAG:
+ return d->getCEFromOffsetCE32(c, ce32);
+ case Collation::IMPLICIT_TAG:
+ return Collation::unassignedCEFromCodePoint(c);
+ }
+ }
+ return Collation::ceFromSimpleCE32(ce32);
+}
+
uint32_t
CollationData::getFirstPrimaryForGroup(int32_t script) const {
- int32_t index = findScript(script);
- if(index < 0) {
- return 0;
- }
- uint32_t head = scripts[index];
- return (head & 0xff00) << 16;
+ int32_t index = getScriptIndex(script);
+ return index == 0 ? 0 : (uint32_t)scriptStarts[index] << 16;
}
uint32_t
CollationData::getLastPrimaryForGroup(int32_t script) const {
- int32_t index = findScript(script);
- if(index < 0) {
+ int32_t index = getScriptIndex(script);
+ if(index == 0) {
return 0;
}
- uint32_t head = scripts[index];
- uint32_t lastByte = head & 0xff;
- return ((lastByte + 1) << 24) - 1;
+ uint32_t limit = scriptStarts[index + 1];
+ return (limit << 16) - 1;
}
int32_t
CollationData::getGroupForPrimary(uint32_t p) const {
- p >>= 24; // Reordering groups are distinguished by primary lead bytes.
- for(int32_t i = 0; i < scriptsLength; i = i + 2 + scripts[i + 1]) {
- uint32_t lastByte = scripts[i] & 0xff;
- if(p <= lastByte) {
- return scripts[i + 2];
+ p >>= 16;
+ if(p < scriptStarts[1] || scriptStarts[scriptStartsLength - 1] <= p) {
+ return -1;
+ }
+ int32_t index = 1;
+ while(p >= scriptStarts[index + 1]) { ++index; }
+ for(int32_t i = 0; i < numScripts; ++i) {
+ if(scriptsIndex[i] == index) {
+ return i;
+ }
+ }
+ for(int32_t i = 0; i < MAX_NUM_SPECIAL_REORDER_CODES; ++i) {
+ if(scriptsIndex[numScripts + i] == index) {
+ return UCOL_REORDER_CODE_FIRST + i;
}
}
return -1;
}
int32_t
-CollationData::findScript(int32_t script) const {
- if(script < 0 || 0xffff < script) { return -1; }
- for(int32_t i = 0; i < scriptsLength;) {
- int32_t limit = i + 2 + scripts[i + 1];
- for(int32_t j = i + 2; j < limit; ++j) {
- if(script == scripts[j]) { return i; }
+CollationData::getScriptIndex(int32_t script) const {
+ if(script < 0) {
+ return 0;
+ } else if(script < numScripts) {
+ return scriptsIndex[script];
+ } else if(script < UCOL_REORDER_CODE_FIRST) {
+ return 0;
+ } else {
+ script -= UCOL_REORDER_CODE_FIRST;
+ if(script < MAX_NUM_SPECIAL_REORDER_CODES) {
+ return scriptsIndex[numScripts + script];
+ } else {
+ return 0;
}
- i = limit;
}
- return -1;
}
int32_t
int32_t dest[], int32_t capacity,
UErrorCode &errorCode) const {
if(U_FAILURE(errorCode)) { return 0; }
- int32_t i = findScript(script);
- if(i < 0) { return 0; }
- int32_t length = scripts[i + 1];
- U_ASSERT(length != 0);
- if(length > capacity) {
- errorCode = U_BUFFER_OVERFLOW_ERROR;
- return length;
- }
- i += 2;
- dest[0] = scripts[i++];
- for(int32_t j = 1; j < length; ++j) {
- script = scripts[i++];
- // Sorted insertion.
- for(int32_t k = j;; --k) {
- // Invariant: dest[k] is free to receive either script or dest[k - 1].
- if(k > 0 && script < dest[k - 1]) {
- dest[k] = dest[k - 1];
- } else {
- dest[k] = script;
- break;
+ int32_t index = getScriptIndex(script);
+ if(index == 0) { return 0; }
+ if(script >= UCOL_REORDER_CODE_FIRST) {
+ // Special groups have no aliases.
+ if(capacity > 0) {
+ dest[0] = script;
+ } else {
+ errorCode = U_BUFFER_OVERFLOW_ERROR;
+ }
+ return 1;
+ }
+
+ int32_t length = 0;
+ for(int32_t i = 0; i < numScripts; ++i) {
+ if(scriptsIndex[i] == index) {
+ if(length < capacity) {
+ dest[length] = i;
}
+ ++length;
}
}
+ if(length > capacity) {
+ errorCode = U_BUFFER_OVERFLOW_ERROR;
+ }
return length;
}
void
-CollationData::makeReorderTable(const int32_t *reorder, int32_t length,
- uint8_t table[256], UErrorCode &errorCode) const {
- if(U_FAILURE(errorCode)) { return; }
+CollationData::makeReorderRanges(const int32_t *reorder, int32_t length,
+ UVector32 &ranges, UErrorCode &errorCode) const {
+ makeReorderRanges(reorder, length, FALSE, ranges, errorCode);
+}
- // Initialize the table.
- // Never reorder special low and high primary lead bytes.
- int32_t lowByte;
- for(lowByte = 0; lowByte <= Collation::MERGE_SEPARATOR_BYTE; ++lowByte) {
- table[lowByte] = lowByte;
+void
+CollationData::makeReorderRanges(const int32_t *reorder, int32_t length,
+ UBool latinMustMove,
+ UVector32 &ranges, UErrorCode &errorCode) const {
+ if(U_FAILURE(errorCode)) { return; }
+ ranges.removeAllElements();
+ if(length == 0 || (length == 1 && reorder[0] == USCRIPT_UNKNOWN)) {
+ return;
}
- // lowByte == 03
- int32_t highByte;
- for(highByte = 0xff; highByte >= Collation::TRAIL_WEIGHT_BYTE; --highByte) {
- table[highByte] = highByte;
- }
- // highByte == FE
+ // Maps each script-or-group range to a new lead byte.
+ uint8_t table[MAX_NUM_SCRIPT_RANGES];
+ uprv_memset(table, 0, sizeof(table));
- // Set intermediate bytes to 0 to indicate that they have not been set yet.
- for(int32_t i = lowByte; i <= highByte; ++i) {
- table[i] = 0;
+ {
+ // Set "don't care" values for reserved ranges.
+ int32_t index = scriptsIndex[
+ numScripts + REORDER_RESERVED_BEFORE_LATIN - UCOL_REORDER_CODE_FIRST];
+ if(index != 0) {
+ table[index] = 0xff;
+ }
+ index = scriptsIndex[
+ numScripts + REORDER_RESERVED_AFTER_LATIN - UCOL_REORDER_CODE_FIRST];
+ if(index != 0) {
+ table[index] = 0xff;
+ }
}
+ // Never reorder special low and high primary lead bytes.
+ U_ASSERT(scriptStartsLength >= 2);
+ U_ASSERT(scriptStarts[0] == 0);
+ int32_t lowStart = scriptStarts[1];
+ U_ASSERT(lowStart == ((Collation::MERGE_SEPARATOR_BYTE + 1) << 8));
+ int32_t highLimit = scriptStarts[scriptStartsLength - 1];
+ U_ASSERT(highLimit == (Collation::TRAIL_WEIGHT_BYTE << 8));
+
// Get the set of special reorder codes in the input list.
- // This supports up to 32 special reorder codes;
+ // This supports a fixed number of special reorder codes;
// it works for data with codes beyond UCOL_REORDER_CODE_LIMIT.
uint32_t specials = 0;
for(int32_t i = 0; i < length; ++i) {
int32_t reorderCode = reorder[i] - UCOL_REORDER_CODE_FIRST;
- if(0 <= reorderCode && reorderCode <= 31) {
+ if(0 <= reorderCode && reorderCode < MAX_NUM_SPECIAL_REORDER_CODES) {
specials |= (uint32_t)1 << reorderCode;
}
}
// Start the reordering with the special low reorder codes that do not occur in the input.
- for(int32_t i = 0;; i += 3) {
- if(scripts[i + 1] != 1) { break; } // Went beyond special single-code reorder codes.
- int32_t reorderCode = (int32_t)scripts[i + 2] - UCOL_REORDER_CODE_FIRST;
- if(reorderCode < 0) { break; } // Went beyond special reorder codes.
- if((specials & ((uint32_t)1 << reorderCode)) == 0) {
- int32_t head = scripts[i];
- int32_t firstByte = head >> 8;
- int32_t lastByte = head & 0xff;
- do { table[firstByte++] = lowByte++; } while(firstByte <= lastByte);
+ for(int32_t i = 0; i < MAX_NUM_SPECIAL_REORDER_CODES; ++i) {
+ int32_t index = scriptsIndex[numScripts + i];
+ if(index != 0 && (specials & ((uint32_t)1 << i)) == 0) {
+ lowStart = addLowScriptRange(table, index, lowStart);
}
}
- // Reorder according to the input scripts, continuing from the bottom of the bytes range.
+ // Skip the reserved range before Latin if Latin is the first script,
+ // so that we do not move it unnecessarily.
+ int32_t skippedReserved = 0;
+ if(specials == 0 && reorder[0] == USCRIPT_LATIN && !latinMustMove) {
+ int32_t index = scriptsIndex[USCRIPT_LATIN];
+ U_ASSERT(index != 0);
+ int32_t start = scriptStarts[index];
+ U_ASSERT(lowStart <= start);
+ skippedReserved = start - lowStart;
+ lowStart = start;
+ }
+
+ // Reorder according to the input scripts, continuing from the bottom of the primary range.
+ int32_t originalLength = length; // length will be decremented if "others" is in the list.
+ UBool hasReorderToEnd = FALSE;
for(int32_t i = 0; i < length;) {
int32_t script = reorder[i++];
if(script == USCRIPT_UNKNOWN) {
// Put the remaining scripts at the top.
+ hasReorderToEnd = TRUE;
while(i < length) {
script = reorder[--length];
if(script == USCRIPT_UNKNOWN || // Must occur at most once.
errorCode = U_ILLEGAL_ARGUMENT_ERROR;
return;
}
- int32_t index = findScript(script);
- if(index < 0) { continue; }
- int32_t head = scripts[index];
- int32_t firstByte = head >> 8;
- int32_t lastByte = head & 0xff;
- if(table[firstByte] != 0) { // Duplicate or equivalent script.
+ int32_t index = getScriptIndex(script);
+ if(index == 0) { continue; }
+ if(table[index] != 0) { // Duplicate or equivalent script.
errorCode = U_ILLEGAL_ARGUMENT_ERROR;
return;
}
- do { table[lastByte--] = highByte--; } while(firstByte <= lastByte);
+ highLimit = addHighScriptRange(table, index, highLimit);
}
break;
}
errorCode = U_ILLEGAL_ARGUMENT_ERROR;
return;
}
- int32_t index = findScript(script);
- if(index < 0) { continue; }
- int32_t head = scripts[index];
- int32_t firstByte = head >> 8;
- int32_t lastByte = head & 0xff;
- if(table[firstByte] != 0) { // Duplicate or equivalent script.
+ int32_t index = getScriptIndex(script);
+ if(index == 0) { continue; }
+ if(table[index] != 0) { // Duplicate or equivalent script.
errorCode = U_ILLEGAL_ARGUMENT_ERROR;
return;
}
- do { table[firstByte++] = lowByte++; } while(firstByte <= lastByte);
+ lowStart = addLowScriptRange(table, index, lowStart);
}
// Put all remaining scripts into the middle.
- // Avoid table[0] which must remain 0.
- for(int32_t i = 1; i <= 0xff; ++i) {
- if(table[i] == 0) { table[i] = lowByte++; }
+ for(int32_t i = 1; i < scriptStartsLength - 1; ++i) {
+ int32_t leadByte = table[i];
+ if(leadByte != 0) { continue; }
+ int32_t start = scriptStarts[i];
+ if(!hasReorderToEnd && start > lowStart) {
+ // No need to move this script.
+ lowStart = start;
+ }
+ lowStart = addLowScriptRange(table, i, lowStart);
+ }
+ if(lowStart > highLimit) {
+ if((lowStart - (skippedReserved & 0xff00)) <= highLimit) {
+ // Try not skipping the before-Latin reserved range.
+ makeReorderRanges(reorder, originalLength, TRUE, ranges, errorCode);
+ return;
+ }
+ // We need more primary lead bytes than available, despite the reserved ranges.
+ errorCode = U_BUFFER_OVERFLOW_ERROR;
+ return;
+ }
+
+ // Turn lead bytes into a list of (limit, offset) pairs.
+ // Encode each pair in one list element:
+ // Upper 16 bits = limit, lower 16 = signed lead byte offset.
+ int32_t offset = 0;
+ for(int32_t i = 1;; ++i) {
+ int32_t nextOffset = offset;
+ while(i < scriptStartsLength - 1) {
+ int32_t newLeadByte = table[i];
+ if(newLeadByte == 0xff) {
+ // "Don't care" lead byte for reserved range, continue with current offset.
+ } else {
+ nextOffset = newLeadByte - (scriptStarts[i] >> 8);
+ if(nextOffset != offset) { break; }
+ }
+ ++i;
+ }
+ if(offset != 0 || i < scriptStartsLength - 1) {
+ ranges.addElement(((int32_t)scriptStarts[i] << 16) | (offset & 0xffff), errorCode);
+ }
+ if(i == scriptStartsLength - 1) { break; }
+ offset = nextOffset;
+ }
+}
+
+int32_t
+CollationData::addLowScriptRange(uint8_t table[], int32_t index, int32_t lowStart) const {
+ int32_t start = scriptStarts[index];
+ if((start & 0xff) < (lowStart & 0xff)) {
+ lowStart += 0x100;
+ }
+ table[index] = (uint8_t)(lowStart >> 8);
+ int32_t limit = scriptStarts[index + 1];
+ lowStart = ((lowStart & 0xff00) + ((limit & 0xff00) - (start & 0xff00))) | (limit & 0xff);
+ return lowStart;
+}
+
+int32_t
+CollationData::addHighScriptRange(uint8_t table[], int32_t index, int32_t highLimit) const {
+ int32_t limit = scriptStarts[index + 1];
+ if((limit & 0xff) > (highLimit & 0xff)) {
+ highLimit -= 0x100;
}
- U_ASSERT(lowByte == highByte + 1);
+ int32_t start = scriptStarts[index];
+ highLimit = ((highLimit & 0xff00) - ((limit & 0xff00) - (start & 0xff00))) | (start & 0xff);
+ table[index] = (uint8_t)(highLimit >> 8);
+ return highLimit;
}
U_NAMESPACE_END
projects / apple / icu.git / blobdiff