+//
+// This function is the hotspot of symbol lookup. It was pulled out of findExportedSymbol()
+// to enable it to be re-written in assembler if needed.
+//
+const uint8_t* ImageLoader::trieWalk(const uint8_t* start, const uint8_t* end, const char* s)
+{
+ //dyld::log("trieWalk(%p, %p, %s)\n", start, end, s);
+ ++fgSymbolTrieSearchs;
+ const uint8_t* p = start;
+ while ( p != NULL ) {
+ uintptr_t terminalSize = *p++;
+ if ( terminalSize > 127 ) {
+ // except for re-export-with-rename, all terminal sizes fit in one byte
+ --p;
+ terminalSize = read_uleb128(p, end);
+ }
+ if ( (*s == '\0') && (terminalSize != 0) ) {
+ //dyld::log("trieWalk(%p) returning %p\n", start, p);
+ return p;
+ }
+ const uint8_t* children = p + terminalSize;
+ if ( children > end ) {
+ dyld::log("trieWalk() malformed trie node, terminalSize=0x%lx extends past end of trie\n", terminalSize);
+ return NULL;
+ }
+ //dyld::log("trieWalk(%p) sym=%s, terminalSize=%lu, children=%p\n", start, s, terminalSize, children);
+ uint8_t childrenRemaining = *children++;
+ p = children;
+ uintptr_t nodeOffset = 0;
+ for (; childrenRemaining > 0; --childrenRemaining) {
+ const char* ss = s;
+ //dyld::log("trieWalk(%p) child str=%s\n", start, (char*)p);
+ bool wrongEdge = false;
+ // scan whole edge to get to next edge
+ // if edge is longer than target symbol name, don't read past end of symbol name
+ char c = *p;
+ while ( c != '\0' ) {
+ if ( !wrongEdge ) {
+ if ( c != *ss )
+ wrongEdge = true;
+ ++ss;
+ }
+ ++p;
+ c = *p;
+ }
+ if ( wrongEdge ) {
+ // advance to next child
+ ++p; // skip over zero terminator
+ // skip over uleb128 until last byte is found
+ while ( (*p & 0x80) != 0 )
+ ++p;
+ ++p; // skip over last byte of uleb128
+ if ( p > end ) {
+ dyld::log("trieWalk() malformed trie node, child node extends past end of trie\n");
+ return NULL;
+ }
+ }
+ else {
+ // the symbol so far matches this edge (child)
+ // so advance to the child's node
+ ++p;
+ nodeOffset = read_uleb128(p, end);
+ if ( (nodeOffset == 0) || ( &start[nodeOffset] > end) ) {
+ dyld::log("trieWalk() malformed trie child, nodeOffset=0x%lx out of range\n", nodeOffset);
+ return NULL;
+ }
+ s = ss;
+ //dyld::log("trieWalk() found matching edge advancing to node 0x%lx\n", nodeOffset);
+ break;
+ }
+ }
+ if ( nodeOffset != 0 )
+ p = &start[nodeOffset];
+ else
+ p = NULL;
+ }
+ //dyld::log("trieWalk(%p) return NULL\n", start);
+ return NULL;
+}
+
+
+
+uintptr_t ImageLoader::read_uleb128(const uint8_t*& p, const uint8_t* end)
+{
+ uint64_t result = 0;
+ int bit = 0;
+ do {
+ if (p == end)
+ dyld::throwf("malformed uleb128");
+
+ uint64_t slice = *p & 0x7f;
+
+ if (bit > 63)
+ dyld::throwf("uleb128 too big for uint64, bit=%d, result=0x%0llX", bit, result);
+ else {
+ result |= (slice << bit);
+ bit += 7;
+ }
+ } while (*p++ & 0x80);
+ return (uintptr_t)result;
+}
+
+
+intptr_t ImageLoader::read_sleb128(const uint8_t*& p, const uint8_t* end)
+{
+ int64_t result = 0;
+ int bit = 0;
+ uint8_t byte;
+ do {
+ if (p == end)
+ throw "malformed sleb128";
+ byte = *p++;
+ result |= (((int64_t)(byte & 0x7f)) << bit);
+ bit += 7;
+ } while (byte & 0x80);
+ // sign extend negative numbers
+ if ( (byte & 0x40) != 0 )
+ result |= (~0ULL) << bit;
+ return (intptr_t)result;
+}
+
+
projects / apple / dyld.git / blobdiff