collationfastlatin.h (14332B)
1 // © 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 ******************************************************************************* 5 * Copyright (C) 2013-2015, International Business Machines 6 * Corporation and others. All Rights Reserved. 7 ******************************************************************************* 8 * collationfastlatin.h 9 * 10 * created on: 2013aug09 11 * created by: Markus W. Scherer 12 */ 13 14 #ifndef __COLLATIONFASTLATIN_H__ 15 #define __COLLATIONFASTLATIN_H__ 16 17 #include "unicode/utypes.h" 18 19 #if !UCONFIG_NO_COLLATION 20 21 U_NAMESPACE_BEGIN 22 23 struct CollationData; 24 struct CollationSettings; 25 26 class U_I18N_API CollationFastLatin /* all static */ { 27 public: 28 /** 29 * Fast Latin format version (one byte 1..FF). 30 * Must be incremented for any runtime-incompatible changes, 31 * in particular, for changes to any of the following constants. 32 * 33 * When the major version number of the main data format changes, 34 * we can reset this fast Latin version to 1. 35 */ 36 static const uint16_t VERSION = 2; 37 38 static const int32_t LATIN_MAX = 0x17f; 39 static const int32_t LATIN_LIMIT = LATIN_MAX + 1; 40 41 static const int32_t LATIN_MAX_UTF8_LEAD = 0xc5; // UTF-8 lead byte of LATIN_MAX 42 43 static const int32_t PUNCT_START = 0x2000; 44 static const int32_t PUNCT_LIMIT = 0x2040; 45 46 // excludes U+FFFE & U+FFFF 47 static const int32_t NUM_FAST_CHARS = LATIN_LIMIT + (PUNCT_LIMIT - PUNCT_START); 48 49 // Note on the supported weight ranges: 50 // Analysis of UCA 6.3 and CLDR 23 non-search tailorings shows that 51 // the CEs for characters in the above ranges, excluding expansions with length >2, 52 // excluding contractions of >2 characters, and other restrictions 53 // (see the builder's getCEsFromCE32()), 54 // use at most about 150 primary weights, 55 // where about 94 primary weights are possibly-variable (space/punct/symbol/currency), 56 // at most 4 secondary before-common weights, 57 // at most 4 secondary after-common weights, 58 // at most 16 secondary high weights (in secondary CEs), and 59 // at most 4 tertiary after-common weights. 60 // The following ranges are designed to support slightly more weights than that. 61 // (en_US_POSIX is unusual: It creates about 64 variable + 116 Latin primaries.) 62 63 // Digits may use long primaries (preserving more short ones) 64 // or short primaries (faster) without changing this data structure. 65 // (If we supported numeric collation, then digits would have to have long primaries 66 // so that special handling does not affect the fast path.) 67 68 static const uint32_t SHORT_PRIMARY_MASK = 0xfc00; // bits 15..10 69 static const uint32_t INDEX_MASK = 0x3ff; // bits 9..0 for expansions & contractions 70 static const uint32_t SECONDARY_MASK = 0x3e0; // bits 9..5 71 static const uint32_t CASE_MASK = 0x18; // bits 4..3 72 static const uint32_t LONG_PRIMARY_MASK = 0xfff8; // bits 15..3 73 static const uint32_t TERTIARY_MASK = 7; // bits 2..0 74 static const uint32_t CASE_AND_TERTIARY_MASK = CASE_MASK | TERTIARY_MASK; 75 76 static const uint32_t TWO_SHORT_PRIMARIES_MASK = 77 (SHORT_PRIMARY_MASK << 16) | SHORT_PRIMARY_MASK; // 0xfc00fc00 78 static const uint32_t TWO_LONG_PRIMARIES_MASK = 79 (LONG_PRIMARY_MASK << 16) | LONG_PRIMARY_MASK; // 0xfff8fff8 80 static const uint32_t TWO_SECONDARIES_MASK = 81 (SECONDARY_MASK << 16) | SECONDARY_MASK; // 0x3e003e0 82 static const uint32_t TWO_CASES_MASK = 83 (CASE_MASK << 16) | CASE_MASK; // 0x180018 84 static const uint32_t TWO_TERTIARIES_MASK = 85 (TERTIARY_MASK << 16) | TERTIARY_MASK; // 0x70007 86 87 /** 88 * Contraction with one fast Latin character. 89 * Use INDEX_MASK to find the start of the contraction list after the fixed table. 90 * The first entry contains the default mapping. 91 * Otherwise use CONTR_CHAR_MASK for the contraction character index 92 * (in ascending order). 93 * Use CONTR_LENGTH_SHIFT for the length of the entry 94 * (1=BAIL_OUT, 2=one CE, 3=two CEs). 95 * 96 * Also, U+0000 maps to a contraction entry, so that the fast path need not 97 * check for NUL termination. 98 * It usually maps to a contraction list with only the completely ignorable default value. 99 */ 100 static const uint32_t CONTRACTION = 0x400; 101 /** 102 * An expansion encodes two CEs. 103 * Use INDEX_MASK to find the pair of CEs after the fixed table. 104 * 105 * The higher a mini CE value, the easier it is to process. 106 * For expansions and higher, no context needs to be considered. 107 */ 108 static const uint32_t EXPANSION = 0x800; 109 /** 110 * Encodes one CE with a long/low mini primary (there are 128). 111 * All potentially-variable primaries must be in this range, 112 * to make the short-primary path as fast as possible. 113 */ 114 static const uint32_t MIN_LONG = 0xc00; 115 static const uint32_t LONG_INC = 8; 116 static const uint32_t MAX_LONG = 0xff8; 117 /** 118 * Encodes one CE with a short/high primary (there are 60), 119 * plus a secondary CE if the secondary weight is high. 120 * Fast handling: At least all letter primaries should be in this range. 121 */ 122 static const uint32_t MIN_SHORT = 0x1000; 123 static const uint32_t SHORT_INC = 0x400; 124 /** The highest primary weight is reserved for U+FFFF. */ 125 static const uint32_t MAX_SHORT = SHORT_PRIMARY_MASK; 126 127 static const uint32_t MIN_SEC_BEFORE = 0; // must add SEC_OFFSET 128 static const uint32_t SEC_INC = 0x20; 129 static const uint32_t MAX_SEC_BEFORE = MIN_SEC_BEFORE + 4 * SEC_INC; // 5 before common 130 static const uint32_t COMMON_SEC = MAX_SEC_BEFORE + SEC_INC; 131 static const uint32_t MIN_SEC_AFTER = COMMON_SEC + SEC_INC; 132 static const uint32_t MAX_SEC_AFTER = MIN_SEC_AFTER + 5 * SEC_INC; // 6 after common 133 static const uint32_t MIN_SEC_HIGH = MAX_SEC_AFTER + SEC_INC; // 20 high secondaries 134 static const uint32_t MAX_SEC_HIGH = SECONDARY_MASK; 135 136 /** 137 * Lookup: Add this offset to secondary weights, except for completely ignorable CEs. 138 * Must be greater than any special value, e.g., MERGE_WEIGHT. 139 * The exact value is not relevant for the format version. 140 */ 141 static const uint32_t SEC_OFFSET = SEC_INC; 142 static const uint32_t COMMON_SEC_PLUS_OFFSET = COMMON_SEC + SEC_OFFSET; 143 144 static const uint32_t TWO_SEC_OFFSETS = 145 (SEC_OFFSET << 16) | SEC_OFFSET; // 0x200020 146 static const uint32_t TWO_COMMON_SEC_PLUS_OFFSET = 147 (COMMON_SEC_PLUS_OFFSET << 16) | COMMON_SEC_PLUS_OFFSET; 148 149 static const uint32_t LOWER_CASE = 8; // case bits include this offset 150 static const uint32_t TWO_LOWER_CASES = (LOWER_CASE << 16) | LOWER_CASE; // 0x80008 151 152 static const uint32_t COMMON_TER = 0; // must add TER_OFFSET 153 static const uint32_t MAX_TER_AFTER = 7; // 7 after common 154 155 /** 156 * Lookup: Add this offset to tertiary weights, except for completely ignorable CEs. 157 * Must be greater than any special value, e.g., MERGE_WEIGHT. 158 * Must be greater than case bits as well, so that with combined case+tertiary weights 159 * plus the offset the tertiary bits does not spill over into the case bits. 160 * The exact value is not relevant for the format version. 161 */ 162 static const uint32_t TER_OFFSET = SEC_OFFSET; 163 static const uint32_t COMMON_TER_PLUS_OFFSET = COMMON_TER + TER_OFFSET; 164 165 static const uint32_t TWO_TER_OFFSETS = (TER_OFFSET << 16) | TER_OFFSET; 166 static const uint32_t TWO_COMMON_TER_PLUS_OFFSET = 167 (COMMON_TER_PLUS_OFFSET << 16) | COMMON_TER_PLUS_OFFSET; 168 169 static const uint32_t MERGE_WEIGHT = 3; 170 static const uint32_t EOS = 2; // end of string 171 static const uint32_t BAIL_OUT = 1; 172 173 /** 174 * Contraction result first word bits 8..0 contain the 175 * second contraction character, as a char index 0..NUM_FAST_CHARS-1. 176 * Each contraction list is terminated with a word containing CONTR_CHAR_MASK. 177 */ 178 static const uint32_t CONTR_CHAR_MASK = 0x1ff; 179 /** 180 * Contraction result first word bits 10..9 contain the result length: 181 * 1=bail out, 2=one mini CE, 3=two mini CEs 182 */ 183 static const uint32_t CONTR_LENGTH_SHIFT = 9; 184 185 /** 186 * Comparison return value when the regular comparison must be used. 187 * The exact value is not relevant for the format version. 188 */ 189 static const int32_t BAIL_OUT_RESULT = -2; 190 191 static inline int32_t getCharIndex(char16_t c) { 192 if(c <= LATIN_MAX) { 193 return c; 194 } else if(PUNCT_START <= c && c < PUNCT_LIMIT) { 195 return c - (PUNCT_START - LATIN_LIMIT); 196 } else { 197 // Not a fast Latin character. 198 // Note: U+FFFE & U+FFFF are forbidden in tailorings 199 // and thus do not occur in any contractions. 200 return -1; 201 } 202 } 203 204 /** 205 * Computes the options value for the compare functions 206 * and writes the precomputed primary weights. 207 * Returns -1 if the Latin fastpath is not supported for the data and settings. 208 * The capacity must be LATIN_LIMIT. 209 */ 210 static int32_t getOptions(const CollationData *data, const CollationSettings &settings, 211 uint16_t *primaries, int32_t capacity); 212 213 static int32_t compareUTF16(const uint16_t *table, const uint16_t *primaries, int32_t options, 214 const char16_t *left, int32_t leftLength, 215 const char16_t *right, int32_t rightLength); 216 217 static int32_t compareUTF8(const uint16_t *table, const uint16_t *primaries, int32_t options, 218 const uint8_t *left, int32_t leftLength, 219 const uint8_t *right, int32_t rightLength); 220 221 private: 222 static uint32_t lookup(const uint16_t *table, UChar32 c); 223 static uint32_t lookupUTF8(const uint16_t *table, UChar32 c, 224 const uint8_t *s8, int32_t &sIndex, int32_t sLength); 225 static uint32_t lookupUTF8Unsafe(const uint16_t *table, UChar32 c, 226 const uint8_t *s8, int32_t &sIndex); 227 228 static uint32_t nextPair(const uint16_t *table, UChar32 c, uint32_t ce, 229 const char16_t *s16, const uint8_t *s8, int32_t &sIndex, int32_t &sLength); 230 231 static inline uint32_t getPrimaries(uint32_t variableTop, uint32_t pair) { 232 uint32_t ce = pair & 0xffff; 233 if(ce >= MIN_SHORT) { return pair & TWO_SHORT_PRIMARIES_MASK; } 234 if(ce > variableTop) { return pair & TWO_LONG_PRIMARIES_MASK; } 235 if(ce >= MIN_LONG) { return 0; } // variable 236 return pair; // special mini CE 237 } 238 static inline uint32_t getSecondariesFromOneShortCE(uint32_t ce) { 239 ce &= SECONDARY_MASK; 240 if(ce < MIN_SEC_HIGH) { 241 return ce + SEC_OFFSET; 242 } else { 243 return ((ce + SEC_OFFSET) << 16) | COMMON_SEC_PLUS_OFFSET; 244 } 245 } 246 static uint32_t getSecondaries(uint32_t variableTop, uint32_t pair); 247 static uint32_t getCases(uint32_t variableTop, UBool strengthIsPrimary, uint32_t pair); 248 static uint32_t getTertiaries(uint32_t variableTop, UBool withCaseBits, uint32_t pair); 249 static uint32_t getQuaternaries(uint32_t variableTop, uint32_t pair); 250 251 private: 252 CollationFastLatin() = delete; // no constructor 253 }; 254 255 /* 256 * Format of the CollationFastLatin data table. 257 * CollationFastLatin::VERSION = 2. 258 * 259 * This table contains data for a Latin-text collation fastpath. 260 * The data is stored as an array of uint16_t which contains the following parts. 261 * 262 * uint16_t -- version & header length 263 * Bits 15..8: version, must match the VERSION 264 * 7..0: length of the header 265 * 266 * uint16_t varTops[header length - 1] 267 * Version 2: 268 * varTops[m] is the highest CollationFastLatin long-primary weight 269 * of supported maxVariable group m 270 * (special reorder group space, punct, symbol, currency). 271 * 272 * Version 1: 273 * Each of these values maps the variable top lead byte of a supported maxVariable group 274 * to the highest CollationFastLatin long-primary weight. 275 * The values are stored in ascending order. 276 * Bits 15..7: max fast-Latin long-primary weight (bits 11..3 shifted left by 4 bits) 277 * 6..0: regular primary lead byte 278 * 279 * uint16_t miniCEs[0x1c0] 280 * A mini collation element for each character U+0000..U+017F and U+2000..U+203F. 281 * Each value encodes one or two mini CEs (two are possible if the first one 282 * has a short mini primary and the second one is a secondary CE, i.e., primary == 0), 283 * or points to an expansion or to a contraction table. 284 * U+0000 always has a contraction entry, 285 * so that NUL-termination need not be tested in the fastpath. 286 * If the collation elements for a character or contraction cannot be encoded in this format, 287 * then the BAIL_OUT value is stored. 288 * For details see the comments for the class constants. 289 * 290 * uint16_t expansions[variable length]; 291 * Expansion mini CEs contain an offset relative to just after the miniCEs table. 292 * An expansions contains exactly 2 mini CEs. 293 * 294 * uint16_t contractions[variable length]; 295 * Contraction mini CEs contain an offset relative to just after the miniCEs table. 296 * It points to a list of tuples which map from a contraction suffix character to a result. 297 * First uint16_t of each tuple: 298 * Bits 10..9: Length of the result (1..3), see comments on CONTR_LENGTH_SHIFT. 299 * Bits 8..0: Contraction character, see comments on CONTR_CHAR_MASK. 300 * This is followed by 0, 1, or 2 uint16_t according to the length. 301 * Each list is terminated by an entry with CONTR_CHAR_MASK. 302 * Each list starts with such an entry which also contains the default result 303 * for when there is no contraction match. 304 * 305 * ----------------- 306 * Changes for version 2 (ICU 55) 307 * 308 * Special reorder groups do not necessarily start on whole primary lead bytes any more. 309 * Therefore, the varTops data has a new format: 310 * Version 1 stored the lead bytes of the highest root primaries for 311 * the maxVariable-supported special reorder groups. 312 * Now the top 16 bits would need to be stored, 313 * and it is simpler to store only the fast-Latin weights. 314 */ 315 316 U_NAMESPACE_END 317 318 #endif // !UCONFIG_NO_COLLATION 319 #endif // __COLLATIONFASTLATIN_H__