git.sesse.net Git - pgn-extract/blob - hashing.c

   1 /*
   2  *  Program: pgn-extract: a Portable Game Notation (PGN) extractor.
   3  *  Copyright (C) 1994-2014 David Barnes
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License as published by
   6  *  the Free Software Foundation; either version 1, or (at your option)
   7  *  any later version.
   8  *
   9  *  This program is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  *  GNU General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU General Public License
  15  *  along with this program; if not, write to the Free Software
  16  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  *
  18  *  David Barnes may be contacted as D.J.Barnes@kent.ac.uk
  19  *  http://www.cs.kent.ac.uk/people/staff/djb/
  20  *
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <ctype.h>
  27 #if defined(__BORLANDC__) || defined(_MSC_VER)
  28 /* For unlink() */
  29 #include <io.h>
  30 #else
  31 /* For unlink() */
  32 #include <unistd.h>
  33 #endif
  34 #include "bool.h"
  35 #include "mymalloc.h"
  36 #include "defs.h"
  37 #include "typedef.h"
  38 #include "tokens.h"
  39 #include "taglist.h"
  40 #include "lex.h"
  41 #include "hashing.h"
  42
  43                 /* Routines, similar in nature to those in apply.c
  44                  * to implement a duplicate hash-table lookup using
  45                  * an external file, rather than malloc'd memory.
  46                  * The only limit should be a file system limit.
  47                  *
  48                  * This version should be slightly more accurate than
  49                  * the alternative because the final_ and cumulative_
  50                  * hash values are both stored, rather than the XOR
  51                  * of them.
  52                  */
  53
  54 /* The name of the file used.
  55  * This is overwritten each time, and removed on normal
  56  * program exit.
  57  */
  58 static char VIRTUAL_FILE[] = "virtual.tmp";
  59
  60 /* Define the size of the hash table.
  61  * Size was 8191 but that seems unduly conservative these days.
  62  */
  63 #define LOG_TABLE_SIZE 100003
  64 /* Define a table to hold hash values of the extracted games.
  65  * This is used to enable duplicate detection.
  66  */
  67 typedef struct{
  68     /* Record the file offset of the first and last entries
  69      * for an index. (head == -1) => empty.
  70      */
  71   long head, tail;
  72 } LogHeaderEntry;
  73
  74 /* If use_virtual_hash_table */
  75 static LogHeaderEntry *VirtualLogTable = NULL;
  76
  77 /* Define a table to hold hash values of the extracted games.
  78  * This is used to enable duplicate detection when not using
  79  * the virtual hash table.
  80  */
  81 static HashLog **LogTable = NULL;
  82
  83         /* Define a type to hold hash values of interest.
  84          * This is used both to aid in duplicate detection
  85          * and in finding positional variations.
  86          */
  87 typedef struct VirtualHashLog {
  88     /* Store the final position hash value and
  89      * the cumulative hash value for a game.
  90      */
  91     HashCode final_hash_value, cumulative_hash_value;
  92     /* Record the file list index for the file this game was first found in. */
  93     int file_number;
  94     /* Record the file offset of the next element
  95      * in this list. -1 => end-of-list.
  96      */
  97     long next;
  98 } VirtualHashLog;
  99
 100 static FILE *hash_file = NULL;
 101
 102 static const char *previous_virtual_occurance(Game game_details);
 103
 104         /* Determine which table to initialise, depending
 105          * on whether use_virtual_hash_table is set or not.
 106          */
 107 void
 108 init_duplicate_hash_table(void)
 109 {  int i;
 110
 111    if(GlobalState.use_virtual_hash_table){
 112        VirtualLogTable = (LogHeaderEntry *)
 113             MallocOrDie(LOG_TABLE_SIZE*sizeof(*VirtualLogTable));
 114        for(i = 0; i < LOG_TABLE_SIZE; i++){
 115            VirtualLogTable[i].head = VirtualLogTable[i].tail = -1;
 116        }
 117        hash_file = fopen(VIRTUAL_FILE,"w+b");
 118        if(hash_file == NULL){
 119            fprintf(GlobalState.logfile,"Unable to open %s\n",
 120                     VIRTUAL_FILE);
 121        }
 122     }
 123     else{
 124        LogTable = (HashLog**) MallocOrDie(LOG_TABLE_SIZE*sizeof(*LogTable));
 125        for(i = 0; i < LOG_TABLE_SIZE; i++){
 126            LogTable[i] = NULL;
 127        }
 128     }
 129 }
 130
 131         /* Close and remove the temporary file if in use. */
 132 void
 133 clear_duplicate_hash_table(void)
 134 {
 135    if(GlobalState.use_virtual_hash_table){
 136       if(hash_file != NULL){
 137         (void) fclose(hash_file);
 138         unlink(VIRTUAL_FILE);
 139         hash_file = NULL;
 140       }
 141    }
 142 }
 143
 144         /* Retrieve a duplicate table entry from the hash file. */
 145 static int
 146 retrieve_virtual_entry(long ix,VirtualHashLog *entry)
 147 {
 148     if(hash_file == NULL){
 149         return 0;
 150     }
 151     else if(fseek(hash_file,ix,SEEK_SET) != 0){
 152         fprintf(GlobalState.logfile,
 153                         "Fseek error to %ld in retrieve_virtual_entry\n",ix);
 154         return 0;
 155     }
 156     else if(fread((void *)entry,sizeof(*entry),1,hash_file) != 1){
 157         fprintf(GlobalState.logfile,
 158                         "Fread error from %ld in retrieve_virtual_entry\n",ix);
 159         return 0;
 160     }
 161     else{
 162         return 1;
 163     }
 164 }
 165
 166         /* Write a duplicate table entry to the hash file. */
 167 static int
 168 write_virtual_entry(long where,const VirtualHashLog *entry)
 169 {
 170     if(fseek(hash_file,where,SEEK_SET) != 0){
 171         fprintf(GlobalState.logfile,
 172                 "Fseek error to %ld in write_virtual_entry\n",where);
 173         return 0;
 174     }
 175     else if(fwrite((void *)entry,sizeof(*entry),1,hash_file) != 1){
 176         fprintf(GlobalState.logfile,
 177                 "Fwrite error from %ld in write_virtual_entry\n",where);
 178         return 0;
 179     }
 180     else{
 181         /* Written ok. */
 182         return 1;
 183     }
 184 }
 185
 186         /* Return the name of the original file if it looks like we
 187          * have met the moves in game_details before, otherwise return
 188          * NULL.  A match is assumed to be so if both
 189          * the final_ and cumulative_ hash values in game_details
 190          * are already present in VirtualLogTable.
 191          */
 192 static const char *
 193 previous_virtual_occurance(Game game_details)
 194 {   unsigned ix = game_details.final_hash_value % LOG_TABLE_SIZE;
 195     VirtualHashLog entry;
 196     Boolean duplicate = FALSE;
 197     const char *original_filename = NULL;
 198
 199
 200     /* Are we keeping this information? */
 201     if(GlobalState.suppress_duplicates || GlobalState.suppress_originals ||
 202                 GlobalState.duplicate_file != NULL){
 203       if(VirtualLogTable[ix].head < 0l){
 204         /* First occurrence. */
 205       }
 206       else{
 207         int keep_going =
 208                 retrieve_virtual_entry(VirtualLogTable[ix].head,&entry);
 209
 210         while(keep_going && !duplicate){
 211             if((entry.final_hash_value == game_details.final_hash_value) &&
 212                (entry.cumulative_hash_value == game_details.cumulative_hash_value)){
 213                 /* We have a match.
 214                  * Determine where it first occured.
 215                  */
 216                 original_filename = input_file_name(entry.file_number);
 217                 duplicate = TRUE;
 218             }
 219             else if(entry.next >= 0l){
 220                keep_going = retrieve_virtual_entry(entry.next,&entry);
 221             }
 222             else{
 223                keep_going = 0;
 224             }
 225         }
 226       }
 227
 228       if(!duplicate){
 229         /* Write an entry for it. */
 230         /* Where to write the next VirtualHashLog entry. */
 231         static long next_free_entry = 0l;
 232
 233         /* Store the XOR of the two hash values. */
 234         entry.final_hash_value = game_details.final_hash_value ;
 235         entry.cumulative_hash_value = game_details.cumulative_hash_value;
 236         entry.file_number = current_file_number();
 237         entry.next = -1l;
 238
 239         /* Write out these details. */
 240         if(write_virtual_entry(next_free_entry,&entry)){
 241             long where_written = next_free_entry;
 242             /* Move on ready for next time. */
 243             next_free_entry += sizeof(entry);
 244
 245             /* Now update the index table. */
 246             if(VirtualLogTable[ix].head < 0l){
 247                 /* First occurrence. */
 248                 VirtualLogTable[ix].head =
 249                         VirtualLogTable[ix].tail = where_written;
 250             }
 251             else{
 252                 VirtualHashLog tail;
 253
 254                 if(retrieve_virtual_entry(VirtualLogTable[ix].tail,&tail)){
 255                     tail.next = where_written;
 256                     (void) write_virtual_entry(VirtualLogTable[ix].tail,&tail);
 257                     /* Store the new tail address. */
 258                     VirtualLogTable[ix].tail = where_written;
 259                 }
 260             }
 261         }
 262       }
 263     }
 264     return original_filename;
 265 }
 266
 267         /* Return the name of the original file if it looks like we
 268          * have met the moves in game_details before, otherwise return
 269          * NULL.
 270          * For non-fuzzy comparision, a match is assumed to be so if both
 271          * final_ and cumulative_ hash values are already present
 272          * as a pair in LogTable.
 273          * Fuzzy matches depend on the match depth and do not use the
 274          * cumulative hash value.
 275          */
 276 const char *
 277 previous_occurance(Game game_details, int plycount)
 278 {
 279   const char *original_filename = NULL;
 280   if(GlobalState.use_virtual_hash_table){
 281     original_filename = previous_virtual_occurance(game_details);
 282   }
 283   else{
 284     unsigned ix = game_details.final_hash_value % LOG_TABLE_SIZE;
 285     HashLog *entry = NULL;
 286     Boolean duplicate = FALSE;
 287
 288     /* Are we keeping this information? */
 289     if(GlobalState.suppress_duplicates || GlobalState.suppress_originals ||
 290                 GlobalState.fuzzy_match_duplicates ||
 291                 GlobalState.duplicate_file != NULL){
 292         for(entry = LogTable[ix]; !duplicate && (entry != NULL);
 293                                         entry = entry->next){
 294             if(entry->final_hash_value == game_details.final_hash_value &&
 295                 entry->cumulative_hash_value == game_details.cumulative_hash_value){
 296                     /* An exact match. */
 297                     duplicate = TRUE;
 298             }
 299             else if(GlobalState.fuzzy_match_duplicates) {
 300                 if(GlobalState.fuzzy_match_depth == 0 &&
 301                     entry->final_hash_value == game_details.final_hash_value) {
 302                     /* Accept positional match at the end of the game. */
 303                     duplicate = TRUE;
 304                 }
 305                 else {
 306                     /* Need to check at the fuzzy_match_depth. */
 307                     if(entry->final_hash_value == game_details.fuzzy_duplicate_hash) {
 308                         duplicate = TRUE;
 309                     }
 310                 }
 311             }
 312             if(duplicate) {
 313                 /* We have a match.
 314                  * Determine where it first occured.
 315                  */
 316                 original_filename = input_file_name(entry->file_number);
 317             }
 318         }
 319
 320         if(!duplicate){
 321             /* First occurrence, so add it to the log. */
 322             entry = (HashLog *) MallocOrDie(sizeof(*entry));
 323
 324             if(!GlobalState.fuzzy_match_duplicates) {
 325                 /* Store the two hash values. */
 326                 entry->final_hash_value = game_details.final_hash_value;
 327                 entry->cumulative_hash_value = game_details.cumulative_hash_value;
 328             }
 329             else if(GlobalState.fuzzy_match_depth > 0 &&
 330                         plycount >= GlobalState.fuzzy_match_depth) {
 331                 /* Store just the hash value from the fuzzy depth. */
 332                 entry->final_hash_value = game_details.fuzzy_duplicate_hash;
 333                 entry->cumulative_hash_value = 0;
 334             }
 335             else {
 336                 /* Store the two hash values. */
 337                 entry->final_hash_value = game_details.final_hash_value;
 338                 entry->cumulative_hash_value = game_details.cumulative_hash_value;
 339             }
 340             entry->file_number = current_file_number();
 341             /* Link it into the head at this index. */
 342             entry->next =  LogTable[ix];
 343             LogTable[ix] = entry;
 344         }
 345     }
 346   }
 347   return original_filename;
 348 }