forked from psanse/BITSCAN
-
Notifications
You must be signed in to change notification settings - Fork 0
/
tables.h
117 lines (94 loc) · 3.55 KB
/
tables.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/*
* tables.h file from the BITSCAN library, a C++ library for bit
* sets optimization. It has been used to implement BBMC, a very
* succesful bit-parallel algorithm for exact maximum clique.
* (see license file for references)
*
* Copyright (C)
* Author: Pablo San Segundo
* Intelligent Control Research Group (CSIC-UPM)
*
* Permission to use, modify and distribute this software is
* granted provided that this copyright notice appears in all
* copies, in source code or in binaries. For precise terms
* see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any
* kind, express or implied, and with no claim as to its
* suitability for any purpose.
*/
#ifndef __TABLES_H__
#define __TABLES_H__
#include "bbtypes.h"
#include "config.h"
#define MASK_LIM WORD_SIZE+1 //mask limit for bitscan operations of a single BITBOARD
#ifdef CACHED_INDEX_OPERATIONS
#define WDIV(i) (Tables::t_wdindex[(i)])
#define WMOD(i) (Tables::t_wmodindex[(i)])
#define WMUL(i) (Tables::t_wxindex[(i)])
#else
#define WDIV(i) ((i)/WORD_SIZE)
#define WMOD(i) ((i)%WORD_SIZE)
#define WMUL(i) ((i)*WORD_SIZE)
#endif
////////////////////
//MACROS for mapping bit index to bitblock index (0 or 1 based)
#define INDEX_0TO0(p) (WDIV(p)) //p>0
#define INDEX_0TO1(p) (WDIV(p)+1) //p>0
#define INDEX_1TO1(p) ((((p)-1)/WORD_SIZE)+1) //p>0
#define INDEX_1TO0(p) ((((p)-1)/WORD_SIZE)) //p>0
class Tables{
friend class BitBoard;
friend class BitBoardN;
private:
Tables(){};
virtual ~Tables(){};
public:
static int InitAllTables(); //Driver for all inits
private:
static void init_masks();
static void init_popc8();
static void init_popc();
static void init_mlsb();
static void init_lsb_l(); //Conditioned to EXTENDED_LOOKUPS
//Table
static void init_cached_index(); //Conditioned to CACHED_INDEX_OPERATIONS
////////////////////////////////////////
//data members
public:
//commonly used tables
static BITBOARD mask[64]; //masks for 64 bit block of a single bit
static U8 mask8[8]; //masks for 8 bit block of a single bit
static BITBOARD mask_right[65]; //1_bit to the right of index (less significant bits, excluding index)
static BITBOARD mask_left[66]; //1_bit to the left of index (more significant bits, excluding index)
//private:
static BITBOARD mask_entre[64/*a*/][64/*b*/]; //1-bits between intervals (a<=b)
//0 but word masks
static BITBOARD mask0_1W;
static BITBOARD mask0_2W;
static BITBOARD mask0_3W;
static BITBOARD mask0_4W;
static int pc[65536]; //16 bit population count
static int lsb[65536]; //LSB lookup table 16 bits
static int lsba[4][65536]; //LSB lookup table 16 bits con pos indes
static int msba[4][65536]; //MSB lookup table 16 bits con pos indes
static int pc8[256]; //population count for 8 bits
static int pc_sa[65536]; //populaton count for 16 bits (Shift + Add)
static int msb[65536]; //MSB for 16 bits
#ifdef EXTENDED_LOOKUPS
static int lsb_l[65536][16]; //LSB for 16 bits list of position of 1-bits)
#endif
////////////////////////
//magic number tables
static const int T_32[37]; //32 bits
static const int T_64[67]; //64 bits
static const int indexDeBruijn64_ISOL[64]; //bit scan with b&(-b)
static const int indexDeBruijn64_SEP[64]; //bit scan with b^(b-1)
//64 bit block index cache
#ifdef CACHED_INDEX_OPERATIONS
static int t_wdindex[MAX_CACHED_INDEX];
static int t_wxindex[MAX_CACHED_INDEX];
static int t_wmodindex[MAX_CACHED_INDEX];
#endif
};
#endif