git.sesse.net Git - stockfish/blob - src/syzygy/tbcore.cpp

   1 /*
   2   Copyright (c) 2011-2013 Ronald de Man
   3   This file may be redistributed and/or modified without restrictions.
   4
   5   tbcore.c contains engine-independent routines of the tablebase probing code.
   6   This file should not need to much adaptation to add tablebase probing to
   7   a particular engine, provided the engine is written in C or C++.
   8 */
   9
  10 #include <stdio.h>
  11 #include <unistd.h>
  12 #include <stdint.h>
  13 #include <stdlib.h>
  14 #include <string.h>
  15 #include <sys/stat.h>
  16 #include <fcntl.h>
  17 #ifndef __WIN32__
  18 #include <sys/mman.h>
  19 #endif
  20 #include "tbcore.h"
  21
  22 #define TBMAX_PIECE 254
  23 #define TBMAX_PAWN 256
  24 #define HSHMAX 5
  25
  26 // for variants where kings can connect and/or captured
  27 // #define CONNECTED_KINGS
  28
  29 #define Swap(a,b) {int tmp=a;a=b;b=tmp;}
  30
  31 #define TB_PAWN 1
  32 #define TB_KNIGHT 2
  33 #define TB_BISHOP 3
  34 #define TB_ROOK 4
  35 #define TB_QUEEN 5
  36 #define TB_KING 6
  37
  38 #define TB_WPAWN TB_PAWN
  39 #define TB_BPAWN (TB_PAWN | 8)
  40
  41 static LOCK_T TB_mutex;
  42
  43 static bool initialized = false;
  44 static int num_paths = 0;
  45 static char *path_string = NULL;
  46 static char **paths = NULL;
  47
  48 static int TBnum_piece, TBnum_pawn;
  49 static struct TBEntry_piece TB_piece[TBMAX_PIECE];
  50 static struct TBEntry_pawn TB_pawn[TBMAX_PAWN];
  51
  52 static struct TBHashEntry TB_hash[1 << TBHASHBITS][HSHMAX];
  53
  54 #define DTZ_ENTRIES 64
  55
  56 static struct DTZTableEntry DTZ_table[DTZ_ENTRIES];
  57
  58 static void init_indices(void);
  59 static uint64 calc_key_from_pcs(int *pcs, int mirror);
  60 static void free_wdl_entry(struct TBEntry *entry);
  61 static void free_dtz_entry(struct TBEntry *entry);
  62
  63 static FD open_tb(const char *str, const char *suffix)
  64 {
  65   int i;
  66   FD fd;
  67   char file[256];
  68
  69   for (i = 0; i < num_paths; i++) {
  70     strcpy(file, paths[i]);
  71     strcat(file, "/");
  72     strcat(file, str);
  73     strcat(file, suffix);
  74 #ifndef __WIN32__
  75     fd = open(file, O_RDONLY);
  76 #else
  77     fd = CreateFile(file, GENERIC_READ, FILE_SHARE_READ, NULL,
  78                           OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
  79 #endif
  80     if (fd != FD_ERR) return fd;
  81   }
  82   return FD_ERR;
  83 }
  84
  85 static void close_tb(FD fd)
  86 {
  87 #ifndef __WIN32__
  88   close(fd);
  89 #else
  90   CloseHandle(fd);
  91 #endif
  92 }
  93
  94 static char *map_file(const char *name, const char *suffix, uint64 *mapping)
  95 {
  96   FD fd = open_tb(name, suffix);
  97   if (fd == FD_ERR)
  98     return NULL;
  99 #ifndef __WIN32__
 100   struct stat statbuf;
 101   fstat(fd, &statbuf);
 102   *mapping = statbuf.st_size;
 103   char *data = (char *)mmap(NULL, statbuf.st_size, PROT_READ,
 104                               MAP_SHARED, fd, 0);
 105   if (data == (char *)(-1)) {
 106     printf("Could not mmap() %s.\n", name);
 107     exit(1);
 108   }
 109 #else
 110   DWORD size_low, size_high;
 111   size_low = GetFileSize(fd, &size_high);
 112 //  *size = ((uint64)size_high) << 32 | ((uint64)size_low);
 113   HANDLE map = CreateFileMapping(fd, NULL, PAGE_READONLY, size_high, size_low,
 114                                   NULL);
 115   if (map == NULL) {
 116     printf("CreateFileMapping() failed.\n");
 117     exit(1);
 118   }
 119   *mapping = (uint64)map;
 120   char *data = (char *)MapViewOfFile(map, FILE_MAP_READ, 0, 0, 0);
 121   if (data == NULL) {
 122     printf("MapViewOfFile() failed, name = %s%s, error = %lu.\n", name, suffix, GetLastError());
 123     exit(1);
 124   }
 125 #endif
 126   close_tb(fd);
 127   return data;
 128 }
 129
 130 #ifndef __WIN32__
 131 static void unmap_file(char *data, uint64 size)
 132 {
 133   if (!data) return;
 134   munmap(data, size);
 135 }
 136 #else
 137 static void unmap_file(char *data, uint64 mapping)
 138 {
 139   if (!data) return;
 140   UnmapViewOfFile(data);
 141   CloseHandle((HANDLE)mapping);
 142 }
 143 #endif
 144
 145 static void add_to_hash(struct TBEntry *ptr, uint64 key)
 146 {
 147   int i, hshidx;
 148
 149   hshidx = key >> (64 - TBHASHBITS);
 150   i = 0;
 151   while (i < HSHMAX && TB_hash[hshidx][i].ptr)
 152     i++;
 153   if (i == HSHMAX) {
 154     printf("HSHMAX too low!\n");
 155     exit(1);
 156   } else {
 157     TB_hash[hshidx][i].key = key;
 158     TB_hash[hshidx][i].ptr = ptr;
 159   }
 160 }
 161
 162 static char pchr[] = {'K', 'Q', 'R', 'B', 'N', 'P'};
 163
 164 static void init_tb(char *str)
 165 {
 166   FD fd;
 167   struct TBEntry *entry;
 168   int i, j, pcs[16];
 169   uint64 key, key2;
 170   int color;
 171   char *s;
 172
 173   fd = open_tb(str, WDLSUFFIX);
 174   if (fd == FD_ERR) return;
 175   close_tb(fd);
 176
 177   for (i = 0; i < 16; i++)
 178     pcs[i] = 0;
 179   color = 0;
 180   for (s = str; *s; s++)
 181     switch (*s) {
 182     case 'P':
 183       pcs[TB_PAWN | color]++;
 184       break;
 185     case 'N':
 186       pcs[TB_KNIGHT | color]++;
 187       break;
 188     case 'B':
 189       pcs[TB_BISHOP | color]++;
 190       break;
 191     case 'R':
 192       pcs[TB_ROOK | color]++;
 193       break;
 194     case 'Q':
 195       pcs[TB_QUEEN | color]++;
 196       break;
 197     case 'K':
 198       pcs[TB_KING | color]++;
 199       break;
 200     case 'v':
 201       color = 0x08;
 202       break;
 203     }
 204   for (i = 0; i < 8; i++)
 205     if (pcs[i] != pcs[i+8])
 206       break;
 207   key = calc_key_from_pcs(pcs, 0);
 208   key2 = calc_key_from_pcs(pcs, 1);
 209   if (pcs[TB_WPAWN] + pcs[TB_BPAWN] == 0) {
 210     if (TBnum_piece == TBMAX_PIECE) {
 211       printf("TBMAX_PIECE limit too low!\n");
 212       exit(1);
 213     }
 214     entry = (struct TBEntry *)&TB_piece[TBnum_piece++];
 215   } else {
 216     if (TBnum_pawn == TBMAX_PAWN) {
 217       printf("TBMAX_PAWN limit too low!\n");
 218       exit(1);
 219     }
 220     entry = (struct TBEntry *)&TB_pawn[TBnum_pawn++];
 221   }
 222   entry->key = key;
 223   entry->ready = 0;
 224   entry->num = 0;
 225   for (i = 0; i < 16; i++)
 226     entry->num += pcs[i];
 227   entry->symmetric = (key == key2);
 228   entry->has_pawns = (pcs[TB_WPAWN] + pcs[TB_BPAWN] > 0);
 229   if (entry->num > Tablebases::TBLargest)
 230     Tablebases::TBLargest = entry->num;
 231
 232   if (entry->has_pawns) {
 233     struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
 234     ptr->pawns[0] = pcs[TB_WPAWN];
 235     ptr->pawns[1] = pcs[TB_BPAWN];
 236     if (pcs[TB_BPAWN] > 0
 237               && (pcs[TB_WPAWN] == 0 || pcs[TB_BPAWN] < pcs[TB_WPAWN])) {
 238       ptr->pawns[0] = pcs[TB_BPAWN];
 239       ptr->pawns[1] = pcs[TB_WPAWN];
 240     }
 241   } else {
 242     struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
 243     for (i = 0, j = 0; i < 16; i++)
 244       if (pcs[i] == 1) j++;
 245     if (j >= 3) ptr->enc_type = 0;
 246     else if (j == 2) ptr->enc_type = 2;
 247     else { /* only for suicide */
 248       j = 16;
 249       for (i = 0; i < 16; i++) {
 250         if (pcs[i] < j && pcs[i] > 1) j = pcs[i];
 251         ptr->enc_type = 1 + j;
 252       }
 253     }
 254   }
 255   add_to_hash(entry, key);
 256   if (key2 != key) add_to_hash(entry, key2);
 257 }
 258
 259 void Tablebases::init(const std::string& path)
 260 {
 261   char str[16];
 262   int i, j, k, l;
 263
 264   if (initialized) {
 265     free(path_string);
 266     free(paths);
 267     struct TBEntry *entry;
 268     for (i = 0; i < TBnum_piece; i++) {
 269       entry = (struct TBEntry *)&TB_piece[i];
 270       free_wdl_entry(entry);
 271     }
 272     for (i = 0; i < TBnum_pawn; i++) {
 273       entry = (struct TBEntry *)&TB_pawn[i];
 274       free_wdl_entry(entry);
 275     }
 276     for (i = 0; i < DTZ_ENTRIES; i++)
 277       if (DTZ_table[i].entry)
 278         free_dtz_entry(DTZ_table[i].entry);
 279   } else {
 280     init_indices();
 281     initialized = true;
 282   }
 283
 284   const char *p = path.c_str();
 285   if (strlen(p) == 0 || !strcmp(p, "<empty>")) return;
 286   path_string = (char *)malloc(strlen(p) + 1);
 287   strcpy(path_string, p);
 288   num_paths = 0;
 289   for (i = 0;; i++) {
 290     if (path_string[i] != SEP_CHAR)
 291       num_paths++;
 292     while (path_string[i] && path_string[i] != SEP_CHAR)
 293       i++;
 294     if (!path_string[i]) break;
 295     path_string[i] = 0;
 296   }
 297   paths = (char **)malloc(num_paths * sizeof(char *));
 298   for (i = j = 0; i < num_paths; i++) {
 299     while (!path_string[j]) j++;
 300     paths[i] = &path_string[j];
 301     while (path_string[j]) j++;
 302   }
 303
 304   LOCK_INIT(TB_mutex);
 305
 306   TBnum_piece = TBnum_pawn = 0;
 307   TBLargest = 0;
 308
 309   for (i = 0; i < (1 << TBHASHBITS); i++)
 310     for (j = 0; j < HSHMAX; j++) {
 311       TB_hash[i][j].key = 0ULL;
 312       TB_hash[i][j].ptr = NULL;
 313     }
 314
 315   for (i = 0; i < DTZ_ENTRIES; i++)
 316     DTZ_table[i].entry = NULL;
 317
 318   for (i = 1; i < 6; i++) {
 319     sprintf(str, "K%cvK", pchr[i]);
 320     init_tb(str);
 321   }
 322
 323   for (i = 1; i < 6; i++)
 324     for (j = i; j < 6; j++) {
 325       sprintf(str, "K%cvK%c", pchr[i], pchr[j]);
 326       init_tb(str);
 327     }
 328
 329   for (i = 1; i < 6; i++)
 330     for (j = i; j < 6; j++) {
 331       sprintf(str, "K%c%cvK", pchr[i], pchr[j]);
 332       init_tb(str);
 333     }
 334
 335   for (i = 1; i < 6; i++)
 336     for (j = i; j < 6; j++)
 337       for (k = 1; k < 6; k++) {
 338         sprintf(str, "K%c%cvK%c", pchr[i], pchr[j], pchr[k]);
 339         init_tb(str);
 340       }
 341
 342   for (i = 1; i < 6; i++)
 343     for (j = i; j < 6; j++)
 344       for (k = j; k < 6; k++) {
 345         sprintf(str, "K%c%c%cvK", pchr[i], pchr[j], pchr[k]);
 346         init_tb(str);
 347       }
 348
 349   for (i = 1; i < 6; i++)
 350     for (j = i; j < 6; j++)
 351       for (k = i; k < 6; k++)
 352         for (l = (i == k) ? j : k; l < 6; l++) {
 353           sprintf(str, "K%c%cvK%c%c", pchr[i], pchr[j], pchr[k], pchr[l]);
 354           init_tb(str);
 355         }
 356
 357   for (i = 1; i < 6; i++)
 358     for (j = i; j < 6; j++)
 359       for (k = j; k < 6; k++)
 360         for (l = 1; l < 6; l++) {
 361           sprintf(str, "K%c%c%cvK%c", pchr[i], pchr[j], pchr[k], pchr[l]);
 362           init_tb(str);
 363         }
 364
 365   for (i = 1; i < 6; i++)
 366     for (j = i; j < 6; j++)
 367       for (k = j; k < 6; k++)
 368         for (l = k; l < 6; l++) {
 369           sprintf(str, "K%c%c%c%cvK", pchr[i], pchr[j], pchr[k], pchr[l]);
 370           init_tb(str);
 371         }
 372
 373   printf("info string Found %d tablebases.\n", TBnum_piece + TBnum_pawn);
 374 }
 375
 376 static const char offdiag[] = {
 377   0,-1,-1,-1,-1,-1,-1,-1,
 378   1, 0,-1,-1,-1,-1,-1,-1,
 379   1, 1, 0,-1,-1,-1,-1,-1,
 380   1, 1, 1, 0,-1,-1,-1,-1,
 381   1, 1, 1, 1, 0,-1,-1,-1,
 382   1, 1, 1, 1, 1, 0,-1,-1,
 383   1, 1, 1, 1, 1, 1, 0,-1,
 384   1, 1, 1, 1, 1, 1, 1, 0
 385 };
 386
 387 static const ubyte triangle[] = {
 388   6, 0, 1, 2, 2, 1, 0, 6,
 389   0, 7, 3, 4, 4, 3, 7, 0,
 390   1, 3, 8, 5, 5, 8, 3, 1,
 391   2, 4, 5, 9, 9, 5, 4, 2,
 392   2, 4, 5, 9, 9, 5, 4, 2,
 393   1, 3, 8, 5, 5, 8, 3, 1,
 394   0, 7, 3, 4, 4, 3, 7, 0,
 395   6, 0, 1, 2, 2, 1, 0, 6
 396 };
 397
 398 static const ubyte invtriangle[] = {
 399   1, 2, 3, 10, 11, 19, 0, 9, 18, 27
 400 };
 401
 402 static const ubyte invdiag[] = {
 403   0, 9, 18, 27, 36, 45, 54, 63,
 404   7, 14, 21, 28, 35, 42, 49, 56
 405 };
 406
 407 static const ubyte flipdiag[] = {
 408    0,  8, 16, 24, 32, 40, 48, 56,
 409    1,  9, 17, 25, 33, 41, 49, 57,
 410    2, 10, 18, 26, 34, 42, 50, 58,
 411    3, 11, 19, 27, 35, 43, 51, 59,
 412    4, 12, 20, 28, 36, 44, 52, 60,
 413    5, 13, 21, 29, 37, 45, 53, 61,
 414    6, 14, 22, 30, 38, 46, 54, 62,
 415    7, 15, 23, 31, 39, 47, 55, 63
 416 };
 417
 418 static const ubyte lower[] = {
 419   28,  0,  1,  2,  3,  4,  5,  6,
 420    0, 29,  7,  8,  9, 10, 11, 12,
 421    1,  7, 30, 13, 14, 15, 16, 17,
 422    2,  8, 13, 31, 18, 19, 20, 21,
 423    3,  9, 14, 18, 32, 22, 23, 24,
 424    4, 10, 15, 19, 22, 33, 25, 26,
 425    5, 11, 16, 20, 23, 25, 34, 27,
 426    6, 12, 17, 21, 24, 26, 27, 35
 427 };
 428
 429 static const ubyte diag[] = {
 430    0,  0,  0,  0,  0,  0,  0,  8,
 431    0,  1,  0,  0,  0,  0,  9,  0,
 432    0,  0,  2,  0,  0, 10,  0,  0,
 433    0,  0,  0,  3, 11,  0,  0,  0,
 434    0,  0,  0, 12,  4,  0,  0,  0,
 435    0,  0, 13,  0,  0,  5,  0,  0,
 436    0, 14,  0,  0,  0,  0,  6,  0,
 437   15,  0,  0,  0,  0,  0,  0,  7
 438 };
 439
 440 static const ubyte flap[] = {
 441   0, 0, 0, 0, 0, 0, 0, 0,
 442   0, 6, 12, 18, 18, 12, 6, 0,
 443   1, 7, 13, 19, 19, 13, 7, 1,
 444   2, 8, 14, 20, 20, 14, 8, 2,
 445   3, 9, 15, 21, 21, 15, 9, 3,
 446   4, 10, 16, 22, 22, 16, 10, 4,
 447   5, 11, 17, 23, 23, 17, 11, 5,
 448   0, 0, 0, 0, 0, 0, 0, 0
 449 };
 450
 451 static const ubyte ptwist[] = {
 452   0, 0, 0, 0, 0, 0, 0, 0,
 453   47, 35, 23, 11, 10, 22, 34, 46,
 454   45, 33, 21, 9, 8, 20, 32, 44,
 455   43, 31, 19, 7, 6, 18, 30, 42,
 456   41, 29, 17, 5, 4, 16, 28, 40,
 457   39, 27, 15, 3, 2, 14, 26, 38,
 458   37, 25, 13, 1, 0, 12, 24, 36,
 459   0, 0, 0, 0, 0, 0, 0, 0
 460 };
 461
 462 static const ubyte invflap[] = {
 463   8, 16, 24, 32, 40, 48,
 464   9, 17, 25, 33, 41, 49,
 465   10, 18, 26, 34, 42, 50,
 466   11, 19, 27, 35, 43, 51
 467 };
 468
 469 static const ubyte invptwist[] = {
 470   52, 51, 44, 43, 36, 35, 28, 27, 20, 19, 12, 11,
 471   53, 50, 45, 42, 37, 34, 29, 26, 21, 18, 13, 10,
 472   54, 49, 46, 41, 38, 33, 30, 25, 22, 17, 14, 9,
 473   55, 48, 47, 40, 39, 32, 31, 24, 23, 16, 15, 8
 474 };
 475
 476 static const ubyte file_to_file[] = {
 477   0, 1, 2, 3, 3, 2, 1, 0
 478 };
 479
 480 #ifndef CONNECTED_KINGS
 481 static const short KK_idx[10][64] = {
 482   { -1, -1, -1,  0,  1,  2,  3,  4,
 483     -1, -1, -1,  5,  6,  7,  8,  9,
 484     10, 11, 12, 13, 14, 15, 16, 17,
 485     18, 19, 20, 21, 22, 23, 24, 25,
 486     26, 27, 28, 29, 30, 31, 32, 33,
 487     34, 35, 36, 37, 38, 39, 40, 41,
 488     42, 43, 44, 45, 46, 47, 48, 49,
 489     50, 51, 52, 53, 54, 55, 56, 57 },
 490   { 58, -1, -1, -1, 59, 60, 61, 62,
 491     63, -1, -1, -1, 64, 65, 66, 67,
 492     68, 69, 70, 71, 72, 73, 74, 75,
 493     76, 77, 78, 79, 80, 81, 82, 83,
 494     84, 85, 86, 87, 88, 89, 90, 91,
 495     92, 93, 94, 95, 96, 97, 98, 99,
 496    100,101,102,103,104,105,106,107,
 497    108,109,110,111,112,113,114,115},
 498   {116,117, -1, -1, -1,118,119,120,
 499    121,122, -1, -1, -1,123,124,125,
 500    126,127,128,129,130,131,132,133,
 501    134,135,136,137,138,139,140,141,
 502    142,143,144,145,146,147,148,149,
 503    150,151,152,153,154,155,156,157,
 504    158,159,160,161,162,163,164,165,
 505    166,167,168,169,170,171,172,173 },
 506   {174, -1, -1, -1,175,176,177,178,
 507    179, -1, -1, -1,180,181,182,183,
 508    184, -1, -1, -1,185,186,187,188,
 509    189,190,191,192,193,194,195,196,
 510    197,198,199,200,201,202,203,204,
 511    205,206,207,208,209,210,211,212,
 512    213,214,215,216,217,218,219,220,
 513    221,222,223,224,225,226,227,228 },
 514   {229,230, -1, -1, -1,231,232,233,
 515    234,235, -1, -1, -1,236,237,238,
 516    239,240, -1, -1, -1,241,242,243,
 517    244,245,246,247,248,249,250,251,
 518    252,253,254,255,256,257,258,259,
 519    260,261,262,263,264,265,266,267,
 520    268,269,270,271,272,273,274,275,
 521    276,277,278,279,280,281,282,283 },
 522   {284,285,286,287,288,289,290,291,
 523    292,293, -1, -1, -1,294,295,296,
 524    297,298, -1, -1, -1,299,300,301,
 525    302,303, -1, -1, -1,304,305,306,
 526    307,308,309,310,311,312,313,314,
 527    315,316,317,318,319,320,321,322,
 528    323,324,325,326,327,328,329,330,
 529    331,332,333,334,335,336,337,338 },
 530   { -1, -1,339,340,341,342,343,344,
 531     -1, -1,345,346,347,348,349,350,
 532     -1, -1,441,351,352,353,354,355,
 533     -1, -1, -1,442,356,357,358,359,
 534     -1, -1, -1, -1,443,360,361,362,
 535     -1, -1, -1, -1, -1,444,363,364,
 536     -1, -1, -1, -1, -1, -1,445,365,
 537     -1, -1, -1, -1, -1, -1, -1,446 },
 538   { -1, -1, -1,366,367,368,369,370,
 539     -1, -1, -1,371,372,373,374,375,
 540     -1, -1, -1,376,377,378,379,380,
 541     -1, -1, -1,447,381,382,383,384,
 542     -1, -1, -1, -1,448,385,386,387,
 543     -1, -1, -1, -1, -1,449,388,389,
 544     -1, -1, -1, -1, -1, -1,450,390,
 545     -1, -1, -1, -1, -1, -1, -1,451 },
 546   {452,391,392,393,394,395,396,397,
 547     -1, -1, -1, -1,398,399,400,401,
 548     -1, -1, -1, -1,402,403,404,405,
 549     -1, -1, -1, -1,406,407,408,409,
 550     -1, -1, -1, -1,453,410,411,412,
 551     -1, -1, -1, -1, -1,454,413,414,
 552     -1, -1, -1, -1, -1, -1,455,415,
 553     -1, -1, -1, -1, -1, -1, -1,456 },
 554   {457,416,417,418,419,420,421,422,
 555     -1,458,423,424,425,426,427,428,
 556     -1, -1, -1, -1, -1,429,430,431,
 557     -1, -1, -1, -1, -1,432,433,434,
 558     -1, -1, -1, -1, -1,435,436,437,
 559     -1, -1, -1, -1, -1,459,438,439,
 560     -1, -1, -1, -1, -1, -1,460,440,
 561     -1, -1, -1, -1, -1, -1, -1,461 }
 562 };
 563 #else
 564 static const short PP_idx[10][64] = {
 565   {  0, -1,  1,  2,  3,  4,  5,  6,
 566      7,  8,  9, 10, 11, 12, 13, 14,
 567     15, 16, 17, 18, 19, 20, 21, 22,
 568     23, 24, 25, 26, 27, 28, 29, 30,
 569     31, 32, 33, 34, 35, 36, 37, 38,
 570     39, 40, 41, 42, 43, 44, 45, 46,
 571     -1, 47, 48, 49, 50, 51, 52, 53,
 572     54, 55, 56, 57, 58, 59, 60, 61 },
 573   { 62, -1, -1, 63, 64, 65, -1, 66,
 574     -1, 67, 68, 69, 70, 71, 72, -1,
 575     73, 74, 75, 76, 77, 78, 79, 80,
 576     81, 82, 83, 84, 85, 86, 87, 88,
 577     89, 90, 91, 92, 93, 94, 95, 96,
 578     -1, 97, 98, 99,100,101,102,103,
 579     -1,104,105,106,107,108,109, -1,
 580    110, -1,111,112,113,114, -1,115 },
 581   {116, -1, -1, -1,117, -1, -1,118,
 582     -1,119,120,121,122,123,124, -1,
 583     -1,125,126,127,128,129,130, -1,
 584    131,132,133,134,135,136,137,138,
 585     -1,139,140,141,142,143,144,145,
 586     -1,146,147,148,149,150,151, -1,
 587     -1,152,153,154,155,156,157, -1,
 588    158, -1, -1,159,160, -1, -1,161 },
 589   {162, -1, -1, -1, -1, -1, -1,163,
 590     -1,164, -1,165,166,167,168, -1,
 591     -1,169,170,171,172,173,174, -1,
 592     -1,175,176,177,178,179,180, -1,
 593     -1,181,182,183,184,185,186, -1,
 594     -1, -1,187,188,189,190,191, -1,
 595     -1,192,193,194,195,196,197, -1,
 596    198, -1, -1, -1, -1, -1, -1,199 },
 597   {200, -1, -1, -1, -1, -1, -1,201,
 598     -1,202, -1, -1,203, -1,204, -1,
 599     -1, -1,205,206,207,208, -1, -1,
 600     -1,209,210,211,212,213,214, -1,
 601     -1, -1,215,216,217,218,219, -1,
 602     -1, -1,220,221,222,223, -1, -1,
 603     -1,224, -1,225,226, -1,227, -1,
 604    228, -1, -1, -1, -1, -1, -1,229 },
 605   {230, -1, -1, -1, -1, -1, -1,231,
 606     -1,232, -1, -1, -1, -1,233, -1,
 607     -1, -1,234, -1,235,236, -1, -1,
 608     -1, -1,237,238,239,240, -1, -1,
 609     -1, -1, -1,241,242,243, -1, -1,
 610     -1, -1,244,245,246,247, -1, -1,
 611     -1,248, -1, -1, -1, -1,249, -1,
 612    250, -1, -1, -1, -1, -1, -1,251 },
 613   { -1, -1, -1, -1, -1, -1, -1,259,
 614     -1,252, -1, -1, -1, -1,260, -1,
 615     -1, -1,253, -1, -1,261, -1, -1,
 616     -1, -1, -1,254,262, -1, -1, -1,
 617     -1, -1, -1, -1,255, -1, -1, -1,
 618     -1, -1, -1, -1, -1,256, -1, -1,
 619     -1, -1, -1, -1, -1, -1,257, -1,
 620     -1, -1, -1, -1, -1, -1, -1,258 },
 621   { -1, -1, -1, -1, -1, -1, -1, -1,
 622     -1, -1, -1, -1, -1, -1,268, -1,
 623     -1, -1,263, -1, -1,269, -1, -1,
 624     -1, -1, -1,264,270, -1, -1, -1,
 625     -1, -1, -1, -1,265, -1, -1, -1,
 626     -1, -1, -1, -1, -1,266, -1, -1,
 627     -1, -1, -1, -1, -1, -1,267, -1,
 628     -1, -1, -1, -1, -1, -1, -1, -1 },
 629   { -1, -1, -1, -1, -1, -1, -1, -1,
 630     -1, -1, -1, -1, -1, -1, -1, -1,
 631     -1, -1, -1, -1, -1,274, -1, -1,
 632     -1, -1, -1,271,275, -1, -1, -1,
 633     -1, -1, -1, -1,272, -1, -1, -1,
 634     -1, -1, -1, -1, -1,273, -1, -1,
 635     -1, -1, -1, -1, -1, -1, -1, -1,
 636     -1, -1, -1, -1, -1, -1, -1, -1 },
 637   { -1, -1, -1, -1, -1, -1, -1, -1,
 638     -1, -1, -1, -1, -1, -1, -1, -1,
 639     -1, -1, -1, -1, -1, -1, -1, -1,
 640     -1, -1, -1, -1,277, -1, -1, -1,
 641     -1, -1, -1, -1,276, -1, -1, -1,
 642     -1, -1, -1, -1, -1, -1, -1, -1,
 643     -1, -1, -1, -1, -1, -1, -1, -1,
 644     -1, -1, -1, -1, -1, -1, -1, -1 }
 645 };
 646
 647 static const ubyte test45[] = {
 648   0, 0, 0, 0, 0, 0, 0, 0,
 649   0, 0, 0, 0, 0, 0, 0, 0,
 650   0, 0, 0, 0, 0, 0, 0, 0,
 651   0, 0, 0, 0, 0, 0, 0, 0,
 652   1, 1, 1, 0, 0, 0, 0, 0,
 653   1, 1, 0, 0, 0, 0, 0, 0,
 654   1, 0, 0, 0, 0, 0, 0, 0,
 655   0, 0, 0, 0, 0, 0, 0, 0
 656 };
 657
 658 static const ubyte mtwist[] = {
 659   15, 63, 55, 47, 40, 48, 56, 12,
 660   62, 11, 39, 31, 24, 32,  8, 57,
 661   54, 38,  7, 23, 16,  4, 33, 49,
 662   46, 30, 22,  3,  0, 17, 25, 41,
 663   45, 29, 21,  2,  1, 18, 26, 42,
 664   53, 37,  6, 20, 19,  5, 34, 50,
 665   61, 10, 36, 28, 27, 35,  9, 58,
 666   14, 60, 52, 44, 43, 51, 59, 13
 667 };
 668 #endif
 669
 670 static int binomial[5][64];
 671 static int pawnidx[5][24];
 672 static int pfactor[5][4];
 673 #ifdef CONNECTED_KINGS
 674 static int multidx[5][10];
 675 static int mfactor[5];
 676 #endif
 677
 678 static void init_indices(void)
 679 {
 680   int i, j, k;
 681
 682 // binomial[k-1][n] = Bin(n, k)
 683   for (i = 0; i < 5; i++)
 684     for (j = 0; j < 64; j++) {
 685       int f = j;
 686       int l = 1;
 687       for (k = 1; k <= i; k++) {
 688         f *= (j - k);
 689         l *= (k + 1);
 690       }
 691       binomial[i][j] = f / l;
 692     }
 693
 694   for (i = 0; i < 5; i++) {
 695     int s = 0;
 696     for (j = 0; j < 6; j++) {
 697       pawnidx[i][j] = s;
 698       s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
 699     }
 700     pfactor[i][0] = s;
 701     s = 0;
 702     for (; j < 12; j++) {
 703       pawnidx[i][j] = s;
 704       s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
 705     }
 706     pfactor[i][1] = s;
 707     s = 0;
 708     for (; j < 18; j++) {
 709       pawnidx[i][j] = s;
 710       s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
 711     }
 712     pfactor[i][2] = s;
 713     s = 0;
 714     for (; j < 24; j++) {
 715       pawnidx[i][j] = s;
 716       s += (i == 0) ? 1 : binomial[i - 1][ptwist[invflap[j]]];
 717     }
 718     pfactor[i][3] = s;
 719   }
 720
 721 #ifdef CONNECTED_KINGS
 722   for (i = 0; i < 5; i++) {
 723     int s = 0;
 724     for (j = 0; j < 10; j++) {
 725       multidx[i][j] = s;
 726       s += (i == 0) ? 1 : binomial[i - 1][mtwist[invtriangle[j]]];
 727     }
 728     mfactor[i] = s;
 729   }
 730 #endif
 731 }
 732
 733 #ifndef CONNECTED_KINGS
 734 static uint64 encode_piece(struct TBEntry_piece *ptr, ubyte *norm, int *pos, int *factor)
 735 {
 736   uint64 idx;
 737   int i, j, k, m, l, p;
 738   int n = ptr->num;
 739
 740   if (pos[0] & 0x04) {
 741     for (i = 0; i < n; i++)
 742       pos[i] ^= 0x07;
 743   }
 744   if (pos[0] & 0x20) {
 745     for (i = 0; i < n; i++)
 746       pos[i] ^= 0x38;
 747   }
 748
 749   for (i = 0; i < n; i++)
 750     if (offdiag[pos[i]]) break;
 751   if (i < (ptr->enc_type == 0 ? 3 : 2) && offdiag[pos[i]] > 0)
 752     for (i = 0; i < n; i++)
 753       pos[i] = flipdiag[pos[i]];
 754
 755   switch (ptr->enc_type) {
 756
 757   case 0: /* 111 */
 758     i = (pos[1] > pos[0]);
 759     j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
 760
 761     if (offdiag[pos[0]])
 762       idx = triangle[pos[0]] * 63*62 + (pos[1] - i) * 62 + (pos[2] - j);
 763     else if (offdiag[pos[1]])
 764       idx = 6*63*62 + diag[pos[0]] * 28*62 + lower[pos[1]] * 62 + pos[2] - j;
 765     else if (offdiag[pos[2]])
 766       idx = 6*63*62 + 4*28*62 + (diag[pos[0]]) * 7*28 + (diag[pos[1]] - i) * 28 + lower[pos[2]];
 767     else
 768       idx = 6*63*62 + 4*28*62 + 4*7*28 + (diag[pos[0]] * 7*6) + (diag[pos[1]] - i) * 6 + (diag[pos[2]] - j);
 769     i = 3;
 770     break;
 771
 772   case 1: /* K3 */
 773     j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
 774
 775     idx = KK_idx[triangle[pos[0]]][pos[1]];
 776     if (idx < 441)
 777       idx = idx + 441 * (pos[2] - j);
 778     else {
 779       idx = 441*62 + (idx - 441) + 21 * lower[pos[2]];
 780       if (!offdiag[pos[2]])
 781         idx -= j * 21;
 782     }
 783     i = 3;
 784     break;
 785
 786   default: /* K2 */
 787     idx = KK_idx[triangle[pos[0]]][pos[1]];
 788     i = 2;
 789     break;
 790   }
 791   idx *= factor[0];
 792
 793   for (; i < n;) {
 794     int t = norm[i];
 795     for (j = i; j < i + t; j++)
 796       for (k = j + 1; k < i + t; k++)
 797         if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
 798     int s = 0;
 799     for (m = i; m < i + t; m++) {
 800       p = pos[m];
 801       for (l = 0, j = 0; l < i; l++)
 802         j += (p > pos[l]);
 803       s += binomial[m - i][p - j];
 804     }
 805     idx += ((uint64)s) * ((uint64)factor[i]);
 806     i += t;
 807   }
 808
 809   return idx;
 810 }
 811 #else
 812 static uint64 encode_piece(struct TBEntry_piece *ptr, ubyte *norm, int *pos, int *factor)
 813 {
 814   uint64 idx;
 815   int i, j, k, m, l, p;
 816   int n = ptr->num;
 817
 818   if (ptr->enc_type < 3) {
 819     if (pos[0] & 0x04) {
 820       for (i = 0; i < n; i++)
 821         pos[i] ^= 0x07;
 822     }
 823     if (pos[0] & 0x20) {
 824       for (i = 0; i < n; i++)
 825         pos[i] ^= 0x38;
 826     }
 827
 828     for (i = 0; i < n; i++)
 829       if (offdiag[pos[i]]) break;
 830     if (i < (ptr->enc_type == 0 ? 3 : 2) && offdiag[pos[i]] > 0)
 831       for (i = 0; i < n; i++)
 832         pos[i] = flipdiag[pos[i]];
 833
 834     switch (ptr->enc_type) {
 835
 836     case 0: /* 111 */
 837       i = (pos[1] > pos[0]);
 838       j = (pos[2] > pos[0]) + (pos[2] > pos[1]);
 839
 840       if (offdiag[pos[0]])
 841         idx = triangle[pos[0]] * 63*62 + (pos[1] - i) * 62 + (pos[2] - j);
 842       else if (offdiag[pos[1]])
 843         idx = 6*63*62 + diag[pos[0]] * 28*62 + lower[pos[1]] * 62 + pos[2] - j;
 844       else if (offdiag[pos[2]])
 845         idx = 6*63*62 + 4*28*62 + (diag[pos[0]]) * 7*28 + (diag[pos[1]] - i) * 28 + lower[pos[2]];
 846       else
 847         idx = 6*63*62 + 4*28*62 + 4*7*28 + (diag[pos[0]] * 7*6) + (diag[pos[1]] - i) * 6 + (diag[pos[2]] - j);
 848       i = 3;
 849       break;
 850
 851     case 2: /* 11 */
 852       i = (pos[1] > pos[0]);
 853
 854       if (offdiag[pos[0]])
 855         idx = triangle[pos[0]] * 63 + (pos[1] - i);
 856       else if (offdiag[pos[1]])
 857         idx = 6*63 + diag[pos[0]] * 28 + lower[pos[1]];
 858       else
 859         idx = 6*63 + 4*28 + (diag[pos[0]]) * 7 + (diag[pos[1]] - i);
 860       i = 2;
 861       break;
 862
 863     }
 864   } else if (ptr->enc_type == 3) { /* 2, e.g. KKvK */
 865     if (triangle[pos[0]] > triangle[pos[1]])
 866       Swap(pos[0], pos[1]);
 867     if (pos[0] & 0x04)
 868       for (i = 0; i < n; i++)
 869         pos[i] ^= 0x07;
 870     if (pos[0] & 0x20)
 871       for (i = 0; i < n; i++)
 872         pos[i] ^= 0x38;
 873     if (offdiag[pos[0]] > 0 || (offdiag[pos[0]] == 0 && offdiag[pos[1]] > 0))
 874       for (i = 0; i < n; i++)
 875         pos[i] = flipdiag[pos[i]];
 876     if (test45[pos[1]] && triangle[pos[0]] == triangle[pos[1]]) {
 877       Swap(pos[0], pos[1]);
 878       for (i = 0; i < n; i++)
 879         pos[i] = flipdiag[pos[i] ^ 0x38];
 880     }
 881     idx = PP_idx[triangle[pos[0]]][pos[1]];
 882     i = 2;
 883   } else { /* 3 and higher, e.g. KKKvK and KKKKvK */
 884     for (i = 1; i < norm[0]; i++)
 885       if (triangle[pos[0]] > triangle[pos[i]])
 886         Swap(pos[0], pos[i]);
 887     if (pos[0] & 0x04)
 888       for (i = 0; i < n; i++)
 889         pos[i] ^= 0x07;
 890     if (pos[0] & 0x20)
 891       for (i = 0; i < n; i++)
 892         pos[i] ^= 0x38;
 893     if (offdiag[pos[0]] > 0)
 894       for (i = 0; i < n; i++)
 895         pos[i] = flipdiag[pos[i]];
 896     for (i = 1; i < norm[0]; i++)
 897       for (j = i + 1; j < norm[0]; j++)
 898         if (mtwist[pos[i]] > mtwist[pos[j]])
 899           Swap(pos[i], pos[j]);
 900
 901     idx = multidx[norm[0] - 1][triangle[pos[0]]];
 902     for (i = 1; i < norm[0]; i++)
 903       idx += binomial[i - 1][mtwist[pos[i]]];
 904   }
 905   idx *= factor[0];
 906
 907   for (; i < n;) {
 908     int t = norm[i];
 909     for (j = i; j < i + t; j++)
 910       for (k = j + 1; k < i + t; k++)
 911         if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
 912     int s = 0;
 913     for (m = i; m < i + t; m++) {
 914       p = pos[m];
 915       for (l = 0, j = 0; l < i; l++)
 916         j += (p > pos[l]);
 917       s += binomial[m - i][p - j];
 918     }
 919     idx += ((uint64)s) * ((uint64)factor[i]);
 920     i += t;
 921   }
 922
 923   return idx;
 924 }
 925 #endif
 926
 927 // determine file of leftmost pawn and sort pawns
 928 static int pawn_file(struct TBEntry_pawn *ptr, int *pos)
 929 {
 930   int i;
 931
 932   for (i = 1; i < ptr->pawns[0]; i++)
 933     if (flap[pos[0]] > flap[pos[i]])
 934       Swap(pos[0], pos[i]);
 935
 936   return file_to_file[pos[0] & 0x07];
 937 }
 938
 939 static uint64 encode_pawn(struct TBEntry_pawn *ptr, ubyte *norm, int *pos, int *factor)
 940 {
 941   uint64 idx;
 942   int i, j, k, m, s, t;
 943   int n = ptr->num;
 944
 945   if (pos[0] & 0x04)
 946     for (i = 0; i < n; i++)
 947       pos[i] ^= 0x07;
 948
 949   for (i = 1; i < ptr->pawns[0]; i++)
 950     for (j = i + 1; j < ptr->pawns[0]; j++)
 951       if (ptwist[pos[i]] < ptwist[pos[j]])
 952         Swap(pos[i], pos[j]);
 953
 954   t = ptr->pawns[0] - 1;
 955   idx = pawnidx[t][flap[pos[0]]];
 956   for (i = t; i > 0; i--)
 957     idx += binomial[t - i][ptwist[pos[i]]];
 958   idx *= factor[0];
 959
 960 // remaining pawns
 961   i = ptr->pawns[0];
 962   t = i + ptr->pawns[1];
 963   if (t > i) {
 964     for (j = i; j < t; j++)
 965       for (k = j + 1; k < t; k++)
 966         if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
 967     s = 0;
 968     for (m = i; m < t; m++) {
 969       int p = pos[m];
 970       for (k = 0, j = 0; k < i; k++)
 971         j += (p > pos[k]);
 972       s += binomial[m - i][p - j - 8];
 973     }
 974     idx += ((uint64)s) * ((uint64)factor[i]);
 975     i = t;
 976   }
 977
 978   for (; i < n;) {
 979     t = norm[i];
 980     for (j = i; j < i + t; j++)
 981       for (k = j + 1; k < i + t; k++)
 982         if (pos[j] > pos[k]) Swap(pos[j], pos[k]);
 983     s = 0;
 984     for (m = i; m < i + t; m++) {
 985       int p = pos[m];
 986       for (k = 0, j = 0; k < i; k++)
 987         j += (p > pos[k]);
 988       s += binomial[m - i][p - j];
 989     }
 990     idx += ((uint64)s) * ((uint64)factor[i]);
 991     i += t;
 992   }
 993
 994   return idx;
 995 }
 996
 997 // place k like pieces on n squares
 998 static int subfactor(int k, int n)
 999 {
1000   int i, f, l;
1001
1002   f = n;
1003   l = 1;
1004   for (i = 1; i < k; i++) {
1005     f *= n - i;
1006     l *= i + 1;
1007   }
1008
1009   return f / l;
1010 }
1011
1012 static uint64 calc_factors_piece(int *factor, int num, int order, ubyte *norm, ubyte enc_type)
1013 {
1014   int i, k, n;
1015   uint64 f;
1016 #ifndef CONNECTED_KINGS
1017   static int pivfac[] = { 31332, 28056, 462 };
1018 #else
1019   static int pivfac[] = { 31332, 0, 518, 278 };
1020 #endif
1021
1022   n = 64 - norm[0];
1023
1024   f = 1;
1025   for (i = norm[0], k = 0; i < num || k == order; k++) {
1026     if (k == order) {
1027       factor[0] = f;
1028 #ifndef CONNECTED_KINGS
1029       f *= pivfac[enc_type];
1030 #else
1031       if (enc_type < 4)
1032         f *= pivfac[enc_type];
1033       else
1034         f *= mfactor[enc_type - 2];
1035 #endif
1036     } else {
1037       factor[i] = f;
1038       f *= subfactor(norm[i], n);
1039       n -= norm[i];
1040       i += norm[i];
1041     }
1042   }
1043
1044   return f;
1045 }
1046
1047 static uint64 calc_factors_pawn(int *factor, int num, int order, int order2, ubyte *norm, int file)
1048 {
1049   int i, k, n;
1050   uint64 f;
1051
1052   i = norm[0];
1053   if (order2 < 0x0f) i += norm[i];
1054   n = 64 - i;
1055
1056   f = 1;
1057   for (k = 0; i < num || k == order || k == order2; k++) {
1058     if (k == order) {
1059       factor[0] = f;
1060       f *= pfactor[norm[0] - 1][file];
1061     } else if (k == order2) {
1062       factor[norm[0]] = f;
1063       f *= subfactor(norm[norm[0]], 48 - norm[0]);
1064     } else {
1065       factor[i] = f;
1066       f *= subfactor(norm[i], n);
1067       n -= norm[i];
1068       i += norm[i];
1069     }
1070   }
1071
1072   return f;
1073 }
1074
1075 static void set_norm_piece(struct TBEntry_piece *ptr, ubyte *norm, ubyte *pieces)
1076 {
1077   int i, j;
1078
1079   for (i = 0; i < ptr->num; i++)
1080     norm[i] = 0;
1081
1082   switch (ptr->enc_type) {
1083   case 0:
1084     norm[0] = 3;
1085     break;
1086   case 2:
1087     norm[0] = 2;
1088     break;
1089   default:
1090     norm[0] = ptr->enc_type - 1;
1091     break;
1092   }
1093
1094   for (i = norm[0]; i < ptr->num; i += norm[i])
1095     for (j = i; j < ptr->num && pieces[j] == pieces[i]; j++)
1096       norm[i]++;
1097 }
1098
1099 static void set_norm_pawn(struct TBEntry_pawn *ptr, ubyte *norm, ubyte *pieces)
1100 {
1101   int i, j;
1102
1103   for (i = 0; i < ptr->num; i++)
1104     norm[i] = 0;
1105
1106   norm[0] = ptr->pawns[0];
1107   if (ptr->pawns[1]) norm[ptr->pawns[0]] = ptr->pawns[1];
1108
1109   for (i = ptr->pawns[0] + ptr->pawns[1]; i < ptr->num; i += norm[i])
1110     for (j = i; j < ptr->num && pieces[j] == pieces[i]; j++)
1111       norm[i]++;
1112 }
1113
1114 static void setup_pieces_piece(struct TBEntry_piece *ptr, unsigned char *data, uint64 *tb_size)
1115 {
1116   int i;
1117   int order;
1118
1119   for (i = 0; i < ptr->num; i++)
1120     ptr->pieces[0][i] = data[i + 1] & 0x0f;
1121   order = data[0] & 0x0f;
1122   set_norm_piece(ptr, ptr->norm[0], ptr->pieces[0]);
1123   tb_size[0] = calc_factors_piece(ptr->factor[0], ptr->num, order, ptr->norm[0], ptr->enc_type);
1124
1125   for (i = 0; i < ptr->num; i++)
1126     ptr->pieces[1][i] = data[i + 1] >> 4;
1127   order = data[0] >> 4;
1128   set_norm_piece(ptr, ptr->norm[1], ptr->pieces[1]);
1129   tb_size[1] = calc_factors_piece(ptr->factor[1], ptr->num, order, ptr->norm[1], ptr->enc_type);
1130 }
1131
1132 static void setup_pieces_piece_dtz(struct DTZEntry_piece *ptr, unsigned char *data, uint64 *tb_size)
1133 {
1134   int i;
1135   int order;
1136
1137   for (i = 0; i < ptr->num; i++)
1138     ptr->pieces[i] = data[i + 1] & 0x0f;
1139   order = data[0] & 0x0f;
1140   set_norm_piece((struct TBEntry_piece *)ptr, ptr->norm, ptr->pieces);
1141   tb_size[0] = calc_factors_piece(ptr->factor, ptr->num, order, ptr->norm, ptr->enc_type);
1142 }
1143
1144 static void setup_pieces_pawn(struct TBEntry_pawn *ptr, unsigned char *data, uint64 *tb_size, int f)
1145 {
1146   int i, j;
1147   int order, order2;
1148
1149   j = 1 + (ptr->pawns[1] > 0);
1150   order = data[0] & 0x0f;
1151   order2 = ptr->pawns[1] ? (data[1] & 0x0f) : 0x0f;
1152   for (i = 0; i < ptr->num; i++)
1153     ptr->file[f].pieces[0][i] = data[i + j] & 0x0f;
1154   set_norm_pawn(ptr, ptr->file[f].norm[0], ptr->file[f].pieces[0]);
1155   tb_size[0] = calc_factors_pawn(ptr->file[f].factor[0], ptr->num, order, order2, ptr->file[f].norm[0], f);
1156
1157   order = data[0] >> 4;
1158   order2 = ptr->pawns[1] ? (data[1] >> 4) : 0x0f;
1159   for (i = 0; i < ptr->num; i++)
1160     ptr->file[f].pieces[1][i] = data[i + j] >> 4;
1161   set_norm_pawn(ptr, ptr->file[f].norm[1], ptr->file[f].pieces[1]);
1162   tb_size[1] = calc_factors_pawn(ptr->file[f].factor[1], ptr->num, order, order2, ptr->file[f].norm[1], f);
1163 }
1164
1165 static void setup_pieces_pawn_dtz(struct DTZEntry_pawn *ptr, unsigned char *data, uint64 *tb_size, int f)
1166 {
1167   int i, j;
1168   int order, order2;
1169
1170   j = 1 + (ptr->pawns[1] > 0);
1171   order = data[0] & 0x0f;
1172   order2 = ptr->pawns[1] ? (data[1] & 0x0f) : 0x0f;
1173   for (i = 0; i < ptr->num; i++)
1174     ptr->file[f].pieces[i] = data[i + j] & 0x0f;
1175   set_norm_pawn((struct TBEntry_pawn *)ptr, ptr->file[f].norm, ptr->file[f].pieces);
1176   tb_size[0] = calc_factors_pawn(ptr->file[f].factor, ptr->num, order, order2, ptr->file[f].norm, f);
1177 }
1178
1179 static void calc_symlen(struct PairsData *d, int s, char *tmp)
1180 {
1181   int s1, s2;
1182
1183   ubyte* w = d->sympat + 3 * s;
1184   s2 = (w[2] << 4) | (w[1] >> 4);
1185   if (s2 == 0x0fff)
1186     d->symlen[s] = 0;
1187   else {
1188     s1 = ((w[1] & 0xf) << 8) | w[0];
1189     if (!tmp[s1]) calc_symlen(d, s1, tmp);
1190     if (!tmp[s2]) calc_symlen(d, s2, tmp);
1191     d->symlen[s] = d->symlen[s1] + d->symlen[s2] + 1;
1192   }
1193   tmp[s] = 1;
1194 }
1195
1196 ushort ReadUshort(ubyte* d) {
1197   return d[0] | (d[1] << 8);
1198 }
1199
1200 uint32 ReadUint32(ubyte* d) {
1201   return d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24);
1202 }
1203
1204 static struct PairsData *setup_pairs(unsigned char *data, uint64 tb_size, uint64 *size, unsigned char **next, ubyte *flags, int wdl)
1205 {
1206   struct PairsData *d;
1207   int i;
1208
1209   *flags = data[0];
1210   if (data[0] & 0x80) {
1211     d = (struct PairsData *)malloc(sizeof(struct PairsData));
1212     d->idxbits = 0;
1213     if (wdl)
1214       d->min_len = data[1];
1215     else
1216       d->min_len = 0;
1217     *next = data + 2;
1218     size[0] = size[1] = size[2] = 0;
1219     return d;
1220   }
1221
1222   int blocksize = data[1];
1223   int idxbits = data[2];
1224   int real_num_blocks = ReadUint32(&data[4]);
1225   int num_blocks = real_num_blocks + *(ubyte *)(&data[3]);
1226   int max_len = data[8];
1227   int min_len = data[9];
1228   int h = max_len - min_len + 1;
1229   int num_syms = ReadUshort(&data[10 + 2 * h]);
1230   d = (struct PairsData *)malloc(sizeof(struct PairsData) + (h - 1) * sizeof(base_t) + num_syms);
1231   d->blocksize = blocksize;
1232   d->idxbits = idxbits;
1233   d->offset = (ushort*)(&data[10]);
1234   d->symlen = ((ubyte *)d) + sizeof(struct PairsData) + (h - 1) * sizeof(base_t);
1235   d->sympat = &data[12 + 2 * h];
1236   d->min_len = min_len;
1237   *next = &data[12 + 2 * h + 3 * num_syms + (num_syms & 1)];
1238
1239   int num_indices = (tb_size + (1ULL << idxbits) - 1) >> idxbits;
1240   size[0] = 6ULL * num_indices;
1241   size[1] = 2ULL * num_blocks;
1242   size[2] = (1ULL << blocksize) * real_num_blocks;
1243
1244   // char tmp[num_syms];
1245   char tmp[4096];
1246   for (i = 0; i < num_syms; i++)
1247     tmp[i] = 0;
1248   for (i = 0; i < num_syms; i++)
1249     if (!tmp[i])
1250       calc_symlen(d, i, tmp);
1251
1252   d->base[h - 1] = 0;
1253   for (i = h - 2; i >= 0; i--)
1254     d->base[i] = (d->base[i + 1] + ReadUshort((ubyte*)(d->offset + i)) - ReadUshort((ubyte*)(d->offset + i + 1))) / 2;
1255   for (i = 0; i < h; i++)
1256     d->base[i] <<= 64 - (min_len + i);
1257
1258   d->offset -= d->min_len;
1259
1260   return d;
1261 }
1262
1263 static int init_table_wdl(struct TBEntry *entry, char *str)
1264 {
1265   ubyte *next;
1266   int f, s;
1267   uint64 tb_size[8];
1268   uint64 size[8 * 3];
1269   ubyte flags;
1270
1271   // first mmap the table into memory
1272
1273   entry->data = map_file(str, WDLSUFFIX, &entry->mapping);
1274   if (!entry->data) {
1275     printf("Could not find %s" WDLSUFFIX, str);
1276     return 0;
1277   }
1278
1279   ubyte *data = (ubyte *)entry->data;
1280   if (data[0] != WDL_MAGIC[0] ||
1281       data[1] != WDL_MAGIC[1] ||
1282       data[2] != WDL_MAGIC[2] ||
1283       data[3] != WDL_MAGIC[3]) {
1284     printf("Corrupted table.\n");
1285     unmap_file(entry->data, entry->mapping);
1286     entry->data = 0;
1287     return 0;
1288   }
1289
1290   int split = data[4] & 0x01;
1291   int files = data[4] & 0x02 ? 4 : 1;
1292
1293   data += 5;
1294
1295   if (!entry->has_pawns) {
1296     struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
1297     setup_pieces_piece(ptr, data, &tb_size[0]);
1298     data += ptr->num + 1;
1299     data += ((uintptr_t)data) & 0x01;
1300
1301     ptr->precomp[0] = setup_pairs(data, tb_size[0], &size[0], &next, &flags, 1);
1302     data = next;
1303     if (split) {
1304       ptr->precomp[1] = setup_pairs(data, tb_size[1], &size[3], &next, &flags, 1);
1305       data = next;
1306     } else
1307       ptr->precomp[1] = NULL;
1308
1309     ptr->precomp[0]->indextable = (char *)data;
1310     data += size[0];
1311     if (split) {
1312       ptr->precomp[1]->indextable = (char *)data;
1313       data += size[3];
1314     }
1315
1316     ptr->precomp[0]->sizetable = (ushort *)data;
1317     data += size[1];
1318     if (split) {
1319       ptr->precomp[1]->sizetable = (ushort *)data;
1320       data += size[4];
1321     }
1322
1323     data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1324     ptr->precomp[0]->data = data;
1325     data += size[2];
1326     if (split) {
1327       data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1328       ptr->precomp[1]->data = data;
1329     }
1330   } else {
1331     struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
1332     s = 1 + (ptr->pawns[1] > 0);
1333     for (f = 0; f < 4; f++) {
1334       setup_pieces_pawn((struct TBEntry_pawn *)ptr, data, &tb_size[2 * f], f);
1335       data += ptr->num + s;
1336     }
1337     data += ((uintptr_t)data) & 0x01;
1338
1339     for (f = 0; f < files; f++) {
1340       ptr->file[f].precomp[0] = setup_pairs(data, tb_size[2 * f], &size[6 * f], &next, &flags, 1);
1341       data = next;
1342       if (split) {
1343         ptr->file[f].precomp[1] = setup_pairs(data, tb_size[2 * f + 1], &size[6 * f + 3], &next, &flags, 1);
1344         data = next;
1345       } else
1346         ptr->file[f].precomp[1] = NULL;
1347     }
1348
1349     for (f = 0; f < files; f++) {
1350       ptr->file[f].precomp[0]->indextable = (char *)data;
1351       data += size[6 * f];
1352       if (split) {
1353         ptr->file[f].precomp[1]->indextable = (char *)data;
1354         data += size[6 * f + 3];
1355       }
1356     }
1357
1358     for (f = 0; f < files; f++) {
1359       ptr->file[f].precomp[0]->sizetable = (ushort *)data;
1360       data += size[6 * f + 1];
1361       if (split) {
1362         ptr->file[f].precomp[1]->sizetable = (ushort *)data;
1363         data += size[6 * f + 4];
1364       }
1365     }
1366
1367     for (f = 0; f < files; f++) {
1368       data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1369       ptr->file[f].precomp[0]->data = data;
1370       data += size[6 * f + 2];
1371       if (split) {
1372         data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1373         ptr->file[f].precomp[1]->data = data;
1374         data += size[6 * f + 5];
1375       }
1376     }
1377   }
1378
1379   return 1;
1380 }
1381
1382 static int init_table_dtz(struct TBEntry *entry)
1383 {
1384   ubyte *data = (ubyte *)entry->data;
1385   ubyte *next;
1386   int f, s;
1387   uint64 tb_size[4];
1388   uint64 size[4 * 3];
1389
1390   if (!data)
1391     return 0;
1392
1393   if (data[0] != DTZ_MAGIC[0] ||
1394       data[1] != DTZ_MAGIC[1] ||
1395       data[2] != DTZ_MAGIC[2] ||
1396       data[3] != DTZ_MAGIC[3]) {
1397     printf("Corrupted table.\n");
1398     return 0;
1399   }
1400
1401   int files = data[4] & 0x02 ? 4 : 1;
1402
1403   data += 5;
1404
1405   if (!entry->has_pawns) {
1406     struct DTZEntry_piece *ptr = (struct DTZEntry_piece *)entry;
1407     setup_pieces_piece_dtz(ptr, data, &tb_size[0]);
1408     data += ptr->num + 1;
1409     data += ((uintptr_t)data) & 0x01;
1410
1411     ptr->precomp = setup_pairs(data, tb_size[0], &size[0], &next, &(ptr->flags), 0);
1412     data = next;
1413
1414     ptr->map = data;
1415     if (ptr->flags & 2) {
1416       int i;
1417       for (i = 0; i < 4; i++) {
1418         ptr->map_idx[i] = (data + 1 - ptr->map);
1419         data += 1 + data[0];
1420       }
1421       data += ((uintptr_t)data) & 0x01;
1422     }
1423
1424     ptr->precomp->indextable = (char *)data;
1425     data += size[0];
1426
1427     ptr->precomp->sizetable = (ushort *)data;
1428     data += size[1];
1429
1430     data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1431     ptr->precomp->data = data;
1432     data += size[2];
1433   } else {
1434     struct DTZEntry_pawn *ptr = (struct DTZEntry_pawn *)entry;
1435     s = 1 + (ptr->pawns[1] > 0);
1436     for (f = 0; f < 4; f++) {
1437       setup_pieces_pawn_dtz(ptr, data, &tb_size[f], f);
1438       data += ptr->num + s;
1439     }
1440     data += ((uintptr_t)data) & 0x01;
1441
1442     for (f = 0; f < files; f++) {
1443       ptr->file[f].precomp = setup_pairs(data, tb_size[f], &size[3 * f], &next, &(ptr->flags[f]), 0);
1444       data = next;
1445     }
1446
1447     ptr->map = data;
1448     for (f = 0; f < files; f++) {
1449       if (ptr->flags[f] & 2) {
1450         int i;
1451         for (i = 0; i < 4; i++) {
1452           ptr->map_idx[f][i] = (data + 1 - ptr->map);
1453           data += 1 + data[0];
1454         }
1455       }
1456     }
1457     data += ((uintptr_t)data) & 0x01;
1458
1459     for (f = 0; f < files; f++) {
1460       ptr->file[f].precomp->indextable = (char *)data;
1461       data += size[3 * f];
1462     }
1463
1464     for (f = 0; f < files; f++) {
1465       ptr->file[f].precomp->sizetable = (ushort *)data;
1466       data += size[3 * f + 1];
1467     }
1468
1469     for (f = 0; f < files; f++) {
1470       data = (ubyte *)((((uintptr_t)data) + 0x3f) & ~0x3f);
1471       ptr->file[f].precomp->data = data;
1472       data += size[3 * f + 2];
1473     }
1474   }
1475
1476   return 1;
1477 }
1478
1479 template<bool LittleEndian>
1480 static ubyte decompress_pairs(struct PairsData *d, uint64 idx)
1481 {
1482   if (!d->idxbits)
1483     return d->min_len;
1484
1485   uint32 mainidx = idx >> d->idxbits;
1486   int litidx = (idx & ((1 << d->idxbits) - 1)) - (1 << (d->idxbits - 1));
1487   uint32 block = *(uint32 *)(d->indextable + 6 * mainidx);
1488   if (!LittleEndian)
1489     block = __builtin_bswap32(block);
1490
1491   ushort idxOffset = *(ushort *)(d->indextable + 6 * mainidx + 4);
1492   if (!LittleEndian)
1493     idxOffset = (idxOffset << 8) | (idxOffset >> 8);
1494   litidx += idxOffset;
1495
1496   if (litidx < 0) {
1497     do {
1498       litidx += d->sizetable[--block] + 1;
1499     } while (litidx < 0);
1500   } else {
1501     while (litidx > d->sizetable[block])
1502       litidx -= d->sizetable[block++] + 1;
1503   }
1504
1505   uint32 *ptr = (uint32 *)(d->data + (block << d->blocksize));
1506
1507   int m = d->min_len;
1508   ushort *offset = d->offset;
1509   base_t *base = d->base - m;
1510   ubyte *symlen = d->symlen;
1511   int sym, bitcnt;
1512
1513   uint64 code = *((uint64 *)ptr);
1514   if (LittleEndian)
1515     code = __builtin_bswap64(code);
1516
1517   ptr += 2;
1518   bitcnt = 0; // number of "empty bits" in code
1519   for (;;) {
1520     int l = m;
1521     while (code < base[l]) l++;
1522     sym = offset[l];
1523     if (!LittleEndian)
1524       sym = ((sym & 0xff) << 8) | (sym >> 8);
1525     sym += ((code - base[l]) >> (64 - l));
1526     if (litidx < (int)symlen[sym] + 1) break;
1527     litidx -= (int)symlen[sym] + 1;
1528     code <<= l;
1529     bitcnt += l;
1530     if (bitcnt >= 32) {
1531       bitcnt -= 32;
1532       uint32 tmp = *ptr++;
1533       if (LittleEndian)
1534         tmp = __builtin_bswap32(tmp);
1535       code |= ((uint64)tmp) << bitcnt;
1536      }
1537    }
1538
1539   ubyte *sympat = d->sympat;
1540   while (symlen[sym] != 0) {
1541     ubyte* w = sympat + (3 * sym);
1542     int s1 = ((w[1] & 0xf) << 8) | w[0];
1543     if (litidx < (int)symlen[s1] + 1)
1544       sym = s1;
1545     else {
1546       litidx -= (int)symlen[s1] + 1;
1547       sym = (w[2] << 4) | (w[1] >> 4);
1548     }
1549   }
1550
1551   return sympat[3 * sym];
1552 }
1553
1554 void load_dtz_table(char *str, uint64 key1, uint64 key2)
1555 {
1556   int i;
1557   struct TBEntry *ptr, *ptr3;
1558   struct TBHashEntry *ptr2;
1559
1560   DTZ_table[0].key1 = key1;
1561   DTZ_table[0].key2 = key2;
1562   DTZ_table[0].entry = NULL;
1563
1564   // find corresponding WDL entry
1565   ptr2 = TB_hash[key1 >> (64 - TBHASHBITS)];
1566   for (i = 0; i < HSHMAX; i++)
1567     if (ptr2[i].key == key1) break;
1568   if (i == HSHMAX) return;
1569   ptr = ptr2[i].ptr;
1570
1571   ptr3 = (struct TBEntry *)malloc(ptr->has_pawns
1572                                 ? sizeof(struct DTZEntry_pawn)
1573                                 : sizeof(struct DTZEntry_piece));
1574
1575   ptr3->data = map_file(str, DTZSUFFIX, &ptr3->mapping);
1576   ptr3->key = ptr->key;
1577   ptr3->num = ptr->num;
1578   ptr3->symmetric = ptr->symmetric;
1579   ptr3->has_pawns = ptr->has_pawns;
1580   if (ptr3->has_pawns) {
1581     struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *)ptr3;
1582     entry->pawns[0] = ((struct TBEntry_pawn *)ptr)->pawns[0];
1583     entry->pawns[1] = ((struct TBEntry_pawn *)ptr)->pawns[1];
1584   } else {
1585     struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr3;
1586     entry->enc_type = ((struct TBEntry_piece *)ptr)->enc_type;
1587   }
1588   if (!init_table_dtz(ptr3))
1589     free(ptr3);
1590   else
1591     DTZ_table[0].entry = ptr3;
1592 }
1593
1594 static void free_wdl_entry(struct TBEntry *entry)
1595 {
1596   unmap_file(entry->data, entry->mapping);
1597   if (!entry->has_pawns) {
1598     struct TBEntry_piece *ptr = (struct TBEntry_piece *)entry;
1599     free(ptr->precomp[0]);
1600     if (ptr->precomp[1])
1601       free(ptr->precomp[1]);
1602   } else {
1603     struct TBEntry_pawn *ptr = (struct TBEntry_pawn *)entry;
1604     int f;
1605     for (f = 0; f < 4; f++) {
1606       free(ptr->file[f].precomp[0]);
1607       if (ptr->file[f].precomp[1])
1608         free(ptr->file[f].precomp[1]);
1609     }
1610   }
1611 }
1612
1613 static void free_dtz_entry(struct TBEntry *entry)
1614 {
1615   unmap_file(entry->data, entry->mapping);
1616   if (!entry->has_pawns) {
1617     struct DTZEntry_piece *ptr = (struct DTZEntry_piece *)entry;
1618     free(ptr->precomp);
1619   } else {
1620     struct DTZEntry_pawn *ptr = (struct DTZEntry_pawn *)entry;
1621     int f;
1622     for (f = 0; f < 4; f++)
1623       free(ptr->file[f].precomp);
1624   }
1625   free(entry);
1626 }
1627
1628 static int wdl_to_map[5] = { 1, 3, 0, 2, 0 };
1629 static ubyte pa_flags[5] = { 8, 0, 0, 0, 4 };
1630