BitMagicC++Library
Data Structures | Macros | Functions
BIT functions

Data Structures

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

Macros

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

Functions

BMFORCEINLINE bm::id_t bm::word_bitcount (bm::id_t w)
 
BMFORCEINLINE int bm::word_bitcount64 (bm::id64_t x)
 
BMFORCEINLINE bm::id_t bm::word_trailing_zeros (bm::id_t w)
 
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...
 
BMFORCEINLINE void bm::set_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_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)
 
bm::id_t bm::bit_block_calc_count_change (const bm::word_t *block, const bm::word_t *block_end, unsigned *bit_count)
 
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)
 
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, T *end)
 
bool bm::is_bits_one (const bm::wordop_t *start, const bm::wordop_t *end)
 Returns "true" if all bits in the block are 1. More...
 
bool bm::bit_is_all_zero (const bm::wordop_t *start, const bm::wordop_t *end)
 Returns "true" if all bits in the block are 0. 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_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...
 
unsigned bm::bit_block_and_count (const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *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 *src1_end, 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 src1_end, 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 src1_end, 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 src1_end, 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 src1_end, 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 *src1_end, 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 src1_end, const bm::word_t *BMRESTRICT src2)
 Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
bm::word_tbm::bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock AND operation. More...
 
bm::id_t bm::bit_operation_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, 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 src1_end, 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 src1_end, 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 src1_end, 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 src1_end, 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 src1_end, 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 src1_end, const bm::word_t *BMRESTRICT src2)
 Performs bitblock OR operation test. More...
 
void 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...
 
bm::word_tbm::bit_operation_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Block OR operation. Makes analysis if block is 0 or FULL. More...
 
void 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::word_tbm::bit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock SUB operation. More...
 
void 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...
 
bm::word_tbm::bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock XOR operation. More...
 
bm::id_t bm::bit_operation_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, 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 src1_end, 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...
 
int bm::bit_find_in_block (const bm::word_t *data, unsigned nbit, bm::id_t *prev)
 Searches for the next 1 bit in the BIT block. 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_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 offs=0)
 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...
 
template<typename T , typename B >
unsigned bm::bit_list (T w, B *bits)
 Unpacks word into list of ON bit indexes. More...
 
bm::set_representation bm::best_representation (unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size)
 Choose best representation for a bit-block. More...
 
template<typename T >
bm::bit_convert_to_arr (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len, unsigned mask=0)
 Convert bit block into an array of ints corresponding to 1 bits. More...
 
unsigned short bm::bitscan_wave (const bm::word_t *w_ptr, unsigned char *bits)
 Unpacks word wave (2x 32-bit words) More...
 
template<class Func >
void bm::for_each_bit_blk (const bm::word_t *block, bm::id_t 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...
 

Detailed Description

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

Macro Definition Documentation

◆ BM_INCWORD_BITCOUNT

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

Function Documentation

◆ best_representation()

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

Choose best representation for a bit-block.

Definition at line 5036 of file bmfunc.h.

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

Referenced by bm::compute_tmatrix_rstat().

◆ bit_block_and()

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

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

Parameters
dst- destination block.
src- source block.

Definition at line 3764 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_AND_ARR.

Referenced by bm::bit_operation_and(), and bm::serial_stream_iterator< DEC >::get_bit_block_AND().

◆ bit_block_and_any()

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

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

Parameters
src1- first bit block
src1_end- first bit block end
src2- second bit block

Definition at line 3848 of file bmfunc.h.

Referenced by bm::bit_operation_and_any().

◆ bit_block_and_count()

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

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

Parameters
src1- first bit block
src1_end- first bit block end
src2- second bit block

Definition at line 3798 of file bmfunc.h.

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

Referenced by bm::bit_operation_and_count().

◆ bit_block_any_range()

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

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

Definition at line 3327 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_or_any(), bm::gap_bitset_sub_any(), and bm::gap_bitset_xor_any().

◆ bit_block_calc_count()

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

Bitcount for bit string.

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

Definition at line 2912 of file bmfunc.h.

References bm::bitcount64_4way(), BM_ASSERT, BM_INCWORD_BITCOUNT, 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::serial_stream_iterator< DEC >::get_bit_block_COUNT_A(), and bm::tmatrix_distance().

◆ bit_block_calc_count_change()

bm::id_t bm::bit_block_calc_count_change ( const bm::word_t block,
const bm::word_t block_end,
unsigned *  bit_count 
)
inline

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

Parameters
bit_count- OUT total number of bits ON
block- bit-block start pointer
block_end- bit-block end pointer
Returns
number of 1-0, 0-1 transitions

Definition at line 3053 of file bmfunc.h.

References bm::bit_count_change32(), BM_ASSERT, bm::sse2_bit_block_calc_count_change(), bm::sse4_bit_block_calc_count_change(), and bm::word_bitcount64().

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

◆ bit_block_calc_count_range()

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

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

Definition at line 3150 of file bmfunc.h.

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

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

◆ bit_block_calc_count_to()

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

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

Definition at line 3215 of file bmfunc.h.

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

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

◆ bit_block_copy()

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

Bitblock copy operation.

Parameters
dst- destination block.
src- source block.

Definition at line 3744 of file bmfunc.h.

References bm::set_block_size, and VECT_COPY_BLOCK.

Referenced by bm::bvector<>::combine_operation(), and bm::random_subset< BV >::sample().

◆ bit_block_or()

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

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

Parameters
dst- destination block.
src- source block.

Definition at line 4378 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_ARR.

Referenced by bm::bit_operation_or().

◆ bit_block_or_any()

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

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

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

Definition at line 4088 of file bmfunc.h.

Referenced by bm::bit_operation_or_any().

◆ bit_block_or_count()

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

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

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

Definition at line 4039 of file bmfunc.h.

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

Referenced by bm::bit_operation_or_count().

◆ bit_block_rotate_left_1()

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

Cyclic rotation of bit-block left by 1 bit

Definition at line 3277 of file bmfunc.h.

References bm::set_block_size.

◆ bit_block_rotate_left_1_unr()

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

Unrolled cyclic rotation of bit-block left by 1 bit

Definition at line 3292 of file bmfunc.h.

References bm::set_block_size.

◆ bit_block_set()

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

◆ bit_block_sub()

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

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

Parameters
dst- destination block.
src- source block.

Definition at line 4474 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_SUB_ARR.

Referenced by bm::bit_operation_sub(), and bm::serial_stream_iterator< DEC >::get_bit_block_SUB().

◆ bit_block_sub_any()

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

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

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

Definition at line 4009 of file bmfunc.h.

Referenced by bm::bit_operation_sub_any().

◆ bit_block_sub_count()

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

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

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

Definition at line 3960 of file bmfunc.h.

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

Referenced by bm::bit_operation_sub_count().

◆ bit_block_xor()

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

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

Parameters
dst- destination block.
src- source block.

Definition at line 4570 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_XOR_ARR.

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

◆ bit_block_xor_any()

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

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

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

Definition at line 3929 of file bmfunc.h.

Referenced by bm::bit_operation_xor_any().

◆ bit_block_xor_count()

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

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

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

Definition at line 3879 of file bmfunc.h.

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

Referenced by bm::bit_operation_xor_count().

◆ bit_convert_to_arr()

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

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

Definition at line 5071 of file bmfunc.h.

References bm::bitscan_popcnt(), and BMRESTRICT.

Referenced by bm::random_subset< BV >::sample(), and bm::serializer< bvector_type >::serialize().

◆ bit_count_change()

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

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

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

Definition at line 2972 of file bmfunc.h.

References bm::word_bitcount().

◆ bit_count_nonzero_size()

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

Inspects block for full zero words.

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

Definition at line 4704 of file bmfunc.h.

References BM_ASSERT.

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

◆ bit_find_in_block()

int bm::bit_find_in_block ( const bm::word_t data,
unsigned  nbit,
bm::id_t prev 
)
inline

Searches for the next 1 bit in the BIT block.

Parameters
data- BIT buffer
nbit- bit index to start checking from
prev- returns previously checked value

Definition at line 4765 of file bmfunc.h.

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

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

◆ bit_for_each()

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

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

Parameters
w- value
func- bit functor

Definition at line 4878 of file bmfunc.h.

Referenced by bm::bit_list().

◆ bit_for_each_4()

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

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

Parameters
w- value
func- bit functor

Definition at line 4808 of file bmfunc.h.

References BM_ASSERT.

Referenced by bm::bit_list_4().

◆ bit_iblock_make_pcv()

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

!< ibpc limiter

Make a compression descriptor vector for bit-plains

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

Definition at line 419 of file bmtrans.h.

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

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

◆ bit_invert()

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

Function inverts block of bits

Definition at line 3392 of file bmfunc.h.

References VECT_INVERT_ARR.

◆ bit_is_all_zero()

bool bm::bit_is_all_zero ( const bm::wordop_t start,
const bm::wordop_t end 
)
inline

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

Definition at line 3438 of file bmfunc.h.

References VECT_IS_ZERO_BLOCK.

Referenced by bm::bit_operation_or_any(), bm::bit_operation_sub_any(), bm::bit_operation_xor_any(), bm::combine_any_operation_with_block(), and bm::bvector<>::compare().

◆ bit_list()

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

Unpacks word into list of ON bit indexes.

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

Definition at line 5023 of file bmfunc.h.

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

Referenced by bm::random_subset< BV >::sample().

◆ bit_list_4()

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

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

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

Definition at line 4949 of file bmfunc.h.

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

Referenced by bm::random_subset< BV >::sample().

◆ bit_operation_and()

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

bitblock AND operation.

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

Definition at line 4120 of file bmfunc.h.

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

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

◆ bit_operation_and_any()

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

Performs bitblock AND operation test.

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

Definition at line 4208 of file bmfunc.h.

References bm::bit_block_and_any(), and IS_EMPTY_BLOCK.

Referenced by bm::combine_any_operation_with_block().

◆ bit_operation_and_count()

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

Performs bitblock AND operation and calculates bitcount of the result.

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

Definition at line 4185 of file bmfunc.h.

References bm::bit_block_and_count(), and IS_EMPTY_BLOCK.

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

◆ bit_operation_or()

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

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

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

Definition at line 4416 of file bmfunc.h.

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

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

◆ bit_operation_or_any()

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

Performs bitblock OR operation test.

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

Definition at line 4346 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

◆ bit_operation_or_count()

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

Performs bitblock OR operation and calculates bitcount of the result.

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

Definition at line 4314 of file bmfunc.h.

References bm::bit_block_calc_count(), bm::bit_block_or_count(), and IS_EMPTY_BLOCK.

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

◆ bit_operation_sub()

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

bitblock SUB operation.

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

Definition at line 4514 of file bmfunc.h.

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

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

◆ bit_operation_sub_any()

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

Performs bitblock test of SUB operation.

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

Definition at line 4284 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

◆ bit_operation_sub_count()

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

Performs bitblock SUB operation and calculates bitcount of the result.

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

Definition at line 4233 of file bmfunc.h.

References bm::bit_block_calc_count(), bm::bit_block_sub_count(), and IS_EMPTY_BLOCK.

Referenced by bm::operation_functions< T >::bit_operation_count(), 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().

◆ bit_operation_sub_count_inv()

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

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

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

Definition at line 4263 of file bmfunc.h.

References bm::bit_operation_sub_count().

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

◆ bit_operation_xor()

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

bitblock XOR operation.

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

Definition at line 4610 of file bmfunc.h.

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

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

◆ bit_operation_xor_any()

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

Performs bitblock XOR operation test.

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

Definition at line 4675 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

◆ bit_operation_xor_count()

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

Performs bitblock XOR operation and calculates bitcount of the result.

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

Definition at line 4649 of file bmfunc.h.

References bm::bit_block_calc_count(), bm::bit_block_xor_count(), and IS_EMPTY_BLOCK.

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

◆ bitcmp()

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

Lexicographical comparison of BIT buffers.

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

Definition at line 2675 of file bmfunc.h.

References BM_ASSERT.

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

◆ bitscan_popcnt()

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

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

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

Definition at line 4965 of file bmfunc.h.

References bm::word_bitcount().

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

◆ bitscan_popcnt64()

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

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

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

Definition at line 4987 of file bmfunc.h.

References bm::word_bitcount64().

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

◆ bitscan_wave()

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

Unpacks word wave (2x 32-bit words)

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

Definition at line 5539 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().

◆ for_each_bit_blk()

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

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

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

Definition at line 1664 of file bmalgo_impl.h.

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

Referenced by bm::for_each_bit().

◆ is_bits_one()

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

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

Definition at line 3413 of file bmfunc.h.

References bm::all_bits_mask, and VECT_IS_ONE_BLOCK.

◆ or_bit_block()

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

Sets bits to 1 in the bitblock.

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

Definition at line 1682 of file bmfunc.h.

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

Referenced by bm::bvector<>::combine_operation(), and bm::gap_add_to_bitset().

◆ set_bit()

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

◆ sub_bit_block()

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

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

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

Definition at line 1744 of file bmfunc.h.

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

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

◆ test_bit()

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

Test 1 bit in a block.

Definition at line 1665 of file bmfunc.h.

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

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

◆ tmatrix_distance()

template<typename T , unsigned BPC, unsigned BPS>
void bm::tmatrix_distance ( const T  tmatrix[BPC][BPS],
unsigned  distance[BPC][BPC] 
)

Compute pairwise Row x Row Humming distances on plains(rows) of the transposed bit block.

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

Definition at line 353 of file bmtrans.h.

References bm::bit_block_calc_count(), and BM_INCWORD_BITCOUNT.

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

◆ word_bitcount()

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

◆ word_bitcount64()

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

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

Definition at line 154 of file bmfunc.h.

Referenced by bm::bit_block_calc_count_change(), bm::bit_block_calc_count_to(), and bm::bitscan_popcnt64().

◆ word_trailing_zeros()

BMFORCEINLINE bm::id_t bm::word_trailing_zeros ( bm::id_t  w)

Returns number of trailing zeros

Definition at line 205 of file bmfunc.h.

Referenced by bm::bit_find_in_block().

◆ wordcmp()

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

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

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

Definition at line 374 of file bmfunc.h.

◆ wordcmp0()

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

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

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

Definition at line 344 of file bmfunc.h.

◆ xor_bit_block()

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

XOR bit interval to 1 in the bitblock.

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

Definition at line 1806 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().