icuSources/common/uresdata.c

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