/*
    Copyright 2015 Harm Jetten

    This file is part of Moby Dam.

    Moby Dam is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Moby Dam is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Moby Dam.  If not, see <http://www.gnu.org/licenses/>.
*/

/* tt.c: the transposition table functions */

#include "core.h"

ttentry *trans_tbl;   /* the transposition table */
bool large_pg = FALSE;/* trans_tbl alloc'ed as large pages in Windows */
u64 tt_mask;          /* masking unused addressing bits and slot selection */
u64 hash_init;        /* initializer for hash function */
int tt_size = 25;     /* exponent of transposition table size */

/* flush transposition table */
/* it gets a new initial value for the hash function, */
/* thus no need to zero out the whole table */
void flush_tt(void)
{
    hash_init  = (u64)rand();
    hash_init += (u64)rand() << 32;
}

/* wipe transposition table */
/* use instead of flush_tt for somewhat reproducible timing tests */
void wipe_tt(void)
{
    u64 i;

    for (i = 0; i < tt_mask + 4; i++)
    {
        trans_tbl[i].ttsig = 0;
    }
    logf("wiped tt with %" PRIu64 " entries\n", i);
    hash_init = 0x0ecf2aaef2c937b6ULL;
}

/* allocate & initialize transposition table */
/* returns: TRUE if successful */
bool init_tt(void)
{
    u64 i;
    u64 ttentries;

    ttentries = 1ULL << tt_size;

#ifdef _WIN32
    LUID luid;
    HANDLE hToken;
    TOKEN_PRIVILEGES tp;

    /* try to allocate large memory pages to improve performance;   */
    /* for this to work, the program must be run as administrator,  */
    /* and the user's account must previously have been granted the */
    /* "Lock Pages in Memory" privilege in the Group Policy Editor  */
    if (OpenProcessToken(GetCurrentProcess(),
                         TOKEN_ADJUST_PRIVILEGES | TOKEN_QUERY, &hToken) &&
        LookupPrivilegeValue(NULL, SE_LOCK_MEMORY_NAME, &luid))
    {
        tp.PrivilegeCount = 1;
        tp.Privileges[0].Luid = luid;
        tp.Privileges[0].Attributes = SE_PRIVILEGE_ENABLED;
        if (AdjustTokenPrivileges(hToken, FALSE, &tp, sizeof tp, NULL, NULL) &&
            GetLastError() != ERROR_NOT_ALL_ASSIGNED)
        {
            trans_tbl = VirtualAlloc(NULL, ttentries*sizeof(ttentry),
                                     MEM_LARGE_PAGES | MEM_RESERVE | MEM_COMMIT,
                                     PAGE_READWRITE);
        }
    }
    if (trans_tbl != NULL)
    {
        logf("tt allocated with large pages\n");
        large_pg = TRUE;
    }
    else
    {
        /* large pages not available; allocate regular pages; */
        /* align on cache line boundary */
        trans_tbl = _aligned_malloc(ttentries*sizeof(ttentry), 64);
        if (trans_tbl == NULL)
        {
            return FALSE;
        }
    }
#else
    /* the linux kernel has transparent hugepage support; */
    /* align on 2M page boundary for best chance of getting the large pages */
    if (posix_memalign((void **)&trans_tbl, 2097152,
                       ttentries*sizeof(ttentry)) != 0)
    {
        return FALSE;
    }
#ifdef MADV_HUGEPAGE
    /* just in case kernel thp mode is 'madvise' instead of 'always' */
    madvise(trans_tbl, ttentries*sizeof(ttentry), MADV_HUGEPAGE);
#endif
#endif

    /* mask's 2 lsb's are zero, to have 4 slots per bucket (1 cache line) */
    tt_mask = ttentries - 4;
    logf("created tt with %" PRIu64 " entries (2^%u), size=%" PRIu64 "MiB\n",
           ttentries, __builtin_ctzll(ttentries),
           ttentries*sizeof(ttentry)/1048576);
    /* force os to commit the memory now */
    for (i = 0; i < ttentries; i += 256)
    {
        trans_tbl[i].ttsig = 0;
    }
    hash_init = 0x0ecf2aaef2c937b6ULL;
    return TRUE;
}

/* release transposition table memory */
void free_tt(void)
{
#ifdef _DEBUG
    u64 i, nzentry;

    nzentry = 0;
    for (i = 0; i < tt_mask + 4; i++)
    {
        if (trans_tbl[i].ttsig != 0)
        {
            nzentry++;
        }
    }
    fprintf(stderr, "%" PRIu64 " / %" PRIu64 " non-zero tt entries\n",
            nzentry, tt_mask + 4);
#endif
#ifdef _WIN32
    if (large_pg)
    {
        VirtualFree(trans_tbl, 0, MEM_RELEASE);
    }
    else
    {
        _aligned_free(trans_tbl);
    }
#else
    free(trans_tbl);
#endif
}

/* probe transposition table for current board position */
/* bb -> current board */
/* ply = ply level */
/* depth = search depth */
/* alpha = alpha value */
/* beta = beta value */
/* out: scoreptr -> value of position */
/* out: bestptr -> best move, or NULL */
/* returns: TRUE if found in table */
bool probe_tt(bitboard *bb, int ply, int depth, s32 alpha, s32 beta, s32 *scoreptr, int *bestptr)
{
    ttentry *ttbucket;
    ttentry ttslot;
    u64 key;
    u64 a, b, c;
    s32 score;

    /* scramble board position into a hash */
    a = bb->white + hash_init;
    b = bb->black;
    c = bb->kings + 0x9e3779b97f4a7c13ULL; /* "golden ratio", arbitrary value */
    mix64(a, b, c);

    ttbucket = &trans_tbl[c & tt_mask];
    key = b ^ -bb->side;

    /* Hyatt-style lockless check of max 4 slots for our signature */
    /* 4 slots share 1 cache line, so after retrieving the first one */
    /* from main memory, the other 3 are also cached, and fast to access */

    ttslot = ttbucket[0];
    if (ttslot.ttsig != (key ^ ttslot.data))
    {
        ttslot = ttbucket[1];
        if (ttslot.ttsig != (key ^ ttslot.data))
        {
            ttslot = ttbucket[2];
            if (ttslot.ttsig != (key ^ ttslot.data))
            {
                ttslot = ttbucket[3];
                if (ttslot.ttsig != (key ^ ttslot.data))
                {
                    return FALSE;
                }
            }
        }
    }

    /* give caller the best move, */
    /* to be used for move ordering if depth is insufficient */
    /* (also used to reconstruct and print the pv) */
    if (bestptr != NULL)
    {
        *bestptr = ttslot.bestmove;
    }

    if (ttslot.depth >= depth)
    {
        score = ttslot.score;
        /* adjust dtw score for root node level */
        if (score > INFIN - MAXEXACT)
        {
            score -= ply;
        }
        else if (score < MAXEXACT - INFIN)
        {
            score += ply;
        }

        if (ttslot.betabound)
        {
            if (score >= beta)
            {
                /* beta-bound result found */
                *scoreptr = score;
                return TRUE;
            }
            if (score > alpha)
            {
                /* not a definite result, but we can improve alpha bound */
                *scoreptr = score;
            }
        }
        else if (ttslot.alphabound)
        {
            if (score <= alpha)
            {
                /* alpha-bound result found */
                *scoreptr = score;
                return TRUE;
            }
        }
        else
        {
            /* exact result found */
            *scoreptr = score;
            return TRUE;
        }
    }
    return FALSE;
}

/* store current board position in transposition table */
/* bb -> current board */
/* ply = ply level */
/* depth = search depth */
/* alpha = alpha value */
/* beta = beta value */
/* score = value of position */
/* bestmove -> best move found by search */
void store_tt(bitboard *bb, int ply, int depth, s32 alpha, s32 beta, s32 score, int bestmove)
{
    ttentry *ttbucket;
    ttentry ttslot;
    u64 key;
    u64 a, b, c;

    /* scramble board position into a hash */
    a = bb->white + hash_init;
    b = bb->black;
    c = bb->kings + 0x9e3779b97f4a7c13ULL; /* "golden ratio", arbitrary value */
    mix64(a, b, c);

    ttbucket = &trans_tbl[c & tt_mask];
    key = b ^ -bb->side;

    /* lockless check of signature to see if current position is stored here */
    ttslot = ttbucket[0];
    if (ttslot.ttsig != (key ^ ttslot.data))
    {
        ttslot = ttbucket[1];
        if (ttslot.ttsig != (key ^ ttslot.data))
        {
            ttslot = ttbucket[2];
            if (ttslot.ttsig != (key ^ ttslot.data))
            {
                ttslot = ttbucket[3];
                if (ttslot.ttsig != (key ^ ttslot.data))
                {
                    ttslot.bestmove = bestmove;
                    ttslot.depth = 0;
                }
                ttbucket[3] = ttbucket[2];    /* move slots to make room */
            }
            ttbucket[2] = ttbucket[1];
        }
        ttbucket[1] = ttbucket[0];
    }

    /* take care not to overwrite better info */
    if (depth > ttslot.depth ||
        (depth == ttslot.depth && (score > alpha || ttslot.alphabound)))
    {
        /* assemble data for new slot 0 */
        ttslot.depth = depth;
        ttslot.alphabound = (score <= alpha);
        ttslot.betabound = (score >= beta);
        /* if alpha bound, keep old slot's best move, since */
        /* the alpha fail-low's best move is near worthless */
        if (score > alpha)
        {
            ttslot.bestmove = bestmove;
        }
        /* adjust dtw score for root node level */
        if (score > INFIN - MAXEXACT)
        {
            score += ply;
        }
        else if (score < MAXEXACT - INFIN)
        {
            score -= ply;
        }
        ttslot.score = score;
        ttslot.ttsig = key ^ ttslot.data;
    }
    ttbucket[0] = ttslot;
}

/* recursive part of finding the PV continuation moves in */
/* the transposition table; completeness is not guaranteed, */
/* because table entries may have been overwritten. */
/* bb -> current board */
/* ply = ply level */
/* returns: nr. of chars written, excluding nul */
static int sprint_pvmoves(char *str, bitboard *bb, int ply)
{
    movelist list;
    int bestmove;
    s32 score;
    int m, len = 0;

    /* find next move, alpha- or beta-bound score is fine, too */
    /* (20 is an arbitrary limit, also preventing cycles */
    if (ply < 20 && probe_tt(bb, 0, 0, INFIN, -INFIN, &score, &bestmove))
    {
        /* generate all valid moves */
        gen_moves(bb, &list, NULL, TRUE);
        for (m = 0; m < list.count; m++)
        {
            if (move_square(&list.move[m], FROMTO) == bestmove)
            {
                len += sprint_move(&str[len], &list.move[m]);
                len += sprint_pvmoves(&str[len], &list.move[m], ply + 1); /* recurse */
                return len;
            }
        }
    }
    /* no bestmove found in transposition table or among valid moves */
    len += sprintf(&str[len], "\n");    /* terminate the move list */
    len += sprint_board(&str[len], bb); /* also print the resulting board diagram */
    return len;
}

/* like above, but in hub format, and no diagram */
/* bb -> current board */
/* ply = ply level */
/* returns: nr. of chars written, excluding nul */
static int sprint_pvmoves_hub(char *str, bitboard *bb, int ply)
{
    movelist list;
    int bestmove;
    s32 score;
    int m, len = 0;

    /* find next move, alpha- or beta-bound score is fine, too */
    /* (20 is an arbitrary limit, also preventing cycles */
    if (ply < 20 && probe_tt(bb, 0, 0, INFIN, -INFIN, &score, &bestmove))
    {
        /* generate all valid moves */
        gen_moves(bb, &list, NULL, TRUE);
        for (m = 0; m < list.count; m++)
        {
            if (move_square(&list.move[m], FROMTO) == bestmove)
            {
                len += sprint_move_hub(&str[len], &list.move[m]);
                len += sprint_pvmoves_hub(&str[len], &list.move[m], ply + 1); /* recurse */
                return len;
            }
        }
    }
    /* no bestmove found in transposition table or among valid moves */
    return len;
}

/* print the principal variation to string */
/* the ply0 move has been made, find the rest in the tt */
/* str -> destination string, must be at least 356 chars */
/* ply0mvptr -> the root move to start from */
/* returns: nr. of chars written, excluding nul */
int sprint_pv(char *str, bitboard *ply0mvptr)
{
    int len;

    len = sprint_move(str, ply0mvptr);
    len += sprint_pvmoves(&str[len], ply0mvptr, 1);
    return len;
}

/* print the principal variation to string in hub format */
/* the ply0 move has been made, find the rest in the tt */
/* str -> destination string, must be at least 356 chars */
/* ply0mvptr -> the root move to start from */
/* returns: nr. of chars written, excluding nul */
int sprint_pv_hub(char *str, bitboard *ply0mvptr)
{
    int len;

    len = sprint_move_hub(str, ply0mvptr);
    len += sprint_pvmoves_hub(&str[len], ply0mvptr, 1);
    str[--len] = '\0';    /* remove final space */
    return len;
}
