#include <assert.h>
#include <stdio.h>
#include "ramjet.h"
#include "bitboard.h"

// generalised left shift operator
BITBOARD bb_shift(BITBOARD bb, int i)
{
    assert(i > -64 && i < 64);
    return (i > 0)? bb << i : bb >> -i;
}

// diagonal rays on an empty board
BITBOARD bb_diag[64];
BITBOARD bb_anti[64];

// initialise the diagonal rays
static void bb_diag_anti_init()
{
    int sq, rk, fl;

    static const BITBOARD diag = BB_CONST(0x8040201008040201);
    static const BITBOARD anti = BB_CONST(0x0102040810204080);

    // shift the base mask by the (anti)diagonal index
    for(sq = 0; sq < 64; ++sq) {
        rk = SQ_RANK(sq);
        fl = SQ_FILE(sq);
        bb_diag[sq] = bb_shift(diag, 8 * (rk - fl));
        bb_anti[sq] = bb_shift(anti, 8 * (rk + fl - 7));
    }
}

// leapers on an empty board
BITBOARD bb_k_leap[64];
BITBOARD bb_n_leap[64];

static void bb_k_n_leap_init()
{
    static const BITBOARD rank_78 = ~BB_CONST(0x000000000000FFFF);
    static const BITBOARD rank_12 = ~BB_CONST(0xFFFF000000000000);
    static const BITBOARD file_ab = ~BB_CONST(0x0303030303030303);
    static const BITBOARD file_gh = ~BB_CONST(0xC0C0C0C0C0C0C0C0);
    static const BITBOARD ray_Kd4 = BB_CONST(0x00001C141C000000);
    static const BITBOARD ray_Nd4 = BB_CONST(0x0014220022140000);

    int sq, rk, fl;

    // for each square
    for(sq = 0; sq < 64; ++sq) {
        rk = SQ_RANK(sq);
        fl = SQ_FILE(sq);

        // shift the base pattern by the square difference
        bb_k_leap[sq] = bb_shift(ray_Kd4, sq - D4);
        bb_n_leap[sq] = bb_shift(ray_Nd4, sq - D4);

        // mask the overflows away (rank)
        if(rk < 2) {
            bb_k_leap[sq] &= rank_12;
            bb_n_leap[sq] &= rank_12;
        } else if(rk >= 6) {
            bb_k_leap[sq] &= rank_78;
            bb_n_leap[sq] &= rank_78;
        }

        // mask the overflows away (file)
        if(fl < 2) {
            bb_k_leap[sq] &= file_gh;
            bb_n_leap[sq] &= file_gh;
        } else if(fl >= 6) {
            bb_k_leap[sq] &= file_ab;
            bb_n_leap[sq] &= file_ab;
        }
    }
}

// en-passant attackers
BITBOARD bb_ep_atk[65] = {BB_NULL};

// initialise the en-passant bitboards
static void bb_ep_atk_init()
{
    int sq;

    for(sq = A6; sq <= G6; ++sq)
        bb_ep_atk[sq] |= BB_SQ(SQ_DIA_E(sq, BLACK));
    for(sq = B6; sq <= H6; ++sq)
        bb_ep_atk[sq] |= BB_SQ(SQ_DIA_W(sq, BLACK));
    for(sq = A3; sq <= G3; ++sq)
        bb_ep_atk[sq] |= BB_SQ(SQ_DIA_E(sq, WHITE));
    for(sq = B3; sq <= H3; ++sq)
        bb_ep_atk[sq] |= BB_SQ(SQ_DIA_W(sq, WHITE));
}

// castle occupancy mask
BITBOARD bb_castle_occ[8][8];

// initialise the castle bitboards
static void bb_castle_occ_init()
{
    BITBOARD bb;
    int east, from, to, k_sq, r_sq;

    // "impossible" [from][to] combos are assigned all ones
    // legit combos only the relevant squares for castling
    for(to = 0; to < 8; ++to) {
        bb_castle_occ[0][to] = BB_ALL(1);
        bb_castle_occ[7][to] = BB_ALL(1);
        for(from = 1; from <= 6; ++from) {
            if(from == to)
                bb_castle_occ[from][to] = BB_ALL(1);
            else {
                east = ((from - to) >> 3) & 1;
                k_sq = SQ_K_CASTLE(east, BLACK);
                r_sq = SQ_R_CASTLE(east, BLACK);
                bb = ((BB_SQ(from) - 1) ^ (BB_SQ(k_sq) - 1)) | BB_SQ(k_sq);
                bb |= ((BB_SQ(to) - 1) ^ (BB_SQ(r_sq) - 1)) | BB_SQ(r_sq);
                bb &= ~(BB_SQ(from) | BB_SQ(to));
                bb_castle_occ[from][to] = bb | (bb << 56);
            }
        }
    }
}

// kindergarten attack masks
static BITBOARD kg_rank[8][64];
static BITBOARD kg_file[8][64];

// compute the kindergarten attack mask for the first byte
static BITBOARD kg_first_byte(int occ, int sq)
{
    assert(occ >= 0 && occ < 256);
    assert(sq >= 0 && sq < 8);

    BITBOARD bb = BB_NULL;
    int i;

    // slide down to the first obstacle
    for(i = sq - 1; i >= 0; --i) {
        bb |= (1 << i);
        if((occ & (1 << i)))
            break;
    }

    // slide up to the first obstacle
    for(i = sq + 1; i < 8; ++i) {
        bb |= (1 << i);
        if((occ & (1 << i)))
            break;
    }

    return bb;
}

// initialise the kindergarten attack masks
static void kg_rank_file_init()
{
    static const BITBOARD file_a = BB_CONST(0x0101010101010101);
    static const BITBOARD diag = BB_CONST(0x8040201008040201);

    BITBOARD bb;
    int sq, occ;

    // rank (and diagonals) are just an eight-fold replica of the first byte
    // whereas file attacks are restricted on the a file and inverted
    for(sq = 0; sq < 8; ++sq)
        for(occ = 0; occ < 64; ++occ) {
            bb = kg_first_byte(occ << 1, sq);
            kg_rank[sq][occ] = bb * file_a;
            kg_file[sq ^ 7][occ] = ((bb * diag) >> 7) & file_a;
        }
}

// initialise the constants
void bb_init()
{
    bb_diag_anti_init();
    bb_k_n_leap_init();
    bb_ep_atk_init();
    bb_castle_occ_init();
    kg_rank_file_init();
}

// return the index of the least significant bit (modulo 67 version)
int bb_lsb_sq(BITBOARD bb)
{
    static const int table[67] = {64,  0,  1, 39,  2, 15, 40, 23,  3, 12, 16, 59, 41, 19, 24, 54,  4,
                                  -1, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, 47,  5, 32,
                                  -1, 38, 14, 22, 11, 58, 18, 53, 63,  9, 61, 27, 29, 50, 43, 46, 31,
                                  37, 21, 57, 52,  8, 26, 49, 45, 36, 56,  7, 48, 35,  6, 34, 33};

    return table[(bb & -bb) % 67];
}

// return the index of the least significant bit while setting it to zero
int bb_lsb_next(BITBOARD* bb)
{
    int sq = bb_lsb_sq(*bb);
    *bb &= (*bb - 1);
    return sq;
}

// return the number of bits that are on (Donald Knuth version)
int bb_pop_count(BITBOARD bb)
{
    static const BITBOARD mask_duo = BB_CONST(0x5555555555555555);
    static const BITBOARD mask_nibble = BB_CONST(0x3333333333333333);
    static const BITBOARD mask_octet = BB_CONST(0x0F0F0F0F0F0F0F0F);
    static const BITBOARD mask_sum = BB_CONST(0x0101010101010101);

    bb -= ((bb >> 1) & mask_duo);
    bb = (bb & mask_nibble) + ((bb >> 2) & mask_nibble);
    bb += (bb >> 4);
    bb = ((bb & mask_octet) * mask_sum) >> 56;

    return (int) bb;
}

// true for single populated bitboards
int is_bb_single(BITBOARD bb)
{
    return (bb != BB_NULL && (bb & (bb - 1)) == 0);
}

// sliding attacks along the diagonal
BITBOARD bb_diag_atk(BITBOARD occ, SQUARE sq)
{
    assert(!IS_SQ_BAD(sq));
    static const BITBOARD file_b = BB_CONST(0x0202020202020202);
    occ = ((occ & bb_diag[sq]) * file_b) >> 58;
    return bb_diag[sq] & kg_rank[SQ_FILE(sq)][occ];
}

// sliding attacks along the anti-diagonal
BITBOARD bb_anti_atk(BITBOARD occ, SQUARE sq)
{
    assert(!IS_SQ_BAD(sq));
    static const BITBOARD file_b = BB_CONST(0x0202020202020202);
    occ = ((occ & bb_anti[sq]) * file_b) >> 58;
    return bb_anti[sq] & kg_rank[SQ_FILE(sq)][occ];
}

// sliding attacks along the rank
BITBOARD bb_rank_atk(BITBOARD occ, SQUARE sq)
{
    assert(!IS_SQ_BAD(sq));
    static const BITBOARD file_b = BB_CONST(0x0202020202020202);
    occ = ((occ & BB_RANK(sq)) * file_b) >> 58;
    return BB_RANK(sq) & kg_rank[SQ_FILE(sq)][occ];
}

// sliding attacks along the file
BITBOARD bb_file_atk(BITBOARD occ, SQUARE sq)
{
    assert(!IS_SQ_BAD(sq));
    static const BITBOARD file_a = BB_CONST(0x0101010101010101);
    static const BITBOARD diag_c7h2 = BB_CONST(0x0080402010080400);
    occ = (occ >> SQ_FILE(sq)) & file_a;
    occ = (occ * diag_c7h2) >> 58;
    return kg_file[SQ_RANK(sq)][occ] << SQ_FILE(sq);
}

// bishop combo attacks
BITBOARD bb_b_slide(BITBOARD occ, SQUARE sq)
{
    return bb_diag_atk(occ, sq) | bb_anti_atk(occ, sq);
}

// rook combo attacks
BITBOARD bb_r_slide(BITBOARD occ, SQUARE sq)
{
    return bb_rank_atk(occ, sq) | bb_file_atk(occ, sq);
}

// colour-dependent shift forward
BITBOARD bb_front(BITBOARD bb, PLAYER pl)
{
    assert(!IS_PL_BAD(pl));
    return (pl == WHITE)? bb >> 8 : bb << 8;
}

// colour-dependent shift forward on rank 4 (white) and rank 5 (black)
BITBOARD bb_front_45(BITBOARD bb, PLAYER pl)
{
    assert(!IS_PL_BAD(pl));
    static const BITBOARD rank_4 = BB_CONST(0x000000FF00000000);
    static const BITBOARD rank_5 = BB_CONST(0x00000000FF000000);
    return (pl == WHITE)? (bb >> 8) & rank_4 : (bb << 8) & rank_5;
}

// colour-dependent diagonal shift westward
BITBOARD bb_dia_w(BITBOARD bb, PLAYER pl)
{
    assert(!IS_PL_BAD(pl));
    static const BITBOARD file_h = ~BB_CONST(0x8080808080808080);
    return ((pl == WHITE)? bb >> 9 : bb << 7) & file_h;
}

// colour-dependent diagonal shift eastward
BITBOARD bb_dia_e(BITBOARD bb, PLAYER pl)
{
    assert(!IS_PL_BAD(pl));
    static const BITBOARD file_a = ~BB_CONST(0x0101010101010101);
    return ((pl == WHITE)? bb >> 7 : bb << 9) & file_a;
}

// pawn combo attacks
BITBOARD bb_p_atk(SQUARE sq, PLAYER pl)
{
    assert(!IS_SQ_BAD(sq));
    return bb_dia_w(BB_SQ(sq), pl) | bb_dia_e(BB_SQ(sq), pl);
}

// pawn combo pushes
BITBOARD bb_p_push(BITBOARD occ, SQUARE sq, PLAYER pl)
{
    assert(!IS_SQ_BAD(sq));
    BITBOARD mask = bb_front(BB_SQ(sq), pl) & ~occ;
    return mask | (bb_front_45(mask, pl) & ~occ);
}

// write the bitboard in 0-1 format at the end of the file
void bb_print_01(FILE* fp, BITBOARD bb)
{
    int rk, fl;

    if(fp == NULL)
        return;

    for(rk = 0; rk < 8; ++rk) {
        for(fl = 0; fl < 8; ++fl) {
            fprintf(fp, "%c", '0' + (int) (bb & 1));
            bb >>= 1;
        }
        fprintf(fp, "\n");
    }
    fprintf(fp, "\n");
}

// test the functions above
int bb_test()
{
    // square selection
    BITBOARD mask = BB_SQ(A5) | BB_SQ(B3) | BB_SQ(C1) | BB_SQ(D7) |
                    BB_SQ(E2) | BB_SQ(F8) | BB_SQ(G6) | BB_SQ(H4);
    if(BB_ALL(1) != ~BB_NULL || mask != BB_CONST(0x0410028001400820))
        return 1;

    // rays on an empty board
    if(BB_RANK(D7) != BB_CONST(0x000000000000FF00) ||
       BB_FILE(D7) != BB_CONST(0x0808080808080808) ||
       bb_diag[D7] != BB_CONST(0x0000804020100804) ||
       bb_anti[D7] != BB_CONST(0x0000000102040810))
        return 2;

    // leapers on an empty board
    if(bb_k_leap[A8] != BB_CONST(0x0000000000000302) ||
       bb_k_leap[G1] != BB_CONST(0xA0E0000000000000) ||
       bb_n_leap[B2] != BB_CONST(0x0800080500000000) ||
       bb_n_leap[H7] != BB_CONST(0x0000000040200020))
        return 3;

    // en-passant attackers
    if(bb_ep_atk[SQ_NULL] != BB_NULL || bb_ep_atk[D4] != BB_NULL ||
       bb_ep_atk[A6] != BB_SQ(B5) || bb_ep_atk[H3] != BB_SQ(G4) ||
       bb_ep_atk[C3] != (BB_SQ(B4) | BB_SQ(D4)))
        return 4;

    // castle occupancy mask on both rank 1 and 8
    if(bb_castle_occ[6][0] != BB_CONST(0x3E0000000000003E) ||
       bb_castle_occ[3][5] != BB_CONST(0x5000000000000050) ||
       BB_CASTLE_CHECK(D8, G8) != (BB_SQ(D8) | BB_SQ(E8) | BB_SQ(F8)) ||
       BB_CASTLE_CHECK(C1, C1) != BB_SQ(C1))
        return 5;

    // return the index of the least significant bit
    mask = BB_SQ(E3) | BB_SQ(F4);
    if(bb_lsb_next(&mask) != F4 || bb_lsb_next(&mask) != E3)
        return 6;

    // return the number of bits that are on
    if(bb_pop_count(BB_NULL) != 0 || bb_pop_count(BB_SQ(E1) | BB_SQ(E3) | BB_SQ(E4)) != 3)
        return 7;

    // true for single populated bitboards
    if(is_bb_single(BB_NULL) || !is_bb_single(BB_SQ(D4)) || is_bb_single(BB_SQ(G5) | BB_SQ(G4)))
        return 8;

    // sliding attacks along the four rays
    mask = BB_SQ(B5) | BB_SQ(B2) | BB_SQ(E2);
    if(bb_diag_atk(mask, C4) != BB_CONST(0x0010080002000000) ||
       bb_anti_atk(mask, G4) != BB_CONST(0x0010200080000000) ||
       bb_rank_atk(mask, H2) != BB_CONST(0x0070000000000000) ||
       bb_file_atk(mask, B4) != BB_CONST(0x0002020002000000))
        return 9;

    // colour-dependent shifts
    mask = BB_SQ(A6) | BB_SQ(H5);
    if(bb_front_45(mask, WHITE) || bb_front_45(mask, BLACK) != BB_SQ(A5) ||
       bb_dia_w(mask, WHITE) != BB_SQ(G6) || bb_dia_w(mask, BLACK) != BB_SQ(G4) ||
       bb_dia_e(mask, WHITE) != BB_SQ(B7) || bb_dia_e(mask, BLACK) != BB_SQ(B5))
        return 10;

    return 0;
}
