OLD | NEW |
(Empty) | |
| 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 LATI
N_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_STA
RT); |
| 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 len
gth >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 t
hat. |
| 59 // (en_US_POSIX is unusual: It creates about 64 variable + 116 Latin primari
es.) |
| 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 p
rimaries |
| 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 & con
tractions |
| 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 b
efore 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 aft
er common |
| 131 static const uint32_t MIN_SEC_HIGH = MAX_SEC_AFTER + SEC_INC; // 20 high se
condaries |
| 132 static const uint32_t MAX_SEC_HIGH = SECONDARY_MASK; |
| 133 |
| 134 /** |
| 135 * Lookup: Add this offset to secondary weights, except for completely ignor
able 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 ignora
ble 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+tertia
ry 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_MAS
K. |
| 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 settin
gs. |
| 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 sLeng
th); |
| 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 &sInde
x, 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, uint
32_t pair); |
| 246 static uint32_t getTertiaries(uint32_t variableTop, UBool withCaseBits, uint
32_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 maxVari
able 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+20
3F. |
| 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., primar
y == 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 tab
le. |
| 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 t
able. |
| 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_SHI
FT. |
| 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__ |
OLD | NEW |