
// trans.cpp

// includes

#include "hash.h"
#include "move.h"
#include "option.h"
#include "protocol.h"
#include "trans.h"
#include "util.h"
#include "value.h"

// macros

#define MIN(a,b) ((a)<=(b)?(a):(b))
#define MAX(a,b) ((a)>=(b)?(a):(b))

// constants

static const bool UseModulo = false;

static const int DateSize = 16;

static const int ClusterSize = 4; // TODO: unsigned?

static const int DepthNone = -128;

// types

struct entry_t {
    uint32 lock;
    uint16 move;
    sint8 depth;
    uint8 date;
    sint8 move_depth;
    uint8 flags;
    sint8 min_depth;
    sint8 max_depth;
    sint16 min_value;
    sint16 max_value;
};

struct trans { // HACK: typedef'ed in trans.h
    entry_t * table;
    uint32 size;
    uint32 mask;
    int date;
    int age[DateSize];
    uint32 used;
    sint64 read_nb;
    sint64 read_hit;
    sint64 write_nb;
    sint64 write_hit;
    sint64 write_collision;
};

// variables

trans_t Trans[1];

// prototypes

static void      trans_set_date (trans_t * trans, int date);
static int       trans_age      (const trans_t * trans, int date);

static entry_t * trans_entry    (trans_t * trans, uint64 key);

static bool      entry_is_ok    (const entry_t * entry);

// functions

// trans_is_ok()

bool trans_is_ok(const trans_t * trans) {

    int date;

    if (trans == NULL) return false;

    if (trans->table == NULL) return false;
    if (trans->size == 0) return false;
    if (trans->mask == 0 || trans->mask >= trans->size) return false;
    if (trans->date >= DateSize) return false;

    for (date = 0; date < DateSize; date++) {
        if (trans->age[date] != trans_age(trans,date)) return false;
    }

    return true;
}

// trans_init()

void trans_init(trans_t * trans) {

    ASSERT(trans!=NULL);

    ASSERT(sizeof(entry_t)==16);

    trans->size = 0;
    trans->mask = 0;
    trans->table = NULL;

    trans_set_date(trans,0);

    trans_clear(trans);

    // ASSERT(trans_is_ok(trans));
}

// trans_alloc()

void trans_alloc(trans_t * trans) {

    uint32 size, target;

    ASSERT(trans!=NULL);

    // calculate size

    target = option_get_int("Hash");
    if (target < 4) target = 16;
    target *= 1024 * 1024;

    for (size = 1; size != 0 && size <= target; size *= 2)
        ;

    size /= 2;
    ASSERT(size>0&&size<=target);

    // allocate table

    size /= sizeof(entry_t);
    ASSERT(size!=0&&(size&(size-1))==0); // power of 2

    trans->size = size + (ClusterSize - 1); // HACK to avoid testing for end of table
    trans->mask = size - 1;

    trans->table = (entry_t *) my_malloc(trans->size*sizeof(entry_t));

    trans_clear(trans);

    ASSERT(trans_is_ok(trans));
}

// trans_free()

void trans_free(trans_t * trans) {

    ASSERT(trans_is_ok(trans));

    my_free(trans->table);

    trans->table = NULL;
    trans->size = 0;
    trans->mask = 0;
}

// trans_clear()

void trans_clear(trans_t * trans) {

    entry_t clear_entry[1];
    entry_t * entry;
    uint32 index;

    ASSERT(trans!=NULL);

    trans_set_date(trans,0);

    clear_entry->lock = 0;
    clear_entry->move = MoveNone;
    clear_entry->depth = DepthNone;
    clear_entry->date = trans->date;
    clear_entry->move_depth = DepthNone;
    clear_entry->flags = 0;
    clear_entry->min_depth = DepthNone;
    clear_entry->max_depth = DepthNone;
    clear_entry->min_value = -ValueInf;
    clear_entry->max_value = +ValueInf;

    ASSERT(entry_is_ok(clear_entry));

    entry = trans->table;

    for (index = 0; index < trans->size; index++) {
        *entry++ = *clear_entry;
    }
}

// trans_inc_date()

void trans_inc_date(trans_t * trans) {

    ASSERT(trans!=NULL);

    trans_set_date(trans,(trans->date+1)%DateSize);
}

// trans_set_date()

static void trans_set_date(trans_t * trans, int date) {

    ASSERT(trans!=NULL);
    ASSERT(date>=0&&date<DateSize);

    trans->date = date;

    for (date = 0; date < DateSize; date++) {
        trans->age[date] = trans_age(trans,date);
    }

    trans->used = 0;
    trans->read_nb = 0;
    trans->read_hit = 0;
    trans->write_nb = 0;
    trans->write_hit = 0;
    trans->write_collision = 0;
}

// trans_age()

static int trans_age(const trans_t * trans, int date) {

    int age;

    ASSERT(trans!=NULL);
    ASSERT(date>=0&&date<DateSize);

    age = trans->date - date;
    if (age < 0) age += DateSize;

    ASSERT(age>=0&&age<DateSize);

    return age;
}

// trans_store()

void trans_store(trans_t * trans, uint64 key, int move, int depth, int min_value, int max_value) {

    entry_t * entry, * best_entry;
    int score, best_score;
    int i;

    ASSERT(trans_is_ok(trans));
    ASSERT(move>=0&&move<65536);
    ASSERT(depth>=-127&&depth<=+127);
    ASSERT(min_value>=-ValueInf&&min_value<=+ValueInf);
    ASSERT(max_value>=-ValueInf&&max_value<=+ValueInf);
    ASSERT(min_value<=max_value);

    // init

    trans->write_nb++;

    // probe

    best_entry = NULL;
    best_score = -32767;

    entry = trans_entry(trans,key);

    for (i = 0; i < ClusterSize; i++, entry++) {

        if (entry->lock == KEY_LOCK(key)) {

            // hash hit => update existing entry

            trans->write_hit++;
            if (entry->date != trans->date) trans->used++;

            entry->date = trans->date;

            if (trans_endgame || depth > entry->depth) entry->depth = depth;
            /* if (depth > entry->depth)  entry->depth = depth; // for replacement scheme */

            // if (move != MoveNone /* && depth >= entry->move_depth */) {
            if (move != MoveNone && (trans_endgame || depth >= entry->move_depth)) {
                entry->move_depth = depth;
                entry->move = move;
            }

            // if (min_value > -ValueInf /* && depth >= entry->min_depth */) {
            if (min_value > -ValueInf && (trans_endgame || depth >= entry->min_depth)) {
                entry->min_depth = depth;
                entry->min_value = min_value;
            }

            // if (max_value < +ValueInf /* && depth >= entry->max_depth */) {
            if (max_value < +ValueInf && (trans_endgame || depth >= entry->max_depth)) {
                entry->max_depth = depth;
                entry->max_value = max_value;
            }

            ASSERT(entry_is_ok(entry));

            return;
        }

        // evaluate replacement score

        score = trans->age[entry->date] * 256 - entry->depth;
        ASSERT(score>-32767);

        if (score > best_score) {
            best_entry = entry;
            best_score = score;
        }
    }

    // "best" entry found

    entry = best_entry;
    ASSERT(entry!=NULL);
    ASSERT(entry->lock!=KEY_LOCK(key));

    if (entry->date == trans->date) {
        trans->write_collision++;
    } else {
        trans->used++;
    }

    // store

    ASSERT(entry!=NULL);

    entry->lock = KEY_LOCK(key);
    entry->date = trans->date;

    entry->depth = depth;

    entry->move_depth = (move != MoveNone) ? depth : DepthNone;
    entry->move = move;

    entry->min_depth = (min_value > -ValueInf) ? depth : DepthNone;
    entry->max_depth = (max_value < +ValueInf) ? depth : DepthNone;
    entry->min_value = min_value;
    entry->max_value = max_value;

    ASSERT(entry_is_ok(entry));
}

// trans_retrieve()

bool trans_retrieve(trans_t * trans, uint64 key, int * move, int * min_depth, int * max_depth, int * min_value, int * max_value) {

    entry_t * entry;
    int i;

    ASSERT(trans_is_ok(trans));
    ASSERT(move!=NULL);
    ASSERT(min_depth!=NULL);
    ASSERT(max_depth!=NULL);
    ASSERT(min_value!=NULL);
    ASSERT(max_value!=NULL);

    // init

    trans->read_nb++;

    // probe

    entry = trans_entry(trans,key);

    for (i = 0; i < ClusterSize; i++, entry++) {

        if (entry->lock == KEY_LOCK(key)) {

            // found

            trans->read_hit++;
            if (entry->date != trans->date) entry->date = trans->date;

            *move = entry->move;

            *min_depth = entry->min_depth;
            *max_depth = entry->max_depth;
            *min_value = entry->min_value;
            *max_value = entry->max_value;

            return true;
        }
    }

    // not found

    return false;
}

// trans_stats()

void trans_stats(const trans_t * trans) {

    double full;
    // double hit, collision;

    ASSERT(trans_is_ok(trans));

    full = double(trans->used) / double(trans->size);
    // hit = double(trans->read_hit) / double(trans->read_nb);
    // collision = double(trans->write_collision) / double(trans->write_nb);

    send("info hashfull %.0f",full*1000.0);
}

// trans_entry()

static entry_t * trans_entry(trans_t * trans, uint64 key) {

    uint32 index;

    ASSERT(trans_is_ok(trans));

    if (UseModulo) {
        index = KEY_INDEX(key) % (trans->mask + 1);
    } else {
        index = KEY_INDEX(key) & trans->mask;
    }

    ASSERT(index<=trans->mask);

    return &trans->table[index];
}

// entry_is_ok()

static bool entry_is_ok(const entry_t * entry) {

    if (entry == NULL) return false;

    if (entry->date >= DateSize) return false;

    if (entry->move == MoveNone && entry->move_depth != DepthNone) return false;
    if (entry->move != MoveNone && entry->move_depth == DepthNone) return false;

    if (entry->min_value == -ValueInf && entry->min_depth != DepthNone) return false;
    if (entry->min_value >  -ValueInf && entry->min_depth == DepthNone) return false;

    if (entry->max_value == +ValueInf && entry->max_depth != DepthNone) return false;
    if (entry->max_value <  +ValueInf && entry->max_depth == DepthNone) return false;

    return true;
}

// end of trans.cpp

