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