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