[android/aapt.git] / StringPool.cpp

//
// Copyright 2006 The Android Open Source Project
//
// Build resource files from raw assets.
//

#include "StringPool.h"
#include "ResourceTable.h"

#include <utils/ByteOrder.h>
#include <utils/SortedVector.h>

#if HAVE_PRINTF_ZD
#  define ZD "%zd"
#  define ZD_TYPE ssize_t
#else
#  define ZD "%ld"
#  define ZD_TYPE long
#endif

#define NOISY(x) //x

void strcpy16_htod(uint16_t* dst, const uint16_t* src)
{
    while (*src) {
        char16_t s = htods(*src);
        *dst++ = s;
        src++;
    }
    *dst = 0;
}

void printStringPool(const ResStringPool* pool)
{
    SortedVector<const void*> uniqueStrings;
    const size_t N = pool->size();
    for (size_t i=0; i<N; i++) {
        size_t len;
        if (pool->isUTF8()) {
            uniqueStrings.add(pool->string8At(i, &len));
        } else {
            uniqueStrings.add(pool->stringAt(i, &len));
        }
    }

    printf("String pool of " ZD " unique %s %s strings, " ZD " entries and "
            ZD " styles using " ZD " bytes:\n",
            (ZD_TYPE)uniqueStrings.size(), pool->isUTF8() ? "UTF-8" : "UTF-16",
            pool->isSorted() ? "sorted" : "non-sorted",
            (ZD_TYPE)N, (ZD_TYPE)pool->styleCount(), (ZD_TYPE)pool->bytes());

    const size_t NS = pool->size();
    for (size_t s=0; s<NS; s++) {
        String8 str = pool->string8ObjectAt(s);
        printf("String #" ZD ": %s\n", (ZD_TYPE) s, str.string());
    }
}

String8 StringPool::entry::makeConfigsString() const {
    String8 configStr(configTypeName);
    if (configStr.size() > 0) configStr.append(" ");
    if (configs.size() > 0) {
        for (size_t j=0; j<configs.size(); j++) {
            if (j > 0) configStr.append(", ");
            configStr.append(configs[j].toString());
        }
    } else {
        configStr = "(none)";
    }
    return configStr;
}

int StringPool::entry::compare(const entry& o) const {
    // Strings with styles go first, to reduce the size of the
    // styles array.
    if (hasStyles) {
        return o.hasStyles ? 0 : -1;
    }
    if (o.hasStyles) {
        return 1;
    }
    int comp = configTypeName.compare(o.configTypeName);
    if (comp != 0) {
        return comp;
    }
    const size_t LHN = configs.size();
    const size_t RHN = o.configs.size();
    size_t i=0;
    while (i < LHN && i < RHN) {
        comp = configs[i].compareLogical(o.configs[i]);
        if (comp != 0) {
            return comp;
        }
        i++;
    }
    if (LHN < RHN) return -1;
    else if (LHN > RHN) return 1;
    return 0;
}

StringPool::StringPool(bool sorted, bool utf8)
    : mSorted(sorted), mUTF8(utf8), mValues(-1), mIdents(-1)
{
}

ssize_t StringPool::add(const String16& value, bool mergeDuplicates,
        const String8* configTypeName, const ResTable_config* config)
{
    return add(String16(), value, mergeDuplicates, configTypeName, config);
}

ssize_t StringPool::add(const String16& value, const Vector<entry_style_span>& spans,
        const String8* configTypeName, const ResTable_config* config)
{
    ssize_t res = add(String16(), value, false, configTypeName, config);
    if (res >= 0) {
        addStyleSpans(res, spans);
    }
    return res;
}

ssize_t StringPool::add(const String16& ident, const String16& value,
        bool mergeDuplicates, const String8* configTypeName, const ResTable_config* config)
{
    if (ident.size() > 0) {
        ssize_t idx = mIdents.valueFor(ident);
        if (idx >= 0) {
            fprintf(stderr, "ERROR: Duplicate string identifier %s\n",
                    String8(mEntries[idx].value).string());
            return UNKNOWN_ERROR;
        }
    }

    ssize_t vidx = mValues.indexOfKey(value);
    ssize_t pos = vidx >= 0 ? mValues.valueAt(vidx) : -1;
    ssize_t eidx = pos >= 0 ? mEntryArray.itemAt(pos) : -1;
    if (eidx < 0) {
        eidx = mEntries.add(entry(value));
        if (eidx < 0) {
            fprintf(stderr, "Failure adding string %s\n", String8(value).string());
            return eidx;
        }
    }

    if (configTypeName != NULL) {
        entry& ent = mEntries.editItemAt(eidx);
        NOISY(printf("*** adding config type name %s, was %s\n",
                configTypeName->string(), ent.configTypeName.string()));
        if (ent.configTypeName.size() <= 0) {
            ent.configTypeName = *configTypeName;
        } else if (ent.configTypeName != *configTypeName) {
            ent.configTypeName = " ";
        }
    }

    if (config != NULL) {
        // Add this to the set of configs associated with the string.
        entry& ent = mEntries.editItemAt(eidx);
        size_t addPos;
        for (addPos=0; addPos<ent.configs.size(); addPos++) {
            int cmp = ent.configs.itemAt(addPos).compareLogical(*config);
            if (cmp >= 0) {
                if (cmp > 0) {
                    NOISY(printf("*** inserting config: %s\n", config->toString().string()));
                    ent.configs.insertAt(*config, addPos);
                }
                break;
            }
        }
        if (addPos >= ent.configs.size()) {
            NOISY(printf("*** adding config: %s\n", config->toString().string()));
            ent.configs.add(*config);
        }
    }

    const bool first = vidx < 0;
    if (first || !mergeDuplicates) {
        pos = mEntryArray.add(eidx);
        if (first) {
            vidx = mValues.add(value, pos);
        }
        if (!mSorted) {
            entry& ent = mEntries.editItemAt(eidx);
            ent.indices.add(pos);
        }
    }

    if (ident.size() > 0) {
        mIdents.add(ident, vidx);
    }

    NOISY(printf("Adding string %s to pool: pos=%d eidx=%d vidx=%d\n",
            String8(value).string(), pos, eidx, vidx));
    
    return pos;
}

status_t StringPool::addStyleSpan(size_t idx, const String16& name,
                                  uint32_t start, uint32_t end)
{
    entry_style_span span;
    span.name = name;
    span.span.firstChar = start;
    span.span.lastChar = end;
    return addStyleSpan(idx, span);
}

status_t StringPool::addStyleSpans(size_t idx, const Vector<entry_style_span>& spans)
{
    const size_t N=spans.size();
    for (size_t i=0; i<N; i++) {
        status_t err = addStyleSpan(idx, spans[i]);
        if (err != NO_ERROR) {
            return err;
        }
    }
    return NO_ERROR;
}

status_t StringPool::addStyleSpan(size_t idx, const entry_style_span& span)
{
    LOG_ALWAYS_FATAL_IF(mSorted, "Can't use styles with sorted string pools.");

    // Place blank entries in the span array up to this index.
    while (mEntryStyleArray.size() <= idx) {
        mEntryStyleArray.add();
    }

    entry_style& style = mEntryStyleArray.editItemAt(idx);
    style.spans.add(span);
    mEntries.editItemAt(mEntryArray[idx]).hasStyles = true;
    return NO_ERROR;
}

size_t StringPool::size() const
{
    return mSorted ? mValues.size() : mEntryArray.size();
}

const StringPool::entry& StringPool::entryAt(size_t idx) const
{
    if (!mSorted) {
        return mEntries[mEntryArray[idx]];
    } else {
        return mEntries[mEntryArray[mValues.valueAt(idx)]];
    }
}

size_t StringPool::countIdentifiers() const
{
    return mIdents.size();
}

int StringPool::config_sort(const size_t* lhs, const size_t* rhs, void* state)
{
    StringPool* pool = (StringPool*)state;
    const entry& lhe = pool->mEntries[pool->mEntryArray[*lhs]];
    const entry& rhe = pool->mEntries[pool->mEntryArray[*rhs]];
    return lhe.compare(rhe);
}

void StringPool::sortByConfig()
{
    LOG_ALWAYS_FATAL_IF(mSorted, "Can't sort string pool containing identifiers.");
    LOG_ALWAYS_FATAL_IF(mIdents.size() > 0, "Can't sort string pool containing identifiers.");
    LOG_ALWAYS_FATAL_IF(mOriginalPosToNewPos.size() > 0, "Can't sort string pool after already sorted.");

    const size_t N = mEntryArray.size();

    // This is a vector that starts out with a 1:1 mapping to entries
    // in the array, which we will sort to come up with the desired order.
    // At that point it maps from the new position in the array to the
    // original position the entry appeared.
    Vector<size_t> newPosToOriginalPos;
    for (size_t i=0; i<mEntryArray.size(); i++) {
        newPosToOriginalPos.add(i);
    }

    // Sort the array.
    NOISY(printf("SORTING STRINGS BY CONFIGURATION...\n"));
    newPosToOriginalPos.sort(config_sort, this);
    NOISY(printf("DONE SORTING STRINGS BY CONFIGURATION.\n"));

    // Create the reverse mapping from the original position in the array
    // to the new position where it appears in the sorted array.  This is
    // so that clients can re-map any positions they had previously stored.
    mOriginalPosToNewPos = newPosToOriginalPos;
    for (size_t i=0; i<N; i++) {
        mOriginalPosToNewPos.editItemAt(newPosToOriginalPos[i]) = i;
    }

#if 0
    SortedVector<entry> entries;

    for (size_t i=0; i<N; i++) {
        printf("#%d was %d: %s\n", i, newPosToOriginalPos[i],
                mEntries[mEntryArray[newPosToOriginalPos[i]]].makeConfigsString().string());
        entries.add(mEntries[mEntryArray[i]]);
    }

    for (size_t i=0; i<entries.size(); i++) {
        printf("Sorted config #%d: %s\n", i,
                entries[i].makeConfigsString().string());
    }
#endif

    // Now we rebuild the arrays.
    Vector<entry> newEntries;
    Vector<size_t> newEntryArray;
    Vector<entry_style> newEntryStyleArray;
    DefaultKeyedVector<size_t, size_t> origOffsetToNewOffset;

    for (size_t i=0; i<N; i++) {
        // We are filling in new offset 'i'; oldI is where we can find it
        // in the original data structure.
        size_t oldI = newPosToOriginalPos[i];
        // This is the actual entry associated with the old offset.
        const entry& oldEnt = mEntries[mEntryArray[oldI]];
        // This is the same entry the last time we added it to the
        // new entry array, if any.
        ssize_t newIndexOfOffset = origOffsetToNewOffset.indexOfKey(oldI);
        size_t newOffset;
        if (newIndexOfOffset < 0) {
            // This is the first time we have seen the entry, so add
            // it.
            newOffset = newEntries.add(oldEnt);
            newEntries.editItemAt(newOffset).indices.clear();
        } else {
            // We have seen this entry before, use the existing one
            // instead of adding it again.
            newOffset = origOffsetToNewOffset.valueAt(newIndexOfOffset);
        }
        // Update the indices to include this new position.
        newEntries.editItemAt(newOffset).indices.add(i);
        // And add the offset of the entry to the new entry array.
        newEntryArray.add(newOffset);
        // Add any old style to the new style array.
        if (mEntryStyleArray.size() > 0) {
            if (oldI < mEntryStyleArray.size()) {
                newEntryStyleArray.add(mEntryStyleArray[oldI]);
            } else {
                newEntryStyleArray.add(entry_style());
            }
        }
    }

    // Now trim any entries at the end of the new style array that are
    // not needed.
    for (ssize_t i=newEntryStyleArray.size()-1; i>=0; i--) {
        const entry_style& style = newEntryStyleArray[i];
        if (style.spans.size() > 0) {
            // That's it.
            break;
        }
        // This one is not needed; remove.
        newEntryStyleArray.removeAt(i);
    }

    // All done, install the new data structures and upate mValues with
    // the new positions.
    mEntries = newEntries;
    mEntryArray = newEntryArray;
    mEntryStyleArray = newEntryStyleArray;
    mValues.clear();
    for (size_t i=0; i<mEntries.size(); i++) {
        const entry& ent = mEntries[i];
        mValues.add(ent.value, ent.indices[0]);
    }

#if 0
    printf("FINAL SORTED STRING CONFIGS:\n");
    for (size_t i=0; i<mEntries.size(); i++) {
        const entry& ent = mEntries[i];
        printf("#" ZD " %s: %s\n", (ZD_TYPE)i, ent.makeConfigsString().string(),
                String8(ent.value).string());
    }
#endif
}

sp<AaptFile> StringPool::createStringBlock()
{
    sp<AaptFile> pool = new AaptFile(String8(), AaptGroupEntry(),
                                     String8());
    status_t err = writeStringBlock(pool);
    return err == NO_ERROR ? pool : NULL;
}

#define ENCODE_LENGTH(str, chrsz, strSize) \
{ \
    size_t maxMask = 1 << ((chrsz*8)-1); \
    size_t maxSize = maxMask-1; \
    if (strSize > maxSize) { \
        *str++ = maxMask | ((strSize>>(chrsz*8))&maxSize); \
    } \
    *str++ = strSize; \
}

status_t StringPool::writeStringBlock(const sp<AaptFile>& pool)
{
    // Allow appending.  Sorry this is a little wacky.
    if (pool->getSize() > 0) {
        sp<AaptFile> block = createStringBlock();
        if (block == NULL) {
            return UNKNOWN_ERROR;
        }
        ssize_t res = pool->writeData(block->getData(), block->getSize());
        return (res >= 0) ? (status_t)NO_ERROR : res;
    }

    // First we need to add all style span names to the string pool.
    // We do this now (instead of when the span is added) so that these
    // will appear at the end of the pool, not disrupting the order
    // our client placed their own strings in it.
    
    const size_t STYLES = mEntryStyleArray.size();
    size_t i;

    for (i=0; i<STYLES; i++) {
        entry_style& style = mEntryStyleArray.editItemAt(i);
        const size_t N = style.spans.size();
        for (size_t i=0; i<N; i++) {
            entry_style_span& span = style.spans.editItemAt(i);
            ssize_t idx = add(span.name, true);
            if (idx < 0) {
                fprintf(stderr, "Error adding span for style tag '%s'\n",
                        String8(span.name).string());
                return idx;
            }
            span.span.name.index = (uint32_t)idx;
        }
    }

    const size_t ENTRIES = size();

    // Now build the pool of unique strings.

    const size_t STRINGS = mEntries.size();
    const size_t preSize = sizeof(ResStringPool_header)
                         + (sizeof(uint32_t)*ENTRIES)
                         + (sizeof(uint32_t)*STYLES);
    if (pool->editData(preSize) == NULL) {
        fprintf(stderr, "ERROR: Out of memory for string pool\n");
        return NO_MEMORY;
    }

    const size_t charSize = mUTF8 ? sizeof(uint8_t) : sizeof(char16_t);

    size_t strPos = 0;
    for (i=0; i<STRINGS; i++) {
        entry& ent = mEntries.editItemAt(i);
        const size_t strSize = (ent.value.size());
        const size_t lenSize = strSize > (size_t)(1<<((charSize*8)-1))-1 ?
            charSize*2 : charSize;

        String8 encStr;
        if (mUTF8) {
            encStr = String8(ent.value);
        }

        const size_t encSize = mUTF8 ? encStr.size() : 0;
        const size_t encLenSize = mUTF8 ?
            (encSize > (size_t)(1<<((charSize*8)-1))-1 ?
                charSize*2 : charSize) : 0;

        ent.offset = strPos;

        const size_t totalSize = lenSize + encLenSize +
            ((mUTF8 ? encSize : strSize)+1)*charSize;

        void* dat = (void*)pool->editData(preSize + strPos + totalSize);
        if (dat == NULL) {
            fprintf(stderr, "ERROR: Out of memory for string pool\n");
            return NO_MEMORY;
        }
        dat = (uint8_t*)dat + preSize + strPos;
        if (mUTF8) {
            uint8_t* strings = (uint8_t*)dat;

            ENCODE_LENGTH(strings, sizeof(uint8_t), strSize)

            ENCODE_LENGTH(strings, sizeof(uint8_t), encSize)

            strncpy((char*)strings, encStr, encSize+1);
        } else {
            uint16_t* strings = (uint16_t*)dat;

            ENCODE_LENGTH(strings, sizeof(uint16_t), strSize)

            strcpy16_htod(strings, ent.value);
        }

        strPos += totalSize;
    }

    // Pad ending string position up to a uint32_t boundary.

    if (strPos&0x3) {
        size_t padPos = ((strPos+3)&~0x3);
        uint8_t* dat = (uint8_t*)pool->editData(preSize + padPos);
        if (dat == NULL) {
            fprintf(stderr, "ERROR: Out of memory padding string pool\n");
            return NO_MEMORY;
        }
        memset(dat+preSize+strPos, 0, padPos-strPos);
        strPos = padPos;
    }

    // Build the pool of style spans.

    size_t styPos = strPos;
    for (i=0; i<STYLES; i++) {
        entry_style& ent = mEntryStyleArray.editItemAt(i);
        const size_t N = ent.spans.size();
        const size_t totalSize = (N*sizeof(ResStringPool_span))
                               + sizeof(ResStringPool_ref);

        ent.offset = styPos-strPos;
        uint8_t* dat = (uint8_t*)pool->editData(preSize + styPos + totalSize);
        if (dat == NULL) {
            fprintf(stderr, "ERROR: Out of memory for string styles\n");
            return NO_MEMORY;
        }
        ResStringPool_span* span = (ResStringPool_span*)(dat+preSize+styPos);
        for (size_t i=0; i<N; i++) {
            span->name.index = htodl(ent.spans[i].span.name.index);
            span->firstChar = htodl(ent.spans[i].span.firstChar);
            span->lastChar = htodl(ent.spans[i].span.lastChar);
            span++;
        }
        span->name.index = htodl(ResStringPool_span::END);

        styPos += totalSize;
    }

    if (STYLES > 0) {
        // Add full terminator at the end (when reading we validate that
        // the end of the pool is fully terminated to simplify error
        // checking).
        size_t extra = sizeof(ResStringPool_span)-sizeof(ResStringPool_ref);
        uint8_t* dat = (uint8_t*)pool->editData(preSize + styPos + extra);
        if (dat == NULL) {
            fprintf(stderr, "ERROR: Out of memory for string styles\n");
            return NO_MEMORY;
        }
        uint32_t* p = (uint32_t*)(dat+preSize+styPos);
        while (extra > 0) {
            *p++ = htodl(ResStringPool_span::END);
            extra -= sizeof(uint32_t);
        }
        styPos += extra;
    }

    // Write header.

    ResStringPool_header* header =
        (ResStringPool_header*)pool->padData(sizeof(uint32_t));
    if (header == NULL) {
        fprintf(stderr, "ERROR: Out of memory for string pool\n");
        return NO_MEMORY;
    }
    memset(header, 0, sizeof(*header));
    header->header.type = htods(RES_STRING_POOL_TYPE);
    header->header.headerSize = htods(sizeof(*header));
    header->header.size = htodl(pool->getSize());
    header->stringCount = htodl(ENTRIES);
    header->styleCount = htodl(STYLES);
    if (mSorted) {
        header->flags |= htodl(ResStringPool_header::SORTED_FLAG);
    }
    if (mUTF8) {
        header->flags |= htodl(ResStringPool_header::UTF8_FLAG);
    }
    header->stringsStart = htodl(preSize);
    header->stylesStart = htodl(STYLES > 0 ? (preSize+strPos) : 0);

    // Write string index array.

    uint32_t* index = (uint32_t*)(header+1);
    if (mSorted) {
        for (i=0; i<ENTRIES; i++) {
            entry& ent = const_cast<entry&>(entryAt(i));
            ent.indices.clear();
            ent.indices.add(i);
            *index++ = htodl(ent.offset);
        }
    } else {
        for (i=0; i<ENTRIES; i++) {
            entry& ent = mEntries.editItemAt(mEntryArray[i]);
            *index++ = htodl(ent.offset);
            NOISY(printf("Writing entry #%d: \"%s\" ent=%d off=%d\n", i,
                    String8(ent.value).string(),
                    mEntryArray[i], ent.offset));
        }
    }

    // Write style index array.

    if (mSorted) {
        for (i=0; i<STYLES; i++) {
            LOG_ALWAYS_FATAL("Shouldn't be here!");
        }
    } else {
        for (i=0; i<STYLES; i++) {
            *index++ = htodl(mEntryStyleArray[i].offset);
        }
    }

    return NO_ERROR;
}

ssize_t StringPool::offsetForString(const String16& val) const
{
    const Vector<size_t>* indices = offsetsForString(val);
    ssize_t res = indices != NULL && indices->size() > 0 ? indices->itemAt(0) : -1;
    NOISY(printf("Offset for string %s: %d (%s)\n", String8(val).string(), res,
            res >= 0 ? String8(mEntries[mEntryArray[res]].value).string() : String8()));
    return res;
}

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