BitMagic-C++
Data Structures | Typedefs | Enumerations | Functions | Variables
bm Namespace Reference

Data Structures

struct  _copyright
 Internal structure. More...
 
class  aggregator
 Algorithms for fast aggregation of a group of bit-vectors. More...
 
struct  all_set
 Structure carries pointer on bit block with all bits 1. More...
 
class  alloc_pool
 Allocation pool object. More...
 
struct  and_func
 and functor More...
 
class  base_sparse_vector
 Base class for bit-transposed sparse vector construction. More...
 
class  basic_bmatrix
 Basic dense bit-matrix class. More...
 
struct  bit_AND
 Bit AND functor. More...
 
struct  bit_ASSIGN
 Bit ASSIGN functor. More...
 
struct  bit_block_t
 bit-block array wrapped into union for correct interpretation of 32-bit vs 64-bit access vs SIMD More...
 
struct  bit_COUNT
 Bit COUNT functor. More...
 
struct  bit_COUNT_A
 Bit COUNT A functor. More...
 
struct  bit_COUNT_AND
 Bit COUNT AND functor. More...
 
struct  bit_COUNT_B
 Bit COUNT B functor. More...
 
struct  bit_COUNT_OR
 Bit COUNT OR functor. More...
 
struct  bit_COUNT_SUB_AB
 Bit COUNT SUB AB functor. More...
 
struct  bit_COUNT_SUB_BA
 Bit SUB BA functor. More...
 
struct  bit_count_table
 Structure to aid in counting bits table contains count of bits in 0-255 diapason of numbers. More...
 
struct  bit_COUNT_XOR
 Bit COUNT XOR functor. More...
 
struct  bit_decode_cache
 bit-decode cache structure More...
 
struct  bit_grabber
 
struct  bit_grabber< unsigned char, 8 >
 
struct  bit_grabber< unsigned short, 16 >
 
struct  bit_grabber< unsigned, 32 >
 
class  bit_in
 Byte based reader for un-aligned bit streaming. More...
 
struct  bit_OR
 Bit OR functor. More...
 
class  bit_out
 Byte based writer for un-aligned bit streaming. More...
 
struct  bit_SUB
 Bit SUB functor. More...
 
struct  bit_trans_grabber
 
struct  bit_vistor_copy_functor
 Functor for bit-copy (for testing) More...
 
struct  bit_vitor_callback_adaptor
 private adaptor for C-style callbacks More...
 
struct  bit_XOR
 Bit XOR functor. More...
 
class  bitblock_get_adapter
 Bit-block get adapter, takes bitblock and represents it as a get_32() accessor function. More...
 
class  bitblock_store_adapter
 Bit-block store adapter, takes bitblock and saves results into it. More...
 
class  bitblock_sum_adapter
 Bit-block sum adapter, takes values and sums it /internal. More...
 
class  block_allocator
 Default malloc based bitblock allocator class. More...
 
struct  block_set_table
 Structure keeps all-left/right ON bits masks. More...
 
struct  block_waves_xor_descr
 Structure to compute XOR gap-count profile by sub-block waves. More...
 
class  bv_ref_vector
 List of reference bit-vectors with their true index associations. More...
 
struct  bv_statistics
 Structure with statistical information about memory allocation footprint, serialization projection, number of vectors. More...
 
class  bvector
 Bitvector Bit-vector container with runtime compression of bits. More...
 
class  bvector_mini
 Bitvector class with very limited functionality. More...
 
class  bvmini
 Mini bit-vector for auxiliary purposes. More...
 
class  bvps_addr_resolver
 Bit-bector prefix sum address resolver using bit-vector prefix sum as a space compactor. More...
 
class  chrono_taker
 Utility class to collect performance measurements and statistics. More...
 
class  compressed_buffer_collection
 Compressed (sparse collection of objects) More...
 
class  compressed_collection
 Compressed (sparse collection of objects) More...
 
class  compressed_collection_deserializer
 Deseriaizer for compressed collections. More...
 
class  compressed_collection_serializer
 Seriaizer for compressed collections. More...
 
struct  conditional
 ad-hoc conditional expressions More...
 
struct  conditional< false >
 
class  copy_to_array_functor
 Adaptor to copy 1 bits to array. More...
 
struct  d_copy_func
 d-Gap copy functor More...
 
struct  DeBruijn_bit_position
 DeBruijn majic table. More...
 
class  decoder
 Class for decoding data from memory buffer. More...
 
class  decoder_base
 Base class for all decoding functionality. More...
 
class  decoder_little_endian
 Class for decoding data from memory buffer. More...
 
class  decoder_range_adapter
 Adapter to get words from a range stream (see range serialized bit-block) More...
 
class  deseriaizer_base
 Base deserialization class. More...
 
class  deserializer
 Deserializer for bit-vector. More...
 
struct  distance_metric_descriptor
 Distance metric descriptor, holds metric code and result. More...
 
class  encoder
 Memory encoding. More...
 
struct  first_bit_table
 Structure keeps index of first right 1 bit for every byte. More...
 
class  gamma_decoder
 Elias Gamma decoder. More...
 
class  gamma_encoder
 Functor for Elias Gamma encoding. More...
 
struct  gap_len_table
 Default GAP lengths table. More...
 
struct  gap_len_table_min
 Alternative GAP lengths table. Good for for memory saver mode and very sparse bitsets. More...
 
struct  gap_len_table_nl
 Non-linear size growth GAP lengths table. More...
 
class  gap_transpose_engine
 Bit-plain splicing of a GAP block. More...
 
struct  globals
 Internal structure. More...
 
class  interval_enumerator
 forward iterator class to traverse bit-vector as ranges More...
 
class  iterator_deserializer
 Iterator to walk forward the serialized stream. More...
 
struct  lzcnt_table
 Structure for LZCNT constants (4-bit) More...
 
class  mem_alloc
 BM style allocator adapter. More...
 
class  miniset
 Template class implements memory saving set functionality. More...
 
class  operation_deserializer
 Deserializer, performs logical operations between bit-vector and serialized bit-vector. More...
 
struct  operation_functions
 
struct  or_func
 or functor More...
 
struct  pair
 Pair type. More...
 
class  pointer_pool_array
 Pool of pointers to buffer cyclic allocations. More...
 
class  ptr_allocator
 Default malloc based bitblock allocator class. More...
 
class  ptr_guard
 Mini auto-pointer for internal memory management. More...
 
union  ptr_payload_t
 helper union to interpret pointer as integers More...
 
class  random_subset
 
class  rank_compressor
 Algorithms for rank compression of bit-vector. More...
 
class  rsc_sparse_vector
 Rank-Select compressed sparse vector. More...
 
class  serial_stream_iterator
 Serialization stream iterator. More...
 
class  serializer
 Bit-vector serialization class. More...
 
class  set2set_11_transform
 Integer set to set transformation (functional image in groups theory) https://en.wikipedia.org/wiki/Image_(mathematics) More...
 
struct  similarity_batch
 
class  similarity_descriptor
 
class  sparse_vector
 sparse vector with runtime compression using bit transposition method More...
 
class  sparse_vector_deserializer
 sparse vector de-serializer More...
 
class  sparse_vector_scanner
 algorithms for sparse_vector scan/search More...
 
struct  sparse_vector_serial_layout
 layout class for serialization buffer structure More...
 
class  sparse_vector_serializer
 Serialize sparse vector into a memory buffer(s) structure. More...
 
class  sse_empty_guard
 SSE2 reinitialization guard class. More...
 
class  str_sparse_vector
 sparse vector for strings with compression using bit transposition method More...
 
struct  sub_func
 sub functor More...
 
class  sv_addr_resolver
 sparse vector based address resolver (no space compactor, just bit-plane compressors provided by sparse_vector) More...
 
struct  tmatrix
 Mini-matrix for bit transposition purposes. More...
 
struct  tzcnt_table
 Structure for TZCNT constants. More...
 
struct  xor_func
 xor functor More...
 
class  xor_scanner
 XOR scanner to search for complement-similarities in collections of bit-vectors. More...
 

Typedefs

typedef void(* gap_operation_to_bitset_func_type) (unsigned *, const gap_word_t *)
 
typedef gap_word_t *(* gap_operation_func_type) (const gap_word_t *BMRESTRICT, const gap_word_t *BMRESTRICT, gap_word_t *BMRESTRICT, unsigned &)
 
typedef bm::id_t(* bit_operation_count_func_type) (const bm::word_t *BMRESTRICT, const bm::word_t *BMRESTRICT)
 
typedef decoder decoder_big_endian
 Class for decoding data from memory buffer. More...
 
typedef unsigned long long int id64_t
 
typedef unsigned int id_t
 
typedef unsigned int word_t
 
typedef unsigned short short_t
 
typedef unsigned short gap_word_t
 
typedef id64_t wordop_t
 
typedef bm::alloc_pool< block_allocator, ptr_allocatorstandard_alloc_pool
 
typedef bm::mem_alloc< block_allocator, ptr_allocator, standard_alloc_poolstandard_allocator
 

Enumerations

enum  xor_complement_match { e_no_xor_match = 0, e_xor_match_GC, e_xor_match_BC, e_xor_match_iBC }
 XOR complementarity type between 2 blocks. More...
 
enum  strategy { BM_BIT = 0, BM_GAP = 1 }
 Block allocation strategies. More...
 
enum  set_operation {
  set_AND = 0, set_OR = 1, set_SUB = 2, set_XOR = 3,
  set_ASSIGN = 4, set_COUNT = 5, set_COUNT_AND = 6, set_COUNT_XOR = 7,
  set_COUNT_OR = 8, set_COUNT_SUB_AB = 9, set_COUNT_SUB_BA = 10, set_COUNT_A = 11,
  set_COUNT_B = 12, set_END
}
 Codes of set operations. More...
 
enum  operation { BM_AND = set_AND, BM_OR = set_OR, BM_SUB = set_SUB, BM_XOR = set_XOR }
 Bit operations. More...
 
enum  sort_order { BM_UNSORTED = 0, BM_SORTED = 1, BM_SORTED_UNIFORM = 2, BM_UNKNOWN = 3 }
 Sort order declaration. More...
 
enum  set_representation { set_bitset = 0, set_gap = 1, set_array1 = 2, set_array0 = 3 }
 set representation variants More...
 
enum  null_support { use_null = 0, no_null = 1 }
 NULL-able value support. More...
 
enum  simd_codes {
  simd_none = 0, simd_sse2 = 1, simd_sse42 = 2, simd_avx2 = 5,
  simd_avx512 = 6
}
 codes for supported SIMD optimizations More...
 
enum  ByteOrder { BigEndian = 0, LittleEndian = 1 }
 Byte orders recognized by the library. More...
 
enum  distance_metric {
  COUNT_AND = set_COUNT_AND, COUNT_XOR = set_COUNT_XOR, COUNT_OR = set_COUNT_OR, COUNT_SUB_AB = set_COUNT_SUB_AB,
  COUNT_SUB_BA = set_COUNT_SUB_BA, COUNT_A = set_COUNT_A, COUNT_B = set_COUNT_B
}
 Distance metrics codes defined for vectors A and B. More...
 
enum  serialization_header_mask {
  BM_HM_DEFAULT = 1, BM_HM_RESIZE = (1 << 1), BM_HM_ID_LIST = (1 << 2), BM_HM_NO_BO = (1 << 3),
  BM_HM_NO_GAPL = (1 << 4), BM_HM_64_BIT = (1 << 5), BM_HM_HXOR = (1 << 6), BM_HM_SPARSE = (1 << 7)
}
 
enum  serialization_flags { BM_NO_BYTE_ORDER = 1, BM_NO_GAP_LENGTH = (1 << 1) }
 Bit mask flags for serialization algorithm. More...
 

Functions

template<class Alloc >
bvector< Alloc > operator & (const bvector< Alloc > &bv1, const bvector< Alloc > &bv2)
 
template<class Alloc >
bvector< Alloc > operator| (const bvector< Alloc > &bv1, const bvector< Alloc > &bv2)
 
template<class Alloc >
bvector< Alloc > operator^ (const bvector< Alloc > &bv1, const bvector< Alloc > &bv2)
 
template<class Alloc >
bvector< Alloc > operator- (const bvector< Alloc > &bv1, const bvector< Alloc > &bv2)
 
bm::id_t bit_block_calc_count_range (const bm::word_t *block, bm::word_t left, bm::word_t right) BMNOEXCEPT
 
bm::id_t bit_block_any_range (const bm::word_t *block, bm::word_t left, bm::word_t right) BMNOEXCEPT
 
template<typename BI_TYPE >
BMFORCEINLINE void get_block_coord (BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
 Recalc linear bvector block index into 2D matrix coordinates. More...
 
template<typename RTYPE >
BMFORCEINLINE RTYPE get_super_block_start (unsigned i) BMNOEXCEPT
 Compute bit address of the first bit in a superblock. More...
 
template<typename RTYPE >
BMFORCEINLINE RTYPE get_block_start (unsigned i, unsigned j) BMNOEXCEPT
 Compute bit address of the first bit in a block. More...
 
BMFORCEINLINE bm::id_t word_bitcount (bm::id_t w) BMNOEXCEPT
 
int parallel_popcnt_32 (unsigned int n) BMNOEXCEPT
 
BMFORCEINLINE unsigned word_bitcount64 (bm::id64_t x) BMNOEXCEPT
 
unsigned bitcount64_4way (bm::id64_t x, bm::id64_t y, bm::id64_t u, bm::id64_t v) BMNOEXCEPT
 
template<typename T , typename F >
void bit_for_each_4 (T w, F &func)
 Templated algorithm to unpacks octet based word into list of ON bit indexes. More...
 
template<typename T , typename F >
void bit_for_each (T w, F &func)
 Templated algorithm to unpacks word into list of ON bit indexes. More...
 
unsigned bitscan_nibble (unsigned w, unsigned *bits) BMNOEXCEPT
 portable, switch based bitscan More...
 
template<typename T , typename B >
unsigned bit_list (T w, B *bits) BMNOEXCEPT
 Unpacks word into list of ON bit indexes. More...
 
template<typename T , typename B >
unsigned bit_list_4 (T w, B *bits) BMNOEXCEPT
 Unpacks word into list of ON bit indexes (quad-bit based) More...
 
template<typename B >
unsigned short bitscan_popcnt (bm::id_t w, B *bits, unsigned short offs) BMNOEXCEPT
 Unpacks word into list of ON bit indexes using popcnt method. More...
 
template<typename B >
unsigned short bitscan_popcnt (bm::id_t w, B *bits) BMNOEXCEPT
 Unpacks word into list of ON bit indexes using popcnt method. More...
 
template<typename B >
unsigned short bitscan_popcnt64 (bm::id64_t w, B *bits) BMNOEXCEPT
 Unpacks 64-bit word into list of ON bit indexes using popcnt method. More...
 
template<typename B >
unsigned short bitscan_bsf (unsigned w, B *bits) BMNOEXCEPT
 Unpacks word into list of ON bits (BSF/__builtin_ctz) More...
 
template<typename B , typename OT >
unsigned short bitscan_bsf (unsigned w, B *bits, OT offs) BMNOEXCEPT
 
template<typename B >
unsigned short bitscan_bsf64 (bm::id64_t w, B *bits) BMNOEXCEPT
 Unpacks word into list of ON bits (BSF/__builtin_ctz) More...
 
template<typename B >
unsigned short bitscan_popcnt64 (bm::id64_t w, B *bits, unsigned short offs) BMNOEXCEPT
 Unpacks 64-bit word into list of ON bit indexes using popcnt method. More...
 
template<typename V , typename B >
unsigned short bitscan (V w, B *bits) BMNOEXCEPT
 Templated Bitscan with dynamic dispatch for best type. More...
 
unsigned word_select64_linear (bm::id64_t w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned word_select64_bitscan_popcnt (bm::id64_t w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned word_select64_bitscan_tz (bm::id64_t w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned word_select32_bitscan_popcnt (unsigned w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned word_select32_bitscan_tz (unsigned w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned word_select64 (bm::id64_t w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned word_select32 (unsigned w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
BMFORCEINLINE bm::id64_t widx_to_digest_mask (unsigned w_idx) BMNOEXCEPT
 Compute digest mask for word address in block. More...
 
bm::id64_t dm_control (unsigned from, unsigned to) BMNOEXCEPT
 digest mask control generation (for debug and test only) More...
 
BMFORCEINLINE bm::id64_t digest_mask (unsigned from, unsigned to) BMNOEXCEPT
 Compute digest mask for [from..to] positions. More...
 
bool check_zero_digest (bm::id64_t digest, unsigned bitpos_from, unsigned bitpos_to) BMNOEXCEPT
 check if all digest bits for the range [from..to] are 0 More...
 
void block_init_digest0 (bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT
 Init block with 000111000 pattren based on digest. More...
 
bm::id64_t calc_block_digest0 (const bm::word_t *const block) BMNOEXCEPT
 Compute digest for 64 non-zero areas. More...
 
bm::id64_t update_block_digest0 (const bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT
 Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas) More...
 
bool is_const_set_operation (set_operation op) BMNOEXCEPT
 Returns true if set operation is constant (bitcount) More...
 
bm::operation setop2op (bm::set_operation op) BMNOEXCEPT
 Convert set operation to operation. More...
 
template<typename W >
void xor_swap (W &x, W &y) BMNOEXCEPT
 XOR swap two scalar variables. More...
 
template<typename N >
bool find_not_null_ptr (bm::word_t ***arr, N start, N size, N *pos) BMNOEXCEPT
 
template<typename T >
int wordcmp0 (T w1, T w2)
 Lexicographical comparison of two words as bit strings (reference) Auxiliary implementation for testing and reference purposes. More...
 
template<typename T >
int wordcmp (T a, T b)
 Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes. More...
 
bool bit_is_all_zero (const bm::word_t *BMRESTRICT start) BMNOEXCEPT
 Returns "true" if all bits in the block are 0. More...
 
BMFORCEINLINE bool gap_is_all_zero (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
 Checks if GAP block is all-zero. More...
 
BMFORCEINLINE bool gap_is_all_one (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
 Checks if GAP block is all-one. More...
 
BMFORCEINLINE bm::gap_word_t gap_length (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
 Returs GAP block length. More...
 
template<typename T >
unsigned gap_capacity (const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
 Returs GAP block capacity. More...
 
template<typename T >
unsigned gap_limit (const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
 Returs GAP block capacity limit. More...
 
template<typename T >
gap_level (const T *BMRESTRICT buf) BMNOEXCEPT
 Returs GAP blocks capacity level. More...
 
template<typename T >
unsigned gap_find_last (const T *BMRESTRICT buf, unsigned *BMRESTRICT last) BMNOEXCEPT
 GAP block find the last set bit. More...
 
template<typename T >
unsigned gap_find_first (const T *BMRESTRICT buf, unsigned *BMRESTRICT first) BMNOEXCEPT
 GAP block find the first set bit. More...
 
template<typename T >
unsigned gap_bfind (const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
 
template<typename T >
unsigned gap_test (const T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
 Tests if bit = pos is true. More...
 
template<typename T >
unsigned gap_test_unr (const T *BMRESTRICT buf, const unsigned pos) BMNOEXCEPT
 Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling. More...
 
template<typename T , typename N , typename F >
void for_each_nzblock_range (T ***root, N top_size, N nb_from, N nb_to, F &f) BMNOEXCEPT
 
template<class T , class F >
void for_each_nzblock (T ***root, unsigned size1, F &f)
 
template<class T , class F >
void for_each_nzblock2 (T ***root, unsigned size1, F &f)
 
template<typename T , typename BI , typename F >
bool for_each_nzblock_if (T ***root, BI size1, F &f) BMNOEXCEPT
 
template<class T , class F , typename BLOCK_IDX >
void for_each_block (T ***root, unsigned size1, F &f, BLOCK_IDX start)
 
template<class T , class F >
bmfor_each (T first, T last, F f)
 
template<typename T >
bm::id64_t sum_arr (const T *first, const T *last) BMNOEXCEPT
 
template<typename T >
void gap_split (const T *buf, T *arr0, T *arr1, T &arr0_cnt, T &arr1_cnt) BMNOEXCEPT
 
template<typename T >
unsigned gap_bit_count (const T *buf, unsigned dsize=0) BMNOEXCEPT
 Calculates number of bits ON in GAP buffer. More...
 
template<typename T >
unsigned gap_bit_count_unr (const T *buf) BMNOEXCEPT
 Calculates number of bits ON in GAP buffer. Loop unrolled version. More...
 
template<typename T >
unsigned gap_bit_count_range (const T *const buf, unsigned left, unsigned right) BMNOEXCEPT
 Counts 1 bits in GAP buffer in the closed [left, right] range. More...
 
template<typename T >
bool gap_is_all_one_range (const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
 Test if all bits are 1 in GAP buffer in the [left, right] range. More...
 
template<typename T >
bool gap_any_range (const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
 Test if any bits are 1 in GAP buffer in the [left, right] range. More...
 
template<typename T >
bool gap_is_interval (const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
 Test if any bits are 1 in GAP buffer in the [left, right] range and flanked with 0s. More...
 
template<typename T >
bool gap_find_interval_end (const T *const BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Searches for the last 1 bit in the 111 interval of a GAP block. More...
 
template<typename T >
bool gap_find_interval_start (const T *const BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Searches for the first 1 bit in the 111 interval of a GAP block. More...
 
template<typename T >
bool gap_find_prev (const T *const BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 reverse search for the first 1 bit of a GAP block More...
 
template<typename T , typename SIZE_TYPE >
SIZE_TYPE gap_find_rank (const T *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) BMNOEXCEPT
 GAP block find position for the rank. More...
 
template<typename T >
unsigned gap_bit_count_to (const T *const buf, T right, bool is_corrected=false) BMNOEXCEPT
 Counts 1 bits in GAP buffer in the closed [0, right] range. More...
 
template<class T , class Func >
void for_each_dgap (const T *gap_buf, Func &func)
 
template<typename T >
T * gap_2_dgap (const T *BMRESTRICT gap_buf, T *BMRESTRICT dgap_buf, bool copy_head=true) BMNOEXCEPT
 Convert GAP buffer into D-GAP buffer. More...
 
template<typename T >
void dgap_2_gap (const T *BMRESTRICT dgap_buf, T *BMRESTRICT gap_buf, T gap_header=0) BMNOEXCEPT
 Convert D-GAP buffer into GAP buffer. More...
 
template<typename T >
int gapcmp (const T *buf1, const T *buf2) BMNOEXCEPT
 Lexicographical comparison of GAP buffers. More...
 
template<typename T >
bool gap_find_first_diff (const T *BMRESTRICT buf1, const T *BMRESTRICT buf2, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Find first bit which is different between two GAP-blocks. More...
 
template<typename T , class F >
void gap_buff_op (T *BMRESTRICT dest, const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, unsigned &dlen) BMNOEXCEPT2
 Abstract operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T , class F >
unsigned gap_buff_any_op (const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask) BMNOEXCEPT2
 Abstract operation for GAP buffers (predicts legth) Receives functor F as a template argument. More...
 
template<typename T , class F >
unsigned gap_buff_count_op (const T *vect1, const T *vect2) BMNOEXCEPT2
 Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T >
unsigned gap_set_value (unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned gap_set_value (unsigned val, T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned gap_add_value (T *buf, unsigned pos) BMNOEXCEPT
 Add new value to the end of GAP buffer. More...
 
template<typename T >
bool gap_shift_r1 (T *BMRESTRICT buf, unsigned co_flag, unsigned *BMRESTRICT new_len) BMNOEXCEPT
 Right shift GAP block by 1 bit. More...
 
template<typename T >
bool gap_shift_l1 (T *BMRESTRICT buf, unsigned co_flag, unsigned *BMRESTRICT new_len) BMNOEXCEPT
 Left shift GAP block by 1 bit. More...
 
template<typename T >
unsigned gap_set_array (T *buf, const T *arr, unsigned len) BMNOEXCEPT
 Convert array to GAP buffer. More...
 
template<typename T >
unsigned bit_array_compute_gaps (const T *arr, unsigned len) BMNOEXCEPT
 Compute number of GAPs in bit-array. More...
 
template<typename T >
unsigned gap_block_find (const T *BMRESTRICT buf, unsigned nbit, bm::id_t *BMRESTRICT prev) BMNOEXCEPT
 Searches for the next 1 bit in the GAP block. More...
 
BMFORCEINLINE void set_bit (unsigned *dest, unsigned bitpos) BMNOEXCEPT
 Set 1 bit in a block. More...
 
BMFORCEINLINE void clear_bit (unsigned *dest, unsigned bitpos) BMNOEXCEPT
 Set 1 bit in a block. More...
 
BMFORCEINLINE unsigned test_bit (const unsigned *block, unsigned bitpos) BMNOEXCEPT
 Test 1 bit in a block. More...
 
void or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
 Sets bits to 1 in the bitblock. More...
 
void sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
 SUB (AND NOT) bit interval to 1 in the bitblock. More...
 
void xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
 XOR bit interval to 1 in the bitblock. More...
 
template<typename T >
void gap_sub_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
 SUB (AND NOT) GAP block to bitblock. More...
 
template<typename T >
void gap_sub_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, bm::id64_t digest0) BMNOEXCEPT
 SUB (AND NOT) GAP block to bitblock with digest assist. More...
 
template<typename T >
void gap_xor_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
 XOR GAP block to bitblock. More...
 
template<typename T >
void gap_add_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, unsigned len) BMNOEXCEPT
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void gap_add_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void gap_and_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
 ANDs GAP block to bitblock. More...
 
template<typename T >
void gap_and_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, bm::id64_t digest0) BMNOEXCEPT
 ANDs GAP block to bitblock with digest assist. More...
 
template<typename T >
bm::id_t gap_bitset_and_count (const unsigned *BMRESTRICT block, const T *BMRESTRICT pcurr) BMNOEXCEPT
 Compute bitcount of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t gap_bitset_and_any (const unsigned *BMRESTRICT block, const T *BMRESTRICT pcurr) BMNOEXCEPT
 Bitcount test of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t gap_bitset_sub_count (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount of bit block SUB masked by GAP block. More...
 
template<typename T >
bm::id_t gap_bitset_sub_any (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount test of bit block SUB masked by GAP block. More...
 
template<typename T >
bm::id_t gap_bitset_xor_count (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount of bit block XOR masked by GAP block. More...
 
template<typename T >
bm::id_t gap_bitset_xor_any (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount test of bit block XOR masked by GAP block. More...
 
template<typename T >
bm::id_t gap_bitset_or_count (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount of bit block OR masked by GAP block. More...
 
template<typename T >
bm::id_t gap_bitset_or_any (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount test of bit block OR masked by GAP block. More...
 
void bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value) BMNOEXCEPT
 Bitblock memset operation. More...
 
template<typename T >
void gap_convert_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT buf) BMNOEXCEPT
 GAP block to bitblock conversion. More...
 
template<typename T >
unsigned * gap_convert_to_bitset_smart (unsigned *BMRESTRICT dest, const T *BMRESTRICT buf, id_t set_max) BMNOEXCEPT
 Smart GAP block to bitblock conversion. More...
 
template<typename T >
unsigned gap_control_sum (const T *buf) BMNOEXCEPT
 Calculates sum of all words in GAP block. (For debugging purposes) More...
 
template<class T >
void gap_set_all (T *buf, unsigned set_max, unsigned value) BMNOEXCEPT
 Sets all bits to 0 or 1 (GAP) More...
 
template<class T >
void gap_init_range_block (T *buf, T from, T to, T value) BMNOEXCEPT
 Init gap block so it has block in it (can be whole block) More...
 
template<typename T >
void gap_invert (T *buf) BMNOEXCEPT
 Inverts all bits in the GAP buffer. More...
 
template<typename T >
void set_gap_level (T *buf, int level) BMNOEXCEPT
 Sets GAP block capacity level. More...
 
template<typename T >
int gap_calc_level (unsigned len, const T *glevel_len) BMNOEXCEPT
 Calculates GAP block capacity level. More...
 
template<typename T >
unsigned gap_free_elements (const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
 Returns number of free elements in GAP block array. Difference between GAP block capacity on this level and actual GAP length. More...
 
template<typename T >
int bitcmp (const T *buf1, const T *buf2, unsigned len) BMNOEXCEPT
 Lexicographical comparison of BIT buffers. More...
 
bool bit_find_first_diff (const bm::word_t *BMRESTRICT blk1, const bm::word_t *BMRESTRICT blk2, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Find first bit which is different between two bit-blocks. More...
 
unsigned bit_block_to_gap (gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
 Converts bit block to GAP. More...
 
unsigned bit_to_gap (gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
 Convert bit block to GAP representation. More...
 
template<class T , class F >
void for_each_gap_dbit (const T *buf, F &func)
 Iterate gap block as delta-bits with a functor. More...
 
template<typename D , typename T >
gap_convert_to_arr (D *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned dest_len, bool invert=false) BMNOEXCEPT
 Convert gap block into array of ints corresponding to 1 bits. More...
 
BMFORCEINLINE unsigned bit_count_min_unroll (const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT block_end) BMNOEXCEPT
 Bitcount for bit block without agressive unrolling. More...
 
bm::id_t bit_block_count (const bm::word_t *block) BMNOEXCEPT
 Bitcount for bit block. More...
 
bm::id_t bit_block_count (const bm::word_t *BMRESTRICT const block, bm::id64_t digest) BMNOEXCEPT
 Bitcount for bit block. More...
 
bm::id_t bit_count_change (bm::word_t w) BMNOEXCEPT
 
unsigned bit_block_change32 (const bm::word_t *block, unsigned size) BMNOEXCEPT
 
void bit_block_change_bc (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc) BMNOEXCEPT
 
unsigned bit_block_calc_change (const bm::word_t *block) BMNOEXCEPT
 
bool bit_block_is_all_one_range (const bm::word_t *const BMRESTRICT block, bm::word_t left, bm::word_t right) BMNOEXCEPT
 
bm::id_t bit_block_calc_count_to (const bm::word_t *block, bm::word_t right) BMNOEXCEPT
 
void bit_block_rotate_left_1 (bm::word_t *block) BMNOEXCEPT
 
void bit_block_rotate_left_1_unr (bm::word_t *block) BMNOEXCEPT
 Unrolled cyclic rotation of bit-block left by 1 bit. More...
 
bm::word_t bit_block_insert (bm::word_t *BMRESTRICT block, unsigned bitpos, bool value) BMNOEXCEPT
 insert bit into position and shift the rest right with carryover More...
 
bool bit_block_shift_r1 (bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::word_t co_flag) BMNOEXCEPT
 Right bit-shift bitblock by 1 bit (reference) More...
 
bool bit_block_shift_r1_unr_min (bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::id64_t co_flag) BMNOEXCEPT
 Right bit-shift bitblock by 1 bit (minimum unroll) More...
 
bool bit_block_shift_r1_unr (bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::word_t co_flag) BMNOEXCEPT
 Right bit-shift of bit-block by 1 bit (loop unrolled) More...
 
bool bit_block_shift_l1 (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) BMNOEXCEPT
 Left bit-shift bitblock by 1 bit (reference) More...
 
bool bit_block_shift_l1_unr_min (bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, unsigned co_flag) BMNOEXCEPT
 Left bit-shift bitblock by 1 bit (minimum unroll) More...
 
bool bit_block_shift_l1_unr (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) BMNOEXCEPT
 Left bit-shift of bit-block by 1 bit (loop unrolled) More...
 
void bit_block_erase (bm::word_t *block, unsigned bitpos, bool carry_over) BMNOEXCEPT
 erase bit from position and shift the rest right with carryover More...
 
bool bit_block_shift_r1_and (bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest) BMNOEXCEPT
 Right bit-shift of bit-block by 1 bit (reference) + AND. More...
 
bool bit_block_shift_r1_and_unr (bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest) BMNOEXCEPT
 Right bit-shift bitblock by 1 bit (reference) + AND. More...
 
bm::id_t bit_block_any_range (const bm::word_t *const BMRESTRICT block, bm::word_t left, bm::word_t right) BMNOEXCEPT
 
template<typename T >
void bit_invert (T *start) BMNOEXCEPT
 
bool is_bits_one (const bm::wordop_t *start) BMNOEXCEPT
 Returns "true" if all bits in the block are 1. More...
 
bool block_is_all_one_range (const bm::word_t *const BMRESTRICT block, unsigned left, unsigned right) BMNOEXCEPT
 Returns "true" if all bits are 1 in the block [left, right] Function check for block varieties. More...
 
bool block_is_interval (const bm::word_t *const BMRESTRICT block, unsigned left, unsigned right) BMNOEXCEPT
 Returns "true" if all bits are 1 in the block [left, right] and border bits are 0. More...
 
bool bit_block_find_interval_end (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Searches for the last 1 bit in the 111 interval of a BIT block. More...
 
unsigned block_find_interval_end (const bm::word_t *BMRESTRICT block, unsigned nbit_from, unsigned *BMRESTRICT found_nbit) BMNOEXCEPT
 Find end of the current 111 interval. More...
 
bool bit_block_find_interval_start (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Searches for the first 1 bit in the 111 interval of a BIT block. More...
 
bool bit_block_find_prev (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Reverse search for the previous 1 bit. More...
 
unsigned block_find_interval_start (const bm::word_t *BMRESTRICT block, unsigned nbit_from, unsigned *BMRESTRICT found_nbit) BMNOEXCEPT
 Find start of the current 111 interval. More...
 
bool block_find_reverse (const bm::word_t *BMRESTRICT block, unsigned nbit_from, unsigned *BMRESTRICT found_nbit) BMNOEXCEPT
 Reverse find 1. More...
 
bool block_any_range (const bm::word_t *const BMRESTRICT block, unsigned left, unsigned right) BMNOEXCEPT
 Returns "true" if one bit is set in the block [left, right] Function check for block varieties. More...
 
bool block_any (const bm::word_t *const BMRESTRICT block) BMNOEXCEPT
 Returns "true" if one bit is set in the block Function check for block varieties. More...
 
gap_word_tgap_operation_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
 GAP AND operation. More...
 
unsigned gap_operation_any_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP AND operation test. More...
 
unsigned gap_count_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP bitcount AND operation test. More...
 
gap_word_tgap_operation_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
 GAP XOR operation. More...
 
BMFORCEINLINE unsigned gap_operation_any_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP XOR operation test. More...
 
BMFORCEINLINE unsigned gap_count_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP bitcount XOR operation test. More...
 
gap_word_tgap_operation_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
 GAP OR operation. More...
 
BMFORCEINLINE unsigned gap_count_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP bitcount OR operation test. More...
 
gap_word_tgap_operation_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
 GAP SUB (AND NOT) operation. More...
 
unsigned gap_operation_any_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP SUB operation test. More...
 
BMFORCEINLINE unsigned gap_count_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP bitcount SUB (AND NOT) operation test. More...
 
void bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Bitblock copy operation. More...
 
void bit_block_stream (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Bitblock copy/stream operation. More...
 
bm::id64_t bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Plain bitblock AND operation. Function does not analyse availability of source and destination blocks. More...
 
bm::id64_t bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest) BMNOEXCEPT
 digest based bit-block AND More...
 
bm::id64_t bit_block_and_5way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src0, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, bm::id64_t digest) BMNOEXCEPT
 digest based bit-block AND 5-way More...
 
bm::id64_t bit_block_and_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest) BMNOEXCEPT
 digest based bit-block AND More...
 
unsigned bit_block_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bit_block_and_any (const bm::word_t *src1, const bm::word_t *src2) BMNOEXCEPT
 Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bit_block_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bit_block_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bit_block_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bit_block_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bit_block_or_count (const bm::word_t *src1, const bm::word_t *src2) BMNOEXCEPT
 Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bit_block_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
bm::word_tbit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 bitblock AND operation. More...
 
bm::id_t bit_operation_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock AND operation and calculates bitcount of the result. More...
 
bm::id_t bit_operation_and_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock AND operation test. More...
 
bm::id_t bit_operation_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock SUB operation and calculates bitcount of the result. More...
 
bm::id_t bit_operation_sub_count_inv (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs inverted bitblock SUB operation and calculates bitcount of the result. More...
 
bm::id_t bit_operation_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock test of SUB operation. More...
 
bm::id_t bit_operation_or_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock OR operation and calculates bitcount of the result. More...
 
bm::id_t bit_operation_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock OR operation test. More...
 
bool bit_block_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Plain bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bool bit_block_or_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 2 way (target := source1 | source2) bitblock OR operation. More...
 
bm::id64_t bit_block_xor_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 2 way (target := source1 ^ source2) bitblock XOR operation. More...
 
bool bit_block_or_3way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bool bit_block_or_5way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, const bm::word_t *BMRESTRICT src4) BMNOEXCEPT
 5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bm::word_tbit_operation_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Block OR operation. Makes analysis if block is 0 or FULL. More...
 
bm::id64_t bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks. More...
 
bm::id64_t bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest) BMNOEXCEPT
 digest based bitblock SUB (AND NOT) operation More...
 
bm::id64_t bit_block_sub_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest) BMNOEXCEPT
 digest based bitblock SUB (AND NOT) operation (3 operand) More...
 
bm::word_tbit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 bitblock SUB operation. More...
 
bm::id64_t bit_block_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks. More...
 
void bit_andnot_arr_ffmask (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 bitblock AND NOT with constant ~0 mask operation. More...
 
bm::word_tbit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 bitblock XOR operation. More...
 
bm::id_t bit_operation_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock XOR operation and calculates bitcount of the result. More...
 
bm::id_t bit_operation_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock XOR operation test. More...
 
template<class T >
unsigned bit_count_nonzero_size (const T *blk, unsigned data_size) BMNOEXCEPT
 Inspects block for full zero words. More...
 
unsigned bit_block_find (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Searches for the next 1 bit in the BIT block. More...
 
unsigned bit_find_last (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT last) BMNOEXCEPT
 BIT block find the last set bit (backward search) More...
 
bool bit_find_first (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT pos) BMNOEXCEPT
 BIT block find the first set bit. More...
 
unsigned bit_find_first (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT first, bm::id64_t digest) BMNOEXCEPT
 BIT block find the first set bit. More...
 
bool bit_find_first_if_1 (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT first, bm::id64_t digest) BMNOEXCEPT
 BIT block find the first set bit if only 1 bit is set. More...
 
template<typename SIZE_TYPE >
SIZE_TYPE bit_find_rank (const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) BMNOEXCEPT
 BIT block find position for the rank. More...
 
template<typename SIZE_TYPE >
SIZE_TYPE block_find_rank (const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) BMNOEXCEPT
 Find rank in block (GAP or BIT) More...
 
bm::set_representation best_representation (unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size) BMNOEXCEPT
 Choose best representation for a bit-block. More...
 
template<typename T >
unsigned bit_block_convert_to_arr (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bool inverted) BMNOEXCEPT
 Convert bit block into an array of ints corresponding to 1 bits. More...
 
bool check_block_zero (const bm::word_t *blk, bool deep_scan) BMNOEXCEPT
 Checks all conditions and returns true if block consists of only 0 bits. More...
 
bool check_block_one (const bm::word_t *blk, bool deep_scan) BMNOEXCEPT
 Checks if block has only 1 bits. More...
 
template<typename T >
unsigned gap_overhead (const T *length, const T *length_end, const T *glevel_len) BMNOEXCEPT
 Calculates memory overhead for number of gap blocks sharing the same memory allocation table (level lengths table). More...
 
template<typename T >
bool improve_gap_levels (const T *length, const T *length_end, T *glevel_len) BMNOEXCEPT
 Finds optimal gap blocks lengths. More...
 
bool block_find_first_diff (const bm::word_t *BMRESTRICT blk, const bm::word_t *BMRESTRICT arg_blk, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Find first bit which is different between two blocks (GAP or bit) More...
 
template<class It1 , class It2 , class BinaryOp , class Encoder >
void bit_recomb (It1 &it1, It2 &it2, BinaryOp &op, Encoder &enc, unsigned block_size=bm::set_block_size) BMNOEXCEPT
 
unsigned short bitscan_wave (const bm::word_t *BMRESTRICT w_ptr, unsigned char *BMRESTRICT bits) BMNOEXCEPT
 Unpacks word wave (Nx 32-bit words) More...
 
void bit_block_gather_scatter (unsigned *BMRESTRICT arr, const bm::word_t *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx) BMNOEXCEPT
 bit index to word gather-scatter algorithm (SIMD) More...
 
template<typename TRGW , typename IDX , typename SZ >
void bit_block_gather_scatter (TRGW *BMRESTRICT arr, const bm::word_t *BMRESTRICT blk, const IDX *BMRESTRICT idx, SZ size, SZ start, unsigned bit_idx) BMNOEXCEPT
 bit index to word gather-scatter algorithm More...
 
bm::id64_t idx_arr_block_lookup_u64 (const bm::id64_t *idx, bm::id64_t size, bm::id64_t nb, bm::id64_t start) BMNOEXCEPT
 block boundaries look ahead U32 More...
 
unsigned idx_arr_block_lookup_u32 (const unsigned *idx, unsigned size, unsigned nb, unsigned start) BMNOEXCEPT
 block boundaries look ahead U32 More...
 
void set_block_bits_u64 (bm::word_t *BMRESTRICT block, const bm::id64_t *BMRESTRICT idx, bm::id64_t start, bm::id64_t stop) BMNOEXCEPT
 set bits in a bit-block using global index More...
 
void set_block_bits_u32 (bm::word_t *BMRESTRICT block, const unsigned *BMRESTRICT idx, unsigned start, unsigned stop) BMNOEXCEPT
 set bits in a bit-block using global index More...
 
bool block_ptr_array_range (bm::word_t **arr, unsigned &left, unsigned &right) BMNOEXCEPT
 array range detector More...
 
unsigned lower_bound_linear_u32 (const unsigned *arr, unsigned target, unsigned from, unsigned to) BMNOEXCEPT
 Linear lower bound search in unsigned array. More...
 
unsigned lower_bound_linear_u64 (const unsigned long long *arr, unsigned long long target, unsigned from, unsigned to) BMNOEXCEPT
 Linear lower bound search in unsigned LONG array. More...
 
unsigned lower_bound_u32 (const unsigned *arr, unsigned target, unsigned from, unsigned to) BMNOEXCEPT
 Hybrid, binary-linear lower bound search in unsigned array. More...
 
unsigned lower_bound_u64 (const unsigned long long *arr, unsigned long long target, unsigned from, unsigned to) BMNOEXCEPT
 Hybrid, binary-linear lower bound search in unsigned LONG array. More...
 
bm::id_t block_to_global_index (unsigned i, unsigned j, unsigned block_idx) BMNOEXCEPT
 calculate bvector<> global bit-index from block-local coords More...
 
unsigned min_delta_u32 (const unsigned *arr, size_t arr_size)
 Calculate minimal delta between elements of sorted array. More...
 
void min_delta_apply (unsigned *arr, size_t arr_size, unsigned delta)
 Recalculate the array to decrement delta as arr[i] = arr[i] - delta + 1 so that array remains monotonically growing (fit for interpolative compression) More...
 
template<typename VT , typename SZ >
bool find_max_nz (const VT *arr, SZ arr_size, SZ *found_idx)
 Find max non-zero value in an array. More...
 
template<typename VT , typename SZ >
bool find_first_nz (const VT *arr, SZ arr_size, SZ *found_idx)
 Find max non-zero value in an array. More...
 
template<typename VT , typename SZ >
SZ count_nz (const VT *arr, SZ arr_size)
 Find count of non-zero elements in the array. More...
 
bm::id64_t ptrp_test (ptr_payload_t ptr, bm::gap_word_t v) BMNOEXCEPT
 
int simd_version ()
 return SIMD optimization used for building BitMagic More...
 
void bit_block_xor_change32 (const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, unsigned size, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc) BMNOEXCEPT
 
void bit_block_xor_change (const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, unsigned size, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc) BMNOEXCEPT
 
void compute_complexity_descr (const bm::word_t *BMRESTRICT block, block_waves_xor_descr &BMRESTRICT x_descr) BMNOEXCEPT
 Compute reference (non-XOR) 64-dim complexity descriptor for the target block. More...
 
void compute_xor_complexity_descr (const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, bm::block_waves_xor_descr &BMRESTRICT x_descr, bm::xor_complement_match &BMRESTRICT match_type, bm::id64_t &BMRESTRICT digest, unsigned &BMRESTRICT block_gain) BMNOEXCEPT
 Compute reference complexity descriptor based on XOR vector. More...
 
void bit_block_xor (bm::word_t *target_block, const bm::word_t *block, const bm::word_t *xor_block, bm::id64_t digest) BMNOEXCEPT
 Build partial XOR product of 2 bit-blocks using digest mask. More...
 
template<typename T >
void gap_convert_to_bitset (unsigned *dest, const T *buf, unsigned dest_len)
 GAP block to bitblock conversion. More...
 
void sse2_xor_arr_2_mask (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src, const __m128i *BMRESTRICT src_end, bm::word_t mask)
 XOR array elements to specified mask dst = *src ^ mask. More...
 
void sse2_andnot_arr_2_mask (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src, const __m128i *BMRESTRICT src_end, bm::word_t mask)
 Inverts array elements and NOT them to specified mask dst = ~*src & mask. More...
 
unsigned sse2_and_block (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 AND blocks2 dst &= *src. More...
 
unsigned sse2_and_arr_unal (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src, const __m128i *BMRESTRICT src_end)
 AND array elements against another array (unaligned) dst &= *src. More...
 
unsigned sse2_and_block (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src, const __m128i *BMRESTRICT src_end)
 
bool sse2_or_block (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 OR array elements against another array dst |= *src. More...
 
bool sse2_or_arr_unal (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src, const __m128i *BMRESTRICT src_end)
 OR array elements against another array (unaligned) dst |= *src. More...
 
bool sse2_or_block_2way (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src1, const __m128i *BMRESTRICT src2)
 OR 2 blocks anc copy result to the destination dst = *src1 | src2. More...
 
bool sse2_or_block_3way (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src1, const __m128i *BMRESTRICT src2)
 OR array elements against another 2 arrays dst |= *src1 | src2. More...
 
bool sse2_or_block_5way (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src1, const __m128i *BMRESTRICT src2, const __m128i *BMRESTRICT src3, const __m128i *BMRESTRICT src4)
 OR array elements against another 2 arrays dst |= *src1 | src2 | src3 | src4. More...
 
unsigned sse2_xor_block (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 XOR block against another dst ^= *src. More...
 
unsigned sse2_xor_block_2way (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src1, const __m128i *BMRESTRICT src2)
 3 operand XOR dst = *src1 ^ src2 More...
 
unsigned sse2_sub_block (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 AND-NOT (SUB) array elements against another array dst &= ~*src. More...
 
BMFORCEINLINE void sse2_set_block (__m128i *BMRESTRICT dst, bm::word_t value)
 SSE2 block memset dst = value. More...
 
BMFORCEINLINE void sse2_copy_block (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 SSE2 block copy dst = *src. More...
 
BMFORCEINLINE void sse2_stream_block (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 SSE2 block copy dst = *src. More...
 
void sse2_invert_block (__m128i *dst)
 Invert bit block dst = ~*dst or dst ^= *dst. More...
 
BMFORCEINLINE __m128i sse2_and (__m128i a, __m128i b)
 
BMFORCEINLINE __m128i sse2_or (__m128i a, __m128i b)
 
BMFORCEINLINE __m128i sse2_xor (__m128i a, __m128i b)
 
BMFORCEINLINE __m128i sse2_sub (__m128i a, __m128i b)
 
const bm::gap_word_tsse2_gap_sum_arr (const bm::gap_word_t *BMRESTRICT pbuf, unsigned sse_vect_waves, unsigned *sum)
 Gap block population count (array sum) utility. More...
 
bm::id_t avx2_bit_count (const __m256i *BMRESTRICT block, const __m256i *BMRESTRICT block_end)
 AVX2 Harley-Seal popcount The algorithm is based on the paper "Faster Population Counts using AVX2 Instructions" by Daniel Lemire, Nathan Kurz and Wojciech Mula (23 Nov 2016). More...
 
bm::id_t avx2_bit_block_count (const bm::word_t *const block, bm::id64_t digest)
 Calculate population count based on digest. More...
 
bm::id_t avx2_bit_count_and (const __m256i *BMRESTRICT block, const __m256i *BMRESTRICT block_end, const __m256i *BMRESTRICT mask_block)
 AND bit count for two aligned bit-blocks. More...
 
bm::id_t avx2_bit_count_or (const __m256i *BMRESTRICT block, const __m256i *BMRESTRICT block_end, const __m256i *BMRESTRICT mask_block)
 
bm::id_t avx2_bit_count_xor (const __m256i *BMRESTRICT block, const __m256i *BMRESTRICT block_end, const __m256i *BMRESTRICT mask_block)
 XOR bit count for two aligned bit-blocks. More...
 
bm::id_t avx2_bit_count_sub (const __m256i *BMRESTRICT block, const __m256i *BMRESTRICT block_end, const __m256i *BMRESTRICT mask_block)
 AND NOT bit count for two aligned bit-blocks. More...
 
void avx2_xor_arr_2_mask (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src, const __m256i *BMRESTRICT src_end, bm::word_t mask)
 XOR array elements to specified mask dst = *src ^ mask. More...
 
void avx2_andnot_arr_2_mask (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src, const __m256i *BMRESTRICT src_end, bm::word_t mask)
 Inverts array elements and NOT them to specified mask dst = ~*src & mask. More...
 
unsigned avx2_and_block (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src)
 AND array elements against another array dst &= *src. More...
 
bool avx2_and_digest (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src)
 AND block digest stride dst &= *src. More...
 
bool avx2_and_digest_2way (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src1, const __m256i *BMRESTRICT src2)
 AND block digest stride 2 way dst = *src1 & *src2. More...
 
bool avx2_and_digest_5way (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src1, const __m256i *BMRESTRICT src2, const __m256i *BMRESTRICT src3, const __m256i *BMRESTRICT src4)
 AND block digest stride. More...
 
unsigned avx2_and_arr_unal (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src, const __m256i *BMRESTRICT src_end)
 AND array elements against another array (unaligned) dst &= *src. More...
 
bool avx2_or_block (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src)
 OR array elements against another array dst |= *src. More...
 
bool avx2_or_arr_unal (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src, const __m256i *BMRESTRICT src_end)
 OR array elements against another unaligned array dst |= *src. More...
 
bool avx2_or_block_2way (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src1, const __m256i *BMRESTRICT src2)
 OR 2 arrays and copy to the destination dst = *src1 | src2. More...
 
bool avx2_or_block_3way (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src1, const __m256i *BMRESTRICT src2)
 OR array elements against another 2 arrays dst |= *src1 | src2. More...
 
bool avx2_or_block_5way (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src1, const __m256i *BMRESTRICT src2, const __m256i *BMRESTRICT src3, const __m256i *BMRESTRICT src4)
 OR array elements against another 4 arrays dst |= *src1 | src2. More...
 
unsigned avx2_xor_block (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src)
 XOR block against another dst ^= *src. More...
 
unsigned avx2_xor_block_2way (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src1, const __m256i *BMRESTRICT src2)
 3 operand XOR dst = *src1 ^ src2 More...
 
unsigned avx2_sub_block (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src)
 AND-NOT (SUB) array elements against another array dst &= ~*src. More...
 
bool avx2_sub_digest (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src)
 SUB (AND NOT) block digest stride dst &= ~*src. More...
 
bool avx2_sub_digest_2way (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src1, const __m256i *BMRESTRICT src2)
 2-operand SUB (AND NOT) block digest stride dst = *src1 & ~*src2 More...
 
BMFORCEINLINE void avx2_set_block (__m256i *BMRESTRICT dst, bm::word_t value)
 AVX2 block memset dst = value. More...
 
void avx2_copy_block (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src)
 AVX2 block copy dst = *src. More...
 
void avx2_stream_block (__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src)
 AVX2 block copy dst = *src. More...
 
void avx2_invert_block (__m256i *BMRESTRICT dst)
 Invert bit-block dst = ~*dst or dst ^= *dst. More...
 
bool avx2_is_all_zero (const __m256i *BMRESTRICT block)
 check if block is all zero bits More...
 
bool avx2_is_digest_zero (const __m256i *BMRESTRICT block)
 check if digest stride is all zero bits More...
 
void avx2_block_set_digest (__m256i *dst, unsigned value)
 set digest stride to 0xFF.. or 0x0 value More...
 
bool avx2_is_all_one (const __m256i *BMRESTRICT block)
 check if block is all one bits More...
 
BMFORCEINLINE bool avx2_test_all_one_wave (const void *ptr)
 check if wave of pointers is all 0xFFF More...
 
BMFORCEINLINE bool avx2_test_all_zero_wave (const void *ptr)
 check if wave of pointers is all NULL More...
 
BMFORCEINLINE bool avx2_test_all_zero_wave2 (const void *ptr0, const void *ptr1)
 check if 2 wave of pointers are all NULL More...
 
BMFORCEINLINE bool avx2_test_all_eq_wave2 (const void *ptr0, const void *ptr1)
 check if 2 wave of pointers are all the same (NULL or FULL) More...
 
bool avx2_shift_l1 (__m256i *block, bm::word_t *empty_acc, unsigned co1)
 block shift left by 1 More...
 
bool avx2_shift_r1 (__m256i *block, bm::word_t *empty_acc, unsigned co1)
 block shift right by 1 More...
 
bool avx2_shift_r1_and (__m256i *BMRESTRICT block, bm::word_t co1, const __m256i *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest)
 fused block shift right by 1 plus AND More...
 
unsigned avx2_bit_block_calc_change (const __m256i *BMRESTRICT block, unsigned size)
 
void avx2_bit_block_calc_xor_change (const __m256i *BMRESTRICT block, const __m256i *BMRESTRICT xor_block, unsigned size, unsigned *BMRESTRICT gcount, unsigned *BMRESTRICT bcount)
 
void avx2_bit_block_calc_change_bc (const __m256i *BMRESTRICT block, unsigned *gcount, unsigned *bcount)
 
bool avx2_bit_find_first_diff (const __m256i *BMRESTRICT block1, const __m256i *BMRESTRICT block2, unsigned *pos)
 Find first bit which is different between two bit-blocks. More...
 
bool avx2_bit_find_first (const __m256i *BMRESTRICT block, unsigned *pos)
 Find first bit set. More...
 
const bm::gap_word_tavx2_gap_sum_arr (const bm::gap_word_t *pbuf, unsigned avx_vect_waves, unsigned *sum)
 
unsigned avx2_idx_arr_block_lookup (const unsigned *idx, unsigned size, unsigned nb, unsigned start)
 
void avx2_set_block_bits (bm::word_t *BMRESTRICT block, const unsigned *BMRESTRICT idx, unsigned start, unsigned stop)
 
BMFORCEINLINE __m256i avx2_setbit_256 (__m256i target, __m256i source)
 Set a bits in an AVX target, by indexes (int4) from the source. More...
 
void avx2_set_block_bits2 (bm::word_t *BMRESTRICT block, const unsigned *BMRESTRICT idx, unsigned start, unsigned stop)
 Experimental code to set bits via AVX strides. More...
 
void avx2_set_block_bits3 (bm::word_t *BMRESTRICT block, const unsigned *BMRESTRICT idx, unsigned start, unsigned stop)
 Experimental code to set bits via AVX strides. More...
 
__m256i avx2_setbit_to256 (unsigned i)
 Experiemntal. More...
 
int avx2_cmpge_u32 (__m256i vect8, unsigned value)
 Experimental (test) function to do SIMD vector search (lower bound) in sorted, growing array. More...
 
int avx2_cmpge_u16 (__m256i vect16, unsigned short value)
 Experimental (test) function to do SIMD vector search in sorted, growing array. More...
 
unsigned avx2_gap_bfind (const unsigned short *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
 Hybrid binary search, starts as binary, then switches to scan. More...
 
unsigned avx2_gap_test (const unsigned short *BMRESTRICT buf, unsigned pos)
 Hybrid binary search, starts as binary, then switches to scan. More...
 
unsigned avx2_lower_bound_scan_u32 (const unsigned *BMRESTRICT arr, unsigned target, unsigned from, unsigned to)
 lower bound (great or equal) linear scan in ascending order sorted array More...
 
void avx2_bit_block_gather_scatter (unsigned *BMRESTRICT arr, const unsigned *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx)
 
unsigned avx2_bit_to_gap (gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len)
 Convert bit block to GAP block. More...
 
void avx2_bit_block_xor (bm::word_t *target_block, const bm::word_t *block, const bm::word_t *xor_block, bm::id64_t digest)
 Build partial XOR product of 2 bit-blocks using digest mask. More...
 
bm::id_t sse4_bit_count (const __m128i *block, const __m128i *block_end)
 
BMFORCEINLINE unsigned op_xor (unsigned a, unsigned b)
 
BMFORCEINLINE unsigned op_or (unsigned a, unsigned b)
 
BMFORCEINLINE unsigned op_and (unsigned a, unsigned b)
 
template<class Func >
bm::id_t sse4_bit_count_op (const __m128i *BMRESTRICT block, const __m128i *BMRESTRICT block_end, const __m128i *BMRESTRICT mask_block, Func sse2_func)
 
bool sse4_is_all_zero (const __m128i *BMRESTRICT block)
 check if block is all zero bits More...
 
bool sse4_is_digest_zero (const __m128i *BMRESTRICT block)
 check if digest stride is all zero bits More...
 
void sse4_block_set_digest (__m128i *dst, unsigned value)
 set digest stride to 0xFF.. or 0x0 value More...
 
unsigned sse4_and_block (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 AND blocks2 dst &= *src. More...
 
bool sse4_and_digest (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 AND block digest stride dst &= *src. More...
 
bool sse4_and_digest_2way (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src1, const __m128i *BMRESTRICT src2)
 AND block digest stride dst = *src1 & src2. More...
 
bool sse4_and_digest_5way (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src1, const __m128i *BMRESTRICT src2, const __m128i *BMRESTRICT src3, const __m128i *BMRESTRICT src4)
 AND block digest stride. More...
 
bool sse4_sub_digest (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src)
 SUB (AND NOT) block digest stride dst &= ~*src. More...
 
bool sse4_sub_digest_2way (__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src1, const __m128i *BMRESTRICT src2)
 2-operand SUB (AND NOT) block digest stride dst = src1 & ~*src2 More...
 
bool sse4_is_all_one (const __m128i *BMRESTRICT block)
 check if block is all zero bits More...
 
BMFORCEINLINE bool sse42_test_all_one_wave (const void *ptr)
 check if SSE wave is all oxFFFF...FFF More...
 
BMFORCEINLINE bool sse42_test_all_zero_wave (const void *ptr)
 check if wave of pointers is all NULL More...
 
BMFORCEINLINE bool sse42_test_all_zero_wave2 (const void *ptr0, const void *ptr1)
 check if 2 waves of pointers are all NULL More...
 
BMFORCEINLINE bool sse42_test_all_eq_wave2 (const void *ptr0, const void *ptr1)
 check if wave of 2 pointers are the same (null or FULL) More...
 
unsigned sse42_bit_block_calc_change (const __m128i *BMRESTRICT block, unsigned size)
 
void sse42_bit_block_calc_xor_change (const __m128i *BMRESTRICT block, const __m128i *BMRESTRICT xor_block, unsigned size, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc)
 
void sse42_bit_block_calc_change_bc (const __m128i *BMRESTRICT block, unsigned *gc, unsigned *bc)
 
bool sse42_bit_find_first_diff (const __m128i *BMRESTRICT block1, const __m128i *BMRESTRICT block2, unsigned *pos)
 Find first bit which is different between two bit-blocks. More...
 
bool sse42_bit_find_first (const __m128i *BMRESTRICT block, unsigned *pos)
 Find first non-zero bit. More...
 
unsigned sse4_gap_find (const bm::gap_word_t *BMRESTRICT pbuf, const bm::gap_word_t pos, const unsigned size)
 
unsigned sse42_gap_bfind (const unsigned short *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
 Hybrid binary search, starts as binary, then switches to linear scan. More...
 
unsigned sse42_gap_test (const unsigned short *BMRESTRICT buf, unsigned pos)
 Hybrid binary search, starts as binary, then switches to scan. More...
 
int sse42_cmpge_u32 (__m128i vect4, unsigned value)
 Experimental (test) function to do SIMD vector search (lower bound) in sorted, growing array. More...
 
unsigned sse4_lower_bound_scan_u32 (const unsigned *BMRESTRICT arr, unsigned target, unsigned from, unsigned to)
 lower bound (great or equal) linear scan in ascending order sorted array More...
 
unsigned sse42_idx_arr_block_lookup (const unsigned *idx, unsigned size, unsigned nb, unsigned start)
 
void sse42_set_block_bits (bm::word_t *BMRESTRICT block, const unsigned *BMRESTRICT idx, unsigned start, unsigned stop)
 
void sse4_bit_block_gather_scatter (unsigned *BMRESTRICT arr, const unsigned *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx)
 
bool sse42_shift_l1 (__m128i *block, unsigned *empty_acc, unsigned co1)
 block shift left by 1 More...
 
bool sse42_shift_r1 (__m128i *block, unsigned *empty_acc, unsigned co1)
 block shift right by 1 More...
 
bool sse42_shift_r1_and (__m128i *block, bm::word_t co1, const __m128i *BMRESTRICT mask_block, bm::id64_t *digest)
 block shift right by 1 plus AND More...
 
void sse42_bit_block_xor (bm::word_t *target_block, const bm::word_t *block, const bm::word_t *xor_block, bm::id64_t digest)
 Build partial XOR product of 2 bit-blocks using digest mask. More...
 
bm::id_t sse2_bit_count (const __m128i *block, const __m128i *block_end)
 
template<class Func >
bm::id_t sse2_bit_count_op (const __m128i *BMRESTRICT block, const __m128i *BMRESTRICT block_end, const __m128i *BMRESTRICT mask_block, Func sse2_func)
 
bm::id_t sse2_bit_block_calc_count_change (const __m128i *BMRESTRICT block, const __m128i *BMRESTRICT block_end, unsigned *BMRESTRICT bit_count)
 
unsigned sse2_gap_find (const bm::gap_word_t *BMRESTRICT pbuf, const bm::gap_word_t pos, const unsigned size)
 
unsigned sse2_gap_bfind (const unsigned short *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
 Hybrid binary search, starts as binary, then switches to linear scan. More...
 
unsigned sse2_gap_test (const unsigned short *BMRESTRICT buf, unsigned pos)
 Hybrid binary search, starts as binary, then switches to scan. More...
 
template<class BV >
BV::size_type count_and (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Computes bitcount of AND operation of two bitsets. More...
 
template<class BV >
BV::size_type any_and (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Computes if there is any bit in AND operation of two bitsets. More...
 
template<class BV >
bm::distance_metric_descriptor::size_type count_xor (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Computes bitcount of XOR operation of two bitsets. More...
 
template<class BV >
BV::size_type any_xor (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Computes if there is any bit in XOR operation of two bitsets. More...
 
template<class BV >
BV::size_type count_sub (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Computes bitcount of SUB operation of two bitsets. More...
 
template<class BV >
BV::size_type any_sub (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Computes if there is any bit in SUB operation of two bitsets. More...
 
template<class BV >
BV::size_type count_or (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Computes bitcount of OR operation of two bitsets. More...
 
template<class BV >
BV::size_type any_or (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Computes if there is any bit in OR operation of two bitsets. More...
 
template<class BV , class Func >
void for_each_bit (const BV &bv, Func &bit_functor)
 bit-vector visitor scanner to traverse each 1 bit using C++ visitor More...
 
template<class BV , class Func >
void for_each_bit_range (const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
 bit-vector range visitor to traverse each 1 bit More...
 
template<class BV >
void visit_each_bit (const BV &bv, void *handle_ptr, bit_visitor_callback_type callback_ptr)
 bvector visitor scanner to traverse each 1 bit using C callback More...
 
template<class BV >
void visit_each_bit_range (const BV &bv, typename BV::size_type left, typename BV::size_type right, void *handle_ptr, bit_visitor_callback_type callback_ptr)
 bvector visitor scanner to traverse each bits in range (C callback) More...
 
template<typename BV , typename PairVect >
void rank_range_split (const BV &bv, typename BV::size_type rank, PairVect &target_v)
 Algorithm to identify bit-vector ranges (splits) for the rank. More...
 
distance_metric operation2metric (set_operation op) BMNOEXCEPT
 Convert set operation into compatible distance metric. More...
 
void combine_count_operation_with_block (const bm::word_t *blk, const bm::word_t *arg_blk, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
 Internal function computes different distance metrics. More...
 
unsigned combine_count_and_operation_with_block (const bm::word_t *blk, const bm::word_t *arg_blk) BMNOEXCEPT
 Internal function computes AND distance. More...
 
void combine_any_operation_with_block (const bm::word_t *blk, unsigned gap, const bm::word_t *arg_blk, unsigned arg_gap, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
 Internal function computes different existense of distance metric. More...
 
unsigned combine_count_operation_with_block (const bm::word_t *blk, const bm::word_t *arg_blk, distance_metric metric) BMNOEXCEPT
 
bm::distance_metric_descriptor::size_type combine_any_operation_with_block (const bm::word_t *blk, unsigned gap, const bm::word_t *arg_blk, unsigned arg_gap, distance_metric metric) BMNOEXCEPT
 
void distance_stage (const distance_metric_descriptor *dmit, const distance_metric_descriptor *dmit_end, bool *is_all_and) BMNOEXCEPT
 Staging function for distance operation. More...
 
template<class BV >
void distance_operation (const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
 Distance computing template function. More...
 
template<class BV >
BV::size_type distance_and_operation (const BV &bv1, const BV &bv2) BMNOEXCEPT
 Distance AND computing template function. More...
 
template<class BV >
void distance_operation_any (const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
 Distance screening template function. More...
 
template<typename It , typename SIZE_TYPE >
It block_range_scan (It first, It last, SIZE_TYPE nblock, SIZE_TYPE *max_id) BMNOEXCEPT
 Internal algorithms scans the input for the block range limit. More...
 
template<class BV , class It >
void combine_or (BV &bv, It first, It last)
 OR Combine bitvector and the iterable sequence. More...
 
template<class BV , class It >
void combine_xor (BV &bv, It first, It last)
 XOR Combine bitvector and the iterable sequence. More...
 
template<class BV , class It >
void combine_sub (BV &bv, It first, It last)
 SUB Combine bitvector and the iterable sequence. More...
 
template<class BV , class It >
void combine_and_sorted (BV &bv, It first, It last)
 AND Combine bitvector and the iterable sequence. More...
 
template<class BV , class It >
void combine_and (BV &bv, It first, It last)
 AND Combine bitvector and the iterable sequence. More...
 
template<class BV >
BV::size_type count_intervals (const BV &bv)
 Compute number of bit intervals (GAPs) in the bitvector. More...
 
template<typename BV , class It >
void export_array (BV &bv, It first, It last)
 Export bitset from an array of binary data representing the bit vector. More...
 
template<typename Func , typename SIZE_TYPE >
void for_each_bit_blk (const bm::word_t *block, SIZE_TYPE offset, Func &bit_functor)
 for-each visitor, calls a visitor functor for each 1 bit group More...
 
template<typename Func , typename SIZE_TYPE >
void for_each_bit_blk (const bm::word_t *block, SIZE_TYPE offset, unsigned left, unsigned right, Func &bit_functor)
 for-each range visitor, calls a visitor functor for each 1 bit group More...
 
template<typename T , typename Func , typename SIZE_TYPE >
void for_each_gap_blk (const T *buf, SIZE_TYPE offset, Func &bit_functor)
 for-each visitor, calls a special visitor functor for each 1 bit range More...
 
template<typename T , typename Func , typename SIZE_TYPE >
void for_each_gap_blk_range (const T *BMRESTRICT buf, SIZE_TYPE offset, unsigned left, unsigned right, Func &bit_functor)
 for-each visitor, calls a special visitor functor for each 1 bit range More...
 
template<typename T , typename N , typename F >
void for_each_bit_block_range (T ***root, N top_size, N nb_from, N nb_to, F &f)
 
template<class BV , class Func >
void for_each_bit_range_no_check (const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
 Implementation of for_each_bit_range without boilerplave checks. More...
 
template<typename BV , typename VECT >
void convert_sub_to_arr (const BV &bv, unsigned sb, VECT &vect)
 convert sub-blocks to an array of set 1s (32-bit) More...
 
template<class SIMBATCH , class SV >
void build_jaccard_similarity_batch (SIMBATCH &sbatch, const SV &sv)
 Utility function to build jaccard similarity batch for sparse_vector<> More...
 
template<class BV >
bool is_interval (const BV &bv, typename BV::size_type left, typename BV::size_type right) BMNOEXCEPT
 Returns true if range is all 1s flanked with 0s Function performs the test on a closed range [left, right] true interval is all 1s AND test(left-1)==false AND test(right+1)==false Examples: 01110 [1,3] - true 11110 [0,3] - true 11110 [1,3] - false. More...
 
template<class BV >
bool find_interval_start (const BV &bv, typename BV::size_type from, typename BV::size_type &pos) BMNOEXCEPT
 Reverse find index of first 1 bit gap (01110) starting from position Reverse scan for the first 1 in a block of continious 1s. Method employs closed interval semantics: 0[pos..from]. More...
 
template<typename BV >
bool find_interval_end (const BV &bv, typename BV::size_type from, typename BV::size_type &pos) BMNOEXCEPT
 Reverse find index of first 1 bit gap (01110) starting from position Reverse scan for the first 1 in a block of continious 1s. Method employs closed interval semantics: 0[pos..from]. More...
 
template<typename T , unsigned BPC, unsigned BPS>
void vect_bit_transpose (const T *arr, unsigned arr_size, T tmatrix[BPC][BPS])
 Generic bit-array transposition function T - array type (any int) BPC - bit plain count BPS - bit plain size. More...
 
template<typename T , unsigned BPC, unsigned BPS>
void vect_bit_trestore (const T tmatrix[BPC][BPS], T *arr)
 Restore bit array from the transposition matrix T - array type (any int) BPC - bit plain count BPS - bit plain size. More...
 
template<typename T , unsigned BPC, unsigned BPS>
void tmatrix_distance (const T tmatrix[BPC][BPS], unsigned distance[BPC][BPC])
 Compute pairwise Row x Row Humming distances on plains(rows) of the transposed bit block. More...
 
template<typename T , unsigned BPC, unsigned BPS>
void bit_iblock_make_pcv (const unsigned distance[BPC][BPC], unsigned char *pc_vector)
 !< ibpc limiter More...
 
void bit_iblock_pcv_stat (const unsigned char *BMRESTRICT pc_vector, const unsigned char *BMRESTRICT pc_vector_end, unsigned *BMRESTRICT pc_vector_stat)
 Compute number of ibpc codes in pc_vector. More...
 
void bit_iblock_reduce (const unsigned tmatrix[bm::set_block_plain_cnt][bm::set_block_plain_size], const unsigned char *BMRESTRICT pc_vector, const unsigned char *BMRESTRICT pc_vector_end, unsigned tmatrix_out[bm::set_block_plain_cnt][bm::set_block_plain_size])
 Matrix reduction based on transformation pc vector. More...
 
template<class TMatrix >
void tmatrix_reduce (TMatrix &tmatrix, const unsigned char *pc_vector, const unsigned effective_cols)
 Transposed Matrix reduction based on transformation pc vector. More...
 
template<class TMatrix >
void tmatrix_restore (TMatrix &tmatrix, const unsigned char *pc_vector, const unsigned effective_cols)
 Transposed Matrix restore based on transformation pc vector. More...
 
template<typename GT , typename BT >
void gap_2_bitblock (const GT *BMRESTRICT gap_buf, BT *BMRESTRICT block, unsigned block_size)
 Copy GAP block body to bit block with DGap transformation. More...
 
template<typename TM >
unsigned find_effective_columns (const TM &tmatrix)
 Compute effective right column border of the t-matrix. More...
 
template<typename T >
BMFORCEINLINEmin_value (T v1, T v2) BMNOEXCEPT
 Get minimum of 2 values. More...
 
template<typename T >
BMFORCEINLINEilog2 (T x) BMNOEXCEPT
 Fast loop-less function to find LOG2. More...
 
template<>
BMFORCEINLINE bm::gap_word_t ilog2 (gap_word_t x) BMNOEXCEPT
 
BMFORCEINLINE unsigned count_leading_zeros (unsigned x) BMNOEXCEPT
 Portable LZCNT with (uses minimal LUT) More...
 
BMFORCEINLINE unsigned count_trailing_zeros (unsigned v) BMNOEXCEPT
 Portable TZCNT with (uses 37-LUT) More...
 
template<typename T >
BMFORCEINLINEilog2_LUT (T x) BMNOEXCEPT
 Lookup table based integer LOG2. More...
 
template<>
BMFORCEINLINE bm::gap_word_t ilog2_LUT< bm::gap_word_t > (bm::gap_word_t x) BMNOEXCEPT
 Lookup table based short integer LOG2. More...
 
template<typename T >
BMFORCEINLINEbit_scan_fwd (T v) BMNOEXCEPT
 
BMFORCEINLINE unsigned bit_scan_reverse32 (unsigned w) BMNOEXCEPT
 
BMFORCEINLINE unsigned bit_scan_forward32 (unsigned w) BMNOEXCEPT
 
BMFORCEINLINE unsigned long long bmi_bslr_u64 (unsigned long long w) BMNOEXCEPT
 
BMFORCEINLINE unsigned long long bmi_blsi_u64 (unsigned long long w)
 
unsigned count_leading_zeros_u32 (unsigned w) BMNOEXCEPT
 32-bit bit-scan reverse More...
 
unsigned count_leading_zeros_u64 (bm::id64_t w) BMNOEXCEPT
 64-bit bit-scan reverse More...
 
unsigned count_trailing_zeros_u32 (unsigned w) BMNOEXCEPT
 32-bit bit-scan fwd More...
 
unsigned count_trailing_zeros_u64 (bm::id64_t w) BMNOEXCEPT
 64-bit bit-scan fwd More...
 
template<class T >
unsigned bit_scan_reverse (T value) BMNOEXCEPT
 
BMFORCEINLINE unsigned mask_r_u32 (unsigned nbit) BMNOEXCEPT
 
BMFORCEINLINE unsigned mask_l_u32 (unsigned nbit) BMNOEXCEPT
 
template<typename Agg , typename It >
void aggregator_pipeline_execute (It first, It last)
 Experimental method ro run multiple aggregators in sync. More...
 
template<class BV >
size_t serialize (const BV &bv, unsigned char *buf, bm::word_t *temp_block=0, unsigned serialization_flags=0)
 Saves bitvector into memory. More...
 
template<class BV >
size_t serialize (BV &bv, unsigned char *buf, unsigned serialization_flags=0)
 Saves bitvector into memory. Allocates temporary memory block for bvector. More...
 
template<class BV >
size_t deserialize (BV &bv, const unsigned char *buf, bm::word_t *temp_block=0, const bm::bv_ref_vector< BV > *ref_vect=0)
 Bitvector deserialization from a memory BLOB. More...
 
template<class BV >
void deserialize_range (BV &bv, const unsigned char *buf, typename BV::size_type from, typename BV::size_type to, const bm::bv_ref_vector< BV > *ref_vect=0)
 Bitvector range deserialization from a memory BLOB. More...
 
template<class BV >
BV::size_type process_operation (BV &bv, BV &bv_tmp, bm::set_operation op)
 Utility function to process operation using temp vector. More...
 
void * aligned_new_malloc (size_t size)
 Aligned malloc (unlike classic malloc it throws bad_alloc exception) More...
 
void aligned_free (void *ptr) BMNOEXCEPT
 Aligned free. More...
 
template<typename SV >
void dynamic_range_clip_high (SV &svect, unsigned high_bit)
 Clip dynamic range for signal higher than specified. More...
 
template<typename SV >
void dynamic_range_clip_low (SV &svect, unsigned low_bit)
 Clip dynamic range for signal lower than specified (boost) More...
 
template<typename SV >
bool sparse_vector_find_first_mismatch (const SV &sv1, const SV &sv2, typename SV::size_type &midx, bm::null_support null_proc=bm::use_null)
 Find first mismatch (element which is different) between two sparse vectors (uses linear scan in bit-vector plains) More...
 
template<typename SV1 , typename SV2 >
void sparse_vector_find_mismatch (typename SV1::bvector_type &bv, const SV1 &sv1, const SV2 &sv2, bm::null_support null_proc)
 Find mismatch vector, indicating positions of mismatch between two sparse vectors (uses linear scan in bit-vector plains) More...
 
template<class SV >
void sparse_vector_serialize (const SV &sv, sparse_vector_serial_layout< SV > &sv_layout, bm::word_t *temp_block=0)
 Serialize sparse vector into a memory buffer(s) structure. More...
 
template<class SV >
int sparse_vector_deserialize (SV &sv, const unsigned char *buf, bm::word_t *temp_block=0)
 Deserialize sparse vector. More...
 

Variables

const unsigned short set_bitscan_wave_size = 4
 Size of bit decode wave in words. More...
 
const unsigned id_max32 = 0xFFFFFFFFu
 
const unsigned set_block_size = 2048u
 
const unsigned set_block_shift = 16u
 
const unsigned set_block_mask = 0xFFFFu
 
const unsigned set_blkblk_mask = 0xFFFFFFu
 
const unsigned set_block_alloc_size = bm::set_block_size * unsigned(sizeof(bm::word_t))
 
const unsigned set_block_plain_size = bm::set_block_size / 32u
 
const unsigned set_block_plain_cnt = (unsigned)(sizeof(bm::word_t) * 8u)
 
const unsigned block_waves = 64
 
const unsigned set_block_digest_wave_size = bm::set_block_size / bm::block_waves
 
const unsigned set_block_digest_pos_shift = 10
 
const unsigned set_word_shift = 5u
 
const unsigned set_word_mask = 0x1Fu
 
const unsigned gap_max_buff_len = 1280
 
const unsigned gap_max_bits = 65536
 
const unsigned gap_equiv_len
 
const unsigned gap_max_bits_cmrz = bm::gap_max_bits / 2
 
const unsigned gap_levels = 4
 
const unsigned gap_max_level = bm::gap_levels - 1
 
const unsigned bie_cut_off = 16384
 
const unsigned set_array_size32 = 256u
 
const unsigned set_sub_array_size = set_array_size32
 
const unsigned set_array_shift = 8u
 
const unsigned set_array_mask = 0xFFu
 
const unsigned set_total_blocks32 = (bm::set_array_size32 * bm::set_array_size32)
 
const unsigned set_sub_total_bits = bm::set_sub_array_size * bm::gap_max_bits
 
const unsigned id_max = bm::id_max32
 
const unsigned set_top_array_size = bm::set_array_size32
 
const unsigned set_total_blocks = bm::set_total_blocks32
 
const unsigned bits_in_block = bm::set_block_size * unsigned((sizeof(bm::word_t) * 8))
 
const unsigned bits_in_array = bm::bits_in_block * bm::set_array_size32
 
const unsigned rs3_border0 = 21824
 
const unsigned rs3_border1 = (rs3_border0 * 2)
 
const unsigned rs3_half_span = rs3_border0 / 2
 
const unsigned sub_block3_size = bm::gap_max_bits / 4
 
const id64_t all_bits_mask = 0xffffffffffffffffULL
 
const unsigned set_block_size_op = bm::set_block_size / 2
 
const unsigned char ibpc_uncompr = 0
 
const unsigned char ibpc_all_zero = 1
 !< plain uncompressed More...
 
const unsigned char ibpc_all_one = 2
 !< plain ALL ZERO More...
 
const unsigned char ibpc_equiv = 3
 !< plain ALL ONE More...
 
const unsigned char ibpc_close = 4
 !< plain is equal to plain M More...
 
const unsigned char ibpc_end = 8
 !< plain is close to plain M More...
 
const unsigned set_compression_max = 6
 Maximum supported compression level. More...
 
const unsigned set_compression_default = 6
 Default compression level. More...
 
const unsigned char set_block_end = 0
 End of serialization. More...
 
const unsigned char set_block_1zero = 1
 One all-zero block. More...
 
const unsigned char set_block_1one = 2
 One block all-set (1111...) More...
 
const unsigned char set_block_8zero = 3
 Up to 256 zero blocks. More...
 
const unsigned char set_block_8one = 4
 Up to 256 all-set blocks. More...
 
const unsigned char set_block_16zero = 5
 Up to 65536 zero blocks. More...
 
const unsigned char set_block_16one = 6
 UP to 65536 all-set blocks. More...
 
const unsigned char set_block_32zero = 7
 Up to 4G zero blocks. More...
 
const unsigned char set_block_32one = 8
 UP to 4G all-set blocks. More...
 
const unsigned char set_block_azero = 9
 All other blocks zero. More...
 
const unsigned char set_block_aone = 10
 All other blocks one. More...
 
const unsigned char set_block_bit = 11
 Plain bit block. More...
 
const unsigned char set_block_sgapbit = 12
 SGAP compressed bitblock. More...
 
const unsigned char set_block_sgapgap = 13
 SGAP compressed GAP block. More...
 
const unsigned char set_block_gap = 14
 Plain GAP block. More...
 
const unsigned char set_block_gapbit = 15
 GAP compressed bitblock. More...
 
const unsigned char set_block_arrbit = 16
 List of bits ON. More...
 
const unsigned char set_block_bit_interval = 17
 Interval block. More...
 
const unsigned char set_block_arrgap = 18
 List of bits ON (GAP block) More...
 
const unsigned char set_block_bit_1bit = 19
 Bit block with 1 bit ON. More...
 
const unsigned char set_block_gap_egamma = 20
 Gamma compressed GAP block. More...
 
const unsigned char set_block_arrgap_egamma = 21
 Gamma compressed delta GAP array. More...
 
const unsigned char set_block_bit_0runs = 22
 Bit block with encoded zero intervals. More...
 
const unsigned char set_block_arrgap_egamma_inv = 23
 Gamma compressed inverted delta GAP array. More...
 
const unsigned char set_block_arrgap_inv = 24
 List of bits OFF (GAP block) More...
 
const unsigned char set_block_64zero = 25
 lots of zero blocks More...
 
const unsigned char set_block_64one = 26
 lots of all-set blocks More...
 
const unsigned char set_block_gap_bienc = 27
 Interpolated GAP block (legacy) More...
 
const unsigned char set_block_arrgap_bienc = 28
 Interpolated GAP array. More...
 
const unsigned char set_block_arrgap_bienc_inv = 29
 Interpolated GAP array (inverted) More...
 
const unsigned char set_block_arrbit_inv = 30
 List of bits OFF. More...
 
const unsigned char set_block_arr_bienc = 31
 Interpolated block as int array. More...
 
const unsigned char set_block_arr_bienc_inv = 32
 Interpolated inverted block int array. More...
 
const unsigned char set_block_bitgap_bienc = 33
 Interpolated bit-block as GAPs. More...
 
const unsigned char set_block_bit_digest0 = 34
 H-compression with digest mask. More...
 
const unsigned char set_block_ref_eq = 35
 block is a copy of a reference block More...
 
const unsigned char set_block_xor_ref8 = 36
 block is masked XOR of a reference block (8-bit) More...
 
const unsigned char set_block_xor_ref16 = 37
 block is masked XOR of a reference block (16-bit) More...
 
const unsigned char set_block_xor_ref32 = 38
 ..... 32-bit (should never happen) More...
 
const unsigned char set_block_xor_gap_ref8 = 39
 ..... 8-bit More...
 
const unsigned char set_block_xor_gap_ref16 = 40
 ..... 16-bit More...
 
const unsigned char set_block_xor_gap_ref32 = 41
 ..... 32-bit (should never happen) More...
 
const unsigned char set_block_xor_chain = 42
 XOR chain (reserved) More...
 
const unsigned char set_block_gap_bienc_v2 = 43
 Interpolated GAP block (v2) More...
 
const unsigned char set_block_arrgap_bienc_v2 = 44
 //!< Interpolated GAP array (v2) More...
 
const unsigned char set_block_arrgap_bienc_inv_v2 = 45
 Interpolated GAP array (inverted) More...
 
const unsigned char set_block_bitgap_bienc_v2 = 46
 Interpolated bit-block as GAPs (v2 - reseved) More...
 
const unsigned char set_nb_bookmark16 = 47
 jump ahead mark (16-bit) More...
 
const unsigned char set_nb_bookmark24 = 48
 jump ahead mark (24-bit) More...
 
const unsigned char set_nb_bookmark32 = 49
 jump ahead mark (32-bit) More...
 
const unsigned char set_nb_sync_mark8 = 50
 bookmark sync point (8-bits) More...
 
const unsigned char set_nb_sync_mark16 = 51
 
const unsigned char set_nb_sync_mark24 = 52
 
const unsigned char set_nb_sync_mark32 = 53
 
const unsigned char set_nb_sync_mark48 = 54
 
const unsigned char set_nb_sync_mark64 = 55
 ..... 64-bit (should never happen) More...
 
const unsigned char set_sblock_bienc = 56
 super-block interpolated list More...
 
const unsigned char set_block_arr_bienc_8bh = 57
 BIC block 8bit header. More...
 
const unsigned sparse_max_l5 = 48
 
const unsigned sparse_max_l6 = 256
 
const unsigned sblock_flag_sb16 = (1u << 0)
 16-bit SB index (8-bit by default) More...
 
const unsigned sblock_flag_sb32 = (1u << 1)
 32-bit SB index More...
 
const unsigned sblock_flag_min16 = (1u << 2)
 16-bit minv More...
 
const unsigned sblock_flag_min24 = (1u << 3)
 24-bit minv More...
 
const unsigned sblock_flag_min32 = bm::sblock_flag_min16 | bm::sblock_flag_min24
 
const unsigned sblock_flag_len16 = (1u << 4)
 16-bit len (8-bit by default) More...
 
const unsigned sblock_flag_max16 = (1u << 5)
 
const unsigned sblock_flag_max24 = (1u << 6)
 
const unsigned sblock_flag_max32 = bm::sblock_flag_max16 | bm::sblock_flag_max24
 

Typedef Documentation

◆ bit_operation_count_func_type

typedef bm::id_t(* bm::bit_operation_count_func_type) (const bm::word_t *BMRESTRICT, const bm::word_t *BMRESTRICT)

Definition at line 8941 of file bmfunc.h.

◆ gap_operation_func_type

typedef gap_word_t*(* bm::gap_operation_func_type) (const gap_word_t *BMRESTRICT, const gap_word_t *BMRESTRICT, gap_word_t *BMRESTRICT, unsigned &)

Definition at line 8935 of file bmfunc.h.

◆ gap_operation_to_bitset_func_type

typedef void(* bm::gap_operation_to_bitset_func_type) (unsigned *, const gap_word_t *)

Definition at line 8931 of file bmfunc.h.

◆ gap_word_t

typedef unsigned short bm::gap_word_t

Definition at line 77 of file bmconst.h.

◆ id64_t

typedef unsigned long long int bm::id64_t
Examples:
inv_list.cpp.

Definition at line 34 of file bmconst.h.

◆ id_t

typedef unsigned int bm::id_t
Examples:
svsample06.cpp.

Definition at line 37 of file bmconst.h.

◆ short_t

typedef unsigned short bm::short_t

Definition at line 39 of file bmconst.h.

◆ word_t

typedef unsigned int bm::word_t
Examples:
sample6.cpp.

Definition at line 38 of file bmconst.h.

◆ wordop_t

Definition at line 127 of file bmconst.h.

Enumeration Type Documentation

◆ ByteOrder

Byte orders recognized by the library.

Enumerator
BigEndian 
LittleEndian 

Definition at line 428 of file bmconst.h.

◆ serialization_header_mask

Enumerator
BM_HM_DEFAULT 
BM_HM_RESIZE 

resized vector

BM_HM_ID_LIST 

id list stored

BM_HM_NO_BO 

no byte-order

BM_HM_NO_GAPL 

no GAP levels

BM_HM_64_BIT 

64-bit vector

BM_HM_HXOR 

horizontal XOR compression turned ON

BM_HM_SPARSE 

very sparse vector

Definition at line 1026 of file bmserial.h.

◆ set_representation

set representation variants

Enumerator
set_bitset 

Simple bitset.

set_gap 

GAP-RLE compression.

set_array1 

array of set 1 values

set_array0 

array of 0 values

Definition at line 201 of file bmconst.h.

◆ simd_codes

codes for supported SIMD optimizations

Enumerator
simd_none 
simd_sse2 

!< No SIMD or any other optimization

simd_sse42 

!< Intel SSE2

simd_avx2 

!< Intel SSE4.2

simd_avx512 

!< Intel AVX2

Definition at line 414 of file bmconst.h.

◆ xor_complement_match

XOR complementarity type between 2 blocks.

Enumerator
e_no_xor_match 
e_xor_match_GC 
e_xor_match_BC 
e_xor_match_iBC 

Definition at line 36 of file bmxor.h.

Function Documentation

◆ aligned_free()

void bm::aligned_free ( void *  ptr)
inline

◆ aligned_new_malloc()

void* bm::aligned_new_malloc ( size_t  size)
inline

Aligned malloc (unlike classic malloc it throws bad_alloc exception)

To allocate temp bit-block use: bm::aligned_new_malloc(bm::set_block_alloc_size);

Definition at line 396 of file bmalloc.h.

References BM_ALLOC_ALIGN.

Referenced by bm::aggregator< bvector_type >::aggregator(), bm::bvps_addr_resolver< bvector_type >::construct_rs_index(), and bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::decode_buf().

◆ avx2_bit_block_gather_scatter()

void bm::avx2_bit_block_gather_scatter ( unsigned *BMRESTRICT  arr,
const unsigned *BMRESTRICT  blk,
const unsigned *BMRESTRICT  idx,
unsigned  size,
unsigned  start,
unsigned  bit_idx 
)
inline

AVX2 bit block gather-scatter

Parameters
arr- destination array to set bits
blk- source bit-block
idx- gather index array
size- gather array size
start- gaher start index
bit_idx- bit to set in the target array

Definition at line 2764 of file bmavx2.h.

References BM_ALIGN32, BM_ALIGN32ATTR, set_block_mask, set_word_mask, and set_word_shift.

Referenced by bit_block_gather_scatter().

◆ avx2_bit_count_or()

bm::id_t bm::avx2_bit_count_or ( const __m256i *BMRESTRICT  block,
const __m256i *BMRESTRICT  block_end,
const __m256i *BMRESTRICT  mask_block 
)
inline

Definition at line 337 of file bmavx2.h.

References BM_AVX2_BIT_COUNT, and BM_AVX2_POPCNT_PROLOG.

◆ avx2_gap_sum_arr()

const bm::gap_word_t* bm::avx2_gap_sum_arr ( const bm::gap_word_t pbuf,
unsigned  avx_vect_waves,
unsigned *  sum 
)
inline

Definition at line 2094 of file bmavx2.h.

Referenced by gap_bit_count_unr().

◆ avx2_idx_arr_block_lookup()

unsigned bm::avx2_idx_arr_block_lookup ( const unsigned *  idx,
unsigned  size,
unsigned  nb,
unsigned  start 
)
inline

AVX2 index lookup to check what belongs to the same block (8 elements)

Definition at line 2133 of file bmavx2.h.

References set_block_shift.

◆ avx2_set_block_bits()

void bm::avx2_set_block_bits ( bm::word_t *BMRESTRICT  block,
const unsigned *BMRESTRICT  idx,
unsigned  start,
unsigned  stop 
)
inline

SSE4.2 bulk bit set

Definition at line 2174 of file bmavx2.h.

References BM_ALIGN32, BM_ALIGN32ATTR, BMFORCEINLINE, set_block_mask, set_word_mask, and set_word_shift.

◆ avx2_set_block_bits2()

void bm::avx2_set_block_bits2 ( bm::word_t *BMRESTRICT  block,
const unsigned *BMRESTRICT  idx,
unsigned  start,
unsigned  stop 
)
inline

Experimental code to set bits via AVX strides.

Definition at line 2350 of file bmavx2.h.

References set_block_mask.

◆ avx2_set_block_bits3()

void bm::avx2_set_block_bits3 ( bm::word_t *BMRESTRICT  block,
const unsigned *BMRESTRICT  idx,
unsigned  start,
unsigned  stop 
)
inline

Experimental code to set bits via AVX strides.

Definition at line 2389 of file bmavx2.h.

References avx2_setbit_256(), BM_ALIGN32, BM_ALIGN32ATTR, set_block_mask, set_word_mask, and set_word_shift.

◆ avx2_setbit_256()

BMFORCEINLINE __m256i bm::avx2_setbit_256 ( __m256i  target,
__m256i  source 
)

Set a bits in an AVX target, by indexes (int4) from the source.

Definition at line 2303 of file bmavx2.h.

Referenced by avx2_set_block_bits3().

◆ avx2_setbit_to256()

__m256i bm::avx2_setbit_to256 ( unsigned  i)
inline

Experiemntal.

Set number of bits in AVX register from 0 to i [ 000000 00000 0000000 00011 11111 ] - i = 7

Definition at line 2482 of file bmavx2.h.

◆ bit_block_any_range()

bm::id_t bm::bit_block_any_range ( const bm::word_t block,
bm::word_t  left,
bm::word_t  right 
)
inline

◆ bit_block_change32()

unsigned bm::bit_block_change32 ( const bm::word_t block,
unsigned  size 
)
inline

Function calculates number of times when bit value changed

Definition at line 4944 of file bmfunc.h.

References BM_INCWORD_BITCOUNT.

Referenced by bit_block_calc_change(), bit_block_change_bc(), and compute_complexity_descr().

◆ bit_block_change_bc()

void bm::bit_block_change_bc ( const bm::word_t *BMRESTRICT  block,
unsigned *BMRESTRICT  gc,
unsigned *BMRESTRICT  bc 
)
inline

Function calculates basic bit-block statistics number of times when bit value changed (GAPS) and population count

Parameters
block- bit-block pointer
gc- [output] gap_count
bc- [output] bit count

Definition at line 4992 of file bmfunc.h.

References bit_block_change32(), bit_block_count(), BM_ASSERT, set_block_size, and VECT_BLOCK_CHANGE_BC.

Referenced by bm::xor_scanner< bvector_type >::compute_x_block_stats(), bm::serializer< bvector_type >::find_bit_best_encoding(), bm::serializer< bvector_type >::find_bit_best_encoding_l5(), bm::xor_scanner< bvector_type >::search_best_xor_mask(), and bm::xor_scanner< bvector_type >::validate_found().

◆ bit_block_xor()

void bm::bit_block_xor ( bm::word_t target_block,
const bm::word_t block,
const bm::word_t xor_block,
bm::id64_t  digest 
)
inline

Build partial XOR product of 2 bit-blocks using digest mask.

Parameters
target_block- target := block ^ xor_block
block- arg1
xor_block- arg2
digest- mask for each block wave to XOR (1) or just copy (0)

Definition at line 273 of file bmxor.h.

References block_waves, BM_ASSERT, set_block_digest_wave_size, and VECT_BIT_BLOCK_XOR.

◆ bit_block_xor_change()

void bm::bit_block_xor_change ( const bm::word_t *BMRESTRICT  block,
const bm::word_t *BMRESTRICT  xor_block,
unsigned  size,
unsigned *BMRESTRICT  gc,
unsigned *BMRESTRICT  bc 
)
inline

Function calculates number of times when bit value changed

Definition at line 103 of file bmxor.h.

References bit_block_xor_change32(), and VECT_BLOCK_XOR_CHANGE.

Referenced by compute_xor_complexity_descr().

◆ bit_iblock_pcv_stat()

void bm::bit_iblock_pcv_stat ( const unsigned char *BMRESTRICT  pc_vector,
const unsigned char *BMRESTRICT  pc_vector_end,
unsigned *BMRESTRICT  pc_vector_stat 
)
inline

Compute number of ibpc codes in pc_vector.

Definition at line 443 of file bmtrans.h.

References BM_ASSERT.

Referenced by bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::compute_distance_matrix().

◆ bit_iblock_reduce()

void bm::bit_iblock_reduce ( const unsigned  tmatrix[bm::set_block_plain_cnt][bm::set_block_plain_size],
const unsigned char *BMRESTRICT  pc_vector,
const unsigned char *BMRESTRICT  pc_vector_end,
unsigned  tmatrix_out[bm::set_block_plain_cnt][bm::set_block_plain_size] 
)
inline

Matrix reduction based on transformation pc vector.

Definition at line 463 of file bmtrans.h.

References BM_ASSERT, ibpc_all_one, ibpc_all_zero, ibpc_close, ibpc_equiv, ibpc_uncompr, bm::tmatrix< T, ROWS, COLS >::row(), set_block_plain_cnt, and set_block_plain_size.

◆ bit_recomb()

template<class It1 , class It2 , class BinaryOp , class Encoder >
void bm::bit_recomb ( It1 &  it1,
It2 &  it2,
BinaryOp &  op,
Encoder &  enc,
unsigned  block_size = bm::set_block_size 
)

◆ bit_scan_forward32()

BMFORCEINLINE unsigned bm::bit_scan_forward32 ( unsigned  w)

◆ bit_scan_fwd()

template<typename T >
BMFORCEINLINE T bm::bit_scan_fwd ( v)

Definition at line 295 of file bmutil.h.

References BMFORCEINLINE.

Referenced by bit_scan_forward32(), bm::bit_in< TDecoder >::gamma(), and sse2_gap_find().

◆ bit_scan_reverse32()

BMFORCEINLINE unsigned bm::bit_scan_reverse32 ( unsigned  w)

◆ bit_to_gap()

unsigned bm::bit_to_gap ( gap_word_t *BMRESTRICT  dest,
const unsigned *BMRESTRICT  block,
unsigned  dest_len 
)
inline

◆ bitscan_bsf()

template<typename B , typename OT >
unsigned short bm::bitscan_bsf ( unsigned  w,
B *  bits,
OT  offs 
)

Definition at line 725 of file bmfunc.h.

References count_trailing_zeros_u32().

◆ bitscan_nibble()

unsigned bm::bitscan_nibble ( unsigned  w,
unsigned *  bits 
)
inline

portable, switch based bitscan

Definition at line 398 of file bmfunc.h.

◆ block_any()

bool bm::block_any ( const bm::word_t *const BMRESTRICT  block)
inline

Returns "true" if one bit is set in the block Function check for block varieties.

Definition at line 6198 of file bmfunc.h.

References bit_is_all_zero(), BM_IS_GAP, BMGAP_PTR, gap_is_all_zero(), and IS_FULL_BLOCK.

Referenced by bm::bvector<>::any_range().

◆ block_any_range()

bool bm::block_any_range ( const bm::word_t *const BMRESTRICT  block,
unsigned  left,
unsigned  right 
)
inline

Returns "true" if one bit is set in the block [left, right] Function check for block varieties.

Definition at line 6177 of file bmfunc.h.

References bit_block_any_range(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, gap_any_range(), gap_max_bits, and IS_FULL_BLOCK.

Referenced by bm::bvector<>::any_range().

◆ block_find_first_diff()

bool bm::block_find_first_diff ( const bm::word_t *BMRESTRICT  blk,
const bm::word_t *BMRESTRICT  arg_blk,
unsigned *BMRESTRICT  pos 
)
inline

Find first bit which is different between two blocks (GAP or bit)

Parameters
blk- block 1
arg_blk- block 2
pos- out - position of difference (undefined if blocks are equal)
Returns
true if difference was found

Definition at line 8626 of file bmfunc.h.

References bit_find_first(), bit_find_first_diff(), BM_IS_GAP, BMGAP_PTR, gap_convert_to_bitset(), gap_find_first(), and gap_find_first_diff().

Referenced by bm::bvector<>::find_first_mismatch().

◆ block_find_interval_end()

unsigned bm::block_find_interval_end ( const bm::word_t *BMRESTRICT  block,
unsigned  nbit_from,
unsigned *BMRESTRICT  found_nbit 
)
inline

Find end of the current 111 interval.

Returns
search result code 0 - not found, 1 found, 2 - found at the end

Definition at line 5948 of file bmfunc.h.

References bit_block_find_interval_end(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, gap_find_interval_end(), gap_max_bits, and IS_FULL_BLOCK.

Referenced by find_interval_end().

◆ block_find_interval_start()

unsigned bm::block_find_interval_start ( const bm::word_t *BMRESTRICT  block,
unsigned  nbit_from,
unsigned *BMRESTRICT  found_nbit 
)
inline

Find start of the current 111 interval.

Returns
search result code 0 - not found, 1 found, 2 - found at the start

Definition at line 6112 of file bmfunc.h.

References bit_block_find_interval_start(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, gap_find_interval_start(), gap_max_bits, and IS_FULL_BLOCK.

Referenced by find_interval_start().

◆ block_find_rank()

template<typename SIZE_TYPE >
SIZE_TYPE bm::block_find_rank ( const bm::word_t *const  block,
SIZE_TYPE  rank,
unsigned  nbit_from,
unsigned &  nbit_pos 
)

Find rank in block (GAP or BIT)

Parameters
block- bit block buffer pointer
rank- rank to find (must be > 0)
nbit_from- start bit position in block
nbit_pos- found position
Returns
0 if position with rank was found, or the remaining rank (rank - population count)

Definition at line 8355 of file bmfunc.h.

References bit_find_rank(), BM_IS_GAP, BMGAP_PTR, and gap_find_rank().

Referenced by bm::bvector<>::find_rank(), and bm::bvector<>::select().

◆ block_find_reverse()

bool bm::block_find_reverse ( const bm::word_t *BMRESTRICT  block,
unsigned  nbit_from,
unsigned *BMRESTRICT  found_nbit 
)
inline

Reverse find 1.

Returns
search result code 0 - not found, 1 found

Definition at line 6147 of file bmfunc.h.

References bit_block_find_prev(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, gap_find_prev(), gap_max_bits, and IS_FULL_BLOCK.

Referenced by bm::bvector<>::find_reverse().

◆ block_is_all_one_range()

bool bm::block_is_all_one_range ( const bm::word_t *const BMRESTRICT  block,
unsigned  left,
unsigned  right 
)
inline

Returns "true" if all bits are 1 in the block [left, right] Function check for block varieties.

Definition at line 5823 of file bmfunc.h.

References bit_block_is_all_one_range(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, gap_is_all_one_range(), and gap_max_bits.

Referenced by bm::bvector<>::is_all_one_range().

◆ block_is_interval()

bool bm::block_is_interval ( const bm::word_t *const BMRESTRICT  block,
unsigned  left,
unsigned  right 
)
inline

Returns "true" if all bits are 1 in the block [left, right] and border bits are 0.

Definition at line 5844 of file bmfunc.h.

References bit_block_is_all_one_range(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, gap_is_interval(), gap_max_bits, set_word_mask, and set_word_shift.

Referenced by is_interval().

◆ block_ptr_array_range()

bool bm::block_ptr_array_range ( bm::word_t **  arr,
unsigned &  left,
unsigned &  right 
)
inline

array range detector

Definition at line 9264 of file bmfunc.h.

References BM_ASSERT, and set_sub_array_size.

◆ block_range_scan()

template<typename It , typename SIZE_TYPE >
It bm::block_range_scan ( It  first,
It  last,
SIZE_TYPE  nblock,
SIZE_TYPE *  max_id 
)

Internal algorithms scans the input for the block range limit.

Definition at line 983 of file bmalgo_impl.h.

References BM_ASSERT, id_max, and set_block_shift.

Referenced by combine_or(), combine_sub(), and combine_xor().

◆ block_to_global_index()

bm::id_t bm::block_to_global_index ( unsigned  i,
unsigned  j,
unsigned  block_idx 
)
inline

calculate bvector<> global bit-index from block-local coords

Returns
bit index in linear bit-vector coordinates

Definition at line 9430 of file bmfunc.h.

References gap_max_bits, and set_sub_array_size.

Referenced by bm::aggregator< bvector_type >::find_first_and_sub(), and lower_bound_u64().

◆ bmfor_each()

template<class T , class F >
F bm::bmfor_each ( first,
last,
f 
)

Special BM optimized analog of STL for_each

Definition at line 2063 of file bmfunc.h.

◆ bmi_blsi_u64()

BMFORCEINLINE unsigned long long bm::bmi_blsi_u64 ( unsigned long long  w)

◆ bmi_bslr_u64()

BMFORCEINLINE unsigned long long bm::bmi_bslr_u64 ( unsigned long long  w)

◆ build_jaccard_similarity_batch()

template<class SIMBATCH , class SV >
void bm::build_jaccard_similarity_batch ( SIMBATCH &  sbatch,
const SV &  sv 
)

Utility function to build jaccard similarity batch for sparse_vector<>

Definition at line 190 of file bmalgo_similarity.h.

References COUNT_AND, COUNT_OR, and bm::distance_metric_descriptor::metric.

◆ check_block_one()

bool bm::check_block_one ( const bm::word_t blk,
bool  deep_scan 
)
inline

Checks if block has only 1 bits.

Parameters
blk- Block's pointer
deep_scan- flag to do full bit block verification (scan) when deep scan is not requested result can be approximate
Returns
true if block consists of 1 bits.

Definition at line 8478 of file bmfunc.h.

References BM_IS_GAP, BMGAP_PTR, gap_is_all_one(), is_bits_one(), and IS_FULL_BLOCK.

Referenced by bm::bvector<>::is_all_one_range(), and bm::serializer< bvector_type >::serialize().

◆ check_block_zero()

bool bm::check_block_zero ( const bm::word_t blk,
bool  deep_scan 
)
inline

Checks all conditions and returns true if block consists of only 0 bits.

Parameters
blk- Blocks's pointer
deep_scan- flag to do full bit block verification (scan) when deep scan is not requested result can be approximate
Returns
true if all bits are in the block are 0

Definition at line 8454 of file bmfunc.h.

References bit_is_all_zero(), BM_IS_GAP, BMGAP_PTR, gap_is_all_zero(), and IS_FULL_BLOCK.

Referenced by bm::iterator_deserializer< BV, bm::serial_stream_iterator >::deserialize(), and bm::serializer< bvector_type >::serialize().

◆ combine_any_operation_with_block() [1/2]

void bm::combine_any_operation_with_block ( const bm::word_t blk,
unsigned  gap,
const bm::word_t arg_blk,
unsigned  arg_gap,
distance_metric_descriptor dmit,
distance_metric_descriptor dmit_end 
)
inline

◆ combine_any_operation_with_block() [2/2]

bm::distance_metric_descriptor::size_type bm::combine_any_operation_with_block ( const bm::word_t blk,
unsigned  gap,
const bm::word_t arg_blk,
unsigned  arg_gap,
distance_metric  metric 
)
inline

Convenience internal function to compute combine any for one metric

Definition at line 648 of file bmalgo_impl.h.

References combine_any_operation_with_block(), bm::distance_metric_descriptor::metric, and bm::distance_metric_descriptor::result.

◆ combine_count_and_operation_with_block()

unsigned bm::combine_count_and_operation_with_block ( const bm::word_t blk,
const bm::word_t arg_blk 
)
inline

Internal function computes AND distance.

Definition at line 342 of file bmalgo_impl.h.

References bit_operation_and_count(), BM_IS_GAP, BMGAP_PTR, gap_bitset_and_count(), and gap_count_and().

Referenced by distance_and_operation().

◆ combine_count_operation_with_block() [1/2]

void bm::combine_count_operation_with_block ( const bm::word_t blk,
const bm::word_t arg_blk,
distance_metric_descriptor dmit,
distance_metric_descriptor dmit_end 
)
inline

◆ combine_count_operation_with_block() [2/2]

unsigned bm::combine_count_operation_with_block ( const bm::word_t blk,
const bm::word_t arg_blk,
distance_metric  metric 
)
inline

Convenience internal function to compute combine count for one metric

Definition at line 629 of file bmalgo_impl.h.

References combine_count_operation_with_block(), bm::distance_metric_descriptor::metric, and bm::distance_metric_descriptor::result.

◆ compute_complexity_descr()

void bm::compute_complexity_descr ( const bm::word_t *BMRESTRICT  block,
block_waves_xor_descr &BMRESTRICT  x_descr 
)
inline

Compute reference (non-XOR) 64-dim complexity descriptor for the target block.

Phase 1 of the XOR filtering process is to establish the base metric

Definition at line 140 of file bmxor.h.

References bit_block_change32(), bit_count_min_unroll(), block_waves, set_block_digest_wave_size, and VECT_BLOCK_CHANGE.

Referenced by bm::xor_scanner< bvector_type >::compute_x_block_stats().

◆ compute_xor_complexity_descr()

void bm::compute_xor_complexity_descr ( const bm::word_t *BMRESTRICT  block,
const bm::word_t *BMRESTRICT  xor_block,
bm::block_waves_xor_descr &BMRESTRICT  x_descr,
bm::xor_complement_match &BMRESTRICT  match_type,
bm::id64_t &BMRESTRICT  digest,
unsigned &BMRESTRICT  block_gain 
)
inline

Compute reference complexity descriptor based on XOR vector.

Returns the digest of sub-blocks where XOR filtering improved the metric (function needs reference to estimate the improvement).

part of Phase 2 of the XOR filtering process

See also
compute_sub_block_complexity_descr

Definition at line 175 of file bmxor.h.

References bit_block_xor_change(), block_waves, calc_block_digest0(), e_no_xor_match, e_xor_match_BC, e_xor_match_GC, and set_block_digest_wave_size.

Referenced by bm::xor_scanner< bvector_type >::search_best_xor_mask().

◆ convert_sub_to_arr()

template<typename BV , typename VECT >
void bm::convert_sub_to_arr ( const BV &  bv,
unsigned  sb,
VECT &  vect 
)

convert sub-blocks to an array of set 1s (32-bit)

Definition at line 1913 of file bmalgo_impl.h.

References gap_max_bits, id_max, and set_sub_array_size.

Referenced by bm::serializer< bvector_type >::bienc_arr_sblock().

◆ count_leading_zeros_u32()

unsigned bm::count_leading_zeros_u32 ( unsigned  w)
inline

32-bit bit-scan reverse

Definition at line 354 of file bmutil.h.

References BM_ASSERT, and count_leading_zeros().

◆ count_leading_zeros_u64()

unsigned bm::count_leading_zeros_u64 ( bm::id64_t  w)
inline

64-bit bit-scan reverse

Definition at line 371 of file bmutil.h.

References bit_scan_reverse32(), and BM_ASSERT.

Referenced by gap_and_to_bitset(), and gap_sub_to_bitset().

◆ count_nz()

template<typename VT , typename SZ >
SZ bm::count_nz ( const VT *  arr,
SZ  arr_size 
)

Find count of non-zero elements in the array.

Definition at line 9530 of file bmfunc.h.

Referenced by bm::sparse_vector_serializer< SV >::encode_remap_matrix().

◆ count_trailing_zeros_u32()

unsigned bm::count_trailing_zeros_u32 ( unsigned  w)
inline

32-bit bit-scan fwd

Definition at line 399 of file bmutil.h.

References bit_scan_forward32(), and BM_ASSERT.

Referenced by bitscan_bsf(), and word_select32_bitscan_tz().

◆ count_trailing_zeros_u64()

unsigned bm::count_trailing_zeros_u64 ( bm::id64_t  w)
inline

64-bit bit-scan fwd

Definition at line 417 of file bmutil.h.

References bit_scan_forward32(), and BM_ASSERT.

Referenced by bit_find_first_diff(), bitscan_bsf64(), gap_and_to_bitset(), gap_sub_to_bitset(), and word_select64_bitscan_tz().

◆ dgap_2_gap()

template<typename T >
void bm::dgap_2_gap ( const T *BMRESTRICT  dgap_buf,
T *BMRESTRICT  gap_buf,
gap_header = 0 
)

Convert D-GAP buffer into GAP buffer.

GAP representation is GAP[N] = DGAP[N] + DGAP[N-1]

Parameters
dgap_buf- Delta-GAP buffer
gap_header- GAP header word
gap_buf- GAP buffer

Definition at line 2627 of file bmfunc.h.

◆ distance_stage()

void bm::distance_stage ( const distance_metric_descriptor dmit,
const distance_metric_descriptor dmit_end,
bool *  is_all_and 
)
inline

Staging function for distance operation.

Returns
temp block allocated (or NULL)

Definition at line 669 of file bmalgo_impl.h.

References COUNT_AND.

Referenced by distance_operation(), and distance_operation_any().

◆ dm_control()

bm::id64_t bm::dm_control ( unsigned  from,
unsigned  to 
)
inline

digest mask control generation (for debug and test only)

Definition at line 1022 of file bmfunc.h.

References BMFORCEINLINE.

◆ find_effective_columns()

template<typename TM >
unsigned bm::find_effective_columns ( const TM &  tmatrix)

Compute effective right column border of the t-matrix.

Definition at line 714 of file bmtrans.h.

References bm::tmatrix< T, ROWS, COLS >::row().

Referenced by bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::transpose().

◆ find_first_nz()

template<typename VT , typename SZ >
bool bm::find_first_nz ( const VT *  arr,
SZ  arr_size,
SZ *  found_idx 
)

Find max non-zero value in an array.

Definition at line 9511 of file bmfunc.h.

Referenced by bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::build_octet_remap().

◆ find_max_nz()

template<typename VT , typename SZ >
bool bm::find_max_nz ( const VT *  arr,
SZ  arr_size,
SZ *  found_idx 
)

Find max non-zero value in an array.

Definition at line 9490 of file bmfunc.h.

Referenced by bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::build_octet_remap().

◆ find_not_null_ptr()

template<typename N >
bool bm::find_not_null_ptr ( bm::word_t ***  arr,
start,
size,
N *  pos 
)

Fini not NULL position

Returns
index of not NULL pointer

Definition at line 1304 of file bmfunc.h.

References avx2_test_all_zero_wave(), and BM_ASSERT.

Referenced by bm::bvector<>::calc_stat(), bm::bvector<>::count(), and bm::bvector<>::erase().

◆ for_each_bit_block_range()

template<typename T , typename N , typename F >
void bm::for_each_bit_block_range ( T ***  root,
top_size,
nb_from,
nb_to,
F &  f 
)

For each non-zero block in [from, to] executes supplied functor

Definition at line 1749 of file bmalgo_impl.h.

References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, for_each_bit_blk(), for_each_gap_blk(), FULL_BLOCK_FAKE_ADDR, gap_max_bits, set_array_mask, set_array_shift, set_sub_array_size, and set_sub_total_bits.

Referenced by for_each_bit_range_no_check().

◆ for_each_bit_range_no_check()

template<class BV , class Func >
void bm::for_each_bit_range_no_check ( const BV &  bv,
typename BV::size_type  left,
typename BV::size_type  right,
Func &  bit_functor 
)

◆ for_each_block()

template<class T , class F , typename BLOCK_IDX >
void bm::for_each_block ( T ***  root,
unsigned  size1,
F &  f,
BLOCK_IDX  start 
)

For each block executes supplied function.

Definition at line 2028 of file bmfunc.h.

References FULL_BLOCK_FAKE_ADDR, and set_sub_array_size.

Referenced by count_intervals().

◆ for_each_dgap()

template<class T , class Func >
void bm::for_each_dgap ( const T *  gap_buf,
Func &  func 
)

D-GAP block for_each algorithm

D-Gap Functor is called for each element but last one.

Parameters
gap_buf- GAP buffer
func- functor object

Definition at line 2560 of file bmfunc.h.

Referenced by bm::serializer< bvector_type >::gamma_gap_block().

◆ for_each_nzblock()

template<class T , class F >
void bm::for_each_nzblock ( T ***  root,
unsigned  size1,
F &  f 
)

For each non-zero block executes supplied function.

Definition at line 1763 of file bmfunc.h.

References avx2_test_all_zero_wave(), FULL_BLOCK_FAKE_ADDR, set_sub_array_size, and sse42_test_all_zero_wave().

Referenced by bm::bvector<>::count_blocks(), and bm::bvector<>::set_gap_levels().

◆ for_each_nzblock2()

template<class T , class F >
void bm::for_each_nzblock2 ( T ***  root,
unsigned  size1,
F &  f 
)

For each non-zero block executes supplied function.

Definition at line 1872 of file bmfunc.h.

References FULL_BLOCK_FAKE_ADDR, and set_sub_array_size.

◆ for_each_nzblock_if()

template<typename T , typename BI , typename F >
bool bm::for_each_nzblock_if ( T ***  root,
BI  size1,
F &  f 
)

For each non-zero block executes supplied function-predicate. Function returns if function-predicate returns true

Definition at line 1994 of file bmfunc.h.

References FULL_BLOCK_FAKE_ADDR, and set_sub_array_size.

Referenced by bm::bvector<>::any().

◆ for_each_nzblock_range()

template<typename T , typename N , typename F >
void bm::for_each_nzblock_range ( T ***  root,
top_size,
nb_from,
nb_to,
F &  f 
)

For each non-zero block in [from, to] executes supplied functor

Definition at line 1706 of file bmfunc.h.

References BM_ASSERT, FULL_BLOCK_FAKE_ADDR, gap_max_bits, set_array_mask, set_array_shift, set_sub_array_size, and set_sub_total_bits.

Referenced by bm::bvector<>::count_range().

◆ gap_2_bitblock()

template<typename GT , typename BT >
void bm::gap_2_bitblock ( const GT *BMRESTRICT  gap_buf,
BT *BMRESTRICT  block,
unsigned  block_size 
)

◆ gap_2_dgap()

template<typename T >
T* bm::gap_2_dgap ( const T *BMRESTRICT  gap_buf,
T *BMRESTRICT  dgap_buf,
bool  copy_head = true 
)

Convert GAP buffer into D-GAP buffer.

Delta GAP representation is DGAP[N] = GAP[N] - GAP[N-1]

Parameters
gap_buf- GAP buffer
dgap_buf- Delta-GAP buffer
copy_head- flag to copy GAP header

Definition at line 2601 of file bmfunc.h.

References bm::d_copy_func< T >::dgap_buf_.

◆ gap_bfind()

template<typename T >
unsigned bm::gap_bfind ( const T *BMRESTRICT  buf,
unsigned  pos,
unsigned *BMRESTRICT  is_set 
)

◆ gap_buff_op()

template<typename T , class F >
void bm::gap_buff_op ( T *BMRESTRICT  dest,
const T *BMRESTRICT  vect1,
unsigned  vect1_mask,
const T *BMRESTRICT  vect2,
unsigned  vect2_mask,
unsigned &  dlen 
)

Abstract operation for GAP buffers. Receives functor F as a template argument.

Parameters
dest- destination memory buffer.
vect1- operand 1 GAP encoded buffer.
vect1_mask- XOR mask for starting bitflag for vector1 can be 0 or 1 (1 inverts the vector)
vect2- operand 2 GAP encoded buffer.
vect2_mask- same as vect1_mask
dlen- destination length after the operation
Note
Internal function.

Definition at line 2765 of file bmfunc.h.

References gap_max_bits.

◆ gap_convert_to_bitset()

template<typename T >
void bm::gap_convert_to_bitset ( unsigned *  dest,
const T *  buf,
unsigned  dest_len 
)

GAP block to bitblock conversion.

Parameters
dest- bitblock buffer pointer.
buf- GAP buffer pointer.
dest_len- length/size of the destination buffer.

Definition at line 47 of file bmvmin.h.

References gap_add_to_bitset().

◆ get_block_coord()

template<typename BI_TYPE >
BMFORCEINLINE void bm::get_block_coord ( BI_TYPE  nb,
unsigned &  i,
unsigned &  j 
)

◆ get_block_start()

template<typename RTYPE >
BMFORCEINLINE RTYPE bm::get_block_start ( unsigned  i,
unsigned  j 
)

Compute bit address of the first bit in a block.

Definition at line 169 of file bmfunc.h.

References BMFORCEINLINE, and gap_max_bits.

◆ get_super_block_start()

template<typename RTYPE >
BMFORCEINLINE RTYPE bm::get_super_block_start ( unsigned  i)

Compute bit address of the first bit in a superblock.

Definition at line 159 of file bmfunc.h.

References set_sub_total_bits.

◆ idx_arr_block_lookup_u32()

unsigned bm::idx_arr_block_lookup_u32 ( const unsigned *  idx,
unsigned  size,
unsigned  nb,
unsigned  start 
)
inline

block boundaries look ahead U32

Parameters
idx- array to look into
size- array size
nb- block number to look ahead
start- start offset in idx
Returns
block boundary offset end (no more match at the returned offset)

Definition at line 9174 of file bmfunc.h.

References BM_ASSERT, set_block_shift, and VECT_ARR_BLOCK_LOOKUP.

Referenced by bm::sparse_vector< unsigned short, bvector_type >::gather(), and bm::bvector<>::import().

◆ idx_arr_block_lookup_u64()

bm::id64_t bm::idx_arr_block_lookup_u64 ( const bm::id64_t idx,
bm::id64_t  size,
bm::id64_t  nb,
bm::id64_t  start 
)
inline

block boundaries look ahead U32

Parameters
idx- array to look into
size- array size
nb- block number to look ahead
start- start offset in idx
Returns
block boundary offset end (no more match at the returned offset)

Definition at line 9148 of file bmfunc.h.

References BM_ASSERT, and set_block_shift.

Referenced by bm::sparse_vector< unsigned short, bvector_type >::gather(), and bm::bvector<>::import().

◆ ilog2() [1/2]

template<typename T >
BMFORCEINLINE T bm::ilog2 ( x)

Fast loop-less function to find LOG2.

Definition at line 124 of file bmutil.h.

References BMFORCEINLINE.

◆ ilog2() [2/2]

template<>
BMFORCEINLINE bm::gap_word_t bm::ilog2 ( gap_word_t  x)

Definition at line 138 of file bmutil.h.

◆ ilog2_LUT()

template<typename T >
BMFORCEINLINE T bm::ilog2_LUT ( x)

Lookup table based integer LOG2.

Definition at line 197 of file bmutil.h.

◆ ilog2_LUT< bm::gap_word_t >()

Lookup table based short integer LOG2.

Definition at line 216 of file bmutil.h.

References BMFORCEINLINE, and BMNOEXCEPT.

◆ is_const_set_operation()

bool bm::is_const_set_operation ( set_operation  op)
inline

Returns true if set operation is constant (bitcount)

Definition at line 1198 of file bmfunc.h.

References set_COUNT.

Referenced by bm::iterator_deserializer< BV, bm::serial_stream_iterator >::deserialize(), and operation2metric().

◆ lower_bound_linear_u32()

unsigned bm::lower_bound_linear_u32 ( const unsigned *  arr,
unsigned  target,
unsigned  from,
unsigned  to 
)
inline

Linear lower bound search in unsigned array.

Definition at line 9299 of file bmfunc.h.

References BM_ASSERT, and VECT_LOWER_BOUND_SCAN_U32.

Referenced by lower_bound_u32().

◆ lower_bound_linear_u64()

unsigned bm::lower_bound_linear_u64 ( const unsigned long long *  arr,
unsigned long long  target,
unsigned  from,
unsigned  to 
)
inline

Linear lower bound search in unsigned LONG array.

Definition at line 9322 of file bmfunc.h.

References BM_ASSERT.

Referenced by lower_bound_u64().

◆ lower_bound_u32()

unsigned bm::lower_bound_u32 ( const unsigned *  arr,
unsigned  target,
unsigned  from,
unsigned  to 
)
inline

Hybrid, binary-linear lower bound search in unsigned array.

Definition at line 9347 of file bmfunc.h.

References BM_ASSERT, and lower_bound_linear_u32().

◆ lower_bound_u64()

unsigned bm::lower_bound_u64 ( const unsigned long long *  arr,
unsigned long long  target,
unsigned  from,
unsigned  to 
)
inline

Hybrid, binary-linear lower bound search in unsigned LONG array.

Definition at line 9382 of file bmfunc.h.

References block_to_global_index(), BM_ASSERT, gap_max_bits, lower_bound_linear_u64(), and set_sub_array_size.

◆ mask_l_u32()

BMFORCEINLINE unsigned bm::mask_l_u32 ( unsigned  nbit)

◆ mask_r_u32()

BMFORCEINLINE unsigned bm::mask_r_u32 ( unsigned  nbit)

◆ min_delta_apply()

void bm::min_delta_apply ( unsigned *  arr,
size_t  arr_size,
unsigned  delta 
)
inline

Recalculate the array to decrement delta as arr[i] = arr[i] - delta + 1 so that array remains monotonically growing (fit for interpolative compression)

Definition at line 9473 of file bmfunc.h.

References BM_ASSERT.

◆ min_delta_u32()

unsigned bm::min_delta_u32 ( const unsigned *  arr,
size_t  arr_size 
)
inline

Calculate minimal delta between elements of sorted array.

Definition at line 9444 of file bmfunc.h.

References BM_ASSERT.

◆ min_value()

template<typename T >
BMFORCEINLINE T bm::min_value ( v1,
v2 
)

Get minimum of 2 values.

Definition at line 101 of file bmutil.h.

Referenced by distance_and_operation().

◆ op_and()

BMFORCEINLINE unsigned bm::op_and ( unsigned  a,
unsigned  b 
)

Definition at line 126 of file bmsse4.h.

◆ op_or()

BMFORCEINLINE unsigned bm::op_or ( unsigned  a,
unsigned  b 
)

Definition at line 117 of file bmsse4.h.

References BMFORCEINLINE.

◆ op_xor()

BMFORCEINLINE unsigned bm::op_xor ( unsigned  a,
unsigned  b 
)

Definition at line 107 of file bmsse4.h.

References BMFORCEINLINE.

◆ operator &()

template<class Alloc >
bvector<Alloc> bm::operator& ( const bvector< Alloc > &  bv1,
const bvector< Alloc > &  bv2 
)
inline

Definition at line 2104 of file bm.h.

References bm::bvector< Alloc >::bit_and().

◆ operator-()

template<class Alloc >
bvector<Alloc> bm::operator- ( const bvector< Alloc > &  bv1,
const bvector< Alloc > &  bv2 
)
inline

Definition at line 2137 of file bm.h.

References bm::bvector< Alloc >::bit_sub().

◆ operator^()

template<class Alloc >
bvector<Alloc> bm::operator^ ( const bvector< Alloc > &  bv1,
const bvector< Alloc > &  bv2 
)
inline

Definition at line 2126 of file bm.h.

References bm::bvector< Alloc >::bit_xor().

◆ operator|()

template<class Alloc >
bvector<Alloc> bm::operator| ( const bvector< Alloc > &  bv1,
const bvector< Alloc > &  bv2 
)
inline

Definition at line 2115 of file bm.h.

References bm::bvector< Alloc >::bit_or().

◆ parallel_popcnt_32()

int bm::parallel_popcnt_32 ( unsigned int  n)
inline

Definition at line 217 of file bmfunc.h.

References BMFORCEINLINE.

◆ process_operation()

template<class BV >
BV::size_type bm::process_operation ( BV &  bv,
BV &  bv_tmp,
bm::set_operation  op 
)

◆ ptrp_test()

bm::id64_t bm::ptrp_test ( ptr_payload_t  ptr,
bm::gap_word_t  v 
)
inline

Test presense of value in payload pointer

Definition at line 9558 of file bmfunc.h.

◆ set_block_bits_u32()

void bm::set_block_bits_u32 ( bm::word_t *BMRESTRICT  block,
const unsigned *BMRESTRICT  idx,
unsigned  start,
unsigned  stop 
)
inline

set bits in a bit-block using global index

Parameters
idx- array to look into
block- block pointer to set bits
start- index array start
stop- index array stop in a range [start..stop)
Returns
block boundary offset end (no more match at the returned offset)

Definition at line 9237 of file bmfunc.h.

References set_block_mask, set_word_mask, set_word_shift, and VECT_SET_BLOCK_BITS.

Referenced by bm::bvector<>::import_block().

◆ set_block_bits_u64()

void bm::set_block_bits_u64 ( bm::word_t *BMRESTRICT  block,
const bm::id64_t *BMRESTRICT  idx,
bm::id64_t  start,
bm::id64_t  stop 
)
inline

set bits in a bit-block using global index

Parameters
idx- array to look into
block- block pointer to set bits
start- index array start
stop- index array stop in a range [start..stop)
Returns
block boundary offset end (no more match at the returned offset)

Definition at line 9207 of file bmfunc.h.

References set_block_mask, set_word_mask, and set_word_shift.

Referenced by bm::bvector<>::import_block().

◆ setop2op()

bm::operation bm::setop2op ( bm::set_operation  op)
inline

Convert set operation to operation.

Definition at line 1207 of file bmfunc.h.

References BM_ASSERT, set_AND, set_OR, set_SUB, and set_XOR.

Referenced by bm::iterator_deserializer< BV, bm::serial_stream_iterator >::deserialize().

◆ sse2_and()

BMFORCEINLINE __m128i bm::sse2_and ( __m128i  a,
__m128i  b 
)

Definition at line 855 of file bmsse_util.h.

References BMFORCEINLINE.

◆ sse2_and_block()

unsigned bm::sse2_and_block ( __m128i *BMRESTRICT  dst,
const __m128i *BMRESTRICT  src,
const __m128i *BMRESTRICT  src_end 
)
inline

Definition at line 228 of file bmsse_util.h.

References BM_ALIGN16, and BM_ALIGN16ATTR.

◆ sse2_bit_block_calc_count_change()

bm::id_t bm::sse2_bit_block_calc_count_change ( const __m128i *BMRESTRICT  block,
const __m128i *BMRESTRICT  block_end,
unsigned *BMRESTRICT  bit_count 
)
inline

Definition at line 187 of file bmsse2.h.

References BM_ALIGN16, BM_ALIGN16ATTR, BM_INCWORD_BITCOUNT, and BMRESTRICT.

◆ sse2_bit_count_op()

template<class Func >
bm::id_t bm::sse2_bit_count_op ( const __m128i *BMRESTRICT  block,
const __m128i *BMRESTRICT  block_end,
const __m128i *BMRESTRICT  mask_block,
Func  sse2_func 
)

Definition at line 123 of file bmsse2.h.

References BM_ALIGN16, and BM_ALIGN16ATTR.

◆ sse2_gap_find()

unsigned bm::sse2_gap_find ( const bm::gap_word_t *BMRESTRICT  pbuf,
const bm::gap_word_t  pos,
const unsigned  size 
)
inline

SSE4.2 check for one to two (variable len) 128 bit SSE lines for gap search results (8 elements)

Definition at line 345 of file bmsse2.h.

References bit_scan_fwd(), BM_ASSERT, and BMRESTRICT.

Referenced by sse2_gap_bfind().

◆ sse2_gap_sum_arr()

const bm::gap_word_t* bm::sse2_gap_sum_arr ( const bm::gap_word_t *BMRESTRICT  pbuf,
unsigned  sse_vect_waves,
unsigned *  sum 
)
inline

Gap block population count (array sum) utility.

Parameters
pbuf- unrolled, aligned to 1-start GAP buffer
sse_vect_waves- number of SSE vector lines to process
sum- result acumulator
Returns
tail pointer

Definition at line 891 of file bmsse_util.h.

Referenced by gap_bit_count_unr().

◆ sse2_or()

BMFORCEINLINE __m128i bm::sse2_or ( __m128i  a,
__m128i  b 
)

Definition at line 861 of file bmsse_util.h.

References BMFORCEINLINE.

◆ sse2_sub()

BMFORCEINLINE __m128i bm::sse2_sub ( __m128i  a,
__m128i  b 
)

Definition at line 874 of file bmsse_util.h.

◆ sse2_xor()

BMFORCEINLINE __m128i bm::sse2_xor ( __m128i  a,
__m128i  b 
)

Definition at line 868 of file bmsse_util.h.

References BMFORCEINLINE.

◆ sse42_idx_arr_block_lookup()

unsigned bm::sse42_idx_arr_block_lookup ( const unsigned *  idx,
unsigned  size,
unsigned  nb,
unsigned  start 
)
inline

SSE4.2 index lookup to check what belongs to the same block (8 elements)

Definition at line 1254 of file bmsse4.h.

References set_block_shift.

◆ sse42_set_block_bits()

void bm::sse42_set_block_bits ( bm::word_t *BMRESTRICT  block,
const unsigned *BMRESTRICT  idx,
unsigned  start,
unsigned  stop 
)
inline

SSE4.2 bulk bit set

Definition at line 1291 of file bmsse4.h.

References BM_ALIGN16, BM_ALIGN16ATTR, set_block_mask, set_word_mask, and set_word_shift.

◆ sse4_bit_block_gather_scatter()

void bm::sse4_bit_block_gather_scatter ( unsigned *BMRESTRICT  arr,
const unsigned *BMRESTRICT  blk,
const unsigned *BMRESTRICT  idx,
unsigned  size,
unsigned  start,
unsigned  bit_idx 
)
inline

SSE4.2 bit block gather-scatter

Parameters
arr- destination array to set bits
blk- source bit-block
idx- gather index array
size- gather array size
start- gaher start index
bit_idx- bit to set in the target array

Definition at line 1375 of file bmsse4.h.

References BM_ALIGN16, BM_ALIGN16ATTR, set_block_mask, set_word_mask, and set_word_shift.

Referenced by bit_block_gather_scatter().

◆ sse4_bit_count_op()

template<class Func >
bm::id_t bm::sse4_bit_count_op ( const __m128i *BMRESTRICT  block,
const __m128i *BMRESTRICT  block_end,
const __m128i *BMRESTRICT  mask_block,
Func  sse2_func 
)

Definition at line 133 of file bmsse4.h.

◆ sum_arr()

template<typename T >
bm::id64_t bm::sum_arr ( const T *  first,
const T *  last 
)

Computes SUM of all elements of the sequence

Definition at line 2076 of file bmfunc.h.

◆ tmatrix_reduce()

template<class TMatrix >
void bm::tmatrix_reduce ( TMatrix &  tmatrix,
const unsigned char *  pc_vector,
const unsigned  effective_cols 
)

Transposed Matrix reduction based on transformation pc vector.

Definition at line 518 of file bmtrans.h.

References BM_ASSERT, bm::tmatrix< T, ROWS, COLS >::cols(), ibpc_all_one, ibpc_all_zero, ibpc_close, ibpc_equiv, ibpc_uncompr, and bm::tmatrix< T, ROWS, COLS >::row().

Referenced by bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::reduce().

◆ tmatrix_restore()

template<class TMatrix >
void bm::tmatrix_restore ( TMatrix &  tmatrix,
const unsigned char *  pc_vector,
const unsigned  effective_cols 
)

Transposed Matrix restore based on transformation pc vector.

Definition at line 565 of file bmtrans.h.

References BM_ASSERT, bm::tmatrix< T, ROWS, COLS >::cols(), ibpc_all_one, ibpc_all_zero, ibpc_close, ibpc_equiv, ibpc_uncompr, and bm::tmatrix< T, ROWS, COLS >::row().

Referenced by bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::restore().

◆ vect_bit_transpose()

template<typename T , unsigned BPC, unsigned BPS>
void bm::vect_bit_transpose ( const T *  arr,
unsigned  arr_size,
tmatrix[BPC][BPS] 
)

Generic bit-array transposition function T - array type (any int) BPC - bit plain count BPS - bit plain size.

Parameters
arr- source array start
arr_size- source array size
tmatrix- destination bit matrix

Definition at line 257 of file bmtrans.h.

References BM_ASSERT, bm::bit_grabber< T, BPC >::get(), and bm::tmatrix< T, ROWS, COLS >::row().

◆ vect_bit_trestore()

template<typename T , unsigned BPC, unsigned BPS>
void bm::vect_bit_trestore ( const T  tmatrix[BPC][BPS],
T *  arr 
)

Restore bit array from the transposition matrix T - array type (any int) BPC - bit plain count BPS - bit plain size.

Parameters
arr- dest array
tmatrix- source bit-slice matrix

Definition at line 290 of file bmtrans.h.

References bm::bit_trans_grabber< T, BPC, BPS >::get().

◆ xor_swap()

template<typename W >
void bm::xor_swap ( W &  x,
W &  y 
)

Variable Documentation

◆ all_bits_mask

const id64_t bm::all_bits_mask = 0xffffffffffffffffULL

Definition at line 128 of file bmconst.h.

Referenced by bit_andnot_arr_ffmask(), bm::bvector<>::combine_operation(), and is_bits_one().

◆ bie_cut_off

const unsigned bm::bie_cut_off = 16384

Definition at line 87 of file bmconst.h.

◆ bits_in_array

const unsigned bm::bits_in_array = bm::bits_in_block * bm::set_array_size32

◆ bits_in_block

const unsigned bm::bits_in_block = bm::set_block_size * unsigned((sizeof(bm::word_t) * 8))

◆ block_waves

const unsigned bm::block_waves = 64

◆ gap_equiv_len

const unsigned bm::gap_equiv_len

◆ gap_levels

const unsigned bm::gap_levels = 4

◆ gap_max_bits

const unsigned bm::gap_max_bits = 65536

Definition at line 80 of file bmconst.h.

Referenced by bm::interval_enumerator< BV >::advance(), bm::bvector<>::any_range(), avx2_gap_bfind(), bm::sparse_vector_scanner< SV >::bfind_eq_str(), bm::serializer< bvector_type >::bienc_gap_bit_block(), bm::sparse_vector_scanner< SV >::bind(), bit_block_calc_count_range(), bit_block_convert_to_arr(), bit_block_find_interval_end(), bit_block_is_all_one_range(), bit_operation_or_count(), bit_operation_sub_count(), bit_operation_xor_count(), block_any_range(), block_find_interval_end(), block_find_interval_start(), block_find_reverse(), block_is_all_one_range(), block_is_interval(), block_to_global_index(), bm::bvector<>::combine_operation(), convert_sub_to_arr(), bm::bvector<>::copy_range(), bm::bvector<>::count(), bm::bvector<>::count_blocks(), bm::deserializer< BV, bm::decoder >::decode_arr_sblock(), bm::deserializer< BV, bm::decoder >::deserialize(), bm::deserializer< BV, bm::decoder >::deserialize_gap(), bm::deserializer< BV, bm::decoder >::deserializer(), digest_mask(), bm::bvector<>::erase(), bm::bvector<>::find(), bm::serializer< bvector_type >::find_bit_best_encoding(), bm::serializer< bvector_type >::find_bit_best_encoding_l5(), bm::bvector<>::find_first_mismatch(), bm::serializer< bvector_type >::find_gap_best_encoding(), find_interval_end(), find_interval_start(), bm::bvector<>::find_rank(), bm::bvector<>::find_reverse(), for_each_bit_blk(), for_each_bit_block_range(), for_each_nzblock_range(), gap_add_value(), gap_any_range(), gap_bfind(), gap_bit_count_range(), gap_block_find(), gap_buff_any_op(), gap_buff_count_op(), gap_buff_op(), gap_find_first(), gap_find_interval_end(), gap_find_interval_start(), gap_find_last(), gap_find_prev(), gap_is_all_one(), gap_is_all_one_range(), gap_is_all_zero(), gap_is_interval(), gap_set_array(), gap_set_value(), gap_shift_l1(), gap_shift_r1(), gap_test(), gap_test_unr(), get_block_start(), bm::bvector< Alloc >::enumerator::go_first(), bm::interval_enumerator< BV >::go_to_impl(), bm::bvector< Alloc >::enumerator::go_up(), bm::bvector<>::insert(), bm::serializer< bvector_type >::interpolated_gap_bit_block(), bm::bvector<>::is_all_one_range(), is_interval(), lower_bound_u64(), bm::deseriaizer_base< bm::decoder, BV::block_idx_type >::read_gap_block(), bm::random_subset< BV >::sample(), bm::xor_scanner< bvector_type >::search_best_xor_mask(), bm::bvector<>::select(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::serial_stream_iterator(), bm::serializer< bvector_type >::serializer(), bm::bvector< Alloc >::enumerator::skip(), and bm::miniset< A, N >::swap().

◆ gap_max_bits_cmrz

const unsigned bm::gap_max_bits_cmrz = bm::gap_max_bits / 2

Definition at line 83 of file bmconst.h.

◆ gap_max_buff_len

const unsigned bm::gap_max_buff_len = 1280

◆ gap_max_level

const unsigned bm::gap_max_level = bm::gap_levels - 1

Definition at line 85 of file bmconst.h.

◆ ibpc_all_one

const unsigned char bm::ibpc_all_one = 2

!< plain ALL ZERO

Definition at line 353 of file bmtrans.h.

Referenced by bit_iblock_make_pcv(), bit_iblock_reduce(), gap_2_bitblock(), tmatrix_reduce(), and tmatrix_restore().

◆ ibpc_all_zero

const unsigned char bm::ibpc_all_zero = 1

!< plain uncompressed

Definition at line 352 of file bmtrans.h.

Referenced by bit_iblock_make_pcv(), bit_iblock_reduce(), gap_2_bitblock(), tmatrix_reduce(), and tmatrix_restore().

◆ ibpc_close

const unsigned char bm::ibpc_close = 4

!< plain is equal to plain M

Definition at line 355 of file bmtrans.h.

Referenced by bit_iblock_reduce(), gap_2_bitblock(), tmatrix_reduce(), and tmatrix_restore().

◆ ibpc_end

const unsigned char bm::ibpc_end = 8

!< plain is close to plain M

Definition at line 357 of file bmtrans.h.

◆ ibpc_equiv

const unsigned char bm::ibpc_equiv = 3

!< plain ALL ONE

Definition at line 354 of file bmtrans.h.

Referenced by bit_iblock_reduce(), gap_2_bitblock(), tmatrix_reduce(), and tmatrix_restore().

◆ ibpc_uncompr

const unsigned char bm::ibpc_uncompr = 0

◆ id_max

const unsigned bm::id_max = bm::id_max32
Examples:
bvsample01_64.cpp, and sample24.cpp.

Definition at line 108 of file bmconst.h.

Referenced by bm::interval_enumerator< BV >::advance(), bm::rsc_sparse_vector< Val, SV >::const_iterator::advance(), bm::sparse_vector< Val, BV >::const_iterator::advance(), bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::const_iterator::advance(), bm::bvector<>::any_range(), block_range_scan(), combine_or(), combine_sub(), combine_xor(), bm::rsc_sparse_vector< Val, SV >::const_iterator::const_iterator(), bm::sparse_vector< Val, BV >::const_iterator::const_iterator(), bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::const_iterator::const_iterator(), convert_sub_to_arr(), bm::bvector<>::copy_range(), count_intervals(), bm::bvector<>::count_range(), bm::bvector<>::count_to(), bm::bvector<>::count_to_test(), bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::decode(), bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::decode_buf(), bm::serializer< bvector_type >::encode_header(), bm::sparse_vector< unsigned short, bvector_type >::end(), bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::end(), bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::end(), bm::bvector<>::equal(), bm::bvector<>::erase(), bm::bvector<>::extract_next(), bm::bvector<>::find(), find_interval_end(), bm::bvector<>::find_rank(), bm::sparse_vector_scanner< SV >::find_zero(), for_each_bit_range(), bm::sparse_vector< unsigned short, bvector_type >::get(), bm::bvector<>::get_next(), bm::rsc_sparse_vector< Val, SV >::const_iterator::go_to(), bm::sparse_vector< Val, BV >::const_iterator::go_to(), bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::const_iterator::go_to(), bm::interval_enumerator< BV >::go_to_impl(), bm::bvector<>::import(), bm::bvector<>::insert(), bm::rsc_sparse_vector< Val, SV >::const_iterator::invalidate(), bm::sparse_vector< Val, BV >::const_iterator::invalidate(), bm::interval_enumerator< BV >::invalidate(), bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::const_iterator::invalidate(), bm::bvector< Alloc >::iterator_base::invalidate(), bm::sparse_vector_scanner< SV >::invert(), bm::bvector<>::invert(), bm::bvector<>::is_all_one_range(), is_interval(), main(), bm::bvector< Alloc >::insert_iterator::operator=(), bm::bvector< Alloc >::bulk_insert_iterator::operator=(), bm::bvector<>::operator[](), bm::sparse_vector< unsigned short, bvector_type >::push_back_null(), bm::bvector<>::rank_corrected(), bm::aggregator< bvector_type >::reset(), bm::sparse_vector_scanner< SV >::reset_search_range(), bm::bvector<>::set_bit(), bm::bvector<>::set_bit_conditional(), bm::bvector<>::set_bit_no_check(), bm::iterator_deserializer< BV, bm::serial_stream_iterator >::set_range(), bm::bvector<>::set_range(), bm::rsc_sparse_vector< Val, SV >::const_iterator::skip_zero_values(), bm::sparse_vector< Val, BV >::const_iterator::skip_zero_values(), sparse_vector_find_first_mismatch(), bm::sparse_vector_scanner< SV >::sparse_vector_scanner(), sse42_shift_r1_and(), bm::bvector<>::sync_size(), bm::interval_enumerator< BV >::valid(), bm::rsc_sparse_vector< Val, SV >::const_iterator::valid(), bm::sparse_vector< Val, BV >::const_iterator::valid(), bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::const_iterator::valid(), bm::bvector< Alloc >::iterator_base::valid(), and bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::const_iterator::value().

◆ id_max32

const unsigned bm::id_max32 = 0xFFFFFFFFu

Definition at line 49 of file bmconst.h.

Referenced by bm::sparse_vector_serializer< SV >::serialize().

◆ rs3_border0

const unsigned bm::rs3_border0 = 21824

Definition at line 118 of file bmconst.h.

Referenced by bm::bvector<>::build_rs_index(), and bm::bvector<>::count_blocks().

◆ rs3_border1

const unsigned bm::rs3_border1 = (rs3_border0 * 2)

Definition at line 119 of file bmconst.h.

Referenced by bm::bvector<>::build_rs_index(), and bm::bvector<>::count_blocks().

◆ rs3_half_span

const unsigned bm::rs3_half_span = rs3_border0 / 2

Definition at line 120 of file bmconst.h.

Referenced by bm::bvector<>::count_blocks().

◆ sblock_flag_len16

const unsigned bm::sblock_flag_len16 = (1u << 4)

◆ sblock_flag_max16

const unsigned bm::sblock_flag_max16 = (1u << 5)

◆ sblock_flag_max24

const unsigned bm::sblock_flag_max24 = (1u << 6)

◆ sblock_flag_max32

const unsigned bm::sblock_flag_max32 = bm::sblock_flag_max16 | bm::sblock_flag_max24

Definition at line 2189 of file bmserial.h.

Referenced by bm::serializer< bvector_type >::bienc_arr_sblock().

◆ sblock_flag_min16

const unsigned bm::sblock_flag_min16 = (1u << 2)

◆ sblock_flag_min24

const unsigned bm::sblock_flag_min24 = (1u << 3)

◆ sblock_flag_min32

const unsigned bm::sblock_flag_min32 = bm::sblock_flag_min16 | bm::sblock_flag_min24

Definition at line 2184 of file bmserial.h.

Referenced by bm::serializer< bvector_type >::bienc_arr_sblock().

◆ sblock_flag_sb16

const unsigned bm::sblock_flag_sb16 = (1u << 0)

◆ sblock_flag_sb32

const unsigned bm::sblock_flag_sb32 = (1u << 1)

◆ set_array_mask

const unsigned bm::set_array_mask = 0xFFu

◆ set_array_shift

const unsigned bm::set_array_shift = 8u

◆ set_array_size32

const unsigned bm::set_array_size32 = 256u

Definition at line 93 of file bmconst.h.

◆ set_bitscan_wave_size

const unsigned short bm::set_bitscan_wave_size = 4

◆ set_blkblk_mask

const unsigned bm::set_blkblk_mask = 0xFFFFFFu

Definition at line 57 of file bmconst.h.

◆ set_block_16one

const unsigned char bm::set_block_16one = 6

UP to 65536 all-set blocks.

Definition at line 1048 of file bmserial.h.

Referenced by bm::deserializer< BV, bm::decoder >::deserialize(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::next().

◆ set_block_16zero

const unsigned char bm::set_block_16zero = 5

Up to 65536 zero blocks.

Definition at line 1047 of file bmserial.h.

Referenced by bm::deserializer< BV, bm::decoder >::deserialize(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::next().

◆ set_block_1one

const unsigned char bm::set_block_1one = 2

One block all-set (1111...)

Definition at line 1044 of file bmserial.h.

Referenced by bm::deserializer< BV, bm::decoder >::deserialize(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::next().

◆ set_block_1zero

const unsigned char bm::set_block_1zero = 1

◆ set_block_32one

const unsigned char bm::set_block_32one = 8

UP to 4G all-set blocks.

Definition at line 1050 of file bmserial.h.

Referenced by bm::deserializer< BV, bm::decoder >::deserialize(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::next().

◆ set_block_32zero

const unsigned char bm::set_block_32zero = 7

◆ set_block_64one

const unsigned char bm::set_block_64one = 26

◆ set_block_64zero

const unsigned char bm::set_block_64zero = 25

lots of zero blocks

Definition at line 1067 of file bmserial.h.

Referenced by bm::deserializer< BV, bm::decoder >::deserialize().

◆ set_block_8one

const unsigned char bm::set_block_8one = 4

Up to 256 all-set blocks.

Definition at line 1046 of file bmserial.h.

Referenced by bm::deserializer< BV, bm::decoder >::deserialize(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::next().

◆ set_block_8zero

const unsigned char bm::set_block_8zero = 3

◆ set_block_alloc_size

const unsigned bm::set_block_alloc_size = bm::set_block_size * unsigned(sizeof(bm::word_t))

Definition at line 60 of file bmconst.h.

◆ set_block_aone

const unsigned char bm::set_block_aone = 10

◆ set_block_arr_bienc

const unsigned char bm::set_block_arr_bienc = 31

◆ set_block_arr_bienc_8bh

const unsigned char bm::set_block_arr_bienc_8bh = 57

◆ set_block_arr_bienc_inv

const unsigned char bm::set_block_arr_bienc_inv = 32

◆ set_block_arrbit

const unsigned char bm::set_block_arrbit = 16

◆ set_block_arrbit_inv

const unsigned char bm::set_block_arrbit_inv = 30

◆ set_block_arrgap

const unsigned char bm::set_block_arrgap = 18

◆ set_block_arrgap_bienc

const unsigned char bm::set_block_arrgap_bienc = 28

◆ set_block_arrgap_bienc_inv

const unsigned char bm::set_block_arrgap_bienc_inv = 29

◆ set_block_arrgap_bienc_inv_v2

const unsigned char bm::set_block_arrgap_bienc_inv_v2 = 45

◆ set_block_arrgap_bienc_v2

const unsigned char bm::set_block_arrgap_bienc_v2 = 44

◆ set_block_arrgap_egamma

const unsigned char bm::set_block_arrgap_egamma = 21

◆ set_block_arrgap_egamma_inv

const unsigned char bm::set_block_arrgap_egamma_inv = 23

◆ set_block_arrgap_inv

const unsigned char bm::set_block_arrgap_inv = 24

◆ set_block_azero

const unsigned char bm::set_block_azero = 9

◆ set_block_bit

const unsigned char bm::set_block_bit = 11

◆ set_block_bit_0runs

const unsigned char bm::set_block_bit_0runs = 22

◆ set_block_bit_1bit

const unsigned char bm::set_block_bit_1bit = 19

◆ set_block_bit_digest0

const unsigned char bm::set_block_bit_digest0 = 34

◆ set_block_bit_interval

const unsigned char bm::set_block_bit_interval = 17

◆ set_block_bitgap_bienc

const unsigned char bm::set_block_bitgap_bienc = 33

◆ set_block_bitgap_bienc_v2

const unsigned char bm::set_block_bitgap_bienc_v2 = 46

Interpolated bit-block as GAPs (v2 - reseved)

Definition at line 1091 of file bmserial.h.

◆ set_block_digest_pos_shift

const unsigned bm::set_block_digest_pos_shift = 10

Definition at line 67 of file bmconst.h.

Referenced by digest_mask(), gap_and_to_bitset(), and gap_sub_to_bitset().

◆ set_block_digest_wave_size

const unsigned bm::set_block_digest_wave_size = bm::set_block_size / bm::block_waves

◆ set_block_end

const unsigned char bm::set_block_end = 0

◆ set_block_gap

const unsigned char bm::set_block_gap = 14

◆ set_block_gap_bienc

const unsigned char bm::set_block_gap_bienc = 27

◆ set_block_gap_bienc_v2

const unsigned char bm::set_block_gap_bienc_v2 = 43

◆ set_block_gap_egamma

const unsigned char bm::set_block_gap_egamma = 20

◆ set_block_gapbit

const unsigned char bm::set_block_gapbit = 15

◆ set_block_mask

const unsigned bm::set_block_mask = 0xFFFFu

◆ set_block_plain_cnt

const unsigned bm::set_block_plain_cnt = (unsigned)(sizeof(bm::word_t) * 8u)

Definition at line 63 of file bmconst.h.

Referenced by bit_iblock_reduce().

◆ set_block_plain_size

const unsigned bm::set_block_plain_size = bm::set_block_size / 32u

Definition at line 62 of file bmconst.h.

Referenced by bit_iblock_reduce().

◆ set_block_ref_eq

const unsigned char bm::set_block_ref_eq = 35

◆ set_block_sgapbit

const unsigned char bm::set_block_sgapbit = 12

SGAP compressed bitblock.

Definition at line 1054 of file bmserial.h.

◆ set_block_sgapgap

const unsigned char bm::set_block_sgapgap = 13

SGAP compressed GAP block.

Definition at line 1055 of file bmserial.h.

◆ set_block_shift

const unsigned bm::set_block_shift = 16u

Definition at line 55 of file bmconst.h.

Referenced by bm::interval_enumerator< BV >::advance(), bm::bvector<>::any_range(), avx2_idx_arr_block_lookup(), bm::sparse_vector< Val, BV >::back_insert_iterator::back_insert_iterator(), bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::back_insert_iterator::back_insert_iterator(), bm::sparse_vector_scanner< SV >::bfind_eq_str(), bm::sparse_vector_scanner< SV >::bind(), block_range_scan(), bm::bvector<>::build_rs_index(), bm::bvector<>::combine_operation(), combine_or(), combine_sub(), combine_xor(), bm::sparse_vector_scanner< SV >::compare_str(), bm::bvector<>::copy_range(), bm::bvector<>::count_range(), bm::bvector<>::count_to(), bm::bvector<>::count_to_test(), bm::deserializer< BV, bm::decoder >::deserialize(), bm::iterator_deserializer< BV, bm::serial_stream_iterator >::deserialize(), bm::bvector<>::erase(), bm::sparse_vector< unsigned short, bvector_type >::extract_range(), bm::aggregator< bvector_type >::find_first_and_sub(), bm::bvector<>::find_first_mismatch(), find_interval_end(), find_interval_start(), bm::bvector<>::find_rank(), bm::bvector<>::find_reverse(), bm::sparse_vector< Val, BV >::back_insert_iterator::flush(), bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::back_insert_iterator::flush(), for_each_bit_range_no_check(), bm::sparse_vector< unsigned short, bvector_type >::gather(), bm::bvector<>::get_bit(), bm::basic_bmatrix< bvector_type >::get_half_octet(), bm::basic_bmatrix< bvector_type >::get_octet(), bm::bvector< Alloc >::enumerator::go_to(), bm::interval_enumerator< BV >::go_to_impl(), idx_arr_block_lookup_u32(), idx_arr_block_lookup_u64(), bm::bvector<>::import(), bm::bvector<>::inc(), bm::bvector<>::insert(), bm::bvector<>::is_all_one_range(), is_interval(), bm::aggregator< bvector_type >::process_bit_blocks_and(), bm::bvector<>::rank_corrected(), bm::set2set_11_transform< SV >::remap(), bm::bvector<>::select(), bm::bvector<>::set_bit_no_check(), bm::iterator_deserializer< BV, bm::serial_stream_iterator >::set_range(), bm::sparse_vector< unsigned short, bvector_type >::set_value_no_null(), and sse42_idx_arr_block_lookup().

◆ set_block_size

const unsigned bm::set_block_size = 2048u

Definition at line 54 of file bmconst.h.

Referenced by bm::bv_statistics::add_bit_block(), bm::alloc_pool< BA, PA >::alloc_bit_block(), bm::mem_alloc< BA, PA, APool >::alloc_bit_block(), avx2_and_block(), avx2_bit_block_calc_change_bc(), avx2_bit_find_first(), avx2_bit_find_first_diff(), avx2_bit_to_gap(), avx2_copy_block(), avx2_invert_block(), avx2_is_all_one(), avx2_is_all_zero(), avx2_or_block(), avx2_or_block_2way(), avx2_or_block_3way(), avx2_or_block_5way(), avx2_set_block(), avx2_shift_l1(), avx2_shift_r1(), avx2_stream_block(), avx2_sub_block(), avx2_xor_block(), avx2_xor_block_2way(), bm::serializer< bvector_type >::bienc_gap_bit_block(), bit_andnot_arr_ffmask(), bit_block_and(), bit_block_and_any(), bit_block_and_count(), bit_block_calc_change(), bit_block_change_bc(), bit_block_copy(), bit_block_count(), bit_block_erase(), bit_block_find(), bit_block_find_interval_end(), bit_block_insert(), bit_block_or(), bit_block_or_2way(), bit_block_or_3way(), bit_block_or_5way(), bit_block_or_any(), bit_block_or_count(), bit_block_rotate_left_1(), bit_block_rotate_left_1_unr(), bit_block_set(), bit_block_shift_l1(), bit_block_shift_l1_unr_min(), bit_block_shift_r1(), bit_block_shift_r1_and(), bit_block_shift_r1_unr_min(), bit_block_stream(), bit_block_sub(), bit_block_sub_any(), bit_block_sub_count(), bit_block_to_gap(), bit_block_xor(), bit_block_xor_2way(), bit_block_xor_any(), bit_block_xor_count(), bit_find_first(), bit_find_first_diff(), bit_find_last(), bit_find_rank(), bit_invert(), bit_is_all_zero(), bit_operation_or(), bm::bvector< Alloc >::bulk_insert_iterator::buf_size_max(), bm::bvector<>::calc_stat(), combine_any_operation_with_block(), combine_count_operation_with_block(), bm::bvector<>::combine_operation(), bm::deserializer< BV, bm::decoder >::decode_block_bit(), bm::deserializer< BV, bm::decoder >::decode_block_bit_interval(), bm::serializer< bvector_type >::encode_bit_digest(), bm::serializer< bvector_type >::encode_bit_interval(), bm::bit_block_t::end(), bm::bvector<>::erase(), export_array(), bm::serializer< bvector_type >::find_bit_best_encoding(), bm::serializer< bvector_type >::find_bit_best_encoding_l5(), bm::bvector<>::find_rank(), for_each_bit_blk(), bm::alloc_pool< BA, PA >::free_bit_block(), bm::mem_alloc< BA, PA, APool >::free_bit_block(), bm::alloc_pool< BA, PA >::free_pools(), bm::serializer< bvector_type >::gamma_arr_bit_block(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_AND(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_ASSIGN(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_A(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_AND(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_OR(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_SUB_AB(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_SUB_BA(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_XOR(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_OR(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_SUB(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_XOR(), bm::bvector< Alloc >::enumerator::go_first(), bm::bvector< Alloc >::enumerator::go_to(), bm::bvector<>::import_block(), bm::bvector<>::insert(), bm::serializer< bvector_type >::interpolated_arr_bit_block(), is_bits_one(), bm::aggregator< bvector_type >::process_shift_right_and(), bm::random_subset< BV >::random_subset(), bm::deseriaizer_base< bm::decoder, BV::block_idx_type >::read_0runs_block(), bm::random_subset< BV >::sample(), bm::bvector<>::select(), bm::serializer< bvector_type >::serialize(), sse2_and_block(), sse2_copy_block(), sse2_invert_block(), sse2_or_block(), sse2_or_block_2way(), sse2_or_block_3way(), sse2_or_block_5way(), sse2_set_block(), sse2_stream_block(), sse2_sub_block(), sse2_xor_block(), sse2_xor_block_2way(), sse42_bit_block_calc_change_bc(), sse42_bit_find_first(), sse42_bit_find_first_diff(), sse42_shift_l1(), sse42_shift_r1(), sse4_and_block(), sse4_is_all_one(), and sse4_is_all_zero().

◆ set_block_size_op

const unsigned bm::set_block_size_op = bm::set_block_size / 2

Definition at line 129 of file bmconst.h.

Referenced by bm::bvector<>::compare().

◆ set_block_xor_chain

const unsigned char bm::set_block_xor_chain = 42

XOR chain (reserved)

Definition at line 1086 of file bmserial.h.

◆ set_block_xor_gap_ref16

const unsigned char bm::set_block_xor_gap_ref16 = 40

◆ set_block_xor_gap_ref32

const unsigned char bm::set_block_xor_gap_ref32 = 41

..... 32-bit (should never happen)

Definition at line 1085 of file bmserial.h.

Referenced by bm::deserializer< BV, bm::decoder >::deserialize(), and bm::serializer< bvector_type >::serialize().

◆ set_block_xor_gap_ref8

const unsigned char bm::set_block_xor_gap_ref8 = 39

◆ set_block_xor_ref16

const unsigned char bm::set_block_xor_ref16 = 37

◆ set_block_xor_ref32

const unsigned char bm::set_block_xor_ref32 = 38

◆ set_block_xor_ref8

const unsigned char bm::set_block_xor_ref8 = 36

◆ set_compression_default

const unsigned bm::set_compression_default = 6

Default compression level.

Examples:
inv_list.cpp.

Definition at line 60 of file bmserial.h.

◆ set_compression_max

const unsigned bm::set_compression_max = 6

Maximum supported compression level.

Definition at line 59 of file bmserial.h.

Referenced by bm::serializer< bvector_type >::set_compression_level().

◆ set_nb_bookmark16

const unsigned char bm::set_nb_bookmark16 = 47

◆ set_nb_bookmark24

const unsigned char bm::set_nb_bookmark24 = 48

◆ set_nb_bookmark32

const unsigned char bm::set_nb_bookmark32 = 49

◆ set_nb_sync_mark16

const unsigned char bm::set_nb_sync_mark16 = 51

◆ set_nb_sync_mark24

const unsigned char bm::set_nb_sync_mark24 = 52

◆ set_nb_sync_mark32

const unsigned char bm::set_nb_sync_mark32 = 53

◆ set_nb_sync_mark48

const unsigned char bm::set_nb_sync_mark48 = 54

◆ set_nb_sync_mark64

const unsigned char bm::set_nb_sync_mark64 = 55

◆ set_nb_sync_mark8

const unsigned char bm::set_nb_sync_mark8 = 50

◆ set_sblock_bienc

const unsigned char bm::set_sblock_bienc = 56

◆ set_sub_array_size

const unsigned bm::set_sub_array_size = set_array_size32

Definition at line 94 of file bmconst.h.

Referenced by aggregator_pipeline_execute(), bm::all_set< T >::all_set_block::all_set_block(), bm::bvector<>::any_range(), bm::bvector<>::bit_and(), bm::bvector<>::bit_or(), bm::bvector<>::bit_sub(), bm::bvector<>::bit_xor(), block_ptr_array_range(), block_to_global_index(), bm::bvector<>::build_rs_index(), bm::bvector<>::calc_stat(), bm::aggregator< bvector_type >::combine_and(), bm::aggregator< bvector_type >::combine_and_sub(), bm::bvector<>::combine_operation(), bm::bvector<>::combine_operation_and(), bm::bvector<>::combine_operation_or(), bm::bvector<>::combine_operation_sub(), bm::bvector<>::combine_operation_xor(), bm::aggregator< bvector_type >::combine_or(), bm::aggregator< bvector_type >::combine_shift_right_and(), bm::bvector<>::compare(), convert_sub_to_arr(), bm::bvector<>::count(), bm::deserializer< BV, bm::decoder >::decode_arr_sblock(), bm::deserializer< BV, bm::decoder >::deserialize(), distance_and_operation(), distance_operation(), distance_operation_any(), bm::bvector<>::erase(), bm::bvector<>::find(), bm::aggregator< bvector_type >::find_effective_sub_block_size(), bm::aggregator< bvector_type >::find_first_and_sub(), bm::bvector<>::find_first_mismatch(), find_interval_end(), bm::bvector<>::find_reverse(), for_each_bit(), for_each_bit_block_range(), for_each_block(), for_each_nzblock(), for_each_nzblock2(), for_each_nzblock_if(), for_each_nzblock_range(), bm::bvector< Alloc >::enumerator::go_first(), bm::bvector<>::insert(), bm::bvector<>::invert(), bm::bvector<>::is_all_one_range(), lower_bound_u64(), bm::bvector<>::merge(), bm::bvector<>::optimize(), bm::aggregator< bvector_type >::run_step(), bm::bvector<>::select(), bm::serializer< bvector_type >::serialize(), and bm::iterator_deserializer< BV, bm::serial_stream_iterator >::set_range().

◆ set_sub_total_bits

const unsigned bm::set_sub_total_bits = bm::set_sub_array_size * bm::gap_max_bits

◆ set_top_array_size

const unsigned bm::set_top_array_size = bm::set_array_size32

◆ set_total_blocks

const unsigned bm::set_total_blocks = bm::set_total_blocks32

◆ set_total_blocks32

const unsigned bm::set_total_blocks32 = (bm::set_array_size32 * bm::set_array_size32)

Definition at line 98 of file bmconst.h.

◆ set_word_mask

const unsigned bm::set_word_mask = 0x1Fu

◆ set_word_shift

const unsigned bm::set_word_shift = 5u

◆ sparse_max_l5

const unsigned bm::sparse_max_l5 = 48

Definition at line 1108 of file bmserial.h.

Referenced by bm::serializer< bvector_type >::set_compression_level().

◆ sparse_max_l6

const unsigned bm::sparse_max_l6 = 256

◆ sub_block3_size

const unsigned bm::sub_block3_size = bm::gap_max_bits / 4