Check in the pristine copy of ICU 4.6...

icu46/source/tools/toolutil/ucmstate.c

+/*
+*******************************************************************************
+*
+*   Copyright (C) 2003-2010, International Business Machines
+*   Corporation and others.  All Rights Reserved.
+*
+*******************************************************************************
+*   file name:  ucmstate.c
+*   encoding:   US-ASCII
+*   tab size:   8 (not used)
+*   indentation:4
+*
+*   created on: 2003oct09
+*   created by: Markus W. Scherer
+*
+*   This file handles ICU .ucm file state information as part of the ucm module.
+*   Most of this code used to be in makeconv.c.
+*/
+
+#include "unicode/utypes.h"
+#include "cstring.h"
+#include "cmemory.h"
+#include "uarrsort.h"
+#include "ucnvmbcs.h"
+#include "ucnv_ext.h"
+#include "uparse.h"
+#include "ucm.h"
+#include <stdio.h>
+
+#if !UCONFIG_NO_CONVERSION
+
+/* MBCS state handling ------------------------------------------------------ */
+
+/*
+ * state table row grammar (ebnf-style):
+ * (whitespace is allowed between all tokens)
+ *
+ * row=[[firstentry ','] entry (',' entry)*]
+ * firstentry="initial" | "surrogates"
+ *            (initial state (default for state 0), output is all surrogate pairs)
+ * entry=range [':' nextstate] ['.' action]
+ * range=number ['-' number]
+ * nextstate=number
+ *           (0..7f)
+ * action='u' | 's' | 'p' | 'i'
+ *        (unassigned, state change only, surrogate pair, illegal)
+ * number=(1- or 2-digit hexadecimal number)
+ */
+static const char *
+parseState(const char *s, int32_t state[256], uint32_t *pFlags) {
+    const char *t;
+    uint32_t start, end, i;
+    int32_t entry;
+
+    /* initialize the state: all illegal with U+ffff */
+    for(i=0; i<256; ++i) {
+        state[i]=MBCS_ENTRY_FINAL(0, MBCS_STATE_ILLEGAL, 0xffff);
+    }
+
+    /* skip leading white space */
+    s=u_skipWhitespace(s);
+
+    /* is there an "initial" or "surrogates" directive? */
+    if(uprv_strncmp("initial", s, 7)==0) {
+        *pFlags=MBCS_STATE_FLAG_DIRECT;
+        s=u_skipWhitespace(s+7);
+        if(*s++!=',') {
+            return s-1;
+        }
+    } else if(*pFlags==0 && uprv_strncmp("surrogates", s, 10)==0) {
+        *pFlags=MBCS_STATE_FLAG_SURROGATES;
+        s=u_skipWhitespace(s+10);
+        if(*s++!=',') {
+            return s-1;
+        }
+    } else if(*s==0) {
+        /* empty state row: all-illegal */
+        return NULL;
+    }
+
+    for(;;) {
+        /* read an entry, the start of the range first */
+        s=u_skipWhitespace(s);
+        start=uprv_strtoul(s, (char **)&t, 16);
+        if(s==t || 0xff<start) {
+            return s;
+        }
+        s=u_skipWhitespace(t);
+
+        /* read the end of the range if there is one */
+        if(*s=='-') {
+            s=u_skipWhitespace(s+1);
+            end=uprv_strtoul(s, (char **)&t, 16);
+            if(s==t || end<start || 0xff<end) {
+                return s;
+            }
+            s=u_skipWhitespace(t);
+        } else {
+            end=start;
+        }
+
+        /* determine the state entrys for this range */
+        if(*s!=':' && *s!='.') {
+            /* the default is: final state with valid entries */
+            entry=MBCS_ENTRY_FINAL(0, MBCS_STATE_VALID_16, 0);
+        } else {
+            entry=MBCS_ENTRY_TRANSITION(0, 0);
+            if(*s==':') {
+                /* get the next state, default to 0 */
+                s=u_skipWhitespace(s+1);
+                i=uprv_strtoul(s, (char **)&t, 16);
+                if(s!=t) {
+                    if(0x7f<i) {
+                        return s;
+                    }
+                    s=u_skipWhitespace(t);
+                    entry=MBCS_ENTRY_SET_STATE(entry, i);
+                }
+            }
+
+            /* get the state action, default to valid */
+            if(*s=='.') {
+                /* this is a final state */
+                entry=MBCS_ENTRY_SET_FINAL(entry);
+
+                s=u_skipWhitespace(s+1);
+                if(*s=='u') {
+                    /* unassigned set U+fffe */
+                    entry=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_UNASSIGNED, 0xfffe);
+                    s=u_skipWhitespace(s+1);
+                } else if(*s=='p') {
+                    if(*pFlags!=MBCS_STATE_FLAG_DIRECT) {
+                        entry=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_VALID_16_PAIR);
+                    } else {
+                        entry=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_VALID_16);
+                    }
+                    s=u_skipWhitespace(s+1);
+                } else if(*s=='s') {
+                    entry=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_CHANGE_ONLY);
+                    s=u_skipWhitespace(s+1);
+                } else if(*s=='i') {
+                    /* illegal set U+ffff */
+                    entry=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_ILLEGAL, 0xffff);
+                    s=u_skipWhitespace(s+1);
+                } else {
+                    /* default to valid */
+                    entry=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_VALID_16);
+                }
+            } else {
+                /* this is an intermediate state, nothing to do */
+            }
+        }
+
+        /* adjust "final valid" states according to the state flags */
+        if(MBCS_ENTRY_FINAL_ACTION(entry)==MBCS_STATE_VALID_16) {
+            switch(*pFlags) {
+            case 0:
+                /* no adjustment */
+                break;
+            case MBCS_STATE_FLAG_DIRECT:
+                /* set the valid-direct code point to "unassigned"==0xfffe */
+                entry=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_VALID_DIRECT_16, 0xfffe);
+                break;
+            case MBCS_STATE_FLAG_SURROGATES:
+                entry=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_VALID_16_PAIR, 0);
+                break;
+            default:
+                break;
+            }
+        }
+
+        /* set this entry for the range */
+        for(i=start; i<=end; ++i) {
+            state[i]=entry;
+        }
+
+        if(*s==',') {
+            ++s;
+        } else {
+            return *s==0 ? NULL : s;
+        }
+    }
+}
+
+U_CAPI void U_EXPORT2
+ucm_addState(UCMStates *states, const char *s) {
+    const char *error;
+
+    if(states->countStates==MBCS_MAX_STATE_COUNT) {
+        fprintf(stderr, "ucm error: too many states (maximum %u)\n", MBCS_MAX_STATE_COUNT);
+        exit(U_INVALID_TABLE_FORMAT);
+    }
+
+    error=parseState(s, states->stateTable[states->countStates],
+                       &states->stateFlags[states->countStates]);
+    if(error!=NULL) {
+        fprintf(stderr, "ucm error: parse error in state definition at '%s'\n", error);
+        exit(U_INVALID_TABLE_FORMAT);
+    }
+
+    ++states->countStates;
+}
+
+U_CAPI UBool U_EXPORT2
+ucm_parseHeaderLine(UCMFile *ucm,
+                    char *line, char **pKey, char **pValue) {
+    UCMStates *states;
+    char *s, *end;
+    char c;
+
+    states=&ucm->states;
+
+    /* remove comments and trailing CR and LF and remove whitespace from the end */
+    for(end=line; (c=*end)!=0; ++end) {
+        if(c=='#' || c=='\r' || c=='\n') {
+            break;
+        }
+    }
+    while(end>line && (*(end-1)==' ' || *(end-1)=='\t')) {
+        --end;
+    }
+    *end=0;
+
+    /* skip leading white space and ignore empty lines */
+    s=(char *)u_skipWhitespace(line);
+    if(*s==0) {
+        return TRUE;
+    }
+
+    /* stop at the beginning of the mapping section */
+    if(uprv_memcmp(s, "CHARMAP", 7)==0) {
+        return FALSE;
+    }
+
+    /* get the key name, bracketed in <> */
+    if(*s!='<') {
+        fprintf(stderr, "ucm error: no header field <key> in line \"%s\"\n", line);
+        exit(U_INVALID_TABLE_FORMAT);
+    }
+    *pKey=++s;
+    while(*s!='>') {
+        if(*s==0) {
+            fprintf(stderr, "ucm error: incomplete header field <key> in line \"%s\"\n", line);
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        ++s;
+    }
+    *s=0;
+
+    /* get the value string, possibly quoted */
+    s=(char *)u_skipWhitespace(s+1);
+    if(*s!='"') {
+        *pValue=s;
+    } else {
+        /* remove the quotes */
+        *pValue=s+1;
+        if(end>*pValue && *(end-1)=='"') {
+            *--end=0;
+        }
+    }
+
+    /* collect the information from the header field, ignore unknown keys */
+    if(uprv_strcmp(*pKey, "uconv_class")==0) {
+        if(uprv_strcmp(*pValue, "DBCS")==0) {
+            states->conversionType=UCNV_DBCS;
+        } else if(uprv_strcmp(*pValue, "SBCS")==0) {
+            states->conversionType = UCNV_SBCS;
+        } else if(uprv_strcmp(*pValue, "MBCS")==0) {
+            states->conversionType = UCNV_MBCS;
+        } else if(uprv_strcmp(*pValue, "EBCDIC_STATEFUL")==0) {
+            states->conversionType = UCNV_EBCDIC_STATEFUL;
+        } else {
+            fprintf(stderr, "ucm error: unknown <uconv_class> %s\n", *pValue);
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        return TRUE;
+    } else if(uprv_strcmp(*pKey, "mb_cur_max")==0) {
+        c=**pValue;
+        if('1'<=c && c<='4' && (*pValue)[1]==0) {
+            states->maxCharLength=(int8_t)(c-'0');
+            states->outputType=(int8_t)(states->maxCharLength-1);
+        } else {
+            fprintf(stderr, "ucm error: illegal <mb_cur_max> %s\n", *pValue);
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        return TRUE;
+    } else if(uprv_strcmp(*pKey, "mb_cur_min")==0) {
+        c=**pValue;
+        if('1'<=c && c<='4' && (*pValue)[1]==0) {
+            states->minCharLength=(int8_t)(c-'0');
+        } else {
+            fprintf(stderr, "ucm error: illegal <mb_cur_min> %s\n", *pValue);
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        return TRUE;
+    } else if(uprv_strcmp(*pKey, "icu:state")==0) {
+        /* if an SBCS/DBCS/EBCDIC_STATEFUL converter has icu:state, then turn it into MBCS */
+        switch(states->conversionType) {
+        case UCNV_SBCS:
+        case UCNV_DBCS:
+        case UCNV_EBCDIC_STATEFUL:
+            states->conversionType=UCNV_MBCS;
+            break;
+        case UCNV_MBCS:
+            break;
+        default:
+            fprintf(stderr, "ucm error: <icu:state> entry for non-MBCS table or before the <uconv_class> line\n");
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+
+        if(states->maxCharLength==0) {
+            fprintf(stderr, "ucm error: <icu:state> before the <mb_cur_max> line\n");
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        ucm_addState(states, *pValue);
+        return TRUE;
+    } else if(uprv_strcmp(*pKey, "icu:base")==0) {
+        if(**pValue==0) {
+            fprintf(stderr, "ucm error: <icu:base> without a base table name\n");
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        uprv_strcpy(ucm->baseName, *pValue);
+        return TRUE;
+    }
+
+    return FALSE;
+}
+
+/* post-processing ---------------------------------------------------------- */
+
+static int32_t
+sumUpStates(UCMStates *states) {
+    int32_t entry, sum, state, cell, count;
+    UBool allStatesReady;
+
+    /*
+     * Sum up the offsets for all states.
+     * In each final state (where there are only final entries),
+     * the offsets add up directly.
+     * In all other state table rows, for each transition entry to another state,
+     * the offsets sum of that state needs to be added.
+     * This is achieved in at most countStates iterations.
+     */
+    allStatesReady=FALSE;
+    for(count=states->countStates; !allStatesReady && count>=0; --count) {
+        allStatesReady=TRUE;
+        for(state=states->countStates-1; state>=0; --state) {
+            if(!(states->stateFlags[state]&MBCS_STATE_FLAG_READY)) {
+                allStatesReady=FALSE;
+                sum=0;
+
+                /* at first, add up only the final delta offsets to keep them <512 */
+                for(cell=0; cell<256; ++cell) {
+                    entry=states->stateTable[state][cell];
+                    if(MBCS_ENTRY_IS_FINAL(entry)) {
+                        switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
+                        case MBCS_STATE_VALID_16:
+                            states->stateTable[state][cell]=MBCS_ENTRY_FINAL_SET_VALUE(entry, sum);
+                            sum+=1;
+                            break;
+                        case MBCS_STATE_VALID_16_PAIR:
+                            states->stateTable[state][cell]=MBCS_ENTRY_FINAL_SET_VALUE(entry, sum);
+                            sum+=2;
+                            break;
+                        default:
+                            /* no addition */
+                            break;
+                        }
+                    }
+                }
+
+                /* now, add up the delta offsets for the transitional entries */
+                for(cell=0; cell<256; ++cell) {
+                    entry=states->stateTable[state][cell];
+                    if(MBCS_ENTRY_IS_TRANSITION(entry)) {
+                        if(states->stateFlags[MBCS_ENTRY_TRANSITION_STATE(entry)]&MBCS_STATE_FLAG_READY) {
+                            states->stateTable[state][cell]=MBCS_ENTRY_TRANSITION_SET_OFFSET(entry, sum);
+                            sum+=states->stateOffsetSum[MBCS_ENTRY_TRANSITION_STATE(entry)];
+                        } else {
+                            /* that next state does not have a sum yet, we cannot finish the one for this state */
+                            sum=-1;
+                            break;
+                        }
+                    }
+                }
+
+                if(sum!=-1) {
+                    states->stateOffsetSum[state]=sum;
+                    states->stateFlags[state]|=MBCS_STATE_FLAG_READY;
+                }
+            }
+        }
+    }
+
+    if(!allStatesReady) {
+        fprintf(stderr, "ucm error: the state table contains loops\n");
+        exit(U_INVALID_TABLE_FORMAT);
+    }
+
+    /*
+     * For all "direct" (i.e., initial) states>0,
+     * the offsets need to be increased by the sum of
+     * the previous initial states.
+     */
+    sum=states->stateOffsetSum[0];
+    for(state=1; state<states->countStates; ++state) {
+        if((states->stateFlags[state]&0xf)==MBCS_STATE_FLAG_DIRECT) {
+            int32_t sum2=sum;
+            sum+=states->stateOffsetSum[state];
+            for(cell=0; cell<256; ++cell) {
+                entry=states->stateTable[state][cell];
+                if(MBCS_ENTRY_IS_TRANSITION(entry)) {
+                    states->stateTable[state][cell]=MBCS_ENTRY_TRANSITION_ADD_OFFSET(entry, sum2);
+                }
+            }
+        }
+    }
+
+    /* round up to the next even number to have the following data 32-bit-aligned */
+    return states->countToUCodeUnits=(sum+1)&~1;
+}
+
+U_CAPI void U_EXPORT2
+ucm_processStates(UCMStates *states, UBool ignoreSISOCheck) {
+    int32_t entry, state, cell, count;
+
+    if(states->conversionType==UCNV_UNSUPPORTED_CONVERTER) {
+        fprintf(stderr, "ucm error: missing conversion type (<uconv_class>)\n");
+        exit(U_INVALID_TABLE_FORMAT);
+    }
+
+    if(states->countStates==0) {
+        switch(states->conversionType) {
+        case UCNV_SBCS:
+            /* SBCS: use MBCS data structure with a default state table */
+            if(states->maxCharLength!=1) {
+                fprintf(stderr, "error: SBCS codepage with max B/char!=1\n");
+                exit(U_INVALID_TABLE_FORMAT);
+            }
+            states->conversionType=UCNV_MBCS;
+            ucm_addState(states, "0-ff");
+            break;
+        case UCNV_MBCS:
+            fprintf(stderr, "ucm error: missing state table information (<icu:state>) for MBCS\n");
+            exit(U_INVALID_TABLE_FORMAT);
+            break;
+        case UCNV_EBCDIC_STATEFUL:
+            /* EBCDIC_STATEFUL: use MBCS data structure with a default state table */
+            if(states->minCharLength!=1 || states->maxCharLength!=2) {
+                fprintf(stderr, "error: DBCS codepage with min B/char!=1 or max B/char!=2\n");
+                exit(U_INVALID_TABLE_FORMAT);
+            }
+            states->conversionType=UCNV_MBCS;
+            ucm_addState(states, "0-ff, e:1.s, f:0.s");
+            ucm_addState(states, "initial, 0-3f:4, e:1.s, f:0.s, 40:3, 41-fe:2, ff:4");
+            ucm_addState(states, "0-40:1.i, 41-fe:1., ff:1.i");
+            ucm_addState(states, "0-ff:1.i, 40:1.");
+            ucm_addState(states, "0-ff:1.i");
+            break;
+        case UCNV_DBCS:
+            /* DBCS: use MBCS data structure with a default state table */
+            if(states->minCharLength!=2 || states->maxCharLength!=2) {
+                fprintf(stderr, "error: DBCS codepage with min or max B/char!=2\n");
+                exit(U_INVALID_TABLE_FORMAT);
+            }
+            states->conversionType = UCNV_MBCS;
+            ucm_addState(states, "0-3f:3, 40:2, 41-fe:1, ff:3");
+            ucm_addState(states, "41-fe");
+            ucm_addState(states, "40");
+            ucm_addState(states, "");
+            break;
+        default:
+            fprintf(stderr, "ucm error: unknown charset structure\n");
+            exit(U_INVALID_TABLE_FORMAT);
+            break;
+        }
+    }
+
+    /*
+     * check that the min/max character lengths are reasonable;
+     * to do this right, all paths through the state table would have to be
+     * recursively walked while keeping track of the sequence lengths,
+     * but these simple checks cover most state tables in practice
+     */
+    if(states->maxCharLength<states->minCharLength) {
+        fprintf(stderr, "ucm error: max B/char < min B/char\n");
+        exit(U_INVALID_TABLE_FORMAT);
+    }
+
+    /* count non-direct states and compare with max B/char */
+    count=0;
+    for(state=0; state<states->countStates; ++state) {
+        if((states->stateFlags[state]&0xf)!=MBCS_STATE_FLAG_DIRECT) {
+            ++count;
+        }
+    }
+    if(states->maxCharLength>count+1) {
+        fprintf(stderr, "ucm error: max B/char too large\n");
+        exit(U_INVALID_TABLE_FORMAT);
+    }
+
+    if(states->minCharLength==1) {
+        int32_t action;
+
+        /*
+         * if there are single-byte characters,
+         * then the initial state must have direct result states
+         */
+        for(cell=0; cell<256; ++cell) {
+            entry=states->stateTable[0][cell];
+            if( MBCS_ENTRY_IS_FINAL(entry) &&
+                ((action=MBCS_ENTRY_FINAL_ACTION(entry))==MBCS_STATE_VALID_DIRECT_16 ||
+                 action==MBCS_STATE_UNASSIGNED)
+            ) {
+                break;
+            }
+        }
+
+        if(cell==256) {
+            fprintf(stderr, "ucm warning: min B/char too small\n");
+        }
+    }
+
+    /*
+     * make sure that all "next state" values are within limits
+     * and that all next states after final ones have the "direct"
+     * flag of initial states
+     */
+    for(state=states->countStates-1; state>=0; --state) {
+        for(cell=0; cell<256; ++cell) {
+            entry=states->stateTable[state][cell];
+            if((uint8_t)MBCS_ENTRY_STATE(entry)>=states->countStates) {
+                fprintf(stderr, "ucm error: state table entry [%x][%x] has a next state of %x that is too high\n",
+                    (int)state, (int)cell, (int)MBCS_ENTRY_STATE(entry));
+                exit(U_INVALID_TABLE_FORMAT);
+            }
+            if(MBCS_ENTRY_IS_FINAL(entry) && (states->stateFlags[MBCS_ENTRY_STATE(entry)]&0xf)!=MBCS_STATE_FLAG_DIRECT) {
+                fprintf(stderr, "ucm error: state table entry [%x][%x] is final but has a non-initial next state of %x\n",
+                    (int)state, (int)cell, (int)MBCS_ENTRY_STATE(entry));
+                exit(U_INVALID_TABLE_FORMAT);
+            } else if(MBCS_ENTRY_IS_TRANSITION(entry) && (states->stateFlags[MBCS_ENTRY_STATE(entry)]&0xf)==MBCS_STATE_FLAG_DIRECT) {
+                fprintf(stderr, "ucm error: state table entry [%x][%x] is not final but has an initial next state of %x\n",
+                    (int)state, (int)cell, (int)MBCS_ENTRY_STATE(entry));
+                exit(U_INVALID_TABLE_FORMAT);
+            }
+        }
+    }
+
+    /* is this an SI/SO (like EBCDIC-stateful) state table? */
+    if(states->countStates>=2 && (states->stateFlags[1]&0xf)==MBCS_STATE_FLAG_DIRECT) {
+        if(states->maxCharLength!=2) {
+            fprintf(stderr, "ucm error: SI/SO codepages must have max 2 bytes/char (not %x)\n", (int)states->maxCharLength);
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        if(states->countStates<3) {
+            fprintf(stderr, "ucm error: SI/SO codepages must have at least 3 states (not %x)\n", (int)states->countStates);
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        /* are the SI/SO all in the right places? */
+        if( ignoreSISOCheck ||
+           (states->stateTable[0][0xe]==MBCS_ENTRY_FINAL(1, MBCS_STATE_CHANGE_ONLY, 0) &&
+            states->stateTable[0][0xf]==MBCS_ENTRY_FINAL(0, MBCS_STATE_CHANGE_ONLY, 0) &&
+            states->stateTable[1][0xe]==MBCS_ENTRY_FINAL(1, MBCS_STATE_CHANGE_ONLY, 0) &&
+            states->stateTable[1][0xf]==MBCS_ENTRY_FINAL(0, MBCS_STATE_CHANGE_ONLY, 0))
+        ) {
+            states->outputType=MBCS_OUTPUT_2_SISO;
+        } else {
+            fprintf(stderr, "ucm error: SI/SO codepages must have in states 0 and 1 transitions e:1.s, f:0.s\n");
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        state=2;
+    } else {
+        state=1;
+    }
+
+    /* check that no unexpected state is a "direct" one */
+    while(state<states->countStates) {
+        if((states->stateFlags[state]&0xf)==MBCS_STATE_FLAG_DIRECT) {
+            fprintf(stderr, "ucm error: state %d is 'initial' - not supported except for SI/SO codepages\n", (int)state);
+            exit(U_INVALID_TABLE_FORMAT);
+        }
+        ++state;
+    }
+
+    sumUpStates(states);
+}
+
+/* find a fallback for this offset; return the index or -1 if not found */
+U_CAPI int32_t U_EXPORT2
+ucm_findFallback(_MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
+                 uint32_t offset) {
+    int32_t i;
+
+    if(countToUFallbacks==0) {
+        /* shortcut: most codepages do not have fallbacks from codepage to Unicode */
+        return -1;
+    }
+
+    /* do a linear search for the fallback mapping (the table is not yet sorted) */
+    for(i=0; i<countToUFallbacks; ++i) {
+        if(offset==toUFallbacks[i].offset) {
+            return i;
+        }
+    }
+    return -1;
+}
+
+/*
+ * This function tries to compact toUnicode tables for 2-byte codepages
+ * by finding lead bytes with all-unassigned trail bytes and adding another state
+ * for them.
+ */
+static void
+compactToUnicode2(UCMStates *states,
+                  uint16_t **pUnicodeCodeUnits,
+                  _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
+                  UBool verbose) {
+    int32_t (*oldStateTable)[256];
+    uint16_t count[256];
+    uint16_t *oldUnicodeCodeUnits;
+    int32_t entry, offset, oldOffset, trailOffset, oldTrailOffset, savings, sum;
+    int32_t i, j, leadState, trailState, newState, fallback;
+    uint16_t unit;
+
+    /* find the lead state */
+    if(states->outputType==MBCS_OUTPUT_2_SISO) {
+        /* use the DBCS lead state for SI/SO codepages */
+        leadState=1;
+    } else {
+        leadState=0;
+    }
+
+    /* find the main trail state: the most used target state */
+    uprv_memset(count, 0, sizeof(count));
+    for(i=0; i<256; ++i) {
+        entry=states->stateTable[leadState][i];
+        if(MBCS_ENTRY_IS_TRANSITION(entry)) {
+            ++count[MBCS_ENTRY_TRANSITION_STATE(entry)];
+        }
+    }
+    trailState=0;
+    for(i=1; i<states->countStates; ++i) {
+        if(count[i]>count[trailState]) {
+            trailState=i;
+        }
+    }
+
+    /* count possible savings from lead bytes with all-unassigned results in all trail bytes */
+    uprv_memset(count, 0, sizeof(count));
+    savings=0;
+    /* for each lead byte */
+    for(i=0; i<256; ++i) {
+        entry=states->stateTable[leadState][i];
+        if(MBCS_ENTRY_IS_TRANSITION(entry) && (MBCS_ENTRY_TRANSITION_STATE(entry))==trailState) {
+            /* the offset is different for each lead byte */
+            offset=MBCS_ENTRY_TRANSITION_OFFSET(entry);
+            /* for each trail byte for this lead byte */
+            for(j=0; j<256; ++j) {
+                entry=states->stateTable[trailState][j];
+                switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
+                case MBCS_STATE_VALID_16:
+                    entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
+                    if((*pUnicodeCodeUnits)[entry]==0xfffe && ucm_findFallback(toUFallbacks, countToUFallbacks, entry)<0) {
+                        ++count[i];
+                    } else {
+                        j=999; /* do not count for this lead byte because there are assignments */
+                    }
+                    break;
+                case MBCS_STATE_VALID_16_PAIR:
+                    entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
+                    if((*pUnicodeCodeUnits)[entry]==0xfffe) {
+                        count[i]+=2;
+                    } else {
+                        j=999; /* do not count for this lead byte because there are assignments */
+                    }
+                    break;
+                default:
+                    break;
+                }
+            }
+            if(j==256) {
+                /* all trail bytes for this lead byte are unassigned */
+                savings+=count[i];
+            } else {
+                count[i]=0;
+            }
+        }
+    }
+    /* subtract from the possible savings the cost of an additional state */
+    savings=savings*2-1024; /* count bytes, not 16-bit words */
+    if(savings<=0) {
+        return;
+    }
+    if(verbose) {
+        printf("compacting toUnicode data saves %ld bytes\n", (long)savings);
+    }
+    if(states->countStates>=MBCS_MAX_STATE_COUNT) {
+        fprintf(stderr, "cannot compact toUnicode because the maximum number of states is reached\n");
+        return;
+    }
+
+    /* make a copy of the state table */
+    oldStateTable=(int32_t (*)[256])uprv_malloc(states->countStates*1024);
+    if(oldStateTable==NULL) {
+        fprintf(stderr, "cannot compact toUnicode: out of memory\n");
+        return;
+    }
+    uprv_memcpy(oldStateTable, states->stateTable, states->countStates*1024);
+
+    /* add the new state */
+    /*
+     * this function does not catch the degenerate case where all lead bytes
+     * have all-unassigned trail bytes and the lead state could be removed
+     */
+    newState=states->countStates++;
+    states->stateFlags[newState]=0;
+    /* copy the old trail state, turning all assigned states into unassigned ones */
+    for(i=0; i<256; ++i) {
+        entry=states->stateTable[trailState][i];
+        switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
+        case MBCS_STATE_VALID_16:
+        case MBCS_STATE_VALID_16_PAIR:
+            states->stateTable[newState][i]=MBCS_ENTRY_FINAL_SET_ACTION_VALUE(entry, MBCS_STATE_UNASSIGNED, 0xfffe);
+            break;
+        default:
+            states->stateTable[newState][i]=entry;
+            break;
+        }
+    }
+
+    /* in the lead state, redirect all lead bytes with all-unassigned trail bytes to the new state */
+    for(i=0; i<256; ++i) {
+        if(count[i]>0) {
+            states->stateTable[leadState][i]=MBCS_ENTRY_SET_STATE(states->stateTable[leadState][i], newState);
+        }
+    }
+
+    /* sum up the new state table */
+    for(i=0; i<states->countStates; ++i) {
+        states->stateFlags[i]&=~MBCS_STATE_FLAG_READY;
+    }
+    sum=sumUpStates(states);
+
+    /* allocate a new, smaller code units array */
+    oldUnicodeCodeUnits=*pUnicodeCodeUnits;
+    if(sum==0) {
+        *pUnicodeCodeUnits=NULL;
+        if(oldUnicodeCodeUnits!=NULL) {
+            uprv_free(oldUnicodeCodeUnits);
+        }
+        uprv_free(oldStateTable);
+        return;
+    }
+    *pUnicodeCodeUnits=(uint16_t *)uprv_malloc(sum*sizeof(uint16_t));
+    if(*pUnicodeCodeUnits==NULL) {
+        fprintf(stderr, "cannot compact toUnicode: out of memory allocating %ld 16-bit code units\n",
+            (long)sum);
+        /* revert to the old state table */
+        *pUnicodeCodeUnits=oldUnicodeCodeUnits;
+        --states->countStates;
+        uprv_memcpy(states->stateTable, oldStateTable, states->countStates*1024);
+        uprv_free(oldStateTable);
+        return;
+    }
+    for(i=0; i<sum; ++i) {
+        (*pUnicodeCodeUnits)[i]=0xfffe;
+    }
+
+    /* copy the code units for all assigned characters */
+    /*
+     * The old state table has the same lead _and_ trail states for assigned characters!
+     * The differences are in the offsets, and in the trail states for some unassigned characters.
+     * For each character with an assigned state in the new table, it was assigned in the old one.
+     * Only still-assigned characters are copied.
+     * Note that fallback mappings need to get their offset values adjusted.
+     */
+
+    /* for each initial state */
+    for(leadState=0; leadState<states->countStates; ++leadState) {
+        if((states->stateFlags[leadState]&0xf)==MBCS_STATE_FLAG_DIRECT) {
+            /* for each lead byte from there */
+            for(i=0; i<256; ++i) {
+                entry=states->stateTable[leadState][i];
+                if(MBCS_ENTRY_IS_TRANSITION(entry)) {
+                    trailState=(uint8_t)MBCS_ENTRY_TRANSITION_STATE(entry);
+                    /* the new state does not have assigned states */
+                    if(trailState!=newState) {
+                        trailOffset=MBCS_ENTRY_TRANSITION_OFFSET(entry);
+                        oldTrailOffset=MBCS_ENTRY_TRANSITION_OFFSET(oldStateTable[leadState][i]);
+                        /* for each trail byte */
+                        for(j=0; j<256; ++j) {
+                            entry=states->stateTable[trailState][j];
+                            /* copy assigned-character code units and adjust fallback offsets */
+                            switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
+                            case MBCS_STATE_VALID_16:
+                                offset=trailOffset+MBCS_ENTRY_FINAL_VALUE_16(entry);
+                                /* find the old offset according to the old state table */
+                                oldOffset=oldTrailOffset+MBCS_ENTRY_FINAL_VALUE_16(oldStateTable[trailState][j]);
+                                unit=(*pUnicodeCodeUnits)[offset]=oldUnicodeCodeUnits[oldOffset];
+                                if(unit==0xfffe && (fallback=ucm_findFallback(toUFallbacks, countToUFallbacks, oldOffset))>=0) {
+                                    toUFallbacks[fallback].offset=0x80000000|offset;
+                                }
+                                break;
+                            case MBCS_STATE_VALID_16_PAIR:
+                                offset=trailOffset+MBCS_ENTRY_FINAL_VALUE_16(entry);
+                                /* find the old offset according to the old state table */
+                                oldOffset=oldTrailOffset+MBCS_ENTRY_FINAL_VALUE_16(oldStateTable[trailState][j]);
+                                (*pUnicodeCodeUnits)[offset++]=oldUnicodeCodeUnits[oldOffset++];
+                                (*pUnicodeCodeUnits)[offset]=oldUnicodeCodeUnits[oldOffset];
+                                break;
+                            default:
+                                break;
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    /* remove temporary flags from fallback offsets that protected them from being modified twice */
+    for(i=0; i<countToUFallbacks; ++i) {
+        toUFallbacks[i].offset&=0x7fffffff;
+    }
+
+    /* free temporary memory */
+    uprv_free(oldUnicodeCodeUnits);
+    uprv_free(oldStateTable);
+}
+
+/*
+ * recursive sub-function of compactToUnicodeHelper()
+ * returns:
+ * >0 number of bytes that are used in unicodeCodeUnits[] that could be saved,
+ *    if all sequences from this state are unassigned, returns the
+ * <0 there are assignments in unicodeCodeUnits[]
+ * 0  no use of unicodeCodeUnits[]
+ */
+static int32_t
+findUnassigned(UCMStates *states,
+               uint16_t *unicodeCodeUnits,
+               _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
+               int32_t state, int32_t offset, uint32_t b) {
+    int32_t i, entry, savings, localSavings, belowSavings;
+    UBool haveAssigned;
+
+    localSavings=belowSavings=0;
+    haveAssigned=FALSE;
+    for(i=0; i<256; ++i) {
+        entry=states->stateTable[state][i];
+        if(MBCS_ENTRY_IS_TRANSITION(entry)) {
+            savings=findUnassigned(states,
+                        unicodeCodeUnits,
+                        toUFallbacks, countToUFallbacks,
+                        MBCS_ENTRY_TRANSITION_STATE(entry),
+                        offset+MBCS_ENTRY_TRANSITION_OFFSET(entry),
+                        (b<<8)|(uint32_t)i);
+            if(savings<0) {
+                haveAssigned=TRUE;
+            } else if(savings>0) {
+                printf("    all-unassigned sequences from prefix 0x%02lx state %ld use %ld bytes\n",
+                    (unsigned long)((b<<8)|i), (long)state, (long)savings);
+                belowSavings+=savings;
+            }
+        } else if(!haveAssigned) {
+            switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
+            case MBCS_STATE_VALID_16:
+                entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
+                if(unicodeCodeUnits[entry]==0xfffe && ucm_findFallback(toUFallbacks, countToUFallbacks, entry)<0) {
+                    localSavings+=2;
+                } else {
+                    haveAssigned=TRUE;
+                }
+                break;
+            case MBCS_STATE_VALID_16_PAIR:
+                entry=offset+MBCS_ENTRY_FINAL_VALUE_16(entry);
+                if(unicodeCodeUnits[entry]==0xfffe) {
+                    localSavings+=4;
+                } else {
+                    haveAssigned=TRUE;
+                }
+                break;
+            default:
+                break;
+            }
+        }
+    }
+    if(haveAssigned) {
+        return -1;
+    } else {
+        return localSavings+belowSavings;
+    }
+}
+
+/* helper function for finding compaction opportunities */
+static void
+compactToUnicodeHelper(UCMStates *states,
+                       uint16_t *unicodeCodeUnits,
+                       _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks) {
+    int32_t state, savings;
+
+    /* for each initial state */
+    for(state=0; state<states->countStates; ++state) {
+        if((states->stateFlags[state]&0xf)==MBCS_STATE_FLAG_DIRECT) {
+            savings=findUnassigned(states,
+                        unicodeCodeUnits,
+                        toUFallbacks, countToUFallbacks,
+                        state, 0, 0);
+            if(savings>0) {
+                printf("    all-unassigned sequences from initial state %ld use %ld bytes\n",
+                    (long)state, (long)savings);
+            }
+        }
+    }
+}
+
+static int32_t
+compareFallbacks(const void *context, const void *fb1, const void *fb2) {
+    return ((const _MBCSToUFallback *)fb1)->offset-((const _MBCSToUFallback *)fb2)->offset;
+}
+
+U_CAPI void U_EXPORT2
+ucm_optimizeStates(UCMStates *states,
+                   uint16_t **pUnicodeCodeUnits,
+                   _MBCSToUFallback *toUFallbacks, int32_t countToUFallbacks,
+                   UBool verbose) {
+    UErrorCode errorCode;
+    int32_t state, cell, entry;
+
+    /* test each state table entry */
+    for(state=0; state<states->countStates; ++state) {
+        for(cell=0; cell<256; ++cell) {
+            entry=states->stateTable[state][cell];
+            /*
+             * if the entry is a final one with an MBCS_STATE_VALID_DIRECT_16 action code
+             * and the code point is "unassigned" (0xfffe), then change it to
+             * the "unassigned" action code with bits 26..23 set to zero and U+fffe.
+             */
+            if(MBCS_ENTRY_SET_STATE(entry, 0)==MBCS_ENTRY_FINAL(0, MBCS_STATE_VALID_DIRECT_16, 0xfffe)) {
+                states->stateTable[state][cell]=MBCS_ENTRY_FINAL_SET_ACTION(entry, MBCS_STATE_UNASSIGNED);
+            }
+        }
+    }
+
+    /* try to compact the toUnicode tables */
+    if(states->maxCharLength==2) {
+        compactToUnicode2(states, pUnicodeCodeUnits, toUFallbacks, countToUFallbacks, verbose);
+    } else if(states->maxCharLength>2) {
+        if(verbose) {
+            compactToUnicodeHelper(states, *pUnicodeCodeUnits, toUFallbacks, countToUFallbacks);
+        }
+    }
+
+    /* sort toUFallbacks */
+    /*
+     * It should be safe to sort them before compactToUnicode2() is called,
+     * because it should not change the relative order of the offset values
+     * that it adjusts, but they need to be sorted at some point, and
+     * it is safest here.
+     */
+    if(countToUFallbacks>0) {
+        errorCode=U_ZERO_ERROR; /* nothing bad will happen... */
+        uprv_sortArray(toUFallbacks, countToUFallbacks,
+                       sizeof(_MBCSToUFallback),
+                       compareFallbacks, NULL, FALSE, &errorCode);
+    }
+}
+
+/* use a complete state table ----------------------------------------------- */
+
+U_CAPI int32_t U_EXPORT2
+ucm_countChars(UCMStates *states,
+               const uint8_t *bytes, int32_t length) {
+    uint32_t offset;
+    int32_t i, entry, count;
+    uint8_t state;
+
+    offset=0;
+    i=count=0;
+    state=0;
+
+    if(states->countStates==0) {
+        fprintf(stderr, "ucm error: there is no state information!\n");
+        return -1;
+    }
+
+    /* for SI/SO (like EBCDIC-stateful), double-byte sequences start in state 1 */
+    if(length==2 && states->outputType==MBCS_OUTPUT_2_SISO) {
+        state=1;
+    }
+
+    /*
+     * Walk down the state table like in conversion,
+     * much like getNextUChar().
+     * We assume that c<=0x10ffff.
+     */
+    for(i=0; i<length; ++i) {
+        entry=states->stateTable[state][bytes[i]];
+        if(MBCS_ENTRY_IS_TRANSITION(entry)) {
+            state=(uint8_t)MBCS_ENTRY_TRANSITION_STATE(entry);
+            offset+=MBCS_ENTRY_TRANSITION_OFFSET(entry);
+        } else {
+            switch(MBCS_ENTRY_FINAL_ACTION(entry)) {
+            case MBCS_STATE_ILLEGAL:
+                fprintf(stderr, "ucm error: byte sequence ends in illegal state\n");
+                return -1;
+            case MBCS_STATE_CHANGE_ONLY:
+                fprintf(stderr, "ucm error: byte sequence ends in state-change-only\n");
+                return -1;
+            case MBCS_STATE_UNASSIGNED:
+            case MBCS_STATE_FALLBACK_DIRECT_16:
+            case MBCS_STATE_VALID_DIRECT_16:
+            case MBCS_STATE_FALLBACK_DIRECT_20:
+            case MBCS_STATE_VALID_DIRECT_20:
+            case MBCS_STATE_VALID_16:
+            case MBCS_STATE_VALID_16_PAIR:
+                /* count a complete character and prepare for a new one */
+                ++count;
+                state=(uint8_t)MBCS_ENTRY_FINAL_STATE(entry);
+                offset=0;
+                break;
+            default:
+                /* reserved, must never occur */
+                fprintf(stderr, "ucm error: byte sequence reached reserved action code, entry: 0x%02lx\n", (unsigned long)entry);
+                return -1;
+            }
+        }
+    }
+
+    if(offset!=0) {
+        fprintf(stderr, "ucm error: byte sequence too short, ends in non-final state %hu\n", state);
+        return -1;
+    }
+
+    /*
+     * for SI/SO (like EBCDIC-stateful), multiple-character results
+     * must consist of only double-byte sequences
+     */
+    if(count>1 && states->outputType==MBCS_OUTPUT_2_SISO && length!=2*count) {
+        fprintf(stderr, "ucm error: SI/SO (like EBCDIC-stateful) result with %d characters does not contain all DBCS\n", (int)count);
+        return -1;
+    }
+
+    return count;
+}
+#endif
+