1 // 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 ****************************************************************************** 5 * 6 * Copyright (C) 2001-2014, International Business Machines 7 * Corporation and others. All Rights Reserved. 8 * 9 ****************************************************************************** 10 * file name: utrie2_builder.cpp 11 * encoding: UTF-8 12 * tab size: 8 (not used) 13 * indentation:4 14 * 15 * created on: 2008sep26 (split off from utrie2.c) 16 * created by: Markus W. Scherer 17 * 18 * This is a common implementation of a Unicode 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 * This is the second common version of a Unicode trie (hence the name UTrie2). 22 * See utrie2.h for a comparison. 23 * 24 * This file contains only the builder code. 25 * See utrie2.c for the runtime and enumeration code. 26 */ 27 #ifdef UTRIE2_DEBUG 28 # include <stdio.h> 29 #endif 30 31 #include "unicode/utypes.h" 32 #include "cmemory.h" 33 #include "utrie2.h" 34 #include "utrie2_impl.h" 35 36 #include "utrie.h" /* for utrie2_fromUTrie() and utrie_swap() */ 37 38 /* Implementation notes ----------------------------------------------------- */ 39 40 /* 41 * The UTRIE2_SHIFT_1, UTRIE2_SHIFT_2, UTRIE2_INDEX_SHIFT and other values 42 * have been chosen to minimize trie sizes overall. 43 * Most of the code is flexible enough to work with a range of values, 44 * within certain limits. 45 * 46 * Exception: Support for separate values for lead surrogate code _units_ 47 * vs. code _points_ was added after the constants were fixed, 48 * and has not been tested nor particularly designed for different constant values. 49 * (Especially the utrie2_enum() code that jumps to the special LSCP index-2 50 * part and back.) 51 * 52 * Requires UTRIE2_SHIFT_2<=6. Otherwise 0xc0 which is the top of the ASCII-linear data 53 * including the bad-UTF-8-data block is not a multiple of UTRIE2_DATA_BLOCK_LENGTH 54 * and map[block>>UTRIE2_SHIFT_2] (used in reference counting and compaction 55 * remapping) stops working. 56 * 57 * Requires UTRIE2_SHIFT_1>=10 because utrie2_enumForLeadSurrogate() 58 * assumes that a single index-2 block is used for 0x400 code points 59 * corresponding to one lead surrogate. 60 * 61 * Requires UTRIE2_SHIFT_1<=16. Otherwise one single index-2 block contains 62 * more than one Unicode plane, and the split of the index-2 table into a BMP 63 * part and a supplementary part, with a gap in between, would not work. 64 * 65 * Requires UTRIE2_INDEX_SHIFT>=1 not because of the code but because 66 * there is data with more than 64k distinct values, 67 * for example for Unihan collation with a separate collation weight per 68 * Han character. 69 */ 70 71 /* Building a trie ----------------------------------------------------------*/ 72 73 enum { 74 /** The null index-2 block, following the gap in the index-2 table. */ 75 UNEWTRIE2_INDEX_2_NULL_OFFSET=UNEWTRIE2_INDEX_GAP_OFFSET+UNEWTRIE2_INDEX_GAP_LENGTH, 76 77 /** The start of allocated index-2 blocks. */ 78 UNEWTRIE2_INDEX_2_START_OFFSET=UNEWTRIE2_INDEX_2_NULL_OFFSET+UTRIE2_INDEX_2_BLOCK_LENGTH, 79 80 /** 81 * The null data block. 82 * Length 64=0x40 even if UTRIE2_DATA_BLOCK_LENGTH is smaller, 83 * to work with 6-bit trail bytes from 2-byte UTF-8. 84 */ 85 UNEWTRIE2_DATA_NULL_OFFSET=UTRIE2_DATA_START_OFFSET, 86 87 /** The start of allocated data blocks. */ 88 UNEWTRIE2_DATA_START_OFFSET=UNEWTRIE2_DATA_NULL_OFFSET+0x40, 89 90 /** 91 * The start of data blocks for U+0800 and above. 92 * Below, compaction uses a block length of 64 for 2-byte UTF-8. 93 * From here on, compaction uses UTRIE2_DATA_BLOCK_LENGTH. 94 * Data values for 0x780 code points beyond ASCII. 95 */ 96 UNEWTRIE2_DATA_0800_OFFSET=UNEWTRIE2_DATA_START_OFFSET+0x780 97 }; 98 99 /* Start with allocation of 16k data entries. */ 100 #define UNEWTRIE2_INITIAL_DATA_LENGTH ((int32_t)1<<14) 101 102 /* Grow about 8x each time. */ 103 #define UNEWTRIE2_MEDIUM_DATA_LENGTH ((int32_t)1<<17) 104 105 static int32_t 106 allocIndex2Block(UNewTrie2 *trie); 107 108 U_CAPI UTrie2 * U_EXPORT2 109 utrie2_open(uint32_t initialValue, uint32_t errorValue, UErrorCode *pErrorCode) { 110 UTrie2 *trie; 111 UNewTrie2 *newTrie; 112 uint32_t *data; 113 int32_t i, j; 114 115 if(U_FAILURE(*pErrorCode)) { 116 return NULL; 117 } 118 119 trie=(UTrie2 *)uprv_malloc(sizeof(UTrie2)); 120 newTrie=(UNewTrie2 *)uprv_malloc(sizeof(UNewTrie2)); 121 data=(uint32_t *)uprv_malloc(UNEWTRIE2_INITIAL_DATA_LENGTH*4); 122 if(trie==NULL || newTrie==NULL || data==NULL) { 123 uprv_free(trie); 124 uprv_free(newTrie); 125 uprv_free(data); 126 *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 127 return 0; 128 } 129 130 uprv_memset(trie, 0, sizeof(UTrie2)); 131 trie->initialValue=initialValue; 132 trie->errorValue=errorValue; 133 trie->highStart=0x110000; 134 trie->newTrie=newTrie; 135 136 newTrie->data=data; 137 newTrie->dataCapacity=UNEWTRIE2_INITIAL_DATA_LENGTH; 138 newTrie->initialValue=initialValue; 139 newTrie->errorValue=errorValue; 140 newTrie->highStart=0x110000; 141 newTrie->firstFreeBlock=0; /* no free block in the list */ 142 newTrie->isCompacted=FALSE; 143 144 /* 145 * preallocate and reset 146 * - ASCII 147 * - the bad-UTF-8-data block 148 * - the null data block 149 */ 150 for(i=0; i<0x80; ++i) { 151 newTrie->data[i]=initialValue; 152 } 153 for(; i<0xc0; ++i) { 154 newTrie->data[i]=errorValue; 155 } 156 for(i=UNEWTRIE2_DATA_NULL_OFFSET; i<UNEWTRIE2_DATA_START_OFFSET; ++i) { 157 newTrie->data[i]=initialValue; 158 } 159 newTrie->dataNullOffset=UNEWTRIE2_DATA_NULL_OFFSET; 160 newTrie->dataLength=UNEWTRIE2_DATA_START_OFFSET; 161 162 /* set the index-2 indexes for the 2=0x80>>UTRIE2_SHIFT_2 ASCII data blocks */ 163 for(i=0, j=0; j<0x80; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) { 164 newTrie->index2[i]=j; 165 newTrie->map[i]=1; 166 } 167 /* reference counts for the bad-UTF-8-data block */ 168 for(; j<0xc0; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) { 169 newTrie->map[i]=0; 170 } 171 /* 172 * Reference counts for the null data block: all blocks except for the ASCII blocks. 173 * Plus 1 so that we don't drop this block during compaction. 174 * Plus as many as needed for lead surrogate code points. 175 */ 176 /* i==newTrie->dataNullOffset */ 177 newTrie->map[i++]= 178 (0x110000>>UTRIE2_SHIFT_2)- 179 (0x80>>UTRIE2_SHIFT_2)+ 180 1+ 181 UTRIE2_LSCP_INDEX_2_LENGTH; 182 j+=UTRIE2_DATA_BLOCK_LENGTH; 183 for(; j<UNEWTRIE2_DATA_START_OFFSET; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) { 184 newTrie->map[i]=0; 185 } 186 187 /* 188 * set the remaining indexes in the BMP index-2 block 189 * to the null data block 190 */ 191 for(i=0x80>>UTRIE2_SHIFT_2; i<UTRIE2_INDEX_2_BMP_LENGTH; ++i) { 192 newTrie->index2[i]=UNEWTRIE2_DATA_NULL_OFFSET; 193 } 194 195 /* 196 * Fill the index gap with impossible values so that compaction 197 * does not overlap other index-2 blocks with the gap. 198 */ 199 for(i=0; i<UNEWTRIE2_INDEX_GAP_LENGTH; ++i) { 200 newTrie->index2[UNEWTRIE2_INDEX_GAP_OFFSET+i]=-1; 201 } 202 203 /* set the indexes in the null index-2 block */ 204 for(i=0; i<UTRIE2_INDEX_2_BLOCK_LENGTH; ++i) { 205 newTrie->index2[UNEWTRIE2_INDEX_2_NULL_OFFSET+i]=UNEWTRIE2_DATA_NULL_OFFSET; 206 } 207 newTrie->index2NullOffset=UNEWTRIE2_INDEX_2_NULL_OFFSET; 208 newTrie->index2Length=UNEWTRIE2_INDEX_2_START_OFFSET; 209 210 /* set the index-1 indexes for the linear index-2 block */ 211 for(i=0, j=0; 212 i<UTRIE2_OMITTED_BMP_INDEX_1_LENGTH; 213 ++i, j+=UTRIE2_INDEX_2_BLOCK_LENGTH 214 ) { 215 newTrie->index1[i]=j; 216 } 217 218 /* set the remaining index-1 indexes to the null index-2 block */ 219 for(; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) { 220 newTrie->index1[i]=UNEWTRIE2_INDEX_2_NULL_OFFSET; 221 } 222 223 /* 224 * Preallocate and reset data for U+0080..U+07ff, 225 * for 2-byte UTF-8 which will be compacted in 64-blocks 226 * even if UTRIE2_DATA_BLOCK_LENGTH is smaller. 227 */ 228 for(i=0x80; i<0x800; i+=UTRIE2_DATA_BLOCK_LENGTH) { 229 utrie2_set32(trie, i, initialValue, pErrorCode); 230 } 231 232 return trie; 233 } 234 235 static UNewTrie2 * 236 cloneBuilder(const UNewTrie2 *other) { 237 UNewTrie2 *trie; 238 239 trie=(UNewTrie2 *)uprv_malloc(sizeof(UNewTrie2)); 240 if(trie==NULL) { 241 return NULL; 242 } 243 244 trie->data=(uint32_t *)uprv_malloc(other->dataCapacity*4); 245 if(trie->data==NULL) { 246 uprv_free(trie); 247 return NULL; 248 } 249 trie->dataCapacity=other->dataCapacity; 250 251 /* clone data */ 252 uprv_memcpy(trie->index1, other->index1, sizeof(trie->index1)); 253 uprv_memcpy(trie->index2, other->index2, (size_t)other->index2Length*4); 254 trie->index2NullOffset=other->index2NullOffset; 255 trie->index2Length=other->index2Length; 256 257 uprv_memcpy(trie->data, other->data, (size_t)other->dataLength*4); 258 trie->dataNullOffset=other->dataNullOffset; 259 trie->dataLength=other->dataLength; 260 261 /* reference counters */ 262 if(other->isCompacted) { 263 trie->firstFreeBlock=0; 264 } else { 265 uprv_memcpy(trie->map, other->map, ((size_t)other->dataLength>>UTRIE2_SHIFT_2)*4); 266 trie->firstFreeBlock=other->firstFreeBlock; 267 } 268 269 trie->initialValue=other->initialValue; 270 trie->errorValue=other->errorValue; 271 trie->highStart=other->highStart; 272 trie->isCompacted=other->isCompacted; 273 274 return trie; 275 } 276 277 U_CAPI UTrie2 * U_EXPORT2 278 utrie2_clone(const UTrie2 *other, UErrorCode *pErrorCode) { 279 UTrie2 *trie; 280 281 if(U_FAILURE(*pErrorCode)) { 282 return NULL; 283 } 284 if(other==NULL || (other->memory==NULL && other->newTrie==NULL)) { 285 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 286 return NULL; 287 } 288 289 trie=(UTrie2 *)uprv_malloc(sizeof(UTrie2)); 290 if(trie==NULL) { 291 return NULL; 292 } 293 uprv_memcpy(trie, other, sizeof(UTrie2)); 294 295 if(other->memory!=NULL) { 296 trie->memory=uprv_malloc(other->length); 297 if(trie->memory!=NULL) { 298 trie->isMemoryOwned=TRUE; 299 uprv_memcpy(trie->memory, other->memory, other->length); 300 301 /* make the clone's pointers point to its own memory */ 302 trie->index=(uint16_t *)trie->memory+(other->index-(uint16_t *)other->memory); 303 if(other->data16!=NULL) { 304 trie->data16=(uint16_t *)trie->memory+(other->data16-(uint16_t *)other->memory); 305 } 306 if(other->data32!=NULL) { 307 trie->data32=(uint32_t *)trie->memory+(other->data32-(uint32_t *)other->memory); 308 } 309 } 310 } else /* other->newTrie!=NULL */ { 311 trie->newTrie=cloneBuilder(other->newTrie); 312 } 313 314 if(trie->memory==NULL && trie->newTrie==NULL) { 315 uprv_free(trie); 316 trie=NULL; 317 } 318 return trie; 319 } 320 321 typedef struct NewTrieAndStatus { 322 UTrie2 *trie; 323 UErrorCode errorCode; 324 UBool exclusiveLimit; /* rather than inclusive range end */ 325 } NewTrieAndStatus; 326 327 static UBool U_CALLCONV 328 copyEnumRange(const void *context, UChar32 start, UChar32 end, uint32_t value) { 329 NewTrieAndStatus *nt=(NewTrieAndStatus *)context; 330 if(value!=nt->trie->initialValue) { 331 if(nt->exclusiveLimit) { 332 --end; 333 } 334 if(start==end) { 335 utrie2_set32(nt->trie, start, value, &nt->errorCode); 336 } else { 337 utrie2_setRange32(nt->trie, start, end, value, TRUE, &nt->errorCode); 338 } 339 return U_SUCCESS(nt->errorCode); 340 } else { 341 return TRUE; 342 } 343 } 344 345 #ifdef UTRIE2_DEBUG 346 static void 347 utrie_printLengths(const UTrie *trie) { 348 long indexLength=trie->indexLength; 349 long dataLength=(long)trie->dataLength; 350 long totalLength=(long)sizeof(UTrieHeader)+indexLength*2+dataLength*(trie->data32!=NULL ? 4 : 2); 351 printf("**UTrieLengths** index:%6ld data:%6ld serialized:%6ld\n", 352 indexLength, dataLength, totalLength); 353 } 354 355 static void 356 utrie2_printLengths(const UTrie2 *trie, const char *which) { 357 long indexLength=trie->indexLength; 358 long dataLength=(long)trie->dataLength; 359 long totalLength=(long)sizeof(UTrie2Header)+indexLength*2+dataLength*(trie->data32!=NULL ? 4 : 2); 360 printf("**UTrie2Lengths(%s)** index:%6ld data:%6ld serialized:%6ld\n", 361 which, indexLength, dataLength, totalLength); 362 } 363 #endif 364 365 U_CAPI UTrie2 * U_EXPORT2 366 utrie2_cloneAsThawed(const UTrie2 *other, UErrorCode *pErrorCode) { 367 NewTrieAndStatus context; 368 UChar lead; 369 370 if(U_FAILURE(*pErrorCode)) { 371 return NULL; 372 } 373 if(other==NULL || (other->memory==NULL && other->newTrie==NULL)) { 374 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 375 return NULL; 376 } 377 if(other->newTrie!=NULL && !other->newTrie->isCompacted) { 378 return utrie2_clone(other, pErrorCode); /* clone an unfrozen trie */ 379 } 380 381 /* Clone the frozen trie by enumerating it and building a new one. */ 382 context.trie=utrie2_open(other->initialValue, other->errorValue, pErrorCode); 383 if(U_FAILURE(*pErrorCode)) { 384 return NULL; 385 } 386 context.exclusiveLimit=FALSE; 387 context.errorCode=*pErrorCode; 388 utrie2_enum(other, NULL, copyEnumRange, &context); 389 *pErrorCode=context.errorCode; 390 for(lead=0xd800; lead<0xdc00; ++lead) { 391 uint32_t value; 392 if(other->data32==NULL) { 393 value=UTRIE2_GET16_FROM_U16_SINGLE_LEAD(other, lead); 394 } else { 395 value=UTRIE2_GET32_FROM_U16_SINGLE_LEAD(other, lead); 396 } 397 if(value!=other->initialValue) { 398 utrie2_set32ForLeadSurrogateCodeUnit(context.trie, lead, value, pErrorCode); 399 } 400 } 401 if(U_FAILURE(*pErrorCode)) { 402 utrie2_close(context.trie); 403 context.trie=NULL; 404 } 405 return context.trie; 406 } 407 408 /* Almost the same as utrie2_cloneAsThawed() but copies a UTrie and freezes the clone. */ 409 U_CAPI UTrie2 * U_EXPORT2 410 utrie2_fromUTrie(const UTrie *trie1, uint32_t errorValue, UErrorCode *pErrorCode) { 411 NewTrieAndStatus context; 412 UChar lead; 413 414 if(U_FAILURE(*pErrorCode)) { 415 return NULL; 416 } 417 if(trie1==NULL) { 418 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 419 return NULL; 420 } 421 context.trie=utrie2_open(trie1->initialValue, errorValue, pErrorCode); 422 if(U_FAILURE(*pErrorCode)) { 423 return NULL; 424 } 425 context.exclusiveLimit=TRUE; 426 context.errorCode=*pErrorCode; 427 utrie_enum(trie1, NULL, copyEnumRange, &context); 428 *pErrorCode=context.errorCode; 429 for(lead=0xd800; lead<0xdc00; ++lead) { 430 uint32_t value; 431 if(trie1->data32==NULL) { 432 value=UTRIE_GET16_FROM_LEAD(trie1, lead); 433 } else { 434 value=UTRIE_GET32_FROM_LEAD(trie1, lead); 435 } 436 if(value!=trie1->initialValue) { 437 utrie2_set32ForLeadSurrogateCodeUnit(context.trie, lead, value, pErrorCode); 438 } 439 } 440 if(U_SUCCESS(*pErrorCode)) { 441 utrie2_freeze(context.trie, 442 trie1->data32!=NULL ? UTRIE2_32_VALUE_BITS : UTRIE2_16_VALUE_BITS, 443 pErrorCode); 444 } 445 #ifdef UTRIE2_DEBUG 446 if(U_SUCCESS(*pErrorCode)) { 447 utrie_printLengths(trie1); 448 utrie2_printLengths(context.trie, "fromUTrie"); 449 } 450 #endif 451 if(U_FAILURE(*pErrorCode)) { 452 utrie2_close(context.trie); 453 context.trie=NULL; 454 } 455 return context.trie; 456 } 457 458 static inline UBool 459 isInNullBlock(UNewTrie2 *trie, UChar32 c, UBool forLSCP) { 460 int32_t i2, block; 461 462 if(U_IS_LEAD(c) && forLSCP) { 463 i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+ 464 (c>>UTRIE2_SHIFT_2); 465 } else { 466 i2=trie->index1[c>>UTRIE2_SHIFT_1]+ 467 ((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK); 468 } 469 block=trie->index2[i2]; 470 return (UBool)(block==trie->dataNullOffset); 471 } 472 473 static int32_t 474 allocIndex2Block(UNewTrie2 *trie) { 475 int32_t newBlock, newTop; 476 477 newBlock=trie->index2Length; 478 newTop=newBlock+UTRIE2_INDEX_2_BLOCK_LENGTH; 479 if(newTop>UPRV_LENGTHOF(trie->index2)) { 480 /* 481 * Should never occur. 482 * Either UTRIE2_MAX_BUILD_TIME_INDEX_LENGTH is incorrect, 483 * or the code writes more values than should be possible. 484 */ 485 return -1; 486 } 487 trie->index2Length=newTop; 488 uprv_memcpy(trie->index2+newBlock, trie->index2+trie->index2NullOffset, UTRIE2_INDEX_2_BLOCK_LENGTH*4); 489 return newBlock; 490 } 491 492 static int32_t 493 getIndex2Block(UNewTrie2 *trie, UChar32 c, UBool forLSCP) { 494 int32_t i1, i2; 495 496 if(U_IS_LEAD(c) && forLSCP) { 497 return UTRIE2_LSCP_INDEX_2_OFFSET; 498 } 499 500 i1=c>>UTRIE2_SHIFT_1; 501 i2=trie->index1[i1]; 502 if(i2==trie->index2NullOffset) { 503 i2=allocIndex2Block(trie); 504 if(i2<0) { 505 return -1; /* program error */ 506 } 507 trie->index1[i1]=i2; 508 } 509 return i2; 510 } 511 512 static int32_t 513 allocDataBlock(UNewTrie2 *trie, int32_t copyBlock) { 514 int32_t newBlock, newTop; 515 516 if(trie->firstFreeBlock!=0) { 517 /* get the first free block */ 518 newBlock=trie->firstFreeBlock; 519 trie->firstFreeBlock=-trie->map[newBlock>>UTRIE2_SHIFT_2]; 520 } else { 521 /* get a new block from the high end */ 522 newBlock=trie->dataLength; 523 newTop=newBlock+UTRIE2_DATA_BLOCK_LENGTH; 524 if(newTop>trie->dataCapacity) { 525 /* out of memory in the data array */ 526 int32_t capacity; 527 uint32_t *data; 528 529 if(trie->dataCapacity<UNEWTRIE2_MEDIUM_DATA_LENGTH) { 530 capacity=UNEWTRIE2_MEDIUM_DATA_LENGTH; 531 } else if(trie->dataCapacity<UNEWTRIE2_MAX_DATA_LENGTH) { 532 capacity=UNEWTRIE2_MAX_DATA_LENGTH; 533 } else { 534 /* 535 * Should never occur. 536 * Either UNEWTRIE2_MAX_DATA_LENGTH is incorrect, 537 * or the code writes more values than should be possible. 538 */ 539 return -1; 540 } 541 data=(uint32_t *)uprv_malloc(capacity*4); 542 if(data==NULL) { 543 return -1; 544 } 545 uprv_memcpy(data, trie->data, (size_t)trie->dataLength*4); 546 uprv_free(trie->data); 547 trie->data=data; 548 trie->dataCapacity=capacity; 549 } 550 trie->dataLength=newTop; 551 } 552 uprv_memcpy(trie->data+newBlock, trie->data+copyBlock, UTRIE2_DATA_BLOCK_LENGTH*4); 553 trie->map[newBlock>>UTRIE2_SHIFT_2]=0; 554 return newBlock; 555 } 556 557 /* call when the block's reference counter reaches 0 */ 558 static void 559 releaseDataBlock(UNewTrie2 *trie, int32_t block) { 560 /* put this block at the front of the free-block chain */ 561 trie->map[block>>UTRIE2_SHIFT_2]=-trie->firstFreeBlock; 562 trie->firstFreeBlock=block; 563 } 564 565 static inline UBool 566 isWritableBlock(UNewTrie2 *trie, int32_t block) { 567 return (UBool)(block!=trie->dataNullOffset && 1==trie->map[block>>UTRIE2_SHIFT_2]); 568 } 569 570 static inline void 571 setIndex2Entry(UNewTrie2 *trie, int32_t i2, int32_t block) { 572 int32_t oldBlock; 573 ++trie->map[block>>UTRIE2_SHIFT_2]; /* increment first, in case block==oldBlock! */ 574 oldBlock=trie->index2[i2]; 575 if(0 == --trie->map[oldBlock>>UTRIE2_SHIFT_2]) { 576 releaseDataBlock(trie, oldBlock); 577 } 578 trie->index2[i2]=block; 579 } 580 581 /** 582 * No error checking for illegal arguments. 583 * 584 * @return -1 if no new data block available (out of memory in data array) 585 * @internal 586 */ 587 static int32_t 588 getDataBlock(UNewTrie2 *trie, UChar32 c, UBool forLSCP) { 589 int32_t i2, oldBlock, newBlock; 590 591 i2=getIndex2Block(trie, c, forLSCP); 592 if(i2<0) { 593 return -1; /* program error */ 594 } 595 596 i2+=(c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK; 597 oldBlock=trie->index2[i2]; 598 if(isWritableBlock(trie, oldBlock)) { 599 return oldBlock; 600 } 601 602 /* allocate a new data block */ 603 newBlock=allocDataBlock(trie, oldBlock); 604 if(newBlock<0) { 605 /* out of memory in the data array */ 606 return -1; 607 } 608 setIndex2Entry(trie, i2, newBlock); 609 return newBlock; 610 } 611 612 /** 613 * @return TRUE if the value was successfully set 614 */ 615 static void 616 set32(UNewTrie2 *trie, 617 UChar32 c, UBool forLSCP, uint32_t value, 618 UErrorCode *pErrorCode) { 619 int32_t block; 620 621 if(trie==NULL || trie->isCompacted) { 622 *pErrorCode=U_NO_WRITE_PERMISSION; 623 return; 624 } 625 626 block=getDataBlock(trie, c, forLSCP); 627 if(block<0) { 628 *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 629 return; 630 } 631 632 trie->data[block+(c&UTRIE2_DATA_MASK)]=value; 633 } 634 635 U_CAPI void U_EXPORT2 636 utrie2_set32(UTrie2 *trie, UChar32 c, uint32_t value, UErrorCode *pErrorCode) { 637 if(U_FAILURE(*pErrorCode)) { 638 return; 639 } 640 if((uint32_t)c>0x10ffff) { 641 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 642 return; 643 } 644 set32(trie->newTrie, c, TRUE, value, pErrorCode); 645 } 646 647 U_CAPI void U_EXPORT2 648 utrie2_set32ForLeadSurrogateCodeUnit(UTrie2 *trie, 649 UChar32 c, uint32_t value, 650 UErrorCode *pErrorCode) { 651 if(U_FAILURE(*pErrorCode)) { 652 return; 653 } 654 if(!U_IS_LEAD(c)) { 655 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 656 return; 657 } 658 set32(trie->newTrie, c, FALSE, value, pErrorCode); 659 } 660 661 static void 662 writeBlock(uint32_t *block, uint32_t value) { 663 uint32_t *limit=block+UTRIE2_DATA_BLOCK_LENGTH; 664 while(block<limit) { 665 *block++=value; 666 } 667 } 668 669 /** 670 * initialValue is ignored if overwrite=TRUE 671 * @internal 672 */ 673 static void 674 fillBlock(uint32_t *block, UChar32 start, UChar32 limit, 675 uint32_t value, uint32_t initialValue, UBool overwrite) { 676 uint32_t *pLimit; 677 678 pLimit=block+limit; 679 block+=start; 680 if(overwrite) { 681 while(block<pLimit) { 682 *block++=value; 683 } 684 } else { 685 while(block<pLimit) { 686 if(*block==initialValue) { 687 *block=value; 688 } 689 ++block; 690 } 691 } 692 } 693 694 U_CAPI void U_EXPORT2 695 utrie2_setRange32(UTrie2 *trie, 696 UChar32 start, UChar32 end, 697 uint32_t value, UBool overwrite, 698 UErrorCode *pErrorCode) { 699 /* 700 * repeat value in [start..end] 701 * mark index values for repeat-data blocks by setting bit 31 of the index values 702 * fill around existing values if any, if(overwrite) 703 */ 704 UNewTrie2 *newTrie; 705 int32_t block, rest, repeatBlock; 706 UChar32 limit; 707 708 if(U_FAILURE(*pErrorCode)) { 709 return; 710 } 711 if((uint32_t)start>0x10ffff || (uint32_t)end>0x10ffff || start>end) { 712 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 713 return; 714 } 715 newTrie=trie->newTrie; 716 if(newTrie==NULL || newTrie->isCompacted) { 717 *pErrorCode=U_NO_WRITE_PERMISSION; 718 return; 719 } 720 if(!overwrite && value==newTrie->initialValue) { 721 return; /* nothing to do */ 722 } 723 724 limit=end+1; 725 if(start&UTRIE2_DATA_MASK) { 726 UChar32 nextStart; 727 728 /* set partial block at [start..following block boundary[ */ 729 block=getDataBlock(newTrie, start, TRUE); 730 if(block<0) { 731 *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 732 return; 733 } 734 735 nextStart=(start+UTRIE2_DATA_BLOCK_LENGTH)&~UTRIE2_DATA_MASK; 736 if(nextStart<=limit) { 737 fillBlock(newTrie->data+block, start&UTRIE2_DATA_MASK, UTRIE2_DATA_BLOCK_LENGTH, 738 value, newTrie->initialValue, overwrite); 739 start=nextStart; 740 } else { 741 fillBlock(newTrie->data+block, start&UTRIE2_DATA_MASK, limit&UTRIE2_DATA_MASK, 742 value, newTrie->initialValue, overwrite); 743 return; 744 } 745 } 746 747 /* number of positions in the last, partial block */ 748 rest=limit&UTRIE2_DATA_MASK; 749 750 /* round down limit to a block boundary */ 751 limit&=~UTRIE2_DATA_MASK; 752 753 /* iterate over all-value blocks */ 754 if(value==newTrie->initialValue) { 755 repeatBlock=newTrie->dataNullOffset; 756 } else { 757 repeatBlock=-1; 758 } 759 760 while(start<limit) { 761 int32_t i2; 762 UBool setRepeatBlock=FALSE; 763 764 if(value==newTrie->initialValue && isInNullBlock(newTrie, start, TRUE)) { 765 start+=UTRIE2_DATA_BLOCK_LENGTH; /* nothing to do */ 766 continue; 767 } 768 769 /* get index value */ 770 i2=getIndex2Block(newTrie, start, TRUE); 771 if(i2<0) { 772 *pErrorCode=U_INTERNAL_PROGRAM_ERROR; 773 return; 774 } 775 i2+=(start>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK; 776 block=newTrie->index2[i2]; 777 if(isWritableBlock(newTrie, block)) { 778 /* already allocated */ 779 if(overwrite && block>=UNEWTRIE2_DATA_0800_OFFSET) { 780 /* 781 * We overwrite all values, and it's not a 782 * protected (ASCII-linear or 2-byte UTF-8) block: 783 * replace with the repeatBlock. 784 */ 785 setRepeatBlock=TRUE; 786 } else { 787 /* !overwrite, or protected block: just write the values into this block */ 788 fillBlock(newTrie->data+block, 789 0, UTRIE2_DATA_BLOCK_LENGTH, 790 value, newTrie->initialValue, overwrite); 791 } 792 } else if(newTrie->data[block]!=value && (overwrite || block==newTrie->dataNullOffset)) { 793 /* 794 * Set the repeatBlock instead of the null block or previous repeat block: 795 * 796 * If !isWritableBlock() then all entries in the block have the same value 797 * because it's the null block or a range block (the repeatBlock from a previous 798 * call to utrie2_setRange32()). 799 * No other blocks are used multiple times before compacting. 800 * 801 * The null block is the only non-writable block with the initialValue because 802 * of the repeatBlock initialization above. (If value==initialValue, then 803 * the repeatBlock will be the null data block.) 804 * 805 * We set our repeatBlock if the desired value differs from the block's value, 806 * and if we overwrite any data or if the data is all initial values 807 * (which is the same as the block being the null block, see above). 808 */ 809 setRepeatBlock=TRUE; 810 } 811 if(setRepeatBlock) { 812 if(repeatBlock>=0) { 813 setIndex2Entry(newTrie, i2, repeatBlock); 814 } else { 815 /* create and set and fill the repeatBlock */ 816 repeatBlock=getDataBlock(newTrie, start, TRUE); 817 if(repeatBlock<0) { 818 *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 819 return; 820 } 821 writeBlock(newTrie->data+repeatBlock, value); 822 } 823 } 824 825 start+=UTRIE2_DATA_BLOCK_LENGTH; 826 } 827 828 if(rest>0) { 829 /* set partial block at [last block boundary..limit[ */ 830 block=getDataBlock(newTrie, start, TRUE); 831 if(block<0) { 832 *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 833 return; 834 } 835 836 fillBlock(newTrie->data+block, 0, rest, value, newTrie->initialValue, overwrite); 837 } 838 839 return; 840 } 841 842 /* compaction --------------------------------------------------------------- */ 843 844 static inline UBool 845 equal_int32(const int32_t *s, const int32_t *t, int32_t length) { 846 while(length>0 && *s==*t) { 847 ++s; 848 ++t; 849 --length; 850 } 851 return (UBool)(length==0); 852 } 853 854 static inline UBool 855 equal_uint32(const uint32_t *s, const uint32_t *t, int32_t length) { 856 while(length>0 && *s==*t) { 857 ++s; 858 ++t; 859 --length; 860 } 861 return (UBool)(length==0); 862 } 863 864 static int32_t 865 findSameIndex2Block(const int32_t *idx, int32_t index2Length, int32_t otherBlock) { 866 int32_t block; 867 868 /* ensure that we do not even partially get past index2Length */ 869 index2Length-=UTRIE2_INDEX_2_BLOCK_LENGTH; 870 871 for(block=0; block<=index2Length; ++block) { 872 if(equal_int32(idx+block, idx+otherBlock, UTRIE2_INDEX_2_BLOCK_LENGTH)) { 873 return block; 874 } 875 } 876 return -1; 877 } 878 879 static int32_t 880 findSameDataBlock(const uint32_t *data, int32_t dataLength, int32_t otherBlock, int32_t blockLength) { 881 int32_t block; 882 883 /* ensure that we do not even partially get past dataLength */ 884 dataLength-=blockLength; 885 886 for(block=0; block<=dataLength; block+=UTRIE2_DATA_GRANULARITY) { 887 if(equal_uint32(data+block, data+otherBlock, blockLength)) { 888 return block; 889 } 890 } 891 return -1; 892 } 893 894 /* 895 * Find the start of the last range in the trie by enumerating backward. 896 * Indexes for supplementary code points higher than this will be omitted. 897 */ 898 static UChar32 899 findHighStart(UNewTrie2 *trie, uint32_t highValue) { 900 const uint32_t *data32; 901 902 uint32_t value, initialValue; 903 UChar32 c, prev; 904 int32_t i1, i2, j, i2Block, prevI2Block, index2NullOffset, block, prevBlock, nullBlock; 905 906 data32=trie->data; 907 initialValue=trie->initialValue; 908 909 index2NullOffset=trie->index2NullOffset; 910 nullBlock=trie->dataNullOffset; 911 912 /* set variables for previous range */ 913 if(highValue==initialValue) { 914 prevI2Block=index2NullOffset; 915 prevBlock=nullBlock; 916 } else { 917 prevI2Block=-1; 918 prevBlock=-1; 919 } 920 prev=0x110000; 921 922 /* enumerate index-2 blocks */ 923 i1=UNEWTRIE2_INDEX_1_LENGTH; 924 c=prev; 925 while(c>0) { 926 i2Block=trie->index1[--i1]; 927 if(i2Block==prevI2Block) { 928 /* the index-2 block is the same as the previous one, and filled with highValue */ 929 c-=UTRIE2_CP_PER_INDEX_1_ENTRY; 930 continue; 931 } 932 prevI2Block=i2Block; 933 if(i2Block==index2NullOffset) { 934 /* this is the null index-2 block */ 935 if(highValue!=initialValue) { 936 return c; 937 } 938 c-=UTRIE2_CP_PER_INDEX_1_ENTRY; 939 } else { 940 /* enumerate data blocks for one index-2 block */ 941 for(i2=UTRIE2_INDEX_2_BLOCK_LENGTH; i2>0;) { 942 block=trie->index2[i2Block+ --i2]; 943 if(block==prevBlock) { 944 /* the block is the same as the previous one, and filled with highValue */ 945 c-=UTRIE2_DATA_BLOCK_LENGTH; 946 continue; 947 } 948 prevBlock=block; 949 if(block==nullBlock) { 950 /* this is the null data block */ 951 if(highValue!=initialValue) { 952 return c; 953 } 954 c-=UTRIE2_DATA_BLOCK_LENGTH; 955 } else { 956 for(j=UTRIE2_DATA_BLOCK_LENGTH; j>0;) { 957 value=data32[block+ --j]; 958 if(value!=highValue) { 959 return c; 960 } 961 --c; 962 } 963 } 964 } 965 } 966 } 967 968 /* deliver last range */ 969 return 0; 970 } 971 972 /* 973 * Compact a build-time trie. 974 * 975 * The compaction 976 * - removes blocks that are identical with earlier ones 977 * - overlaps adjacent blocks as much as possible (if overlap==TRUE) 978 * - moves blocks in steps of the data granularity 979 * - moves and overlaps blocks that overlap with multiple values in the overlap region 980 * 981 * It does not 982 * - try to move and overlap blocks that are not already adjacent 983 */ 984 static void 985 compactData(UNewTrie2 *trie) { 986 int32_t start, newStart, movedStart; 987 int32_t blockLength, overlap; 988 int32_t i, mapIndex, blockCount; 989 990 /* do not compact linear-ASCII data */ 991 newStart=UTRIE2_DATA_START_OFFSET; 992 for(start=0, i=0; start<newStart; start+=UTRIE2_DATA_BLOCK_LENGTH, ++i) { 993 trie->map[i]=start; 994 } 995 996 /* 997 * Start with a block length of 64 for 2-byte UTF-8, 998 * then switch to UTRIE2_DATA_BLOCK_LENGTH. 999 */ 1000 blockLength=64; 1001 blockCount=blockLength>>UTRIE2_SHIFT_2; 1002 for(start=newStart; start<trie->dataLength;) { 1003 /* 1004 * start: index of first entry of current block 1005 * newStart: index where the current block is to be moved 1006 * (right after current end of already-compacted data) 1007 */ 1008 if(start==UNEWTRIE2_DATA_0800_OFFSET) { 1009 blockLength=UTRIE2_DATA_BLOCK_LENGTH; 1010 blockCount=1; 1011 } 1012 1013 /* skip blocks that are not used */ 1014 if(trie->map[start>>UTRIE2_SHIFT_2]<=0) { 1015 /* advance start to the next block */ 1016 start+=blockLength; 1017 1018 /* leave newStart with the previous block! */ 1019 continue; 1020 } 1021 1022 /* search for an identical block */ 1023 if( (movedStart=findSameDataBlock(trie->data, newStart, start, blockLength)) 1024 >=0 1025 ) { 1026 /* found an identical block, set the other block's index value for the current block */ 1027 for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) { 1028 trie->map[mapIndex++]=movedStart; 1029 movedStart+=UTRIE2_DATA_BLOCK_LENGTH; 1030 } 1031 1032 /* advance start to the next block */ 1033 start+=blockLength; 1034 1035 /* leave newStart with the previous block! */ 1036 continue; 1037 } 1038 1039 /* see if the beginning of this block can be overlapped with the end of the previous block */ 1040 /* look for maximum overlap (modulo granularity) with the previous, adjacent block */ 1041 for(overlap=blockLength-UTRIE2_DATA_GRANULARITY; 1042 overlap>0 && !equal_uint32(trie->data+(newStart-overlap), trie->data+start, overlap); 1043 overlap-=UTRIE2_DATA_GRANULARITY) {} 1044 1045 if(overlap>0 || newStart<start) { 1046 /* some overlap, or just move the whole block */ 1047 movedStart=newStart-overlap; 1048 for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) { 1049 trie->map[mapIndex++]=movedStart; 1050 movedStart+=UTRIE2_DATA_BLOCK_LENGTH; 1051 } 1052 1053 /* move the non-overlapping indexes to their new positions */ 1054 start+=overlap; 1055 for(i=blockLength-overlap; i>0; --i) { 1056 trie->data[newStart++]=trie->data[start++]; 1057 } 1058 } else /* no overlap && newStart==start */ { 1059 for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) { 1060 trie->map[mapIndex++]=start; 1061 start+=UTRIE2_DATA_BLOCK_LENGTH; 1062 } 1063 newStart=start; 1064 } 1065 } 1066 1067 /* now adjust the index-2 table */ 1068 for(i=0; i<trie->index2Length; ++i) { 1069 if(i==UNEWTRIE2_INDEX_GAP_OFFSET) { 1070 /* Gap indexes are invalid (-1). Skip over the gap. */ 1071 i+=UNEWTRIE2_INDEX_GAP_LENGTH; 1072 } 1073 trie->index2[i]=trie->map[trie->index2[i]>>UTRIE2_SHIFT_2]; 1074 } 1075 trie->dataNullOffset=trie->map[trie->dataNullOffset>>UTRIE2_SHIFT_2]; 1076 1077 /* ensure dataLength alignment */ 1078 while((newStart&(UTRIE2_DATA_GRANULARITY-1))!=0) { 1079 trie->data[newStart++]=trie->initialValue; 1080 } 1081 1082 #ifdef UTRIE2_DEBUG 1083 /* we saved some space */ 1084 printf("compacting UTrie2: count of 32-bit data words %lu->%lu\n", 1085 (long)trie->dataLength, (long)newStart); 1086 #endif 1087 1088 trie->dataLength=newStart; 1089 } 1090 1091 static void 1092 compactIndex2(UNewTrie2 *trie) { 1093 int32_t i, start, newStart, movedStart, overlap; 1094 1095 /* do not compact linear-BMP index-2 blocks */ 1096 newStart=UTRIE2_INDEX_2_BMP_LENGTH; 1097 for(start=0, i=0; start<newStart; start+=UTRIE2_INDEX_2_BLOCK_LENGTH, ++i) { 1098 trie->map[i]=start; 1099 } 1100 1101 /* Reduce the index table gap to what will be needed at runtime. */ 1102 newStart+=UTRIE2_UTF8_2B_INDEX_2_LENGTH+((trie->highStart-0x10000)>>UTRIE2_SHIFT_1); 1103 1104 for(start=UNEWTRIE2_INDEX_2_NULL_OFFSET; start<trie->index2Length;) { 1105 /* 1106 * start: index of first entry of current block 1107 * newStart: index where the current block is to be moved 1108 * (right after current end of already-compacted data) 1109 */ 1110 1111 /* search for an identical block */ 1112 if( (movedStart=findSameIndex2Block(trie->index2, newStart, start)) 1113 >=0 1114 ) { 1115 /* found an identical block, set the other block's index value for the current block */ 1116 trie->map[start>>UTRIE2_SHIFT_1_2]=movedStart; 1117 1118 /* advance start to the next block */ 1119 start+=UTRIE2_INDEX_2_BLOCK_LENGTH; 1120 1121 /* leave newStart with the previous block! */ 1122 continue; 1123 } 1124 1125 /* see if the beginning of this block can be overlapped with the end of the previous block */ 1126 /* look for maximum overlap with the previous, adjacent block */ 1127 for(overlap=UTRIE2_INDEX_2_BLOCK_LENGTH-1; 1128 overlap>0 && !equal_int32(trie->index2+(newStart-overlap), trie->index2+start, overlap); 1129 --overlap) {} 1130 1131 if(overlap>0 || newStart<start) { 1132 /* some overlap, or just move the whole block */ 1133 trie->map[start>>UTRIE2_SHIFT_1_2]=newStart-overlap; 1134 1135 /* move the non-overlapping indexes to their new positions */ 1136 start+=overlap; 1137 for(i=UTRIE2_INDEX_2_BLOCK_LENGTH-overlap; i>0; --i) { 1138 trie->index2[newStart++]=trie->index2[start++]; 1139 } 1140 } else /* no overlap && newStart==start */ { 1141 trie->map[start>>UTRIE2_SHIFT_1_2]=start; 1142 start+=UTRIE2_INDEX_2_BLOCK_LENGTH; 1143 newStart=start; 1144 } 1145 } 1146 1147 /* now adjust the index-1 table */ 1148 for(i=0; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) { 1149 trie->index1[i]=trie->map[trie->index1[i]>>UTRIE2_SHIFT_1_2]; 1150 } 1151 trie->index2NullOffset=trie->map[trie->index2NullOffset>>UTRIE2_SHIFT_1_2]; 1152 1153 /* 1154 * Ensure data table alignment: 1155 * Needs to be granularity-aligned for 16-bit trie 1156 * (so that dataMove will be down-shiftable), 1157 * and 2-aligned for uint32_t data. 1158 */ 1159 while((newStart&((UTRIE2_DATA_GRANULARITY-1)|1))!=0) { 1160 /* Arbitrary value: 0x3fffc not possible for real data. */ 1161 trie->index2[newStart++]=(int32_t)0xffff<<UTRIE2_INDEX_SHIFT; 1162 } 1163 1164 #ifdef UTRIE2_DEBUG 1165 /* we saved some space */ 1166 printf("compacting UTrie2: count of 16-bit index-2 words %lu->%lu\n", 1167 (long)trie->index2Length, (long)newStart); 1168 #endif 1169 1170 trie->index2Length=newStart; 1171 } 1172 1173 static void 1174 compactTrie(UTrie2 *trie, UErrorCode *pErrorCode) { 1175 UNewTrie2 *newTrie; 1176 UChar32 highStart, suppHighStart; 1177 uint32_t highValue; 1178 1179 newTrie=trie->newTrie; 1180 1181 /* find highStart and round it up */ 1182 highValue=utrie2_get32(trie, 0x10ffff); 1183 highStart=findHighStart(newTrie, highValue); 1184 highStart=(highStart+(UTRIE2_CP_PER_INDEX_1_ENTRY-1))&~(UTRIE2_CP_PER_INDEX_1_ENTRY-1); 1185 if(highStart==0x110000) { 1186 highValue=trie->errorValue; 1187 } 1188 1189 /* 1190 * Set trie->highStart only after utrie2_get32(trie, highStart). 1191 * Otherwise utrie2_get32(trie, highStart) would try to read the highValue. 1192 */ 1193 trie->highStart=newTrie->highStart=highStart; 1194 1195 #ifdef UTRIE2_DEBUG 1196 printf("UTrie2: highStart U+%04lx highValue 0x%lx initialValue 0x%lx\n", 1197 (long)highStart, (long)highValue, (long)trie->initialValue); 1198 #endif 1199 1200 if(highStart<0x110000) { 1201 /* Blank out [highStart..10ffff] to release associated data blocks. */ 1202 suppHighStart= highStart<=0x10000 ? 0x10000 : highStart; 1203 utrie2_setRange32(trie, suppHighStart, 0x10ffff, trie->initialValue, TRUE, pErrorCode); 1204 if(U_FAILURE(*pErrorCode)) { 1205 return; 1206 } 1207 } 1208 1209 compactData(newTrie); 1210 if(highStart>0x10000) { 1211 compactIndex2(newTrie); 1212 #ifdef UTRIE2_DEBUG 1213 } else { 1214 printf("UTrie2: highStart U+%04lx count of 16-bit index-2 words %lu->%lu\n", 1215 (long)highStart, (long)trie->newTrie->index2Length, (long)UTRIE2_INDEX_1_OFFSET); 1216 #endif 1217 } 1218 1219 /* 1220 * Store the highValue in the data array and round up the dataLength. 1221 * Must be done after compactData() because that assumes that dataLength 1222 * is a multiple of UTRIE2_DATA_BLOCK_LENGTH. 1223 */ 1224 newTrie->data[newTrie->dataLength++]=highValue; 1225 while((newTrie->dataLength&(UTRIE2_DATA_GRANULARITY-1))!=0) { 1226 newTrie->data[newTrie->dataLength++]=trie->initialValue; 1227 } 1228 1229 newTrie->isCompacted=TRUE; 1230 } 1231 1232 /* serialization ------------------------------------------------------------ */ 1233 1234 /** 1235 * Maximum length of the runtime index array. 1236 * Limited by its own 16-bit index values, and by uint16_t UTrie2Header.indexLength. 1237 * (The actual maximum length is lower, 1238 * (0x110000>>UTRIE2_SHIFT_2)+UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH.) 1239 */ 1240 #define UTRIE2_MAX_INDEX_LENGTH 0xffff 1241 1242 /** 1243 * Maximum length of the runtime data array. 1244 * Limited by 16-bit index values that are left-shifted by UTRIE2_INDEX_SHIFT, 1245 * and by uint16_t UTrie2Header.shiftedDataLength. 1246 */ 1247 #define UTRIE2_MAX_DATA_LENGTH (0xffff<<UTRIE2_INDEX_SHIFT) 1248 1249 /* Compact and internally serialize the trie. */ 1250 U_CAPI void U_EXPORT2 1251 utrie2_freeze(UTrie2 *trie, UTrie2ValueBits valueBits, UErrorCode *pErrorCode) { 1252 UNewTrie2 *newTrie; 1253 UTrie2Header *header; 1254 uint32_t *p; 1255 uint16_t *dest16; 1256 int32_t i, length; 1257 int32_t allIndexesLength; 1258 int32_t dataMove; /* >0 if the data is moved to the end of the index array */ 1259 UChar32 highStart; 1260 1261 /* argument check */ 1262 if(U_FAILURE(*pErrorCode)) { 1263 return; 1264 } 1265 if( trie==NULL || 1266 valueBits<0 || UTRIE2_COUNT_VALUE_BITS<=valueBits 1267 ) { 1268 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 1269 return; 1270 } 1271 newTrie=trie->newTrie; 1272 if(newTrie==NULL) { 1273 /* already frozen */ 1274 UTrie2ValueBits frozenValueBits= 1275 trie->data16!=NULL ? UTRIE2_16_VALUE_BITS : UTRIE2_32_VALUE_BITS; 1276 if(valueBits!=frozenValueBits) { 1277 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 1278 } 1279 return; 1280 } 1281 1282 /* compact if necessary */ 1283 if(!newTrie->isCompacted) { 1284 compactTrie(trie, pErrorCode); 1285 if(U_FAILURE(*pErrorCode)) { 1286 return; 1287 } 1288 } 1289 highStart=trie->highStart; 1290 1291 if(highStart<=0x10000) { 1292 allIndexesLength=UTRIE2_INDEX_1_OFFSET; 1293 } else { 1294 allIndexesLength=newTrie->index2Length; 1295 } 1296 if(valueBits==UTRIE2_16_VALUE_BITS) { 1297 dataMove=allIndexesLength; 1298 } else { 1299 dataMove=0; 1300 } 1301 1302 /* are indexLength and dataLength within limits? */ 1303 if( /* for unshifted indexLength */ 1304 allIndexesLength>UTRIE2_MAX_INDEX_LENGTH || 1305 /* for unshifted dataNullOffset */ 1306 (dataMove+newTrie->dataNullOffset)>0xffff || 1307 /* for unshifted 2-byte UTF-8 index-2 values */ 1308 (dataMove+UNEWTRIE2_DATA_0800_OFFSET)>0xffff || 1309 /* for shiftedDataLength */ 1310 (dataMove+newTrie->dataLength)>UTRIE2_MAX_DATA_LENGTH 1311 ) { 1312 *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR; 1313 return; 1314 } 1315 1316 /* calculate the total serialized length */ 1317 length=sizeof(UTrie2Header)+allIndexesLength*2; 1318 if(valueBits==UTRIE2_16_VALUE_BITS) { 1319 length+=newTrie->dataLength*2; 1320 } else { 1321 length+=newTrie->dataLength*4; 1322 } 1323 1324 trie->memory=uprv_malloc(length); 1325 if(trie->memory==NULL) { 1326 *pErrorCode=U_MEMORY_ALLOCATION_ERROR; 1327 return; 1328 } 1329 trie->length=length; 1330 trie->isMemoryOwned=TRUE; 1331 1332 trie->indexLength=allIndexesLength; 1333 trie->dataLength=newTrie->dataLength; 1334 if(highStart<=0x10000) { 1335 trie->index2NullOffset=0xffff; 1336 } else { 1337 trie->index2NullOffset=UTRIE2_INDEX_2_OFFSET+newTrie->index2NullOffset; 1338 } 1339 trie->dataNullOffset=(uint16_t)(dataMove+newTrie->dataNullOffset); 1340 trie->highValueIndex=dataMove+trie->dataLength-UTRIE2_DATA_GRANULARITY; 1341 1342 /* set the header fields */ 1343 header=(UTrie2Header *)trie->memory; 1344 1345 header->signature=UTRIE2_SIG; /* "Tri2" */ 1346 header->options=(uint16_t)valueBits; 1347 1348 header->indexLength=(uint16_t)trie->indexLength; 1349 header->shiftedDataLength=(uint16_t)(trie->dataLength>>UTRIE2_INDEX_SHIFT); 1350 header->index2NullOffset=trie->index2NullOffset; 1351 header->dataNullOffset=trie->dataNullOffset; 1352 header->shiftedHighStart=(uint16_t)(highStart>>UTRIE2_SHIFT_1); 1353 1354 /* fill the index and data arrays */ 1355 dest16=(uint16_t *)(header+1); 1356 trie->index=dest16; 1357 1358 /* write the index-2 array values shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove */ 1359 p=(uint32_t *)newTrie->index2; 1360 for(i=UTRIE2_INDEX_2_BMP_LENGTH; i>0; --i) { 1361 *dest16++=(uint16_t)((dataMove + *p++)>>UTRIE2_INDEX_SHIFT); 1362 } 1363 1364 /* write UTF-8 2-byte index-2 values, not right-shifted */ 1365 for(i=0; i<(0xc2-0xc0); ++i) { /* C0..C1 */ 1366 *dest16++=(uint16_t)(dataMove+UTRIE2_BAD_UTF8_DATA_OFFSET); 1367 } 1368 for(; i<(0xe0-0xc0); ++i) { /* C2..DF */ 1369 *dest16++=(uint16_t)(dataMove+newTrie->index2[i<<(6-UTRIE2_SHIFT_2)]); 1370 } 1371 1372 if(highStart>0x10000) { 1373 int32_t index1Length=(highStart-0x10000)>>UTRIE2_SHIFT_1; 1374 int32_t index2Offset=UTRIE2_INDEX_2_BMP_LENGTH+UTRIE2_UTF8_2B_INDEX_2_LENGTH+index1Length; 1375 1376 /* write 16-bit index-1 values for supplementary code points */ 1377 p=(uint32_t *)newTrie->index1+UTRIE2_OMITTED_BMP_INDEX_1_LENGTH; 1378 for(i=index1Length; i>0; --i) { 1379 *dest16++=(uint16_t)(UTRIE2_INDEX_2_OFFSET + *p++); 1380 } 1381 1382 /* 1383 * write the index-2 array values for supplementary code points, 1384 * shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove 1385 */ 1386 p=(uint32_t *)newTrie->index2+index2Offset; 1387 for(i=newTrie->index2Length-index2Offset; i>0; --i) { 1388 *dest16++=(uint16_t)((dataMove + *p++)>>UTRIE2_INDEX_SHIFT); 1389 } 1390 } 1391 1392 /* write the 16/32-bit data array */ 1393 switch(valueBits) { 1394 case UTRIE2_16_VALUE_BITS: 1395 /* write 16-bit data values */ 1396 trie->data16=dest16; 1397 trie->data32=NULL; 1398 p=newTrie->data; 1399 for(i=newTrie->dataLength; i>0; --i) { 1400 *dest16++=(uint16_t)*p++; 1401 } 1402 break; 1403 case UTRIE2_32_VALUE_BITS: 1404 /* write 32-bit data values */ 1405 trie->data16=NULL; 1406 trie->data32=(uint32_t *)dest16; 1407 uprv_memcpy(dest16, newTrie->data, (size_t)newTrie->dataLength*4); 1408 break; 1409 default: 1410 *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; 1411 return; 1412 } 1413 1414 /* Delete the UNewTrie2. */ 1415 uprv_free(newTrie->data); 1416 uprv_free(newTrie); 1417 trie->newTrie=NULL; 1418 } 1419 1420 /* 1421 * This is here to avoid a dependency from utrie2.cpp on utrie.c. 1422 * This file already depends on utrie.c. 1423 * Otherwise, this should be in utrie2.cpp right after utrie2_swap(). 1424 */ 1425 U_CAPI int32_t U_EXPORT2 1426 utrie2_swapAnyVersion(const UDataSwapper *ds, 1427 const void *inData, int32_t length, void *outData, 1428 UErrorCode *pErrorCode) { 1429 if(U_SUCCESS(*pErrorCode)) { 1430 switch(utrie2_getVersion(inData, length, TRUE)) { 1431 case 1: 1432 return utrie_swap(ds, inData, length, outData, pErrorCode); 1433 case 2: 1434 return utrie2_swap(ds, inData, length, outData, pErrorCode); 1435 default: 1436 *pErrorCode=U_INVALID_FORMAT_ERROR; 1437 return 0; 1438 } 1439 } 1440 return 0; 1441 } 1442
