// Copyright 1994, 1995, 1996 by Jon Dart.  All Rights Reserved.

// Stand-alone executable to build the binary opening book from
// a text file.

// The book file is a binary file consisting of one or more "pages".
// Each page is a self-contained data structure consisting of
// three portions: a header, a hash table, and an array of book
// entries.  The page size and hash table size are configurable.

// By default each page is 65536 bytes, with a hash table of 511
// entries.  This makes each page hold slightly over 10,700 half-
// moves.  A book file must have a number of pages that is a power
// of 2, because the page is selected by taking a number of bits
// from the low-order bits of the hash code for the board position.

// The header is defined in bookdefs.h.  It currently contains 4
// fields:
//   version number
//   number of pages
//   page size (bytes)
//   hash table size (number of entries)

// The hash table is an array of unsigned indexes into the book
// entry array.  The high-order 32 bits of the hash code for the
// position modulo the hash table size is used to look up in this
// array the first book entry for the position.

// For the style book, the 4 bits of the hash table probe value
// (hash code % hash table size) are modified to equal the style
// value.  This is done both on construction of the book and on
// access to it, guaranteeing that only nodes which match the
// preferred style are accessed.

// The book entries themselves are structures defined in bookentr.h.
// Each one is 10 bytes and contains the full hash code, the move
// index, and a weight indicating how often the computer should play
// the move.  Hash entries for each chain in the hash table are stored
// contiguously in the book, and the weight byte for the last entry
// in each chain has its hi bit set.

#include "stdafx.h"
#include "board.h"
#include "emove.h"
#include "bookentr.h"
#include "bookdefs.h"
#include "hash.h"
#include "bhash.h"
#include "movegen.h"
#include "notation.h"
#include "types.h"
#include "debug.h"
#include "bearing.h"
extern "C"
{
#include <string.h>
#include <ctype.h>
};

#include <fstream.h>
#include <iostream.h>

char *programPath;

static const int Buffer_Size = 4096;
// max. moves per page
unsigned max_moves;

// This is the number of bits of hash code that are used
// to select a "page" of the book.  Hence the size in
// bytes of the book is (page size >> bookBits).
static int bookBits = 4;  //512K book
// number of pages in the book.
static int bookPages;
// mask to select bookBits
static int bookMask;
// size of a single page
static int pageSize = 65536;
// hash table size (number of entries).  Each entry is 2 bytes
static unsigned int hashSize = 2043;

static int style = 0;

static char *output_name;

struct book_info
{
    unsigned next_free;
    CWordArray *hash_table; 
    CPtrArray *book_moves; // array of Book_Entry *
};

// During opening book construction, we add an extra member to
// each book entry type.
class Book_Entry2  : public Book_Entry
{
public:
     Book_Entry2( hash_t hc, byte rec, byte mv_indx,
                  unsigned int nxt, BOOL last = FALSE);

     unsigned int next;
};

Book_Entry2::Book_Entry2( hash_t hc, byte rec, byte mv_indx,
                          unsigned int nxt, BOOL last)
:Book_Entry(hc,rec,mv_indx,last),next(nxt)
{
}

static book_info *book_data;

static BOOL
search(const unsigned start, const unsigned move_index,
       const int page,
       const hash_t hc)
{
   unsigned indx = start;
   Book_Entry2 be(hc, 0, move_index, 0, FALSE);
   while (indx != INVALID)
   {
      UNCOND_ASSERT(indx < max_moves);
      Book_Entry2 *entry = (Book_Entry2*)(*(book_data[page].book_moves))[indx];
      if (entry->is_equal(be) && entry->move_index == move_index)
              return TRUE;
      indx = entry->next;
   }
   return FALSE;
}

static void
add_move(const Board & board, int move_index, int recommend)
{
   unsigned page = (unsigned)(board.HashCode() & bookMask);
   // use the high order bits of the hash code as the table probe
   unsigned probe = (unsigned) (board.HashCode()>>32) % hashSize;
   if (style)
   {
       // Make the low-level bits of the bucket index match the
       // style
       probe &= ~(MAX_STYLES-1);
       probe |= style;
   }
   unsigned hit = (*(book_data[page].hash_table))[probe];
   if (hit == INVALID || !search(hit, move_index, page,
                                 board.HashCode()))
   {
      Book_Entry2 *new_entry = new Book_Entry2(board.HashCode(), recommend,
                                             move_index, hit, FALSE);
      ASSERT(new_entry);
      if (book_data[page].next_free >= max_moves)
      {
         cerr << "\nError - Too many moves in book " << 
              "(page " << page << ")" << endl;
         exit(-1);
      }
      unsigned next = book_data[page].next_free;
      (*(book_data[page].book_moves))[next] = new_entry;
      (*(book_data[page].hash_table))[probe] = next;
#ifdef DEBUG
      cout << "pg:" << page << " p:" << probe << 
           " h:" << (hex) << board.HashCode() << 
           (dec) << " i:" <<
           move_index << " f:" << next << " w:" << recommend << endl;
#endif
      book_data[page].next_free++;
   }
}

static void write_page(int page,ofstream &book_file)
{
   byte *write_buffer = new byte[Buffer_Size];
   ASSERT(write_buffer);

   // write the header
   struct Book_Header hdr;
   
   hdr.version = Book_Version;
   hdr.num_pages = bookPages;
   hdr.page_capacity = pageSize;
   hdr.hash_table_size = hashSize;

   book_file.write((char*)&hdr, Header_Size);

   // Re-work the hash table.  Right now it holds pointers to the
   // head of each hash chain, linked together with "next" pointers.
   // We are going to rearrange the chains so they are contiguous
   // in the book.  Then the hash table will hold indexes to the start
   // of each block of hash entries - these indexes are counts of
   // how many Book_Entry objects lie before the start of the desired
   // block.

   int running_count = 0;
   for (unsigned i = 0; i < hashSize; i++)
   {
      unsigned ht_entry = (*(book_data[page].hash_table))[i];
      if (ht_entry == INVALID)
      {
         book_file.put((char)(INVALID % 256));
         book_file.put((char)(INVALID / 256));
      }
      else
      {
         book_file.put((char)(running_count % 256));
         book_file.put((char)(running_count / 256));

         unsigned indx = ht_entry;
         unsigned count = 0;
         Book_Entry2 *entry = NULL;
         while (indx != INVALID)
         {
           entry = (Book_Entry2*)(*(book_data[page].book_moves))[indx];
           indx = entry->next;
           ++running_count;
         }
         if (entry)
           entry->set_last();
      }
   }

   // write the book moves

   unsigned index = 0;
   for (i = 0; i < hashSize; i++)
   {
      unsigned ht_entry = (*(book_data[page].hash_table))[i];
      while (ht_entry != INVALID)
      {
         Book_Entry2 *book_entr = 
             (Book_Entry2*)(*(book_data[page].book_moves))[ht_entry];
         if (index + Entry_Size <= Buffer_Size)
         {
                memcpy(write_buffer + index,
                           &book_entr->my_hash_code, Entry_Size);
                index += Entry_Size;
         } 
         else
         {
                unsigned to_go = Buffer_Size - index;
                if (to_go)
                {
                   memcpy(write_buffer + index,
                          &book_entr->my_hash_code, to_go);
                }
                book_file.write(write_buffer, Buffer_Size);
                memcpy(write_buffer, (char*)(&book_entr->my_hash_code) + to_go, Entry_Size - to_go);
                index = Entry_Size - to_go;
         }
         ht_entry = book_entr->next;
      }
   }
   if (index)
      book_file.write(write_buffer, index);
   long bookSize = book_file.tellp();
   while (bookSize % pageSize != 0L)
   {
      book_file.put('\0');
      bookSize++;
   }
   delete[] write_buffer;

   cout << "page " << page << ": " <<
      book_data[page].next_free << " moves." << endl;
}

static void write_book()
{
   ofstream book_file(output_name,
                       ios::out | ios::trunc | ios::binary);
   long total_moves = 0L;
   for (int i = 0; i < bookPages && book_file.good(); i++)
   {
      write_page(i,book_file);
      total_moves += book_data[i].next_free;
   }
   cout << total_moves << " total moves." << endl;
   book_file.close();
}

int
main(int argc, char **argv)
{
   char book_name[MAX_PATH];
   fstream infile;
   
   programPath = strdup(argv[0]);

   output_name = NULL;
   int arg = 1;
   while (arg < argc)
   {
      if (*argv[arg] == '-')
      {
         char c = argv[arg][1];
         switch(c)
         {
         case 'p': /* page size */
           ++arg;
           pageSize = atoi(argv[arg]);
           if (pageSize == 0 || pageSize > 0xffff)
           {
              cerr << "Illegal page size" << endl;
              exit(-1);
           }
           break;
         case 'o': /* output file name */
           ++arg;
           output_name = strdup(argv[arg]);
           break;
         case 'n': /* number of pages (power of 2)*/
           ++arg;
           bookBits = atoi(argv[arg]);
           if (bookBits == 0 || bookBits > MAXBOOKBITS)
           {
              cerr << "Illegal size specified for -n" << endl;
              exit(-1);
           }
           break;
        case 'h': /* hash size */         
           ++arg;
           hashSize = atoi(argv[arg]);
           if (hashSize == 0)
           {
              cerr << "Illegal hash size" << endl;
              exit(-1);
           }
           break;
         default:
           cerr << "Illegal switch: " << c << endl;
           cerr << "Usage:" << endl;
           cerr << "makebook -n <bits> -p <page size> -h <hash size>" << endl;
           cerr << "         -o <output file> <input file>" << endl;
           exit(-1);
         }
         ++arg;
      }
      else
          break;
   }
   bookPages = 1 << (bookBits-1);
   bookMask = bookPages-1;
   max_moves = (pageSize - hashSize*2 - Header_Size)/Entry_Size;
   if (max_moves < 5)
   {
      cerr << "Insufficient page size.  Use a larger value for -p"
          << endl;
      exit(-1);
   }
   else if (max_moves*Entry_Size < pageSize/4)
   {
      cerr << "Warning: hash table will consume > 1/4 of page." << endl;
      cerr << "Suggest you use a larger page size or smaller hash table size." << endl;
   }

   if (arg < argc)
      strcpy(book_name, argv[arg]);
   else
      strcpy(book_name, "book.txt");
   if (!output_name)
   {
       // construct the output name from the book name
       // by appending ".BIN".
      output_name = (char*)malloc(strlen(book_name)+5);
      strcpy(output_name,book_name);
      char *q = strrchr(output_name,'.');
      if (q)
      {
         *q = '\0';
      }
      strcat(output_name,".bin");
   }

   infile.open(book_name, ios::in);
   if (!infile.good())
   {
      cerr << "Can't open book file: " << book_name << endl;
      return -1;
   }

   // Initialize the "book_data" structures that will hold
   // the opening book info during book construction.
   
   book_data = new book_info[bookPages];
   for (int i = 0; i < bookPages; i++)
   {
      book_data[i].book_moves = new CPtrArray ();
      book_data[i].book_moves->SetSize(max_moves);
      book_data[i].hash_table = new CWordArray ();
      book_data[i].hash_table->SetSize(hashSize);
      book_data[i].next_free = 0;
   }
   
   for (int j = 0; j < bookPages; j++)
   {
      for (unsigned i = 0; i < hashSize; i++)
      {
         (*(book_data[j].hash_table))[i] = INVALID;
      }
      for (i = 0; i < max_moves; i++)
      {
         (*(book_data[j].book_moves))[i] = NULL;
      }
   }

   char buf[256];
   char movebuf[20];
   unsigned line = 0;
   char *q;
   Board board;
   Board tmpboard;
   int recommend;
   Move moves[Move_Generator::MaxMoves];
   int dots = 0;

   while (!infile.eof())
   {
      recommend = 5;
      infile.getline(buf, 256);
#ifdef DEBUG
      cout << buf << endl;
#endif
      line++;
      char *p = buf;
      while (isspace(*p))
             p++;
      switch (*p)
      {
      case '\0':
            continue;
      case ';':
            continue;
      case 'm':
            tmpboard = board;
            continue;
      case 'r':
            board = tmpboard;
            continue;
      case 's':
            ++p;
            while (isspace(*p))
                    p++;
            if (*p && isdigit(*p))
            {
                 sscanf(p,"%d",&style);
            }
            while (!isspace(*p)) ++p;
            
            continue;
      case '-':
            board.Reset();
            break;
      default:
          {
            while (*p)
            {
               while (isspace(*p))
                      p++;
               if (*p == '\0')
                  break;
               q = movebuf;
               int count = 0;
               while (!isspace(*p) && *p && count < 19)
               {
                      *q++ = *p++;
                      ++count;
               }
               *q = '\0';
               Move move = Notation::Value(board, board.Side(), movebuf);
               if (move.IsNull())
               {
                      cerr << endl << "Illegal move in file, line " << 
                         line << " (" << movebuf << ")" << endl;
                      infile.close();
                      return -1;
               }
               ExtendedMove emove(board, move);

               // check (pseudo) legality:
               Move_Generator mg(board, 0, Move::NullMove());
               int found = 0;
               int move_indx = 0;

               int n = mg.Generate_Moves(moves, TRUE /* repeatable */);

               for (int i = 0; i < n; i++)
               {
                      if (moves[i] == emove)
                      {
                         move_indx = i;
                         found++;
                         break;
                      }
               }
               if (!found)
               {
                       cerr << endl << "Illegal move in file, line " << line << " ("
                          << movebuf << ")" << endl;
                       infile.close();
                       return -1;
               }
               dots++;
               if (dots % 50 == 0)
                       cout << '.' << (flush);
               if (dots > 3000)
               {
                       cout << endl;
                       dots = 1;
               }
               recommend = 5;
               while (isspace(*p))
                       p++;
               if (*p)
               {
                       if ((*p >= '0') && (*p <= '9'))
                       {
                           recommend = *p - '0';
                           p++;
                       }
               }
               add_move(board, move_indx, recommend);
               board.MakeMove(emove);
            }
          }
      }
   }
   infile.close();

   cout << endl;
   write_book();
   cout << "Total book size: " <<
       pageSize*bookPages/1024 << "K. ";
   cout << "Capacity is about " <<
       max_moves*bookPages << " moves." << endl;
   
   return 0;
}
