icuSources/i18n/collation.h

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