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 isAssignedCE32(uint32_t ce32)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 makeLongPrimaryCE32(uint32_t p)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. */ primaryFromLongPrimaryCE32(uint32_t ce32)313 static inline uint32_t primaryFromLongPrimaryCE32(uint32_t ce32) { 314 return ce32 & 0xffffff00; 315 } ceFromLongPrimaryCE32(uint32_t ce32)316 static inline int64_t ceFromLongPrimaryCE32(uint32_t ce32) { 317 return ((int64_t)(ce32 & 0xffffff00) << 32) | COMMON_SEC_AND_TER_CE; 318 } 319 makeLongSecondaryCE32(uint32_t lower32)320 static uint32_t makeLongSecondaryCE32(uint32_t lower32) { 321 return lower32 | SPECIAL_CE32_LOW_BYTE | LONG_SECONDARY_TAG; 322 } ceFromLongSecondaryCE32(uint32_t ce32)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. */ makeCE32FromTagIndexAndLength(int32_t tag,int32_t index,int32_t 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. */ makeCE32FromTagAndIndex(int32_t tag,int32_t index)332 static uint32_t makeCE32FromTagAndIndex(int32_t tag, int32_t index) { 333 return (index << 13) | SPECIAL_CE32_LOW_BYTE | tag; 334 } 335 isSpecialCE32(uint32_t ce32)336 static inline UBool isSpecialCE32(uint32_t ce32) { 337 return (ce32 & 0xff) >= SPECIAL_CE32_LOW_BYTE; 338 } 339 tagFromCE32(uint32_t ce32)340 static inline int32_t tagFromCE32(uint32_t ce32) { 341 return (int32_t)(ce32 & 0xf); 342 } 343 hasCE32Tag(uint32_t ce32,int32_t tag)344 static inline UBool hasCE32Tag(uint32_t ce32, int32_t tag) { 345 return isSpecialCE32(ce32) && tagFromCE32(ce32) == tag; 346 } 347 isLongPrimaryCE32(uint32_t ce32)348 static inline UBool isLongPrimaryCE32(uint32_t ce32) { 349 return hasCE32Tag(ce32, LONG_PRIMARY_TAG); 350 } 351 isSimpleOrLongCE32(uint32_t ce32)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 */ isSelfContainedCE32(uint32_t ce32)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 isPrefixCE32(uint32_t ce32)368 static inline UBool isPrefixCE32(uint32_t ce32) { 369 return hasCE32Tag(ce32, PREFIX_TAG); 370 } 371 isContractionCE32(uint32_t ce32)372 static inline UBool isContractionCE32(uint32_t ce32) { 373 return hasCE32Tag(ce32, CONTRACTION_TAG); 374 } 375 ce32HasContext(uint32_t ce32)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 */ latinCE0FromCE32(uint32_t ce32)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 */ latinCE1FromCE32(uint32_t ce32)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 */ indexFromCE32(uint32_t ce32)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 */ lengthFromCE32(uint32_t ce32)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 */ digitFromCE32(uint32_t ce32)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). */ ceFromSimpleCE32(uint32_t ce32)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. */ ceFromCE32(uint32_t 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. */ makeCE(uint32_t p)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 */ makeCE(uint32_t p,uint32_t s,uint32_t t,uint32_t q)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 unassignedCEFromCodePoint(UChar32 c)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__ 501