Home | History | Annotate | Download | only in toolutil
      1 /*
      2 *******************************************************************************
      3 *
      4 *   Copyright (C) 2003-2010, 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, UBool ignoreSISOCheck) {
    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( ignoreSISOCheck ||
    561            (states->stateTable[0][0xe]==MBCS_ENTRY_FINAL(1, MBCS_STATE_CHANGE_ONLY, 0) &&
    562             states->stateTable[0][0xf]==MBCS_ENTRY_FINAL(0, MBCS_STATE_CHANGE_ONLY, 0) &&
    563             states->stateTable[1][0xe]==MBCS_ENTRY_FINAL(1, MBCS_STATE_CHANGE_ONLY, 0) &&
    564             states->stateTable[1][0xf]==MBCS_ENTRY_FINAL(0, MBCS_STATE_CHANGE_ONLY, 0))
    565         ) {
    566             states->outputType=MBCS_OUTPUT_2_SISO;
    567         } else {
    568             fprintf(stderr, "ucm error: SI/SO codepages must have in states 0 and 1 transitions e:1.s, f:0.s\n");
    569             exit(U_INVALID_TABLE_FORMAT);
    570         }
    571         state=2;
    572     } else {
    573         state=1;
    574     }
    575 
    576     /* check that no unexpected state is a "direct" one */
    577     while(state<states->countStates) {
    578         if((states->stateFlags[state]&0xf)==MBCS_STATE_FLAG_DIRECT) {
    579             fprintf(stderr, "ucm error: state %d is 'initial' - not supported except for SI/SO codepages\n", (int)state);
    580             exit(U_INVALID_TABLE_FORMAT);
    581         }
    582         ++state;
    583     }
    584 
    585     sumUpStates(states);
    586 }
    587 
    588 /* find a fallback for this offset; return the index or -1 if not found */
    589 U_CAPI int32_t U_EXPORT2
    590 ucm_findFallback(_MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
    591                  uint32_t offset) {
    592     int32_t i;
    593 
    594     if(countToUFallbacks==0) {
    595         /* shortcut: most codepages do not have fallbacks from codepage to Unicode */
    596         return -1;
    597     }
    598 
    599     /* do a linear search for the fallback mapping (the table is not yet sorted) */
    600     for(i=0; i<countToUFallbacks; ++i) {
    601         if(offset==toUFallbacks[i].offset) {
    602             return i;
    603         }
    604     }
    605     return -1;
    606 }
    607 
    608 /*
    609  * This function tries to compact toUnicode tables for 2-byte codepages
    610  * by finding lead bytes with all-unassigned trail bytes and adding another state
    611  * for them.
    612  */
    613 static void
    614 compactToUnicode2(UCMStates *states,
    615                   uint16_t **pUnicodeCodeUnits,
    616                   _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
    617                   UBool verbose) {
    618     int32_t (*oldStateTable)[256];
    619     uint16_t count[256];
    620     uint16_t *oldUnicodeCodeUnits;
    621     int32_t entry, offset, oldOffset, trailOffset, oldTrailOffset, savings, sum;
    622     int32_t i, j, leadState, trailState, newState, fallback;
    623     uint16_t unit;
    624 
    625     /* find the lead state */
    626     if(states->outputType==MBCS_OUTPUT_2_SISO) {
    627         /* use the DBCS lead state for SI/SO codepages */
    628         leadState=1;
    629     } else {
    630         leadState=0;
    631     }
    632 
    633     /* find the main trail state: the most used target state */
    634     uprv_memset(count, 0, sizeof(count));
    635     for(i=0; i<256; ++i) {
    636         entry=states->stateTable[leadState][i];
    637         if(MBCS_ENTRY_IS_TRANSITION(entry)) {
    638             ++count[MBCS_ENTRY_TRANSITION_STATE(entry)];
    639         }
    640     }
    641     trailState=0;
    642     for(i=1; i<states->countStates; ++i) {
    643         if(count[i]>count[trailState]) {
    644             trailState=i;
    645         }
    646     }
    647 
    648     /* count possible savings from lead bytes with all-unassigned results in all trail bytes */
    649     uprv_memset(count, 0, sizeof(count));
    650     savings=0;
    651     /* for each lead byte */
    652     for(i=0; i<256; ++i) {
    653         entry=states->stateTable[leadState][i];
    654         if(MBCS_ENTRY_IS_TRANSITION(entry) && (MBCS_ENTRY_TRANSITION_STATE(entry))==trailState) {
    655             /* the offset is different for each lead byte */
    656             offset=MBCS_ENTRY_TRANSITION_OFFSET(entry);
    657             /* for each trail byte for this lead byte */
    658             for(j=0; j<256; ++j) {
    659                 entry=states->stateTable[trailState][j];
    660                 switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
    661                 case MBCS_STATE_VALID_16:
    662                     entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
    663                     if((*pUnicodeCodeUnits)[entry]==0xfffe && ucm_findFallback(toUFallbacks, countToUFallbacks, entry)<0) {
    664                         ++count[i];
    665                     } else {
    666                         j=999; /* do not count for this lead byte because there are assignments */
    667                     }
    668                     break;
    669                 case MBCS_STATE_VALID_16_PAIR:
    670                     entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
    671                     if((*pUnicodeCodeUnits)[entry]==0xfffe) {
    672                         count[i]+=2;
    673                     } else {
    674                         j=999; /* do not count for this lead byte because there are assignments */
    675                     }
    676                     break;
    677                 default:
    678                     break;
    679                 }
    680             }
    681             if(j==256) {
    682                 /* all trail bytes for this lead byte are unassigned */
    683                 savings+=count[i];
    684             } else {
    685                 count[i]=0;
    686             }
    687         }
    688     }
    689     /* subtract from the possible savings the cost of an additional state */
    690     savings=savings*2-1024; /* count bytes, not 16-bit words */
    691     if(savings<=0) {
    692         return;
    693     }
    694     if(verbose) {
    695         printf("compacting toUnicode data saves %ld bytes\n", (long)savings);
    696     }
    697     if(states->countStates>=MBCS_MAX_STATE_COUNT) {
    698         fprintf(stderr, "cannot compact toUnicode because the maximum number of states is reached\n");
    699         return;
    700     }
    701 
    702     /* make a copy of the state table */
    703     oldStateTable=(int32_t (*)[256])uprv_malloc(states->countStates*1024);
    704     if(oldStateTable==NULL) {
    705         fprintf(stderr, "cannot compact toUnicode: out of memory\n");
    706         return;
    707     }
    708     uprv_memcpy(oldStateTable, states->stateTable, states->countStates*1024);
    709 
    710     /* add the new state */
    711     /*
    712      * this function does not catch the degenerate case where all lead bytes
    713      * have all-unassigned trail bytes and the lead state could be removed
    714      */
    715     newState=states->countStates++;
    716     states->stateFlags[newState]=0;
    717     /* copy the old trail state, turning all assigned states into unassigned ones */
    718     for(i=0; i<256; ++i) {
    719         entry=states->stateTable[trailState][i];
    720         switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
    721         case MBCS_STATE_VALID_16:
    722         case MBCS_STATE_VALID_16_PAIR:
    723             states->stateTable[newState][i]=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_UNASSIGNED, 0xfffe);
    724             break;
    725         default:
    726             states->stateTable[newState][i]=entry;
    727             break;
    728         }
    729     }
    730 
    731     /* in the lead state, redirect all lead bytes with all-unassigned trail bytes to the new state */
    732     for(i=0; i<256; ++i) {
    733         if(count[i]>0) {
    734             states->stateTable[leadState][i]=MBCS_ENTRY_SET_STATE(states->stateTable[leadState][i], newState);
    735         }
    736     }
    737 
    738     /* sum up the new state table */
    739     for(i=0; i<states->countStates; ++i) {
    740         states->stateFlags[i]&=~MBCS_STATE_FLAG_READY;
    741     }
    742     sum=sumUpStates(states);
    743 
    744     /* allocate a new, smaller code units array */
    745     oldUnicodeCodeUnits=*pUnicodeCodeUnits;
    746     if(sum==0) {
    747         *pUnicodeCodeUnits=NULL;
    748         if(oldUnicodeCodeUnits!=NULL) {
    749             uprv_free(oldUnicodeCodeUnits);
    750         }
    751         uprv_free(oldStateTable);
    752         return;
    753     }
    754     *pUnicodeCodeUnits=(uint16_t *)uprv_malloc(sum*sizeof(uint16_t));
    755     if(*pUnicodeCodeUnits==NULL) {
    756         fprintf(stderr, "cannot compact toUnicode: out of memory allocating %ld 16-bit code units\n",
    757             (long)sum);
    758         /* revert to the old state table */
    759         *pUnicodeCodeUnits=oldUnicodeCodeUnits;
    760         --states->countStates;
    761         uprv_memcpy(states->stateTable, oldStateTable, states->countStates*1024);
    762         uprv_free(oldStateTable);
    763         return;
    764     }
    765     for(i=0; i<sum; ++i) {
    766         (*pUnicodeCodeUnits)[i]=0xfffe;
    767     }
    768 
    769     /* copy the code units for all assigned characters */
    770     /*
    771      * The old state table has the same lead _and_ trail states for assigned characters!
    772      * The differences are in the offsets, and in the trail states for some unassigned characters.
    773      * For each character with an assigned state in the new table, it was assigned in the old one.
    774      * Only still-assigned characters are copied.
    775      * Note that fallback mappings need to get their offset values adjusted.
    776      */
    777 
    778     /* for each initial state */
    779     for(leadState=0; leadState<states->countStates; ++leadState) {
    780         if((states->stateFlags[leadState]&0xf)==MBCS_STATE_FLAG_DIRECT) {
    781             /* for each lead byte from there */
    782             for(i=0; i<256; ++i) {
    783                 entry=states->stateTable[leadState][i];
    784                 if(MBCS_ENTRY_IS_TRANSITION(entry)) {
    785                     trailState=(uint8_t)MBCS_ENTRY_TRANSITION_STATE(entry);
    786                     /* the new state does not have assigned states */
    787                     if(trailState!=newState) {
    788                         trailOffset=MBCS_ENTRY_TRANSITION_OFFSET(entry);
    789                         oldTrailOffset=MBCS_ENTRY_TRANSITION_OFFSET(oldStateTable[leadState][i]);
    790                         /* for each trail byte */
    791                         for(j=0; j<256; ++j) {
    792                             entry=states->stateTable[trailState][j];
    793                             /* copy assigned-character code units and adjust fallback offsets */
    794                             switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
    795                             case MBCS_STATE_VALID_16:
    796                                 offset=trailOffset+MBCS_ENTRY_FINAL_VALUE_16(entry);
    797                                 /* find the old offset according to the old state table */
    798                                 oldOffset=oldTrailOffset+MBCS_ENTRY_FINAL_VALUE_16(oldStateTable[trailState][j]);
    799                                 unit=(*pUnicodeCodeUnits)[offset]=oldUnicodeCodeUnits[oldOffset];
    800                                 if(unit==0xfffe && (fallback=ucm_findFallback(toUFallbacks, countToUFallbacks, oldOffset))>=0) {
    801                                     toUFallbacks[fallback].offset=0x80000000|offset;
    802                                 }
    803                                 break;
    804                             case MBCS_STATE_VALID_16_PAIR:
    805                                 offset=trailOffset+MBCS_ENTRY_FINAL_VALUE_16(entry);
    806                                 /* find the old offset according to the old state table */
    807                                 oldOffset=oldTrailOffset+MBCS_ENTRY_FINAL_VALUE_16(oldStateTable[trailState][j]);
    808                                 (*pUnicodeCodeUnits)[offset++]=oldUnicodeCodeUnits[oldOffset++];
    809                                 (*pUnicodeCodeUnits)[offset]=oldUnicodeCodeUnits[oldOffset];
    810                                 break;
    811                             default:
    812                                 break;
    813                             }
    814                         }
    815                     }
    816                 }
    817             }
    818         }
    819     }
    820 
    821     /* remove temporary flags from fallback offsets that protected them from being modified twice */
    822     for(i=0; i<countToUFallbacks; ++i) {
    823         toUFallbacks[i].offset&=0x7fffffff;
    824     }
    825 
    826     /* free temporary memory */
    827     uprv_free(oldUnicodeCodeUnits);
    828     uprv_free(oldStateTable);
    829 }
    830 
    831 /*
    832  * recursive sub-function of compactToUnicodeHelper()
    833  * returns:
    834  * >0 number of bytes that are used in unicodeCodeUnits[] that could be saved,
    835  *    if all sequences from this state are unassigned, returns the
    836  * <0 there are assignments in unicodeCodeUnits[]
    837  * 0  no use of unicodeCodeUnits[]
    838  */
    839 static int32_t
    840 findUnassigned(UCMStates *states,
    841                uint16_t *unicodeCodeUnits,
    842                _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
    843                int32_t state, int32_t offset, uint32_t b) {
    844     int32_t i, entry, savings, localSavings, belowSavings;
    845     UBool haveAssigned;
    846 
    847     localSavings=belowSavings=0;
    848     haveAssigned=FALSE;
    849     for(i=0; i<256; ++i) {
    850         entry=states->stateTable[state][i];
    851         if(MBCS_ENTRY_IS_TRANSITION(entry)) {
    852             savings=findUnassigned(states,
    853                         unicodeCodeUnits,
    854                         toUFallbacks, countToUFallbacks,
    855                         MBCS_ENTRY_TRANSITION_STATE(entry),
    856                         offset+MBCS_ENTRY_TRANSITION_OFFSET(entry),
    857                         (b<<8)|(uint32_t)i);
    858             if(savings<0) {
    859                 haveAssigned=TRUE;
    860             } else if(savings>0) {
    861                 printf("    all-unassigned sequences from prefix 0x%02lx state %ld use %ld bytes\n",
    862                     (unsigned long)((b<<8)|i), (long)state, (long)savings);
    863                 belowSavings+=savings;
    864             }
    865         } else if(!haveAssigned) {
    866             switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
    867             case MBCS_STATE_VALID_16:
    868                 entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
    869                 if(unicodeCodeUnits[entry]==0xfffe && ucm_findFallback(toUFallbacks, countToUFallbacks, entry)<0) {
    870                     localSavings+=2;
    871                 } else {
    872                     haveAssigned=TRUE;
    873                 }
    874                 break;
    875             case MBCS_STATE_VALID_16_PAIR:
    876                 entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
    877                 if(unicodeCodeUnits[entry]==0xfffe) {
    878                     localSavings+=4;
    879                 } else {
    880                     haveAssigned=TRUE;
    881                 }
    882                 break;
    883             default:
    884                 break;
    885             }
    886         }
    887     }
    888     if(haveAssigned) {
    889         return -1;
    890     } else {
    891         return localSavings+belowSavings;
    892     }
    893 }
    894 
    895 /* helper function for finding compaction opportunities */
    896 static void
    897 compactToUnicodeHelper(UCMStates *states,
    898                        uint16_t *unicodeCodeUnits,
    899                        _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks) {
    900     int32_t state, savings;
    901 
    902     /* for each initial state */
    903     for(state=0; state<states->countStates; ++state) {
    904         if((states->stateFlags[state]&0xf)==MBCS_STATE_FLAG_DIRECT) {
    905             savings=findUnassigned(states,
    906                         unicodeCodeUnits,
    907                         toUFallbacks, countToUFallbacks,
    908                         state, 0, 0);
    909             if(savings>0) {
    910                 printf("    all-unassigned sequences from initial state %ld use %ld bytes\n",
    911                     (long)state, (long)savings);
    912             }
    913         }
    914     }
    915 }
    916 
    917 static int32_t
    918 compareFallbacks(const void *context, const void *fb1, const void *fb2) {
    919     return ((const _MBCSToUFallback *)fb1)->offset-((const _MBCSToUFallback *)fb2)->offset;
    920 }
    921 
    922 U_CAPI void U_EXPORT2
    923 ucm_optimizeStates(UCMStates *states,
    924                    uint16_t **pUnicodeCodeUnits,
    925                    _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
    926                    UBool verbose) {
    927     UErrorCode errorCode;
    928     int32_t state, cell, entry;
    929 
    930     /* test each state table entry */
    931     for(state=0; state<states->countStates; ++state) {
    932         for(cell=0; cell<256; ++cell) {
    933             entry=states->stateTable[state][cell];
    934             /*
    935              * if the entry is a final one with an MBCS_STATE_VALID_DIRECT_16 action code
    936              * and the code point is "unassigned" (0xfffe), then change it to
    937              * the "unassigned" action code with bits 26..23 set to zero and U+fffe.
    938              */
    939             if(MBCS_ENTRY_SET_STATE(entry, 0)==MBCS_ENTRY_FINAL(0, MBCS_STATE_VALID_DIRECT_16, 0xfffe)) {
    940                 states->stateTable[state][cell]=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_UNASSIGNED);
    941             }
    942         }
    943     }
    944 
    945     /* try to compact the toUnicode tables */
    946     if(states->maxCharLength==2) {
    947         compactToUnicode2(states, pUnicodeCodeUnits, toUFallbacks, countToUFallbacks, verbose);
    948     } else if(states->maxCharLength>2) {
    949         if(verbose) {
    950             compactToUnicodeHelper(states, *pUnicodeCodeUnits, toUFallbacks, countToUFallbacks);
    951         }
    952     }
    953 
    954     /* sort toUFallbacks */
    955     /*
    956      * It should be safe to sort them before compactToUnicode2() is called,
    957      * because it should not change the relative order of the offset values
    958      * that it adjusts, but they need to be sorted at some point, and
    959      * it is safest here.
    960      */
    961     if(countToUFallbacks>0) {
    962         errorCode=U_ZERO_ERROR; /* nothing bad will happen... */
    963         uprv_sortArray(toUFallbacks, countToUFallbacks,
    964                        sizeof(_MBCSToUFallback),
    965                        compareFallbacks, NULL, FALSE, &errorCode);
    966     }
    967 }
    968 
    969 /* use a complete state table ----------------------------------------------- */
    970 
    971 U_CAPI int32_t U_EXPORT2
    972 ucm_countChars(UCMStates *states,
    973                const uint8_t *bytes, int32_t length) {
    974     uint32_t offset;
    975     int32_t i, entry, count;
    976     uint8_t state;
    977 
    978     offset=0;
    979     i=count=0;
    980     state=0;
    981 
    982     if(states->countStates==0) {
    983         fprintf(stderr, "ucm error: there is no state information!\n");
    984         return -1;
    985     }
    986 
    987     /* for SI/SO (like EBCDIC-stateful), double-byte sequences start in state 1 */
    988     if(length==2 && states->outputType==MBCS_OUTPUT_2_SISO) {
    989         state=1;
    990     }
    991 
    992     /*
    993      * Walk down the state table like in conversion,
    994      * much like getNextUChar().
    995      * We assume that c<=0x10ffff.
    996      */
    997     for(i=0; i<length; ++i) {
    998         entry=states->stateTable[state][bytes[i]];
    999         if(MBCS_ENTRY_IS_TRANSITION(entry)) {
   1000             state=(uint8_t)MBCS_ENTRY_TRANSITION_STATE(entry);
   1001             offset+=MBCS_ENTRY_TRANSITION_OFFSET(entry);
   1002         } else {
   1003             switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
   1004             case MBCS_STATE_ILLEGAL:
   1005                 fprintf(stderr, "ucm error: byte sequence ends in illegal state\n");
   1006                 return -1;
   1007             case MBCS_STATE_CHANGE_ONLY:
   1008                 fprintf(stderr, "ucm error: byte sequence ends in state-change-only\n");
   1009                 return -1;
   1010             case MBCS_STATE_UNASSIGNED:
   1011             case MBCS_STATE_FALLBACK_DIRECT_16:
   1012             case MBCS_STATE_VALID_DIRECT_16:
   1013             case MBCS_STATE_FALLBACK_DIRECT_20:
   1014             case MBCS_STATE_VALID_DIRECT_20:
   1015             case MBCS_STATE_VALID_16:
   1016             case MBCS_STATE_VALID_16_PAIR:
   1017                 /* count a complete character and prepare for a new one */
   1018                 ++count;
   1019                 state=(uint8_t)MBCS_ENTRY_FINAL_STATE(entry);
   1020                 offset=0;
   1021                 break;
   1022             default:
   1023                 /* reserved, must never occur */
   1024                 fprintf(stderr, "ucm error: byte sequence reached reserved action code, entry: 0x%02lx\n", (unsigned long)entry);
   1025                 return -1;
   1026             }
   1027         }
   1028     }
   1029 
   1030     if(offset!=0) {
   1031         fprintf(stderr, "ucm error: byte sequence too short, ends in non-final state %hu\n", state);
   1032         return -1;
   1033     }
   1034 
   1035     /*
   1036      * for SI/SO (like EBCDIC-stateful), multiple-character results
   1037      * must consist of only double-byte sequences
   1038      */
   1039     if(count>1 && states->outputType==MBCS_OUTPUT_2_SISO && length!=2*count) {
   1040         fprintf(stderr, "ucm error: SI/SO (like EBCDIC-stateful) result with %d characters does not contain all DBCS\n", (int)count);
   1041         return -1;
   1042     }
   1043 
   1044     return count;
   1045 }
   1046 #endif
   1047 
   1048