BitMagicC++Library
bmconst.h
Go to the documentation of this file.
1 #ifndef BMCONST__H__INCLUDED__
2 #define BMCONST__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 namespace bm
22 {
23 
24 #if defined(_WIN32) || defined (_WIN64)
25 
26 typedef unsigned __int64 id64_t;
27 
28 #else
29 
30 typedef unsigned long long int id64_t;
31 
32 #endif
33 
34 typedef unsigned int id_t;
35 typedef unsigned int word_t;
36 typedef unsigned short short_t;
37 
38 
39 
40 const unsigned id_max = 0xFFFFFFFF;
41 
42 // Data Block parameters
43 
44 const unsigned set_block_size = 2048u;
45 const unsigned set_block_shift = 16u;
46 const unsigned set_block_mask = 0xFFFFu;
47 const unsigned set_blkblk_mask = 0xFFFFFFu;
48 
49 const unsigned set_block_plain_size = set_block_size / 32u;
50 const unsigned set_block_plain_cnt = (unsigned)(sizeof(bm::word_t) * 8u);
51 
52 // Word parameters
53 
54 const unsigned set_word_shift = 5u;
55 const unsigned set_word_mask = 0x1Fu;
56 
57 
58 // GAP related parameters.
59 
60 typedef unsigned short gap_word_t;
61 
62 const unsigned gap_max_buff_len = 1280;
63 const unsigned gap_max_bits = 65536;
64 const unsigned gap_equiv_len = (unsigned)
65  ((sizeof(bm::word_t) * bm::set_block_size) / sizeof(gap_word_t));
66 const unsigned gap_levels = 4;
67 const unsigned gap_max_level = bm::gap_levels - 1;
68 
69 
70 // Block Array parameters
71 
72 const unsigned set_array_size = 256u;
73 const unsigned set_array_shift = 8u;
74 const unsigned set_array_mask = 0xFFu;
76 
77 const unsigned bits_in_block = bm::set_block_size * (unsigned)(sizeof(bm::word_t) * 8);
79 
80 
81 #if defined(BM64OPT) || defined(BM64_SSE4)
82 
83 typedef id64_t wordop_t;
84 const id64_t all_bits_mask = 0xffffffffffffffff;
86 
87 #else
88 
89 typedef word_t wordop_t;
90 const word_t all_bits_mask = 0xffffffff;
91 const unsigned set_block_size_op = bm::set_block_size;
92 
93 #endif
94 
95 # define BM_DECLARE_TEMP_BLOCK(x) unsigned BM_VECT_ALIGN x[bm::set_block_size] BM_VECT_ALIGN_ATTR;
96 
97 
98 /*!
99  @brief Block allocation strategies.
100  @ingroup bvector
101 */
103 {
104  BM_BIT = 0, //!< No GAP compression strategy. All new blocks are bit blocks.
105  BM_GAP = 1 //!< GAP compression is ON.
106 };
107 
108 
109 /*!
110  @brief set representation variants
111  @internal
112 */
114 {
115  set_bitset = 0, //!< Simple bitset
116  set_gap = 1, //!< GAP-RLE compression
117  set_array1 = 2, //!< array of set 1 values
118  set_array0 = 3 //!< array of 0 values
119 };
120 
121 /**
122  Internal structure. Copyright information.
123 */
124 template<bool T> struct _copyright
125 {
126  static const char _p[];
127  static const unsigned _v[3];
128 };
129 
130 template<bool T> const char _copyright<T>::_p[] =
131  "BitMagic C++ Library. v.3.10.1 (c) 2002-2017 Anatoliy Kuznetsov.";
132 template<bool T> const unsigned _copyright<T>::_v[3] = {3, 9, 0};
133 
134 
135 template<bool T> struct DeBruijn_bit_position
136 {
137  static const unsigned _multiply[32];
138 };
139 
140 template<bool T>
141 const unsigned DeBruijn_bit_position<T>::_multiply[32] = {
142  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
143  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
144 };
145 
146 /** Structure keeps index of first right 1 bit for every byte.
147  @ingroup bitfunc
148 */
149 template<bool T> struct first_bit_table
150 {
151  static const signed char _idx[256];
152 };
153 
154 template<bool T>
155 const signed char first_bit_table<T>::_idx[256] = {
156  -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
157  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
158  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
159  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
160  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
161  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
162  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
163  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
164  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
165  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
166  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
167  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
168  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
169  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
170  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
171  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
172 };
173 
174 //---------------------------------------------------------------------
175 
176 /** Structure to aid in counting bits
177  table contains count of bits in 0-255 diapason of numbers
178 
179  @ingroup bitfunc
180 */
181 template<bool T> struct bit_count_table
182 {
183  static const unsigned char _count[256];
184 };
185 
186 template<bool T>
187 const unsigned char bit_count_table<T>::_count[256] = {
188  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,
189  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,
190  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,
191  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,
192  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,
193  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,
194  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,
195  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
196 };
197 
198 //---------------------------------------------------------------------
199 
200 /** Structure keeps all-left/right ON bits masks.
201  @ingroup bitfunc
202 */
203 template<bool T> struct block_set_table
204 {
205  static const unsigned _left[32];
206  static const unsigned _right[32];
207 };
208 
209 template<bool T>
210 const unsigned block_set_table<T>::_left[32] = {
211  0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff, 0x7ff,
212  0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff, 0x1ffff, 0x3ffff, 0x7ffff,
213  0xfffff, 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff, 0x1ffffff, 0x3ffffff,
214  0x7ffffff, 0xfffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff
215 };
216 
217 template<bool T>
218 const unsigned block_set_table<T>::_right[32] = {
219  0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8, 0xfffffff0,
220  0xffffffe0, 0xffffffc0, 0xffffff80, 0xffffff00, 0xfffffe00,
221  0xfffffc00, 0xfffff800, 0xfffff000, 0xffffe000, 0xffffc000,
222  0xffff8000, 0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
223  0xfff00000, 0xffe00000, 0xffc00000, 0xff800000, 0xff000000,
224  0xfe000000, 0xfc000000, 0xf8000000, 0xf0000000, 0xe0000000,
225  0xc0000000, 0x80000000
226 };
227 
228 //---------------------------------------------------------------------
229 
230 
231 
232 /*! @brief Default GAP lengths table.
233  @ingroup gapfunc
234 */
235 template<bool T> struct gap_len_table
236 {
237  static const gap_word_t _len[bm::gap_levels];
238 };
239 
240 template<bool T>
241 const gap_word_t gap_len_table<T>::_len[bm::gap_levels] =
242  { 128, 256, 512, bm::gap_max_buff_len };
243 
244 
245 /*! @brief Alternative GAP lengths table.
246  Good for for memory saver mode and very sparse bitsets.
247 
248  @ingroup gapfunc
249 */
250 template<bool T> struct gap_len_table_min
251 {
252  static const gap_word_t _len[bm::gap_levels];
253 };
254 
255 template<bool T>
256 const gap_word_t gap_len_table_min<T>::_len[bm::gap_levels] =
257  { 32, 96, 128, 512 };
258 
259 
260 /*! @brief Non-linear size growth GAP lengths table.
261  @ingroup gapfunc
262 */
263 template<bool T> struct gap_len_table_nl
264 {
265  static const gap_word_t _len[bm::gap_levels];
266 };
267 
268 template<bool T>
269 const gap_word_t gap_len_table_nl<T>::_len[bm::gap_levels] =
270  { 32, 128, 512, bm::gap_max_buff_len };
271 
272 /*!
273  @brief codes for supported SIMD optimizations
274  @internal
275 */
277 {
278  simd_none = 0, ///!< No SIMD or any other optimization
279  simd_sse2 = 1, ///!< Intel SSE2
280  simd_sse42 = 2, ///!< Intel SSE4.2
281  simd_avx2 = 5 ///!< Intel AVX2
282 };
283 
284 
285 
286 } // namespace
287 
288 #endif
289 
Structure keeps all-left/right ON bits masks.
Definition: bmconst.h:203
!< Intel SSE4.2
Definition: bmconst.h:281
const unsigned set_block_size
Definition: bmconst.h:44
Alternative GAP lengths table. Good for for memory saver mode and very sparse bitsets.
Definition: bmconst.h:250
const unsigned set_word_shift
Definition: bmconst.h:54
const unsigned set_array_shift
Definition: bmconst.h:73
GAP-RLE compression.
Definition: bmconst.h:116
unsigned long long int id64_t
Definition: bmconst.h:30
Simple bitset.
Definition: bmconst.h:115
Definition: bm.h:59
const unsigned gap_equiv_len
Definition: bmconst.h:64
array of set 1 values
Definition: bmconst.h:117
GAP compression is ON.
Definition: bmconst.h:105
const unsigned id_max
Definition: bmconst.h:40
Non-linear size growth GAP lengths table.
Definition: bmconst.h:263
const unsigned gap_max_level
Definition: bmconst.h:67
unsigned int word_t
Definition: bmconst.h:35
const unsigned gap_max_buff_len
Definition: bmconst.h:62
No GAP compression strategy. All new blocks are bit blocks.
Definition: bmconst.h:104
unsigned short short_t
Definition: bmconst.h:36
!< Intel SSE2
Definition: bmconst.h:280
const unsigned gap_levels
Definition: bmconst.h:66
Default GAP lengths table.
Definition: bmconst.h:235
const unsigned set_array_mask
Definition: bmconst.h:74
unsigned short gap_word_t
Definition: bmconst.h:60
!< No SIMD or any other optimization
Definition: bmconst.h:279
const unsigned bits_in_array
Definition: bmconst.h:78
const unsigned set_blkblk_mask
Definition: bmconst.h:47
const unsigned bits_in_block
Definition: bmconst.h:77
const unsigned set_block_size_op
Definition: bmconst.h:85
const unsigned gap_max_bits
Definition: bmconst.h:63
Structure to aid in counting bits table contains count of bits in 0-255 diapason of numbers...
Definition: bmconst.h:181
const unsigned set_block_plain_cnt
Definition: bmconst.h:50
const unsigned set_block_mask
Definition: bmconst.h:46
const unsigned set_array_size
Definition: bmconst.h:72
const unsigned set_word_mask
Definition: bmconst.h:55
unsigned int id_t
Definition: bmconst.h:34
const unsigned set_total_blocks
Definition: bmconst.h:75
id64_t wordop_t
Definition: bmconst.h:83
const unsigned set_block_plain_size
Definition: bmconst.h:49
const unsigned set_block_shift
Definition: bmconst.h:45
strategy
Block allocation strategies.
Definition: bmconst.h:102
set_representation
set representation variants
Definition: bmconst.h:113
const id64_t all_bits_mask
Definition: bmconst.h:84
Structure keeps index of first right 1 bit for every byte.
Definition: bmconst.h:149
array of 0 values
Definition: bmconst.h:118
simd_codes
codes for supported SIMD optimizations
Definition: bmconst.h:276