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