path: root/src/testbitboard.c

/**

Copyright (c) Scott Gasch

Module Name:

    testbitboard.c

Abstract:

    Unit test for the bitboard code.

Author:

    Scott Gasch ([email protected]) 19 Oct 2004

Revision History:

**/

#ifdef TEST
#include "chess.h"

void TestBitboards(void)
/**

Routine description:

    Sanity check bitboard code and benchmark the different ways to
    twiddle bits.

Parameters:

    void

Return value:

    void

**/
{
    COOR c;
    ULONG b;
    BITBOARD bb;
    // volatile, separate from bb (which is reused below for unrelated
    // correctness checks and gets passed by address -- making it
    // volatile there breaks those calls): without a volatile sink, the
    // SLOWCOOR_TO_BB/COOR_TO_BB benchmark loops just below compute a
    // value and never use it again, so the optimizer proves they have
    // no effect and deletes them entirely -- this used to silently
    // report "0 cycles/op" for both, an obviously impossible number
    // that was never actually measuring anything (same class of bug
    // documented in eval.c's RunEvalRookAB comment: "the first time
    // this was written it produced 0.000s / inf calls/sec"). Other
    // loops below (CountBits/LastBit/FirstBit etc.) happened to
    // survive because those are real out-of-line/opaque calls the
    // optimizer can't prove are side-effect-free; the COOR_TO_BB
    // macros expand to plain visible expressions with nothing
    // stopping them from being optimized away.
    volatile BITBOARD bbSink;
    BITBOARD bbSpeed[1000];
    ULONG u, v, w, z;
    UINT64 u64;

    Trace("Testing bitboard operations...\n");

    //
    // Make a table of 1000 random bitboards
    //
    for (u = 0;
         u < 1000;
         u++)
    {
        bbSpeed[u] = 0;
        w = rand() % 24;
        for (v = 0; v < w; v++)
        {
            z = RANDOM_COOR;
            ASSERT(SLOWCOOR_TO_BB(z) == COOR_TO_BB(z));
            bb = COOR_TO_BB(z);
            bbSpeed[u] |= bb;
        }
    }

#if 1
    //
    // Various benchmaring code.
    //
    u64 = SystemReadTimeStampCounter();
    for (u = 0; u < 1000000; u++)
    {
        b = u % 64;
        bbSink = SLOWCOOR_TO_BB(b);
    }
    printf(" SLOWCOOR_TO_BB:   %" COMPILER_LONGLONG_UNSIGNED_FORMAT
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / 1000000);
    u64 = SystemReadTimeStampCounter();
    for (u = 0; u < 1000000; u++)
    {
        b = u % 64;
        bbSink = COOR_TO_BB(b);
    }
    printf(" COOR_TO_BB:       %" COMPILER_LONGLONG_UNSIGNED_FORMAT
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / 1000000);
    // bbSink's individual writes are never dead-code-eliminated
    // (that's what volatile guarantees) regardless of whether anything
    // reads it afterward, but nothing did until this line -- report it
    // so the compiler doesn't flag it as unused, same pattern the
    // evalcycles command uses for its own timing-loop sink.
    printf(" (bbSink final value, just to use it: %#llx)\n",
           (unsigned long long)bbSink);

    u64 = SystemReadTimeStampCounter();
    for (v = 1; v < 1000; v++)
    {
        for (u = 0; u < 1000; u++)
        {
            b = SlowCountBits(bbSpeed[u]);
        }
    }
    printf(" SlowCountBits:    %" COMPILER_LONGLONG_UNSIGNED_FORMAT 
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / (1000 * 1000));

    u64 = SystemReadTimeStampCounter();
    for (v = 0; v < 1000; v++)
    {
        for (u = 0; u < 1000; u++)
        {
            b = CountBits(bbSpeed[u]);
        }
    }
    printf(" CountBits:        %" COMPILER_LONGLONG_UNSIGNED_FORMAT 
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / (1000 * 1000));

    u64 = SystemReadTimeStampCounter();
    for (v = 0; v < 1000; v++)
    {
        for (u = 0; u < 1000; u++)
        {
            b = SlowLastBit(bbSpeed[u]);
        }
    }
    printf(" SlowLastBit:      %" COMPILER_LONGLONG_UNSIGNED_FORMAT 
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / (1000 * 1000));

    u64 = SystemReadTimeStampCounter();
    for (v = 0; v < 1000; v++)
    {
        for (u = 0; u < 1000; u++)
        {
            b = LastBit(bbSpeed[u]);
        }
    }
    printf(" LastBit:          %" COMPILER_LONGLONG_UNSIGNED_FORMAT 
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / (1000 * 1000));

    u64 = SystemReadTimeStampCounter();
    for (v = 0; v < 1000; v++)
    {
        for (u = 0; u < 1000; u++)
        {
            b = SlowFirstBit(bbSpeed[u]);
        }
    }
    printf(" SlowFirstBit:     %" COMPILER_LONGLONG_UNSIGNED_FORMAT 
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / (1000 * 1000));

    u64 = SystemReadTimeStampCounter();
    for (v = 0; v < 1000; v++)
    {
        for (u = 0; u < 1000; u++)
        {
            b = DeBruijnFirstBit(bbSpeed[u]);
        }
    }
    printf(" DeBruijnFirstBit: %" COMPILER_LONGLONG_UNSIGNED_FORMAT 
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / (1000 * 1000));

    u64 = SystemReadTimeStampCounter();
    for (v = 0; v < 1000; v++)
    {
        for (u = 0; u < 1000; u++)
        {
            b = FirstBit(bbSpeed[u]);
        }
    }
    printf(" FirstBit:         %" COMPILER_LONGLONG_UNSIGNED_FORMAT
           " cycles/op\n",
           (SystemReadTimeStampCounter() - u64) / (1000 * 1000));

    // 2026-10-05: measuring the bitboard-bit -> 0x88 COOR conversion
    // chain actually used in generate.c's per-piece scan loops
    // (FastCoorFromBitBoardRank8ToRank1: ctzll + BIT_NUMBER_TO_COOR +
    // bit-clear, all inlined) -- not the bare macro in isolation, the
    // real call site shape, same rdtsc methodology as the other
    // benchmarks in this function.
    {
        volatile COOR cSink;
        BITBOARD bbScan;
        UINT64 u64Ops = 0;
        u64 = SystemReadTimeStampCounter();
        for (v = 0; v < 1000; v++)
        {
            for (u = 0; u < 1000; u++)
            {
                bbScan = bbSpeed[u];
                while (bbScan)
                {
                    cSink = FastCoorFromBitBoardRank8ToRank1(&bbScan);
                    u64Ops++;
                }
            }
        }
        u64Ops += (0 == u64Ops);
        printf(" FastCoorFromBitBoardRank8ToRank1 (per bit popped, "
               "%" COMPILER_LONGLONG_UNSIGNED_FORMAT " total ops): %"
               COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/op\n",
               u64Ops,
               (SystemReadTimeStampCounter() - u64) / u64Ops);
        printf(" (cSink final value, just to use it: %u)\n", cSink);
    }

    // Bare BIT_NUMBER_TO_COOR macro alone, no bit-scan, to isolate the
    // conversion arithmetic itself from the ctzll/bit-clear around it.
    {
        volatile COOR cSink2;
        u64 = SystemReadTimeStampCounter();
        for (u = 0; u < 1000000; u++)
        {
            b = u % 64;
            cSink2 = BIT_NUMBER_TO_COOR(b);
        }
        printf(" BIT_NUMBER_TO_COOR (bare macro): %"
               COMPILER_LONGLONG_UNSIGNED_FORMAT " cycles/op\n",
               (SystemReadTimeStampCounter() - u64) / 1000000);
        printf(" (cSink2 final value, just to use it: %u)\n", cSink2);
    }
#endif

    FOREACH_SQUARE(c)
    {
        if (!IS_ON_BOARD(c)) continue;
        
        if (BIT_NUMBER_TO_COOR(COOR_TO_BIT_NUMBER(c)) != c)
        {
            UtilPanic(TESTCASE_FAILURE,
                      NULL, 
                      "bit number to coor / coor to bit number", 
                      NULL, 
                      NULL,
                      __FILE__, __LINE__);
        }

        if (SLOW_BIT_NUMBER_TO_COOR(COOR_TO_BIT_NUMBER(c)) != c)
        {
            UtilPanic(TESTCASE_FAILURE,
                      NULL, 
                      "slow bit number to coor / coor to bit number", 
                      NULL,
                      NULL,
                      __FILE__, __LINE__);
        }
        
        if (BIT_NUMBER_TO_COOR(COOR_TO_BIT_NUMBER(c)) !=
            SLOW_BIT_NUMBER_TO_COOR(COOR_TO_BIT_NUMBER(c)))
        {
            UtilPanic(TESTCASE_FAILURE,
                      NULL, 
                      "bit number to coor / slow bit number to coor", 
                      NULL, 
                      NULL,
                      __FILE__, __LINE__);
        }
    }
    
    for (b = 1;
         b < 64;
         b++)
    {
        if (COOR_TO_BIT_NUMBER(BIT_NUMBER_TO_COOR(b)) != (b))
        {
            UtilPanic(TESTCASE_FAILURE,
                      NULL, 
                      "coor to bit number / bit number to coor", 
                      NULL, 
                      NULL,
                      __FILE__, __LINE__);
        }
    }
    
    bb = COOR_TO_BB(A4);
    bb |= COOR_TO_BB(A6);
    bb |= COOR_TO_BB(A8);
    bb |= COOR_TO_BB(B6);
    bb |= COOR_TO_BB(H2);
    if (CountBits(bb) != 5)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "CountBits", NULL, NULL,
                  __FILE__, __LINE__);
    }
    bb &= BBFILE[A];
    if (CountBits(bb) != 3)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "CountBits", NULL, NULL,
                  __FILE__, __LINE__);
    }
    b = 0;
    while(IS_ON_BOARD(c = CoorFromBitBoardRank8ToRank1(&bb)))
    {
        b++;
        if ((c != A4) && (c != A6) && (c != A8))
        {
            UtilPanic(TESTCASE_FAILURE,
                      NULL, "CoorFromBitBoardRank8ToRank1", NULL, NULL,
                      __FILE__, __LINE__);
        }
    }

    if (b != 3)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "CoorFromBitBoardRank8ToRank1", NULL, NULL,
                  __FILE__, __LINE__);
    }

    bb = SLOWCOOR_TO_BB(A4) | SLOWCOOR_TO_BB(H2);
    bb |= SLOWCOOR_TO_BB(D4) | SLOWCOOR_TO_BB(F6) | SLOWCOOR_TO_BB(F4);
    if (CountBits(bb) != 5)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "CountBits", NULL, NULL,
                  __FILE__, __LINE__);
    }
    bb &= BBRANK[4];
    if (CountBits(bb) != 3)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "CountBits", NULL, NULL,
                  __FILE__, __LINE__);
    }
    b = 0;
    while(IS_ON_BOARD(c = CoorFromBitBoardRank1ToRank8(&bb)))
    {
        b++;
        if ((c != A4) && (c != D4) && (c != F4))
        {
            UtilPanic(TESTCASE_FAILURE,
                      NULL, "CoorFromBitBoardRank1ToRank8", NULL, NULL,
                      __FILE__, __LINE__);
        }
    }

    if (b != 3)
    {
        UtilPanic(TESTCASE_FAILURE,
                  NULL, "CoorFromBitBoardRank1ToRank8", NULL, NULL,
                  __FILE__, __LINE__);
    }
}
#endif