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