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