The Tor Browser: intl/icu/source/common/utrie.cpp@b8a032363ba2 (annotated)

intl/icu/source/common/utrie.cpp@b8a032363ba2 (annotated)

intl/icu/source/common/utrie.cpp

Thu, 22 Jan 2015 13:21:57 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Thu, 22 Jan 2015 13:21:57 +0100
branch: TOR_BUG_9701
changeset 15: b8a032363ba2
permissions: -rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

 /*
 ******************************************************************************
 *
 *   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, 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),
 *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,
 *(indexLength-UTRIE_BMP_INDEX_LENGTH));
     uprv_memcpy(idx+UTRIE_BMP_INDEX_LENGTH,
                 leadIndexes,
 *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*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);
 }

The Tor Browser / annotate

intl/icu/source/common/utrie.cpp@b8a032363ba2 (annotated)

intl/icu/source/common/utrie.cpp