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