icuSources/tools/makeconv/gencnvex.c

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