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