Update ICU to 54.1 step 1

source/i18n/collationfastlatinbuilder.cpp

+/*
+*******************************************************************************
+* Copyright (C) 2013-2014, International Business Machines
+* Corporation and others.  All Rights Reserved.
+*******************************************************************************
+* collationfastlatinbuilder.cpp
+*
+* created on: 2013aug09
+* created by: Markus W. Scherer
+*/
+
+#define DEBUG_COLLATION_FAST_LATIN_BUILDER 0  // 0 or 1 or 2
+#if DEBUG_COLLATION_FAST_LATIN_BUILDER
+#include <stdio.h>
+#include <string>
+#endif
+
+#include "unicode/utypes.h"
+
+#if !UCONFIG_NO_COLLATION
+
+#include "unicode/ucol.h"
+#include "unicode/ucharstrie.h"
+#include "unicode/unistr.h"
+#include "unicode/uobject.h"
+#include "unicode/uscript.h"
+#include "cmemory.h"
+#include "collation.h"
+#include "collationdata.h"
+#include "collationfastlatin.h"
+#include "collationfastlatinbuilder.h"
+#include "uassert.h"
+#include "uvectr64.h"
+
+U_NAMESPACE_BEGIN
+
+struct CollationData;
+
+namespace {
+
+/**
+ * Compare two signed int64_t values as if they were unsigned.
+ */
+int32_t
+compareInt64AsUnsigned(int64_t a, int64_t b) {
+    if((uint64_t)a < (uint64_t)b) {
+        return -1;
+    } else if((uint64_t)a > (uint64_t)b) {
+        return 1;
+    } else {
+        return 0;
+    }
+}
+
+// TODO: Merge this with the near-identical version in collationbasedatabuilder.cpp
+/**
+ * Like Java Collections.binarySearch(List, String, Comparator).
+ *
+ * @return the index>=0 where the item was found,
+ *         or the index<0 for inserting the string at ~index in sorted order
+ */
+int32_t
+binarySearch(const int64_t list[], int32_t limit, int64_t ce) {
+    if (limit == 0) { return ~0; }
+    int32_t start = 0;
+    for (;;) {
+        int32_t i = (start + limit) / 2;
+        int32_t cmp = compareInt64AsUnsigned(ce, list[i]);
+        if (cmp == 0) {
+            return i;
+        } else if (cmp < 0) {
+            if (i == start) {
+                return ~start;  // insert ce before i
+            }
+            limit = i;
+        } else {
+            if (i == start) {
+                return ~(start + 1);  // insert ce after i
+            }
+            start = i;
+        }
+    }
+}
+
+}  // namespace
+
+CollationFastLatinBuilder::CollationFastLatinBuilder(UErrorCode &errorCode)
+        : ce0(0), ce1(0),
+          contractionCEs(errorCode), uniqueCEs(errorCode),
+          miniCEs(NULL),
+          firstDigitPrimary(0), firstLatinPrimary(0), lastLatinPrimary(0),
+          firstShortPrimary(0), shortPrimaryOverflow(FALSE),
+          headerLength(0) {
+}
+
+CollationFastLatinBuilder::~CollationFastLatinBuilder() {
+    uprv_free(miniCEs);
+}
+
+UBool
+CollationFastLatinBuilder::forData(const CollationData &data, UErrorCode &errorCode) {
+    if(U_FAILURE(errorCode)) { return FALSE; }
+    if(!result.isEmpty()) {  // This builder is not reusable.
+        errorCode = U_INVALID_STATE_ERROR;
+        return FALSE;
+    }
+    if(!loadGroups(data, errorCode)) { return FALSE; }
+
+    // Fast handling of digits.
+    firstShortPrimary = firstDigitPrimary;
+    getCEs(data, errorCode);
+    if(!encodeUniqueCEs(errorCode)) { return FALSE; }
+    if(shortPrimaryOverflow) {
+        // Give digits long mini primaries,
+        // so that there are more short primaries for letters.
+        firstShortPrimary = firstLatinPrimary;
+        resetCEs();
+        getCEs(data, errorCode);
+        if(!encodeUniqueCEs(errorCode)) { return FALSE; }
+    }
+    // Note: If we still have a short-primary overflow but not a long-primary overflow,
+    // then we could calculate how many more long primaries would fit,
+    // and set the firstShortPrimary to that many after the current firstShortPrimary,
+    // and try again.
+    // However, this might only benefit the en_US_POSIX tailoring,
+    // and it is simpler to suppress building fast Latin data for it in genrb,
+    // or by returning FALSE here if shortPrimaryOverflow.
+
+    UBool ok = !shortPrimaryOverflow &&
+            encodeCharCEs(errorCode) && encodeContractions(errorCode);
+    contractionCEs.removeAllElements();  // might reduce heap memory usage
+    uniqueCEs.removeAllElements();
+    return ok;
+}
+
+UBool
+CollationFastLatinBuilder::loadGroups(const CollationData &data, UErrorCode &errorCode) {
+    if(U_FAILURE(errorCode)) { return FALSE; }
+    result.append(0);  // reserved for version & headerLength
+    // The first few reordering groups should be special groups
+    // (space, punct, ..., digit) followed by Latn, then Grek and other scripts.
+    for(int32_t i = 0;;) {
+        if(i >= data.scriptsLength) {
+            // no Latn script
+            errorCode = U_INTERNAL_PROGRAM_ERROR;
+            return FALSE;
+        }
+        uint32_t head = data.scripts[i];
+        uint32_t lastByte = head & 0xff;  // last primary byte in the group
+        int32_t group = data.scripts[i + 2];
+        if(group == UCOL_REORDER_CODE_DIGIT) {
+            firstDigitPrimary = (head & 0xff00) << 16;
+            headerLength = result.length();
+            uint32_t r0 = (CollationFastLatin::VERSION << 8) | headerLength;
+            result.setCharAt(0, (UChar)r0);
+        } else if(group == USCRIPT_LATIN) {
+            if(firstDigitPrimary == 0) {
+                // no digit group
+                errorCode = U_INTERNAL_PROGRAM_ERROR;
+                return FALSE;
+            }
+            firstLatinPrimary = (head & 0xff00) << 16;
+            lastLatinPrimary = (lastByte << 24) | 0xffffff;
+            break;
+        } else if(firstDigitPrimary == 0) {
+            // a group below digits
+            if(lastByte > 0x7f) {
+                // We only use 7 bits for the last byte of a below-digits group.
+                // This does not warrant an errorCode, but we do not build a fast Latin table.
+                return FALSE;
+            }
+            result.append((UChar)lastByte);
+        }
+        i = i + 2 + data.scripts[i + 1];
+    }
+    return TRUE;
+}
+
+UBool
+CollationFastLatinBuilder::inSameGroup(uint32_t p, uint32_t q) const {
+    // Both or neither need to be encoded as short primaries,
+    // so that we can test only one and use the same bit mask.
+    if(p >= firstShortPrimary) {
+        return q >= firstShortPrimary;
+    } else if(q >= firstShortPrimary) {
+        return FALSE;
+    }
+    // Both or neither must be potentially-variable,
+    // so that we can test only one and determine if both are variable.
+    if(p >= firstDigitPrimary) {
+        return q >= firstDigitPrimary;
+    } else if(q >= firstDigitPrimary) {
+        return FALSE;
+    }
+    // Both will be encoded with long mini primaries.
+    // They must be in the same special reordering group,
+    // so that we can test only one and determine if both are variable.
+    p >>= 24;  // first primary byte
+    q >>= 24;
+    U_ASSERT(p != 0 && q != 0);
+    U_ASSERT(p <= result[headerLength - 1]);  // the loop will terminate
+    for(int32_t i = 1;; ++i) {
+        uint32_t lastByte = result[i];
+        if(p <= lastByte) {
+            return q <= lastByte;
+        } else if(q <= lastByte) {
+            return FALSE;
+        }
+    }
+}
+
+void
+CollationFastLatinBuilder::resetCEs() {
+    contractionCEs.removeAllElements();
+    uniqueCEs.removeAllElements();
+    shortPrimaryOverflow = FALSE;
+    result.truncate(headerLength);
+}
+
+void
+CollationFastLatinBuilder::getCEs(const CollationData &data, UErrorCode &errorCode) {
+    if(U_FAILURE(errorCode)) { return; }
+    int32_t i = 0;
+    for(UChar c = 0;; ++i, ++c) {
+        if(c == CollationFastLatin::LATIN_LIMIT) {
+            c = CollationFastLatin::PUNCT_START;
+        } else if(c == CollationFastLatin::PUNCT_LIMIT) {
+            break;
+        }
+        const CollationData *d;
+        uint32_t ce32 = data.getCE32(c);
+        if(ce32 == Collation::FALLBACK_CE32) {
+            d = data.base;
+            ce32 = d->getCE32(c);
+        } else {
+            d = &data;
+        }
+        if(getCEsFromCE32(*d, c, ce32, errorCode)) {
+            charCEs[i][0] = ce0;
+            charCEs[i][1] = ce1;
+            addUniqueCE(ce0, errorCode);
+            addUniqueCE(ce1, errorCode);
+        } else {
+            // bail out for c
+            charCEs[i][0] = ce0 = Collation::NO_CE;
+            charCEs[i][1] = ce1 = 0;
+        }
+        if(c == 0 && !isContractionCharCE(ce0)) {
+            // Always map U+0000 to a contraction.
+            // Write a contraction list with only a default value if there is no real contraction.
+            U_ASSERT(contractionCEs.isEmpty());
+            addContractionEntry(CollationFastLatin::CONTR_CHAR_MASK, ce0, ce1, errorCode);
+            charCEs[0][0] = ((int64_t)Collation::NO_CE_PRIMARY << 32) | CONTRACTION_FLAG;
+            charCEs[0][1] = 0;
+        }
+    }
+    // Terminate the last contraction list.
+    contractionCEs.addElement(CollationFastLatin::CONTR_CHAR_MASK, errorCode);
+}
+
+UBool
+CollationFastLatinBuilder::getCEsFromCE32(const CollationData &data, UChar32 c, uint32_t ce32,
+                                          UErrorCode &errorCode) {
+    if(U_FAILURE(errorCode)) { return FALSE; }
+    ce32 = data.getFinalCE32(ce32);
+    ce1 = 0;
+    if(Collation::isSimpleOrLongCE32(ce32)) {
+        ce0 = Collation::ceFromCE32(ce32);
+    } else {
+        switch(Collation::tagFromCE32(ce32)) {
+        case Collation::LATIN_EXPANSION_TAG:
+            ce0 = Collation::latinCE0FromCE32(ce32);
+            ce1 = Collation::latinCE1FromCE32(ce32);
+            break;
+        case Collation::EXPANSION32_TAG: {
+            const uint32_t *ce32s = data.ce32s + Collation::indexFromCE32(ce32);
+            int32_t length = Collation::lengthFromCE32(ce32);
+            if(length <= 2) {
+                ce0 = Collation::ceFromCE32(ce32s[0]);
+                if(length == 2) {
+                    ce1 = Collation::ceFromCE32(ce32s[1]);
+                }
+                break;
+            } else {
+                return FALSE;
+            }
+        }
+        case Collation::EXPANSION_TAG: {
+            const int64_t *ces = data.ces + Collation::indexFromCE32(ce32);
+            int32_t length = Collation::lengthFromCE32(ce32);
+            if(length <= 2) {
+                ce0 = ces[0];
+                if(length == 2) {
+                    ce1 = ces[1];
+                }
+                break;
+            } else {
+                return FALSE;
+            }
+        }
+        // Note: We could support PREFIX_TAG (assert c>=0)
+        // by recursing on its default CE32 and checking that none of the prefixes starts
+        // with a fast Latin character.
+        // However, currently (2013) there are only the L-before-middle-dot
+        // prefix mappings in the Latin range, and those would be rejected anyway.
+        case Collation::CONTRACTION_TAG:
+            U_ASSERT(c >= 0);
+            return getCEsFromContractionCE32(data, ce32, errorCode);
+        case Collation::OFFSET_TAG:
+            U_ASSERT(c >= 0);
+            ce0 = data.getCEFromOffsetCE32(c, ce32);
+            break;
+        default:
+            return FALSE;
+        }
+    }
+    // A mapping can be completely ignorable.
+    if(ce0 == 0) { return ce1 == 0; }
+    // We do not support an ignorable ce0 unless it is completely ignorable.
+    uint32_t p0 = (uint32_t)(ce0 >> 32);
+    if(p0 == 0) { return FALSE; }
+    // We only support primaries up to the Latin script.
+    if(p0 > lastLatinPrimary) { return FALSE; }
+    // We support non-common secondary and case weights only together with short primaries.
+    uint32_t lower32_0 = (uint32_t)ce0;
+    if(p0 < firstShortPrimary) {
+        uint32_t sc0 = lower32_0 & Collation::SECONDARY_AND_CASE_MASK;
+        if(sc0 != Collation::COMMON_SECONDARY_CE) { return FALSE; }
+    }
+    // No below-common tertiary weights.
+    if((lower32_0 & Collation::ONLY_TERTIARY_MASK) < Collation::COMMON_WEIGHT16) { return FALSE; }
+    if(ce1 != 0) {
+        // Both primaries must be in the same group,
+        // or both must get short mini primaries,
+        // or a short-primary CE is followed by a secondary CE.
+        // This is so that we can test the first primary and use the same mask for both,
+        // and determine for both whether they are variable.
+        uint32_t p1 = (uint32_t)(ce1 >> 32);
+        if(p1 == 0 ? p0 < firstShortPrimary : !inSameGroup(p0, p1)) { return FALSE; }
+        uint32_t lower32_1 = (uint32_t)ce1;
+        // No tertiary CEs.
+        if((lower32_1 >> 16) == 0) { return FALSE; }
+        // We support non-common secondary and case weights
+        // only for secondary CEs or together with short primaries.
+        if(p1 != 0 && p1 < firstShortPrimary) {
+            uint32_t sc1 = lower32_1 & Collation::SECONDARY_AND_CASE_MASK;
+            if(sc1 != Collation::COMMON_SECONDARY_CE) { return FALSE; }
+        }
+        // No below-common tertiary weights.
+        if((lower32_1 & Collation::ONLY_TERTIARY_MASK) < Collation::COMMON_WEIGHT16) { return FALSE; }
+    }
+    // No quaternary weights.
+    if(((ce0 | ce1) & Collation::QUATERNARY_MASK) != 0) { return FALSE; }
+    return TRUE;
+}
+
+UBool
+CollationFastLatinBuilder::getCEsFromContractionCE32(const CollationData &data, uint32_t ce32,
+                                                     UErrorCode &errorCode) {
+    if(U_FAILURE(errorCode)) { return FALSE; }
+    const UChar *p = data.contexts + Collation::indexFromCE32(ce32);
+    ce32 = CollationData::readCE32(p);  // Default if no suffix match.
+    // Since the original ce32 is not a prefix mapping,
+    // the default ce32 must not be another contraction.
+    U_ASSERT(!Collation::isContractionCE32(ce32));
+    int32_t contractionIndex = contractionCEs.size();
+    if(getCEsFromCE32(data, U_SENTINEL, ce32, errorCode)) {
+        addContractionEntry(CollationFastLatin::CONTR_CHAR_MASK, ce0, ce1, errorCode);
+    } else {
+        // Bail out for c-without-contraction.
+        addContractionEntry(CollationFastLatin::CONTR_CHAR_MASK, Collation::NO_CE, 0, errorCode);
+    }
+    // Handle an encodable contraction unless the next contraction is too long
+    // and starts with the same character.
+    int32_t prevX = -1;
+    UBool addContraction = FALSE;
+    UCharsTrie::Iterator suffixes(p + 2, 0, errorCode);
+    while(suffixes.next(errorCode)) {
+        const UnicodeString &suffix = suffixes.getString();
+        int32_t x = CollationFastLatin::getCharIndex(suffix.charAt(0));
+        if(x < 0) { continue; }  // ignore anything but fast Latin text
+        if(x == prevX) {
+            if(addContraction) {
+                // Bail out for all contractions starting with this character.
+                addContractionEntry(x, Collation::NO_CE, 0, errorCode);
+                addContraction = FALSE;
+            }
+            continue;
+        }
+        if(addContraction) {
+            addContractionEntry(prevX, ce0, ce1, errorCode);
+        }
+        ce32 = (uint32_t)suffixes.getValue();
+        if(suffix.length() == 1 && getCEsFromCE32(data, U_SENTINEL, ce32, errorCode)) {
+            addContraction = TRUE;
+        } else {
+            addContractionEntry(x, Collation::NO_CE, 0, errorCode);
+            addContraction = FALSE;
+        }
+        prevX = x;
+    }
+    if(addContraction) {
+        addContractionEntry(prevX, ce0, ce1, errorCode);
+    }
+    if(U_FAILURE(errorCode)) { return FALSE; }
+    // Note: There might not be any fast Latin contractions, but
+    // we need to enter contraction handling anyway so that we can bail out
+    // when there is a non-fast-Latin character following.
+    // For example: Danish &Y<<u+umlaut, when we compare Y vs. u\u0308 we need to see the
+    // following umlaut and bail out, rather than return the difference of Y vs. u.
+    ce0 = ((int64_t)Collation::NO_CE_PRIMARY << 32) | CONTRACTION_FLAG | contractionIndex;
+    ce1 = 0;
+    return TRUE;
+}
+
+void
+CollationFastLatinBuilder::addContractionEntry(int32_t x, int64_t cce0, int64_t cce1,
+                                               UErrorCode &errorCode) {
+    contractionCEs.addElement(x, errorCode);
+    contractionCEs.addElement(cce0, errorCode);
+    contractionCEs.addElement(cce1, errorCode);
+    addUniqueCE(cce0, errorCode);
+    addUniqueCE(cce1, errorCode);
+}
+
+void
+CollationFastLatinBuilder::addUniqueCE(int64_t ce, UErrorCode &errorCode) {
+    if(U_FAILURE(errorCode)) { return; }
+    if(ce == 0 || (uint32_t)(ce >> 32) == Collation::NO_CE_PRIMARY) { return; }
+    ce &= ~(int64_t)Collation::CASE_MASK;  // blank out case bits
+    int32_t i = binarySearch(uniqueCEs.getBuffer(), uniqueCEs.size(), ce);
+    if(i < 0) {
+        uniqueCEs.insertElementAt(ce, ~i, errorCode);
+    }
+}
+
+uint32_t
+CollationFastLatinBuilder::getMiniCE(int64_t ce) const {
+    ce &= ~(int64_t)Collation::CASE_MASK;  // blank out case bits
+    int32_t index = binarySearch(uniqueCEs.getBuffer(), uniqueCEs.size(), ce);
+    U_ASSERT(index >= 0);
+    return miniCEs[index];
+}
+
+UBool
+CollationFastLatinBuilder::encodeUniqueCEs(UErrorCode &errorCode) {
+    if(U_FAILURE(errorCode)) { return FALSE; }
+    uprv_free(miniCEs);
+    miniCEs = (uint16_t *)uprv_malloc(uniqueCEs.size() * 2);
+    if(miniCEs == NULL) {
+        errorCode = U_MEMORY_ALLOCATION_ERROR;
+        return FALSE;
+    }
+    int32_t group = 1;
+    uint32_t lastGroupByte = result[group];
+    // The lowest unique CE must be at least a secondary CE.
+    U_ASSERT(((uint32_t)uniqueCEs.elementAti(0) >> 16) != 0);
+    uint32_t prevPrimary = 0;
+    uint32_t prevSecondary = 0;
+    uint32_t pri = 0;
+    uint32_t sec = 0;
+    uint32_t ter = CollationFastLatin::COMMON_TER;
+    for(int32_t i = 0; i < uniqueCEs.size(); ++i) {
+        int64_t ce = uniqueCEs.elementAti(i);
+        // Note: At least one of the p/s/t weights changes from one unique CE to the next.
+        // (uniqueCEs does not store case bits.)
+        uint32_t p = (uint32_t)(ce >> 32);
+        if(p != prevPrimary) {
+            uint32_t p1 = p >> 24;
+            while(p1 > lastGroupByte) {
+                U_ASSERT(pri <= CollationFastLatin::MAX_LONG);
+                // Add the last "long primary" in or before the group
+                // into the upper 9 bits of the group entry.
+                result.setCharAt(group, (UChar)((pri << 4) | lastGroupByte));
+                if(++group < headerLength) {  // group is 1-based
+                    lastGroupByte = result[group];
+                } else {
+                    lastGroupByte = 0xff;
+                    break;
+                }
+            }
+            if(p < firstShortPrimary) {
+                if(pri == 0) {
+                    pri = CollationFastLatin::MIN_LONG;
+                } else if(pri < CollationFastLatin::MAX_LONG) {
+                    pri += CollationFastLatin::LONG_INC;
+                } else {
+#if DEBUG_COLLATION_FAST_LATIN_BUILDER
+                    printf("long-primary overflow for %08x\n", p);
+#endif
+                    miniCEs[i] = CollationFastLatin::BAIL_OUT;
+                    continue;
+                }
+            } else {
+                if(pri < CollationFastLatin::MIN_SHORT) {
+                    pri = CollationFastLatin::MIN_SHORT;
+                } else if(pri < (CollationFastLatin::MAX_SHORT - CollationFastLatin::SHORT_INC)) {
+                    // Reserve the highest primary weight for U+FFFF.
+                    pri += CollationFastLatin::SHORT_INC;
+                } else {
+#if DEBUG_COLLATION_FAST_LATIN_BUILDER
+                    printf("short-primary overflow for %08x\n", p);
+#endif
+                    shortPrimaryOverflow = TRUE;
+                    miniCEs[i] = CollationFastLatin::BAIL_OUT;
+                    continue;
+                }
+            }
+            prevPrimary = p;
+            prevSecondary = Collation::COMMON_WEIGHT16;
+            sec = CollationFastLatin::COMMON_SEC;
+            ter = CollationFastLatin::COMMON_TER;
+        }
+        uint32_t lower32 = (uint32_t)ce;
+        uint32_t s = lower32 >> 16;
+        if(s != prevSecondary) {
+            if(pri == 0) {
+                if(sec == 0) {
+                    sec = CollationFastLatin::MIN_SEC_HIGH;
+                } else if(sec < CollationFastLatin::MAX_SEC_HIGH) {
+                    sec += CollationFastLatin::SEC_INC;
+                } else {
+                    miniCEs[i] = CollationFastLatin::BAIL_OUT;
+                    continue;
+                }
+                prevSecondary = s;
+                ter = CollationFastLatin::COMMON_TER;
+            } else if(s < Collation::COMMON_WEIGHT16) {
+                if(sec == CollationFastLatin::COMMON_SEC) {
+                    sec = CollationFastLatin::MIN_SEC_BEFORE;
+                } else if(sec < CollationFastLatin::MAX_SEC_BEFORE) {
+                    sec += CollationFastLatin::SEC_INC;
+                } else {
+                    miniCEs[i] = CollationFastLatin::BAIL_OUT;
+                    continue;
+                }
+            } else if(s == Collation::COMMON_WEIGHT16) {
+                sec = CollationFastLatin::COMMON_SEC;
+            } else {
+                if(sec < CollationFastLatin::MIN_SEC_AFTER) {
+                    sec = CollationFastLatin::MIN_SEC_AFTER;
+                } else if(sec < CollationFastLatin::MAX_SEC_AFTER) {
+                    sec += CollationFastLatin::SEC_INC;
+                } else {
+                    miniCEs[i] = CollationFastLatin::BAIL_OUT;
+                    continue;
+                }
+            }
+            prevSecondary = s;
+            ter = CollationFastLatin::COMMON_TER;
+        }
+        U_ASSERT((lower32 & Collation::CASE_MASK) == 0);  // blanked out in uniqueCEs
+        uint32_t t = lower32 & Collation::ONLY_TERTIARY_MASK;
+        if(t > Collation::COMMON_WEIGHT16) {
+            if(ter < CollationFastLatin::MAX_TER_AFTER) {
+                ++ter;
+            } else {
+                miniCEs[i] = CollationFastLatin::BAIL_OUT;
+                continue;
+            }
+        }
+        if(CollationFastLatin::MIN_LONG <= pri && pri <= CollationFastLatin::MAX_LONG) {
+            U_ASSERT(sec == CollationFastLatin::COMMON_SEC);
+            miniCEs[i] = (uint16_t)(pri | ter);
+        } else {
+            miniCEs[i] = (uint16_t)(pri | sec | ter);
+        }
+    }
+#if DEBUG_COLLATION_FAST_LATIN_BUILDER
+    printf("last mini primary: %04x\n", pri);
+#endif
+#if DEBUG_COLLATION_FAST_LATIN_BUILDER >= 2
+    for(int32_t i = 0; i < uniqueCEs.size(); ++i) {
+        int64_t ce = uniqueCEs.elementAti(i);
+        printf("unique CE 0x%016lx -> 0x%04x\n", ce, miniCEs[i]);
+    }
+#endif
+    return U_SUCCESS(errorCode);
+}
+
+UBool
+CollationFastLatinBuilder::encodeCharCEs(UErrorCode &errorCode) {
+    if(U_FAILURE(errorCode)) { return FALSE; }
+    int32_t miniCEsStart = result.length();
+    for(int32_t i = 0; i < CollationFastLatin::NUM_FAST_CHARS; ++i) {
+        result.append(0);  // initialize to completely ignorable
+    }
+    int32_t indexBase = result.length();
+    for(int32_t i = 0; i < CollationFastLatin::NUM_FAST_CHARS; ++i) {
+        int64_t ce = charCEs[i][0];
+        if(isContractionCharCE(ce)) { continue; }  // defer contraction
+        uint32_t miniCE = encodeTwoCEs(ce, charCEs[i][1]);
+        if(miniCE > 0xffff) {
+            // Note: There is a chance that this new expansion is the same as a previous one,
+            // and if so, then we could reuse the other expansion.
+            // However, that seems unlikely.
+            int32_t expansionIndex = result.length() - indexBase;
+            if(expansionIndex > (int32_t)CollationFastLatin::INDEX_MASK) {
+                miniCE = CollationFastLatin::BAIL_OUT;
+            } else {
+                result.append((UChar)(miniCE >> 16)).append((UChar)miniCE);
+                miniCE = CollationFastLatin::EXPANSION | expansionIndex;
+            }
+        }
+        result.setCharAt(miniCEsStart + i, (UChar)miniCE);
+    }
+    return U_SUCCESS(errorCode);
+}
+
+UBool
+CollationFastLatinBuilder::encodeContractions(UErrorCode &errorCode) {
+    // We encode all contraction lists so that the first word of a list
+    // terminates the previous list, and we only need one additional terminator at the end.
+    if(U_FAILURE(errorCode)) { return FALSE; }
+    int32_t indexBase = headerLength + CollationFastLatin::NUM_FAST_CHARS;
+    int32_t firstContractionIndex = result.length();
+    for(int32_t i = 0; i < CollationFastLatin::NUM_FAST_CHARS; ++i) {
+        int64_t ce = charCEs[i][0];
+        if(!isContractionCharCE(ce)) { continue; }
+        int32_t contractionIndex = result.length() - indexBase;
+        if(contractionIndex > (int32_t)CollationFastLatin::INDEX_MASK) {
+            result.setCharAt(headerLength + i, CollationFastLatin::BAIL_OUT);
+            continue;
+        }
+        UBool firstTriple = TRUE;
+        for(int32_t index = (int32_t)ce & 0x7fffffff;; index += 3) {
+            int32_t x = contractionCEs.elementAti(index);
+            if((uint32_t)x == CollationFastLatin::CONTR_CHAR_MASK && !firstTriple) { break; }
+            int64_t cce0 = contractionCEs.elementAti(index + 1);
+            int64_t cce1 = contractionCEs.elementAti(index + 2);
+            uint32_t miniCE = encodeTwoCEs(cce0, cce1);
+            if(miniCE == CollationFastLatin::BAIL_OUT) {
+                result.append((UChar)(x | (1 << CollationFastLatin::CONTR_LENGTH_SHIFT)));
+            } else if(miniCE <= 0xffff) {
+                result.append((UChar)(x | (2 << CollationFastLatin::CONTR_LENGTH_SHIFT)));
+                result.append((UChar)miniCE);
+            } else {
+                result.append((UChar)(x | (3 << CollationFastLatin::CONTR_LENGTH_SHIFT)));
+                result.append((UChar)(miniCE >> 16)).append((UChar)miniCE);
+            }
+            firstTriple = FALSE;
+        }
+        // Note: There is a chance that this new contraction list is the same as a previous one,
+        // and if so, then we could truncate the result and reuse the other list.
+        // However, that seems unlikely.
+        result.setCharAt(headerLength + i,
+                         (UChar)(CollationFastLatin::CONTRACTION | contractionIndex));
+    }
+    if(result.length() > firstContractionIndex) {
+        // Terminate the last contraction list.
+        result.append((UChar)CollationFastLatin::CONTR_CHAR_MASK);
+    }
+    if(result.isBogus()) {
+        errorCode = U_MEMORY_ALLOCATION_ERROR;
+        return FALSE;
+    }
+#if DEBUG_COLLATION_FAST_LATIN_BUILDER
+    printf("** fast Latin %d * 2 = %d bytes\n", result.length(), result.length() * 2);
+    puts("   header & below-digit groups map");
+    int32_t i = 0;
+    for(; i < headerLength; ++i) {
+        printf(" %04x", result[i]);
+    }
+    printf("\n   char mini CEs");
+    U_ASSERT(CollationFastLatin::NUM_FAST_CHARS % 16 == 0);
+    for(; i < indexBase; i += 16) {
+        UChar32 c = i - headerLength;
+        if(c >= CollationFastLatin::LATIN_LIMIT) {
+            c = CollationFastLatin::PUNCT_START + c - CollationFastLatin::LATIN_LIMIT;
+        }
+        printf("\n %04x:", c);
+        for(int32_t j = 0; j < 16; ++j) {
+            printf(" %04x", result[i + j]);
+        }
+    }
+    printf("\n   expansions & contractions");
+    for(; i < result.length(); ++i) {
+        if((i - indexBase) % 16 == 0) { puts(""); }
+        printf(" %04x", result[i]);
+    }
+    puts("");
+#endif
+    return TRUE;
+}
+
+uint32_t
+CollationFastLatinBuilder::encodeTwoCEs(int64_t first, int64_t second) const {
+    if(first == 0) {
+        return 0;  // completely ignorable
+    }
+    if(first == Collation::NO_CE) {
+        return CollationFastLatin::BAIL_OUT;
+    }
+    U_ASSERT((uint32_t)(first >> 32) != Collation::NO_CE_PRIMARY);
+
+    uint32_t miniCE = getMiniCE(first);
+    if(miniCE == CollationFastLatin::BAIL_OUT) { return miniCE; }
+    if(miniCE >= CollationFastLatin::MIN_SHORT) {
+        // Extract & copy the case bits.
+        // Shift them from normal CE bits 15..14 to mini CE bits 4..3.
+        uint32_t c = (((uint32_t)first & Collation::CASE_MASK) >> (14 - 3));
+        // Only in mini CEs: Ignorable case bits = 0, lowercase = 1.
+        c += CollationFastLatin::LOWER_CASE;
+        miniCE |= c;
+    }
+    if(second == 0) { return miniCE; }
+
+    uint32_t miniCE1 = getMiniCE(second);
+    if(miniCE1 == CollationFastLatin::BAIL_OUT) { return miniCE1; }
+
+    uint32_t case1 = (uint32_t)second & Collation::CASE_MASK;
+    if(miniCE >= CollationFastLatin::MIN_SHORT &&
+            (miniCE & CollationFastLatin::SECONDARY_MASK) == CollationFastLatin::COMMON_SEC) {
+        // Try to combine the two mini CEs into one.
+        uint32_t sec1 = miniCE1 & CollationFastLatin::SECONDARY_MASK;
+        uint32_t ter1 = miniCE1 & CollationFastLatin::TERTIARY_MASK;
+        if(sec1 >= CollationFastLatin::MIN_SEC_HIGH && case1 == 0 &&
+                ter1 == CollationFastLatin::COMMON_TER) {
+            // sec1>=sec_high implies pri1==0.
+            return (miniCE & ~CollationFastLatin::SECONDARY_MASK) | sec1;
+        }
+    }
+
+    if(miniCE1 <= CollationFastLatin::SECONDARY_MASK || CollationFastLatin::MIN_SHORT <= miniCE1) {
+        // Secondary CE, or a CE with a short primary, copy the case bits.
+        case1 = (case1 >> (14 - 3)) + CollationFastLatin::LOWER_CASE;
+        miniCE1 |= case1;
+    }
+    return (miniCE << 16) | miniCE1;
+}
+
+U_NAMESPACE_END
+
+#endif  // !UCONFIG_NO_COLLATION