path: root/src/data.c

/**

Copyright (c) Scott Gasch

Module Name:

    data.c

Abstract:

    Large data structures and the code that creates/verifies them.

Author:

    Scott Gasch ([email protected]) 10 May 2004

Revision History:

    $Id: data.c 345 2007-12-02 22:56:42Z scott $

**/

#include "chess.h"

// Distance between two squares lookup table
ULONG g_uDistance[256];
ULONG *g_pDistance = &(g_uDistance[128]);

// Who controls the square lookup table
CHAR g_SwapTable[14][32][32];

// Vector (bitvector indicating which pieces can move between squares) and
// Delta (direction to travel to get from square a to square b) lookup table.
VECTOR_DELTA g_VectorDelta[256];
VECTOR_DELTA *g_pVectorDelta = &(g_VectorDelta[128]);

// Hardcoded move patterns to terminate PVs with
MOVE NULLMOVE = {0};
MOVE HASHMOVE = {0x11118888};
MOVE RECOGNMOVE = {0x22228888};
MOVE DRAWMOVE = {0x33338888};
MOVE MATEMOVE = {0x44448888};

// Is a square white?
FLAG g_fIsWhiteSquare[128];

#ifdef DEBUG
COOR 
DistanceBetweenSquares(COOR a, COOR b)
{
    int i = (int)a - (int)b + 128;
    int j = (int)b - (int)a + 128;
    ASSERT(IS_ON_BOARD(a));
    ASSERT(IS_ON_BOARD(b));
    ASSERT((i >= 0) && (i < 256));
    ASSERT(g_uDistance[i] == REAL_DISTANCE(a, b));
    ASSERT(g_pDistance[(int)a - (int)b] == g_uDistance[i]);
    ASSERT(g_pDistance[(int)b - (int)a] == g_uDistance[i]);
    ASSERT(g_uDistance[j] == REAL_DISTANCE(a, b));
    return(REAL_DISTANCE(a, b));
}

#define VALID_VECTOR(x) \
    (((x) == 0) || \
     ((x) == (1 << KNIGHT)) || \
     ((x) == ( (1 << BISHOP) | (1 << QUEEN))) || \
     ((x) == ( (1 << ROOK) | (1 << QUEEN))) || \
     ((x) == ( (1 << BISHOP) | (1 << QUEEN) | (1 << KING))) || \
     ((x) == ( (1 << ROOK) | (1 << QUEEN) | (1 << KING))) || \
     ((x) == ( (1 << BISHOP) | (1 << QUEEN) | (1 << KING) | (1 << PAWN))))


#define VALID_INDEX(x) \
    (((x) >= -128) && ((x) <= 127))

ULONG
CheckVectorWithIndex(int i, ULONG uColor) 
{
	ULONG u;
    ASSERT(VALID_INDEX(i));
    ASSERT(IS_VALID_COLOR(uColor));
    u = g_pVectorDelta[i].iVector[uColor];
    ASSERT(VALID_VECTOR(u));
    ASSERT(u == g_VectorDelta[i + 128].iVector[uColor]);
    ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128]));
    return(u);
}

#define VALID_DELTA(x) \
    (((x) == 0) || \
     ((x) == +1) || ((x) == -1) || \
     ((x) == +16) || ((x) == -16) || \
     ((x) == +15) || ((x) == -15) || \
     ((x) == +17) || ((x) == -17))

int
DirectionBetweenSquaresWithIndex(int i) 
{
    int iDir;
    ASSERT(VALID_INDEX(i));
    iDir = g_pVectorDelta[i].iDelta;
    ASSERT(iDir == g_VectorDelta[i + 128].iDelta);
    ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128]));
    ASSERT(VALID_DELTA(iDir));
    ASSERT(iDir == -g_pVectorDelta[i].iNegDelta);
    return(iDir);
}

int 
DirectionBetweenSquaresFromTo(COOR from, COOR to) 
{
    int i = (int)from - (int)to;
    return DirectionBetweenSquaresWithIndex(i);
}

int 
NegativeDirectionBetweenSquaresWithIndex(int i)
{
    int iDir;
    ASSERT(VALID_INDEX(i));
    iDir = g_pVectorDelta[i].iNegDelta;
    ASSERT(iDir == g_VectorDelta[i + 128].iNegDelta);
    ASSERT(&(g_pVectorDelta[i]) == &(g_VectorDelta[i + 128]));
    ASSERT(VALID_DELTA(iDir));
    ASSERT(iDir == -g_pVectorDelta[i].iDelta);
    return(iDir);
}
    
int
DirectionBetweenSquares(COOR cFrom, COOR cTo)
{
    int i = (int)cFrom - (int)cTo;
    return(DirectionBetweenSquaresWithIndex(i));
}

FLAG 
IsSquareWhite(COOR c) 
{
	BITBOARD bb;
    FLAG f = IS_WHITE_SQUARE_COOR(c);
    ASSERT(IS_ON_BOARD(c));
    ASSERT(f == g_fIsWhiteSquare[c]);
    bb = COOR_TO_BB(c);
    ASSERT(f == ((bb & BBWHITESQ) != 0));
    ASSERT(f == ((bb & BBBLACKSQ) == 0));
    return(f);
}
#endif

void
VerifyVectorDelta(void)
{
    int iIndex;
    int iChecksum = 0;
    
    for (iIndex = 0;
         iIndex < 256;
         iIndex++)
    {
        ASSERT(VALID_VECTOR(g_VectorDelta[iIndex].iVector[BLACK]));
        ASSERT(VALID_VECTOR(g_VectorDelta[iIndex].iVector[WHITE]));
        ASSERT(VALID_DELTA(g_VectorDelta[iIndex].iDelta));
        ASSERT(VALID_DELTA(g_VectorDelta[iIndex].iNegDelta));
        ASSERT(-g_VectorDelta[iIndex].iDelta == 
               g_VectorDelta[iIndex].iNegDelta);
        iChecksum += g_VectorDelta[iIndex].iVector[BLACK] * iIndex;
        iChecksum += g_VectorDelta[iIndex].iVector[WHITE] * iIndex;
        iChecksum += g_VectorDelta[iIndex].iDelta * iIndex;
    }
    
    if (iChecksum != 0xb1b58)
    {
        UtilPanic(DETECTED_INCORRECT_INITIALIZATION,
                  NULL,
                  "vector/delta",
                  (void *)(size_t)iChecksum,
                  (void *)(size_t)0xb1b58, 
                  __FILE__, __LINE__);
    }
}

void
InitializeWhiteSquaresTable(void) 
{
    COOR c;

    FOREACH_SQUARE(c)
    {
        g_fIsWhiteSquare[c] = FALSE;
        if (!IS_ON_BOARD(c)) 
        {
            continue;
        }
        g_fIsWhiteSquare[c] = IS_WHITE_SQUARE_COOR(c);
    }
}

void
InitializeVectorDeltaTable(void)
{
    COOR cStart;
    COOR cNew;
    COOR cRay;
    int iIndex;
    PIECE p;
    int iDir;
    ULONG u;
    static const BYTE _LOCATIONS[] = 
    {
        D4, A5, A3, G3, C1, B5, H4, E5, E3, A6, C5, A5, A5, 
        G5, A6, D3, D2, A5, E1, E1, A6, H4, B2, D1, D2, E5 
    };
    static int iNumDirs[7] =    { 0, 0, 8, 4, 4, 8, 8 };
    static int iDelta[7][8] =   { {   0,   0,   0,   0,   0,   0,   0,   0 },
                                  {   0,   0,   0,   0,   0,   0,   0,   0 },
                                  { -33, -31, -18, -14, +14, +18, +31, +33 },
                                  { -17, -15, +15, +17,   0,   0,   0,   0 },
                                  { -16,  -1,  +1, +16,   0,   0,   0,   0 },
                                  { -17, -16, -15,  -1,  +1, +15, +16, +17 },
                                  { -17, -16, -15,  -1,  +1, +15, +16, +17 } };

    memset(g_VectorDelta, 0, sizeof(g_VectorDelta));
    FOREACH_SQUARE(cStart)
    {
        if (!IS_ON_BOARD(cStart)) continue;
        for (u = 0; u < ARRAY_LENGTH(_LOCATIONS); u++) 
        {
            if (cStart == _LOCATIONS[u]) 
            {
                iIndex = 0;
            }
        }
        
        //
        // Do the pawn bits
        //
        iIndex = (int)cStart - ((int)cStart - 17) + 128;
        g_VectorDelta[iIndex].iVector[WHITE] |= (1 << PAWN);
        iIndex = (int)cStart - ((int)cStart - 15) + 128;
        g_VectorDelta[iIndex].iVector[WHITE] |= (1 << PAWN);
        
        iIndex = (int)cStart - ((int)cStart + 17) + 128;
        g_VectorDelta[iIndex].iVector[BLACK] |= (1 << PAWN);
        iIndex = (int)cStart - ((int)cStart + 15) + 128;
        g_VectorDelta[iIndex].iVector[BLACK] |= (1 << PAWN);
        
        //
        // Do the piece bits
        //
        for (p = KNIGHT; p <= KING; p++)
        {
            for (iDir = 0; 
                 iDir < iNumDirs[p]; 
                 iDir++)
            {
                cRay = cStart;
                cNew = cRay + iDelta[p][iDir];
                while (IS_ON_BOARD(cNew))
                {
                    iIndex = (int)cStart - (int)cNew + 128;
                    
                    //
                    // Fill in the vector
                    //
                    g_VectorDelta[iIndex].iVector[WHITE] |= (1 << p);
                    g_VectorDelta[iIndex].iVector[BLACK] |= (1 << p);
                    
                    //
                    // Fill in the delta
                    //
                    if (FILE(cStart) == FILE(cNew))
                    {
                        if (cStart < cNew)
                        {
                            g_VectorDelta[iIndex].iDelta = 16;
                            g_VectorDelta[iIndex].iNegDelta = -16;
                        }
                        else
                        {
                            g_VectorDelta[iIndex].iDelta = -16;
                            g_VectorDelta[iIndex].iNegDelta = 16;
                        }                            
                    }
                    else if (RANK(cStart) == RANK(cNew))
                    {
                        if (cStart < cNew)
                        {
                            g_VectorDelta[iIndex].iDelta = 1;
                            g_VectorDelta[iIndex].iNegDelta = -1;
                        }
                        else
                        {
                            g_VectorDelta[iIndex].iDelta = -1;
                            g_VectorDelta[iIndex].iNegDelta = 1;
                        }
                    }
                    else if ((cStart % 15) == (cNew % 15))
                    {
                        if (cStart < cNew)
                        {
                            g_VectorDelta[iIndex].iDelta = +15;
                            g_VectorDelta[iIndex].iNegDelta = -15;
                        }
                        else
                        {
                            g_VectorDelta[iIndex].iDelta = -15;
                            g_VectorDelta[iIndex].iNegDelta = 15;
                        }
                    }
                    else if ((cStart % 17) == (cNew % 17))
                    {
                        if (cStart < cNew)
                        {
                            g_VectorDelta[iIndex].iDelta = +17;
                            g_VectorDelta[iIndex].iNegDelta = -17;
                        }
                        else
                        {
                            g_VectorDelta[iIndex].iDelta = -17;
                            g_VectorDelta[iIndex].iNegDelta = 17;
                        }
                    }
                    cNew += iDelta[p][iDir];
                    
                    if ((KING == p) || (KNIGHT == p))
                    {
                        break;
                    }
                }
            }
        }
    }
    
    (void)VerifyVectorDelta();
#ifdef OSX
    //
    // nasm under OSX/macho has a nasty bug that causes the addresses
    // of extern symbols to be screwed up.  I only use two extern data
    // structs in the x86.asm code: the vector delta table and the
    // piece data table.  My workaround to the nasm bug is to copy
    // these tables into a symbol in the asm module and access them
    // locally on OSX.
    //
    extern VECTOR_DELTA *g_NasmVectorDelta;
    extern PIECE_DATA *g_NasmPieceData;

    memcpy(&g_NasmVectorDelta, &g_VectorDelta, sizeof(g_VectorDelta));
    memcpy(&g_NasmPieceData, &g_PieceData, sizeof(g_PieceData));
#endif
}

//
// TODO: fix this to use attack counts also
//
void
InitializeSwapTable(void)
{
    ULONG GET_HIGH_BIT[32] = 
    {
        0, // 00000 = 0
        1, // 00001 = 1
        2, // 00010 = 2
        2, // 00011 = 3
        4, // 00100 = 4
        4, // 00101 = 5
        4, // 00110 = 6 
        4, // 00111 = 7
        8, // 01000 = 8 
        8, // 01001 = 9
        8, // 01010 = 10
        8, // 01011 = 11
        8, // 01100 = 12
        8, // 01101 = 13
        8, // 01110 = 14 
        8, // 01111 = 15
       16, // 10000 = 16
       16, // 10001 = 17
       16, // 10010 = 18
       16, // 10011 = 19
       16, // 10100 = 20
       16, // 10101 = 21
       16, // 10110 = 22
       16, // 10111 = 23
       16, // 11000 = 24
       16, // 11001 = 25
       16, // 11010 = 26
       16, // 11011 = 27
       16, // 11100 = 28
       16, // 11101 = 29 
       16, // 11110 = 30
       16  // 11111 = 31
    };
    ULONG uOnMove;
    PIECE p;
    ULONG uAtStake;
    ULONG uBlack;
    ULONG uWhite;
    ULONG uOld;
    ULONG uGains[2];
    ULONG uAttacks[2];
    INT iDiff;
    
    for (p = 0; p <= WHITE_KING; p++)
    {
        if (p > 1)
        {
            for (uBlack = 0; uBlack < 32; uBlack++)
            {
                for (uWhite = 0; uWhite < 32; uWhite++)
                {
                    uGains[BLACK] = uGains[WHITE] = 0;
                    uAttacks[BLACK] = uBlack;
                    uAttacks[WHITE] = uWhite;
                    uAtStake = PIECE_VALUE(p);
                    uOnMove = WHITE;
                    if (GET_COLOR(p) == WHITE)
                    {
                        uOnMove = BLACK;
                    }

                    //
                    // Ok, if the side on move has an attack, play it 
                    // and give them credit for some plunder.
                    //
                    while(uAttacks[uOnMove])
                    {
                        uOld = uAtStake;
                        uGains[uOnMove] += uAtStake;
                        uAtStake = GET_HIGH_BIT[uAttacks[uOnMove]];
                        if (uAtStake == 16)
                        {
                            uAtStake = VALUE_PAWN;
                        }
                        else if (uAtStake == 8)
                        {
                            uAtStake = VALUE_BISHOP;
                        }
                        else if (uAtStake == 4)
                        {
                            uAtStake = VALUE_ROOK;
                        }
                        else if (uAtStake == 2)
                        {
                            uAtStake = VALUE_QUEEN;
                        }
                        else if (uAtStake == 1)
                        {
                            //
                            // Don't let them move into check
                            //
                            if (uAttacks[FLIP(uOnMove)])
                            {
                                uGains[uOnMove] -= uOld;
                                uAtStake = 0;
                            }
                            break;
                        }
                        else
                        {
                            UtilPanic(SHOULD_NOT_GET_HERE,
                                      NULL, NULL, NULL, NULL,
                                      __FILE__, __LINE__);
                        }
                        uAttacks[uOnMove] &= ~GET_HIGH_BIT[uAttacks[uOnMove]];
                        uOnMove = FLIP(uOnMove);
                    }
                    
                    //
                    // The side on move doesn't have an attack... does
                    // the side not on move have an attack?  If so they
                    // get a chance to assert some more control.
                    //
                    if (uAttacks[FLIP(uOnMove)])
                    {
                        uGains[FLIP(uOnMove)] += 100;
                    }

                    if (uGains[BLACK] > uGains[WHITE])
                    {
                        iDiff = uGains[BLACK] - uGains[WHITE];
                        iDiff /= 100;
						iDiff += (iDiff == 0);
                        g_SwapTable[p][uWhite][uBlack] = MIN(+127, iDiff);
                        g_SwapTable[p][uWhite][uBlack] *= -1;
                    }
                    else if (uGains[WHITE] > uGains[BLACK])
                    {
                        iDiff = uGains[WHITE] - uGains[BLACK];
                        iDiff /= 100;
						iDiff += (iDiff == 0);
                        g_SwapTable[p][uWhite][uBlack] = MIN(+127, iDiff);
                    }
                    else
                    {
                        g_SwapTable[p][uWhite][uBlack] = 0;
                    }
                }
            }
        }
        else                                  // no piece sitting there
        {
            for (uBlack = 0; uBlack < 32; uBlack++)
            {
                for (uWhite = 0; uWhite < 32; uWhite++)
                {
                    if (uBlack > uWhite)
                    {
                        g_SwapTable[p][uWhite][uBlack] = -1;
                    }
                    else if (uWhite > uBlack)
                    {
                        g_SwapTable[p][uWhite][uBlack] = +1;
                    }
                    else
                    {
                        g_SwapTable[p][uWhite][uBlack] = 0;
                    }
                }
            }
        }            
    }
}

void
InitializeDistanceTable(void) 
{
    COOR x, y;
    int i;
#ifdef DEBUG
	int j;
#endif

    for (x = 0; x < 128; x++) 
    {
        if (!IS_ON_BOARD(x)) continue;
        for (y = 0; y < 128; y++) 
        {
            if (!IS_ON_BOARD(y)) continue;
            i = (int)x - (int)y;
            i += 128;
            g_uDistance[i] = REAL_DISTANCE(x, y);
            ASSERT(g_uDistance[i] >= 0);
            ASSERT(g_uDistance[i] <= 7);
        }
    }

#ifdef DEBUG
    for (x = 0; x < 128; x++) 
    {
        if (!IS_ON_BOARD(x)) continue;
        for (y = 0; y < 128; y++) 
        {
            if (!IS_ON_BOARD(y)) continue;
            i = (int)x - (int)y + 128;
            ASSERT(g_uDistance[i] == REAL_DISTANCE(x, y));
            ASSERT(g_pDistance[(int)x - (int)y] == g_uDistance[i]);
            ASSERT(&(g_pDistance[(int)x - (int)y]) == &(g_uDistance[i]));
            j = (int)y - (int)x + 128;
            ASSERT(g_uDistance[j] == REAL_DISTANCE(x, y));
            ASSERT(g_pDistance[(int)y - (int)x] == g_uDistance[j]);
            ASSERT(&(g_pDistance[(int)y - (int)x]) == &(g_uDistance[j]));
        }
    }
#endif
}

//
// Per-square, per-direction "ray to board edge" bitboards for the
// rook, indexed [direction][c] with direction matching
// g_RookRayDeltas below (N, S, E, W). Only entries for real board
// squares (IS_ON_BOARD(c)) are ever populated/queried; off-board
// indices are left zeroed and unused. Built once at startup by
// InitializeRookRayTables() -- part of eval.c's occupancy-bitboard
// PoC (_EvalRookOccupancyBB et al.), turning a per-call
// walk-to-the-edge loop into an O(1) table lookup.
//
BITBOARD g_RookRayToEdge[4][128];
const int g_RookRayDeltas[4] = { 16, -16, 1, -1 }; // N, S, E, W (0x88)
const FLAG g_RookRayPositiveDir[4] = { TRUE, FALSE, TRUE, FALSE };

// Per-square OR of all 4 g_RookRayToEdge directions -- "every square a
// rook on c could reach on an empty board, regardless of direction."
// One lookup (+ AND against a slider bitboard) to answer "is uSide's
// rook/queen bitboard aligned with c *at all*", vs. 4 separate
// g_RookRayToEdge lookups to discover the same "no" -- see
// _WhoAttacksSquareBB (see.c) for the consumer and
// board_representation/MIGRATION.md section 3 for the writeup.
BITBOARD g_RookRayAll[128];

void
InitializeRookRayTables(void)
/**

Routine description:

    One-time startup init for g_RookRayToEdge -- see its comment.

Parameters:

    void

Return value:

    void

**/
{
    ULONG uRank, uFile, uDir;
    COOR c, cSquare;

    memset(g_RookRayToEdge, 0, sizeof(g_RookRayToEdge));
    memset(g_RookRayAll, 0, sizeof(g_RookRayAll));
    for (uRank = 0; uRank < 8; uRank++)
    {
        for (uFile = 0; uFile < 8; uFile++)
        {
            c = (uRank << 4) | uFile;
            for (uDir = 0; uDir < 4; uDir++)
            {
                for (cSquare = c + g_RookRayDeltas[uDir];
                     IS_ON_BOARD(cSquare);
                     cSquare += g_RookRayDeltas[uDir])
                {
                    g_RookRayToEdge[uDir][c] |= COOR_TO_BB(cSquare);
                    g_RookRayAll[c] |= COOR_TO_BB(cSquare);
                }
            }
        }
    }
}

//
// Same idea as g_RookRayToEdge, for the bishop's 4 diagonal directions.
//
BITBOARD g_BishopRayToEdge[4][128];
const int g_BishopRayDeltas[4] = { 17, -17, 15, -15 }; // NE, SW, NW, SE (0x88)
const FLAG g_BishopRayPositiveDir[4] = { TRUE, FALSE, TRUE, FALSE };

// g_RookRayAll's counterpart for the bishop's 4 diagonal directions.
BITBOARD g_BishopRayAll[128];

void
InitializeBishopRayTables(void)
/**

Routine description:

    One-time startup init for g_BishopRayToEdge -- see its comment.

Parameters:

    void

Return value:

    void

**/
{
    ULONG uRank, uFile, uDir;
    COOR c, cSquare;

    memset(g_BishopRayToEdge, 0, sizeof(g_BishopRayToEdge));
    memset(g_BishopRayAll, 0, sizeof(g_BishopRayAll));
    for (uRank = 0; uRank < 8; uRank++)
    {
        for (uFile = 0; uFile < 8; uFile++)
        {
            c = (uRank << 4) | uFile;
            for (uDir = 0; uDir < 4; uDir++)
            {
                for (cSquare = c + g_BishopRayDeltas[uDir];
                     IS_ON_BOARD(cSquare);
                     cSquare += g_BishopRayDeltas[uDir])
                {
                    g_BishopRayToEdge[uDir][c] |= COOR_TO_BB(cSquare);
                    g_BishopRayAll[c] |= COOR_TO_BB(cSquare);
                }
            }
        }
    }
}

// A combined 8-ray queen table (rook's 4 directions + bishop's 4,
// concatenated) was tried here and measured SLOWER than
// _EvalQueenOccupancyBB's two-pass version reusing g_RookRayToEdge/
// g_BishopRayToEdge directly -- see that function's comment for why
// (probable lost constant-folding on the orthogonal-ray flag). Removed
// rather than left around unused.

//
// Per-square "all squares a knight on c can hop to" bitboard. Unlike
// the rook/bishop ray tables, a knight has no blocking to account for
// -- there's nothing "in between" a knight and its landing square --
// so this is the complete, final answer for a given square, not a
// ray-to-edge that still needs an occupancy AND to find blockers.
// Built once at startup by InitializeKnightAttackTables().
//
BITBOARD g_KnightAttacksBB[128];

void
InitializeKnightAttackTables(void)
/**

Routine description:

    One-time startup init for g_KnightAttacksBB -- see its comment.

Parameters:

    void

Return value:

    void

**/
{
    ULONG uRank, uFile, uDir;
    COOR c, cSquare;

    memset(g_KnightAttacksBB, 0, sizeof(g_KnightAttacksBB));
    for (uRank = 0; uRank < 8; uRank++)
    {
        for (uFile = 0; uFile < 8; uFile++)
        {
            c = (uRank << 4) | uFile;
            for (uDir = 0; g_iNDeltas[uDir] != 0; uDir++)
            {
                cSquare = c + g_iNDeltas[uDir];
                if (IS_ON_BOARD(cSquare))
                {
                    g_KnightAttacksBB[c] |= COOR_TO_BB(cSquare);
                }
            }
        }
    }
}

//
// Per-square "all squares a king on c can step to" bitboard (normal
// king moves only -- castling stays mailbox, see
// board_representation/MOVEGEN_MIGRATION.md section 1's explicit
// non-goal and section 3 step 2). Same shape as g_KnightAttacksBB:
// GetAttacks's king case used a DISTANCE(...)==1 delta check instead,
// since it only ever needs a single square's membership test, not an
// enumerable destination set -- move generation needs the actual set,
// hence this table exists where GetAttacks needed none. Built once at
// startup by InitializeKingAttackTables().
//
BITBOARD g_KingAttacksBB[128];

void
InitializeKingAttackTables(void)
/**

Routine description:

    One-time startup init for g_KingAttacksBB -- see its comment.

Parameters:

    void

Return value:

    void

**/
{
    ULONG uRank, uFile, uDir;
    COOR c, cSquare;

    memset(g_KingAttacksBB, 0, sizeof(g_KingAttacksBB));
    for (uRank = 0; uRank < 8; uRank++)
    {
        for (uFile = 0; uFile < 8; uFile++)
        {
            c = (uRank << 4) | uFile;
            for (uDir = 0; g_iQKDeltas[uDir] != 0; uDir++)
            {
                cSquare = c + g_iQKDeltas[uDir];
                if (IS_ON_BOARD(cSquare))
                {
                    g_KingAttacksBB[c] |= COOR_TO_BB(cSquare);
                }
            }
        }
    }
}

//
// Per-square, per-side "the (up to 2) squares a pawn of this side
// would need to stand on to attack c" bitboard -- e.g.
// g_PawnAttackOriginBB[WHITE][c] is c's two SE/SW neighbors (a white
// pawn attacks diagonally forward, so it must stand behind-and-beside
// c to hit it). Same idea as g_KnightAttacksBB: a single lookup+AND
// against bbPawns[side] answers "does uSide have a pawn attacking c"
// entirely in bit-space, no COOR arithmetic/IS_ON_BOARD check at
// runtime -- see _GetAttacksBB (see.c) for the consumer.
//
BITBOARD g_PawnAttackOriginBB[2][128];

void
InitializePawnAttackOriginTable(void)
/**

Routine description:

    One-time startup init for g_PawnAttackOriginBB -- see its comment.

Parameters:

    void

Return value:

    void

**/
{
    static const int iSeeDelta[2] = { -17, +15 }; // BLACK, WHITE
    ULONG uRank, uFile, uSide;
    COOR c, cOrigin;

    memset(g_PawnAttackOriginBB, 0, sizeof(g_PawnAttackOriginBB));
    for (uRank = 0; uRank < 8; uRank++)
    {
        for (uFile = 0; uFile < 8; uFile++)
        {
            c = (uRank << 4) | uFile;
            for (uSide = 0; uSide < 2; uSide++)
            {
                cOrigin = c + iSeeDelta[uSide];
                if (IS_ON_BOARD(cOrigin))
                {
                    g_PawnAttackOriginBB[uSide][c] |= COOR_TO_BB(cOrigin);
                }
                cOrigin += 2;
                if (IS_ON_BOARD(cOrigin))
                {
                    g_PawnAttackOriginBB[uSide][c] |= COOR_TO_BB(cOrigin);
                }
            }
        }
    }
}

//
// Magic-bitboard tables for rook/bishop move generation -- see
// board_representation/MOVEGEN_MIGRATION.md sections 2a/3 for the
// full design writeup. Everything here (occupancy masks, magic
// numbers, and the attack tables they index into) is computed once at
// startup by InitMagic(), never hardcoded -- a validation prototype
// measured the full search+build+verify cost at ~0.22s for both piece
// types combined, cheap enough to just pay at every process launch
// rather than maintaining hand-pasted constants that could silently
// drift out of sync with the ray tables or square numbering they're
// derived from.
//
// g_RookOccupancyMask[c] / g_BishopOccupancyMask[c]: the "relevant
// occupancy" bits for a slider on c -- g_RookRayToEdge/
// g_BishopRayToEdge's full ray-to-edge, minus each direction's
// outermost square (a piece standing on the actual board edge can't
// hide a further blocker, so it doesn't affect which squares are
// reachable and must be excluded to keep the occupancy-permutation
// count, and therefore the attack table size, minimal).
//
// g_RookMagic[c] / g_BishopMagic[c] and g_RookMagicShift[c] /
// g_BishopMagicShift[c]: found by InitMagic() via a random
// sparse-candidate search, fixed-seeded (see g_MagicRngState below)
// so a given build reproduces the exact same magics on every run --
// deliberately NOT using libc's rand()/srand(), since main.c's
// startup path already calls srand((unsigned int)time(0)) for
// unrelated reasons, and piggybacking on that shared, time-seeded
// generator would silently reintroduce the very non-determinism this
// design is meant to avoid.
//
// g_RookAttackTable[c] / g_BishopAttackTable[c]: one malloc'd array
// per square, indexed by ((occupancy & mask) * magic) >> shift,
// giving the complete pseudo-legal destination bitboard (empty
// squares plus the nearest blocker in every direction, regardless of
// which side owns it -- the caller is responsible for ANDing off
// friendly occupancy before treating the blocker square as a legal
// destination, same convention g_KnightAttacksBB's consumer already
// uses). Never freed -- these live for the process's lifetime, same
// as every other table in this file.
//
BITBOARD g_RookOccupancyMask[128];
BITBOARD g_BishopOccupancyMask[128];
BITBOARD g_RookMagic[128];
BITBOARD g_BishopMagic[128];
ULONG g_RookMagicShift[128];
ULONG g_BishopMagicShift[128];
BITBOARD *g_RookAttackTable[128];
BITBOARD *g_BishopAttackTable[128];

// Private PRNG state for the magic-number search -- deliberately
// separate from libc's rand()/srand() (see the block comment above).
// xorshift64*, fixed literal seed: the exact value doesn't matter, but
// it must never change to a time-based or otherwise run-varying seed,
// or every reproducibility claim in MOVEGEN_MIGRATION.md section 2a
// stops being true.
static UINT64 g_MagicRngState = 88172645463325252ULL;

static UINT64
_MagicNextRandom64(void)
{
    UINT64 x = g_MagicRngState;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    g_MagicRngState = x;
    return x;
}

// Sparse (mostly-zero-bit) candidates are known to converge faster in
// magic-number search than uniform random 64-bit values -- standard
// technique, matches the validation prototype this was ported from.
static UINT64
_MagicSparseRandom64(void)
{
    return _MagicNextRandom64() & _MagicNextRandom64() & _MagicNextRandom64();
}

// Slow, obviously-correct reference used both to build each magic
// table's contents and to verify it before InitMagic() accepts it:
// walk each of the 4 directions from c until (and including) the
// first occupied square, given a full occupancy bitboard covering
// both sides' pieces.
static BITBOARD
_MagicSlowAttacks(COOR c, BITBOARD bbOccupied, const int iDelta[4])
{
    BITBOARD bbResult = 0;
    ULONG uDir;
    COOR cSquare;

    for (uDir = 0; uDir < 4; uDir++)
    {
        for (cSquare = c + iDelta[uDir];
             IS_ON_BOARD(cSquare);
             cSquare += iDelta[uDir])
        {
            BITBOARD bbSq = COOR_TO_BB(cSquare);
            bbResult |= bbSq;
            if (bbOccupied & bbSq)
            {
                break;
            }
        }
    }
    return bbResult;
}

// Standard "carry-rippler" occupancy-subset enumeration: the uIndex-th
// subset of mask's set bits, treating uIndex's own bits as a
// present/absent flag for each of mask's bits in ascending-bit order.
static BITBOARD
_MagicIndexToOccupancy(ULONG uIndex, ULONG uBits, BITBOARD mask)
{
    BITBOARD bbResult = 0;
    ULONG i, uBit;

    for (i = 0; i < uBits; i++)
    {
        uBit = FastFirstBit(mask) - 1;
        mask &= mask - 1;
        if (uIndex & (1UL << i))
        {
            bbResult |= (1ULL << uBit);
        }
    }
    return bbResult;
}

// Builds the relevant-occupancy mask for one square: the full ray to
// the edge in each of the 4 directions, minus that direction's
// outermost square -- see the block comment above
// g_RookOccupancyMask/g_BishopOccupancyMask.
static BITBOARD
_MagicBuildOccupancyMask(COOR c, const int iDelta[4])
{
    BITBOARD bbResult = 0;
    ULONG uDir;
    COOR cSquare;

    for (uDir = 0; uDir < 4; uDir++)
    {
        for (cSquare = c + iDelta[uDir];
             IS_ON_BOARD(cSquare);
             cSquare += iDelta[uDir])
        {
            if (IS_ON_BOARD(cSquare + iDelta[uDir]))
            {
                bbResult |= COOR_TO_BB(cSquare);
            }
        }
    }
    return bbResult;
}

// Finds a collision-free magic number for one square, builds its
// attack table from it, and verifies the whole thing against the slow
// reference one more time before returning -- the section 2a
// collision-freedom gate, run fresh at every startup rather than
// trusted from a prior offline run.
static void
_MagicFindAndBuildForSquare(COOR c, BITBOARD mask, const int iDelta[4],
                             BITBOARD *pMagic, ULONG *pShift,
                             BITBOARD **ppTable)
{
    ULONG uBits = CountBits(mask);
    ULONG uSize = 1UL << uBits;
    ULONG uShift = 64 - uBits;
    BITBOARD *rgbbOccupancy = malloc(sizeof(BITBOARD) * uSize);
    BITBOARD *rgbbAttacks = malloc(sizeof(BITBOARD) * uSize);
    BITBOARD *rgbbTable = malloc(sizeof(BITBOARD) * uSize);
    FLAG *rgfFilled = malloc(sizeof(FLAG) * uSize);
    ULONG i;
    UINT64 uMagic;

    if ((NULL == rgbbOccupancy) || (NULL == rgbbAttacks) ||
        (NULL == rgbbTable) || (NULL == rgfFilled))
    {
        Bug("InitMagic: out of memory building table for square %d\n", c);
    }

    for (i = 0; i < uSize; i++)
    {
        rgbbOccupancy[i] = _MagicIndexToOccupancy(i, uBits, mask);
        rgbbAttacks[i] = _MagicSlowAttacks(c, rgbbOccupancy[i], iDelta);
    }

    for (;;)
    {
        FLAG fCollision = FALSE;
        ULONG uIndex;

        uMagic = _MagicSparseRandom64();

        // Quick reject: a magic whose high byte doesn't spread widely
        // when multiplied against the mask rarely yields a
        // collision-free hash -- a cheap filter to skip obviously bad
        // candidates before paying for the full uSize-entry pass.
        if (CountBits((UINT64)(mask * uMagic) & 0xFF00000000000000ULL) < 6)
        {
            continue;
        }

        memset(rgfFilled, 0, sizeof(FLAG) * uSize);
        for (i = 0; (i < uSize) && !fCollision; i++)
        {
            uIndex = (ULONG)(((UINT64)rgbbOccupancy[i] * uMagic) >> uShift);
            if (!rgfFilled[uIndex])
            {
                rgfFilled[uIndex] = TRUE;
                rgbbTable[uIndex] = rgbbAttacks[i];
            }
            else if (rgbbTable[uIndex] != rgbbAttacks[i])
            {
                fCollision = TRUE;
            }
        }
        if (!fCollision)
        {
            break;
        }
    }

    //
    // Belt-and-suspenders: re-verify every occupancy subset against
    // the slow reference one more time before accepting this magic.
    // Redundant with the search loop's own collision bookkeeping
    // above in the common case, but this is the load-bearing
    // correctness gate the rest of the magic-bitboard subsystem
    // depends on (MOVEGEN_MIGRATION.md section 2a) -- worth paying
    // for explicitly rather than trusting the search loop alone.
    //
    for (i = 0; i < uSize; i++)
    {
        BITBOARD bbOcc = _MagicIndexToOccupancy(i, uBits, mask);
        BITBOARD bbExpected = _MagicSlowAttacks(c, bbOcc, iDelta);
        ULONG uIndex = (ULONG)(((UINT64)bbOcc * uMagic) >> uShift);

        if (rgbbTable[uIndex] != bbExpected)
        {
            Bug("InitMagic: verification failed for square %d, "
                "occupancy subset %lu\n", c, i);
        }
    }

    *pMagic = uMagic;
    *pShift = uShift;
    *ppTable = rgbbTable;
    free(rgbbOccupancy);
    free(rgbbAttacks);
    free(rgfFilled);
}

void
InitMagic(void)
/**

Routine description:

    One-time startup init for the rook/bishop magic-bitboard tables --
    see the block comment above g_RookOccupancyMask/g_BishopOccupancyMask
    for the full design and board_representation/MOVEGEN_MIGRATION.md
    sections 2a/3 for the writeup. Must run after nothing in particular
    (no dependency on the other Initialize*Tables functions), but is
    grouped alongside them in main.c's startup sequence for consistency.

Parameters:

    void

Return value:

    void

**/
{
    ULONG uRank, uFile;

    memset(g_RookOccupancyMask, 0, sizeof(g_RookOccupancyMask));
    memset(g_BishopOccupancyMask, 0, sizeof(g_BishopOccupancyMask));
    memset(g_RookMagic, 0, sizeof(g_RookMagic));
    memset(g_BishopMagic, 0, sizeof(g_BishopMagic));
    memset(g_RookMagicShift, 0, sizeof(g_RookMagicShift));
    memset(g_BishopMagicShift, 0, sizeof(g_BishopMagicShift));
    memset(g_RookAttackTable, 0, sizeof(g_RookAttackTable));
    memset(g_BishopAttackTable, 0, sizeof(g_BishopAttackTable));

    for (uRank = 0; uRank < 8; uRank++)
    {
        for (uFile = 0; uFile < 8; uFile++)
        {
            COOR c = (uRank << 4) | uFile;

            g_RookOccupancyMask[c] =
                _MagicBuildOccupancyMask(c, g_RookRayDeltas);
            _MagicFindAndBuildForSquare(c, g_RookOccupancyMask[c],
                                        g_RookRayDeltas,
                                        &g_RookMagic[c],
                                        &g_RookMagicShift[c],
                                        &g_RookAttackTable[c]);

            g_BishopOccupancyMask[c] =
                _MagicBuildOccupancyMask(c, g_BishopRayDeltas);
            _MagicFindAndBuildForSquare(c, g_BishopOccupancyMask[c],
                                        g_BishopRayDeltas,
                                        &g_BishopMagic[c],
                                        &g_BishopMagicShift[c],
                                        &g_BishopAttackTable[c]);
        }
    }
}