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) 2003-2014, International Business Machines 7 * Corporation and others. All Rights Reserved. 8 * 9 ******************************************************************************* 10 * file name: gencnvex.c 11 * encoding: UTF-8 12 * tab size: 8 (not used) 13 * indentation:4 14 * 15 * created on: 2003oct12 16 * created by: Markus W. Scherer 17 */ 18 19 #include <stdio.h> 20 #include "unicode/utypes.h" 21 #include "unicode/ustring.h" 22 #include "cstring.h" 23 #include "cmemory.h" 24 #include "ucnv_cnv.h" 25 #include "ucnvmbcs.h" 26 #include "toolutil.h" 27 #include "unewdata.h" 28 #include "ucm.h" 29 #include "makeconv.h" 30 #include "genmbcs.h" 31 32 static void 33 CnvExtClose(NewConverter *cnvData); 34 35 static UBool 36 CnvExtIsValid(NewConverter *cnvData, 37 const uint8_t *bytes, int32_t length); 38 39 static UBool 40 CnvExtAddTable(NewConverter *cnvData, UCMTable *table, UConverterStaticData *staticData); 41 42 static uint32_t 43 CnvExtWrite(NewConverter *cnvData, const UConverterStaticData *staticData, 44 UNewDataMemory *pData, int32_t tableType); 45 46 typedef struct CnvExtData { 47 NewConverter newConverter; 48 49 UCMFile *ucm; 50 51 /* toUnicode (state table in ucm->states) */ 52 UToolMemory *toUTable, *toUUChars; 53 54 /* fromUnicode */ 55 UToolMemory *fromUTableUChars, *fromUTableValues, *fromUBytes; 56 57 uint16_t stage1[MBCS_STAGE_1_SIZE]; 58 uint16_t stage2[MBCS_STAGE_2_SIZE]; 59 uint16_t stage3[0x10000<<UCNV_EXT_STAGE_2_LEFT_SHIFT]; /* 0x10000 because of 16-bit stage 2/3 indexes */ 60 uint32_t stage3b[0x10000]; 61 62 int32_t stage1Top, stage2Top, stage3Top, stage3bTop; 63 64 /* for stage3 compaction of <subchar1> |2 mappings */ 65 uint16_t stage3Sub1Block; 66 67 /* statistics */ 68 int32_t 69 maxInBytes, maxOutBytes, maxBytesPerUChar, 70 maxInUChars, maxOutUChars, maxUCharsPerByte; 71 } CnvExtData; 72 73 NewConverter * 74 CnvExtOpen(UCMFile *ucm) { 75 CnvExtData *extData; 76 77 extData=(CnvExtData *)uprv_malloc(sizeof(CnvExtData)); 78 if(extData==NULL) { 79 printf("out of memory\n"); 80 exit(U_MEMORY_ALLOCATION_ERROR); 81 } 82 uprv_memset(extData, 0, sizeof(CnvExtData)); 83 84 extData->ucm=ucm; /* aliased, not owned */ 85 86 extData->newConverter.close=CnvExtClose; 87 extData->newConverter.isValid=CnvExtIsValid; 88 extData->newConverter.addTable=CnvExtAddTable; 89 extData->newConverter.write=CnvExtWrite; 90 return &extData->newConverter; 91 } 92 93 static void 94 CnvExtClose(NewConverter *cnvData) { 95 CnvExtData *extData=(CnvExtData *)cnvData; 96 if(extData!=NULL) { 97 utm_close(extData->toUTable); 98 utm_close(extData->toUUChars); 99 utm_close(extData->fromUTableUChars); 100 utm_close(extData->fromUTableValues); 101 utm_close(extData->fromUBytes); 102 uprv_free(extData); 103 } 104 } 105 106 /* we do not expect this to be called */ 107 static UBool 108 CnvExtIsValid(NewConverter *cnvData, 109 const uint8_t *bytes, int32_t length) { 110 return FALSE; 111 } 112 113 static uint32_t 114 CnvExtWrite(NewConverter *cnvData, const UConverterStaticData *staticData, 115 UNewDataMemory *pData, int32_t tableType) { 116 CnvExtData *extData=(CnvExtData *)cnvData; 117 int32_t length, top, headerSize; 118 119 int32_t indexes[UCNV_EXT_INDEXES_MIN_LENGTH]={ 0 }; 120 121 if(tableType&TABLE_BASE) { 122 headerSize=0; 123 } else { 124 _MBCSHeader header={ { 0, 0, 0, 0 }, 0, 0, 0, 0, 0, 0, 0 }; 125 126 /* write the header and base table name for an extension-only table */ 127 length=(int32_t)uprv_strlen(extData->ucm->baseName)+1; 128 while(length&3) { 129 /* add padding */ 130 extData->ucm->baseName[length++]=0; 131 } 132 133 headerSize=MBCS_HEADER_V4_LENGTH*4+length; 134 135 /* fill the header */ 136 header.version[0]=4; 137 header.version[1]=2; 138 header.flags=(uint32_t)((headerSize<<8)|MBCS_OUTPUT_EXT_ONLY); 139 140 /* write the header and the base table name */ 141 udata_writeBlock(pData, &header, MBCS_HEADER_V4_LENGTH*4); 142 udata_writeBlock(pData, extData->ucm->baseName, length); 143 } 144 145 /* fill indexes[] - offsets/indexes are in units of the target array */ 146 top=0; 147 148 indexes[UCNV_EXT_INDEXES_LENGTH]=length=UCNV_EXT_INDEXES_MIN_LENGTH; 149 top+=length*4; 150 151 indexes[UCNV_EXT_TO_U_INDEX]=top; 152 indexes[UCNV_EXT_TO_U_LENGTH]=length=utm_countItems(extData->toUTable); 153 top+=length*4; 154 155 indexes[UCNV_EXT_TO_U_UCHARS_INDEX]=top; 156 indexes[UCNV_EXT_TO_U_UCHARS_LENGTH]=length=utm_countItems(extData->toUUChars); 157 top+=length*2; 158 159 indexes[UCNV_EXT_FROM_U_UCHARS_INDEX]=top; 160 length=utm_countItems(extData->fromUTableUChars); 161 top+=length*2; 162 163 if(top&3) { 164 /* add padding */ 165 *((UChar *)utm_alloc(extData->fromUTableUChars))=0; 166 *((uint32_t *)utm_alloc(extData->fromUTableValues))=0; 167 ++length; 168 top+=2; 169 } 170 indexes[UCNV_EXT_FROM_U_LENGTH]=length; 171 172 indexes[UCNV_EXT_FROM_U_VALUES_INDEX]=top; 173 top+=length*4; 174 175 indexes[UCNV_EXT_FROM_U_BYTES_INDEX]=top; 176 length=utm_countItems(extData->fromUBytes); 177 top+=length; 178 179 if(top&1) { 180 /* add padding */ 181 *((uint8_t *)utm_alloc(extData->fromUBytes))=0; 182 ++length; 183 ++top; 184 } 185 indexes[UCNV_EXT_FROM_U_BYTES_LENGTH]=length; 186 187 indexes[UCNV_EXT_FROM_U_STAGE_12_INDEX]=top; 188 indexes[UCNV_EXT_FROM_U_STAGE_1_LENGTH]=length=extData->stage1Top; 189 indexes[UCNV_EXT_FROM_U_STAGE_12_LENGTH]=length+=extData->stage2Top; 190 top+=length*2; 191 192 indexes[UCNV_EXT_FROM_U_STAGE_3_INDEX]=top; 193 length=extData->stage3Top; 194 top+=length*2; 195 196 if(top&3) { 197 /* add padding */ 198 extData->stage3[extData->stage3Top++]=0; 199 ++length; 200 top+=2; 201 } 202 indexes[UCNV_EXT_FROM_U_STAGE_3_LENGTH]=length; 203 204 indexes[UCNV_EXT_FROM_U_STAGE_3B_INDEX]=top; 205 indexes[UCNV_EXT_FROM_U_STAGE_3B_LENGTH]=length=extData->stage3bTop; 206 top+=length*4; 207 208 indexes[UCNV_EXT_SIZE]=top; 209 210 /* statistics */ 211 indexes[UCNV_EXT_COUNT_BYTES]= 212 (extData->maxInBytes<<16)| 213 (extData->maxOutBytes<<8)| 214 extData->maxBytesPerUChar; 215 indexes[UCNV_EXT_COUNT_UCHARS]= 216 (extData->maxInUChars<<16)| 217 (extData->maxOutUChars<<8)| 218 extData->maxUCharsPerByte; 219 220 indexes[UCNV_EXT_FLAGS]=extData->ucm->ext->unicodeMask; 221 222 /* write the extension data */ 223 udata_writeBlock(pData, indexes, sizeof(indexes)); 224 udata_writeBlock(pData, utm_getStart(extData->toUTable), indexes[UCNV_EXT_TO_U_LENGTH]*4); 225 udata_writeBlock(pData, utm_getStart(extData->toUUChars), indexes[UCNV_EXT_TO_U_UCHARS_LENGTH]*2); 226 227 udata_writeBlock(pData, utm_getStart(extData->fromUTableUChars), indexes[UCNV_EXT_FROM_U_LENGTH]*2); 228 udata_writeBlock(pData, utm_getStart(extData->fromUTableValues), indexes[UCNV_EXT_FROM_U_LENGTH]*4); 229 udata_writeBlock(pData, utm_getStart(extData->fromUBytes), indexes[UCNV_EXT_FROM_U_BYTES_LENGTH]); 230 231 udata_writeBlock(pData, extData->stage1, extData->stage1Top*2); 232 udata_writeBlock(pData, extData->stage2, extData->stage2Top*2); 233 udata_writeBlock(pData, extData->stage3, extData->stage3Top*2); 234 udata_writeBlock(pData, extData->stage3b, extData->stage3bTop*4); 235 236 #if 0 237 { 238 int32_t i, j; 239 240 length=extData->stage1Top; 241 printf("\nstage1[%x]:\n", length); 242 243 for(i=0; i<length; ++i) { 244 if(extData->stage1[i]!=length) { 245 printf("stage1[%04x]=%04x\n", i, extData->stage1[i]); 246 } 247 } 248 249 j=length; 250 length=extData->stage2Top; 251 printf("\nstage2[%x]:\n", length); 252 253 for(i=0; i<length; ++j, ++i) { 254 if(extData->stage2[i]!=0) { 255 printf("stage12[%04x]=%04x\n", j, extData->stage2[i]); 256 } 257 } 258 259 length=extData->stage3Top; 260 printf("\nstage3[%x]:\n", length); 261 262 for(i=0; i<length; ++i) { 263 if(extData->stage3[i]!=0) { 264 printf("stage3[%04x]=%04x\n", i, extData->stage3[i]); 265 } 266 } 267 268 length=extData->stage3bTop; 269 printf("\nstage3b[%x]:\n", length); 270 271 for(i=0; i<length; ++i) { 272 if(extData->stage3b[i]!=0) { 273 printf("stage3b[%04x]=%08x\n", i, extData->stage3b[i]); 274 } 275 } 276 } 277 #endif 278 279 if(VERBOSE) { 280 printf("size of extension data: %ld\n", (long)top); 281 } 282 283 /* return the number of bytes that should have been written */ 284 return (uint32_t)(headerSize+top); 285 } 286 287 /* to Unicode --------------------------------------------------------------- */ 288 289 /* 290 * Remove fromUnicode fallbacks and SUB mappings which are irrelevant for 291 * the toUnicode table. 292 * This includes mappings with MBCS_FROM_U_EXT_FLAG which were suitable 293 * for the base toUnicode table but not for the base fromUnicode table. 294 * The table must be sorted. 295 * Modifies previous data in the reverseMap. 296 */ 297 static int32_t 298 reduceToUMappings(UCMTable *table) { 299 UCMapping *mappings; 300 int32_t *map; 301 int32_t i, j, count; 302 int8_t flag; 303 304 mappings=table->mappings; 305 map=table->reverseMap; 306 count=table->mappingsLength; 307 308 /* leave the map alone for the initial mappings with desired flags */ 309 for(i=j=0; i<count; ++i) { 310 flag=mappings[map[i]].f; 311 if(flag!=0 && flag!=3) { 312 break; 313 } 314 } 315 316 /* reduce from here to the rest */ 317 for(j=i; i<count; ++i) { 318 flag=mappings[map[i]].f; 319 if(flag==0 || flag==3) { 320 map[j++]=map[i]; 321 } 322 } 323 324 return j; 325 } 326 327 static uint32_t 328 getToUnicodeValue(CnvExtData *extData, UCMTable *table, UCMapping *m) { 329 UChar32 *u32; 330 UChar *u; 331 uint32_t value; 332 int32_t u16Length, ratio; 333 UErrorCode errorCode; 334 335 /* write the Unicode result code point or string index */ 336 if(m->uLen==1) { 337 u16Length=U16_LENGTH(m->u); 338 value=(uint32_t)(UCNV_EXT_TO_U_MIN_CODE_POINT+m->u); 339 } else { 340 /* the parser enforces m->uLen<=UCNV_EXT_MAX_UCHARS */ 341 342 /* get the result code point string and its 16-bit string length */ 343 u32=UCM_GET_CODE_POINTS(table, m); 344 errorCode=U_ZERO_ERROR; 345 u_strFromUTF32(NULL, 0, &u16Length, u32, m->uLen, &errorCode); 346 if(U_FAILURE(errorCode) && errorCode!=U_BUFFER_OVERFLOW_ERROR) { 347 exit(errorCode); 348 } 349 350 /* allocate it and put its length and index into the value */ 351 value= 352 (((uint32_t)u16Length+UCNV_EXT_TO_U_LENGTH_OFFSET)<<UCNV_EXT_TO_U_LENGTH_SHIFT)| 353 ((uint32_t)utm_countItems(extData->toUUChars)); 354 u=utm_allocN(extData->toUUChars, u16Length); 355 356 /* write the result 16-bit string */ 357 errorCode=U_ZERO_ERROR; 358 u_strFromUTF32(u, u16Length, NULL, u32, m->uLen, &errorCode); 359 if(U_FAILURE(errorCode) && errorCode!=U_BUFFER_OVERFLOW_ERROR) { 360 exit(errorCode); 361 } 362 } 363 if(m->f==0) { 364 value|=UCNV_EXT_TO_U_ROUNDTRIP_FLAG; 365 } 366 367 /* update statistics */ 368 if(m->bLen>extData->maxInBytes) { 369 extData->maxInBytes=m->bLen; 370 } 371 if(u16Length>extData->maxOutUChars) { 372 extData->maxOutUChars=u16Length; 373 } 374 375 ratio=(u16Length+(m->bLen-1))/m->bLen; 376 if(ratio>extData->maxUCharsPerByte) { 377 extData->maxUCharsPerByte=ratio; 378 } 379 380 return value; 381 } 382 383 /* 384 * Recursive toUTable generator core function. 385 * Preconditions: 386 * - start<limit (There is at least one mapping.) 387 * - The mappings are sorted lexically. (Access is through the reverseMap.) 388 * - All mappings between start and limit have input sequences that share 389 * the same prefix of unitIndex length, and therefore all of these sequences 390 * are at least unitIndex+1 long. 391 * - There are only relevant mappings available through the reverseMap, 392 * see reduceToUMappings(). 393 * 394 * One function invocation generates one section table. 395 * 396 * Steps: 397 * 1. Count the number of unique unit values and get the low/high unit values 398 * that occur at unitIndex. 399 * 2. Allocate the section table with possible optimization for linear access. 400 * 3. Write temporary version of the section table with start indexes of 401 * subsections, each corresponding to one unit value at unitIndex. 402 * 4. Iterate through the table once more, and depending on the subsection length: 403 * 0: write 0 as a result value (unused byte in linear-access section table) 404 * >0: if there is one mapping with an input unit sequence of unitIndex+1 405 * then defaultValue=compute the mapping result for this whole sequence 406 * else defaultValue=0 407 * 408 * recurse into the subsection 409 */ 410 static UBool 411 generateToUTable(CnvExtData *extData, UCMTable *table, 412 int32_t start, int32_t limit, int32_t unitIndex, 413 uint32_t defaultValue) { 414 UCMapping *mappings, *m; 415 int32_t *map; 416 int32_t i, j, uniqueCount, count, subStart, subLimit; 417 418 uint8_t *bytes; 419 int32_t low, high, prev; 420 421 uint32_t *section; 422 423 mappings=table->mappings; 424 map=table->reverseMap; 425 426 /* step 1: examine the input units; set low, high, uniqueCount */ 427 m=mappings+map[start]; 428 bytes=UCM_GET_BYTES(table, m); 429 low=bytes[unitIndex]; 430 uniqueCount=1; 431 432 prev=high=low; 433 for(i=start+1; i<limit; ++i) { 434 m=mappings+map[i]; 435 bytes=UCM_GET_BYTES(table, m); 436 high=bytes[unitIndex]; 437 438 if(high!=prev) { 439 prev=high; 440 ++uniqueCount; 441 } 442 } 443 444 /* step 2: allocate the section; set count, section */ 445 count=(high-low)+1; 446 if(count<0x100 && (unitIndex==0 || uniqueCount>=(3*count)/4)) { 447 /* 448 * for the root table and for fairly full tables: 449 * allocate for direct, linear array access 450 * by keeping count, to write an entry for each unit value 451 * from low to high 452 * exception: use a compact table if count==0x100 because 453 * that cannot be encoded in the length byte 454 */ 455 } else { 456 count=uniqueCount; 457 } 458 459 if(count>=0x100) { 460 fprintf(stderr, "error: toUnicode extension table section overflow: %ld section entries\n", (long)count); 461 return FALSE; 462 } 463 464 /* allocate the section: 1 entry for the header + count for the items */ 465 section=(uint32_t *)utm_allocN(extData->toUTable, 1+count); 466 467 /* write the section header */ 468 *section++=((uint32_t)count<<UCNV_EXT_TO_U_BYTE_SHIFT)|defaultValue; 469 470 /* step 3: write temporary section table with subsection starts */ 471 prev=low-1; /* just before low to prevent empty subsections before low */ 472 j=0; /* section table index */ 473 for(i=start; i<limit; ++i) { 474 m=mappings+map[i]; 475 bytes=UCM_GET_BYTES(table, m); 476 high=bytes[unitIndex]; 477 478 if(high!=prev) { 479 /* start of a new subsection for unit high */ 480 if(count>uniqueCount) { 481 /* write empty subsections for unused units in a linear table */ 482 while(++prev<high) { 483 section[j++]=((uint32_t)prev<<UCNV_EXT_TO_U_BYTE_SHIFT)|(uint32_t)i; 484 } 485 } else { 486 prev=high; 487 } 488 489 /* write the entry with the subsection start */ 490 section[j++]=((uint32_t)high<<UCNV_EXT_TO_U_BYTE_SHIFT)|(uint32_t)i; 491 } 492 } 493 /* assert(j==count) */ 494 495 /* step 4: recurse and write results */ 496 subLimit=UCNV_EXT_TO_U_GET_VALUE(section[0]); 497 for(j=0; j<count; ++j) { 498 subStart=subLimit; 499 subLimit= (j+1)<count ? UCNV_EXT_TO_U_GET_VALUE(section[j+1]) : limit; 500 501 /* remove the subStart temporary value */ 502 section[j]&=~UCNV_EXT_TO_U_VALUE_MASK; 503 504 if(subStart==subLimit) { 505 /* leave the value zero: empty subsection for unused unit in a linear table */ 506 continue; 507 } 508 509 /* see if there is exactly one input unit sequence of length unitIndex+1 */ 510 defaultValue=0; 511 m=mappings+map[subStart]; 512 if(m->bLen==unitIndex+1) { 513 /* do not include this in generateToUTable() */ 514 ++subStart; 515 516 if(subStart<subLimit && mappings[map[subStart]].bLen==unitIndex+1) { 517 /* print error for multiple same-input-sequence mappings */ 518 fprintf(stderr, "error: multiple mappings from same bytes\n"); 519 ucm_printMapping(table, m, stderr); 520 ucm_printMapping(table, mappings+map[subStart], stderr); 521 return FALSE; 522 } 523 524 defaultValue=getToUnicodeValue(extData, table, m); 525 } 526 527 if(subStart==subLimit) { 528 /* write the result for the input sequence ending here */ 529 section[j]|=defaultValue; 530 } else { 531 /* write the index to the subsection table */ 532 section[j]|=(uint32_t)utm_countItems(extData->toUTable); 533 534 /* recurse */ 535 if(!generateToUTable(extData, table, subStart, subLimit, unitIndex+1, defaultValue)) { 536 return FALSE; 537 } 538 } 539 } 540 return TRUE; 541 } 542 543 /* 544 * Generate the toUTable and toUUChars from the input table. 545 * The input table must be sorted, and all precision flags must be 0..3. 546 * This function will modify the table's reverseMap. 547 */ 548 static UBool 549 makeToUTable(CnvExtData *extData, UCMTable *table) { 550 int32_t toUCount; 551 552 toUCount=reduceToUMappings(table); 553 554 extData->toUTable=utm_open("cnv extension toUTable", 0x10000, UCNV_EXT_TO_U_MIN_CODE_POINT, 4); 555 extData->toUUChars=utm_open("cnv extension toUUChars", 0x10000, UCNV_EXT_TO_U_INDEX_MASK+1, 2); 556 557 return generateToUTable(extData, table, 0, toUCount, 0, 0); 558 } 559 560 /* from Unicode ------------------------------------------------------------- */ 561 562 /* 563 * preprocessing: 564 * rebuild reverseMap with mapping indexes for mappings relevant for from Unicode 565 * change each Unicode string to encode all but the first code point in 16-bit form 566 * 567 * generation: 568 * for each unique code point 569 * write an entry in the 3-stage trie 570 * check that there is only one single-code point sequence 571 * start recursion for following 16-bit input units 572 */ 573 574 /* 575 * Remove toUnicode fallbacks and non-<subchar1> SUB mappings 576 * which are irrelevant for the fromUnicode extension table. 577 * Remove MBCS_FROM_U_EXT_FLAG bits. 578 * Overwrite the reverseMap with an index array to the relevant mappings. 579 * Modify the code point sequences to a generator-friendly format where 580 * the first code points remains unchanged but the following are recoded 581 * into 16-bit Unicode string form. 582 * The table must be sorted. 583 * Destroys previous data in the reverseMap. 584 */ 585 static int32_t 586 prepareFromUMappings(UCMTable *table) { 587 UCMapping *mappings, *m; 588 int32_t *map; 589 int32_t i, j, count; 590 int8_t flag; 591 592 mappings=table->mappings; 593 map=table->reverseMap; 594 count=table->mappingsLength; 595 596 /* 597 * we do not go through the map on input because the mappings are 598 * sorted lexically 599 */ 600 m=mappings; 601 602 for(i=j=0; i<count; ++m, ++i) { 603 flag=m->f; 604 if(flag>=0) { 605 flag&=MBCS_FROM_U_EXT_MASK; 606 m->f=flag; 607 } 608 if(flag==0 || flag==1 || (flag==2 && m->bLen==1) || flag==4) { 609 map[j++]=i; 610 611 if(m->uLen>1) { 612 /* recode all but the first code point to 16-bit Unicode */ 613 UChar32 *u32; 614 UChar *u; 615 UChar32 c; 616 int32_t q, r; 617 618 u32=UCM_GET_CODE_POINTS(table, m); 619 u=(UChar *)u32; /* destructive in-place recoding */ 620 for(r=2, q=1; q<m->uLen; ++q) { 621 c=u32[q]; 622 U16_APPEND_UNSAFE(u, r, c); 623 } 624 625 /* counts the first code point always at 2 - the first 16-bit unit is at 16-bit index 2 */ 626 m->uLen=(int8_t)r; 627 } 628 } 629 } 630 631 return j; 632 } 633 634 static uint32_t 635 getFromUBytesValue(CnvExtData *extData, UCMTable *table, UCMapping *m) { 636 uint8_t *bytes, *resultBytes; 637 uint32_t value; 638 int32_t u16Length, ratio; 639 640 if(m->f==2) { 641 /* 642 * no mapping, <subchar1> preferred 643 * 644 * no need to count in statistics because the subchars are already 645 * counted for maxOutBytes and maxBytesPerUChar in UConverterStaticData, 646 * and this non-mapping does not count for maxInUChars which are always 647 * trivially at least two if counting unmappable supplementary code points 648 */ 649 return UCNV_EXT_FROM_U_SUBCHAR1; 650 } 651 652 bytes=UCM_GET_BYTES(table, m); 653 value=0; 654 switch(m->bLen) { 655 /* 1..3: store the bytes in the value word */ 656 case 3: 657 value=((uint32_t)*bytes++)<<16; 658 case 2: 659 value|=((uint32_t)*bytes++)<<8; 660 case 1: 661 value|=*bytes; 662 break; 663 default: 664 /* the parser enforces m->bLen<=UCNV_EXT_MAX_BYTES */ 665 /* store the bytes in fromUBytes[] and the index in the value word */ 666 value=(uint32_t)utm_countItems(extData->fromUBytes); 667 resultBytes=utm_allocN(extData->fromUBytes, m->bLen); 668 uprv_memcpy(resultBytes, bytes, m->bLen); 669 break; 670 } 671 value|=(uint32_t)m->bLen<<UCNV_EXT_FROM_U_LENGTH_SHIFT; 672 if(m->f==0) { 673 value|=UCNV_EXT_FROM_U_ROUNDTRIP_FLAG; 674 } else if(m->f==4) { 675 value|=UCNV_EXT_FROM_U_GOOD_ONE_WAY_FLAG; 676 } 677 678 /* calculate the real UTF-16 length (see recoding in prepareFromUMappings()) */ 679 if(m->uLen==1) { 680 u16Length=U16_LENGTH(m->u); 681 } else { 682 u16Length=U16_LENGTH(UCM_GET_CODE_POINTS(table, m)[0])+(m->uLen-2); 683 } 684 685 /* update statistics */ 686 if(u16Length>extData->maxInUChars) { 687 extData->maxInUChars=u16Length; 688 } 689 if(m->bLen>extData->maxOutBytes) { 690 extData->maxOutBytes=m->bLen; 691 } 692 693 ratio=(m->bLen+(u16Length-1))/u16Length; 694 if(ratio>extData->maxBytesPerUChar) { 695 extData->maxBytesPerUChar=ratio; 696 } 697 698 return value; 699 } 700 701 /* 702 * works like generateToUTable(), except that the 703 * output section consists of two arrays, one for input UChars and one 704 * for result values 705 * 706 * also, fromUTable sections are always stored in a compact form for 707 * access via binary search 708 */ 709 static UBool 710 generateFromUTable(CnvExtData *extData, UCMTable *table, 711 int32_t start, int32_t limit, int32_t unitIndex, 712 uint32_t defaultValue) { 713 UCMapping *mappings, *m; 714 int32_t *map; 715 int32_t i, j, uniqueCount, count, subStart, subLimit; 716 717 UChar *uchars; 718 UChar32 low, high, prev; 719 720 UChar *sectionUChars; 721 uint32_t *sectionValues; 722 723 mappings=table->mappings; 724 map=table->reverseMap; 725 726 /* step 1: examine the input units; set low, high, uniqueCount */ 727 m=mappings+map[start]; 728 uchars=(UChar *)UCM_GET_CODE_POINTS(table, m); 729 low=uchars[unitIndex]; 730 uniqueCount=1; 731 732 prev=high=low; 733 for(i=start+1; i<limit; ++i) { 734 m=mappings+map[i]; 735 uchars=(UChar *)UCM_GET_CODE_POINTS(table, m); 736 high=uchars[unitIndex]; 737 738 if(high!=prev) { 739 prev=high; 740 ++uniqueCount; 741 } 742 } 743 744 /* step 2: allocate the section; set count, section */ 745 /* the fromUTable always stores for access via binary search */ 746 count=uniqueCount; 747 748 /* allocate the section: 1 entry for the header + count for the items */ 749 sectionUChars=(UChar *)utm_allocN(extData->fromUTableUChars, 1+count); 750 sectionValues=(uint32_t *)utm_allocN(extData->fromUTableValues, 1+count); 751 752 /* write the section header */ 753 *sectionUChars++=(UChar)count; 754 *sectionValues++=defaultValue; 755 756 /* step 3: write temporary section table with subsection starts */ 757 prev=low-1; /* just before low to prevent empty subsections before low */ 758 j=0; /* section table index */ 759 for(i=start; i<limit; ++i) { 760 m=mappings+map[i]; 761 uchars=(UChar *)UCM_GET_CODE_POINTS(table, m); 762 high=uchars[unitIndex]; 763 764 if(high!=prev) { 765 /* start of a new subsection for unit high */ 766 prev=high; 767 768 /* write the entry with the subsection start */ 769 sectionUChars[j]=(UChar)high; 770 sectionValues[j]=(uint32_t)i; 771 ++j; 772 } 773 } 774 /* assert(j==count) */ 775 776 /* step 4: recurse and write results */ 777 subLimit=(int32_t)(sectionValues[0]); 778 for(j=0; j<count; ++j) { 779 subStart=subLimit; 780 subLimit= (j+1)<count ? (int32_t)(sectionValues[j+1]) : limit; 781 782 /* see if there is exactly one input unit sequence of length unitIndex+1 */ 783 defaultValue=0; 784 m=mappings+map[subStart]; 785 if(m->uLen==unitIndex+1) { 786 /* do not include this in generateToUTable() */ 787 ++subStart; 788 789 if(subStart<subLimit && mappings[map[subStart]].uLen==unitIndex+1) { 790 /* print error for multiple same-input-sequence mappings */ 791 fprintf(stderr, "error: multiple mappings from same Unicode code points\n"); 792 ucm_printMapping(table, m, stderr); 793 ucm_printMapping(table, mappings+map[subStart], stderr); 794 return FALSE; 795 } 796 797 defaultValue=getFromUBytesValue(extData, table, m); 798 } 799 800 if(subStart==subLimit) { 801 /* write the result for the input sequence ending here */ 802 sectionValues[j]=defaultValue; 803 } else { 804 /* write the index to the subsection table */ 805 sectionValues[j]=(uint32_t)utm_countItems(extData->fromUTableValues); 806 807 /* recurse */ 808 if(!generateFromUTable(extData, table, subStart, subLimit, unitIndex+1, defaultValue)) { 809 return FALSE; 810 } 811 } 812 } 813 return TRUE; 814 } 815 816 /* 817 * add entries to the fromUnicode trie, 818 * assume to be called with code points in ascending order 819 * and use that to build the trie in precompacted form 820 */ 821 static void 822 addFromUTrieEntry(CnvExtData *extData, UChar32 c, uint32_t value) { 823 int32_t i1, i2, i3, i3b, nextOffset, min, newBlock; 824 825 if(value==0) { 826 return; 827 } 828 829 /* 830 * compute the index for each stage, 831 * allocate a stage block if necessary, 832 * and write the stage value 833 */ 834 i1=c>>10; 835 if(i1>=extData->stage1Top) { 836 extData->stage1Top=i1+1; 837 } 838 839 nextOffset=(c>>4)&0x3f; 840 841 if(extData->stage1[i1]==0) { 842 /* allocate another block in stage 2; overlap with the previous block */ 843 newBlock=extData->stage2Top; 844 min=newBlock-nextOffset; /* minimum block start with overlap */ 845 while(min<newBlock && extData->stage2[newBlock-1]==0) { 846 --newBlock; 847 } 848 849 extData->stage1[i1]=(uint16_t)newBlock; 850 extData->stage2Top=newBlock+MBCS_STAGE_2_BLOCK_SIZE; 851 if(extData->stage2Top>UPRV_LENGTHOF(extData->stage2)) { 852 fprintf(stderr, "error: too many stage 2 entries at U+%04x\n", (int)c); 853 exit(U_MEMORY_ALLOCATION_ERROR); 854 } 855 } 856 857 i2=extData->stage1[i1]+nextOffset; 858 nextOffset=c&0xf; 859 860 if(extData->stage2[i2]==0) { 861 /* allocate another block in stage 3; overlap with the previous block */ 862 newBlock=extData->stage3Top; 863 min=newBlock-nextOffset; /* minimum block start with overlap */ 864 while(min<newBlock && extData->stage3[newBlock-1]==0) { 865 --newBlock; 866 } 867 868 /* round up to a multiple of stage 3 granularity >1 (similar to utrie.c) */ 869 newBlock=(newBlock+(UCNV_EXT_STAGE_3_GRANULARITY-1))&~(UCNV_EXT_STAGE_3_GRANULARITY-1); 870 extData->stage2[i2]=(uint16_t)(newBlock>>UCNV_EXT_STAGE_2_LEFT_SHIFT); 871 872 extData->stage3Top=newBlock+MBCS_STAGE_3_BLOCK_SIZE; 873 if(extData->stage3Top>UPRV_LENGTHOF(extData->stage3)) { 874 fprintf(stderr, "error: too many stage 3 entries at U+%04x\n", (int)c); 875 exit(U_MEMORY_ALLOCATION_ERROR); 876 } 877 } 878 879 i3=((int32_t)extData->stage2[i2]<<UCNV_EXT_STAGE_2_LEFT_SHIFT)+nextOffset; 880 /* 881 * assume extData->stage3[i3]==0 because we get 882 * code points in strictly ascending order 883 */ 884 885 if(value==UCNV_EXT_FROM_U_SUBCHAR1) { 886 /* <subchar1> SUB mapping, see getFromUBytesValue() and prepareFromUMappings() */ 887 extData->stage3[i3]=1; 888 889 /* 890 * precompaction is not optimal for <subchar1> |2 mappings because 891 * stage3 values for them are all the same, unlike for other mappings 892 * which all have unique values; 893 * use a simple compaction of reusing a whole block filled with these 894 * mappings 895 */ 896 897 /* is the entire block filled with <subchar1> |2 mappings? */ 898 if(nextOffset==MBCS_STAGE_3_BLOCK_SIZE-1) { 899 for(min=i3-nextOffset; 900 min<i3 && extData->stage3[min]==1; 901 ++min) {} 902 903 if(min==i3) { 904 /* the entire block is filled with these mappings */ 905 if(extData->stage3Sub1Block!=0) { 906 /* point to the previous such block and remove this block from stage3 */ 907 extData->stage2[i2]=extData->stage3Sub1Block; 908 extData->stage3Top-=MBCS_STAGE_3_BLOCK_SIZE; 909 uprv_memset(extData->stage3+extData->stage3Top, 0, MBCS_STAGE_3_BLOCK_SIZE*2); 910 } else { 911 /* remember this block's stage2 entry */ 912 extData->stage3Sub1Block=extData->stage2[i2]; 913 } 914 } 915 } 916 } else { 917 if((i3b=extData->stage3bTop++)>=UPRV_LENGTHOF(extData->stage3b)) { 918 fprintf(stderr, "error: too many stage 3b entries at U+%04x\n", (int)c); 919 exit(U_MEMORY_ALLOCATION_ERROR); 920 } 921 922 /* roundtrip or fallback mapping */ 923 extData->stage3[i3]=(uint16_t)i3b; 924 extData->stage3b[i3b]=value; 925 } 926 } 927 928 static UBool 929 generateFromUTrie(CnvExtData *extData, UCMTable *table, int32_t mapLength) { 930 UCMapping *mappings, *m; 931 int32_t *map; 932 uint32_t value; 933 int32_t subStart, subLimit; 934 935 UChar32 *codePoints; 936 UChar32 c, next; 937 938 if(mapLength==0) { 939 return TRUE; 940 } 941 942 mappings=table->mappings; 943 map=table->reverseMap; 944 945 /* 946 * iterate over same-initial-code point mappings, 947 * enter the initial code point into the trie, 948 * and start a recursion on the corresponding mappings section 949 * with generateFromUTable() 950 */ 951 m=mappings+map[0]; 952 codePoints=UCM_GET_CODE_POINTS(table, m); 953 next=codePoints[0]; 954 subLimit=0; 955 while(subLimit<mapLength) { 956 /* get a new subsection of mappings starting with the same code point */ 957 subStart=subLimit; 958 c=next; 959 while(next==c && ++subLimit<mapLength) { 960 m=mappings+map[subLimit]; 961 codePoints=UCM_GET_CODE_POINTS(table, m); 962 next=codePoints[0]; 963 } 964 965 /* 966 * compute the value for this code point; 967 * if there is a mapping for this code point alone, it is at subStart 968 * because the table is sorted lexically 969 */ 970 value=0; 971 m=mappings+map[subStart]; 972 codePoints=UCM_GET_CODE_POINTS(table, m); 973 if(m->uLen==1) { 974 /* do not include this in generateFromUTable() */ 975 ++subStart; 976 977 if(subStart<subLimit && mappings[map[subStart]].uLen==1) { 978 /* print error for multiple same-input-sequence mappings */ 979 fprintf(stderr, "error: multiple mappings from same Unicode code points\n"); 980 ucm_printMapping(table, m, stderr); 981 ucm_printMapping(table, mappings+map[subStart], stderr); 982 return FALSE; 983 } 984 985 value=getFromUBytesValue(extData, table, m); 986 } 987 988 if(subStart==subLimit) { 989 /* write the result for this one code point */ 990 addFromUTrieEntry(extData, c, value); 991 } else { 992 /* write the index to the subsection table */ 993 addFromUTrieEntry(extData, c, (uint32_t)utm_countItems(extData->fromUTableValues)); 994 995 /* recurse, starting from 16-bit-unit index 2, the first 16-bit unit after c */ 996 if(!generateFromUTable(extData, table, subStart, subLimit, 2, value)) { 997 return FALSE; 998 } 999 } 1000 } 1001 return TRUE; 1002 } 1003 1004 /* 1005 * Generate the fromU data structures from the input table. 1006 * The input table must be sorted, and all precision flags must be 0..3. 1007 * This function will modify the table's reverseMap. 1008 */ 1009 static UBool 1010 makeFromUTable(CnvExtData *extData, UCMTable *table) { 1011 uint16_t *stage1; 1012 int32_t i, stage1Top, fromUCount; 1013 1014 fromUCount=prepareFromUMappings(table); 1015 1016 extData->fromUTableUChars=utm_open("cnv extension fromUTableUChars", 0x10000, UCNV_EXT_FROM_U_DATA_MASK+1, 2); 1017 extData->fromUTableValues=utm_open("cnv extension fromUTableValues", 0x10000, UCNV_EXT_FROM_U_DATA_MASK+1, 4); 1018 extData->fromUBytes=utm_open("cnv extension fromUBytes", 0x10000, UCNV_EXT_FROM_U_DATA_MASK+1, 1); 1019 1020 /* allocate all-unassigned stage blocks */ 1021 extData->stage2Top=MBCS_STAGE_2_FIRST_ASSIGNED; 1022 extData->stage3Top=MBCS_STAGE_3_FIRST_ASSIGNED; 1023 1024 /* 1025 * stage 3b stores only unique values, and in 1026 * index 0: 0 for "no mapping" 1027 * index 1: "no mapping" with preference for <subchar1> rather than <subchar> 1028 */ 1029 extData->stage3b[1]=UCNV_EXT_FROM_U_SUBCHAR1; 1030 extData->stage3bTop=2; 1031 1032 /* allocate the first entry in the fromUTable because index 0 means "no result" */ 1033 utm_alloc(extData->fromUTableUChars); 1034 utm_alloc(extData->fromUTableValues); 1035 1036 if(!generateFromUTrie(extData, table, fromUCount)) { 1037 return FALSE; 1038 } 1039 1040 /* 1041 * offset the stage 1 trie entries by stage1Top because they will 1042 * be stored in a single array 1043 */ 1044 stage1=extData->stage1; 1045 stage1Top=extData->stage1Top; 1046 for(i=0; i<stage1Top; ++i) { 1047 stage1[i]=(uint16_t)(stage1[i]+stage1Top); 1048 } 1049 1050 return TRUE; 1051 } 1052 1053 /* -------------------------------------------------------------------------- */ 1054 1055 static UBool 1056 CnvExtAddTable(NewConverter *cnvData, UCMTable *table, UConverterStaticData *staticData) { 1057 CnvExtData *extData; 1058 1059 if(table->unicodeMask&UCNV_HAS_SURROGATES) { 1060 fprintf(stderr, "error: contains mappings for surrogate code points\n"); 1061 return FALSE; 1062 } 1063 1064 staticData->conversionType=UCNV_MBCS; 1065 1066 extData=(CnvExtData *)cnvData; 1067 1068 /* 1069 * assume that the table is sorted 1070 * 1071 * call the functions in this order because 1072 * makeToUTable() modifies the original reverseMap, 1073 * makeFromUTable() writes a whole new mapping into reverseMap 1074 */ 1075 return 1076 makeToUTable(extData, table) && 1077 makeFromUTable(extData, table); 1078 } 1079