1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 ******************************************************************************
5 *
6 * Copyright (C) 2001-2012, International Business Machines
7 * Corporation and others. All Rights Reserved.
8 *
9 ******************************************************************************
10 * file name: utrie.cpp
11 * encoding: UTF-8
12 * tab size: 8 (not used)
13 * indentation:4
14 *
15 * created on: 2001oct20
16 * created by: Markus W. Scherer
17 *
18 * This is a common implementation of a "folded" trie.
19 * It is a kind of compressed, serializable table of 16- or 32-bit values associated with
20 * Unicode code points (0..0x10ffff).
21 */
22
23 #ifdef UTRIE_DEBUG
24 # include <stdio.h>
25 #endif
26
27 #include "unicode/utypes.h"
28 #include "cmemory.h"
29 #include "utrie.h"
30
31 /* miscellaneous ------------------------------------------------------------ */
32
33 #undef ABS
34 #define ABS(x) ((x)>=0 ? (x) : -(x))
35
36 static inline UBool
equal_uint32(const uint32_t * s,const uint32_t * t,int32_t length)37 equal_uint32(const uint32_t *s, const uint32_t *t, int32_t length) {
38 while(length>0 && *s==*t) {
39 ++s;
40 ++t;
41 --length;
42 }
43 return (UBool)(length==0);
44 }
45
46 /* Building a trie ----------------------------------------------------------*/
47
48 U_CAPI UNewTrie * U_EXPORT2
utrie_open(UNewTrie * fillIn,uint32_t * aliasData,int32_t maxDataLength,uint32_t initialValue,uint32_t leadUnitValue,UBool latin1Linear)49 utrie_open(UNewTrie *fillIn,
50 uint32_t *aliasData, int32_t maxDataLength,
51 uint32_t initialValue, uint32_t leadUnitValue,
52 UBool latin1Linear) {
53 UNewTrie *trie;
54 int32_t i, j;
55
56 if( maxDataLength<UTRIE_DATA_BLOCK_LENGTH ||
57 (latin1Linear && maxDataLength<1024)
58 ) {
59 return NULL;
60 }
61
62 if(fillIn!=NULL) {
63 trie=fillIn;
64 } else {
65 trie=(UNewTrie *)uprv_malloc(sizeof(UNewTrie));
66 if(trie==NULL) {
67 return NULL;
68 }
69 }
70 uprv_memset(trie, 0, sizeof(UNewTrie));
71 trie->isAllocated= (UBool)(fillIn==NULL);
72
73 if(aliasData!=NULL) {
74 trie->data=aliasData;
75 trie->isDataAllocated=FALSE;
76 } else {
77 trie->data=(uint32_t *)uprv_malloc(maxDataLength*4);
78 if(trie->data==NULL) {
79 uprv_free(trie);
80 return NULL;
81 }
82 trie->isDataAllocated=TRUE;
83 }
84
85 /* preallocate and reset the first data block (block index 0) */
86 j=UTRIE_DATA_BLOCK_LENGTH;
87
88 if(latin1Linear) {
89 /* preallocate and reset the first block (number 0) and Latin-1 (U+0000..U+00ff) after that */
90 /* made sure above that maxDataLength>=1024 */
91
92 /* set indexes to point to consecutive data blocks */
93 i=0;
94 do {
95 /* do this at least for trie->index[0] even if that block is only partly used for Latin-1 */
96 trie->index[i++]=j;
97 j+=UTRIE_DATA_BLOCK_LENGTH;
98 } while(i<(256>>UTRIE_SHIFT));
99 }
100
101 /* reset the initially allocated blocks to the initial value */
102 trie->dataLength=j;
103 while(j>0) {
104 trie->data[--j]=initialValue;
105 }
106
107 trie->leadUnitValue=leadUnitValue;
108 trie->indexLength=UTRIE_MAX_INDEX_LENGTH;
109 trie->dataCapacity=maxDataLength;
110 trie->isLatin1Linear=latin1Linear;
111 trie->isCompacted=FALSE;
112 return trie;
113 }
114
115 U_CAPI UNewTrie * U_EXPORT2
utrie_clone(UNewTrie * fillIn,const UNewTrie * other,uint32_t * aliasData,int32_t aliasDataCapacity)116 utrie_clone(UNewTrie *fillIn, const UNewTrie *other, uint32_t *aliasData, int32_t aliasDataCapacity) {
117 UNewTrie *trie;
118 UBool isDataAllocated;
119
120 /* do not clone if other is not valid or already compacted */
121 if(other==NULL || other->data==NULL || other->isCompacted) {
122 return NULL;
123 }
124
125 /* clone data */
126 if(aliasData!=NULL && aliasDataCapacity>=other->dataCapacity) {
127 isDataAllocated=FALSE;
128 } else {
129 aliasDataCapacity=other->dataCapacity;
130 aliasData=(uint32_t *)uprv_malloc(other->dataCapacity*4);
131 if(aliasData==NULL) {
132 return NULL;
133 }
134 isDataAllocated=TRUE;
135 }
136
137 trie=utrie_open(fillIn, aliasData, aliasDataCapacity,
138 other->data[0], other->leadUnitValue,
139 other->isLatin1Linear);
140 if(trie==NULL) {
141 uprv_free(aliasData);
142 } else {
143 uprv_memcpy(trie->index, other->index, sizeof(trie->index));
144 uprv_memcpy(trie->data, other->data, (size_t)other->dataLength*4);
145 trie->dataLength=other->dataLength;
146 trie->isDataAllocated=isDataAllocated;
147 }
148
149 return trie;
150 }
151
152 U_CAPI void U_EXPORT2
utrie_close(UNewTrie * trie)153 utrie_close(UNewTrie *trie) {
154 if(trie!=NULL) {
155 if(trie->isDataAllocated) {
156 uprv_free(trie->data);
157 trie->data=NULL;
158 }
159 if(trie->isAllocated) {
160 uprv_free(trie);
161 }
162 }
163 }
164
165 U_CAPI uint32_t * U_EXPORT2
utrie_getData(UNewTrie * trie,int32_t * pLength)166 utrie_getData(UNewTrie *trie, int32_t *pLength) {
167 if(trie==NULL || pLength==NULL) {
168 return NULL;
169 }
170
171 *pLength=trie->dataLength;
172 return trie->data;
173 }
174
175 static int32_t
utrie_allocDataBlock(UNewTrie * trie)176 utrie_allocDataBlock(UNewTrie *trie) {
177 int32_t newBlock, newTop;
178
179 newBlock=trie->dataLength;
180 newTop=newBlock+UTRIE_DATA_BLOCK_LENGTH;
181 if(newTop>trie->dataCapacity) {
182 /* out of memory in the data array */
183 return -1;
184 }
185 trie->dataLength=newTop;
186 return newBlock;
187 }
188
189 /**
190 * No error checking for illegal arguments.
191 *
192 * @return -1 if no new data block available (out of memory in data array)
193 * @internal
194 */
195 static int32_t
utrie_getDataBlock(UNewTrie * trie,UChar32 c)196 utrie_getDataBlock(UNewTrie *trie, UChar32 c) {
197 int32_t indexValue, newBlock;
198
199 c>>=UTRIE_SHIFT;
200 indexValue=trie->index[c];
201 if(indexValue>0) {
202 return indexValue;
203 }
204
205 /* allocate a new data block */
206 newBlock=utrie_allocDataBlock(trie);
207 if(newBlock<0) {
208 /* out of memory in the data array */
209 return -1;
210 }
211 trie->index[c]=newBlock;
212
213 /* copy-on-write for a block from a setRange() */
214 uprv_memcpy(trie->data+newBlock, trie->data-indexValue, 4*UTRIE_DATA_BLOCK_LENGTH);
215 return newBlock;
216 }
217
218 /**
219 * @return TRUE if the value was successfully set
220 */
221 U_CAPI UBool U_EXPORT2
utrie_set32(UNewTrie * trie,UChar32 c,uint32_t value)222 utrie_set32(UNewTrie *trie, UChar32 c, uint32_t value) {
223 int32_t block;
224
225 /* valid, uncompacted trie and valid c? */
226 if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) {
227 return FALSE;
228 }
229
230 block=utrie_getDataBlock(trie, c);
231 if(block<0) {
232 return FALSE;
233 }
234
235 trie->data[block+(c&UTRIE_MASK)]=value;
236 return TRUE;
237 }
238
239 U_CAPI uint32_t U_EXPORT2
utrie_get32(UNewTrie * trie,UChar32 c,UBool * pInBlockZero)240 utrie_get32(UNewTrie *trie, UChar32 c, UBool *pInBlockZero) {
241 int32_t block;
242
243 /* valid, uncompacted trie and valid c? */
244 if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) {
245 if(pInBlockZero!=NULL) {
246 *pInBlockZero=TRUE;
247 }
248 return 0;
249 }
250
251 block=trie->index[c>>UTRIE_SHIFT];
252 if(pInBlockZero!=NULL) {
253 *pInBlockZero= (UBool)(block==0);
254 }
255
256 return trie->data[ABS(block)+(c&UTRIE_MASK)];
257 }
258
259 /**
260 * @internal
261 */
262 static void
utrie_fillBlock(uint32_t * block,UChar32 start,UChar32 limit,uint32_t value,uint32_t initialValue,UBool overwrite)263 utrie_fillBlock(uint32_t *block, UChar32 start, UChar32 limit,
264 uint32_t value, uint32_t initialValue, UBool overwrite) {
265 uint32_t *pLimit;
266
267 pLimit=block+limit;
268 block+=start;
269 if(overwrite) {
270 while(block<pLimit) {
271 *block++=value;
272 }
273 } else {
274 while(block<pLimit) {
275 if(*block==initialValue) {
276 *block=value;
277 }
278 ++block;
279 }
280 }
281 }
282
283 U_CAPI UBool U_EXPORT2
utrie_setRange32(UNewTrie * trie,UChar32 start,UChar32 limit,uint32_t value,UBool overwrite)284 utrie_setRange32(UNewTrie *trie, UChar32 start, UChar32 limit, uint32_t value, UBool overwrite) {
285 /*
286 * repeat value in [start..limit[
287 * mark index values for repeat-data blocks by setting bit 31 of the index values
288 * fill around existing values if any, if(overwrite)
289 */
290 uint32_t initialValue;
291 int32_t block, rest, repeatBlock;
292
293 /* valid, uncompacted trie and valid indexes? */
294 if( trie==NULL || trie->isCompacted ||
295 (uint32_t)start>0x10ffff || (uint32_t)limit>0x110000 || start>limit
296 ) {
297 return FALSE;
298 }
299 if(start==limit) {
300 return TRUE; /* nothing to do */
301 }
302
303 initialValue=trie->data[0];
304 if(start&UTRIE_MASK) {
305 UChar32 nextStart;
306
307 /* set partial block at [start..following block boundary[ */
308 block=utrie_getDataBlock(trie, start);
309 if(block<0) {
310 return FALSE;
311 }
312
313 nextStart=(start+UTRIE_DATA_BLOCK_LENGTH)&~UTRIE_MASK;
314 if(nextStart<=limit) {
315 utrie_fillBlock(trie->data+block, start&UTRIE_MASK, UTRIE_DATA_BLOCK_LENGTH,
316 value, initialValue, overwrite);
317 start=nextStart;
318 } else {
319 utrie_fillBlock(trie->data+block, start&UTRIE_MASK, limit&UTRIE_MASK,
320 value, initialValue, overwrite);
321 return TRUE;
322 }
323 }
324
325 /* number of positions in the last, partial block */
326 rest=limit&UTRIE_MASK;
327
328 /* round down limit to a block boundary */
329 limit&=~UTRIE_MASK;
330
331 /* iterate over all-value blocks */
332 if(value==initialValue) {
333 repeatBlock=0;
334 } else {
335 repeatBlock=-1;
336 }
337 while(start<limit) {
338 /* get index value */
339 block=trie->index[start>>UTRIE_SHIFT];
340 if(block>0) {
341 /* already allocated, fill in value */
342 utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, overwrite);
343 } else if(trie->data[-block]!=value && (block==0 || overwrite)) {
344 /* set the repeatBlock instead of the current block 0 or range block */
345 if(repeatBlock>=0) {
346 trie->index[start>>UTRIE_SHIFT]=-repeatBlock;
347 } else {
348 /* create and set and fill the repeatBlock */
349 repeatBlock=utrie_getDataBlock(trie, start);
350 if(repeatBlock<0) {
351 return FALSE;
352 }
353
354 /* set the negative block number to indicate that it is a repeat block */
355 trie->index[start>>UTRIE_SHIFT]=-repeatBlock;
356 utrie_fillBlock(trie->data+repeatBlock, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, TRUE);
357 }
358 }
359
360 start+=UTRIE_DATA_BLOCK_LENGTH;
361 }
362
363 if(rest>0) {
364 /* set partial block at [last block boundary..limit[ */
365 block=utrie_getDataBlock(trie, start);
366 if(block<0) {
367 return FALSE;
368 }
369
370 utrie_fillBlock(trie->data+block, 0, rest, value, initialValue, overwrite);
371 }
372
373 return TRUE;
374 }
375
376 static int32_t
_findSameIndexBlock(const int32_t * idx,int32_t indexLength,int32_t otherBlock)377 _findSameIndexBlock(const int32_t *idx, int32_t indexLength,
378 int32_t otherBlock) {
379 int32_t block, i;
380
381 for(block=UTRIE_BMP_INDEX_LENGTH; block<indexLength; block+=UTRIE_SURROGATE_BLOCK_COUNT) {
382 for(i=0; i<UTRIE_SURROGATE_BLOCK_COUNT; ++i) {
383 if(idx[block+i]!=idx[otherBlock+i]) {
384 break;
385 }
386 }
387 if(i==UTRIE_SURROGATE_BLOCK_COUNT) {
388 return block;
389 }
390 }
391 return indexLength;
392 }
393
394 /*
395 * Fold the normalization data for supplementary code points into
396 * a compact area on top of the BMP-part of the trie index,
397 * with the lead surrogates indexing this compact area.
398 *
399 * Duplicate the index values for lead surrogates:
400 * From inside the BMP area, where some may be overridden with folded values,
401 * to just after the BMP area, where they can be retrieved for
402 * code point lookups.
403 */
404 static void
utrie_fold(UNewTrie * trie,UNewTrieGetFoldedValue * getFoldedValue,UErrorCode * pErrorCode)405 utrie_fold(UNewTrie *trie, UNewTrieGetFoldedValue *getFoldedValue, UErrorCode *pErrorCode) {
406 int32_t leadIndexes[UTRIE_SURROGATE_BLOCK_COUNT];
407 int32_t *idx;
408 uint32_t value;
409 UChar32 c;
410 int32_t indexLength, block;
411 #ifdef UTRIE_DEBUG
412 int countLeadCUWithData=0;
413 #endif
414
415 idx=trie->index;
416
417 /* copy the lead surrogate indexes into a temporary array */
418 uprv_memcpy(leadIndexes, idx+(0xd800>>UTRIE_SHIFT), 4*UTRIE_SURROGATE_BLOCK_COUNT);
419
420 /*
421 * set all values for lead surrogate code *units* to leadUnitValue
422 * so that, by default, runtime lookups will find no data for associated
423 * supplementary code points, unless there is data for such code points
424 * which will result in a non-zero folding value below that is set for
425 * the respective lead units
426 *
427 * the above saved the indexes for surrogate code *points*
428 * fill the indexes with simplified code from utrie_setRange32()
429 */
430 if(trie->leadUnitValue==trie->data[0]) {
431 block=0; /* leadUnitValue==initialValue, use all-initial-value block */
432 } else {
433 /* create and fill the repeatBlock */
434 block=utrie_allocDataBlock(trie);
435 if(block<0) {
436 /* data table overflow */
437 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
438 return;
439 }
440 utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, trie->leadUnitValue, trie->data[0], TRUE);
441 block=-block; /* negative block number to indicate that it is a repeat block */
442 }
443 for(c=(0xd800>>UTRIE_SHIFT); c<(0xdc00>>UTRIE_SHIFT); ++c) {
444 trie->index[c]=block;
445 }
446
447 /*
448 * Fold significant index values into the area just after the BMP indexes.
449 * In case the first lead surrogate has significant data,
450 * its index block must be used first (in which case the folding is a no-op).
451 * Later all folded index blocks are moved up one to insert the copied
452 * lead surrogate indexes.
453 */
454 indexLength=UTRIE_BMP_INDEX_LENGTH;
455
456 /* search for any index (stage 1) entries for supplementary code points */
457 for(c=0x10000; c<0x110000;) {
458 if(idx[c>>UTRIE_SHIFT]!=0) {
459 /* there is data, treat the full block for a lead surrogate */
460 c&=~0x3ff;
461
462 #ifdef UTRIE_DEBUG
463 ++countLeadCUWithData;
464 /* printf("supplementary data for lead surrogate U+%04lx\n", (long)(0xd7c0+(c>>10))); */
465 #endif
466
467 /* is there an identical index block? */
468 block=_findSameIndexBlock(idx, indexLength, c>>UTRIE_SHIFT);
469
470 /*
471 * get a folded value for [c..c+0x400[ and,
472 * if different from the value for the lead surrogate code point,
473 * set it for the lead surrogate code unit
474 */
475 value=getFoldedValue(trie, c, block+UTRIE_SURROGATE_BLOCK_COUNT);
476 if(value!=utrie_get32(trie, U16_LEAD(c), NULL)) {
477 if(!utrie_set32(trie, U16_LEAD(c), value)) {
478 /* data table overflow */
479 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
480 return;
481 }
482
483 /* if we did not find an identical index block... */
484 if(block==indexLength) {
485 /* move the actual index (stage 1) entries from the supplementary position to the new one */
486 uprv_memmove(idx+indexLength,
487 idx+(c>>UTRIE_SHIFT),
488 4*UTRIE_SURROGATE_BLOCK_COUNT);
489 indexLength+=UTRIE_SURROGATE_BLOCK_COUNT;
490 }
491 }
492 c+=0x400;
493 } else {
494 c+=UTRIE_DATA_BLOCK_LENGTH;
495 }
496 }
497 #ifdef UTRIE_DEBUG
498 if(countLeadCUWithData>0) {
499 printf("supplementary data for %d lead surrogates\n", countLeadCUWithData);
500 }
501 #endif
502
503 /*
504 * index array overflow?
505 * This is to guarantee that a folding offset is of the form
506 * UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT with n=0..1023.
507 * If the index is too large, then n>=1024 and more than 10 bits are necessary.
508 *
509 * In fact, it can only ever become n==1024 with completely unfoldable data and
510 * the additional block of duplicated values for lead surrogates.
511 */
512 if(indexLength>=UTRIE_MAX_INDEX_LENGTH) {
513 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
514 return;
515 }
516
517 /*
518 * make space for the lead surrogate index block and
519 * insert it between the BMP indexes and the folded ones
520 */
521 uprv_memmove(idx+UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT,
522 idx+UTRIE_BMP_INDEX_LENGTH,
523 4*(indexLength-UTRIE_BMP_INDEX_LENGTH));
524 uprv_memcpy(idx+UTRIE_BMP_INDEX_LENGTH,
525 leadIndexes,
526 4*UTRIE_SURROGATE_BLOCK_COUNT);
527 indexLength+=UTRIE_SURROGATE_BLOCK_COUNT;
528
529 #ifdef UTRIE_DEBUG
530 printf("trie index count: BMP %ld all Unicode %ld folded %ld\n",
531 UTRIE_BMP_INDEX_LENGTH, (long)UTRIE_MAX_INDEX_LENGTH, indexLength);
532 #endif
533
534 trie->indexLength=indexLength;
535 }
536
537 /*
538 * Set a value in the trie index map to indicate which data block
539 * is referenced and which one is not.
540 * utrie_compact() will remove data blocks that are not used at all.
541 * Set
542 * - 0 if it is used
543 * - -1 if it is not used
544 */
545 static void
_findUnusedBlocks(UNewTrie * trie)546 _findUnusedBlocks(UNewTrie *trie) {
547 int32_t i;
548
549 /* fill the entire map with "not used" */
550 uprv_memset(trie->map, 0xff, (UTRIE_MAX_BUILD_TIME_DATA_LENGTH>>UTRIE_SHIFT)*4);
551
552 /* mark each block that _is_ used with 0 */
553 for(i=0; i<trie->indexLength; ++i) {
554 trie->map[ABS(trie->index[i])>>UTRIE_SHIFT]=0;
555 }
556
557 /* never move the all-initial-value block 0 */
558 trie->map[0]=0;
559 }
560
561 static int32_t
_findSameDataBlock(const uint32_t * data,int32_t dataLength,int32_t otherBlock,int32_t step)562 _findSameDataBlock(const uint32_t *data, int32_t dataLength,
563 int32_t otherBlock, int32_t step) {
564 int32_t block;
565
566 /* ensure that we do not even partially get past dataLength */
567 dataLength-=UTRIE_DATA_BLOCK_LENGTH;
568
569 for(block=0; block<=dataLength; block+=step) {
570 if(equal_uint32(data+block, data+otherBlock, UTRIE_DATA_BLOCK_LENGTH)) {
571 return block;
572 }
573 }
574 return -1;
575 }
576
577 /*
578 * Compact a folded build-time trie.
579 *
580 * The compaction
581 * - removes blocks that are identical with earlier ones
582 * - overlaps adjacent blocks as much as possible (if overlap==TRUE)
583 * - moves blocks in steps of the data granularity
584 * - moves and overlaps blocks that overlap with multiple values in the overlap region
585 *
586 * It does not
587 * - try to move and overlap blocks that are not already adjacent
588 */
589 static void
utrie_compact(UNewTrie * trie,UBool overlap,UErrorCode * pErrorCode)590 utrie_compact(UNewTrie *trie, UBool overlap, UErrorCode *pErrorCode) {
591 int32_t i, start, newStart, overlapStart;
592
593 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
594 return;
595 }
596
597 /* valid, uncompacted trie? */
598 if(trie==NULL) {
599 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
600 return;
601 }
602 if(trie->isCompacted) {
603 return; /* nothing left to do */
604 }
605
606 /* compaction */
607
608 /* initialize the index map with "block is used/unused" flags */
609 _findUnusedBlocks(trie);
610
611 /* if Latin-1 is preallocated and linear, then do not compact Latin-1 data */
612 if(trie->isLatin1Linear && UTRIE_SHIFT<=8) {
613 overlapStart=UTRIE_DATA_BLOCK_LENGTH+256;
614 } else {
615 overlapStart=UTRIE_DATA_BLOCK_LENGTH;
616 }
617
618 newStart=UTRIE_DATA_BLOCK_LENGTH;
619 for(start=newStart; start<trie->dataLength;) {
620 /*
621 * start: index of first entry of current block
622 * newStart: index where the current block is to be moved
623 * (right after current end of already-compacted data)
624 */
625
626 /* skip blocks that are not used */
627 if(trie->map[start>>UTRIE_SHIFT]<0) {
628 /* advance start to the next block */
629 start+=UTRIE_DATA_BLOCK_LENGTH;
630
631 /* leave newStart with the previous block! */
632 continue;
633 }
634
635 /* search for an identical block */
636 if( start>=overlapStart &&
637 (i=_findSameDataBlock(trie->data, newStart, start,
638 overlap ? UTRIE_DATA_GRANULARITY : UTRIE_DATA_BLOCK_LENGTH))
639 >=0
640 ) {
641 /* found an identical block, set the other block's index value for the current block */
642 trie->map[start>>UTRIE_SHIFT]=i;
643
644 /* advance start to the next block */
645 start+=UTRIE_DATA_BLOCK_LENGTH;
646
647 /* leave newStart with the previous block! */
648 continue;
649 }
650
651 /* see if the beginning of this block can be overlapped with the end of the previous block */
652 if(overlap && start>=overlapStart) {
653 /* look for maximum overlap (modulo granularity) with the previous, adjacent block */
654 for(i=UTRIE_DATA_BLOCK_LENGTH-UTRIE_DATA_GRANULARITY;
655 i>0 && !equal_uint32(trie->data+(newStart-i), trie->data+start, i);
656 i-=UTRIE_DATA_GRANULARITY) {}
657 } else {
658 i=0;
659 }
660
661 if(i>0) {
662 /* some overlap */
663 trie->map[start>>UTRIE_SHIFT]=newStart-i;
664
665 /* move the non-overlapping indexes to their new positions */
666 start+=i;
667 for(i=UTRIE_DATA_BLOCK_LENGTH-i; i>0; --i) {
668 trie->data[newStart++]=trie->data[start++];
669 }
670 } else if(newStart<start) {
671 /* no overlap, just move the indexes to their new positions */
672 trie->map[start>>UTRIE_SHIFT]=newStart;
673 for(i=UTRIE_DATA_BLOCK_LENGTH; i>0; --i) {
674 trie->data[newStart++]=trie->data[start++];
675 }
676 } else /* no overlap && newStart==start */ {
677 trie->map[start>>UTRIE_SHIFT]=start;
678 newStart+=UTRIE_DATA_BLOCK_LENGTH;
679 start=newStart;
680 }
681 }
682
683 /* now adjust the index (stage 1) table */
684 for(i=0; i<trie->indexLength; ++i) {
685 trie->index[i]=trie->map[ABS(trie->index[i])>>UTRIE_SHIFT];
686 }
687
688 #ifdef UTRIE_DEBUG
689 /* we saved some space */
690 printf("compacting trie: count of 32-bit words %lu->%lu\n",
691 (long)trie->dataLength, (long)newStart);
692 #endif
693
694 trie->dataLength=newStart;
695 }
696
697 /* serialization ------------------------------------------------------------ */
698
699 /*
700 * Default function for the folding value:
701 * Just store the offset (16 bits) if there is any non-initial-value entry.
702 *
703 * The offset parameter is never 0.
704 * Returning the offset itself is safe for UTRIE_SHIFT>=5 because
705 * for UTRIE_SHIFT==5 the maximum index length is UTRIE_MAX_INDEX_LENGTH==0x8800
706 * which fits into 16-bit trie values;
707 * for higher UTRIE_SHIFT, UTRIE_MAX_INDEX_LENGTH decreases.
708 *
709 * Theoretically, it would be safer for all possible UTRIE_SHIFT including
710 * those of 4 and lower to return offset>>UTRIE_SURROGATE_BLOCK_BITS
711 * which would always result in a value of 0x40..0x43f
712 * (start/end 1k blocks of supplementary Unicode code points).
713 * However, this would be uglier, and would not work for some existing
714 * binary data file formats.
715 *
716 * Also, we do not plan to change UTRIE_SHIFT because it would change binary
717 * data file formats, and we would probably not make it smaller because of
718 * the then even larger BMP index length even for empty tries.
719 */
720 static uint32_t U_CALLCONV
defaultGetFoldedValue(UNewTrie * trie,UChar32 start,int32_t offset)721 defaultGetFoldedValue(UNewTrie *trie, UChar32 start, int32_t offset) {
722 uint32_t value, initialValue;
723 UChar32 limit;
724 UBool inBlockZero;
725
726 initialValue=trie->data[0];
727 limit=start+0x400;
728 while(start<limit) {
729 value=utrie_get32(trie, start, &inBlockZero);
730 if(inBlockZero) {
731 start+=UTRIE_DATA_BLOCK_LENGTH;
732 } else if(value!=initialValue) {
733 return (uint32_t)offset;
734 } else {
735 ++start;
736 }
737 }
738 return 0;
739 }
740
741 U_CAPI int32_t U_EXPORT2
utrie_serialize(UNewTrie * trie,void * dt,int32_t capacity,UNewTrieGetFoldedValue * getFoldedValue,UBool reduceTo16Bits,UErrorCode * pErrorCode)742 utrie_serialize(UNewTrie *trie, void *dt, int32_t capacity,
743 UNewTrieGetFoldedValue *getFoldedValue,
744 UBool reduceTo16Bits,
745 UErrorCode *pErrorCode) {
746 UTrieHeader *header;
747 uint32_t *p;
748 uint16_t *dest16;
749 int32_t i, length;
750 uint8_t* data = NULL;
751
752 /* argument check */
753 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
754 return 0;
755 }
756
757 if(trie==NULL || capacity<0 || (capacity>0 && dt==NULL)) {
758 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
759 return 0;
760 }
761 if(getFoldedValue==NULL) {
762 getFoldedValue=defaultGetFoldedValue;
763 }
764
765 data = (uint8_t*)dt;
766 /* fold and compact if necessary, also checks that indexLength is within limits */
767 if(!trie->isCompacted) {
768 /* compact once without overlap to improve folding */
769 utrie_compact(trie, FALSE, pErrorCode);
770
771 /* fold the supplementary part of the index array */
772 utrie_fold(trie, getFoldedValue, pErrorCode);
773
774 /* compact again with overlap for minimum data array length */
775 utrie_compact(trie, TRUE, pErrorCode);
776
777 trie->isCompacted=TRUE;
778 if(U_FAILURE(*pErrorCode)) {
779 return 0;
780 }
781 }
782
783 /* is dataLength within limits? */
784 if( (reduceTo16Bits ? (trie->dataLength+trie->indexLength) : trie->dataLength) >= UTRIE_MAX_DATA_LENGTH) {
785 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
786 }
787
788 length=sizeof(UTrieHeader)+2*trie->indexLength;
789 if(reduceTo16Bits) {
790 length+=2*trie->dataLength;
791 } else {
792 length+=4*trie->dataLength;
793 }
794
795 if(length>capacity) {
796 return length; /* preflighting */
797 }
798
799 #ifdef UTRIE_DEBUG
800 printf("**UTrieLengths(serialize)** index:%6ld data:%6ld serialized:%6ld\n",
801 (long)trie->indexLength, (long)trie->dataLength, (long)length);
802 #endif
803
804 /* set the header fields */
805 header=(UTrieHeader *)data;
806 data+=sizeof(UTrieHeader);
807
808 header->signature=0x54726965; /* "Trie" */
809 header->options=UTRIE_SHIFT | (UTRIE_INDEX_SHIFT<<UTRIE_OPTIONS_INDEX_SHIFT);
810
811 if(!reduceTo16Bits) {
812 header->options|=UTRIE_OPTIONS_DATA_IS_32_BIT;
813 }
814 if(trie->isLatin1Linear) {
815 header->options|=UTRIE_OPTIONS_LATIN1_IS_LINEAR;
816 }
817
818 header->indexLength=trie->indexLength;
819 header->dataLength=trie->dataLength;
820
821 /* write the index (stage 1) array and the 16/32-bit data (stage 2) array */
822 if(reduceTo16Bits) {
823 /* write 16-bit index values shifted right by UTRIE_INDEX_SHIFT, after adding indexLength */
824 p=(uint32_t *)trie->index;
825 dest16=(uint16_t *)data;
826 for(i=trie->indexLength; i>0; --i) {
827 *dest16++=(uint16_t)((*p++ + trie->indexLength)>>UTRIE_INDEX_SHIFT);
828 }
829
830 /* write 16-bit data values */
831 p=trie->data;
832 for(i=trie->dataLength; i>0; --i) {
833 *dest16++=(uint16_t)*p++;
834 }
835 } else {
836 /* write 16-bit index values shifted right by UTRIE_INDEX_SHIFT */
837 p=(uint32_t *)trie->index;
838 dest16=(uint16_t *)data;
839 for(i=trie->indexLength; i>0; --i) {
840 *dest16++=(uint16_t)(*p++ >> UTRIE_INDEX_SHIFT);
841 }
842
843 /* write 32-bit data values */
844 uprv_memcpy(dest16, trie->data, 4*(size_t)trie->dataLength);
845 }
846
847 return length;
848 }
849
850 /* inverse to defaultGetFoldedValue() */
851 U_CAPI int32_t U_EXPORT2
utrie_defaultGetFoldingOffset(uint32_t data)852 utrie_defaultGetFoldingOffset(uint32_t data) {
853 return (int32_t)data;
854 }
855
856 U_CAPI int32_t U_EXPORT2
utrie_unserialize(UTrie * trie,const void * data,int32_t length,UErrorCode * pErrorCode)857 utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode) {
858 const UTrieHeader *header;
859 const uint16_t *p16;
860 uint32_t options;
861
862 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
863 return -1;
864 }
865
866 /* enough data for a trie header? */
867 if(length<(int32_t)sizeof(UTrieHeader)) {
868 *pErrorCode=U_INVALID_FORMAT_ERROR;
869 return -1;
870 }
871
872 /* check the signature */
873 header=(const UTrieHeader *)data;
874 if(header->signature!=0x54726965) {
875 *pErrorCode=U_INVALID_FORMAT_ERROR;
876 return -1;
877 }
878
879 /* get the options and check the shift values */
880 options=header->options;
881 if( (options&UTRIE_OPTIONS_SHIFT_MASK)!=UTRIE_SHIFT ||
882 ((options>>UTRIE_OPTIONS_INDEX_SHIFT)&UTRIE_OPTIONS_SHIFT_MASK)!=UTRIE_INDEX_SHIFT
883 ) {
884 *pErrorCode=U_INVALID_FORMAT_ERROR;
885 return -1;
886 }
887 trie->isLatin1Linear= (UBool)((options&UTRIE_OPTIONS_LATIN1_IS_LINEAR)!=0);
888
889 /* get the length values */
890 trie->indexLength=header->indexLength;
891 trie->dataLength=header->dataLength;
892
893 length-=(int32_t)sizeof(UTrieHeader);
894
895 /* enough data for the index? */
896 if(length<2*trie->indexLength) {
897 *pErrorCode=U_INVALID_FORMAT_ERROR;
898 return -1;
899 }
900 p16=(const uint16_t *)(header+1);
901 trie->index=p16;
902 p16+=trie->indexLength;
903 length-=2*trie->indexLength;
904
905 /* get the data */
906 if(options&UTRIE_OPTIONS_DATA_IS_32_BIT) {
907 if(length<4*trie->dataLength) {
908 *pErrorCode=U_INVALID_FORMAT_ERROR;
909 return -1;
910 }
911 trie->data32=(const uint32_t *)p16;
912 trie->initialValue=trie->data32[0];
913 length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+4*trie->dataLength;
914 } else {
915 if(length<2*trie->dataLength) {
916 *pErrorCode=U_INVALID_FORMAT_ERROR;
917 return -1;
918 }
919
920 /* the "data16" data is used via the index pointer */
921 trie->data32=NULL;
922 trie->initialValue=trie->index[trie->indexLength];
923 length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+2*trie->dataLength;
924 }
925
926 trie->getFoldingOffset=utrie_defaultGetFoldingOffset;
927
928 return length;
929 }
930
931 U_CAPI int32_t U_EXPORT2
utrie_unserializeDummy(UTrie * trie,void * data,int32_t length,uint32_t initialValue,uint32_t leadUnitValue,UBool make16BitTrie,UErrorCode * pErrorCode)932 utrie_unserializeDummy(UTrie *trie,
933 void *data, int32_t length,
934 uint32_t initialValue, uint32_t leadUnitValue,
935 UBool make16BitTrie,
936 UErrorCode *pErrorCode) {
937 uint16_t *p16;
938 int32_t actualLength, latin1Length, i, limit;
939 uint16_t block;
940
941 if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
942 return -1;
943 }
944
945 /* calculate the actual size of the dummy trie data */
946
947 /* max(Latin-1, block 0) */
948 latin1Length= 256; /*UTRIE_SHIFT<=8 ? 256 : UTRIE_DATA_BLOCK_LENGTH;*/
949
950 trie->indexLength=UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT;
951 trie->dataLength=latin1Length;
952 if(leadUnitValue!=initialValue) {
953 trie->dataLength+=UTRIE_DATA_BLOCK_LENGTH;
954 }
955
956 actualLength=trie->indexLength*2;
957 if(make16BitTrie) {
958 actualLength+=trie->dataLength*2;
959 } else {
960 actualLength+=trie->dataLength*4;
961 }
962
963 /* enough space for the dummy trie? */
964 if(length<actualLength) {
965 *pErrorCode=U_BUFFER_OVERFLOW_ERROR;
966 return actualLength;
967 }
968
969 trie->isLatin1Linear=TRUE;
970 trie->initialValue=initialValue;
971
972 /* fill the index and data arrays */
973 p16=(uint16_t *)data;
974 trie->index=p16;
975
976 if(make16BitTrie) {
977 /* indexes to block 0 */
978 block=(uint16_t)(trie->indexLength>>UTRIE_INDEX_SHIFT);
979 limit=trie->indexLength;
980 for(i=0; i<limit; ++i) {
981 p16[i]=block;
982 }
983
984 if(leadUnitValue!=initialValue) {
985 /* indexes for lead surrogate code units to the block after Latin-1 */
986 block+=(uint16_t)(latin1Length>>UTRIE_INDEX_SHIFT);
987 i=0xd800>>UTRIE_SHIFT;
988 limit=0xdc00>>UTRIE_SHIFT;
989 for(; i<limit; ++i) {
990 p16[i]=block;
991 }
992 }
993
994 trie->data32=NULL;
995
996 /* Latin-1 data */
997 p16+=trie->indexLength;
998 for(i=0; i<latin1Length; ++i) {
999 p16[i]=(uint16_t)initialValue;
1000 }
1001
1002 /* data for lead surrogate code units */
1003 if(leadUnitValue!=initialValue) {
1004 limit=latin1Length+UTRIE_DATA_BLOCK_LENGTH;
1005 for(/* i=latin1Length */; i<limit; ++i) {
1006 p16[i]=(uint16_t)leadUnitValue;
1007 }
1008 }
1009 } else {
1010 uint32_t *p32;
1011
1012 /* indexes to block 0 */
1013 uprv_memset(p16, 0, trie->indexLength*2);
1014
1015 if(leadUnitValue!=initialValue) {
1016 /* indexes for lead surrogate code units to the block after Latin-1 */
1017 block=(uint16_t)(latin1Length>>UTRIE_INDEX_SHIFT);
1018 i=0xd800>>UTRIE_SHIFT;
1019 limit=0xdc00>>UTRIE_SHIFT;
1020 for(; i<limit; ++i) {
1021 p16[i]=block;
1022 }
1023 }
1024
1025 trie->data32=p32=(uint32_t *)(p16+trie->indexLength);
1026
1027 /* Latin-1 data */
1028 for(i=0; i<latin1Length; ++i) {
1029 p32[i]=initialValue;
1030 }
1031
1032 /* data for lead surrogate code units */
1033 if(leadUnitValue!=initialValue) {
1034 limit=latin1Length+UTRIE_DATA_BLOCK_LENGTH;
1035 for(/* i=latin1Length */; i<limit; ++i) {
1036 p32[i]=leadUnitValue;
1037 }
1038 }
1039 }
1040
1041 trie->getFoldingOffset=utrie_defaultGetFoldingOffset;
1042
1043 return actualLength;
1044 }
1045
1046 /* enumeration -------------------------------------------------------------- */
1047
1048 /* default UTrieEnumValue() returns the input value itself */
1049 static uint32_t U_CALLCONV
enumSameValue(const void *,uint32_t value)1050 enumSameValue(const void * /*context*/, uint32_t value) {
1051 return value;
1052 }
1053
1054 /**
1055 * Enumerate all ranges of code points with the same relevant values.
1056 * The values are transformed from the raw trie entries by the enumValue function.
1057 */
1058 U_CAPI void U_EXPORT2
utrie_enum(const UTrie * trie,UTrieEnumValue * enumValue,UTrieEnumRange * enumRange,const void * context)1059 utrie_enum(const UTrie *trie,
1060 UTrieEnumValue *enumValue, UTrieEnumRange *enumRange, const void *context) {
1061 const uint32_t *data32;
1062 const uint16_t *idx;
1063
1064 uint32_t value, prevValue, initialValue;
1065 UChar32 c, prev;
1066 int32_t l, i, j, block, prevBlock, nullBlock, offset;
1067
1068 /* check arguments */
1069 if(trie==NULL || trie->index==NULL || enumRange==NULL) {
1070 return;
1071 }
1072 if(enumValue==NULL) {
1073 enumValue=enumSameValue;
1074 }
1075
1076 idx=trie->index;
1077 data32=trie->data32;
1078
1079 /* get the enumeration value that corresponds to an initial-value trie data entry */
1080 initialValue=enumValue(context, trie->initialValue);
1081
1082 if(data32==NULL) {
1083 nullBlock=trie->indexLength;
1084 } else {
1085 nullBlock=0;
1086 }
1087
1088 /* set variables for previous range */
1089 prevBlock=nullBlock;
1090 prev=0;
1091 prevValue=initialValue;
1092
1093 /* enumerate BMP - the main loop enumerates data blocks */
1094 for(i=0, c=0; c<=0xffff; ++i) {
1095 if(c==0xd800) {
1096 /* skip lead surrogate code _units_, go to lead surr. code _points_ */
1097 i=UTRIE_BMP_INDEX_LENGTH;
1098 } else if(c==0xdc00) {
1099 /* go back to regular BMP code points */
1100 i=c>>UTRIE_SHIFT;
1101 }
1102
1103 block=idx[i]<<UTRIE_INDEX_SHIFT;
1104 if(block==prevBlock) {
1105 /* the block is the same as the previous one, and filled with value */
1106 c+=UTRIE_DATA_BLOCK_LENGTH;
1107 } else if(block==nullBlock) {
1108 /* this is the all-initial-value block */
1109 if(prevValue!=initialValue) {
1110 if(prev<c) {
1111 if(!enumRange(context, prev, c, prevValue)) {
1112 return;
1113 }
1114 }
1115 prevBlock=nullBlock;
1116 prev=c;
1117 prevValue=initialValue;
1118 }
1119 c+=UTRIE_DATA_BLOCK_LENGTH;
1120 } else {
1121 prevBlock=block;
1122 for(j=0; j<UTRIE_DATA_BLOCK_LENGTH; ++j) {
1123 value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]);
1124 if(value!=prevValue) {
1125 if(prev<c) {
1126 if(!enumRange(context, prev, c, prevValue)) {
1127 return;
1128 }
1129 }
1130 if(j>0) {
1131 /* the block is not filled with all the same value */
1132 prevBlock=-1;
1133 }
1134 prev=c;
1135 prevValue=value;
1136 }
1137 ++c;
1138 }
1139 }
1140 }
1141
1142 /* enumerate supplementary code points */
1143 for(l=0xd800; l<0xdc00;) {
1144 /* lead surrogate access */
1145 offset=idx[l>>UTRIE_SHIFT]<<UTRIE_INDEX_SHIFT;
1146 if(offset==nullBlock) {
1147 /* no entries for a whole block of lead surrogates */
1148 if(prevValue!=initialValue) {
1149 if(prev<c) {
1150 if(!enumRange(context, prev, c, prevValue)) {
1151 return;
1152 }
1153 }
1154 prevBlock=nullBlock;
1155 prev=c;
1156 prevValue=initialValue;
1157 }
1158
1159 l+=UTRIE_DATA_BLOCK_LENGTH;
1160 c+=UTRIE_DATA_BLOCK_LENGTH<<10;
1161 continue;
1162 }
1163
1164 value= data32!=NULL ? data32[offset+(l&UTRIE_MASK)] : idx[offset+(l&UTRIE_MASK)];
1165
1166 /* enumerate trail surrogates for this lead surrogate */
1167 offset=trie->getFoldingOffset(value);
1168 if(offset<=0) {
1169 /* no data for this lead surrogate */
1170 if(prevValue!=initialValue) {
1171 if(prev<c) {
1172 if(!enumRange(context, prev, c, prevValue)) {
1173 return;
1174 }
1175 }
1176 prevBlock=nullBlock;
1177 prev=c;
1178 prevValue=initialValue;
1179 }
1180
1181 /* nothing else to do for the supplementary code points for this lead surrogate */
1182 c+=0x400;
1183 } else {
1184 /* enumerate code points for this lead surrogate */
1185 i=offset;
1186 offset+=UTRIE_SURROGATE_BLOCK_COUNT;
1187 do {
1188 /* copy of most of the body of the BMP loop */
1189 block=idx[i]<<UTRIE_INDEX_SHIFT;
1190 if(block==prevBlock) {
1191 /* the block is the same as the previous one, and filled with value */
1192 c+=UTRIE_DATA_BLOCK_LENGTH;
1193 } else if(block==nullBlock) {
1194 /* this is the all-initial-value block */
1195 if(prevValue!=initialValue) {
1196 if(prev<c) {
1197 if(!enumRange(context, prev, c, prevValue)) {
1198 return;
1199 }
1200 }
1201 prevBlock=nullBlock;
1202 prev=c;
1203 prevValue=initialValue;
1204 }
1205 c+=UTRIE_DATA_BLOCK_LENGTH;
1206 } else {
1207 prevBlock=block;
1208 for(j=0; j<UTRIE_DATA_BLOCK_LENGTH; ++j) {
1209 value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]);
1210 if(value!=prevValue) {
1211 if(prev<c) {
1212 if(!enumRange(context, prev, c, prevValue)) {
1213 return;
1214 }
1215 }
1216 if(j>0) {
1217 /* the block is not filled with all the same value */
1218 prevBlock=-1;
1219 }
1220 prev=c;
1221 prevValue=value;
1222 }
1223 ++c;
1224 }
1225 }
1226 } while(++i<offset);
1227 }
1228
1229 ++l;
1230 }
1231
1232 /* deliver last range */
1233 enumRange(context, prev, c, prevValue);
1234 }
1235