25,161
edits
Changes
Created page with "'''Home * People * Matt Taylor''' '''Matt Taylor''' was involved in forum discussions on low level optimization and x86 assembly language i..."
'''[[Main Page|Home]] * [[People]] * Matt Taylor'''
'''Matt Taylor''' was involved in forum discussions on low level optimization and [[x86]] [[Assembly|assembly language]] issues.
Beside other things Matt was busy to optimize a minimal perfect hashing scheme for [[BitScan|bitscan]] purposes.
=BitScan=
Based on ideas of [[Walter Faxon]] and [[BitScan#DeBruijnMultiplation|De Bruijn Multiplication]], Matt came up with a [[BitScan#MattTaylorsFoldingtrick|genius folding trick]] as a quintessence <ref>[http://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/de9546cd019bd72b/f46209f47d2a7ddb?lnk=gst&q=Matt+Taylor+magic#f46209f47d2a7ddb Bit magic] by [[Matt Taylor]], [http://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], June 26, 2003</ref>:
<pre>
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];
}
</pre>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=275160 Bitscan Conclusions] by [[Matt Taylor]], [[CCC]], January 05, 2003
* [https://www.stmintz.com/ccc/index.php?id=278848 Cleverness, Please!] by [[Matt Taylor]], [[CCC]], January 22, 2003
* [https://www.stmintz.com/ccc/index.php?id=283655 Bitscan] by [[Matt Taylor]], [[CCC]], February 11, 2003
* [http://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/de9546cd019bd72b Bit magic] by [[Matt Taylor]], [http://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], June 26, 2003
* [http://groups.google.com/group/comp.lang.asm.x86/msg/26c662942c961ecd Re: Static memory allocation] by [[Matt Taylor]], [http://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], July 03, 2004
=References=
<references />
'''[[People|Up one level]]'''
'''Matt Taylor''' was involved in forum discussions on low level optimization and [[x86]] [[Assembly|assembly language]] issues.
Beside other things Matt was busy to optimize a minimal perfect hashing scheme for [[BitScan|bitscan]] purposes.
=BitScan=
Based on ideas of [[Walter Faxon]] and [[BitScan#DeBruijnMultiplation|De Bruijn Multiplication]], Matt came up with a [[BitScan#MattTaylorsFoldingtrick|genius folding trick]] as a quintessence <ref>[http://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/de9546cd019bd72b/f46209f47d2a7ddb?lnk=gst&q=Matt+Taylor+magic#f46209f47d2a7ddb Bit magic] by [[Matt Taylor]], [http://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], June 26, 2003</ref>:
<pre>
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];
}
</pre>
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=275160 Bitscan Conclusions] by [[Matt Taylor]], [[CCC]], January 05, 2003
* [https://www.stmintz.com/ccc/index.php?id=278848 Cleverness, Please!] by [[Matt Taylor]], [[CCC]], January 22, 2003
* [https://www.stmintz.com/ccc/index.php?id=283655 Bitscan] by [[Matt Taylor]], [[CCC]], February 11, 2003
* [http://groups.google.com/group/comp.lang.asm.x86/browse_frm/thread/de9546cd019bd72b Bit magic] by [[Matt Taylor]], [http://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], June 26, 2003
* [http://groups.google.com/group/comp.lang.asm.x86/msg/26c662942c961ecd Re: Static memory allocation] by [[Matt Taylor]], [http://groups.google.com/group/comp.lang.asm.x86/topics comp.lang.asm.x86], July 03, 2004
=References=
<references />
'''[[People|Up one level]]'''
