• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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