icuSources/common/uresdata.c

   1 /*
   2 *******************************************************************************
   3 *                                                                             *
   4 * Copyright (C) 1999-2011, International Business Machines Corporation        *
   5 *               and others. All Rights Reserved.                              *
   6 *                                                                             *
   7 *******************************************************************************
   8 *   file name:  uresdata.c
   9 *   encoding:   US-ASCII
  10 *   tab size:   8 (not used)
  11 *   indentation:4
  12 *
  13 *   created on: 1999dec08
  14 *   created by: Markus W. Scherer
  15 * Modification History:
  16 *
  17 *   Date        Name        Description
  18 *   06/20/2000  helena      OS/400 port changes; mostly typecast.
  19 *   06/24/02    weiv        Added support for resource sharing
  20 */
  21
  22 #include "unicode/utypes.h"
  23 #include "unicode/udata.h"
  24 #include "unicode/ustring.h"
  25 #include "unicode/utf16.h"
  26 #include "cmemory.h"
  27 #include "cstring.h"
  28 #include "uarrsort.h"
  29 #include "udataswp.h"
  30 #include "ucol_swp.h"
  31 #include "uinvchar.h"
  32 #include "uresdata.h"
  33 #include "uresimp.h"
  34 #include "uassert.h"
  35
  36 #define LENGTHOF(array) (int32_t)(sizeof(array)/sizeof((array)[0]))
  37
  38 /*
  39  * Resource access helpers
  40  */
  41
  42 /* get a const char* pointer to the key with the keyOffset byte offset from pRoot */
  43 #define RES_GET_KEY16(pResData, keyOffset) \
  44     ((keyOffset)<(pResData)->localKeyLimit ? \
  45         (const char *)(pResData)->pRoot+(keyOffset) : \
  46         (pResData)->poolBundleKeys+(keyOffset)-(pResData)->localKeyLimit)
  47
  48 #define RES_GET_KEY32(pResData, keyOffset) \
  49     ((keyOffset)>=0 ? \
  50         (const char *)(pResData)->pRoot+(keyOffset) : \
  51         (pResData)->poolBundleKeys+((keyOffset)&0x7fffffff))
  52
  53 #define URESDATA_ITEM_NOT_FOUND -1
  54
  55 /* empty resources, returned when the resource offset is 0 */
  56 static const uint16_t gEmpty16=0;
  57
  58 static const struct {
  59     int32_t length;
  60     int32_t res;
  61 } gEmpty32={ 0, 0 };
  62
  63 static const struct {
  64     int32_t length;
  65     UChar nul;
  66     UChar pad;
  67 } gEmptyString={ 0, 0, 0 };
  68
  69 /*
  70  * All the type-access functions assume that
  71  * the resource is of the expected type.
  72  */
  73
  74 static int32_t
  75 _res_findTableItem(const ResourceData *pResData, const uint16_t *keyOffsets, int32_t length,
  76                    const char *key, const char **realKey) {
  77     const char *tableKey;
  78     int32_t mid, start, limit;
  79     int result;
  80
  81     /* do a binary search for the key */
  82     start=0;
  83     limit=length;
  84     while(start<limit) {
  85         mid = (start + limit) / 2;
  86         tableKey = RES_GET_KEY16(pResData, keyOffsets[mid]);
  87         if (pResData->useNativeStrcmp) {
  88             result = uprv_strcmp(key, tableKey);
  89         } else {
  90             result = uprv_compareInvCharsAsAscii(key, tableKey);
  91         }
  92         if (result < 0) {
  93             limit = mid;
  94         } else if (result > 0) {
  95             start = mid + 1;
  96         } else {
  97             /* We found it! */
  98             *realKey=tableKey;
  99             return mid;
 100         }
 101     }
 102     return URESDATA_ITEM_NOT_FOUND;  /* not found or table is empty. */
 103 }
 104
 105 static int32_t
 106 _res_findTable32Item(const ResourceData *pResData, const int32_t *keyOffsets, int32_t length,
 107                      const char *key, const char **realKey) {
 108     const char *tableKey;
 109     int32_t mid, start, limit;
 110     int result;
 111
 112     /* do a binary search for the key */
 113     start=0;
 114     limit=length;
 115     while(start<limit) {
 116         mid = (start + limit) / 2;
 117         tableKey = RES_GET_KEY32(pResData, keyOffsets[mid]);
 118         if (pResData->useNativeStrcmp) {
 119             result = uprv_strcmp(key, tableKey);
 120         } else {
 121             result = uprv_compareInvCharsAsAscii(key, tableKey);
 122         }
 123         if (result < 0) {
 124             limit = mid;
 125         } else if (result > 0) {
 126             start = mid + 1;
 127         } else {
 128             /* We found it! */
 129             *realKey=tableKey;
 130             return mid;
 131         }
 132     }
 133     return URESDATA_ITEM_NOT_FOUND;  /* not found or table is empty. */
 134 }
 135
 136 /* helper for res_load() ---------------------------------------------------- */
 137
 138 static UBool U_CALLCONV
 139 isAcceptable(void *context,
 140              const char *type, const char *name,
 141              const UDataInfo *pInfo) {
 142     uprv_memcpy(context, pInfo->formatVersion, 4);
 143     return (UBool)(
 144         pInfo->size>=20 &&
 145         pInfo->isBigEndian==U_IS_BIG_ENDIAN &&
 146         pInfo->charsetFamily==U_CHARSET_FAMILY &&
 147         pInfo->sizeofUChar==U_SIZEOF_UCHAR &&
 148         pInfo->dataFormat[0]==0x52 &&   /* dataFormat="ResB" */
 149         pInfo->dataFormat[1]==0x65 &&
 150         pInfo->dataFormat[2]==0x73 &&
 151         pInfo->dataFormat[3]==0x42 &&
 152         (pInfo->formatVersion[0]==1 || pInfo->formatVersion[0]==2));
 153 }
 154
 155 /* semi-public functions ---------------------------------------------------- */
 156
 157 static void
 158 res_init(ResourceData *pResData,
 159          UVersionInfo formatVersion, const void *inBytes, int32_t length,
 160          UErrorCode *errorCode) {
 161     UResType rootType;
 162
 163     /* get the root resource */
 164     pResData->pRoot=(const int32_t *)inBytes;
 165     pResData->rootRes=(Resource)*pResData->pRoot;
 166     pResData->p16BitUnits=&gEmpty16;
 167
 168     /* formatVersion 1.1 must have a root item and at least 5 indexes */
 169     if(length>=0 && (length/4)<((formatVersion[0]==1 && formatVersion[1]==0) ? 1 : 1+5)) {
 170         *errorCode=U_INVALID_FORMAT_ERROR;
 171         res_unload(pResData);
 172         return;
 173     }
 174
 175     /* currently, we accept only resources that have a Table as their roots */
 176     rootType=RES_GET_TYPE(pResData->rootRes);
 177     if(!URES_IS_TABLE(rootType)) {
 178         *errorCode=U_INVALID_FORMAT_ERROR;
 179         res_unload(pResData);
 180         return;
 181     }
 182
 183     if(formatVersion[0]==1 && formatVersion[1]==0) {
 184         pResData->localKeyLimit=0x10000;  /* greater than any 16-bit key string offset */
 185     } else {
 186         /* bundles with formatVersion 1.1 and later contain an indexes[] array */
 187         const int32_t *indexes=pResData->pRoot+1;
 188         int32_t indexLength=indexes[URES_INDEX_LENGTH]&0xff;
 189         if(indexLength<=URES_INDEX_MAX_TABLE_LENGTH) {
 190             *errorCode=U_INVALID_FORMAT_ERROR;
 191             res_unload(pResData);
 192             return;
 193         }
 194         if( length>=0 &&
 195             (length<((1+indexLength)<<2) ||
 196              length<(indexes[URES_INDEX_BUNDLE_TOP]<<2))
 197         ) {
 198             *errorCode=U_INVALID_FORMAT_ERROR;
 199             res_unload(pResData);
 200             return;
 201         }
 202         if(indexes[URES_INDEX_KEYS_TOP]>(1+indexLength)) {
 203             pResData->localKeyLimit=indexes[URES_INDEX_KEYS_TOP]<<2;
 204         }
 205         if(indexLength>URES_INDEX_ATTRIBUTES) {
 206             int32_t att=indexes[URES_INDEX_ATTRIBUTES];
 207             pResData->noFallback=(UBool)(att&URES_ATT_NO_FALLBACK);
 208             pResData->isPoolBundle=(UBool)((att&URES_ATT_IS_POOL_BUNDLE)!=0);
 209             pResData->usesPoolBundle=(UBool)((att&URES_ATT_USES_POOL_BUNDLE)!=0);
 210         }
 211         if((pResData->isPoolBundle || pResData->usesPoolBundle) && indexLength<=URES_INDEX_POOL_CHECKSUM) {
 212             *errorCode=U_INVALID_FORMAT_ERROR;
 213             res_unload(pResData);
 214             return;
 215         }
 216         if( indexLength>URES_INDEX_16BIT_TOP &&
 217             indexes[URES_INDEX_16BIT_TOP]>indexes[URES_INDEX_KEYS_TOP]
 218         ) {
 219             pResData->p16BitUnits=(const uint16_t *)(pResData->pRoot+indexes[URES_INDEX_KEYS_TOP]);
 220         }
 221     }
 222
 223     if(formatVersion[0]==1 || U_CHARSET_FAMILY==U_ASCII_FAMILY) {
 224         /*
 225          * formatVersion 1: compare key strings in native-charset order
 226          * formatVersion 2 and up: compare key strings in ASCII order
 227          */
 228         pResData->useNativeStrcmp=TRUE;
 229     }
 230 }
 231
 232 U_CAPI void U_EXPORT2
 233 res_read(ResourceData *pResData,
 234          const UDataInfo *pInfo, const void *inBytes, int32_t length,
 235          UErrorCode *errorCode) {
 236     UVersionInfo formatVersion;
 237
 238     uprv_memset(pResData, 0, sizeof(ResourceData));
 239     if(U_FAILURE(*errorCode)) {
 240         return;
 241     }
 242     if(!isAcceptable(formatVersion, NULL, NULL, pInfo)) {
 243         *errorCode=U_INVALID_FORMAT_ERROR;
 244         return;
 245     }
 246     res_init(pResData, formatVersion, inBytes, length, errorCode);
 247 }
 248
 249 U_CFUNC void
 250 res_load(ResourceData *pResData,
 251          const char *path, const char *name, UErrorCode *errorCode) {
 252     UVersionInfo formatVersion;
 253
 254     uprv_memset(pResData, 0, sizeof(ResourceData));
 255
 256     /* load the ResourceBundle file */
 257     pResData->data=udata_openChoice(path, "res", name, isAcceptable, formatVersion, errorCode);
 258     if(U_FAILURE(*errorCode)) {
 259         return;
 260     }
 261
 262     /* get its memory and initialize *pResData */
 263     res_init(pResData, formatVersion, udata_getMemory(pResData->data), -1, errorCode);
 264 }
 265
 266 U_CFUNC void
 267 res_unload(ResourceData *pResData) {
 268     if(pResData->data!=NULL) {
 269         udata_close(pResData->data);
 270         pResData->data=NULL;
 271     }
 272 }
 273
 274 static const int8_t gPublicTypes[URES_LIMIT] = {
 275     URES_STRING,
 276     URES_BINARY,
 277     URES_TABLE,
 278     URES_ALIAS,
 279
 280     URES_TABLE,     /* URES_TABLE32 */
 281     URES_TABLE,     /* URES_TABLE16 */
 282     URES_STRING,    /* URES_STRING_V2 */
 283     URES_INT,
 284
 285     URES_ARRAY,
 286     URES_ARRAY,     /* URES_ARRAY16 */
 287     URES_NONE,
 288     URES_NONE,
 289
 290     URES_NONE,
 291     URES_NONE,
 292     URES_INT_VECTOR,
 293     URES_NONE
 294 };
 295
 296 U_CAPI UResType U_EXPORT2
 297 res_getPublicType(Resource res) {
 298     return (UResType)gPublicTypes[RES_GET_TYPE(res)];
 299 }
 300
 301 U_CAPI const UChar * U_EXPORT2
 302 res_getString(const ResourceData *pResData, Resource res, int32_t *pLength) {
 303     const UChar *p;
 304     uint32_t offset=RES_GET_OFFSET(res);
 305     int32_t length;
 306     if(RES_GET_TYPE(res)==URES_STRING_V2) {
 307         int32_t first;
 308         p=(const UChar *)(pResData->p16BitUnits+offset);
 309         first=*p;
 310         if(!U16_IS_TRAIL(first)) {
 311             length=u_strlen(p);
 312         } else if(first<0xdfef) {
 313             length=first&0x3ff;
 314             ++p;
 315         } else if(first<0xdfff) {
 316             length=((first-0xdfef)<<16)|p[1];
 317             p+=2;
 318         } else {
 319             length=((int32_t)p[1]<<16)|p[2];
 320             p+=3;
 321         }
 322     } else if(res==offset) /* RES_GET_TYPE(res)==URES_STRING */ {
 323         const int32_t *p32= res==0 ? &gEmptyString.length : pResData->pRoot+res;
 324         length=*p32++;
 325         p=(const UChar *)p32;
 326     } else {
 327         p=NULL;
 328         length=0;
 329     }
 330     if(pLength) {
 331         *pLength=length;
 332     }
 333     return p;
 334 }
 335
 336 U_CAPI const UChar * U_EXPORT2
 337 res_getAlias(const ResourceData *pResData, Resource res, int32_t *pLength) {
 338     const UChar *p;
 339     uint32_t offset=RES_GET_OFFSET(res);
 340     int32_t length;
 341     if(RES_GET_TYPE(res)==URES_ALIAS) {
 342         const int32_t *p32= offset==0 ? &gEmptyString.length : pResData->pRoot+offset;
 343         length=*p32++;
 344         p=(const UChar *)p32;
 345     } else {
 346         p=NULL;
 347         length=0;
 348     }
 349     if(pLength) {
 350         *pLength=length;
 351     }
 352     return p;
 353 }
 354
 355 U_CAPI const uint8_t * U_EXPORT2
 356 res_getBinary(const ResourceData *pResData, Resource res, int32_t *pLength) {
 357     const uint8_t *p;
 358     uint32_t offset=RES_GET_OFFSET(res);
 359     int32_t length;
 360     if(RES_GET_TYPE(res)==URES_BINARY) {
 361         const int32_t *p32= offset==0 ? (const int32_t*)&gEmpty32 : pResData->pRoot+offset;
 362         length=*p32++;
 363         p=(const uint8_t *)p32;
 364     } else {
 365         p=NULL;
 366         length=0;
 367     }
 368     if(pLength) {
 369         *pLength=length;
 370     }
 371     return p;
 372 }
 373
 374
 375 U_CAPI const int32_t * U_EXPORT2
 376 res_getIntVector(const ResourceData *pResData, Resource res, int32_t *pLength) {
 377     const int32_t *p;
 378     uint32_t offset=RES_GET_OFFSET(res);
 379     int32_t length;
 380     if(RES_GET_TYPE(res)==URES_INT_VECTOR) {
 381         p= offset==0 ? (const int32_t *)&gEmpty32 : pResData->pRoot+offset;
 382         length=*p++;
 383     } else {
 384         p=NULL;
 385         length=0;
 386     }
 387     if(pLength) {
 388         *pLength=length;
 389     }
 390     return p;
 391 }
 392
 393 U_CAPI int32_t U_EXPORT2
 394 res_countArrayItems(const ResourceData *pResData, Resource res) {
 395     uint32_t offset=RES_GET_OFFSET(res);
 396     switch(RES_GET_TYPE(res)) {
 397     case URES_STRING:
 398     case URES_STRING_V2:
 399     case URES_BINARY:
 400     case URES_ALIAS:
 401     case URES_INT:
 402     case URES_INT_VECTOR:
 403         return 1;
 404     case URES_ARRAY:
 405     case URES_TABLE32:
 406         return offset==0 ? 0 : *(pResData->pRoot+offset);
 407     case URES_TABLE:
 408         return offset==0 ? 0 : *((const uint16_t *)(pResData->pRoot+offset));
 409     case URES_ARRAY16:
 410     case URES_TABLE16:
 411         return pResData->p16BitUnits[offset];
 412     default:
 413         return 0;
 414     }
 415 }
 416
 417 U_CAPI Resource U_EXPORT2
 418 res_getTableItemByKey(const ResourceData *pResData, Resource table,
 419                       int32_t *indexR, const char **key) {
 420     uint32_t offset=RES_GET_OFFSET(table);
 421     int32_t length;
 422     int32_t idx;
 423     if(key == NULL || *key == NULL) {
 424         return RES_BOGUS;
 425     }
 426     switch(RES_GET_TYPE(table)) {
 427     case URES_TABLE: {
 428         if (offset!=0) { /* empty if offset==0 */
 429             const uint16_t *p= (const uint16_t *)(pResData->pRoot+offset);
 430             length=*p++;
 431             *indexR=idx=_res_findTableItem(pResData, p, length, *key, key);
 432             if(idx>=0) {
 433                 const Resource *p32=(const Resource *)(p+length+(~length&1));
 434                 return p32[idx];
 435             }
 436         }
 437         break;
 438     }
 439     case URES_TABLE16: {
 440         const uint16_t *p=pResData->p16BitUnits+offset;
 441         length=*p++;
 442         *indexR=idx=_res_findTableItem(pResData, p, length, *key, key);
 443         if(idx>=0) {
 444             return URES_MAKE_RESOURCE(URES_STRING_V2, p[length+idx]);
 445         }
 446         break;
 447     }
 448     case URES_TABLE32: {
 449         if (offset!=0) { /* empty if offset==0 */
 450             const int32_t *p= pResData->pRoot+offset;
 451             length=*p++;
 452             *indexR=idx=_res_findTable32Item(pResData, p, length, *key, key);
 453             if(idx>=0) {
 454                 return (Resource)p[length+idx];
 455             }
 456         }
 457         break;
 458     }
 459     default:
 460         break;
 461     }
 462     return RES_BOGUS;
 463 }
 464
 465 U_CAPI Resource U_EXPORT2
 466 res_getTableItemByIndex(const ResourceData *pResData, Resource table,
 467                         int32_t indexR, const char **key) {
 468     uint32_t offset=RES_GET_OFFSET(table);
 469     int32_t length;
 470     U_ASSERT(indexR>=0); /* to ensure the index is not negative */
 471     switch(RES_GET_TYPE(table)) {
 472     case URES_TABLE: {
 473         if (offset != 0) { /* empty if offset==0 */
 474             const uint16_t *p= (const uint16_t *)(pResData->pRoot+offset);
 475             length=*p++;
 476             if(indexR<length) {
 477                 const Resource *p32=(const Resource *)(p+length+(~length&1));
 478                 if(key!=NULL) {
 479                     *key=RES_GET_KEY16(pResData, p[indexR]);
 480                 }
 481                 return p32[indexR];
 482             }
 483         }
 484         break;
 485     }
 486     case URES_TABLE16: {
 487         const uint16_t *p=pResData->p16BitUnits+offset;
 488         length=*p++;
 489         if(indexR<length) {
 490             if(key!=NULL) {
 491                 *key=RES_GET_KEY16(pResData, p[indexR]);
 492             }
 493             return URES_MAKE_RESOURCE(URES_STRING_V2, p[length+indexR]);
 494         }
 495         break;
 496     }
 497     case URES_TABLE32: {
 498         if (offset != 0) { /* empty if offset==0 */
 499             const int32_t *p= pResData->pRoot+offset;
 500             length=*p++;
 501             if(indexR<length) {
 502                 if(key!=NULL) {
 503                     *key=RES_GET_KEY32(pResData, p[indexR]);
 504                 }
 505                 return (Resource)p[length+indexR];
 506             }
 507         }
 508         break;
 509     }
 510     default:
 511         break;
 512     }
 513     return RES_BOGUS;
 514 }
 515
 516 U_CAPI Resource U_EXPORT2
 517 res_getResource(const ResourceData *pResData, const char *key) {
 518     const char *realKey=key;
 519     int32_t idx;
 520     return res_getTableItemByKey(pResData, pResData->rootRes, &idx, &realKey);
 521 }
 522
 523 U_CAPI Resource U_EXPORT2
 524 res_getArrayItem(const ResourceData *pResData, Resource array, int32_t indexR) {
 525     uint32_t offset=RES_GET_OFFSET(array);
 526     U_ASSERT(indexR>=0); /* to ensure the index is not negative */
 527     switch(RES_GET_TYPE(array)) {
 528     case URES_ARRAY: {
 529         if (offset!=0) { /* empty if offset==0 */
 530             const int32_t *p= pResData->pRoot+offset;
 531             if(indexR<*p) {
 532                 return (Resource)p[1+indexR];
 533             }
 534         }
 535         break;
 536     }
 537     case URES_ARRAY16: {
 538         const uint16_t *p=pResData->p16BitUnits+offset;
 539         if(indexR<*p) {
 540             return URES_MAKE_RESOURCE(URES_STRING_V2, p[1+indexR]);
 541         }
 542         break;
 543     }
 544     default:
 545         break;
 546     }
 547     return RES_BOGUS;
 548 }
 549
 550 U_CFUNC Resource
 551 res_findResource(const ResourceData *pResData, Resource r, char** path, const char** key) {
 552   /* we pass in a path. CollationElements/Sequence or zoneStrings/3/2 etc.
 553    * iterates over a path and stops when a scalar resource is found. This
 554    * CAN be an alias. Path gets set to the part that has not yet been processed.
 555    */
 556
 557   char *pathP = *path, *nextSepP = *path;
 558   char *closeIndex = NULL;
 559   Resource t1 = r;
 560   Resource t2;
 561   int32_t indexR = 0;
 562   UResType type = RES_GET_TYPE(t1);
 563
 564   /* if you come in with an empty path, you'll be getting back the same resource */
 565   if(!uprv_strlen(pathP)) {
 566       return r;
 567   }
 568
 569   /* one needs to have an aggregate resource in order to search in it */
 570   if(!URES_IS_CONTAINER(type)) {
 571       return RES_BOGUS;
 572   }
 573
 574   while(nextSepP && *pathP && t1 != RES_BOGUS && URES_IS_CONTAINER(type)) {
 575     /* Iteration stops if: the path has been consumed, we found a non-existing
 576      * resource (t1 == RES_BOGUS) or we found a scalar resource (including alias)
 577      */
 578     nextSepP = uprv_strchr(pathP, RES_PATH_SEPARATOR);
 579     /* if there are more separators, terminate string
 580      * and set path to the remaining part of the string
 581      */
 582     if(nextSepP != NULL) {
 583       *nextSepP = 0; /* overwrite the separator with a NUL to terminate the key */
 584       *path = nextSepP+1;
 585     } else {
 586       *path = uprv_strchr(pathP, 0);
 587     }
 588
 589     /* if the resource is a table */
 590     /* try the key based access */
 591     if(URES_IS_TABLE(type)) {
 592       *key = pathP;
 593       t2 = res_getTableItemByKey(pResData, t1, &indexR, key);
 594       if(t2 == RES_BOGUS) {
 595         /* if we fail to get the resource by key, maybe we got an index */
 596         indexR = uprv_strtol(pathP, &closeIndex, 10);
 597         if(closeIndex != pathP) {
 598           /* if we indeed have an index, try to get the item by index */
 599           t2 = res_getTableItemByIndex(pResData, t1, indexR, key);
 600         }
 601       }
 602     } else if(URES_IS_ARRAY(type)) {
 603       indexR = uprv_strtol(pathP, &closeIndex, 10);
 604       if(closeIndex != pathP) {
 605         t2 = res_getArrayItem(pResData, t1, indexR);
 606       } else {
 607         t2 = RES_BOGUS; /* have an array, but don't have a valid index */
 608       }
 609       *key = NULL;
 610     } else { /* can't do much here, except setting t2 to bogus */
 611       t2 = RES_BOGUS;
 612     }
 613     t1 = t2;
 614     type = RES_GET_TYPE(t1);
 615     /* position pathP to next resource key/index */
 616     pathP = *path;
 617   }
 618
 619   return t1;
 620 }
 621
 622 /* resource bundle swapping ------------------------------------------------- */
 623
 624 /*
 625  * Need to always enumerate the entire item tree,
 626  * track the lowest address of any item to use as the limit for char keys[],
 627  * track the highest address of any item to return the size of the data.
 628  *
 629  * We should have thought of storing those in the data...
 630  * It is possible to extend the data structure by putting additional values
 631  * in places that are inaccessible by ordinary enumeration of the item tree.
 632  * For example, additional integers could be stored at the beginning or
 633  * end of the key strings; this could be indicated by a minor version number,
 634  * and the data swapping would have to know about these values.
 635  *
 636  * The data structure does not forbid keys to be shared, so we must swap
 637  * all keys once instead of each key when it is referenced.
 638  *
 639  * These swapping functions assume that a resource bundle always has a length
 640  * that is a multiple of 4 bytes.
 641  * Currently, this is trivially true because genrb writes bundle tree leaves
 642  * physically first, before their branches, so that the root table with its
 643  * array of resource items (uint32_t values) is always last.
 644  */
 645
 646 /* definitions for table sorting ------------------------ */
 647
 648 /*
 649  * row of a temporary array
 650  *
 651  * gets platform-endian key string indexes and sorting indexes;
 652  * after sorting this array by keys, the actual key/value arrays are permutated
 653  * according to the sorting indexes
 654  */
 655 typedef struct Row {
 656     int32_t keyIndex, sortIndex;
 657 } Row;
 658
 659 static int32_t
 660 ures_compareRows(const void *context, const void *left, const void *right) {
 661     const char *keyChars=(const char *)context;
 662     return (int32_t)uprv_strcmp(keyChars+((const Row *)left)->keyIndex,
 663                                 keyChars+((const Row *)right)->keyIndex);
 664 }
 665
 666 typedef struct TempTable {
 667     const char *keyChars;
 668     Row *rows;
 669     int32_t *resort;
 670     uint32_t *resFlags;
 671     int32_t localKeyLimit;
 672     uint8_t majorFormatVersion;
 673 } TempTable;
 674
 675 enum {
 676     STACK_ROW_CAPACITY=200
 677 };
 678
 679 /* The table item key string is not locally available. */
 680 static const char *const gUnknownKey="";
 681
 682 /* resource table key for collation binaries: "%%CollationBin" */
 683 static const UChar gCollationBinKey[]={
 684     0x25, 0x25,
 685     0x43, 0x6f, 0x6c, 0x6c, 0x61, 0x74, 0x69, 0x6f, 0x6e,
 686     0x42, 0x69, 0x6e,
 687     0
 688 };
 689
 690 /*
 691  * swap one resource item
 692  */
 693 static void
 694 ures_swapResource(const UDataSwapper *ds,
 695                   const Resource *inBundle, Resource *outBundle,
 696                   Resource res, /* caller swaps res itself */
 697                   const char *key,
 698                   TempTable *pTempTable,
 699                   UErrorCode *pErrorCode) {
 700     const Resource *p;
 701     Resource *q;
 702     int32_t offset, count;
 703
 704     switch(RES_GET_TYPE(res)) {
 705     case URES_TABLE16:
 706     case URES_STRING_V2:
 707     case URES_INT:
 708     case URES_ARRAY16:
 709         /* integer, or points to 16-bit units, nothing to do here */
 710         return;
 711     default:
 712         break;
 713     }
 714
 715     /* all other types use an offset to point to their data */
 716     offset=(int32_t)RES_GET_OFFSET(res);
 717     if(offset==0) {
 718         /* special offset indicating an empty item */
 719         return;
 720     }
 721     if(pTempTable->resFlags[offset>>5]&((uint32_t)1<<(offset&0x1f))) {
 722         /* we already swapped this resource item */
 723         return;
 724     } else {
 725         /* mark it as swapped now */
 726         pTempTable->resFlags[offset>>5]|=((uint32_t)1<<(offset&0x1f));
 727     }
 728
 729     p=inBundle+offset;
 730     q=outBundle+offset;
 731
 732     switch(RES_GET_TYPE(res)) {
 733     case URES_ALIAS:
 734         /* physically same value layout as string, fall through */
 735     case URES_STRING:
 736         count=udata_readInt32(ds, (int32_t)*p);
 737         /* swap length */
 738         ds->swapArray32(ds, p, 4, q, pErrorCode);
 739         /* swap each UChar (the terminating NUL would not change) */
 740         ds->swapArray16(ds, p+1, 2*count, q+1, pErrorCode);
 741         break;
 742     case URES_BINARY:
 743         count=udata_readInt32(ds, (int32_t)*p);
 744         /* swap length */
 745         ds->swapArray32(ds, p, 4, q, pErrorCode);
 746         /* no need to swap or copy bytes - ures_swap() copied them all */
 747
 748         /* swap known formats */
 749 #if !UCONFIG_NO_COLLATION
 750         if( key!=NULL &&  /* the binary is in a table */
 751             (key!=gUnknownKey ?
 752                 /* its table key string is "%%CollationBin" */
 753                 0==ds->compareInvChars(ds, key, -1,
 754                                        gCollationBinKey, LENGTHOF(gCollationBinKey)-1) :
 755                 /* its table key string is unknown but it looks like a collation binary */
 756                 ucol_looksLikeCollationBinary(ds, p+1, count))
 757         ) {
 758             ucol_swapBinary(ds, p+1, count, q+1, pErrorCode);
 759         }
 760 #endif
 761         break;
 762     case URES_TABLE:
 763     case URES_TABLE32:
 764         {
 765             const uint16_t *pKey16;
 766             uint16_t *qKey16;
 767
 768             const int32_t *pKey32;
 769             int32_t *qKey32;
 770
 771             Resource item;
 772             int32_t i, oldIndex;
 773
 774             if(RES_GET_TYPE(res)==URES_TABLE) {
 775                 /* get table item count */
 776                 pKey16=(const uint16_t *)p;
 777                 qKey16=(uint16_t *)q;
 778                 count=ds->readUInt16(*pKey16);
 779
 780                 pKey32=qKey32=NULL;
 781
 782                 /* swap count */
 783                 ds->swapArray16(ds, pKey16++, 2, qKey16++, pErrorCode);
 784
 785                 offset+=((1+count)+1)/2;
 786             } else {
 787                 /* get table item count */
 788                 pKey32=(const int32_t *)p;
 789                 qKey32=(int32_t *)q;
 790                 count=udata_readInt32(ds, *pKey32);
 791
 792                 pKey16=qKey16=NULL;
 793
 794                 /* swap count */
 795                 ds->swapArray32(ds, pKey32++, 4, qKey32++, pErrorCode);
 796
 797                 offset+=1+count;
 798             }
 799
 800             if(count==0) {
 801                 break;
 802             }
 803
 804             p=inBundle+offset; /* pointer to table resources */
 805             q=outBundle+offset;
 806
 807             /* recurse */
 808             for(i=0; i<count; ++i) {
 809                 const char *itemKey=gUnknownKey;
 810                 if(pKey16!=NULL) {
 811                     int32_t keyOffset=ds->readUInt16(pKey16[i]);
 812                     if(keyOffset<pTempTable->localKeyLimit) {
 813                         itemKey=(const char *)outBundle+keyOffset;
 814                     }
 815                 } else {
 816                     int32_t keyOffset=udata_readInt32(ds, pKey32[i]);
 817                     if(keyOffset>=0) {
 818                         itemKey=(const char *)outBundle+keyOffset;
 819                     }
 820                 }
 821                 item=ds->readUInt32(p[i]);
 822                 ures_swapResource(ds, inBundle, outBundle, item, itemKey, pTempTable, pErrorCode);
 823                 if(U_FAILURE(*pErrorCode)) {
 824                     udata_printError(ds, "ures_swapResource(table res=%08x)[%d].recurse(%08x) failed\n",
 825                                      res, i, item);
 826                     return;
 827                 }
 828             }
 829
 830             if(pTempTable->majorFormatVersion>1 || ds->inCharset==ds->outCharset) {
 831                 /* no need to sort, just swap the offset/value arrays */
 832                 if(pKey16!=NULL) {
 833                     ds->swapArray16(ds, pKey16, count*2, qKey16, pErrorCode);
 834                     ds->swapArray32(ds, p, count*4, q, pErrorCode);
 835                 } else {
 836                     /* swap key offsets and items as one array */
 837                     ds->swapArray32(ds, pKey32, count*2*4, qKey32, pErrorCode);
 838                 }
 839                 break;
 840             }
 841
 842             /*
 843              * We need to sort tables by outCharset key strings because they
 844              * sort differently for different charset families.
 845              * ures_swap() already set pTempTable->keyChars appropriately.
 846              * First we set up a temporary table with the key indexes and
 847              * sorting indexes and sort that.
 848              * Then we permutate and copy/swap the actual values.
 849              */
 850             if(pKey16!=NULL) {
 851                 for(i=0; i<count; ++i) {
 852                     pTempTable->rows[i].keyIndex=ds->readUInt16(pKey16[i]);
 853                     pTempTable->rows[i].sortIndex=i;
 854                 }
 855             } else {
 856                 for(i=0; i<count; ++i) {
 857                     pTempTable->rows[i].keyIndex=udata_readInt32(ds, pKey32[i]);
 858                     pTempTable->rows[i].sortIndex=i;
 859                 }
 860             }
 861             uprv_sortArray(pTempTable->rows, count, sizeof(Row),
 862                            ures_compareRows, pTempTable->keyChars,
 863                            FALSE, pErrorCode);
 864             if(U_FAILURE(*pErrorCode)) {
 865                 udata_printError(ds, "ures_swapResource(table res=%08x).uprv_sortArray(%d items) failed\n",
 866                                  res, count);
 867                 return;
 868             }
 869
 870             /*
 871              * copy/swap/permutate items
 872              *
 873              * If we swap in-place, then the permutation must use another
 874              * temporary array (pTempTable->resort)
 875              * before the results are copied to the outBundle.
 876              */
 877             /* keys */
 878             if(pKey16!=NULL) {
 879                 uint16_t *rKey16;
 880
 881                 if(pKey16!=qKey16) {
 882                     rKey16=qKey16;
 883                 } else {
 884                     rKey16=(uint16_t *)pTempTable->resort;
 885                 }
 886                 for(i=0; i<count; ++i) {
 887                     oldIndex=pTempTable->rows[i].sortIndex;
 888                     ds->swapArray16(ds, pKey16+oldIndex, 2, rKey16+i, pErrorCode);
 889                 }
 890                 if(qKey16!=rKey16) {
 891                     uprv_memcpy(qKey16, rKey16, 2*count);
 892                 }
 893             } else {
 894                 int32_t *rKey32;
 895
 896                 if(pKey32!=qKey32) {
 897                     rKey32=qKey32;
 898                 } else {
 899                     rKey32=pTempTable->resort;
 900                 }
 901                 for(i=0; i<count; ++i) {
 902                     oldIndex=pTempTable->rows[i].sortIndex;
 903                     ds->swapArray32(ds, pKey32+oldIndex, 4, rKey32+i, pErrorCode);
 904                 }
 905                 if(qKey32!=rKey32) {
 906                     uprv_memcpy(qKey32, rKey32, 4*count);
 907                 }
 908             }
 909
 910             /* resources */
 911             {
 912                 Resource *r;
 913
 914
 915                 if(p!=q) {
 916                     r=q;
 917                 } else {
 918                     r=(Resource *)pTempTable->resort;
 919                 }
 920                 for(i=0; i<count; ++i) {
 921                     oldIndex=pTempTable->rows[i].sortIndex;
 922                     ds->swapArray32(ds, p+oldIndex, 4, r+i, pErrorCode);
 923                 }
 924                 if(q!=r) {
 925                     uprv_memcpy(q, r, 4*count);
 926                 }
 927             }
 928         }
 929         break;
 930     case URES_ARRAY:
 931         {
 932             Resource item;
 933             int32_t i;
 934
 935             count=udata_readInt32(ds, (int32_t)*p);
 936             /* swap length */
 937             ds->swapArray32(ds, p++, 4, q++, pErrorCode);
 938
 939             /* recurse */
 940             for(i=0; i<count; ++i) {
 941                 item=ds->readUInt32(p[i]);
 942                 ures_swapResource(ds, inBundle, outBundle, item, NULL, pTempTable, pErrorCode);
 943                 if(U_FAILURE(*pErrorCode)) {
 944                     udata_printError(ds, "ures_swapResource(array res=%08x)[%d].recurse(%08x) failed\n",
 945                                      res, i, item);
 946                     return;
 947                 }
 948             }
 949
 950             /* swap items */
 951             ds->swapArray32(ds, p, 4*count, q, pErrorCode);
 952         }
 953         break;
 954     case URES_INT_VECTOR:
 955         count=udata_readInt32(ds, (int32_t)*p);
 956         /* swap length and each integer */
 957         ds->swapArray32(ds, p, 4*(1+count), q, pErrorCode);
 958         break;
 959     default:
 960         /* also catches RES_BOGUS */
 961         *pErrorCode=U_UNSUPPORTED_ERROR;
 962         break;
 963     }
 964 }
 965
 966 U_CAPI int32_t U_EXPORT2
 967 ures_swap(const UDataSwapper *ds,
 968           const void *inData, int32_t length, void *outData,
 969           UErrorCode *pErrorCode) {
 970     const UDataInfo *pInfo;
 971     const Resource *inBundle;
 972     Resource rootRes;
 973     int32_t headerSize, maxTableLength;
 974
 975     Row rows[STACK_ROW_CAPACITY];
 976     int32_t resort[STACK_ROW_CAPACITY];
 977     TempTable tempTable;
 978
 979     const int32_t *inIndexes;
 980
 981     /* the following integers count Resource item offsets (4 bytes each), not bytes */
 982     int32_t bundleLength, indexLength, keysBottom, keysTop, resBottom, top;
 983
 984     /* udata_swapDataHeader checks the arguments */
 985     headerSize=udata_swapDataHeader(ds, inData, length, outData, pErrorCode);
 986     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
 987         return 0;
 988     }
 989
 990     /* check data format and format version */
 991     pInfo=(const UDataInfo *)((const char *)inData+4);
 992     if(!(
 993         pInfo->dataFormat[0]==0x52 &&   /* dataFormat="ResB" */
 994         pInfo->dataFormat[1]==0x65 &&
 995         pInfo->dataFormat[2]==0x73 &&
 996         pInfo->dataFormat[3]==0x42 &&
 997         ((pInfo->formatVersion[0]==1 && pInfo->formatVersion[1]>=1) ||  /* formatVersion 1.1+ or 2.x */
 998          pInfo->formatVersion[0]==2)
 999     )) {
1000         udata_printError(ds, "ures_swap(): data format %02x.%02x.%02x.%02x (format version %02x.%02x) is not a resource bundle\n",
1001                          pInfo->dataFormat[0], pInfo->dataFormat[1],
1002                          pInfo->dataFormat[2], pInfo->dataFormat[3],
1003                          pInfo->formatVersion[0], pInfo->formatVersion[1]);
1004         *pErrorCode=U_UNSUPPORTED_ERROR;
1005         return 0;
1006     }
1007     tempTable.majorFormatVersion=pInfo->formatVersion[0];
1008
1009     /* a resource bundle must contain at least one resource item */
1010     if(length<0) {
1011         bundleLength=-1;
1012     } else {
1013         bundleLength=(length-headerSize)/4;
1014
1015         /* formatVersion 1.1 must have a root item and at least 5 indexes */
1016         if(bundleLength<(1+5)) {
1017             udata_printError(ds, "ures_swap(): too few bytes (%d after header) for a resource bundle\n",
1018                              length-headerSize);
1019             *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
1020             return 0;
1021         }
1022     }
1023
1024     inBundle=(const Resource *)((const char *)inData+headerSize);
1025     rootRes=ds->readUInt32(*inBundle);
1026
1027     /* formatVersion 1.1 adds the indexes[] array */
1028     inIndexes=(const int32_t *)(inBundle+1);
1029
1030     indexLength=udata_readInt32(ds, inIndexes[URES_INDEX_LENGTH])&0xff;
1031     if(indexLength<=URES_INDEX_MAX_TABLE_LENGTH) {
1032         udata_printError(ds, "ures_swap(): too few indexes for a 1.1+ resource bundle\n");
1033         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
1034         return 0;
1035     }
1036     keysBottom=1+indexLength;
1037     keysTop=udata_readInt32(ds, inIndexes[URES_INDEX_KEYS_TOP]);
1038     if(indexLength>URES_INDEX_16BIT_TOP) {
1039         resBottom=udata_readInt32(ds, inIndexes[URES_INDEX_16BIT_TOP]);
1040     } else {
1041         resBottom=keysTop;
1042     }
1043     top=udata_readInt32(ds, inIndexes[URES_INDEX_BUNDLE_TOP]);
1044     maxTableLength=udata_readInt32(ds, inIndexes[URES_INDEX_MAX_TABLE_LENGTH]);
1045
1046     if(0<=bundleLength && bundleLength<top) {
1047         udata_printError(ds, "ures_swap(): resource top %d exceeds bundle length %d\n",
1048                          top, bundleLength);
1049         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
1050         return 0;
1051     }
1052     if(keysTop>(1+indexLength)) {
1053         tempTable.localKeyLimit=keysTop<<2;
1054     } else {
1055         tempTable.localKeyLimit=0;
1056     }
1057
1058     if(length>=0) {
1059         Resource *outBundle=(Resource *)((char *)outData+headerSize);
1060
1061         /* track which resources we have already swapped */
1062         uint32_t stackResFlags[STACK_ROW_CAPACITY];
1063         int32_t resFlagsLength;
1064
1065         /*
1066          * We need one bit per 4 resource bundle bytes so that we can track
1067          * every possible Resource for whether we have swapped it already.
1068          * Multiple Resource words can refer to the same bundle offsets
1069          * for sharing identical values.
1070          * We could optimize this by allocating only for locations above
1071          * where Resource values are stored (above keys & strings).
1072          */
1073         resFlagsLength=(length+31)>>5;          /* number of bytes needed */
1074         resFlagsLength=(resFlagsLength+3)&~3;   /* multiple of 4 bytes for uint32_t */
1075         if(resFlagsLength<=sizeof(stackResFlags)) {
1076             tempTable.resFlags=stackResFlags;
1077         } else {
1078             tempTable.resFlags=(uint32_t *)uprv_malloc(resFlagsLength);
1079             if(tempTable.resFlags==NULL) {
1080                 udata_printError(ds, "ures_swap(): unable to allocate memory for tracking resources\n");
1081                 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1082                 return 0;
1083             }
1084         }
1085         uprv_memset(tempTable.resFlags, 0, resFlagsLength);
1086
1087         /* copy the bundle for binary and inaccessible data */
1088         if(inData!=outData) {
1089             uprv_memcpy(outBundle, inBundle, 4*top);
1090         }
1091
1092         /* swap the key strings, but not the padding bytes (0xaa) after the last string and its NUL */
1093         udata_swapInvStringBlock(ds, inBundle+keysBottom, 4*(keysTop-keysBottom),
1094                                     outBundle+keysBottom, pErrorCode);
1095         if(U_FAILURE(*pErrorCode)) {
1096             udata_printError(ds, "ures_swap().udata_swapInvStringBlock(keys[%d]) failed\n", 4*(keysTop-keysBottom));
1097             return 0;
1098         }
1099
1100         /* swap the 16-bit units (strings, table16, array16) */
1101         if(keysTop<resBottom) {
1102             ds->swapArray16(ds, inBundle+keysTop, (resBottom-keysTop)*4, outBundle+keysTop, pErrorCode);
1103             if(U_FAILURE(*pErrorCode)) {
1104                 udata_printError(ds, "ures_swap().swapArray16(16-bit units[%d]) failed\n", 2*(resBottom-keysTop));
1105                 return 0;
1106             }
1107         }
1108
1109         /* allocate the temporary table for sorting resource tables */
1110         tempTable.keyChars=(const char *)outBundle; /* sort by outCharset */
1111         if(tempTable.majorFormatVersion>1 || maxTableLength<=STACK_ROW_CAPACITY) {
1112             tempTable.rows=rows;
1113             tempTable.resort=resort;
1114         } else {
1115             tempTable.rows=(Row *)uprv_malloc(maxTableLength*sizeof(Row)+maxTableLength*4);
1116             if(tempTable.rows==NULL) {
1117                 udata_printError(ds, "ures_swap(): unable to allocate memory for sorting tables (max length: %d)\n",
1118                                  maxTableLength);
1119                 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1120                 if(tempTable.resFlags!=stackResFlags) {
1121                     uprv_free(tempTable.resFlags);
1122                 }
1123                 return 0;
1124             }
1125             tempTable.resort=(int32_t *)(tempTable.rows+maxTableLength);
1126         }
1127
1128         /* swap the resources */
1129         ures_swapResource(ds, inBundle, outBundle, rootRes, NULL, &tempTable, pErrorCode);
1130         if(U_FAILURE(*pErrorCode)) {
1131             udata_printError(ds, "ures_swapResource(root res=%08x) failed\n",
1132                              rootRes);
1133         }
1134
1135         if(tempTable.rows!=rows) {
1136             uprv_free(tempTable.rows);
1137         }
1138         if(tempTable.resFlags!=stackResFlags) {
1139             uprv_free(tempTable.resFlags);
1140         }
1141
1142         /* swap the root resource and indexes */
1143         ds->swapArray32(ds, inBundle, keysBottom*4, outBundle, pErrorCode);
1144     }
1145
1146     return headerSize+4*top;
1147 }