Author: Gerd Isenberg
Date: 12:05:26 07/14/03
Go up one level in this thread
On July 14, 2003 at 09:54:39, Walter Faxon wrote:
>On July 13, 2003 at 12:51:45, Gerd Isenberg wrote (after snipping):
>
>>Hi Bas,
>>
>>Nice constants, but they map 32-bit to a range of 64 or 60 - about the double
>>space as necessary ;-) Ahh, you use signed char for table, may be a additional
>>and 0xff or movsx instead of mov. Why not using de Bruijn constants, that map to
>>a range of 32?
>>
>>Regards,
>>Gerd
>
>
>Hi, Gerd; Bas.
>
>Here's one with a 32-byte array, and (hopefully) use of conditional-move instead
>of a branch, which reduces the code size as well. Again, this version doesn't
>remove the bit. An unsigned byte table is ok if we can 'or' the byte into a
>byte-addressable register, I think.
>
>A smaller table doesn't solve the cache problem, but still, smaller should be
>better. There's got to be some way to disable replacement of some cache lines.
>
>-- Walter
>
>
>// ---------------------------------------------------------------------------
>// Should we use a union to force better alignment of this table?
>const unsigned char MT32table [32] = {
> 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
> 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
>
>// Constant, table reference and inline function below, all in header file.
>// There are 1024 such constants possible.
>
>#define MT32magic (130329821UL)
>extern const unsigned char MT32table [32];
>
>/* Return index of least-significant bit of 64; argument must be non-zero.
> "Magic" indexing algorithm by Matt Taylor.
> Version for 32-bit architecture by WF.
> No warranty.
>*/
>__forceinline int leastSigBit64( unsigned __int64 bb )
>{
> unsigned long bb0, bb1;
> int bbHalf;
>
> bb0 = ((unsigned long*)&bb)[0];
> bb1 = ((unsigned long*)&bb)[1]; // if bb in registers, no code
> bbHalf = (bb0 == 0);
> if (bbHalf) bb0 = bb1; // will code as cmov (ideally)
> bb0 ^= bb0 - 1;
> bb0 *= MT32magic;
> return (bbHalf << 5) | MT32table[bb0 >> 27];
> // if bbHalf in byte-addressable register, bitwise-or
> // preferred to avoid int+char type/sizing conflict
>}
>
>//eof
Hi Walter,
that's what i meant. Unfortunately no cmov with MSVC 6 :-(
Therefore i would prefere the unconditional one with the 0x78291ACF with
64-Byte lookup table.
Regards,
Gerd
My small De Bruijn Test of 130329821:
0x07C4ACDD
00000111110001001010110011011101B
bit 31 - bit 27 00000 0
bit 30 - bit 26 00001 1
bit 29 - bit 25 00011 3
bit 28 - bit 24 00111 7
bit 27 - bit 23 01111 15
bit 26 - bit 22 11111 31
bit 25 - bit 21 11110 30
bit 24 - bit 20 11100 28
bit 23 - bit 19 11000 24
bit 22 - bit 18 10001 17
bit 21 - bit 17 00010 2
bit 20 - bit 16 00100 4
bit 19 - bit 15 01001 9
bit 18 - bit 14 10010 18
bit 17 - bit 13 00101 5
bit 16 - bit 12 01010 10
bit 15 - bit 11 10101 21
bit 14 - bit 10 01011 11
bit 13 - bit 9 10110 22
bit 12 - bit 8 01100 12
bit 11 - bit 7 11001 25
bit 10 - bit 6 10011 19
bit 9 - bit 5 00110 6
bit 8 - bit 4 01101 13
bit 7 - bit 3 11011 27
bit 6 - bit 2 10111 23
bit 5 - bit 1 01110 14
bit 4 - bit 0 11101 29
0x07C4ACDD is 5bit de Bruin Sequence
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.