00001 #ifndef BMCONST__H__INCLUDED__
00002 #define BMCONST__H__INCLUDED__
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 namespace bm
00030 {
00031
00032 #if defined(_WIN32) || defined (_WIN64)
00033
00034 typedef unsigned __int64 id64_t;
00035
00036 #else
00037
00038 typedef unsigned long long id64_t;
00039
00040 #endif
00041
00042 typedef unsigned int id_t;
00043 typedef unsigned int word_t;
00044 typedef unsigned short short_t;
00045
00046
00047
00048 const unsigned id_max = 0xFFFFFFFF;
00049
00050
00051
00052 const unsigned set_block_size = 2048u;
00053 const unsigned set_block_shift = 16u;
00054 const unsigned set_block_mask = 0xFFFFu;
00055 const unsigned set_blkblk_mask = 0xFFFFFFu;
00056
00057 const unsigned set_block_plain_size = set_block_size / 32u;
00058 const unsigned set_block_plain_cnt = sizeof(bm::word_t) * 8u;
00059
00060
00061
00062 const unsigned set_word_shift = 5u;
00063 const unsigned set_word_mask = 0x1Fu;
00064
00065
00066
00067
00068 typedef unsigned short gap_word_t;
00069
00070 const unsigned gap_max_buff_len = 1280;
00071 const unsigned gap_max_bits = 65536;
00072 const unsigned gap_equiv_len =
00073 (sizeof(bm::word_t) * bm::set_block_size) / sizeof(gap_word_t);
00074 const unsigned gap_levels = 4;
00075 const unsigned gap_max_level = bm::gap_levels - 1;
00076
00077
00078
00079
00080 const unsigned set_array_size = 256u;
00081 const unsigned set_array_shift = 8u;
00082 const unsigned set_array_mask = 0xFFu;
00083 const unsigned set_total_blocks = (bm::set_array_size * bm::set_array_size);
00084
00085 const unsigned bits_in_block = bm::set_block_size * sizeof(bm::word_t) * 8;
00086 const unsigned bits_in_array = bm::bits_in_block * bm::set_array_size;
00087
00088
00089 #ifdef BM64OPT
00090
00091 typedef id64_t wordop_t;
00092 const id64_t all_bits_mask = 0xffffffffffffffff;
00093
00094 # define DECLARE_TEMP_BLOCK(x) bm::id64_t x[bm::set_block_size / 2];
00095 const unsigned set_block_size_op = bm::set_block_size / 2;
00096
00097
00098 #else
00099
00100 typedef word_t wordop_t;
00101 const word_t all_bits_mask = 0xffffffff;
00102
00103 # define DECLARE_TEMP_BLOCK(x) unsigned x[bm::set_block_size];
00104 const unsigned set_block_size_op = bm::set_block_size;
00105
00106 #endif
00107
00108
00109
00110
00111
00112
00113
00114 enum strategy
00115 {
00116 BM_BIT = 0,
00117 BM_GAP = 1
00118 };
00119
00120
00121
00122
00123
00124
00125 enum set_representation
00126 {
00127 set_bitset = 0,
00128 set_gap = 1,
00129 set_array1 = 2,
00130 set_array0 = 3
00131 };
00132
00133 template<bool T> struct DeBruijn_bit_position
00134 {
00135 static const unsigned _multiply[32];
00136 };
00137
00138 template<bool T>
00139 const unsigned DeBruijn_bit_position<T>::_multiply[32] = {
00140 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
00141 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
00142 };
00143
00144
00145
00146
00147 template<bool T> struct first_bit_table
00148 {
00149 static const char _idx[256];
00150 };
00151
00152 template<bool T>
00153 const char first_bit_table<T>::_idx[256] = {
00154 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
00155 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
00156 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
00157 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
00158 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00159 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00160 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00161 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00162 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00163 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00164 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00165 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00166 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00167 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00168 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00169 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00170 };
00171
00172
00173
00174
00175
00176
00177
00178
00179 template<bool T> struct bit_count_table
00180 {
00181 static const unsigned char _count[256];
00182 };
00183
00184 template<bool T>
00185 const unsigned char bit_count_table<T>::_count[256] = {
00186 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
00187 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00188 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00189 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00190 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00191 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00192 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00193 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
00194 };
00195
00196
00197 }
00198
00199 #endif
00200