1 /*
2 *******************************************************************************
3 * Copyright (C) 2013-2015, International Business Machines
4 * Corporation and others.  All Rights Reserved.
5 *******************************************************************************
6 * collationfastlatinbuilder.cpp
7 *
8 * created on: 2013aug09
9 * created by: Markus W. Scherer
10 */
11 
12 #define DEBUG_COLLATION_FAST_LATIN_BUILDER 0  // 0 or 1 or 2
13 #if DEBUG_COLLATION_FAST_LATIN_BUILDER
14 #include <stdio.h>
15 #include <string>
16 #endif
17 
18 #include "unicode/utypes.h"
19 
20 #if !UCONFIG_NO_COLLATION
21 
22 #include "unicode/ucol.h"
23 #include "unicode/ucharstrie.h"
24 #include "unicode/unistr.h"
25 #include "unicode/uobject.h"
26 #include "unicode/uscript.h"
27 #include "cmemory.h"
28 #include "collation.h"
29 #include "collationdata.h"
30 #include "collationfastlatin.h"
31 #include "collationfastlatinbuilder.h"
32 #include "uassert.h"
33 #include "uvectr64.h"
34 
35 U_NAMESPACE_BEGIN
36 
37 struct CollationData;
38 
39 namespace {
40 
41 /**
42  * Compare two signed int64_t values as if they were unsigned.
43  */
44 int32_t
compareInt64AsUnsigned(int64_t a,int64_t b)45 compareInt64AsUnsigned(int64_t a, int64_t b) {
46     if((uint64_t)a < (uint64_t)b) {
47         return -1;
48     } else if((uint64_t)a > (uint64_t)b) {
49         return 1;
50     } else {
51         return 0;
52     }
53 }
54 
55 // TODO: Merge this with the near-identical version in collationbasedatabuilder.cpp
56 /**
57  * Like Java Collections.binarySearch(List, String, Comparator).
58  *
59  * @return the index>=0 where the item was found,
60  *         or the index<0 for inserting the string at ~index in sorted order
61  */
62 int32_t
binarySearch(const int64_t list[],int32_t limit,int64_t ce)63 binarySearch(const int64_t list[], int32_t limit, int64_t ce) {
64     if (limit == 0) { return ~0; }
65     int32_t start = 0;
66     for (;;) {
67         int32_t i = (start + limit) / 2;
68         int32_t cmp = compareInt64AsUnsigned(ce, list[i]);
69         if (cmp == 0) {
70             return i;
71         } else if (cmp < 0) {
72             if (i == start) {
73                 return ~start;  // insert ce before i
74             }
75             limit = i;
76         } else {
77             if (i == start) {
78                 return ~(start + 1);  // insert ce after i
79             }
80             start = i;
81         }
82     }
83 }
84 
85 }  // namespace
86 
CollationFastLatinBuilder(UErrorCode & errorCode)87 CollationFastLatinBuilder::CollationFastLatinBuilder(UErrorCode &errorCode)
88         : ce0(0), ce1(0),
89           contractionCEs(errorCode), uniqueCEs(errorCode),
90           miniCEs(NULL),
91           firstDigitPrimary(0), firstLatinPrimary(0), lastLatinPrimary(0),
92           firstShortPrimary(0), shortPrimaryOverflow(FALSE),
93           headerLength(0) {
94 }
95 
~CollationFastLatinBuilder()96 CollationFastLatinBuilder::~CollationFastLatinBuilder() {
97     uprv_free(miniCEs);
98 }
99 
100 UBool
forData(const CollationData & data,UErrorCode & errorCode)101 CollationFastLatinBuilder::forData(const CollationData &data, UErrorCode &errorCode) {
102     if(U_FAILURE(errorCode)) { return FALSE; }
103     if(!result.isEmpty()) {  // This builder is not reusable.
104         errorCode = U_INVALID_STATE_ERROR;
105         return FALSE;
106     }
107     if(!loadGroups(data, errorCode)) { return FALSE; }
108 
109     // Fast handling of digits.
110     firstShortPrimary = firstDigitPrimary;
111     getCEs(data, errorCode);
112     if(!encodeUniqueCEs(errorCode)) { return FALSE; }
113     if(shortPrimaryOverflow) {
114         // Give digits long mini primaries,
115         // so that there are more short primaries for letters.
116         firstShortPrimary = firstLatinPrimary;
117         resetCEs();
118         getCEs(data, errorCode);
119         if(!encodeUniqueCEs(errorCode)) { return FALSE; }
120     }
121     // Note: If we still have a short-primary overflow but not a long-primary overflow,
122     // then we could calculate how many more long primaries would fit,
123     // and set the firstShortPrimary to that many after the current firstShortPrimary,
124     // and try again.
125     // However, this might only benefit the en_US_POSIX tailoring,
126     // and it is simpler to suppress building fast Latin data for it in genrb,
127     // or by returning FALSE here if shortPrimaryOverflow.
128 
129     UBool ok = !shortPrimaryOverflow &&
130             encodeCharCEs(errorCode) && encodeContractions(errorCode);
131     contractionCEs.removeAllElements();  // might reduce heap memory usage
132     uniqueCEs.removeAllElements();
133     return ok;
134 }
135 
136 UBool
loadGroups(const CollationData & data,UErrorCode & errorCode)137 CollationFastLatinBuilder::loadGroups(const CollationData &data, UErrorCode &errorCode) {
138     if(U_FAILURE(errorCode)) { return FALSE; }
139     headerLength = 1 + NUM_SPECIAL_GROUPS;
140     uint32_t r0 = (CollationFastLatin::VERSION << 8) | headerLength;
141     result.append((UChar)r0);
142     // The first few reordering groups should be special groups
143     // (space, punct, ..., digit) followed by Latn, then Grek and other scripts.
144     for(int32_t i = 0; i < NUM_SPECIAL_GROUPS; ++i) {
145         lastSpecialPrimaries[i] = data.getLastPrimaryForGroup(UCOL_REORDER_CODE_FIRST + i);
146         if(lastSpecialPrimaries[i] == 0) {
147             // missing data
148             return FALSE;
149         }
150         result.append(0);  // reserve a slot for this group
151     }
152 
153     firstDigitPrimary = data.getFirstPrimaryForGroup(UCOL_REORDER_CODE_DIGIT);
154     firstLatinPrimary = data.getFirstPrimaryForGroup(USCRIPT_LATIN);
155     lastLatinPrimary = data.getLastPrimaryForGroup(USCRIPT_LATIN);
156     if(firstDigitPrimary == 0 || firstLatinPrimary == 0) {
157         // missing data
158         return FALSE;
159     }
160     return TRUE;
161 }
162 
163 UBool
inSameGroup(uint32_t p,uint32_t q) const164 CollationFastLatinBuilder::inSameGroup(uint32_t p, uint32_t q) const {
165     // Both or neither need to be encoded as short primaries,
166     // so that we can test only one and use the same bit mask.
167     if(p >= firstShortPrimary) {
168         return q >= firstShortPrimary;
169     } else if(q >= firstShortPrimary) {
170         return FALSE;
171     }
172     // Both or neither must be potentially-variable,
173     // so that we can test only one and determine if both are variable.
174     uint32_t lastVariablePrimary = lastSpecialPrimaries[NUM_SPECIAL_GROUPS - 1];
175     if(p > lastVariablePrimary) {
176         return q > lastVariablePrimary;
177     } else if(q > lastVariablePrimary) {
178         return FALSE;
179     }
180     // Both will be encoded with long mini primaries.
181     // They must be in the same special reordering group,
182     // so that we can test only one and determine if both are variable.
183     U_ASSERT(p != 0 && q != 0);
184     for(int32_t i = 0;; ++i) {  // will terminate
185         uint32_t lastPrimary = lastSpecialPrimaries[i];
186         if(p <= lastPrimary) {
187             return q <= lastPrimary;
188         } else if(q <= lastPrimary) {
189             return FALSE;
190         }
191     }
192 }
193 
194 void
resetCEs()195 CollationFastLatinBuilder::resetCEs() {
196     contractionCEs.removeAllElements();
197     uniqueCEs.removeAllElements();
198     shortPrimaryOverflow = FALSE;
199     result.truncate(headerLength);
200 }
201 
202 void
getCEs(const CollationData & data,UErrorCode & errorCode)203 CollationFastLatinBuilder::getCEs(const CollationData &data, UErrorCode &errorCode) {
204     if(U_FAILURE(errorCode)) { return; }
205     int32_t i = 0;
206     for(UChar c = 0;; ++i, ++c) {
207         if(c == CollationFastLatin::LATIN_LIMIT) {
208             c = CollationFastLatin::PUNCT_START;
209         } else if(c == CollationFastLatin::PUNCT_LIMIT) {
210             break;
211         }
212         const CollationData *d;
213         uint32_t ce32 = data.getCE32(c);
214         if(ce32 == Collation::FALLBACK_CE32) {
215             d = data.base;
216             ce32 = d->getCE32(c);
217         } else {
218             d = &data;
219         }
220         if(getCEsFromCE32(*d, c, ce32, errorCode)) {
221             charCEs[i][0] = ce0;
222             charCEs[i][1] = ce1;
223             addUniqueCE(ce0, errorCode);
224             addUniqueCE(ce1, errorCode);
225         } else {
226             // bail out for c
227             charCEs[i][0] = ce0 = Collation::NO_CE;
228             charCEs[i][1] = ce1 = 0;
229         }
230         if(c == 0 && !isContractionCharCE(ce0)) {
231             // Always map U+0000 to a contraction.
232             // Write a contraction list with only a default value if there is no real contraction.
233             U_ASSERT(contractionCEs.isEmpty());
234             addContractionEntry(CollationFastLatin::CONTR_CHAR_MASK, ce0, ce1, errorCode);
235             charCEs[0][0] = ((int64_t)Collation::NO_CE_PRIMARY << 32) | CONTRACTION_FLAG;
236             charCEs[0][1] = 0;
237         }
238     }
239     // Terminate the last contraction list.
240     contractionCEs.addElement(CollationFastLatin::CONTR_CHAR_MASK, errorCode);
241 }
242 
243 UBool
getCEsFromCE32(const CollationData & data,UChar32 c,uint32_t ce32,UErrorCode & errorCode)244 CollationFastLatinBuilder::getCEsFromCE32(const CollationData &data, UChar32 c, uint32_t ce32,
245                                           UErrorCode &errorCode) {
246     if(U_FAILURE(errorCode)) { return FALSE; }
247     ce32 = data.getFinalCE32(ce32);
248     ce1 = 0;
249     if(Collation::isSimpleOrLongCE32(ce32)) {
250         ce0 = Collation::ceFromCE32(ce32);
251     } else {
252         switch(Collation::tagFromCE32(ce32)) {
253         case Collation::LATIN_EXPANSION_TAG:
254             ce0 = Collation::latinCE0FromCE32(ce32);
255             ce1 = Collation::latinCE1FromCE32(ce32);
256             break;
257         case Collation::EXPANSION32_TAG: {
258             const uint32_t *ce32s = data.ce32s + Collation::indexFromCE32(ce32);
259             int32_t length = Collation::lengthFromCE32(ce32);
260             if(length <= 2) {
261                 ce0 = Collation::ceFromCE32(ce32s[0]);
262                 if(length == 2) {
263                     ce1 = Collation::ceFromCE32(ce32s[1]);
264                 }
265                 break;
266             } else {
267                 return FALSE;
268             }
269         }
270         case Collation::EXPANSION_TAG: {
271             const int64_t *ces = data.ces + Collation::indexFromCE32(ce32);
272             int32_t length = Collation::lengthFromCE32(ce32);
273             if(length <= 2) {
274                 ce0 = ces[0];
275                 if(length == 2) {
276                     ce1 = ces[1];
277                 }
278                 break;
279             } else {
280                 return FALSE;
281             }
282         }
283         // Note: We could support PREFIX_TAG (assert c>=0)
284         // by recursing on its default CE32 and checking that none of the prefixes starts
285         // with a fast Latin character.
286         // However, currently (2013) there are only the L-before-middle-dot
287         // prefix mappings in the Latin range, and those would be rejected anyway.
288         case Collation::CONTRACTION_TAG:
289             U_ASSERT(c >= 0);
290             return getCEsFromContractionCE32(data, ce32, errorCode);
291         case Collation::OFFSET_TAG:
292             U_ASSERT(c >= 0);
293             ce0 = data.getCEFromOffsetCE32(c, ce32);
294             break;
295         default:
296             return FALSE;
297         }
298     }
299     // A mapping can be completely ignorable.
300     if(ce0 == 0) { return ce1 == 0; }
301     // We do not support an ignorable ce0 unless it is completely ignorable.
302     uint32_t p0 = (uint32_t)(ce0 >> 32);
303     if(p0 == 0) { return FALSE; }
304     // We only support primaries up to the Latin script.
305     if(p0 > lastLatinPrimary) { return FALSE; }
306     // We support non-common secondary and case weights only together with short primaries.
307     uint32_t lower32_0 = (uint32_t)ce0;
308     if(p0 < firstShortPrimary) {
309         uint32_t sc0 = lower32_0 & Collation::SECONDARY_AND_CASE_MASK;
310         if(sc0 != Collation::COMMON_SECONDARY_CE) { return FALSE; }
311     }
312     // No below-common tertiary weights.
313     if((lower32_0 & Collation::ONLY_TERTIARY_MASK) < Collation::COMMON_WEIGHT16) { return FALSE; }
314     if(ce1 != 0) {
315         // Both primaries must be in the same group,
316         // or both must get short mini primaries,
317         // or a short-primary CE is followed by a secondary CE.
318         // This is so that we can test the first primary and use the same mask for both,
319         // and determine for both whether they are variable.
320         uint32_t p1 = (uint32_t)(ce1 >> 32);
321         if(p1 == 0 ? p0 < firstShortPrimary : !inSameGroup(p0, p1)) { return FALSE; }
322         uint32_t lower32_1 = (uint32_t)ce1;
323         // No tertiary CEs.
324         if((lower32_1 >> 16) == 0) { return FALSE; }
325         // We support non-common secondary and case weights
326         // only for secondary CEs or together with short primaries.
327         if(p1 != 0 && p1 < firstShortPrimary) {
328             uint32_t sc1 = lower32_1 & Collation::SECONDARY_AND_CASE_MASK;
329             if(sc1 != Collation::COMMON_SECONDARY_CE) { return FALSE; }
330         }
331         // No below-common tertiary weights.
332         if((lower32_1 & Collation::ONLY_TERTIARY_MASK) < Collation::COMMON_WEIGHT16) { return FALSE; }
333     }
334     // No quaternary weights.
335     if(((ce0 | ce1) & Collation::QUATERNARY_MASK) != 0) { return FALSE; }
336     return TRUE;
337 }
338 
339 UBool
getCEsFromContractionCE32(const CollationData & data,uint32_t ce32,UErrorCode & errorCode)340 CollationFastLatinBuilder::getCEsFromContractionCE32(const CollationData &data, uint32_t ce32,
341                                                      UErrorCode &errorCode) {
342     if(U_FAILURE(errorCode)) { return FALSE; }
343     const UChar *p = data.contexts + Collation::indexFromCE32(ce32);
344     ce32 = CollationData::readCE32(p);  // Default if no suffix match.
345     // Since the original ce32 is not a prefix mapping,
346     // the default ce32 must not be another contraction.
347     U_ASSERT(!Collation::isContractionCE32(ce32));
348     int32_t contractionIndex = contractionCEs.size();
349     if(getCEsFromCE32(data, U_SENTINEL, ce32, errorCode)) {
350         addContractionEntry(CollationFastLatin::CONTR_CHAR_MASK, ce0, ce1, errorCode);
351     } else {
352         // Bail out for c-without-contraction.
353         addContractionEntry(CollationFastLatin::CONTR_CHAR_MASK, Collation::NO_CE, 0, errorCode);
354     }
355     // Handle an encodable contraction unless the next contraction is too long
356     // and starts with the same character.
357     int32_t prevX = -1;
358     UBool addContraction = FALSE;
359     UCharsTrie::Iterator suffixes(p + 2, 0, errorCode);
360     while(suffixes.next(errorCode)) {
361         const UnicodeString &suffix = suffixes.getString();
362         int32_t x = CollationFastLatin::getCharIndex(suffix.charAt(0));
363         if(x < 0) { continue; }  // ignore anything but fast Latin text
364         if(x == prevX) {
365             if(addContraction) {
366                 // Bail out for all contractions starting with this character.
367                 addContractionEntry(x, Collation::NO_CE, 0, errorCode);
368                 addContraction = FALSE;
369             }
370             continue;
371         }
372         if(addContraction) {
373             addContractionEntry(prevX, ce0, ce1, errorCode);
374         }
375         ce32 = (uint32_t)suffixes.getValue();
376         if(suffix.length() == 1 && getCEsFromCE32(data, U_SENTINEL, ce32, errorCode)) {
377             addContraction = TRUE;
378         } else {
379             addContractionEntry(x, Collation::NO_CE, 0, errorCode);
380             addContraction = FALSE;
381         }
382         prevX = x;
383     }
384     if(addContraction) {
385         addContractionEntry(prevX, ce0, ce1, errorCode);
386     }
387     if(U_FAILURE(errorCode)) { return FALSE; }
388     // Note: There might not be any fast Latin contractions, but
389     // we need to enter contraction handling anyway so that we can bail out
390     // when there is a non-fast-Latin character following.
391     // For example: Danish &Y<<u+umlaut, when we compare Y vs. u\u0308 we need to see the
392     // following umlaut and bail out, rather than return the difference of Y vs. u.
393     ce0 = ((int64_t)Collation::NO_CE_PRIMARY << 32) | CONTRACTION_FLAG | contractionIndex;
394     ce1 = 0;
395     return TRUE;
396 }
397 
398 void
addContractionEntry(int32_t x,int64_t cce0,int64_t cce1,UErrorCode & errorCode)399 CollationFastLatinBuilder::addContractionEntry(int32_t x, int64_t cce0, int64_t cce1,
400                                                UErrorCode &errorCode) {
401     contractionCEs.addElement(x, errorCode);
402     contractionCEs.addElement(cce0, errorCode);
403     contractionCEs.addElement(cce1, errorCode);
404     addUniqueCE(cce0, errorCode);
405     addUniqueCE(cce1, errorCode);
406 }
407 
408 void
addUniqueCE(int64_t ce,UErrorCode & errorCode)409 CollationFastLatinBuilder::addUniqueCE(int64_t ce, UErrorCode &errorCode) {
410     if(U_FAILURE(errorCode)) { return; }
411     if(ce == 0 || (uint32_t)(ce >> 32) == Collation::NO_CE_PRIMARY) { return; }
412     ce &= ~(int64_t)Collation::CASE_MASK;  // blank out case bits
413     int32_t i = binarySearch(uniqueCEs.getBuffer(), uniqueCEs.size(), ce);
414     if(i < 0) {
415         uniqueCEs.insertElementAt(ce, ~i, errorCode);
416     }
417 }
418 
419 uint32_t
getMiniCE(int64_t ce) const420 CollationFastLatinBuilder::getMiniCE(int64_t ce) const {
421     ce &= ~(int64_t)Collation::CASE_MASK;  // blank out case bits
422     int32_t index = binarySearch(uniqueCEs.getBuffer(), uniqueCEs.size(), ce);
423     U_ASSERT(index >= 0);
424     return miniCEs[index];
425 }
426 
427 UBool
encodeUniqueCEs(UErrorCode & errorCode)428 CollationFastLatinBuilder::encodeUniqueCEs(UErrorCode &errorCode) {
429     if(U_FAILURE(errorCode)) { return FALSE; }
430     uprv_free(miniCEs);
431     miniCEs = (uint16_t *)uprv_malloc(uniqueCEs.size() * 2);
432     if(miniCEs == NULL) {
433         errorCode = U_MEMORY_ALLOCATION_ERROR;
434         return FALSE;
435     }
436     int32_t group = 0;
437     uint32_t lastGroupPrimary = lastSpecialPrimaries[group];
438     // The lowest unique CE must be at least a secondary CE.
439     U_ASSERT(((uint32_t)uniqueCEs.elementAti(0) >> 16) != 0);
440     uint32_t prevPrimary = 0;
441     uint32_t prevSecondary = 0;
442     uint32_t pri = 0;
443     uint32_t sec = 0;
444     uint32_t ter = CollationFastLatin::COMMON_TER;
445     for(int32_t i = 0; i < uniqueCEs.size(); ++i) {
446         int64_t ce = uniqueCEs.elementAti(i);
447         // Note: At least one of the p/s/t weights changes from one unique CE to the next.
448         // (uniqueCEs does not store case bits.)
449         uint32_t p = (uint32_t)(ce >> 32);
450         if(p != prevPrimary) {
451             while(p > lastGroupPrimary) {
452                 U_ASSERT(pri <= CollationFastLatin::MAX_LONG);
453                 // Set the group's header entry to the
454                 // last "long primary" in or before the group.
455                 result.setCharAt(1 + group, (UChar)pri);
456                 if(++group < NUM_SPECIAL_GROUPS) {
457                     lastGroupPrimary = lastSpecialPrimaries[group];
458                 } else {
459                     lastGroupPrimary = 0xffffffff;
460                     break;
461                 }
462             }
463             if(p < firstShortPrimary) {
464                 if(pri == 0) {
465                     pri = CollationFastLatin::MIN_LONG;
466                 } else if(pri < CollationFastLatin::MAX_LONG) {
467                     pri += CollationFastLatin::LONG_INC;
468                 } else {
469 #if DEBUG_COLLATION_FAST_LATIN_BUILDER
470                     printf("long-primary overflow for %08x\n", p);
471 #endif
472                     miniCEs[i] = CollationFastLatin::BAIL_OUT;
473                     continue;
474                 }
475             } else {
476                 if(pri < CollationFastLatin::MIN_SHORT) {
477                     pri = CollationFastLatin::MIN_SHORT;
478                 } else if(pri < (CollationFastLatin::MAX_SHORT - CollationFastLatin::SHORT_INC)) {
479                     // Reserve the highest primary weight for U+FFFF.
480                     pri += CollationFastLatin::SHORT_INC;
481                 } else {
482 #if DEBUG_COLLATION_FAST_LATIN_BUILDER
483                     printf("short-primary overflow for %08x\n", p);
484 #endif
485                     shortPrimaryOverflow = TRUE;
486                     miniCEs[i] = CollationFastLatin::BAIL_OUT;
487                     continue;
488                 }
489             }
490             prevPrimary = p;
491             prevSecondary = Collation::COMMON_WEIGHT16;
492             sec = CollationFastLatin::COMMON_SEC;
493             ter = CollationFastLatin::COMMON_TER;
494         }
495         uint32_t lower32 = (uint32_t)ce;
496         uint32_t s = lower32 >> 16;
497         if(s != prevSecondary) {
498             if(pri == 0) {
499                 if(sec == 0) {
500                     sec = CollationFastLatin::MIN_SEC_HIGH;
501                 } else if(sec < CollationFastLatin::MAX_SEC_HIGH) {
502                     sec += CollationFastLatin::SEC_INC;
503                 } else {
504                     miniCEs[i] = CollationFastLatin::BAIL_OUT;
505                     continue;
506                 }
507                 prevSecondary = s;
508                 ter = CollationFastLatin::COMMON_TER;
509             } else if(s < Collation::COMMON_WEIGHT16) {
510                 if(sec == CollationFastLatin::COMMON_SEC) {
511                     sec = CollationFastLatin::MIN_SEC_BEFORE;
512                 } else if(sec < CollationFastLatin::MAX_SEC_BEFORE) {
513                     sec += CollationFastLatin::SEC_INC;
514                 } else {
515                     miniCEs[i] = CollationFastLatin::BAIL_OUT;
516                     continue;
517                 }
518             } else if(s == Collation::COMMON_WEIGHT16) {
519                 sec = CollationFastLatin::COMMON_SEC;
520             } else {
521                 if(sec < CollationFastLatin::MIN_SEC_AFTER) {
522                     sec = CollationFastLatin::MIN_SEC_AFTER;
523                 } else if(sec < CollationFastLatin::MAX_SEC_AFTER) {
524                     sec += CollationFastLatin::SEC_INC;
525                 } else {
526                     miniCEs[i] = CollationFastLatin::BAIL_OUT;
527                     continue;
528                 }
529             }
530             prevSecondary = s;
531             ter = CollationFastLatin::COMMON_TER;
532         }
533         U_ASSERT((lower32 & Collation::CASE_MASK) == 0);  // blanked out in uniqueCEs
534         uint32_t t = lower32 & Collation::ONLY_TERTIARY_MASK;
535         if(t > Collation::COMMON_WEIGHT16) {
536             if(ter < CollationFastLatin::MAX_TER_AFTER) {
537                 ++ter;
538             } else {
539                 miniCEs[i] = CollationFastLatin::BAIL_OUT;
540                 continue;
541             }
542         }
543         if(CollationFastLatin::MIN_LONG <= pri && pri <= CollationFastLatin::MAX_LONG) {
544             U_ASSERT(sec == CollationFastLatin::COMMON_SEC);
545             miniCEs[i] = (uint16_t)(pri | ter);
546         } else {
547             miniCEs[i] = (uint16_t)(pri | sec | ter);
548         }
549     }
550 #if DEBUG_COLLATION_FAST_LATIN_BUILDER
551     printf("last mini primary: %04x\n", pri);
552 #endif
553 #if DEBUG_COLLATION_FAST_LATIN_BUILDER >= 2
554     for(int32_t i = 0; i < uniqueCEs.size(); ++i) {
555         int64_t ce = uniqueCEs.elementAti(i);
556         printf("unique CE 0x%016lx -> 0x%04x\n", ce, miniCEs[i]);
557     }
558 #endif
559     return U_SUCCESS(errorCode);
560 }
561 
562 UBool
encodeCharCEs(UErrorCode & errorCode)563 CollationFastLatinBuilder::encodeCharCEs(UErrorCode &errorCode) {
564     if(U_FAILURE(errorCode)) { return FALSE; }
565     int32_t miniCEsStart = result.length();
566     for(int32_t i = 0; i < CollationFastLatin::NUM_FAST_CHARS; ++i) {
567         result.append(0);  // initialize to completely ignorable
568     }
569     int32_t indexBase = result.length();
570     for(int32_t i = 0; i < CollationFastLatin::NUM_FAST_CHARS; ++i) {
571         int64_t ce = charCEs[i][0];
572         if(isContractionCharCE(ce)) { continue; }  // defer contraction
573         uint32_t miniCE = encodeTwoCEs(ce, charCEs[i][1]);
574         if(miniCE > 0xffff) {
575             // Note: There is a chance that this new expansion is the same as a previous one,
576             // and if so, then we could reuse the other expansion.
577             // However, that seems unlikely.
578             int32_t expansionIndex = result.length() - indexBase;
579             if(expansionIndex > (int32_t)CollationFastLatin::INDEX_MASK) {
580                 miniCE = CollationFastLatin::BAIL_OUT;
581             } else {
582                 result.append((UChar)(miniCE >> 16)).append((UChar)miniCE);
583                 miniCE = CollationFastLatin::EXPANSION | expansionIndex;
584             }
585         }
586         result.setCharAt(miniCEsStart + i, (UChar)miniCE);
587     }
588     return U_SUCCESS(errorCode);
589 }
590 
591 UBool
encodeContractions(UErrorCode & errorCode)592 CollationFastLatinBuilder::encodeContractions(UErrorCode &errorCode) {
593     // We encode all contraction lists so that the first word of a list
594     // terminates the previous list, and we only need one additional terminator at the end.
595     if(U_FAILURE(errorCode)) { return FALSE; }
596     int32_t indexBase = headerLength + CollationFastLatin::NUM_FAST_CHARS;
597     int32_t firstContractionIndex = result.length();
598     for(int32_t i = 0; i < CollationFastLatin::NUM_FAST_CHARS; ++i) {
599         int64_t ce = charCEs[i][0];
600         if(!isContractionCharCE(ce)) { continue; }
601         int32_t contractionIndex = result.length() - indexBase;
602         if(contractionIndex > (int32_t)CollationFastLatin::INDEX_MASK) {
603             result.setCharAt(headerLength + i, CollationFastLatin::BAIL_OUT);
604             continue;
605         }
606         UBool firstTriple = TRUE;
607         for(int32_t index = (int32_t)ce & 0x7fffffff;; index += 3) {
608             int32_t x = contractionCEs.elementAti(index);
609             if((uint32_t)x == CollationFastLatin::CONTR_CHAR_MASK && !firstTriple) { break; }
610             int64_t cce0 = contractionCEs.elementAti(index + 1);
611             int64_t cce1 = contractionCEs.elementAti(index + 2);
612             uint32_t miniCE = encodeTwoCEs(cce0, cce1);
613             if(miniCE == CollationFastLatin::BAIL_OUT) {
614                 result.append((UChar)(x | (1 << CollationFastLatin::CONTR_LENGTH_SHIFT)));
615             } else if(miniCE <= 0xffff) {
616                 result.append((UChar)(x | (2 << CollationFastLatin::CONTR_LENGTH_SHIFT)));
617                 result.append((UChar)miniCE);
618             } else {
619                 result.append((UChar)(x | (3 << CollationFastLatin::CONTR_LENGTH_SHIFT)));
620                 result.append((UChar)(miniCE >> 16)).append((UChar)miniCE);
621             }
622             firstTriple = FALSE;
623         }
624         // Note: There is a chance that this new contraction list is the same as a previous one,
625         // and if so, then we could truncate the result and reuse the other list.
626         // However, that seems unlikely.
627         result.setCharAt(headerLength + i,
628                          (UChar)(CollationFastLatin::CONTRACTION | contractionIndex));
629     }
630     if(result.length() > firstContractionIndex) {
631         // Terminate the last contraction list.
632         result.append((UChar)CollationFastLatin::CONTR_CHAR_MASK);
633     }
634     if(result.isBogus()) {
635         errorCode = U_MEMORY_ALLOCATION_ERROR;
636         return FALSE;
637     }
638 #if DEBUG_COLLATION_FAST_LATIN_BUILDER
639     printf("** fast Latin %d * 2 = %d bytes\n", result.length(), result.length() * 2);
640     puts("   header & below-digit groups map");
641     int32_t i = 0;
642     for(; i < headerLength; ++i) {
643         printf(" %04x", result[i]);
644     }
645     printf("\n   char mini CEs");
646     U_ASSERT(CollationFastLatin::NUM_FAST_CHARS % 16 == 0);
647     for(; i < indexBase; i += 16) {
648         UChar32 c = i - headerLength;
649         if(c >= CollationFastLatin::LATIN_LIMIT) {
650             c = CollationFastLatin::PUNCT_START + c - CollationFastLatin::LATIN_LIMIT;
651         }
652         printf("\n %04x:", c);
653         for(int32_t j = 0; j < 16; ++j) {
654             printf(" %04x", result[i + j]);
655         }
656     }
657     printf("\n   expansions & contractions");
658     for(; i < result.length(); ++i) {
659         if((i - indexBase) % 16 == 0) { puts(""); }
660         printf(" %04x", result[i]);
661     }
662     puts("");
663 #endif
664     return TRUE;
665 }
666 
667 uint32_t
encodeTwoCEs(int64_t first,int64_t second) const668 CollationFastLatinBuilder::encodeTwoCEs(int64_t first, int64_t second) const {
669     if(first == 0) {
670         return 0;  // completely ignorable
671     }
672     if(first == Collation::NO_CE) {
673         return CollationFastLatin::BAIL_OUT;
674     }
675     U_ASSERT((uint32_t)(first >> 32) != Collation::NO_CE_PRIMARY);
676 
677     uint32_t miniCE = getMiniCE(first);
678     if(miniCE == CollationFastLatin::BAIL_OUT) { return miniCE; }
679     if(miniCE >= CollationFastLatin::MIN_SHORT) {
680         // Extract & copy the case bits.
681         // Shift them from normal CE bits 15..14 to mini CE bits 4..3.
682         uint32_t c = (((uint32_t)first & Collation::CASE_MASK) >> (14 - 3));
683         // Only in mini CEs: Ignorable case bits = 0, lowercase = 1.
684         c += CollationFastLatin::LOWER_CASE;
685         miniCE |= c;
686     }
687     if(second == 0) { return miniCE; }
688 
689     uint32_t miniCE1 = getMiniCE(second);
690     if(miniCE1 == CollationFastLatin::BAIL_OUT) { return miniCE1; }
691 
692     uint32_t case1 = (uint32_t)second & Collation::CASE_MASK;
693     if(miniCE >= CollationFastLatin::MIN_SHORT &&
694             (miniCE & CollationFastLatin::SECONDARY_MASK) == CollationFastLatin::COMMON_SEC) {
695         // Try to combine the two mini CEs into one.
696         uint32_t sec1 = miniCE1 & CollationFastLatin::SECONDARY_MASK;
697         uint32_t ter1 = miniCE1 & CollationFastLatin::TERTIARY_MASK;
698         if(sec1 >= CollationFastLatin::MIN_SEC_HIGH && case1 == 0 &&
699                 ter1 == CollationFastLatin::COMMON_TER) {
700             // sec1>=sec_high implies pri1==0.
701             return (miniCE & ~CollationFastLatin::SECONDARY_MASK) | sec1;
702         }
703     }
704 
705     if(miniCE1 <= CollationFastLatin::SECONDARY_MASK || CollationFastLatin::MIN_SHORT <= miniCE1) {
706         // Secondary CE, or a CE with a short primary, copy the case bits.
707         case1 = (case1 >> (14 - 3)) + CollationFastLatin::LOWER_CASE;
708         miniCE1 |= case1;
709     }
710     return (miniCE << 16) | miniCE1;
711 }
712 
713 U_NAMESPACE_END
714 
715 #endif  // !UCONFIG_NO_COLLATION
716