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