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     {
  55         __builtin_prefetch( &hash_table[ (i + 30) & HMASK] );
  56         hash_table[i].is_old = 1;
  57     }
  58 }
  59
  60 /* is this useful? */
  61 void
  62 Engine::prefetch_hash(const HashKey& hk)
  63 {
  64     __builtin_prefetch( &hash_table[ (hk.index) & HMASK] );
  65     __builtin_prefetch( &hash_table[ (hk.index+REHASH-1) & HMASK] );
  66 }
  67
  68 HashEntry*
  69 Engine::probe_hash(const HashKey& hk)
  70 {
  71     for(int i=0;i<REHASH;i++)
  72     {
  73         HashEntry* h = &hash_table[(hk.index + i) & HMASK];
  74         if(!h->check)
  75             return NULL;
  76         if(h->check == hk.check)
  77         {
  78             h->is_old = 0;
  79             return h;
  80         }
  81     }
  82     return NULL;
  83 }
  84
  85 void
  86 Engine::write_hash(const HashKey& hk, int16_t lo, int16_t up, int depth, int best_cont, bool no_good_moves)
  87 {
  88     HashEntry* h = 0;
  89
  90     /* look for an empty entry or the same entry to update */
  91     for(int i=0;i<REHASH;i++)
  92     {
  93         HashEntry* tmp = &hash_table[(hk.index + i) & HMASK];
  94         if(!tmp->check || tmp->check == hk.check)
  95         {
  96             h = tmp;
  97             break;
  98         }
  99     }
 100
 101     if(!h) /* look for an entry searched at lower depth */
 102     {
 103         int d = INF;
 104         int lowest = -1;
 105         for(int i=0;i<REHASH;i++)
 106         {
 107             HashEntry* tmp = &hash_table[(hk.index + i) & HMASK];
 108             if(tmp->depth < d)
 109             {
 110                 lowest = i;
 111                 d = tmp->depth;
 112             }
 113         }
 114
 115         if(d < depth)
 116             h = &hash_table[(hk.index + lowest) & HMASK];
 117     }
 118
 119     if(!h) /* look for an old entry and take the one searched at lowest depth */
 120     {
 121         int d = INF;
 122         int lowest = -1;
 123         for(int i=0;i<REHASH;i++)
 124         {
 125             HashEntry* tmp = &hash_table[(hk.index + i) & HMASK];
 126             if(tmp->depth < d && tmp->is_old == 1)
 127             {
 128                 lowest = i;
 129                 d = tmp->depth;
 130             }
 131         }
 132
 133         if(d != INF)
 134             h = &hash_table[(hk.index + lowest) & HMASK];
 135     }
 136
 137     if(!h)
 138         return;
 139 #if 0
 140     if(h->check == hk.check && h->depth>depth)
 141         return;
 142
 143     if(h->check == hk.check && h->depth==depth)
 144     {
 145         /* same entry, improve bounds */
 146         h->up = MIN(h->up, up);
 147         h->lo = MAX(h->lo, lo);
 148     }
 149     else
 150     {
 151         /* replace bounds */
 152         h->up = up;
 153         h->lo = lo;
 154     }
 155 #endif
 156
 157     h->up = up;
 158     h->lo = lo;
 159
 160     h->check = hk.check;
 161     h->depth = depth;
 162     h->best_mv = best_cont;
 163     h->no_good_moves = no_good_moves;
 164     h->is_old = 0;
 165 }