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...

## Functions

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.
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.
template<typename T, typename B>
unsigned | bm::bit_list (T w, B *bits) BMNOEXCEPT
| Unpacks word into list of ON bit indexes.
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).
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.
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.
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.
template<typename B>
unsigned short | bm::bitscan_bsf (unsigned w, B *bits) BMNOEXCEPT
| Unpacks word into list of ON bits (BSF/__builtin_ctz).
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).
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.
template<typename V, typename B>
unsigned short | bm::bitscan (V w, B *bits) BMNOEXCEPT
| Templated Bitscan with dynamic dispatch for best type.
unsigned | bm::word_select64_linear (bm::id64_t w, unsigned rank) BMNOEXCEPT
| word find index of the rank-th bit set by bit-testing
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
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
unsigned | bm::word_select32_bitscan_popcnt (unsigned w, unsigned rank) BMNOEXCEPT
| word find index of the rank-th bit set by bit-testing
unsigned | bm::word_select32_bitscan_tz (unsigned w, unsigned rank) BMNOEXCEPT
| word find index of the rank-th bit set by bit-testing
unsigned | bm::word_select64 (bm::id64_t w, unsigned rank) BMNOEXCEPT
| word find index of the rank-th bit set by bit-testing
unsigned | bm::word_select32 (unsigned w, unsigned rank) BMNOEXCEPT
| word find index of the rank-th bit set by bit-testing
BMFORCEINLINE bm::id64_t | bm::widx_to_digest_mask (unsigned w_idx) BMNOEXCEPT
| Compute digest mask for word address in block.
BMFORCEINLINE bm::id64_t | bm::digest_mask (unsigned from, unsigned to) BMNOEXCEPT
| Compute digest mask for [from..to] positions.
BMFORCEINLINE 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
void | bm::block_init_digest0 (bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT
| Init block with 000111000 pattren based on digest.
bm::id64_t | bm::calc_block_digest0 (const bm::word_t *const block) BMNOEXCEPT
| Compute digest for 64 non-zero areas.
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).
void | bm::block_compact_by_digest (bm::word_t *t_block, const bm::word_t *block, bm::id64_t digest, bool zero_tail) BMNOEXCEPT
| Compact sub-blocks by digest (rank compaction).
void | bm::block_expand_by_digest (bm::word_t *t_block, const bm::word_t *block, bm::id64_t digest, bool zero_subs) BMNOEXCEPT
| expand sub-blocks by digest (rank expansion)
template<typename T>
int | bm::wordcmp0 (T w1, T w2) BMNOEXCEPT
| Lexicographical comparison of two words as bit strings (reference) Auxiliary implementation for testing and reference purposes.
template<typename T>
int | bm::wordcmp (T a, T b) BMNOEXCEPT
| Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes.
bool | bm::bit_is_all_zero (const bm::word_t *BMRESTRICT start) BMNOEXCEPT
| Returns "true" if all bits in the block are 0.
BMFORCEINLINE void | bm::set_bit (unsigned *dest, unsigned bitpos) BMNOEXCEPT
| Set 1 bit in a block.
BMFORCEINLINE void | bm::clear_bit (unsigned *dest, unsigned bitpos) BMNOEXCEPT
| Set 1 bit in a block.
BMFORCEINLINE unsigned | bm::test_bit (const unsigned *block, unsigned bitpos) BMNOEXCEPT
| Test 1 bit in a block.
void | bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
| Sets bits to 1 in the bitblock.
void | bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
| SUB (AND NOT) bit interval to 1 in the bitblock.
void | bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
| XOR bit interval to 1 in the bitblock.
void | bm::bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value) BMNOEXCEPT
| Bitblock memset operation.
template<typename T>
int | bm::bitcmp (const T *buf1, const T *buf2, unsigned len) BMNOEXCEPT
| Lexicographical comparison of BIT buffers.
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.
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.
bm::id_t | bm::bit_block_count (const bm::word_t *block) BMNOEXCEPT
| Bitcount for bit block.
bm::id_t | bm::bit_block_count (const bm::word_t *BMRESTRICT const block, bm::id64_t digest) BMNOEXCEPT
| Bitcount for bit block.
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
template<bool LWA = false, bool RWA = false>
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.
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
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).
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).
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).
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).
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).
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).
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
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.
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.
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.
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.
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.
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.
void | bm::bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
| Bitblock copy operation.
void | bm::bit_block_copy_unalign (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
| Bitblock copy operation (unaligned src).
void | bm::bit_block_stream (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
| Bitblock copy/stream operation.
void | bm::bit_block_stream_unalign (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
| Bitblock copy/stream operation (unaligned src).
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.
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
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
bm::id64_t | bm::bit_block_and_3way (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
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
bm::id64_t | bm::bit_block_init_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 (0 elements of digest will be zeroed)
bm::id64_t | bm::bit_block_and_or_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 - OR
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.
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.
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.
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.
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.
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.
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.
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.
bm::word_t * | bm::bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
| bitblock AND operation.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
bm::word_t * | bm::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.
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.
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
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)
bm::id64_t | bm::bit_block_sub_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 SUB 5-way
bm::id64_t | bm::bit_block_sub_3way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src0, const bm::word_t *BMRESTRICT src1, bm::id64_t digest) BMNOEXCEPT
| digest based bit-block SUB 3-way
bm::word_t * | bm::bit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
| bitblock SUB operation.
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.
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.
bm::word_t * | bm::bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
| bitblock XOR operation.
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.
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.
template<class T>
unsigned | bm::bit_count_nonzero_size (const T *blk, unsigned data_size) BMNOEXCEPT
| Inspects block for full zero words.
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.
unsigned | bm::bit_find_last (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT last) BMNOEXCEPT
| BIT block find the last set bit (backward search).
bool | bm::bit_find_first (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT pos) BMNOEXCEPT
| BIT block find the first set bit.
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.
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.
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.
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.
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.
unsigned short | bm::bitscan_wave (const bm::word_t *BMRESTRICT w_ptr, unsigned char *BMRESTRICT bits) BMNOEXCEPT
| Unpacks word wave (Nx 32-bit words).
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)
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
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
void | bm::bit_block_xor_change64 (const bm::word_t *BMRESTRICT s_block, const bm::word_t *BMRESTRICT ref_block, unsigned size, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc) BMNOEXCEPT
template<typename Func, typename SIZE_TYPE>
int | 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
template<typename Func, typename SIZE_TYPE>
int | 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
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 planes(rows) of the transposed bit block.
template<typename T, unsigned BPC, unsigned BPS>
void | bm::bit_iblock_make_pcv (const unsigned distance[BPC][BPC], unsigned char *pc_vector)
| !< ibpc limiter
BMFORCEINLINE unsigned | bm::count_leading_zeros (unsigned x) BMNOEXCEPT
| Portable LZCNT with (uses minimal LUT).
BMFORCEINLINE unsigned | bm::count_trailing_zeros (unsigned v) BMNOEXCEPT
| Portable TZCNT with (uses 37-LUT).
template<class T>
unsigned | bm::bit_scan_reverse (T value) BMNOEXCEPT
BMFORCEINLINE bm::id_t | bm::word_bitcount (bm::id_t w) BMNOEXCEPT
BMFORCEINLINE unsigned | bm::word_bitcount64 (bm::id64_t x) BMNOEXCEPT

## Detailed Description

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

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

References BMNOEXCEPT, set_array0, set_array1, set_bitset, and set_gap.

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

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

References all_bits_mask, BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_ANDNOT_ARR_2_MASK.

Referenced by bm::bvector< Alloc >::combine_operation_block_sub(), and bm::bvector< Alloc >::combine_operation_with_block().

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

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_AND_BLOCK.

Referenced by bit_operation_and(), bm::bvector< Alloc >::combine_operation_block_and(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_AND(), and bm::aggregator< BV >::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 6895 of file bmfunc.h.

References BM_ASSERT, bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_AND_DIGEST, and 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 7076 of file bmfunc.h.

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

Referenced by bm::bvector< Alloc >::combine_operation_block_and(), and bm::aggregator< BV >::process_bit_blocks_and().

## bit_block_and_3way()

bm::id64_t bm::bit_block_and_3way | ( | 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 | - src/destination block.
  src1 | - source block.
  src2 | - source block.
  digest | - known initial digest

Returns
  new digest

Definition at line 7011 of file bmfunc.h.

References BM_ASSERT, bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_AND_DIGEST_3WAY, and word_bitcount64().

Referenced by bm::aggregator< BV >::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

digest based bit-block AND 5-way

Returns
  new digest

Definition at line 6949 of file bmfunc.h.

References BM_ASSERT, bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_AND_DIGEST_5WAY, and word_bitcount64().

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

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

References BMNOEXCEPT, and set_block_size.

Referenced by 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 7274 of file bmfunc.h.

References bitcount64_4way(), BMNOEXCEPT, BMRESTRICT, set_block_size, VECT_BITCOUNT_AND, and word_bitcount().

Referenced by bit_operation_and_count().

## bit_block_and_or_2way()

bm::id64_t bm::bit_block_and_or_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 - OR

dst =dst OR (src1 AND src2)

Parameters

  dst | - destination block.
  src1 | - source block.
  src2 | - source block.
  digest | - known initial digest

Returns
  new digest (for the AND operation)

Definition at line 7210 of file bmfunc.h.

References BM_ASSERT, bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_AND_OR_DIGEST_2WAY, and word_bitcount64().

Referenced by bm::bvector< Alloc >::combine_operation_block_and_or().

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

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, mask_l_u32(), mask_r_u32(), set_word_mask, and 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 5283 of file bmfunc.h.

References bit_block_change32(), bit_block_change64(), BMNOEXCEPT, set_block_size, and VECT_BLOCK_CHANGE.

## bit_block_calc_count_range()

template<bool LWA = false, bool RWA = false>

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

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.

LWA - left word aligned RWA - right word aligned

Definition at line 5390 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, gap_max_bits, mask_l_u32(), mask_r_u32(), set_word_mask, set_word_shift, and word_bitcount().

Referenced by bm::bvector< Alloc >::build_rs_index(), bm::bvector< Alloc >::count_range_no_check(), gap_bitset_and_count(), gap_bitset_or_count(), gap_bitset_sub_count(), and 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 5476 of file bmfunc.h.

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

Referenced by bm::bvector< Alloc >::build_rs_index(), and bm::bvector< Alloc >::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 9064 of file bmfunc.h.

References bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, gap_max_bits, and word_bitcount64().

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

## bit_block_copy()

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

inline

Bitblock copy operation.

Parameters

  dst | [out] - destination block.
  src | [in] - source block.

Definition at line 6777 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_COPY_BLOCK.

Referenced by bm::bvector< Alloc >::combine_operation_block_and(), bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), bm::bvector< Alloc >::combine_operation_block_xor(), bm::bvector< Alloc >::combine_operation_with_block(), bm::aggregator< BV >::combine_shift_right_and(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_ASSIGN(), bm::aggregator< BV >::process_bit_blocks_and(), and bm::aggregator< BV >::process_bit_blocks_or().

## bit_block_copy_unalign()

void bm::bit_block_copy_unalign | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src )

inline

Bitblock copy operation (unaligned src).

Parameters

  dst | [out] - destination block.
  src | [in] - source block.

Definition at line 6795 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_COPY_BLOCK_UNALIGN.

Referenced by bit_import_u32().

## bit_block_count() [1/2]

bm::id_t bm::bit_block_count | ( | const bm::word_t * | block | ) |

inline

Bitcount for bit block.

Function calculates number of 1 bits in the given array of words. Make sure the addresses are aligned.

Definition at line 5051 of file bmfunc.h.

References bit_count_min_unroll(), BMNOEXCEPT, set_block_size, and VECT_BITCOUNT.

Referenced by bit_block_change_bc(), bit_operation_or_count(), bit_operation_sub_count(), bit_operation_xor_count(), bm::aggregator< BV >::combine_and_sub(), combine_count_operation_with_block(), bm::aggregator< BV >::combine_shift_right_and(), bm::serializer< BV >::find_bit_best_encoding(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_A(), and tmatrix_distance().

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

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

References bit_block_shift_l1_unr(), BM_ASSERT, BMNOEXCEPT, mask_r_u32(), set_block_mask, set_block_size, set_word_mask, and set_word_shift.

Referenced by bm::bvector< Alloc >::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 8657 of file bmfunc.h.

References bit_scan_forward32(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, set_block_size, set_word_mask, and set_word_shift.

Referenced by bm::bvector< Alloc >::check_or_next(), and bm::serializer< BV >::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 6177 of file bmfunc.h.

References bit_scan_forward32(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_max_bits, set_block_size, set_word_mask, and set_word_shift.

Referenced by 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 6273 of file bmfunc.h.

References bit_scan_reverse32(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, mask_l_u32(), set_word_mask, and set_word_shift.

Referenced by 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 6337 of file bmfunc.h.

References bit_scan_reverse32(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, mask_l_u32(), set_word_mask, and set_word_shift.

Referenced by block_find_reverse().

## bit_block_gather_scatter() [1/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 9713 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_mask, set_word_mask, and set_word_shift.

## bit_block_gather_scatter() [2/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 9679 of file bmfunc.h.

References avx2_bit_block_gather_scatter(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and sse4_bit_block_gather_scatter().

Referenced by bm::sparse_vector< Val, BV >::gather().

## bit_block_init_and_2way()

bm::id64_t bm::bit_block_init_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 (0 elements of digest will be zeroed)

dst = src1 AND src2

Parameters

  dst | - destination block.
  src1 | - source block.
  src2 | - source block.
  digest | - known initial digest

Returns
  new digest

Definition at line 7140 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_AND_DIGEST_2WAY, and VECT_BLOCK_SET_DIGEST.

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

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

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, mask_r_u32(), set_block_mask, set_block_size, set_word_mask, and set_word_shift.

Referenced by bm::bvector< Alloc >::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 5301 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_max_bits, mask_l_u32(), mask_r_u32(), set_word_mask, and set_word_shift.

Referenced by block_is_all_one_range(), and 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 7835 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_OR_BLOCK.

Referenced by bit_operation_or(), bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), bm::deserializer< BV, DEC >::decode_bit_block(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_OR(), bm::aggregator< BV >::process_bit_blocks_or(), and bm::deserializer< BV, DEC >::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 7872 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_OR_BLOCK_2WAY.

Referenced by bm::bvector< Alloc >::combine_operation_block_or().

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

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_OR_BLOCK_3WAY.

Referenced by bm::aggregator< BV >::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 7996 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_OR_BLOCK_5WAY.

Referenced by bm::aggregator< BV >::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 7545 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and set_block_size.

Referenced by 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 7498 of file bmfunc.h.

References bitcount64_4way(), BMNOEXCEPT, set_block_size, VECT_BITCOUNT_OR, and word_bitcount().

Referenced by 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 5533 of file bmfunc.h.

References BMNOEXCEPT, and 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 5549 of file bmfunc.h.

References BMNOEXCEPT, and 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 4456 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_SET_BLOCK.

Referenced by bm::bvector< Alloc >::combine_operation_block_xor(), bm::aggregator< BV >::combine_shift_right_and(), bm::deserializer< BV, DEC >::decode_arrbit(), bm::deserializer< BV, DEC >::decode_bit_block(), bm::deserializer< BV, DEC >::decode_block_bit_interval(), 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< BV >::process_bit_blocks_or(), bm::aggregator< BV >::process_shift_right_and(), bm::deseriaizer_base< DEC, BLOCK_IDX >::read_0runs_block(), bm::deseriaizer_base< DEC, BLOCK_IDX >::read_bic_arr_inv(), 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 5736 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and 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 5811 of file bmfunc.h.

References bit_block_shift_l1_unr_min(), BM_ASSERT, BMNOEXCEPT, and VECT_SHIFT_L1.

Referenced by bit_block_erase(), and bm::bvector< Alloc >::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 5767 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and set_block_size.

Referenced by 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 5634 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and set_block_size.

Referenced by 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 5890 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, set_block_size, and word_bitcount64().

Referenced by 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 5962 of file bmfunc.h.

References bit_block_shift_r1_and(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and VECT_SHIFT_R1_AND.

Referenced by bm::aggregator< BV >::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 5711 of file bmfunc.h.

References bit_block_shift_r1_unr_min(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and VECT_SHIFT_R1.

Referenced by bm::bvector< Alloc >::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 5665 of file bmfunc.h.

References bit_block_shift_r1(), BMNOEXCEPT, BMRESTRICT, and set_block_size.

Referenced by 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 6816 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_STREAM_BLOCK.

## bit_block_stream_unalign()

void bm::bit_block_stream_unalign | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src )

inline

Bitblock copy/stream operation (unaligned src).

Parameters

  dst | [out] - destination block.
  src | [in] - source block (unaligned address)

Definition at line 6834 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_STREAM_BLOCK_UNALIGN.

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

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_SUB_BLOCK.

Referenced by bit_operation_sub(), bm::bvector< Alloc >::combine_operation_block_sub(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_SUB(), and bm::aggregator< BV >::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 8141 of file bmfunc.h.

References BM_ASSERT, bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_SUB_DIGEST, and 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 8201 of file bmfunc.h.

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

Referenced by bm::bvector< Alloc >::combine_operation_block_sub().

## bit_block_sub_3way()

bm::id64_t bm::bit_block_sub_3way | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src0,
|  | const bm::word_t *BMRESTRICT | src1,
|  | bm::id64_t | digest )

inline

digest based bit-block SUB 3-way

Returns
  new digest

Definition at line 8316 of file bmfunc.h.

References BM_ASSERT, bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_SUB_DIGEST_3WAY, and word_bitcount64().

Referenced by bm::aggregator< BV >::process_bit_blocks_sub().

## bit_block_sub_5way()

bm::id64_t bm::bit_block_sub_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

digest based bit-block SUB 5-way

Returns
  new digest

Definition at line 8259 of file bmfunc.h.

References BM_ASSERT, bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_SUB_DIGEST_5WAY, and word_bitcount64().

Referenced by bm::aggregator< BV >::process_bit_blocks_sub().

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

References BMNOEXCEPT, BMRESTRICT, and set_block_size.

Referenced by 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 7424 of file bmfunc.h.

References bitcount64_4way(), BMNOEXCEPT, BMRESTRICT, set_block_size, VECT_BITCOUNT_SUB, and word_bitcount().

Referenced by 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 8434 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_XOR_BLOCK.

Referenced by bm::xor_scanner< BV >::apply_xor_match_vector(), bit_operation_xor(), bm::bvector< Alloc >::combine_operation_block_xor(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_XOR(), bm::xor_scanner< BV >::search_best_xor_mask(), bm::deserializer< BV, DEC >::xor_decode(), bm::deserializer< BV, DEC >::xor_decode_chain(), and bm::serializer< BV >::xor_tmp_product().

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

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_XOR_BLOCK_2WAY.

Referenced by bm::bvector< Alloc >::combine_operation_block_xor().

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

References BMNOEXCEPT, BMRESTRICT, and set_block_size.

Referenced by 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 (32-bit) calculates basic complexity statistics on XOR product of two blocks (b1 XOR b2)

Definition at line 96 of file bmxor.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and word_bitcount().

Referenced by bit_block_xor_change().

## bit_block_xor_change64()

void bm::bit_block_xor_change64 | ( | const bm::word_t *BMRESTRICT | s_block,
|  | const bm::word_t *BMRESTRICT | ref_block,
|  | unsigned | size,
|  | unsigned *BMRESTRICT | gc,
|  | unsigned *BMRESTRICT | bc )

inline

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

Definition at line 151 of file bmxor.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and word_bitcount64().

Referenced by 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 7350 of file bmfunc.h.

References bitcount64_4way(), BMNOEXCEPT, BMRESTRICT, set_block_size, VECT_BITCOUNT_XOR, and word_bitcount().

Referenced by 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 5145 of file bmfunc.h.

References BMNOEXCEPT, and 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 4996 of file bmfunc.h.

References bitcount64_4way(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and word_bitcount().

Referenced by bit_block_count(), and compute_s_block_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 8601 of file bmfunc.h.

References BM_ASSERT, and BMNOEXCEPT.

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

## bit_find_first() [1/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 8777 of file bmfunc.h.

References bit_scan_forward32(), BM_ASSERT, bmi_blsi_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, set_block_size, VECT_BIT_FIND_FIRST, and word_bitcount64().

## bit_find_first() [2/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 8742 of file bmfunc.h.

References bit_scan_forward32(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_BIT_FIND_FIRST.

Referenced by block_find_first_diff(), bm::bvector< Alloc >::check_or_next(), bm::bvector< Alloc >::find(), and bm::aggregator< BV >::find_first_and_sub().

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

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

Referenced by block_find_first_diff().

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

References bit_scan_forward32(), BM_ASSERT, bmi_blsi_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, word_bitcount(), and word_bitcount64().

Referenced by bm::aggregator< BV >::process_bit_blocks_and(), bm::aggregator< BV >::process_bit_blocks_sub(), bm::aggregator< BV >::process_gap_blocks_and(), and bm::aggregator< BV >::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 8708 of file bmfunc.h.

References bit_scan_reverse(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and set_block_size.

Referenced by bm::bvector< Alloc >::find_reverse(), and bm::bvector< Alloc >::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 8916 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, set_block_size, set_word_mask, set_word_shift, word_bitcount(), word_bitcount64(), word_select32(), and word_select64().

Referenced by block_find_rank().

## bit_for_each()

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.

Parameters

  w | - value
  func | - bit functor

Definition at line 359 of file bmfunc.h.

Referenced by bit_list().

## bit_for_each_4()

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.

Parameters

  w | - value
  func | - bit functor

Definition at line 289 of file bmfunc.h.

References BM_ASSERT.

Referenced by 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-planes

Parameters

  distance | - pairwise distance matrix

  pc_vector

  - OUT compression descriptor vector

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

Definition at line 379 of file bmtrans.h.

References BM_ASSERT, ibpc_all_one, ibpc_all_zero, ibpc_close, ibpc_equiv, and 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 | ) |

Function inverts block of bits

Definition at line 6057 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, IS_VALID_ADDR, set_block_size, and VECT_INVERT_BLOCK.

Referenced by bm::bvector< Alloc >::combine_operation_block_xor(), bm::deserializer< BV, DEC >::decode_bit_block(), bm::bvector< Alloc >::invert(), and bm::deseriaizer_base< DEC, BLOCK_IDX >::read_bic_arr_inv().

## bit_is_all_zero()

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

inline

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

Definition at line 1550 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_IS_ZERO_BLOCK.

Referenced by bit_operation_or_any(), bit_operation_sub_any(), bit_operation_xor_any(), block_any(), check_block_zero(), combine_any_operation_with_block(), bm::bvector< Alloc >::combine_operation_block_and(), bm::bvector< Alloc >::combine_operation_block_and(), bm::bvector< Alloc >::combine_operation_block_sub(), bm::aggregator< BV >::combine_shift_right_and(), bm::bvector< Alloc >::compare(), gap_bitset_or_any(), bm::aggregator< BV >::process_gap_blocks_and(), and bm::aggregator< BV >::process_gap_blocks_sub().

## bit_list()

template<typename T, typename B>

unsigned bm::bit_list | ( | T | 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 595 of file bmfunc.h.

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

Referenced by bm::str_sparse_vector< char, bm::bvector<>, 64 >::import_char_slice().

## bit_list_4()

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

Parameters

  w | - value
  bits | - pointer on the result array

Returns
  number of bits in the list

Definition at line 613 of file bmfunc.h.

References bit_for_each_4(), BMNOEXCEPT, 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 7578 of file bmfunc.h.

References bit_block_and(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, IS_EMPTY_BLOCK, IS_FULL_BLOCK, and IS_VALID_ADDR.

Referenced by bm::bvector< Alloc >::combine_operation_with_block().

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

References bit_block_and_any(), BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.

Referenced by 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 7626 of file bmfunc.h.

References bit_block_and_count(), BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.

Referenced by 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 8045 of file bmfunc.h.

References bit_block_or(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_FAKE_ADDR, IS_FULL_BLOCK, IS_VALID_ADDR, and set_block_size.

Referenced by bm::bvector< Alloc >::combine_operation_with_block().

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

References bit_block_or_any(), bit_is_all_zero(), BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.

Referenced by 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 7765 of file bmfunc.h.

References bit_block_count(), bit_block_or_count(), BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

Referenced by 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 8376 of file bmfunc.h.

References bit_block_sub(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, IS_FULL_BLOCK, and IS_VALID_ADDR.

Referenced by bm::bvector< Alloc >::combine_operation_block_sub(), and bm::bvector< Alloc >::combine_operation_with_block().

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

References bit_block_sub_any(), bit_is_all_zero(), BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

Referenced by 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

Performs bitblock SUB operation and calculates bitcount of the result.

Parameters

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

Returns
  bitcount value

Definition at line 7675 of file bmfunc.h.

References bit_block_count(), bit_block_sub_count(), BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

Referenced by bit_operation_sub_count_inv(), combine_count_operation_with_block(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_SUB_AB(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_SUB_BA().

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

References bit_operation_sub_count(), BMNOEXCEPT, and BMRESTRICT.

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

References bit_block_xor(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and IS_VALID_ADDR.

Referenced by bm::bvector< Alloc >::combine_operation_with_block().

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

References bit_block_xor_any(), bit_is_all_zero(), BMNOEXCEPT, BMRESTRICT, and IS_EMPTY_BLOCK.

Referenced by 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 8543 of file bmfunc.h.

References bit_block_count(), bit_block_xor_count(), BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

Referenced by bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_XOR().

## bit_scan_reverse()

template<class T>

unsigned bm::bit_scan_reverse | ( | T | value | ) |

Returns BSR value

Definition at line 453 of file bmutil.h.

References bit_scan_reverse32(), BM_ASSERT, and BMNOEXCEPT.

Referenced by bit_find_last(), bm::sparse_vector< Val, BV >::insert_value_no_null(), and bm::sparse_vector< Val, BV >::set_value_no_null().

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

References BM_ASSERT, and BMNOEXCEPT.

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

## bitcount64_4way()

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

inline

Parallel popcount on 4x 64-bit words

Definition at line 248 of file bmfunc.h.

References BMNOEXCEPT.

Referenced by bit_block_and_count(), bit_block_count(), bit_block_or_count(), bit_block_sub_count(), bit_block_xor_count(), and bit_count_min_unroll().

## bitscan()

template<typename V, typename B>

unsigned short bm::bitscan | ( | V | w,
|  | B * | bits )

Templated Bitscan with dynamic dispatch for best type.

Definition at line 769 of file bmfunc.h.

References bitscan_bsf(), bitscan_bsf64(), bitscan_popcnt(), bitscan_popcnt64(), and BMNOEXCEPT.

Referenced by bm::sparse_vector_scanner< SV, S_FACTOR >::add_agg_char(), bm::sparse_vector_scanner< SV, S_FACTOR >::find_eq_with_nulls_horizontal(), bm::sparse_vector_scanner< SV, S_FACTOR >::find_gt_horizontal(), for_each_bit_blk(), bm::sparse_vector< Val, BV >::import_u_nocheck(), and bm::sparse_vector_scanner< SV, S_FACTOR >::prepare_and_sub_aggregator().

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

References BMNOEXCEPT, and count_trailing_zeros_u32().

Referenced by bitscan(), and 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 730 of file bmfunc.h.

References BMNOEXCEPT, and count_trailing_zeros_u64().

Referenced by bitscan().

## bitscan_popcnt() [1/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 654 of file bmfunc.h.

References BMNOEXCEPT, and word_bitcount().

## bitscan_popcnt() [2/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 632 of file bmfunc.h.

References BMNOEXCEPT, and word_bitcount().

Referenced by bitscan(), and bitscan_wave().

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

References bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, and word_bitcount64().

Referenced by bitscan(), and 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 752 of file bmfunc.h.

References bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, and 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 9635 of file bmfunc.h.

References bitscan_bsf(), bitscan_popcnt(), bitscan_popcnt64(), BMNOEXCEPT, and BMRESTRICT.

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

## block_compact_by_digest()

void bm::block_compact_by_digest | ( | bm::word_t * | t_block,
|  | const bm::word_t * | block,
|  | bm::id64_t | digest,
|  | bool | zero_tail )

inline

Compact sub-blocks by digest (rank compaction).

Parameters

  t_block | - target block
  block | - src bit block
  digest | - digest to use for copy
  zero_tail | - flag to zero the tail memory

Definition at line 1211 of file bmfunc.h.

References block_waves, bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, set_block_digest_wave_size, and word_bitcount64().

## block_expand_by_digest()

void bm::block_expand_by_digest | ( | bm::word_t * | t_block,
|  | const bm::word_t * | block,
|  | bm::id64_t | digest,
|  | bool | zero_subs )

inline

expand sub-blocks by digest (rank expansion)

Parameters

  t_block | - target block
  block | - src bit block
  digest | - digest to use for copy
  zero_subs | - flag to zero the non-digest sub waves

Definition at line 1278 of file bmfunc.h.

References block_waves, BMNOEXCEPT, and set_block_digest_wave_size.

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

References BM_ASSERT, BMNOEXCEPT, set_block_digest_wave_size, and VECT_BLOCK_SET_DIGEST.

Referenced by bm::aggregator< BV >::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 1120 of file bmfunc.h.

References BMNOEXCEPT, set_block_digest_wave_size, and VECT_IS_DIGEST_ZERO.

Referenced by bm::bvector< Alloc >::combine_operation_block_and(), bm::xor_scanner< BV >::compute_xor_complexity_descr(), bm::serializer< BV >::find_bit_best_encoding(), bm::serializer< BV >::find_bit_best_encoding_l5(), bm::aggregator< BV >::process_bit_blocks_and(), bm::aggregator< BV >::process_shift_right_and(), and bm::xor_scanner< BV >::search_best_xor_mask().

## check_zero_digest()

BMFORCEINLINE 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

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

References BMNOEXCEPT, and digest_mask().

Referenced by gap_and_to_bitset(), and gap_sub_to_bitset().

## clear_bit()

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

Set 1 bit in a block.

Definition at line 3734 of file bmfunc.h.

References BMNOEXCEPT, set_block_mask, set_word_mask, and set_word_shift.

Referenced by bm::deserializer< BV, DEC >::decode_bit_block(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_inv_arr().

## count_leading_zeros()

BMFORCEINLINE unsigned bm::count_leading_zeros | ( | unsigned | x | ) |

Portable LZCNT with (uses minimal LUT).

Definition at line 173 of file bmutil.h.

References bm::lzcnt_table< T >::_lut, and BMNOEXCEPT.

Referenced by count_leading_zeros_u32().

## count_trailing_zeros()

BMFORCEINLINE unsigned bm::count_trailing_zeros | ( | unsigned | v | ) |

Portable TZCNT with (uses 37-LUT).

Definition at line 189 of file bmutil.h.

References bm::tzcnt_table< T >::_lut, and BMNOEXCEPT.

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

References BM_ASSERT, BMNOEXCEPT, gap_max_bits, and set_block_digest_pos_shift.

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

## for_each_bit_blk() [1/2]

template<typename Func, typename SIZE_TYPE>

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

Returns
  - functor return code (< 0 - interrupt the processing)

Definition at line 1597 of file bmalgo_impl.h.

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

Referenced by bm::aggregator< BV >::combine_and_sub(), for_each_bit_block_range(), and for_each_bit_range_no_check().

## for_each_bit_blk() [2/2]

template<typename Func, typename SIZE_TYPE>

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

Returns
  - functor return code (< 0 - interrupt the processing)

Definition at line 1637 of file bmalgo_impl.h.

References bits_in_block, bitscan(), bitscan_wave(), BM_ASSERT, IS_FULL_BLOCK, mask_l_u32(), mask_r_u32(), set_bitscan_wave_size, set_word_mask, and 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 6081 of file bmfunc.h.

References all_bits_mask, BMNOEXCEPT, BMRESTRICT, set_block_size, and VECT_IS_ONE_BLOCK.

Referenced by check_block_one(), bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), and bm::aggregator< BV >::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 3766 of file bmfunc.h.

References BMNOEXCEPT, set_word_mask, and set_word_shift.

Referenced by gap_add_to_bitset().

## set_bit()

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

Set 1 bit in a block.

Definition at line 3721 of file bmfunc.h.

References BMNOEXCEPT, set_block_mask, set_word_mask, and set_word_shift.

Referenced by bm::deserializer< BV, DEC >::decode_arrbit(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_arr_bit(), and bm::deseriaizer_base< DEC, BLOCK_IDX >::read_bic_arr().

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

References BM_ASSERT, BMNOEXCEPT, set_word_mask, and set_word_shift.

Referenced by gap_and_to_bitset(), gap_and_to_bitset(), gap_sub_to_bitset(), and 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 3748 of file bmfunc.h.

References BMNOEXCEPT, set_block_mask, set_word_mask, and 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 planes(rows) of the transposed bit block.

Parameters

  tmatrix | - bit-block transposition matrix (bit-planes)
  distance | - pairwise NxN Humming distance matrix (diagonal is popcnt)

Definition at line 315 of file bmtrans.h.

References bit_block_count(), and word_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 1162 of file bmfunc.h.

References bmi_blsi_u64(), bmi_bslr_u64(), BMNOEXCEPT, BMRESTRICT, set_block_digest_wave_size, VECT_IS_DIGEST_ZERO, and word_bitcount64().

Referenced by gap_and_to_bitset(), and gap_sub_to_bitset().

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

References BMNOEXCEPT, and set_block_digest_wave_size.

## word_bitcount()

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

Returns bit count

Definition at line 582 of file bmutil.h.

References bm::bit_count_table< T >::_count, and BMNOEXCEPT.

Referenced by bm::sparse_vector_scanner< SV, S_FACTOR >::add_agg_char(), bit_block_and_count(), bit_block_calc_count_range(), bit_block_calc_count_to(), bit_block_change32(), bit_block_count(), bit_block_or_count(), bit_block_sub_count(), bit_block_xor_change32(), bit_block_xor_count(), bit_count_change(), bit_count_min_unroll(), bit_find_first_if_1(), bit_find_rank(), bitscan_popcnt(), bitscan_popcnt(), 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::str_sparse_vector< char, bm::bvector<>, 64 >::import_char_slice(), bm::bit_COUNT< W >::operator()(), bm::bit_COUNT_A< W >::operator()(), bm::bit_COUNT_AND< W >::operator()(), bm::bit_COUNT_B< W >::operator()(), bm::bit_COUNT_OR< W >::operator()(), bm::bit_COUNT_SUB_AB< W >::operator()(), bm::bit_COUNT_SUB_BA< W >::operator()(), bm::bit_COUNT_XOR< W >::operator()(), sse2_bit_block_calc_count_change(), tmatrix_distance(), word_bitcount64(), word_select32_bitscan_popcnt(), and word_select32_bitscan_tz().

## word_bitcount64()

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

Function calculates number of 1 bits in 64-bit word.

Definition at line 605 of file bmutil.h.

References BMNOEXCEPT, and word_bitcount().

Referenced by bit_block_and(), bit_block_and_2way(), bit_block_and_3way(), bit_block_and_5way(), bit_block_and_or_2way(), bit_block_calc_count_to(), bit_block_change64(), bit_block_convert_to_arr(), bit_block_count(), bit_block_shift_r1_and(), bit_block_sub(), bit_block_sub_2way(), bit_block_sub_3way(), bit_block_sub_5way(), bit_block_xor(), bit_block_xor_change64(), bit_find_first(), bit_find_first_if_1(), bit_find_rank(), bitscan_popcnt64(), bitscan_popcnt64(), block_compact_by_digest(), bm::aggregator< BV >::combine_and_sub(), bm::bvector< Alloc >::combine_operation_block_and(), bm::serializer< BV >::encode_bit_digest(), bm::serializer< BV >::find_bit_best_encoding(), bm::serializer< BV >::find_bit_best_encoding_l5(), bm::aggregator< BV >::process_bit_blocks_and(), bm::aggregator< BV >::process_bit_blocks_sub(), bm::aggregator< BV >::process_gap_blocks_and(), bm::aggregator< BV >::process_gap_blocks_sub(), bm::deseriaizer_base< DEC, BLOCK_IDX >::read_digest0_block(), sse2_bit_block_xor_2way(), update_block_digest0(), word_select64_bitscan_popcnt(), and word_select64_bitscan_tz().

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

References BMNOEXCEPT, word_select32_bitscan_popcnt(), and word_select32_bitscan_tz().

Referenced by 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 883 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and word_bitcount().

Referenced by 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 912 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, count_trailing_zeros_u32(), and word_bitcount().

Referenced by 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 938 of file bmfunc.h.

References BMNOEXCEPT, word_select64_bitscan_popcnt(), and word_select64_bitscan_tz().

Referenced by 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 825 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and word_bitcount64().

Referenced by 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 854 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, count_trailing_zeros_u64(), and word_bitcount64().

Referenced by 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 799 of file bmfunc.h.

References BM_ASSERT, and BMNOEXCEPT.

## wordcmp()

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.

Parameters

  a | - First word.
  b | - Second word.

Returns
  <0 - less, =0 - equal, >0 - greater.

Definition at line 1532 of file bmfunc.h.

References BMNOEXCEPT.

## wordcmp0()

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.

Parameters

  w1 | - First word.
  w2 | - Second word.

Returns
  <0 - less, =0 - equal, >0 - greater.

Definition at line 1503 of file bmfunc.h.

References BMNOEXCEPT.

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

References BMNOEXCEPT, mask_l_u32(), mask_r_u32(), set_block_mask, set_word_mask, and set_word_shift.

Referenced by gap_xor_to_bitset().