BitMagic-C++
|
Bit functions implement different opereations on bit blocks (internals) and serve as a minimal building blocks. More...
Data Structures | |
struct | bm::all_set< T > |
Structure carries pointer on bit block with all bits 1. More... | |
struct | bm::first_bit_table< T > |
Structure keeps index of first right 1 bit for every byte. More... | |
struct | bm::bit_count_table< T > |
Structure to aid in counting bits table contains count of bits in 0-255 diapason of numbers. More... | |
struct | bm::lzcnt_table< T > |
Structure for LZCNT constants (4-bit) More... | |
struct | bm::tzcnt_table< T > |
Structure for TZCNT constants. More... | |
struct | bm::block_set_table< T > |
Structure keeps all-left/right ON bits masks. More... | |
Macros | |
#define | BM_INCWORD_BITCOUNT(cnt, w) cnt += unsigned(_mm_popcnt_u32(w)); |
Functions | |
template<class T > | |
unsigned | bm::bit_scan_reverse (T value) |
BMFORCEINLINE bm::id_t | bm::word_bitcount (bm::id_t w) |
BMFORCEINLINE unsigned | bm::word_bitcount64 (bm::id64_t x) |
template<typename T , typename F > | |
void | bm::bit_for_each_4 (T w, F &func) |
Templated algorithm to unpacks octet based word into list of ON bit indexes. More... | |
template<typename T , typename F > | |
void | bm::bit_for_each (T w, F &func) |
Templated algorithm to unpacks word into list of ON bit indexes. More... | |
template<typename T , typename B > | |
unsigned | bm::bit_list (T w, B *bits) |
Unpacks word into list of ON bit indexes. More... | |
template<typename T , typename B > | |
unsigned | bm::bit_list_4 (T w, B *bits) |
Unpacks word into list of ON bit indexes (quad-bit based) More... | |
template<typename B > | |
unsigned short | bm::bitscan_popcnt (bm::id_t w, B *bits, unsigned short offs) |
Unpacks word into list of ON bit indexes using popcnt method. More... | |
template<typename B > | |
unsigned short | bm::bitscan_popcnt (bm::id_t w, B *bits) |
Unpacks word into list of ON bit indexes using popcnt method. More... | |
template<typename B > | |
unsigned short | bm::bitscan_popcnt64 (bm::id64_t w, B *bits) |
Unpacks 64-bit word into list of ON bit indexes using popcnt method. More... | |
BMFORCEINLINE bm::id64_t | bm::widx_to_digest_mask (unsigned w_idx) |
Compute digest mask for word address in block. More... | |
BMFORCEINLINE bm::id64_t | bm::digest_mask (unsigned from, unsigned to) |
Compute digest mask for [from..to] positions. More... | |
bool | bm::check_zero_digest (bm::id64_t digest, unsigned bitpos_from, unsigned bitpos_to) |
check if all digest bits for the range [from..to] are 0 More... | |
void | bm::block_init_digest0 (bm::word_t *const block, bm::id64_t digest) |
Init block with 000111000 pattren based on digest. More... | |
bm::id64_t | bm::calc_block_digest0 (const bm::word_t *const block) |
Compute digest for 64 non-zero areas. More... | |
bm::id64_t | bm::update_block_digest0 (const bm::word_t *const block, bm::id64_t digest) |
Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas) More... | |
template<typename T > | |
int | bm::wordcmp0 (T w1, T w2) |
Lexicographical comparison of two words as bit strings (reference) Auxiliary implementation for testing and reference purposes. More... | |
template<typename T > | |
int | bm::wordcmp (T a, T b) |
Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes. More... | |
bool | bm::bit_is_all_zero (const bm::word_t *BMRESTRICT start) |
Returns "true" if all bits in the block are 0. More... | |
BMFORCEINLINE void | bm::set_bit (unsigned *dest, unsigned bitpos) |
Set 1 bit in a block. More... | |
BMFORCEINLINE void | bm::clear_bit (unsigned *dest, unsigned bitpos) |
Set 1 bit in a block. More... | |
BMFORCEINLINE unsigned | bm::test_bit (const unsigned *block, unsigned bitpos) |
Test 1 bit in a block. More... | |
void | bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) |
Sets bits to 1 in the bitblock. More... | |
void | bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) |
SUB (AND NOT) bit interval to 1 in the bitblock. More... | |
void | bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) |
XOR bit interval to 1 in the bitblock. More... | |
void | bm::bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value) |
Bitblock memset operation. More... | |
template<typename T > | |
int | bm::bitcmp (const T *buf1, const T *buf2, unsigned len) |
Lexicographical comparison of BIT buffers. More... | |
bm::id_t | bm::bit_block_count (const bm::word_t *block) |
Bitcount for bit block. More... | |
bm::id_t | bm::bit_block_count (const bm::word_t *const block, bm::id64_t digest) |
Bitcount for bit block. More... | |
bm::id_t | bm::bit_block_calc_count (const bm::word_t *block, const bm::word_t *block_end) |
Bitcount for bit string. More... | |
bm::id_t | bm::bit_count_change (bm::word_t w) |
unsigned | bm::bit_block_calc_change (const bm::word_t *block) |
bm::id_t | bm::bit_block_calc_count_range (const bm::word_t *block, bm::word_t left, bm::word_t right) |
bm::id_t | bm::bit_block_calc_count_to (const bm::word_t *block, bm::word_t right) |
void | bm::bit_block_rotate_left_1 (bm::word_t *block) |
void | bm::bit_block_rotate_left_1_unr (bm::word_t *block) |
Unrolled cyclic rotation of bit-block left by 1 bit. More... | |
bm::word_t | bm::bit_block_insert (bm::word_t *block, unsigned bitpos, bool value) |
insert bit into position and shift the rest right with carryover More... | |
bool | bm::bit_block_shift_r1 (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) |
Right bit-shift bitblock by 1 bit (reference) More... | |
bool | bm::bit_block_shift_r1_unr (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) |
Right bit-shift of bit-block by 1 bit (loop unrolled) More... | |
bool | bm::bit_block_shift_l1 (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) |
Left bit-shift bitblock by 1 bit (reference) More... | |
bool | bm::bit_block_shift_l1_unr (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) |
Left bit-shift of bit-block by 1 bit (loop unrolled) More... | |
void | bm::bit_block_erase (bm::word_t *block, unsigned bitpos, bool carry_over) |
erase bit from position and shift the rest right with carryover More... | |
bool | bm::bit_block_shift_r1_and (bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest) |
Right bit-shift of bit-block by 1 bit (reference) + AND. More... | |
bool | bm::bit_block_shift_r1_and_unr (bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest) |
Right bit-shift bitblock by 1 bit (reference) + AND. More... | |
bm::id_t | bm::bit_block_any_range (const bm::word_t *block, bm::word_t left, bm::word_t right) |
template<typename T > | |
void | bm::bit_invert (T *start) |
bool | bm::is_bits_one (const bm::wordop_t *start) |
Returns "true" if all bits in the block are 1. More... | |
void | bm::bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Bitblock copy operation. More... | |
void | bm::bit_block_stream (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Bitblock copy/stream operation. More... | |
bm::id64_t | bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks. More... | |
bm::id64_t | bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest) |
digest based bit-block AND More... | |
bm::id64_t | bm::bit_block_and_5way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src0, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, bm::id64_t digest) |
digest based bit-block AND 5-way More... | |
bm::id64_t | bm::bit_block_and_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest) |
digest based bit-block AND More... | |
unsigned | bm::bit_block_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_and_any (const bm::word_t *src1, const bm::word_t *src2) |
Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_or_count (const bm::word_t *src1, const bm::word_t *src2) |
Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More... | |
unsigned | bm::bit_block_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More... | |
bm::word_t * | bm::bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
bitblock AND operation. More... | |
bm::id_t | bm::bit_operation_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs bitblock AND operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_and_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs bitblock AND operation test. More... | |
bm::id_t | bm::bit_operation_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs bitblock SUB operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_sub_count_inv (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs inverted bitblock SUB operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs bitblock test of SUB operation. More... | |
bm::id_t | bm::bit_operation_or_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs bitblock OR operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs bitblock OR operation test. More... | |
bool | bm::bit_block_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks. More... | |
bool | bm::bit_block_or_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
2 way (target := source1 | source2) bitblock OR operation. More... | |
bm::id64_t | bm::bit_block_xor_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
2 way (target := source1 ^ source2) bitblock XOR operation. More... | |
bool | bm::bit_block_or_3way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More... | |
bool | bm::bit_block_or_5way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, const bm::word_t *BMRESTRICT src4) |
5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More... | |
bm::word_t * | bm::bit_operation_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Block OR operation. Makes analysis if block is 0 or FULL. More... | |
bm::id64_t | bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks. More... | |
bm::id64_t | bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest) |
digest based bitblock SUB (AND NOT) operation More... | |
bm::id64_t | bm::bit_block_sub_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest) |
digest based bitblock SUB (AND NOT) operation (3 operand) More... | |
bm::word_t * | bm::bit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
bitblock SUB operation. More... | |
bm::id64_t | bm::bit_block_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks. More... | |
void | bm::bit_andnot_arr_ffmask (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
bitblock AND NOT with constant ~0 mask operation. More... | |
bm::word_t * | bm::bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
bitblock XOR operation. More... | |
bm::id_t | bm::bit_operation_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs bitblock XOR operation and calculates bitcount of the result. More... | |
bm::id_t | bm::bit_operation_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) |
Performs bitblock XOR operation test. More... | |
template<class T > | |
unsigned | bm::bit_count_nonzero_size (const T *blk, unsigned data_size) |
Inspects block for full zero words. More... | |
unsigned | bm::bit_block_find (const bm::word_t *block, unsigned nbit, unsigned *pos) |
Searches for the next 1 bit in the BIT block. More... | |
unsigned | bm::bit_find_last (const bm::word_t *block, unsigned *last) |
BIT block find the last set bit (backward search) More... | |
unsigned | bm::bit_find_first (const bm::word_t *block, unsigned *first) |
BIT block find the first set bit. More... | |
unsigned | bm::bit_find_first (const bm::word_t *block, unsigned *first, bm::id64_t digest) |
BIT block find the first set bit. More... | |
bool | bm::bit_find_first_if_1 (const bm::word_t *block, unsigned *first, bm::id64_t digest) |
BIT block find the first set bit if only 1 bit is set. More... | |
template<typename SIZE_TYPE > | |
SIZE_TYPE | bm::bit_find_rank (const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) |
BIT block find position for the rank. More... | |
bm::set_representation | bm::best_representation (unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size) |
Choose best representation for a bit-block. More... | |
template<typename T > | |
T | bm::bit_convert_to_arr (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len, unsigned mask=0) |
Convert bit block into an array of ints corresponding to 1 bits. More... | |
unsigned short | bm::bitscan_wave (const bm::word_t *w_ptr, unsigned char *bits) |
Unpacks word wave (Nx 32-bit words) More... | |
void | bm::bit_block_gather_scatter (unsigned *arr, const bm::word_t *blk, const unsigned *idx, unsigned size, unsigned start, unsigned bit_idx) |
bit index to word gather-scatter algorithm (SIMD) More... | |
template<typename TRGW , typename IDX , typename SZ > | |
void | bm::bit_block_gather_scatter (TRGW *arr, const bm::word_t *blk, const IDX *idx, SZ size, SZ start, unsigned bit_idx) |
bit index to word gather-scatter algorithm More... | |
template<typename Func , typename SIZE_TYPE > | |
void | bm::for_each_bit_blk (const bm::word_t *block, SIZE_TYPE offset, Func &bit_functor) |
for-each visitor, calls a special visitor functor for each 1 bit group More... | |
template<typename T , unsigned BPC, unsigned BPS> | |
void | bm::tmatrix_distance (const T tmatrix[BPC][BPS], unsigned distance[BPC][BPC]) |
Compute pairwise Row x Row Humming distances on plains(rows) of the transposed bit block. More... | |
template<typename T , unsigned BPC, unsigned BPS> | |
void | bm::bit_iblock_make_pcv (const unsigned distance[BPC][BPC], unsigned char *pc_vector) |
!< ibpc limiter More... | |
unsigned | bm::count_leading_zeros (unsigned x) |
Portable LZCNT with (uses minimal LUT) More... | |
unsigned | bm::count_trailing_zeros (unsigned v) |
Portable TZCNT with (uses 37-LUT) More... | |
Bit functions implement different opereations on bit blocks (internals) and serve as a minimal building blocks.
#define BM_INCWORD_BITCOUNT | ( | cnt, | |
w | |||
) | cnt += unsigned(_mm_popcnt_u32(w)); |
|
inline |
Choose best representation for a bit-block.
Definition at line 6941 of file bmfunc.h.
References bm::set_array0, bm::set_array1, bm::set_bitset, and bm::set_gap.
|
inline |
bitblock AND NOT with constant ~0 mask operation.
dst | - destination block. |
src | - source block. |
Definition at line 6439 of file bmfunc.h.
References bm::all_bits_mask, BMRESTRICT, bm::set_block_size, and VECT_ANDNOT_ARR_2_MASK.
|
inline |
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks.
dst | - destination block. |
src | - source block. |
Definition at line 5107 of file bmfunc.h.
References BM_ASSERT, BMRESTRICT, bm::set_block_size, and VECT_AND_BLOCK.
Referenced by bm::bit_operation_and(), bm::serial_stream_iterator< DEC >::get_bit_block_AND(), and bm::aggregator< bvector_type >::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 5145 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_AND_DIGEST, and bm::word_bitcount64().
|
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 5267 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_AND_DIGEST_2WAY, and bm::word_bitcount64().
Referenced by bm::aggregator< bvector_type >::process_bit_blocks_and().
|
inline |
digest based bit-block AND 5-way
Definition at line 5200 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< bvector_type >::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 5379 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 5330 of file bmfunc.h.
References bm::bitcount64_4way(), BM_INCWORD_BITCOUNT, bm::set_block_size, and VECT_BITCOUNT_AND.
Referenced by bm::bit_operation_and_count().
|
inline |
Function calculates if there is any number of 1 bits in the given array of words in the range between left anf right bits (borders included). Make sure the addresses are aligned.
Definition at line 4673 of file bmfunc.h.
References BM_ASSERT, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::gap_bitset_and_any(), bm::gap_bitset_sub_any(), and bm::gap_bitset_xor_any().
|
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 4173 of file bmfunc.h.
References bm::bit_block_change32(), and VECT_BLOCK_CHANGE.
Referenced by bm::serializer< bvector_type >::find_bit_best_encoding().
|
inline |
Bitcount for bit string.
Added for back-compatibility purposes, not block aligned, not SIMD accelerated
Definition at line 4074 of file bmfunc.h.
References BM_INCWORD_BITCOUNT.
|
inline |
Function calculates number of 1 bits in the given array of words in the range between left anf right bits (borders included) Make sure the addr is aligned.
Definition at line 4191 of file bmfunc.h.
References BM_ASSERT, bm::gap_max_bits, bm::set_word_mask, bm::set_word_shift, and bm::word_bitcount().
Referenced by bm::bvector<>::build_rs_index(), bm::bvector<>::count_range(), 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 4260 of file bmfunc.h.
References BM_ASSERT, bm::word_bitcount(), and bm::word_bitcount64().
Referenced by bm::bvector<>::count_to_test().
|
inline |
Bitblock copy operation.
dst | - destination block. |
src | - source block. |
Definition at line 5067 of file bmfunc.h.
References bm::set_block_size, and VECT_COPY_BLOCK.
Referenced by bm::aggregator< bvector_type >::combine_shift_right_and(), bm::serial_stream_iterator< DEC >::get_bit_block_ASSIGN(), bm::aggregator< bvector_type >::process_bit_blocks_and(), and bm::aggregator< bvector_type >::process_bit_blocks_or().
|
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 3972 of file bmfunc.h.
References bm::bitcount64_4way(), BM_ASSERT, BM_INCWORD_BITCOUNT, bm::set_block_size, and VECT_BITCOUNT.
Referenced by bm::bit_operation_or_count(), bm::bit_operation_sub_count(), bm::bit_operation_xor_count(), bm::combine_count_operation_with_block(), bm::serializer< bvector_type >::find_bit_best_encoding(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT(), bm::serial_stream_iterator< DEC >::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 4035 of file bmfunc.h.
References bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, and bm::word_bitcount64().
|
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 4522 of file bmfunc.h.
References bm::bit_block_shift_l1_unr(), BM_ASSERT, bm::set_block_mask, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector<>::erase().
|
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 6631 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::serializer< bvector_type >::serialize().
void bm::bit_block_gather_scatter | ( | TRGW * | arr, |
const bm::word_t * | blk, | ||
const IDX * | idx, | ||
SZ | size, | ||
SZ | start, | ||
unsigned | bit_idx | ||
) |
bit index to word gather-scatter algorithm
Definition at line 7551 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
|
inline |
bit index to word gather-scatter algorithm (SIMD)
Definition at line 7520 of file bmfunc.h.
References BM_ASSERT, and bm::sse4_bit_block_gather_scatter().
Referenced by bm::sparse_vector< unsigned, bm::bvector<> >::gather().
|
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 4369 of file bmfunc.h.
References BM_ASSERT, bm::set_block_mask, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::bvector<>::insert().
|
inline |
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.
dst | - destination block. |
src | - source block. |
Definition at line 5915 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK.
Referenced by bm::bit_operation_or(), bm::deserializer< typename SV::bvector_type, bm::decoder >::decode_bit_block(), bm::serial_stream_iterator< DEC >::get_bit_block_OR(), and bm::aggregator< bvector_type >::process_bit_blocks_or().
|
inline |
2 way (target := source1 | source2) bitblock OR operation.
dst | - dest block [out] |
src1 | - source 1 |
src2 | - source 2 |
Definition at line 5952 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_2WAY.
|
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 6032 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_3WAY.
Referenced by bm::aggregator< bvector_type >::process_bit_blocks_or().
|
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 |
Definition at line 6073 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_5WAY.
Referenced by bm::aggregator< bvector_type >::process_bit_blocks_or().
|
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 5610 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 5562 of file bmfunc.h.
References bm::bitcount64_4way(), BM_INCWORD_BITCOUNT, bm::set_block_size, and VECT_BITCOUNT_OR.
Referenced by bm::bit_operation_or_count().
|
inline |
Cyclic rotation of bit-block left by 1 bit
Definition at line 4317 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 4333 of file bmfunc.h.
References bm::set_block_size.
|
inline |
Bitblock memset operation.
dst | - destination block. |
value | - value to set. |
Definition at line 3492 of file bmfunc.h.
References bm::set_block_size, and VECT_SET_BLOCK.
Referenced by bm::aggregator< bvector_type >::combine_shift_right_and(), bm::deserializer< typename SV::bvector_type, bm::decoder >::decode_bit_block(), bm::deserializer< typename SV::bvector_type, bm::decoder >::deserialize(), bm::gap_convert_to_bitset(), bm::serial_stream_iterator< DEC >::get_arr_bit(), bm::serial_stream_iterator< DEC >::get_bit_block_AND(), bm::serial_stream_iterator< DEC >::get_bit_block_ASSIGN(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_AND(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_OR(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_SUB_AB(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_SUB_BA(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_XOR(), bm::serial_stream_iterator< DEC >::get_bit_block_SUB(), bm::serial_stream_iterator< DEC >::get_bit_block_XOR(), bm::serial_stream_iterator< DEC >::get_inv_arr(), bm::aggregator< bvector_type >::process_bit_blocks_or(), bm::aggregator< bvector_type >::process_shift_right_and(), bm::deseriaizer_base< bm::decoder >::read_0runs_block(), bm::deseriaizer_base< bm::decoder >::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 4470 of file bmfunc.h.
References BM_ASSERT, and bm::set_block_size.
Referenced by bm::bit_block_shift_l1_unr().
|
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 4500 of file bmfunc.h.
References bm::bit_block_shift_l1(), BM_ASSERT, and VECT_SHIFT_L1.
Referenced by bm::bit_block_erase(), and bm::bvector<>::erase().
|
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 4417 of file bmfunc.h.
References BM_ASSERT, and bm::set_block_size.
Referenced by bm::bit_block_shift_r1_unr().
|
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 4576 of file bmfunc.h.
References BM_ASSERT, bm::set_block_digest_wave_size, bm::set_block_size, and bm::word_bitcount64().
Referenced by bm::bit_block_shift_r1_and_unr().
|
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 4648 of file bmfunc.h.
References bm::bit_block_shift_r1_and(), BM_ASSERT, and VECT_SHIFT_R1_AND.
Referenced by bm::aggregator< bvector_type >::process_shift_right_and().
|
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 4446 of file bmfunc.h.
References bm::bit_block_shift_r1(), BM_ASSERT, and VECT_SHIFT_R1.
Referenced by bm::bvector<>::insert().
|
inline |
Bitblock copy/stream operation.
dst | - destination block. |
src | - source block. |
Definition at line 5085 of file bmfunc.h.
References bm::set_block_size, and VECT_STREAM_BLOCK.
|
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 6182 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_SUB_BLOCK.
Referenced by bm::bit_operation_sub(), bm::serial_stream_iterator< DEC >::get_bit_block_SUB(), and bm::aggregator< bvector_type >::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 6218 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_SUB_DIGEST, and bm::word_bitcount64().
|
inline |
digest based bitblock SUB (AND NOT) operation (3 operand)
dst | - destination block. |
src1 | - source block. |
src1 | - source block. |
digest | - known digest of dst block |
Definition at line 6278 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::set_block_digest_wave_size, VECT_SUB_DIGEST_2WAY, and bm::word_bitcount64().
|
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 5533 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 5485 of file bmfunc.h.
References bm::bitcount64_4way(), BM_INCWORD_BITCOUNT, BMRESTRICT, bm::set_block_size, and VECT_BITCOUNT_SUB.
Referenced by bm::bit_operation_sub_count().
|
inline |
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks.
dst | - destination block. |
src | - source block. |
Definition at line 6403 of file bmfunc.h.
References BM_ASSERT, BMRESTRICT, bm::set_block_size, and VECT_XOR_BLOCK.
Referenced by bm::bit_operation_xor(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), and bm::serial_stream_iterator< DEC >::get_bit_block_XOR().
|
inline |
2 way (target := source1 ^ source2) bitblock XOR operation.
dst | - dest block [out] |
src1 | - source 1 |
src2 | - source 2 |
Definition at line 5991 of file bmfunc.h.
References BMRESTRICT, bm::set_block_size, and VECT_XOR_BLOCK_2WAY.
|
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 5458 of file bmfunc.h.
References BMRESTRICT, and bm::set_block_size.
Referenced by bm::bit_operation_xor_any().
|
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 5409 of file bmfunc.h.
References bm::bitcount64_4way(), BM_INCWORD_BITCOUNT, BMRESTRICT, bm::set_block_size, and VECT_BITCOUNT_XOR.
Referenced by bm::bit_operation_xor_count().
T bm::bit_convert_to_arr | ( | T *BMRESTRICT | dest, |
const unsigned *BMRESTRICT | src, | ||
bm::id_t | bits, | ||
unsigned | dest_len, | ||
unsigned | mask = 0 |
||
) |
Convert bit block into an array of ints corresponding to 1 bits.
Definition at line 6978 of file bmfunc.h.
References BMRESTRICT, and bm::word_bitcount().
Referenced by bm::serializer< bvector_type >::bienc_arr_bit_block(), bm::serializer< bvector_type >::encode_bit_array(), bm::serializer< bvector_type >::gamma_arr_bit_block(), and bm::serializer< bvector_type >::interpolated_arr_bit_block().
|
inline |
Function calculates number of times when bit value changed (1-0 or 0-1).
For 001 result is 2 010 - 3 011 - 2 111 - 1
Definition at line 4109 of file bmfunc.h.
References bm::word_bitcount().
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 6571 of file bmfunc.h.
References BM_ASSERT.
Referenced by bm::serializer< bvector_type >::find_bit_best_encoding().
|
inline |
BIT block find the first set bit.
block | - bit block buffer pointer |
first | - index of the first 1 bit (out) |
Definition at line 6711 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, and bm::set_block_size.
Referenced by bm::bvector<>::find(), and bm::aggregator< bvector_type >::find_first_and_sub().
|
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 6743 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, bm::bmi_blsi_u64(), bm::set_block_digest_wave_size, bm::set_block_size, and bm::word_bitcount64().
|
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 6781 of file bmfunc.h.
References bm::bit_scan_forward32(), BM_ASSERT, bm::bmi_blsi_u64(), bm::set_block_digest_wave_size, bm::word_bitcount(), and bm::word_bitcount64().
Referenced by bm::aggregator< bvector_type >::process_bit_blocks_and(), bm::aggregator< bvector_type >::process_bit_blocks_sub(), bm::aggregator< bvector_type >::process_gap_blocks_and(), and bm::aggregator< bvector_type >::process_gap_blocks_sub().
|
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 6679 of file bmfunc.h.
References bm::bit_scan_reverse(), BM_ASSERT, and bm::set_block_size.
Referenced by bm::bvector<>::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 6838 of file bmfunc.h.
References BM_ASSERT, bm::set_block_size, bm::set_word_mask, bm::set_word_shift, bm::word_bitcount(), bm::word_bitcount64(), and bm::word_select64().
Referenced by bm::block_find_rank().
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 355 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 285 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-plains
distance | - pairwise distance matrix |
pc_vector | - OUT compression descriptor vector pc_vector[] format: each element (pc_vector[i]) describes the plain compression: first 3 bits - compression code: 0 - plain uncompressed 1 - plain is ALL ZERO (000000...) 2 - plain is ALL ONE (111111...) 3 - plain is equal to another plain J (5 high bits (max 31)) 4 - plain is close (but not equal) to plain J next 5 bits - number of plain used as a XOR expression ( compression codes: 3,4 ) |
Definition at line 381 of file bmtrans.h.
References BM_ASSERT, bm::ibpc_all_one, bm::ibpc_all_zero, 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 4736 of file bmfunc.h.
References BM_ASSERT, IS_VALID_ADDR, bm::set_block_size, and VECT_INVERT_BLOCK.
Referenced by bm::deserializer< typename SV::bvector_type, bm::decoder >::decode_bit_block(), bm::bvector<>::invert(), and bm::deseriaizer_base< bm::decoder >::read_bic_arr_inv().
|
inline |
Returns "true" if all bits in the block are 0.
Definition at line 1012 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::check_block_zero(), bm::combine_any_operation_with_block(), bm::aggregator< bvector_type >::combine_shift_right_and(), bm::bvector<>::compare(), bm::gap_bitset_or_any(), bm::aggregator< bvector_type >::process_gap_blocks_and(), and bm::aggregator< bvector_type >::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 426 of file bmfunc.h.
References bm::bit_for_each(), and bm::copy_to_array_functor< B >::ptr().
Referenced by bm::str_sparse_vector< CharType, BV, MAX_STR_SIZE >::import_no_check().
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 443 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 5642 of file bmfunc.h.
References bm::bit_block_and(), BM_ASSERT, IS_EMPTY_BLOCK, IS_FULL_BLOCK, and IS_VALID_ADDR.
|
inline |
Performs bitblock AND operation test.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 5730 of file bmfunc.h.
References bm::bit_block_and_any(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.
Referenced by bm::combine_any_operation_with_block().
|
inline |
Performs bitblock AND operation and calculates bitcount of the result.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 5706 of file bmfunc.h.
References bm::bit_block_and_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.
Referenced by bm::combine_count_and_operation_with_block(), and bm::serial_stream_iterator< DEC >::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 6122 of file bmfunc.h.
References bm::bit_block_or(), BM_ASSERT, FULL_BLOCK_FAKE_ADDR, IS_FULL_BLOCK, IS_VALID_ADDR, and bm::set_block_size.
|
inline |
Performs bitblock OR operation test.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 5882 of file bmfunc.h.
References bm::bit_block_or_any(), bm::bit_is_all_zero(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.
Referenced by bm::combine_any_operation_with_block().
|
inline |
Performs bitblock OR operation and calculates bitcount of the result.
src1 | - first bit block. |
src2 | - second bit block. |
Definition at line 5845 of file bmfunc.h.
References bm::bit_block_count(), bm::bit_block_or_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.
Referenced by bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_OR().
|
inline |
bitblock SUB operation.
dst | - destination block. |
src | - source block. |
Definition at line 6345 of file bmfunc.h.
References bm::bit_block_sub(), BM_ASSERT, IS_FULL_BLOCK, and IS_VALID_ADDR.
|
inline |
Performs bitblock test of SUB operation.
src1 | - first bit block. |
src2 | - second bit block |
Definition at line 5810 of file bmfunc.h.
References bm::bit_block_sub_any(), bm::bit_is_all_zero(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.
Referenced by bm::combine_any_operation_with_block().
|
inline |
Performs bitblock SUB operation and calculates bitcount of the result.
src1 | - first bit block. |
src2 | - second bit block |
Definition at line 5755 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 >::get_bit_block_COUNT_SUB_AB(), and bm::serial_stream_iterator< DEC >::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 5792 of file bmfunc.h.
References bm::bit_operation_sub_count().
|
inline |
bitblock XOR operation.
dst | - destination block. |
src | - source block. |
Definition at line 6474 of file bmfunc.h.
References bm::bit_block_xor(), BM_ASSERT, and IS_VALID_ADDR.
|
inline |
Performs bitblock XOR operation test.
src1 | - bit block start ptr |
src2 | - second bit block ptr |
Definition at line 6545 of file bmfunc.h.
References bm::bit_block_xor_any(), bm::bit_is_all_zero(), and IS_EMPTY_BLOCK.
Referenced by bm::combine_any_operation_with_block().
|
inline |
Performs bitblock XOR operation and calculates bitcount of the result.
src1 | - bit block start ptr |
src1_end | - bit block end ptr |
src2 | - second bit block |
Definition at line 6513 of file bmfunc.h.
References bm::bit_block_count(), bm::bit_block_xor_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.
Referenced by bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_XOR().
unsigned bm::bit_scan_reverse | ( | T | value | ) |
Returns BSR value
Definition at line 172 of file bmfunc.h.
References bm::bit_scan_reverse32(), and BM_ASSERT.
Referenced by bm::bit_find_last(), bm::sparse_vector< unsigned, bm::bvector<> >::insert_value_no_null(), and bm::sparse_vector< unsigned, bm::bvector<> >::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 3733 of file bmfunc.h.
References BM_ASSERT.
Referenced by bm::bvector<>::compare().
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 483 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 461 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 |
offs | - bit address offset to add (0 - default) |
Definition at line 506 of file bmfunc.h.
References bm::word_bitcount64().
Referenced by bm::bitscan(), and bm::bitscan_wave().
|
inline |
Unpacks word wave (Nx 32-bit words)
w_ptr | - pointer on wave start |
bits | - pointer on the result array |
Definition at line 7491 of file bmfunc.h.
References bm::bitscan_popcnt(), and bm::bitscan_popcnt64().
Referenced by bm::for_each_bit_blk(), and bm::bvector< Alloc >::enumerator::go_to().
|
inline |
Init block with 000111000 pattren based on digest.
block | - Bit block [out] |
digest | - digest (used for block initialization) |
Definition at line 672 of file bmfunc.h.
References bm::set_block_digest_wave_size, and VECT_BLOCK_SET_DIGEST.
Referenced by bm::aggregator< bvector_type >::process_bit_blocks_and().
|
inline |
Compute digest for 64 non-zero areas.
block | - Bit block |
Definition at line 702 of file bmfunc.h.
References bm::set_block_digest_wave_size, and VECT_IS_DIGEST_ZERO.
Referenced by bm::serializer< bvector_type >::find_bit_best_encoding(), bm::aggregator< bvector_type >::process_bit_blocks_and(), bm::aggregator< bvector_type >::process_shift_right_and(), and bm::update_block_digest0().
|
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 657 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 2803 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::deserializer< typename SV::bvector_type, bm::decoder >::decode_bit_block(), and bm::serial_stream_iterator< DEC >::get_inv_arr().
|
inline |
|
inline |
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 634 of file bmfunc.h.
References BM_ASSERT, and bm::set_block_digest_pos_shift.
Referenced by bm::check_zero_digest(), and bm::aggregator< bvector_type >::process_bit_blocks_and().
void bm::for_each_bit_blk | ( | const bm::word_t * | block, |
SIZE_TYPE | offset, | ||
Func & | bit_functor | ||
) |
for-each visitor, calls a special visitor functor for each 1 bit group
block | - bit block buffer pointer |
offset | - global block offset (number of bits) |
bit_functor | - functor must support .add_bits(offset, bits_ptr, size) |
Definition at line 1660 of file bmalgo_impl.h.
References bm::bitscan_wave(), bm::gap_max_bits, IS_FULL_BLOCK, bm::set_bitscan_wave_size, and bm::set_block_size.
|
inline |
Returns "true" if all bits in the block are 1.
Definition at line 4760 of file bmfunc.h.
References bm::all_bits_mask, BMRESTRICT, bm::set_block_size, and VECT_IS_ONE_BLOCK.
Referenced by bm::check_block_one(), and bm::aggregator< bvector_type >::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 2835 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 2790 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::deserializer< typename SV::bvector_type, bm::decoder >::deserialize(), bm::serial_stream_iterator< DEC >::get_arr_bit(), bm::deseriaizer_base< bm::decoder >::read_bic_arr(), and bm::bvector<>::set().
|
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 2882 of file bmfunc.h.
References bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::gap_and_to_bitset(), and bm::gap_sub_to_bitset().
BMFORCEINLINE unsigned bm::test_bit | ( | const unsigned * | block, |
unsigned | bitpos | ||
) |
Test 1 bit in a block.
Definition at line 2817 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
void bm::tmatrix_distance | ( | const T | tmatrix[BPC][BPS], |
unsigned | distance[BPC][BPC] | ||
) |
Compute pairwise Row x Row Humming distances on plains(rows) of the transposed bit block.
tmatrix | - bit-block transposition matrix (bit-plains) |
distance | - pairwise NxN Humming distance matrix (diagonal is popcnt) |
Definition at line 315 of file bmtrans.h.
References bm::bit_block_count(), and BM_INCWORD_BITCOUNT.
Referenced by bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::compute_distance_matrix().
|
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 743 of file bmfunc.h.
References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::calc_block_digest0(), bm::set_block_digest_wave_size, VECT_IS_DIGEST_ZERO, and bm::word_bitcount64().
Referenced by bm::aggregator< bvector_type >::process_gap_blocks_and(), bm::aggregator< bvector_type >::process_gap_blocks_sub(), and bm::aggregator< bvector_type >::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 619 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 195 of file bmfunc.h.
Referenced by bm::bit_block_calc_count_range(), bm::bit_block_calc_count_to(), bm::bit_convert_to_arr(), bm::bit_count_change(), bm::bit_find_first_if_1(), bm::bit_find_rank(), bm::bitscan_popcnt(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_AND(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_OR(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_SUB_AB(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_SUB_BA(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_XOR(), and bm::sparse_vector_scanner< SV >::prepare_and_sub_aggregator().
BMFORCEINLINE unsigned bm::word_bitcount64 | ( | bm::id64_t | x | ) |
Function calculates number of 1 bits in 64-bit word.
Definition at line 224 of file bmfunc.h.
Referenced by bm::bit_block_and(), bm::bit_block_and_2way(), bm::bit_block_and_5way(), bm::bit_block_calc_count_to(), bm::bit_block_count(), bm::bit_block_shift_r1_and(), bm::bit_block_sub(), bm::bit_block_sub_2way(), bm::bit_find_first(), bm::bit_find_first_if_1(), bm::bit_find_rank(), bm::bitscan_popcnt64(), bm::serializer< bvector_type >::encode_bit_digest(), bm::serializer< bvector_type >::find_bit_best_encoding(), bm::deseriaizer_base< bm::decoder >::read_digest0_block(), bm::update_block_digest0(), and bm::word_select64_bitscan().
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 2929 of file bmfunc.h.
References bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.
Referenced by bm::gap_xor_to_bitset().