Reviewers: Kasper Lund, Message: A fun review for you.
Description: Change the utils WhichPowerOf2 function to use a simpler algorithm. Please review this at http://codereview.chromium.org/4247004/show SVN Base: http://v8.googlecode.com/svn/branches/bleeding_edge/ Affected files: M src/utils.h M src/utils.cc M test/cctest/test-utils.cc Index: src/utils.cc =================================================================== --- src/utils.cc (revision 5762) +++ src/utils.cc (working copy) @@ -51,6 +51,15 @@ } +// Every power of 2 from 2^0 to 2^35 has a different remainder modulo 37. +// If (1 << i) % 37 == x, then kPowersOf2Modulo37[x] = i. +int kPowersOf2Modulo37[] = { + -1, 0, 1, 26, 2, 23, 27, -1, 3, 16, 24, + 30, 28, 11, -1, 13, 4, 7, 17, -1, 25, + 22, 31, 15, 29, 10, 12, 6, -1, 21, 14, + 9, 5, 20, 8, 19, 18}; + + // Thomas Wang, Integer Hash Functions. // http://www.concentric.net/~Ttwang/tech/inthash.htm uint32_t ComputeIntegerHash(uint32_t key) { Index: src/utils.h =================================================================== --- src/utils.h (revision 5762) +++ src/utils.h (working copy) @@ -46,6 +46,7 @@ return IS_POWER_OF_TWO(x); } +extern int kPowersOf2Modulo37[]; // X must be a power of 2. Returns the number of trailing zeros. template <typename T> @@ -53,32 +54,9 @@ ASSERT(IsPowerOf2(x)); ASSERT(x != 0); if (x < 0) return 31; - int bits = 0; -#ifdef DEBUG - int original_x = x; -#endif - if (x >= 0x10000) { - bits += 16; - x >>= 16; - } - if (x >= 0x100) { - bits += 8; - x >>= 8; - } - if (x >= 0x10) { - bits += 4; - x >>= 4; - } - switch (x) { - default: UNREACHABLE(); - case 8: bits++; // Fall through. - case 4: bits++; // Fall through. - case 2: bits++; // Fall through. - case 1: break; - } - ASSERT_EQ(1 << bits, original_x); + int bits = kPowersOf2Modulo37[x % 37]; + ASSERT_EQ(1 << bits, x); return bits; - return 0; } Index: test/cctest/test-utils.cc =================================================================== --- test/cctest/test-utils.cc (revision 5762) +++ test/cctest/test-utils.cc (working copy) @@ -192,3 +192,11 @@ } result.Dispose(); } + + +TEST(WhichPower) { + const int kMaxPowerOf2 = 31; // Maximum valid power for WhichPowerOf2. + for (int i = 0; i <= kMaxPowerOf2; ++i) { + CHECK_EQ(i, WhichPowerOf2(1 << i)); + } +} -- v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev
