icuSources/i18n/collationfastlatin.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) 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(UChar 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 UChar *left, int32_t leftLength,
 215                                 const UChar *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 UChar *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();  // 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__