collationkeys.cpp (28052B)
1 // © 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 ******************************************************************************* 5 * Copyright (C) 2012-2015, International Business Machines 6 * Corporation and others. All Rights Reserved. 7 ******************************************************************************* 8 * collationkeys.cpp 9 * 10 * created on: 2012sep02 11 * created by: Markus W. Scherer 12 */ 13 14 #include "unicode/utypes.h" 15 16 #if !UCONFIG_NO_COLLATION 17 18 #include "unicode/bytestream.h" 19 #include "collation.h" 20 #include "collationiterator.h" 21 #include "collationkeys.h" 22 #include "collationsettings.h" 23 #include "uassert.h" 24 25 U_NAMESPACE_BEGIN 26 27 SortKeyByteSink::~SortKeyByteSink() {} 28 29 void 30 SortKeyByteSink::Append(const char *bytes, int32_t n) { 31 if (n <= 0 || bytes == nullptr) { 32 return; 33 } 34 if (ignore_ > 0) { 35 int32_t ignoreRest = ignore_ - n; 36 if (ignoreRest >= 0) { 37 ignore_ = ignoreRest; 38 return; 39 } else { 40 bytes += ignore_; 41 n = -ignoreRest; 42 ignore_ = 0; 43 } 44 } 45 int32_t length = appended_; 46 appended_ += n; 47 if ((buffer_ + length) == bytes) { 48 return; // the caller used GetAppendBuffer() and wrote the bytes already 49 } 50 int32_t available = capacity_ - length; 51 if (n <= available) { 52 uprv_memcpy(buffer_ + length, bytes, n); 53 } else { 54 AppendBeyondCapacity(bytes, n, length); 55 } 56 } 57 58 char * 59 SortKeyByteSink::GetAppendBuffer(int32_t min_capacity, 60 int32_t desired_capacity_hint, 61 char *scratch, 62 int32_t scratch_capacity, 63 int32_t *result_capacity) { 64 if (min_capacity < 1 || scratch_capacity < min_capacity) { 65 *result_capacity = 0; 66 return nullptr; 67 } 68 if (ignore_ > 0) { 69 // Do not write ignored bytes right at the end of the buffer. 70 *result_capacity = scratch_capacity; 71 return scratch; 72 } 73 int32_t available = capacity_ - appended_; 74 if (available >= min_capacity) { 75 *result_capacity = available; 76 return buffer_ + appended_; 77 } else if (Resize(desired_capacity_hint, appended_)) { 78 *result_capacity = capacity_ - appended_; 79 return buffer_ + appended_; 80 } else { 81 *result_capacity = scratch_capacity; 82 return scratch; 83 } 84 } 85 86 namespace { 87 88 /** 89 * uint8_t byte buffer, similar to CharString but simpler. 90 */ 91 class SortKeyLevel : public UMemory { 92 public: 93 SortKeyLevel() : len(0), ok(true) {} 94 ~SortKeyLevel() {} 95 96 /** @return false if memory allocation failed */ 97 UBool isOk() const { return ok; } 98 UBool isEmpty() const { return len == 0; } 99 int32_t length() const { return len; } 100 const uint8_t *data() const { return buffer.getAlias(); } 101 uint8_t operator[](int32_t index) const { return buffer[index]; } 102 103 uint8_t *data() { return buffer.getAlias(); } 104 105 void appendByte(uint32_t b); 106 void appendWeight16(uint32_t w); 107 void appendWeight32(uint32_t w); 108 void appendReverseWeight16(uint32_t w); 109 110 /** Appends all but the last byte to the sink. The last byte should be the 01 terminator. */ 111 void appendTo(ByteSink &sink) const { 112 U_ASSERT(len > 0 && buffer[len - 1] == 1); 113 sink.Append(reinterpret_cast<const char *>(buffer.getAlias()), len - 1); 114 } 115 116 private: 117 MaybeStackArray<uint8_t, 40> buffer; 118 int32_t len; 119 UBool ok; 120 121 UBool ensureCapacity(int32_t appendCapacity); 122 123 SortKeyLevel(const SortKeyLevel &other); // forbid copying of this class 124 SortKeyLevel &operator=(const SortKeyLevel &other); // forbid copying of this class 125 }; 126 127 void SortKeyLevel::appendByte(uint32_t b) { 128 if(len < buffer.getCapacity() || ensureCapacity(1)) { 129 buffer[len++] = static_cast<uint8_t>(b); 130 } 131 } 132 133 void 134 SortKeyLevel::appendWeight16(uint32_t w) { 135 U_ASSERT((w & 0xffff) != 0); 136 uint8_t b0 = static_cast<uint8_t>(w >> 8); 137 uint8_t b1 = static_cast<uint8_t>(w); 138 int32_t appendLength = (b1 == 0) ? 1 : 2; 139 if((len + appendLength) <= buffer.getCapacity() || ensureCapacity(appendLength)) { 140 buffer[len++] = b0; 141 if(b1 != 0) { 142 buffer[len++] = b1; 143 } 144 } 145 } 146 147 void 148 SortKeyLevel::appendWeight32(uint32_t w) { 149 U_ASSERT(w != 0); 150 uint8_t bytes[4] = { 151 static_cast<uint8_t>(w >> 24), 152 static_cast<uint8_t>(w >> 16), 153 static_cast<uint8_t>(w >> 8), 154 static_cast<uint8_t>(w) 155 }; 156 int32_t appendLength = (bytes[1] == 0) ? 1 : (bytes[2] == 0) ? 2 : (bytes[3] == 0) ? 3 : 4; 157 if((len + appendLength) <= buffer.getCapacity() || ensureCapacity(appendLength)) { 158 buffer[len++] = bytes[0]; 159 if(bytes[1] != 0) { 160 buffer[len++] = bytes[1]; 161 if(bytes[2] != 0) { 162 buffer[len++] = bytes[2]; 163 if(bytes[3] != 0) { 164 buffer[len++] = bytes[3]; 165 } 166 } 167 } 168 } 169 } 170 171 void 172 SortKeyLevel::appendReverseWeight16(uint32_t w) { 173 U_ASSERT((w & 0xffff) != 0); 174 uint8_t b0 = static_cast<uint8_t>(w >> 8); 175 uint8_t b1 = static_cast<uint8_t>(w); 176 int32_t appendLength = (b1 == 0) ? 1 : 2; 177 if((len + appendLength) <= buffer.getCapacity() || ensureCapacity(appendLength)) { 178 if(b1 == 0) { 179 buffer[len++] = b0; 180 } else { 181 buffer[len] = b1; 182 buffer[len + 1] = b0; 183 len += 2; 184 } 185 } 186 } 187 188 UBool SortKeyLevel::ensureCapacity(int32_t appendCapacity) { 189 if(!ok) { 190 return false; 191 } 192 int32_t newCapacity = 2 * buffer.getCapacity(); 193 int32_t altCapacity = len + 2 * appendCapacity; 194 if (newCapacity < altCapacity) { 195 newCapacity = altCapacity; 196 } 197 if (newCapacity < 200) { 198 newCapacity = 200; 199 } 200 if(buffer.resize(newCapacity, len)==nullptr) { 201 return ok = false; 202 } 203 return true; 204 } 205 206 } // namespace 207 208 CollationKeys::LevelCallback::~LevelCallback() {} 209 210 UBool 211 CollationKeys::LevelCallback::needToWrite(Collation::Level /*level*/) { return true; } 212 213 /** 214 * Map from collation strength (UColAttributeValue) 215 * to a mask of Collation::Level bits up to that strength, 216 * excluding the CASE_LEVEL which is independent of the strength, 217 * and excluding IDENTICAL_LEVEL which this function does not write. 218 */ 219 static const uint32_t levelMasks[UCOL_STRENGTH_LIMIT] = { 220 2, // UCOL_PRIMARY -> PRIMARY_LEVEL 221 6, // UCOL_SECONDARY -> up to SECONDARY_LEVEL 222 0x16, // UCOL_TERTIARY -> up to TERTIARY_LEVEL 223 0x36, // UCOL_QUATERNARY -> up to QUATERNARY_LEVEL 224 0, 0, 0, 0, 225 0, 0, 0, 0, 226 0, 0, 0, 227 0x36 // UCOL_IDENTICAL -> up to QUATERNARY_LEVEL 228 }; 229 230 void 231 CollationKeys::writeSortKeyUpToQuaternary(CollationIterator &iter, 232 const UBool *compressibleBytes, 233 const CollationSettings &settings, 234 SortKeyByteSink &sink, 235 Collation::Level minLevel, LevelCallback &callback, 236 UBool preflight, UErrorCode &errorCode) { 237 if(U_FAILURE(errorCode)) { return; } 238 239 int32_t options = settings.options; 240 // Set of levels to process and write. 241 uint32_t levels = levelMasks[CollationSettings::getStrength(options)]; 242 if((options & CollationSettings::CASE_LEVEL) != 0) { 243 levels |= Collation::CASE_LEVEL_FLAG; 244 } 245 // Minus the levels below minLevel. 246 levels &= ~((static_cast<uint32_t>(1) << minLevel) - 1); 247 if(levels == 0) { return; } 248 249 uint32_t variableTop; 250 if((options & CollationSettings::ALTERNATE_MASK) == 0) { 251 variableTop = 0; 252 } else { 253 // +1 so that we can use "<" and primary ignorables test out early. 254 variableTop = settings.variableTop + 1; 255 } 256 257 uint32_t tertiaryMask = CollationSettings::getTertiaryMask(options); 258 259 SortKeyLevel cases; 260 SortKeyLevel secondaries; 261 SortKeyLevel tertiaries; 262 SortKeyLevel quaternaries; 263 264 uint32_t prevReorderedPrimary = 0; // 0==no compression 265 int32_t commonCases = 0; 266 int32_t commonSecondaries = 0; 267 int32_t commonTertiaries = 0; 268 int32_t commonQuaternaries = 0; 269 270 uint32_t prevSecondary = 0; 271 int32_t secSegmentStart = 0; 272 273 for(;;) { 274 // No need to keep all CEs in the buffer when we write a sort key. 275 iter.clearCEsIfNoneRemaining(); 276 int64_t ce = iter.nextCE(errorCode); 277 uint32_t p = static_cast<uint32_t>(ce >> 32); 278 if(p < variableTop && p > Collation::MERGE_SEPARATOR_PRIMARY) { 279 // Variable CE, shift it to quaternary level. 280 // Ignore all following primary ignorables, and shift further variable CEs. 281 if(commonQuaternaries != 0) { 282 --commonQuaternaries; 283 while(commonQuaternaries >= QUAT_COMMON_MAX_COUNT) { 284 quaternaries.appendByte(QUAT_COMMON_MIDDLE); 285 commonQuaternaries -= QUAT_COMMON_MAX_COUNT; 286 } 287 // Shifted primary weights are lower than the common weight. 288 quaternaries.appendByte(QUAT_COMMON_LOW + commonQuaternaries); 289 commonQuaternaries = 0; 290 } 291 do { 292 if((levels & Collation::QUATERNARY_LEVEL_FLAG) != 0) { 293 if(settings.hasReordering()) { 294 p = settings.reorder(p); 295 } 296 if((p >> 24) >= QUAT_SHIFTED_LIMIT_BYTE) { 297 // Prevent shifted primary lead bytes from 298 // overlapping with the common compression range. 299 quaternaries.appendByte(QUAT_SHIFTED_LIMIT_BYTE); 300 } 301 quaternaries.appendWeight32(p); 302 } 303 do { 304 ce = iter.nextCE(errorCode); 305 p = static_cast<uint32_t>(ce >> 32); 306 } while(p == 0); 307 } while(p < variableTop && p > Collation::MERGE_SEPARATOR_PRIMARY); 308 } 309 // ce could be primary ignorable, or NO_CE, or the merge separator, 310 // or a regular primary CE, but it is not variable. 311 // If ce==NO_CE, then write nothing for the primary level but 312 // terminate compression on all levels and then exit the loop. 313 if(p > Collation::NO_CE_PRIMARY && (levels & Collation::PRIMARY_LEVEL_FLAG) != 0) { 314 // Test the un-reordered primary for compressibility. 315 UBool isCompressible = compressibleBytes[p >> 24]; 316 if(settings.hasReordering()) { 317 p = settings.reorder(p); 318 } 319 uint32_t p1 = p >> 24; 320 if(!isCompressible || p1 != (prevReorderedPrimary >> 24)) { 321 if(prevReorderedPrimary != 0) { 322 if(p < prevReorderedPrimary) { 323 // No primary compression terminator 324 // at the end of the level or merged segment. 325 if(p1 > Collation::MERGE_SEPARATOR_BYTE) { 326 sink.Append(Collation::PRIMARY_COMPRESSION_LOW_BYTE); 327 } 328 } else { 329 sink.Append(Collation::PRIMARY_COMPRESSION_HIGH_BYTE); 330 } 331 } 332 sink.Append(p1); 333 if(isCompressible) { 334 prevReorderedPrimary = p; 335 } else { 336 prevReorderedPrimary = 0; 337 } 338 } 339 char p2 = static_cast<char>(p >> 16); 340 if(p2 != 0) { 341 char buffer[3] = {p2, static_cast<char>(p >> 8), static_cast<char>(p)}; 342 sink.Append(buffer, (buffer[1] == 0) ? 1 : (buffer[2] == 0) ? 2 : 3); 343 } 344 // Optimization for internalNextSortKeyPart(): 345 // When the primary level overflows we can stop because we need not 346 // calculate (preflight) the whole sort key length. 347 if(!preflight && sink.Overflowed()) { 348 if(U_SUCCESS(errorCode) && !sink.IsOk()) { 349 errorCode = U_MEMORY_ALLOCATION_ERROR; 350 } 351 return; 352 } 353 } 354 355 uint32_t lower32 = static_cast<uint32_t>(ce); 356 if(lower32 == 0) { continue; } // completely ignorable, no secondary/case/tertiary/quaternary 357 358 if((levels & Collation::SECONDARY_LEVEL_FLAG) != 0) { 359 uint32_t s = lower32 >> 16; 360 if(s == 0) { 361 // secondary ignorable 362 } else if(s == Collation::COMMON_WEIGHT16 && 363 ((options & CollationSettings::BACKWARD_SECONDARY) == 0 || 364 p != Collation::MERGE_SEPARATOR_PRIMARY)) { 365 // s is a common secondary weight, and 366 // backwards-secondary is off or the ce is not the merge separator. 367 ++commonSecondaries; 368 } else if((options & CollationSettings::BACKWARD_SECONDARY) == 0) { 369 if(commonSecondaries != 0) { 370 --commonSecondaries; 371 while(commonSecondaries >= SEC_COMMON_MAX_COUNT) { 372 secondaries.appendByte(SEC_COMMON_MIDDLE); 373 commonSecondaries -= SEC_COMMON_MAX_COUNT; 374 } 375 uint32_t b; 376 if(s < Collation::COMMON_WEIGHT16) { 377 b = SEC_COMMON_LOW + commonSecondaries; 378 } else { 379 b = SEC_COMMON_HIGH - commonSecondaries; 380 } 381 secondaries.appendByte(b); 382 commonSecondaries = 0; 383 } 384 secondaries.appendWeight16(s); 385 } else { 386 if(commonSecondaries != 0) { 387 --commonSecondaries; 388 // Append reverse weights. The level will be re-reversed later. 389 int32_t remainder = commonSecondaries % SEC_COMMON_MAX_COUNT; 390 uint32_t b; 391 if(prevSecondary < Collation::COMMON_WEIGHT16) { 392 b = SEC_COMMON_LOW + remainder; 393 } else { 394 b = SEC_COMMON_HIGH - remainder; 395 } 396 secondaries.appendByte(b); 397 commonSecondaries -= remainder; 398 // commonSecondaries is now a multiple of SEC_COMMON_MAX_COUNT. 399 while(commonSecondaries > 0) { // same as >= SEC_COMMON_MAX_COUNT 400 secondaries.appendByte(SEC_COMMON_MIDDLE); 401 commonSecondaries -= SEC_COMMON_MAX_COUNT; 402 } 403 // commonSecondaries == 0 404 } 405 if(0 < p && p <= Collation::MERGE_SEPARATOR_PRIMARY) { 406 // The backwards secondary level compares secondary weights backwards 407 // within segments separated by the merge separator (U+FFFE). 408 uint8_t *secs = secondaries.data(); 409 int32_t last = secondaries.length() - 1; 410 if(secSegmentStart < last) { 411 uint8_t *q = secs + secSegmentStart; 412 uint8_t *r = secs + last; 413 do { 414 uint8_t b = *q; 415 *q++ = *r; 416 *r-- = b; 417 } while(q < r); 418 } 419 secondaries.appendByte(p == Collation::NO_CE_PRIMARY ? 420 Collation::LEVEL_SEPARATOR_BYTE : Collation::MERGE_SEPARATOR_BYTE); 421 prevSecondary = 0; 422 secSegmentStart = secondaries.length(); 423 } else { 424 secondaries.appendReverseWeight16(s); 425 prevSecondary = s; 426 } 427 } 428 } 429 430 if((levels & Collation::CASE_LEVEL_FLAG) != 0) { 431 if((CollationSettings::getStrength(options) == UCOL_PRIMARY) ? 432 p == 0 : lower32 <= 0xffff) { 433 // Primary+caseLevel: Ignore case level weights of primary ignorables. 434 // Otherwise: Ignore case level weights of secondary ignorables. 435 // For details see the comments in the CollationCompare class. 436 } else { 437 uint32_t c = (lower32 >> 8) & 0xff; // case bits & tertiary lead byte 438 U_ASSERT((c & 0xc0) != 0xc0); 439 if((c & 0xc0) == 0 && c > Collation::LEVEL_SEPARATOR_BYTE) { 440 ++commonCases; 441 } else { 442 if((options & CollationSettings::UPPER_FIRST) == 0) { 443 // lowerFirst: Compress common weights to nibbles 1..7..13, mixed=14, upper=15. 444 // If there are only common (=lowest) weights in the whole level, 445 // then we need not write anything. 446 // Level length differences are handled already on the next-higher level. 447 if(commonCases != 0 && 448 (c > Collation::LEVEL_SEPARATOR_BYTE || !cases.isEmpty())) { 449 --commonCases; 450 while(commonCases >= CASE_LOWER_FIRST_COMMON_MAX_COUNT) { 451 cases.appendByte(CASE_LOWER_FIRST_COMMON_MIDDLE << 4); 452 commonCases -= CASE_LOWER_FIRST_COMMON_MAX_COUNT; 453 } 454 uint32_t b; 455 if(c <= Collation::LEVEL_SEPARATOR_BYTE) { 456 b = CASE_LOWER_FIRST_COMMON_LOW + commonCases; 457 } else { 458 b = CASE_LOWER_FIRST_COMMON_HIGH - commonCases; 459 } 460 cases.appendByte(b << 4); 461 commonCases = 0; 462 } 463 if(c > Collation::LEVEL_SEPARATOR_BYTE) { 464 c = (CASE_LOWER_FIRST_COMMON_HIGH + (c >> 6)) << 4; // 14 or 15 465 } 466 } else { 467 // upperFirst: Compress common weights to nibbles 3..15, mixed=2, upper=1. 468 // The compressed common case weights only go up from the "low" value 469 // because with upperFirst the common weight is the highest one. 470 if(commonCases != 0) { 471 --commonCases; 472 while(commonCases >= CASE_UPPER_FIRST_COMMON_MAX_COUNT) { 473 cases.appendByte(CASE_UPPER_FIRST_COMMON_LOW << 4); 474 commonCases -= CASE_UPPER_FIRST_COMMON_MAX_COUNT; 475 } 476 cases.appendByte((CASE_UPPER_FIRST_COMMON_LOW + commonCases) << 4); 477 commonCases = 0; 478 } 479 if(c > Collation::LEVEL_SEPARATOR_BYTE) { 480 c = (CASE_UPPER_FIRST_COMMON_LOW - (c >> 6)) << 4; // 2 or 1 481 } 482 } 483 // c is a separator byte 01, 484 // or a left-shifted nibble 0x10, 0x20, ... 0xf0. 485 cases.appendByte(c); 486 } 487 } 488 } 489 490 if((levels & Collation::TERTIARY_LEVEL_FLAG) != 0) { 491 uint32_t t = lower32 & tertiaryMask; 492 U_ASSERT((lower32 & 0xc000) != 0xc000); 493 if(t == Collation::COMMON_WEIGHT16) { 494 ++commonTertiaries; 495 } else if((tertiaryMask & 0x8000) == 0) { 496 // Tertiary weights without case bits. 497 // Move lead bytes 06..3F to C6..FF for a large common-weight range. 498 if(commonTertiaries != 0) { 499 --commonTertiaries; 500 while(commonTertiaries >= TER_ONLY_COMMON_MAX_COUNT) { 501 tertiaries.appendByte(TER_ONLY_COMMON_MIDDLE); 502 commonTertiaries -= TER_ONLY_COMMON_MAX_COUNT; 503 } 504 uint32_t b; 505 if(t < Collation::COMMON_WEIGHT16) { 506 b = TER_ONLY_COMMON_LOW + commonTertiaries; 507 } else { 508 b = TER_ONLY_COMMON_HIGH - commonTertiaries; 509 } 510 tertiaries.appendByte(b); 511 commonTertiaries = 0; 512 } 513 if(t > Collation::COMMON_WEIGHT16) { t += 0xc000; } 514 tertiaries.appendWeight16(t); 515 } else if((options & CollationSettings::UPPER_FIRST) == 0) { 516 // Tertiary weights with caseFirst=lowerFirst. 517 // Move lead bytes 06..BF to 46..FF for the common-weight range. 518 if(commonTertiaries != 0) { 519 --commonTertiaries; 520 while(commonTertiaries >= TER_LOWER_FIRST_COMMON_MAX_COUNT) { 521 tertiaries.appendByte(TER_LOWER_FIRST_COMMON_MIDDLE); 522 commonTertiaries -= TER_LOWER_FIRST_COMMON_MAX_COUNT; 523 } 524 uint32_t b; 525 if(t < Collation::COMMON_WEIGHT16) { 526 b = TER_LOWER_FIRST_COMMON_LOW + commonTertiaries; 527 } else { 528 b = TER_LOWER_FIRST_COMMON_HIGH - commonTertiaries; 529 } 530 tertiaries.appendByte(b); 531 commonTertiaries = 0; 532 } 533 if(t > Collation::COMMON_WEIGHT16) { t += 0x4000; } 534 tertiaries.appendWeight16(t); 535 } else { 536 // Tertiary weights with caseFirst=upperFirst. 537 // Do not change the artificial uppercase weight of a tertiary CE (0.0.ut), 538 // to keep tertiary CEs well-formed. 539 // Their case+tertiary weights must be greater than those of 540 // primary and secondary CEs. 541 // 542 // Separator 01 -> 01 (unchanged) 543 // Lowercase 02..04 -> 82..84 (includes uncased) 544 // Common weight 05 -> 85..C5 (common-weight compression range) 545 // Lowercase 06..3F -> C6..FF 546 // Mixed case 42..7F -> 42..7F 547 // Uppercase 82..BF -> 02..3F 548 // Tertiary CE 86..BF -> C6..FF 549 if(t <= Collation::NO_CE_WEIGHT16) { 550 // Keep separators unchanged. 551 } else if(lower32 > 0xffff) { 552 // Invert case bits of primary & secondary CEs. 553 t ^= 0xc000; 554 if(t < (TER_UPPER_FIRST_COMMON_HIGH << 8)) { 555 t -= 0x4000; 556 } 557 } else { 558 // Keep uppercase bits of tertiary CEs. 559 U_ASSERT(0x8600 <= t && t <= 0xbfff); 560 t += 0x4000; 561 } 562 if(commonTertiaries != 0) { 563 --commonTertiaries; 564 while(commonTertiaries >= TER_UPPER_FIRST_COMMON_MAX_COUNT) { 565 tertiaries.appendByte(TER_UPPER_FIRST_COMMON_MIDDLE); 566 commonTertiaries -= TER_UPPER_FIRST_COMMON_MAX_COUNT; 567 } 568 uint32_t b; 569 if(t < (TER_UPPER_FIRST_COMMON_LOW << 8)) { 570 b = TER_UPPER_FIRST_COMMON_LOW + commonTertiaries; 571 } else { 572 b = TER_UPPER_FIRST_COMMON_HIGH - commonTertiaries; 573 } 574 tertiaries.appendByte(b); 575 commonTertiaries = 0; 576 } 577 tertiaries.appendWeight16(t); 578 } 579 } 580 581 if((levels & Collation::QUATERNARY_LEVEL_FLAG) != 0) { 582 uint32_t q = lower32 & 0xffff; 583 if((q & 0xc0) == 0 && q > Collation::NO_CE_WEIGHT16) { 584 ++commonQuaternaries; 585 } else if(q == Collation::NO_CE_WEIGHT16 && 586 (options & CollationSettings::ALTERNATE_MASK) == 0 && 587 quaternaries.isEmpty()) { 588 // If alternate=non-ignorable and there are only common quaternary weights, 589 // then we need not write anything. 590 // The only weights greater than the merge separator and less than the common weight 591 // are shifted primary weights, which are not generated for alternate=non-ignorable. 592 // There are also exactly as many quaternary weights as tertiary weights, 593 // so level length differences are handled already on tertiary level. 594 // Any above-common quaternary weight will compare greater regardless. 595 quaternaries.appendByte(Collation::LEVEL_SEPARATOR_BYTE); 596 } else { 597 if(q == Collation::NO_CE_WEIGHT16) { 598 q = Collation::LEVEL_SEPARATOR_BYTE; 599 } else { 600 q = 0xfc + ((q >> 6) & 3); 601 } 602 if(commonQuaternaries != 0) { 603 --commonQuaternaries; 604 while(commonQuaternaries >= QUAT_COMMON_MAX_COUNT) { 605 quaternaries.appendByte(QUAT_COMMON_MIDDLE); 606 commonQuaternaries -= QUAT_COMMON_MAX_COUNT; 607 } 608 uint32_t b; 609 if(q < QUAT_COMMON_LOW) { 610 b = QUAT_COMMON_LOW + commonQuaternaries; 611 } else { 612 b = QUAT_COMMON_HIGH - commonQuaternaries; 613 } 614 quaternaries.appendByte(b); 615 commonQuaternaries = 0; 616 } 617 quaternaries.appendByte(q); 618 } 619 } 620 621 if((lower32 >> 24) == Collation::LEVEL_SEPARATOR_BYTE) { break; } // ce == NO_CE 622 } 623 624 if(U_FAILURE(errorCode)) { return; } 625 626 // Append the beyond-primary levels. 627 UBool ok = true; 628 if((levels & Collation::SECONDARY_LEVEL_FLAG) != 0) { 629 if(!callback.needToWrite(Collation::SECONDARY_LEVEL)) { return; } 630 ok &= secondaries.isOk(); 631 sink.Append(Collation::LEVEL_SEPARATOR_BYTE); 632 secondaries.appendTo(sink); 633 } 634 635 if((levels & Collation::CASE_LEVEL_FLAG) != 0) { 636 if(!callback.needToWrite(Collation::CASE_LEVEL)) { return; } 637 ok &= cases.isOk(); 638 sink.Append(Collation::LEVEL_SEPARATOR_BYTE); 639 // Write pairs of nibbles as bytes, except separator bytes as themselves. 640 int32_t length = cases.length() - 1; // Ignore the trailing NO_CE. 641 uint8_t b = 0; 642 for(int32_t i = 0; i < length; ++i) { 643 uint8_t c = cases[i]; 644 U_ASSERT((c & 0xf) == 0 && c != 0); 645 if(b == 0) { 646 b = c; 647 } else { 648 sink.Append(b | (c >> 4)); 649 b = 0; 650 } 651 } 652 if(b != 0) { 653 sink.Append(b); 654 } 655 } 656 657 if((levels & Collation::TERTIARY_LEVEL_FLAG) != 0) { 658 if(!callback.needToWrite(Collation::TERTIARY_LEVEL)) { return; } 659 ok &= tertiaries.isOk(); 660 sink.Append(Collation::LEVEL_SEPARATOR_BYTE); 661 tertiaries.appendTo(sink); 662 } 663 664 if((levels & Collation::QUATERNARY_LEVEL_FLAG) != 0) { 665 if(!callback.needToWrite(Collation::QUATERNARY_LEVEL)) { return; } 666 ok &= quaternaries.isOk(); 667 sink.Append(Collation::LEVEL_SEPARATOR_BYTE); 668 quaternaries.appendTo(sink); 669 } 670 671 if(!ok || !sink.IsOk()) { 672 errorCode = U_MEMORY_ALLOCATION_ERROR; 673 } 674 } 675 676 U_NAMESPACE_END 677 678 #endif // !UCONFIG_NO_COLLATION