1 /*
2 *******************************************************************************
3 *
4 *   Copyright (C) 2003-2012, 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 *
parseState(const char * s,int32_t state[256],uint32_t * pFlags)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
ucm_addState(UCMStates * states,const char * s)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
ucm_parseHeaderLine(UCMFile * ucm,char * line,char ** pKey,char ** pValue)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
sumUpStates(UCMStates * states)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
ucm_processStates(UCMStates * states,UBool ignoreSISOCheck)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
ucm_findFallback(_MBCSToUFallback * toUFallbacks,int32_t countToUFallbacks,uint32_t offset)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
compactToUnicode2(UCMStates * states,uint16_t ** pUnicodeCodeUnits,_MBCSToUFallback * toUFallbacks,int32_t countToUFallbacks,UBool verbose)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
findUnassigned(UCMStates * states,uint16_t * unicodeCodeUnits,_MBCSToUFallback * toUFallbacks,int32_t countToUFallbacks,int32_t state,int32_t offset,uint32_t b)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
compactToUnicodeHelper(UCMStates * states,uint16_t * unicodeCodeUnits,_MBCSToUFallback * toUFallbacks,int32_t countToUFallbacks)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
compareFallbacks(const void * context,const void * fb1,const void * fb2)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
ucm_optimizeStates(UCMStates * states,uint16_t ** pUnicodeCodeUnits,_MBCSToUFallback * toUFallbacks,int32_t countToUFallbacks,UBool verbose)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
ucm_countChars(UCMStates * states,const uint8_t * bytes,int32_t length)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     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 %u\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