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