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