Difference between revisions of "Matt Taylor"
GerdIsenberg (talk | contribs) (Created page with "'''Home * People * Matt Taylor''' '''Matt Taylor''' was involved in forum discussions on low level optimization and x86 assembly language i...") |
(No difference)
|
Revision as of 15:09, 27 February 2019
Matt Taylor was involved in forum discussions on low level optimization and x86 assembly language issues. Beside other things Matt was busy to optimize a minimal perfect hashing scheme for bitscan purposes.
BitScan
Based on ideas of Walter Faxon and De Bruijn Multiplication, Matt came up with a genius folding trick as a quintessence [1]:
const int lsb_64_table[64] = { 63, 30, 3, 32, 59, 14, 11, 33, 60, 24, 50, 9, 55, 19, 21, 34, 61, 29, 2, 53, 51, 23, 41, 18, 56, 28, 1, 43, 46, 27, 0, 35, 62, 31, 58, 4, 5, 49, 54, 6, 15, 52, 12, 40, 7, 42, 45, 16, 25, 57, 48, 13, 10, 39, 8, 44, 20, 47, 38, 22, 17, 37, 36, 26 }; /** * bitScanForward * @author Matt Taylor (2003) * @param bb bitboard to scan * @precondition bb != 0 * @return index (0..63) of least significant one bit */ int bitScanForward(U64 bb) { unsigned int folded; assert (bb != 0); bb ^= bb - 1; folded = (int) bb ^ (bb >> 32); return lsb_64_table[folded * 0x78291ACF >> 26]; }
Forum Posts
- Bitscan Conclusions by Matt Taylor, CCC, January 05, 2003
- Cleverness, Please! by Matt Taylor, CCC, January 22, 2003
- Bitscan by Matt Taylor, CCC, February 11, 2003
- Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
- Re: Static memory allocation by Matt Taylor, comp.lang.asm.x86, July 03, 2004
References
- ↑ Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003