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
19U_NAMESPACE_BEGIN
20
21struct CollationData;
22struct CollationSettings;
23
24class U_I18N_API CollationFastLatin /* all static */ {
25public:
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
219private:
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
249private:
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
298U_NAMESPACE_END
299
300#endif  // !UCONFIG_NO_COLLATION
301#endif  // __COLLATIONFASTLATIN_H__
302