1 /* 2 ****************************************************************************** 3 * 4 * Copyright (C) 2003-2007, International Business Machines 5 * Corporation and others. All Rights Reserved. 6 * 7 ****************************************************************************** 8 * file name: ucnv_ext.h 9 * encoding: US-ASCII 10 * tab size: 8 (not used) 11 * indentation:4 12 * 13 * created on: 2003jun13 14 * created by: Markus W. Scherer 15 * 16 * Conversion extensions 17 */ 18 19 #ifndef __UCNV_EXT_H__ 20 #define __UCNV_EXT_H__ 21 22 #include "unicode/utypes.h" 23 24 #if !UCONFIG_NO_CONVERSION 25 26 #include "unicode/ucnv.h" 27 #include "ucnv_cnv.h" 28 29 /* 30 * See icuhtml/design/conversion/conversion_extensions.html 31 * 32 * Conversion extensions serve two purposes: 33 * 1. They support m:n mappings. 34 * 2. They support extension-only conversion files that are used together 35 * with the regular conversion data in base files. 36 * 37 * A base file may contain an extension table (explicitly requested or 38 * implicitly generated for m:n mappings), but its extension table is not 39 * used when an extension-only file is used. 40 * 41 * It is an error if a base file contains any regular (not extension) mapping 42 * from the same sequence as a mapping in the extension file 43 * because the base mapping would hide the extension mapping. 44 * 45 * 46 * Data for conversion extensions: 47 * 48 * One set of data structures per conversion direction (to/from Unicode). 49 * The data structures are sorted by input units to allow for binary search. 50 * Input sequences of more than one unit are handled like contraction tables 51 * in collation: 52 * The lookup value of a unit points to another table that is to be searched 53 * for the next unit, recursively. 54 * 55 * For conversion from Unicode, the initial code point is looked up in 56 * a 3-stage trie for speed, 57 * with an additional table of unique results to save space. 58 * 59 * Long output strings are stored in separate arrays, with length and index 60 * in the lookup tables. 61 * Output results also include a flag distinguishing roundtrip from 62 * (reverse) fallback mappings. 63 * 64 * Input Unicode strings must not begin or end with unpaired surrogates 65 * to avoid problems with matches on parts of surrogate pairs. 66 * 67 * Mappings from multiple characters (code points or codepage state 68 * table sequences) must be searched preferring the longest match. 69 * For this to work and be efficient, the variable-width table must contain 70 * all mappings that contain prefixes of the multiple characters. 71 * If an extension table is built on top of a base table in another file 72 * and a base table entry is a prefix of a multi-character mapping, then 73 * this is an error. 74 * 75 * 76 * Implementation note: 77 * 78 * Currently, the parser and several checks in the code limit the number 79 * of UChars or bytes in a mapping to 80 * UCNV_EXT_MAX_UCHARS and UCNV_EXT_MAX_BYTES, respectively, 81 * which are output value limits in the data structure. 82 * 83 * For input, this is not strictly necessary - it is a hard limit only for the 84 * buffers in UConverter that are used to store partial matches. 85 * 86 * Input sequences could otherwise be arbitrarily long if partial matches 87 * need not be stored (i.e., if a sequence does not span several buffers with too 88 * many units before the last buffer), although then results would differ 89 * depending on whether partial matches exceed the limits or not, 90 * which depends on the pattern of buffer sizes. 91 * 92 * 93 * Data structure: 94 * 95 * int32_t indexes[>=32]; 96 * 97 * Array of indexes and lengths etc. The length of the array is at least 32. 98 * The actual length is stored in indexes[0] to be forward compatible. 99 * 100 * Each index to another array is the number of bytes from indexes[]. 101 * Each length of an array is the number of array base units in that array. 102 * 103 * Some of the structures may not be present, in which case their indexes 104 * and lengths are 0. 105 * 106 * Usage of indexes[i]: 107 * [0] length of indexes[] 108 * 109 * // to Unicode table 110 * [1] index of toUTable[] (array of uint32_t) 111 * [2] length of toUTable[] 112 * [3] index of toUUChars[] (array of UChar) 113 * [4] length of toUUChars[] 114 * 115 * // from Unicode table, not for the initial code point 116 * [5] index of fromUTableUChars[] (array of UChar) 117 * [6] index of fromUTableValues[] (array of uint32_t) 118 * [7] length of fromUTableUChars[] and fromUTableValues[] 119 * [8] index of fromUBytes[] (array of char) 120 * [9] length of fromUBytes[] 121 * 122 * // from Unicode trie for initial-code point lookup 123 * [10] index of fromUStage12[] (combined array of uint16_t for stages 1 & 2) 124 * [11] length of stage 1 portion of fromUStage12[] 125 * [12] length of fromUStage12[] 126 * [13] index of fromUStage3[] (array of uint16_t indexes into fromUStage3b[]) 127 * [14] length of fromUStage3[] 128 * [15] index of fromUStage3b[] (array of uint32_t like fromUTableValues[]) 129 * [16] length of fromUStage3b[] 130 * 131 * [17] Bit field containing numbers of bytes: 132 * 31..24 reserved, 0 133 * 23..16 maximum input bytes 134 * 15.. 8 maximum output bytes 135 * 7.. 0 maximum bytes per UChar 136 * 137 * [18] Bit field containing numbers of UChars: 138 * 31..24 reserved, 0 139 * 23..16 maximum input UChars 140 * 15.. 8 maximum output UChars 141 * 7.. 0 maximum UChars per byte 142 * 143 * [19] Bit field containing flags: 144 * (extension table unicodeMask) 145 * 1 UCNV_HAS_SURROGATES flag for the extension table 146 * 0 UCNV_HAS_SUPPLEMENTARY flag for the extension table 147 * 148 * [20]..[30] reserved, 0 149 * [31] number of bytes for the entire extension structure 150 * [>31] reserved; there are indexes[0] indexes 151 * 152 * 153 * uint32_t toUTable[]; 154 * 155 * Array of byte/value pairs for lookups for toUnicode conversion. 156 * The array is partitioned into sections like collation contraction tables. 157 * Each section contains one word with the number of following words and 158 * a default value for when the lookup in this section yields no match. 159 * 160 * A section is sorted in ascending order of input bytes, 161 * allowing for fast linear or binary searches. 162 * The builder may store entries for a contiguous range of byte values 163 * (compare difference between the first and last one with count), 164 * which then allows for direct array access. 165 * The builder should always do this for the initial table section. 166 * 167 * Entries may have 0 values, see below. 168 * No two entries in a section have the same byte values. 169 * 170 * Each uint32_t contains an input byte value in bits 31..24 and the 171 * corresponding lookup value in bits 23..0. 172 * Interpret the value as follows: 173 * if(value==0) { 174 * no match, see below 175 * } else if(value<0x1f0000) { 176 * partial match - use value as index to the next toUTable section 177 * and match the next unit; (value indexes toUTable[value]) 178 * } else { 179 * if(bit 23 set) { 180 * roundtrip; 181 * } else { 182 * fallback; 183 * } 184 * unset value bit 23; 185 * if(value<=0x2fffff) { 186 * (value-0x1f0000) is a code point; (BMP: value<=0x1fffff) 187 * } else { 188 * bits 17..0 (value&0x3ffff) is an index to 189 * the result UChars in toUUChars[]; (0 indexes toUUChars[0]) 190 * length of the result=((value>>18)-12); (length=0..19) 191 * } 192 * } 193 * 194 * The first word in a section contains the number of following words in the 195 * input byte position (bits 31..24, number=1..0xff). 196 * The value of the initial word is used when the current byte is not found 197 * in this section. 198 * If the value is not 0, then it represents a result as above. 199 * If the value is 0, then the search has to return a shorter match with an 200 * earlier default value as the result, or result in "unmappable" even for the 201 * initial bytes. 202 * If the value is 0 for the initial toUTable entry, then the initial byte 203 * does not start any mapping input. 204 * 205 * 206 * UChar toUUChars[]; 207 * 208 * Contains toUnicode mapping results, stored as sequences of UChars. 209 * Indexes and lengths stored in the toUTable[]. 210 * 211 * 212 * UChar fromUTableUChars[]; 213 * uint32_t fromUTableValues[]; 214 * 215 * The fromUTable is split into two arrays, but works otherwise much like 216 * the toUTable. The array is partitioned into sections like collation 217 * contraction tables and toUTable. 218 * A row in the table consists of same-index entries in fromUTableUChars[] 219 * and fromUTableValues[]. 220 * 221 * Interpret a value as follows: 222 * if(value==0) { 223 * no match, see below 224 * } else if(value<=0xffffff) { (bits 31..24 are 0) 225 * partial match - use value as index to the next fromUTable section 226 * and match the next unit; (value indexes fromUTable[value]) 227 * } else { 228 * if(value==0x80000001) { 229 * return no mapping, but request for <subchar1>; 230 * } 231 * if(bit 31 set) { 232 * roundtrip; 233 * } else { 234 * fallback; 235 * } 236 * // bits 30..29 reserved, 0 237 * length=(value>>24)&0x1f; (bits 28..24) 238 * if(length==1..3) { 239 * bits 23..0 contain 1..3 bytes, padded with 00s on the left; 240 * } else { 241 * bits 23..0 (value&0xffffff) is an index to 242 * the result bytes in fromUBytes[]; (0 indexes fromUBytes[0]) 243 * } 244 * } 245 * 246 * The first pair in a section contains the number of following pairs in the 247 * UChar position (16 bits, number=1..0xffff). 248 * The value of the initial pair is used when the current UChar is not found 249 * in this section. 250 * If the value is not 0, then it represents a result as above. 251 * If the value is 0, then the search has to return a shorter match with an 252 * earlier default value as the result, or result in "unmappable" even for the 253 * initial UChars. 254 * 255 * If the from Unicode trie is present, then the from Unicode search tables 256 * are not used for initial code points. 257 * In this case, the first entries (index 0) in the tables are not used 258 * (reserved, set to 0) because a value of 0 is used in trie results 259 * to indicate no mapping. 260 * 261 * 262 * uint16_t fromUStage12[]; 263 * 264 * Stages 1 & 2 of a trie that maps an initial code point. 265 * Indexes in stage 1 are all offset by the length of stage 1 so that the 266 * same array pointer can be used for both stages. 267 * If (c>>10)>=(length of stage 1) then c does not start any mapping. 268 * Same bit distribution as for regular conversion tries. 269 * 270 * 271 * uint16_t fromUStage3[]; 272 * uint32_t fromUStage3b[]; 273 * 274 * Stage 3 of the trie. The first array simply contains indexes to the second, 275 * which contains words in the same format as fromUTableValues[]. 276 * Use a stage 3 granularity of 4, which allows for 256k stage 3 entries, 277 * and 16-bit entries in stage 3 allow for 64k stage 3b entries. 278 * The stage 3 granularity means that the stage 2 entry needs to be left-shifted. 279 * 280 * Two arrays are used because it is expected that more than half of the stage 3 281 * entries will be zero. The 16-bit index stage 3 array saves space even 282 * considering storing a total of 6 bytes per non-zero entry in both arrays 283 * together. 284 * Using a stage 3 granularity of >1 diminishes the compactability in that stage 285 * but provides a larger effective addressing space in stage 2. 286 * All but the final result stage use 16-bit entries to save space. 287 * 288 * fromUStage3b[] contains a zero for "no mapping" at its index 0, 289 * and may contain UCNV_EXT_FROM_U_SUBCHAR1 at index 1 for "<subchar1> SUB mapping" 290 * (i.e., "no mapping" with preference for <subchar1> rather than <subchar>), 291 * and all other items are unique non-zero results. 292 * 293 * The default value of a fromUTableValues[] section that is referenced 294 * _directly_ from a fromUStage3b[] item may also be UCNV_EXT_FROM_U_SUBCHAR1, 295 * but this value must not occur anywhere else in fromUTableValues[] 296 * because "no mapping" is always a property of a single code point, 297 * never of multiple. 298 * 299 * 300 * char fromUBytes[]; 301 * 302 * Contains fromUnicode mapping results, stored as sequences of chars. 303 * Indexes and lengths stored in the fromUTableValues[]. 304 */ 305 enum { 306 UCNV_EXT_INDEXES_LENGTH, /* 0 */ 307 308 UCNV_EXT_TO_U_INDEX, /* 1 */ 309 UCNV_EXT_TO_U_LENGTH, 310 UCNV_EXT_TO_U_UCHARS_INDEX, 311 UCNV_EXT_TO_U_UCHARS_LENGTH, 312 313 UCNV_EXT_FROM_U_UCHARS_INDEX, /* 5 */ 314 UCNV_EXT_FROM_U_VALUES_INDEX, 315 UCNV_EXT_FROM_U_LENGTH, 316 UCNV_EXT_FROM_U_BYTES_INDEX, 317 UCNV_EXT_FROM_U_BYTES_LENGTH, 318 319 UCNV_EXT_FROM_U_STAGE_12_INDEX, /* 10 */ 320 UCNV_EXT_FROM_U_STAGE_1_LENGTH, 321 UCNV_EXT_FROM_U_STAGE_12_LENGTH, 322 UCNV_EXT_FROM_U_STAGE_3_INDEX, 323 UCNV_EXT_FROM_U_STAGE_3_LENGTH, 324 UCNV_EXT_FROM_U_STAGE_3B_INDEX, 325 UCNV_EXT_FROM_U_STAGE_3B_LENGTH, 326 327 UCNV_EXT_COUNT_BYTES, /* 17 */ 328 UCNV_EXT_COUNT_UCHARS, 329 UCNV_EXT_FLAGS, 330 331 UCNV_EXT_RESERVED_INDEX, /* 20, moves with additional indexes */ 332 333 UCNV_EXT_SIZE=31, 334 UCNV_EXT_INDEXES_MIN_LENGTH=32 335 }; 336 337 /* get the pointer to an extension array from indexes[index] */ 338 #define UCNV_EXT_ARRAY(indexes, index, itemType) \ 339 ((const itemType *)((const char *)(indexes)+(indexes)[index])) 340 341 #define UCNV_GET_MAX_BYTES_PER_UCHAR(indexes) \ 342 ((indexes)[UCNV_EXT_COUNT_BYTES]&0xff) 343 344 /* internal API ------------------------------------------------------------- */ 345 346 U_CFUNC UBool 347 ucnv_extInitialMatchToU(UConverter *cnv, const int32_t *cx, 348 int32_t firstLength, 349 const char **src, const char *srcLimit, 350 UChar **target, const UChar *targetLimit, 351 int32_t **offsets, int32_t srcIndex, 352 UBool flush, 353 UErrorCode *pErrorCode); 354 355 U_CFUNC UChar32 356 ucnv_extSimpleMatchToU(const int32_t *cx, 357 const char *source, int32_t length, 358 UBool useFallback); 359 360 U_CFUNC void 361 ucnv_extContinueMatchToU(UConverter *cnv, 362 UConverterToUnicodeArgs *pArgs, int32_t srcIndex, 363 UErrorCode *pErrorCode); 364 365 366 U_CFUNC UBool 367 ucnv_extInitialMatchFromU(UConverter *cnv, const int32_t *cx, 368 UChar32 cp, 369 const UChar **src, const UChar *srcLimit, 370 char **target, const char *targetLimit, 371 int32_t **offsets, int32_t srcIndex, 372 UBool flush, 373 UErrorCode *pErrorCode); 374 375 U_CFUNC int32_t 376 ucnv_extSimpleMatchFromU(const int32_t *cx, 377 UChar32 cp, uint32_t *pValue, 378 UBool useFallback); 379 380 U_CFUNC void 381 ucnv_extContinueMatchFromU(UConverter *cnv, 382 UConverterFromUnicodeArgs *pArgs, int32_t srcIndex, 383 UErrorCode *pErrorCode); 384 385 /* 386 * Add code points and strings to the set according to the extension mappings. 387 * Limitation on the UConverterSetFilter: 388 * The filters currently assume that they are used with 1:1 mappings. 389 * They only apply to single input code points, and then they pass through 390 * only mappings with single-charset-code results. 391 * For example, the Shift-JIS filter only works for 2-byte results and tests 392 * that those 2 bytes are in the JIS X 0208 range of Shift-JIS. 393 */ 394 U_CFUNC void 395 ucnv_extGetUnicodeSet(const UConverterSharedData *sharedData, 396 const USetAdder *sa, 397 UConverterUnicodeSet which, 398 UConverterSetFilter filter, 399 UErrorCode *pErrorCode); 400 401 /* toUnicode helpers -------------------------------------------------------- */ 402 403 #define UCNV_EXT_TO_U_BYTE_SHIFT 24 404 #define UCNV_EXT_TO_U_VALUE_MASK 0xffffff 405 #define UCNV_EXT_TO_U_MIN_CODE_POINT 0x1f0000 406 #define UCNV_EXT_TO_U_MAX_CODE_POINT 0x2fffff 407 #define UCNV_EXT_TO_U_ROUNDTRIP_FLAG ((uint32_t)1<<23) 408 #define UCNV_EXT_TO_U_INDEX_MASK 0x3ffff 409 #define UCNV_EXT_TO_U_LENGTH_SHIFT 18 410 #define UCNV_EXT_TO_U_LENGTH_OFFSET 12 411 412 /* maximum number of indexed UChars */ 413 #define UCNV_EXT_MAX_UCHARS 19 414 415 #define UCNV_EXT_TO_U_MAKE_WORD(byte, value) (((uint32_t)(byte)<<UCNV_EXT_TO_U_BYTE_SHIFT)|(value)) 416 417 #define UCNV_EXT_TO_U_GET_BYTE(word) ((word)>>UCNV_EXT_TO_U_BYTE_SHIFT) 418 #define UCNV_EXT_TO_U_GET_VALUE(word) ((word)&UCNV_EXT_TO_U_VALUE_MASK) 419 420 #define UCNV_EXT_TO_U_IS_PARTIAL(value) ((value)<UCNV_EXT_TO_U_MIN_CODE_POINT) 421 #define UCNV_EXT_TO_U_GET_PARTIAL_INDEX(value) (value) 422 423 #define UCNV_EXT_TO_U_IS_ROUNDTRIP(value) (((value)&UCNV_EXT_TO_U_ROUNDTRIP_FLAG)!=0) 424 #define UCNV_EXT_TO_U_MASK_ROUNDTRIP(value) ((value)&~UCNV_EXT_TO_U_ROUNDTRIP_FLAG) 425 426 /* use after masking off the roundtrip flag */ 427 #define UCNV_EXT_TO_U_IS_CODE_POINT(value) ((value)<=UCNV_EXT_TO_U_MAX_CODE_POINT) 428 #define UCNV_EXT_TO_U_GET_CODE_POINT(value) ((value)-UCNV_EXT_TO_U_MIN_CODE_POINT) 429 430 #define UCNV_EXT_TO_U_GET_INDEX(value) ((value)&UCNV_EXT_TO_U_INDEX_MASK) 431 #define UCNV_EXT_TO_U_GET_LENGTH(value) (((value)>>UCNV_EXT_TO_U_LENGTH_SHIFT)-UCNV_EXT_TO_U_LENGTH_OFFSET) 432 433 /* fromUnicode helpers ------------------------------------------------------ */ 434 435 /* most trie constants are shared with ucnvmbcs.h */ 436 437 /* see similar utrie.h UTRIE_INDEX_SHIFT and UTRIE_DATA_GRANULARITY */ 438 #define UCNV_EXT_STAGE_2_LEFT_SHIFT 2 439 #define UCNV_EXT_STAGE_3_GRANULARITY 4 440 441 /* trie access, returns the stage 3 value=index to stage 3b; s1Index=c>>10 */ 442 #define UCNV_EXT_FROM_U(stage12, stage3, s1Index, c) \ 443 (stage3)[ ((int32_t)(stage12)[ (stage12)[s1Index] +(((c)>>4)&0x3f) ]<<UCNV_EXT_STAGE_2_LEFT_SHIFT) +((c)&0xf) ] 444 445 #define UCNV_EXT_FROM_U_LENGTH_SHIFT 24 446 #define UCNV_EXT_FROM_U_ROUNDTRIP_FLAG ((uint32_t)1<<31) 447 #define UCNV_EXT_FROM_U_RESERVED_MASK 0x60000000 448 #define UCNV_EXT_FROM_U_DATA_MASK 0xffffff 449 450 /* special value for "no mapping" to <subchar1> (impossible roundtrip to 0 bytes, value 01) */ 451 #define UCNV_EXT_FROM_U_SUBCHAR1 0x80000001 452 453 /* at most 3 bytes in the lower part of the value */ 454 #define UCNV_EXT_FROM_U_MAX_DIRECT_LENGTH 3 455 456 /* maximum number of indexed bytes */ 457 #define UCNV_EXT_MAX_BYTES 0x1f 458 459 #define UCNV_EXT_FROM_U_IS_PARTIAL(value) (((value)>>UCNV_EXT_FROM_U_LENGTH_SHIFT)==0) 460 #define UCNV_EXT_FROM_U_GET_PARTIAL_INDEX(value) (value) 461 462 #define UCNV_EXT_FROM_U_IS_ROUNDTRIP(value) (((value)&UCNV_EXT_FROM_U_ROUNDTRIP_FLAG)!=0) 463 #define UCNV_EXT_FROM_U_MASK_ROUNDTRIP(value) ((value)&~UCNV_EXT_FROM_U_ROUNDTRIP_FLAG) 464 465 /* get length; masks away all other bits */ 466 #define UCNV_EXT_FROM_U_GET_LENGTH(value) (int32_t)(((value)>>UCNV_EXT_FROM_U_LENGTH_SHIFT)&UCNV_EXT_MAX_BYTES) 467 468 /* get bytes or bytes index */ 469 #define UCNV_EXT_FROM_U_GET_DATA(value) ((value)&UCNV_EXT_FROM_U_DATA_MASK) 470 471 #endif 472 473 #endif 474