]> git.saurik.com Git - apple/icu.git/blame - icuSources/tools/makeconv/gencnvex.c
ICU-8.11.4.tar.gz
[apple/icu.git] / icuSources / tools / makeconv / gencnvex.c
CommitLineData
374ca955
A
1/*
2*******************************************************************************
3*
73c04bcf 4* Copyright (C) 2003-2006, International Business Machines
374ca955
A
5* Corporation and others. All Rights Reserved.
6*
7*******************************************************************************
8* file name: gencnvex.c
9* encoding: US-ASCII
10* tab size: 8 (not used)
11* indentation:4
12*
13* created on: 2003oct12
14* created by: Markus W. Scherer
15*/
16
17#include <stdio.h>
18#include "unicode/utypes.h"
19#include "unicode/ustring.h"
20#include "cstring.h"
21#include "cmemory.h"
22#include "ucnv_cnv.h"
23#include "ucnvmbcs.h"
24#include "toolutil.h"
25#include "unewdata.h"
26#include "ucm.h"
27#include "makeconv.h"
28#include "genmbcs.h"
29
30#define LENGTHOF(array) (int32_t)(sizeof(array)/sizeof((array)[0]))
31
73c04bcf 32
374ca955
A
33static void
34CnvExtClose(NewConverter *cnvData);
35
36static UBool
37CnvExtIsValid(NewConverter *cnvData,
38 const uint8_t *bytes, int32_t length);
39
40static UBool
41CnvExtAddTable(NewConverter *cnvData, UCMTable *table, UConverterStaticData *staticData);
42
43static uint32_t
44CnvExtWrite(NewConverter *cnvData, const UConverterStaticData *staticData,
45 UNewDataMemory *pData, int32_t tableType);
46
47typedef struct CnvExtData {
48 NewConverter newConverter;
49
50 UCMFile *ucm;
51
52 /* toUnicode (state table in ucm->states) */
53 UToolMemory *toUTable, *toUUChars;
54
55 /* fromUnicode */
56 UToolMemory *fromUTableUChars, *fromUTableValues, *fromUBytes;
57
58 uint16_t stage1[MBCS_STAGE_1_SIZE];
59 uint16_t stage2[MBCS_STAGE_2_SIZE];
60 uint16_t stage3[0x10000<<UCNV_EXT_STAGE_2_LEFT_SHIFT]; /* 0x10000 because of 16-bit stage 2/3 indexes */
61 uint32_t stage3b[0x10000];
62
63 int32_t stage1Top, stage2Top, stage3Top, stage3bTop;
64
65 /* for stage3 compaction of <subchar1> |2 mappings */
66 uint16_t stage3Sub1Block;
67
68 /* statistics */
69 int32_t
70 maxInBytes, maxOutBytes, maxBytesPerUChar,
71 maxInUChars, maxOutUChars, maxUCharsPerByte;
72} CnvExtData;
73
74NewConverter *
75CnvExtOpen(UCMFile *ucm) {
76 CnvExtData *extData;
77
78 extData=(CnvExtData *)uprv_malloc(sizeof(CnvExtData));
79 if(extData!=NULL) {
80 uprv_memset(extData, 0, sizeof(CnvExtData));
81
82 extData->ucm=ucm; /* aliased, not owned */
83
84 extData->newConverter.close=CnvExtClose;
85 extData->newConverter.isValid=CnvExtIsValid;
86 extData->newConverter.addTable=CnvExtAddTable;
87 extData->newConverter.write=CnvExtWrite;
88 }
89 return &extData->newConverter;
90}
91
92static void
93CnvExtClose(NewConverter *cnvData) {
94 CnvExtData *extData=(CnvExtData *)cnvData;
95 if(extData!=NULL) {
96 utm_close(extData->toUTable);
97 utm_close(extData->toUUChars);
98 utm_close(extData->fromUTableUChars);
99 utm_close(extData->fromUTableValues);
100 utm_close(extData->fromUBytes);
101 }
102}
103
104/* we do not expect this to be called */
105static UBool
106CnvExtIsValid(NewConverter *cnvData,
107 const uint8_t *bytes, int32_t length) {
108 return FALSE;
109}
110
111static uint32_t
112CnvExtWrite(NewConverter *cnvData, const UConverterStaticData *staticData,
113 UNewDataMemory *pData, int32_t tableType) {
114 CnvExtData *extData=(CnvExtData *)cnvData;
115 int32_t length, top, headerSize;
116
117 int32_t indexes[UCNV_EXT_INDEXES_MIN_LENGTH]={ 0 };
118
119 if(tableType&TABLE_BASE) {
120 headerSize=0;
121 } else {
122 _MBCSHeader header={ { 0, 0, 0, 0 }, 0, 0, 0, 0, 0, 0, 0 };
123
124 /* write the header and base table name for an extension-only table */
125 length=(int32_t)uprv_strlen(extData->ucm->baseName)+1;
126 while(length&3) {
127 /* add padding */
128 extData->ucm->baseName[length++]=0;
129 }
130
131 headerSize=sizeof(header)+length;
132
133 /* fill the header */
134 header.version[0]=4;
135 header.version[1]=2;
136 header.flags=(uint32_t)((headerSize<<8)|MBCS_OUTPUT_EXT_ONLY);
137
138 /* write the header and the base table name */
139 udata_writeBlock(pData, &header, sizeof(header));
140 udata_writeBlock(pData, extData->ucm->baseName, length);
141 }
142
143 /* fill indexes[] - offsets/indexes are in units of the target array */
144 top=0;
145
146 indexes[UCNV_EXT_INDEXES_LENGTH]=length=UCNV_EXT_INDEXES_MIN_LENGTH;
147 top+=length*4;
148
149 indexes[UCNV_EXT_TO_U_INDEX]=top;
150 indexes[UCNV_EXT_TO_U_LENGTH]=length=utm_countItems(extData->toUTable);
151 top+=length*4;
152
153 indexes[UCNV_EXT_TO_U_UCHARS_INDEX]=top;
154 indexes[UCNV_EXT_TO_U_UCHARS_LENGTH]=length=utm_countItems(extData->toUUChars);
155 top+=length*2;
156
157 indexes[UCNV_EXT_FROM_U_UCHARS_INDEX]=top;
158 length=utm_countItems(extData->fromUTableUChars);
159 top+=length*2;
160
161 if(top&3) {
162 /* add padding */
163 *((UChar *)utm_alloc(extData->fromUTableUChars))=0;
164 *((uint32_t *)utm_alloc(extData->fromUTableValues))=0;
165 ++length;
166 top+=2;
167 }
168 indexes[UCNV_EXT_FROM_U_LENGTH]=length;
169
170 indexes[UCNV_EXT_FROM_U_VALUES_INDEX]=top;
171 top+=length*4;
172
173 indexes[UCNV_EXT_FROM_U_BYTES_INDEX]=top;
174 length=utm_countItems(extData->fromUBytes);
175 top+=length;
176
177 if(top&1) {
178 /* add padding */
179 *((uint8_t *)utm_alloc(extData->fromUBytes))=0;
180 ++length;
181 ++top;
182 }
183 indexes[UCNV_EXT_FROM_U_BYTES_LENGTH]=length;
184
185 indexes[UCNV_EXT_FROM_U_STAGE_12_INDEX]=top;
186 indexes[UCNV_EXT_FROM_U_STAGE_1_LENGTH]=length=extData->stage1Top;
187 indexes[UCNV_EXT_FROM_U_STAGE_12_LENGTH]=length+=extData->stage2Top;
188 top+=length*2;
189
190 indexes[UCNV_EXT_FROM_U_STAGE_3_INDEX]=top;
191 length=extData->stage3Top;
192 top+=length*2;
193
194 if(top&3) {
195 /* add padding */
196 extData->stage3[extData->stage3Top++]=0;
197 ++length;
198 top+=2;
199 }
200 indexes[UCNV_EXT_FROM_U_STAGE_3_LENGTH]=length;
201
202 indexes[UCNV_EXT_FROM_U_STAGE_3B_INDEX]=top;
203 indexes[UCNV_EXT_FROM_U_STAGE_3B_LENGTH]=length=extData->stage3bTop;
204 top+=length*4;
205
206 indexes[UCNV_EXT_SIZE]=top;
207
208 /* statistics */
209 indexes[UCNV_EXT_COUNT_BYTES]=
210 (extData->maxInBytes<<16)|
211 (extData->maxOutBytes<<8)|
212 extData->maxBytesPerUChar;
213 indexes[UCNV_EXT_COUNT_UCHARS]=
214 (extData->maxInUChars<<16)|
215 (extData->maxOutUChars<<8)|
216 extData->maxUCharsPerByte;
217
218 indexes[UCNV_EXT_FLAGS]=extData->ucm->ext->unicodeMask;
219
220 /* write the extension data */
221 udata_writeBlock(pData, indexes, sizeof(indexes));
222 udata_writeBlock(pData, utm_getStart(extData->toUTable), indexes[UCNV_EXT_TO_U_LENGTH]*4);
223 udata_writeBlock(pData, utm_getStart(extData->toUUChars), indexes[UCNV_EXT_TO_U_UCHARS_LENGTH]*2);
224
225 udata_writeBlock(pData, utm_getStart(extData->fromUTableUChars), indexes[UCNV_EXT_FROM_U_LENGTH]*2);
226 udata_writeBlock(pData, utm_getStart(extData->fromUTableValues), indexes[UCNV_EXT_FROM_U_LENGTH]*4);
227 udata_writeBlock(pData, utm_getStart(extData->fromUBytes), indexes[UCNV_EXT_FROM_U_BYTES_LENGTH]);
228
229 udata_writeBlock(pData, extData->stage1, extData->stage1Top*2);
230 udata_writeBlock(pData, extData->stage2, extData->stage2Top*2);
231 udata_writeBlock(pData, extData->stage3, extData->stage3Top*2);
232 udata_writeBlock(pData, extData->stage3b, extData->stage3bTop*4);
233
234#if 0
235 {
236 int32_t i, j;
237
238 length=extData->stage1Top;
239 printf("\nstage1[%x]:\n", length);
240
241 for(i=0; i<length; ++i) {
242 if(extData->stage1[i]!=length) {
243 printf("stage1[%04x]=%04x\n", i, extData->stage1[i]);
244 }
245 }
246
247 j=length;
248 length=extData->stage2Top;
249 printf("\nstage2[%x]:\n", length);
250
251 for(i=0; i<length; ++j, ++i) {
252 if(extData->stage2[i]!=0) {
253 printf("stage12[%04x]=%04x\n", j, extData->stage2[i]);
254 }
255 }
256
257 length=extData->stage3Top;
258 printf("\nstage3[%x]:\n", length);
259
260 for(i=0; i<length; ++i) {
261 if(extData->stage3[i]!=0) {
262 printf("stage3[%04x]=%04x\n", i, extData->stage3[i]);
263 }
264 }
265
266 length=extData->stage3bTop;
267 printf("\nstage3b[%x]:\n", length);
268
269 for(i=0; i<length; ++i) {
270 if(extData->stage3b[i]!=0) {
271 printf("stage3b[%04x]=%08x\n", i, extData->stage3b[i]);
272 }
273 }
274 }
275#endif
276
277 if(VERBOSE) {
278 printf("size of extension data: %ld\n", (long)top);
279 }
280
281 /* return the number of bytes that should have been written */
282 return (uint32_t)(headerSize+top);
283}
284
285/* to Unicode --------------------------------------------------------------- */
286
287/*
288 * Remove fromUnicode fallbacks and SUB mappings which are irrelevant for
289 * the toUnicode table.
290 * The table must be sorted.
291 * Destroys previous data in the reverseMap.
292 */
293static int32_t
294reduceToUMappings(UCMTable *table) {
295 UCMapping *mappings;
296 int32_t *map;
297 int32_t i, j, count;
298 int8_t flag;
299
300 mappings=table->mappings;
301 map=table->reverseMap;
302 count=table->mappingsLength;
303
304 /* leave the map alone for the initial mappings with desired flags */
305 for(i=j=0; i<count; ++i) {
306 flag=mappings[map[i]].f;
307 if(flag!=0 && flag!=3) {
308 break;
309 }
310 }
311
312 /* reduce from here to the rest */
313 for(j=i; i<count; ++i) {
314 flag=mappings[map[i]].f;
315 if(flag==0 || flag==3) {
316 map[j++]=map[i];
317 }
318 }
319
320 return j;
321}
322
323static uint32_t
324getToUnicodeValue(CnvExtData *extData, UCMTable *table, UCMapping *m) {
325 UChar32 *u32;
326 UChar *u;
327 uint32_t value;
328 int32_t u16Length, ratio;
329 UErrorCode errorCode;
330
331 /* write the Unicode result code point or string index */
332 if(m->uLen==1) {
333 u16Length=U16_LENGTH(m->u);
334 value=(uint32_t)(UCNV_EXT_TO_U_MIN_CODE_POINT+m->u);
335 } else {
336 /* the parser enforces m->uLen<=UCNV_EXT_MAX_UCHARS */
337
338 /* get the result code point string and its 16-bit string length */
339 u32=UCM_GET_CODE_POINTS(table, m);
340 errorCode=U_ZERO_ERROR;
341 u_strFromUTF32(NULL, 0, &u16Length, u32, m->uLen, &errorCode);
342 if(U_FAILURE(errorCode) && errorCode!=U_BUFFER_OVERFLOW_ERROR) {
343 exit(errorCode);
344 }
345
346 /* allocate it and put its length and index into the value */
347 value=
348 (((uint32_t)m->uLen+UCNV_EXT_TO_U_LENGTH_OFFSET)<<UCNV_EXT_TO_U_LENGTH_SHIFT)|
349 ((uint32_t)utm_countItems(extData->toUUChars));
350 u=utm_allocN(extData->toUUChars, u16Length);
351
352 /* write the result 16-bit string */
353 errorCode=U_ZERO_ERROR;
354 u_strFromUTF32(u, u16Length, NULL, u32, m->uLen, &errorCode);
355 if(U_FAILURE(errorCode) && errorCode!=U_BUFFER_OVERFLOW_ERROR) {
356 exit(errorCode);
357 }
358 }
359 if(m->f==0) {
360 value|=UCNV_EXT_TO_U_ROUNDTRIP_FLAG;
361 }
362
363 /* update statistics */
364 if(m->bLen>extData->maxInBytes) {
365 extData->maxInBytes=m->bLen;
366 }
367 if(u16Length>extData->maxOutUChars) {
368 extData->maxOutUChars=u16Length;
369 }
370
371 ratio=(u16Length+(m->bLen-1))/m->bLen;
372 if(ratio>extData->maxUCharsPerByte) {
373 extData->maxUCharsPerByte=ratio;
374 }
375
376 return value;
377}
378
379/*
380 * Recursive toUTable generator core function.
381 * Preconditions:
382 * - start<limit (There is at least one mapping.)
383 * - The mappings are sorted lexically. (Access is through the reverseMap.)
384 * - All mappings between start and limit have input sequences that share
385 * the same prefix of unitIndex length, and therefore all of these sequences
386 * are at least unitIndex+1 long.
387 * - There are only relevant mappings available through the reverseMap,
388 * see reduceToUMappings().
389 *
390 * One function invocation generates one section table.
391 *
392 * Steps:
393 * 1. Count the number of unique unit values and get the low/high unit values
394 * that occur at unitIndex.
395 * 2. Allocate the section table with possible optimization for linear access.
396 * 3. Write temporary version of the section table with start indexes of
397 * subsections, each corresponding to one unit value at unitIndex.
398 * 4. Iterate through the table once more, and depending on the subsection length:
399 * 0: write 0 as a result value (unused byte in linear-access section table)
400 * >0: if there is one mapping with an input unit sequence of unitIndex+1
401 * then defaultValue=compute the mapping result for this whole sequence
402 * else defaultValue=0
403 *
404 * recurse into the subsection
405 */
406static UBool
407generateToUTable(CnvExtData *extData, UCMTable *table,
408 int32_t start, int32_t limit, int32_t unitIndex,
409 uint32_t defaultValue) {
410 UCMapping *mappings, *m;
411 int32_t *map;
412 int32_t i, j, uniqueCount, count, subStart, subLimit;
413
414 uint8_t *bytes;
415 int32_t low, high, prev;
416
417 uint32_t *section;
418
419 mappings=table->mappings;
420 map=table->reverseMap;
421
422 /* step 1: examine the input units; set low, high, uniqueCount */
423 m=mappings+map[start];
424 bytes=UCM_GET_BYTES(table, m);
425 low=bytes[unitIndex];
426 uniqueCount=1;
427
428 prev=high=low;
429 for(i=start+1; i<limit; ++i) {
430 m=mappings+map[i];
431 bytes=UCM_GET_BYTES(table, m);
432 high=bytes[unitIndex];
433
434 if(high!=prev) {
435 prev=high;
436 ++uniqueCount;
437 }
438 }
439
440 /* step 2: allocate the section; set count, section */
441 count=(high-low)+1;
442 if(unitIndex==0 || uniqueCount>=(3*count)/4) {
443 /*
444 * for the root table and for fairly full tables:
445 * allocate for direct, linear array access
446 * by keeping count, to write an entry for each unit value
447 * from low to high
448 */
449 } else {
450 count=uniqueCount;
451 }
452
453 /* allocate the section: 1 entry for the header + count for the items */
454 section=(uint32_t *)utm_allocN(extData->toUTable, 1+count);
455
456 /* write the section header */
457 *section++=((uint32_t)count<<UCNV_EXT_TO_U_BYTE_SHIFT)|defaultValue;
458
459 /* step 3: write temporary section table with subsection starts */
460 prev=low-1; /* just before low to prevent empty subsections before low */
461 j=0; /* section table index */
462 for(i=start; i<limit; ++i) {
463 m=mappings+map[i];
464 bytes=UCM_GET_BYTES(table, m);
465 high=bytes[unitIndex];
466
467 if(high!=prev) {
468 /* start of a new subsection for unit high */
469 if(count>uniqueCount) {
470 /* write empty subsections for unused units in a linear table */
471 while(++prev<high) {
472 section[j++]=((uint32_t)prev<<UCNV_EXT_TO_U_BYTE_SHIFT)|(uint32_t)i;
473 }
474 } else {
475 prev=high;
476 }
477
478 /* write the entry with the subsection start */
479 section[j++]=((uint32_t)high<<UCNV_EXT_TO_U_BYTE_SHIFT)|(uint32_t)i;
480 }
481 }
482 /* assert(j==count) */
483
484 /* step 4: recurse and write results */
485 subLimit=UCNV_EXT_TO_U_GET_VALUE(section[0]);
486 for(j=0; j<count; ++j) {
487 subStart=subLimit;
488 subLimit= (j+1)<count ? UCNV_EXT_TO_U_GET_VALUE(section[j+1]) : limit;
489
490 /* remove the subStart temporary value */
491 section[j]&=~UCNV_EXT_TO_U_VALUE_MASK;
492
493 if(subStart==subLimit) {
494 /* leave the value zero: empty subsection for unused unit in a linear table */
495 continue;
496 }
497
498 /* see if there is exactly one input unit sequence of length unitIndex+1 */
499 defaultValue=0;
500 m=mappings+map[subStart];
501 if(m->bLen==unitIndex+1) {
502 /* do not include this in generateToUTable() */
503 ++subStart;
504
505 if(subStart<subLimit && mappings[map[subStart]].bLen==unitIndex+1) {
506 /* print error for multiple same-input-sequence mappings */
507 fprintf(stderr, "error: multiple mappings from same bytes\n");
508 ucm_printMapping(table, m, stderr);
509 ucm_printMapping(table, mappings+map[subStart], stderr);
510 return FALSE;
511 }
512
513 defaultValue=getToUnicodeValue(extData, table, m);
514 }
515
516 if(subStart==subLimit) {
517 /* write the result for the input sequence ending here */
518 section[j]|=defaultValue;
519 } else {
520 /* write the index to the subsection table */
521 section[j]|=(uint32_t)utm_countItems(extData->toUTable);
522
523 /* recurse */
524 if(!generateToUTable(extData, table, subStart, subLimit, unitIndex+1, defaultValue)) {
525 return FALSE;
526 }
527 }
528 }
529 return TRUE;
530}
531
532/*
533 * Generate the toUTable and toUUChars from the input table.
534 * The input table must be sorted, and all precision flags must be 0..3.
535 * This function will modify the table's reverseMap.
536 */
537static UBool
538makeToUTable(CnvExtData *extData, UCMTable *table) {
539 int32_t toUCount;
540
541 toUCount=reduceToUMappings(table);
542
543 extData->toUTable=utm_open("cnv extension toUTable", 0x10000, UCNV_EXT_TO_U_MIN_CODE_POINT, 4);
544 extData->toUUChars=utm_open("cnv extension toUUChars", 0x10000, UCNV_EXT_TO_U_INDEX_MASK+1, 2);
545
546 return generateToUTable(extData, table, 0, toUCount, 0, 0);
547}
548
549/* from Unicode ------------------------------------------------------------- */
550
551/*
552 * preprocessing:
553 * rebuild reverseMap with mapping indexes for mappings relevant for from Unicode
554 * change each Unicode string to encode all but the first code point in 16-bit form
555 *
556 * generation:
557 * for each unique code point
558 * write an entry in the 3-stage trie
559 * check that there is only one single-code point sequence
560 * start recursion for following 16-bit input units
561 */
562
563/*
564 * Remove toUnicode fallbacks and non-<subchar1> SUB mappings
565 * which are irrelevant for the fromUnicode extension table.
566 * Overwrite the reverseMap with an index array to the relevant mappings.
567 * Modify the code point sequences to a generator-friendly format where
568 * the first code points remains unchanged but the following are recoded
569 * into 16-bit Unicode string form.
570 * The table must be sorted.
571 * Destroys previous data in the reverseMap.
572 */
573static int32_t
574prepareFromUMappings(UCMTable *table) {
575 UCMapping *mappings, *m;
576 int32_t *map;
577 int32_t i, j, count;
578 int8_t flag;
579
580 mappings=table->mappings;
581 map=table->reverseMap;
582 count=table->mappingsLength;
583
584 /*
585 * we do not go through the map on input because the mappings are
586 * sorted lexically
587 */
588 m=mappings;
589
590 for(i=j=0; i<count; ++m, ++i) {
591 flag=m->f;
592 if(flag==0 || flag==1 || (flag==2 && m->bLen==1)) {
593 map[j++]=i;
594
595 if(m->uLen>1) {
596 /* recode all but the first code point to 16-bit Unicode */
597 UChar32 *u32;
598 UChar *u;
599 UChar32 c;
600 int32_t q, r;
601
602 u32=UCM_GET_CODE_POINTS(table, m);
603 u=(UChar *)u32; /* destructive in-place recoding */
604 for(r=2, q=1; q<m->uLen; ++q) {
605 c=u32[q];
606 U16_APPEND_UNSAFE(u, r, c);
607 }
608
609 /* counts the first code point always at 2 - the first 16-bit unit is at 16-bit index 2 */
610 m->uLen=(int8_t)r;
611 }
612 }
613 }
614
615 return j;
616}
617
618static uint32_t
619getFromUBytesValue(CnvExtData *extData, UCMTable *table, UCMapping *m) {
620 uint8_t *bytes, *resultBytes;
621 uint32_t value;
622 int32_t u16Length, ratio;
623
624 if(m->f==2) {
625 /*
626 * no mapping, <subchar1> preferred
627 *
628 * no need to count in statistics because the subchars are already
629 * counted for maxOutBytes and maxBytesPerUChar in UConverterStaticData,
630 * and this non-mapping does not count for maxInUChars which are always
631 * trivially at least two if counting unmappable supplementary code points
632 */
633 return UCNV_EXT_FROM_U_SUBCHAR1;
634 }
635
636 bytes=UCM_GET_BYTES(table, m);
637 value=0;
638 switch(m->bLen) {
639 /* 1..3: store the bytes in the value word */
640 case 3:
641 value=((uint32_t)*bytes++)<<16;
642 case 2:
643 value|=((uint32_t)*bytes++)<<8;
644 case 1:
645 value|=*bytes;
646 break;
647 default:
648 /* the parser enforces m->bLen<=UCNV_EXT_MAX_BYTES */
649 /* store the bytes in fromUBytes[] and the index in the value word */
650 value=(uint32_t)utm_countItems(extData->fromUBytes);
651 resultBytes=utm_allocN(extData->fromUBytes, m->bLen);
652 uprv_memcpy(resultBytes, bytes, m->bLen);
653 break;
654 }
655 value|=(uint32_t)m->bLen<<UCNV_EXT_FROM_U_LENGTH_SHIFT;
656 if(m->f==0) {
657 value|=UCNV_EXT_FROM_U_ROUNDTRIP_FLAG;
658 }
659
660 /* calculate the real UTF-16 length (see recoding in prepareFromUMappings()) */
661 if(m->uLen==1) {
662 u16Length=U16_LENGTH(m->u);
663 } else {
664 u16Length=U16_LENGTH(UCM_GET_CODE_POINTS(table, m)[0])+(m->uLen-2);
665 }
666
667 /* update statistics */
668 if(u16Length>extData->maxInUChars) {
669 extData->maxInUChars=u16Length;
670 }
671 if(m->bLen>extData->maxOutBytes) {
672 extData->maxOutBytes=m->bLen;
673 }
674
675 ratio=(m->bLen+(u16Length-1))/u16Length;
676 if(ratio>extData->maxBytesPerUChar) {
677 extData->maxBytesPerUChar=ratio;
678 }
679
680 return value;
681}
682
683/*
684 * works like generateToUTable(), except that the
685 * output section consists of two arrays, one for input UChars and one
686 * for result values
687 *
688 * also, fromUTable sections are always stored in a compact form for
689 * access via binary search
690 */
691static UBool
692generateFromUTable(CnvExtData *extData, UCMTable *table,
693 int32_t start, int32_t limit, int32_t unitIndex,
694 uint32_t defaultValue) {
695 UCMapping *mappings, *m;
696 int32_t *map;
697 int32_t i, j, uniqueCount, count, subStart, subLimit;
698
699 UChar *uchars;
700 UChar32 low, high, prev;
701
702 UChar *sectionUChars;
703 uint32_t *sectionValues;
704
705 mappings=table->mappings;
706 map=table->reverseMap;
707
708 /* step 1: examine the input units; set low, high, uniqueCount */
709 m=mappings+map[start];
710 uchars=(UChar *)UCM_GET_CODE_POINTS(table, m);
711 low=uchars[unitIndex];
712 uniqueCount=1;
713
714 prev=high=low;
715 for(i=start+1; i<limit; ++i) {
716 m=mappings+map[i];
717 uchars=(UChar *)UCM_GET_CODE_POINTS(table, m);
718 high=uchars[unitIndex];
719
720 if(high!=prev) {
721 prev=high;
722 ++uniqueCount;
723 }
724 }
725
726 /* step 2: allocate the section; set count, section */
727 /* the fromUTable always stores for access via binary search */
728 count=uniqueCount;
729
730 /* allocate the section: 1 entry for the header + count for the items */
731 sectionUChars=(UChar *)utm_allocN(extData->fromUTableUChars, 1+count);
732 sectionValues=(uint32_t *)utm_allocN(extData->fromUTableValues, 1+count);
733
734 /* write the section header */
735 *sectionUChars++=(UChar)count;
736 *sectionValues++=defaultValue;
737
738 /* step 3: write temporary section table with subsection starts */
739 prev=low-1; /* just before low to prevent empty subsections before low */
740 j=0; /* section table index */
741 for(i=start; i<limit; ++i) {
742 m=mappings+map[i];
743 uchars=(UChar *)UCM_GET_CODE_POINTS(table, m);
744 high=uchars[unitIndex];
745
746 if(high!=prev) {
747 /* start of a new subsection for unit high */
748 prev=high;
749
750 /* write the entry with the subsection start */
751 sectionUChars[j]=(UChar)high;
752 sectionValues[j]=(uint32_t)i;
753 ++j;
754 }
755 }
756 /* assert(j==count) */
757
758 /* step 4: recurse and write results */
759 subLimit=(int32_t)(sectionValues[0]);
760 for(j=0; j<count; ++j) {
761 subStart=subLimit;
762 subLimit= (j+1)<count ? (int32_t)(sectionValues[j+1]) : limit;
763
764 /* see if there is exactly one input unit sequence of length unitIndex+1 */
765 defaultValue=0;
766 m=mappings+map[subStart];
767 if(m->uLen==unitIndex+1) {
768 /* do not include this in generateToUTable() */
769 ++subStart;
770
771 if(subStart<subLimit && mappings[map[subStart]].uLen==unitIndex+1) {
772 /* print error for multiple same-input-sequence mappings */
773 fprintf(stderr, "error: multiple mappings from same Unicode code points\n");
774 ucm_printMapping(table, m, stderr);
775 ucm_printMapping(table, mappings+map[subStart], stderr);
776 return FALSE;
777 }
778
779 defaultValue=getFromUBytesValue(extData, table, m);
780 }
781
782 if(subStart==subLimit) {
783 /* write the result for the input sequence ending here */
784 sectionValues[j]=defaultValue;
785 } else {
786 /* write the index to the subsection table */
787 sectionValues[j]=(uint32_t)utm_countItems(extData->fromUTableValues);
788
789 /* recurse */
790 if(!generateFromUTable(extData, table, subStart, subLimit, unitIndex+1, defaultValue)) {
791 return FALSE;
792 }
793 }
794 }
795 return TRUE;
796}
797
798/*
799 * add entries to the fromUnicode trie,
800 * assume to be called with code points in ascending order
801 * and use that to build the trie in precompacted form
802 */
803static void
804addFromUTrieEntry(CnvExtData *extData, UChar32 c, uint32_t value) {
805 int32_t i1, i2, i3, i3b, nextOffset, min, newBlock;
806
807 if(value==0) {
808 return;
809 }
810
811 /*
812 * compute the index for each stage,
813 * allocate a stage block if necessary,
814 * and write the stage value
815 */
816 i1=c>>10;
817 if(i1>=extData->stage1Top) {
818 extData->stage1Top=i1+1;
819 }
820
821 nextOffset=(c>>4)&0x3f;
822
823 if(extData->stage1[i1]==0) {
824 /* allocate another block in stage 2; overlap with the previous block */
825 newBlock=extData->stage2Top;
826 min=newBlock-nextOffset; /* minimum block start with overlap */
827 while(min<newBlock && extData->stage2[newBlock-1]==0) {
828 --newBlock;
829 }
830
831 extData->stage1[i1]=(uint16_t)newBlock;
832 extData->stage2Top=newBlock+MBCS_STAGE_2_BLOCK_SIZE;
833 if(extData->stage2Top>LENGTHOF(extData->stage2)) {
834 fprintf(stderr, "error: too many stage 2 entries at U+%04x\n", (int)c);
835 exit(U_MEMORY_ALLOCATION_ERROR);
836 }
837 }
838
839 i2=extData->stage1[i1]+nextOffset;
840 nextOffset=c&0xf;
841
842 if(extData->stage2[i2]==0) {
843 /* allocate another block in stage 3; overlap with the previous block */
844 newBlock=extData->stage3Top;
845 min=newBlock-nextOffset; /* minimum block start with overlap */
846 while(min<newBlock && extData->stage3[newBlock-1]==0) {
847 --newBlock;
848 }
849
850 /* round up to a multiple of stage 3 granularity >1 (similar to utrie.c) */
851 newBlock=(newBlock+(UCNV_EXT_STAGE_3_GRANULARITY-1))&~(UCNV_EXT_STAGE_3_GRANULARITY-1);
852 extData->stage2[i2]=(uint16_t)(newBlock>>UCNV_EXT_STAGE_2_LEFT_SHIFT);
853
854 extData->stage3Top=newBlock+MBCS_STAGE_3_BLOCK_SIZE;
855 if(extData->stage3Top>LENGTHOF(extData->stage3)) {
856 fprintf(stderr, "error: too many stage 3 entries at U+%04x\n", (int)c);
857 exit(U_MEMORY_ALLOCATION_ERROR);
858 }
859 }
860
861 i3=((int32_t)extData->stage2[i2]<<UCNV_EXT_STAGE_2_LEFT_SHIFT)+nextOffset;
862 /*
863 * assume extData->stage3[i3]==0 because we get
864 * code points in strictly ascending order
865 */
866
867 if(value==UCNV_EXT_FROM_U_SUBCHAR1) {
868 /* <subchar1> SUB mapping, see getFromUBytesValue() and prepareFromUMappings() */
869 extData->stage3[i3]=1;
870
871 /*
872 * precompaction is not optimal for <subchar1> |2 mappings because
873 * stage3 values for them are all the same, unlike for other mappings
874 * which all have unique values;
875 * use a simple compaction of reusing a whole block filled with these
876 * mappings
877 */
878
879 /* is the entire block filled with <subchar1> |2 mappings? */
880 if(nextOffset==MBCS_STAGE_3_BLOCK_SIZE-1) {
881 for(min=i3-nextOffset;
882 min<i3 && extData->stage3[min]==1;
883 ++min) {}
884
885 if(min==i3) {
886 /* the entire block is filled with these mappings */
887 if(extData->stage3Sub1Block!=0) {
888 /* point to the previous such block and remove this block from stage3 */
889 extData->stage2[i2]=extData->stage3Sub1Block;
890 extData->stage3Top-=MBCS_STAGE_3_BLOCK_SIZE;
891 uprv_memset(extData->stage3+extData->stage3Top, 0, MBCS_STAGE_3_BLOCK_SIZE*2);
892 } else {
893 /* remember this block's stage2 entry */
894 extData->stage3Sub1Block=extData->stage2[i2];
895 }
896 }
897 }
898 } else {
899 if((i3b=extData->stage3bTop++)>=LENGTHOF(extData->stage3b)) {
900 fprintf(stderr, "error: too many stage 3b entries at U+%04x\n", (int)c);
901 exit(U_MEMORY_ALLOCATION_ERROR);
902 }
903
904 /* roundtrip or fallback mapping */
905 extData->stage3[i3]=(uint16_t)i3b;
906 extData->stage3b[i3b]=value;
907 }
908}
909
910static UBool
911generateFromUTrie(CnvExtData *extData, UCMTable *table, int32_t mapLength) {
912 UCMapping *mappings, *m;
913 int32_t *map;
914 uint32_t value;
915 int32_t subStart, subLimit;
916
917 UChar32 *codePoints;
918 UChar32 c, next;
919
920 if(mapLength==0) {
921 return TRUE;
922 }
923
924 mappings=table->mappings;
925 map=table->reverseMap;
926
927 /*
928 * iterate over same-initial-code point mappings,
929 * enter the initial code point into the trie,
930 * and start a recursion on the corresponding mappings section
931 * with generateFromUTable()
932 */
933 m=mappings+map[0];
934 codePoints=UCM_GET_CODE_POINTS(table, m);
935 next=codePoints[0];
936 subLimit=0;
937 while(subLimit<mapLength) {
938 /* get a new subsection of mappings starting with the same code point */
939 subStart=subLimit;
940 c=next;
941 while(next==c && ++subLimit<mapLength) {
942 m=mappings+map[subLimit];
943 codePoints=UCM_GET_CODE_POINTS(table, m);
944 next=codePoints[0];
945 }
946
947 /*
948 * compute the value for this code point;
949 * if there is a mapping for this code point alone, it is at subStart
950 * because the table is sorted lexically
951 */
952 value=0;
953 m=mappings+map[subStart];
954 codePoints=UCM_GET_CODE_POINTS(table, m);
955 if(m->uLen==1) {
956 /* do not include this in generateFromUTable() */
957 ++subStart;
958
959 if(subStart<subLimit && mappings[map[subStart]].uLen==1) {
960 /* print error for multiple same-input-sequence mappings */
961 fprintf(stderr, "error: multiple mappings from same Unicode code points\n");
962 ucm_printMapping(table, m, stderr);
963 ucm_printMapping(table, mappings+map[subStart], stderr);
964 return FALSE;
965 }
966
967 value=getFromUBytesValue(extData, table, m);
968 }
969
970 if(subStart==subLimit) {
971 /* write the result for this one code point */
972 addFromUTrieEntry(extData, c, value);
973 } else {
974 /* write the index to the subsection table */
975 addFromUTrieEntry(extData, c, (uint32_t)utm_countItems(extData->fromUTableValues));
976
977 /* recurse, starting from 16-bit-unit index 2, the first 16-bit unit after c */
978 if(!generateFromUTable(extData, table, subStart, subLimit, 2, value)) {
979 return FALSE;
980 }
981 }
982 }
983 return TRUE;
984}
985
986/*
987 * Generate the fromU data structures from the input table.
988 * The input table must be sorted, and all precision flags must be 0..3.
989 * This function will modify the table's reverseMap.
990 */
991static UBool
992makeFromUTable(CnvExtData *extData, UCMTable *table) {
993 uint16_t *stage1;
994 int32_t i, stage1Top, fromUCount;
995
996 fromUCount=prepareFromUMappings(table);
997
998 extData->fromUTableUChars=utm_open("cnv extension fromUTableUChars", 0x10000, UCNV_EXT_FROM_U_DATA_MASK+1, 2);
999 extData->fromUTableValues=utm_open("cnv extension fromUTableValues", 0x10000, UCNV_EXT_FROM_U_DATA_MASK+1, 4);
1000 extData->fromUBytes=utm_open("cnv extension fromUBytes", 0x10000, UCNV_EXT_FROM_U_DATA_MASK+1, 1);
1001
1002 /* allocate all-unassigned stage blocks */
1003 extData->stage2Top=MBCS_STAGE_2_FIRST_ASSIGNED;
1004 extData->stage3Top=MBCS_STAGE_3_FIRST_ASSIGNED;
1005
1006 /*
1007 * stage 3b stores only unique values, and in
1008 * index 0: 0 for "no mapping"
1009 * index 1: "no mapping" with preference for <subchar1> rather than <subchar>
1010 */
1011 extData->stage3b[1]=UCNV_EXT_FROM_U_SUBCHAR1;
1012 extData->stage3bTop=2;
1013
1014 /* allocate the first entry in the fromUTable because index 0 means "no result" */
1015 utm_alloc(extData->fromUTableUChars);
1016 utm_alloc(extData->fromUTableValues);
1017
1018 if(!generateFromUTrie(extData, table, fromUCount)) {
1019 return FALSE;
1020 }
1021
1022 /*
1023 * offset the stage 1 trie entries by stage1Top because they will
1024 * be stored in a single array
1025 */
1026 stage1=extData->stage1;
1027 stage1Top=extData->stage1Top;
1028 for(i=0; i<stage1Top; ++i) {
1029 stage1[i]=(uint16_t)(stage1[i]+stage1Top);
1030 }
1031
1032 return TRUE;
1033}
1034
1035/* -------------------------------------------------------------------------- */
1036
1037static UBool
1038CnvExtAddTable(NewConverter *cnvData, UCMTable *table, UConverterStaticData *staticData) {
1039 CnvExtData *extData;
1040
1041 if(table->unicodeMask&UCNV_HAS_SURROGATES) {
1042 fprintf(stderr, "error: contains mappings for surrogate code points\n");
1043 return FALSE;
1044 }
1045
1046 staticData->conversionType=UCNV_MBCS;
1047
1048 extData=(CnvExtData *)cnvData;
1049
1050 /*
1051 * assume that the table is sorted
1052 *
1053 * call the functions in this order because
1054 * makeToUTable() modifies the original reverseMap,
1055 * makeFromUTable() writes a whole new mapping into reverseMap
1056 */
1057 return
1058 makeToUTable(extData, table) &&
1059 makeFromUTable(extData, table);
1060}
73c04bcf 1061