/src/icu/icu4c/source/common/ucptrie.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | // © 2017 and later: Unicode, Inc. and others. |
2 | | // License & terms of use: http://www.unicode.org/copyright.html |
3 | | |
4 | | // ucptrie.cpp (modified from utrie2.cpp) |
5 | | // created: 2017dec29 Markus W. Scherer |
6 | | |
7 | | // #define UCPTRIE_DEBUG |
8 | | #ifdef UCPTRIE_DEBUG |
9 | | # include <stdio.h> |
10 | | #endif |
11 | | |
12 | | #include "unicode/utypes.h" |
13 | | #include "unicode/ucptrie.h" |
14 | | #include "unicode/utf.h" |
15 | | #include "unicode/utf8.h" |
16 | | #include "unicode/utf16.h" |
17 | | #include "cmemory.h" |
18 | | #include "uassert.h" |
19 | | #include "ucptrie_impl.h" |
20 | | |
21 | | U_CAPI UCPTrie * U_EXPORT2 |
22 | | ucptrie_openFromBinary(UCPTrieType type, UCPTrieValueWidth valueWidth, |
23 | | const void *data, int32_t length, int32_t *pActualLength, |
24 | 24.4k | UErrorCode *pErrorCode) { |
25 | 24.4k | if (U_FAILURE(*pErrorCode)) { |
26 | 0 | return nullptr; |
27 | 0 | } |
28 | | |
29 | 24.4k | if (length <= 0 || (U_POINTER_MASK_LSB(data, 3) != 0) || |
30 | 24.4k | type < UCPTRIE_TYPE_ANY || UCPTRIE_TYPE_SMALL < type || |
31 | 24.4k | valueWidth < UCPTRIE_VALUE_BITS_ANY || UCPTRIE_VALUE_BITS_8 < valueWidth) { |
32 | 0 | *pErrorCode = U_ILLEGAL_ARGUMENT_ERROR; |
33 | 0 | return nullptr; |
34 | 0 | } |
35 | | |
36 | | // Enough data for a trie header? |
37 | 24.4k | if (length < (int32_t)sizeof(UCPTrieHeader)) { |
38 | 0 | *pErrorCode = U_INVALID_FORMAT_ERROR; |
39 | 0 | return nullptr; |
40 | 0 | } |
41 | | |
42 | | // Check the signature. |
43 | 24.4k | const UCPTrieHeader *header = (const UCPTrieHeader *)data; |
44 | 24.4k | if (header->signature != UCPTRIE_SIG) { |
45 | 0 | *pErrorCode = U_INVALID_FORMAT_ERROR; |
46 | 0 | return nullptr; |
47 | 0 | } |
48 | | |
49 | 24.4k | int32_t options = header->options; |
50 | 24.4k | int32_t typeInt = (options >> 6) & 3; |
51 | 24.4k | int32_t valueWidthInt = options & UCPTRIE_OPTIONS_VALUE_BITS_MASK; |
52 | 24.4k | if (typeInt > UCPTRIE_TYPE_SMALL || valueWidthInt > UCPTRIE_VALUE_BITS_8 || |
53 | 24.4k | (options & UCPTRIE_OPTIONS_RESERVED_MASK) != 0) { |
54 | 0 | *pErrorCode = U_INVALID_FORMAT_ERROR; |
55 | 0 | return nullptr; |
56 | 0 | } |
57 | 24.4k | UCPTrieType actualType = (UCPTrieType)typeInt; |
58 | 24.4k | UCPTrieValueWidth actualValueWidth = (UCPTrieValueWidth)valueWidthInt; |
59 | 24.4k | if (type < 0) { |
60 | 9 | type = actualType; |
61 | 9 | } |
62 | 24.4k | if (valueWidth < 0) { |
63 | 24.4k | valueWidth = actualValueWidth; |
64 | 24.4k | } |
65 | 24.4k | if (type != actualType || valueWidth != actualValueWidth) { |
66 | 0 | *pErrorCode = U_INVALID_FORMAT_ERROR; |
67 | 0 | return nullptr; |
68 | 0 | } |
69 | | |
70 | | // Get the length values and offsets. |
71 | 24.4k | UCPTrie tempTrie; |
72 | 24.4k | uprv_memset(&tempTrie, 0, sizeof(tempTrie)); |
73 | 24.4k | tempTrie.indexLength = header->indexLength; |
74 | 24.4k | tempTrie.dataLength = |
75 | 24.4k | ((options & UCPTRIE_OPTIONS_DATA_LENGTH_MASK) << 4) | header->dataLength; |
76 | 24.4k | tempTrie.index3NullOffset = header->index3NullOffset; |
77 | 24.4k | tempTrie.dataNullOffset = |
78 | 24.4k | ((options & UCPTRIE_OPTIONS_DATA_NULL_OFFSET_MASK) << 8) | header->dataNullOffset; |
79 | | |
80 | 24.4k | tempTrie.highStart = header->shiftedHighStart << UCPTRIE_SHIFT_2; |
81 | 24.4k | tempTrie.shifted12HighStart = (tempTrie.highStart + 0xfff) >> 12; |
82 | 24.4k | tempTrie.type = type; |
83 | 24.4k | tempTrie.valueWidth = valueWidth; |
84 | | |
85 | | // Calculate the actual length. |
86 | 24.4k | int32_t actualLength = (int32_t)sizeof(UCPTrieHeader) + tempTrie.indexLength * 2; |
87 | 24.4k | if (valueWidth == UCPTRIE_VALUE_BITS_16) { |
88 | 78 | actualLength += tempTrie.dataLength * 2; |
89 | 24.3k | } else if (valueWidth == UCPTRIE_VALUE_BITS_32) { |
90 | 0 | actualLength += tempTrie.dataLength * 4; |
91 | 24.3k | } else { |
92 | 24.3k | actualLength += tempTrie.dataLength; |
93 | 24.3k | } |
94 | 24.4k | if (length < actualLength) { |
95 | 0 | *pErrorCode = U_INVALID_FORMAT_ERROR; // Not enough bytes. |
96 | 0 | return nullptr; |
97 | 0 | } |
98 | | |
99 | | // Allocate the trie. |
100 | 24.4k | UCPTrie *trie = (UCPTrie *)uprv_malloc(sizeof(UCPTrie)); |
101 | 24.4k | if (trie == nullptr) { |
102 | 0 | *pErrorCode = U_MEMORY_ALLOCATION_ERROR; |
103 | 0 | return nullptr; |
104 | 0 | } |
105 | 24.4k | uprv_memcpy(trie, &tempTrie, sizeof(tempTrie)); |
106 | | #ifdef UCPTRIE_DEBUG |
107 | | trie->name = "fromSerialized"; |
108 | | #endif |
109 | | |
110 | | // Set the pointers to its index and data arrays. |
111 | 24.4k | const uint16_t *p16 = (const uint16_t *)(header + 1); |
112 | 24.4k | trie->index = p16; |
113 | 24.4k | p16 += trie->indexLength; |
114 | | |
115 | | // Get the data. |
116 | 24.4k | int32_t nullValueOffset = trie->dataNullOffset; |
117 | 24.4k | if (nullValueOffset >= trie->dataLength) { |
118 | 0 | nullValueOffset = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET; |
119 | 0 | } |
120 | 24.4k | switch (valueWidth) { |
121 | 78 | case UCPTRIE_VALUE_BITS_16: |
122 | 78 | trie->data.ptr16 = p16; |
123 | 78 | trie->nullValue = trie->data.ptr16[nullValueOffset]; |
124 | 78 | break; |
125 | 0 | case UCPTRIE_VALUE_BITS_32: |
126 | 0 | trie->data.ptr32 = (const uint32_t *)p16; |
127 | 0 | trie->nullValue = trie->data.ptr32[nullValueOffset]; |
128 | 0 | break; |
129 | 24.3k | case UCPTRIE_VALUE_BITS_8: |
130 | 24.3k | trie->data.ptr8 = (const uint8_t *)p16; |
131 | 24.3k | trie->nullValue = trie->data.ptr8[nullValueOffset]; |
132 | 24.3k | break; |
133 | 0 | default: |
134 | | // Unreachable because valueWidth was checked above. |
135 | 0 | *pErrorCode = U_INVALID_FORMAT_ERROR; |
136 | 0 | return nullptr; |
137 | 24.4k | } |
138 | | |
139 | 24.4k | if (pActualLength != nullptr) { |
140 | 0 | *pActualLength = actualLength; |
141 | 0 | } |
142 | 24.4k | return trie; |
143 | 24.4k | } |
144 | | |
145 | | U_CAPI void U_EXPORT2 |
146 | 33.1k | ucptrie_close(UCPTrie *trie) { |
147 | 33.1k | uprv_free(trie); |
148 | 33.1k | } |
149 | | |
150 | | U_CAPI UCPTrieType U_EXPORT2 |
151 | 0 | ucptrie_getType(const UCPTrie *trie) { |
152 | 0 | return (UCPTrieType)trie->type; |
153 | 0 | } |
154 | | |
155 | | U_CAPI UCPTrieValueWidth U_EXPORT2 |
156 | 320M | ucptrie_getValueWidth(const UCPTrie *trie) { |
157 | 320M | return (UCPTrieValueWidth)trie->valueWidth; |
158 | 320M | } |
159 | | |
160 | | U_CAPI int32_t U_EXPORT2 |
161 | 39.2M | ucptrie_internalSmallIndex(const UCPTrie *trie, UChar32 c) { |
162 | 39.2M | int32_t i1 = c >> UCPTRIE_SHIFT_1; |
163 | 39.2M | if (trie->type == UCPTRIE_TYPE_FAST) { |
164 | 26.8M | U_ASSERT(0xffff < c && c < trie->highStart); |
165 | 26.8M | i1 += UCPTRIE_BMP_INDEX_LENGTH - UCPTRIE_OMITTED_BMP_INDEX_1_LENGTH; |
166 | 26.8M | } else { |
167 | 12.3M | U_ASSERT((uint32_t)c < (uint32_t)trie->highStart && trie->highStart > UCPTRIE_SMALL_LIMIT); |
168 | 12.3M | i1 += UCPTRIE_SMALL_INDEX_LENGTH; |
169 | 12.3M | } |
170 | 39.2M | int32_t i3Block = trie->index[ |
171 | 39.2M | (int32_t)trie->index[i1] + ((c >> UCPTRIE_SHIFT_2) & UCPTRIE_INDEX_2_MASK)]; |
172 | 39.2M | int32_t i3 = (c >> UCPTRIE_SHIFT_3) & UCPTRIE_INDEX_3_MASK; |
173 | 39.2M | int32_t dataBlock; |
174 | 39.2M | if ((i3Block & 0x8000) == 0) { |
175 | | // 16-bit indexes |
176 | 39.2M | dataBlock = trie->index[i3Block + i3]; |
177 | 39.2M | } else { |
178 | | // 18-bit indexes stored in groups of 9 entries per 8 indexes. |
179 | 0 | i3Block = (i3Block & 0x7fff) + (i3 & ~7) + (i3 >> 3); |
180 | 0 | i3 &= 7; |
181 | 0 | dataBlock = ((int32_t)trie->index[i3Block++] << (2 + (2 * i3))) & 0x30000; |
182 | 0 | dataBlock |= trie->index[i3Block + i3]; |
183 | 0 | } |
184 | 39.2M | return dataBlock + (c & UCPTRIE_SMALL_DATA_MASK); |
185 | 39.2M | } |
186 | | |
187 | | U_CAPI int32_t U_EXPORT2 |
188 | 0 | ucptrie_internalSmallU8Index(const UCPTrie *trie, int32_t lt1, uint8_t t2, uint8_t t3) { |
189 | 0 | UChar32 c = (lt1 << 12) | (t2 << 6) | t3; |
190 | 0 | if (c >= trie->highStart) { |
191 | | // Possible because the UTF-8 macro compares with shifted12HighStart which may be higher. |
192 | 0 | return trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET; |
193 | 0 | } |
194 | 0 | return ucptrie_internalSmallIndex(trie, c); |
195 | 0 | } |
196 | | |
197 | | U_CAPI int32_t U_EXPORT2 |
198 | | ucptrie_internalU8PrevIndex(const UCPTrie *trie, UChar32 c, |
199 | 0 | const uint8_t *start, const uint8_t *src) { |
200 | 0 | int32_t i, length; |
201 | | // Support 64-bit pointers by avoiding cast of arbitrary difference. |
202 | 0 | if ((src - start) <= 7) { |
203 | 0 | i = length = (int32_t)(src - start); |
204 | 0 | } else { |
205 | 0 | i = length = 7; |
206 | 0 | start = src - 7; |
207 | 0 | } |
208 | 0 | c = utf8_prevCharSafeBody(start, 0, &i, c, -1); |
209 | 0 | i = length - i; // Number of bytes read backward from src. |
210 | 0 | int32_t idx = _UCPTRIE_CP_INDEX(trie, 0xffff, c); |
211 | 0 | return (idx << 3) | i; |
212 | 0 | } |
213 | | |
214 | | namespace { |
215 | | |
216 | 64.9M | inline uint32_t getValue(UCPTrieData data, UCPTrieValueWidth valueWidth, int32_t dataIndex) { |
217 | 64.9M | switch (valueWidth) { |
218 | 1.89M | case UCPTRIE_VALUE_BITS_16: |
219 | 1.89M | return data.ptr16[dataIndex]; |
220 | 20.7M | case UCPTRIE_VALUE_BITS_32: |
221 | 20.7M | return data.ptr32[dataIndex]; |
222 | 42.2M | case UCPTRIE_VALUE_BITS_8: |
223 | 42.2M | return data.ptr8[dataIndex]; |
224 | 0 | default: |
225 | | // Unreachable if the trie is properly initialized. |
226 | 0 | return 0xffffffff; |
227 | 64.9M | } |
228 | 64.9M | } |
229 | | |
230 | | } // namespace |
231 | | |
232 | | U_CAPI uint32_t U_EXPORT2 |
233 | 64.5M | ucptrie_get(const UCPTrie *trie, UChar32 c) { |
234 | 64.5M | int32_t dataIndex; |
235 | 64.5M | if ((uint32_t)c <= 0x7f) { |
236 | | // linear ASCII |
237 | 2.58M | dataIndex = c; |
238 | 61.9M | } else { |
239 | 61.9M | UChar32 fastMax = trie->type == UCPTRIE_TYPE_FAST ? 0xffff : UCPTRIE_SMALL_MAX; |
240 | 61.9M | dataIndex = _UCPTRIE_CP_INDEX(trie, fastMax, c); |
241 | 61.9M | } |
242 | 64.5M | return getValue(trie->data, (UCPTrieValueWidth)trie->valueWidth, dataIndex); |
243 | 64.5M | } |
244 | | |
245 | | namespace { |
246 | | |
247 | | constexpr int32_t MAX_UNICODE = 0x10ffff; |
248 | | |
249 | | inline uint32_t maybeFilterValue(uint32_t value, uint32_t trieNullValue, uint32_t nullValue, |
250 | 64.6k | UCPMapValueFilter *filter, const void *context) { |
251 | 64.6k | if (value == trieNullValue) { |
252 | 8.59k | value = nullValue; |
253 | 56.0k | } else if (filter != nullptr) { |
254 | 1.61k | value = filter(context, value); |
255 | 1.61k | } |
256 | 64.6k | return value; |
257 | 64.6k | } |
258 | | |
259 | | UChar32 getRange(const void *t, UChar32 start, |
260 | 62.3k | UCPMapValueFilter *filter, const void *context, uint32_t *pValue) { |
261 | 62.3k | if (static_cast<uint32_t>(start) > MAX_UNICODE) { |
262 | 21 | return U_SENTINEL; |
263 | 21 | } |
264 | 62.2k | const UCPTrie *trie = reinterpret_cast<const UCPTrie *>(t); |
265 | 62.2k | UCPTrieValueWidth valueWidth = static_cast<UCPTrieValueWidth>(trie->valueWidth); |
266 | 62.2k | if (start >= trie->highStart) { |
267 | 1 | if (pValue != nullptr) { |
268 | 1 | int32_t di = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET; |
269 | 1 | uint32_t value = getValue(trie->data, valueWidth, di); |
270 | 1 | if (filter != nullptr) { value = filter(context, value); } |
271 | 1 | *pValue = value; |
272 | 1 | } |
273 | 1 | return MAX_UNICODE; |
274 | 1 | } |
275 | | |
276 | 62.2k | uint32_t nullValue = trie->nullValue; |
277 | 62.2k | if (filter != nullptr) { nullValue = filter(context, nullValue); } |
278 | 62.2k | const uint16_t *index = trie->index; |
279 | | |
280 | 62.2k | int32_t prevI3Block = -1; |
281 | 62.2k | int32_t prevBlock = -1; |
282 | 62.2k | UChar32 c = start; |
283 | 62.2k | uint32_t trieValue, value = nullValue; |
284 | 62.2k | bool haveValue = false; |
285 | 77.6k | do { |
286 | 77.6k | int32_t i3Block; |
287 | 77.6k | int32_t i3; |
288 | 77.6k | int32_t i3BlockLength; |
289 | 77.6k | int32_t dataBlockLength; |
290 | 77.6k | if (c <= 0xffff && (trie->type == UCPTRIE_TYPE_FAST || c <= UCPTRIE_SMALL_MAX)) { |
291 | 45.4k | i3Block = 0; |
292 | 45.4k | i3 = c >> UCPTRIE_FAST_SHIFT; |
293 | 45.4k | i3BlockLength = trie->type == UCPTRIE_TYPE_FAST ? |
294 | 44.0k | UCPTRIE_BMP_INDEX_LENGTH : UCPTRIE_SMALL_INDEX_LENGTH; |
295 | 45.4k | dataBlockLength = UCPTRIE_FAST_DATA_BLOCK_LENGTH; |
296 | 45.4k | } else { |
297 | | // Use the multi-stage index. |
298 | 32.1k | int32_t i1 = c >> UCPTRIE_SHIFT_1; |
299 | 32.1k | if (trie->type == UCPTRIE_TYPE_FAST) { |
300 | 21.1k | U_ASSERT(0xffff < c && c < trie->highStart); |
301 | 21.1k | i1 += UCPTRIE_BMP_INDEX_LENGTH - UCPTRIE_OMITTED_BMP_INDEX_1_LENGTH; |
302 | 21.1k | } else { |
303 | 11.0k | U_ASSERT(c < trie->highStart && trie->highStart > UCPTRIE_SMALL_LIMIT); |
304 | 11.0k | i1 += UCPTRIE_SMALL_INDEX_LENGTH; |
305 | 11.0k | } |
306 | 32.1k | i3Block = trie->index[ |
307 | 32.1k | static_cast<int32_t>(trie->index[i1]) + ((c >> UCPTRIE_SHIFT_2) & UCPTRIE_INDEX_2_MASK)]; |
308 | 32.1k | if (i3Block == prevI3Block && (c - start) >= UCPTRIE_CP_PER_INDEX_2_ENTRY) { |
309 | | // The index-3 block is the same as the previous one, and filled with value. |
310 | 14.4k | U_ASSERT((c & (UCPTRIE_CP_PER_INDEX_2_ENTRY - 1)) == 0); |
311 | 14.4k | c += UCPTRIE_CP_PER_INDEX_2_ENTRY; |
312 | 14.4k | continue; |
313 | 14.4k | } |
314 | 17.7k | prevI3Block = i3Block; |
315 | 17.7k | if (i3Block == trie->index3NullOffset) { |
316 | | // This is the index-3 null block. |
317 | 237 | if (haveValue) { |
318 | 222 | if (nullValue != value) { |
319 | 15 | return c - 1; |
320 | 15 | } |
321 | 222 | } else { |
322 | 15 | trieValue = trie->nullValue; |
323 | 15 | value = nullValue; |
324 | 15 | if (pValue != nullptr) { *pValue = nullValue; } |
325 | 15 | haveValue = true; |
326 | 15 | } |
327 | 222 | prevBlock = trie->dataNullOffset; |
328 | 222 | c = (c + UCPTRIE_CP_PER_INDEX_2_ENTRY) & ~(UCPTRIE_CP_PER_INDEX_2_ENTRY - 1); |
329 | 222 | continue; |
330 | 237 | } |
331 | 17.5k | i3 = (c >> UCPTRIE_SHIFT_3) & UCPTRIE_INDEX_3_MASK; |
332 | 17.5k | i3BlockLength = UCPTRIE_INDEX_3_BLOCK_LENGTH; |
333 | 17.5k | dataBlockLength = UCPTRIE_SMALL_DATA_BLOCK_LENGTH; |
334 | 17.5k | } |
335 | | // Enumerate data blocks for one index-3 block. |
336 | 100k | do { |
337 | 100k | int32_t block; |
338 | 100k | if ((i3Block & 0x8000) == 0) { |
339 | 100k | block = index[i3Block + i3]; |
340 | 100k | } else { |
341 | | // 18-bit indexes stored in groups of 9 entries per 8 indexes. |
342 | 0 | int32_t group = (i3Block & 0x7fff) + (i3 & ~7) + (i3 >> 3); |
343 | 0 | int32_t gi = i3 & 7; |
344 | 0 | block = (static_cast<int32_t>(index[group++]) << (2 + (2 * gi))) & 0x30000; |
345 | 0 | block |= index[group + gi]; |
346 | 0 | } |
347 | 100k | if (block == prevBlock && (c - start) >= dataBlockLength) { |
348 | | // The block is the same as the previous one, and filled with value. |
349 | 28.8k | U_ASSERT((c & (dataBlockLength - 1)) == 0); |
350 | 28.8k | c += dataBlockLength; |
351 | 72.1k | } else { |
352 | 72.1k | int32_t dataMask = dataBlockLength - 1; |
353 | 72.1k | prevBlock = block; |
354 | 72.1k | if (block == trie->dataNullOffset) { |
355 | | // This is the data null block. |
356 | 2.30k | if (haveValue) { |
357 | 1.99k | if (nullValue != value) { |
358 | 288 | return c - 1; |
359 | 288 | } |
360 | 1.99k | } else { |
361 | 305 | trieValue = trie->nullValue; |
362 | 305 | value = nullValue; |
363 | 305 | if (pValue != nullptr) { *pValue = nullValue; } |
364 | 305 | haveValue = true; |
365 | 305 | } |
366 | 2.01k | c = (c + dataBlockLength) & ~dataMask; |
367 | 69.8k | } else { |
368 | 69.8k | int32_t di = block + (c & dataMask); |
369 | 69.8k | uint32_t trieValue2 = getValue(trie->data, valueWidth, di); |
370 | 69.8k | if (haveValue) { |
371 | 7.84k | if (trieValue2 != trieValue) { |
372 | 2.55k | if (filter == nullptr || |
373 | 2.55k | maybeFilterValue(trieValue2, trie->nullValue, nullValue, |
374 | 2.44k | filter, context) != value) { |
375 | 2.44k | return c - 1; |
376 | 2.44k | } |
377 | 108 | trieValue = trieValue2; // may or may not help |
378 | 108 | } |
379 | 61.9k | } else { |
380 | 61.9k | trieValue = trieValue2; |
381 | 61.9k | value = maybeFilterValue(trieValue2, trie->nullValue, nullValue, |
382 | 61.9k | filter, context); |
383 | 61.9k | if (pValue != nullptr) { *pValue = value; } |
384 | 61.9k | haveValue = true; |
385 | 61.9k | } |
386 | 318k | while ((++c & dataMask) != 0) { |
387 | 310k | trieValue2 = getValue(trie->data, valueWidth, ++di); |
388 | 310k | if (trieValue2 != trieValue) { |
389 | 61.6k | if (filter == nullptr || |
390 | 61.6k | maybeFilterValue(trieValue2, trie->nullValue, nullValue, |
391 | 59.5k | filter, context) != value) { |
392 | 59.5k | return c - 1; |
393 | 59.5k | } |
394 | 2.11k | trieValue = trieValue2; // may or may not help |
395 | 2.11k | } |
396 | 310k | } |
397 | 67.3k | } |
398 | 72.1k | } |
399 | 100k | } while (++i3 < i3BlockLength); |
400 | 63.0k | } while (c < trie->highStart); |
401 | 23 | U_ASSERT(haveValue); |
402 | 23 | int32_t di = trie->dataLength - UCPTRIE_HIGH_VALUE_NEG_DATA_OFFSET; |
403 | 23 | uint32_t highValue = getValue(trie->data, valueWidth, di); |
404 | 23 | if (maybeFilterValue(highValue, trie->nullValue, nullValue, |
405 | 23 | filter, context) != value) { |
406 | 3 | return c - 1; |
407 | 20 | } else { |
408 | 20 | return MAX_UNICODE; |
409 | 20 | } |
410 | 23 | } |
411 | | |
412 | | } // namespace |
413 | | |
414 | | U_CFUNC UChar32 |
415 | | ucptrie_internalGetRange(UCPTrieGetRange *getRange, |
416 | | const void *trie, UChar32 start, |
417 | | UCPMapRangeOption option, uint32_t surrogateValue, |
418 | 62.2k | UCPMapValueFilter *filter, const void *context, uint32_t *pValue) { |
419 | 62.2k | if (option == UCPMAP_RANGE_NORMAL) { |
420 | 5.86k | return getRange(trie, start, filter, context, pValue); |
421 | 5.86k | } |
422 | 56.4k | uint32_t value; |
423 | 56.4k | if (pValue == nullptr) { |
424 | | // We need to examine the range value even if the caller does not want it. |
425 | 0 | pValue = &value; |
426 | 0 | } |
427 | 56.4k | UChar32 surrEnd = option == UCPMAP_RANGE_FIXED_ALL_SURROGATES ? 0xdfff : 0xdbff; |
428 | 56.4k | UChar32 end = getRange(trie, start, filter, context, pValue); |
429 | 56.4k | if (end < 0xd7ff || start > surrEnd) { |
430 | 56.4k | return end; |
431 | 56.4k | } |
432 | | // The range overlaps with surrogates, or ends just before the first one. |
433 | 12 | if (*pValue == surrogateValue) { |
434 | 12 | if (end >= surrEnd) { |
435 | | // Surrogates followed by a non-surrogateValue range, |
436 | | // or surrogates are part of a larger surrogateValue range. |
437 | 0 | return end; |
438 | 0 | } |
439 | 12 | } else { |
440 | 0 | if (start <= 0xd7ff) { |
441 | 0 | return 0xd7ff; // Non-surrogateValue range ends before surrogateValue surrogates. |
442 | 0 | } |
443 | | // Start is a surrogate with a non-surrogateValue code *unit* value. |
444 | | // Return a surrogateValue code *point* range. |
445 | 0 | *pValue = surrogateValue; |
446 | 0 | if (end > surrEnd) { |
447 | 0 | return surrEnd; // Surrogate range ends before non-surrogateValue rest of range. |
448 | 0 | } |
449 | 0 | } |
450 | | // See if the surrogateValue surrogate range can be merged with |
451 | | // an immediately following range. |
452 | 12 | uint32_t value2; |
453 | 12 | UChar32 end2 = getRange(trie, surrEnd + 1, filter, context, &value2); |
454 | 12 | if (value2 == surrogateValue) { |
455 | 12 | return end2; |
456 | 12 | } |
457 | 0 | return surrEnd; |
458 | 12 | } |
459 | | |
460 | | U_CAPI UChar32 U_EXPORT2 |
461 | | ucptrie_getRange(const UCPTrie *trie, UChar32 start, |
462 | | UCPMapRangeOption option, uint32_t surrogateValue, |
463 | 62.2k | UCPMapValueFilter *filter, const void *context, uint32_t *pValue) { |
464 | 62.2k | return ucptrie_internalGetRange(getRange, trie, start, |
465 | 62.2k | option, surrogateValue, |
466 | 62.2k | filter, context, pValue); |
467 | 62.2k | } |
468 | | |
469 | | U_CAPI int32_t U_EXPORT2 |
470 | | ucptrie_toBinary(const UCPTrie *trie, |
471 | | void *data, int32_t capacity, |
472 | 5.50k | UErrorCode *pErrorCode) { |
473 | 5.50k | if (U_FAILURE(*pErrorCode)) { |
474 | 0 | return 0; |
475 | 0 | } |
476 | | |
477 | 5.50k | UCPTrieType type = (UCPTrieType)trie->type; |
478 | 5.50k | UCPTrieValueWidth valueWidth = (UCPTrieValueWidth)trie->valueWidth; |
479 | 5.50k | if (type < UCPTRIE_TYPE_FAST || UCPTRIE_TYPE_SMALL < type || |
480 | 5.50k | valueWidth < UCPTRIE_VALUE_BITS_16 || UCPTRIE_VALUE_BITS_8 < valueWidth || |
481 | 5.50k | capacity < 0 || |
482 | 5.50k | (capacity > 0 && (data == nullptr || (U_POINTER_MASK_LSB(data, 3) != 0)))) { |
483 | 0 | *pErrorCode = U_ILLEGAL_ARGUMENT_ERROR; |
484 | 0 | return 0; |
485 | 0 | } |
486 | | |
487 | 5.50k | int32_t length = (int32_t)sizeof(UCPTrieHeader) + trie->indexLength * 2; |
488 | 5.50k | switch (valueWidth) { |
489 | 140 | case UCPTRIE_VALUE_BITS_16: |
490 | 140 | length += trie->dataLength * 2; |
491 | 140 | break; |
492 | 0 | case UCPTRIE_VALUE_BITS_32: |
493 | 0 | length += trie->dataLength * 4; |
494 | 0 | break; |
495 | 5.36k | case UCPTRIE_VALUE_BITS_8: |
496 | 5.36k | length += trie->dataLength; |
497 | 5.36k | break; |
498 | 0 | default: |
499 | | // unreachable |
500 | 0 | break; |
501 | 5.50k | } |
502 | 5.50k | if (capacity < length) { |
503 | 2.75k | *pErrorCode = U_BUFFER_OVERFLOW_ERROR; |
504 | 2.75k | return length; |
505 | 2.75k | } |
506 | | |
507 | 2.75k | char *bytes = (char *)data; |
508 | 2.75k | UCPTrieHeader *header = (UCPTrieHeader *)bytes; |
509 | 2.75k | header->signature = UCPTRIE_SIG; // "Tri3" |
510 | 2.75k | header->options = (uint16_t)( |
511 | 2.75k | ((trie->dataLength & 0xf0000) >> 4) | |
512 | 2.75k | ((trie->dataNullOffset & 0xf0000) >> 8) | |
513 | 2.75k | (trie->type << 6) | |
514 | 2.75k | valueWidth); |
515 | 2.75k | header->indexLength = (uint16_t)trie->indexLength; |
516 | 2.75k | header->dataLength = (uint16_t)trie->dataLength; |
517 | 2.75k | header->index3NullOffset = trie->index3NullOffset; |
518 | 2.75k | header->dataNullOffset = (uint16_t)trie->dataNullOffset; |
519 | 2.75k | header->shiftedHighStart = trie->highStart >> UCPTRIE_SHIFT_2; |
520 | 2.75k | bytes += sizeof(UCPTrieHeader); |
521 | | |
522 | 2.75k | uprv_memcpy(bytes, trie->index, trie->indexLength * 2); |
523 | 2.75k | bytes += trie->indexLength * 2; |
524 | | |
525 | 2.75k | switch (valueWidth) { |
526 | 70 | case UCPTRIE_VALUE_BITS_16: |
527 | 70 | uprv_memcpy(bytes, trie->data.ptr16, trie->dataLength * 2); |
528 | 70 | break; |
529 | 0 | case UCPTRIE_VALUE_BITS_32: |
530 | 0 | uprv_memcpy(bytes, trie->data.ptr32, trie->dataLength * 4); |
531 | 0 | break; |
532 | 2.68k | case UCPTRIE_VALUE_BITS_8: |
533 | 2.68k | uprv_memcpy(bytes, trie->data.ptr8, trie->dataLength); |
534 | 2.68k | break; |
535 | 0 | default: |
536 | | // unreachable |
537 | 0 | break; |
538 | 2.75k | } |
539 | 2.75k | return length; |
540 | 2.75k | } |
541 | | |
542 | | namespace { |
543 | | |
544 | | #ifdef UCPTRIE_DEBUG |
545 | | long countNull(const UCPTrie *trie) { |
546 | | uint32_t nullValue=trie->nullValue; |
547 | | int32_t length=trie->dataLength; |
548 | | long count=0; |
549 | | switch (trie->valueWidth) { |
550 | | case UCPTRIE_VALUE_BITS_16: |
551 | | for(int32_t i=0; i<length; ++i) { |
552 | | if(trie->data.ptr16[i]==nullValue) { ++count; } |
553 | | } |
554 | | break; |
555 | | case UCPTRIE_VALUE_BITS_32: |
556 | | for(int32_t i=0; i<length; ++i) { |
557 | | if(trie->data.ptr32[i]==nullValue) { ++count; } |
558 | | } |
559 | | break; |
560 | | case UCPTRIE_VALUE_BITS_8: |
561 | | for(int32_t i=0; i<length; ++i) { |
562 | | if(trie->data.ptr8[i]==nullValue) { ++count; } |
563 | | } |
564 | | break; |
565 | | default: |
566 | | // unreachable |
567 | | break; |
568 | | } |
569 | | return count; |
570 | | } |
571 | | |
572 | | U_CFUNC void |
573 | | ucptrie_printLengths(const UCPTrie *trie, const char *which) { |
574 | | long indexLength=trie->indexLength; |
575 | | long dataLength=(long)trie->dataLength; |
576 | | long totalLength=(long)sizeof(UCPTrieHeader)+indexLength*2+ |
577 | | dataLength*(trie->valueWidth==UCPTRIE_VALUE_BITS_16 ? 2 : |
578 | | trie->valueWidth==UCPTRIE_VALUE_BITS_32 ? 4 : 1); |
579 | | printf("**UCPTrieLengths(%s %s)** index:%6ld data:%6ld countNull:%6ld serialized:%6ld\n", |
580 | | which, trie->name, indexLength, dataLength, countNull(trie), totalLength); |
581 | | } |
582 | | #endif |
583 | | |
584 | | } // namespace |
585 | | |
586 | | // UCPMap ---- |
587 | | // Initially, this is the same as UCPTrie. This may well change. |
588 | | |
589 | | U_CAPI uint32_t U_EXPORT2 |
590 | 0 | ucpmap_get(const UCPMap *map, UChar32 c) { |
591 | 0 | return ucptrie_get(reinterpret_cast<const UCPTrie *>(map), c); |
592 | 0 | } |
593 | | |
594 | | U_CAPI UChar32 U_EXPORT2 |
595 | | ucpmap_getRange(const UCPMap *map, UChar32 start, |
596 | | UCPMapRangeOption option, uint32_t surrogateValue, |
597 | 0 | UCPMapValueFilter *filter, const void *context, uint32_t *pValue) { |
598 | 0 | return ucptrie_getRange(reinterpret_cast<const UCPTrie *>(map), start, |
599 | 0 | option, surrogateValue, |
600 | 0 | filter, context, pValue); |
601 | 0 | } |