diff options
Diffstat (limited to 'deps/node/deps/icu-small/source/common/utrie.cpp')
| -rw-r--r-- | deps/node/deps/icu-small/source/common/utrie.cpp | 1234 |
1 files changed, 0 insertions, 1234 deletions
diff --git a/deps/node/deps/icu-small/source/common/utrie.cpp b/deps/node/deps/icu-small/source/common/utrie.cpp deleted file mode 100644 index ecf9b1cb..00000000 --- a/deps/node/deps/icu-small/source/common/utrie.cpp +++ /dev/null @@ -1,1234 +0,0 @@ -// © 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: UTF-8 -* 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); -} |