Collaboration diagram for BIT functions:

Data Structures
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...
struct	bm::all_set< T >
	Structure carries pointer on bit block with all bits 1. More...
Functions
BMFORCEINLINE bm::id_t	bm::word_bitcount (bm::id_t w)
template<typename T >
int	bm::wordcmp0 (T w1, T w2)
	Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes.
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.
BMFORCEINLINE void	bm::set_bit (unsigned *dest, unsigned bitpos)
	Set 1 bit in a block.
BMFORCEINLINE unsigned	bm::test_bit (const unsigned *block, unsigned bitpos)
	Test 1 bit in a block.
void	bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
	Sets bits to 1 in the bitblock.
void	bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
	SUB (AND NOT) bit interval to 1 in the bitblock.
void	bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
	XOR bit interval to 1 in the bitblock.
template<typename T >
bm::id_t	bm::gap_bitset_and_count (const unsigned block, const T buf)
	Compute bitcount of bit block AND masked by GAP block.
template<typename T >
bm::id_t	bm::gap_bitset_and_any (const unsigned block, const T buf)
	Bitcount test of bit block AND masked by GAP block.
template<typename T >
bm::id_t	bm::gap_bitset_sub_count (const unsigned block, const T buf)
	Compute bitcount of bit block SUB masked by GAP block.
template<typename T >
bm::id_t	bm::gap_bitset_sub_any (const unsigned block, const T buf)
	Compute bitcount test of bit block SUB masked by GAP block.
template<typename T >
bm::id_t	bm::gap_bitset_xor_count (const unsigned block, const T buf)
	Compute bitcount of bit block XOR masked by GAP block.
template<typename T >
bm::id_t	bm::gap_bitset_xor_any (const unsigned block, const T buf)
	Compute bitcount test of bit block XOR masked by GAP block.
template<typename T >
bm::id_t	bm::gap_bitset_or_count (const unsigned block, const T buf)
	Compute bitcount of bit block OR masked by GAP block.
template<typename T >
bm::id_t	bm::gap_bitset_or_any (const unsigned block, const T buf)
	Compute bitcount test of bit block OR masked by GAP block.
void	bm::bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value)
	Bitblock memset operation.
template<typename T >
int	bm::bitcmp (const T buf1, const T buf2, unsigned len)
	Lexicographical comparison of BIT buffers.
bm::id_t	bm::bit_block_calc_count (const bm::word_t block, const bm::word_t block_end)
	Bitcount for bit string.
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_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.
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.
void	bm::bit_block_copy (bm::word_t BMRESTRICT dst, const bm::word_t BMRESTRICT src)
	Bitblock copy operation.
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.
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.
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.
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.
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.
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.
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.
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.
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.
bm::word_t *	bm::bit_operation_and (bm::word_t BMRESTRICT dst, const bm::word_t BMRESTRICT src)
	bitblock AND operation.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
bm::word_t *	bm::bit_operation_sub (bm::word_t BMRESTRICT dst, const bm::word_t BMRESTRICT src)
	bitblock SUB operation.
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.
bm::word_t *	bm::bit_operation_xor (bm::word_t BMRESTRICT dst, const bm::word_t BMRESTRICT src)
	bitblock XOR operation.
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.
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.
template<class T >
unsigned	bm::bit_count_nonzero_size (const T *blk, unsigned data_size)
	Inspects block for full zero words.
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.
template<typename T , typename F >
void	bm::bit_for_each_4 (T w, F &func)
	Templated algorithm to unpacks octet based word into list of ON bit indexes.
template<typename T , typename F >
void	bm::bit_for_each (T w, F &func)
	Templated algorithm to unpacks word into list of ON bit indexes.
template<typename T , typename B >
unsigned	bm::bit_list_4 (T w, B *bits)
	Unpacks word into list of ON bit indexes (quad-bit based)
template<typename T , typename B >
unsigned	bm::bit_list (T w, B *bits)
	Unpacks word into list of ON bit indexes.
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.
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.
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.
template<typename T , unsigned BPC, unsigned BPS>
void	bm::bit_iblock_make_pcv (const unsigned distance[BPC][BPC], unsigned char *pc_vector)
	!< ibpc limiter

Detailed Description

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

Function Documentation

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

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

Referenced by bm::compute_tmatrix_rstat().

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

References bm::set_block_size, and VECT_AND_ARR.

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

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

Referenced by bm::bit_operation_and_any().

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

References VECT_BITCOUNT_AND.

Referenced by bm::bit_operation_and_count().

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

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

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

References VECT_BITCOUNT.

Referenced by bm::bit_operation_or_count(), bm::bit_operation_sub_count(), bm::bit_operation_xor_count(), bm::blocks_manager< Alloc >::block_bitcount(), bm::combine_count_operation_with_block(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_A(), print_stat(), and bm::tmatrix_distance().

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

Returns:: number of 1-0, 0-1 transitions

Definition at line 2875 of file bmfunc.h.

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

Referenced by bm::blocks_manager< Alloc >::block_count_change_func::block_count(), and bm::serializer< BV >::serialize().

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 addresses are aligned.

Definition at line 2961 of file bmfunc.h.

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

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

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

References bm::set_block_size, and VECT_COPY_BLOCK.

Referenced by bm::bvector< Alloc >::combine_operation_with_block(), bm::blocks_manager< Alloc >::copy_bit_block(), bm::blocks_manager< Alloc >::copy_block(), bm::blocks_manager< Alloc >::deoptimize_block(), bm::random_subset< BV >::get_subset(), and bm::blocks_manager< Alloc >::block_copy_func::operator()().

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

References bm::set_block_size, and VECT_OR_ARR.

Referenced by bm::bit_operation_or().

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

Referenced by bm::bit_operation_or_any().

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

References VECT_BITCOUNT_OR.

Referenced by bm::bit_operation_or_count().

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

Bitblock memset operation.

Parameters:

dst	- destination block.
value	- value to set.

Definition at line 2137 of file bmfunc.h.

References bm::set_block_size.

Referenced by bm::blocks_manager< Alloc >::check_allocate_block(), bm::deserializer< BV, DEC >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), bm::gap_convert_to_bitset(), bm::gap_convert_to_bitset_l(), bm::serial_stream_iterator< DEC >::get_arr_bit(), bm::serial_stream_iterator< DEC >::get_bit_block_ASSIGN(), bm::random_subset< BV >::get_subset(), bm::blocks_manager< Alloc >::make_bit_block(), bm::blocks_manager< Alloc >::block_zero_func::operator()(), and bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::transpose().

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

References bm::set_block_size, and VECT_SUB_ARR.

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

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

Referenced by bm::bit_operation_sub_any().

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

References VECT_BITCOUNT_SUB.

Referenced by bm::bit_operation_sub_count().

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

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

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

Referenced by bm::bit_operation_xor_any().

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

References VECT_BITCOUNT_XOR.

Referenced by bm::bit_operation_xor_count().

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

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

Referenced by bm::random_subset< BV >::get_random_subset(), bm::random_subset< BV >::get_subset(), and bm::serializer< BV >::serialize().

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

template<class T >

unsigned bm::bit_count_nonzero_size	(	const T *	blk,
		unsigned	data_size
	)

Inspects block for full zero words.

Parameters:

data	- bit block pointer
data_size	- data size

Returns:: size of all non-zero words

Definition at line 4395 of file bmfunc.h.

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

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

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

Referenced by bm::bvector< Alloc >::check_or_next(), bm::bvector< Alloc >::check_or_next_extract(), and bm::serializer< BV >::serialize().

template<typename T , typename F >

void bm::bit_for_each	(	T	w,
		F &	func
	)

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

Parameters:

w	- value
func	- bit functor

Definition at line 4573 of file bmfunc.h.

Referenced by bm::bit_list().

template<typename T , typename F >

void bm::bit_for_each_4	(	T	w,
		F &	func
	)

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

Parameters:

w	- value
func	- bit functor

Definition at line 4503 of file bmfunc.h.

Referenced by bm::bit_convert_to_arr(), and bm::bit_list_4().

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 418 of file bmtrans.h.

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

template<typename T >

void bm::bit_invert	(	T *	start,
		T *	end
	)

Function inverts block of bits

Definition at line 3092 of file bmfunc.h.

References VECT_INVERT_ARR.

Referenced by bm::blocks_manager< Alloc >::block_invert_func::operator()().

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

Referenced by bm::bit_operation_or_any(), bm::bit_operation_sub_any(), bm::bit_operation_xor_any(), bm::combine_any_operation_with_block(), bm::bvector< Alloc >::compare(), bm::blocks_manager< Alloc >::block_any_func::operator()(), and bm::blocks_manager< Alloc >::block_opt_func::operator()().

template<typename T , typename B >

unsigned bm::bit_list	(	T	w,
		B *	bits
	)

Unpacks word into list of ON bit indexes.

Parameters:

w	- value
bits	- pointer on the result array

Returns:: number of bits in the list

Definition at line 4711 of file bmfunc.h.

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

template<typename T , typename B >

unsigned bm::bit_list_4	(	T	w,
		B *	bits
	)

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

Parameters:

w	- value
bits	- pointer on the result array

Returns:: number of bits in the list

Definition at line 4696 of file bmfunc.h.

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

Referenced by bm::bvector< Alloc >::enumerator::go_up(), bm::random_subset< BV >::process_word(), and bm::bvector< Alloc >::enumerator::search_in_bitblock().

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

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

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

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

References bm::bit_block_and_any(), and IS_EMPTY_BLOCK.

Referenced by bm::combine_any_operation_with_block().

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

References bm::bit_block_and_count(), and IS_EMPTY_BLOCK.

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

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

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

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

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

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

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

Referenced by bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_OR().

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

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

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

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

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

References bm::bit_block_calc_count(), bm::bit_block_sub_count(), and IS_EMPTY_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().

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

References bm::bit_operation_sub_count().

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

References bm::bit_block_xor(), and IS_VALID_ADDR.

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

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	- first bit block.
src2	- second bit block.

Returns:: non zero value if there are bits

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

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	- first bit block.
src2	- second bit block.

Returns:: bitcount value

Definition at line 4341 of file bmfunc.h.

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

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

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

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

template<typename T >

bm::id_t bm::gap_bitset_and_any	(	const unsigned *	block,
		const T *	buf
	)

Bitcount test of bit block AND masked by GAP block.

Parameters:

dest	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Definition at line 1848 of file bmfunc.h.

References bm::bit_block_any_range().

Referenced by bm::combine_any_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_and_count	(	const unsigned *	block,
		const T *	buf
	)

Compute bitcount of bit block AND masked by GAP block.

Parameters:

dest	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Definition at line 1817 of file bmfunc.h.

References bm::bit_block_calc_count_range().

Referenced by bm::combine_count_and_operation_with_block(), and bm::combine_count_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_or_any	(	const unsigned *	block,
		const T *	buf
	)

Compute bitcount test of bit block OR masked by GAP block.

Parameters:

dest	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Definition at line 2086 of file bmfunc.h.

References bm::bit_block_any_range().

Referenced by bm::combine_any_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_or_count	(	const unsigned *	block,
		const T *	buf
	)

Compute bitcount of bit block OR masked by GAP block.

Parameters:

dest	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Definition at line 2039 of file bmfunc.h.

References bm::bit_block_calc_count_range().

Referenced by bm::combine_count_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_sub_any	(	const unsigned *	block,
		const T *	buf
	)

Compute bitcount test of bit block SUB masked by GAP block.

Parameters:

dest	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Definition at line 1920 of file bmfunc.h.

References bm::bit_block_any_range().

Referenced by bm::combine_any_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_sub_count	(	const unsigned *	block,
		const T *	buf
	)

Compute bitcount of bit block SUB masked by GAP block.

Parameters:

dest	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Definition at line 1887 of file bmfunc.h.

References bm::bit_block_calc_count_range().

Referenced by bm::combine_count_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_xor_any	(	const unsigned *	block,
		const T *	buf
	)

Compute bitcount test of bit block XOR masked by GAP block.

Parameters:

dest	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Definition at line 1996 of file bmfunc.h.

References bm::bit_block_any_range().

Referenced by bm::combine_any_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_xor_count	(	const unsigned *	block,
		const T *	buf
	)

Compute bitcount of bit block XOR masked by GAP block.

Parameters:

dest	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Definition at line 1958 of file bmfunc.h.

References bm::bit_block_calc_count_range().

Referenced by bm::combine_count_operation_with_block().

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

References bm::all_bits_mask.

Referenced by bm::blocks_manager< Alloc >::is_block_one(), and bm::blocks_manager< Alloc >::block_opt_func::operator()().

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

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

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

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

Set 1 bit in a block.

Definition at line 1472 of file bmfunc.h.

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

Referenced by bm::deserializer< BV, DEC >::deserialize(), bm::serial_stream_iterator< DEC >::get_arr_bit(), and bm::random_subset< BV >::get_random_array().

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

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

Test 1 bit in a block.

Definition at line 1485 of file bmfunc.h.

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

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

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 352 of file bmtrans.h.

References bm::bit_block_calc_count().

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

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

Returns bit count

Definition at line 176 of file bmfunc.h.

Referenced by 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::random_subset< BV >::process_word().

template<typename T >

int bm::wordcmp	(	T	a,
		T	b
	)

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

Parameters:

buf1	- First word.
buf2	- Second word.

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

Definition at line 382 of file bmfunc.h.

template<typename T >

int bm::wordcmp0	(	T	w1,
		T	w2
	)

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

Parameters:

buf1	- First word.
buf2	- Second word.

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

Definition at line 352 of file bmfunc.h.

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

Data Structures

Functions

Detailed Description

Function Documentation