1/*
2*******************************************************************************
3*
4*   Copyright (C) 2000-2010, International Business Machines
5*   Corporation and others.  All Rights Reserved.
6*
7*******************************************************************************
8*
9* File reslist.c
10*
11* Modification History:
12*
13*   Date        Name        Description
14*   02/21/00    weiv        Creation.
15*******************************************************************************
16*/
17
18#include <assert.h>
19#include <stdio.h>
20#include "reslist.h"
21#include "unewdata.h"
22#include "unicode/ures.h"
23#include "unicode/putil.h"
24#include "errmsg.h"
25
26#include "uarrsort.h"
27#include "uinvchar.h"
28
29/*
30 * Align binary data at a 16-byte offset from the start of the resource bundle,
31 * to be safe for any data type it may contain.
32 */
33#define BIN_ALIGNMENT 16
34
35static UBool gIncludeCopyright = FALSE;
36static UBool gUsePoolBundle = FALSE;
37static int32_t gFormatVersion = 2;
38
39static UChar gEmptyString = 0;
40
41/* How do we store string values? */
42enum {
43    STRINGS_UTF16_V1,   /* formatVersion 1: int length + UChars + NUL + padding to 4 bytes */
44    STRINGS_UTF16_V2    /* formatVersion 2: optional length in 1..3 UChars + UChars + NUL */
45};
46
47enum {
48    MAX_IMPLICIT_STRING_LENGTH = 40  /* do not store the length explicitly for such strings */
49};
50
51/*
52 * res_none() returns the address of kNoResource,
53 * for use in non-error cases when no resource is to be added to the bundle.
54 * (NULL is used in error cases.)
55 */
56static const struct SResource kNoResource = { URES_NONE };
57
58static UDataInfo dataInfo= {
59    sizeof(UDataInfo),
60    0,
61
62    U_IS_BIG_ENDIAN,
63    U_CHARSET_FAMILY,
64    sizeof(UChar),
65    0,
66
67    {0x52, 0x65, 0x73, 0x42},     /* dataFormat="ResB" */
68    {1, 3, 0, 0},                 /* formatVersion */
69    {1, 4, 0, 0}                  /* dataVersion take a look at version inside parsed resb*/
70};
71
72static const UVersionInfo gFormatVersions[3] = {  /* indexed by a major-formatVersion integer */
73    { 0, 0, 0, 0 },
74    { 1, 3, 0, 0 },
75    { 2, 0, 0, 0 }
76};
77
78static uint8_t calcPadding(uint32_t size) {
79    /* returns space we need to pad */
80    return (uint8_t) ((size % sizeof(uint32_t)) ? (sizeof(uint32_t) - (size % sizeof(uint32_t))) : 0);
81
82}
83
84void setIncludeCopyright(UBool val){
85    gIncludeCopyright=val;
86}
87
88UBool getIncludeCopyright(void){
89    return gIncludeCopyright;
90}
91
92void setFormatVersion(int32_t formatVersion) {
93    gFormatVersion = formatVersion;
94}
95
96void setUsePoolBundle(UBool use) {
97    gUsePoolBundle = use;
98}
99
100static void
101bundle_compactStrings(struct SRBRoot *bundle, UErrorCode *status);
102
103/* Writing Functions */
104
105/*
106 * type_write16() functions write resource values into f16BitUnits
107 * and determine the resource item word, if possible.
108 */
109static void
110res_write16(struct SRBRoot *bundle, struct SResource *res,
111            UErrorCode *status);
112
113/*
114 * type_preWrite() functions calculate ("preflight") and advance the *byteOffset
115 * by the size of their data in the binary file and
116 * determine the resource item word.
117 * Most type_preWrite() functions may add any number of bytes, but res_preWrite()
118 * will always pad it to a multiple of 4.
119 * The resource item type may be a related subtype of the fType.
120 *
121 * The type_preWrite() and type_write() functions start and end at the same
122 * byteOffset values.
123 * Prewriting allows bundle_write() to determine the root resource item word,
124 * before actually writing the bundle contents to the file,
125 * which is necessary because the root item is stored at the beginning.
126 */
127static void
128res_preWrite(uint32_t *byteOffset,
129             struct SRBRoot *bundle, struct SResource *res,
130             UErrorCode *status);
131
132/*
133 * type_write() functions write their data to mem and update the byteOffset
134 * in parallel.
135 * (A kingdom for C++ and polymorphism...)
136 */
137static void
138res_write(UNewDataMemory *mem, uint32_t *byteOffset,
139          struct SRBRoot *bundle, struct SResource *res,
140          UErrorCode *status);
141
142static uint16_t *
143reserve16BitUnits(struct SRBRoot *bundle, int32_t length, UErrorCode *status) {
144    if (U_FAILURE(*status)) {
145        return NULL;
146    }
147    if ((bundle->f16BitUnitsLength + length) > bundle->f16BitUnitsCapacity) {
148        uint16_t *newUnits;
149        int32_t capacity = 2 * bundle->f16BitUnitsCapacity + length + 1024;
150        capacity &= ~1;  /* ensures padding fits if f16BitUnitsLength needs it */
151        newUnits = (uint16_t *)uprv_malloc(capacity * 2);
152        if (newUnits == NULL) {
153            *status = U_MEMORY_ALLOCATION_ERROR;
154            return NULL;
155        }
156        if (bundle->f16BitUnitsLength > 0) {
157            uprv_memcpy(newUnits, bundle->f16BitUnits, bundle->f16BitUnitsLength * 2);
158        } else {
159            newUnits[0] = 0;
160            bundle->f16BitUnitsLength = 1;
161        }
162        uprv_free(bundle->f16BitUnits);
163        bundle->f16BitUnits = newUnits;
164        bundle->f16BitUnitsCapacity = capacity;
165    }
166    return bundle->f16BitUnits + bundle->f16BitUnitsLength;
167}
168
169static int32_t
170makeRes16(uint32_t resWord) {
171    uint32_t type, offset;
172    if (resWord == 0) {
173        return 0;  /* empty string */
174    }
175    type = RES_GET_TYPE(resWord);
176    offset = RES_GET_OFFSET(resWord);
177    if (type == URES_STRING_V2 && offset <= 0xffff) {
178        return (int32_t)offset;
179    }
180    return -1;
181}
182
183static int32_t
184mapKey(struct SRBRoot *bundle, int32_t oldpos) {
185    const KeyMapEntry *map = bundle->fKeyMap;
186    int32_t i, start, limit;
187
188    /* do a binary search for the old, pre-bundle_compactKeys() key offset */
189    start = bundle->fPoolBundleKeysCount;
190    limit = start + bundle->fKeysCount;
191    while (start < limit - 1) {
192        i = (start + limit) / 2;
193        if (oldpos < map[i].oldpos) {
194            limit = i;
195        } else {
196            start = i;
197        }
198    }
199    assert(oldpos == map[start].oldpos);
200    return map[start].newpos;
201}
202
203static uint16_t
204makeKey16(struct SRBRoot *bundle, int32_t key) {
205    if (key >= 0) {
206        return (uint16_t)key;
207    } else {
208        return (uint16_t)(key + bundle->fLocalKeyLimit);  /* offset in the pool bundle */
209    }
210}
211
212/*
213 * Only called for UTF-16 v1 strings and duplicate UTF-16 v2 strings.
214 * For unique UTF-16 v2 strings, res_write16() sees fRes != RES_BOGUS
215 * and exits early.
216 */
217static void
218string_write16(struct SRBRoot *bundle, struct SResource *res, UErrorCode *status) {
219    struct SResource *same;
220    if ((same = res->u.fString.fSame) != NULL) {
221        /* This is a duplicate. */
222        if (same->fRes == RES_BOGUS) {
223            /* The original has not been visited yet. */
224            string_write16(bundle, same, status);
225        }
226        res->fRes = same->fRes;
227        res->fWritten = same->fWritten;
228    }
229}
230
231static void
232array_write16(struct SRBRoot *bundle, struct SResource *res,
233              UErrorCode *status) {
234    struct SResource *current;
235    int32_t res16 = 0;
236
237    if (U_FAILURE(*status)) {
238        return;
239    }
240    if (res->u.fArray.fCount == 0 && gFormatVersion > 1) {
241        res->fRes = URES_MAKE_EMPTY_RESOURCE(URES_ARRAY);
242        res->fWritten = TRUE;
243        return;
244    }
245    for (current = res->u.fArray.fFirst; current != NULL; current = current->fNext) {
246        res_write16(bundle, current, status);
247        res16 |= makeRes16(current->fRes);
248    }
249    if (U_SUCCESS(*status) && res->u.fArray.fCount <= 0xffff && res16 >= 0 && gFormatVersion > 1) {
250        uint16_t *p16 = reserve16BitUnits(bundle, 1 + res->u.fArray.fCount, status);
251        if (U_SUCCESS(*status)) {
252            res->fRes = URES_MAKE_RESOURCE(URES_ARRAY16, bundle->f16BitUnitsLength);
253            *p16++ = (uint16_t)res->u.fArray.fCount;
254            for (current = res->u.fArray.fFirst; current != NULL; current = current->fNext) {
255                *p16++ = (uint16_t)makeRes16(current->fRes);
256            }
257            bundle->f16BitUnitsLength += 1 + res->u.fArray.fCount;
258            res->fWritten = TRUE;
259        }
260    }
261}
262
263static void
264table_write16(struct SRBRoot *bundle, struct SResource *res,
265              UErrorCode *status) {
266    struct SResource *current;
267    int32_t maxKey = 0, maxPoolKey = 0x80000000;
268    int32_t res16 = 0;
269    UBool hasLocalKeys = FALSE, hasPoolKeys = FALSE;
270
271    if (U_FAILURE(*status)) {
272        return;
273    }
274    if (res->u.fTable.fCount == 0 && gFormatVersion > 1) {
275        res->fRes = URES_MAKE_EMPTY_RESOURCE(URES_TABLE);
276        res->fWritten = TRUE;
277        return;
278    }
279    /* Find the smallest table type that fits the data. */
280    for (current = res->u.fTable.fFirst; current != NULL; current = current->fNext) {
281        int32_t key;
282        res_write16(bundle, current, status);
283        if (bundle->fKeyMap == NULL) {
284            key = current->fKey;
285        } else {
286            key = current->fKey = mapKey(bundle, current->fKey);
287        }
288        if (key >= 0) {
289            hasLocalKeys = TRUE;
290            if (key > maxKey) {
291                maxKey = key;
292            }
293        } else {
294            hasPoolKeys = TRUE;
295            if (key > maxPoolKey) {
296                maxPoolKey = key;
297            }
298        }
299        res16 |= makeRes16(current->fRes);
300    }
301    if (U_FAILURE(*status)) {
302        return;
303    }
304    if(res->u.fTable.fCount > (uint32_t)bundle->fMaxTableLength) {
305        bundle->fMaxTableLength = res->u.fTable.fCount;
306    }
307    maxPoolKey &= 0x7fffffff;
308    if (res->u.fTable.fCount <= 0xffff &&
309        (!hasLocalKeys || maxKey < bundle->fLocalKeyLimit) &&
310        (!hasPoolKeys || maxPoolKey < (0x10000 - bundle->fLocalKeyLimit))
311    ) {
312        if (res16 >= 0 && gFormatVersion > 1) {
313            uint16_t *p16 = reserve16BitUnits(bundle, 1 + res->u.fTable.fCount * 2, status);
314            if (U_SUCCESS(*status)) {
315                /* 16-bit count, key offsets and values */
316                res->fRes = URES_MAKE_RESOURCE(URES_TABLE16, bundle->f16BitUnitsLength);
317                *p16++ = (uint16_t)res->u.fTable.fCount;
318                for (current = res->u.fTable.fFirst; current != NULL; current = current->fNext) {
319                    *p16++ = makeKey16(bundle, current->fKey);
320                }
321                for (current = res->u.fTable.fFirst; current != NULL; current = current->fNext) {
322                    *p16++ = (uint16_t)makeRes16(current->fRes);
323                }
324                bundle->f16BitUnitsLength += 1 + res->u.fTable.fCount * 2;
325                res->fWritten = TRUE;
326            }
327        } else {
328            /* 16-bit count, 16-bit key offsets, 32-bit values */
329            res->u.fTable.fType = URES_TABLE;
330        }
331    } else {
332        /* 32-bit count, key offsets and values */
333        res->u.fTable.fType = URES_TABLE32;
334    }
335}
336
337static void
338res_write16(struct SRBRoot *bundle, struct SResource *res,
339            UErrorCode *status) {
340    if (U_FAILURE(*status) || res == NULL) {
341        return;
342    }
343    if (res->fRes != RES_BOGUS) {
344        /*
345         * The resource item word was already precomputed, which means
346         * no further data needs to be written.
347         * This might be an integer, or an empty or UTF-16 v2 string,
348         * an empty binary, etc.
349         */
350        return;
351    }
352    switch (res->fType) {
353    case URES_STRING:
354        string_write16(bundle, res, status);
355        break;
356    case URES_ARRAY:
357        array_write16(bundle, res, status);
358        break;
359    case URES_TABLE:
360        table_write16(bundle, res, status);
361        break;
362    default:
363        /* Only a few resource types write 16-bit units. */
364        break;
365    }
366}
367
368/*
369 * Only called for UTF-16 v1 strings.
370 * For UTF-16 v2 strings, res_preWrite() sees fRes != RES_BOGUS
371 * and exits early.
372 */
373static void
374string_preWrite(uint32_t *byteOffset,
375                struct SRBRoot *bundle, struct SResource *res,
376                UErrorCode *status) {
377    /* Write the UTF-16 v1 string. */
378    res->fRes = URES_MAKE_RESOURCE(URES_STRING, *byteOffset >> 2);
379    *byteOffset += 4 + (res->u.fString.fLength + 1) * U_SIZEOF_UCHAR;
380}
381
382static void
383bin_preWrite(uint32_t *byteOffset,
384             struct SRBRoot *bundle, struct SResource *res,
385             UErrorCode *status) {
386    uint32_t pad       = 0;
387    uint32_t dataStart = *byteOffset + sizeof(res->u.fBinaryValue.fLength);
388
389    if (dataStart % BIN_ALIGNMENT) {
390        pad = (BIN_ALIGNMENT - dataStart % BIN_ALIGNMENT);
391        *byteOffset += pad;  /* pad == 4 or 8 or 12 */
392    }
393    res->fRes = URES_MAKE_RESOURCE(URES_BINARY, *byteOffset >> 2);
394    *byteOffset += 4 + res->u.fBinaryValue.fLength;
395}
396
397static void
398array_preWrite(uint32_t *byteOffset,
399               struct SRBRoot *bundle, struct SResource *res,
400               UErrorCode *status) {
401    struct SResource *current;
402
403    if (U_FAILURE(*status)) {
404        return;
405    }
406    for (current = res->u.fArray.fFirst; current != NULL; current = current->fNext) {
407        res_preWrite(byteOffset, bundle, current, status);
408    }
409    res->fRes = URES_MAKE_RESOURCE(URES_ARRAY, *byteOffset >> 2);
410    *byteOffset += (1 + res->u.fArray.fCount) * 4;
411}
412
413static void
414table_preWrite(uint32_t *byteOffset,
415               struct SRBRoot *bundle, struct SResource *res,
416               UErrorCode *status) {
417    struct SResource *current;
418
419    if (U_FAILURE(*status)) {
420        return;
421    }
422    for (current = res->u.fTable.fFirst; current != NULL; current = current->fNext) {
423        res_preWrite(byteOffset, bundle, current, status);
424    }
425    if (res->u.fTable.fType == URES_TABLE) {
426        /* 16-bit count, 16-bit key offsets, 32-bit values */
427        res->fRes = URES_MAKE_RESOURCE(URES_TABLE, *byteOffset >> 2);
428        *byteOffset += 2 + res->u.fTable.fCount * 6;
429    } else {
430        /* 32-bit count, key offsets and values */
431        res->fRes = URES_MAKE_RESOURCE(URES_TABLE32, *byteOffset >> 2);
432        *byteOffset += 4 + res->u.fTable.fCount * 8;
433    }
434}
435
436static void
437res_preWrite(uint32_t *byteOffset,
438             struct SRBRoot *bundle, struct SResource *res,
439             UErrorCode *status) {
440    if (U_FAILURE(*status) || res == NULL) {
441        return;
442    }
443    if (res->fRes != RES_BOGUS) {
444        /*
445         * The resource item word was already precomputed, which means
446         * no further data needs to be written.
447         * This might be an integer, or an empty or UTF-16 v2 string,
448         * an empty binary, etc.
449         */
450        return;
451    }
452    switch (res->fType) {
453    case URES_STRING:
454        string_preWrite(byteOffset, bundle, res, status);
455        break;
456    case URES_ALIAS:
457        res->fRes = URES_MAKE_RESOURCE(URES_ALIAS, *byteOffset >> 2);
458        *byteOffset += 4 + (res->u.fString.fLength + 1) * U_SIZEOF_UCHAR;
459        break;
460    case URES_INT_VECTOR:
461        if (res->u.fIntVector.fCount == 0 && gFormatVersion > 1) {
462            res->fRes = URES_MAKE_EMPTY_RESOURCE(URES_INT_VECTOR);
463            res->fWritten = TRUE;
464        } else {
465            res->fRes = URES_MAKE_RESOURCE(URES_INT_VECTOR, *byteOffset >> 2);
466            *byteOffset += (1 + res->u.fIntVector.fCount) * 4;
467        }
468        break;
469    case URES_BINARY:
470        bin_preWrite(byteOffset, bundle, res, status);
471        break;
472    case URES_INT:
473        break;
474    case URES_ARRAY:
475        array_preWrite(byteOffset, bundle, res, status);
476        break;
477    case URES_TABLE:
478        table_preWrite(byteOffset, bundle, res, status);
479        break;
480    default:
481        *status = U_INTERNAL_PROGRAM_ERROR;
482        break;
483    }
484    *byteOffset += calcPadding(*byteOffset);
485}
486
487/*
488 * Only called for UTF-16 v1 strings. For UTF-16 v2 strings,
489 * res_write() sees fWritten and exits early.
490 */
491static void string_write(UNewDataMemory *mem, uint32_t *byteOffset,
492                         struct SRBRoot *bundle, struct SResource *res,
493                         UErrorCode *status) {
494    /* Write the UTF-16 v1 string. */
495    int32_t length = res->u.fString.fLength;
496    udata_write32(mem, length);
497    udata_writeUString(mem, res->u.fString.fChars, length + 1);
498    *byteOffset += 4 + (length + 1) * U_SIZEOF_UCHAR;
499    res->fWritten = TRUE;
500}
501
502static void alias_write(UNewDataMemory *mem, uint32_t *byteOffset,
503                        struct SRBRoot *bundle, struct SResource *res,
504                        UErrorCode *status) {
505    int32_t length = res->u.fString.fLength;
506    udata_write32(mem, length);
507    udata_writeUString(mem, res->u.fString.fChars, length + 1);
508    *byteOffset += 4 + (length + 1) * U_SIZEOF_UCHAR;
509}
510
511static void array_write(UNewDataMemory *mem, uint32_t *byteOffset,
512                        struct SRBRoot *bundle, struct SResource *res,
513                        UErrorCode *status) {
514    uint32_t  i;
515
516    struct SResource *current = NULL;
517
518    if (U_FAILURE(*status)) {
519        return;
520    }
521    for (i = 0, current = res->u.fArray.fFirst; current != NULL; ++i, current = current->fNext) {
522        res_write(mem, byteOffset, bundle, current, status);
523    }
524    assert(i == res->u.fArray.fCount);
525
526    udata_write32(mem, res->u.fArray.fCount);
527    for (current = res->u.fArray.fFirst; current != NULL; current = current->fNext) {
528        udata_write32(mem, current->fRes);
529    }
530    *byteOffset += (1 + res->u.fArray.fCount) * 4;
531}
532
533static void intvector_write(UNewDataMemory *mem, uint32_t *byteOffset,
534                            struct SRBRoot *bundle, struct SResource *res,
535                            UErrorCode *status) {
536    uint32_t i = 0;
537    udata_write32(mem, res->u.fIntVector.fCount);
538    for(i = 0; i<res->u.fIntVector.fCount; i++) {
539      udata_write32(mem, res->u.fIntVector.fArray[i]);
540    }
541    *byteOffset += (1 + res->u.fIntVector.fCount) * 4;
542}
543
544static void bin_write(UNewDataMemory *mem, uint32_t *byteOffset,
545                      struct SRBRoot *bundle, struct SResource *res,
546                      UErrorCode *status) {
547    uint32_t pad       = 0;
548    uint32_t dataStart = *byteOffset + sizeof(res->u.fBinaryValue.fLength);
549
550    if (dataStart % BIN_ALIGNMENT) {
551        pad = (BIN_ALIGNMENT - dataStart % BIN_ALIGNMENT);
552        udata_writePadding(mem, pad);  /* pad == 4 or 8 or 12 */
553        *byteOffset += pad;
554    }
555
556    udata_write32(mem, res->u.fBinaryValue.fLength);
557    if (res->u.fBinaryValue.fLength > 0) {
558        udata_writeBlock(mem, res->u.fBinaryValue.fData, res->u.fBinaryValue.fLength);
559    }
560    *byteOffset += 4 + res->u.fBinaryValue.fLength;
561}
562
563static void table_write(UNewDataMemory *mem, uint32_t *byteOffset,
564                        struct SRBRoot *bundle, struct SResource *res,
565                        UErrorCode *status) {
566    struct SResource *current;
567    uint32_t i;
568
569    if (U_FAILURE(*status)) {
570        return;
571    }
572    for (i = 0, current = res->u.fTable.fFirst; current != NULL; ++i, current = current->fNext) {
573        assert(i < res->u.fTable.fCount);
574        res_write(mem, byteOffset, bundle, current, status);
575    }
576    assert(i == res->u.fTable.fCount);
577
578    if(res->u.fTable.fType == URES_TABLE) {
579        udata_write16(mem, (uint16_t)res->u.fTable.fCount);
580        for (current = res->u.fTable.fFirst; current != NULL; current = current->fNext) {
581            udata_write16(mem, makeKey16(bundle, current->fKey));
582        }
583        *byteOffset += (1 + res->u.fTable.fCount)* 2;
584        if ((res->u.fTable.fCount & 1) == 0) {
585            /* 16-bit count and even number of 16-bit key offsets need padding before 32-bit resource items */
586            udata_writePadding(mem, 2);
587            *byteOffset += 2;
588        }
589    } else /* URES_TABLE32 */ {
590        udata_write32(mem, res->u.fTable.fCount);
591        for (current = res->u.fTable.fFirst; current != NULL; current = current->fNext) {
592            udata_write32(mem, (uint32_t)current->fKey);
593        }
594        *byteOffset += (1 + res->u.fTable.fCount)* 4;
595    }
596    for (current = res->u.fTable.fFirst; current != NULL; current = current->fNext) {
597        udata_write32(mem, current->fRes);
598    }
599    *byteOffset += res->u.fTable.fCount * 4;
600}
601
602void res_write(UNewDataMemory *mem, uint32_t *byteOffset,
603               struct SRBRoot *bundle, struct SResource *res,
604               UErrorCode *status) {
605    uint8_t paddingSize;
606
607    if (U_FAILURE(*status) || res == NULL) {
608        return;
609    }
610    if (res->fWritten) {
611        assert(res->fRes != RES_BOGUS);
612        return;
613    }
614    switch (res->fType) {
615    case URES_STRING:
616        string_write    (mem, byteOffset, bundle, res, status);
617        break;
618    case URES_ALIAS:
619        alias_write     (mem, byteOffset, bundle, res, status);
620        break;
621    case URES_INT_VECTOR:
622        intvector_write (mem, byteOffset, bundle, res, status);
623        break;
624    case URES_BINARY:
625        bin_write       (mem, byteOffset, bundle, res, status);
626        break;
627    case URES_INT:
628        break;  /* fRes was set by int_open() */
629    case URES_ARRAY:
630        array_write     (mem, byteOffset, bundle, res, status);
631        break;
632    case URES_TABLE:
633        table_write     (mem, byteOffset, bundle, res, status);
634        break;
635    default:
636        *status = U_INTERNAL_PROGRAM_ERROR;
637        break;
638    }
639    paddingSize = calcPadding(*byteOffset);
640    if (paddingSize > 0) {
641        udata_writePadding(mem, paddingSize);
642        *byteOffset += paddingSize;
643    }
644    res->fWritten = TRUE;
645}
646
647void bundle_write(struct SRBRoot *bundle,
648                  const char *outputDir, const char *outputPkg,
649                  char *writtenFilename, int writtenFilenameLen,
650                  UErrorCode *status) {
651    UNewDataMemory *mem        = NULL;
652    uint32_t        byteOffset = 0;
653    uint32_t        top, size;
654    char            dataName[1024];
655    int32_t         indexes[URES_INDEX_TOP];
656
657    bundle_compactKeys(bundle, status);
658    /*
659     * Add padding bytes to fKeys so that fKeysTop is 4-aligned.
660     * Safe because the capacity is a multiple of 4.
661     */
662    while (bundle->fKeysTop & 3) {
663        bundle->fKeys[bundle->fKeysTop++] = (char)0xaa;
664    }
665    /*
666     * In URES_TABLE, use all local key offsets that fit into 16 bits,
667     * and use the remaining 16-bit offsets for pool key offsets
668     * if there are any.
669     * If there are no local keys, then use the whole 16-bit space
670     * for pool key offsets.
671     * Note: This cannot be changed without changing the major formatVersion.
672     */
673    if (bundle->fKeysBottom < bundle->fKeysTop) {
674        if (bundle->fKeysTop <= 0x10000) {
675            bundle->fLocalKeyLimit = bundle->fKeysTop;
676        } else {
677            bundle->fLocalKeyLimit = 0x10000;
678        }
679    } else {
680        bundle->fLocalKeyLimit = 0;
681    }
682
683    bundle_compactStrings(bundle, status);
684    res_write16(bundle, bundle->fRoot, status);
685    if (bundle->f16BitUnitsLength & 1) {
686        bundle->f16BitUnits[bundle->f16BitUnitsLength++] = 0xaaaa;  /* pad to multiple of 4 bytes */
687    }
688    /* all keys have been mapped */
689    uprv_free(bundle->fKeyMap);
690    bundle->fKeyMap = NULL;
691
692    byteOffset = bundle->fKeysTop + bundle->f16BitUnitsLength * 2;
693    res_preWrite(&byteOffset, bundle, bundle->fRoot, status);
694
695    /* total size including the root item */
696    top = byteOffset;
697
698    if (U_FAILURE(*status)) {
699        return;
700    }
701
702    if (writtenFilename && writtenFilenameLen) {
703        *writtenFilename = 0;
704    }
705
706    if (writtenFilename) {
707       int32_t off = 0, len = 0;
708       if (outputDir) {
709           len = (int32_t)uprv_strlen(outputDir);
710           if (len > writtenFilenameLen) {
711               len = writtenFilenameLen;
712           }
713           uprv_strncpy(writtenFilename, outputDir, len);
714       }
715       if (writtenFilenameLen -= len) {
716           off += len;
717           writtenFilename[off] = U_FILE_SEP_CHAR;
718           if (--writtenFilenameLen) {
719               ++off;
720               if(outputPkg != NULL)
721               {
722                   uprv_strcpy(writtenFilename+off, outputPkg);
723                   off += (int32_t)uprv_strlen(outputPkg);
724                   writtenFilename[off] = '_';
725                   ++off;
726               }
727
728               len = (int32_t)uprv_strlen(bundle->fLocale);
729               if (len > writtenFilenameLen) {
730                   len = writtenFilenameLen;
731               }
732               uprv_strncpy(writtenFilename + off, bundle->fLocale, len);
733               if (writtenFilenameLen -= len) {
734                   off += len;
735                   len = 5;
736                   if (len > writtenFilenameLen) {
737                       len = writtenFilenameLen;
738                   }
739                   uprv_strncpy(writtenFilename +  off, ".res", len);
740               }
741           }
742       }
743    }
744
745    if(outputPkg)
746    {
747        uprv_strcpy(dataName, outputPkg);
748        uprv_strcat(dataName, "_");
749        uprv_strcat(dataName, bundle->fLocale);
750    }
751    else
752    {
753        uprv_strcpy(dataName, bundle->fLocale);
754    }
755
756    uprv_memcpy(dataInfo.formatVersion, gFormatVersions + gFormatVersion, sizeof(UVersionInfo));
757
758    mem = udata_create(outputDir, "res", dataName, &dataInfo, (gIncludeCopyright==TRUE)? U_COPYRIGHT_STRING:NULL, status);
759    if(U_FAILURE(*status)){
760        return;
761    }
762
763    /* write the root item */
764    udata_write32(mem, bundle->fRoot->fRes);
765
766    /*
767     * formatVersion 1.1 (ICU 2.8):
768     * write int32_t indexes[] after root and before the strings
769     * to make it easier to parse resource bundles in icuswap or from Java etc.
770     */
771    uprv_memset(indexes, 0, sizeof(indexes));
772    indexes[URES_INDEX_LENGTH]=             bundle->fIndexLength;
773    indexes[URES_INDEX_KEYS_TOP]=           bundle->fKeysTop>>2;
774    indexes[URES_INDEX_RESOURCES_TOP]=      (int32_t)(top>>2);
775    indexes[URES_INDEX_BUNDLE_TOP]=         indexes[URES_INDEX_RESOURCES_TOP];
776    indexes[URES_INDEX_MAX_TABLE_LENGTH]=   bundle->fMaxTableLength;
777
778    /*
779     * formatVersion 1.2 (ICU 3.6):
780     * write indexes[URES_INDEX_ATTRIBUTES] with URES_ATT_NO_FALLBACK set or not set
781     * the memset() above initialized all indexes[] to 0
782     */
783    if (bundle->noFallback) {
784        indexes[URES_INDEX_ATTRIBUTES]=URES_ATT_NO_FALLBACK;
785    }
786    /*
787     * formatVersion 2.0 (ICU 4.4):
788     * more compact string value storage, optional pool bundle
789     */
790    if (URES_INDEX_16BIT_TOP < bundle->fIndexLength) {
791        indexes[URES_INDEX_16BIT_TOP] = (bundle->fKeysTop>>2) + (bundle->f16BitUnitsLength>>1);
792    }
793    if (URES_INDEX_POOL_CHECKSUM < bundle->fIndexLength) {
794        if (bundle->fIsPoolBundle) {
795            indexes[URES_INDEX_ATTRIBUTES] |= URES_ATT_IS_POOL_BUNDLE | URES_ATT_NO_FALLBACK;
796            indexes[URES_INDEX_POOL_CHECKSUM] =
797                (int32_t)computeCRC((char *)(bundle->fKeys + bundle->fKeysBottom),
798                                    (uint32_t)(bundle->fKeysTop - bundle->fKeysBottom),
799                                    0);
800        } else if (gUsePoolBundle) {
801            indexes[URES_INDEX_ATTRIBUTES] |= URES_ATT_USES_POOL_BUNDLE;
802            indexes[URES_INDEX_POOL_CHECKSUM] = bundle->fPoolChecksum;
803        }
804    }
805
806    /* write the indexes[] */
807    udata_writeBlock(mem, indexes, bundle->fIndexLength*4);
808
809    /* write the table key strings */
810    udata_writeBlock(mem, bundle->fKeys+bundle->fKeysBottom,
811                          bundle->fKeysTop-bundle->fKeysBottom);
812
813    /* write the v2 UTF-16 strings, URES_TABLE16 and URES_ARRAY16 */
814    udata_writeBlock(mem, bundle->f16BitUnits, bundle->f16BitUnitsLength*2);
815
816    /* write all of the bundle contents: the root item and its children */
817    byteOffset = bundle->fKeysTop + bundle->f16BitUnitsLength * 2;
818    res_write(mem, &byteOffset, bundle, bundle->fRoot, status);
819    assert(byteOffset == top);
820
821    size = udata_finish(mem, status);
822    if(top != size) {
823        fprintf(stderr, "genrb error: wrote %u bytes but counted %u\n",
824                (int)size, (int)top);
825        *status = U_INTERNAL_PROGRAM_ERROR;
826    }
827}
828
829/* Opening Functions */
830
831/* gcc 4.2 complained "no previous prototype for res_open" without this prototype... */
832struct SResource* res_open(struct SRBRoot *bundle, const char *tag,
833                           const struct UString* comment, UErrorCode* status);
834
835struct SResource* res_open(struct SRBRoot *bundle, const char *tag,
836                           const struct UString* comment, UErrorCode* status){
837    struct SResource *res;
838    int32_t key = bundle_addtag(bundle, tag, status);
839    if (U_FAILURE(*status)) {
840        return NULL;
841    }
842
843    res = (struct SResource *) uprv_malloc(sizeof(struct SResource));
844    if (res == NULL) {
845        *status = U_MEMORY_ALLOCATION_ERROR;
846        return NULL;
847    }
848    uprv_memset(res, 0, sizeof(struct SResource));
849    res->fKey = key;
850    res->fRes = RES_BOGUS;
851
852    ustr_init(&res->fComment);
853    if(comment != NULL){
854        ustr_cpy(&res->fComment, comment, status);
855        if (U_FAILURE(*status)) {
856            res_close(res);
857            return NULL;
858        }
859    }
860    return res;
861}
862
863struct SResource* res_none() {
864    return (struct SResource*)&kNoResource;
865}
866
867struct SResource* table_open(struct SRBRoot *bundle, const char *tag, const struct UString* comment, UErrorCode *status) {
868    struct SResource *res = res_open(bundle, tag, comment, status);
869    if (U_FAILURE(*status)) {
870        return NULL;
871    }
872    res->fType = URES_TABLE;
873    res->u.fTable.fRoot = bundle;
874    return res;
875}
876
877struct SResource* array_open(struct SRBRoot *bundle, const char *tag, const struct UString* comment, UErrorCode *status) {
878    struct SResource *res = res_open(bundle, tag, comment, status);
879    if (U_FAILURE(*status)) {
880        return NULL;
881    }
882    res->fType = URES_ARRAY;
883    return res;
884}
885
886static int32_t U_CALLCONV
887string_hash(const UHashTok key) {
888    const struct SResource *res = (struct SResource *)key.pointer;
889    return uhash_hashUCharsN(res->u.fString.fChars, res->u.fString.fLength);
890}
891
892static UBool U_CALLCONV
893string_comp(const UHashTok key1, const UHashTok key2) {
894    const struct SResource *res1 = (struct SResource *)key1.pointer;
895    const struct SResource *res2 = (struct SResource *)key2.pointer;
896    return 0 == u_strCompare(res1->u.fString.fChars, res1->u.fString.fLength,
897                             res2->u.fString.fChars, res2->u.fString.fLength,
898                             FALSE);
899}
900
901struct SResource *string_open(struct SRBRoot *bundle, char *tag, const UChar *value, int32_t len, const struct UString* comment, UErrorCode *status) {
902    struct SResource *res = res_open(bundle, tag, comment, status);
903    if (U_FAILURE(*status)) {
904        return NULL;
905    }
906    res->fType = URES_STRING;
907
908    if (len == 0 && gFormatVersion > 1) {
909        res->u.fString.fChars = &gEmptyString;
910        res->fRes = 0;
911        res->fWritten = TRUE;
912        return res;
913    }
914
915    res->u.fString.fLength = len;
916
917    if (gFormatVersion > 1) {
918        /* check for duplicates */
919        res->u.fString.fChars  = (UChar *)value;
920        if (bundle->fStringSet == NULL) {
921            UErrorCode localStatus = U_ZERO_ERROR;  /* if failure: just don't detect dups */
922            bundle->fStringSet = uhash_open(string_hash, string_comp, string_comp, &localStatus);
923        } else {
924            res->u.fString.fSame = uhash_get(bundle->fStringSet, res);
925        }
926    }
927    if (res->u.fString.fSame == NULL) {
928        /* this is a new string */
929        res->u.fString.fChars = (UChar *) uprv_malloc(sizeof(UChar) * (len + 1));
930
931        if (res->u.fString.fChars == NULL) {
932            *status = U_MEMORY_ALLOCATION_ERROR;
933            uprv_free(res);
934            return NULL;
935        }
936
937        uprv_memcpy(res->u.fString.fChars, value, sizeof(UChar) * len);
938        res->u.fString.fChars[len] = 0;
939        if (bundle->fStringSet != NULL) {
940            /* put it into the set for finding duplicates */
941            uhash_put(bundle->fStringSet, res, res, status);
942        }
943
944        if (bundle->fStringsForm != STRINGS_UTF16_V1) {
945            if (len <= MAX_IMPLICIT_STRING_LENGTH && !U16_IS_TRAIL(value[0]) && len == u_strlen(value)) {
946                /*
947                 * This string will be stored without an explicit length.
948                 * Runtime will detect !U16_IS_TRAIL(value[0]) and call u_strlen().
949                 */
950                res->u.fString.fNumCharsForLength = 0;
951            } else if (len <= 0x3ee) {
952                res->u.fString.fNumCharsForLength = 1;
953            } else if (len <= 0xfffff) {
954                res->u.fString.fNumCharsForLength = 2;
955            } else {
956                res->u.fString.fNumCharsForLength = 3;
957            }
958            bundle->f16BitUnitsLength += res->u.fString.fNumCharsForLength + len + 1;  /* +1 for the NUL */
959        }
960    } else {
961        /* this is a duplicate of fSame */
962        struct SResource *same = res->u.fString.fSame;
963        res->u.fString.fChars = same->u.fString.fChars;
964    }
965    return res;
966}
967
968/* TODO: make alias_open and string_open use the same code */
969struct SResource *alias_open(struct SRBRoot *bundle, char *tag, UChar *value, int32_t len, const struct UString* comment, UErrorCode *status) {
970    struct SResource *res = res_open(bundle, tag, comment, status);
971    if (U_FAILURE(*status)) {
972        return NULL;
973    }
974    res->fType = URES_ALIAS;
975    if (len == 0 && gFormatVersion > 1) {
976        res->u.fString.fChars = &gEmptyString;
977        res->fRes = URES_MAKE_EMPTY_RESOURCE(URES_ALIAS);
978        res->fWritten = TRUE;
979        return res;
980    }
981
982    res->u.fString.fLength = len;
983    res->u.fString.fChars  = (UChar *) uprv_malloc(sizeof(UChar) * (len + 1));
984    if (res->u.fString.fChars == NULL) {
985        *status = U_MEMORY_ALLOCATION_ERROR;
986        uprv_free(res);
987        return NULL;
988    }
989    uprv_memcpy(res->u.fString.fChars, value, sizeof(UChar) * (len + 1));
990    return res;
991}
992
993
994struct SResource* intvector_open(struct SRBRoot *bundle, char *tag, const struct UString* comment, UErrorCode *status) {
995    struct SResource *res = res_open(bundle, tag, comment, status);
996    if (U_FAILURE(*status)) {
997        return NULL;
998    }
999    res->fType = URES_INT_VECTOR;
1000
1001    res->u.fIntVector.fCount = 0;
1002    res->u.fIntVector.fArray = (uint32_t *) uprv_malloc(sizeof(uint32_t) * RESLIST_MAX_INT_VECTOR);
1003    if (res->u.fIntVector.fArray == NULL) {
1004        *status = U_MEMORY_ALLOCATION_ERROR;
1005        uprv_free(res);
1006        return NULL;
1007    }
1008    return res;
1009}
1010
1011struct SResource *int_open(struct SRBRoot *bundle, char *tag, int32_t value, const struct UString* comment, UErrorCode *status) {
1012    struct SResource *res = res_open(bundle, tag, comment, status);
1013    if (U_FAILURE(*status)) {
1014        return NULL;
1015    }
1016    res->fType = URES_INT;
1017    res->u.fIntValue.fValue = value;
1018    res->fRes = URES_MAKE_RESOURCE(URES_INT, value & 0x0FFFFFFF);
1019    res->fWritten = TRUE;
1020    return res;
1021}
1022
1023struct SResource *bin_open(struct SRBRoot *bundle, const char *tag, uint32_t length, uint8_t *data, const char* fileName, const struct UString* comment, UErrorCode *status) {
1024    struct SResource *res = res_open(bundle, tag, comment, status);
1025    if (U_FAILURE(*status)) {
1026        return NULL;
1027    }
1028    res->fType = URES_BINARY;
1029
1030    res->u.fBinaryValue.fLength = length;
1031    res->u.fBinaryValue.fFileName = NULL;
1032    if(fileName!=NULL && uprv_strcmp(fileName, "") !=0){
1033        res->u.fBinaryValue.fFileName = (char*) uprv_malloc(sizeof(char) * (uprv_strlen(fileName)+1));
1034        uprv_strcpy(res->u.fBinaryValue.fFileName,fileName);
1035    }
1036    if (length > 0) {
1037        res->u.fBinaryValue.fData   = (uint8_t *) uprv_malloc(sizeof(uint8_t) * length);
1038
1039        if (res->u.fBinaryValue.fData == NULL) {
1040            *status = U_MEMORY_ALLOCATION_ERROR;
1041            uprv_free(res);
1042            return NULL;
1043        }
1044
1045        uprv_memcpy(res->u.fBinaryValue.fData, data, length);
1046    }
1047    else {
1048        res->u.fBinaryValue.fData = NULL;
1049        if (gFormatVersion > 1) {
1050            res->fRes = URES_MAKE_EMPTY_RESOURCE(URES_BINARY);
1051            res->fWritten = TRUE;
1052        }
1053    }
1054
1055    return res;
1056}
1057
1058struct SRBRoot *bundle_open(const struct UString* comment, UBool isPoolBundle, UErrorCode *status) {
1059    struct SRBRoot *bundle;
1060
1061    if (U_FAILURE(*status)) {
1062        return NULL;
1063    }
1064
1065    bundle = (struct SRBRoot *) uprv_malloc(sizeof(struct SRBRoot));
1066    if (bundle == NULL) {
1067        *status = U_MEMORY_ALLOCATION_ERROR;
1068        return 0;
1069    }
1070    uprv_memset(bundle, 0, sizeof(struct SRBRoot));
1071
1072    bundle->fKeys = (char *) uprv_malloc(sizeof(char) * KEY_SPACE_SIZE);
1073    bundle->fRoot = table_open(bundle, NULL, comment, status);
1074    if (bundle->fKeys == NULL || bundle->fRoot == NULL || U_FAILURE(*status)) {
1075        if (U_SUCCESS(*status)) {
1076            *status = U_MEMORY_ALLOCATION_ERROR;
1077        }
1078        bundle_close(bundle, status);
1079        return NULL;
1080    }
1081
1082    bundle->fLocale   = NULL;
1083    bundle->fKeysCapacity = KEY_SPACE_SIZE;
1084    /* formatVersion 1.1: start fKeysTop after the root item and indexes[] */
1085    bundle->fIsPoolBundle = isPoolBundle;
1086    if (gUsePoolBundle || isPoolBundle) {
1087        bundle->fIndexLength = URES_INDEX_POOL_CHECKSUM + 1;
1088    } else if (gFormatVersion >= 2) {
1089        bundle->fIndexLength = URES_INDEX_16BIT_TOP + 1;
1090    } else /* formatVersion 1 */ {
1091        bundle->fIndexLength = URES_INDEX_ATTRIBUTES + 1;
1092    }
1093    bundle->fKeysBottom = (1 /* root */ + bundle->fIndexLength) * 4;
1094    uprv_memset(bundle->fKeys, 0, bundle->fKeysBottom);
1095    bundle->fKeysTop = bundle->fKeysBottom;
1096
1097    if (gFormatVersion == 1) {
1098        bundle->fStringsForm = STRINGS_UTF16_V1;
1099    } else {
1100        bundle->fStringsForm = STRINGS_UTF16_V2;
1101    }
1102
1103    return bundle;
1104}
1105
1106/* Closing Functions */
1107static void table_close(struct SResource *table) {
1108    struct SResource *current = NULL;
1109    struct SResource *prev    = NULL;
1110
1111    current = table->u.fTable.fFirst;
1112
1113    while (current != NULL) {
1114        prev    = current;
1115        current = current->fNext;
1116
1117        res_close(prev);
1118    }
1119
1120    table->u.fTable.fFirst = NULL;
1121}
1122
1123static void array_close(struct SResource *array) {
1124    struct SResource *current = NULL;
1125    struct SResource *prev    = NULL;
1126
1127    if(array==NULL){
1128        return;
1129    }
1130    current = array->u.fArray.fFirst;
1131
1132    while (current != NULL) {
1133        prev    = current;
1134        current = current->fNext;
1135
1136        res_close(prev);
1137    }
1138    array->u.fArray.fFirst = NULL;
1139}
1140
1141static void string_close(struct SResource *string) {
1142    if (string->u.fString.fChars != NULL &&
1143        string->u.fString.fChars != &gEmptyString &&
1144        string->u.fString.fSame == NULL
1145    ) {
1146        uprv_free(string->u.fString.fChars);
1147        string->u.fString.fChars =NULL;
1148    }
1149}
1150
1151static void alias_close(struct SResource *alias) {
1152    if (alias->u.fString.fChars != NULL) {
1153        uprv_free(alias->u.fString.fChars);
1154        alias->u.fString.fChars =NULL;
1155    }
1156}
1157
1158static void intvector_close(struct SResource *intvector) {
1159    if (intvector->u.fIntVector.fArray != NULL) {
1160        uprv_free(intvector->u.fIntVector.fArray);
1161        intvector->u.fIntVector.fArray =NULL;
1162    }
1163}
1164
1165static void int_close(struct SResource *intres) {
1166    /* Intentionally left blank */
1167}
1168
1169static void bin_close(struct SResource *binres) {
1170    if (binres->u.fBinaryValue.fData != NULL) {
1171        uprv_free(binres->u.fBinaryValue.fData);
1172        binres->u.fBinaryValue.fData = NULL;
1173    }
1174}
1175
1176void res_close(struct SResource *res) {
1177    if (res != NULL) {
1178        switch(res->fType) {
1179        case URES_STRING:
1180            string_close(res);
1181            break;
1182        case URES_ALIAS:
1183            alias_close(res);
1184            break;
1185        case URES_INT_VECTOR:
1186            intvector_close(res);
1187            break;
1188        case URES_BINARY:
1189            bin_close(res);
1190            break;
1191        case URES_INT:
1192            int_close(res);
1193            break;
1194        case URES_ARRAY:
1195            array_close(res);
1196            break;
1197        case URES_TABLE:
1198            table_close(res);
1199            break;
1200        default:
1201            /* Shouldn't happen */
1202            break;
1203        }
1204
1205        ustr_deinit(&res->fComment);
1206        uprv_free(res);
1207    }
1208}
1209
1210void bundle_close(struct SRBRoot *bundle, UErrorCode *status) {
1211    res_close(bundle->fRoot);
1212    uprv_free(bundle->fLocale);
1213    uprv_free(bundle->fKeys);
1214    uprv_free(bundle->fKeyMap);
1215    uhash_close(bundle->fStringSet);
1216    uprv_free(bundle->f16BitUnits);
1217    uprv_free(bundle);
1218}
1219
1220void bundle_closeString(struct SRBRoot *bundle, struct SResource *string) {
1221    if (bundle->fStringSet != NULL) {
1222        uhash_remove(bundle->fStringSet, string);
1223    }
1224    string_close(string);
1225}
1226
1227/* Adding Functions */
1228void table_add(struct SResource *table, struct SResource *res, int linenumber, UErrorCode *status) {
1229    struct SResource *current = NULL;
1230    struct SResource *prev    = NULL;
1231    struct SResTable *list;
1232    const char *resKeyString;
1233
1234    if (U_FAILURE(*status)) {
1235        return;
1236    }
1237    if (res == &kNoResource) {
1238        return;
1239    }
1240
1241    /* remember this linenumber to report to the user if there is a duplicate key */
1242    res->line = linenumber;
1243
1244    /* here we need to traverse the list */
1245    list = &(table->u.fTable);
1246    ++(list->fCount);
1247
1248    /* is list still empty? */
1249    if (list->fFirst == NULL) {
1250        list->fFirst = res;
1251        res->fNext   = NULL;
1252        return;
1253    }
1254
1255    resKeyString = list->fRoot->fKeys + res->fKey;
1256
1257    current = list->fFirst;
1258
1259    while (current != NULL) {
1260        const char *currentKeyString = list->fRoot->fKeys + current->fKey;
1261        int diff;
1262        /*
1263         * formatVersion 1: compare key strings in native-charset order
1264         * formatVersion 2 and up: compare key strings in ASCII order
1265         */
1266        if (gFormatVersion == 1 || U_CHARSET_FAMILY == U_ASCII_FAMILY) {
1267            diff = uprv_strcmp(currentKeyString, resKeyString);
1268        } else {
1269            diff = uprv_compareInvCharsAsAscii(currentKeyString, resKeyString);
1270        }
1271        if (diff < 0) {
1272            prev    = current;
1273            current = current->fNext;
1274        } else if (diff > 0) {
1275            /* we're either in front of list, or in middle */
1276            if (prev == NULL) {
1277                /* front of the list */
1278                list->fFirst = res;
1279            } else {
1280                /* middle of the list */
1281                prev->fNext = res;
1282            }
1283
1284            res->fNext = current;
1285            return;
1286        } else {
1287            /* Key already exists! ERROR! */
1288            error(linenumber, "duplicate key '%s' in table, first appeared at line %d", currentKeyString, current->line);
1289            *status = U_UNSUPPORTED_ERROR;
1290            return;
1291        }
1292    }
1293
1294    /* end of list */
1295    prev->fNext = res;
1296    res->fNext  = NULL;
1297}
1298
1299void array_add(struct SResource *array, struct SResource *res, UErrorCode *status) {
1300    if (U_FAILURE(*status)) {
1301        return;
1302    }
1303
1304    if (array->u.fArray.fFirst == NULL) {
1305        array->u.fArray.fFirst = res;
1306        array->u.fArray.fLast  = res;
1307    } else {
1308        array->u.fArray.fLast->fNext = res;
1309        array->u.fArray.fLast        = res;
1310    }
1311
1312    (array->u.fArray.fCount)++;
1313}
1314
1315void intvector_add(struct SResource *intvector, int32_t value, UErrorCode *status) {
1316    if (U_FAILURE(*status)) {
1317        return;
1318    }
1319
1320    *(intvector->u.fIntVector.fArray + intvector->u.fIntVector.fCount) = value;
1321    intvector->u.fIntVector.fCount++;
1322}
1323
1324/* Misc Functions */
1325
1326void bundle_setlocale(struct SRBRoot *bundle, UChar *locale, UErrorCode *status) {
1327
1328    if(U_FAILURE(*status)) {
1329        return;
1330    }
1331
1332    if (bundle->fLocale!=NULL) {
1333        uprv_free(bundle->fLocale);
1334    }
1335
1336    bundle->fLocale= (char*) uprv_malloc(sizeof(char) * (u_strlen(locale)+1));
1337
1338    if(bundle->fLocale == NULL) {
1339        *status = U_MEMORY_ALLOCATION_ERROR;
1340        return;
1341    }
1342
1343    /*u_strcpy(bundle->fLocale, locale);*/
1344    u_UCharsToChars(locale, bundle->fLocale, u_strlen(locale)+1);
1345
1346}
1347
1348static const char *
1349getKeyString(const struct SRBRoot *bundle, int32_t key) {
1350    if (key < 0) {
1351        return bundle->fPoolBundleKeys + (key & 0x7fffffff);
1352    } else {
1353        return bundle->fKeys + key;
1354    }
1355}
1356
1357const char *
1358res_getKeyString(const struct SRBRoot *bundle, const struct SResource *res, char temp[8]) {
1359    if (res->fKey == -1) {
1360        return NULL;
1361    }
1362    return getKeyString(bundle, res->fKey);
1363}
1364
1365const char *
1366bundle_getKeyBytes(struct SRBRoot *bundle, int32_t *pLength) {
1367    *pLength = bundle->fKeysTop - bundle->fKeysBottom;
1368    return bundle->fKeys + bundle->fKeysBottom;
1369}
1370
1371int32_t
1372bundle_addKeyBytes(struct SRBRoot *bundle, const char *keyBytes, int32_t length, UErrorCode *status) {
1373    int32_t keypos;
1374
1375    if (U_FAILURE(*status)) {
1376        return -1;
1377    }
1378    if (length < 0 || (keyBytes == NULL && length != 0)) {
1379        *status = U_ILLEGAL_ARGUMENT_ERROR;
1380        return -1;
1381    }
1382    if (length == 0) {
1383        return bundle->fKeysTop;
1384    }
1385
1386    keypos = bundle->fKeysTop;
1387    bundle->fKeysTop += length;
1388    if (bundle->fKeysTop >= bundle->fKeysCapacity) {
1389        /* overflow - resize the keys buffer */
1390        bundle->fKeysCapacity += KEY_SPACE_SIZE;
1391        bundle->fKeys = uprv_realloc(bundle->fKeys, bundle->fKeysCapacity);
1392        if(bundle->fKeys == NULL) {
1393            *status = U_MEMORY_ALLOCATION_ERROR;
1394            return -1;
1395        }
1396    }
1397
1398    uprv_memcpy(bundle->fKeys + keypos, keyBytes, length);
1399
1400    return keypos;
1401}
1402
1403int32_t
1404bundle_addtag(struct SRBRoot *bundle, const char *tag, UErrorCode *status) {
1405    int32_t keypos;
1406
1407    if (U_FAILURE(*status)) {
1408        return -1;
1409    }
1410
1411    if (tag == NULL) {
1412        /* no error: the root table and array items have no keys */
1413        return -1;
1414    }
1415
1416    keypos = bundle_addKeyBytes(bundle, tag, (int32_t)(uprv_strlen(tag) + 1), status);
1417    if (U_SUCCESS(*status)) {
1418        ++bundle->fKeysCount;
1419    }
1420    return keypos;
1421}
1422
1423static int32_t
1424compareInt32(int32_t lPos, int32_t rPos) {
1425    /*
1426     * Compare possibly-negative key offsets. Don't just return lPos - rPos
1427     * because that is prone to negative-integer underflows.
1428     */
1429    if (lPos < rPos) {
1430        return -1;
1431    } else if (lPos > rPos) {
1432        return 1;
1433    } else {
1434        return 0;
1435    }
1436}
1437
1438static int32_t U_CALLCONV
1439compareKeySuffixes(const void *context, const void *l, const void *r) {
1440    const struct SRBRoot *bundle=(const struct SRBRoot *)context;
1441    int32_t lPos = ((const KeyMapEntry *)l)->oldpos;
1442    int32_t rPos = ((const KeyMapEntry *)r)->oldpos;
1443    const char *lStart = getKeyString(bundle, lPos);
1444    const char *lLimit = lStart;
1445    const char *rStart = getKeyString(bundle, rPos);
1446    const char *rLimit = rStart;
1447    int32_t diff;
1448    while (*lLimit != 0) { ++lLimit; }
1449    while (*rLimit != 0) { ++rLimit; }
1450    /* compare keys in reverse character order */
1451    while (lStart < lLimit && rStart < rLimit) {
1452        diff = (int32_t)(uint8_t)*--lLimit - (int32_t)(uint8_t)*--rLimit;
1453        if (diff != 0) {
1454            return diff;
1455        }
1456    }
1457    /* sort equal suffixes by descending key length */
1458    diff = (int32_t)(rLimit - rStart) - (int32_t)(lLimit - lStart);
1459    if (diff != 0) {
1460        return diff;
1461    }
1462    /* Sort pool bundle keys first (negative oldpos), and otherwise keys in parsing order. */
1463    return compareInt32(lPos, rPos);
1464}
1465
1466static int32_t U_CALLCONV
1467compareKeyNewpos(const void *context, const void *l, const void *r) {
1468    return compareInt32(((const KeyMapEntry *)l)->newpos, ((const KeyMapEntry *)r)->newpos);
1469}
1470
1471static int32_t U_CALLCONV
1472compareKeyOldpos(const void *context, const void *l, const void *r) {
1473    return compareInt32(((const KeyMapEntry *)l)->oldpos, ((const KeyMapEntry *)r)->oldpos);
1474}
1475
1476void
1477bundle_compactKeys(struct SRBRoot *bundle, UErrorCode *status) {
1478    KeyMapEntry *map;
1479    char *keys;
1480    int32_t i;
1481    int32_t keysCount = bundle->fPoolBundleKeysCount + bundle->fKeysCount;
1482    if (U_FAILURE(*status) || bundle->fKeysCount == 0 || bundle->fKeyMap != NULL) {
1483        return;
1484    }
1485    map = (KeyMapEntry *)uprv_malloc(keysCount * sizeof(KeyMapEntry));
1486    if (map == NULL) {
1487        *status = U_MEMORY_ALLOCATION_ERROR;
1488        return;
1489    }
1490    keys = (char *)bundle->fPoolBundleKeys;
1491    for (i = 0; i < bundle->fPoolBundleKeysCount; ++i) {
1492        map[i].oldpos =
1493            (int32_t)(keys - bundle->fPoolBundleKeys) | 0x80000000;  /* negative oldpos */
1494        map[i].newpos = 0;
1495        while (*keys != 0) { ++keys; }  /* skip the key */
1496        ++keys;  /* skip the NUL */
1497    }
1498    keys = bundle->fKeys + bundle->fKeysBottom;
1499    for (; i < keysCount; ++i) {
1500        map[i].oldpos = (int32_t)(keys - bundle->fKeys);
1501        map[i].newpos = 0;
1502        while (*keys != 0) { ++keys; }  /* skip the key */
1503        ++keys;  /* skip the NUL */
1504    }
1505    /* Sort the keys so that each one is immediately followed by all of its suffixes. */
1506    uprv_sortArray(map, keysCount, (int32_t)sizeof(KeyMapEntry),
1507                   compareKeySuffixes, bundle, FALSE, status);
1508    /*
1509     * Make suffixes point into earlier, longer strings that contain them
1510     * and mark the old, now unused suffix bytes as deleted.
1511     */
1512    if (U_SUCCESS(*status)) {
1513        keys = bundle->fKeys;
1514        for (i = 0; i < keysCount;) {
1515            /*
1516             * This key is not a suffix of the previous one;
1517             * keep this one and delete the following ones that are
1518             * suffixes of this one.
1519             */
1520            const char *key;
1521            const char *keyLimit;
1522            int32_t j = i + 1;
1523            map[i].newpos = map[i].oldpos;
1524            if (j < keysCount && map[j].oldpos < 0) {
1525                /* Key string from the pool bundle, do not delete. */
1526                i = j;
1527                continue;
1528            }
1529            key = getKeyString(bundle, map[i].oldpos);
1530            for (keyLimit = key; *keyLimit != 0; ++keyLimit) {}
1531            for (; j < keysCount && map[j].oldpos >= 0; ++j) {
1532                const char *k;
1533                char *suffix;
1534                const char *suffixLimit;
1535                int32_t offset;
1536                suffix = keys + map[j].oldpos;
1537                for (suffixLimit = suffix; *suffixLimit != 0; ++suffixLimit) {}
1538                offset = (int32_t)(keyLimit - key) - (suffixLimit - suffix);
1539                if (offset < 0) {
1540                    break;  /* suffix cannot be longer than the original */
1541                }
1542                /* Is it a suffix of the earlier, longer key? */
1543                for (k = keyLimit; suffix < suffixLimit && *--k == *--suffixLimit;) {}
1544                if (suffix == suffixLimit && *k == *suffixLimit) {
1545                    map[j].newpos = map[i].oldpos + offset;  /* yes, point to the earlier key */
1546                    /* mark the suffix as deleted */
1547                    while (*suffix != 0) { *suffix++ = 1; }
1548                    *suffix = 1;
1549                } else {
1550                    break;  /* not a suffix, restart from here */
1551                }
1552            }
1553            i = j;
1554        }
1555        /*
1556         * Re-sort by newpos, then modify the key characters array in-place
1557         * to squeeze out unused bytes, and readjust the newpos offsets.
1558         */
1559        uprv_sortArray(map, keysCount, (int32_t)sizeof(KeyMapEntry),
1560                       compareKeyNewpos, NULL, FALSE, status);
1561        if (U_SUCCESS(*status)) {
1562            int32_t oldpos, newpos, limit;
1563            oldpos = newpos = bundle->fKeysBottom;
1564            limit = bundle->fKeysTop;
1565            /* skip key offsets that point into the pool bundle rather than this new bundle */
1566            for (i = 0; i < keysCount && map[i].newpos < 0; ++i) {}
1567            if (i < keysCount) {
1568                while (oldpos < limit) {
1569                    if (keys[oldpos] == 1) {
1570                        ++oldpos;  /* skip unused bytes */
1571                    } else {
1572                        /* adjust the new offsets for keys starting here */
1573                        while (i < keysCount && map[i].newpos == oldpos) {
1574                            map[i++].newpos = newpos;
1575                        }
1576                        /* move the key characters to their new position */
1577                        keys[newpos++] = keys[oldpos++];
1578                    }
1579                }
1580                assert(i == keysCount);
1581            }
1582            bundle->fKeysTop = newpos;
1583            /* Re-sort once more, by old offsets for binary searching. */
1584            uprv_sortArray(map, keysCount, (int32_t)sizeof(KeyMapEntry),
1585                           compareKeyOldpos, NULL, FALSE, status);
1586            if (U_SUCCESS(*status)) {
1587                /* key size reduction by limit - newpos */
1588                bundle->fKeyMap = map;
1589                map = NULL;
1590            }
1591        }
1592    }
1593    uprv_free(map);
1594}
1595
1596static int32_t U_CALLCONV
1597compareStringSuffixes(const void *context, const void *l, const void *r) {
1598    struct SResource *left = *((struct SResource **)l);
1599    struct SResource *right = *((struct SResource **)r);
1600    const UChar *lStart = left->u.fString.fChars;
1601    const UChar *lLimit = lStart + left->u.fString.fLength;
1602    const UChar *rStart = right->u.fString.fChars;
1603    const UChar *rLimit = rStart + right->u.fString.fLength;
1604    int32_t diff;
1605    /* compare keys in reverse character order */
1606    while (lStart < lLimit && rStart < rLimit) {
1607        diff = (int32_t)*--lLimit - (int32_t)*--rLimit;
1608        if (diff != 0) {
1609            return diff;
1610        }
1611    }
1612    /* sort equal suffixes by descending string length */
1613    return right->u.fString.fLength - left->u.fString.fLength;
1614}
1615
1616static int32_t U_CALLCONV
1617compareStringLengths(const void *context, const void *l, const void *r) {
1618    struct SResource *left = *((struct SResource **)l);
1619    struct SResource *right = *((struct SResource **)r);
1620    int32_t diff;
1621    /* Make "is suffix of another string" compare greater than a non-suffix. */
1622    diff = (int)(left->u.fString.fSame != NULL) - (int)(right->u.fString.fSame != NULL);
1623    if (diff != 0) {
1624        return diff;
1625    }
1626    /* sort by ascending string length */
1627    return left->u.fString.fLength - right->u.fString.fLength;
1628}
1629
1630static int32_t
1631string_writeUTF16v2(struct SRBRoot *bundle, struct SResource *res, int32_t utf16Length) {
1632    int32_t length = res->u.fString.fLength;
1633    res->fRes = URES_MAKE_RESOURCE(URES_STRING_V2, utf16Length);
1634    res->fWritten = TRUE;
1635    switch(res->u.fString.fNumCharsForLength) {
1636    case 0:
1637        break;
1638    case 1:
1639        bundle->f16BitUnits[utf16Length++] = (uint16_t)(0xdc00 + length);
1640        break;
1641    case 2:
1642        bundle->f16BitUnits[utf16Length] = (uint16_t)(0xdfef + (length >> 16));
1643        bundle->f16BitUnits[utf16Length + 1] = (uint16_t)length;
1644        utf16Length += 2;
1645        break;
1646    case 3:
1647        bundle->f16BitUnits[utf16Length] = 0xdfff;
1648        bundle->f16BitUnits[utf16Length + 1] = (uint16_t)(length >> 16);
1649        bundle->f16BitUnits[utf16Length + 2] = (uint16_t)length;
1650        utf16Length += 3;
1651        break;
1652    default:
1653        break;  /* will not occur */
1654    }
1655    u_memcpy(bundle->f16BitUnits + utf16Length, res->u.fString.fChars, length + 1);
1656    return utf16Length + length + 1;
1657}
1658
1659static void
1660bundle_compactStrings(struct SRBRoot *bundle, UErrorCode *status) {
1661    if (U_FAILURE(*status)) {
1662        return;
1663    }
1664    switch(bundle->fStringsForm) {
1665    case STRINGS_UTF16_V2:
1666        if (bundle->f16BitUnitsLength > 0) {
1667            struct SResource **array;
1668            int32_t count = uhash_count(bundle->fStringSet);
1669            int32_t i, pos;
1670            /*
1671             * Allocate enough space for the initial NUL and the UTF-16 v2 strings,
1672             * and some extra for URES_TABLE16 and URES_ARRAY16 values.
1673             * Round down to an even number.
1674             */
1675            int32_t utf16Length = (bundle->f16BitUnitsLength + 20000) & ~1;
1676            bundle->f16BitUnits = (UChar *)uprv_malloc(utf16Length * U_SIZEOF_UCHAR);
1677            array = (struct SResource **)uprv_malloc(count * sizeof(struct SResource **));
1678            if (bundle->f16BitUnits == NULL || array == NULL) {
1679                uprv_free(bundle->f16BitUnits);
1680                bundle->f16BitUnits = NULL;
1681                uprv_free(array);
1682                *status = U_MEMORY_ALLOCATION_ERROR;
1683                return;
1684            }
1685            bundle->f16BitUnitsCapacity = utf16Length;
1686            /* insert the initial NUL */
1687            bundle->f16BitUnits[0] = 0;
1688            utf16Length = 1;
1689            ++bundle->f16BitUnitsLength;
1690            for (pos = -1, i = 0; i < count; ++i) {
1691                array[i] = (struct SResource *)uhash_nextElement(bundle->fStringSet, &pos)->key.pointer;
1692            }
1693            /* Sort the strings so that each one is immediately followed by all of its suffixes. */
1694            uprv_sortArray(array, count, (int32_t)sizeof(struct SResource **),
1695                           compareStringSuffixes, NULL, FALSE, status);
1696            /*
1697             * Make suffixes point into earlier, longer strings that contain them.
1698             * Temporarily use fSame and fSuffixOffset for suffix strings to
1699             * refer to the remaining ones.
1700             */
1701            if (U_SUCCESS(*status)) {
1702                for (i = 0; i < count;) {
1703                    /*
1704                     * This string is not a suffix of the previous one;
1705                     * write this one and subsume the following ones that are
1706                     * suffixes of this one.
1707                     */
1708                    struct SResource *res = array[i];
1709                    const UChar *strLimit = res->u.fString.fChars + res->u.fString.fLength;
1710                    int32_t j;
1711                    for (j = i + 1; j < count; ++j) {
1712                        struct SResource *suffixRes = array[j];
1713                        const UChar *s;
1714                        const UChar *suffix = suffixRes->u.fString.fChars;
1715                        const UChar *suffixLimit = suffix + suffixRes->u.fString.fLength;
1716                        int32_t offset = res->u.fString.fLength - suffixRes->u.fString.fLength;
1717                        if (offset < 0) {
1718                            break;  /* suffix cannot be longer than the original */
1719                        }
1720                        /* Is it a suffix of the earlier, longer key? */
1721                        for (s = strLimit; suffix < suffixLimit && *--s == *--suffixLimit;) {}
1722                        if (suffix == suffixLimit && *s == *suffixLimit) {
1723                            if (suffixRes->u.fString.fNumCharsForLength == 0) {
1724                                /* yes, point to the earlier string */
1725                                suffixRes->u.fString.fSame = res;
1726                                suffixRes->u.fString.fSuffixOffset = offset;
1727                            } else {
1728                                /* write the suffix by itself if we need explicit length */
1729                            }
1730                        } else {
1731                            break;  /* not a suffix, restart from here */
1732                        }
1733                    }
1734                    i = j;
1735                }
1736            }
1737            /*
1738             * Re-sort the strings by ascending length (except suffixes last)
1739             * to optimize for URES_TABLE16 and URES_ARRAY16:
1740             * Keep as many as possible within reach of 16-bit offsets.
1741             */
1742            uprv_sortArray(array, count, (int32_t)sizeof(struct SResource **),
1743                           compareStringLengths, NULL, FALSE, status);
1744            if (U_SUCCESS(*status)) {
1745                /* Write the non-suffix strings. */
1746                for (i = 0; i < count && array[i]->u.fString.fSame == NULL; ++i) {
1747                    utf16Length = string_writeUTF16v2(bundle, array[i], utf16Length);
1748                }
1749                /* Write the suffix strings. Make each point to the real string. */
1750                for (; i < count; ++i) {
1751                    struct SResource *res = array[i];
1752                    struct SResource *same = res->u.fString.fSame;
1753                    res->fRes = same->fRes + same->u.fString.fNumCharsForLength + res->u.fString.fSuffixOffset;
1754                    res->u.fString.fSame = NULL;
1755                    res->fWritten = TRUE;
1756                }
1757            }
1758            assert(utf16Length <= bundle->f16BitUnitsLength);
1759            bundle->f16BitUnitsLength = utf16Length;
1760            uprv_free(array);
1761        }
1762        break;
1763    default:
1764        break;
1765    }
1766}
1767