icuSources/common/ucnv_ext.h

   1 /*
   2 ******************************************************************************
   3 *
   4 *   Copyright (C) 2003-2004, 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 U_CFUNC void
 386 ucnv_extGetUnicodeSet(const UConverterSharedData *sharedData,
 387                       USetAdder *sa,
 388                       UConverterUnicodeSet which,
 389                       UErrorCode *pErrorCode);
 390
 391 /* toUnicode helpers -------------------------------------------------------- */
 392
 393 #define UCNV_EXT_TO_U_BYTE_SHIFT 24
 394 #define UCNV_EXT_TO_U_VALUE_MASK 0xffffff
 395 #define UCNV_EXT_TO_U_MIN_CODE_POINT 0x1f0000
 396 #define UCNV_EXT_TO_U_MAX_CODE_POINT 0x2fffff
 397 #define UCNV_EXT_TO_U_ROUNDTRIP_FLAG ((uint32_t)1<<23)
 398 #define UCNV_EXT_TO_U_INDEX_MASK 0x3ffff
 399 #define UCNV_EXT_TO_U_LENGTH_SHIFT 18
 400 #define UCNV_EXT_TO_U_LENGTH_OFFSET 12
 401
 402 /* maximum number of indexed UChars */
 403 #define UCNV_EXT_MAX_UCHARS 19
 404
 405 #define UCNV_EXT_TO_U_MAKE_WORD(byte, value) (((uint32_t)(byte)<<UCNV_EXT_TO_U_BYTE_SHIFT)|(value))
 406
 407 #define UCNV_EXT_TO_U_GET_BYTE(word) ((word)>>UCNV_EXT_TO_U_BYTE_SHIFT)
 408 #define UCNV_EXT_TO_U_GET_VALUE(word) ((word)&UCNV_EXT_TO_U_VALUE_MASK)
 409
 410 #define UCNV_EXT_TO_U_IS_PARTIAL(value) ((value)<UCNV_EXT_TO_U_MIN_CODE_POINT)
 411 #define UCNV_EXT_TO_U_GET_PARTIAL_INDEX(value) (value)
 412
 413 #define UCNV_EXT_TO_U_IS_ROUNDTRIP(value) (((value)&UCNV_EXT_TO_U_ROUNDTRIP_FLAG)!=0)
 414 #define UCNV_EXT_TO_U_MASK_ROUNDTRIP(value) ((value)&~UCNV_EXT_TO_U_ROUNDTRIP_FLAG)
 415
 416 /* use after masking off the roundtrip flag */
 417 #define UCNV_EXT_TO_U_IS_CODE_POINT(value) ((value)<=UCNV_EXT_TO_U_MAX_CODE_POINT)
 418 #define UCNV_EXT_TO_U_GET_CODE_POINT(value) ((value)-UCNV_EXT_TO_U_MIN_CODE_POINT)
 419
 420 #define UCNV_EXT_TO_U_GET_INDEX(value) ((value)&UCNV_EXT_TO_U_INDEX_MASK)
 421 #define UCNV_EXT_TO_U_GET_LENGTH(value) (((value)>>UCNV_EXT_TO_U_LENGTH_SHIFT)-UCNV_EXT_TO_U_LENGTH_OFFSET)
 422
 423 /* fromUnicode helpers ------------------------------------------------------ */
 424
 425 /* most trie constants are shared with ucnvmbcs.h */
 426
 427 /* see similar utrie.h UTRIE_INDEX_SHIFT and UTRIE_DATA_GRANULARITY */
 428 #define UCNV_EXT_STAGE_2_LEFT_SHIFT 2
 429 #define UCNV_EXT_STAGE_3_GRANULARITY 4
 430
 431 /* trie access, returns the stage 3 value=index to stage 3b; s1Index=c>>10 */
 432 #define UCNV_EXT_FROM_U(stage12, stage3, s1Index, c) \
 433     (stage3)[ ((int32_t)(stage12)[ (stage12)[s1Index] +(((c)>>4)&0x3f) ]<<UCNV_EXT_STAGE_2_LEFT_SHIFT) +((c)&0xf) ]
 434
 435 #define UCNV_EXT_FROM_U_LENGTH_SHIFT 24
 436 #define UCNV_EXT_FROM_U_ROUNDTRIP_FLAG ((uint32_t)1<<31)
 437 #define UCNV_EXT_FROM_U_RESERVED_MASK 0x60000000
 438 #define UCNV_EXT_FROM_U_DATA_MASK 0xffffff
 439
 440 /* special value for "no mapping" to <subchar1> (impossible roundtrip to 0 bytes, value 01) */
 441 #define UCNV_EXT_FROM_U_SUBCHAR1 0x80000001
 442
 443 /* at most 3 bytes in the lower part of the value */
 444 #define UCNV_EXT_FROM_U_MAX_DIRECT_LENGTH 3
 445
 446 /* maximum number of indexed bytes */
 447 #define UCNV_EXT_MAX_BYTES 0x1f
 448
 449 #define UCNV_EXT_FROM_U_IS_PARTIAL(value) (((value)>>UCNV_EXT_FROM_U_LENGTH_SHIFT)==0)
 450 #define UCNV_EXT_FROM_U_GET_PARTIAL_INDEX(value) (value)
 451
 452 #define UCNV_EXT_FROM_U_IS_ROUNDTRIP(value) (((value)&UCNV_EXT_FROM_U_ROUNDTRIP_FLAG)!=0)
 453 #define UCNV_EXT_FROM_U_MASK_ROUNDTRIP(value) ((value)&~UCNV_EXT_FROM_U_ROUNDTRIP_FLAG)
 454
 455 /* use after masking off the roundtrip flag */
 456 #define UCNV_EXT_FROM_U_GET_LENGTH(value) (int32_t)(((value)>>UCNV_EXT_FROM_U_LENGTH_SHIFT)&UCNV_EXT_MAX_BYTES)
 457
 458 /* get bytes or bytes index */
 459 #define UCNV_EXT_FROM_U_GET_DATA(value) ((value)&UCNV_EXT_FROM_U_DATA_MASK)
 460
 461 #endif
 462
 463 #endif