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