Home | History | Annotate | Download | only in makeconv
      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