A few thoughts

[Genbox]

Hi hypervis0r and Jeff,

Interesting blogpost from you guys. A few things came to mind while reading it. Hope you don't mind me dumping a few of them here.

• Hashing is tricky. It is a tradeoff between performance and entropy. DJB2 hash is great for its simplicity, but you can get a lot more speed out of a modern CPU with another equally well-randomized hash function. Checkout SMhasher for inspiration. The trick in your case would be to hash more data at the same time.
• If your hash table is bounded by an upper bound, such as your case when you pre-generate a hash table at compile-time, it is possible to generate a hash function that would not only be faster but map directly from X to Y without using a general-purpose hash function. Such a hash is called a "perfect hash". It maps distinct items of a set to an offset in an array at the cost of overhead in memory. There are also minimal perfect hash functions that take longer to construct but have no overhead. Check out the CMPH project.
• PE export tables also support lookup by ordinal. You better be sure it is exported when calling it, but it does make for some interesting optimizations both with hash tables and binary search since sorting/hashing integers is much faster.

[hypervis0r]

Hey, thanks for your input!

1. I definitely know that there are a few hashing algorithms that are way more optimized and efficient than DJB2 (murmurHash and xxHash are two that come to mind). However, this is simply meant to be a proof of concept to demonstrate that GetProcAddress could be made faster (and also I'm lazy). If you could write a PoC that uses a faster hash algorithm, I would love to see those results, but that goes beyond the scope of this PoC.

2. I did some research into perfect hashing when writing case 6, as of course this would make sense in the terms of a constant-sized hash table. The main issue with perfect hashing is the fact that you need a different hash algorithm for all different combinations of input, and portability would be lost. I had a thought that maybe the hash function could be compiled into the PE binary itself, but I'm not sure about the feasibility of this.

3. Of course these cases do not demonstrate search via ordinal, which is essential. They also do not support forwarders, which are also used often with Microsoft DLLs such as kernel32.dll. As I've said before, this is simply a proof of concept to demonstrate different search methods.