source/tools/makeconv/gencnvex.c

   1 // Copyright (C) 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:   US-ASCII
  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 }