icuSources/i18n/collation.h

   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 2*6 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-implict.
 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     static UBool isAssignedCE32(uint32_t ce32) {
 278         return ce32 != FALLBACK_CE32 && ce32 != UNASSIGNED_CE32;
 279     }
 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     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     static inline uint32_t primaryFromLongPrimaryCE32(uint32_t ce32) {
 314         return ce32 & 0xffffff00;
 315     }
 316     static inline int64_t ceFromLongPrimaryCE32(uint32_t ce32) {
 317         return ((int64_t)(ce32 & 0xffffff00) << 32) | COMMON_SEC_AND_TER_CE;
 318     }
 319
 320     static uint32_t makeLongSecondaryCE32(uint32_t lower32) {
 321         return lower32 | SPECIAL_CE32_LOW_BYTE | LONG_SECONDARY_TAG;
 322     }
 323     static inline int64_t ceFromLongSecondaryCE32(uint32_t ce32) {
 324         return ce32 & 0xffffff00;
 325     }
 326
 327     /** Makes a special CE32 with tag, index and length. */
 328     static uint32_t makeCE32FromTagIndexAndLength(int32_t tag, int32_t index, int32_t length) {
 329         return (index << 13) | (length << 8) | SPECIAL_CE32_LOW_BYTE | tag;
 330     }
 331     /** Makes a special CE32 with only tag and index. */
 332     static uint32_t makeCE32FromTagAndIndex(int32_t tag, int32_t index) {
 333         return (index << 13) | SPECIAL_CE32_LOW_BYTE | tag;
 334     }
 335
 336     static inline UBool isSpecialCE32(uint32_t ce32) {
 337         return (ce32 & 0xff) >= SPECIAL_CE32_LOW_BYTE;
 338     }
 339
 340     static inline int32_t tagFromCE32(uint32_t ce32) {
 341         return (int32_t)(ce32 & 0xf);
 342     }
 343
 344     static inline UBool hasCE32Tag(uint32_t ce32, int32_t tag) {
 345         return isSpecialCE32(ce32) && tagFromCE32(ce32) == tag;
 346     }
 347
 348     static inline UBool isLongPrimaryCE32(uint32_t ce32) {
 349         return hasCE32Tag(ce32, LONG_PRIMARY_TAG);
 350     }
 351
 352     static UBool isSimpleOrLongCE32(uint32_t ce32) {
 353         return !isSpecialCE32(ce32) ||
 354                 tagFromCE32(ce32) == LONG_PRIMARY_TAG ||
 355                 tagFromCE32(ce32) == LONG_SECONDARY_TAG;
 356     }
 357
 358     /**
 359      * @return TRUE if the ce32 yields one or more CEs without further data lookups
 360      */
 361     static UBool isSelfContainedCE32(uint32_t ce32) {
 362         return !isSpecialCE32(ce32) ||
 363                 tagFromCE32(ce32) == LONG_PRIMARY_TAG ||
 364                 tagFromCE32(ce32) == LONG_SECONDARY_TAG ||
 365                 tagFromCE32(ce32) == LATIN_EXPANSION_TAG;
 366     }
 367
 368     static inline UBool isPrefixCE32(uint32_t ce32) {
 369         return hasCE32Tag(ce32, PREFIX_TAG);
 370     }
 371
 372     static inline UBool isContractionCE32(uint32_t ce32) {
 373         return hasCE32Tag(ce32, CONTRACTION_TAG);
 374     }
 375
 376     static inline UBool ce32HasContext(uint32_t ce32) {
 377         return isSpecialCE32(ce32) &&
 378                 (tagFromCE32(ce32) == PREFIX_TAG ||
 379                 tagFromCE32(ce32) == CONTRACTION_TAG);
 380     }
 381
 382     /**
 383      * Get the first of the two Latin-expansion CEs encoded in ce32.
 384      * @see LATIN_EXPANSION_TAG
 385      */
 386     static inline int64_t latinCE0FromCE32(uint32_t ce32) {
 387         return ((int64_t)(ce32 & 0xff000000) << 32) | COMMON_SECONDARY_CE | ((ce32 & 0xff0000) >> 8);
 388     }
 389
 390     /**
 391      * Get the second of the two Latin-expansion CEs encoded in ce32.
 392      * @see LATIN_EXPANSION_TAG
 393      */
 394     static inline int64_t latinCE1FromCE32(uint32_t ce32) {
 395         return ((ce32 & 0xff00) << 16) | COMMON_TERTIARY_CE;
 396     }
 397
 398     /**
 399      * Returns the data index from a special CE32.
 400      */
 401     static inline int32_t indexFromCE32(uint32_t ce32) {
 402         return (int32_t)(ce32 >> 13);
 403     }
 404
 405     /**
 406      * Returns the data length from a ce32.
 407      */
 408     static inline int32_t lengthFromCE32(uint32_t ce32) {
 409         return (ce32 >> 8) & 31;
 410     }
 411
 412     /**
 413      * Returns the digit value from a DIGIT_TAG ce32.
 414      */
 415     static inline char digitFromCE32(uint32_t ce32) {
 416         return (char)((ce32 >> 8) & 0xf);
 417     }
 418
 419     /** Returns a 64-bit CE from a simple CE32 (not special). */
 420     static inline int64_t ceFromSimpleCE32(uint32_t ce32) {
 421         // normal form ppppsstt -> pppp0000ss00tt00
 422         // assert (ce32 & 0xff) < SPECIAL_CE32_LOW_BYTE
 423         return ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | ((ce32 & 0xff) << 8);
 424     }
 425
 426     /** Returns a 64-bit CE from a simple/long-primary/long-secondary CE32. */
 427     static inline int64_t ceFromCE32(uint32_t ce32) {
 428         uint32_t tertiary = ce32 & 0xff;
 429         if(tertiary < SPECIAL_CE32_LOW_BYTE) {
 430             // normal form ppppsstt -> pppp0000ss00tt00
 431             return ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | (tertiary << 8);
 432         } else {
 433             ce32 -= tertiary;
 434             if((tertiary & 0xf) == LONG_PRIMARY_TAG) {
 435                 // long-primary form ppppppC1 -> pppppp00050000500
 436                 return ((int64_t)ce32 << 32) | COMMON_SEC_AND_TER_CE;
 437             } else {
 438                 // long-secondary form ssssttC2 -> 00000000sssstt00
 439                 // assert (tertiary & 0xf) == LONG_SECONDARY_TAG
 440                 return ce32;
 441             }
 442         }
 443     }
 444
 445     /** Creates a CE from a primary weight. */
 446     static inline int64_t makeCE(uint32_t p) {
 447         return ((int64_t)p << 32) | COMMON_SEC_AND_TER_CE;
 448     }
 449     /**
 450      * Creates a CE from a primary weight,
 451      * 16-bit secondary/tertiary weights, and a 2-bit quaternary.
 452      */
 453     static inline int64_t makeCE(uint32_t p, uint32_t s, uint32_t t, uint32_t q) {
 454         return ((int64_t)p << 32) | (s << 16) | t | (q << 6);
 455     }
 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     static inline int64_t unassignedCEFromCodePoint(UChar32 c) {
 490         return makeCE(unassignedPrimaryFromCodePoint(c));
 491     }
 492
 493 private:
 494     Collation();  // No instantiation.
 495 };
 496
 497 U_NAMESPACE_END
 498
 499 #endif  // !UCONFIG_NO_COLLATION
 500 #endif  // __COLLATION_H__