/src/icu/source/i18n/collation.h

Source (jump to first uncovered line)
// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
* Copyright (C) 2010-2015, International Business Machines
* Corporation and others.  All Rights Reserved.
*******************************************************************************
* collation.h
*
* created on: 2010oct27
* created by: Markus W. Scherer
*/

#ifndef __COLLATION_H__
#define __COLLATION_H__

#include "unicode/utypes.h"

#if !UCONFIG_NO_COLLATION

U_NAMESPACE_BEGIN

/**
 * Collation v2 basic definitions and static helper functions.
 *
 * Data structures except for expansion tables store 32-bit CEs which are
 * either specials (see tags below) or are compact forms of 64-bit CEs.
 */
class U_I18N_API Collation {
public:
    // Special sort key bytes for all levels.
    static const uint8_t TERMINATOR_BYTE = 0;
    static const uint8_t LEVEL_SEPARATOR_BYTE = 1;

    /** The secondary/tertiary lower limit for tailoring before any root elements. */
    static const uint32_t BEFORE_WEIGHT16 = 0x0100;

    /**
     * Merge-sort-key separator.
     * Same as the unique primary and identical-level weights of U+FFFE.
     * Must not be used as primary compression low terminator.
     * Otherwise usable.
     */
    static const uint8_t MERGE_SEPARATOR_BYTE = 2;
    static const uint32_t MERGE_SEPARATOR_PRIMARY = 0x02000000;  // U+FFFE
    static const uint32_t MERGE_SEPARATOR_CE32 = 0x02000505;  // U+FFFE

    /**
     * Primary compression low terminator, must be greater than MERGE_SEPARATOR_BYTE.
     * Reserved value in primary second byte if the lead byte is compressible.
     * Otherwise usable in all CE weight bytes.
     */
    static const uint8_t PRIMARY_COMPRESSION_LOW_BYTE = 3;
    /**
     * Primary compression high terminator.
     * Reserved value in primary second byte if the lead byte is compressible.
     * Otherwise usable in all CE weight bytes.
     */
    static const uint8_t PRIMARY_COMPRESSION_HIGH_BYTE = 0xff;

    /** Default secondary/tertiary weight lead byte. */
    static const uint8_t COMMON_BYTE = 5;
    static const uint32_t COMMON_WEIGHT16 = 0x0500;
    /** Middle 16 bits of a CE with a common secondary weight. */
    static const uint32_t COMMON_SECONDARY_CE = 0x05000000;
    /** Lower 16 bits of a CE with a common tertiary weight. */
    static const uint32_t COMMON_TERTIARY_CE = 0x0500;
    /** Lower 32 bits of a CE with common secondary and tertiary weights. */
    static const uint32_t COMMON_SEC_AND_TER_CE = 0x05000500;

    static const uint32_t SECONDARY_MASK = 0xffff0000;
    static const uint32_t CASE_MASK = 0xc000;
    static const uint32_t SECONDARY_AND_CASE_MASK = SECONDARY_MASK | CASE_MASK;
    /** Only the 2*6 bits for the pure tertiary weight. */
    static const uint32_t ONLY_TERTIARY_MASK = 0x3f3f;
    /** Only the secondary & tertiary bits; no case, no quaternary. */
    static const uint32_t ONLY_SEC_TER_MASK = SECONDARY_MASK | ONLY_TERTIARY_MASK;
    /** Case bits and tertiary bits. */
    static const uint32_t CASE_AND_TERTIARY_MASK = CASE_MASK | ONLY_TERTIARY_MASK;
    static const uint32_t QUATERNARY_MASK = 0xc0;
    /** Case bits and quaternary bits. */
    static const uint32_t CASE_AND_QUATERNARY_MASK = CASE_MASK | QUATERNARY_MASK;

    static const uint8_t UNASSIGNED_IMPLICIT_BYTE = 0xfe;  // compressible
    /**
     * First unassigned: AlphabeticIndex overflow boundary.
     * We want a 3-byte primary so that it fits into the root elements table.
     *
     * This 3-byte primary will not collide with
     * any unassigned-implicit 4-byte primaries because
     * the first few hundred Unicode code points all have real mappings.
     */
    static const uint32_t FIRST_UNASSIGNED_PRIMARY = 0xfe040200;

    static const uint8_t TRAIL_WEIGHT_BYTE = 0xff;  // not compressible
    static const uint32_t FIRST_TRAILING_PRIMARY = 0xff020200;  // [first trailing]
    static const uint32_t MAX_PRIMARY = 0xffff0000;  // U+FFFF
    static const uint32_t MAX_REGULAR_CE32 = 0xffff0505;  // U+FFFF

    // CE32 value for U+FFFD as well as illegal UTF-8 byte sequences (which behave like U+FFFD).
    // We use the third-highest primary weight for U+FFFD (as in UCA 6.3+).
    static const uint32_t FFFD_PRIMARY = MAX_PRIMARY - 0x20000;
    static const uint32_t FFFD_CE32 = MAX_REGULAR_CE32 - 0x20000;

    /**
     * A CE32 is special if its low byte is this or greater.
     * Impossible case bits 11 mark special CE32s.
     * This value itself is used to indicate a fallback to the base collator.
     */
    static const uint8_t SPECIAL_CE32_LOW_BYTE = 0xc0;
    static const uint32_t FALLBACK_CE32 = SPECIAL_CE32_LOW_BYTE;
    /**
     * Low byte of a long-primary special CE32.
     */
    static const uint8_t LONG_PRIMARY_CE32_LOW_BYTE = 0xc1;  // SPECIAL_CE32_LOW_BYTE | LONG_PRIMARY_TAG

    static const uint32_t UNASSIGNED_CE32 = 0xffffffff;  // Compute an unassigned-implicit CE.

    static const uint32_t NO_CE32 = 1;

    /** No CE: End of input. Only used in runtime code, not stored in data. */
    static const uint32_t NO_CE_PRIMARY = 1;  // not a left-adjusted weight
    static const uint32_t NO_CE_WEIGHT16 = 0x0100;  // weight of LEVEL_SEPARATOR_BYTE
    static const int64_t NO_CE = INT64_C(0x101000100);  // NO_CE_PRIMARY, NO_CE_WEIGHT16, NO_CE_WEIGHT16

    /** Sort key levels. */
    enum Level {
        /** Unspecified level. */
        NO_LEVEL,
        PRIMARY_LEVEL,
        SECONDARY_LEVEL,
        CASE_LEVEL,
        TERTIARY_LEVEL,
        QUATERNARY_LEVEL,
        IDENTICAL_LEVEL,
        /** Beyond sort key bytes. */
        ZERO_LEVEL
    };

    /**
     * Sort key level flags: xx_FLAG = 1 << xx_LEVEL.
     * In Java, use enum Level with flag() getters, or use EnumSet rather than hand-made bit sets.
     */
    static const uint32_t NO_LEVEL_FLAG = 1;
    static const uint32_t PRIMARY_LEVEL_FLAG = 2;
    static const uint32_t SECONDARY_LEVEL_FLAG = 4;
    static const uint32_t CASE_LEVEL_FLAG = 8;
    static const uint32_t TERTIARY_LEVEL_FLAG = 0x10;
    static const uint32_t QUATERNARY_LEVEL_FLAG = 0x20;
    static const uint32_t IDENTICAL_LEVEL_FLAG = 0x40;
    static const uint32_t ZERO_LEVEL_FLAG = 0x80;

    /**
     * Special-CE32 tags, from bits 3..0 of a special 32-bit CE.
     * Bits 31..8 are available for tag-specific data.
     * Bits  5..4: Reserved. May be used in the future to indicate lccc!=0 and tccc!=0.
     */
    enum {
        /**
         * Fall back to the base collator.
         * This is the tag value in SPECIAL_CE32_LOW_BYTE and FALLBACK_CE32.
         * Bits 31..8: Unused, 0.
         */
        FALLBACK_TAG = 0,
        /**
         * Long-primary CE with COMMON_SEC_AND_TER_CE.
         * Bits 31..8: Three-byte primary.
         */
        LONG_PRIMARY_TAG = 1,
        /**
         * Long-secondary CE with zero primary.
         * Bits 31..16: Secondary weight.
         * Bits 15.. 8: Tertiary weight.
         */
        LONG_SECONDARY_TAG = 2,
        /**
         * Unused.
         * May be used in the future for single-byte secondary CEs (SHORT_SECONDARY_TAG),
         * storing the secondary in bits 31..24, the ccc in bits 23..16,
         * and the tertiary in bits 15..8.
         */
        RESERVED_TAG_3 = 3,
        /**
         * Latin mini expansions of two simple CEs [pp, 05, tt] [00, ss, 05].
         * Bits 31..24: Single-byte primary weight pp of the first CE.
         * Bits 23..16: Tertiary weight tt of the first CE.
         * Bits 15.. 8: Secondary weight ss of the second CE.
         */
        LATIN_EXPANSION_TAG = 4,
        /**
         * Points to one or more simple/long-primary/long-secondary 32-bit CE32s.
         * Bits 31..13: Index into uint32_t table.
         * Bits 12.. 8: Length=1..31.
         */
        EXPANSION32_TAG = 5,
        /**
         * Points to one or more 64-bit CEs.
         * Bits 31..13: Index into CE table.
         * Bits 12.. 8: Length=1..31.
         */
        EXPANSION_TAG = 6,
        /**
         * Builder data, used only in the CollationDataBuilder, not in runtime data.
         *
         * If bit 8 is 0: Builder context, points to a list of context-sensitive mappings.
         * Bits 31..13: Index to the builder's list of ConditionalCE32 for this character.
         * Bits 12.. 9: Unused, 0.
         *
         * If bit 8 is 1 (IS_BUILDER_JAMO_CE32): Builder-only jamoCE32 value.
         * The builder fetches the Jamo CE32 from the trie.
         * Bits 31..13: Jamo code point.
         * Bits 12.. 9: Unused, 0.
         */
        BUILDER_DATA_TAG = 7,
        /**
         * Points to prefix trie.
         * Bits 31..13: Index into prefix/contraction data.
         * Bits 12.. 8: Unused, 0.
         */
        PREFIX_TAG = 8,
        /**
         * Points to contraction data.
         * Bits 31..13: Index into prefix/contraction data.
         * Bits 12..11: Unused, 0.
         * Bit      10: CONTRACT_TRAILING_CCC flag.
         * Bit       9: CONTRACT_NEXT_CCC flag.
         * Bit       8: CONTRACT_SINGLE_CP_NO_MATCH flag.
         */
        CONTRACTION_TAG = 9,
        /**
         * Decimal digit.
         * Bits 31..13: Index into uint32_t table for non-numeric-collation CE32.
         * Bit      12: Unused, 0.
         * Bits 11.. 8: Digit value 0..9.
         */
        DIGIT_TAG = 10,
        /**
         * Tag for U+0000, for moving the NUL-termination handling
         * from the regular fastpath into specials-handling code.
         * Bits 31..8: Unused, 0.
         */
        U0000_TAG = 11,
        /**
         * Tag for a Hangul syllable.
         * Bits 31..9: Unused, 0.
         * Bit      8: HANGUL_NO_SPECIAL_JAMO flag.
         */
        HANGUL_TAG = 12,
        /**
         * Tag for a lead surrogate code unit.
         * Optional optimization for UTF-16 string processing.
         * Bits 31..10: Unused, 0.
         *       9.. 8: =0: All associated supplementary code points are unassigned-implicit.
         *              =1: All associated supplementary code points fall back to the base data.
         *              else: (Normally 2) Look up the data for the supplementary code point.
         */
        LEAD_SURROGATE_TAG = 13,
        /**
         * Tag for CEs with primary weights in code point order.
         * Bits 31..13: Index into CE table, for one data "CE".
         * Bits 12.. 8: Unused, 0.
         *
         * This data "CE" has the following bit fields:
         * Bits 63..32: Three-byte primary pppppp00.
         *      31.. 8: Start/base code point of the in-order range.
         *           7: Flag isCompressible primary.
         *       6.. 0: Per-code point primary-weight increment.
         */
        OFFSET_TAG = 14,
        /**
         * Implicit CE tag. Compute an unassigned-implicit CE.
         * All bits are set (UNASSIGNED_CE32=0xffffffff).
         */
        IMPLICIT_TAG = 15
    };

    static UBool isAssignedCE32(uint32_t ce32) {
        return ce32 != FALLBACK_CE32 && ce32 != UNASSIGNED_CE32;
    }

    /**
     * We limit the number of CEs in an expansion
     * so that we can use a small number of length bits in the data structure,
     * and so that an implementation can copy CEs at runtime without growing a destination buffer.
     */
    static const int32_t MAX_EXPANSION_LENGTH = 31;
    static const int32_t MAX_INDEX = 0x7ffff;

    /**
     * Set if there is no match for the single (no-suffix) character itself.
     * This is only possible if there is a prefix.
     * In this case, discontiguous contraction matching cannot add combining marks
     * starting from an empty suffix.
     * The default CE32 is used anyway if there is no suffix match.
     */
    static const uint32_t CONTRACT_SINGLE_CP_NO_MATCH = 0x100;
    /** Set if the first character of every contraction suffix has lccc!=0. */
    static const uint32_t CONTRACT_NEXT_CCC = 0x200;
    /** Set if any contraction suffix ends with lccc!=0. */
    static const uint32_t CONTRACT_TRAILING_CCC = 0x400;

    /** For HANGUL_TAG: None of its Jamo CE32s isSpecialCE32(). */
    static const uint32_t HANGUL_NO_SPECIAL_JAMO = 0x100;

    static const uint32_t LEAD_ALL_UNASSIGNED = 0;
    static const uint32_t LEAD_ALL_FALLBACK = 0x100;
    static const uint32_t LEAD_MIXED = 0x200;
    static const uint32_t LEAD_TYPE_MASK = 0x300;

    static uint32_t makeLongPrimaryCE32(uint32_t p) { return p | LONG_PRIMARY_CE32_LOW_BYTE; }

    /** Turns the long-primary CE32 into a primary weight pppppp00. */
    static inline uint32_t primaryFromLongPrimaryCE32(uint32_t ce32) {
        return ce32 & 0xffffff00;
    }
    static inline int64_t ceFromLongPrimaryCE32(uint32_t ce32) {
        return ((int64_t)(ce32 & 0xffffff00) << 32) | COMMON_SEC_AND_TER_CE;
    }

    static uint32_t makeLongSecondaryCE32(uint32_t lower32) {
        return lower32 | SPECIAL_CE32_LOW_BYTE | LONG_SECONDARY_TAG;
    }
    static inline int64_t ceFromLongSecondaryCE32(uint32_t ce32) {
        return ce32 & 0xffffff00;
    }

    /** Makes a special CE32 with tag, index and length. */
    static uint32_t makeCE32FromTagIndexAndLength(int32_t tag, int32_t index, int32_t length) {
        return (index << 13) | (length << 8) | SPECIAL_CE32_LOW_BYTE | tag;
    }
    /** Makes a special CE32 with only tag and index. */
    static uint32_t makeCE32FromTagAndIndex(int32_t tag, int32_t index) {
        return (index << 13) | SPECIAL_CE32_LOW_BYTE | tag;
    }

    static inline UBool isSpecialCE32(uint32_t ce32) {
        return (ce32 & 0xff) >= SPECIAL_CE32_LOW_BYTE;
    }

    static inline int32_t tagFromCE32(uint32_t ce32) {
        return (int32_t)(ce32 & 0xf);
    }

    static inline UBool hasCE32Tag(uint32_t ce32, int32_t tag) {
        return isSpecialCE32(ce32) && tagFromCE32(ce32) == tag;
    }

    static inline UBool isLongPrimaryCE32(uint32_t ce32) {
        return hasCE32Tag(ce32, LONG_PRIMARY_TAG);
    }

    static UBool isSimpleOrLongCE32(uint32_t ce32) {
        return !isSpecialCE32(ce32) ||
                tagFromCE32(ce32) == LONG_PRIMARY_TAG ||
                tagFromCE32(ce32) == LONG_SECONDARY_TAG;
    }

    /**
     * @return true if the ce32 yields one or more CEs without further data lookups
     */
    static UBool isSelfContainedCE32(uint32_t ce32) {
        return !isSpecialCE32(ce32) ||
                tagFromCE32(ce32) == LONG_PRIMARY_TAG ||
                tagFromCE32(ce32) == LONG_SECONDARY_TAG ||
                tagFromCE32(ce32) == LATIN_EXPANSION_TAG;
    }

    static inline UBool isPrefixCE32(uint32_t ce32) {
        return hasCE32Tag(ce32, PREFIX_TAG);
    }

    static inline UBool isContractionCE32(uint32_t ce32) {
        return hasCE32Tag(ce32, CONTRACTION_TAG);
    }

    static inline UBool ce32HasContext(uint32_t ce32) {
        return isSpecialCE32(ce32) &&
                (tagFromCE32(ce32) == PREFIX_TAG ||
                tagFromCE32(ce32) == CONTRACTION_TAG);
    }

    /**
     * Get the first of the two Latin-expansion CEs encoded in ce32.
     * @see LATIN_EXPANSION_TAG
     */
    static inline int64_t latinCE0FromCE32(uint32_t ce32) {
        return ((int64_t)(ce32 & 0xff000000) << 32) | COMMON_SECONDARY_CE | ((ce32 & 0xff0000) >> 8);
    }

    /**
     * Get the second of the two Latin-expansion CEs encoded in ce32.
     * @see LATIN_EXPANSION_TAG
     */
    static inline int64_t latinCE1FromCE32(uint32_t ce32) {
        return ((ce32 & 0xff00) << 16) | COMMON_TERTIARY_CE;
    }

    /**
     * Returns the data index from a special CE32.
     */
    static inline int32_t indexFromCE32(uint32_t ce32) {
        return (int32_t)(ce32 >> 13);
    }

    /**
     * Returns the data length from a ce32.
     */
    static inline int32_t lengthFromCE32(uint32_t ce32) {
        return (ce32 >> 8) & 31;
    }

    /**
     * Returns the digit value from a DIGIT_TAG ce32.
     */
    static inline char digitFromCE32(uint32_t ce32) {
        return (char)((ce32 >> 8) & 0xf);
    }

    /** Returns a 64-bit CE from a simple CE32 (not special). */
    static inline int64_t ceFromSimpleCE32(uint32_t ce32) {
        // normal form ppppsstt -> pppp0000ss00tt00
        // assert (ce32 & 0xff) < SPECIAL_CE32_LOW_BYTE
        return ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | ((ce32 & 0xff) << 8);
    }

    /** Returns a 64-bit CE from a simple/long-primary/long-secondary CE32. */
    static inline int64_t ceFromCE32(uint32_t ce32) {
        uint32_t tertiary = ce32 & 0xff;
        if(tertiary < SPECIAL_CE32_LOW_BYTE) {
            // normal form ppppsstt -> pppp0000ss00tt00
            return ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | (tertiary << 8);
        } else {
            ce32 -= tertiary;
            if((tertiary & 0xf) == LONG_PRIMARY_TAG) {
                // long-primary form ppppppC1 -> pppppp00050000500
                return ((int64_t)ce32 << 32) | COMMON_SEC_AND_TER_CE;
            } else {
                // long-secondary form ssssttC2 -> 00000000sssstt00
                // assert (tertiary & 0xf) == LONG_SECONDARY_TAG
                return ce32;
            }
        }
    }

    /** Creates a CE from a primary weight. */
    static inline int64_t makeCE(uint32_t p) {
        return ((int64_t)p << 32) | COMMON_SEC_AND_TER_CE;
    }
    /**
     * Creates a CE from a primary weight,
     * 16-bit secondary/tertiary weights, and a 2-bit quaternary.
     */
    static inline int64_t makeCE(uint32_t p, uint32_t s, uint32_t t, uint32_t q) {
        return ((int64_t)p << 32) | (s << 16) | t | (q << 6);
    }

    /**
     * Increments a 2-byte primary by a code point offset.
     */
    static uint32_t incTwoBytePrimaryByOffset(uint32_t basePrimary, UBool isCompressible,
                                              int32_t offset);

    /**
     * Increments a 3-byte primary by a code point offset.
     */
    static uint32_t incThreeBytePrimaryByOffset(uint32_t basePrimary, UBool isCompressible,
                                                int32_t offset);

    /**
     * Decrements a 2-byte primary by one range step (1..0x7f).
     */
    static uint32_t decTwoBytePrimaryByOneStep(uint32_t basePrimary, UBool isCompressible, int32_t step);

    /**
     * Decrements a 3-byte primary by one range step (1..0x7f).
     */
    static uint32_t decThreeBytePrimaryByOneStep(uint32_t basePrimary, UBool isCompressible, int32_t step);

    /**
     * Computes a 3-byte primary for c's OFFSET_TAG data "CE".
     */
    static uint32_t getThreeBytePrimaryForOffsetData(UChar32 c, int64_t dataCE);

    /**
     * Returns the unassigned-character implicit primary weight for any valid code point c.
     */
    static uint32_t unassignedPrimaryFromCodePoint(UChar32 c);

    static inline int64_t unassignedCEFromCodePoint(UChar32 c) {
        return makeCE(unassignedPrimaryFromCodePoint(c));
    }

private:
    Collation();  // No instantiation.
};

U_NAMESPACE_END

#endif  // !UCONFIG_NO_COLLATION
#endif  // __COLLATION_H__

Coverage Report

Created: 2025-01-28 06:38

Line	Count	Source (jump to first uncovered line)
1		// © 2016 and later: Unicode, Inc. and others.
2		// License & terms of use: http://www.unicode.org/copyright.html
3		/*
4		*******************************************************************************
5		* Copyright (C) 2010-2015, International Business Machines
6		* Corporation and others. All Rights Reserved.
7		*******************************************************************************
8		* collation.h
9		*
10		* created on: 2010oct27
11		* created by: Markus W. Scherer
12		*/
13
14		#ifndef __COLLATION_H__
15		#define __COLLATION_H__
16
17		#include "unicode/utypes.h"
18
19		#if !UCONFIG_NO_COLLATION
20
21		U_NAMESPACE_BEGIN
22
23		/**
24		* Collation v2 basic definitions and static helper functions.
25		*
26		* Data structures except for expansion tables store 32-bit CEs which are
27		* either specials (see tags below) or are compact forms of 64-bit CEs.
28		*/
29		class U_I18N_API Collation {
30		public:
31		// Special sort key bytes for all levels.
32		static const uint8_t TERMINATOR_BYTE = 0;
33		static const uint8_t LEVEL_SEPARATOR_BYTE = 1;
34
35		/** The secondary/tertiary lower limit for tailoring before any root elements. */
36		static const uint32_t BEFORE_WEIGHT16 = 0x0100;
37
38		/**
39		* Merge-sort-key separator.
40		* Same as the unique primary and identical-level weights of U+FFFE.
41		* Must not be used as primary compression low terminator.
42		* Otherwise usable.
43		*/
44		static const uint8_t MERGE_SEPARATOR_BYTE = 2;
45		static const uint32_t MERGE_SEPARATOR_PRIMARY = 0x02000000; // U+FFFE
46		static const uint32_t MERGE_SEPARATOR_CE32 = 0x02000505; // U+FFFE
47
48		/**
49		* Primary compression low terminator, must be greater than MERGE_SEPARATOR_BYTE.
50		* Reserved value in primary second byte if the lead byte is compressible.
51		* Otherwise usable in all CE weight bytes.
52		*/
53		static const uint8_t PRIMARY_COMPRESSION_LOW_BYTE = 3;
54		/**
55		* Primary compression high terminator.
56		* Reserved value in primary second byte if the lead byte is compressible.
57		* Otherwise usable in all CE weight bytes.
58		*/
59		static const uint8_t PRIMARY_COMPRESSION_HIGH_BYTE = 0xff;
60
61		/** Default secondary/tertiary weight lead byte. */
62		static const uint8_t COMMON_BYTE = 5;
63		static const uint32_t COMMON_WEIGHT16 = 0x0500;
64		/** Middle 16 bits of a CE with a common secondary weight. */
65		static const uint32_t COMMON_SECONDARY_CE = 0x05000000;
66		/** Lower 16 bits of a CE with a common tertiary weight. */
67		static const uint32_t COMMON_TERTIARY_CE = 0x0500;
68		/** Lower 32 bits of a CE with common secondary and tertiary weights. */
69		static const uint32_t COMMON_SEC_AND_TER_CE = 0x05000500;
70
71		static const uint32_t SECONDARY_MASK = 0xffff0000;
72		static const uint32_t CASE_MASK = 0xc000;
73		static const uint32_t SECONDARY_AND_CASE_MASK = SECONDARY_MASK \| CASE_MASK;
74		/** Only the 26 bits for the pure tertiary weight. /
75		static const uint32_t ONLY_TERTIARY_MASK = 0x3f3f;
76		/** Only the secondary & tertiary bits; no case, no quaternary. */
77		static const uint32_t ONLY_SEC_TER_MASK = SECONDARY_MASK \| ONLY_TERTIARY_MASK;
78		/** Case bits and tertiary bits. */
79		static const uint32_t CASE_AND_TERTIARY_MASK = CASE_MASK \| ONLY_TERTIARY_MASK;
80		static const uint32_t QUATERNARY_MASK = 0xc0;
81		/** Case bits and quaternary bits. */
82		static const uint32_t CASE_AND_QUATERNARY_MASK = CASE_MASK \| QUATERNARY_MASK;
83
84		static const uint8_t UNASSIGNED_IMPLICIT_BYTE = 0xfe; // compressible
85		/**
86		* First unassigned: AlphabeticIndex overflow boundary.
87		* We want a 3-byte primary so that it fits into the root elements table.
88		*
89		* This 3-byte primary will not collide with
90		* any unassigned-implicit 4-byte primaries because
91		* the first few hundred Unicode code points all have real mappings.
92		*/
93		static const uint32_t FIRST_UNASSIGNED_PRIMARY = 0xfe040200;
94
95		static const uint8_t TRAIL_WEIGHT_BYTE = 0xff; // not compressible
96		static const uint32_t FIRST_TRAILING_PRIMARY = 0xff020200; // [first trailing]
97		static const uint32_t MAX_PRIMARY = 0xffff0000; // U+FFFF
98		static const uint32_t MAX_REGULAR_CE32 = 0xffff0505; // U+FFFF
99
100		// CE32 value for U+FFFD as well as illegal UTF-8 byte sequences (which behave like U+FFFD).
101		// We use the third-highest primary weight for U+FFFD (as in UCA 6.3+).
102		static const uint32_t FFFD_PRIMARY = MAX_PRIMARY - 0x20000;
103		static const uint32_t FFFD_CE32 = MAX_REGULAR_CE32 - 0x20000;
104
105		/**
106		* A CE32 is special if its low byte is this or greater.
107		* Impossible case bits 11 mark special CE32s.
108		* This value itself is used to indicate a fallback to the base collator.
109		*/
110		static const uint8_t SPECIAL_CE32_LOW_BYTE = 0xc0;
111		static const uint32_t FALLBACK_CE32 = SPECIAL_CE32_LOW_BYTE;
112		/**
113		* Low byte of a long-primary special CE32.
114		*/
115		static const uint8_t LONG_PRIMARY_CE32_LOW_BYTE = 0xc1; // SPECIAL_CE32_LOW_BYTE \| LONG_PRIMARY_TAG
116
117		static const uint32_t UNASSIGNED_CE32 = 0xffffffff; // Compute an unassigned-implicit CE.
118
119		static const uint32_t NO_CE32 = 1;
120
121		/** No CE: End of input. Only used in runtime code, not stored in data. */
122		static const uint32_t NO_CE_PRIMARY = 1; // not a left-adjusted weight
123		static const uint32_t NO_CE_WEIGHT16 = 0x0100; // weight of LEVEL_SEPARATOR_BYTE
124		static const int64_t NO_CE = INT64_C(0x101000100); // NO_CE_PRIMARY, NO_CE_WEIGHT16, NO_CE_WEIGHT16
125
126		/** Sort key levels. */
127		enum Level {
128		/** Unspecified level. */
129		NO_LEVEL,
130		PRIMARY_LEVEL,
131		SECONDARY_LEVEL,
132		CASE_LEVEL,
133		TERTIARY_LEVEL,
134		QUATERNARY_LEVEL,
135		IDENTICAL_LEVEL,
136		/** Beyond sort key bytes. */
137		ZERO_LEVEL
138		};
139
140		/**
141		* Sort key level flags: xx_FLAG = 1 << xx_LEVEL.
142		* In Java, use enum Level with flag() getters, or use EnumSet rather than hand-made bit sets.
143		*/
144		static const uint32_t NO_LEVEL_FLAG = 1;
145		static const uint32_t PRIMARY_LEVEL_FLAG = 2;
146		static const uint32_t SECONDARY_LEVEL_FLAG = 4;
147		static const uint32_t CASE_LEVEL_FLAG = 8;
148		static const uint32_t TERTIARY_LEVEL_FLAG = 0x10;
149		static const uint32_t QUATERNARY_LEVEL_FLAG = 0x20;
150		static const uint32_t IDENTICAL_LEVEL_FLAG = 0x40;
151		static const uint32_t ZERO_LEVEL_FLAG = 0x80;
152
153		/**
154		* Special-CE32 tags, from bits 3..0 of a special 32-bit CE.
155		* Bits 31..8 are available for tag-specific data.
156		* Bits 5..4: Reserved. May be used in the future to indicate lccc!=0 and tccc!=0.
157		*/
158		enum {
159		/**
160		* Fall back to the base collator.
161		* This is the tag value in SPECIAL_CE32_LOW_BYTE and FALLBACK_CE32.
162		* Bits 31..8: Unused, 0.
163		*/
164		FALLBACK_TAG = 0,
165		/**
166		* Long-primary CE with COMMON_SEC_AND_TER_CE.
167		* Bits 31..8: Three-byte primary.
168		*/
169		LONG_PRIMARY_TAG = 1,
170		/**
171		* Long-secondary CE with zero primary.
172		* Bits 31..16: Secondary weight.
173		* Bits 15.. 8: Tertiary weight.
174		*/
175		LONG_SECONDARY_TAG = 2,
176		/**
177		* Unused.
178		* May be used in the future for single-byte secondary CEs (SHORT_SECONDARY_TAG),
179		* storing the secondary in bits 31..24, the ccc in bits 23..16,
180		* and the tertiary in bits 15..8.
181		*/
182		RESERVED_TAG_3 = 3,
183		/**
184		* Latin mini expansions of two simple CEs [pp, 05, tt] [00, ss, 05].
185		* Bits 31..24: Single-byte primary weight pp of the first CE.
186		* Bits 23..16: Tertiary weight tt of the first CE.
187		* Bits 15.. 8: Secondary weight ss of the second CE.
188		*/
189		LATIN_EXPANSION_TAG = 4,
190		/**
191		* Points to one or more simple/long-primary/long-secondary 32-bit CE32s.
192		* Bits 31..13: Index into uint32_t table.
193		* Bits 12.. 8: Length=1..31.
194		*/
195		EXPANSION32_TAG = 5,
196		/**
197		* Points to one or more 64-bit CEs.
198		* Bits 31..13: Index into CE table.
199		* Bits 12.. 8: Length=1..31.
200		*/
201		EXPANSION_TAG = 6,
202		/**
203		* Builder data, used only in the CollationDataBuilder, not in runtime data.
204		*
205		* If bit 8 is 0: Builder context, points to a list of context-sensitive mappings.
206		* Bits 31..13: Index to the builder's list of ConditionalCE32 for this character.
207		* Bits 12.. 9: Unused, 0.
208		*
209		* If bit 8 is 1 (IS_BUILDER_JAMO_CE32): Builder-only jamoCE32 value.
210		* The builder fetches the Jamo CE32 from the trie.
211		* Bits 31..13: Jamo code point.
212		* Bits 12.. 9: Unused, 0.
213		*/
214		BUILDER_DATA_TAG = 7,
215		/**
216		* Points to prefix trie.
217		* Bits 31..13: Index into prefix/contraction data.
218		* Bits 12.. 8: Unused, 0.
219		*/
220		PREFIX_TAG = 8,
221		/**
222		* Points to contraction data.
223		* Bits 31..13: Index into prefix/contraction data.
224		* Bits 12..11: Unused, 0.
225		* Bit 10: CONTRACT_TRAILING_CCC flag.
226		* Bit 9: CONTRACT_NEXT_CCC flag.
227		* Bit 8: CONTRACT_SINGLE_CP_NO_MATCH flag.
228		*/
229		CONTRACTION_TAG = 9,
230		/**
231		* Decimal digit.
232		* Bits 31..13: Index into uint32_t table for non-numeric-collation CE32.
233		* Bit 12: Unused, 0.
234		* Bits 11.. 8: Digit value 0..9.
235		*/
236		DIGIT_TAG = 10,
237		/**
238		* Tag for U+0000, for moving the NUL-termination handling
239		* from the regular fastpath into specials-handling code.
240		* Bits 31..8: Unused, 0.
241		*/
242		U0000_TAG = 11,
243		/**
244		* Tag for a Hangul syllable.
245		* Bits 31..9: Unused, 0.
246		* Bit 8: HANGUL_NO_SPECIAL_JAMO flag.
247		*/
248		HANGUL_TAG = 12,
249		/**
250		* Tag for a lead surrogate code unit.
251		* Optional optimization for UTF-16 string processing.
252		* Bits 31..10: Unused, 0.
253		* 9.. 8: =0: All associated supplementary code points are unassigned-implicit.
254		* =1: All associated supplementary code points fall back to the base data.
255		* else: (Normally 2) Look up the data for the supplementary code point.
256		*/
257		LEAD_SURROGATE_TAG = 13,
258		/**
259		* Tag for CEs with primary weights in code point order.
260		* Bits 31..13: Index into CE table, for one data "CE".
261		* Bits 12.. 8: Unused, 0.
262		*
263		* This data "CE" has the following bit fields:
264		* Bits 63..32: Three-byte primary pppppp00.
265		* 31.. 8: Start/base code point of the in-order range.
266		* 7: Flag isCompressible primary.
267		* 6.. 0: Per-code point primary-weight increment.
268		*/
269		OFFSET_TAG = 14,
270		/**
271		* Implicit CE tag. Compute an unassigned-implicit CE.
272		* All bits are set (UNASSIGNED_CE32=0xffffffff).
273		*/
274		IMPLICIT_TAG = 15
275		};
276
277	0	static UBool isAssignedCE32(uint32_t ce32) {
278	0	return ce32 != FALLBACK_CE32 && ce32 != UNASSIGNED_CE32;
279	0	}
280
281		/**
282		* We limit the number of CEs in an expansion
283		* so that we can use a small number of length bits in the data structure,
284		* and so that an implementation can copy CEs at runtime without growing a destination buffer.
285		*/
286		static const int32_t MAX_EXPANSION_LENGTH = 31;
287		static const int32_t MAX_INDEX = 0x7ffff;
288
289		/**
290		* Set if there is no match for the single (no-suffix) character itself.
291		* This is only possible if there is a prefix.
292		* In this case, discontiguous contraction matching cannot add combining marks
293		* starting from an empty suffix.
294		* The default CE32 is used anyway if there is no suffix match.
295		*/
296		static const uint32_t CONTRACT_SINGLE_CP_NO_MATCH = 0x100;
297		/** Set if the first character of every contraction suffix has lccc!=0. */
298		static const uint32_t CONTRACT_NEXT_CCC = 0x200;
299		/** Set if any contraction suffix ends with lccc!=0. */
300		static const uint32_t CONTRACT_TRAILING_CCC = 0x400;
301
302		/** For HANGUL_TAG: None of its Jamo CE32s isSpecialCE32(). */
303		static const uint32_t HANGUL_NO_SPECIAL_JAMO = 0x100;
304
305		static const uint32_t LEAD_ALL_UNASSIGNED = 0;
306		static const uint32_t LEAD_ALL_FALLBACK = 0x100;
307		static const uint32_t LEAD_MIXED = 0x200;
308		static const uint32_t LEAD_TYPE_MASK = 0x300;
309
310	0	static uint32_t makeLongPrimaryCE32(uint32_t p) { return p \| LONG_PRIMARY_CE32_LOW_BYTE; }
311
312		/** Turns the long-primary CE32 into a primary weight pppppp00. */
313	0	static inline uint32_t primaryFromLongPrimaryCE32(uint32_t ce32) {
314	0	return ce32 & 0xffffff00;
315	0	}
316	0	static inline int64_t ceFromLongPrimaryCE32(uint32_t ce32) {
317	0	return ((int64_t)(ce32 & 0xffffff00) << 32) \| COMMON_SEC_AND_TER_CE;
318	0	}
319
320	0	static uint32_t makeLongSecondaryCE32(uint32_t lower32) {
321	0	return lower32 \| SPECIAL_CE32_LOW_BYTE \| LONG_SECONDARY_TAG;
322	0	}
323	0	static inline int64_t ceFromLongSecondaryCE32(uint32_t ce32) {
324	0	return ce32 & 0xffffff00;
325	0	}
326
327		/** Makes a special CE32 with tag, index and length. */
328	0	static uint32_t makeCE32FromTagIndexAndLength(int32_t tag, int32_t index, int32_t length) {
329	0	return (index << 13) \| (length << 8) \| SPECIAL_CE32_LOW_BYTE \| tag;
330	0	}
331		/** Makes a special CE32 with only tag and index. */
332	0	static uint32_t makeCE32FromTagAndIndex(int32_t tag, int32_t index) {
333	0	return (index << 13) \| SPECIAL_CE32_LOW_BYTE \| tag;
334	0	}
335
336	0	static inline UBool isSpecialCE32(uint32_t ce32) {
337	0	return (ce32 & 0xff) >= SPECIAL_CE32_LOW_BYTE;
338	0	}
339
340	0	static inline int32_t tagFromCE32(uint32_t ce32) {
341	0	return (int32_t)(ce32 & 0xf);
342	0	}
343
344	0	static inline UBool hasCE32Tag(uint32_t ce32, int32_t tag) {
345	0	return isSpecialCE32(ce32) && tagFromCE32(ce32) == tag;
346	0	}
347
348	0	static inline UBool isLongPrimaryCE32(uint32_t ce32) {
349	0	return hasCE32Tag(ce32, LONG_PRIMARY_TAG);
350	0	}
351
352	0	static UBool isSimpleOrLongCE32(uint32_t ce32) {
353	0	return !isSpecialCE32(ce32) \|\|
354	0	tagFromCE32(ce32) == LONG_PRIMARY_TAG \|\|
355	0	tagFromCE32(ce32) == LONG_SECONDARY_TAG;
356	0	}
357
358		/**
359		* @return true if the ce32 yields one or more CEs without further data lookups
360		*/
361	0	static UBool isSelfContainedCE32(uint32_t ce32) {
362	0	return !isSpecialCE32(ce32) \|\|
363	0	tagFromCE32(ce32) == LONG_PRIMARY_TAG \|\|
364	0	tagFromCE32(ce32) == LONG_SECONDARY_TAG \|\|
365	0	tagFromCE32(ce32) == LATIN_EXPANSION_TAG;
366	0	}
367
368	0	static inline UBool isPrefixCE32(uint32_t ce32) {
369	0	return hasCE32Tag(ce32, PREFIX_TAG);
370	0	}
371
372	0	static inline UBool isContractionCE32(uint32_t ce32) {
373	0	return hasCE32Tag(ce32, CONTRACTION_TAG);
374	0	}
375
376	0	static inline UBool ce32HasContext(uint32_t ce32) {
377	0	return isSpecialCE32(ce32) &&
378	0	(tagFromCE32(ce32) == PREFIX_TAG \|\|
379	0	tagFromCE32(ce32) == CONTRACTION_TAG);
380	0	}
381
382		/**
383		* Get the first of the two Latin-expansion CEs encoded in ce32.
384		* @see LATIN_EXPANSION_TAG
385		*/
386	0	static inline int64_t latinCE0FromCE32(uint32_t ce32) {
387	0	return ((int64_t)(ce32 & 0xff000000) << 32) \| COMMON_SECONDARY_CE \| ((ce32 & 0xff0000) >> 8);
388	0	}
389
390		/**
391		* Get the second of the two Latin-expansion CEs encoded in ce32.
392		* @see LATIN_EXPANSION_TAG
393		*/
394	0	static inline int64_t latinCE1FromCE32(uint32_t ce32) {
395	0	return ((ce32 & 0xff00) << 16) \| COMMON_TERTIARY_CE;
396	0	}
397
398		/**
399		* Returns the data index from a special CE32.
400		*/
401	0	static inline int32_t indexFromCE32(uint32_t ce32) {
402	0	return (int32_t)(ce32 >> 13);
403	0	}
404
405		/**
406		* Returns the data length from a ce32.
407		*/
408	0	static inline int32_t lengthFromCE32(uint32_t ce32) {
409	0	return (ce32 >> 8) & 31;
410	0	}
411
412		/**
413		* Returns the digit value from a DIGIT_TAG ce32.
414		*/
415	0	static inline char digitFromCE32(uint32_t ce32) {
416	0	return (char)((ce32 >> 8) & 0xf);
417	0	}
418
419		/** Returns a 64-bit CE from a simple CE32 (not special). */
420	0	static inline int64_t ceFromSimpleCE32(uint32_t ce32) {
421		// normal form ppppsstt -> pppp0000ss00tt00
422		// assert (ce32 & 0xff) < SPECIAL_CE32_LOW_BYTE
423	0	return ((int64_t)(ce32 & 0xffff0000) << 32) \| ((ce32 & 0xff00) << 16) \| ((ce32 & 0xff) << 8);
424	0	}
425
426		/** Returns a 64-bit CE from a simple/long-primary/long-secondary CE32. */
427	0	static inline int64_t ceFromCE32(uint32_t ce32) {
428	0	uint32_t tertiary = ce32 & 0xff;
429	0	if(tertiary < SPECIAL_CE32_LOW_BYTE) {
430		// normal form ppppsstt -> pppp0000ss00tt00
431	0	return ((int64_t)(ce32 & 0xffff0000) << 32) \| ((ce32 & 0xff00) << 16) \| (tertiary << 8);
432	0	} else {
433	0	ce32 -= tertiary;
434	0	if((tertiary & 0xf) == LONG_PRIMARY_TAG) {
435		// long-primary form ppppppC1 -> pppppp00050000500
436	0	return ((int64_t)ce32 << 32) \| COMMON_SEC_AND_TER_CE;
437	0	} else {
438		// long-secondary form ssssttC2 -> 00000000sssstt00
439		// assert (tertiary & 0xf) == LONG_SECONDARY_TAG
440	0	return ce32;
441	0	}
442	0	}
443	0	}
444
445		/** Creates a CE from a primary weight. */
446	0	static inline int64_t makeCE(uint32_t p) {
447	0	return ((int64_t)p << 32) \| COMMON_SEC_AND_TER_CE;
448	0	}
449		/**
450		* Creates a CE from a primary weight,
451		* 16-bit secondary/tertiary weights, and a 2-bit quaternary.
452		*/
453	0	static inline int64_t makeCE(uint32_t p, uint32_t s, uint32_t t, uint32_t q) {
454	0	return ((int64_t)p << 32) \| (s << 16) \| t \| (q << 6);
455	0	}
456
457		/**
458		* Increments a 2-byte primary by a code point offset.
459		*/
460		static uint32_t incTwoBytePrimaryByOffset(uint32_t basePrimary, UBool isCompressible,
461		int32_t offset);
462
463		/**
464		* Increments a 3-byte primary by a code point offset.
465		*/
466		static uint32_t incThreeBytePrimaryByOffset(uint32_t basePrimary, UBool isCompressible,
467		int32_t offset);
468
469		/**
470		* Decrements a 2-byte primary by one range step (1..0x7f).
471		*/
472		static uint32_t decTwoBytePrimaryByOneStep(uint32_t basePrimary, UBool isCompressible, int32_t step);
473
474		/**
475		* Decrements a 3-byte primary by one range step (1..0x7f).
476		*/
477		static uint32_t decThreeBytePrimaryByOneStep(uint32_t basePrimary, UBool isCompressible, int32_t step);
478
479		/**
480		* Computes a 3-byte primary for c's OFFSET_TAG data "CE".
481		*/
482		static uint32_t getThreeBytePrimaryForOffsetData(UChar32 c, int64_t dataCE);
483
484		/**
485		* Returns the unassigned-character implicit primary weight for any valid code point c.
486		*/
487		static uint32_t unassignedPrimaryFromCodePoint(UChar32 c);
488
489	0	static inline int64_t unassignedCEFromCodePoint(UChar32 c) {
490	0	return makeCE(unassignedPrimaryFromCodePoint(c));
491	0	}
492
493		private:
494		Collation(); // No instantiation.
495		};
496
497		U_NAMESPACE_END
498
499		#endif // !UCONFIG_NO_COLLATION
500		#endif // __COLLATION_H__