icuSources/tools/makeconv/gencnvex.c

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