BitMagic-C++
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 /*! \file bmconst.h
22  \brief Constants, tables and typedefs
23  @internal
24 */
25 
26 namespace bm
27 {
28 
29 #if defined(_WIN32) || defined (_WIN64)
30 typedef unsigned __int64 id64_t;
31 #else
32 typedef unsigned long long int id64_t;
33 #endif
34 
35 typedef unsigned int id_t;
36 typedef unsigned int word_t;
37 typedef unsigned short short_t;
38 
39 #ifndef BM_DEFAULT_POOL_SIZE
40 # define BM_DEFAULT_POOL_SIZE 4096
41 #endif
42 
43 
44 const unsigned id_max = 0xFFFFFFFF;
45 
46 // Data Block parameters
47 
48 const unsigned set_block_size = 2048u;
49 const unsigned set_block_shift = 16u;
50 const unsigned set_block_mask = 0xFFFFu;
51 const unsigned set_blkblk_mask = 0xFFFFFFu;
52 
53 // set block size in bytes
54 const unsigned set_block_alloc_size = bm::set_block_size * unsigned(sizeof(bm::word_t));
55 
57 const unsigned set_block_plain_cnt = (unsigned)(sizeof(bm::word_t) * 8u);
58 
60 const unsigned set_block_digest_pos_shift = 10;
61 
62 // Word parameters
63 
64 const unsigned set_word_shift = 5u;
65 const unsigned set_word_mask = 0x1Fu;
66 
67 
68 // GAP related parameters.
69 
70 typedef unsigned short gap_word_t;
71 
72 const unsigned gap_max_buff_len = 1280;
73 const unsigned gap_max_bits = 65536;
74 const unsigned gap_equiv_len = (unsigned)
75  ((sizeof(bm::word_t) * bm::set_block_size) / sizeof(gap_word_t));
76 const unsigned gap_levels = 4;
77 const unsigned gap_max_level = bm::gap_levels - 1;
78 
79 
80 // Block Array parameters
81 
82 const unsigned set_array_size = 256u;
83 const unsigned set_array_shift = 8u;
84 const unsigned set_array_mask = 0xFFu;
86 
87 const unsigned bits_in_block = bm::set_block_size * (unsigned)(sizeof(bm::word_t) * 8);
89 
90 // Rank-Select parameters
91 const unsigned rs3_border0 = 21824; // 682 words by 32-bits
92 const unsigned rs3_border1 = (rs3_border0 * 2); // 43648
93 const unsigned rs3_half_span = rs3_border0 / 2;
94 
95 // misc parameters for sparse vec algorithms
96 const unsigned sub_block3_size = bm::gap_max_bits / 4;
97 
98 
99 #if defined(BM64OPT) || defined(BM64_SSE4)
100 
101 typedef id64_t wordop_t;
102 const id64_t all_bits_mask = 0xffffffffffffffff;
104 
105 #else
106 
107 typedef word_t wordop_t;
108 const word_t all_bits_mask = 0xffffffff;
109 const unsigned set_block_size_op = bm::set_block_size;
110 
111 #endif
112 
113 
114 /*!
115  @brief Block allocation strategies.
116  @ingroup bvector
117 */
119 {
120  BM_BIT = 0, //!< No GAP compression strategy. All new blocks are bit blocks.
121  BM_GAP = 1 //!< GAP compression is ON.
122 };
123 
124 
125 /**
126  Codes of set operations
127  @ingroup bvector
128 */
130 {
131  set_AND = 0,
132  set_OR = 1,
133  set_SUB = 2,
134  set_XOR = 3,
144 
146 };
147 
148 /**
149  Bit operations
150  @ingroup bvector
151 */
153 {
158 };
159 
160 
161 /*!
162  @brief Sort order declaration
163  @ingroup bvector
164 */
166 {
167  BM_UNSORTED = 0, //!< input set is NOT sorted
168  BM_SORTED = 1, //!< input set is sorted (ascending order)
169  BM_SORTED_UNIFORM = 2, //!< sorted and in one block (internal!)
170  BM_UNKNOWN = 3 //!< sort order unknown
171 };
172 
173 
174 /*!
175  @brief set representation variants
176  @internal
177 */
179 {
180  set_bitset = 0, //!< Simple bitset
181  set_gap = 1, //!< GAP-RLE compression
182  set_array1 = 2, //!< array of set 1 values
183  set_array0 = 3 //!< array of 0 values
184 };
185 
186 /*!
187  @brief NULL-able value support
188  @ingroup bvector
189 */
191 {
192  use_null = 0, //!< support "non-assigned" or "NULL" logic
193  no_null = 1 //!< do not support NULL values
194 };
195 
196 
197 /**
198  Internal structure. Copyright information.
199  @internal
200 */
201 template<bool T> struct _copyright
202 {
203  static const char _p[];
204  static const unsigned _v[3];
205 };
206 
207 template<bool T> const char _copyright<T>::_p[] =
208  "BitMagic C++ Library. v.3.20.0 (c) 2002-2019 Anatoliy Kuznetsov.";
209 template<bool T> const unsigned _copyright<T>::_v[3] = {3, 20, 0};
210 
211 
212 
213 /**
214  DeBruijn majic table
215  @internal
216 */
217 template<bool T> struct DeBruijn_bit_position
218 {
219  static const unsigned _multiply[32];
220 };
221 
222 template<bool T>
223 const unsigned DeBruijn_bit_position<T>::_multiply[32] = {
224  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
225  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
226 };
227 
228 /**
229  Structure keeps index of first right 1 bit for every byte.
230  @ingroup bitfunc
231 */
232 template<bool T> struct first_bit_table
233 {
234  static const signed char _idx[256];
235 };
236 
237 template<bool T>
238 const signed char first_bit_table<T>::_idx[256] = {
239  -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
240  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
241  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
242  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
243  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
244  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
245  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
246  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
247  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
248  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
249  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
250  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
251  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
252  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
253  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
254  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
255 };
256 
257 //---------------------------------------------------------------------
258 
259 /** Structure to aid in counting bits
260  table contains count of bits in 0-255 diapason of numbers
261 
262  @ingroup bitfunc
263 */
264 template<bool T> struct bit_count_table
265 {
266  static const unsigned char _count[256];
267 };
268 
269 template<bool T>
270 const unsigned char bit_count_table<T>::_count[256] = {
271  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,
272  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,
273  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,
274  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,
275  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,
276  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,
277  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,
278  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
279 };
280 
281 //---------------------------------------------------------------------
282 
283 /** Structure for LZCNT constants (4-bit)
284  @ingroup bitfunc
285 */
286 template<bool T> struct lzcnt_table
287 {
288  static unsigned char const _lut[16];
289 };
290 
291 template<bool T>
292 const unsigned char lzcnt_table<T>::_lut[16] =
293 {
294  32U, 31U, 30U, 30U, 29U, 29U, 29U, 29U,
295  28U, 28U, 28U, 28U, 28U, 28U, 28U, 28U
296 };
297 
298 /** Structure for TZCNT constants
299  @ingroup bitfunc
300 */
301 template<bool T> struct tzcnt_table
302 {
303  static unsigned char const _lut[37];
304 };
305 
306 template<bool T>
307 const unsigned char tzcnt_table<T>::_lut[37] =
308 {
309  32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11,
310  0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0,
311  21, 14, 9, 5, 20, 8, 19, 18
312 };
313 
314 
315 
316 /** Structure keeps all-left/right ON bits masks.
317  @ingroup bitfunc
318 */
319 template<bool T> struct block_set_table
320 {
321  static const unsigned _left[32];
322  static const unsigned _right[32];
323 };
324 
325 template<bool T>
326 const unsigned block_set_table<T>::_left[32] = {
327  0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff, 0x7ff,
328  0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff, 0x1ffff, 0x3ffff, 0x7ffff,
329  0xfffff, 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff, 0x1ffffff, 0x3ffffff,
330  0x7ffffff, 0xfffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff, 0xffffffff
331 };
332 
333 template<bool T>
334 const unsigned block_set_table<T>::_right[32] = {
335  0xffffffff, 0xfffffffe, 0xfffffffc, 0xfffffff8, 0xfffffff0,
336  0xffffffe0, 0xffffffc0, 0xffffff80, 0xffffff00, 0xfffffe00,
337  0xfffffc00, 0xfffff800, 0xfffff000, 0xffffe000, 0xffffc000,
338  0xffff8000, 0xffff0000, 0xfffe0000, 0xfffc0000, 0xfff80000,
339  0xfff00000, 0xffe00000, 0xffc00000, 0xff800000, 0xff000000,
340  0xfe000000, 0xfc000000, 0xf8000000, 0xf0000000, 0xe0000000,
341  0xc0000000, 0x80000000
342 };
343 
344 //---------------------------------------------------------------------
345 
346 
347 
348 /*! @brief Default GAP lengths table.
349  @ingroup gapfunc
350 */
351 template<bool T> struct gap_len_table
352 {
353  static const gap_word_t _len[bm::gap_levels];
354 };
355 
356 template<bool T>
357 const gap_word_t gap_len_table<T>::_len[bm::gap_levels] =
358  { 128, 256, 512, bm::gap_max_buff_len };
359 
360 
361 /*! @brief Alternative GAP lengths table.
362  Good for for memory saver mode and very sparse bitsets.
363 
364  @ingroup gapfunc
365 */
366 template<bool T> struct gap_len_table_min
367 {
368  static const gap_word_t _len[bm::gap_levels];
369 };
370 
371 template<bool T>
372 const gap_word_t gap_len_table_min<T>::_len[bm::gap_levels] =
373  { 32, 96, 128, 512 };
374 
375 
376 /*! @brief Non-linear size growth GAP lengths table.
377  @ingroup gapfunc
378 */
379 template<bool T> struct gap_len_table_nl
380 {
381  static const gap_word_t _len[bm::gap_levels];
382 };
383 
384 template<bool T>
385 const gap_word_t gap_len_table_nl<T>::_len[bm::gap_levels] =
386  { 32, 128, 512, bm::gap_max_buff_len };
387 
388 /*!
389  @brief codes for supported SIMD optimizations
390 */
392 {
393  simd_none = 0, ///!< No SIMD or any other optimization
394  simd_sse2 = 1, ///!< Intel SSE2
395  simd_sse42 = 2, ///!< Intel SSE4.2
396  simd_avx2 = 5, ///!< Intel AVX2
397  simd_avx512 = 6 ///!< Intel AVX512
398 };
399 
400 
401 /*!
402  \brief Byte orders recognized by the library.
403  @internal
404 */
406 {
409 };
410 
411 /**
412  Internal structure. Different global settings.
413  @internal
414 */
415 template<bool T> struct globals
416 {
417  struct bo
418  {
420 
421  bo()
422  {
423  unsigned x;
424  unsigned char *s = (unsigned char *)&x;
425  s[0] = 1; s[1] = 2; s[2] = 3; s[3] = 4;
426  if(x == 0x04030201)
427  {
428  _byte_order = LittleEndian;
429  return;
430  }
431  if(x == 0x01020304)
432  {
433  _byte_order = BigEndian;
434  return;
435  }
436  _byte_order = LittleEndian;
437  }
438  };
439 
440  static bo _bo;
441  static ByteOrder byte_order() { return _bo._byte_order; }
442 };
443 template<bool T> typename globals<T>::bo globals<T>::_bo;
444 
445 
446 } // namespace
447 
448 #endif
449 
Structure keeps all-left/right ON bits masks.
Definition: bmconst.h:319
!< Intel SSE4.2
Definition: bmconst.h:396
const unsigned set_block_size
Definition: bmconst.h:48
Structure for TZCNT constants.
Definition: bmconst.h:301
Alternative GAP lengths table. Good for for memory saver mode and very sparse bitsets.
Definition: bmconst.h:366
const unsigned set_word_shift
Definition: bmconst.h:64
const unsigned set_block_digest_pos_shift
Definition: bmconst.h:60
const unsigned set_array_shift
Definition: bmconst.h:83
operation
Bit operations.
Definition: bmconst.h:152
GAP-RLE compression.
Definition: bmconst.h:181
unsigned long long int id64_t
Definition: bmconst.h:32
Simple bitset.
Definition: bmconst.h:180
ByteOrder _byte_order
Definition: bmconst.h:419
Definition: bm.h:69
const unsigned gap_equiv_len
Definition: bmconst.h:74
array of set 1 values
Definition: bmconst.h:182
GAP compression is ON.
Definition: bmconst.h:121
do not support NULL values
Definition: bmconst.h:193
const unsigned id_max
Definition: bmconst.h:44
const unsigned rs3_border1
Definition: bmconst.h:92
const unsigned rs3_border0
Definition: bmconst.h:91
sort order unknown
Definition: bmconst.h:170
null_support
NULL-able value support.
Definition: bmconst.h:190
Non-linear size growth GAP lengths table.
Definition: bmconst.h:379
input set is sorted (ascending order)
Definition: bmconst.h:168
sort_order
Sort order declaration.
Definition: bmconst.h:165
const unsigned gap_max_level
Definition: bmconst.h:77
unsigned int word_t
Definition: bmconst.h:36
const unsigned sub_block3_size
Definition: bmconst.h:96
static bo _bo
Definition: bmconst.h:440
support "non-assigned" or "NULL" logic
Definition: bmconst.h:192
const unsigned gap_max_buff_len
Definition: bmconst.h:72
No GAP compression strategy. All new blocks are bit blocks.
Definition: bmconst.h:120
unsigned short short_t
Definition: bmconst.h:37
!< Intel SSE2
Definition: bmconst.h:395
static ByteOrder byte_order()
Definition: bmconst.h:441
const unsigned gap_levels
Definition: bmconst.h:76
!< Intel AVX2
Definition: bmconst.h:397
Default GAP lengths table.
Definition: bmconst.h:351
const unsigned set_array_mask
Definition: bmconst.h:84
Internal structure.
Definition: bmconst.h:415
unsigned short gap_word_t
Definition: bmconst.h:70
!< No SIMD or any other optimization
Definition: bmconst.h:394
const unsigned bits_in_array
Definition: bmconst.h:88
const unsigned set_blkblk_mask
Definition: bmconst.h:51
const unsigned rs3_half_span
Definition: bmconst.h:93
set_operation
Codes of set operations.
Definition: bmconst.h:129
const unsigned bits_in_block
Definition: bmconst.h:87
const unsigned set_block_size_op
Definition: bmconst.h:103
const unsigned gap_max_bits
Definition: bmconst.h:73
Structure to aid in counting bits table contains count of bits in 0-255 diapason of numbers...
Definition: bmconst.h:264
const unsigned set_block_plain_cnt
Definition: bmconst.h:57
const unsigned set_block_mask
Definition: bmconst.h:50
const unsigned set_array_size
Definition: bmconst.h:82
const unsigned set_word_mask
Definition: bmconst.h:65
Structure for LZCNT constants (4-bit)
Definition: bmconst.h:286
unsigned int id_t
Definition: bmconst.h:35
input set is NOT sorted
Definition: bmconst.h:167
const unsigned set_total_blocks
Definition: bmconst.h:85
id64_t wordop_t
Definition: bmconst.h:101
const unsigned set_block_plain_size
Definition: bmconst.h:56
const unsigned set_block_shift
Definition: bmconst.h:49
strategy
Block allocation strategies.
Definition: bmconst.h:118
set_representation
set representation variants
Definition: bmconst.h:178
DeBruijn majic table.
Definition: bmconst.h:217
ByteOrder
Byte orders recognized by the library.
Definition: bmconst.h:405
const id64_t all_bits_mask
Definition: bmconst.h:102
sorted and in one block (internal!)
Definition: bmconst.h:169
Structure keeps index of first right 1 bit for every byte.
Definition: bmconst.h:232
array of 0 values
Definition: bmconst.h:183
simd_codes
codes for supported SIMD optimizations
Definition: bmconst.h:391
const unsigned set_block_alloc_size
Definition: bmconst.h:54
const unsigned set_block_digest_wave_size
Definition: bmconst.h:59