/* this contains all the code the the hash tables (transposition tables) 

   The transposition table has 2 levels. The first level is replaced if the new entry 
   has a higher priority than the old entry. The 2nd level is a "always replace" level
   where entries are placed if they are of lower priority than the first level.
 */
#include "includes.h"
#include "knightcap.h"

int hash_hits, hash_misses, hash_shallow;
static int bad_updates, good_updates;
static unsigned hash_tag=0;
extern int mulling;

extern struct state *state;

#if APLINUX
static unsigned num_cells;
static unsigned cell;
#endif

#define PAR_HASH_LEVEL -1

struct hash_entry *hash_table;
unsigned hash_table_size;

static int initialised;

unsigned hts() 
{
	return hash_table_size;
}

void hash_reset_stats(void)
{
	hash_misses = hash_hits = hash_shallow = 0;
	bad_updates = good_updates = 0;
}

void hash_reset(void)
{
	if (!initialised) return;

	if (!hash_table) {
		init_hash_table();
		return;
	}

	memset(hash_table, 0, 
	       sizeof(hash_table[0])*hash_table_size);
	lprintf(0,"reset hash table\n");
	if (state->move_time > 1)
		brain_fill_hash(NULL);
}


void init_hash_table(void)
{
	int size;

	if (initialised) return;
	initialised = 1;

	hash_reset_stats();

	do {
		hash_table_size = (state->hash_table_size * 1024*1024) / 
			sizeof(hash_table[0]);

#if HASH_LEVELS
		hash_table_size &= ~(HASH_LEVELS - 1);
#endif

		size = hash_table_size*sizeof(hash_table[0]);

		hash_table = (struct hash_entry *)malloc(size);

		if (!hash_table) {
			state->hash_table_size--;
		}
	} while (!hash_table);

	printf("hash table size %d MB  %d entries\n", 
	       state->hash_table_size, hash_table_size);

	if (!mulling) {
		hash_reset();
		order_reset();
	}
#if APLINUX
	num_cells = getncel();
	cell = getcid();
#endif
}

static inline unsigned get_index(Position *b)
{
	unsigned ret;
	ret = b->hash1 % hash_table_size;
#if HASH_LEVELS
	ret &= ~(HASH_LEVELS - 1);
#endif	
	return ret;
}

int check_hash(Position *b, 
	       int depth, Eval testv, Eval *v, Move *move)
{
	struct hash_entry *t;
	uint32 hashindex = get_index(b);

	t = &hash_table[hashindex];

#if APLINUX
	if (depth > PAR_HASH_LEVEL) {
		int get_flag = 0;
		int cid = (b->hash1 >> HASH_TABLE_BITS) % num_cells;
		get(cid, &b->h_entry, sizeof(*t), t, &get_flag, NULL);
		amcheck(&get_flag, 1);
	} else {
		b->h_entry = (*t);
	}
	t = &b->h_entry;
#endif
	
#if HASH_LEVELS
	{
		int j;
		for (j=0;j<HASH_LEVELS;j++, t++)
			if (t->hash2 == b->hash2 && 
			    t->hash1 == b->hash1) break;
		if (j == HASH_LEVELS) {
			if (depth)
				hash_misses++;
			return HASH_MISS;
		}
	}
#else
	if (t->hash2 != b->hash2 || 
	    t->hash1 != b->hash1) {
		if (depth)
			hash_misses++;
		return HASH_MISS;
	}
#endif

	if (move) {
		/* even if we get a hash miss we return the move
		   if we have one - it might be a good guess */
		move->from = t->from;
		move->to = t->to;
	}

	if (t->depth_high >= depth && t->high.v < testv.v) {
		if (depth)
			hash_hits++;
		(*v) = t->high;
		return HASH_HIT;
	}

	if (t->depth_low >= depth && t->low.v >= testv.v) {
		if (depth)
			hash_hits++;
		(*v) = t->low;
		return HASH_HIT;
	}
	if (depth)
		hash_shallow++;
	return HASH_MISS;
}


struct hash_entry *fetch_hash(Position *b)
{
	struct hash_entry *t;
	uint32 hashindex;

	init_hash_table();

	hashindex = get_index(b);
	t = &hash_table[hashindex];

#if HASH_LEVELS
	{
		int j;
		for (j=0;j<HASH_LEVELS;j++, t++)
			if (t->hash2 == b->hash2 && 
			    t->hash1 == b->hash1) break;
		if (j == HASH_LEVELS) {
			return NULL;
		}
	}
#else
	if (t->hash2 != b->hash2 || 
	    t->hash1 != b->hash1) {
		return 0;
	}
#endif

	return t;
}

static inline int maxdepth(struct hash_entry *t)
{
	return imax(t->depth_low, t->depth_high);
}

void insert_hash(Position *b, int depth, Eval testv, Eval evaluation, Move *move)
{
	int depth0;
	struct hash_entry *t;
	uint32 hashindex = get_index(b);
	int lower = (evaluation.v >= testv.v); /* is this a new lower bound? */
#if APLINUX
	struct hash_entry *t1;
	int cid;
#endif
	
	t = &hash_table[hashindex];

#if APLINUX
	t1 = t;

	t = &b->h_entry;
#endif

	if  (t[0].move_num || t[1].move_num) {
		if (t[0].hash1 != b->hash1)
			return;
		else {
			lprintf(0, "overwriting hash entry: %d %d %d/%d depth=%d/%d %08x by: %08x depth=%d\n",
				t[0].move_num, t[1].move_num, t[0].low.v, t[0].high.v, 
				t[0].depth_low, t[0].depth_high, t[0].hash1, b->hash1, depth);
		}
	}

	/* see if it matches either entry */
	if (t[0].hash1 == b->hash1 && t[0].hash2 == b->hash2) {
		/* we match the deep entry, don't need to do anything */
	} else if (t[1].hash1 == b->hash1 && t[1].hash2 == b->hash2) {
		/* we match the "always" entry. This might refresh the 
		   hash tag on the always entry, so check if the always
		   and deep entries need swapping */
		if (maxdepth(&t[1]) >= maxdepth(&t[0])) {
			struct hash_entry tmp;
			tmp = t[0];
			t[0] = t[1];
			t[1] = tmp;
		} else {
			/* they don't need swapping, just use the
                           "always" entry */
			t++;
		}
	} else if (t[0].tag == hash_tag && maxdepth(&t[0]) > depth) {
		/* the deep entry is deeper than the new entry. Use
		   the always entry unless this is a quiesce entry
		   and the always entry isn't */
		if (depth == 0 && maxdepth(&t[1]) > 0 && t[1].tag == hash_tag)
			return;
		/* put it in the "always replace" slot */
		t++;
	} else {
		/* replace the deep entry, and move the deep entry to the 
		 "always" slot */
		t[1] = t[0];
	}

	t->tag = hash_tag;

	if (t->hash2 != b->hash2 || t->hash1 != b->hash1) {
		t->depth_low = 0;
		t->depth_high = 0;
		t->low = makeeval(b, -INFINITY);
		t->high = makeeval(b, INFINITY);
		t->hash1 = b->hash1;
		t->hash2 = b->hash2;
		t->from = t->to = A1;
	} else {
#if SAVE_EXTENSIONS
		if (depth > 2 && depth >= (lower?t->depth_low+1:t->depth_high+1)) {
			ddprintf(0, "%s %d %d %d %d %d %d %d\n", 		
				position_to_ppn(b),
				t->depth_low, t->depth_high,
				t->low.v, t->high.v, 
				lower?evaluation.v:t->low.v,
				lower?t->high.v:evaluation.v,
				depth);
		}
#endif
		if (depth < (lower?t->depth_low:t->depth_high))
			bad_updates++;
		else if ((lower?t->depth_low:t->depth_high) > 0)
			good_updates++;

	}

	if (lower) {
		if (move) {
			t->from = move->from;
			t->to = move->to;
		}
		depth0 = t->depth_low;
		t->depth_low = depth;
		t->low = evaluation;
		if (t->high.v < t->low.v) {
			if (depth0 == depth && t->depth_high == depth) {
				t->high = t->low;
			} else {
				t->high = makeeval(b, INFINITY);
				t->depth_high = 0;
			}
		}
	} else {
		depth0 = t->depth_high;
		t->depth_high = depth;
		t->high = evaluation;
		if (t->high.v < t->low.v) {
			if (depth0 == depth && t->depth_low == depth) {
				t->low = t->high;
			} else {
				t->low = makeeval(b, -INFINITY);
				t->depth_low = 0;
			}
		}
	}

#if APLINUX
	if (depth > PAR_HASH_LEVEL) {
		cid = (b->hash1 >> HASH_TABLE_BITS) % num_cells;
		put(cid, t, sizeof(*t), t1, NULL, NULL, 0);
	} else {
		(*t1) = (*t);
	}
#endif
}

void hash_change_tag(int move_num)
{
	static int last_move_num;
	if (move_num < last_move_num) {
		hash_reset();
	}

	last_move_num = move_num;

	hash_tag = (hash_tag % 15) + 1;
}

char *hashstats(void)
{
	static char ret[30];
	sprintf(ret, "h/s/b=%d/%d/%d%%",
		(100*hash_hits)/(hash_misses+hash_hits+hash_shallow+1),
		(100*hash_shallow)/(hash_misses+hash_hits+hash_shallow+1),
		(100*bad_updates)/(good_updates+bad_updates+1));
	return ret;
}



int check_hash2(Position *b, int depth, Eval testv, Eval *v)
{
	struct hash_entry *t;
	uint32 hashindex = get_index(b);

	t = &hash_table[hashindex];

#if HASH_LEVELS
	{
		int j;
		for (j=0;j<HASH_LEVELS;j++, t++)
			if (t->hash2 == b->hash2 && 
			    t->hash1 == b->hash1) break;
		if (j == HASH_LEVELS) {
			return 0;
		}
	}
#else
	if (t->hash2 != b->hash2 || 
	    t->hash1 != b->hash1) {
		return 0;
	}
#endif

	if (t->depth_high >= depth && t->high.v < testv.v) {
		if (depth)
			hash_hits++;
		(*v) = t->high;
		return 1;
	}
	
	if (depth)
		hash_shallow++;
	return 0;
}

int ettc_check_hash(Position *b, Move *moves, int num_moves,
		    int depth, Eval testv, Eval *v, Move *m1)
{
	int m;
	uint32 hash1, hash2;
	Eval v1;
	int cutoff = 0;

	hash1 = b->hash1;
	hash2 = b->hash2;

	testv = flip(testv);

	depth--;

	for (m=0;m<num_moves;m++) {
		remove_hash(b, moves[m].from, b->board[moves[m].from]);
		if (b->board[moves[m].to]) {
			remove_hash(b, moves[m].to, b->board[moves[m].to]);
		}
		add_hash(b, moves[m].to, b->board[moves[m].from]);
		b->hash1 ^= 1;
		
		if (check_hash2(b, depth, testv, &v1)) {
			/* now confirm it */
			Position b1;

			b->hash1 = hash1;
			b->hash2 = hash2;

			if (!do_move(&b1, b, &moves[m])) continue;
			if (check_repitition(&b1, 1)) continue;

			if (check_hash2(&b1, depth, testv, &v1)) {
				if (!cutoff || (-v1.v) > v->v) { 
					cutoff = 1;
					(*v) = v1;
					v->v = -v->v;
					if (m1)
						(*m1) = moves[m];
				}
			}
		} else {
			b->hash1 = hash1;
			b->hash2 = hash2;
		}
	}

	return cutoff;
}


/* return >0 if this move could produce a hash hit, <0 if it can't
   and =0 if we can't tell */
int hash_ordering(Position *b, Move *move, Eval testv)
{
	uint32 hash1, hash2, hashindex;
	struct hash_entry *t;

	hash1 = b->hash1;
	hash2 = b->hash2;

	testv = flip(testv);

	remove_hash(b, move->from, b->board[move->from]);
	if (b->board[move->to]) {
		remove_hash(b, move->to, b->board[move->to]);
	}
	add_hash(b, move->to, b->board[move->from]);
	b->hash1 ^= 1;


	hashindex = get_index(b);
	t = &hash_table[hashindex];

#if HASH_LEVELS
	{
		int j;
		for (j=0;j<HASH_LEVELS;j++, t++)
			if (t->hash2 == b->hash2 && 
			    t->hash1 == b->hash1) break;
		if (j == HASH_LEVELS) {
			b->hash1 = hash1;
			b->hash2 = hash2;
			return 0;
		}
	}
#else
	if (t->hash2 != b->hash2 || 
	    t->hash1 != b->hash1) {
		b->hash1 = hash1;
		b->hash2 = hash2;
		return 0;
	}
#endif

	b->hash1 = hash1;
	b->hash2 = hash2;

	if (t->low.v >= testv.v) {
		return -(1+((t->low.v - testv.v) / (STATIC_PAWN_VALUE/2)));
	}

	if (t->high.v < testv.v) {
		return 1+((testv.v - t->high.v) / (STATIC_PAWN_VALUE/2));
	}

	return 0;
}