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