diff options
Diffstat (limited to 'intl/icu/source/common/utrie.cpp')
| -rw-r--r-- | intl/icu/source/common/utrie.cpp | 1234 |
1 files changed, 1234 insertions, 0 deletions
diff --git a/intl/icu/source/common/utrie.cpp b/intl/icu/source/common/utrie.cpp new file mode 100644 index 000000000..478560df6 --- /dev/null +++ b/intl/icu/source/common/utrie.cpp @@ -0,0 +1,1234 @@ +// Copyright (C) 2016 and later: Unicode, Inc. and others. +// License & terms of use: http://www.unicode.org/copyright.html +/* +****************************************************************************** +* +* Copyright (C) 2001-2012, International Business Machines +* Corporation and others. All Rights Reserved. +* +****************************************************************************** +* file name: utrie.cpp +* encoding: US-ASCII +* tab size: 8 (not used) +* indentation:4 +* +* created on: 2001oct20 +* created by: Markus W. Scherer +* +* This is a common implementation of a "folded" trie. +* It is a kind of compressed, serializable table of 16- or 32-bit values associated with +* Unicode code points (0..0x10ffff). +*/ + +#ifdef UTRIE_DEBUG +# include <stdio.h> +#endif + +#include "unicode/utypes.h" +#include "cmemory.h" +#include "utrie.h" + +/* miscellaneous ------------------------------------------------------------ */ + +#undef ABS +#define ABS(x) ((x)>=0 ? (x) : -(x)) + +static inline UBool +equal_uint32(const uint32_t *s, const uint32_t *t, int32_t length) { + while(length>0 && *s==*t) { + ++s; + ++t; + --length; + } + return (UBool)(length==0); +} + +/* Building a trie ----------------------------------------------------------*/ + +U_CAPI UNewTrie * U_EXPORT2 +utrie_open(UNewTrie *fillIn, + uint32_t *aliasData, int32_t maxDataLength, + uint32_t initialValue, uint32_t leadUnitValue, + UBool latin1Linear) { + UNewTrie *trie; + int32_t i, j; + + if( maxDataLength<UTRIE_DATA_BLOCK_LENGTH || + (latin1Linear && maxDataLength<1024) + ) { + return NULL; + } + + if(fillIn!=NULL) { + trie=fillIn; + } else { + trie=(UNewTrie *)uprv_malloc(sizeof(UNewTrie)); + if(trie==NULL) { + return NULL; + } + } + uprv_memset(trie, 0, sizeof(UNewTrie)); + trie->isAllocated= (UBool)(fillIn==NULL); + + if(aliasData!=NULL) { + trie->data=aliasData; + trie->isDataAllocated=FALSE; + } else { + trie->data=(uint32_t *)uprv_malloc(maxDataLength*4); + if(trie->data==NULL) { + uprv_free(trie); + return NULL; + } + trie->isDataAllocated=TRUE; + } + + /* preallocate and reset the first data block (block index 0) */ + j=UTRIE_DATA_BLOCK_LENGTH; + + if(latin1Linear) { + /* preallocate and reset the first block (number 0) and Latin-1 (U+0000..U+00ff) after that */ + /* made sure above that maxDataLength>=1024 */ + + /* set indexes to point to consecutive data blocks */ + i=0; + do { + /* do this at least for trie->index[0] even if that block is only partly used for Latin-1 */ + trie->index[i++]=j; + j+=UTRIE_DATA_BLOCK_LENGTH; + } while(i<(256>>UTRIE_SHIFT)); + } + + /* reset the initially allocated blocks to the initial value */ + trie->dataLength=j; + while(j>0) { + trie->data[--j]=initialValue; + } + + trie->leadUnitValue=leadUnitValue; + trie->indexLength=UTRIE_MAX_INDEX_LENGTH; + trie->dataCapacity=maxDataLength; + trie->isLatin1Linear=latin1Linear; + trie->isCompacted=FALSE; + return trie; +} + +U_CAPI UNewTrie * U_EXPORT2 +utrie_clone(UNewTrie *fillIn, const UNewTrie *other, uint32_t *aliasData, int32_t aliasDataCapacity) { + UNewTrie *trie; + UBool isDataAllocated; + + /* do not clone if other is not valid or already compacted */ + if(other==NULL || other->data==NULL || other->isCompacted) { + return NULL; + } + + /* clone data */ + if(aliasData!=NULL && aliasDataCapacity>=other->dataCapacity) { + isDataAllocated=FALSE; + } else { + aliasDataCapacity=other->dataCapacity; + aliasData=(uint32_t *)uprv_malloc(other->dataCapacity*4); + if(aliasData==NULL) { + return NULL; + } + isDataAllocated=TRUE; + } + + trie=utrie_open(fillIn, aliasData, aliasDataCapacity, + other->data[0], other->leadUnitValue, + other->isLatin1Linear); + if(trie==NULL) { + uprv_free(aliasData); + } else { + uprv_memcpy(trie->index, other->index, sizeof(trie->index)); + uprv_memcpy(trie->data, other->data, (size_t)other->dataLength*4); + trie->dataLength=other->dataLength; + trie->isDataAllocated=isDataAllocated; + } + + return trie; +} + +U_CAPI void U_EXPORT2 +utrie_close(UNewTrie *trie) { + if(trie!=NULL) { + if(trie->isDataAllocated) { + uprv_free(trie->data); + trie->data=NULL; + } + if(trie->isAllocated) { + uprv_free(trie); + } + } +} + +U_CAPI uint32_t * U_EXPORT2 +utrie_getData(UNewTrie *trie, int32_t *pLength) { + if(trie==NULL || pLength==NULL) { + return NULL; + } + + *pLength=trie->dataLength; + return trie->data; +} + +static int32_t +utrie_allocDataBlock(UNewTrie *trie) { + int32_t newBlock, newTop; + + newBlock=trie->dataLength; + newTop=newBlock+UTRIE_DATA_BLOCK_LENGTH; + if(newTop>trie->dataCapacity) { + /* out of memory in the data array */ + return -1; + } + trie->dataLength=newTop; + return newBlock; +} + +/** + * No error checking for illegal arguments. + * + * @return -1 if no new data block available (out of memory in data array) + * @internal + */ +static int32_t +utrie_getDataBlock(UNewTrie *trie, UChar32 c) { + int32_t indexValue, newBlock; + + c>>=UTRIE_SHIFT; + indexValue=trie->index[c]; + if(indexValue>0) { + return indexValue; + } + + /* allocate a new data block */ + newBlock=utrie_allocDataBlock(trie); + if(newBlock<0) { + /* out of memory in the data array */ + return -1; + } + trie->index[c]=newBlock; + + /* copy-on-write for a block from a setRange() */ + uprv_memcpy(trie->data+newBlock, trie->data-indexValue, 4*UTRIE_DATA_BLOCK_LENGTH); + return newBlock; +} + +/** + * @return TRUE if the value was successfully set + */ +U_CAPI UBool U_EXPORT2 +utrie_set32(UNewTrie *trie, UChar32 c, uint32_t value) { + int32_t block; + + /* valid, uncompacted trie and valid c? */ + if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) { + return FALSE; + } + + block=utrie_getDataBlock(trie, c); + if(block<0) { + return FALSE; + } + + trie->data[block+(c&UTRIE_MASK)]=value; + return TRUE; +} + +U_CAPI uint32_t U_EXPORT2 +utrie_get32(UNewTrie *trie, UChar32 c, UBool *pInBlockZero) { + int32_t block; + + /* valid, uncompacted trie and valid c? */ + if(trie==NULL || trie->isCompacted || (uint32_t)c>0x10ffff) { + if(pInBlockZero!=NULL) { + *pInBlockZero=TRUE; + } + return 0; + } + + block=trie->index[c>>UTRIE_SHIFT]; + if(pInBlockZero!=NULL) { + *pInBlockZero= (UBool)(block==0); + } + + return trie->data[ABS(block)+(c&UTRIE_MASK)]; +} + +/** + * @internal + */ +static void +utrie_fillBlock(uint32_t *block, UChar32 start, UChar32 limit, + uint32_t value, uint32_t initialValue, UBool overwrite) { + uint32_t *pLimit; + + pLimit=block+limit; + block+=start; + if(overwrite) { + while(block<pLimit) { + *block++=value; + } + } else { + while(block<pLimit) { + if(*block==initialValue) { + *block=value; + } + ++block; + } + } +} + +U_CAPI UBool U_EXPORT2 +utrie_setRange32(UNewTrie *trie, UChar32 start, UChar32 limit, uint32_t value, UBool overwrite) { + /* + * repeat value in [start..limit[ + * mark index values for repeat-data blocks by setting bit 31 of the index values + * fill around existing values if any, if(overwrite) + */ + uint32_t initialValue; + int32_t block, rest, repeatBlock; + + /* valid, uncompacted trie and valid indexes? */ + if( trie==NULL || trie->isCompacted || + (uint32_t)start>0x10ffff || (uint32_t)limit>0x110000 || start>limit + ) { + return FALSE; + } + if(start==limit) { + return TRUE; /* nothing to do */ + } + + initialValue=trie->data[0]; + if(start&UTRIE_MASK) { + UChar32 nextStart; + + /* set partial block at [start..following block boundary[ */ + block=utrie_getDataBlock(trie, start); + if(block<0) { + return FALSE; + } + + nextStart=(start+UTRIE_DATA_BLOCK_LENGTH)&~UTRIE_MASK; + if(nextStart<=limit) { + utrie_fillBlock(trie->data+block, start&UTRIE_MASK, UTRIE_DATA_BLOCK_LENGTH, + value, initialValue, overwrite); + start=nextStart; + } else { + utrie_fillBlock(trie->data+block, start&UTRIE_MASK, limit&UTRIE_MASK, + value, initialValue, overwrite); + return TRUE; + } + } + + /* number of positions in the last, partial block */ + rest=limit&UTRIE_MASK; + + /* round down limit to a block boundary */ + limit&=~UTRIE_MASK; + + /* iterate over all-value blocks */ + if(value==initialValue) { + repeatBlock=0; + } else { + repeatBlock=-1; + } + while(start<limit) { + /* get index value */ + block=trie->index[start>>UTRIE_SHIFT]; + if(block>0) { + /* already allocated, fill in value */ + utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, overwrite); + } else if(trie->data[-block]!=value && (block==0 || overwrite)) { + /* set the repeatBlock instead of the current block 0 or range block */ + if(repeatBlock>=0) { + trie->index[start>>UTRIE_SHIFT]=-repeatBlock; + } else { + /* create and set and fill the repeatBlock */ + repeatBlock=utrie_getDataBlock(trie, start); + if(repeatBlock<0) { + return FALSE; + } + + /* set the negative block number to indicate that it is a repeat block */ + trie->index[start>>UTRIE_SHIFT]=-repeatBlock; + utrie_fillBlock(trie->data+repeatBlock, 0, UTRIE_DATA_BLOCK_LENGTH, value, initialValue, TRUE); + } + } + + start+=UTRIE_DATA_BLOCK_LENGTH; + } + + if(rest>0) { + /* set partial block at [last block boundary..limit[ */ + block=utrie_getDataBlock(trie, start); + if(block<0) { + return FALSE; + } + + utrie_fillBlock(trie->data+block, 0, rest, value, initialValue, overwrite); + } + + return TRUE; +} + +static int32_t +_findSameIndexBlock(const int32_t *idx, int32_t indexLength, + int32_t otherBlock) { + int32_t block, i; + + for(block=UTRIE_BMP_INDEX_LENGTH; block<indexLength; block+=UTRIE_SURROGATE_BLOCK_COUNT) { + for(i=0; i<UTRIE_SURROGATE_BLOCK_COUNT; ++i) { + if(idx[block+i]!=idx[otherBlock+i]) { + break; + } + } + if(i==UTRIE_SURROGATE_BLOCK_COUNT) { + return block; + } + } + return indexLength; +} + +/* + * Fold the normalization data for supplementary code points into + * a compact area on top of the BMP-part of the trie index, + * with the lead surrogates indexing this compact area. + * + * Duplicate the index values for lead surrogates: + * From inside the BMP area, where some may be overridden with folded values, + * to just after the BMP area, where they can be retrieved for + * code point lookups. + */ +static void +utrie_fold(UNewTrie *trie, UNewTrieGetFoldedValue *getFoldedValue, UErrorCode *pErrorCode) { + int32_t leadIndexes[UTRIE_SURROGATE_BLOCK_COUNT]; + int32_t *idx; + uint32_t value; + UChar32 c; + int32_t indexLength, block; +#ifdef UTRIE_DEBUG + int countLeadCUWithData=0; +#endif + + idx=trie->index; + + /* copy the lead surrogate indexes into a temporary array */ + uprv_memcpy(leadIndexes, idx+(0xd800>>UTRIE_SHIFT), 4*UTRIE_SURROGATE_BLOCK_COUNT); + + /* + * set all values for lead surrogate code *units* to leadUnitValue + * so that, by default, runtime lookups will find no data for associated + * supplementary code points, unless there is data for such code points + * which will result in a non-zero folding value below that is set for + * the respective lead units + * + * the above saved the indexes for surrogate code *points* + * fill the indexes with simplified code from utrie_setRange32() + */ + if(trie->leadUnitValue==trie->data[0]) { + block=0; /* leadUnitValue==initialValue, use all-initial-value block */ + } else { + /* create and fill the repeatBlock */ + block=utrie_allocDataBlock(trie); + if(block<0) { + /* data table overflow */ + *pErrorCode=U_MEMORY_ALLOCATION_ERROR; + return; + } + utrie_fillBlock(trie->data+block, 0, UTRIE_DATA_BLOCK_LENGTH, trie->leadUnitValue, trie->data[0], TRUE); + block=-block; /* negative block number to indicate that it is a repeat block */ + } + for(c=(0xd800>>UTRIE_SHIFT); c<(0xdc00>>UTRIE_SHIFT); ++c) { + trie->index[c]=block; + } + + /* + * Fold significant index values into the area just after the BMP indexes. + * In case the first lead surrogate has significant data, + * its index block must be used first (in which case the folding is a no-op). + * Later all folded index blocks are moved up one to insert the copied + * lead surrogate indexes. + */ + indexLength=UTRIE_BMP_INDEX_LENGTH; + + /* search for any index (stage 1) entries for supplementary code points */ + for(c=0x10000; c<0x110000;) { + if(idx[c>>UTRIE_SHIFT]!=0) { + /* there is data, treat the full block for a lead surrogate */ + c&=~0x3ff; + +#ifdef UTRIE_DEBUG + ++countLeadCUWithData; + /* printf("supplementary data for lead surrogate U+%04lx\n", (long)(0xd7c0+(c>>10))); */ +#endif + + /* is there an identical index block? */ + block=_findSameIndexBlock(idx, indexLength, c>>UTRIE_SHIFT); + + /* + * get a folded value for [c..c+0x400[ and, + * if different from the value for the lead surrogate code point, + * set it for the lead surrogate code unit + */ + value=getFoldedValue(trie, c, block+UTRIE_SURROGATE_BLOCK_COUNT); + if(value!=utrie_get32(trie, U16_LEAD(c), NULL)) { + if(!utrie_set32(trie, U16_LEAD(c), value)) { + /* data table overflow */ + *pErrorCode=U_MEMORY_ALLOCATION_ERROR; + return; + } + + /* if we did not find an identical index block... */ + if(block==indexLength) { + /* move the actual index (stage 1) entries from the supplementary position to the new one */ + uprv_memmove(idx+indexLength, + idx+(c>>UTRIE_SHIFT), + 4*UTRIE_SURROGATE_BLOCK_COUNT); + indexLength+=UTRIE_SURROGATE_BLOCK_COUNT; + } + } + c+=0x400; + } else { + c+=UTRIE_DATA_BLOCK_LENGTH; + } + } +#ifdef UTRIE_DEBUG + if(countLeadCUWithData>0) { + printf("supplementary data for %d lead surrogates\n", countLeadCUWithData); + } +#endif + + /* + * index array overflow? + * This is to guarantee that a folding offset is of the form + * UTRIE_BMP_INDEX_LENGTH+n*UTRIE_SURROGATE_BLOCK_COUNT with n=0..1023. + * If the index is too large, then n>=1024 and more than 10 bits are necessary. + * + * In fact, it can only ever become n==1024 with completely unfoldable data and + * the additional block of duplicated values for lead surrogates. + */ + if(indexLength>=UTRIE_MAX_INDEX_LENGTH) { + *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR; + return; + } + + /* + * make space for the lead surrogate index block and + * insert it between the BMP indexes and the folded ones + */ + uprv_memmove(idx+UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT, + idx+UTRIE_BMP_INDEX_LENGTH, + 4*(indexLength-UTRIE_BMP_INDEX_LENGTH)); + uprv_memcpy(idx+UTRIE_BMP_INDEX_LENGTH, + leadIndexes, + 4*UTRIE_SURROGATE_BLOCK_COUNT); + indexLength+=UTRIE_SURROGATE_BLOCK_COUNT; + +#ifdef UTRIE_DEBUG + printf("trie index count: BMP %ld all Unicode %ld folded %ld\n", + UTRIE_BMP_INDEX_LENGTH, (long)UTRIE_MAX_INDEX_LENGTH, indexLength); +#endif + + trie->indexLength=indexLength; +} + +/* + * Set a value in the trie index map to indicate which data block + * is referenced and which one is not. + * utrie_compact() will remove data blocks that are not used at all. + * Set + * - 0 if it is used + * - -1 if it is not used + */ +static void +_findUnusedBlocks(UNewTrie *trie) { + int32_t i; + + /* fill the entire map with "not used" */ + uprv_memset(trie->map, 0xff, (UTRIE_MAX_BUILD_TIME_DATA_LENGTH>>UTRIE_SHIFT)*4); + + /* mark each block that _is_ used with 0 */ + for(i=0; i<trie->indexLength; ++i) { + trie->map[ABS(trie->index[i])>>UTRIE_SHIFT]=0; + } + + /* never move the all-initial-value block 0 */ + trie->map[0]=0; +} + +static int32_t +_findSameDataBlock(const uint32_t *data, int32_t dataLength, + int32_t otherBlock, int32_t step) { + int32_t block; + + /* ensure that we do not even partially get past dataLength */ + dataLength-=UTRIE_DATA_BLOCK_LENGTH; + + for(block=0; block<=dataLength; block+=step) { + if(equal_uint32(data+block, data+otherBlock, UTRIE_DATA_BLOCK_LENGTH)) { + return block; + } + } + return -1; +} + +/* + * Compact a folded build-time trie. + * + * The compaction + * - removes blocks that are identical with earlier ones + * - overlaps adjacent blocks as much as possible (if overlap==TRUE) + * - moves blocks in steps of the data granularity + * - moves and overlaps blocks that overlap with multiple values in the overlap region + * + * It does not + * - try to move and overlap blocks that are not already adjacent + */ +static void +utrie_compact(UNewTrie *trie, UBool overlap, UErrorCode *pErrorCode) { + int32_t i, start, newStart, overlapStart; + + if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) { + return; + } + + /* valid, uncompacted trie? */ + if(trie==NULL) { + *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; + return; + } + if(trie->isCompacted) { + return; /* nothing left to do */ + } + + /* compaction */ + + /* initialize the index map with "block is used/unused" flags */ + _findUnusedBlocks(trie); + + /* if Latin-1 is preallocated and linear, then do not compact Latin-1 data */ + if(trie->isLatin1Linear && UTRIE_SHIFT<=8) { + overlapStart=UTRIE_DATA_BLOCK_LENGTH+256; + } else { + overlapStart=UTRIE_DATA_BLOCK_LENGTH; + } + + newStart=UTRIE_DATA_BLOCK_LENGTH; + for(start=newStart; start<trie->dataLength;) { + /* + * start: index of first entry of current block + * newStart: index where the current block is to be moved + * (right after current end of already-compacted data) + */ + + /* skip blocks that are not used */ + if(trie->map[start>>UTRIE_SHIFT]<0) { + /* advance start to the next block */ + start+=UTRIE_DATA_BLOCK_LENGTH; + + /* leave newStart with the previous block! */ + continue; + } + + /* search for an identical block */ + if( start>=overlapStart && + (i=_findSameDataBlock(trie->data, newStart, start, + overlap ? UTRIE_DATA_GRANULARITY : UTRIE_DATA_BLOCK_LENGTH)) + >=0 + ) { + /* found an identical block, set the other block's index value for the current block */ + trie->map[start>>UTRIE_SHIFT]=i; + + /* advance start to the next block */ + start+=UTRIE_DATA_BLOCK_LENGTH; + + /* leave newStart with the previous block! */ + continue; + } + + /* see if the beginning of this block can be overlapped with the end of the previous block */ + if(overlap && start>=overlapStart) { + /* look for maximum overlap (modulo granularity) with the previous, adjacent block */ + for(i=UTRIE_DATA_BLOCK_LENGTH-UTRIE_DATA_GRANULARITY; + i>0 && !equal_uint32(trie->data+(newStart-i), trie->data+start, i); + i-=UTRIE_DATA_GRANULARITY) {} + } else { + i=0; + } + + if(i>0) { + /* some overlap */ + trie->map[start>>UTRIE_SHIFT]=newStart-i; + + /* move the non-overlapping indexes to their new positions */ + start+=i; + for(i=UTRIE_DATA_BLOCK_LENGTH-i; i>0; --i) { + trie->data[newStart++]=trie->data[start++]; + } + } else if(newStart<start) { + /* no overlap, just move the indexes to their new positions */ + trie->map[start>>UTRIE_SHIFT]=newStart; + for(i=UTRIE_DATA_BLOCK_LENGTH; i>0; --i) { + trie->data[newStart++]=trie->data[start++]; + } + } else /* no overlap && newStart==start */ { + trie->map[start>>UTRIE_SHIFT]=start; + newStart+=UTRIE_DATA_BLOCK_LENGTH; + start=newStart; + } + } + + /* now adjust the index (stage 1) table */ + for(i=0; i<trie->indexLength; ++i) { + trie->index[i]=trie->map[ABS(trie->index[i])>>UTRIE_SHIFT]; + } + +#ifdef UTRIE_DEBUG + /* we saved some space */ + printf("compacting trie: count of 32-bit words %lu->%lu\n", + (long)trie->dataLength, (long)newStart); +#endif + + trie->dataLength=newStart; +} + +/* serialization ------------------------------------------------------------ */ + +/* + * Default function for the folding value: + * Just store the offset (16 bits) if there is any non-initial-value entry. + * + * The offset parameter is never 0. + * Returning the offset itself is safe for UTRIE_SHIFT>=5 because + * for UTRIE_SHIFT==5 the maximum index length is UTRIE_MAX_INDEX_LENGTH==0x8800 + * which fits into 16-bit trie values; + * for higher UTRIE_SHIFT, UTRIE_MAX_INDEX_LENGTH decreases. + * + * Theoretically, it would be safer for all possible UTRIE_SHIFT including + * those of 4 and lower to return offset>>UTRIE_SURROGATE_BLOCK_BITS + * which would always result in a value of 0x40..0x43f + * (start/end 1k blocks of supplementary Unicode code points). + * However, this would be uglier, and would not work for some existing + * binary data file formats. + * + * Also, we do not plan to change UTRIE_SHIFT because it would change binary + * data file formats, and we would probably not make it smaller because of + * the then even larger BMP index length even for empty tries. + */ +static uint32_t U_CALLCONV +defaultGetFoldedValue(UNewTrie *trie, UChar32 start, int32_t offset) { + uint32_t value, initialValue; + UChar32 limit; + UBool inBlockZero; + + initialValue=trie->data[0]; + limit=start+0x400; + while(start<limit) { + value=utrie_get32(trie, start, &inBlockZero); + if(inBlockZero) { + start+=UTRIE_DATA_BLOCK_LENGTH; + } else if(value!=initialValue) { + return (uint32_t)offset; + } else { + ++start; + } + } + return 0; +} + +U_CAPI int32_t U_EXPORT2 +utrie_serialize(UNewTrie *trie, void *dt, int32_t capacity, + UNewTrieGetFoldedValue *getFoldedValue, + UBool reduceTo16Bits, + UErrorCode *pErrorCode) { + UTrieHeader *header; + uint32_t *p; + uint16_t *dest16; + int32_t i, length; + uint8_t* data = NULL; + + /* argument check */ + if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) { + return 0; + } + + if(trie==NULL || capacity<0 || (capacity>0 && dt==NULL)) { + *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; + return 0; + } + if(getFoldedValue==NULL) { + getFoldedValue=defaultGetFoldedValue; + } + + data = (uint8_t*)dt; + /* fold and compact if necessary, also checks that indexLength is within limits */ + if(!trie->isCompacted) { + /* compact once without overlap to improve folding */ + utrie_compact(trie, FALSE, pErrorCode); + + /* fold the supplementary part of the index array */ + utrie_fold(trie, getFoldedValue, pErrorCode); + + /* compact again with overlap for minimum data array length */ + utrie_compact(trie, TRUE, pErrorCode); + + trie->isCompacted=TRUE; + if(U_FAILURE(*pErrorCode)) { + return 0; + } + } + + /* is dataLength within limits? */ + if( (reduceTo16Bits ? (trie->dataLength+trie->indexLength) : trie->dataLength) >= UTRIE_MAX_DATA_LENGTH) { + *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR; + } + + length=sizeof(UTrieHeader)+2*trie->indexLength; + if(reduceTo16Bits) { + length+=2*trie->dataLength; + } else { + length+=4*trie->dataLength; + } + + if(length>capacity) { + return length; /* preflighting */ + } + +#ifdef UTRIE_DEBUG + printf("**UTrieLengths(serialize)** index:%6ld data:%6ld serialized:%6ld\n", + (long)trie->indexLength, (long)trie->dataLength, (long)length); +#endif + + /* set the header fields */ + header=(UTrieHeader *)data; + data+=sizeof(UTrieHeader); + + header->signature=0x54726965; /* "Trie" */ + header->options=UTRIE_SHIFT | (UTRIE_INDEX_SHIFT<<UTRIE_OPTIONS_INDEX_SHIFT); + + if(!reduceTo16Bits) { + header->options|=UTRIE_OPTIONS_DATA_IS_32_BIT; + } + if(trie->isLatin1Linear) { + header->options|=UTRIE_OPTIONS_LATIN1_IS_LINEAR; + } + + header->indexLength=trie->indexLength; + header->dataLength=trie->dataLength; + + /* write the index (stage 1) array and the 16/32-bit data (stage 2) array */ + if(reduceTo16Bits) { + /* write 16-bit index values shifted right by UTRIE_INDEX_SHIFT, after adding indexLength */ + p=(uint32_t *)trie->index; + dest16=(uint16_t *)data; + for(i=trie->indexLength; i>0; --i) { + *dest16++=(uint16_t)((*p++ + trie->indexLength)>>UTRIE_INDEX_SHIFT); + } + + /* write 16-bit data values */ + p=trie->data; + for(i=trie->dataLength; i>0; --i) { + *dest16++=(uint16_t)*p++; + } + } else { + /* write 16-bit index values shifted right by UTRIE_INDEX_SHIFT */ + p=(uint32_t *)trie->index; + dest16=(uint16_t *)data; + for(i=trie->indexLength; i>0; --i) { + *dest16++=(uint16_t)(*p++ >> UTRIE_INDEX_SHIFT); + } + + /* write 32-bit data values */ + uprv_memcpy(dest16, trie->data, 4*(size_t)trie->dataLength); + } + + return length; +} + +/* inverse to defaultGetFoldedValue() */ +U_CAPI int32_t U_EXPORT2 +utrie_defaultGetFoldingOffset(uint32_t data) { + return (int32_t)data; +} + +U_CAPI int32_t U_EXPORT2 +utrie_unserialize(UTrie *trie, const void *data, int32_t length, UErrorCode *pErrorCode) { + const UTrieHeader *header; + const uint16_t *p16; + uint32_t options; + + if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) { + return -1; + } + + /* enough data for a trie header? */ + if(length<(int32_t)sizeof(UTrieHeader)) { + *pErrorCode=U_INVALID_FORMAT_ERROR; + return -1; + } + + /* check the signature */ + header=(const UTrieHeader *)data; + if(header->signature!=0x54726965) { + *pErrorCode=U_INVALID_FORMAT_ERROR; + return -1; + } + + /* get the options and check the shift values */ + options=header->options; + if( (options&UTRIE_OPTIONS_SHIFT_MASK)!=UTRIE_SHIFT || + ((options>>UTRIE_OPTIONS_INDEX_SHIFT)&UTRIE_OPTIONS_SHIFT_MASK)!=UTRIE_INDEX_SHIFT + ) { + *pErrorCode=U_INVALID_FORMAT_ERROR; + return -1; + } + trie->isLatin1Linear= (UBool)((options&UTRIE_OPTIONS_LATIN1_IS_LINEAR)!=0); + + /* get the length values */ + trie->indexLength=header->indexLength; + trie->dataLength=header->dataLength; + + length-=(int32_t)sizeof(UTrieHeader); + + /* enough data for the index? */ + if(length<2*trie->indexLength) { + *pErrorCode=U_INVALID_FORMAT_ERROR; + return -1; + } + p16=(const uint16_t *)(header+1); + trie->index=p16; + p16+=trie->indexLength; + length-=2*trie->indexLength; + + /* get the data */ + if(options&UTRIE_OPTIONS_DATA_IS_32_BIT) { + if(length<4*trie->dataLength) { + *pErrorCode=U_INVALID_FORMAT_ERROR; + return -1; + } + trie->data32=(const uint32_t *)p16; + trie->initialValue=trie->data32[0]; + length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+4*trie->dataLength; + } else { + if(length<2*trie->dataLength) { + *pErrorCode=U_INVALID_FORMAT_ERROR; + return -1; + } + + /* the "data16" data is used via the index pointer */ + trie->data32=NULL; + trie->initialValue=trie->index[trie->indexLength]; + length=(int32_t)sizeof(UTrieHeader)+2*trie->indexLength+2*trie->dataLength; + } + + trie->getFoldingOffset=utrie_defaultGetFoldingOffset; + + return length; +} + +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) { + uint16_t *p16; + int32_t actualLength, latin1Length, i, limit; + uint16_t block; + + if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) { + return -1; + } + + /* calculate the actual size of the dummy trie data */ + + /* max(Latin-1, block 0) */ + latin1Length= 256; /*UTRIE_SHIFT<=8 ? 256 : UTRIE_DATA_BLOCK_LENGTH;*/ + + trie->indexLength=UTRIE_BMP_INDEX_LENGTH+UTRIE_SURROGATE_BLOCK_COUNT; + trie->dataLength=latin1Length; + if(leadUnitValue!=initialValue) { + trie->dataLength+=UTRIE_DATA_BLOCK_LENGTH; + } + + actualLength=trie->indexLength*2; + if(make16BitTrie) { + actualLength+=trie->dataLength*2; + } else { + actualLength+=trie->dataLength*4; + } + + /* enough space for the dummy trie? */ + if(length<actualLength) { + *pErrorCode=U_BUFFER_OVERFLOW_ERROR; + return actualLength; + } + + trie->isLatin1Linear=TRUE; + trie->initialValue=initialValue; + + /* fill the index and data arrays */ + p16=(uint16_t *)data; + trie->index=p16; + + if(make16BitTrie) { + /* indexes to block 0 */ + block=(uint16_t)(trie->indexLength>>UTRIE_INDEX_SHIFT); + limit=trie->indexLength; + for(i=0; i<limit; ++i) { + p16[i]=block; + } + + if(leadUnitValue!=initialValue) { + /* indexes for lead surrogate code units to the block after Latin-1 */ + block+=(uint16_t)(latin1Length>>UTRIE_INDEX_SHIFT); + i=0xd800>>UTRIE_SHIFT; + limit=0xdc00>>UTRIE_SHIFT; + for(; i<limit; ++i) { + p16[i]=block; + } + } + + trie->data32=NULL; + + /* Latin-1 data */ + p16+=trie->indexLength; + for(i=0; i<latin1Length; ++i) { + p16[i]=(uint16_t)initialValue; + } + + /* data for lead surrogate code units */ + if(leadUnitValue!=initialValue) { + limit=latin1Length+UTRIE_DATA_BLOCK_LENGTH; + for(/* i=latin1Length */; i<limit; ++i) { + p16[i]=(uint16_t)leadUnitValue; + } + } + } else { + uint32_t *p32; + + /* indexes to block 0 */ + uprv_memset(p16, 0, trie->indexLength*2); + + if(leadUnitValue!=initialValue) { + /* indexes for lead surrogate code units to the block after Latin-1 */ + block=(uint16_t)(latin1Length>>UTRIE_INDEX_SHIFT); + i=0xd800>>UTRIE_SHIFT; + limit=0xdc00>>UTRIE_SHIFT; + for(; i<limit; ++i) { + p16[i]=block; + } + } + + trie->data32=p32=(uint32_t *)(p16+trie->indexLength); + + /* Latin-1 data */ + for(i=0; i<latin1Length; ++i) { + p32[i]=initialValue; + } + + /* data for lead surrogate code units */ + if(leadUnitValue!=initialValue) { + limit=latin1Length+UTRIE_DATA_BLOCK_LENGTH; + for(/* i=latin1Length */; i<limit; ++i) { + p32[i]=leadUnitValue; + } + } + } + + trie->getFoldingOffset=utrie_defaultGetFoldingOffset; + + return actualLength; +} + +/* enumeration -------------------------------------------------------------- */ + +/* default UTrieEnumValue() returns the input value itself */ +static uint32_t U_CALLCONV +enumSameValue(const void * /*context*/, uint32_t value) { + return value; +} + +/** + * Enumerate all ranges of code points with the same relevant values. + * The values are transformed from the raw trie entries by the enumValue function. + */ +U_CAPI void U_EXPORT2 +utrie_enum(const UTrie *trie, + UTrieEnumValue *enumValue, UTrieEnumRange *enumRange, const void *context) { + const uint32_t *data32; + const uint16_t *idx; + + uint32_t value, prevValue, initialValue; + UChar32 c, prev; + int32_t l, i, j, block, prevBlock, nullBlock, offset; + + /* check arguments */ + if(trie==NULL || trie->index==NULL || enumRange==NULL) { + return; + } + if(enumValue==NULL) { + enumValue=enumSameValue; + } + + idx=trie->index; + data32=trie->data32; + + /* get the enumeration value that corresponds to an initial-value trie data entry */ + initialValue=enumValue(context, trie->initialValue); + + if(data32==NULL) { + nullBlock=trie->indexLength; + } else { + nullBlock=0; + } + + /* set variables for previous range */ + prevBlock=nullBlock; + prev=0; + prevValue=initialValue; + + /* enumerate BMP - the main loop enumerates data blocks */ + for(i=0, c=0; c<=0xffff; ++i) { + if(c==0xd800) { + /* skip lead surrogate code _units_, go to lead surr. code _points_ */ + i=UTRIE_BMP_INDEX_LENGTH; + } else if(c==0xdc00) { + /* go back to regular BMP code points */ + i=c>>UTRIE_SHIFT; + } + + block=idx[i]<<UTRIE_INDEX_SHIFT; + if(block==prevBlock) { + /* the block is the same as the previous one, and filled with value */ + c+=UTRIE_DATA_BLOCK_LENGTH; + } else if(block==nullBlock) { + /* this is the all-initial-value block */ + if(prevValue!=initialValue) { + if(prev<c) { + if(!enumRange(context, prev, c, prevValue)) { + return; + } + } + prevBlock=nullBlock; + prev=c; + prevValue=initialValue; + } + c+=UTRIE_DATA_BLOCK_LENGTH; + } else { + prevBlock=block; + for(j=0; j<UTRIE_DATA_BLOCK_LENGTH; ++j) { + value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]); + if(value!=prevValue) { + if(prev<c) { + if(!enumRange(context, prev, c, prevValue)) { + return; + } + } + if(j>0) { + /* the block is not filled with all the same value */ + prevBlock=-1; + } + prev=c; + prevValue=value; + } + ++c; + } + } + } + + /* enumerate supplementary code points */ + for(l=0xd800; l<0xdc00;) { + /* lead surrogate access */ + offset=idx[l>>UTRIE_SHIFT]<<UTRIE_INDEX_SHIFT; + if(offset==nullBlock) { + /* no entries for a whole block of lead surrogates */ + if(prevValue!=initialValue) { + if(prev<c) { + if(!enumRange(context, prev, c, prevValue)) { + return; + } + } + prevBlock=nullBlock; + prev=c; + prevValue=initialValue; + } + + l+=UTRIE_DATA_BLOCK_LENGTH; + c+=UTRIE_DATA_BLOCK_LENGTH<<10; + continue; + } + + value= data32!=NULL ? data32[offset+(l&UTRIE_MASK)] : idx[offset+(l&UTRIE_MASK)]; + + /* enumerate trail surrogates for this lead surrogate */ + offset=trie->getFoldingOffset(value); + if(offset<=0) { + /* no data for this lead surrogate */ + if(prevValue!=initialValue) { + if(prev<c) { + if(!enumRange(context, prev, c, prevValue)) { + return; + } + } + prevBlock=nullBlock; + prev=c; + prevValue=initialValue; + } + + /* nothing else to do for the supplementary code points for this lead surrogate */ + c+=0x400; + } else { + /* enumerate code points for this lead surrogate */ + i=offset; + offset+=UTRIE_SURROGATE_BLOCK_COUNT; + do { + /* copy of most of the body of the BMP loop */ + block=idx[i]<<UTRIE_INDEX_SHIFT; + if(block==prevBlock) { + /* the block is the same as the previous one, and filled with value */ + c+=UTRIE_DATA_BLOCK_LENGTH; + } else if(block==nullBlock) { + /* this is the all-initial-value block */ + if(prevValue!=initialValue) { + if(prev<c) { + if(!enumRange(context, prev, c, prevValue)) { + return; + } + } + prevBlock=nullBlock; + prev=c; + prevValue=initialValue; + } + c+=UTRIE_DATA_BLOCK_LENGTH; + } else { + prevBlock=block; + for(j=0; j<UTRIE_DATA_BLOCK_LENGTH; ++j) { + value=enumValue(context, data32!=NULL ? data32[block+j] : idx[block+j]); + if(value!=prevValue) { + if(prev<c) { + if(!enumRange(context, prev, c, prevValue)) { + return; + } + } + if(j>0) { + /* the block is not filled with all the same value */ + prevBlock=-1; + } + prev=c; + prevValue=value; + } + ++c; + } + } + } while(++i<offset); + } + + ++l; + } + + /* deliver last range */ + enumRange(context, prev, c, prevValue); +} |