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

struct	bm::all_set< T >
	Structure carries pointer on bit block with all bits 1. More...

struct	bm::block_waves_xor_descr
	Structure to compute XOR gap-count profile by sub-block waves. More...

Functions
template<typename Func , typename SIZE_TYPE >
int	bm::for_each_bit_blk (const bm::word_t *block, SIZE_TYPE offset, Func &bit_functor)
	for-each visitor, calls a visitor functor for each 1 bit group More...

template<typename Func , typename SIZE_TYPE >
int	bm::for_each_bit_blk (const bm::word_t *block, SIZE_TYPE offset, unsigned left, unsigned right, Func &bit_functor)
	for-each range visitor, calls a visitor functor for each 1 bit group More...

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

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) noexcept
	Unpacks word into list of ON bit indexes. More...

template<typename T , typename B >
unsigned	bm::bit_list_4 (T w, B *bits) noexcept
	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) noexcept
	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) noexcept
	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) noexcept
	Unpacks 64-bit word into list of ON bit indexes using popcnt method. More...

template<typename B >
unsigned short	bm::bitscan_bsf (unsigned w, B *bits) noexcept
	Unpacks word into list of ON bits (BSF/__builtin_ctz) More...

template<typename B >
unsigned short	bm::bitscan_bsf64 (bm::id64_t w, B *bits) noexcept
	Unpacks word into list of ON bits (BSF/__builtin_ctz) More...

template<typename B >
unsigned short	bm::bitscan_popcnt64 (bm::id64_t w, B *bits, unsigned short offs) noexcept
	Unpacks 64-bit word into list of ON bit indexes using popcnt method. More...

template<typename V , typename B >
unsigned short	bm::bitscan (V w, B *bits) noexcept
	Templated Bitscan with dynamic dispatch for best type. More...

unsigned	bm::word_select64_linear (bm::id64_t w, unsigned rank) noexcept
	word find index of the rank-th bit set by bit-testing More...

unsigned	bm::word_select64_bitscan_popcnt (bm::id64_t w, unsigned rank) noexcept
	word find index of the rank-th bit set by bit-testing More...

unsigned	bm::word_select64_bitscan_tz (bm::id64_t w, unsigned rank) noexcept
	word find index of the rank-th bit set by bit-testing More...

unsigned	bm::word_select32_bitscan_popcnt (unsigned w, unsigned rank) noexcept
	word find index of the rank-th bit set by bit-testing More...

unsigned	bm::word_select32_bitscan_tz (unsigned w, unsigned rank) noexcept
	word find index of the rank-th bit set by bit-testing More...

unsigned	bm::word_select64 (bm::id64_t w, unsigned rank) noexcept
	word find index of the rank-th bit set by bit-testing More...

unsigned	bm::word_select32 (unsigned w, unsigned rank) noexcept
	word find index of the rank-th bit set by bit-testing More...

bm::id64_t	bm::widx_to_digest_mask (unsigned w_idx) noexcept
	Compute digest mask for word address in block. More...

bm::id64_t	bm::digest_mask (unsigned from, unsigned to) noexcept
	Compute digest mask for [from..to] positions. More...

bool	bm::check_zero_digest (bm::id64_t digest, unsigned bitpos_from, unsigned bitpos_to) noexcept
	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) noexcept
	Init block with 000111000 pattren based on digest. More...

bm::id64_t	bm::calc_block_digest0 (const bm::word_t *const block) noexcept
	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) noexcept
	Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas) More...

void	bm::block_compact_by_digest (bm::word_t t_block, const bm::word_t block, bm::id64_t digest, bool zero_tail) noexcept
	Compact sub-blocks by digest (rank compaction) More...

void	bm::block_expand_by_digest (bm::word_t t_block, const bm::word_t block, bm::id64_t digest, bool zero_subs) noexcept
	expand sub-blocks by digest (rank expansion) More...

template<typename T >
int	bm::wordcmp0 (T w1, T w2) noexcept
	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) noexcept
	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 *start) noexcept
	Returns "true" if all bits in the block are 0. More...

void	bm::set_bit (unsigned *dest, unsigned bitpos) noexcept
	Set 1 bit in a block. More...

void	bm::clear_bit (unsigned *dest, unsigned bitpos) noexcept
	Set 1 bit in a block. More...

unsigned	bm::test_bit (const unsigned *block, unsigned bitpos) noexcept
	Test 1 bit in a block. More...

void	bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) noexcept
	Sets bits to 1 in the bitblock. More...

void	bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) noexcept
	SUB (AND NOT) bit interval to 1 in the bitblock. More...

void	bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) noexcept
	XOR bit interval to 1 in the bitblock. More...

void	bm::bit_block_set (bm::word_t *dst, bm::word_t value) noexcept
	Bitblock memset operation. More...

template<typename T >
int	bm::bitcmp (const T buf1, const T buf2, unsigned len) noexcept
	Lexicographical comparison of BIT buffers. More...

bool	bm::bit_find_first_diff (const bm::word_t blk1, const bm::word_t blk2, unsigned *pos) noexcept
	Find first bit which is different between two bit-blocks. More...

unsigned	bm::bit_count_min_unroll (const bm::word_t block, const bm::word_t block_end) noexcept
	Bitcount for bit block without agressive unrolling. More...

bm::id_t	bm::bit_block_count (const bm::word_t *block) noexcept
	Bitcount for bit block. More...

bm::id_t	bm::bit_block_count (const bm::word_t *const block, bm::id64_t digest) noexcept
	Bitcount for bit block. More...

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

unsigned	bm::bit_block_calc_change (const bm::word_t *block) noexcept

bool	bm::bit_block_is_all_one_range (const bm::word_t *const block, bm::word_t left, bm::word_t right) noexcept

template<bool LWA = false, bool RWA = false>
bm::id_t	bm::bit_block_calc_count_range (const bm::word_t *block, bm::word_t left, bm::word_t right) noexcept

bm::id_t	bm::bit_block_calc_count_to (const bm::word_t *block, bm::word_t right) noexcept

void	bm::bit_block_rotate_left_1 (bm::word_t *block) noexcept

void	bm::bit_block_rotate_left_1_unr (bm::word_t *block) noexcept
	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) noexcept
	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) noexcept
	Right bit-shift bitblock by 1 bit (reference) More...

bool	bm::bit_block_shift_r1_unr_min (bm::word_t block, bm::word_t empty_acc, bm::id64_t co_flag) noexcept
	Right bit-shift bitblock by 1 bit (minimum unroll) More...

bool	bm::bit_block_shift_r1_unr (bm::word_t block, bm::word_t empty_acc, bm::word_t co_flag) noexcept
	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) noexcept
	Left bit-shift bitblock by 1 bit (reference) More...

bool	bm::bit_block_shift_l1_unr_min (bm::word_t block, bm::word_t empty_acc, unsigned co_flag) noexcept
	Left bit-shift bitblock by 1 bit (minimum unroll) More...

bool	bm::bit_block_shift_l1_unr (bm::word_t block, bm::word_t empty_acc, bm::word_t co_flag) noexcept
	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) noexcept
	erase bit from position and shift the rest right with carryover More...

bool	bm::bit_block_shift_r1_and (bm::word_t block, bm::word_t co_flag, const bm::word_t mask_block, bm::id64_t *digest) noexcept
	Right bit-shift of bit-block by 1 bit (reference) + AND. More...

bool	bm::bit_block_shift_r1_and_unr (bm::word_t block, bm::word_t co_flag, const bm::word_t mask_block, bm::id64_t *digest) noexcept
	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) noexcept

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

bool	bm::is_bits_one (const bm::wordop_t *start) noexcept
	Returns "true" if all bits in the block are 1. More...

bool	bm::bit_block_find_interval_end (const bm::word_t block, unsigned nbit, unsigned pos) noexcept
	Searches for the last 1 bit in the 111 interval of a BIT block. More...

bool	bm::bit_block_find_interval_start (const bm::word_t block, unsigned nbit, unsigned pos) noexcept
	Searches for the first 1 bit in the 111 interval of a BIT block. More...

bool	bm::bit_block_find_prev (const bm::word_t block, unsigned nbit, unsigned pos) noexcept
	Reverse search for the previous 1 bit. More...

void	bm::bit_block_copy (bm::word_t dst, const bm::word_t src) noexcept
	Bitblock copy operation. More...

void	bm::bit_block_copy_unalign (bm::word_t dst, const bm::word_t src) noexcept
	Bitblock copy operation (unaligned src) More...

void	bm::bit_block_stream (bm::word_t dst, const bm::word_t src) noexcept
	Bitblock copy/stream operation. More...

void	bm::bit_block_stream_unalign (bm::word_t dst, const bm::word_t src) noexcept
	Bitblock copy/stream operation (unaligned src) More...

bm::id64_t	bm::bit_block_and (bm::word_t dst, const bm::word_t src) noexcept
	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 dst, const bm::word_t src, bm::id64_t digest) noexcept
	digest based bit-block AND More...

bm::id64_t	bm::bit_block_and_5way (bm::word_t dst, const bm::word_t src0, const bm::word_t src1, const bm::word_t src2, const bm::word_t *src3, bm::id64_t digest) noexcept
	digest based bit-block AND 5-way More...

bm::id64_t	bm::bit_block_and_3way (bm::word_t dst, const bm::word_t src1, const bm::word_t *src2, bm::id64_t digest) noexcept
	digest based bit-block AND More...

bm::id64_t	bm::bit_block_and_2way (bm::word_t dst, const bm::word_t src1, const bm::word_t *src2, bm::id64_t digest) noexcept
	digest based bit-block AND More...

bm::id64_t	bm::bit_block_init_and_2way (bm::word_t dst, const bm::word_t src1, const bm::word_t *src2, bm::id64_t digest) noexcept
	digest based bit-block AND (0 elements of digest will be zeroed) More...

bm::id64_t	bm::bit_block_and_or_2way (bm::word_t dst, const bm::word_t src1, const bm::word_t *src2, bm::id64_t digest) noexcept
	digest based bit-block AND - OR More...

unsigned	bm::bit_block_and_count (const bm::word_t src1, const bm::word_t src2) noexcept
	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) noexcept
	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 src1, const bm::word_t src2) noexcept
	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 src1, const bm::word_t src2) noexcept
	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 src1, const bm::word_t src2) noexcept
	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 src1, const bm::word_t src2) noexcept
	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) noexcept
	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 src1, const bm::word_t src2) noexcept
	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 dst, const bm::word_t src) noexcept
	bitblock AND operation. More...

bm::id_t	bm::bit_operation_and_count (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs bitblock AND operation and calculates bitcount of the result. More...

bm::id_t	bm::bit_operation_and_any (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs bitblock AND operation test. More...

bm::id_t	bm::bit_operation_sub_count (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs bitblock SUB operation and calculates bitcount of the result. More...

bm::id_t	bm::bit_operation_sub_count_inv (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs inverted bitblock SUB operation and calculates bitcount of the result. More...

bm::id_t	bm::bit_operation_sub_any (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs bitblock test of SUB operation. More...

bm::id_t	bm::bit_operation_or_count (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs bitblock OR operation and calculates bitcount of the result. More...

bm::id_t	bm::bit_operation_or_any (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs bitblock OR operation test. More...

bool	bm::bit_block_or (bm::word_t dst, const bm::word_t src) noexcept
	Plain bitblock OR operation. Function does not analyse availability of source and destination blocks. More...

bool	bm::bit_block_or_2way (bm::word_t dst, const bm::word_t src1, const bm::word_t *src2) noexcept
	2 way (target := source1 \| source2) bitblock OR operation. More...

bm::id64_t	bm::bit_block_xor_2way (bm::word_t dst, const bm::word_t src1, const bm::word_t *src2) noexcept
	2 way (target := source1 ^ source2) bitblock XOR operation. More...

bool	bm::bit_block_or_3way (bm::word_t dst, const bm::word_t src1, const bm::word_t *src2) noexcept
	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 dst, const bm::word_t src1, const bm::word_t src2, const bm::word_t src3, const bm::word_t *src4) noexcept
	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 dst, const bm::word_t src) noexcept
	Block OR operation. Makes analysis if block is 0 or FULL. More...

bm::id64_t	bm::bit_block_sub (bm::word_t dst, const bm::word_t src) noexcept
	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 dst, const bm::word_t src, bm::id64_t digest) noexcept
	digest based bitblock SUB (AND NOT) operation More...

bm::id64_t	bm::bit_block_sub_2way (bm::word_t dst, const bm::word_t src1, const bm::word_t *src2, bm::id64_t digest) noexcept
	digest based bitblock SUB (AND NOT) operation (3 operand) More...

bm::id64_t	bm::bit_block_sub_5way (bm::word_t dst, const bm::word_t src0, const bm::word_t src1, const bm::word_t src2, const bm::word_t *src3, bm::id64_t digest) noexcept
	digest based bit-block SUB 5-way More...

bm::id64_t	bm::bit_block_sub_3way (bm::word_t dst, const bm::word_t src0, const bm::word_t *src1, bm::id64_t digest) noexcept
	digest based bit-block SUB 3-way More...

bm::word_t *	bm::bit_operation_sub (bm::word_t dst, const bm::word_t src) noexcept
	bitblock SUB operation. More...

bm::id64_t	bm::bit_block_xor (bm::word_t dst, const bm::word_t src) noexcept
	Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks. More...

void	bm::bit_andnot_arr_ffmask (bm::word_t dst, const bm::word_t src) noexcept
	bitblock AND NOT with constant ~0 mask operation. More...

bm::word_t *	bm::bit_operation_xor (bm::word_t dst, const bm::word_t src) noexcept
	bitblock XOR operation. More...

bm::id_t	bm::bit_operation_xor_count (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs bitblock XOR operation and calculates bitcount of the result. More...

bm::id_t	bm::bit_operation_xor_any (const bm::word_t src1, const bm::word_t src2) noexcept
	Performs bitblock XOR operation test. More...

template<class T >
unsigned	bm::bit_count_nonzero_size (const T *blk, unsigned data_size) noexcept
	Inspects block for full zero words. More...

unsigned	bm::bit_block_find (const bm::word_t block, unsigned nbit, unsigned pos) noexcept
	Searches for the next 1 bit in the BIT block. More...

unsigned	bm::bit_find_last (const bm::word_t block, unsigned last) noexcept
	BIT block find the last set bit (backward search) More...

bool	bm::bit_find_first (const bm::word_t block, unsigned pos) noexcept
	BIT block find the first set bit. More...

unsigned	bm::bit_find_first (const bm::word_t block, unsigned first, bm::id64_t digest) noexcept
	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) noexcept
	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) noexcept
	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) noexcept
	Choose best representation for a bit-block. More...

template<typename T >
unsigned	bm::bit_block_convert_to_arr (T dest, const unsigned src, bool inverted) noexcept
	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) noexcept
	Unpacks word wave (Nx 32-bit words) 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) noexcept
	bit index to word gather-scatter algorithm More...

template<typename T , unsigned BPC, unsigned BPS>
void	bm::tmatrix_distance (const T tmatrix[BPC][BPS], unsigned distance[BPC][BPC])
	Compute pairwise Row x Row Humming distances on planes(rows) of the transposed bit block. More...

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

unsigned	bm::count_leading_zeros (unsigned x) noexcept
	Portable LZCNT with (uses minimal LUT) More...

unsigned	bm::count_trailing_zeros (unsigned v) noexcept
	Portable TZCNT with (uses 37-LUT) More...

template<class T >
unsigned	bm::bit_scan_reverse (T value) noexcept

bm::id_t	bm::word_bitcount (bm::id_t w) noexcept

unsigned	bm::word_bitcount64 (bm::id64_t x) noexcept

void	bm::bit_block_xor_change32 (const bm::word_t block, const bm::word_t xor_block, unsigned size, unsigned gc, unsigned bc) noexcept

void	bm::bit_block_xor_change64 (const bm::word_t s_block, const bm::word_t ref_block, unsigned size, unsigned gc, unsigned bc) noexcept

Detailed Description

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

Function Documentation

◆ best_representation()

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

inlinenoexcept

Choose best representation for a bit-block.

Definition at line 9021 of file bmfunc.h.

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

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

◆ bit_andnot_arr_ffmask()

void bm::bit_andnot_arr_ffmask	(	bm::word_t *	dst,
		const bm::word_t *	src
	)

inlinenoexcept

bitblock AND NOT with constant ~0 mask operation.

Parameters

dst	- destination block.
src	- source block.

Definition at line 8470 of file bmfunc.h.

References bm::all_bits_mask, BMRESTRICT, bm::set_block_size, and VECT_ANDNOT_ARR_2_MASK.

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

◆ bit_block_and() [1/2]

bm::id64_t bm::bit_block_and	(	bm::word_t *	dst,
		const bm::word_t *	src
	)

inlinenoexcept

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

Parameters

dst	- destination block.
src	- source block.

Returns: 0 if AND operation did not produce anything (no 1s in the output)

Definition at line 6858 of file bmfunc.h.

References BM_ASSERT, BMRESTRICT, i, bm::set_block_size, and VECT_AND_BLOCK.

Referenced by bm::bit_operation_and(), bm::bvector< Alloc >::combine_operation_block_and(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_AND(), bm::aggregator< BV >::process_bit_blocks_and(), and TestBlockAND().

◆ bit_block_and() [2/2]

bm::id64_t bm::bit_block_and	(	bm::word_t *	dst,
		const bm::word_t *	src,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bit-block AND

Parameters

dst	- destination block.
src	- source block.
digest	- known digest of dst block

Returns: new digest

Definition at line 6895 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_AND_DIGEST, and bm::word_bitcount64().

◆ bit_block_and_2way()

bm::id64_t bm::bit_block_and_2way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bit-block AND

dst = src1 AND src2

Parameters

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

Returns: new digest

Definition at line 7076 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_AND_DIGEST_2WAY, and bm::word_bitcount64().

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

◆ bit_block_and_3way()

bm::id64_t bm::bit_block_and_3way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bit-block AND

dst &= src1 AND src2

Parameters

dst	- src/destination block.
src1	- source block.
src2	- source block.
digest	- known initial digest

Returns: new digest

Definition at line 7011 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_AND_DIGEST_3WAY, and bm::word_bitcount64().

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

◆ bit_block_and_5way()

bm::id64_t bm::bit_block_and_5way	(	bm::word_t *	dst,
		const bm::word_t *	src0,
		const bm::word_t *	src1,
		const bm::word_t *	src2,
		const bm::word_t *	src3,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bit-block AND 5-way

Returns: new digest

Definition at line 6949 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_AND_DIGEST_5WAY, and bm::word_bitcount64().

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

◆ bit_block_and_any()

unsigned bm::bit_block_and_any	(	const bm::word_t *	src1,
		const bm::word_t *	src2
	)

inlinenoexcept

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

Parameters

src1	- first bit block
src2	- second bit block

Definition at line 7321 of file bmfunc.h.

References count, and bm::set_block_size.

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 *	src2
	)

inlinenoexcept

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

Parameters

src1	- first bit block
src2	- second bit block

Definition at line 7274 of file bmfunc.h.

References bm::bitcount64_4way(), count, bm::set_block_size, VECT_BITCOUNT_AND, and bm::word_bitcount().

Referenced by bm::bit_operation_and_count().

◆ bit_block_and_or_2way()

bm::id64_t bm::bit_block_and_or_2way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bit-block AND - OR

dst =dst OR (src1 AND src2)

Parameters

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

Returns: new digest (for the AND operation)

Definition at line 7210 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_AND_OR_DIGEST_2WAY, and bm::word_bitcount64().

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

◆ bit_block_any_range()

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

inlinenoexcept

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

Definition at line 5987 of file bmfunc.h.

References BM_ASSERT, mask, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::block_any_range(), bm::gap_bitset_and_any(), bm::gap_bitset_sub_any(), and bm::gap_bitset_xor_any().

◆ bit_block_calc_change()

unsigned bm::bit_block_calc_change ( const bm::word_t * block )

inlinenoexcept

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

Parameters

block - bit-block start pointer

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

Definition at line 5283 of file bmfunc.h.

References bm::bit_block_change32(), bm::bit_block_change64(), bm::set_block_size, and VECT_BLOCK_CHANGE.

Referenced by BitCountChangeTest(), bm::blocks_manager< Alloc >::block_count_change_func::block_count(), bm::blocks_manager< Alloc >::opt_copy_bit_block(), bm::blocks_manager< Alloc >::optimize_bit_block(), bm::blocks_manager< Alloc >::optimize_bit_block_nocheck(), and bm::blocks_manager< Alloc >::optimize_block().

◆ bit_block_calc_count_range()

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

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

noexcept

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

LWA - left word aligned RWA - right word aligned

Definition at line 5390 of file bmfunc.h.

References _mm_popcnt_u64(), BM_ASSERT, count, bm::gap_max_bits, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_word_mask, bm::set_word_shift, and bm::word_bitcount().

Referenced by BitForEachRangeFuncTest(), BitRangeAllSetTest(), bm::bvector< Alloc >::block_count_to(), bm::bvector< Alloc >::build_rs_index(), bm::bvector< Alloc >::count_range_no_check(), bm::gap_bitset_and_count(), bm::gap_bitset_or_count(), bm::gap_bitset_sub_count(), bm::gap_bitset_xor_count(), GAPCheck(), and SelectTest().

◆ bit_block_calc_count_to()

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

inlinenoexcept

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

Definition at line 5476 of file bmfunc.h.

References BM_ASSERT, BM_AVX2_BIT_COUNT, BM_AVX2_POPCNT_PROLOG, cnt, count, bm::mask_l_u32(), bm::word_bitcount(), and bm::word_bitcount64().

Referenced by bm::bvector< Alloc >::block_count_to(), bm::bvector< Alloc >::build_rs_index(), bm::bvector< Alloc >::count_to_test(), and SelectTest().

◆ bit_block_convert_to_arr()

template<typename T >

unsigned bm::bit_block_convert_to_arr	(	T *	dest,
		const unsigned *	src,
		bool	inverted
	)

noexcept

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

Returns: destination size as a result of block decoding

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

Returns: destination size as a result of block decoding

Definition at line 9064 of file bmfunc.h.

References bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, bm::gap_max_bits, t, T, and bm::word_bitcount64().

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

◆ bit_block_copy()

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

inlinenoexcept

Bitblock copy operation.

Parameters

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

Definition at line 6777 of file bmfunc.h.

References bm::set_block_size, and VECT_COPY_BLOCK.

Referenced by bm::blocks_manager< Alloc >::clone_assign_block(), bm::bvector< Alloc >::combine_operation_block_and(), bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), bm::bvector< Alloc >::combine_operation_block_xor(), bm::bvector< Alloc >::combine_operation_with_block(), bm::aggregator< BV >::combine_shift_right_and(), bm::blocks_manager< Alloc >::copy(), bm::blocks_manager< Alloc >::copy_bit_block(), bm::blocks_manager< Alloc >::copy_block(), bm::blocks_manager< Alloc >::copy_to_arena(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_ASSIGN(), bm::random_subset< BV >::get_subset(), bm::aggregator< BV >::process_bit_blocks_and(), and bm::aggregator< BV >::process_bit_blocks_or().

◆ bit_block_copy_unalign()

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

inlinenoexcept

Bitblock copy operation (unaligned src)

Parameters

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

Definition at line 6795 of file bmfunc.h.

References bm::set_block_size, and VECT_COPY_BLOCK_UNALIGN.

Referenced by bm::bit_import_u32().

◆ bit_block_count() [1/2]

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

inlinenoexcept

Bitcount for bit block.

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

Definition at line 5051 of file bmfunc.h.

References bm::bit_count_min_unroll(), bm::set_block_size, and VECT_BITCOUNT.

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

◆ bit_block_count() [2/2]

bm::id_t bm::bit_block_count	(	const bm::word_t *const	block,
		bm::id64_t	digest
	)

inlinenoexcept

Bitcount for bit block.

Function calculates number of 1 bits in the given array of words. uses digest to understand zero areas

Definition at line 5070 of file bmfunc.h.

References bm::bitcount64_4way(), BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, count, bm::set_block_digest_wave_size, t, VECT_BIT_COUNT_DIGEST, bm::word_bitcount(), and bm::word_bitcount64().

◆ bit_block_erase()

void bm::bit_block_erase	(	bm::word_t *	block,
		unsigned	bitpos,
		bool	carry_over
	)

inlinenoexcept

erase bit from position and shift the rest right with carryover

Parameters

block	- bit-block pointer
bitpos	- bit position to insert
carry_over	- bit value to add to the end (0\|1)

Definition at line 5834 of file bmfunc.h.

References bm::bit_block_shift_l1_unr(), BM_ASSERT, i, bm::mask_r_u32(), bm::set_block_mask, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.

Referenced by BlockBitEraseTest(), and bm::bvector< Alloc >::erase().

◆ bit_block_find()

unsigned bm::bit_block_find	(	const bm::word_t *	block,
		unsigned	nbit,
		unsigned *	pos
	)

inlinenoexcept

Searches for the next 1 bit in the BIT block.

Parameters

block	- BIT buffer
nbit	- bit index to start checking from
pos	- [out] found value

Returns: 0 if not found

Definition at line 8657 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, i, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.

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

◆ bit_block_find_interval_end()

bool bm::bit_block_find_interval_end	(	const bm::word_t *	block,
		unsigned	nbit,
		unsigned *	pos
	)

inlinenoexcept

Searches for the last 1 bit in the 111 interval of a BIT block.

Parameters

block	- BIT buffer
nbit	- bit index to start checking from
pos	- [out] found value

Returns: false if not found

Definition at line 6177 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, bm::gap_max_bits, bm::set_block_size, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::block_find_interval_end().

◆ bit_block_find_interval_start()

bool bm::bit_block_find_interval_start	(	const bm::word_t *	block,
		unsigned	nbit,
		unsigned *	pos
	)

inlinenoexcept

Searches for the first 1 bit in the 111 interval of a BIT block.

Parameters

block	- BIT buffer
nbit	- bit index to start checking from
pos	- [out] found value

Returns: false if not found

Definition at line 6273 of file bmfunc.h.

References bm::bit_scan_reverse32(), BM_ASSERT, bm::mask_l_u32(), bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::block_find_interval_start().

◆ bit_block_find_prev()

bool bm::bit_block_find_prev	(	const bm::word_t *	block,
		unsigned	nbit,
		unsigned *	pos
	)

inlinenoexcept

Reverse search for the previous 1 bit.

Parameters

block	- BIT buffer
nbit	- bit index to start checking from
pos	- [out] found value

Returns: false if not found

Definition at line 6337 of file bmfunc.h.

References bm::bit_scan_reverse32(), BM_ASSERT, bm::mask_l_u32(), bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::block_find_reverse().

◆ bit_block_gather_scatter()

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
	)

noexcept

bit index to word gather-scatter algorithm

Definition at line 9713 of file bmfunc.h.

References arr, len, bm::set_block_mask, bm::set_word_mask, bm::set_word_shift, and ncbi::grid::netcache::search::fields::size.

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

◆ bit_block_init_and_2way()

bm::id64_t bm::bit_block_init_and_2way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bit-block AND (0 elements of digest will be zeroed)

dst = src1 AND src2

Parameters

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

Returns: new digest

Definition at line 7140 of file bmfunc.h.

References BMRESTRICT, i, bm::set_block_digest_wave_size, VECT_AND_DIGEST_2WAY, and VECT_BLOCK_SET_DIGEST.

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

◆ bit_block_insert()

bm::word_t bm::bit_block_insert	(	bm::word_t *	block,
		unsigned	bitpos,
		bool	value
	)

inlinenoexcept

insert bit into position and shift the rest right with carryover

Parameters

block	- bit-block pointer
bitpos	- bit position to insert
value	- bit value (0\|1) to insert

Returns: carry over value

Definition at line 5585 of file bmfunc.h.

References BM_ASSERT, i, bm::mask_r_u32(), bm::set_block_mask, bm::set_block_size, bm::set_word_mask, bm::set_word_shift, and rapidjson::value.

Referenced by BlockBitInsertTest(), and bm::bvector< Alloc >::insert().

◆ bit_block_is_all_one_range()

bool bm::bit_block_is_all_one_range	(	const bm::word_t *const	block,
		bm::word_t	left,
		bm::word_t	right
	)

inlinenoexcept

Check if all bits are 1 in [left, right] range

Definition at line 5301 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, mask, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_word_mask, and bm::set_word_shift.

Referenced by BitForEachRangeFuncTest(), BitRangeAllSetTest(), bm::block_is_all_one_range(), and bm::block_is_interval().

◆ bit_block_or()

bool bm::bit_block_or	(	bm::word_t *	dst,
		const bm::word_t *	src
	)

inlinenoexcept

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

Parameters

dst	- destination block.
src	- source block.

Definition at line 7835 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK.

Referenced by bm::bit_operation_or(), bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), bm::deserializer< BV, DEC >::decode_bit_block(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_OR(), bm::aggregator< BV >::process_bit_blocks_or(), TestBlockOR(), and bm::deserializer< BV, DEC >::xor_decode().

◆ bit_block_or_2way()

bool bm::bit_block_or_2way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2
	)

inlinenoexcept

2 way (target := source1 | source2) bitblock OR operation.

Parameters

dst	- dest block [out]
src1	- source 1
src2	- source 2

Returns: 1 if produced block of ALL ones

Definition at line 7872 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_2WAY.

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

◆ bit_block_or_3way()

bool bm::bit_block_or_3way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2
	)

inlinenoexcept

3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of source and destination blocks.

Parameters

dst	- sst-dest block [in,out]
src1	- source 1
src2	- source 2

Returns: 1 if produced block of ALL ones

Definition at line 7952 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_3WAY.

Referenced by bm::aggregator< BV >::process_bit_blocks_or(), and TestBlockOR().

◆ bit_block_or_5way()

bool bm::bit_block_or_5way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2,
		const bm::word_t *	src3,
		const bm::word_t *	src4
	)

inlinenoexcept

5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of source and destination blocks.

Parameters

dst	- destination block.
src1	- source1, etc
src2	- source1, etc
src3	- source1, etc
src4	- source1, etc

Returns: 1 if produced block of ALL ones

Definition at line 7996 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_OR_BLOCK_5WAY.

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

◆ bit_block_or_any()

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

inlinenoexcept

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

Parameters

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

Definition at line 7545 of file bmfunc.h.

References BMRESTRICT, count, and bm::set_block_size.

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 *	src2
	)

inlinenoexcept

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

Parameters

src1	- first bit block
src2	- second bit block.

Definition at line 7498 of file bmfunc.h.

References bm::bitcount64_4way(), count, bm::set_block_size, VECT_BITCOUNT_OR, and bm::word_bitcount().

Referenced by bm::bit_operation_or_count().

◆ bit_block_rotate_left_1()

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

inlinenoexcept

Cyclic rotation of bit-block left by 1 bit

Definition at line 5533 of file bmfunc.h.

References i, and bm::set_block_size.

Referenced by ShiftRotateTest().

◆ bit_block_rotate_left_1_unr()

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

inlinenoexcept

Unrolled cyclic rotation of bit-block left by 1 bit.

Parameters

block - bit-block pointer

Definition at line 5549 of file bmfunc.h.

References i, and bm::set_block_size.

Referenced by ShiftRotateTest().

◆ bit_block_set()

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

inlinenoexcept

Bitblock memset operation.

Parameters

dst	- destination block.
value	- value to set.

Definition at line 4456 of file bmfunc.h.

References bm::set_block_size, rapidjson::value, and VECT_SET_BLOCK.

◆ bit_block_shift_l1()

bool bm::bit_block_shift_l1	(	bm::word_t *	block,
		bm::word_t *	empty_acc,
		bm::word_t	co_flag
	)

inlinenoexcept

Left bit-shift bitblock by 1 bit (reference)

Parameters

block	- bit-block pointer
empty_acc	- [out] contains 0 if block is empty
co_flag	- carry over from the prev/next block

Returns: carry over bit (1 or 0)

Definition at line 5736 of file bmfunc.h.

References BM_ASSERT, i, and bm::set_block_size.

◆ bit_block_shift_l1_unr()

bool bm::bit_block_shift_l1_unr	(	bm::word_t *	block,
		bm::word_t *	empty_acc,
		bm::word_t	co_flag
	)

inlinenoexcept

Left bit-shift of bit-block by 1 bit (loop unrolled)

Parameters

block	- bit-block pointer
empty_acc	- [out] contains 0 if block is empty
co_flag	- carry over from the prev/next block

Returns: carry over bit (1 or 0)

Definition at line 5811 of file bmfunc.h.

References bm::bit_block_shift_l1_unr_min(), BM_ASSERT, and VECT_SHIFT_L1.

Referenced by bm::bit_block_erase(), BlockBitEraseTest(), and bm::bvector< Alloc >::erase().

◆ bit_block_shift_l1_unr_min()

bool bm::bit_block_shift_l1_unr_min	(	bm::word_t *	block,
		bm::word_t *	empty_acc,
		unsigned	co_flag
	)

inlinenoexcept

Left bit-shift bitblock by 1 bit (minimum unroll)

Parameters

block	- bit-block pointer
empty_acc	- [out] contains 0 if block is empty
co_flag	- carry over from the prev/next block

Returns: carry over bit (1 or 0)

Definition at line 5767 of file bmfunc.h.

References i, and bm::set_block_size.

Referenced by bm::bit_block_shift_l1_unr().

◆ bit_block_shift_r1()

bool bm::bit_block_shift_r1	(	bm::word_t *	block,
		bm::word_t *	empty_acc,
		bm::word_t	co_flag
	)

inlinenoexcept

Right bit-shift bitblock by 1 bit (reference)

Parameters

block	- bit-block pointer
empty_acc	- [out] contains 0 if block is empty
co_flag	- carry over from the previous block

Returns: carry over bit (1 or 0)

Definition at line 5634 of file bmfunc.h.

References BM_ASSERT, i, and bm::set_block_size.

Referenced by bm::bit_block_shift_r1_unr_min(), and ShiftRotateTest().

◆ bit_block_shift_r1_and()

bool bm::bit_block_shift_r1_and	(	bm::word_t *	block,
		bm::word_t	co_flag,
		const bm::word_t *	mask_block,
		bm::id64_t *	digest
	)

inlinenoexcept

Right bit-shift of bit-block by 1 bit (reference) + AND.

Parameters

block	- bit-block pointer
co_flag	- carry over from the previous block
mask_block	- mask bit-block pointer
digest	- block digest

Returns: carry over bit (1 or 0)

Definition at line 5890 of file bmfunc.h.

References BM_ASSERT, i, bm::set_block_digest_wave_size, bm::set_block_size, t, and bm::word_bitcount64().

Referenced by bm::bit_block_shift_r1_and_unr().

◆ bit_block_shift_r1_and_unr()

bool bm::bit_block_shift_r1_and_unr	(	bm::word_t *	block,
		bm::word_t	co_flag,
		const bm::word_t *	mask_block,
		bm::id64_t *	digest
	)

inlinenoexcept

Right bit-shift bitblock by 1 bit (reference) + AND.

Parameters

block	- bit-block pointer
co_flag	- carry over from the previous block
mask_block	- mask bit-block pointer
digest	- block digest

Returns: carry over bit (1 or 0)

Definition at line 5962 of file bmfunc.h.

References bm::bit_block_shift_r1_and(), BM_ASSERT, and VECT_SHIFT_R1_AND.

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

◆ bit_block_shift_r1_unr()

bool bm::bit_block_shift_r1_unr	(	bm::word_t *	block,
		bm::word_t *	empty_acc,
		bm::word_t	co_flag
	)

inlinenoexcept

Right bit-shift of bit-block by 1 bit (loop unrolled)

Parameters

block	- bit-block pointer
empty_acc	- [out] contains 0 if block is empty
co_flag	- carry over from the previous block

Returns: carry over bit (1 or 0)

Definition at line 5711 of file bmfunc.h.

References bm::bit_block_shift_r1_unr_min(), BM_ASSERT, and VECT_SHIFT_R1.

Referenced by bm::bvector< Alloc >::insert(), and ShiftRotateTest().

◆ bit_block_shift_r1_unr_min()

bool bm::bit_block_shift_r1_unr_min	(	bm::word_t *	block,
		bm::word_t *	empty_acc,
		bm::id64_t	co_flag
	)

inlinenoexcept

Right bit-shift bitblock by 1 bit (minimum unroll)

Parameters

block	- bit-block pointer
empty_acc	- [out] contains 0 if block is empty
co_flag	- carry over from the previous block

Returns: carry over bit (1 or 0)

Definition at line 5665 of file bmfunc.h.

References bm::bit_block_shift_r1(), BMRESTRICT, bool, i, and bm::set_block_size.

Referenced by bm::bit_block_shift_r1_unr().

◆ bit_block_stream()

void bm::bit_block_stream	(	bm::word_t *	dst,
		const bm::word_t *	src
	)

inlinenoexcept

Bitblock copy/stream operation.

Parameters

dst	- destination block.
src	- source block.

Definition at line 6816 of file bmfunc.h.

References bm::set_block_size, and VECT_STREAM_BLOCK.

Referenced by bm::blocks_manager< Alloc >::copy_bit_block().

◆ bit_block_stream_unalign()

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

inlinenoexcept

Bitblock copy/stream operation (unaligned src)

Parameters

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

Definition at line 6834 of file bmfunc.h.

References bm::set_block_size, and VECT_STREAM_BLOCK_UNALIGN.

◆ bit_block_sub() [1/2]

bm::id64_t bm::bit_block_sub	(	bm::word_t *	dst,
		const bm::word_t *	src
	)

inlinenoexcept

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

Parameters

dst	- destination block.
src	- source block.

Returns: 0 if SUB operation did not produce anything (no 1s in the output)

Definition at line 8105 of file bmfunc.h.

References BMRESTRICT, i, bm::set_block_size, and VECT_SUB_BLOCK.

Referenced by bm::bit_operation_sub(), bm::bvector< Alloc >::combine_operation_block_sub(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_SUB(), bm::aggregator< BV >::process_bit_blocks_sub(), and TestBlockSUB().

◆ bit_block_sub() [2/2]

bm::id64_t bm::bit_block_sub	(	bm::word_t *	dst,
		const bm::word_t *	src,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bitblock SUB (AND NOT) operation

Parameters

dst	- destination block.
src	- source block.
digest	- known digest of dst block

Returns: new digest

Definition at line 8141 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_SUB_DIGEST, and bm::word_bitcount64().

◆ bit_block_sub_2way()

bm::id64_t bm::bit_block_sub_2way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bitblock SUB (AND NOT) operation (3 operand)

Parameters

dst	- destination block.
src1	- source block 1
src2	- source block 2
digest	- known digest of dst block

Returns: new digest

Definition at line 8201 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_SUB_DIGEST_2WAY, and bm::word_bitcount64().

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

◆ bit_block_sub_3way()

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

inlinenoexcept

digest based bit-block SUB 3-way

Returns: new digest

Definition at line 8316 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_SUB_DIGEST_3WAY, and bm::word_bitcount64().

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

◆ bit_block_sub_5way()

bm::id64_t bm::bit_block_sub_5way	(	bm::word_t *	dst,
		const bm::word_t *	src0,
		const bm::word_t *	src1,
		const bm::word_t *	src2,
		const bm::word_t *	src3,
		bm::id64_t	digest
	)

inlinenoexcept

digest based bit-block SUB 5-way

Returns: new digest

Definition at line 8259 of file bmfunc.h.

References BM_ASSERT, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_SUB_DIGEST_5WAY, and bm::word_bitcount64().

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

◆ bit_block_sub_any()

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

inlinenoexcept

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

Parameters

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

Definition at line 7470 of file bmfunc.h.

References BMRESTRICT, count, and bm::set_block_size.

Referenced by bm::bit_operation_sub_any().

◆ bit_block_sub_count()

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

inlinenoexcept

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

Parameters

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

Definition at line 7424 of file bmfunc.h.

References bm::bitcount64_4way(), BMRESTRICT, count, bm::set_block_size, VECT_BITCOUNT_SUB, and bm::word_bitcount().

Referenced by bm::bit_operation_sub_count().

◆ bit_block_xor()

bm::id64_t bm::bit_block_xor	(	bm::word_t *	dst,
		const bm::word_t *	src
	)

inlinenoexcept

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

Parameters

dst	- destination block.
src	- source block.

Definition at line 8434 of file bmfunc.h.

References BM_ASSERT, BMRESTRICT, i, bm::set_block_size, and VECT_XOR_BLOCK.

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

◆ bit_block_xor_2way()

bm::id64_t bm::bit_block_xor_2way	(	bm::word_t *	dst,
		const bm::word_t *	src1,
		const bm::word_t *	src2
	)

inlinenoexcept

2 way (target := source1 ^ source2) bitblock XOR operation.

Parameters

dst	- dest block [out]
src1	- source 1
src2	- source 2

Returns: OR accumulator

Definition at line 7911 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_XOR_BLOCK_2WAY.

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

◆ bit_block_xor_any()

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

inlinenoexcept

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

Parameters

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

Definition at line 7398 of file bmfunc.h.

References BMRESTRICT, count, and bm::set_block_size.

Referenced by bm::bit_operation_xor_any().

◆ bit_block_xor_change32()

void bm::bit_block_xor_change32	(	const bm::word_t *	block,
		const bm::word_t *	xor_block,
		unsigned	size,
		unsigned *	gc,
		unsigned *	bc
	)

inlinenoexcept

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

Definition at line 96 of file bmxor.h.

References BM_ASSERT, int, ncbi::grid::netcache::search::fields::size, and bm::word_bitcount().

Referenced by bm::bit_block_xor_change().

◆ bit_block_xor_change64()

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

inlinenoexcept

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

Definition at line 151 of file bmxor.h.

References BM_ASSERT, BMRESTRICT, int, ncbi::grid::netcache::search::fields::size, and bm::word_bitcount64().

Referenced by bm::bit_block_xor_change().

◆ bit_block_xor_count()

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

inlinenoexcept

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

Parameters

src1	- first bit block
src2	- second bit block

Definition at line 7350 of file bmfunc.h.

References bm::bitcount64_4way(), BMRESTRICT, count, bm::set_block_size, VECT_BITCOUNT_XOR, and bm::word_bitcount().

Referenced by bm::bit_operation_xor_count(), and Check_XOR_Product().

◆ bit_count_change()

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

inlinenoexcept

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

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

Definition at line 5145 of file bmfunc.h.

References count, and bm::word_bitcount().

Referenced by BitCountChangeTest().

◆ bit_count_min_unroll()

unsigned bm::bit_count_min_unroll	(	const bm::word_t *	block,
		const bm::word_t *	block_end
	)

inlinenoexcept

Bitcount for bit block without agressive unrolling.

Definition at line 4996 of file bmfunc.h.

References bm::bitcount64_4way(), BM_ASSERT, BMRESTRICT, count, and bm::word_bitcount().

Referenced by bm::bit_block_count(), bm::compute_s_block_descr(), and sx_CalcBlockBitCount().

◆ bit_count_nonzero_size()

template<class T >

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

noexcept

Inspects block for full zero words.

Parameters

blk	- bit block pointer
data_size	- data size

Returns: size of all non-zero words

Definition at line 8601 of file bmfunc.h.

References BM_ASSERT, count, and T.

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

◆ bit_find_first() [1/2]

unsigned bm::bit_find_first	(	const bm::word_t *	block,
		unsigned *	first,
		bm::id64_t	digest
	)

inlinenoexcept

BIT block find the first set bit.

Parameters

block	- bit block buffer pointer
first	- index of the first 1 bit (out)
digest	- known digest of dst block

Returns: 0 if not found

Definition at line 8777 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, bm::bmi_blsi_u64(), first(), i, bm::set_block_digest_wave_size, bm::set_block_size, t, VECT_BIT_FIND_FIRST, and bm::word_bitcount64().

◆ bit_find_first() [2/2]

bool bm::bit_find_first	(	const bm::word_t *	block,
		unsigned *	pos
	)

inlinenoexcept

BIT block find the first set bit.

Parameters

block	- bit block buffer pointer
pos	- index of the first 1 bit (out)

Returns: 0 if not found

Definition at line 8742 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, i, bm::set_block_size, and VECT_BIT_FIND_FIRST.

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

◆ bit_find_first_diff()

bool bm::bit_find_first_diff	(	const bm::word_t *	blk1,
		const bm::word_t *	blk2,
		unsigned *	pos
	)

inlinenoexcept

Find first bit which is different between two bit-blocks.

Parameters

blk1	- block 1
blk2	- block 2
pos	- out - position of difference (undefined if blocks are equal)

Returns: true if difference was found

Definition at line 4725 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, BMRESTRICT, bm::count_trailing_zeros_u64(), f, i, bm::set_block_size, and VECT_BIT_FIND_DIFF.

Referenced by bm::block_find_first_diff(), TestBlockExpandCompact(), and TestFindBlockDiff().

◆ bit_find_first_if_1()

bool bm::bit_find_first_if_1	(	const bm::word_t *	block,
		unsigned *	first,
		bm::id64_t	digest
	)

inlinenoexcept

BIT block find the first set bit if only 1 bit is set.

Parameters

block	- bit block buffer pointer
first	- index of the first 1 bit (out)
digest	- known digest of dst block

Returns: 0 if not found

Definition at line 8838 of file bmfunc.h.

References _mm_load_si128(), _mm_test_all_zeros(), bm::bit_scan_forward32(), BM_ASSERT, bm::bmi_blsi_u64(), cnt, first(), i, bm::set_block_digest_wave_size, t, bm::word_bitcount(), and bm::word_bitcount64().

Referenced by bm::aggregator< BV >::process_bit_blocks_and(), bm::aggregator< BV >::process_bit_blocks_sub(), bm::aggregator< BV >::process_gap_blocks_and(), bm::aggregator< BV >::process_gap_blocks_sub(), and TestBlockDigest().

◆ bit_find_last()

unsigned bm::bit_find_last	(	const bm::word_t *	block,
		unsigned *	last
	)

inlinenoexcept

BIT block find the last set bit (backward search)

Parameters

block	- bit block buffer pointer
last	- index of the last 1 bit (out)

Returns: true if found

Definition at line 8708 of file bmfunc.h.

References bm::bit_scan_reverse(), BM_ASSERT, i, last(), and bm::set_block_size.

Referenced by bm::bvector< Alloc >::find_reverse(), and TestBlockLast().

◆ bit_find_rank()

template<typename SIZE_TYPE >

SIZE_TYPE bm::bit_find_rank	(	const bm::word_t *const	block,
		SIZE_TYPE	rank,
		unsigned	nbit_from,
		unsigned &	nbit_pos
	)

noexcept

BIT block find position for the rank.

Parameters

block	- bit block buffer pointer
rank	- rank to find (must be > 0)
nbit_from	- start bit position in block
nbit_pos	- (out)found position

Returns: 0 if position with rank was found, or the remaining rank (rank - population count)

Definition at line 8916 of file bmfunc.h.

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

Referenced by bm::block_find_rank(), and SelectTest().

◆ bit_for_each()

template<typename T , typename F >

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

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

Parameters

w	- value
func	- bit functor

Definition at line 359 of file bmfunc.h.

Referenced by bm::bit_list().

◆ bit_for_each_4()

template<typename T , typename F >

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

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

Parameters

w	- value
func	- bit functor

Definition at line 289 of file bmfunc.h.

References BM_ASSERT.

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

Parameters

distance - pairwise distance matrix

pc_vector

- OUT compression descriptor vector

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

Definition at line 379 of file bmtrans.h.

References BM_ASSERT, i, bm::ibpc_all_one, bm::ibpc_all_zero, bm::ibpc_close, bm::ibpc_equiv, bm::ibpc_uncompr, and T.

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

◆ bit_invert()

template<typename T >

void bm::bit_invert ( T * start )

noexcept

Function inverts block of bits

Definition at line 6057 of file bmfunc.h.

References BM_ASSERT, IS_VALID_ADDR, bm::set_block_size, T, and VECT_INVERT_BLOCK.

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

◆ bit_is_all_zero()

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

inlinenoexcept

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

Definition at line 1550 of file bmfunc.h.

References BMRESTRICT, bm::set_block_size, and VECT_IS_ZERO_BLOCK.

Referenced by bm::bit_operation_or_any(), bm::bit_operation_sub_any(), bm::bit_operation_xor_any(), bm::block_any(), bm::check_block_zero(), bm::combine_any_operation_with_block(), bm::bvector< Alloc >::combine_operation_block_and(), bm::bvector< Alloc >::combine_operation_block_sub(), bm::aggregator< BV >::combine_shift_right_and(), bm::bvector< Alloc >::compare(), bm::gap_bitset_or_any(), bm::blocks_manager< Alloc >::block_any_func::operator()(), bm::blocks_manager< Alloc >::opt_copy_bit_block(), bm::blocks_manager< Alloc >::optimize_block(), bm::aggregator< BV >::process_gap_blocks_and(), bm::aggregator< BV >::process_gap_blocks_sub(), TestBlockAND(), TestBlockSUB(), and TestBlockZero().

◆ bit_list()

template<typename T , typename B >

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

noexcept

Unpacks word into list of ON bit indexes.

Parameters

w	- value
bits	- pointer on the result array

Returns: number of bits in the list

Definition at line 595 of file bmfunc.h.

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

Referenced by BitForEachTest(), bm::random_subset< BV >::get_random_array(), and bm::str_sparse_vector< CharType, BV, STR_SIZE >::import_char_slice().

◆ bit_list_4()

template<typename T , typename B >

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

noexcept

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

Parameters

w	- value
bits	- pointer on the result array

Returns: number of bits in the list

Definition at line 613 of file bmfunc.h.

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

Referenced by BitForEachTest().

◆ bit_operation_and()

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

inlinenoexcept

bitblock AND operation.

Parameters

dst	- destination block.
src	- source block.

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

Definition at line 7578 of file bmfunc.h.

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

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

◆ bit_operation_and_any()

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

inlinenoexcept

Performs bitblock AND operation test.

Parameters

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

Returns: non zero if there is any value

Definition at line 7650 of file bmfunc.h.

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

◆ bit_operation_and_count()

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

inlinenoexcept

Performs bitblock AND operation and calculates bitcount of the result.

Parameters

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

Returns: bitcount value

Definition at line 7626 of file bmfunc.h.

References bm::bit_block_and_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, and IS_EMPTY_BLOCK.

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

◆ bit_operation_or()

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

inlinenoexcept

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

Parameters

dst	- destination block.
src	- source block.

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

Definition at line 8045 of file bmfunc.h.

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

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

◆ bit_operation_or_any()

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

inlinenoexcept

Performs bitblock OR operation test.

Parameters

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

Returns: non zero value if there are any bits

Definition at line 7802 of file bmfunc.h.

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

◆ bit_operation_or_count()

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

inlinenoexcept

Performs bitblock OR operation and calculates bitcount of the result.

Parameters

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

Returns: bitcount value

Definition at line 7765 of file bmfunc.h.

References bm::bit_block_count(), bm::bit_block_or_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

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

◆ bit_operation_sub()

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

inlinenoexcept

bitblock SUB operation.

Parameters

dst	- destination block.
src	- source block.

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

Definition at line 8376 of file bmfunc.h.

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

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

◆ bit_operation_sub_any()

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

inlinenoexcept

Performs bitblock test of SUB operation.

Parameters

src1	- first bit block.
src2	- second bit block

Returns: non zero value if there are any bits

Definition at line 7730 of file bmfunc.h.

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

◆ bit_operation_sub_count()

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

inlinenoexcept

Performs bitblock SUB operation and calculates bitcount of the result.

Parameters

src1	- first bit block.
src2	- second bit block

Returns: bitcount value

Definition at line 7675 of file bmfunc.h.

References bm::bit_block_count(), bm::bit_block_sub_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

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

◆ bit_operation_sub_count_inv()

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

inlinenoexcept

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

Parameters

src1	- first bit block.
src2	- second bit block

Returns: bitcount value

Definition at line 7712 of file bmfunc.h.

References bm::bit_operation_sub_count().

◆ bit_operation_xor()

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

inlinenoexcept

bitblock XOR operation.

Parameters

dst	- destination block.
src	- source block.

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

Definition at line 8505 of file bmfunc.h.

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

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

◆ bit_operation_xor_any()

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

inlinenoexcept

Performs bitblock XOR operation test.

Parameters

src1	- bit block start ptr
src2	- second bit block ptr

Returns: non zero value if there are bits

Definition at line 8575 of file bmfunc.h.

References 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 *	src1,
		const bm::word_t *	src2
	)

inlinenoexcept

Performs bitblock XOR operation and calculates bitcount of the result.

Parameters

src1	- bit block start ptr
src2	- second bit block

Returns: bitcount value

Definition at line 8543 of file bmfunc.h.

References bm::bit_block_count(), bm::bit_block_xor_count(), FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_max_bits, IS_EMPTY_BLOCK, and IS_FULL_BLOCK.

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

◆ bit_scan_reverse()

template<class T >

unsigned bm::bit_scan_reverse ( T value )

noexcept

Returns BSR value

Definition at line 453 of file bmutil.h.

References bm::bit_scan_reverse32(), BM_ASSERT, T, test, and rapidjson::value.

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

◆ bitcmp()

template<typename T >

int bm::bitcmp	(	const T *	buf1,
		const T *	buf2,
		unsigned	len
	)

noexcept

Lexicographical comparison of BIT buffers.

Parameters

buf1	- First buffer pointer.
buf2	- Second buffer pointer.
len	- Buffer length in elements (T).

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

Definition at line 4700 of file bmfunc.h.

References BM_ASSERT, len, and T.

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

◆ bitcount64_4way()

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

inlinenoexcept

Parallel popcount on 4x 64-bit words

Definition at line 248 of file bmfunc.h.

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

◆ bitscan()

template<typename V , typename B >

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

noexcept

Templated Bitscan with dynamic dispatch for best type.

Definition at line 769 of file bmfunc.h.

References bm::bitscan_bsf(), bm::bitscan_bsf64(), bm::bitscan_popcnt(), bm::bitscan_popcnt64(), and rapidjson::value.

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

◆ bitscan_bsf()

template<typename B >

unsigned short bm::bitscan_bsf	(	unsigned	w,
		B *	bits
	)

noexcept

Unpacks word into list of ON bits (BSF/__builtin_ctz)

Parameters

w	- value
bits	- pointer on the result array

Returns: number of bits in the list

Definition at line 697 of file bmfunc.h.

References B, and bm::count_trailing_zeros_u32().

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

◆ bitscan_bsf64()

template<typename B >

unsigned short bm::bitscan_bsf64	(	bm::id64_t	w,
		B *	bits
	)

noexcept

Unpacks word into list of ON bits (BSF/__builtin_ctz)

Parameters

w	- value
bits	- pointer on the result array

Returns: number of bits in the list

Definition at line 730 of file bmfunc.h.

References B, and bm::count_trailing_zeros_u64().

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

◆ bitscan_popcnt() [1/2]

template<typename B >

unsigned short bm::bitscan_popcnt	(	bm::id_t	w,
		B *	bits
	)

noexcept

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

Parameters

w	- value
bits	- pointer on the result array

Returns: number of bits in the list

Definition at line 654 of file bmfunc.h.

References B, t, and bm::word_bitcount().

◆ bitscan_popcnt() [2/2]

template<typename B >

unsigned short bm::bitscan_popcnt	(	bm::id_t	w,
		B *	bits,
		unsigned short	offs
	)

noexcept

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

Parameters

w	- value
bits	- pointer on the result array
offs	- value to add to bit position (programmed shift)

Returns: number of bits in the list

Definition at line 632 of file bmfunc.h.

References B, t, and bm::word_bitcount().

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

◆ bitscan_popcnt64() [1/2]

template<typename B >

unsigned short bm::bitscan_popcnt64	(	bm::id64_t	w,
		B *	bits
	)

noexcept

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

Parameters

w	- value
bits	- pointer on the result array

Returns: number of bits in the list

Definition at line 675 of file bmfunc.h.

References B, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), t, and bm::word_bitcount64().

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

◆ bitscan_popcnt64() [2/2]

template<typename B >

unsigned short bm::bitscan_popcnt64	(	bm::id64_t	w,
		B *	bits,
		unsigned short	offs
	)

noexcept

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

Parameters

w	- value
bits	- pointer on the result array
offs	- value to add to bit position (programmed shift)

Returns: number of bits in the list

Definition at line 752 of file bmfunc.h.

References B, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), t, and bm::word_bitcount64().

◆ bitscan_wave()

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

inlinenoexcept

Unpacks word wave (Nx 32-bit words)

Parameters

w_ptr	- pointer on wave start
bits	- pointer on the result array

Returns: number of bits in the list

Definition at line 9635 of file bmfunc.h.

References bm::bitscan_bsf(), bm::bitscan_popcnt(), and bm::bitscan_popcnt64().

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

◆ block_compact_by_digest()

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

inlinenoexcept

Compact sub-blocks by digest (rank compaction)

Parameters

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

Definition at line 1211 of file bmfunc.h.

References bm::block_waves, bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), bm::set_block_digest_wave_size, t, and bm::word_bitcount64().

Referenced by TestBlockExpandCompact().

◆ block_expand_by_digest()

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

inlinenoexcept

expand sub-blocks by digest (rank expansion)

Parameters

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

Definition at line 1278 of file bmfunc.h.

References bm::block_waves, and bm::set_block_digest_wave_size.

Referenced by TestBlockExpandCompact().

◆ block_init_digest0()

void bm::block_init_digest0	(	bm::word_t *const	block,
		bm::id64_t	digest
	)

inlinenoexcept

Init block with 000111000 pattren based on digest.

Parameters

block	- Bit block [out]
digest	- digest (used for block initialization)

Definition at line 1092 of file bmfunc.h.

References BM_ASSERT, i, mask, bm::set_block_digest_wave_size, and VECT_BLOCK_SET_DIGEST.

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

◆ calc_block_digest0()

bm::id64_t bm::calc_block_digest0 ( const bm::word_t *const block )

inlinenoexcept

Compute digest for 64 non-zero areas.

Parameters

block - Bit block

Returns: digest bit-mask (0 means all block is empty)

Definition at line 1120 of file bmfunc.h.

References i, mask, bm::set_block_digest_wave_size, and VECT_IS_DIGEST_ZERO.

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

◆ check_zero_digest()

bool bm::check_zero_digest	(	bm::id64_t	digest,
		unsigned	bitpos_from,
		unsigned	bitpos_to
	)

inlinenoexcept

check if all digest bits for the range [from..to] are 0

Parameters

digest	- current digest
bitpos_from	- range from (in bit-block coordinates)
bitpos_to	- range to (in bit-block coordinates)

Returns: true if all range is zero

Definition at line 1054 of file bmfunc.h.

References bm::digest_mask(), and mask.

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

◆ clear_bit()

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

inlinenoexcept

Set 1 bit in a block.

Definition at line 3734 of file bmfunc.h.

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

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

◆ count_leading_zeros()

unsigned bm::count_leading_zeros ( unsigned x )

inlinenoexcept

Portable LZCNT with (uses minimal LUT)

Definition at line 173 of file bmutil.h.

References n.

Referenced by bm::count_leading_zeros_u32(), and LZCNTTest().

◆ count_trailing_zeros()

unsigned bm::count_trailing_zeros ( unsigned v )

inlinenoexcept

Portable TZCNT with (uses 37-LUT)

Definition at line 189 of file bmutil.h.

Referenced by LZCNTTest().

◆ digest_mask()

bm::id64_t bm::digest_mask	(	unsigned	from,
		unsigned	to
	)

inlinenoexcept

Compute digest mask for [from..to] positions.

Parameters

from	- range from (in bit-block coordinates)
to	- range to (in bit-block coordinates)

Definition at line 1025 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, mask, and bm::set_block_digest_pos_shift.

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

◆ for_each_bit_blk() [1/2]

template<typename Func , typename SIZE_TYPE >

int bm::for_each_bit_blk	(	const bm::word_t *	block,
		SIZE_TYPE	offset,
		Func &	bit_functor
	)

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

Parameters

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

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

Definition at line 1597 of file bmalgo_impl.h.

References bm::bitscan_wave(), BM_ASSERT, cnt, bm::gap_max_bits, IS_FULL_BLOCK, offset, bm::set_bitscan_wave_size, and bm::set_block_size.

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

◆ for_each_bit_blk() [2/2]

template<typename Func , typename SIZE_TYPE >

int bm::for_each_bit_blk	(	const bm::word_t *	block,
		SIZE_TYPE	offset,
		unsigned	left,
		unsigned	right,
		Func &	bit_functor
	)

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

Parameters

block	- bit block buffer pointer
offset	- global block offset (number of bits)
left	- bit addredd in block from [from..to]
right	- bit addredd in block to [from..to]
bit_functor	- functor must support .add_bits(offset, bits_ptr, size)

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

Definition at line 1637 of file bmalgo_impl.h.

References bm::bits_in_block, bm::bitscan(), bm::bitscan_wave(), BM_ASSERT, cnt, IS_FULL_BLOCK, mask, bm::mask_l_u32(), bm::mask_r_u32(), offset, bm::set_bitscan_wave_size, bm::set_word_mask, and bm::set_word_shift.

◆ is_bits_one()

bool bm::is_bits_one ( const bm::wordop_t * start )

inlinenoexcept

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

Definition at line 6081 of file bmfunc.h.

References bm::all_bits_mask, BMRESTRICT, bm::set_block_size, tmp, and VECT_IS_ONE_BLOCK.

Referenced by bm::check_block_one(), bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), bm::blocks_manager< Alloc >::opt_copy_bit_block(), bm::blocks_manager< Alloc >::optimize_block(), and bm::aggregator< BV >::process_bit_blocks_or().

◆ or_bit_block()

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

inlinenoexcept

Sets bits to 1 in the bitblock.

Parameters

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

Definition at line 3766 of file bmfunc.h.

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

Referenced by BlockBitEraseTest(), bm::gap_add_to_bitset(), and GAPCheck().

◆ set_bit()

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

inlinenoexcept

Set 1 bit in a block.

Definition at line 3721 of file bmfunc.h.

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

Referenced by CJobStatusTracker::AddPendingJob(), CNcbi2naRandomizer::CNcbi2naRandomizer(), bm::deserializer< BV, DEC >::decode_arrbit(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_arr_bit(), bm::random_subset< BV >::get_random_array(), bm::deseriaizer_base< DEC, BLOCK_IDX >::read_bic_arr(), TestBlockExpandCompact(), and TestFindBlockDiff().

◆ sub_bit_block()

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

inlinenoexcept

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

Parameters

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

Definition at line 3811 of file bmfunc.h.

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

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

◆ test_bit()

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

inlinenoexcept

Test 1 bit in a block.

Definition at line 3748 of file bmfunc.h.

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

Referenced by BlockBitEraseTest(), and BlockBitInsertTest().

◆ tmatrix_distance()

template<typename T , unsigned BPC, unsigned BPS>

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

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

Parameters

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

Definition at line 315 of file bmtrans.h.

References bm::bit_block_count(), count, i, r1, r2, r3, T, and bm::word_bitcount().

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

◆ update_block_digest0()

bm::id64_t bm::update_block_digest0	(	const bm::word_t *const	block,
		bm::id64_t	digest
	)

inlinenoexcept

Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas)

Parameters

block	- bit block
digest	- start digest

Returns: digest bit-mask (0 means all block is empty)

Definition at line 1162 of file bmfunc.h.

References bm::bmi_blsi_u64(), bm::bmi_bslr_u64(), BMRESTRICT, mask, bm::set_block_digest_wave_size, t, VECT_IS_DIGEST_ZERO, and bm::word_bitcount64().

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

◆ widx_to_digest_mask()

bm::id64_t bm::widx_to_digest_mask ( unsigned w_idx )

inlinenoexcept

Compute digest mask for word address in block.

Returns: digest bit-mask

Definition at line 997 of file bmfunc.h.

References mask, and bm::set_block_digest_wave_size.

Referenced by TestBlockDigest().

◆ word_bitcount()

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

inlinenoexcept

Returns bit count

Definition at line 582 of file bmutil.h.

References _mm_popcnt_u32().

Referenced by bm::sparse_vector_scanner< bm::rsc_sparse_vector >::add_agg_char(), bm::bit_block_and_count(), bm::bit_block_calc_count_range(), bm::bit_block_calc_count_to(), bm::bit_block_change32(), bm::bit_block_count(), bm::bit_block_or_count(), bm::bit_block_sub_count(), bm::bit_block_xor_change32(), bm::bit_block_xor_count(), bm::bit_count_change(), bm::bit_count_min_unroll(), bm::bit_find_first_if_1(), bm::bit_find_rank(), bm::bitscan_popcnt(), bm::bvector< Alloc >::enumerator::decode_bit_group(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_AND(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_OR(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_SUB_AB(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_SUB_BA(), bm::serial_stream_iterator< DEC, BLOCK_IDX >::get_bit_block_COUNT_XOR(), bm::str_sparse_vector< CharType, BV, STR_SIZE >::import_char_slice(), bm::bit_COUNT< W >::operator()(), bm::bit_COUNT_AND< W >::operator()(), bm::bit_COUNT_XOR< W >::operator()(), bm::bit_COUNT_OR< W >::operator()(), bm::bit_COUNT_SUB_AB< W >::operator()(), bm::bit_COUNT_SUB_BA< W >::operator()(), bm::bit_COUNT_A< W >::operator()(), bm::bit_COUNT_B< W >::operator()(), bm::random_subset< BV >::process_word(), SelectTest(), bm::sse2_bit_block_calc_count_change(), sx_CalcByteBitCount(), bm::tmatrix_distance(), bm::word_bitcount64(), bm::word_select32_bitscan_popcnt(), and bm::word_select32_bitscan_tz().

◆ word_bitcount64()

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

inlinenoexcept

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

Definition at line 605 of file bmutil.h.

References _mm_popcnt_u32(), _mm_popcnt_u64(), and bm::word_bitcount().

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

◆ word_select32()

unsigned bm::word_select32	(	unsigned	w,
		unsigned	rank
	)

inlinenoexcept

word find index of the rank-th bit set by bit-testing

Parameters

w	- 32-bit work to search
rank	- rank to select (should be > 0)

Returns: selected value (inxed of bit set)

Definition at line 965 of file bmfunc.h.

References bm::word_select32_bitscan_popcnt(), and bm::word_select32_bitscan_tz().

Referenced by bm::bit_find_rank().

◆ word_select32_bitscan_popcnt()

unsigned bm::word_select32_bitscan_popcnt	(	unsigned	w,
		unsigned	rank
	)

inlinenoexcept

word find index of the rank-th bit set by bit-testing

Parameters

w	- 32-bit work to search
rank	- rank to select (should be > 0)

Returns: selected value (inxed of bit set)

Definition at line 883 of file bmfunc.h.

References BM_ASSERT, count, t, and bm::word_bitcount().

Referenced by SelectTest(), and bm::word_select32().

◆ word_select32_bitscan_tz()

unsigned bm::word_select32_bitscan_tz	(	unsigned	w,
		unsigned	rank
	)

inlinenoexcept

word find index of the rank-th bit set by bit-testing

Parameters

w	- 32-bit work to search
rank	- rank to select (should be > 0)

Returns: selected value (inxed of bit set)

Definition at line 912 of file bmfunc.h.

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

Referenced by SelectTest(), and bm::word_select32().

◆ word_select64()

unsigned bm::word_select64	(	bm::id64_t	w,
		unsigned	rank
	)

inlinenoexcept

word find index of the rank-th bit set by bit-testing

Parameters

w	- 64-bit work to search
rank	- rank to select (should be > 0)

Returns: selected value (inxed of bit set)

Definition at line 938 of file bmfunc.h.

References bm::word_select64_bitscan_popcnt(), and bm::word_select64_bitscan_tz().

Referenced by bm::bit_find_rank().

◆ word_select64_bitscan_popcnt()

unsigned bm::word_select64_bitscan_popcnt	(	bm::id64_t	w,
		unsigned	rank
	)

inlinenoexcept

word find index of the rank-th bit set by bit-testing

Parameters

w	- 64-bit work to search
rank	- rank to select (should be > 0)

Returns: selected value (inxed of bit set)

Definition at line 825 of file bmfunc.h.

References BM_ASSERT, count, t, and bm::word_bitcount64().

Referenced by SelectTest(), and bm::word_select64().

◆ word_select64_bitscan_tz()

unsigned bm::word_select64_bitscan_tz	(	bm::id64_t	w,
		unsigned	rank
	)

inlinenoexcept

word find index of the rank-th bit set by bit-testing

Parameters

w	- 64-bit work to search
rank	- rank to select (should be > 0)

Returns: selected value (inxed of bit set)

Definition at line 854 of file bmfunc.h.

References BM_ASSERT, count, bm::count_trailing_zeros_u64(), t, and bm::word_bitcount64().

Referenced by SelectTest(), and bm::word_select64().

◆ word_select64_linear()

unsigned bm::word_select64_linear	(	bm::id64_t	w,
		unsigned	rank
	)

inlinenoexcept

word find index of the rank-th bit set by bit-testing

Parameters

w	- 64-bit work to search
rank	- rank to select (should be > 0)

Returns: selected value (inxed of bit set)

Definition at line 799 of file bmfunc.h.

References BM_ASSERT, and count.

Referenced by proxy_bmi1_select64_lz(), proxy_bmi1_select64_tz(), proxy_bmi2_select64_pdep(), and SelectTest().

◆ wordcmp()

template<typename T >

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

noexcept

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

Parameters

a	- First word.
b	- Second word.

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

Definition at line 1532 of file bmfunc.h.

References a, b, and T.

Referenced by WordCmpTest().

◆ wordcmp0()

template<typename T >

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

noexcept

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

Parameters

w1	- First word.
w2	- Second word.

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

Definition at line 1503 of file bmfunc.h.

Referenced by WordCmpTest().

◆ xor_bit_block()

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

inlinenoexcept

XOR bit interval to 1 in the bitblock.

Parameters

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

Definition at line 3854 of file bmfunc.h.

References mask, bm::mask_l_u32(), bm::mask_r_u32(), bm::set_block_mask, bm::set_word_mask, and bm::set_word_shift.

Referenced by bm::gap_xor_to_bitset().

Classes

Functions

Detailed Description

Function Documentation

◆ best_representation()

◆ bit_andnot_arr_ffmask()

◆ bit_block_and() [1/2]

◆ bit_block_and() [2/2]

◆ bit_block_and_2way()

◆ bit_block_and_3way()

◆ bit_block_and_5way()

◆ bit_block_and_any()

◆ bit_block_and_count()

◆ bit_block_and_or_2way()

◆ bit_block_any_range()

◆ bit_block_calc_change()

◆ bit_block_calc_count_range()

◆ bit_block_calc_count_to()

◆ bit_block_convert_to_arr()

◆ bit_block_copy()

◆ bit_block_copy_unalign()

◆ bit_block_count() [1/2]

◆ bit_block_count() [2/2]

◆ bit_block_erase()

◆ bit_block_find()

◆ bit_block_find_interval_end()

◆ bit_block_find_interval_start()

◆ bit_block_find_prev()

◆ bit_block_gather_scatter()

◆ bit_block_init_and_2way()

◆ bit_block_insert()

◆ bit_block_is_all_one_range()

◆ bit_block_or()

◆ bit_block_or_2way()

◆ bit_block_or_3way()

◆ bit_block_or_5way()

◆ bit_block_or_any()

◆ bit_block_or_count()

◆ bit_block_rotate_left_1()

◆ bit_block_rotate_left_1_unr()

◆ bit_block_set()

◆ bit_block_shift_l1()

◆ bit_block_shift_l1_unr()

◆ bit_block_shift_l1_unr_min()

◆ bit_block_shift_r1()

◆ bit_block_shift_r1_and()

◆ bit_block_shift_r1_and_unr()

◆ bit_block_shift_r1_unr()

◆ bit_block_shift_r1_unr_min()

◆ bit_block_stream()

◆ bit_block_stream_unalign()

◆ bit_block_sub() [1/2]

◆ bit_block_sub() [2/2]

◆ bit_block_sub_2way()

◆ bit_block_sub_3way()

◆ bit_block_sub_5way()

◆ bit_block_sub_any()

◆ bit_block_sub_count()

◆ bit_block_xor()

◆ bit_block_xor_2way()

◆ bit_block_xor_any()

◆ bit_block_xor_change32()

◆ bit_block_xor_change64()

◆ bit_block_xor_count()

◆ bit_count_change()

◆ bit_count_min_unroll()

◆ bit_count_nonzero_size()

◆ bit_find_first() [1/2]

◆ bit_find_first() [2/2]

◆ bit_find_first_diff()

◆ bit_find_first_if_1()

◆ bit_find_last()

◆ bit_find_rank()

◆ bit_for_each()

◆ bit_for_each_4()

◆ bit_iblock_make_pcv()

◆ bit_invert()

◆ bit_is_all_zero()

◆ bit_list()

◆ bit_list_4()