BitMagic-C++
|
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 |
More... | |
template<typename T , typename F > | |
void | bm::bit_for_each_4 (T w, F &func) |
Templated algorithm to unpacks octet based word into list of ON bit indexes. More... | |
template<typename T , typename F > | |
void | bm::bit_for_each (T w, F &func) |
Templated algorithm to unpacks word into list of ON bit indexes. More... | |
template<typename T , typename B > | |
unsigned | bm::bit_list (T w, B *bits) BMNOEXCEPT |
Unpacks word into list of ON bit indexes. More... | |
template<typename T , typename B > | |
unsigned | bm::bit_list_4 (T w, B *bits) BMNOEXCEPT |
Unpacks word into list of ON bit indexes (quad-bit based) More... | |
template<typename B > | |
unsigned short | bm::bitscan_popcnt (bm::id_t w, B *bits, unsigned short offs) BMNOEXCEPT |
Unpacks word into list of ON bit indexes using popcnt method. More... | |
template<typename B > | |
unsigned short | bm::bitscan_popcnt (bm::id_t w, B *bits) BMNOEXCEPT |
Unpacks word into list of ON bit indexes using popcnt method. More... | |
template<typename B > | |
unsigned short | bm::bitscan_popcnt64 (bm::id64_t w, B *bits) BMNOEXCEPT |
Unpacks 64-bit word into list of ON bit indexes using popcnt method. More... | |
template<typename B > | |
unsigned short | bm::bitscan_bsf (unsigned w, B *bits) BMNOEXCEPT |
Unpacks word into list of ON bits (BSF/__builtin_ctz) More... | |
template<typename B > | |
unsigned short | bm::bitscan_bsf64 (bm::id64_t w, B *bits) BMNOEXCEPT |
Unpacks word into list of ON bits (BSF/__builtin_ctz) More... | |
template<typename B > | |
unsigned short | bm::bitscan_popcnt64 (bm::id64_t w, B *bits, unsigned short offs) BMNOEXCEPT |
Unpacks 64-bit word into list of ON bit indexes using popcnt method. More... | |
template<typename V , typename B > | |
unsigned short | bm::bitscan (V w, B *bits) BMNOEXCEPT |
Templated Bitscan with dynamic dispatch for best type. More... | |
unsigned | bm::word_select64_linear (bm::id64_t w, unsigned rank) BMNOEXCEPT |
word find index of the rank-th bit set by bit-testing More... | |
unsigned | bm::word_select64_bitscan_popcnt (bm::id64_t w, unsigned rank) BMNOEXCEPT |
word find index of the rank-th bit set by bit-testing More... | |
unsigned | bm::word_select64_bitscan_tz (bm::id64_t w, unsigned rank) BMNOEXCEPT |
word find index of the rank-th bit set by bit-testing More... | |
unsigned | bm::word_select32_bitscan_popcnt (unsigned w, unsigned rank) BMNOEXCEPT |
word find index of the rank-th bit set by bit-testing More... | |
unsigned | bm::word_select32_bitscan_tz (unsigned w, unsigned rank) BMNOEXCEPT |
word find index of the rank-th bit set by bit-testing More... | |
unsigned | bm::word_select64 (bm::id64_t w, unsigned rank) BMNOEXCEPT |
word find index of the rank-th bit set by bit-testing More... | |
unsigned | bm::word_select32 (unsigned w, unsigned rank) BMNOEXCEPT |
word find index of the rank-th bit set by bit-testing More... | |
BMFORCEINLINE bm::id64_t | bm::widx_to_digest_mask (unsigned w_idx) BMNOEXCEPT |
Compute digest mask for word address in block. More... | |
BMFORCEINLINE bm::id64_t | bm::digest_mask (unsigned from, unsigned to) BMNOEXCEPT |
Compute digest mask for [from..to] positions. More... | |
bool | bm::check_zero_digest (bm::id64_t digest, unsigned bitpos_from, unsigned bitpos_to) BMNOEXCEPT |
check if all digest bits for the range [from..to] are 0 More... | |
void | bm::block_init_digest0 (bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT |
Init block with 000111000 pattren based on digest. More... | |
bm::id64_t | bm::calc_block_digest0 (const bm::word_t *const block) BMNOEXCEPT |
Compute digest for 64 non-zero areas. More... | |
bm::id64_t | bm::update_block_digest0 (const bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT |
Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas) More... | |
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) More... | |
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) More... | |
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. More... | |
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. More... | |
bool | bm::bit_is_all_zero (const bm::word_t *BMRESTRICT start) BMNOEXCEPT |
Returns "true" if all bits in the block are 0. More... | |
BMFORCEINLINE void | bm::set_bit (unsigned *dest, unsigned bitpos) BMNOEXCEPT |
Set 1 bit in a block. More... | |
BMFORCEINLINE void | bm::clear_bit (unsigned *dest, unsigned bitpos) BMNOEXCEPT |
Set 1 bit in a block. More... | |
BMFORCEINLINE unsigned | bm::test_bit (const unsigned *block, unsigned bitpos) BMNOEXCEPT |
Test 1 bit in a block. More... | |
void | bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT |
Sets bits to 1 in the bitblock. More... | |
void | bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT |
SUB (AND NOT) bit interval to 1 in the bitblock. More... | |
void | bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT |
XOR bit interval to 1 in the bitblock. More... | |
void | bm::bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value) BMNOEXCEPT |
Bitblock memset operation. More... | |
template<typename T > | |
int | bm::bitcmp (const T *buf1, const T *buf2, unsigned len) BMNOEXCEPT |
Lexicographical comparison of BIT buffers. More... | |
bool | bm::bit_find_first_diff (const bm::word_t *BMRESTRICT blk1, const bm::word_t *BMRESTRICT blk2, unsigned *BMRESTRICT pos) BMNOEXCEPT |
Find first bit which is different between two bit-blocks. More... | |
BMFORCEINLINE unsigned | bm::bit_count_min_unroll (const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT block_end) BMNOEXCEPT |
Bitcount for bit block without agressive unrolling. More... | |
bm::id_t | bm::bit_block_count (const bm::word_t *block) BMNOEXCEPT |
Bitcount for bit block. More... | |
bm::id_t | bm::bit_block_count (const bm::word_t *BMRESTRICT const block, bm::id64_t digest) BMNOEXCEPT |
Bitcount for bit block. More... | |
bm::id_t | bm::bit_count_change (bm::word_t w) BMNOEXCEPT |
More... | |
unsigned | bm::bit_block_calc_change (const bm::word_t *block) BMNOEXCEPT |
More... | |
bool | bm::bit_block_is_all_one_range (const bm::word_t *const BMRESTRICT block, bm::word_t left, bm::word_t right) BMNOEXCEPT |
More... | |
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 |
More... | |
bm::id_t | bm::bit_block_calc_count_to (const bm::word_t *block, bm::word_t right) BMNOEXCEPT |
More... | |
void | bm::bit_block_rotate_left_1 (bm::word_t *block) BMNOEXCEPT |
More... | |
void | bm::bit_block_rotate_left_1_unr (bm::word_t *block) BMNOEXCEPT |
Unrolled cyclic rotation of bit-block left by 1 bit. More... | |
bm::word_t | bm::bit_block_insert (bm::word_t *BMRESTRICT block, unsigned bitpos, bool value) BMNOEXCEPT |
insert bit into position and shift the rest right with carryover More... | |
bool | bm::bit_block_shift_r1 (bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::word_t co_flag) BMNOEXCEPT |
Right bit-shift bitblock by 1 bit (reference) More... | |
bool | bm::bit_block_shift_r1_unr_min (bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::id64_t co_flag) BMNOEXCEPT |
Right bit-shift bitblock by 1 bit (minimum unroll) More... | |
bool | bm::bit_block_shift_r1_unr (bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::word_t co_flag) BMNOEXCEPT |
Right bit-shift of bit-block by 1 bit (loop unrolled) More... | |
bool | bm::bit_block_shift_l1 (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) BMNOEXCEPT |
Left bit-shift bitblock by 1 bit (reference) More... | |
bool | bm::bit_block_shift_l1_unr_min (bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, unsigned co_flag) BMNOEXCEPT |
Left bit-shift bitblock by 1 bit (minimum unroll) More... | |
bool | bm::bit_block_shift_l1_unr (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) BMNOEXCEPT |
Left bit-shift of bit-block by 1 bit (loop unrolled) More... | |
void | bm::bit_block_erase (bm::word_t *block, unsigned bitpos, bool carry_over) BMNOEXCEPT |
erase bit from position and shift the rest right with carryover More... | |
bool | bm::bit_block_shift_r1_and (bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest) BMNOEXCEPT |
Right bit-shift of bit-block by 1 bit (reference) + AND. More... | |
bool | bm::bit_block_shift_r1_and_unr (bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest) BMNOEXCEPT |
Right bit-shift bitblock by 1 bit (reference) + AND. More... | |
bm::id_t | bm::bit_block_any_range (const bm::word_t *const BMRESTRICT block, bm::word_t left, bm::word_t right) BMNOEXCEPT |
More... | |
template<typename T > | |
void | bm::bit_invert (T *start) BMNOEXCEPT |
More... | |
bool | bm::is_bits_one (const bm::wordop_t *start) BMNOEXCEPT |
Returns "true" if all bits in the block are 1. More... | |
bool | bm::bit_block_find_interval_end (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT |
Searches for the last 1 bit in the 111 interval of a BIT block. More... | |
bool | bm::bit_block_find_interval_start (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT |
Searches for the first 1 bit in the 111 interval of a BIT block. More... | |
bool | bm::bit_block_find_prev (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT |
Reverse search for the previous 1 bit. More... | |
void | bm::bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
Bitblock copy operation. More... | |
void | bm::bit_block_copy_unalign (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
Bitblock copy operation (unaligned src) More... | |
void | bm::bit_block_stream (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
Bitblock copy/stream operation. More... | |
void | bm::bit_block_stream_unalign (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
Bitblock copy/stream operation (unaligned src) More... | |
bm::id64_t | bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks. More... | |
bm::id64_t | bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest) BMNOEXCEPT |
digest based bit-block AND More... | |
bm::id64_t | bm::bit_block_and_5way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src0, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, bm::id64_t digest) BMNOEXCEPT |
digest based bit-block AND 5-way More... | |
bm::id64_t | bm::bit_block_and_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest) BMNOEXCEPT |
digest based bit-block AND More... | |
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 More... | |
unsigned | bm::bit_block_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_and_any (const bm::word_t *src1, const bm::word_t *src2) BMNOEXCEPT |
Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_or_count (const bm::word_t *src1, const bm::word_t *src2) BMNOEXCEPT |
Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More... | |
bm::word_t * | bm::bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
bitblock AND operation. More... | |
bm::id_t | bm::bit_operation_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs bitblock AND operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_and_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs bitblock AND operation test. More... | |
bm::id_t | bm::bit_operation_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs bitblock SUB operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_sub_count_inv (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs inverted bitblock SUB operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs bitblock test of SUB operation. More... | |
bm::id_t | bm::bit_operation_or_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs bitblock OR operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs bitblock OR operation test. More... | |
bool | bm::bit_block_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks. More... | |
bool | bm::bit_block_or_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
2 way (target := source1 | source2) bitblock OR operation. More... | |
bm::id64_t | bm::bit_block_xor_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
2 way (target := source1 ^ source2) bitblock XOR operation. More... | |
bool | bm::bit_block_or_3way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More... | |
bool | bm::bit_block_or_5way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, const bm::word_t *BMRESTRICT src4) BMNOEXCEPT |
5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More... | |
bm::word_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. More... | |
bm::id64_t | bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks. More... | |
bm::id64_t | bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest) BMNOEXCEPT |
digest based bitblock SUB (AND NOT) operation More... | |
bm::id64_t | bm::bit_block_sub_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest) BMNOEXCEPT |
digest based bitblock SUB (AND NOT) operation (3 operand) More... | |
bm::word_t * | bm::bit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
bitblock SUB operation. More... | |
bm::id64_t | bm::bit_block_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks. More... | |
void | bm::bit_andnot_arr_ffmask (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
bitblock AND NOT with constant ~0 mask operation. More... | |
bm::word_t * | bm::bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT |
bitblock XOR operation. More... | |
bm::id_t | bm::bit_operation_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs bitblock XOR operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT |
Performs bitblock XOR operation test. More... | |
template<class T > | |
unsigned | bm::bit_count_nonzero_size (const T *blk, unsigned data_size) BMNOEXCEPT |
Inspects block for full zero words. More... | |
unsigned | bm::bit_block_find (const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT |
Searches for the next 1 bit in the BIT block. More... | |
unsigned | bm::bit_find_last (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT last) BMNOEXCEPT |
BIT block find the last set bit (backward search) More... | |
bool | bm::bit_find_first (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT pos) BMNOEXCEPT |
BIT block find the first set bit. More... | |
unsigned | bm::bit_find_first (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT first, bm::id64_t digest) BMNOEXCEPT |
BIT block find the first set bit. More... | |
bool | bm::bit_find_first_if_1 (const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT first, bm::id64_t digest) BMNOEXCEPT |
BIT block find the first set bit if only 1 bit is set. More... | |
template<typename SIZE_TYPE > | |
SIZE_TYPE | bm::bit_find_rank (const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) BMNOEXCEPT |
BIT block find position for the rank. More... | |
bm::set_representation | bm::best_representation (unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size) BMNOEXCEPT |
Choose best representation for a bit-block. More... | |
template<typename T > | |
unsigned | bm::bit_block_convert_to_arr (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bool inverted) BMNOEXCEPT |
Convert bit block into an array of ints corresponding to 1 bits. More... | |
unsigned short | bm::bitscan_wave (const bm::word_t *BMRESTRICT w_ptr, unsigned char *BMRESTRICT bits) BMNOEXCEPT |
Unpacks word wave (Nx 32-bit words) More... | |
void | bm::bit_block_gather_scatter (unsigned *BMRESTRICT arr, const bm::word_t *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx) BMNOEXCEPT |
bit index to word gather-scatter algorithm (SIMD) More... | |
template<typename TRGW , typename IDX , typename SZ > | |
void | bm::bit_block_gather_scatter (TRGW *BMRESTRICT arr, const bm::word_t *BMRESTRICT blk, const IDX *BMRESTRICT idx, SZ size, SZ start, unsigned bit_idx) BMNOEXCEPT |
bit index to word gather-scatter algorithm More... | |
void | bm::bit_block_xor_change32 (const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT xor_block, unsigned size, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc) BMNOEXCEPT |
More... | |
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 |
More... | |
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 More... | |
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 More... | |
template<typename T , unsigned BPC, unsigned BPS> | |
void | bm::tmatrix_distance (const T tmatrix[BPC][BPS], unsigned distance[BPC][BPC]) |
Compute pairwise Row x Row Humming distances on planes(rows) of the transposed bit block. More... | |
template<typename T , unsigned BPC, unsigned BPS> | |
void | bm::bit_iblock_make_pcv (const unsigned distance[BPC][BPC], unsigned char *pc_vector) |
!< ibpc limiter More... | |
BMFORCEINLINE unsigned | bm::count_leading_zeros (unsigned x) BMNOEXCEPT |
Portable LZCNT with (uses minimal LUT) More... | |
BMFORCEINLINE unsigned | bm::count_trailing_zeros (unsigned v) BMNOEXCEPT |
Portable TZCNT with (uses 37-LUT) More... | |
template<class T > | |
unsigned | bm::bit_scan_reverse (T value) BMNOEXCEPT |
More... | |
BMFORCEINLINE bm::id_t | bm::word_bitcount (bm::id_t w) BMNOEXCEPT |
More... | |
BMFORCEINLINE unsigned | bm::word_bitcount64 (bm::id64_t x) BMNOEXCEPT |
More... | |
Bit functions implement different opereations on bit blocks (internals) and serve as a minimal building blocks.
|
inline |
Choose best representation for a bit-block.
Definition at line 8706 of file bmfunc.h.
References bm::set_array0, bm::set_array1, bm::set_bitset, and bm::set_gap.
Referenced by bm::serializer< BV >::find_bit_best_encoding().
|
inline |
bitblock AND NOT with constant ~0 mask operation.
dst | - destination block. |
src | - source block. |
Definition at line 8202 of file bmfunc.h.
References bm::all_bits_mask, BMRESTRICT, bm::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().
|
inline |
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks.
dst | - destination block. |
src | - source block. |
Definition at line 6824 of file bmfunc.h.
References BM_ASSERT, BMRESTRICT, bm::set_block_size, and VECT_AND_BLOCK.
Referenced by bm::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().
|
inline |
digest based bit-block AND
dst | - destination block. |
src | - source block. |
digest | - known digest of dst block |
Definition at line 6861 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_AND_DIGEST, and bm::word_bitcount64().
|
inline |
digest based bit-block AND
dst = src1 AND src2
dst | - destination block. |
src1 | - source block. |
src2 | - source block. |
digest | - known initial digest |
Definition at line 6983 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_AND_DIGEST_2WAY, and bm::word_bitcount64().
Referenced by bm::bvector< Alloc >::combine_operation_block_and(), and bm::aggregator< BV >::process_bit_blocks_and().
|
inline |
digest based bit-block AND 5-way
Definition at line 6916 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_AND_DIGEST_5WAY, and bm::word_bitcount64().
Referenced by bm::aggregator< BV >::process_bit_blocks_and().
|
inline |
Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks.
src1 | - first bit block |
src2 | - second bit block |
Definition at line 7161 of file bmfunc.h.
References bm::set_block_size.
Referenced by bm::bit_operation_and_any().
|
inline |
Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.
src1 | - first bit block |
src2 | - second bit block |
Definition at line 7114 of file bmfunc.h.
References bm::bitcount64_4way(), bm::set_block_size, VECT_BITCOUNT_AND, and bm::word_bitcount().
Referenced by bm::bit_operation_and_count().
|
inline |
digest based bit-block AND - OR
dst =dst OR (src1 AND src2)
dst | - destination block. |
src1 | - source block. |
src2 | - source block. |
digest | - known initial digest |
Definition at line 7050 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_AND_OR_DIGEST_2WAY, and bm::word_bitcount64().
Referenced by bm::bvector< Alloc >::combine_operation_block_and_or().
|
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 5953 of file bmfunc.h.
References BM_ASSERT, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_word_mask, and bm::set_word_shift.
|
inline |
Function calculates number of times when bit value changed (1-0 or 0-1) in the bit block.
block | - bit-block start pointer |
Definition at line 5249 of file bmfunc.h.
References bm::bit_block_change32(), bm::bit_block_change64(), bm::set_block_size, and VECT_BLOCK_CHANGE.
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 5356 of file bmfunc.h.
References BM_ASSERT, bm::gap_max_bits, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_word_mask, bm::set_word_shift, and bm::word_bitcount().
Referenced by bm::bvector< Alloc >::build_rs_index(), bm::bvector< Alloc >::count_range_no_check(), bm::gap_bitset_and_count(), bm::gap_bitset_or_count(), bm::gap_bitset_sub_count(), and bm::gap_bitset_xor_count().
|
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 5442 of file bmfunc.h.
References BM_ASSERT, BM_AVX2_BIT_COUNT, BM_AVX2_POPCNT_PROLOG, bm::mask_l_u32(), bm::word_bitcount(), and bm::word_bitcount64().
Referenced by bm::bvector< Alloc >::build_rs_index(), and bm::bvector< Alloc >::count_to_test().
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.
Convert bit block into an array of ints corresponding to 1 bits
Definition at line 8749 of file bmfunc.h.
References bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::gap_max_bits, and bm::word_bitcount64().
Referenced by bm::serializer< 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().
|
inline |
Bitblock copy operation.
dst | [out] - destination block. |
src | [in] - source block. |
Definition at line 6743 of file bmfunc.h.
References bm::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().
|
inline |
Bitblock copy operation (unaligned src)
dst | [out] - destination block. |
src | [in] - source block. |
Definition at line 6761 of file bmfunc.h.
References bm::set_block_size, and VECT_COPY_BLOCK_UNALIGN.
Referenced by bm::bit_import_u32().
|
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 5017 of file bmfunc.h.
References bm::bit_count_min_unroll(), bm::set_block_size, and VECT_BITCOUNT.
Referenced by bm::bit_block_change_bc(), bm::bit_operation_or_count(), bm::bit_operation_sub_count(), bm::bit_operation_xor_count(), bm::aggregator< BV >::combine_and_sub(), bm::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 bm::tmatrix_distance().
|
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 5036 of file bmfunc.h.
References bm::bitcount64_4way(), BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_BIT_COUNT_DIGEST, bm::word_bitcount(), and bm::word_bitcount64().
|
inline |
erase bit from position and shift the rest right with carryover
block | - bit-block pointer |
bitpos | - bit position to insert |
carry_over | - bit value to add to the end (0|1) |
Definition at line 5800 of file bmfunc.h.
References bm::bit_block_shift_l1_unr(), BM_ASSERT, bm::mask_r_u32(), bm::set_block_mask, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector< Alloc >::erase().
|
inline |
Searches for the next 1 bit in the BIT block.
block | - BIT buffer |
nbit | - bit index to start checking from |
pos | - [out] found value |
Definition at line 8389 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector< Alloc >::check_or_next(), and bm::serializer< BV >::serialize().
|
inline |
Searches for the last 1 bit in the 111 interval of a BIT block.
block | - BIT buffer |
nbit | - bit index to start checking from |
pos | - [out] found value |
Definition at line 6143 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, bm::gap_max_bits, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::block_find_interval_end().
|
inline |
Searches for the first 1 bit in the 111 interval of a BIT block.
block | - BIT buffer |
nbit | - bit index to start checking from |
pos | - [out] found value |
Definition at line 6239 of file bmfunc.h.
References bm::bit_scan_reverse32(), BM_ASSERT, bm::mask_l_u32(), bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::block_find_interval_start().
|
inline |
Reverse search for the previous 1 bit.
block | - BIT buffer |
nbit | - bit index to start checking from |
pos | - [out] found value |
Definition at line 6303 of file bmfunc.h.
References bm::bit_scan_reverse32(), BM_ASSERT, bm::mask_l_u32(), bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::block_find_reverse().
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 9398 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
|
inline |
bit index to word gather-scatter algorithm (SIMD)
Definition at line 9364 of file bmfunc.h.
References bm::avx2_bit_block_gather_scatter(), BM_ASSERT, and bm::sse4_bit_block_gather_scatter().
Referenced by bm::sparse_vector< Val, BV >::gather().
|
inline |
insert bit into position and shift the rest right with carryover
block | - bit-block pointer |
bitpos | - bit position to insert |
value | - bit value (0|1) to insert |
Definition at line 5551 of file bmfunc.h.
References BM_ASSERT, bm::mask_r_u32(), bm::set_block_mask, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector< Alloc >::insert().
|
inline |
Check if all bits are 1 in [left, right] range
Definition at line 5267 of file bmfunc.h.
References BM_ASSERT, bm::gap_max_bits, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::block_is_all_one_range(), and bm::block_is_interval().
|
inline |
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.
dst | - destination block. |
src | - source block. |
Definition at line 7675 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK.
Referenced by bm::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().
|
inline |
2 way (target := source1 | source2) bitblock OR operation.
dst | - dest block [out] |
src1 | - source 1 |
src2 | - source 2 |
Definition at line 7712 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_2WAY.
Referenced by bm::bvector< Alloc >::combine_operation_block_or().
|
inline |
3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of source and destination blocks.
dst | - sst-dest block [in,out] |
src1 | - source 1 |
src2 | - source 2 |
Definition at line 7792 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_3WAY.
Referenced by bm::aggregator< BV >::process_bit_blocks_or().
|
inline |
5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of source and destination blocks.
dst | - destination block. |
src1 | - source1, etc |
src2 | - source1, etc |
src3 | - source1, etc |
src4 | - source1, etc |
Definition at line 7836 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_5WAY.
Referenced by bm::aggregator< BV >::process_bit_blocks_or().
|
inline |
Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 7385 of file bmfunc.h.
References BMRESTRICT, and bm::set_block_size.
Referenced by bm::bit_operation_or_any().
|
inline |
Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.
src1 | - first bit block |
src2 | - second bit block. |
Definition at line 7338 of file bmfunc.h.
References bm::bitcount64_4way(), bm::set_block_size, VECT_BITCOUNT_OR, and bm::word_bitcount().
Referenced by bm::bit_operation_or_count().
|
inline |
Cyclic rotation of bit-block left by 1 bit
Definition at line 5499 of file bmfunc.h.
References bm::set_block_size.
|
inline |
Unrolled cyclic rotation of bit-block left by 1 bit.
block | - bit-block pointer |
Definition at line 5515 of file bmfunc.h.
References bm::set_block_size.
|
inline |
Bitblock memset operation.
dst | - destination block. |
value | - value to set. |
Definition at line 4422 of file bmfunc.h.
References bm::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(), bm::gap_convert_to_bitset(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_arr_bit(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_AND(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_ASSIGN(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_AND(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_OR(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_SUB_AB(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_SUB_BA(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_XOR(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_SUB(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_XOR(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_inv_arr(), bm::aggregator< 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().
|
inline |
Left bit-shift bitblock by 1 bit (reference)
block | - bit-block pointer |
empty_acc | - [out] contains 0 if block is empty |
co_flag | - carry over from the prev/next block |
Definition at line 5702 of file bmfunc.h.
References BM_ASSERT, and bm::set_block_size.
|
inline |
Left bit-shift of bit-block by 1 bit (loop unrolled)
block | - bit-block pointer |
empty_acc | - [out] contains 0 if block is empty |
co_flag | - carry over from the prev/next block |
Definition at line 5777 of file bmfunc.h.
References bm::bit_block_shift_l1_unr_min(), BM_ASSERT, and VECT_SHIFT_L1.
Referenced by bm::bit_block_erase(), and bm::bvector< Alloc >::erase().
|
inline |
Left bit-shift bitblock by 1 bit (minimum unroll)
block | - bit-block pointer |
empty_acc | - [out] contains 0 if block is empty |
co_flag | - carry over from the prev/next block |
Definition at line 5733 of file bmfunc.h.
References bm::set_block_size.
Referenced by bm::bit_block_shift_l1_unr().
|
inline |
Right bit-shift bitblock by 1 bit (reference)
block | - bit-block pointer |
empty_acc | - [out] contains 0 if block is empty |
co_flag | - carry over from the previous block |
Definition at line 5600 of file bmfunc.h.
References BM_ASSERT, and bm::set_block_size.
Referenced by bm::bit_block_shift_r1_unr_min().
|
inline |
Right bit-shift of bit-block by 1 bit (reference) + AND.
block | - bit-block pointer |
co_flag | - carry over from the previous block |
mask_block | - mask bit-block pointer |
digest | - block digest |
Definition at line 5856 of file bmfunc.h.
References BM_ASSERT, bm::set_block_digest_wave_size, bm::set_block_size, and bm::word_bitcount64().
Referenced by bm::bit_block_shift_r1_and_unr().
|
inline |
Right bit-shift bitblock by 1 bit (reference) + AND.
block | - bit-block pointer |
co_flag | - carry over from the previous block |
mask_block | - mask bit-block pointer |
digest | - block digest |
Definition at line 5928 of file bmfunc.h.
References bm::bit_block_shift_r1_and(), BM_ASSERT, and VECT_SHIFT_R1_AND.
Referenced by bm::aggregator< BV >::process_shift_right_and().
|
inline |
Right bit-shift of bit-block by 1 bit (loop unrolled)
block | - bit-block pointer |
empty_acc | - [out] contains 0 if block is empty |
co_flag | - carry over from the previous block |
Definition at line 5677 of file bmfunc.h.
References bm::bit_block_shift_r1_unr_min(), BM_ASSERT, and VECT_SHIFT_R1.
Referenced by bm::bvector< Alloc >::insert().
|
inline |
Right bit-shift bitblock by 1 bit (minimum unroll)
block | - bit-block pointer |
empty_acc | - [out] contains 0 if block is empty |
co_flag | - carry over from the previous block |
Definition at line 5631 of file bmfunc.h.
References bm::bit_block_shift_r1(), BMRESTRICT, and bm::set_block_size.
Referenced by bm::bit_block_shift_r1_unr().
|
inline |
Bitblock copy/stream operation.
dst | - destination block. |
src | - source block. |
Definition at line 6782 of file bmfunc.h.
References bm::set_block_size, and VECT_STREAM_BLOCK.
|
inline |
Bitblock copy/stream operation (unaligned src)
dst | [out] - destination block. |
src | [in] - source block (unaligned address) |
Definition at line 6800 of file bmfunc.h.
References bm::set_block_size, and VECT_STREAM_BLOCK_UNALIGN.
|
inline |
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks.
dst | - destination block. |
src | - source block. |
Definition at line 7945 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_SUB_BLOCK.
Referenced by bm::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().
|
inline |
digest based bitblock SUB (AND NOT) operation
dst | - destination block. |
src | - source block. |
digest | - known digest of dst block |
Definition at line 7981 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_SUB_DIGEST, and bm::word_bitcount64().
|
inline |
digest based bitblock SUB (AND NOT) operation (3 operand)
dst | - destination block. |
src1 | - source block 1 |
src2 | - source block 2 |
digest | - known digest of dst block |
Definition at line 8041 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_SUB_DIGEST_2WAY, and bm::word_bitcount64().
Referenced by bm::bvector< Alloc >::combine_operation_block_sub().
|
inline |
Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 7310 of file bmfunc.h.
References BMRESTRICT, and bm::set_block_size.
Referenced by bm::bit_operation_sub_any().
|
inline |
Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 7264 of file bmfunc.h.
References bm::bitcount64_4way(), BMRESTRICT, bm::set_block_size, VECT_BITCOUNT_SUB, and bm::word_bitcount().
Referenced by bm::bit_operation_sub_count().
|
inline |
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks.
dst | - destination block. |
src | - source block. |
Definition at line 8166 of file bmfunc.h.
References BM_ASSERT, BMRESTRICT, bm::set_block_size, and VECT_XOR_BLOCK.
Referenced by bm::xor_scanner< BV >::apply_xor_match_vector(), bm::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().
|
inline |
2 way (target := source1 ^ source2) bitblock XOR operation.
dst | - dest block [out] |
src1 | - source 1 |
src2 | - source 2 |
Definition at line 7751 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_XOR_BLOCK_2WAY.
Referenced by bm::bvector< Alloc >::combine_operation_block_xor().
|
inline |
Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 7238 of file bmfunc.h.
References BMRESTRICT, and bm::set_block_size.
Referenced by bm::bit_operation_xor_any().
|
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, and bm::word_bitcount().
Referenced by bm::bit_block_xor_change().
|
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, BMRESTRICT, and bm::word_bitcount64().
Referenced by bm::bit_block_xor_change().
|
inline |
Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.
src1 | - first bit block |
src2 | - second bit block |
Definition at line 7190 of file bmfunc.h.
References bm::bitcount64_4way(), BMRESTRICT, bm::set_block_size, VECT_BITCOUNT_XOR, and bm::word_bitcount().
Referenced by bm::bit_operation_xor_count().
|
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 5111 of file bmfunc.h.
References bm::word_bitcount().
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 4962 of file bmfunc.h.
References bm::bitcount64_4way(), BM_ASSERT, BMRESTRICT, and bm::word_bitcount().
Referenced by bm::bit_block_count(), and bm::compute_s_block_descr().
unsigned bm::bit_count_nonzero_size | ( | const T * | blk, |
unsigned | data_size | ||
) |
Inspects block for full zero words.
blk | - bit block pointer |
data_size | - data size |
Definition at line 8333 of file bmfunc.h.
References BM_ASSERT.
Referenced by bm::serializer< BV >::find_bit_best_encoding(), and bm::serializer< BV >::find_bit_best_encoding_l5().
|
inline |
BIT block find the first set bit.
block | - bit block buffer pointer |
first | - index of the first 1 bit (out) |
digest | - known digest of dst block |
Definition at line 8509 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, bm::bmi_blsi_u64(), bm::set_block_digest_wave_size, bm::set_block_size, and bm::word_bitcount64().
|
inline |
BIT block find the first set bit.
block | - bit block buffer pointer |
pos | - index of the first 1 bit (out) |
Definition at line 8474 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, bm::set_block_size, and VECT_BIT_FIND_FIRST.
Referenced by bm::block_find_first_diff(), bm::bvector< Alloc >::check_or_next(), bm::bvector< Alloc >::find(), and bm::aggregator< BV >::find_first_and_sub().
|
inline |
Find first bit which is different between two bit-blocks.
blk1 | - block 1 |
blk2 | - block 2 |
pos | - out - position of difference (undefined if blocks are equal) |
Definition at line 4691 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, BMRESTRICT, bm::count_trailing_zeros_u64(), bm::set_block_size, and VECT_BIT_FIND_DIFF.
Referenced by bm::block_find_first_diff().
|
inline |
BIT block find the first set bit if only 1 bit is set.
block | - bit block buffer pointer |
first | - index of the first 1 bit (out) |
digest | - known digest of dst block |
Definition at line 8547 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, bm::bmi_blsi_u64(), bm::set_block_digest_wave_size, bm::word_bitcount(), and bm::word_bitcount64().
Referenced by bm::aggregator< 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().
|
inline |
BIT block find the last set bit (backward search)
block | - bit block buffer pointer |
last | - index of the last 1 bit (out) |
Definition at line 8440 of file bmfunc.h.
References bm::bit_scan_reverse(), BM_ASSERT, and bm::set_block_size.
Referenced by bm::bvector< Alloc >::find_reverse().
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.
block | - bit block buffer pointer |
rank | - rank to find (must be > 0) |
nbit_from | - start bit position in block |
nbit_pos | - (out)found position |
Definition at line 8601 of file bmfunc.h.
References BM_ASSERT, bm::set_block_size, bm::set_word_mask, bm::set_word_shift, bm::word_bitcount(), bm::word_bitcount64(), bm::word_select32(), and bm::word_select64().
Referenced by bm::block_find_rank().
void bm::bit_for_each | ( | T | w, |
F & | func | ||
) |
Templated algorithm to unpacks word into list of ON bit indexes.
w | - value |
func | - bit functor |
Definition at line 351 of file bmfunc.h.
Referenced by bm::bit_list().
void bm::bit_for_each_4 | ( | T | w, |
F & | func | ||
) |
Templated algorithm to unpacks octet based word into list of ON bit indexes.
w | - value |
func | - bit functor |
Definition at line 281 of file bmfunc.h.
References BM_ASSERT.
Referenced by bm::bit_list_4().
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
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, bm::ibpc_all_one, bm::ibpc_all_zero, bm::ibpc_close, bm::ibpc_equiv, and bm::ibpc_uncompr.
Referenced by bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::compute_distance_matrix().
void bm::bit_invert | ( | T * | start | ) |
Function inverts block of bits
Definition at line 6023 of file bmfunc.h.
References BM_ASSERT, IS_VALID_ADDR, bm::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().
|
inline |
Returns "true" if all bits in the block are 0.
Definition at line 1522 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_IS_ZERO_BLOCK.
Referenced by bm::bit_operation_or_any(), bm::bit_operation_sub_any(), bm::bit_operation_xor_any(), bm::block_any(), bm::check_block_zero(), bm::combine_any_operation_with_block(), 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(), bm::gap_bitset_or_any(), bm::aggregator< BV >::process_gap_blocks_and(), and bm::aggregator< BV >::process_gap_blocks_sub().
unsigned bm::bit_list | ( | T | w, |
B * | bits | ||
) |
Unpacks word into list of ON bit indexes.
w | - value |
bits | - pointer on the result array |
Definition at line 587 of file bmfunc.h.
References bm::bit_for_each(), and bm::copy_to_array_functor< B >::ptr().
Referenced by bm::str_sparse_vector< CharType, BV, STR_SIZE >::import_char_slice().
unsigned bm::bit_list_4 | ( | T | w, |
B * | bits | ||
) |
Unpacks word into list of ON bit indexes (quad-bit based)
w | - value |
bits | - pointer on the result array |
Definition at line 605 of file bmfunc.h.
References bm::bit_for_each_4(), and bm::copy_to_array_functor< B >::ptr().
|
inline |
bitblock AND operation.
dst | - destination block. |
src | - source block. |
Definition at line 7418 of file bmfunc.h.
References bm::bit_block_and(), BM_ASSERT, IS_EMPTY_BLOCK, IS_FULL_BLOCK, and IS_VALID_ADDR.
Referenced by bm::bvector< Alloc >::combine_operation_with_block().
|
inline |
Performs bitblock AND operation test.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 7490 of file bmfunc.h.
References bm::bit_block_and_any(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.
Referenced by bm::combine_any_operation_with_block().
|
inline |
Performs bitblock AND operation and calculates bitcount of the result.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 7466 of file bmfunc.h.
References bm::bit_block_and_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.
Referenced by bm::combine_count_and_operation_with_block(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_AND().
|
inline |
Block OR operation. Makes analysis if block is 0 or FULL.
dst | - destination block. |
src | - source block. |
Definition at line 7885 of file bmfunc.h.
References bm::bit_block_or(), BM_ASSERT, FULL_BLOCK_FAKE_ADDR, IS_FULL_BLOCK, IS_VALID_ADDR, and bm::set_block_size.
Referenced by bm::bvector< Alloc >::combine_operation_with_block().
|
inline |
Performs bitblock OR operation test.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 7642 of file bmfunc.h.
References bm::bit_block_or_any(), bm::bit_is_all_zero(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.
Referenced by bm::combine_any_operation_with_block().
|
inline |
Performs bitblock OR operation and calculates bitcount of the result.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 7605 of file bmfunc.h.
References bm::bit_block_count(), bm::bit_block_or_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.
Referenced by bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_OR().
|
inline |
bitblock SUB operation.
dst | - destination block. |
src | - source block. |
Definition at line 8108 of file bmfunc.h.
References bm::bit_block_sub(), BM_ASSERT, IS_FULL_BLOCK, and IS_VALID_ADDR.
Referenced by bm::bvector< Alloc >::combine_operation_block_sub(), and bm::bvector< Alloc >::combine_operation_with_block().
|
inline |
Performs bitblock test of SUB operation.
src1 | - first bit block. |
src2 | - second bit block |
Definition at line 7570 of file bmfunc.h.
References bm::bit_block_sub_any(), bm::bit_is_all_zero(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.
Referenced by bm::combine_any_operation_with_block().
|
inline |
Performs bitblock SUB operation and calculates bitcount of the result.
src1 | - first bit block. |
src2 | - second bit block |
Definition at line 7515 of file bmfunc.h.
References bm::bit_block_count(), bm::bit_block_sub_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.
Referenced by bm::bit_operation_sub_count_inv(), bm::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().
|
inline |
Performs inverted bitblock SUB operation and calculates bitcount of the result.
src1 | - first bit block. |
src2 | - second bit block |
Definition at line 7552 of file bmfunc.h.
References bm::bit_operation_sub_count().
|
inline |
bitblock XOR operation.
dst | - destination block. |
src | - source block. |
Definition at line 8237 of file bmfunc.h.
References bm::bit_block_xor(), BM_ASSERT, and IS_VALID_ADDR.
Referenced by bm::bvector< Alloc >::combine_operation_with_block().
|
inline |
Performs bitblock XOR operation test.
src1 | - bit block start ptr |
src2 | - second bit block ptr |
Definition at line 8307 of file bmfunc.h.
References bm::bit_block_xor_any(), bm::bit_is_all_zero(), and IS_EMPTY_BLOCK.
Referenced by bm::combine_any_operation_with_block().
|
inline |
Performs bitblock XOR operation and calculates bitcount of the result.
src1 | - bit block start ptr |
src2 | - second bit block |
Definition at line 8275 of file bmfunc.h.
References bm::bit_block_count(), bm::bit_block_xor_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.
Referenced by bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_XOR().
unsigned bm::bit_scan_reverse | ( | T | value | ) |
Returns BSR value
Definition at line 453 of file bmutil.h.
References bm::bit_scan_reverse32(), and BM_ASSERT.
Referenced by bm::bit_find_last(), bm::sparse_vector< Val, BV >::insert_value_no_null(), and bm::sparse_vector< Val, BV >::set_value_no_null().
int bm::bitcmp | ( | const T * | buf1, |
const T * | buf2, | ||
unsigned | len | ||
) |
Lexicographical comparison of BIT buffers.
buf1 | - First buffer pointer. |
buf2 | - Second buffer pointer. |
len | - Buffer length in elements (T). |
Definition at line 4666 of file bmfunc.h.
References BM_ASSERT.
Referenced by bm::bvector< Alloc >::compare().
|
inline |
Parallel popcount on 4x 64-bit words
Definition at line 240 of file bmfunc.h.
Referenced by bm::bit_block_and_count(), bm::bit_block_count(), bm::bit_block_or_count(), bm::bit_block_sub_count(), bm::bit_block_xor_count(), and bm::bit_count_min_unroll().
unsigned short bm::bitscan | ( | V | w, |
B * | bits | ||
) |
Templated Bitscan with dynamic dispatch for best type.
Definition at line 761 of file bmfunc.h.
References bm::bitscan_bsf(), bm::bitscan_bsf64(), bm::bitscan_popcnt(), and bm::bitscan_popcnt64().
Referenced by bm::sparse_vector_scanner< SV >::add_agg_char(), bm::sparse_vector_scanner< SV >::find_eq_with_nulls_horizontal(), bm::sparse_vector_scanner< SV >::find_gt_horizontal(), bm::for_each_bit_blk(), bm::sparse_vector< Val, BV >::import_u_nocheck(), and bm::sparse_vector_scanner< SV >::prepare_and_sub_aggregator().
unsigned short bm::bitscan_bsf | ( | unsigned | w, |
B * | bits | ||
) |
Unpacks word into list of ON bits (BSF/__builtin_ctz)
w | - value |
bits | - pointer on the result array |
Definition at line 689 of file bmfunc.h.
References bm::count_trailing_zeros_u32().
Referenced by bm::bitscan(), and bm::bitscan_wave().
unsigned short bm::bitscan_bsf64 | ( | bm::id64_t | w, |
B * | bits | ||
) |
Unpacks word into list of ON bits (BSF/__builtin_ctz)
w | - value |
bits | - pointer on the result array |
Definition at line 722 of file bmfunc.h.
References bm::count_trailing_zeros_u64().
Referenced by bm::bitscan().
unsigned short bm::bitscan_popcnt | ( | bm::id_t | w, |
B * | bits | ||
) |
Unpacks word into list of ON bit indexes using popcnt method.
w | - value |
bits | - pointer on the result array |
Definition at line 646 of file bmfunc.h.
References bm::word_bitcount().
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.
w | - value |
bits | - pointer on the result array |
offs | - value to add to bit position (programmed shift) |
Definition at line 624 of file bmfunc.h.
References bm::word_bitcount().
Referenced by bm::bitscan(), and bm::bitscan_wave().
unsigned short bm::bitscan_popcnt64 | ( | bm::id64_t | w, |
B * | bits | ||
) |
Unpacks 64-bit word into list of ON bit indexes using popcnt method.
w | - value |
bits | - pointer on the result array |
Definition at line 667 of file bmfunc.h.
References bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), and bm::word_bitcount64().
Referenced by bm::bitscan(), and bm::bitscan_wave().
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.
w | - value |
bits | - pointer on the result array |
offs | - value to add to bit position (programmed shift) |
Definition at line 744 of file bmfunc.h.
References bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), and bm::word_bitcount64().
|
inline |
Unpacks word wave (Nx 32-bit words)
w_ptr | - pointer on wave start |
bits | - pointer on the result array |
Definition at line 9320 of file bmfunc.h.
References bm::bitscan_bsf(), bm::bitscan_popcnt(), and bm::bitscan_popcnt64().
Referenced by bm::for_each_bit_blk(), and bm::bvector< Alloc >::enumerator::go_to().
|
inline |
Compact sub-blocks by digest (rank compaction)
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 1183 of file bmfunc.h.
References bm::block_waves, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), bm::set_block_digest_wave_size, and bm::word_bitcount64().
|
inline |
expand sub-blocks by digest (rank expansion)
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 1250 of file bmfunc.h.
References bm::block_waves, and bm::set_block_digest_wave_size.
|
inline |
Init block with 000111000 pattren based on digest.
block | - Bit block [out] |
digest | - digest (used for block initialization) |
Definition at line 1062 of file bmfunc.h.
References bm::set_block_digest_wave_size, and VECT_BLOCK_SET_DIGEST.
Referenced by bm::aggregator< BV >::process_bit_blocks_and().
|
inline |
Compute digest for 64 non-zero areas.
block | - Bit block |
Definition at line 1092 of file bmfunc.h.
References bm::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(), bm::xor_scanner< BV >::search_best_xor_mask(), and bm::update_block_digest0().
|
inline |
check if all digest bits for the range [from..to] are 0
digest | - current digest |
bitpos_from | - range from (in bit-block coordinates) |
bitpos_to | - range to (in bit-block coordinates) |
Definition at line 1046 of file bmfunc.h.
References bm::digest_mask().
Referenced by bm::gap_and_to_bitset(), and bm::gap_sub_to_bitset().
BMFORCEINLINE void bm::clear_bit | ( | unsigned * | dest, |
unsigned | bitpos | ||
) |
Set 1 bit in a block.
Definition at line 3716 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::deserializer< BV, DEC >::decode_bit_block(), and bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_inv_arr().
BMFORCEINLINE unsigned bm::count_leading_zeros | ( | unsigned | x | ) |
Portable LZCNT with (uses minimal LUT)
Definition at line 173 of file bmutil.h.
Referenced by bm::count_leading_zeros_u32().
BMFORCEINLINE unsigned bm::count_trailing_zeros | ( | unsigned | v | ) |
BMFORCEINLINE bm::id64_t bm::digest_mask | ( | unsigned | from, |
unsigned | to | ||
) |
Compute digest mask for [from..to] positions.
from | - range from (in bit-block coordinates) |
to | - range to (in bit-block coordinates) |
Definition at line 1017 of file bmfunc.h.
References BM_ASSERT, bm::gap_max_bits, and bm::set_block_digest_pos_shift.
Referenced by bm::check_zero_digest(), and bm::aggregator< BV >::process_bit_blocks_and().
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
block | - bit block buffer pointer |
offset | - global block offset (number of bits) |
bit_functor | - functor must support .add_bits(offset, bits_ptr, size) |
Definition at line 1597 of file bmalgo_impl.h.
References bm::bitscan_wave(), BM_ASSERT, bm::gap_max_bits, IS_FULL_BLOCK, bm::set_bitscan_wave_size, and bm::set_block_size.
Referenced by bm::aggregator< BV >::combine_and_sub(), bm::for_each_bit_block_range(), and bm::for_each_bit_range_no_check().
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
block | - bit block buffer pointer |
offset | - global block offset (number of bits) |
left | - bit addredd in block from [from..to] |
right | - bit addredd in block to [from..to] |
bit_functor | - functor must support .add_bits(offset, bits_ptr, size) |
Definition at line 1637 of file bmalgo_impl.h.
References bm::bits_in_block, bm::bitscan(), bm::bitscan_wave(), BM_ASSERT, IS_FULL_BLOCK, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_bitscan_wave_size, bm::set_word_mask, and bm::set_word_shift.
|
inline |
Returns "true" if all bits in the block are 1.
Definition at line 6047 of file bmfunc.h.
References bm::all_bits_mask, BMRESTRICT, bm::set_block_size, and VECT_IS_ONE_BLOCK.
Referenced by bm::check_block_one(), bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), and bm::aggregator< BV >::process_bit_blocks_or().
|
inline |
Sets bits to 1 in the bitblock.
dest | - Bitset buffer. |
bitpos | - Offset of the start bit. |
bitcount | - number of bits to set. |
Definition at line 3748 of file bmfunc.h.
References bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::gap_add_to_bitset().
BMFORCEINLINE void bm::set_bit | ( | unsigned * | dest, |
unsigned | bitpos | ||
) |
Set 1 bit in a block.
Definition at line 3703 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::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().
|
inline |
SUB (AND NOT) bit interval to 1 in the bitblock.
dest | - Bitset buffer. |
bitpos | - Offset of the start bit. |
bitcount | - number of bits to set. |
Definition at line 3795 of file bmfunc.h.
References bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::gap_and_to_bitset(), and bm::gap_sub_to_bitset().
BMFORCEINLINE unsigned bm::test_bit | ( | const unsigned * | block, |
unsigned | bitpos | ||
) |
Test 1 bit in a block.
Definition at line 3730 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
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.
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 bm::bit_block_count(), and bm::word_bitcount().
Referenced by bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::compute_distance_matrix().
|
inline |
Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas)
block | - bit block |
digest | - start digest |
Definition at line 1134 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::calc_block_digest0(), bm::set_block_digest_wave_size, VECT_IS_DIGEST_ZERO, and bm::word_bitcount64().
Referenced by bm::bvector< Alloc >::combine_operation_block_and(), bm::aggregator< BV >::process_gap_blocks_and(), bm::aggregator< BV >::process_gap_blocks_sub(), and bm::aggregator< BV >::process_shift_right_and().
BMFORCEINLINE bm::id64_t bm::widx_to_digest_mask | ( | unsigned | w_idx | ) |
Compute digest mask for word address in block.
Definition at line 989 of file bmfunc.h.
References bm::set_block_digest_wave_size.
BMFORCEINLINE bm::id_t bm::word_bitcount | ( | bm::id_t | w | ) |
Returns bit count
Definition at line 573 of file bmutil.h.
Referenced by bm::sparse_vector_scanner< SV >::add_agg_char(), bm::bit_block_and_count(), bm::bit_block_calc_count_range(), bm::bit_block_calc_count_to(), bm::bit_block_change32(), bm::bit_block_count(), bm::bit_block_or_count(), bm::bit_block_sub_count(), bm::bit_block_xor_change32(), bm::bit_block_xor_count(), bm::bit_count_change(), bm::bit_count_min_unroll(), bm::bit_find_first_if_1(), bm::bit_find_rank(), bm::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< CharType, BV, STR_SIZE >::import_char_slice(), bm::bit_COUNT< W >::operator()(), bm::bit_COUNT_AND< W >::operator()(), bm::bit_COUNT_XOR< 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_A< W >::operator()(), bm::bit_COUNT_B< W >::operator()(), bm::sse2_bit_block_calc_count_change(), bm::tmatrix_distance(), bm::word_bitcount64(), bm::word_select32_bitscan_popcnt(), and bm::word_select32_bitscan_tz().
BMFORCEINLINE unsigned bm::word_bitcount64 | ( | bm::id64_t | x | ) |
Function calculates number of 1 bits in 64-bit word.
Definition at line 596 of file bmutil.h.
References bm::word_bitcount().
Referenced by bm::bit_block_and(), bm::bit_block_and_2way(), bm::bit_block_and_5way(), bm::bit_block_and_or_2way(), bm::bit_block_calc_count_to(), bm::bit_block_change64(), bm::bit_block_convert_to_arr(), bm::bit_block_count(), bm::bit_block_shift_r1_and(), bm::bit_block_sub(), bm::bit_block_sub_2way(), bm::bit_block_xor(), bm::bit_block_xor_change64(), bm::bit_find_first(), bm::bit_find_first_if_1(), bm::bit_find_rank(), bm::bitscan_popcnt64(), bm::block_compact_by_digest(), 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(), bm::sse2_bit_block_xor_2way(), bm::update_block_digest0(), bm::word_select64_bitscan_popcnt(), and bm::word_select64_bitscan_tz().
|
inline |
word find index of the rank-th bit set by bit-testing
w | - 32-bit work to search |
rank | - rank to select (should be > 0) |
Definition at line 957 of file bmfunc.h.
References bm::word_select32_bitscan_popcnt(), and bm::word_select32_bitscan_tz().
Referenced by bm::bit_find_rank().
|
inline |
word find index of the rank-th bit set by bit-testing
w | - 32-bit work to search |
rank | - rank to select (should be > 0) |
Definition at line 875 of file bmfunc.h.
References BM_ASSERT, and bm::word_bitcount().
Referenced by bm::word_select32().
|
inline |
word find index of the rank-th bit set by bit-testing
w | - 32-bit work to search |
rank | - rank to select (should be > 0) |
Definition at line 904 of file bmfunc.h.
References BM_ASSERT, bm::count_trailing_zeros_u32(), and bm::word_bitcount().
Referenced by bm::word_select32().
|
inline |
word find index of the rank-th bit set by bit-testing
w | - 64-bit work to search |
rank | - rank to select (should be > 0) |
Definition at line 930 of file bmfunc.h.
References bm::word_select64_bitscan_popcnt(), and bm::word_select64_bitscan_tz().
Referenced by bm::bit_find_rank().
|
inline |
word find index of the rank-th bit set by bit-testing
w | - 64-bit work to search |
rank | - rank to select (should be > 0) |
Definition at line 817 of file bmfunc.h.
References BM_ASSERT, and bm::word_bitcount64().
Referenced by bm::word_select64().
|
inline |
word find index of the rank-th bit set by bit-testing
w | - 64-bit work to search |
rank | - rank to select (should be > 0) |
Definition at line 846 of file bmfunc.h.
References BM_ASSERT, bm::count_trailing_zeros_u64(), and bm::word_bitcount64().
Referenced by bm::word_select64().
|
inline |
int bm::wordcmp | ( | T | a, |
T | b | ||
) |
int bm::wordcmp0 | ( | T | w1, |
T | w2 | ||
) |
|
inline |
XOR bit interval to 1 in the bitblock.
dest | - Bitset buffer. |
bitpos | - Offset of the start bit. |
bitcount | - number of bits to set. |
Definition at line 3842 of file bmfunc.h.
References bm::mask_l_u32(), bm::mask_r_u32(), bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::gap_xor_to_bitset().