diff --git a/core/jni/android_util_AssetManager.cpp b/core/jni/android_util_AssetManager.cpp
index 94098c9..fba7255 100644
--- a/core/jni/android_util_AssetManager.cpp
+++ b/core/jni/android_util_AssetManager.cpp
@@ -33,6 +33,7 @@
 
 #include <androidfw/Asset.h>
 #include <androidfw/AssetManager.h>
+#include <androidfw/AttributeFinder.h>
 #include <androidfw/ResourceTypes.h>
 
 #include <private/android_filesystem_config.h> // for AID_SYSTEM
@@ -999,6 +1000,30 @@
     theme->dumpToLog();
 }
 
+class XmlAttributeFinder : public BackTrackingAttributeFinder<XmlAttributeFinder, jsize> {
+public:
+    XmlAttributeFinder(const ResXMLParser* parser)
+        : BackTrackingAttributeFinder(0, parser != NULL ? parser->getAttributeCount() : 0)
+        , mParser(parser) {}
+
+    inline uint32_t getAttribute(jsize index) const {
+        return mParser->getAttributeNameResID(index);
+    }
+
+private:
+    const ResXMLParser* mParser;
+};
+
+class BagAttributeFinder : public BackTrackingAttributeFinder<BagAttributeFinder, const ResTable::bag_entry*> {
+public:
+    BagAttributeFinder(const ResTable::bag_entry* start, const ResTable::bag_entry* end)
+        : BackTrackingAttributeFinder(start, end) {}
+
+    inline uint32_t getAttribute(const ResTable::bag_entry* entry) const {
+        return entry->map.name.ident;
+    }
+};
+
 static jboolean android_content_AssetManager_resolveAttrs(JNIEnv* env, jobject clazz,
                                                           jlong themeToken,
                                                           jint defStyleAttr,
@@ -1074,13 +1099,13 @@
     res.lock();
 
     // Retrieve the default style bag, if requested.
-    const ResTable::bag_entry* defStyleEnt = NULL;
+    const ResTable::bag_entry* defStyleStart = NULL;
     uint32_t defStyleTypeSetFlags = 0;
     ssize_t bagOff = defStyleRes != 0
-            ? res.getBagLocked(defStyleRes, &defStyleEnt, &defStyleTypeSetFlags) : -1;
+            ? res.getBagLocked(defStyleRes, &defStyleStart, &defStyleTypeSetFlags) : -1;
     defStyleTypeSetFlags |= defStyleBagTypeSetFlags;
-    const ResTable::bag_entry* endDefStyleEnt = defStyleEnt +
-        (bagOff >= 0 ? bagOff : 0);;
+    const ResTable::bag_entry* const defStyleEnd = defStyleStart + (bagOff >= 0 ? bagOff : 0);
+    BagAttributeFinder defStyleAttrFinder(defStyleStart, defStyleEnd);
 
     // Now iterate through all of the attributes that the client has requested,
     // filling in each with whatever data we can find.
@@ -1108,20 +1133,15 @@
                     value.dataType, value.data));
         }
 
-        // Skip through the default style values until the end or the next possible match.
-        while (defStyleEnt < endDefStyleEnt && curIdent > defStyleEnt->map.name.ident) {
-            defStyleEnt++;
-        }
-        // Retrieve the current default style attribute if it matches, and step to next.
-        if (defStyleEnt < endDefStyleEnt && curIdent == defStyleEnt->map.name.ident) {
-            if (value.dataType == Res_value::TYPE_NULL) {
-                block = defStyleEnt->stringBlock;
+        if (value.dataType == Res_value::TYPE_NULL) {
+            const ResTable::bag_entry* const defStyleEntry = defStyleAttrFinder.find(curIdent);
+            if (defStyleEntry != defStyleEnd) {
+                block = defStyleEntry->stringBlock;
                 typeSetFlags = defStyleTypeSetFlags;
-                value = defStyleEnt->map.value;
+                value = defStyleEntry->map.value;
                 DEBUG_STYLES(ALOGI("-> From def style: type=0x%x, data=0x%08x",
                         value.dataType, value.data));
             }
-            defStyleEnt++;
         }
 
         uint32_t resid = 0;
@@ -1284,34 +1304,32 @@
     res.lock();
 
     // Retrieve the default style bag, if requested.
-    const ResTable::bag_entry* defStyleEnt = NULL;
+    const ResTable::bag_entry* defStyleAttrStart = NULL;
     uint32_t defStyleTypeSetFlags = 0;
     ssize_t bagOff = defStyleRes != 0
-            ? res.getBagLocked(defStyleRes, &defStyleEnt, &defStyleTypeSetFlags) : -1;
+            ? res.getBagLocked(defStyleRes, &defStyleAttrStart, &defStyleTypeSetFlags) : -1;
     defStyleTypeSetFlags |= defStyleBagTypeSetFlags;
-    const ResTable::bag_entry* endDefStyleEnt = defStyleEnt +
-        (bagOff >= 0 ? bagOff : 0);
+    const ResTable::bag_entry* const defStyleAttrEnd = defStyleAttrStart + (bagOff >= 0 ? bagOff : 0);
+    BagAttributeFinder defStyleAttrFinder(defStyleAttrStart, defStyleAttrEnd);
 
     // Retrieve the style class bag, if requested.
-    const ResTable::bag_entry* styleEnt = NULL;
+    const ResTable::bag_entry* styleAttrStart = NULL;
     uint32_t styleTypeSetFlags = 0;
-    bagOff = style != 0 ? res.getBagLocked(style, &styleEnt, &styleTypeSetFlags) : -1;
+    bagOff = style != 0 ? res.getBagLocked(style, &styleAttrStart, &styleTypeSetFlags) : -1;
     styleTypeSetFlags |= styleBagTypeSetFlags;
-    const ResTable::bag_entry* endStyleEnt = styleEnt +
-        (bagOff >= 0 ? bagOff : 0);
+    const ResTable::bag_entry* const styleAttrEnd = styleAttrStart + (bagOff >= 0 ? bagOff : 0);
+    BagAttributeFinder styleAttrFinder(styleAttrStart, styleAttrEnd);
 
     // Retrieve the XML attributes, if requested.
-    const jsize NX = xmlParser ? xmlParser->getAttributeCount() : 0;
-    jsize ix=0;
-    uint32_t curXmlAttr = xmlParser ? xmlParser->getAttributeNameResID(ix) : 0;
-
     static const ssize_t kXmlBlock = 0x10000000;
+    XmlAttributeFinder xmlAttrFinder(xmlParser);
+    const jsize xmlAttrEnd = xmlParser != NULL ? xmlParser->getAttributeCount() : 0;
 
     // Now iterate through all of the attributes that the client has requested,
     // filling in each with whatever data we can find.
     ssize_t block = 0;
     uint32_t typeSetFlags;
-    for (jsize ii=0; ii<NI; ii++) {
+    for (jsize ii = 0; ii < NI; ii++) {
         const uint32_t curIdent = (uint32_t)src[ii];
 
         DEBUG_STYLES(ALOGI("RETRIEVING ATTR 0x%08x...", curIdent));
@@ -1324,51 +1342,40 @@
         typeSetFlags = 0;
         config.density = 0;
 
-        // Skip through XML attributes until the end or the next possible match.
-        while (ix < NX && curIdent > curXmlAttr) {
-            ix++;
-            curXmlAttr = xmlParser->getAttributeNameResID(ix);
-        }
-        // Retrieve the current XML attribute if it matches, and step to next.
-        if (ix < NX && curIdent == curXmlAttr) {
+        // Walk through the xml attributes looking for the requested attribute.
+        const jsize xmlAttrIdx = xmlAttrFinder.find(curIdent);
+        if (xmlAttrIdx != xmlAttrEnd) {
+            // We found the attribute we were looking for.
             block = kXmlBlock;
-            xmlParser->getAttributeValue(ix, &value);
-            ix++;
-            curXmlAttr = xmlParser->getAttributeNameResID(ix);
+            xmlParser->getAttributeValue(xmlAttrIdx, &value);
             DEBUG_STYLES(ALOGI("-> From XML: type=0x%x, data=0x%08x",
                     value.dataType, value.data));
         }
 
-        // Skip through the style values until the end or the next possible match.
-        while (styleEnt < endStyleEnt && curIdent > styleEnt->map.name.ident) {
-            styleEnt++;
-        }
-        // Retrieve the current style attribute if it matches, and step to next.
-        if (styleEnt < endStyleEnt && curIdent == styleEnt->map.name.ident) {
-            if (value.dataType == Res_value::TYPE_NULL) {
-                block = styleEnt->stringBlock;
+        if (value.dataType == Res_value::TYPE_NULL) {
+            // Walk through the style class values looking for the requested attribute.
+            const ResTable::bag_entry* const styleAttrEntry = styleAttrFinder.find(curIdent);
+            if (styleAttrEntry != styleAttrEnd) {
+                // We found the attribute we were looking for.
+                block = styleAttrEntry->stringBlock;
                 typeSetFlags = styleTypeSetFlags;
-                value = styleEnt->map.value;
+                value = styleAttrEntry->map.value;
                 DEBUG_STYLES(ALOGI("-> From style: type=0x%x, data=0x%08x",
                         value.dataType, value.data));
             }
-            styleEnt++;
         }
 
-        // Skip through the default style values until the end or the next possible match.
-        while (defStyleEnt < endDefStyleEnt && curIdent > defStyleEnt->map.name.ident) {
-            defStyleEnt++;
-        }
-        // Retrieve the current default style attribute if it matches, and step to next.
-        if (defStyleEnt < endDefStyleEnt && curIdent == defStyleEnt->map.name.ident) {
-            if (value.dataType == Res_value::TYPE_NULL) {
-                block = defStyleEnt->stringBlock;
-                typeSetFlags = defStyleTypeSetFlags;
-                value = defStyleEnt->map.value;
+        if (value.dataType == Res_value::TYPE_NULL) {
+            // Walk through the default style values looking for the requested attribute.
+            const ResTable::bag_entry* const defStyleAttrEntry = defStyleAttrFinder.find(curIdent);
+            if (defStyleAttrEntry != defStyleAttrEnd) {
+                // We found the attribute we were looking for.
+                block = defStyleAttrEntry->stringBlock;
+                typeSetFlags = styleTypeSetFlags;
+                value = defStyleAttrEntry->map.value;
                 DEBUG_STYLES(ALOGI("-> From def style: type=0x%x, data=0x%08x",
                         value.dataType, value.data));
             }
-            defStyleEnt++;
         }
 
         uint32_t resid = 0;
@@ -1376,7 +1383,9 @@
             // Take care of resolving the found resource to its final value.
             ssize_t newBlock = theme->resolveAttributeReference(&value, block,
                     &resid, &typeSetFlags, &config);
-            if (newBlock >= 0) block = newBlock;
+            if (newBlock >= 0) {
+                block = newBlock;
+            }
             DEBUG_STYLES(ALOGI("-> Resolved attr: type=0x%x, data=0x%08x",
                     value.dataType, value.data));
         } else {
@@ -1394,7 +1403,9 @@
                     return JNI_FALSE;
                 }
 #endif
-                if (newBlock >= 0) block = newBlock;
+                if (newBlock >= 0) {
+                    block = newBlock;
+                }
                 DEBUG_STYLES(ALOGI("-> Resolved theme: type=0x%x, data=0x%08x",
                         value.dataType, value.data));
             }
@@ -1414,8 +1425,8 @@
         // Write the final value back to Java.
         dest[STYLE_TYPE] = value.dataType;
         dest[STYLE_DATA] = value.data;
-        dest[STYLE_ASSET_COOKIE] =
-            block != kXmlBlock ? reinterpret_cast<jint>(res.getTableCookie(block)) : (jint)-1;
+        dest[STYLE_ASSET_COOKIE] = block != kXmlBlock ?
+            static_cast<jint>(res.getTableCookie(block)) : -1;
         dest[STYLE_RESOURCE_ID] = resid;
         dest[STYLE_CHANGING_CONFIGURATIONS] = typeSetFlags;
         dest[STYLE_DENSITY] = config.density;
diff --git a/include/androidfw/AttributeFinder.h b/include/androidfw/AttributeFinder.h
new file mode 100644
index 0000000..a0ffeb3
--- /dev/null
+++ b/include/androidfw/AttributeFinder.h
@@ -0,0 +1,201 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef H_ATTRIBUTE_FINDER
+#define H_ATTRIBUTE_FINDER
+
+#include <stdint.h>
+#include <utils/KeyedVector.h>
+
+namespace android {
+
+static inline uint32_t getPackage(uint32_t attr) {
+    return attr >> 24;
+}
+
+/**
+ * A helper class to search linearly for the requested
+ * attribute, maintaining it's position and optimizing for
+ * the case that subsequent searches will involve an attribute with
+ * a higher attribute ID.
+ *
+ * In the case that a subsequent attribute has a different package ID,
+ * its resource ID may not be larger than the preceding search, so
+ * back tracking is supported for this case. This
+ * back tracking requirement is mainly for shared library
+ * resources, whose package IDs get assigned at runtime
+ * and thus attributes from a shared library may
+ * be out of order.
+ *
+ * We make two assumptions about the order of attributes:
+ * 1) The input has the same sorting rules applied to it as
+ *    the attribute data contained by this class.
+ * 2) Attributes are grouped by package ID.
+ * 3) Among attributes with the same package ID, the attributes are
+ *    sorted by increasing resource ID.
+ *
+ * Ex: 02010000, 02010001, 010100f4, 010100f5, 0x7f010001, 07f010003
+ *
+ * The total order of attributes (including package ID) can not be linear
+ * as shared libraries get assigned dynamic package IDs at runtime, which
+ * may break the sort order established at build time.
+ */
+template <typename Derived, typename Iterator>
+class BackTrackingAttributeFinder {
+public:
+    BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end);
+
+    Iterator find(uint32_t attr);
+
+private:
+    void jumpToClosestAttribute(uint32_t packageId);
+    void markCurrentPackageId(uint32_t packageId);
+
+    Iterator mBegin;
+    Iterator mEnd;
+    Iterator mCurrent;
+    Iterator mLargest;
+    uint32_t mLastPackageId;
+    uint32_t mCurrentAttr;
+
+    // Package Offsets (best-case, fast look-up).
+    Iterator mFrameworkStart;
+    Iterator mAppStart;
+
+    // Worst case, we have shared-library resources.
+    KeyedVector<uint32_t, Iterator> mPackageOffsets;
+};
+
+template <typename Derived, typename Iterator> inline
+BackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end)
+    : mBegin(begin)
+    , mEnd(end)
+    , mCurrent(begin)
+    , mLargest(begin)
+    , mLastPackageId(0)
+    , mCurrentAttr(0)
+    , mFrameworkStart(end)
+    , mAppStart(end) {
+}
+
+template <typename Derived, typename Iterator>
+void BackTrackingAttributeFinder<Derived, Iterator>::jumpToClosestAttribute(const uint32_t packageId) {
+    switch (packageId) {
+        case 0x01:
+            mCurrent = mFrameworkStart;
+            break;
+        case 0x7f:
+            mCurrent = mAppStart;
+            break;
+        default: {
+            ssize_t idx = mPackageOffsets.indexOfKey(packageId);
+            if (idx >= 0) {
+                // We have seen this package ID before, so jump to the first
+                // attribute with this package ID.
+                mCurrent = mPackageOffsets[idx];
+            } else {
+                mCurrent = mEnd;
+            }
+            break;
+        }
+    }
+
+    // We have never seen this package ID yet, so jump to the
+    // latest/largest index we have processed so far.
+    if (mCurrent == mEnd) {
+        mCurrent = mLargest;
+    }
+
+    if (mCurrent != mEnd) {
+        mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent);
+    }
+}
+
+template <typename Derived, typename Iterator>
+void BackTrackingAttributeFinder<Derived, Iterator>::markCurrentPackageId(const uint32_t packageId) {
+    switch (packageId) {
+        case 0x01:
+            mFrameworkStart = mCurrent;
+            break;
+        case 0x7f:
+            mAppStart = mCurrent;
+            break;
+        default:
+            mPackageOffsets.add(packageId, mCurrent);
+            break;
+    }
+}
+
+template <typename Derived, typename Iterator>
+Iterator BackTrackingAttributeFinder<Derived, Iterator>::find(uint32_t attr) {
+    if (!(mBegin < mEnd)) {
+        return mEnd;
+    }
+
+    if (mCurrentAttr == 0) {
+        // One-time initialization.
+        mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mBegin);
+        mLastPackageId = getPackage(mCurrentAttr);
+        markCurrentPackageId(mLastPackageId);
+    }
+
+    // Looking for the needle (attribute we're looking for)
+    // in the haystack (the attributes we're searching through)
+    const uint32_t needlePackageId = getPackage(attr);
+    if (mLastPackageId != needlePackageId) {
+        jumpToClosestAttribute(needlePackageId);
+        mLastPackageId = needlePackageId;
+    }
+
+    // Walk through the xml attributes looking for the requested attribute.
+    while (mCurrent != mEnd) {
+        const uint32_t haystackPackageId = getPackage(mCurrentAttr);
+        if (needlePackageId == haystackPackageId && attr < mCurrentAttr) {
+            // The attribute we are looking was not found.
+            break;
+        }
+        const uint32_t prevAttr = mCurrentAttr;
+
+        // Move to the next attribute in the XML.
+        ++mCurrent;
+        if (mCurrent != mEnd) {
+            mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent);
+            const uint32_t newHaystackPackageId = getPackage(mCurrentAttr);
+            if (haystackPackageId != newHaystackPackageId) {
+                // We've moved to the next group of attributes
+                // with a new package ID, so we should record
+                // the offset of this new package ID.
+                markCurrentPackageId(newHaystackPackageId);
+            }
+        }
+
+        if (mCurrent > mLargest) {
+            // We've moved past the latest attribute we've
+            // seen.
+            mLargest = mCurrent;
+        }
+
+        if (attr == prevAttr) {
+            // We found the attribute we were looking for.
+            return mCurrent - 1;
+        }
+    }
+    return mEnd;
+}
+
+} // namespace android
+
+#endif // H_ATTRIBUTE_FINDER
diff --git a/libs/androidfw/ResourceTypes.cpp b/libs/androidfw/ResourceTypes.cpp
index f1e4858..420fe38 100644
--- a/libs/androidfw/ResourceTypes.cpp
+++ b/libs/androidfw/ResourceTypes.cpp
@@ -1185,7 +1185,11 @@
 {
     int32_t id = getAttributeNameID(idx);
     if (id >= 0 && (size_t)id < mTree.mNumResIds) {
-        return dtohl(mTree.mResIds[id]);
+        uint32_t resId = dtohl(mTree.mResIds[id]);
+        if (mTree.mDynamicRefTable != NULL) {
+            mTree.mDynamicRefTable->lookupResourceId(&resId);
+        }
+        return resId;
     }
     return 0;
 }
@@ -5973,11 +5977,11 @@
     // Do a proper lookup.
     uint8_t translatedId = mLookupTable[packageId];
     if (translatedId == 0) {
-        ALOGE("DynamicRefTable(0x%02x): No mapping for build-time package ID 0x%02x.",
+        ALOGV("DynamicRefTable(0x%02x): No mapping for build-time package ID 0x%02x.",
                 (uint8_t)mAssignedPackageId, (uint8_t)packageId);
         for (size_t i = 0; i < 256; i++) {
             if (mLookupTable[i] != 0) {
-                ALOGE("e[0x%02x] -> 0x%02x", (uint8_t)i, mLookupTable[i]);
+                ALOGV("e[0x%02x] -> 0x%02x", (uint8_t)i, mLookupTable[i]);
             }
         }
         return UNKNOWN_ERROR;
diff --git a/libs/androidfw/tests/Android.mk b/libs/androidfw/tests/Android.mk
index 2d7906f..c1014be 100644
--- a/libs/androidfw/tests/Android.mk
+++ b/libs/androidfw/tests/Android.mk
@@ -20,6 +20,7 @@
 # ==========================================================
 LOCAL_PATH:= $(call my-dir)
 testFiles := \
+    AttributeFinder_test.cpp \
     ByteBucketArray_test.cpp \
     Config_test.cpp \
     ConfigLocale_test.cpp \
diff --git a/libs/androidfw/tests/AttributeFinder_test.cpp b/libs/androidfw/tests/AttributeFinder_test.cpp
new file mode 100644
index 0000000..664709c
--- /dev/null
+++ b/libs/androidfw/tests/AttributeFinder_test.cpp
@@ -0,0 +1,111 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <androidfw/AttributeFinder.h>
+
+#include <gtest/gtest.h>
+
+using android::BackTrackingAttributeFinder;
+
+class MockAttributeFinder : public BackTrackingAttributeFinder<MockAttributeFinder, int> {
+public:
+    MockAttributeFinder(const uint32_t* attrs, int len)
+        : BackTrackingAttributeFinder(0, len) {
+        mAttrs = new uint32_t[len];
+        memcpy(mAttrs, attrs, sizeof(*attrs) * len);
+    }
+
+    ~MockAttributeFinder() {
+        delete mAttrs;
+    }
+
+    inline uint32_t getAttribute(const int index) const {
+        return mAttrs[index];
+    }
+
+private:
+    uint32_t* mAttrs;
+};
+
+static const uint32_t sortedAttributes[] = {
+        0x01010000, 0x01010001, 0x01010002, 0x01010004,
+        0x02010001, 0x02010010, 0x7f010001
+};
+
+static const uint32_t packageUnsortedAttributes[] = {
+        0x02010001, 0x02010010, 0x01010000, 0x01010001,
+        0x01010002, 0x01010004, 0x7f010001
+};
+
+TEST(AttributeFinderTest, IteratesSequentially) {
+    const int end = sizeof(sortedAttributes) / sizeof(*sortedAttributes);
+    MockAttributeFinder finder(sortedAttributes, end);
+
+    EXPECT_EQ(0, finder.find(0x01010000));
+    EXPECT_EQ(1, finder.find(0x01010001));
+    EXPECT_EQ(2, finder.find(0x01010002));
+    EXPECT_EQ(3, finder.find(0x01010004));
+    EXPECT_EQ(4, finder.find(0x02010001));
+    EXPECT_EQ(5, finder.find(0x02010010));
+    EXPECT_EQ(6, finder.find(0x7f010001));
+    EXPECT_EQ(end, finder.find(0x7f010002));
+}
+
+TEST(AttributeFinderTest, PackagesAreOutOfOrder) {
+    const int end = sizeof(sortedAttributes) / sizeof(*sortedAttributes);
+    MockAttributeFinder finder(sortedAttributes, end);
+
+    EXPECT_EQ(6, finder.find(0x7f010001));
+    EXPECT_EQ(end, finder.find(0x7f010002));
+    EXPECT_EQ(4, finder.find(0x02010001));
+    EXPECT_EQ(5, finder.find(0x02010010));
+    EXPECT_EQ(0, finder.find(0x01010000));
+    EXPECT_EQ(1, finder.find(0x01010001));
+    EXPECT_EQ(2, finder.find(0x01010002));
+    EXPECT_EQ(3, finder.find(0x01010004));
+}
+
+TEST(AttributeFinderTest, SomeAttributesAreNotFound) {
+    const int end = sizeof(sortedAttributes) / sizeof(*sortedAttributes);
+    MockAttributeFinder finder(sortedAttributes, end);
+
+    EXPECT_EQ(0, finder.find(0x01010000));
+    EXPECT_EQ(1, finder.find(0x01010001));
+    EXPECT_EQ(2, finder.find(0x01010002));
+    EXPECT_EQ(end, finder.find(0x01010003));
+    EXPECT_EQ(3, finder.find(0x01010004));
+    EXPECT_EQ(end, finder.find(0x01010005));
+    EXPECT_EQ(end, finder.find(0x01010006));
+    EXPECT_EQ(4, finder.find(0x02010001));
+    EXPECT_EQ(end, finder.find(0x02010002));
+}
+
+TEST(AttributeFinderTest, FindAttributesInPackageUnsortedAttributeList) {
+    const int end = sizeof(packageUnsortedAttributes) / sizeof(*packageUnsortedAttributes);
+    MockAttributeFinder finder(packageUnsortedAttributes, end);
+
+    EXPECT_EQ(2, finder.find(0x01010000));
+    EXPECT_EQ(3, finder.find(0x01010001));
+    EXPECT_EQ(4, finder.find(0x01010002));
+    EXPECT_EQ(end, finder.find(0x01010003));
+    EXPECT_EQ(5, finder.find(0x01010004));
+    EXPECT_EQ(end, finder.find(0x01010005));
+    EXPECT_EQ(end, finder.find(0x01010006));
+    EXPECT_EQ(0, finder.find(0x02010001));
+    EXPECT_EQ(end, finder.find(0x02010002));
+    EXPECT_EQ(1, finder.find(0x02010010));
+    EXPECT_EQ(6, finder.find(0x7f010001));
+}