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