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