icuSources/i18n/collation.h

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