icuSources/tools/toolutil/ucmstate.c

   1 /*
   2 *******************************************************************************
   3 *
   4 *   Copyright (C) 2003-2005, International Business Machines
   5 *   Corporation and others.  All Rights Reserved.
   6 *
   7 *******************************************************************************
   8 *   file name:  ucmstate.c
   9 *   encoding:   US-ASCII
  10 *   tab size:   8 (not used)
  11 *   indentation:4
  12 *
  13 *   created on: 2003oct09
  14 *   created by: Markus W. Scherer
  15 *
  16 *   This file handles ICU .ucm file state information as part of the ucm module.
  17 *   Most of this code used to be in makeconv.c.
  18 */
  19
  20 #include "unicode/utypes.h"
  21 #include "cstring.h"
  22 #include "cmemory.h"
  23 #include "uarrsort.h"
  24 #include "ucnvmbcs.h"
  25 #include "ucnv_ext.h"
  26 #include "uparse.h"
  27 #include "ucm.h"
  28 #include <stdio.h>
  29
  30 #if !UCONFIG_NO_CONVERSION
  31
  32 /* MBCS state handling ------------------------------------------------------ */
  33
  34 /*
  35  * state table row grammar (ebnf-style):
  36  * (whitespace is allowed between all tokens)
  37  *
  38  * row=[[firstentry ','] entry (',' entry)*]
  39  * firstentry="initial" | "surrogates"
  40  *            (initial state (default for state 0), output is all surrogate pairs)
  41  * entry=range [':' nextstate] ['.' action]
  42  * range=number ['-' number]
  43  * nextstate=number
  44  *           (0..7f)
  45  * action='u' | 's' | 'p' | 'i'
  46  *        (unassigned, state change only, surrogate pair, illegal)
  47  * number=(1- or 2-digit hexadecimal number)
  48  */
  49 static const char *
  50 parseState(const char *s, int32_t state[256], uint32_t *pFlags) {
  51     const char *t;
  52     uint32_t start, end, i;
  53     int32_t entry;
  54
  55     /* initialize the state: all illegal with U+ffff */
  56     for(i=0; i<256; ++i) {
  57         state[i]=MBCS_ENTRY_FINAL(0, MBCS_STATE_ILLEGAL, 0xffff);
  58     }
  59
  60     /* skip leading white space */
  61     s=u_skipWhitespace(s);
  62
  63     /* is there an "initial" or "surrogates" directive? */
  64     if(uprv_strncmp("initial", s, 7)==0) {
  65         *pFlags=MBCS_STATE_FLAG_DIRECT;
  66         s=u_skipWhitespace(s+7);
  67         if(*s++!=',') {
  68             return s-1;
  69         }
  70     } else if(*pFlags==0 && uprv_strncmp("surrogates", s, 10)==0) {
  71         *pFlags=MBCS_STATE_FLAG_SURROGATES;
  72         s=u_skipWhitespace(s+10);
  73         if(*s++!=',') {
  74             return s-1;
  75         }
  76     } else if(*s==0) {
  77         /* empty state row: all-illegal */
  78         return NULL;
  79     }
  80
  81     for(;;) {
  82         /* read an entry, the start of the range first */
  83         s=u_skipWhitespace(s);
  84         start=uprv_strtoul(s, (char **)&t, 16);
  85         if(s==t || 0xff<start) {
  86             return s;
  87         }
  88         s=u_skipWhitespace(t);
  89
  90         /* read the end of the range if there is one */
  91         if(*s=='-') {
  92             s=u_skipWhitespace(s+1);
  93             end=uprv_strtoul(s, (char **)&t, 16);
  94             if(s==t || end<start || 0xff<end) {
  95                 return s;
  96             }
  97             s=u_skipWhitespace(t);
  98         } else {
  99             end=start;
 100         }
 101
 102         /* determine the state entrys for this range */
 103         if(*s!=':' && *s!='.') {
 104             /* the default is: final state with valid entries */
 105             entry=MBCS_ENTRY_FINAL(0, MBCS_STATE_VALID_16, 0);
 106         } else {
 107             entry=MBCS_ENTRY_TRANSITION(0, 0);
 108             if(*s==':') {
 109                 /* get the next state, default to 0 */
 110                 s=u_skipWhitespace(s+1);
 111                 i=uprv_strtoul(s, (char **)&t, 16);
 112                 if(s!=t) {
 113                     if(0x7f<i) {
 114                         return s;
 115                     }
 116                     s=u_skipWhitespace(t);
 117                     entry=MBCS_ENTRY_SET_STATE(entry, i);
 118                 }
 119             }
 120
 121             /* get the state action, default to valid */
 122             if(*s=='.') {
 123                 /* this is a final state */
 124                 entry=MBCS_ENTRY_SET_FINAL(entry);
 125
 126                 s=u_skipWhitespace(s+1);
 127                 if(*s=='u') {
 128                     /* unassigned set U+fffe */
 129                     entry=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_UNASSIGNED, 0xfffe);
 130                     s=u_skipWhitespace(s+1);
 131                 } else if(*s=='p') {
 132                     if(*pFlags!=MBCS_STATE_FLAG_DIRECT) {
 133                         entry=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_VALID_16_PAIR);
 134                     } else {
 135                         entry=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_VALID_16);
 136                     }
 137                     s=u_skipWhitespace(s+1);
 138                 } else if(*s=='s') {
 139                     entry=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_CHANGE_ONLY);
 140                     s=u_skipWhitespace(s+1);
 141                 } else if(*s=='i') {
 142                     /* illegal set U+ffff */
 143                     entry=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_ILLEGAL, 0xffff);
 144                     s=u_skipWhitespace(s+1);
 145                 } else {
 146                     /* default to valid */
 147                     entry=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_VALID_16);
 148                 }
 149             } else {
 150                 /* this is an intermediate state, nothing to do */
 151             }
 152         }
 153
 154         /* adjust "final valid" states according to the state flags */
 155         if(MBCS_ENTRY_FINAL_ACTION(entry)==MBCS_STATE_VALID_16) {
 156             switch(*pFlags) {
 157             case 0:
 158                 /* no adjustment */
 159                 break;
 160             case MBCS_STATE_FLAG_DIRECT:
 161                 /* set the valid-direct code point to "unassigned"==0xfffe */
 162                 entry=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_VALID_DIRECT_16, 0xfffe);
 163                 break;
 164             case MBCS_STATE_FLAG_SURROGATES:
 165                 entry=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_VALID_16_PAIR, 0);
 166                 break;
 167             default:
 168                 break;
 169             }
 170         }
 171
 172         /* set this entry for the range */
 173         for(i=start; i<=end; ++i) {
 174             state[i]=entry;
 175         }
 176
 177         if(*s==',') {
 178             ++s;
 179         } else {
 180             return *s==0 ? NULL : s;
 181         }
 182     }
 183 }
 184
 185 U_CAPI void U_EXPORT2
 186 ucm_addState(UCMStates *states, const char *s) {
 187     const char *error;
 188
 189     if(states->countStates==MBCS_MAX_STATE_COUNT) {
 190         fprintf(stderr, "ucm error: too many states (maximum %u)\n", MBCS_MAX_STATE_COUNT);
 191         exit(U_INVALID_TABLE_FORMAT);
 192     }
 193
 194     error=parseState(s, states->stateTable[states->countStates],
 195                        &states->stateFlags[states->countStates]);
 196     if(error!=NULL) {
 197         fprintf(stderr, "ucm error: parse error in state definition at '%s'\n", error);
 198         exit(U_INVALID_TABLE_FORMAT);
 199     }
 200
 201     ++states->countStates;
 202 }
 203
 204 U_CAPI UBool U_EXPORT2
 205 ucm_parseHeaderLine(UCMFile *ucm,
 206                     char *line, char **pKey, char **pValue) {
 207     UCMStates *states;
 208     char *s, *end;
 209     char c;
 210
 211     states=&ucm->states;
 212
 213     /* remove comments and trailing CR and LF and remove whitespace from the end */
 214     for(end=line; (c=*end)!=0; ++end) {
 215         if(c=='#' || c=='\r' || c=='\n') {
 216             break;
 217         }
 218     }
 219     while(end>line && (*(end-1)==' ' || *(end-1)=='\t')) {
 220         --end;
 221     }
 222     *end=0;
 223
 224     /* skip leading white space and ignore empty lines */
 225     s=(char *)u_skipWhitespace(line);
 226     if(*s==0) {
 227         return TRUE;
 228     }
 229
 230     /* stop at the beginning of the mapping section */
 231     if(uprv_memcmp(s, "CHARMAP", 7)==0) {
 232         return FALSE;
 233     }
 234
 235     /* get the key name, bracketed in <> */
 236     if(*s!='<') {
 237         fprintf(stderr, "ucm error: no header field <key> in line \"%s\"\n", line);
 238         exit(U_INVALID_TABLE_FORMAT);
 239     }
 240     *pKey=++s;
 241     while(*s!='>') {
 242         if(*s==0) {
 243             fprintf(stderr, "ucm error: incomplete header field <key> in line \"%s\"\n", line);
 244             exit(U_INVALID_TABLE_FORMAT);
 245         }
 246         ++s;
 247     }
 248     *s=0;
 249
 250     /* get the value string, possibly quoted */
 251     s=(char *)u_skipWhitespace(s+1);
 252     if(*s!='"') {
 253         *pValue=s;
 254     } else {
 255         /* remove the quotes */
 256         *pValue=s+1;
 257         if(end>*pValue && *(end-1)=='"') {
 258             *--end=0;
 259         }
 260     }
 261
 262     /* collect the information from the header field, ignore unknown keys */
 263     if(uprv_strcmp(*pKey, "uconv_class")==0) {
 264         if(uprv_strcmp(*pValue, "DBCS")==0) {
 265             states->conversionType=UCNV_DBCS;
 266         } else if(uprv_strcmp(*pValue, "SBCS")==0) {
 267             states->conversionType = UCNV_SBCS;
 268         } else if(uprv_strcmp(*pValue, "MBCS")==0) {
 269             states->conversionType = UCNV_MBCS;
 270         } else if(uprv_strcmp(*pValue, "EBCDIC_STATEFUL")==0) {
 271             states->conversionType = UCNV_EBCDIC_STATEFUL;
 272         } else {
 273             fprintf(stderr, "ucm error: unknown <uconv_class> %s\n", *pValue);
 274             exit(U_INVALID_TABLE_FORMAT);
 275         }
 276         return TRUE;
 277     } else if(uprv_strcmp(*pKey, "mb_cur_max")==0) {
 278         c=**pValue;
 279         if('1'<=c && c<='4' && (*pValue)[1]==0) {
 280             states->maxCharLength=(int8_t)(c-'0');
 281             states->outputType=(int8_t)(states->maxCharLength-1);
 282         } else {
 283             fprintf(stderr, "ucm error: illegal <mb_cur_max> %s\n", *pValue);
 284             exit(U_INVALID_TABLE_FORMAT);
 285         }
 286         return TRUE;
 287     } else if(uprv_strcmp(*pKey, "mb_cur_min")==0) {
 288         c=**pValue;
 289         if('1'<=c && c<='4' && (*pValue)[1]==0) {
 290             states->minCharLength=(int8_t)(c-'0');
 291         } else {
 292             fprintf(stderr, "ucm error: illegal <mb_cur_min> %s\n", *pValue);
 293             exit(U_INVALID_TABLE_FORMAT);
 294         }
 295         return TRUE;
 296     } else if(uprv_strcmp(*pKey, "icu:state")==0) {
 297         /* if an SBCS/DBCS/EBCDIC_STATEFUL converter has icu:state, then turn it into MBCS */
 298         switch(states->conversionType) {
 299         case UCNV_SBCS:
 300         case UCNV_DBCS:
 301         case UCNV_EBCDIC_STATEFUL:
 302             states->conversionType=UCNV_MBCS;
 303             break;
 304         case UCNV_MBCS:
 305             break;
 306         default:
 307             fprintf(stderr, "ucm error: <icu:state> entry for non-MBCS table or before the <uconv_class> line\n");
 308             exit(U_INVALID_TABLE_FORMAT);
 309         }
 310
 311         if(states->maxCharLength==0) {
 312             fprintf(stderr, "ucm error: <icu:state> before the <mb_cur_max> line\n");
 313             exit(U_INVALID_TABLE_FORMAT);
 314         }
 315         ucm_addState(states, *pValue);
 316         return TRUE;
 317     } else if(uprv_strcmp(*pKey, "icu:base")==0) {
 318         if(**pValue==0) {
 319             fprintf(stderr, "ucm error: <icu:base> without a base table name\n");
 320             exit(U_INVALID_TABLE_FORMAT);
 321         }
 322         uprv_strcpy(ucm->baseName, *pValue);
 323         return TRUE;
 324     }
 325
 326     return FALSE;
 327 }
 328
 329 /* post-processing ---------------------------------------------------------- */
 330
 331 static int32_t
 332 sumUpStates(UCMStates *states) {
 333     int32_t entry, sum, state, cell, count;
 334     UBool allStatesReady;
 335
 336     /*
 337      * Sum up the offsets for all states.
 338      * In each final state (where there are only final entries),
 339      * the offsets add up directly.
 340      * In all other state table rows, for each transition entry to another state,
 341      * the offsets sum of that state needs to be added.
 342      * This is achieved in at most countStates iterations.
 343      */
 344     allStatesReady=FALSE;
 345     for(count=states->countStates; !allStatesReady && count>=0; --count) {
 346         allStatesReady=TRUE;
 347         for(state=states->countStates-1; state>=0; --state) {
 348             if(!(states->stateFlags[state]&MBCS_STATE_FLAG_READY)) {
 349                 allStatesReady=FALSE;
 350                 sum=0;
 351
 352                 /* at first, add up only the final delta offsets to keep them <512 */
 353                 for(cell=0; cell<256; ++cell) {
 354                     entry=states->stateTable[state][cell];
 355                     if(MBCS_ENTRY_IS_FINAL(entry)) {
 356                         switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
 357                         case MBCS_STATE_VALID_16:
 358                             states->stateTable[state][cell]=MBCS_ENTRY_FINAL_SET_VALUE(entry, sum);
 359                             sum+=1;
 360                             break;
 361                         case MBCS_STATE_VALID_16_PAIR:
 362                             states->stateTable[state][cell]=MBCS_ENTRY_FINAL_SET_VALUE(entry, sum);
 363                             sum+=2;
 364                             break;
 365                         default:
 366                             /* no addition */
 367                             break;
 368                         }
 369                     }
 370                 }
 371
 372                 /* now, add up the delta offsets for the transitional entries */
 373                 for(cell=0; cell<256; ++cell) {
 374                     entry=states->stateTable[state][cell];
 375                     if(MBCS_ENTRY_IS_TRANSITION(entry)) {
 376                         if(states->stateFlags[MBCS_ENTRY_TRANSITION_STATE(entry)]&MBCS_STATE_FLAG_READY) {
 377                             states->stateTable[state][cell]=MBCS_ENTRY_TRANSITION_SET_OFFSET(entry, sum);
 378                             sum+=states->stateOffsetSum[MBCS_ENTRY_TRANSITION_STATE(entry)];
 379                         } else {
 380                             /* that next state does not have a sum yet, we cannot finish the one for this state */
 381                             sum=-1;
 382                             break;
 383                         }
 384                     }
 385                 }
 386
 387                 if(sum!=-1) {
 388                     states->stateOffsetSum[state]=sum;
 389                     states->stateFlags[state]|=MBCS_STATE_FLAG_READY;
 390                 }
 391             }
 392         }
 393     }
 394
 395     if(!allStatesReady) {
 396         fprintf(stderr, "ucm error: the state table contains loops\n");
 397         exit(U_INVALID_TABLE_FORMAT);
 398     }
 399
 400     /*
 401      * For all "direct" (i.e., initial) states>0,
 402      * the offsets need to be increased by the sum of
 403      * the previous initial states.
 404      */
 405     sum=states->stateOffsetSum[0];
 406     for(state=1; state<states->countStates; ++state) {
 407         if((states->stateFlags[state]&0xf)==MBCS_STATE_FLAG_DIRECT) {
 408             int32_t sum2=sum;
 409             sum+=states->stateOffsetSum[state];
 410             for(cell=0; cell<256; ++cell) {
 411                 entry=states->stateTable[state][cell];
 412                 if(MBCS_ENTRY_IS_TRANSITION(entry)) {
 413                     states->stateTable[state][cell]=MBCS_ENTRY_TRANSITION_ADD_OFFSET(entry, sum2);
 414                 }
 415             }
 416         }
 417     }
 418
 419     /* round up to the next even number to have the following data 32-bit-aligned */
 420     return states->countToUCodeUnits=(sum+1)&~1;
 421 }
 422
 423 U_CAPI void U_EXPORT2
 424 ucm_processStates(UCMStates *states) {
 425     int32_t entry, state, cell, count;
 426
 427     if(states->conversionType==UCNV_UNSUPPORTED_CONVERTER) {
 428         fprintf(stderr, "ucm error: missing conversion type (<uconv_class>)\n");
 429         exit(U_INVALID_TABLE_FORMAT);
 430     }
 431
 432     if(states->countStates==0) {
 433         switch(states->conversionType) {
 434         case UCNV_SBCS:
 435             /* SBCS: use MBCS data structure with a default state table */
 436             if(states->maxCharLength!=1) {
 437                 fprintf(stderr, "error: SBCS codepage with max B/char!=1\n");
 438                 exit(U_INVALID_TABLE_FORMAT);
 439             }
 440             states->conversionType=UCNV_MBCS;
 441             ucm_addState(states, "0-ff");
 442             break;
 443         case UCNV_MBCS:
 444             fprintf(stderr, "ucm error: missing state table information (<icu:state>) for MBCS\n");
 445             exit(U_INVALID_TABLE_FORMAT);
 446             break;
 447         case UCNV_EBCDIC_STATEFUL:
 448             /* EBCDIC_STATEFUL: use MBCS data structure with a default state table */
 449             if(states->minCharLength!=1 || states->maxCharLength!=2) {
 450                 fprintf(stderr, "error: DBCS codepage with min B/char!=1 or max B/char!=2\n");
 451                 exit(U_INVALID_TABLE_FORMAT);
 452             }
 453             states->conversionType=UCNV_MBCS;
 454             ucm_addState(states, "0-ff, e:1.s, f:0.s");
 455             ucm_addState(states, "initial, 0-3f:4, e:1.s, f:0.s, 40:3, 41-fe:2, ff:4");
 456             ucm_addState(states, "0-40:1.i, 41-fe:1., ff:1.i");
 457             ucm_addState(states, "0-ff:1.i, 40:1.");
 458             ucm_addState(states, "0-ff:1.i");
 459             break;
 460         case UCNV_DBCS:
 461             /* DBCS: use MBCS data structure with a default state table */
 462             if(states->minCharLength!=2 || states->maxCharLength!=2) {
 463                 fprintf(stderr, "error: DBCS codepage with min or max B/char!=2\n");
 464                 exit(U_INVALID_TABLE_FORMAT);
 465             }
 466             states->conversionType = UCNV_MBCS;
 467             ucm_addState(states, "0-3f:3, 40:2, 41-fe:1, ff:3");
 468             ucm_addState(states, "41-fe");
 469             ucm_addState(states, "40");
 470             ucm_addState(states, "");
 471             break;
 472         default:
 473             fprintf(stderr, "ucm error: unknown charset structure\n");
 474             exit(U_INVALID_TABLE_FORMAT);
 475             break;
 476         }
 477     }
 478
 479     /*
 480      * check that the min/max character lengths are reasonable;
 481      * to do this right, all paths through the state table would have to be
 482      * recursively walked while keeping track of the sequence lengths,
 483      * but these simple checks cover most state tables in practice
 484      */
 485     if(states->maxCharLength<states->minCharLength) {
 486         fprintf(stderr, "ucm error: max B/char < min B/char\n");
 487         exit(U_INVALID_TABLE_FORMAT);
 488     }
 489
 490     /* count non-direct states and compare with max B/char */
 491     count=0;
 492     for(state=0; state<states->countStates; ++state) {
 493         if((states->stateFlags[state]&0xf)!=MBCS_STATE_FLAG_DIRECT) {
 494             ++count;
 495         }
 496     }
 497     if(states->maxCharLength>count+1) {
 498         fprintf(stderr, "ucm error: max B/char too large\n");
 499         exit(U_INVALID_TABLE_FORMAT);
 500     }
 501
 502     if(states->minCharLength==1) {
 503         int32_t action;
 504
 505         /*
 506          * if there are single-byte characters,
 507          * then the initial state must have direct result states
 508          */
 509         for(cell=0; cell<256; ++cell) {
 510             entry=states->stateTable[0][cell];
 511             if( MBCS_ENTRY_IS_FINAL(entry) &&
 512                 ((action=MBCS_ENTRY_FINAL_ACTION(entry))==MBCS_STATE_VALID_DIRECT_16 ||
 513                  action==MBCS_STATE_UNASSIGNED)
 514             ) {
 515                 break;
 516             }
 517         }
 518
 519         if(cell==256) {
 520             fprintf(stderr, "ucm warning: min B/char too small\n");
 521         }
 522     }
 523
 524     /*
 525      * make sure that all "next state" values are within limits
 526      * and that all next states after final ones have the "direct"
 527      * flag of initial states
 528      */
 529     for(state=states->countStates-1; state>=0; --state) {
 530         for(cell=0; cell<256; ++cell) {
 531             entry=states->stateTable[state][cell];
 532             if((uint8_t)MBCS_ENTRY_STATE(entry)>=states->countStates) {
 533                 fprintf(stderr, "ucm error: state table entry [%x][%x] has a next state of %x that is too high\n",
 534                     (int)state, (int)cell, (int)MBCS_ENTRY_STATE(entry));
 535                 exit(U_INVALID_TABLE_FORMAT);
 536             }
 537             if(MBCS_ENTRY_IS_FINAL(entry) && (states->stateFlags[MBCS_ENTRY_STATE(entry)]&0xf)!=MBCS_STATE_FLAG_DIRECT) {
 538                 fprintf(stderr, "ucm error: state table entry [%x][%x] is final but has a non-initial next state of %x\n",
 539                     (int)state, (int)cell, (int)MBCS_ENTRY_STATE(entry));
 540                 exit(U_INVALID_TABLE_FORMAT);
 541             } else if(MBCS_ENTRY_IS_TRANSITION(entry) && (states->stateFlags[MBCS_ENTRY_STATE(entry)]&0xf)==MBCS_STATE_FLAG_DIRECT) {
 542                 fprintf(stderr, "ucm error: state table entry [%x][%x] is not final but has an initial next state of %x\n",
 543                     (int)state, (int)cell, (int)MBCS_ENTRY_STATE(entry));
 544                 exit(U_INVALID_TABLE_FORMAT);
 545             }
 546         }
 547     }
 548
 549     /* is this an SI/SO (like EBCDIC-stateful) state table? */
 550     if(states->countStates>=2 && (states->stateFlags[1]&0xf)==MBCS_STATE_FLAG_DIRECT) {
 551         if(states->maxCharLength!=2) {
 552             fprintf(stderr, "ucm error: SI/SO codepages must have max 2 bytes/char (not %x)\n", (int)states->maxCharLength);
 553             exit(U_INVALID_TABLE_FORMAT);
 554         }
 555         if(states->countStates<3) {
 556             fprintf(stderr, "ucm error: SI/SO codepages must have at least 3 states (not %x)\n", (int)states->countStates);
 557             exit(U_INVALID_TABLE_FORMAT);
 558         }
 559         /* are the SI/SO all in the right places? */
 560         if( states->stateTable[0][0xe]==MBCS_ENTRY_FINAL(1, MBCS_STATE_CHANGE_ONLY, 0) &&
 561             states->stateTable[0][0xf]==MBCS_ENTRY_FINAL(0, MBCS_STATE_CHANGE_ONLY, 0) &&
 562             states->stateTable[1][0xe]==MBCS_ENTRY_FINAL(1, MBCS_STATE_CHANGE_ONLY, 0) &&
 563             states->stateTable[1][0xf]==MBCS_ENTRY_FINAL(0, MBCS_STATE_CHANGE_ONLY, 0)
 564         ) {
 565             states->outputType=MBCS_OUTPUT_2_SISO;
 566         } else {
 567             fprintf(stderr, "ucm error: SI/SO codepages must have in states 0 and 1 transitions e:1.s, f:0.s\n");
 568             exit(U_INVALID_TABLE_FORMAT);
 569         }
 570         state=2;
 571     } else {
 572         state=1;
 573     }
 574
 575     /* check that no unexpected state is a "direct" one */
 576     while(state<states->countStates) {
 577         if((states->stateFlags[state]&0xf)==MBCS_STATE_FLAG_DIRECT) {
 578             fprintf(stderr, "ucm error: state %d is 'initial' - not supported except for SI/SO codepages\n", (int)state);
 579             exit(U_INVALID_TABLE_FORMAT);
 580         }
 581         ++state;
 582     }
 583
 584     sumUpStates(states);
 585 }
 586
 587 /* find a fallback for this offset; return the index or -1 if not found */
 588 U_CAPI int32_t U_EXPORT2
 589 ucm_findFallback(_MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
 590                  uint32_t offset) {
 591     int32_t i;
 592
 593     if(countToUFallbacks==0) {
 594         /* shortcut: most codepages do not have fallbacks from codepage to Unicode */
 595         return -1;
 596     }
 597
 598     /* do a linear search for the fallback mapping (the table is not yet sorted) */
 599     for(i=0; i<countToUFallbacks; ++i) {
 600         if(offset==toUFallbacks[i].offset) {
 601             return i;
 602         }
 603     }
 604     return -1;
 605 }
 606
 607 /*
 608  * This function tries to compact toUnicode tables for 2-byte codepages
 609  * by finding lead bytes with all-unassigned trail bytes and adding another state
 610  * for them.
 611  */
 612 static void
 613 compactToUnicode2(UCMStates *states,
 614                   uint16_t **pUnicodeCodeUnits,
 615                   _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
 616                   UBool verbose) {
 617     int32_t (*oldStateTable)[256];
 618     uint16_t count[256];
 619     uint16_t *oldUnicodeCodeUnits;
 620     int32_t entry, offset, oldOffset, trailOffset, oldTrailOffset, savings, sum;
 621     int32_t i, j, leadState, trailState, newState, fallback;
 622     uint16_t unit;
 623
 624     /* find the lead state */
 625     if(states->outputType==MBCS_OUTPUT_2_SISO) {
 626         /* use the DBCS lead state for SI/SO codepages */
 627         leadState=1;
 628     } else {
 629         leadState=0;
 630     }
 631
 632     /* find the main trail state: the most used target state */
 633     uprv_memset(count, 0, sizeof(count));
 634     for(i=0; i<256; ++i) {
 635         entry=states->stateTable[leadState][i];
 636         if(MBCS_ENTRY_IS_TRANSITION(entry)) {
 637             ++count[MBCS_ENTRY_TRANSITION_STATE(entry)];
 638         }
 639     }
 640     trailState=0;
 641     for(i=1; i<states->countStates; ++i) {
 642         if(count[i]>count[trailState]) {
 643             trailState=i;
 644         }
 645     }
 646
 647     /* count possible savings from lead bytes with all-unassigned results in all trail bytes */
 648     uprv_memset(count, 0, sizeof(count));
 649     savings=0;
 650     /* for each lead byte */
 651     for(i=0; i<256; ++i) {
 652         entry=states->stateTable[leadState][i];
 653         if(MBCS_ENTRY_IS_TRANSITION(entry) && (MBCS_ENTRY_TRANSITION_STATE(entry))==trailState) {
 654             /* the offset is different for each lead byte */
 655             offset=MBCS_ENTRY_TRANSITION_OFFSET(entry);
 656             /* for each trail byte for this lead byte */
 657             for(j=0; j<256; ++j) {
 658                 entry=states->stateTable[trailState][j];
 659                 switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
 660                 case MBCS_STATE_VALID_16:
 661                     entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
 662                     if((*pUnicodeCodeUnits)[entry]==0xfffe && ucm_findFallback(toUFallbacks, countToUFallbacks, entry)<0) {
 663                         ++count[i];
 664                     } else {
 665                         j=999; /* do not count for this lead byte because there are assignments */
 666                     }
 667                     break;
 668                 case MBCS_STATE_VALID_16_PAIR:
 669                     entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
 670                     if((*pUnicodeCodeUnits)[entry]==0xfffe) {
 671                         count[i]+=2;
 672                     } else {
 673                         j=999; /* do not count for this lead byte because there are assignments */
 674                     }
 675                     break;
 676                 default:
 677                     break;
 678                 }
 679             }
 680             if(j==256) {
 681                 /* all trail bytes for this lead byte are unassigned */
 682                 savings+=count[i];
 683             } else {
 684                 count[i]=0;
 685             }
 686         }
 687     }
 688     /* subtract from the possible savings the cost of an additional state */
 689     savings=savings*2-1024; /* count bytes, not 16-bit words */
 690     if(savings<=0) {
 691         return;
 692     }
 693     if(verbose) {
 694         printf("compacting toUnicode data saves %ld bytes\n", (long)savings);
 695     }
 696     if(states->countStates>=MBCS_MAX_STATE_COUNT) {
 697         fprintf(stderr, "cannot compact toUnicode because the maximum number of states is reached\n");
 698         return;
 699     }
 700
 701     /* make a copy of the state table */
 702     oldStateTable=(int32_t (*)[256])uprv_malloc(states->countStates*1024);
 703     if(oldStateTable==NULL) {
 704         fprintf(stderr, "cannot compact toUnicode: out of memory\n");
 705         return;
 706     }
 707     uprv_memcpy(oldStateTable, states->stateTable, states->countStates*1024);
 708
 709     /* add the new state */
 710     /*
 711      * this function does not catch the degenerate case where all lead bytes
 712      * have all-unassigned trail bytes and the lead state could be removed
 713      */
 714     newState=states->countStates++;
 715     states->stateFlags[newState]=0;
 716     /* copy the old trail state, turning all assigned states into unassigned ones */
 717     for(i=0; i<256; ++i) {
 718         entry=states->stateTable[trailState][i];
 719         switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
 720         case MBCS_STATE_VALID_16:
 721         case MBCS_STATE_VALID_16_PAIR:
 722             states->stateTable[newState][i]=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_UNASSIGNED, 0xfffe);
 723             break;
 724         default:
 725             states->stateTable[newState][i]=entry;
 726             break;
 727         }
 728     }
 729
 730     /* in the lead state, redirect all lead bytes with all-unassigned trail bytes to the new state */
 731     for(i=0; i<256; ++i) {
 732         if(count[i]>0) {
 733             states->stateTable[leadState][i]=MBCS_ENTRY_SET_STATE(states->stateTable[leadState][i], newState);
 734         }
 735     }
 736
 737     /* sum up the new state table */
 738     for(i=0; i<states->countStates; ++i) {
 739         states->stateFlags[i]&=~MBCS_STATE_FLAG_READY;
 740     }
 741     sum=sumUpStates(states);
 742
 743     /* allocate a new, smaller code units array */
 744     oldUnicodeCodeUnits=*pUnicodeCodeUnits;
 745     if(sum==0) {
 746         *pUnicodeCodeUnits=NULL;
 747         if(oldUnicodeCodeUnits!=NULL) {
 748             uprv_free(oldUnicodeCodeUnits);
 749         }
 750         uprv_free(oldStateTable);
 751         return;
 752     }
 753     *pUnicodeCodeUnits=(uint16_t *)uprv_malloc(sum*sizeof(uint16_t));
 754     if(*pUnicodeCodeUnits==NULL) {
 755         fprintf(stderr, "cannot compact toUnicode: out of memory allocating %ld 16-bit code units\n",
 756             (long)sum);
 757         /* revert to the old state table */
 758         *pUnicodeCodeUnits=oldUnicodeCodeUnits;
 759         --states->countStates;
 760         uprv_memcpy(states->stateTable, oldStateTable, states->countStates*1024);
 761         uprv_free(oldStateTable);
 762         return;
 763     }
 764     for(i=0; i<sum; ++i) {
 765         (*pUnicodeCodeUnits)[i]=0xfffe;
 766     }
 767
 768     /* copy the code units for all assigned characters */
 769     /*
 770      * The old state table has the same lead _and_ trail states for assigned characters!
 771      * The differences are in the offsets, and in the trail states for some unassigned characters.
 772      * For each character with an assigned state in the new table, it was assigned in the old one.
 773      * Only still-assigned characters are copied.
 774      * Note that fallback mappings need to get their offset values adjusted.
 775      */
 776
 777     /* for each initial state */
 778     for(leadState=0; leadState<states->countStates; ++leadState) {
 779         if((states->stateFlags[leadState]&0xf)==MBCS_STATE_FLAG_DIRECT) {
 780             /* for each lead byte from there */
 781             for(i=0; i<256; ++i) {
 782                 entry=states->stateTable[leadState][i];
 783                 if(MBCS_ENTRY_IS_TRANSITION(entry)) {
 784                     trailState=(uint8_t)MBCS_ENTRY_TRANSITION_STATE(entry);
 785                     /* the new state does not have assigned states */
 786                     if(trailState!=newState) {
 787                         trailOffset=MBCS_ENTRY_TRANSITION_OFFSET(entry);
 788                         oldTrailOffset=MBCS_ENTRY_TRANSITION_OFFSET(oldStateTable[leadState][i]);
 789                         /* for each trail byte */
 790                         for(j=0; j<256; ++j) {
 791                             entry=states->stateTable[trailState][j];
 792                             /* copy assigned-character code units and adjust fallback offsets */
 793                             switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
 794                             case MBCS_STATE_VALID_16:
 795                                 offset=trailOffset+MBCS_ENTRY_FINAL_VALUE_16(entry);
 796                                 /* find the old offset according to the old state table */
 797                                 oldOffset=oldTrailOffset+MBCS_ENTRY_FINAL_VALUE_16(oldStateTable[trailState][j]);
 798                                 unit=(*pUnicodeCodeUnits)[offset]=oldUnicodeCodeUnits[oldOffset];
 799                                 if(unit==0xfffe && (fallback=ucm_findFallback(toUFallbacks, countToUFallbacks, oldOffset))>=0) {
 800                                     toUFallbacks[fallback].offset=0x80000000|offset;
 801                                 }
 802                                 break;
 803                             case MBCS_STATE_VALID_16_PAIR:
 804                                 offset=trailOffset+MBCS_ENTRY_FINAL_VALUE_16(entry);
 805                                 /* find the old offset according to the old state table */
 806                                 oldOffset=oldTrailOffset+MBCS_ENTRY_FINAL_VALUE_16(oldStateTable[trailState][j]);
 807                                 (*pUnicodeCodeUnits)[offset++]=oldUnicodeCodeUnits[oldOffset++];
 808                                 (*pUnicodeCodeUnits)[offset]=oldUnicodeCodeUnits[oldOffset];
 809                                 break;
 810                             default:
 811                                 break;
 812                             }
 813                         }
 814                     }
 815                 }
 816             }
 817         }
 818     }
 819
 820     /* remove temporary flags from fallback offsets that protected them from being modified twice */
 821     for(i=0; i<countToUFallbacks; ++i) {
 822         toUFallbacks[i].offset&=0x7fffffff;
 823     }
 824
 825     /* free temporary memory */
 826     uprv_free(oldUnicodeCodeUnits);
 827     uprv_free(oldStateTable);
 828 }
 829
 830 /*
 831  * recursive sub-function of compactToUnicodeHelper()
 832  * returns:
 833  * >0 number of bytes that are used in unicodeCodeUnits[] that could be saved,
 834  *    if all sequences from this state are unassigned, returns the
 835  * <0 there are assignments in unicodeCodeUnits[]
 836  * 0  no use of unicodeCodeUnits[]
 837  */
 838 static int32_t
 839 findUnassigned(UCMStates *states,
 840                uint16_t *unicodeCodeUnits,
 841                _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
 842                int32_t state, int32_t offset, uint32_t b) {
 843     int32_t i, entry, savings, localSavings, belowSavings;
 844     UBool haveAssigned;
 845
 846     localSavings=belowSavings=0;
 847     haveAssigned=FALSE;
 848     for(i=0; i<256; ++i) {
 849         entry=states->stateTable[state][i];
 850         if(MBCS_ENTRY_IS_TRANSITION(entry)) {
 851             savings=findUnassigned(states,
 852                         unicodeCodeUnits,
 853                         toUFallbacks, countToUFallbacks,
 854                         MBCS_ENTRY_TRANSITION_STATE(entry),
 855                         offset+MBCS_ENTRY_TRANSITION_OFFSET(entry),
 856                         (b<<8)|(uint32_t)i);
 857             if(savings<0) {
 858                 haveAssigned=TRUE;
 859             } else if(savings>0) {
 860                 printf("    all-unassigned sequences from prefix 0x%02lx state %ld use %ld bytes\n",
 861                     (unsigned long)((b<<8)|i), (long)state, (long)savings);
 862                 belowSavings+=savings;
 863             }
 864         } else if(!haveAssigned) {
 865             switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
 866             case MBCS_STATE_VALID_16:
 867                 entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
 868                 if(unicodeCodeUnits[entry]==0xfffe && ucm_findFallback(toUFallbacks, countToUFallbacks, entry)<0) {
 869                     localSavings+=2;
 870                 } else {
 871                     haveAssigned=TRUE;
 872                 }
 873                 break;
 874             case MBCS_STATE_VALID_16_PAIR:
 875                 entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
 876                 if(unicodeCodeUnits[entry]==0xfffe) {
 877                     localSavings+=4;
 878                 } else {
 879                     haveAssigned=TRUE;
 880                 }
 881                 break;
 882             default:
 883                 break;
 884             }
 885         }
 886     }
 887     if(haveAssigned) {
 888         return -1;
 889     } else {
 890         return localSavings+belowSavings;
 891     }
 892 }
 893
 894 /* helper function for finding compaction opportunities */
 895 static void
 896 compactToUnicodeHelper(UCMStates *states,
 897                        uint16_t *unicodeCodeUnits,
 898                        _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks) {
 899     int32_t state, savings;
 900
 901     /* for each initial state */
 902     for(state=0; state<states->countStates; ++state) {
 903         if((states->stateFlags[state]&0xf)==MBCS_STATE_FLAG_DIRECT) {
 904             savings=findUnassigned(states,
 905                         unicodeCodeUnits,
 906                         toUFallbacks, countToUFallbacks,
 907                         state, 0, 0);
 908             if(savings>0) {
 909                 printf("    all-unassigned sequences from initial state %ld use %ld bytes\n",
 910                     (long)state, (long)savings);
 911             }
 912         }
 913     }
 914 }
 915
 916 static int32_t
 917 compareFallbacks(const void *context, const void *fb1, const void *fb2) {
 918     return ((const _MBCSToUFallback *)fb1)->offset-((const _MBCSToUFallback *)fb2)->offset;
 919 }
 920
 921 U_CAPI void U_EXPORT2
 922 ucm_optimizeStates(UCMStates *states,
 923                    uint16_t **pUnicodeCodeUnits,
 924                    _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
 925                    UBool verbose) {
 926     UErrorCode errorCode;
 927     int32_t state, cell, entry;
 928
 929     /* test each state table entry */
 930     for(state=0; state<states->countStates; ++state) {
 931         for(cell=0; cell<256; ++cell) {
 932             entry=states->stateTable[state][cell];
 933             /*
 934              * if the entry is a final one with an MBCS_STATE_VALID_DIRECT_16 action code
 935              * and the code point is "unassigned" (0xfffe), then change it to
 936              * the "unassigned" action code with bits 26..23 set to zero and U+fffe.
 937              */
 938             if(MBCS_ENTRY_SET_STATE(entry, 0)==MBCS_ENTRY_FINAL(0, MBCS_STATE_VALID_DIRECT_16, 0xfffe)) {
 939                 states->stateTable[state][cell]=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_UNASSIGNED);
 940             }
 941         }
 942     }
 943
 944     /* try to compact the toUnicode tables */
 945     if(states->maxCharLength==2) {
 946         compactToUnicode2(states, pUnicodeCodeUnits, toUFallbacks, countToUFallbacks, verbose);
 947     } else if(states->maxCharLength>2) {
 948         if(verbose) {
 949             compactToUnicodeHelper(states, *pUnicodeCodeUnits, toUFallbacks, countToUFallbacks);
 950         }
 951     }
 952
 953     /* sort toUFallbacks */
 954     /*
 955      * It should be safe to sort them before compactToUnicode2() is called,
 956      * because it should not change the relative order of the offset values
 957      * that it adjusts, but they need to be sorted at some point, and
 958      * it is safest here.
 959      */
 960     if(countToUFallbacks>0) {
 961         errorCode=U_ZERO_ERROR; /* nothing bad will happen... */
 962         uprv_sortArray(toUFallbacks, countToUFallbacks,
 963                        sizeof(_MBCSToUFallback),
 964                        compareFallbacks, NULL, FALSE, &errorCode);
 965     }
 966 }
 967
 968 /* use a complete state table ----------------------------------------------- */
 969
 970 U_CAPI int32_t U_EXPORT2
 971 ucm_countChars(UCMStates *states,
 972                const uint8_t *bytes, int32_t length) {
 973     uint32_t offset;
 974     int32_t i, entry, count;
 975     uint8_t state;
 976
 977     offset=0;
 978     i=count=0;
 979     state=0;
 980
 981     if(states->countStates==0) {
 982         fprintf(stderr, "ucm error: there is no state information!\n");
 983         return -1;
 984     }
 985
 986     /* for SI/SO (like EBCDIC-stateful), double-byte sequences start in state 1 */
 987     if(length==2 && states->outputType==MBCS_OUTPUT_2_SISO) {
 988         state=1;
 989     }
 990
 991     /*
 992      * Walk down the state table like in conversion,
 993      * much like getNextUChar().
 994      * We assume that c<=0x10ffff.
 995      */
 996     for(i=0; i<length; ++i) {
 997         entry=states->stateTable[state][bytes[i]];
 998         if(MBCS_ENTRY_IS_TRANSITION(entry)) {
 999             state=(uint8_t)MBCS_ENTRY_TRANSITION_STATE(entry);
1000             offset+=MBCS_ENTRY_TRANSITION_OFFSET(entry);
1001         } else {
1002             switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
1003             case MBCS_STATE_ILLEGAL:
1004                 fprintf(stderr, "ucm error: byte sequence ends in illegal state\n");
1005                 return -1;
1006             case MBCS_STATE_CHANGE_ONLY:
1007                 fprintf(stderr, "ucm error: byte sequence ends in state-change-only\n");
1008                 return -1;
1009             case MBCS_STATE_UNASSIGNED:
1010             case MBCS_STATE_FALLBACK_DIRECT_16:
1011             case MBCS_STATE_VALID_DIRECT_16:
1012             case MBCS_STATE_FALLBACK_DIRECT_20:
1013             case MBCS_STATE_VALID_DIRECT_20:
1014             case MBCS_STATE_VALID_16:
1015             case MBCS_STATE_VALID_16_PAIR:
1016                 /* count a complete character and prepare for a new one */
1017                 ++count;
1018                 state=(uint8_t)MBCS_ENTRY_FINAL_STATE(entry);
1019                 offset=0;
1020                 break;
1021             default:
1022                 /* reserved, must never occur */
1023                 fprintf(stderr, "ucm error: byte sequence reached reserved action code, entry: 0x%02lx\n", (unsigned long)entry);
1024                 return -1;
1025             }
1026         }
1027     }
1028
1029     if(offset!=0) {
1030         fprintf(stderr, "ucm error: byte sequence too short, ends in non-final state %hu\n", state);
1031         return -1;
1032     }
1033
1034     /*
1035      * for SI/SO (like EBCDIC-stateful), multiple-character results
1036      * must consist of only double-byte sequences
1037      */
1038     if(count>1 && states->outputType==MBCS_OUTPUT_2_SISO && length!=2*count) {
1039         fprintf(stderr, "ucm error: SI/SO (like EBCDIC-stateful) result with %d characters does not contain all DBCS\n", (int)count);
1040         return -1;
1041     }
1042
1043     return count;
1044 }
1045 #endif
1046