1 /* 2 ******************************************************************************* 3 * Copyright (C) 2012-2015, International Business Machines 4 * Corporation and others. All Rights Reserved. 5 ******************************************************************************* 6 * collationdata.cpp 7 * 8 * created on: 2012jul28 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 "unicode/udata.h" 18 #include "unicode/uscript.h" 19 #include "cmemory.h" 20 #include "collation.h" 21 #include "collationdata.h" 22 #include "uassert.h" 23 #include "utrie2.h" 24 #include "uvectr32.h" 25 26 U_NAMESPACE_BEGIN 27 28 uint32_t 29 CollationData::getIndirectCE32(uint32_t ce32) const { 30 U_ASSERT(Collation::isSpecialCE32(ce32)); 31 int32_t tag = Collation::tagFromCE32(ce32); 32 if(tag == Collation::DIGIT_TAG) { 33 // Fetch the non-numeric-collation CE32. 34 ce32 = ce32s[Collation::indexFromCE32(ce32)]; 35 } else if(tag == Collation::LEAD_SURROGATE_TAG) { 36 ce32 = Collation::UNASSIGNED_CE32; 37 } else if(tag == Collation::U0000_TAG) { 38 // Fetch the normal ce32 for U+0000. 39 ce32 = ce32s[0]; 40 } 41 return ce32; 42 } 43 44 uint32_t 45 CollationData::getFinalCE32(uint32_t ce32) const { 46 if(Collation::isSpecialCE32(ce32)) { 47 ce32 = getIndirectCE32(ce32); 48 } 49 return ce32; 50 } 51 52 int64_t 53 CollationData::getSingleCE(UChar32 c, UErrorCode &errorCode) const { 54 if(U_FAILURE(errorCode)) { return 0; } 55 // Keep parallel with CollationDataBuilder::getSingleCE(). 56 const CollationData *d; 57 uint32_t ce32 = getCE32(c); 58 if(ce32 == Collation::FALLBACK_CE32) { 59 d = base; 60 ce32 = base->getCE32(c); 61 } else { 62 d = this; 63 } 64 while(Collation::isSpecialCE32(ce32)) { 65 switch(Collation::tagFromCE32(ce32)) { 66 case Collation::LATIN_EXPANSION_TAG: 67 case Collation::BUILDER_DATA_TAG: 68 case Collation::PREFIX_TAG: 69 case Collation::CONTRACTION_TAG: 70 case Collation::HANGUL_TAG: 71 case Collation::LEAD_SURROGATE_TAG: 72 errorCode = U_UNSUPPORTED_ERROR; 73 return 0; 74 case Collation::FALLBACK_TAG: 75 case Collation::RESERVED_TAG_3: 76 errorCode = U_INTERNAL_PROGRAM_ERROR; 77 return 0; 78 case Collation::LONG_PRIMARY_TAG: 79 return Collation::ceFromLongPrimaryCE32(ce32); 80 case Collation::LONG_SECONDARY_TAG: 81 return Collation::ceFromLongSecondaryCE32(ce32); 82 case Collation::EXPANSION32_TAG: 83 if(Collation::lengthFromCE32(ce32) == 1) { 84 ce32 = d->ce32s[Collation::indexFromCE32(ce32)]; 85 break; 86 } else { 87 errorCode = U_UNSUPPORTED_ERROR; 88 return 0; 89 } 90 case Collation::EXPANSION_TAG: { 91 if(Collation::lengthFromCE32(ce32) == 1) { 92 return d->ces[Collation::indexFromCE32(ce32)]; 93 } else { 94 errorCode = U_UNSUPPORTED_ERROR; 95 return 0; 96 } 97 } 98 case Collation::DIGIT_TAG: 99 // Fetch the non-numeric-collation CE32 and continue. 100 ce32 = d->ce32s[Collation::indexFromCE32(ce32)]; 101 break; 102 case Collation::U0000_TAG: 103 U_ASSERT(c == 0); 104 // Fetch the normal ce32 for U+0000 and continue. 105 ce32 = d->ce32s[0]; 106 break; 107 case Collation::OFFSET_TAG: 108 return d->getCEFromOffsetCE32(c, ce32); 109 case Collation::IMPLICIT_TAG: 110 return Collation::unassignedCEFromCodePoint(c); 111 } 112 } 113 return Collation::ceFromSimpleCE32(ce32); 114 } 115 116 uint32_t 117 CollationData::getFirstPrimaryForGroup(int32_t script) const { 118 int32_t index = getScriptIndex(script); 119 return index == 0 ? 0 : (uint32_t)scriptStarts[index] << 16; 120 } 121 122 uint32_t 123 CollationData::getLastPrimaryForGroup(int32_t script) const { 124 int32_t index = getScriptIndex(script); 125 if(index == 0) { 126 return 0; 127 } 128 uint32_t limit = scriptStarts[index + 1]; 129 return (limit << 16) - 1; 130 } 131 132 int32_t 133 CollationData::getGroupForPrimary(uint32_t p) const { 134 p >>= 16; 135 if(p < scriptStarts[1] || scriptStarts[scriptStartsLength - 1] <= p) { 136 return -1; 137 } 138 int32_t index = 1; 139 while(p >= scriptStarts[index + 1]) { ++index; } 140 for(int32_t i = 0; i < numScripts; ++i) { 141 if(scriptsIndex[i] == index) { 142 return i; 143 } 144 } 145 for(int32_t i = 0; i < MAX_NUM_SPECIAL_REORDER_CODES; ++i) { 146 if(scriptsIndex[numScripts + i] == index) { 147 return UCOL_REORDER_CODE_FIRST + i; 148 } 149 } 150 return -1; 151 } 152 153 int32_t 154 CollationData::getScriptIndex(int32_t script) const { 155 if(script < 0) { 156 return 0; 157 } else if(script < numScripts) { 158 return scriptsIndex[script]; 159 } else if(script < UCOL_REORDER_CODE_FIRST) { 160 return 0; 161 } else { 162 script -= UCOL_REORDER_CODE_FIRST; 163 if(script < MAX_NUM_SPECIAL_REORDER_CODES) { 164 return scriptsIndex[numScripts + script]; 165 } else { 166 return 0; 167 } 168 } 169 } 170 171 int32_t 172 CollationData::getEquivalentScripts(int32_t script, 173 int32_t dest[], int32_t capacity, 174 UErrorCode &errorCode) const { 175 if(U_FAILURE(errorCode)) { return 0; } 176 int32_t index = getScriptIndex(script); 177 if(index == 0) { return 0; } 178 if(script >= UCOL_REORDER_CODE_FIRST) { 179 // Special groups have no aliases. 180 if(capacity > 0) { 181 dest[0] = script; 182 } else { 183 errorCode = U_BUFFER_OVERFLOW_ERROR; 184 } 185 return 1; 186 } 187 188 int32_t length = 0; 189 for(int32_t i = 0; i < numScripts; ++i) { 190 if(scriptsIndex[i] == index) { 191 if(length < capacity) { 192 dest[length] = i; 193 } 194 ++length; 195 } 196 } 197 if(length > capacity) { 198 errorCode = U_BUFFER_OVERFLOW_ERROR; 199 } 200 return length; 201 } 202 203 void 204 CollationData::makeReorderRanges(const int32_t *reorder, int32_t length, 205 UVector32 &ranges, UErrorCode &errorCode) const { 206 makeReorderRanges(reorder, length, FALSE, ranges, errorCode); 207 } 208 209 void 210 CollationData::makeReorderRanges(const int32_t *reorder, int32_t length, 211 UBool latinMustMove, 212 UVector32 &ranges, UErrorCode &errorCode) const { 213 if(U_FAILURE(errorCode)) { return; } 214 ranges.removeAllElements(); 215 if(length == 0 || (length == 1 && reorder[0] == USCRIPT_UNKNOWN)) { 216 return; 217 } 218 219 // Maps each script-or-group range to a new lead byte. 220 uint8_t table[MAX_NUM_SCRIPT_RANGES]; 221 uprv_memset(table, 0, sizeof(table)); 222 223 { 224 // Set "don't care" values for reserved ranges. 225 int32_t index = scriptsIndex[ 226 numScripts + REORDER_RESERVED_BEFORE_LATIN - UCOL_REORDER_CODE_FIRST]; 227 if(index != 0) { 228 table[index] = 0xff; 229 } 230 index = scriptsIndex[ 231 numScripts + REORDER_RESERVED_AFTER_LATIN - UCOL_REORDER_CODE_FIRST]; 232 if(index != 0) { 233 table[index] = 0xff; 234 } 235 } 236 237 // Never reorder special low and high primary lead bytes. 238 U_ASSERT(scriptStartsLength >= 2); 239 U_ASSERT(scriptStarts[0] == 0); 240 int32_t lowStart = scriptStarts[1]; 241 U_ASSERT(lowStart == ((Collation::MERGE_SEPARATOR_BYTE + 1) << 8)); 242 int32_t highLimit = scriptStarts[scriptStartsLength - 1]; 243 U_ASSERT(highLimit == (Collation::TRAIL_WEIGHT_BYTE << 8)); 244 245 // Get the set of special reorder codes in the input list. 246 // This supports a fixed number of special reorder codes; 247 // it works for data with codes beyond UCOL_REORDER_CODE_LIMIT. 248 uint32_t specials = 0; 249 for(int32_t i = 0; i < length; ++i) { 250 int32_t reorderCode = reorder[i] - UCOL_REORDER_CODE_FIRST; 251 if(0 <= reorderCode && reorderCode < MAX_NUM_SPECIAL_REORDER_CODES) { 252 specials |= (uint32_t)1 << reorderCode; 253 } 254 } 255 256 // Start the reordering with the special low reorder codes that do not occur in the input. 257 for(int32_t i = 0; i < MAX_NUM_SPECIAL_REORDER_CODES; ++i) { 258 int32_t index = scriptsIndex[numScripts + i]; 259 if(index != 0 && (specials & ((uint32_t)1 << i)) == 0) { 260 lowStart = addLowScriptRange(table, index, lowStart); 261 } 262 } 263 264 // Skip the reserved range before Latin if Latin is the first script, 265 // so that we do not move it unnecessarily. 266 int32_t skippedReserved = 0; 267 if(specials == 0 && reorder[0] == USCRIPT_LATIN && !latinMustMove) { 268 int32_t index = scriptsIndex[USCRIPT_LATIN]; 269 U_ASSERT(index != 0); 270 int32_t start = scriptStarts[index]; 271 U_ASSERT(lowStart <= start); 272 skippedReserved = start - lowStart; 273 lowStart = start; 274 } 275 276 // Reorder according to the input scripts, continuing from the bottom of the primary range. 277 int32_t originalLength = length; // length will be decremented if "others" is in the list. 278 UBool hasReorderToEnd = FALSE; 279 for(int32_t i = 0; i < length;) { 280 int32_t script = reorder[i++]; 281 if(script == USCRIPT_UNKNOWN) { 282 // Put the remaining scripts at the top. 283 hasReorderToEnd = TRUE; 284 while(i < length) { 285 script = reorder[--length]; 286 if(script == USCRIPT_UNKNOWN || // Must occur at most once. 287 script == UCOL_REORDER_CODE_DEFAULT) { 288 errorCode = U_ILLEGAL_ARGUMENT_ERROR; 289 return; 290 } 291 int32_t index = getScriptIndex(script); 292 if(index == 0) { continue; } 293 if(table[index] != 0) { // Duplicate or equivalent script. 294 errorCode = U_ILLEGAL_ARGUMENT_ERROR; 295 return; 296 } 297 highLimit = addHighScriptRange(table, index, highLimit); 298 } 299 break; 300 } 301 if(script == UCOL_REORDER_CODE_DEFAULT) { 302 // The default code must be the only one in the list, and that is handled by the caller. 303 // Otherwise it must not be used. 304 errorCode = U_ILLEGAL_ARGUMENT_ERROR; 305 return; 306 } 307 int32_t index = getScriptIndex(script); 308 if(index == 0) { continue; } 309 if(table[index] != 0) { // Duplicate or equivalent script. 310 errorCode = U_ILLEGAL_ARGUMENT_ERROR; 311 return; 312 } 313 lowStart = addLowScriptRange(table, index, lowStart); 314 } 315 316 // Put all remaining scripts into the middle. 317 for(int32_t i = 1; i < scriptStartsLength - 1; ++i) { 318 int32_t leadByte = table[i]; 319 if(leadByte != 0) { continue; } 320 int32_t start = scriptStarts[i]; 321 if(!hasReorderToEnd && start > lowStart) { 322 // No need to move this script. 323 lowStart = start; 324 } 325 lowStart = addLowScriptRange(table, i, lowStart); 326 } 327 if(lowStart > highLimit) { 328 if((lowStart - (skippedReserved & 0xff00)) <= highLimit) { 329 // Try not skipping the before-Latin reserved range. 330 makeReorderRanges(reorder, originalLength, TRUE, ranges, errorCode); 331 return; 332 } 333 // We need more primary lead bytes than available, despite the reserved ranges. 334 errorCode = U_BUFFER_OVERFLOW_ERROR; 335 return; 336 } 337 338 // Turn lead bytes into a list of (limit, offset) pairs. 339 // Encode each pair in one list element: 340 // Upper 16 bits = limit, lower 16 = signed lead byte offset. 341 int32_t offset = 0; 342 for(int32_t i = 1;; ++i) { 343 int32_t nextOffset = offset; 344 while(i < scriptStartsLength - 1) { 345 int32_t newLeadByte = table[i]; 346 if(newLeadByte == 0xff) { 347 // "Don't care" lead byte for reserved range, continue with current offset. 348 } else { 349 nextOffset = newLeadByte - (scriptStarts[i] >> 8); 350 if(nextOffset != offset) { break; } 351 } 352 ++i; 353 } 354 if(offset != 0 || i < scriptStartsLength - 1) { 355 ranges.addElement(((int32_t)scriptStarts[i] << 16) | (offset & 0xffff), errorCode); 356 } 357 if(i == scriptStartsLength - 1) { break; } 358 offset = nextOffset; 359 } 360 } 361 362 int32_t 363 CollationData::addLowScriptRange(uint8_t table[], int32_t index, int32_t lowStart) const { 364 int32_t start = scriptStarts[index]; 365 if((start & 0xff) < (lowStart & 0xff)) { 366 lowStart += 0x100; 367 } 368 table[index] = (uint8_t)(lowStart >> 8); 369 int32_t limit = scriptStarts[index + 1]; 370 lowStart = ((lowStart & 0xff00) + ((limit & 0xff00) - (start & 0xff00))) | (limit & 0xff); 371 return lowStart; 372 } 373 374 int32_t 375 CollationData::addHighScriptRange(uint8_t table[], int32_t index, int32_t highLimit) const { 376 int32_t limit = scriptStarts[index + 1]; 377 if((limit & 0xff) > (highLimit & 0xff)) { 378 highLimit -= 0x100; 379 } 380 int32_t start = scriptStarts[index]; 381 highLimit = ((highLimit & 0xff00) - ((limit & 0xff00) - (start & 0xff00))) | (start & 0xff); 382 table[index] = (uint8_t)(highLimit >> 8); 383 return highLimit; 384 } 385 386 U_NAMESPACE_END 387 388 #endif // !UCONFIG_NO_COLLATION 389
