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