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::block_waves_xor_descr
 Structure to compute XOR gap-count profile by sub-block waves. 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

BMFORCEINLINE bm::id_t bm::word_bitcount (bm::id_t w) BMNOEXCEPT
 
BMFORCEINLINE unsigned bm::word_bitcount64 (bm::id64_t x) BMNOEXCEPT
 
unsigned bm::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 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) BMNOEXCEPT
 Unpacks word into list of ON bit indexes. More...
 
template<typename T , typename B >
unsigned bm::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 bm::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 bm::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 bm::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 bm::bitscan_bsf (unsigned w, B *bits) BMNOEXCEPT
 Unpacks word into list of ON bits (BSF/__builtin_ctz) More...
 
template<typename B >
unsigned short bm::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 bm::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 bm::bitscan (V w, B *bits) BMNOEXCEPT
 Templated Bitscan with dynamic dispatch for best type. More...
 
unsigned bm::word_select64_linear (bm::id64_t w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned bm::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 bm::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 bm::word_select32_bitscan_popcnt (unsigned w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned bm::word_select32_bitscan_tz (unsigned w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned bm::word_select64 (bm::id64_t w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
unsigned bm::word_select32 (unsigned w, unsigned rank) BMNOEXCEPT
 word find index of the rank-th bit set by bit-testing More...
 
BMFORCEINLINE bm::id64_t bm::widx_to_digest_mask (unsigned w_idx) BMNOEXCEPT
 Compute digest mask for word address in block. More...
 
BMFORCEINLINE bm::id64_t bm::digest_mask (unsigned from, unsigned to) BMNOEXCEPT
 Compute digest mask for [from..to] positions. More...
 
bool bm::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 bm::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 bm::calc_block_digest0 (const bm::word_t *const block) BMNOEXCEPT
 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) BMNOEXCEPT
 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) BMNOEXCEPT
 Returns "true" if all bits in the block are 0. More...
 
BMFORCEINLINE void bm::set_bit (unsigned *dest, unsigned bitpos) BMNOEXCEPT
 Set 1 bit in a block. More...
 
BMFORCEINLINE void bm::clear_bit (unsigned *dest, unsigned bitpos) BMNOEXCEPT
 Set 1 bit in a block. More...
 
BMFORCEINLINE unsigned bm::test_bit (const unsigned *block, unsigned bitpos) BMNOEXCEPT
 Test 1 bit in a block. More...
 
void bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
 Sets bits to 1 in the bitblock. More...
 
void bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
 SUB (AND NOT) bit interval to 1 in the bitblock. More...
 
void bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
 XOR bit interval to 1 in the bitblock. More...
 
void bm::bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value) BMNOEXCEPT
 Bitblock memset operation. More...
 
template<typename T >
int bm::bitcmp (const T *buf1, const T *buf2, unsigned len) BMNOEXCEPT
 Lexicographical comparison of BIT buffers. More...
 
bool bm::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...
 
BMFORCEINLINE unsigned bm::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 bm::bit_block_count (const bm::word_t *block) BMNOEXCEPT
 Bitcount for bit block. More...
 
bm::id_t bm::bit_block_count (const bm::word_t *BMRESTRICT const block, bm::id64_t digest) BMNOEXCEPT
 Bitcount for bit block. More...
 
bm::id_t bm::bit_count_change (bm::word_t w) BMNOEXCEPT
 
unsigned bm::bit_block_calc_change (const bm::word_t *block) BMNOEXCEPT
 
bool bm::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 bm::bit_block_calc_count_range (const bm::word_t *block, bm::word_t left, bm::word_t right) BMNOEXCEPT
 
bm::id_t bm::bit_block_calc_count_to (const bm::word_t *block, bm::word_t right) BMNOEXCEPT
 
void bm::bit_block_rotate_left_1 (bm::word_t *block) BMNOEXCEPT
 
void bm::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 bm::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 bm::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 bm::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 bm::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 bm::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 bm::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 bm::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 bm::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 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) BMNOEXCEPT
 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) BMNOEXCEPT
 Right bit-shift bitblock by 1 bit (reference) + AND. More...
 
bm::id_t bm::bit_block_any_range (const bm::word_t *const BMRESTRICT block, bm::word_t left, bm::word_t right) BMNOEXCEPT
 
template<typename T >
void bm::bit_invert (T *start) BMNOEXCEPT
 
bool bm::is_bits_one (const bm::wordop_t *start) BMNOEXCEPT
 Returns "true" if all bits in the block are 1. More...
 
bool bm::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...
 
bool bm::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 bm::bit_block_find_prev (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Reverse search for the previous 1 bit. More...
 
void bm::bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Bitblock copy operation. More...
 
void bm::bit_block_stream (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 Bitblock copy/stream operation. More...
 
bm::id64_t bm::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 bm::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 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) BMNOEXCEPT
 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) BMNOEXCEPT
 digest based bit-block AND More...
 
unsigned bm::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 bm::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 bm::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 bm::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 bm::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 bm::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 bm::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 bm::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_tbm::bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 bitblock AND operation. More...
 
bm::id_t bm::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 bm::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 bm::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 bm::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 bm::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 bm::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 bm::bit_operation_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
 Performs bitblock OR operation test. More...
 
bool bm::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 bm::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 bm::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 bm::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 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) BMNOEXCEPT
 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) BMNOEXCEPT
 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) BMNOEXCEPT
 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) BMNOEXCEPT
 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) BMNOEXCEPT
 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) BMNOEXCEPT
 bitblock SUB operation. More...
 
bm::id64_t bm::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 bm::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_tbm::bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
 bitblock XOR operation. More...
 
bm::id_t bm::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 bm::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 bm::bit_count_nonzero_size (const T *blk, unsigned data_size) BMNOEXCEPT
 Inspects block for full zero words. More...
 
unsigned bm::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 bm::bit_find_last (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT last) BMNOEXCEPT
 BIT block find the last set bit (backward search) More...
 
bool bm::bit_find_first (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT pos) BMNOEXCEPT
 BIT block find the first set bit. More...
 
unsigned bm::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 bm::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 bm::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...
 
bm::set_representation bm::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 bm::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...
 
unsigned short bm::bitscan_wave (const bm::word_t *BMRESTRICT w_ptr, unsigned char *BMRESTRICT bits) BMNOEXCEPT
 Unpacks word wave (Nx 32-bit words) More...
 
void bm::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 bm::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...
 
void bm::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
 
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 visitor functor for each 1 bit group More...
 
template<typename Func , typename SIZE_TYPE >
void bm::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 , 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...
 
BMFORCEINLINE unsigned bm::count_leading_zeros (unsigned x) BMNOEXCEPT
 Portable LZCNT with (uses minimal LUT) More...
 
BMFORCEINLINE unsigned bm::count_trailing_zeros (unsigned v) BMNOEXCEPT
 Portable TZCNT with (uses 37-LUT) More...
 
template<class T >
unsigned bm::bit_scan_reverse (T value) BMNOEXCEPT
 

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 8379 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 7872 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 6536 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, BLOCK_IDX >::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 6575 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 6697 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 6809 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 6760 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 *const BMRESTRICT  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 5703 of file bmfunc.h.

References BM_ASSERT, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_word_mask, and bm::set_word_shift.

◆ 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 5019 of file bmfunc.h.

References bm::bit_block_change32(), bm::set_block_size, and VECT_BLOCK_CHANGE.

◆ 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 5122 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, bm::mask_l_u32(), bm::mask_r_u32(), 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 5192 of file bmfunc.h.

References BM_ASSERT, BM_AVX2_BIT_COUNT, BM_AVX2_POPCNT_PROLOG, bm::mask_l_u32(), bm::word_bitcount(), and bm::word_bitcount64().

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

◆ bit_block_convert_to_arr()

template<typename T >
unsigned bm::bit_block_convert_to_arr ( T *BMRESTRICT  dest,
const unsigned *BMRESTRICT  src,
bool  inverted 
)

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

Returns
destination size as a result of block decoding

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

Returns
destination size as a result of block decoding

Definition at line 8422 of file bmfunc.h.

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

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_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 *BMRESTRICT 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 4853 of file bmfunc.h.

References bm::bitcount64_4way(), BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_BIT_COUNT_DIGEST, bm::word_bitcount(), 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 5550 of file bmfunc.h.

References bm::bit_block_shift_l1_unr(), BM_ASSERT, bm::mask_r_u32(), 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 *BMRESTRICT  block,
unsigned  nbit,
unsigned *BMRESTRICT  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 8059 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_find_interval_end()

bool bm::bit_block_find_interval_end ( const bm::word_t *BMRESTRICT  block,
unsigned  nbit,
unsigned *BMRESTRICT  pos 
)
inline

Searches for the last 1 bit in the 111 interval of a BIT block.

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

Definition at line 5893 of file bmfunc.h.

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

Referenced by bm::block_find_interval_end().

◆ bit_block_find_interval_start()

bool bm::bit_block_find_interval_start ( const bm::word_t *BMRESTRICT  block,
unsigned  nbit,
unsigned *BMRESTRICT  pos 
)
inline

Searches for the first 1 bit in the 111 interval of a BIT block.

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

Definition at line 5989 of file bmfunc.h.

References bm::bit_scan_reverse32(), BM_ASSERT, bm::mask_l_u32(), bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::block_find_interval_start().

◆ bit_block_find_prev()

bool bm::bit_block_find_prev ( const bm::word_t *BMRESTRICT  block,
unsigned  nbit,
unsigned *BMRESTRICT  pos 
)
inline

Reverse search for the previous 1 bit.

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

Definition at line 6053 of file bmfunc.h.

References bm::bit_scan_reverse32(), BM_ASSERT, bm::mask_l_u32(), bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::block_find_reverse().

◆ bit_block_gather_scatter() [1/2]

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

bit index to word gather-scatter algorithm (SIMD)

Definition at line 9073 of file bmfunc.h.

References bm::avx2_bit_block_gather_scatter(), BM_ASSERT, and bm::sse4_bit_block_gather_scatter().

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

◆ bit_block_gather_scatter() [2/2]

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

bit index to word gather-scatter algorithm

Definition at line 9106 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 *BMRESTRICT  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 5301 of file bmfunc.h.

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

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

◆ bit_block_is_all_one_range()

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

Check if all bits are 1 in [left, right] range

Definition at line 5033 of file bmfunc.h.

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

Referenced by bm::block_is_all_one_range(), and bm::block_is_interval().

◆ 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 7345 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< BV, bm::decoder >::decode_bit_block(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_OR(), bm::aggregator< bvector_type >::process_bit_blocks_or(), and bm::deserializer< BV, bm::decoder >::xor_decode().

◆ 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 7382 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 7462 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
src2- source1, etc
src3- source1, etc
src4- source1, etc
Returns
1 if produced block of ALL ones

Definition at line 7506 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 7040 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 6992 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 5249 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 5265 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

Bitblock memset operation.

Parameters
dst- destination block.
value- value to set.

Definition at line 4243 of file bmfunc.h.

References bm::set_block_size, and VECT_SET_BLOCK.

Referenced by bm::bvector<>::combine_operation(), bm::aggregator< bvector_type >::combine_shift_right_and(), bm::deserializer< BV, bm::decoder >::decode_arrbit(), bm::deserializer< BV, bm::decoder >::decode_bit_block(), bm::deserializer< BV, bm::decoder >::decode_block_bit_interval(), bm::gap_convert_to_bitset(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_arr_bit(), 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_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_SUB(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_XOR(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_inv_arr(), bm::aggregator< bvector_type >::process_bit_blocks_or(), bm::aggregator< bvector_type >::process_shift_right_and(), bm::deseriaizer_base< bm::decoder, BV::block_idx_type >::read_0runs_block(), bm::deseriaizer_base< bm::decoder, BV::block_idx_type >::read_bic_arr_inv(), bm::random_subset< BV >::sample(), and bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::transpose().

◆ 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 5452 of file bmfunc.h.

References BM_ASSERT, and bm::set_block_size.

◆ 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 5527 of file bmfunc.h.

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

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

◆ bit_block_shift_l1_unr_min()

bool bm::bit_block_shift_l1_unr_min ( bm::word_t *BMRESTRICT  block,
bm::word_t *BMRESTRICT  empty_acc,
unsigned  co_flag 
)
inline

Left bit-shift bitblock by 1 bit (minimum unroll)

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 5483 of file bmfunc.h.

References bm::set_block_size.

Referenced by bm::bit_block_shift_l1_unr().

◆ bit_block_shift_r1()

bool bm::bit_block_shift_r1 ( bm::word_t *BMRESTRICT  block,
bm::word_t *BMRESTRICT  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 5350 of file bmfunc.h.

References BM_ASSERT, and bm::set_block_size.

Referenced by bm::bit_block_shift_r1_unr_min().

◆ 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 5606 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 5678 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 *BMRESTRICT  block,
bm::word_t *BMRESTRICT  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 5427 of file bmfunc.h.

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

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

◆ bit_block_shift_r1_unr_min()

bool bm::bit_block_shift_r1_unr_min ( bm::word_t *BMRESTRICT  block,
bm::word_t *BMRESTRICT  empty_acc,
bm::id64_t  co_flag 
)
inline

Right bit-shift bitblock by 1 bit (minimum unroll)

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 5381 of file bmfunc.h.

References bm::bit_block_shift_r1(), BMRESTRICT, and bm::set_block_size.

Referenced by bm::bit_block_shift_r1_unr().

◆ 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 6513 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 7615 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, BLOCK_IDX >::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 7651 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 1
src2- source block 2
digest- known digest of dst block
Returns
new digest

Definition at line 7711 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 6963 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 6915 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

◆ 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 7421 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 6888 of file bmfunc.h.

References BMRESTRICT, and bm::set_block_size.

Referenced by bm::bit_operation_xor_any().

◆ bit_block_xor_change32()

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

Function calculates basic complexity statistics on XOR product of two blocks (b1 XOR b2)

Definition at line 51 of file bmxor.h.

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

Referenced by bm::bit_block_xor_change().

◆ 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 6839 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_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 4928 of file bmfunc.h.

References bm::word_bitcount().

◆ bit_count_min_unroll()

BMFORCEINLINE unsigned bm::bit_count_min_unroll ( const bm::word_t *BMRESTRICT  block,
const bm::word_t *BMRESTRICT  block_end 
)

Bitcount for bit block without agressive unrolling.

Definition at line 4779 of file bmfunc.h.

References bm::bitcount64_4way(), BM_ASSERT, BMRESTRICT, and bm::word_bitcount().

Referenced by bm::bit_block_count(), and bm::compute_complexity_descr().

◆ 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 8003 of file bmfunc.h.

References BM_ASSERT.

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

◆ bit_find_first() [1/2]

bool bm::bit_find_first ( const bm::word_t *BMRESTRICT  block,
unsigned *BMRESTRICT  pos 
)
inline

BIT block find the first set bit.

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

Definition at line 8144 of file bmfunc.h.

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

Referenced by bm::block_find_first_diff(), 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 *BMRESTRICT  block,
unsigned *BMRESTRICT  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 8179 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_diff()

bool bm::bit_find_first_diff ( const bm::word_t *BMRESTRICT  blk1,
const bm::word_t *BMRESTRICT  blk2,
unsigned *BMRESTRICT  pos 
)
inline

Find first bit which is different between two bit-blocks.

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

Definition at line 4508 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, BMRESTRICT, bm::count_trailing_zeros_u64(), bm::set_block_size, and VECT_BIT_FIND_DIFF.

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

◆ bit_find_first_if_1()

bool bm::bit_find_first_if_1 ( const bm::word_t *BMRESTRICT  block,
unsigned *BMRESTRICT  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 8217 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 *BMRESTRICT  block,
unsigned *BMRESTRICT  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
true if found

Definition at line 8110 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 8274 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(), bm::word_select32(), 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 375 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 305 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 611 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 629 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 7072 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 7160 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 7136 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, BLOCK_IDX >::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 7555 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 7312 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 7275 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, BLOCK_IDX >::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 7778 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 7240 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 7222 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 7907 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 7977 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
src2- second bit block
Returns
bitcount value

Definition at line 7945 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, BLOCK_IDX >::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 4483 of file bmfunc.h.

References BM_ASSERT.

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

◆ bitcount64_4way()

unsigned bm::bitcount64_4way ( bm::id64_t  x,
bm::id64_t  y,
bm::id64_t  u,
bm::id64_t  v 
)
inline

◆ bitscan()

template<typename V , typename B >
unsigned short bm::bitscan ( w,
B *  bits 
)

◆ bitscan_bsf()

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

Unpacks word into list of ON bits (BSF/__builtin_ctz)

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

Definition at line 713 of file bmfunc.h.

References bm::count_trailing_zeros_u32().

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

◆ bitscan_bsf64()

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

Unpacks word into list of ON bits (BSF/__builtin_ctz)

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

Definition at line 746 of file bmfunc.h.

References bm::count_trailing_zeros_u64().

Referenced by bm::bitscan().

◆ 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 648 of file bmfunc.h.

References bm::word_bitcount().

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

◆ 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 670 of file bmfunc.h.

References bm::word_bitcount().

◆ bitscan_popcnt64() [1/2]

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
Returns
number of bits in the list

Definition at line 691 of file bmfunc.h.

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

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

◆ bitscan_popcnt64() [2/2]

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

Unpacks 64-bit 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 768 of file bmfunc.h.

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

◆ bitscan_wave()

unsigned short bm::bitscan_wave ( const bm::word_t *BMRESTRICT  w_ptr,
unsigned char *BMRESTRICT  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 9029 of file bmfunc.h.

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

Referenced by bm::for_each_bit_blk(), bm::bvector< Alloc >::enumerator::go_first(), 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 1085 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

◆ 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 1069 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()

BMFORCEINLINE unsigned bm::count_leading_zeros ( unsigned  x)

Portable LZCNT with (uses minimal LUT)

Definition at line 171 of file bmutil.h.

References BMFORCEINLINE.

Referenced by bm::count_leading_zeros_u32().

◆ count_trailing_zeros()

BMFORCEINLINE unsigned bm::count_trailing_zeros ( unsigned  v)

Portable TZCNT with (uses 37-LUT)

Definition at line 187 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 1040 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, 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() [1/2]

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 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 1532 of file bmalgo_impl.h.

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

Referenced by bm::for_each_bit_block_range(), and bm::for_each_bit_range_no_check().

◆ for_each_bit_blk() [2/2]

template<typename Func , typename SIZE_TYPE >
void bm::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

Parameters
block- bit block buffer pointer
offset- global block offset (number of bits)
left- bit addredd in block from [from..to]
right- bit addredd in block to [from..to]
bit_functor- functor must support .add_bits(offset, bits_ptr, size)

Definition at line 1569 of file bmalgo_impl.h.

References bm::bits_in_block, bm::bitscan(), bm::bitscan_wave(), BM_ASSERT, IS_FULL_BLOCK, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_bitscan_wave_size, bm::set_word_mask, and bm::set_word_shift.

◆ 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 5797 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 3570 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 3617 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 3552 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 1157 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 1012 of file bmfunc.h.

References 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)

◆ word_select32()

unsigned bm::word_select32 ( unsigned  w,
unsigned  rank 
)
inline

word find index of the rank-th bit set by bit-testing

Parameters
w- 32-bit work to search
rank- rank to select (should be > 0)
Returns
selected value (inxed of bit set)

Definition at line 980 of file bmfunc.h.

References BMFORCEINLINE, bm::word_select32_bitscan_popcnt(), and bm::word_select32_bitscan_tz().

Referenced by bm::bit_find_rank().

◆ word_select32_bitscan_popcnt()

unsigned bm::word_select32_bitscan_popcnt ( unsigned  w,
unsigned  rank 
)
inline

word find index of the rank-th bit set by bit-testing

Parameters
w- 32-bit work to search
rank- rank to select (should be > 0)
Returns
selected value (inxed of bit set)

Definition at line 898 of file bmfunc.h.

References BM_ASSERT, and bm::word_bitcount().

Referenced by bm::word_select32().

◆ word_select32_bitscan_tz()

unsigned bm::word_select32_bitscan_tz ( unsigned  w,
unsigned  rank 
)
inline

word find index of the rank-th bit set by bit-testing

Parameters
w- 32-bit work to search
rank- rank to select (should be > 0)
Returns
selected value (inxed of bit set)

Definition at line 927 of file bmfunc.h.

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

Referenced by bm::word_select32().

◆ word_select64()

unsigned bm::word_select64 ( bm::id64_t  w,
unsigned  rank 
)
inline

word find index of the rank-th bit set by bit-testing

Parameters
w- 64-bit work to search
rank- rank to select (should be > 0)
Returns
selected value (inxed of bit set)

Definition at line 953 of file bmfunc.h.

References bm::word_select64_bitscan_popcnt(), and bm::word_select64_bitscan_tz().

Referenced by bm::bit_find_rank().

◆ word_select64_bitscan_popcnt()

unsigned bm::word_select64_bitscan_popcnt ( bm::id64_t  w,
unsigned  rank 
)
inline

word find index of the rank-th bit set by bit-testing

Parameters
w- 64-bit work to search
rank- rank to select (should be > 0)
Returns
selected value (inxed of bit set)

Definition at line 840 of file bmfunc.h.

References BM_ASSERT, and bm::word_bitcount64().

Referenced by bm::word_select64().

◆ word_select64_bitscan_tz()

unsigned bm::word_select64_bitscan_tz ( bm::id64_t  w,
unsigned  rank 
)
inline

word find index of the rank-th bit set by bit-testing

Parameters
w- 64-bit work to search
rank- rank to select (should be > 0)
Returns
selected value (inxed of bit set)

Definition at line 869 of file bmfunc.h.

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

Referenced by bm::word_select64().

◆ word_select64_linear()

unsigned bm::word_select64_linear ( bm::id64_t  w,
unsigned  rank 
)
inline

word find index of the rank-th bit set by bit-testing

Parameters
w- 64-bit work to search
rank- rank to select (should be > 0)
Returns
selected value (inxed of bit set)

Definition at line 814 of file bmfunc.h.

References BM_ASSERT.

◆ 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 1408 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 1379 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 3664 of file bmfunc.h.

References bm::mask_l_u32(), bm::mask_r_u32(), bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::gap_xor_to_bitset().