BitMagic-C++
Data Structures | Macros | Functions
BIT functions

Data Structures

struct  bm::all_set< T >
 Structure carries pointer on bit block with all bits 1. More...
 
struct  bm::first_bit_table< T >
 Structure keeps index of first right 1 bit for every byte. More...
 
struct  bm::bit_count_table< T >
 Structure to aid in counting bits table contains count of bits in 0-255 diapason of numbers. More...
 
struct  bm::lzcnt_table< T >
 Structure for LZCNT constants (4-bit) More...
 
struct  bm::tzcnt_table< T >
 Structure for TZCNT constants. More...
 
struct  bm::block_set_table< T >
 Structure keeps all-left/right ON bits masks. More...
 

Macros

#define BM_INCWORD_BITCOUNT(cnt, w)   cnt += unsigned(_mm_popcnt_u32(w));
 

Functions

template<class T >
unsigned bm::bit_scan_reverse (T value)
 
BMFORCEINLINE bm::id_t bm::word_bitcount (bm::id_t w)
 
BMFORCEINLINE unsigned bm::word_bitcount64 (bm::id64_t x)
 
template<typename T , typename F >
void bm::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 bm::bit_for_each (T w, F &func)
 Templated algorithm to unpacks word into list of ON bit indexes. More...
 
template<typename T , typename B >
unsigned bm::bit_list (T w, B *bits)
 Unpacks word into list of ON bit indexes. More...
 
template<typename T , typename B >
unsigned bm::bit_list_4 (T w, B *bits)
 Unpacks word into list of ON bit indexes (quad-bit based) More...
 
template<typename B >
unsigned short bm::bitscan_popcnt (bm::id_t w, B *bits, unsigned short offs)
 Unpacks word into list of ON bit indexes using popcnt method. More...
 
template<typename B >
unsigned short bm::bitscan_popcnt (bm::id_t w, B *bits)
 Unpacks word into list of ON bit indexes using popcnt method. More...
 
template<typename B >
unsigned short bm::bitscan_popcnt64 (bm::id64_t w, B *bits)
 Unpacks 64-bit word into list of ON bit indexes using popcnt method. More...
 
BMFORCEINLINE bm::id64_t bm::widx_to_digest_mask (unsigned w_idx)
 Compute digest mask for word address in block. More...
 
BMFORCEINLINE bm::id64_t bm::digest_mask (unsigned from, unsigned to)
 Compute digest mask for [from..to] positions. More...
 
bool bm::check_zero_digest (bm::id64_t digest, unsigned bitpos_from, unsigned bitpos_to)
 check if all digest bits for the range [from..to] are 0 More...
 
void bm::block_init_digest0 (bm::word_t *const block, bm::id64_t digest)
 Init block with 000111000 pattren based on digest. More...
 
bm::id64_t bm::calc_block_digest0 (const bm::word_t *const block)
 Compute digest for 64 non-zero areas. More...
 
bm::id64_t bm::update_block_digest0 (const bm::word_t *const block, bm::id64_t digest)
 Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas) More...
 
template<typename T >
int bm::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 bm::wordcmp (T a, T b)
 Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes. More...
 
bool bm::bit_is_all_zero (const bm::word_t *BMRESTRICT start)
 Returns "true" if all bits in the block are 0. More...
 
BMFORCEINLINE void bm::set_bit (unsigned *dest, unsigned bitpos)
 Set 1 bit in a block. More...
 
BMFORCEINLINE void bm::clear_bit (unsigned *dest, unsigned bitpos)
 Set 1 bit in a block. More...
 
BMFORCEINLINE unsigned bm::test_bit (const unsigned *block, unsigned bitpos)
 Test 1 bit in a block. More...
 
void bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
 Sets bits to 1 in the bitblock. More...
 
void bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
 SUB (AND NOT) bit interval to 1 in the bitblock. More...
 
void bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
 XOR bit interval to 1 in the bitblock. More...
 
void bm::bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value)
 Bitblock memset operation. More...
 
template<typename T >
int bm::bitcmp (const T *buf1, const T *buf2, unsigned len)
 Lexicographical comparison of BIT buffers. More...
 
bm::id_t bm::bit_block_count (const bm::word_t *block)
 Bitcount for bit block. More...
 
bm::id_t bm::bit_block_count (const bm::word_t *const block, bm::id64_t digest)
 Bitcount for bit block. More...
 
bm::id_t bm::bit_block_calc_count (const bm::word_t *block, const bm::word_t *block_end)
 Bitcount for bit string. More...
 
bm::id_t bm::bit_count_change (bm::word_t w)
 
unsigned bm::bit_block_calc_change (const bm::word_t *block)
 
bm::id_t bm::bit_block_calc_count_range (const bm::word_t *block, bm::word_t left, bm::word_t right)
 
bm::id_t bm::bit_block_calc_count_to (const bm::word_t *block, bm::word_t right)
 
void bm::bit_block_rotate_left_1 (bm::word_t *block)
 
void bm::bit_block_rotate_left_1_unr (bm::word_t *block)
 Unrolled cyclic rotation of bit-block left by 1 bit. More...
 
bm::word_t bm::bit_block_insert (bm::word_t *block, unsigned bitpos, bool value)
 insert bit into position and shift the rest right with carryover More...
 
bool bm::bit_block_shift_r1 (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag)
 Right bit-shift bitblock by 1 bit (reference) More...
 
bool bm::bit_block_shift_r1_unr (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag)
 Right bit-shift of bit-block by 1 bit (loop unrolled) More...
 
bool bm::bit_block_shift_l1 (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag)
 Left bit-shift bitblock by 1 bit (reference) More...
 
bool bm::bit_block_shift_l1_unr (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag)
 Left bit-shift of bit-block by 1 bit (loop unrolled) More...
 
void bm::bit_block_erase (bm::word_t *block, unsigned bitpos, bool carry_over)
 erase bit from position and shift the rest right with carryover More...
 
bool bm::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)
 Right bit-shift of bit-block by 1 bit (reference) + AND. More...
 
bool bm::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)
 Right bit-shift bitblock by 1 bit (reference) + AND. More...
 
bm::id_t bm::bit_block_any_range (const bm::word_t *block, bm::word_t left, bm::word_t right)
 
template<typename T >
void bm::bit_invert (T *start)
 
bool bm::is_bits_one (const bm::wordop_t *start)
 Returns "true" if all bits in the block are 1. More...
 
void bm::bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Bitblock copy operation. More...
 
void bm::bit_block_stream (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Bitblock copy/stream operation. More...
 
bm::id64_t bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Plain bitblock AND operation. Function does not analyse availability of source and destination blocks. More...
 
bm::id64_t bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest)
 digest based bit-block AND More...
 
bm::id64_t bm::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)
 digest based bit-block AND 5-way More...
 
bm::id64_t bm::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)
 digest based bit-block AND More...
 
unsigned bm::bit_block_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_and_any (const bm::word_t *src1, const bm::word_t *src2)
 Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_or_count (const bm::word_t *src1, const bm::word_t *src2)
 Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
bm::word_tbm::bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock AND operation. More...
 
bm::id_t bm::bit_operation_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock AND operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_and_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock AND operation test. More...
 
bm::id_t bm::bit_operation_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock SUB operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_sub_count_inv (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs inverted bitblock SUB operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock test of SUB operation. More...
 
bm::id_t bm::bit_operation_or_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock OR operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock OR operation test. More...
 
bool bm::bit_block_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Plain bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bool bm::bit_block_or_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 2 way (target := source1 | source2) bitblock OR operation. More...
 
bm::id64_t bm::bit_block_xor_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 2 way (target := source1 ^ source2) bitblock XOR operation. More...
 
bool bm::bit_block_or_3way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bool bm::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)
 5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bm::word_tbm::bit_operation_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Block OR operation. Makes analysis if block is 0 or FULL. More...
 
bm::id64_t bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks. More...
 
bm::id64_t bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest)
 digest based bitblock SUB (AND NOT) operation More...
 
bm::id64_t bm::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)
 digest based bitblock SUB (AND NOT) operation (3 operand) More...
 
bm::word_tbm::bit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock SUB operation. More...
 
bm::id64_t bm::bit_block_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks. More...
 
void bm::bit_andnot_arr_ffmask (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock AND NOT with constant ~0 mask operation. More...
 
bm::word_tbm::bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock XOR operation. More...
 
bm::id_t bm::bit_operation_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock XOR operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock XOR operation test. More...
 
template<class T >
unsigned bm::bit_count_nonzero_size (const T *blk, unsigned data_size)
 Inspects block for full zero words. More...
 
unsigned bm::bit_block_find (const bm::word_t *block, unsigned nbit, unsigned *pos)
 Searches for the next 1 bit in the BIT block. More...
 
unsigned bm::bit_find_last (const bm::word_t *block, unsigned *last)
 BIT block find the last set bit (backward search) More...
 
unsigned bm::bit_find_first (const bm::word_t *block, unsigned *first)
 BIT block find the first set bit. More...
 
unsigned bm::bit_find_first (const bm::word_t *block, unsigned *first, bm::id64_t digest)
 BIT block find the first set bit. More...
 
bool bm::bit_find_first_if_1 (const bm::word_t *block, unsigned *first, bm::id64_t digest)
 BIT block find the first set bit if only 1 bit is set. More...
 
template<typename SIZE_TYPE >
SIZE_TYPE bm::bit_find_rank (const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos)
 BIT block find position for the rank. More...
 
bm::set_representation bm::best_representation (unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size)
 Choose best representation for a bit-block. More...
 
template<typename T >
bm::bit_convert_to_arr (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len, unsigned mask=0)
 Convert bit block into an array of ints corresponding to 1 bits. More...
 
unsigned short bm::bitscan_wave (const bm::word_t *w_ptr, unsigned char *bits)
 Unpacks word wave (Nx 32-bit words) More...
 
void bm::bit_block_gather_scatter (unsigned *arr, const bm::word_t *blk, const unsigned *idx, unsigned size, unsigned start, unsigned bit_idx)
 bit index to word gather-scatter algorithm (SIMD) More...
 
template<typename TRGW , typename IDX , typename SZ >
void bm::bit_block_gather_scatter (TRGW *arr, const bm::word_t *blk, const IDX *idx, SZ size, SZ start, unsigned bit_idx)
 bit index to word gather-scatter algorithm More...
 
template<typename Func , typename SIZE_TYPE >
void bm::for_each_bit_blk (const bm::word_t *block, SIZE_TYPE offset, Func &bit_functor)
 for-each visitor, calls a special visitor functor for each 1 bit group More...
 
template<typename T , unsigned BPC, unsigned BPS>
void bm::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 bm::bit_iblock_make_pcv (const unsigned distance[BPC][BPC], unsigned char *pc_vector)
 !< ibpc limiter More...
 
unsigned bm::count_leading_zeros (unsigned x)
 Portable LZCNT with (uses minimal LUT) More...
 
unsigned bm::count_trailing_zeros (unsigned v)
 Portable TZCNT with (uses 37-LUT) More...
 

Detailed Description

Bit functions implement different opereations on bit blocks (internals) and serve as a minimal building blocks.

Macro Definition Documentation

◆ BM_INCWORD_BITCOUNT

#define BM_INCWORD_BITCOUNT (   cnt,
 
)    cnt += unsigned(_mm_popcnt_u32(w));

Function Documentation

◆ best_representation()

bm::set_representation bm::best_representation ( unsigned  bit_count,
unsigned  total_possible_bitcount,
unsigned  gap_count,
unsigned  block_size 
)
inline

Choose best representation for a bit-block.

Definition at line 6941 of file bmfunc.h.

References bm::set_array0, bm::set_array1, bm::set_bitset, and bm::set_gap.

Referenced by bm::gap_2_bitblock().

◆ bit_andnot_arr_ffmask()

void bm::bit_andnot_arr_ffmask ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

bitblock AND NOT with constant ~0 mask operation.

Parameters
dst- destination block.
src- source block.

Definition at line 6439 of file bmfunc.h.

References bm::all_bits_mask, BMRESTRICT, bm::set_block_size, and VECT_ANDNOT_ARR_2_MASK.

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

◆ bit_block_and() [1/2]

bm::id64_t bm::bit_block_and ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

Plain bitblock AND operation. Function does not analyse availability of source and destination blocks.

Parameters
dst- destination block.
src- source block.
Returns
0 if AND operation did not produce anything (no 1s in the output)

Definition at line 5107 of file bmfunc.h.

References BM_ASSERT, BMRESTRICT, bm::set_block_size, and VECT_AND_BLOCK.

Referenced by bm::bit_operation_and(), bm::bvector<>::combine_operation(), bm::serial_stream_iterator< DEC >::get_bit_block_AND(), and bm::aggregator< bvector_type >::process_bit_blocks_and().

◆ bit_block_and() [2/2]

bm::id64_t bm::bit_block_and ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src,
bm::id64_t  digest 
)
inline

digest based bit-block AND

Parameters
dst- destination block.
src- source block.
digest- known digest of dst block
Returns
new digest

Definition at line 5145 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_AND_DIGEST, and bm::word_bitcount64().

◆ bit_block_and_2way()

bm::id64_t bm::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 
)
inline

digest based bit-block AND

dst = src1 AND src2

Parameters
dst- destination block.
src1- source block.
src2- source block.
digest- known initial digest
Returns
new digest

Definition at line 5267 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_AND_DIGEST_2WAY, and bm::word_bitcount64().

Referenced by bm::bvector<>::combine_operation(), and bm::aggregator< bvector_type >::process_bit_blocks_and().

◆ bit_block_and_5way()

bm::id64_t bm::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 
)
inline

◆ bit_block_and_any()

unsigned bm::bit_block_and_any ( const bm::word_t src1,
const bm::word_t src2 
)
inline

Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks.

Parameters
src1- first bit block
src2- second bit block

Definition at line 5379 of file bmfunc.h.

References bm::set_block_size.

Referenced by bm::bit_operation_and_any().

◆ bit_block_and_count()

unsigned bm::bit_block_and_count ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.

Parameters
src1- first bit block
src2- second bit block

Definition at line 5330 of file bmfunc.h.

References bm::bitcount64_4way(), BM_INCWORD_BITCOUNT, bm::set_block_size, and VECT_BITCOUNT_AND.

Referenced by bm::bit_operation_and_count().

◆ 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

Function calculates if there is any number of 1 bits in the given array of words in the range between left anf right bits (borders included). Make sure the addresses are aligned.

Definition at line 4673 of file bmfunc.h.

References BM_ASSERT, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::gap_bitset_and_any(), bm::gap_bitset_sub_any(), and bm::gap_bitset_xor_any().

◆ bit_block_calc_change()

unsigned bm::bit_block_calc_change ( const bm::word_t block)
inline

Function calculates number of times when bit value changed (1-0 or 0-1) in the bit block.

Parameters
block- bit-block start pointer
Returns
number of 1-0, 0-1 transitions

Definition at line 4173 of file bmfunc.h.

References bm::bit_block_change32(), and VECT_BLOCK_CHANGE.

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

◆ bit_block_calc_count()

bm::id_t bm::bit_block_calc_count ( const bm::word_t block,
const bm::word_t block_end 
)
inline

Bitcount for bit string.

Added for back-compatibility purposes, not block aligned, not SIMD accelerated

Definition at line 4074 of file bmfunc.h.

References BM_INCWORD_BITCOUNT.

◆ bit_block_calc_count_range()

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

Function calculates number of 1 bits in the given array of words in the range between left anf right bits (borders included) Make sure the addr is aligned.

Definition at line 4191 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, bm::set_word_mask, bm::set_word_shift, and bm::word_bitcount().

Referenced by bm::bvector<>::build_rs_index(), bm::bvector<>::count_blocks(), bm::bvector<>::count_range(), bm::gap_bitset_and_count(), bm::gap_bitset_or_count(), bm::gap_bitset_sub_count(), and bm::gap_bitset_xor_count().

◆ bit_block_calc_count_to()

bm::id_t bm::bit_block_calc_count_to ( const bm::word_t block,
bm::word_t  right 
)
inline

Function calculates number of 1 bits in the given array of words in the range between 0 anf right bits (borders included) Make sure the addr is aligned.

Definition at line 4260 of file bmfunc.h.

References BM_ASSERT, bm::word_bitcount(), and bm::word_bitcount64().

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

◆ bit_block_copy()

void bm::bit_block_copy ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

◆ bit_block_count() [1/2]

bm::id_t bm::bit_block_count ( const bm::word_t block)
inline

◆ bit_block_count() [2/2]

bm::id_t bm::bit_block_count ( const bm::word_t *const  block,
bm::id64_t  digest 
)
inline

Bitcount for bit block.

Function calculates number of 1 bits in the given array of words. uses digest to understand zero areas

Definition at line 4035 of file bmfunc.h.

References bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, and bm::word_bitcount64().

◆ bit_block_erase()

void bm::bit_block_erase ( bm::word_t block,
unsigned  bitpos,
bool  carry_over 
)
inline

erase bit from position and shift the rest right with carryover

Parameters
block- bit-block pointer
bitpos- bit position to insert
carry_over- bit value to add to the end (0|1)

Definition at line 4522 of file bmfunc.h.

References bm::bit_block_shift_l1_unr(), BM_ASSERT, bm::set_block_mask, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.

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

◆ bit_block_find()

unsigned bm::bit_block_find ( const bm::word_t block,
unsigned  nbit,
unsigned *  pos 
)
inline

Searches for the next 1 bit in the BIT block.

Parameters
block- BIT buffer
nbit- bit index to start checking from
pos- [out] found value
Returns
0 if not found

Definition at line 6631 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.

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

◆ bit_block_gather_scatter() [1/2]

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

bit index to word gather-scatter algorithm (SIMD)

Definition at line 7520 of file bmfunc.h.

References BM_ASSERT, and bm::sse4_bit_block_gather_scatter().

Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::gather().

◆ bit_block_gather_scatter() [2/2]

template<typename TRGW , typename IDX , typename SZ >
void bm::bit_block_gather_scatter ( TRGW *  arr,
const bm::word_t blk,
const IDX *  idx,
SZ  size,
SZ  start,
unsigned  bit_idx 
)

bit index to word gather-scatter algorithm

Definition at line 7551 of file bmfunc.h.

References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.

◆ bit_block_insert()

bm::word_t bm::bit_block_insert ( bm::word_t block,
unsigned  bitpos,
bool  value 
)
inline

insert bit into position and shift the rest right with carryover

Parameters
block- bit-block pointer
bitpos- bit position to insert
value- bit value (0|1) to insert
Returns
carry over value

Definition at line 4369 of file bmfunc.h.

References BM_ASSERT, bm::set_block_mask, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.

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

◆ bit_block_or()

bool bm::bit_block_or ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.

Parameters
dst- destination block.
src- source block.

Definition at line 5915 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK.

Referenced by bm::bit_operation_or(), bm::bvector<>::combine_operation(), bm::deserializer< typename SV::bvector_type, bm::decoder >::decode_bit_block(), bm::serial_stream_iterator< DEC >::get_bit_block_OR(), and bm::aggregator< bvector_type >::process_bit_blocks_or().

◆ bit_block_or_2way()

bool bm::bit_block_or_2way ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

2 way (target := source1 | source2) bitblock OR operation.

Parameters
dst- dest block [out]
src1- source 1
src2- source 2
Returns
1 if produced block of ALL ones

Definition at line 5952 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_2WAY.

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

◆ bit_block_or_3way()

bool bm::bit_block_or_3way ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of source and destination blocks.

Parameters
dst- sst-dest block [in,out]
src1- source 1
src2- source 2
Returns
1 if produced block of ALL ones

Definition at line 6032 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_3WAY.

Referenced by bm::aggregator< bvector_type >::process_bit_blocks_or().

◆ bit_block_or_5way()

bool bm::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 
)
inline

5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of source and destination blocks.

Parameters
dst- destination block.
src1- source1, etc
Returns
1 if produced block of ALL ones

Definition at line 6073 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_5WAY.

Referenced by bm::aggregator< bvector_type >::process_bit_blocks_or().

◆ bit_block_or_any()

unsigned bm::bit_block_or_any ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.

Parameters
src1- first bit block.
src2- second bit block.

Definition at line 5610 of file bmfunc.h.

References BMRESTRICT, and bm::set_block_size.

Referenced by bm::bit_operation_or_any().

◆ bit_block_or_count()

unsigned bm::bit_block_or_count ( const bm::word_t src1,
const bm::word_t src2 
)
inline

Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.

Parameters
src1- first bit block
src2- second bit block.

Definition at line 5562 of file bmfunc.h.

References bm::bitcount64_4way(), BM_INCWORD_BITCOUNT, bm::set_block_size, and VECT_BITCOUNT_OR.

Referenced by bm::bit_operation_or_count().

◆ bit_block_rotate_left_1()

void bm::bit_block_rotate_left_1 ( bm::word_t block)
inline

Cyclic rotation of bit-block left by 1 bit

Definition at line 4317 of file bmfunc.h.

References bm::set_block_size.

◆ bit_block_rotate_left_1_unr()

void bm::bit_block_rotate_left_1_unr ( bm::word_t block)
inline

Unrolled cyclic rotation of bit-block left by 1 bit.

Parameters
block- bit-block pointer

Definition at line 4333 of file bmfunc.h.

References bm::set_block_size.

◆ bit_block_set()

void bm::bit_block_set ( bm::word_t *BMRESTRICT  dst,
bm::word_t  value 
)
inline

◆ bit_block_shift_l1()

bool bm::bit_block_shift_l1 ( bm::word_t block,
bm::word_t empty_acc,
bm::word_t  co_flag 
)
inline

Left bit-shift bitblock by 1 bit (reference)

Parameters
block- bit-block pointer
empty_acc- [out] contains 0 if block is empty
co_flag- carry over from the prev/next block
Returns
carry over bit (1 or 0)

Definition at line 4470 of file bmfunc.h.

References BM_ASSERT, and bm::set_block_size.

Referenced by bm::bit_block_shift_l1_unr().

◆ bit_block_shift_l1_unr()

bool bm::bit_block_shift_l1_unr ( bm::word_t block,
bm::word_t empty_acc,
bm::word_t  co_flag 
)
inline

Left bit-shift of bit-block by 1 bit (loop unrolled)

Parameters
block- bit-block pointer
empty_acc- [out] contains 0 if block is empty
co_flag- carry over from the prev/next block
Returns
carry over bit (1 or 0)

Definition at line 4500 of file bmfunc.h.

References bm::bit_block_shift_l1(), BM_ASSERT, and VECT_SHIFT_L1.

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

◆ bit_block_shift_r1()

bool bm::bit_block_shift_r1 ( bm::word_t block,
bm::word_t empty_acc,
bm::word_t  co_flag 
)
inline

Right bit-shift bitblock by 1 bit (reference)

Parameters
block- bit-block pointer
empty_acc- [out] contains 0 if block is empty
co_flag- carry over from the previous block
Returns
carry over bit (1 or 0)

Definition at line 4417 of file bmfunc.h.

References BM_ASSERT, and bm::set_block_size.

Referenced by bm::bit_block_shift_r1_unr().

◆ bit_block_shift_r1_and()

bool bm::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 
)
inline

Right bit-shift of bit-block by 1 bit (reference) + AND.

Parameters
block- bit-block pointer
co_flag- carry over from the previous block
mask_block- mask bit-block pointer
digest- block digest
Returns
carry over bit (1 or 0)

Definition at line 4576 of file bmfunc.h.

References BM_ASSERT, bm::set_block_digest_wave_size, bm::set_block_size, and bm::word_bitcount64().

Referenced by bm::bit_block_shift_r1_and_unr().

◆ bit_block_shift_r1_and_unr()

bool bm::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 
)
inline

Right bit-shift bitblock by 1 bit (reference) + AND.

Parameters
block- bit-block pointer
co_flag- carry over from the previous block
mask_block- mask bit-block pointer
digest- block digest
Returns
carry over bit (1 or 0)

Definition at line 4648 of file bmfunc.h.

References bm::bit_block_shift_r1_and(), BM_ASSERT, and VECT_SHIFT_R1_AND.

Referenced by bm::aggregator< bvector_type >::process_shift_right_and().

◆ bit_block_shift_r1_unr()

bool bm::bit_block_shift_r1_unr ( bm::word_t block,
bm::word_t empty_acc,
bm::word_t  co_flag 
)
inline

Right bit-shift of bit-block by 1 bit (loop unrolled)

Parameters
block- bit-block pointer
empty_acc- [out] contains 0 if block is empty
co_flag- carry over from the previous block
Returns
carry over bit (1 or 0)

Definition at line 4446 of file bmfunc.h.

References bm::bit_block_shift_r1(), BM_ASSERT, and VECT_SHIFT_R1.

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

◆ bit_block_stream()

void bm::bit_block_stream ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

Bitblock copy/stream operation.

Parameters
dst- destination block.
src- source block.

Definition at line 5085 of file bmfunc.h.

References bm::set_block_size, and VECT_STREAM_BLOCK.

◆ bit_block_sub() [1/2]

bm::id64_t bm::bit_block_sub ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks.

Parameters
dst- destination block.
src- source block.
Returns
0 if SUB operation did not produce anything (no 1s in the output)

Definition at line 6182 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_SUB_BLOCK.

Referenced by bm::bit_operation_sub(), bm::bvector<>::combine_operation(), bm::serial_stream_iterator< DEC >::get_bit_block_SUB(), and bm::aggregator< bvector_type >::process_bit_blocks_sub().

◆ bit_block_sub() [2/2]

bm::id64_t bm::bit_block_sub ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src,
bm::id64_t  digest 
)
inline

digest based bitblock SUB (AND NOT) operation

Parameters
dst- destination block.
src- source block.
digest- known digest of dst block
Returns
new digest

Definition at line 6218 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_SUB_DIGEST, and bm::word_bitcount64().

◆ bit_block_sub_2way()

bm::id64_t bm::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 
)
inline

digest based bitblock SUB (AND NOT) operation (3 operand)

Parameters
dst- destination block.
src1- source block.
src1- source block.
digest- known digest of dst block
Returns
new digest

Definition at line 6278 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_SUB_DIGEST_2WAY, and bm::word_bitcount64().

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

◆ bit_block_sub_any()

unsigned bm::bit_block_sub_any ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.

Parameters
src1- first bit block.
src2- second bit block.

Definition at line 5533 of file bmfunc.h.

References BMRESTRICT, and bm::set_block_size.

Referenced by bm::bit_operation_sub_any().

◆ bit_block_sub_count()

unsigned bm::bit_block_sub_count ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.

Parameters
src1- first bit block.
src2- second bit block.

Definition at line 5485 of file bmfunc.h.

References bm::bitcount64_4way(), BM_INCWORD_BITCOUNT, BMRESTRICT, bm::set_block_size, and VECT_BITCOUNT_SUB.

Referenced by bm::bit_operation_sub_count().

◆ bit_block_xor()

bm::id64_t bm::bit_block_xor ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks.

Parameters
dst- destination block.
src- source block.

Definition at line 6403 of file bmfunc.h.

References BM_ASSERT, BMRESTRICT, bm::set_block_size, and VECT_XOR_BLOCK.

Referenced by bm::bit_operation_xor(), bm::bvector<>::combine_operation(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), and bm::serial_stream_iterator< DEC >::get_bit_block_XOR().

◆ bit_block_xor_2way()

bm::id64_t bm::bit_block_xor_2way ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

2 way (target := source1 ^ source2) bitblock XOR operation.

Parameters
dst- dest block [out]
src1- source 1
src2- source 2
Returns
OR accumulator

Definition at line 5991 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_XOR_BLOCK_2WAY.

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

◆ bit_block_xor_any()

unsigned bm::bit_block_xor_any ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.

Parameters
src1- first bit block.
src2- second bit block.

Definition at line 5458 of file bmfunc.h.

References BMRESTRICT, and bm::set_block_size.

Referenced by bm::bit_operation_xor_any().

◆ bit_block_xor_count()

unsigned bm::bit_block_xor_count ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.

Parameters
src1- first bit block
src2- second bit block

Definition at line 5409 of file bmfunc.h.

References bm::bitcount64_4way(), BM_INCWORD_BITCOUNT, BMRESTRICT, bm::set_block_size, and VECT_BITCOUNT_XOR.

Referenced by bm::bit_operation_xor_count().

◆ bit_convert_to_arr()

template<typename T >
T bm::bit_convert_to_arr ( T *BMRESTRICT  dest,
const unsigned *BMRESTRICT  src,
bm::id_t  bits,
unsigned  dest_len,
unsigned  mask = 0 
)

Convert bit block into an array of ints corresponding to 1 bits.

Returns
destination size as a result of block decoding

Definition at line 6978 of file bmfunc.h.

References BMRESTRICT, and bm::word_bitcount().

Referenced by bm::serializer< bvector_type >::bienc_arr_bit_block(), bm::serializer< bvector_type >::encode_bit_array(), bm::serializer< bvector_type >::gamma_arr_bit_block(), bm::serializer< bvector_type >::interpolated_arr_bit_block(), and bm::random_subset< BV >::sample().

◆ bit_count_change()

bm::id_t bm::bit_count_change ( bm::word_t  w)
inline

Function calculates number of times when bit value changed (1-0 or 0-1).

For 001 result is 2 010 - 3 011 - 2 111 - 1

Definition at line 4109 of file bmfunc.h.

References bm::word_bitcount().

◆ bit_count_nonzero_size()

template<class T >
unsigned bm::bit_count_nonzero_size ( const T *  blk,
unsigned  data_size 
)

Inspects block for full zero words.

Parameters
blk- bit block pointer
data_size- data size
Returns
size of all non-zero words

Definition at line 6571 of file bmfunc.h.

References BM_ASSERT.

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

◆ bit_find_first() [1/2]

unsigned bm::bit_find_first ( const bm::word_t block,
unsigned *  first 
)
inline

BIT block find the first set bit.

Parameters
block- bit block buffer pointer
first- index of the first 1 bit (out)
Returns
0 if not found

Definition at line 6711 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, and bm::set_block_size.

Referenced by bm::bvector<>::find(), bm::aggregator< bvector_type >::find_first_and_sub(), and bm::bvector<>::select().

◆ bit_find_first() [2/2]

unsigned bm::bit_find_first ( const bm::word_t block,
unsigned *  first,
bm::id64_t  digest 
)
inline

BIT block find the first set bit.

Parameters
block- bit block buffer pointer
first- index of the first 1 bit (out)
digest- known digest of dst block
Returns
0 if not found

Definition at line 6743 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, bm::bmi_blsi_u64(), bm::set_block_digest_wave_size, bm::set_block_size, and bm::word_bitcount64().

◆ bit_find_first_if_1()

bool bm::bit_find_first_if_1 ( const bm::word_t block,
unsigned *  first,
bm::id64_t  digest 
)
inline

BIT block find the first set bit if only 1 bit is set.

Parameters
block- bit block buffer pointer
first- index of the first 1 bit (out)
digest- known digest of dst block
Returns
0 if not found

Definition at line 6781 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, bm::bmi_blsi_u64(), bm::set_block_digest_wave_size, bm::word_bitcount(), and bm::word_bitcount64().

Referenced by bm::aggregator< bvector_type >::process_bit_blocks_and(), bm::aggregator< bvector_type >::process_bit_blocks_sub(), bm::aggregator< bvector_type >::process_gap_blocks_and(), and bm::aggregator< bvector_type >::process_gap_blocks_sub().

◆ bit_find_last()

unsigned bm::bit_find_last ( const bm::word_t block,
unsigned *  last 
)
inline

BIT block find the last set bit (backward search)

Parameters
block- bit block buffer pointer
last- index of the last 1 bit (out)
Returns
0 is not found

Definition at line 6679 of file bmfunc.h.

References bm::bit_scan_reverse(), BM_ASSERT, and bm::set_block_size.

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

◆ bit_find_rank()

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

BIT block find position for the rank.

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

Definition at line 6838 of file bmfunc.h.

References BM_ASSERT, bm::set_block_size, bm::set_word_mask, bm::set_word_shift, bm::word_bitcount(), bm::word_bitcount64(), and bm::word_select64().

Referenced by bm::block_find_rank().

◆ bit_for_each()

template<typename T , typename F >
void bm::bit_for_each ( w,
F &  func 
)

Templated algorithm to unpacks word into list of ON bit indexes.

Parameters
w- value
func- bit functor

Definition at line 355 of file bmfunc.h.

Referenced by bm::bit_list().

◆ bit_for_each_4()

template<typename T , typename F >
void bm::bit_for_each_4 ( w,
F &  func 
)

Templated algorithm to unpacks octet based word into list of ON bit indexes.

Parameters
w- value
func- bit functor

Definition at line 285 of file bmfunc.h.

References BM_ASSERT.

Referenced by bm::bit_list_4().

◆ bit_iblock_make_pcv()

template<typename T , unsigned BPC, unsigned BPS>
void bm::bit_iblock_make_pcv ( const unsigned  distance[BPC][BPC],
unsigned char *  pc_vector 
)

!< ibpc limiter

Make a compression descriptor vector for bit-plains

Parameters
distance- pairwise distance matrix
pc_vector- OUT compression descriptor vector
    pc_vector[] format:
        each element (pc_vector[i]) describes the plain compression:
            first 3 bits - compression code:
                0 - plain uncompressed
                1 - plain is ALL ZERO (000000...)
                2 - plain is ALL ONE  (111111...)
                3 - plain is equal to another plain J (5 high bits (max 31))
                4 - plain is close (but not equal) to plain J
            next 5 bits - number of plain used as a XOR expression
             ( compression codes: 3,4 )

Definition at line 381 of file bmtrans.h.

References BM_ASSERT, bm::ibpc_all_one, bm::ibpc_all_zero, and bm::ibpc_uncompr.

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

◆ bit_invert()

template<typename T >
void bm::bit_invert ( T *  start)

◆ bit_is_all_zero()

bool bm::bit_is_all_zero ( const bm::word_t *BMRESTRICT  start)
inline

◆ bit_list()

template<typename T , typename B >
unsigned bm::bit_list ( w,
B *  bits 
)

Unpacks word into list of ON bit indexes.

Parameters
w- value
bits- pointer on the result array
Returns
number of bits in the list

Definition at line 426 of file bmfunc.h.

References bm::bit_for_each(), and bm::copy_to_array_functor< B >::ptr().

Referenced by bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::import_no_check(), and bm::random_subset< BV >::sample().

◆ bit_list_4()

template<typename T , typename B >
unsigned bm::bit_list_4 ( w,
B *  bits 
)

Unpacks word into list of ON bit indexes (quad-bit based)

Parameters
w- value
bits- pointer on the result array
Returns
number of bits in the list

Definition at line 443 of file bmfunc.h.

References bm::bit_for_each_4(), and bm::copy_to_array_functor< B >::ptr().

◆ bit_operation_and()

bm::word_t* bm::bit_operation_and ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

bitblock AND operation.

Parameters
dst- destination block.
src- source block.
Returns
pointer on destination block. If returned value equal to src means that block mutation requested. NULL is valid return value.

Definition at line 5642 of file bmfunc.h.

References bm::bit_block_and(), BM_ASSERT, IS_EMPTY_BLOCK, IS_FULL_BLOCK, and IS_VALID_ADDR.

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

◆ bit_operation_and_any()

bm::id_t bm::bit_operation_and_any ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Performs bitblock AND operation test.

Parameters
src1- first bit block.
src2- second bit block.
Returns
non zero if there is any value

Definition at line 5730 of file bmfunc.h.

References bm::bit_block_and_any(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.

Referenced by bm::combine_any_operation_with_block().

◆ bit_operation_and_count()

bm::id_t bm::bit_operation_and_count ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Performs bitblock AND operation and calculates bitcount of the result.

Parameters
src1- first bit block.
src2- second bit block.
Returns
bitcount value

Definition at line 5706 of file bmfunc.h.

References bm::bit_block_and_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.

Referenced by bm::operation_functions< T >::bit_operation_count(), bm::combine_count_and_operation_with_block(), and bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_AND().

◆ bit_operation_or()

bm::word_t* bm::bit_operation_or ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

Block OR operation. Makes analysis if block is 0 or FULL.

Parameters
dst- destination block.
src- source block.
Returns
pointer on destination block. If returned value equal to src means that block mutation requested. NULL is valid return value.

Definition at line 6122 of file bmfunc.h.

References bm::bit_block_or(), BM_ASSERT, FULL_BLOCK_FAKE_ADDR, IS_FULL_BLOCK, IS_VALID_ADDR, and bm::set_block_size.

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

◆ bit_operation_or_any()

bm::id_t bm::bit_operation_or_any ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Performs bitblock OR operation test.

Parameters
src1- first bit block.
src2- second bit block.
Returns
non zero value if there are any bits

Definition at line 5882 of file bmfunc.h.

References bm::bit_block_or_any(), bm::bit_is_all_zero(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.

Referenced by bm::combine_any_operation_with_block().

◆ bit_operation_or_count()

bm::id_t bm::bit_operation_or_count ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Performs bitblock OR operation and calculates bitcount of the result.

Parameters
src1- first bit block.
src2- second bit block.
Returns
bitcount value

Definition at line 5845 of file bmfunc.h.

References bm::bit_block_count(), bm::bit_block_or_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

Referenced by bm::operation_functions< T >::bit_operation_count(), and bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_OR().

◆ bit_operation_sub()

bm::word_t* bm::bit_operation_sub ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

bitblock SUB operation.

Parameters
dst- destination block.
src- source block.
Returns
pointer on destination block. If returned value equal to src means that block mutation requested. NULL is valid return value.

Definition at line 6345 of file bmfunc.h.

References bm::bit_block_sub(), BM_ASSERT, IS_FULL_BLOCK, and IS_VALID_ADDR.

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

◆ bit_operation_sub_any()

bm::id_t bm::bit_operation_sub_any ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Performs bitblock test of SUB operation.

Parameters
src1- first bit block.
src2- second bit block
Returns
non zero value if there are any bits

Definition at line 5810 of file bmfunc.h.

References bm::bit_block_sub_any(), bm::bit_is_all_zero(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

Referenced by bm::combine_any_operation_with_block().

◆ bit_operation_sub_count()

bm::id_t bm::bit_operation_sub_count ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

◆ bit_operation_sub_count_inv()

bm::id_t bm::bit_operation_sub_count_inv ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Performs inverted bitblock SUB operation and calculates bitcount of the result.

Parameters
src1- first bit block.
src2- second bit block
Returns
bitcount value

Definition at line 5792 of file bmfunc.h.

References bm::bit_operation_sub_count().

Referenced by bm::operation_functions< T >::bit_operation_count().

◆ bit_operation_xor()

bm::word_t* bm::bit_operation_xor ( bm::word_t *BMRESTRICT  dst,
const bm::word_t *BMRESTRICT  src 
)
inline

bitblock XOR operation.

Parameters
dst- destination block.
src- source block.
Returns
pointer on destination block. If returned value equal to src means that block mutation requested. NULL is valid return value.

Definition at line 6474 of file bmfunc.h.

References bm::bit_block_xor(), BM_ASSERT, and IS_VALID_ADDR.

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

◆ bit_operation_xor_any()

bm::id_t bm::bit_operation_xor_any ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Performs bitblock XOR operation test.

Parameters
src1- bit block start ptr
src2- second bit block ptr
Returns
non zero value if there are bits

Definition at line 6545 of file bmfunc.h.

References bm::bit_block_xor_any(), bm::bit_is_all_zero(), and IS_EMPTY_BLOCK.

Referenced by bm::combine_any_operation_with_block().

◆ bit_operation_xor_count()

bm::id_t bm::bit_operation_xor_count ( const bm::word_t *BMRESTRICT  src1,
const bm::word_t *BMRESTRICT  src2 
)
inline

Performs bitblock XOR operation and calculates bitcount of the result.

Parameters
src1- bit block start ptr
src1_end- bit block end ptr
src2- second bit block
Returns
bitcount value

Definition at line 6513 of file bmfunc.h.

References bm::bit_block_count(), bm::bit_block_xor_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

Referenced by bm::operation_functions< T >::bit_operation_count(), and bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_XOR().

◆ bit_scan_reverse()

template<class T >
unsigned bm::bit_scan_reverse ( value)

◆ bitcmp()

template<typename T >
int bm::bitcmp ( const T *  buf1,
const T *  buf2,
unsigned  len 
)

Lexicographical comparison of BIT buffers.

Parameters
buf1- First buffer pointer.
buf2- Second buffer pointer.
len- Buffer length in elements (T).
Returns
<0 - less, =0 - equal, >0 - greater.

Definition at line 3733 of file bmfunc.h.

References BM_ASSERT.

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

◆ bitscan_popcnt() [1/2]

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

Unpacks word into list of ON bit indexes using popcnt method.

Parameters
w- value
bits- pointer on the result array
offs- value to add to bit position (programmed shift)
Returns
number of bits in the list

Definition at line 461 of file bmfunc.h.

References bm::word_bitcount().

Referenced by bm::bitscan(), bm::bitscan_wave(), and bm::random_subset< BV >::sample().

◆ bitscan_popcnt() [2/2]

template<typename B >
unsigned short bm::bitscan_popcnt ( bm::id_t  w,
B *  bits 
)

Unpacks word into list of ON bit indexes using popcnt method.

Parameters
w- value
bits- pointer on the result array
Returns
number of bits in the list

Definition at line 483 of file bmfunc.h.

References bm::word_bitcount().

◆ bitscan_popcnt64()

template<typename B >
unsigned short bm::bitscan_popcnt64 ( bm::id64_t  w,
B *  bits 
)

Unpacks 64-bit word into list of ON bit indexes using popcnt method.

Parameters
w- value
bits- pointer on the result array
offs- bit address offset to add (0 - default)
Returns
number of bits in the list

Definition at line 506 of file bmfunc.h.

References bm::word_bitcount64().

Referenced by bm::bitscan(), and bm::bitscan_wave().

◆ bitscan_wave()

unsigned short bm::bitscan_wave ( const bm::word_t w_ptr,
unsigned char *  bits 
)
inline

Unpacks word wave (Nx 32-bit words)

Parameters
w_ptr- pointer on wave start
bits- pointer on the result array
Returns
number of bits in the list

Definition at line 7491 of file bmfunc.h.

References bm::bitscan_popcnt(), and bm::bitscan_popcnt64().

Referenced by bm::for_each_bit_blk(), and bm::bvector< Alloc >::enumerator::go_to().

◆ block_init_digest0()

void bm::block_init_digest0 ( bm::word_t *const  block,
bm::id64_t  digest 
)
inline

Init block with 000111000 pattren based on digest.

Parameters
block- Bit block [out]
digest- digest (used for block initialization)

Definition at line 672 of file bmfunc.h.

References bm::set_block_digest_wave_size, and VECT_BLOCK_SET_DIGEST.

Referenced by bm::aggregator< bvector_type >::process_bit_blocks_and().

◆ calc_block_digest0()

bm::id64_t bm::calc_block_digest0 ( const bm::word_t *const  block)
inline

Compute digest for 64 non-zero areas.

Parameters
block- Bit block
Returns
digest bit-mask (0 means all block is empty)

Definition at line 702 of file bmfunc.h.

References bm::set_block_digest_wave_size, and VECT_IS_DIGEST_ZERO.

Referenced by bm::bvector<>::combine_operation(), bm::serializer< bvector_type >::find_bit_best_encoding(), bm::aggregator< bvector_type >::process_bit_blocks_and(), bm::aggregator< bvector_type >::process_shift_right_and(), and bm::update_block_digest0().

◆ check_zero_digest()

bool bm::check_zero_digest ( bm::id64_t  digest,
unsigned  bitpos_from,
unsigned  bitpos_to 
)
inline

check if all digest bits for the range [from..to] are 0

Parameters
digest- current digest
bitpos_from- range from (in bit-block coordinates)
bitpos_to- range to (in bit-block coordinates)
Returns
true if all range is zero

Definition at line 657 of file bmfunc.h.

References bm::digest_mask().

Referenced by bm::gap_and_to_bitset(), and bm::gap_sub_to_bitset().

◆ clear_bit()

BMFORCEINLINE void bm::clear_bit ( unsigned *  dest,
unsigned  bitpos 
)

◆ count_leading_zeros()

unsigned bm::count_leading_zeros ( unsigned  x)
inline

Portable LZCNT with (uses minimal LUT)

Definition at line 158 of file bmutil.h.

◆ count_trailing_zeros()

unsigned bm::count_trailing_zeros ( unsigned  v)
inline

Portable TZCNT with (uses 37-LUT)

Definition at line 174 of file bmutil.h.

◆ digest_mask()

BMFORCEINLINE bm::id64_t bm::digest_mask ( unsigned  from,
unsigned  to 
)

Compute digest mask for [from..to] positions.

Parameters
from- range from (in bit-block coordinates)
to- range to (in bit-block coordinates)

Definition at line 634 of file bmfunc.h.

References BM_ASSERT, and bm::set_block_digest_pos_shift.

Referenced by bm::check_zero_digest(), and bm::aggregator< bvector_type >::process_bit_blocks_and().

◆ for_each_bit_blk()

template<typename Func , typename SIZE_TYPE >
void bm::for_each_bit_blk ( const bm::word_t block,
SIZE_TYPE  offset,
Func &  bit_functor 
)

for-each visitor, calls a special visitor functor for each 1 bit group

Parameters
block- bit block buffer pointer
offset- global block offset (number of bits)
bit_functor- functor must support .add_bits(offset, bits_ptr, size)

Definition at line 1660 of file bmalgo_impl.h.

References bm::bitscan_wave(), bm::gap_max_bits, IS_FULL_BLOCK, bm::set_bitscan_wave_size, and bm::set_block_size.

◆ is_bits_one()

bool bm::is_bits_one ( const bm::wordop_t start)
inline

Returns "true" if all bits in the block are 1.

Definition at line 4760 of file bmfunc.h.

References bm::all_bits_mask, BMRESTRICT, bm::set_block_size, and VECT_IS_ONE_BLOCK.

Referenced by bm::check_block_one(), bm::bvector<>::combine_operation(), and bm::aggregator< bvector_type >::process_bit_blocks_or().

◆ or_bit_block()

void bm::or_bit_block ( unsigned *  dest,
unsigned  bitpos,
unsigned  bitcount 
)
inline

Sets bits to 1 in the bitblock.

Parameters
dest- Bitset buffer.
bitpos- Offset of the start bit.
bitcount- number of bits to set.

Definition at line 2835 of file bmfunc.h.

References bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::gap_add_to_bitset().

◆ set_bit()

BMFORCEINLINE void bm::set_bit ( unsigned *  dest,
unsigned  bitpos 
)

◆ sub_bit_block()

void bm::sub_bit_block ( unsigned *  dest,
unsigned  bitpos,
unsigned  bitcount 
)
inline

SUB (AND NOT) bit interval to 1 in the bitblock.

Parameters
dest- Bitset buffer.
bitpos- Offset of the start bit.
bitcount- number of bits to set.

Definition at line 2882 of file bmfunc.h.

References bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::gap_and_to_bitset(), and bm::gap_sub_to_bitset().

◆ test_bit()

BMFORCEINLINE unsigned bm::test_bit ( const unsigned *  block,
unsigned  bitpos 
)

Test 1 bit in a block.

Definition at line 2817 of file bmfunc.h.

References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.

◆ tmatrix_distance()

template<typename T , unsigned BPC, unsigned BPS>
void bm::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.

Parameters
tmatrix- bit-block transposition matrix (bit-plains)
distance- pairwise NxN Humming distance matrix (diagonal is popcnt)

Definition at line 315 of file bmtrans.h.

References bm::bit_block_count(), and BM_INCWORD_BITCOUNT.

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

◆ update_block_digest0()

bm::id64_t bm::update_block_digest0 ( const bm::word_t *const  block,
bm::id64_t  digest 
)
inline

Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas)

Parameters
block- bit block
digest- start digest
Returns
digest bit-mask (0 means all block is empty)

Definition at line 743 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::calc_block_digest0(), bm::set_block_digest_wave_size, VECT_IS_DIGEST_ZERO, and bm::word_bitcount64().

Referenced by bm::bvector<>::combine_operation(), bm::aggregator< bvector_type >::process_gap_blocks_and(), bm::aggregator< bvector_type >::process_gap_blocks_sub(), and bm::aggregator< bvector_type >::process_shift_right_and().

◆ widx_to_digest_mask()

BMFORCEINLINE bm::id64_t bm::widx_to_digest_mask ( unsigned  w_idx)

Compute digest mask for word address in block.

Returns
digest bit-mask

Definition at line 619 of file bmfunc.h.

References BMFORCEINLINE, and bm::set_block_digest_wave_size.

◆ word_bitcount()

BMFORCEINLINE bm::id_t bm::word_bitcount ( bm::id_t  w)

◆ word_bitcount64()

BMFORCEINLINE unsigned bm::word_bitcount64 ( bm::id64_t  x)

◆ wordcmp()

template<typename T >
int bm::wordcmp ( a,
b 
)

Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes.

Parameters
a- First word.
b- Second word.
Returns
<0 - less, =0 - equal, >0 - greater.

Definition at line 994 of file bmfunc.h.

◆ wordcmp0()

template<typename T >
int bm::wordcmp0 ( w1,
w2 
)

Lexicographical comparison of two words as bit strings (reference) Auxiliary implementation for testing and reference purposes.

Parameters
w1- First word.
w2- Second word.
Returns
<0 - less, =0 - equal, >0 - greater.

Definition at line 965 of file bmfunc.h.

◆ xor_bit_block()

void bm::xor_bit_block ( unsigned *  dest,
unsigned  bitpos,
unsigned  bitcount 
)
inline

XOR bit interval to 1 in the bitblock.

Parameters
dest- Bitset buffer.
bitpos- Offset of the start bit.
bitcount- number of bits to set.

Definition at line 2929 of file bmfunc.h.

References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::gap_xor_to_bitset().