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