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