hash.cpp

   1 /***************************************************************************
   2                    hash.cpp  -  Hash related implementations
   3                              -------------------
   4     begin                : Mon Sep 19 2005
   5     copyright            : (C) 2005 by Maurizio Monge
   6     email                : monge@linuz.sns.it
   7  ***************************************************************************/
   8
   9 /***************************************************************************
  10  *                                                                         *
  11  *   This program is free software; you can redistribute it and/or modify  *
  12  *   it under the terms of the GNU General Public License as published by  *
  13  *   the Free Software Foundation; either version 2 of the License, or     *
  14  *   (at your option) any later version.                                   *
  15  *                                                                         *
  16  ***************************************************************************/
  17
  18 #include "engine.h"
  19 #include <string.h>
  20
  21 #define HSIZE (1<<22)
  22 #define HMASK (HSIZE-1)
  23 #define REHASH 3
  24
  25 void
  26 HashKey::print() const
  27 {
  28     printf("HashKey( 0x%llxLL, 0x%x )\n", (long long)check, index);
  29 }
  30
  31 char* HashKey::to_string(char* buf) const
  32 {
  33     snprintf(buf, 64, "%08x%08x%08x",
  34                       check_hi, check_lo, index);
  35     return buf;
  36 }
  37
  38 void
  39 Engine::create_hash()
  40 {
  41     hash_table = new HashEntry[HSIZE];
  42 }
  43
  44 void
  45 Engine::reset_hash()
  46 {
  47     memset(hash_table, 0, sizeof(HashEntry)*HSIZE);
  48 }
  49
  50 void
  51 Engine::make_old_hash()
  52 {
  53     for(int i=0;i<HSIZE;i++)
  54         hash_table[i].is_old = 1;
  55 }
  56
  57 /* is this useful? */
  58 void
  59 Engine::prefetch_hash(const HashKey& hk)
  60 {
  61     __builtin_prefetch( &hash_table[ (hk.index) & HMASK] );
  62     __builtin_prefetch( &hash_table[ (hk.index+REHASH-1) & HMASK] );
  63 }
  64
  65 HashEntry*
  66 Engine::probe_hash(const HashKey& hk)
  67 {
  68     for(int i=0;i<REHASH;i++)
  69     {
  70         HashEntry* h = &hash_table[(hk.index + i) & HMASK];
  71         if(!h->check)
  72             return NULL;
  73         if(h->check == hk.check)
  74         {
  75             h->is_old = 0;
  76             return h;
  77         }
  78     }
  79     return NULL;
  80 }
  81
  82 void
  83 Engine::write_hash(const HashKey& hk, int16_t lo, int16_t up, int depth, int best_cont, bool no_good_moves)
  84 {
  85     HashEntry* h = 0;
  86
  87     /* look for an empty entry or the same entry to update */
  88     for(int i=0;i<REHASH;i++)
  89     {
  90         HashEntry* tmp = &hash_table[(hk.index + i) & HMASK];
  91         if(!tmp->check || tmp->check == hk.check)
  92         {
  93             h = tmp;
  94             break;
  95         }
  96     }
  97
  98     if(!h) /* look for an entry searched at lower depth */
  99     {
 100         int d = INF;
 101         int lowest = -1;
 102         for(int i=0;i<REHASH;i++)
 103         {
 104             HashEntry* tmp = &hash_table[(hk.index + i) & HMASK];
 105             if(tmp->depth < d)
 106             {
 107                 lowest = i;
 108                 d = tmp->depth;
 109             }
 110         }
 111
 112         if(d < depth)
 113             h = &hash_table[(hk.index + lowest) & HMASK];
 114     }
 115
 116     if(!h) /* look for an old entry and take the one searched at lowest depth */
 117     {
 118         int d = INF;
 119         int lowest = -1;
 120         for(int i=0;i<REHASH;i++)
 121         {
 122             HashEntry* tmp = &hash_table[(hk.index + i) & HMASK];
 123             if(tmp->depth < d && tmp->is_old == 1)
 124             {
 125                 lowest = i;
 126                 d = tmp->depth;
 127             }
 128         }
 129
 130         if(d != INF)
 131             h = &hash_table[(hk.index + lowest) & HMASK];
 132     }
 133
 134     if(!h)
 135         return;
 136 #if 0
 137     if(h->check == hk.check && h->depth>depth)
 138         return;
 139
 140     if(h->check == hk.check && h->depth==depth)
 141     {
 142         /* same entry, improve bounds */
 143         h->up = MIN(h->up, up);
 144         h->lo = MAX(h->lo, lo);
 145     }
 146     else
 147     {
 148         /* replace bounds */
 149         h->up = up;
 150         h->lo = lo;
 151     }
 152 #endif
 153
 154     h->up = up;
 155     h->lo = lo;
 156
 157     h->check = hk.check;
 158     h->depth = depth;
 159     h->best_mv = best_cont;
 160     h->no_good_moves = no_good_moves;
 161     h->is_old = 0;
 162 }