StringPool.cpp

   1 //
   2 // Copyright 2006 The Android Open Source Project
   3 //
   4 // Build resource files from raw assets.
   5 //
   6
   7 #include "StringPool.h"
   8 #include "ResourceTable.h"
   9
  10 #include <utils/ByteOrder.h>
  11 #include <utils/SortedVector.h>
  12
  13 #if HAVE_PRINTF_ZD
  14 #  define ZD "%zd"
  15 #  define ZD_TYPE ssize_t
  16 #else
  17 #  define ZD "%ld"
  18 #  define ZD_TYPE long
  19 #endif
  20
  21 #define NOISY(x) //x
  22
  23 void strcpy16_htod(uint16_t* dst, const uint16_t* src)
  24 {
  25     while (*src) {
  26         char16_t s = htods(*src);
  27         *dst++ = s;
  28         src++;
  29     }
  30     *dst = 0;
  31 }
  32
  33 void printStringPool(const ResStringPool* pool)
  34 {
  35     SortedVector<const void*> uniqueStrings;
  36     const size_t N = pool->size();
  37     for (size_t i=0; i<N; i++) {
  38         size_t len;
  39         if (pool->isUTF8()) {
  40             uniqueStrings.add(pool->string8At(i, &len));
  41         } else {
  42             uniqueStrings.add(pool->stringAt(i, &len));
  43         }
  44     }
  45
  46     printf("String pool of " ZD " unique %s %s strings, " ZD " entries and "
  47             ZD " styles using " ZD " bytes:\n",
  48             (ZD_TYPE)uniqueStrings.size(), pool->isUTF8() ? "UTF-8" : "UTF-16",
  49             pool->isSorted() ? "sorted" : "non-sorted",
  50             (ZD_TYPE)N, (ZD_TYPE)pool->styleCount(), (ZD_TYPE)pool->bytes());
  51
  52     const size_t NS = pool->size();
  53     for (size_t s=0; s<NS; s++) {
  54         String8 str = pool->string8ObjectAt(s);
  55         printf("String #" ZD ": %s\n", (ZD_TYPE) s, str.string());
  56     }
  57 }
  58
  59 String8 StringPool::entry::makeConfigsString() const {
  60     String8 configStr(configTypeName);
  61     if (configStr.size() > 0) configStr.append(" ");
  62     if (configs.size() > 0) {
  63         for (size_t j=0; j<configs.size(); j++) {
  64             if (j > 0) configStr.append(", ");
  65             configStr.append(configs[j].toString());
  66         }
  67     } else {
  68         configStr = "(none)";
  69     }
  70     return configStr;
  71 }
  72
  73 int StringPool::entry::compare(const entry& o) const {
  74     // Strings with styles go first, to reduce the size of the styles array.
  75     // We don't care about the relative order of these strings.
  76     if (hasStyles) {
  77         return o.hasStyles ? 0 : -1;
  78     }
  79     if (o.hasStyles) {
  80         return 1;
  81     }
  82
  83     // Sort unstyled strings by type, then by logical configuration.
  84     int comp = configTypeName.compare(o.configTypeName);
  85     if (comp != 0) {
  86         return comp;
  87     }
  88     const size_t LHN = configs.size();
  89     const size_t RHN = o.configs.size();
  90     size_t i=0;
  91     while (i < LHN && i < RHN) {
  92         comp = configs[i].compareLogical(o.configs[i]);
  93         if (comp != 0) {
  94             return comp;
  95         }
  96         i++;
  97     }
  98     if (LHN < RHN) return -1;
  99     else if (LHN > RHN) return 1;
 100     return 0;
 101 }
 102
 103 StringPool::StringPool(bool utf8) :
 104         mUTF8(utf8), mValues(-1)
 105 {
 106 }
 107
 108 ssize_t StringPool::add(const String16& value, const Vector<entry_style_span>& spans,
 109         const String8* configTypeName, const ResTable_config* config)
 110 {
 111     ssize_t res = add(value, false, configTypeName, config);
 112     if (res >= 0) {
 113         addStyleSpans(res, spans);
 114     }
 115     return res;
 116 }
 117
 118 ssize_t StringPool::add(const String16& value,
 119         bool mergeDuplicates, const String8* configTypeName, const ResTable_config* config)
 120 {
 121     ssize_t vidx = mValues.indexOfKey(value);
 122     ssize_t pos = vidx >= 0 ? mValues.valueAt(vidx) : -1;
 123     ssize_t eidx = pos >= 0 ? mEntryArray.itemAt(pos) : -1;
 124     if (eidx < 0) {
 125         eidx = mEntries.add(entry(value));
 126         if (eidx < 0) {
 127             fprintf(stderr, "Failure adding string %s\n", String8(value).string());
 128             return eidx;
 129         }
 130     }
 131
 132     if (configTypeName != NULL) {
 133         entry& ent = mEntries.editItemAt(eidx);
 134         NOISY(printf("*** adding config type name %s, was %s\n",
 135                 configTypeName->string(), ent.configTypeName.string()));
 136         if (ent.configTypeName.size() <= 0) {
 137             ent.configTypeName = *configTypeName;
 138         } else if (ent.configTypeName != *configTypeName) {
 139             ent.configTypeName = " ";
 140         }
 141     }
 142
 143     if (config != NULL) {
 144         // Add this to the set of configs associated with the string.
 145         entry& ent = mEntries.editItemAt(eidx);
 146         size_t addPos;
 147         for (addPos=0; addPos<ent.configs.size(); addPos++) {
 148             int cmp = ent.configs.itemAt(addPos).compareLogical(*config);
 149             if (cmp >= 0) {
 150                 if (cmp > 0) {
 151                     NOISY(printf("*** inserting config: %s\n", config->toString().string()));
 152                     ent.configs.insertAt(*config, addPos);
 153                 }
 154                 break;
 155             }
 156         }
 157         if (addPos >= ent.configs.size()) {
 158             NOISY(printf("*** adding config: %s\n", config->toString().string()));
 159             ent.configs.add(*config);
 160         }
 161     }
 162
 163     const bool first = vidx < 0;
 164     const bool styled = (pos >= 0 && (size_t)pos < mEntryStyleArray.size()) ?
 165         mEntryStyleArray[pos].spans.size() : 0;
 166     if (first || styled || !mergeDuplicates) {
 167         pos = mEntryArray.add(eidx);
 168         if (first) {
 169             vidx = mValues.add(value, pos);
 170         }
 171         entry& ent = mEntries.editItemAt(eidx);
 172         ent.indices.add(pos);
 173     }
 174
 175     NOISY(printf("Adding string %s to pool: pos=%d eidx=%d vidx=%d\n",
 176             String8(value).string(), pos, eidx, vidx));
 177
 178     return pos;
 179 }
 180
 181 status_t StringPool::addStyleSpan(size_t idx, const String16& name,
 182                                   uint32_t start, uint32_t end)
 183 {
 184     entry_style_span span;
 185     span.name = name;
 186     span.span.firstChar = start;
 187     span.span.lastChar = end;
 188     return addStyleSpan(idx, span);
 189 }
 190
 191 status_t StringPool::addStyleSpans(size_t idx, const Vector<entry_style_span>& spans)
 192 {
 193     const size_t N=spans.size();
 194     for (size_t i=0; i<N; i++) {
 195         status_t err = addStyleSpan(idx, spans[i]);
 196         if (err != NO_ERROR) {
 197             return err;
 198         }
 199     }
 200     return NO_ERROR;
 201 }
 202
 203 status_t StringPool::addStyleSpan(size_t idx, const entry_style_span& span)
 204 {
 205     // Place blank entries in the span array up to this index.
 206     while (mEntryStyleArray.size() <= idx) {
 207         mEntryStyleArray.add();
 208     }
 209
 210     entry_style& style = mEntryStyleArray.editItemAt(idx);
 211     style.spans.add(span);
 212     mEntries.editItemAt(mEntryArray[idx]).hasStyles = true;
 213     return NO_ERROR;
 214 }
 215
 216 int StringPool::config_sort(void* state, const void* lhs, const void* rhs)
 217 {
 218     StringPool* pool = (StringPool*)state;
 219     const entry& lhe = pool->mEntries[pool->mEntryArray[*static_cast<const size_t*>(lhs)]];
 220     const entry& rhe = pool->mEntries[pool->mEntryArray[*static_cast<const size_t*>(rhs)]];
 221     return lhe.compare(rhe);
 222 }
 223
 224 void StringPool::sortByConfig()
 225 {
 226     LOG_ALWAYS_FATAL_IF(mOriginalPosToNewPos.size() > 0, "Can't sort string pool after already sorted.");
 227
 228     const size_t N = mEntryArray.size();
 229
 230     // This is a vector that starts out with a 1:1 mapping to entries
 231     // in the array, which we will sort to come up with the desired order.
 232     // At that point it maps from the new position in the array to the
 233     // original position the entry appeared.
 234     Vector<size_t> newPosToOriginalPos;
 235     newPosToOriginalPos.setCapacity(N);
 236     for (size_t i=0; i < N; i++) {
 237         newPosToOriginalPos.add(i);
 238     }
 239
 240     // Sort the array.
 241     NOISY(printf("SORTING STRINGS BY CONFIGURATION...\n"));
 242     // Vector::sort uses insertion sort, which is very slow for this data set.
 243     // Use quicksort instead because we don't need a stable sort here.
 244     qsort_r(newPosToOriginalPos.editArray(), N, sizeof(size_t), this, config_sort);
 245     //newPosToOriginalPos.sort(config_sort, this);
 246     NOISY(printf("DONE SORTING STRINGS BY CONFIGURATION.\n"));
 247
 248     // Create the reverse mapping from the original position in the array
 249     // to the new position where it appears in the sorted array.  This is
 250     // so that clients can re-map any positions they had previously stored.
 251     mOriginalPosToNewPos = newPosToOriginalPos;
 252     for (size_t i=0; i<N; i++) {
 253         mOriginalPosToNewPos.editItemAt(newPosToOriginalPos[i]) = i;
 254     }
 255
 256 #if 0
 257     SortedVector<entry> entries;
 258
 259     for (size_t i=0; i<N; i++) {
 260         printf("#%d was %d: %s\n", i, newPosToOriginalPos[i],
 261                 mEntries[mEntryArray[newPosToOriginalPos[i]]].makeConfigsString().string());
 262         entries.add(mEntries[mEntryArray[i]]);
 263     }
 264
 265     for (size_t i=0; i<entries.size(); i++) {
 266         printf("Sorted config #%d: %s\n", i,
 267                 entries[i].makeConfigsString().string());
 268     }
 269 #endif
 270
 271     // Now we rebuild the arrays.
 272     Vector<entry> newEntries;
 273     Vector<size_t> newEntryArray;
 274     Vector<entry_style> newEntryStyleArray;
 275     DefaultKeyedVector<size_t, size_t> origOffsetToNewOffset;
 276
 277     for (size_t i=0; i<N; i++) {
 278         // We are filling in new offset 'i'; oldI is where we can find it
 279         // in the original data structure.
 280         size_t oldI = newPosToOriginalPos[i];
 281         // This is the actual entry associated with the old offset.
 282         const entry& oldEnt = mEntries[mEntryArray[oldI]];
 283         // This is the same entry the last time we added it to the
 284         // new entry array, if any.
 285         ssize_t newIndexOfOffset = origOffsetToNewOffset.indexOfKey(oldI);
 286         size_t newOffset;
 287         if (newIndexOfOffset < 0) {
 288             // This is the first time we have seen the entry, so add
 289             // it.
 290             newOffset = newEntries.add(oldEnt);
 291             newEntries.editItemAt(newOffset).indices.clear();
 292         } else {
 293             // We have seen this entry before, use the existing one
 294             // instead of adding it again.
 295             newOffset = origOffsetToNewOffset.valueAt(newIndexOfOffset);
 296         }
 297         // Update the indices to include this new position.
 298         newEntries.editItemAt(newOffset).indices.add(i);
 299         // And add the offset of the entry to the new entry array.
 300         newEntryArray.add(newOffset);
 301         // Add any old style to the new style array.
 302         if (mEntryStyleArray.size() > 0) {
 303             if (oldI < mEntryStyleArray.size()) {
 304                 newEntryStyleArray.add(mEntryStyleArray[oldI]);
 305             } else {
 306                 newEntryStyleArray.add(entry_style());
 307             }
 308         }
 309     }
 310
 311     // Now trim any entries at the end of the new style array that are
 312     // not needed.
 313     for (ssize_t i=newEntryStyleArray.size()-1; i>=0; i--) {
 314         const entry_style& style = newEntryStyleArray[i];
 315         if (style.spans.size() > 0) {
 316             // That's it.
 317             break;
 318         }
 319         // This one is not needed; remove.
 320         newEntryStyleArray.removeAt(i);
 321     }
 322
 323     // All done, install the new data structures and upate mValues with
 324     // the new positions.
 325     mEntries = newEntries;
 326     mEntryArray = newEntryArray;
 327     mEntryStyleArray = newEntryStyleArray;
 328     mValues.clear();
 329     for (size_t i=0; i<mEntries.size(); i++) {
 330         const entry& ent = mEntries[i];
 331         mValues.add(ent.value, ent.indices[0]);
 332     }
 333
 334 #if 0
 335     printf("FINAL SORTED STRING CONFIGS:\n");
 336     for (size_t i=0; i<mEntries.size(); i++) {
 337         const entry& ent = mEntries[i];
 338         printf("#" ZD " %s: %s\n", (ZD_TYPE)i, ent.makeConfigsString().string(),
 339                 String8(ent.value).string());
 340     }
 341 #endif
 342 }
 343
 344 sp<AaptFile> StringPool::createStringBlock()
 345 {
 346     sp<AaptFile> pool = new AaptFile(String8(), AaptGroupEntry(),
 347                                      String8());
 348     status_t err = writeStringBlock(pool);
 349     return err == NO_ERROR ? pool : NULL;
 350 }
 351
 352 #define ENCODE_LENGTH(str, chrsz, strSize) \
 353 { \
 354     size_t maxMask = 1 << ((chrsz*8)-1); \
 355     size_t maxSize = maxMask-1; \
 356     if (strSize > maxSize) { \
 357         *str++ = maxMask | ((strSize>>(chrsz*8))&maxSize); \
 358     } \
 359     *str++ = strSize; \
 360 }
 361
 362 status_t StringPool::writeStringBlock(const sp<AaptFile>& pool)
 363 {
 364     // Allow appending.  Sorry this is a little wacky.
 365     if (pool->getSize() > 0) {
 366         sp<AaptFile> block = createStringBlock();
 367         if (block == NULL) {
 368             return UNKNOWN_ERROR;
 369         }
 370         ssize_t res = pool->writeData(block->getData(), block->getSize());
 371         return (res >= 0) ? (status_t)NO_ERROR : res;
 372     }
 373
 374     // First we need to add all style span names to the string pool.
 375     // We do this now (instead of when the span is added) so that these
 376     // will appear at the end of the pool, not disrupting the order
 377     // our client placed their own strings in it.
 378
 379     const size_t STYLES = mEntryStyleArray.size();
 380     size_t i;
 381
 382     for (i=0; i<STYLES; i++) {
 383         entry_style& style = mEntryStyleArray.editItemAt(i);
 384         const size_t N = style.spans.size();
 385         for (size_t i=0; i<N; i++) {
 386             entry_style_span& span = style.spans.editItemAt(i);
 387             ssize_t idx = add(span.name, true);
 388             if (idx < 0) {
 389                 fprintf(stderr, "Error adding span for style tag '%s'\n",
 390                         String8(span.name).string());
 391                 return idx;
 392             }
 393             span.span.name.index = (uint32_t)idx;
 394         }
 395     }
 396
 397     const size_t ENTRIES = mEntryArray.size();
 398
 399     // Now build the pool of unique strings.
 400
 401     const size_t STRINGS = mEntries.size();
 402     const size_t preSize = sizeof(ResStringPool_header)
 403                          + (sizeof(uint32_t)*ENTRIES)
 404                          + (sizeof(uint32_t)*STYLES);
 405     if (pool->editData(preSize) == NULL) {
 406         fprintf(stderr, "ERROR: Out of memory for string pool\n");
 407         return NO_MEMORY;
 408     }
 409
 410     const size_t charSize = mUTF8 ? sizeof(uint8_t) : sizeof(char16_t);
 411
 412     size_t strPos = 0;
 413     for (i=0; i<STRINGS; i++) {
 414         entry& ent = mEntries.editItemAt(i);
 415         const size_t strSize = (ent.value.size());
 416         const size_t lenSize = strSize > (size_t)(1<<((charSize*8)-1))-1 ?
 417             charSize*2 : charSize;
 418
 419         String8 encStr;
 420         if (mUTF8) {
 421             encStr = String8(ent.value);
 422         }
 423
 424         const size_t encSize = mUTF8 ? encStr.size() : 0;
 425         const size_t encLenSize = mUTF8 ?
 426             (encSize > (size_t)(1<<((charSize*8)-1))-1 ?
 427                 charSize*2 : charSize) : 0;
 428
 429         ent.offset = strPos;
 430
 431         const size_t totalSize = lenSize + encLenSize +
 432             ((mUTF8 ? encSize : strSize)+1)*charSize;
 433
 434         void* dat = (void*)pool->editData(preSize + strPos + totalSize);
 435         if (dat == NULL) {
 436             fprintf(stderr, "ERROR: Out of memory for string pool\n");
 437             return NO_MEMORY;
 438         }
 439         dat = (uint8_t*)dat + preSize + strPos;
 440         if (mUTF8) {
 441             uint8_t* strings = (uint8_t*)dat;
 442
 443             ENCODE_LENGTH(strings, sizeof(uint8_t), strSize)
 444
 445             ENCODE_LENGTH(strings, sizeof(uint8_t), encSize)
 446
 447             strncpy((char*)strings, encStr, encSize+1);
 448         } else {
 449             uint16_t* strings = (uint16_t*)dat;
 450
 451             ENCODE_LENGTH(strings, sizeof(uint16_t), strSize)
 452
 453             strcpy16_htod(strings, ent.value);
 454         }
 455
 456         strPos += totalSize;
 457     }
 458
 459     // Pad ending string position up to a uint32_t boundary.
 460
 461     if (strPos&0x3) {
 462         size_t padPos = ((strPos+3)&~0x3);
 463         uint8_t* dat = (uint8_t*)pool->editData(preSize + padPos);
 464         if (dat == NULL) {
 465             fprintf(stderr, "ERROR: Out of memory padding string pool\n");
 466             return NO_MEMORY;
 467         }
 468         memset(dat+preSize+strPos, 0, padPos-strPos);
 469         strPos = padPos;
 470     }
 471
 472     // Build the pool of style spans.
 473
 474     size_t styPos = strPos;
 475     for (i=0; i<STYLES; i++) {
 476         entry_style& ent = mEntryStyleArray.editItemAt(i);
 477         const size_t N = ent.spans.size();
 478         const size_t totalSize = (N*sizeof(ResStringPool_span))
 479                                + sizeof(ResStringPool_ref);
 480
 481         ent.offset = styPos-strPos;
 482         uint8_t* dat = (uint8_t*)pool->editData(preSize + styPos + totalSize);
 483         if (dat == NULL) {
 484             fprintf(stderr, "ERROR: Out of memory for string styles\n");
 485             return NO_MEMORY;
 486         }
 487         ResStringPool_span* span = (ResStringPool_span*)(dat+preSize+styPos);
 488         for (size_t i=0; i<N; i++) {
 489             span->name.index = htodl(ent.spans[i].span.name.index);
 490             span->firstChar = htodl(ent.spans[i].span.firstChar);
 491             span->lastChar = htodl(ent.spans[i].span.lastChar);
 492             span++;
 493         }
 494         span->name.index = htodl(ResStringPool_span::END);
 495
 496         styPos += totalSize;
 497     }
 498
 499     if (STYLES > 0) {
 500         // Add full terminator at the end (when reading we validate that
 501         // the end of the pool is fully terminated to simplify error
 502         // checking).
 503         size_t extra = sizeof(ResStringPool_span)-sizeof(ResStringPool_ref);
 504         uint8_t* dat = (uint8_t*)pool->editData(preSize + styPos + extra);
 505         if (dat == NULL) {
 506             fprintf(stderr, "ERROR: Out of memory for string styles\n");
 507             return NO_MEMORY;
 508         }
 509         uint32_t* p = (uint32_t*)(dat+preSize+styPos);
 510         while (extra > 0) {
 511             *p++ = htodl(ResStringPool_span::END);
 512             extra -= sizeof(uint32_t);
 513         }
 514         styPos += extra;
 515     }
 516
 517     // Write header.
 518
 519     ResStringPool_header* header =
 520         (ResStringPool_header*)pool->padData(sizeof(uint32_t));
 521     if (header == NULL) {
 522         fprintf(stderr, "ERROR: Out of memory for string pool\n");
 523         return NO_MEMORY;
 524     }
 525     memset(header, 0, sizeof(*header));
 526     header->header.type = htods(RES_STRING_POOL_TYPE);
 527     header->header.headerSize = htods(sizeof(*header));
 528     header->header.size = htodl(pool->getSize());
 529     header->stringCount = htodl(ENTRIES);
 530     header->styleCount = htodl(STYLES);
 531     if (mUTF8) {
 532         header->flags |= htodl(ResStringPool_header::UTF8_FLAG);
 533     }
 534     header->stringsStart = htodl(preSize);
 535     header->stylesStart = htodl(STYLES > 0 ? (preSize+strPos) : 0);
 536
 537     // Write string index array.
 538
 539     uint32_t* index = (uint32_t*)(header+1);
 540     for (i=0; i<ENTRIES; i++) {
 541         entry& ent = mEntries.editItemAt(mEntryArray[i]);
 542         *index++ = htodl(ent.offset);
 543         NOISY(printf("Writing entry #%d: \"%s\" ent=%d off=%d\n", i,
 544                 String8(ent.value).string(),
 545                 mEntryArray[i], ent.offset));
 546     }
 547
 548     // Write style index array.
 549
 550     for (i=0; i<STYLES; i++) {
 551         *index++ = htodl(mEntryStyleArray[i].offset);
 552     }
 553
 554     return NO_ERROR;
 555 }
 556
 557 ssize_t StringPool::offsetForString(const String16& val) const
 558 {
 559     const Vector<size_t>* indices = offsetsForString(val);
 560     ssize_t res = indices != NULL && indices->size() > 0 ? indices->itemAt(0) : -1;
 561     NOISY(printf("Offset for string %s: %d (%s)\n", String8(val).string(), res,
 562             res >= 0 ? String8(mEntries[mEntryArray[res]].value).string() : String8()));
 563     return res;
 564 }
 565
 566 const Vector<size_t>* StringPool::offsetsForString(const String16& val) const
 567 {
 568     ssize_t pos = mValues.valueFor(val);
 569     if (pos < 0) {
 570         return NULL;
 571     }
 572     return &mEntries[mEntryArray[pos]].indices;
 573 }