BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits

[Aleks Peshkov]

The fascinating thing is the number of possible approaches to get sliding attacks. It is still a nice cycle hunting challenge and contest for some of us

I am very happy with forgotten Gerd's "bswap" approach:

Code: Select all

    struct M {
        BitBoard singleton; //optional well-known "bitmask" (1 << sq)
        BitBoard vertical; //attack direction on empty board
        BitBoard diagonal;
        BitBoard antidiag;
        BitBoard knight;
        BitBoard king;
        BitBoard whitePawn;
        BitBoard blackPawn;
    } mask[64];

    BitBoard attack(Square from, BitBoard occupied, BitBoard dirMask) const {
        bit64_t forward = occupied & dirMask;
        bit64_t reverse = bswap(forward);
        forward -= mask[from].singleton;
        reverse -= mask[from ^ 070].singleton;
        forward ^= bswap(reverse);
        return BitBoard(forward & dirMask);
    }

    BitBoard bishop(Square from, BitBoard occupied) const {
        return
            attack(from, occupied, mask[from].diagonal) |
            attack(from, occupied, mask[from].antidiag);
    }

    BitBoard rook(Square from, BitBoard occupied) const {
        return
            attack(from, occupied, mask[from].vertical) |
            rankAttack(from, occupied); //any traditional approach
    }

32 bit and cache friendly. Memory acceses nicely interleaved with simple arithmetic.

[Carey]

The fascinating thing is the number of possible approaches to get sliding attacks. It is still a nice cycle hunting challenge and contest for some of us

There has been a staggering amount of research and results the past couple years.

You and a few others have really revolutionized bitboard data structures.

It's safe to say that if you had tried to do all this back in the days of the ICCA, with its quartlery journal, there wouldn't have been nearly as much progress made.

Your mentioned Pitty method (was not aware on that name) is still worth

The method is so old I doubt it has a name.

That was probably the way Slate & Atkin did some bitboard stuff way back in the selective search Chess 3.x. At the very least, it comes pretty direct from their Chess 4.x and Atkin's Chess 0.5 program.

I called it the 'Pitty method' for several reasons, including that if you try to do rotated bitboards for your very first chess program, somebody needs to take pity on you and suggest a simpler way.

(It is worth pointing out that when he told me he had tried this method, I was definetly surprised he got good results. With the branch misses and the bsf/bsr's I did not expect decent performance.)

to consider with nowadays faster bitscans (core2duo, K10 - K8 has slow 9-10 cycles vector path bitscans - not to mention P4). Specially if you need

That was kind of my feeling too. But since I don't have a 64 bit system (or even a fast 32 bit system), I don't really know what the performance would be. Possibly pretty good though.

one direction only. It is for instance great to get the source square of direction wise target-sets from kogge-stone fills, with different cases (bsr/bsf) for positive and negative directions.

The advantage is the small 4-KByte lookup array and moderate register

Your 1.5k aproach is better. That's what I prefer, even if it's not as fast as other methods. It's just more elegant.

usage. Also it only deals with one but no rotated occupied bitboards and is therefor as versatile as magics. Drawback are the four branches with some chance of miss-predictions up and then and the sequential nature.

Don't the newer X2's & Core2's behave differently in this?

Also, what about the built in compare & swap etc. instruction(s)? Would those be better?

What about a jumpless version. Something to make Mask = $f...f or 0 depending whether Board has any bits at all. Then you could do Bit=Mask&(bsf()+1)

Don't know.... Just throwing out ideas. I don't know the x86 instruction set too well. Can't stand assembler anymore.

Up to eight L1 reads, likely distinct cachelines, four (conditional) bitscans,

It'd only have to be one cache line, though. Put all 8 rays into one data structure. 8 rays of 8 bytes each equals 64 bytes. One cache line.

xors, some ors sounds not that cheap. Otoh with a polluted L1 it might be better to stay with a few branch misses rather than a lot of L1-misses. I wonder how many % L1 misses are necessary so that and, mul, shr, lookup, becomes slower, reading mask/factor/shiftamount[sq] from one cacheline and the lookup from a second.

Finally, emprical evidence for a particular program/cpu is what counts. And if we are talking about 1%-noise in total program performance, I suggest to take the appraoch you like or even (re-)invent by yourself.

There is always personal preference, yes.

But if it works and is competitive, then I think it could be quite practical. Even perhaps recommended for newbies. It's something they could easily understand.

As for the performance... Who knows... it might be 10% faster. Or 20% slower.


But it is an interesting idea. Everybody has been talking about every other fancy method that I just finally decided I had to ask about this classical 'stupid' method.

[Carey]

Up to eight L1 reads, likely distinct cachelines, four (conditional) bitscans,

It'd only have to be one cache line, though. Put all 8 rays into one data structure. 8 rays of 8 bytes each equals 64 bytes. One cache line.

Arghhhh. I'm stupid.

I realize what you mean now.

Don't know what I was thinking. Probably not thinking at all.

Yes, it would cause 8 cache lines. But you might be able to reduce that a little.

Maybe adding two new arrays. One for the 'forward' directions and one for the 'reverse' directions. Those would get accessed more often and might still be in the cache? Just a guess, though.

I wonder if you could compress the 8 rays down to just 4, with each one covering both directions. Combining them with the Forward & Reverse arrays would get the direction needed.

Not sure it'd be worth the effort, though.

(shrug)

[Gerd Isenberg]

The fascinating thing is the number of possible approaches to get sliding attacks. It is still a nice cycle hunting challenge and contest for some of us

There has been a staggering amount of research and results the past couple years.

You and a few others have really revolutionized bitboard data structures.

It's safe to say that if you had tried to do all this back in the days of the ICCA, with its quartlery journal, there wouldn't have been nearly as much progress made.

Thank you for your kind words, I only picked up some ideas from others. Kindergarten bitboards is just a minor extension of Steffan Westcott's collapsed file/rank-index routines. http://www.stmintz.com/ccc/index.php?id=491079

I can't imagine that multiplicative hashing of the occupancies wasn't thought or tried before by the old pioneers, but multiplication was much too expensive that times.

Beside their Inventors, Arthur Samuel, Adelson-Velsky, Slate and Atkins, the bitboard revolutionaries were Bob Hyatt and Ernst Heinz with the rotated bitboards idea. http://en.wikipedia.org/wiki/Bitboard#History

The guy (knows somebody his name?) who wrote the hyperbolica paper in 99, introducing reversed bitboards and the idea (at least to me) to use

Code: Select all

   attacks := occupied ^ (occupied - 2*rooks) 

Albeit it was only used with single sliders, masked rays and shifted squares, the expression works setwise (multiple rooks) in principle - that is with carry or borrow propagation in all eight but not only one direction.
Steffan Westcott, introduced the Kogge-Stone routines - which perform in principle the above expression in all eight directions setwise. To treat sliding attacks as carries of parallel prefix adders. Probably this was the most revolutionary or vanguard approach.

If we classify sliding attack approaches, I would come up with

1.) mapping the relevant occupancy to consecutive bits of an index, to lookup some precalculated tables. Rotated, magic, kindergarten, etc.

2.) arithmetical approaches to direct calculate the attack set. With more or less help of precalculated tables.

[Gerd Isenberg]

Don't the newer X2's & Core2's behave differently in this?

Branch prediction has improved a lot. But still it is possible to pollute
some ressources related to it, namely branch target buffer.

Also, what about the built in compare & swap etc. instruction(s)? Would those be better?

What about a jumpless version. Something to make Mask = $f...f or 0 depending whether Board has any bits at all. Then you could do Bit=Mask&(bsf()+1)

Don't know.... Just throwing out ideas. I don't know the x86 instruction set too well. Can't stand assembler anymore.

We will have fast leading zero count (beside popcount) in K10 and new intels. They may be treated as a branchless bsr^63, since lzc returns 64 for empty sets. For emulating bitscan forward by lzc, intersect the two's complement is necessary, to isolate the least significant bit (if any).

[Harald]

bb_attacks_sherwin_union:

Code: Select all

/*******************************************************************/
/*
The bitboard attacks of Michael Sherwin with union 
as part of the board structure.

(c) 2006 Harald Lüßen
*/
/*******************************************************************/


#include "bb_ifdef.h"
#include "bb_basics.h"
#include "bb_bitboard.h"
#include "bb_board.h"
#include "bb_main.h"


#if USE_SHERWIN_UNION_BITBOARDS()

/*******************************************************************/

/*
    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+

    We use this mapping of the normal board squares to bitboard bits
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h
*/

/*******************************************************************/

// Make sure this is done right.
#define BIG_ENDIAN()    (0)
#define LITTLE_ENDIAN() (1)

#if BIG_ENDIAN() && !LITTLE_ENDIAN()
// Big end first means row 8 is first byte with my square encoding.
struct BBBytes
{
    unsigned char row8;
    unsigned char row7;
    unsigned char row6;
    unsigned char row5;
    unsigned char row4;
    unsigned char row3;
    unsigned char row2;
    unsigned char row1;
};
#elif LITTLE_ENDIAN() && !BIG_ENDIAN()
// Little end first means row 1 is first byte with my square encoding.
struct BBBytes
{
    unsigned char row1;
    unsigned char row2;
    unsigned char row3;
    unsigned char row4;
    unsigned char row5;
    unsigned char row6;
    unsigned char row7;
    unsigned char row8;
};
#else
    #error big little endian
#endif


union BBUnion
{
    Bits64   bb;
    BBBytes  bbb;
};


/*******************************************************************/

// Bishops

/*
The typical 1-bits of a bishop on d4 are shown below, 
with - indicating a don't care bit:
 . . . . . . . -
 - . . . . . 1 .  giving 1 bit  or 2 different values from row 7
 . 1 . . . 1 . .  giving 2 bits or 4 different values from row 6
 . . 1 . 1 . . .  giving 2 bits or 4 different values from row 5
 . . . B . . . .  giving 0 bits or 0 different values from row 4
 . . 1 . 1 . . .  giving 2 bits or 4 different values from row 3
 . 1 . . . 1 . .  giving 2 bits or 4 different values from row 2
 - . . . . . - .

The values are just a mapping of the relevant bits to a compact value. 
For bits named a to i the value for Bd4 will be:
 . . . . . . . -
 - . . . . . i .  giving 1 bit  or 2 different values from row 7
 . g . . . h . .  giving 2 bits or 4 different values from row 6
 . . e . f . . .  giving 2 bits or 4 different values from row 5
 . . . B . . . .  giving 0 bits or 0 different values from row 4
 . . c . d . . .  giving 2 bits or 4 different values from row 3
 . a . . . b . .  giving 2 bits or 4 different values from row 2
 - . . . . . - .

-> 0x0000000ihgfedcba as index. With 2^9 = 512 index values. 

There are 4 squares with 9 bits like Bd4. Other squares need another amount of bits.

 6 5 5 5 5 5 5 6
 5 5 5 5 5 5 5 5
 5 5 7 7 7 7 5 5
 5 5 7 9 9 7 5 5
 5 5 7 9 9 7 5 5
 5 5 7 7 7 7 5 5
 5 5 5 5 5 5 5 5
 6 5 5 5 5 5 5 6

 4 squares with 9 bits for 512 indices are 2048 indices.
12 squares with 7 bits for 128 indices are 1536 indices.
44 squares with 5 bits for  32 indices are 1408 indices.
 4 squares with 6 bits for  64 indices are  256 indices.
                                     Total 5248 indices.
*/

// The big X mask for all moves from sq, but only inner 6x6 area
Bitboard bishopBits[64];

void initBishopBits()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        bishopBits[sq] = 0;
        int i;
        for ( i = sq - 9; i >= 0 && i % 8 != 7; i -= 9 )
        {
            bishopBits[sq] |= C64(1) << i;
        }
        for ( i = sq - 7; i >= 0 && i % 8 != 0; i -= 7 )
        {
            bishopBits[sq] |= C64(1) << i;
        }
        for ( i = sq + 9; i < 64 && i % 8 != 0; i += 9 )
        {
            bishopBits[sq] |= C64(1) << i;
        }
        for ( i = sq + 7; i < 64 && i % 8 != 7; i += 7 )
        {
            bishopBits[sq] |= C64(1) << i;
        }
        bishopBits[sq] &= C64(0x007e7e7e7e7e7e00);
        //logf << "bishopBits " << sq << endl;
        //logf << bishopBits[sq].txt8lines() << endl;
    }
}


// Number of needed bits per square for bishops
const byte squareBitsB[64] = 
{
  6, 5, 5, 5, 5, 5, 5, 6,
  5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 9, 9, 7, 5, 5,
  5, 5, 7, 7, 7, 7, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5,
  6, 5, 5, 5, 5, 5, 5, 6,
};


/*
The big Table with index-bits for all rows.
The indices are in this order:
0000999999999 4 times 9 bit
0001999999999
0010999999999
0011999999999
0100007777777 12 times 7 bit
01....7777777
0110117777777
0111000666666 4 times 6 bit
0111001666666
0111010666666
0111011666666
0111100055555 44 times 5 bit
........55555
1010001155555
bishopRows[sq][row2to7][bitsOnRow]
*/
short int bishopRows[64][6][64];

void initBishopRows()
{
    int baseIndex = 0;
    for ( int bits = 9; bits >= 5; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsB[sq] != bits )
                continue;
            Bitboard bb = bishopBits[sq];
            bb >>= 9;
            int shift = 0;
            for ( int row = 0; row < 6; ++row )
            {
                int p = (bb >> (row * 8)) & 0x3f;
                for ( int pattern = 0; pattern < 64; ++pattern )
                {
                    int index = 0;
                    int s = shift;
                    for ( int i = 0; i < 6; ++i )
                    {
                        if ( p & (1 << i) )
                        {
                            index |= ( (pattern & (1 << i)) ? (1 << s) : 0 );
                            s++;
                            if ( pattern == 63 )
                                shift++;
                        }
                    }
                    bishopRows[sq][row][pattern] = baseIndex + index;
                    //logf << "bishopRows " << sq << " " << row << " " << pattern << " : ";
                    //logf << bishopRows[sq][row][pattern] << endl;
                }
            }
            baseIndex += (1 << bits);
        }
    }
}


// From index to attack bits
Bitboard bishopAttackTable[5248];

void initBishopAttacks()
{
    int baseIndex = 0;
    for ( int bits = 9; bits >= 5; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsB[sq] != bits )
                continue;
            Bitboard bb = bishopBits[sq];
            for ( int index = 0; index < (1 << bits); ++ index )
            {
                Bitboard occ = 0;
                int i = index;
                for ( int rsq = 0; rsq < 64; ++rsq )
                {
                    if ( bb.test_bit( rsq ) )
                    {
                        if ( i & 1 )
                            occ.set_bit( rsq );
                        i >>= 1;
                    }
                }
                Bitboard att = 0;
                int j;
                for ( j = sq + 9; j < 64 && (j & 7) != 0; j += 9 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq + 7; j < 64 && (j & 7) != 7; j += 7 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 9; j >= 0 && (j & 7) != 7; j -= 9 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 7; j >= 0 && (j & 7) != 0; j -= 7 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                bishopAttackTable[baseIndex + index] = att;
            }
            baseIndex += (1 << bits);
        }
    }
}


/**
The bishop attack bitboard for a square and occupied bitboard
*/
Bitboard bishopAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the X-rays
    occ  &= bishopBits[sq]; 
    occ >>= 1;
    BBUnion occu;
    occu.bb = occ;

    // Since every square has its set of row values the six row lookups 
    // simply map any blockers to specific bits that when ored together 
    // gives an offset in the bishop attack table.
    short int *bRows = &bishopRows[sq][0][0];
    int index = (bRows +   0)[occu.bbb.row2]  // row 2
              | (bRows +  64)[occu.bbb.row3]  // row 3
              | (bRows + 128)[occu.bbb.row4]  // row 4
              | (bRows + 192)[occu.bbb.row5]  // row 5
              | (bRows + 256)[occu.bbb.row6]  // row 6
              | (bRows + 320)[occu.bbb.row7]; // row 7
    return bishopAttackTable[index];
}


/*******************************************************************/

// Rooks

/*
The required bit number per square for rooks looks like this:

12 11 11 11 11 11 11 12    4 x 12 bit =  4 x 4096 entries = 16384
11 10 10 10 10 10 10 11   24 x 11 bit = 24 x 2048 entries = 49152
11 10 10 10 10 10 10 11   36 x 10 bit = 36 x 1024 entries = 36864
11 10 10 10 10 10 10 11                            total = 102400
11 10 10 10 10 10 10 11
11 10 10 10 10 10 10 11
11 10 10 10 10 10 10 11
12 11 11 11 11 11 11 12
*/

// The big + mask for all moves from sq
Bitboard rookBits[64];

void initRookBits()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        rookBits[sq] = 0;
        int i;
        for ( i = sq - 1; i >= 0 && i % 8 != 7; --i )
        {
            rookBits[sq] |= C64(1) << i;
        }
        for ( i = sq - 8; i >= 0; i -= 8 )
        {
            rookBits[sq] |= C64(1) << i;
        }
        for ( i = sq + 1; i < 64 && i % 8 != 0; ++i )
        {
            rookBits[sq] |= C64(1) << i;
        }
        for ( i = sq + 8; i < 64; i += 8 )
        {
            rookBits[sq] |= C64(1) << i;
        }
        if ( (sq & 7) != 7 )
            rookBits[sq] &= C64(0x7f7f7f7f7f7f7f7f);
        if ( (sq & 7) != 0 )
            rookBits[sq] &= C64(0xfefefefefefefefe);
        if ( (sq / 8) != 7 )
            rookBits[sq] &= C64(0x00ffffffffffffff);
        if ( (sq / 8) != 0 )
            rookBits[sq] &= C64(0xffffffffffffff00);
        //logf << "rookBits " << sq << endl;
        //logf << rookBits[sq].txt8lines() << endl;
    }
}


// Number of needed bits per square for rooks
const byte squareBitsR[64] = 
{
  12, 11, 11, 11, 11, 11, 11, 12,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  11, 10, 10, 10, 10, 10, 10, 11,
  12, 11, 11, 11, 11, 11, 11, 12,
};


/*
The big Table with index-bits for all rows.
The indices are in this order:
00000cccccccccccc 4 times 12 bit
00001cccccccccccc
00010cccccccccccc
00011cccccccccccc
001000bbbbbbbbbbb 24 times 11 bit
0.....bbbbbbbbbbb
100111bbbbbbbbbbb
1010000aaaaaaaaaa 36 times 10 bit
.......aaaaaaaaaa
1110011aaaaaaaaaa
This index is very big because its values (0-102400) do not fit in 2 byte short int.
rookRows[sq][row1to8][bitsOnRow]
*/
int rookRows[64][8][256];

void initRookRows()
{
    int baseIndex = 0;
    for ( int bits = 12; bits >= 10; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsR[sq] != bits )
                continue;
            Bitboard bb = rookBits[sq];
            int shift = 0;
            for ( int row = 0; row < 8; ++row )
            {
                int p = (bb >> (row * 8)) & 0xff;
                for ( int pattern = 0; pattern < 256; ++pattern )
                {
                    int index = 0;
                    int s = shift;
                    for ( int i = 0; i < 8; ++i )
                    {
                        if ( p & (1 << i) )
                        {
                            index |= ( (pattern & (1 << i)) ? (1 << s) : 0 );
                            s++;
                            if ( pattern == 255 )
                                shift++;
                        }
                    }
                    rookRows[sq][row][pattern] = baseIndex + index;
                    //logf << "rookRows " << sq << " " << row << " " << pattern << " : ";
                    //logf << rookRows[sq][row][pattern] << endl;
                }
            }
            baseIndex += (1 << bits);
        }
    }
}


// From index to attack bits
Bitboard rookAttackTable[102400];

void initRookAttacks()
{
    int baseIndex = 0;
    for ( int bits = 12; bits >= 10; --bits )
    {
        for ( int sq = 0; sq < 64; ++sq )
        {
            if ( squareBitsR[sq] != bits )
                continue;
            Bitboard bb = rookBits[sq];
            for ( int index = 0; index < (1 << bits); ++ index )
            {
                Bitboard occ = 0;
                int i = index;
                for ( int rsq = 0; rsq < 64; ++rsq )
                {
                    if ( bb.test_bit( rsq ) )
                    {
                        if ( i & 1 )
                            occ.set_bit( rsq );
                        i >>= 1;
                    }
                }
                Bitboard att = 0;
                int j;
                for ( j = sq + 1; j < 64 && (j & 7) != 0; ++j )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq + 8; j < 64; j += 8 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 1; j >= 0 && (j & 7) != 7; --j )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                for ( j = sq - 8; j >= 0; j -= 8 )
                {
                    att.set_bit( j );
                    if ( occ.test_bit( j ) )
                        break;
                }
                rookAttackTable[baseIndex + index] = att;
            }
            baseIndex += (1 << bits);
        }
    }
}


/**
The rook attack bitboard for a square and occupied bitboard
*/
Bitboard rookAttacks( int sq, Bitboard occ )
{
    // The remaining blocking pieces in the +-rays
    occ &= rookBits[sq]; 
    BBUnion occu;
    occu.bb = occ;

    // Since every square has its set of row values the six row lookups 
    // simply map any blockers to specific bits that when ored together 
    // gives an offset in the bishop attack table.
    int *rRows = &rookRows[sq][0][0];
    int index = (rRows +    0)[occu.bbb.row1]  // row 1
              | (rRows +  256)[occu.bbb.row2]  // row 2
              | (rRows +  512)[occu.bbb.row3]  // row 3
              | (rRows +  768)[occu.bbb.row4]  // row 4
              | (rRows + 1024)[occu.bbb.row5]  // row 5
              | (rRows + 1280)[occu.bbb.row6]  // row 6
              | (rRows + 1536)[occu.bbb.row7]  // row 7
              | (rRows + 1792)[occu.bbb.row8]; // row 8
    return rookAttackTable[index];
}


/*******************************************************************/

const Bitboard dirMaskRight[8] =
{
    // 0, line_h, line_gh, line_fh, line_eh, line_dh, line_ch, line_bh, 
    0, C64(0x0101010101010101), C64(0x0303030303030303), C64(0x0707070707070707), C64(0x0f0f0f0f0f0f0f0f), 
    C64(0x1f1f1f1f1f1f1f1f), C64(0x3f3f3f3f3f3f3f3f), C64(0x7f7f7f7f7f7f7f7f)
};

const Bitboard dirMaskLeft[8] =
{
    // line_ag, line_af, line_ae, line_ad, line_ac, line_ab, line_a, 0, 
    C64(0xfefefefefefefefe), C64(0xfcfcfcfcfcfcfcfc), C64(0xf8f8f8f8f8f8f8f8), C64(0xf0f0f0f0f0f0f0f0), 
    C64(0xe0e0e0e0e0e0e0e0), C64(0xc0c0c0c0c0c0c0c0), C64(0x8080808080808080), 0
};

const Bitboard dirMaskUp[8] =
{
    // row_28, row_38, row_48, row_58, row_68, row_78, row_8, 0, 
    C64(0xffffffffffffff00), C64(0xffffffffffff0000), C64(0xffffffffff000000), C64(0xffffffff00000000), 
    C64(0xffffff0000000000), C64(0xffff000000000000), C64(0xff00000000000000), 0
};

const Bitboard dirMaskDown[8] =
{
    // 0, row_1, row_12, row_13, row_14, row_15, row_16, row_17,
    0, C64(0x00000000000000ff), C64(0x000000000000ffff), C64(0x0000000000ffffff), C64(0x00000000ffffffff), 
    C64(0x000000ffffffffff), C64(0x0000ffffffffffff), C64(0x00ffffffffffffff)
};


/*******************************************************************/
/*******************************************************************/

/**
Prepare the slider attacks back transformation table.
Put the scattered bits of an sliding attack pattern 
back to the original bitboard.
*/
void Board::init_slider_attacks_index()
{
    initBishopBits();
    initBishopRows();
    initBishopAttacks();
    initRookBits();
    initRookRows();
    initRookAttacks();
}


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board::direction_attacks( byte square, byte dir ) const
{
    Bitboard result;
    Bitboard occ = wpieces_ | bpieces_;

    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    {
      case 1:
        result = rookAttacks( square, occ );
        result &= dirMaskRight[square & 7];
        break;
      case 5:
        result = rookAttacks( square, occ );
        result &= dirMaskLeft[square & 7];
        break;
      case 7:
        result = rookAttacks( square, occ );
        result &= dirMaskDown[square >> 3];
        break;
      case 3:
        result = rookAttacks( square, occ );
        result &= dirMaskUp[square >> 3];
        break;
      case 8:
        result = bishopAttacks( square, occ );
        result &= dirMaskRight[square & 7];
        result &= dirMaskDown[square >> 3];
        break;
      case 4:
        result = bishopAttacks( square, occ );
        result &= dirMaskLeft[square & 7];
        result &= dirMaskUp[square >> 3];
        break;
      case 2:
        result = bishopAttacks( square, occ );
        result &= dirMaskRight[square & 7];
        result &= dirMaskUp[square >> 3];
        break;
      case 6:
        result = bishopAttacks( square, occ );
        result &= dirMaskLeft[square & 7];
        result &= dirMaskDown[square >> 3];
        break;
      default:
        result = 0;
        break;
    }

    return result;
}


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a rook or queen on the square.
*/
Bitboard Board::orthogonal_attacks( byte square ) const
{
    Bitboard occ = wpieces_ | bpieces_;
    Bitboard result = rookAttacks( square, occ );
    return result;
}


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop or queen on the square.
*/
Bitboard Board::diagonal_attacks( byte square ) const
{
    Bitboard occ = wpieces_ | bpieces_;
    Bitboard result = bishopAttacks( square, occ );
    return result;
}


/*******************************************************************/

#endif // #if USE_SHERWIN_UNION_BITBOARDS()

[Harald]

bb_attacks_romi_pitty:

Code: Select all

/*******************************************************************/
/*
The bitboard attacks of RomiChess (Michael Sherwin) with a little bit 
of the Pitty method (Carey) as part of the board structure.

(c) 2007 Harald Lüßen
*/
/*******************************************************************/


#include "bb_ifdef.h"
#include "bb_basics.h"
#include "bb_bitboard.h"
#include "bb_board.h"
#include "bb_main.h"


#if USE_ROMI_BITBOARDS()

/*******************************************************************/

/*
    directions and shifts
    +-----+-----+-----+
    |<<= 9|<<= 8|<<= 7|
    +-----+-----+-----+
    |<<= 1|     |>>= 1|
    +-----+-----+-----+
    |>>= 7|>>= 8|>>= 9|
    +-----+-----+-----+

    We use this mapping of the normal board squares to bitboard bits
    +-------------------------+
    | 63 62 61 60 59 58 57 56 | 8
    | 55 54 53 52 51 50 49 48 | 7
    | 47 46 45 44 43 42 41 40 | 6
    | 39 38 37 36 35 35 33 32 | 5
    | 31 30 29 28 27 26 25 24 | 4
    | 23 22 21 20 19 18 17 16 | 3
    | 15 14 13 12 11 10  9  8 | 2
    |  7  6  5  4  3  2  1  0 | 1
    +-------------------------+
       a  b  c  d  e  f  g  h
*/

/*******************************************************************/

// Bishops

// The 4 rays for all moves from sq. Last index for special BSF/BSR results.
Bitboard rayUpLeft[65];
Bitboard rayUpRight[65];
Bitboard rayDownLeft[65];
Bitboard rayDownRight[65];

void initBishopRays()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        rayUpLeft[sq] = 0;
        rayUpRight[sq] = 0;
        rayDownLeft[sq] = 0;
        rayDownRight[sq] = 0;
        int i;
        for ( i = sq - 9; i >= 0 && i % 8 != 7; i -= 9 )
        {
            rayDownRight[sq] |= C64(1) << i;
        }
        for ( i = sq - 7; i >= 0 && i % 8 != 0; i -= 7 )
        {
            rayDownLeft[sq] |= C64(1) << i;
        }
        for ( i = sq + 9; i < 64 && i % 8 != 0; i += 9 )
        {
            rayUpLeft[sq] |= C64(1) << i;
        }
        for ( i = sq + 7; i < 64 && i % 8 != 7; i += 7 )
        {
            rayUpRight[sq] |= C64(1) << i;
        }
        //logf << "initBishopRays " << sq << endl;
        //logf << rayDownRight[sq].txt8lines() << endl;
        //logf << rayDownLeft[sq].txt8lines() << endl;
        //logf << rayUpRight[sq].txt8lines() << endl;
        //logf << rayUpLeft[sq].txt8lines() << endl;
    }
    rayUpLeft[64] = 0;
    rayUpRight[64] = 0;
    rayDownLeft[64] = 0;
    rayDownRight[64] = 0;
}


/**
The bishop attack bitboard for a square and occupied bitboard
*/
Bitboard bishopAttacks( int sq, Bitboard occ )
{
    Bitboard    ray = rayUpLeft[sq];
    Bitboard occray = ray & occ;
    Bitboard attack = ray ^ rayUpLeft[occray.lsb_nr()];
       ray  = rayUpRight[sq];
    occray  = ray & occ;
    attack |= ray ^ rayUpRight[occray.lsb_nr()];
       ray  = rayDownLeft[sq];
    occray  = ray & occ;
    attack |= ray ^ rayDownLeft[occray.msb_nr()];
       ray  = rayDownRight[sq];
    occray  = ray & occ;
    attack |= ray ^ rayDownRight[occray.msb_nr()];
    //logf << "bishopAttacks " << sq << endl;
    //logf << occ.txt8lines() << ',' << endl;
    //logf << attack.txt8lines() << endl;
    return attack;
}


/*******************************************************************/

// Rooks

// The 4 rays for all moves from sq. Last index for special BSF/BSR results.
Bitboard rayUp[65];
Bitboard rayDown[65];
Bitboard rayLeft[65];
Bitboard rayRight[65];

void initRookRays()
{
    int sq;
    for ( sq = 0; sq < 64; ++sq )
    {
        rayUp[sq] = 0;
        rayDown[sq] = 0;
        rayLeft[sq] = 0;
        rayRight[sq] = 0;
        int i;
        for ( i = sq - 1; i >= 0 && i % 8 != 7; --i )
        {
            rayRight[sq] |= C64(1) << i;
        }
        for ( i = sq - 8; i >= 0; i -= 8 )
        {
            rayDown[sq] |= C64(1) << i;
        }
        for ( i = sq + 1; i < 64 && i % 8 != 0; ++i )
        {
            rayLeft[sq] |= C64(1) << i;
        }
        for ( i = sq + 8; i < 64; i += 8 )
        {
            rayUp[sq] |= C64(1) << i;
        }
        //logf << "initRookRays " << sq << endl;
        //logf << rayRight[sq].txt8lines() << endl;
        //logf << rayDown[sq].txt8lines() << endl;
        //logf << rayLeft[sq].txt8lines() << endl;
        //logf << rayUp[sq].txt8lines() << endl;
    }
    rayUp[64] = 0;
    rayDown[64] = 0;
    rayLeft[64] = 0;
    rayRight[64] = 0;
}


/**
The rook attack bitboard for a square and occupied bitboard
*/
Bitboard rookAttacks( int sq, Bitboard occ )
{
    Bitboard    ray = rayUp[sq];
    Bitboard occray = ray & occ;
    Bitboard attack = ray ^ rayUp[occray.lsb_nr()];
       ray  = rayLeft[sq];
    occray  = ray & occ;
    attack |= ray ^ rayLeft[occray.lsb_nr()];
       ray  = rayDown[sq];
    occray  = ray & occ;
    attack |= ray ^ rayDown[occray.msb_nr()];
       ray  = rayRight[sq];
    occray  = ray & occ;
    attack |= ray ^ rayRight[occray.msb_nr()];
    //logf << "rookAttacks " << sq << endl;
    //logf << occ.txt8lines() << ',' << endl;
    //logf << attack.txt8lines() << endl;
    return attack;
}


/*******************************************************************/

/**
Prepare the slider attacks tables.
*/
void Board::init_slider_attacks_index()
{
    initBishopRays();
    initRookRays();
}


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop, rook or queen on the square moving in the direction.
*/
Bitboard Board::direction_attacks( byte sq, byte dir ) const
{
    Bitboard result;
    Bitboard occ = wpieces_ | bpieces_;

    // 4 3 2
    // 5 0 1
    // 6 7 8
    switch ( dir )
    {
      case 1:
        result = rayRight[sq];
        occ &= result;
        result ^= rayRight[occ.msb_nr()];
        break;
      case 5:
        result = rayLeft[sq];
        occ &= result;
        result ^= rayLeft[occ.lsb_nr()];
        break;
      case 7:
        result = rayDown[sq];
        occ &= result;
        result ^= rayDown[occ.msb_nr()];
        break;
      case 3:
        result = rayUp[sq];
        occ &= result;
        result ^= rayUp[occ.lsb_nr()];
        break;
      case 8:
        result = rayDownRight[sq];
        occ &= result;
        result ^= rayDownRight[occ.msb_nr()];
        break;
      case 4:
        result = rayUpLeft[sq];
        occ &= result;
        result ^= rayUpLeft[occ.lsb_nr()];
        break;
      case 2:
        result = rayUpRight[sq];
        occ &= result;
        result ^= rayUpRight[occ.lsb_nr()];
        break;
      case 6:
        result = rayDownLeft[sq];
        occ &= result;
        result ^= rayDownLeft[occ.msb_nr()];
        break;
      default:
        result = 0;
        break;
    }

    return result;
}


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a rook or queen on the square.
*/
Bitboard Board::orthogonal_attacks( byte square ) const
{
    Bitboard occ = wpieces_ | bpieces_;
    Bitboard result = rookAttacks( square, occ );
    return result;
}


/*******************************************************************/

/**
Get a bitboard with all positions set to 1 which can be attacked 
from a bishop or queen on the square.
*/
Bitboard Board::diagonal_attacks( byte square ) const
{
    Bitboard occ = wpieces_ | bpieces_;
    Bitboard result = bishopAttacks( square, occ );
    return result;
}


/*******************************************************************/

#endif // #if USE_ROMI_BITBOARDS()

[Harald]

Hi, I coded two new bitboard methods, partly on Michael Sherwin's request. The 3 test positions are the same as always:

Code: Select all

Opening      rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Middle game  1r1q1rk1/2p1bppp/p5b1/3pP3/Bn1Pn3/2N1BN1P/1P2QPP1/R2R2K1 w - - 0 1
Near endgame r2r4/pp3p2/4bkpp/8/7P/3B1P2/PP4P1/1K1R3R b - -

There is a possible error of 1-2% depending on a changed test environment
on my machine. E.g. other background virus scanner.

Sherwin Index with union:
For each square each row of a bitboard generates a few bits of an index
to an bitboard attack table. It's a challenge to do the initialisation right.
The row acces is done with a union.

Code: Select all

  9	-0.05	4.5M	0:31.90	d2-d4  d7-d5 Ng1-f3 Nb8-c6  e2-e3 Ng8-f6  c2-c4 Nc6-b4 Nb1-c3  c7-c6 
  8	+0.15	8.0M	0:52.17	Ra1-c1 Rb8-c8 Nf3-d2 Ne4xc3 Rc1xc3 Nb4-a2 Rc3-c6 Na2-b4  g2-g4 Nb4xc6 Ba4xc6 
  9	+0.16	4.1M	0:22.29	Rd8xd3 Rd1xd3 Be6-f5 Rh1-d1 Ra8-e8 Kb1-c2 Re8-e2 Rd1-d2 Bf5xd3 Kc2xd3 

Romi Pitty:
Use a combination of single rays combined wth the occupied bitboard
and a second ray starting at the most/least significant bit (bsr, bsf).
It is implemented similar in Romichess and Carey calls this algorithm pit(t)y.

Code: Select all

  9	-0.05	4.5M	0:29.34	d2-d4  d7-d5 Ng1-f3 Nb8-c6  e2-e3 Ng8-f6  c2-c4 Nc6-b4 Nb1-c3  c7-c6 
  8	+0.15	8.0M	0:48.28	Ra1-c1 Rb8-c8 Nf3-d2 Ne4xc3 Rc1xc3 Nb4-a2 Rc3-c6 Na2-b4  g2-g4 Nb4xc6 Ba4xc6 
  9	+0.16	4.1M	0:20.56	Rd8xd3 Rd1xd3 Be6-f5 Rh1-d1 Ra8-e8 Kb1-c2 Re8-e2 Rd1-d2 Bf5xd3 Kc2xd3 

The new Statistic is this:

Code: Select all

+----------------------------+-----------------------+--------------+-----------+
| Name                       | Inventor or Supporter | Table Size   | Test-Time |
+----------------------------+-----------------------+--------------+-----------+
| Rotated Bitboards (naive)  | Robert Hyatt          |   77.2 KByte |  87.78 s  |
| Rotated Bitboards (aligned)| ?                     |   35.0 KByte |  86.65 s  |
| Rotated Bitboards (switch) | (Harald Lüßen?)       |   14.9 KByte |  88.91 s  |
| Rotated Indices            | Alessandro Damiani    |  128.3 KByte |  78.93 s  |
| Exploding Bitboards        | Harald Lüßen          |    3.5 KByte | 101.79 s  |
| Magic Multiplication       | Gerd Isenberg         |    9.7 KByte |  91.87 s  |
| Magic Multiplication 32 bit| Gerd Isenberg         |    9.7 KByte |  81.37 s  |
| Sherwin Index              | Michael Sherwin       | 1402.4 KByte |  90.03 s  |
| Sherwin Index with union   | Michael Sherwin       | 1402.4 KByte | 106.36 s  |
| Pradu Minimize Magic       | Pradyumna Kannan      |  844.0 KByte |  81.42 s  |
| Pradu Perfect Magic Hash   |  and                  |  627.4 KByte |  82.09 s  |
| Pradu Big                  | Lasse Hansen          | 2306.0 KByte |  82.33 s  |
| Kogge-Stone                | Steffan Westcott      |    0.0 KByte |  99.32 s  |
| Simple Shift               | --                    |    0.0 KByte | 110.25 s  |
| Naive Shift                | --                    |    0.0 KByte | 111.69 s  |
| Romi/Pitty                 | --                    |    4.1 KByte |  98.18 s  |
+----------------------------+-----------------------+--------------+-----------+

The union access is slower than the shift and mask access. Either I did
something wrong or the compiler optimisation did the trick.
I am not good at assembler, 32/64 bit coding, cache lines and branch
prediction. If I should try another code please prepare a better variant
ready to use based on my source.

For the Romy/Pitty code I had to fix a bug in my lsb_nr (bsf) assembler
function. A nice side effect.

There is another method in discussion in this thread (Gerd's bswap).
I am still trying to understand it. What does bswap() do? Perhaps I
implement it one day.

Harald

[Gerd Isenberg]

The fascinating thing is the number of possible approaches to get sliding attacks. It is still a nice cycle hunting challenge and contest for some of us

I am very happy with forgotten Gerd's "bswap" approach:

Code: Select all

    struct M {
        BitBoard singleton; //optional well-known "bitmask" (1 << sq)
        BitBoard vertical; //attack direction on empty board
        BitBoard diagonal;
        BitBoard antidiag;
        BitBoard knight;
        BitBoard king;
        BitBoard whitePawn;
        BitBoard blackPawn;
    } mask[64];

    BitBoard attack(Square from, BitBoard occupied, BitBoard dirMask) const {
        bit64_t forward = occupied & dirMask;
        bit64_t reverse = bswap(forward);
        forward -= mask[from].singleton;
        reverse -= mask[from ^ 070].singleton;
        forward ^= bswap(reverse);
        return BitBoard(forward & dirMask);
    }

    BitBoard bishop(Square from, BitBoard occupied) const {
        return
            attack(from, occupied, mask[from].diagonal) |
            attack(from, occupied, mask[from].antidiag);
    }

    BitBoard rook(Square from, BitBoard occupied) const {
        return
            attack(from, occupied, mask[from].vertical) |
            rankAttack(from, occupied); //any traditional approach
    }

32 bit and cache friendly. Memory acceses nicely interleaved with simple arithmetic.

Wow - you really did some fine improvements!
I had some more xors inside the code.
Seems to outperform kindergarten bishops now.

Code: Select all

?_bishopAttacks@@YA_K_KI@Z PROC	
  00000	40 53		 push	 rbx
  00002	4c 8d 15 00 00
	00 00		 lea	 r10, OFFSET FLAT:?mask
  00009	8b d2		 mov	 edx, edx
  0000b	4c 8b c2	 mov	 r8, rdx
  0000e	48 83 f2 38	 xor	 rdx, 56
  00012	49 c1 e0 05	 shl	 r8, 5
  00016	48 c1 e2 05	 shl	 rdx, 5
  0001a	4b 8b 5c 10 08	 mov	 rbx, QWORD PTR [r8+r10+8]
  0001f	4f 8b 4c 10 10	 mov	 r9, QWORD PTR [r8+r10+16]
  00024	4f 8b 04 10	 mov	 r8, QWORD PTR [r8+r10]
  00028	4a 8b 14 12	 mov	 rdx, QWORD PTR [rdx+r10]
  0002c	4c 8b db	 mov	 r11, rbx
  0002f	49 8b c1	 mov	 rax, r9
  00032	48 23 c1	 and	 rax, rcx
  00035	4c 23 d9	 and	 r11, rcx
  00038	4c 8b d0	 mov	 r10, rax
  0003b	49 2b c0	 sub	 rax, r8
  0003e	49 8b cb	 mov	 rcx, r11
  00041	48 0f c9	 bswap	 rcx
  00044	49 0f ca	 bswap	 r10
  00047	4d 2b d8	 sub	 r11, r8
  0004a	48 2b ca	 sub	 rcx, rdx
  0004d	4c 2b d2	 sub	 r10, rdx
  00050	48 0f c9	 bswap	 rcx
  00053	49 0f ca	 bswap	 r10
  00056	49 33 c2	 xor	 rax, r10
  00059	49 33 cb	 xor	 rcx, r11
  0005c	49 23 c1	 and	 rax, r9
  0005f	48 23 cb	 and	 rcx, rbx
  00062	48 03 c1	 add	 rax, rcx
  00065	5b		 pop	 rbx
  00066	c3		 ret	 0
?_bishopAttacks@@YA_K_KI@Z ENDP

[Michael Sherwin]

Hi, I coded two new bitboard methods, partly on Michael Sherwin's request. The 3 test positions are the same as always:

Code: Select all

Opening      rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Middle game  1r1q1rk1/2p1bppp/p5b1/3pP3/Bn1Pn3/2N1BN1P/1P2QPP1/R2R2K1 w - - 0 1
Near endgame r2r4/pp3p2/4bkpp/8/7P/3B1P2/PP4P1/1K1R3R b - -

There is a possible error of 1-2% depending on a changed test environment
on my machine. E.g. other background virus scanner.

Sherwin Index with union:
For each square each row of a bitboard generates a few bits of an index
to an bitboard attack table. It's a challenge to do the initialisation right.
The row acces is done with a union.

Code: Select all

  9	-0.05	4.5M	0:31.90	d2-d4  d7-d5 Ng1-f3 Nb8-c6  e2-e3 Ng8-f6  c2-c4 Nc6-b4 Nb1-c3  c7-c6 
  8	+0.15	8.0M	0:52.17	Ra1-c1 Rb8-c8 Nf3-d2 Ne4xc3 Rc1xc3 Nb4-a2 Rc3-c6 Na2-b4  g2-g4 Nb4xc6 Ba4xc6 
  9	+0.16	4.1M	0:22.29	Rd8xd3 Rd1xd3 Be6-f5 Rh1-d1 Ra8-e8 Kb1-c2 Re8-e2 Rd1-d2 Bf5xd3 Kc2xd3 

Romi Pitty:
Use a combination of single rays combined wth the occupied bitboard
and a second ray starting at the most/least significant bit (bsr, bsf).
It is implemented similar in Romichess and Carey calls this algorithm pit(t)y.

Code: Select all

  9	-0.05	4.5M	0:29.34	d2-d4  d7-d5 Ng1-f3 Nb8-c6  e2-e3 Ng8-f6  c2-c4 Nc6-b4 Nb1-c3  c7-c6 
  8	+0.15	8.0M	0:48.28	Ra1-c1 Rb8-c8 Nf3-d2 Ne4xc3 Rc1xc3 Nb4-a2 Rc3-c6 Na2-b4  g2-g4 Nb4xc6 Ba4xc6 
  9	+0.16	4.1M	0:20.56	Rd8xd3 Rd1xd3 Be6-f5 Rh1-d1 Ra8-e8 Kb1-c2 Re8-e2 Rd1-d2 Bf5xd3 Kc2xd3 

The new Statistic is this:

Code: Select all

+----------------------------+-----------------------+--------------+-----------+
| Name                       | Inventor or Supporter | Table Size   | Test-Time |
+----------------------------+-----------------------+--------------+-----------+
| Rotated Bitboards (naive)  | Robert Hyatt          |   77.2 KByte |  87.78 s  |
| Rotated Bitboards (aligned)| ?                     |   35.0 KByte |  86.65 s  |
| Rotated Bitboards (switch) | (Harald Lüßen?)       |   14.9 KByte |  88.91 s  |
| Rotated Indices            | Alessandro Damiani    |  128.3 KByte |  78.93 s  |
| Exploding Bitboards        | Harald Lüßen          |    3.5 KByte | 101.79 s  |
| Magic Multiplication       | Gerd Isenberg         |    9.7 KByte |  91.87 s  |
| Magic Multiplication 32 bit| Gerd Isenberg         |    9.7 KByte |  81.37 s  |
| Sherwin Index              | Michael Sherwin       | 1402.4 KByte |  90.03 s  |
| Sherwin Index with union   | Michael Sherwin       | 1402.4 KByte | 106.36 s  |
| Pradu Minimize Magic       | Pradyumna Kannan      |  844.0 KByte |  81.42 s  |
| Pradu Perfect Magic Hash   |  and                  |  627.4 KByte |  82.09 s  |
| Pradu Big                  | Lasse Hansen          | 2306.0 KByte |  82.33 s  |
| Kogge-Stone                | Steffan Westcott      |    0.0 KByte |  99.32 s  |
| Simple Shift               | --                    |    0.0 KByte | 110.25 s  |
| Naive Shift                | --                    |    0.0 KByte | 111.69 s  |
| Romi/Pitty                 | --                    |    4.1 KByte |  98.18 s  |
+----------------------------+-----------------------+--------------+-----------+

The union access is slower than the shift and mask access. Either I did
something wrong or the compiler optimisation did the trick.
I am not good at assembler, 32/64 bit coding, cache lines and branch
prediction. If I should try another code please prepare a better variant
ready to use based on my source.

Responce: I will take a final best guess and submit it to you. Thanks!

For the Romy/Pitty code I had to fix a bug in my lsb_nr (bsf) assembler
function. A nice side effect.

There is another method in discussion in this thread (Gerd's bswap).
I am still trying to understand it. What does bswap() do? Perhaps I
implement it one day.

Harald

Hi Harald,

Thank you! It is good to have answers!

I suppose that for 32 bit machines it would then be best to keep the row indici look-up in-register and just split occ into 2 32 bit halves as that would save 17 32 bit instructions. I wish that I would have just believed you and Gerd about the in-register stuff as now all that needs to be answered is the, '32 bit friendly' in-register question.

OTOH, all very instructive! And that big-endian and little-endian code can be useful to a lot of people that want to write portable code. Me included.

Best,
Mike