# BIT functions
[BitMagic C++ Library]

Collaboration diagram for BIT functions:

## Data Structures

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

## Defines

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

## Functions

BMFORCEINLINE bm::id_t | bm::word_bitcount (bm::id_t w)
template<typename T >
int | bm::wordcmp0 (T w1, T w2)
| Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes.
template<typename T >
int | bm::wordcmp (T a, T b)
| Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes.
BMFORCEINLINE void | bm::set_bit (unsigned *dest, unsigned bitpos)
| Set 1 bit in a block.
BMFORCEINLINE unsigned | bm::test_bit (const unsigned *block, unsigned bitpos)
| Test 1 bit in a block.
void | bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
| Sets bits to 1 in the bitblock.
void | bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
| SUB (AND NOT) bit interval to 1 in the bitblock.
void | bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
| XOR bit interval to 1 in the bitblock.
template<typename T >
bm::id_t | bm::gap_bitset_and_count (const unsigned *block, const T *buf)
| Compute bitcount of bit block AND masked by GAP block.
template<typename T >
bm::id_t | bm::gap_bitset_and_any (const unsigned *block, const T *buf)
| Bitcount test of bit block AND masked by GAP block.
template<typename T >
bm::id_t | bm::gap_bitset_sub_count (const unsigned *block, const T *buf)
| Compute bitcount of bit block SUB masked by GAP block.
template<typename T >
bm::id_t | bm::gap_bitset_sub_any (const unsigned *block, const T *buf)
| Compute bitcount test of bit block SUB masked by GAP block.
template<typename T >
bm::id_t | bm::gap_bitset_xor_count (const unsigned *block, const T *buf)
| Compute bitcount of bit block XOR masked by GAP block.
template<typename T >
bm::id_t | bm::gap_bitset_xor_any (const unsigned *block, const T *buf)
| Compute bitcount test of bit block XOR masked by GAP block.
template<typename T >
bm::id_t | bm::gap_bitset_or_count (const unsigned *block, const T *buf)
| Compute bitcount of bit block OR masked by GAP block.
template<typename T >
bm::id_t | bm::gap_bitset_or_any (const unsigned *block, const T *buf)
| Compute bitcount test of bit block OR masked by GAP block.
void | bm::bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value)
| Bitblock memset operation.
template<typename T >
int | bm::bitcmp (const T *buf1, const T *buf2, unsigned len)
| Lexicographical comparison of BIT buffers.
bm::id_t | bm::bit_block_calc_count (const bm::word_t *block, const bm::word_t *block_end)
| Bitcount for bit string.
bm::id_t | bm::bit_count_change (bm::word_t w)
bm::id_t | bm::bit_block_calc_count_change (const bm::word_t *block, const bm::word_t *block_end, unsigned *bit_count)
bm::id_t | bm::bit_block_calc_count_range (const bm::word_t *block, bm::word_t left, bm::word_t right)
bm::id_t | bm::bit_block_any_range (const bm::word_t *block, bm::word_t left, bm::word_t right)
template<typename T >
void | bm::bit_invert (T *start, T *end)
bool | bm::is_bits_one (const bm::wordop_t *start, const bm::wordop_t *end)
| Returns "true" if all bits in the block are 1.
bool | bm::bit_is_all_zero (const bm::wordop_t *start, const bm::wordop_t *end)
| Returns "true" if all bits in the block are 0.
void | bm::bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| Bitblock copy operation.
void | bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| Plain bitblock AND operation. Function does not analyse availability of source and destination blocks.
unsigned | bm::bit_block_and_count (const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2)
| Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.
unsigned | bm::bit_block_and_any (const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2)
| Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks.
unsigned | bm::bit_block_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.
unsigned | bm::bit_block_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.
unsigned | bm::bit_block_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.
unsigned | bm::bit_block_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.
unsigned | bm::bit_block_or_count (const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2)
| Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks.
unsigned | bm::bit_block_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks.
bm::word_t * | bm::bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| bitblock AND operation.
bm::id_t | bm::bit_operation_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs bitblock AND operation and calculates bitcount of the result.
bm::id_t | bm::bit_operation_and_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs bitblock AND operation test.
bm::id_t | bm::bit_operation_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs bitblock SUB operation and calculates bitcount of the result.
bm::id_t | bm::bit_operation_sub_count_inv (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs inverted bitblock SUB operation and calculates bitcount of the result.
bm::id_t | bm::bit_operation_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs bitblock test of SUB operation.
bm::id_t | bm::bit_operation_or_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs bitblock OR operation and calculates bitcount of the result.
bm::id_t | bm::bit_operation_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs bitblock OR operation test.
void | bm::bit_block_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.
bm::word_t * | bm::bit_operation_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| Block OR operation. Makes analysis if block is 0 or FULL.
void | bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks.
bm::word_t * | bm::bit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| bitblock SUB operation.
void | bm::bit_block_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks.
bm::word_t * | bm::bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
| bitblock XOR operation.
bm::id_t | bm::bit_operation_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs bitblock XOR operation and calculates bitcount of the result.
bm::id_t | bm::bit_operation_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2)
| Performs bitblock XOR operation test.
template<class T >
unsigned | bm::bit_count_nonzero_size (const T *blk, unsigned data_size)
| Inspects block for full zero words.
int | bm::bit_find_in_block (const bm::word_t *data, unsigned nbit, bm::id_t *prev)
| Searches for the next 1 bit in the BIT block.
template<typename T , typename F >
void | bm::bit_for_each_4 (T w, F &func)
| Templated algorithm to unpacks octet based word into list of ON bit indexes.
template<typename T , typename F >
void | bm::bit_for_each (T w, F &func)
| Templated algorithm to unpacks word into list of ON bit indexes.
template<typename T , typename B >
unsigned | bm::bit_list_4 (T w, B *bits)
| Unpacks word into list of ON bit indexes (quad-bit based).
template<typename T , typename B >
unsigned | bm::bit_list (T w, B *bits)
| Unpacks word into list of ON bit indexes.
bm::set_representation | bm::best_representation (unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size)
| Choose best representation for a bit-block.
template<typename T >
T | bm::bit_convert_to_arr (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len, unsigned mask=0)
| Convert bit block into an array of ints corresponding to 1 bits.
template<typename T , unsigned BPC, unsigned BPS>
void | bm::tmatrix_distance (const T tmatrix[BPC][BPS], unsigned distance[BPC][BPC])
| Compute pairwise Row x Row Humming distances on plains(rows) of the transposed bit block.
template<typename T , unsigned BPC, unsigned BPS>
void | bm::bit_iblock_make_pcv (const unsigned distance[BPC][BPC], unsigned char *pc_vector)
| !< ibpc limiter

## Detailed Description

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

## Define Documentation

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

Define calculates number of 1 bits in 32-bit word.

Definition at line 159 of file bmdef.h.

Referenced by bm::bit_block_and_count(), bm::bit_block_calc_count(), bm::bit_block_calc_count_range(), bm::bit_block_or_count(), bm::bit_block_sub_count(), bm::bit_block_xor_count(), bm::bit_count_change(), bm::bit_count_change32(), bm::bit_COUNT_B< W >::operator()(), bm::bit_COUNT_A< W >::operator()(), bm::bit_COUNT_SUB_BA< W >::operator()(), bm::bit_COUNT_SUB_AB< W >::operator()(), bm::bit_COUNT_OR< W >::operator()(), bm::bit_COUNT_XOR< W >::operator()(), bm::bit_COUNT_AND< W >::operator()(), bm::bit_COUNT< W >::operator()(), bm::sse2_bit_block_calc_count_change(), and bm::tmatrix_distance().

## Function Documentation

bm::set_representation bm::best_representation | ( | unsigned | bit_count,
|  | unsigned | total_possible_bitcount,
|  | unsigned | gap_count,
|  | unsigned | block_size |
| ) |  |  | `[inline]`

Choose best representation for a bit-block.

Definition at line 4713 of file bmfunc.h.

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

Referenced by bm::compute_tmatrix_rstat().

void bm::bit_block_and | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

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

Parameters:

  | dst | - destination block.
  | src | - source block.

Definition at line 3446 of file bmfunc.h.

References bm::set_block_size, and VECT_AND_ARR.

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

unsigned bm::bit_block_and_any | ( | const bm::word_t * | src1,
|  | const bm::word_t * | src1_end,
|  | const bm::word_t * | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 3530 of file bmfunc.h.

Referenced by bm::bit_operation_and_any().

unsigned bm::bit_block_and_count | ( | const bm::word_t * | src1,
|  | const bm::word_t * | src1_end,
|  | const bm::word_t * | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 3480 of file bmfunc.h.

References BM_INCWORD_BITCOUNT, and VECT_BITCOUNT_AND.

Referenced by bm::bit_operation_and_count().

bm::id_t bm::bit_block_any_range | ( | const bm::word_t * | block,
|  | bm::word_t | left,
|  | bm::word_t | right |
| ) |  |  | `[inline]`

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

Definition at line 3016 of file bmfunc.h.

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

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

bm::id_t bm::bit_block_calc_count | ( | const bm::word_t * | block,
|  | const bm::word_t * | block_end |
| ) |  |  | `[inline]`

Bitcount for bit string.

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

Definition at line 2726 of file bmfunc.h.

References BM_ASSERT, BM_INCWORD_BITCOUNT, and VECT_BITCOUNT.

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

bm::id_t bm::bit_block_calc_count_change | ( | const bm::word_t * | block,
|  | const bm::word_t * | block_end,
|  | unsigned * | bit_count |
| ) |  |  | `[inline]`

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

Parameters:

  | bit_count | - OUT total number of bits ON

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

Definition at line 2864 of file bmfunc.h.

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

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

bm::id_t bm::bit_block_calc_count_range | ( | const bm::word_t * | block,
|  | bm::word_t | left,
|  | bm::word_t | right |
| ) |  |  | `[inline]`

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

Definition at line 2950 of file bmfunc.h.

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

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

void bm::bit_block_copy | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

Bitblock copy operation.

Parameters:

  | dst | - destination block.
  | src | - source block.

Definition at line 3426 of file bmfunc.h.

References bm::set_block_size, and VECT_COPY_BLOCK.

void bm::bit_block_or | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

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

Parameters:

  | dst | - destination block.
  | src | - source block.

Definition at line 4060 of file bmfunc.h.

References bm::set_block_size, and VECT_OR_ARR.

Referenced by bm::bit_operation_or().

unsigned bm::bit_block_or_any | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 3770 of file bmfunc.h.

Referenced by bm::bit_operation_or_any().

unsigned bm::bit_block_or_count | ( | const bm::word_t * | src1,
|  | const bm::word_t * | src1_end,
|  | const bm::word_t * | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 3721 of file bmfunc.h.

References BM_INCWORD_BITCOUNT, and VECT_BITCOUNT_OR.

Referenced by bm::bit_operation_or_count().

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

Bitblock memset operation.

Parameters:

  | dst | - destination block.
  | value | - value to set.

Definition at line 2126 of file bmfunc.h.

References bm::set_block_size.

Referenced by bm::deserializer< BV, DEC >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), bm::gap_convert_to_bitset(), bm::gap_convert_to_bitset_l(), bm::serial_stream_iterator< DEC >::get_arr_bit(), bm::serial_stream_iterator< DEC >::get_bit_block_ASSIGN(), and bm::gap_transpose_engine< GT, BT, BLOCK_SIZE >::transpose().

void bm::bit_block_sub | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

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

Parameters:

  | dst | - destination block.
  | src | - source block.

Definition at line 4156 of file bmfunc.h.

References bm::set_block_size, and VECT_SUB_ARR.

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

unsigned bm::bit_block_sub_any | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 3691 of file bmfunc.h.

Referenced by bm::bit_operation_sub_any().

unsigned bm::bit_block_sub_count | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 3642 of file bmfunc.h.

References BM_INCWORD_BITCOUNT, and VECT_BITCOUNT_SUB.

Referenced by bm::bit_operation_sub_count().

void bm::bit_block_xor | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

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

Parameters:

  | dst | - destination block.
  | src | - source block.

Definition at line 4252 of file bmfunc.h.

References bm::set_block_size, and VECT_XOR_ARR.

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

unsigned bm::bit_block_xor_any | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 3611 of file bmfunc.h.

Referenced by bm::bit_operation_xor_any().

unsigned bm::bit_block_xor_count | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 3561 of file bmfunc.h.

References BM_INCWORD_BITCOUNT, and VECT_BITCOUNT_XOR.

Referenced by bm::bit_operation_xor_count().

template<typename T >

T bm::bit_convert_to_arr | ( | T *BMRESTRICT | dest,
|  | const unsigned *BMRESTRICT | src,
|  | bm::id_t | bits,
|  | unsigned | dest_len,
|  | unsigned | mask = `0` |
| ) |  |  | `[inline]`

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

Definition at line 4748 of file bmfunc.h.

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

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

bm::id_t bm::bit_count_change | ( | bm::word_t | w | ) | `[inline]`

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

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

Definition at line 2786 of file bmfunc.h.

References BM_INCWORD_BITCOUNT.

template<class T >

unsigned bm::bit_count_nonzero_size | ( | const T * | blk,
|  | unsigned | data_size |
| ) |  |  | `[inline]`

Inspects block for full zero words.

Parameters:

  | data | - bit block pointer
  | data_size | - data size

Returns:
  size of all non-zero words

Definition at line 4384 of file bmfunc.h.

References BM_ASSERT.

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

int bm::bit_find_in_block | ( | const bm::word_t * | data,
|  | unsigned | nbit,
|  | bm::id_t * | prev |
| ) |  |  | `[inline]`

Searches for the next 1 bit in the BIT block.

Parameters:

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

Definition at line 4445 of file bmfunc.h.

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

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

template<typename T , typename F >

void bm::bit_for_each | ( | T | w,
|  | F & | func |
| ) |  |  | `[inline]`

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

Parameters:

  | w | - value
  | func | - bit functor

Definition at line 4562 of file bmfunc.h.

Referenced by bm::bit_list().

template<typename T , typename F >

void bm::bit_for_each_4 | ( | T | w,
|  | F & | func |
| ) |  |  | `[inline]`

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

Parameters:

  | w | - value
  | func | - bit functor

Definition at line 4492 of file bmfunc.h.

References BM_ASSERT.

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

template<typename T , unsigned BPC, unsigned BPS>

void bm::bit_iblock_make_pcv | ( | const unsigned | distance[BPC][BPC],
|  | unsigned char * | pc_vector |
| ) |  |  | `[inline]`

!< ibpc limiter

Make a compression descriptor vector for bit-plains

Parameters:

  | distance | - pairwise distance matrix

  pc_vector

  - OUT compression descriptor vector

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

Definition at line 418 of file bmtrans.h.

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

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

template<typename T >

void bm::bit_invert | ( | T * | start,
|  | T * | end |
| ) |  |  | `[inline]`

Function inverts block of bits

Definition at line 3081 of file bmfunc.h.

References VECT_INVERT_ARR.

bool bm::bit_is_all_zero | ( | const bm::wordop_t * | start,
|  | const bm::wordop_t * | end |
| ) |  |  | `[inline]`

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

Definition at line 3123 of file bmfunc.h.

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

template<typename T , typename B >

unsigned bm::bit_list | ( | T | w,
|  | B * | bits |
| ) |  |  | `[inline]`

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

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

template<typename T , typename B >

unsigned bm::bit_list_4 | ( | T | w,
|  | B * | bits |
| ) |  |  | `[inline]`

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

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

Referenced by bm::bvector< Alloc >::enumerator::go_up().

bm::word_t* bm::bit_operation_and | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

bitblock AND operation.

Parameters:

  | dst | - destination block.
  | src | - source block.

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

Definition at line 3802 of file bmfunc.h.

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

bm::id_t bm::bit_operation_and_any | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

Performs bitblock AND operation test.

Parameters:

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

Returns:
  non zero if there is any value

Definition at line 3890 of file bmfunc.h.

References bm::bit_block_and_any(), and IS_EMPTY_BLOCK.

Referenced by bm::combine_any_operation_with_block().

bm::id_t bm::bit_operation_and_count | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

Performs bitblock AND operation and calculates bitcount of the result.

Parameters:

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

Returns:
  bitcount value

Definition at line 3867 of file bmfunc.h.

References bm::bit_block_and_count(), and IS_EMPTY_BLOCK.

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

bm::word_t* bm::bit_operation_or | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

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

Parameters:

  | dst | - destination block.
  | src | - source block.

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

Definition at line 4098 of file bmfunc.h.

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

bm::id_t bm::bit_operation_or_any | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

Performs bitblock OR operation test.

Parameters:

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

Returns:
  non zero value if there are any bits

Definition at line 4028 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

bm::id_t bm::bit_operation_or_count | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

Performs bitblock OR operation and calculates bitcount of the result.

Parameters:

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

Returns:
  bitcount value

Definition at line 3996 of file bmfunc.h.

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

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

bm::word_t* bm::bit_operation_sub | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

bitblock SUB operation.

Parameters:

  | dst | - destination block.
  | src | - source block.

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

Definition at line 4196 of file bmfunc.h.

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

bm::id_t bm::bit_operation_sub_any | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

Performs bitblock test of SUB operation.

Parameters:

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

Returns:
  non zero value if there are any bits

Definition at line 3966 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

bm::id_t bm::bit_operation_sub_count | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

Performs bitblock SUB operation and calculates bitcount of the result.

Parameters:

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

Returns:
  bitcount value

Definition at line 3915 of file bmfunc.h.

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

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

bm::id_t bm::bit_operation_sub_count_inv | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

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

Parameters:

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

Returns:
  bitcount value

Definition at line 3945 of file bmfunc.h.

References bm::bit_operation_sub_count().

bm::word_t* bm::bit_operation_xor | ( | bm::word_t *BMRESTRICT | dst,
|  | const bm::word_t *BMRESTRICT | src |
| ) |  |  | `[inline]`

bitblock XOR operation.

Parameters:

  | dst | - destination block.
  | src | - source block.

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

Definition at line 4292 of file bmfunc.h.

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

bm::id_t bm::bit_operation_xor_any | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

Performs bitblock XOR operation test.

Parameters:

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

Returns:
  non zero value if there are bits

Definition at line 4355 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

bm::id_t bm::bit_operation_xor_count | ( | const bm::word_t *BMRESTRICT | src1,
|  | const bm::word_t *BMRESTRICT | src1_end,
|  | const bm::word_t *BMRESTRICT | src2 |
| ) |  |  | `[inline]`

Performs bitblock XOR operation and calculates bitcount of the result.

Parameters:

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

Returns:
  bitcount value

Definition at line 4330 of file bmfunc.h.

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

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

template<typename T >

int bm::bitcmp | ( | const T * | buf1,
|  | const T * | buf2,
|  | unsigned | len |
| ) |  |  | `[inline]`

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

References BM_ASSERT.

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

template<typename T >

bm::id_t bm::gap_bitset_and_any | ( | const unsigned * | block,
|  | const T * | buf |
| ) |  |  | `[inline]`

Bitcount test of bit block AND masked by GAP block.

Parameters:

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

Definition at line 1837 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

Referenced by bm::combine_any_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_and_count | ( | const unsigned * | block,
|  | const T * | buf |
| ) |  |  | `[inline]`

Compute bitcount of bit block AND masked by GAP block.

Parameters:

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

Definition at line 1806 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

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

template<typename T >

bm::id_t bm::gap_bitset_or_any | ( | const unsigned * | block,
|  | const T * | buf |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 2075 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

Referenced by bm::combine_any_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_or_count | ( | const unsigned * | block,
|  | const T * | buf |
| ) |  |  | `[inline]`

Compute bitcount of bit block OR masked by GAP block.

Parameters:

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

Definition at line 2028 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

Referenced by bm::combine_count_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_sub_any | ( | const unsigned * | block,
|  | const T * | buf |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 1909 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

Referenced by bm::combine_any_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_sub_count | ( | const unsigned * | block,
|  | const T * | buf |
| ) |  |  | `[inline]`

Compute bitcount of bit block SUB masked by GAP block.

Parameters:

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

Definition at line 1876 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

Referenced by bm::combine_count_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_xor_any | ( | const unsigned * | block,
|  | const T * | buf |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 1985 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

Referenced by bm::combine_any_operation_with_block().

template<typename T >

bm::id_t bm::gap_bitset_xor_count | ( | const unsigned * | block,
|  | const T * | buf |
| ) |  |  | `[inline]`

Compute bitcount of bit block XOR masked by GAP block.

Parameters:

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

Definition at line 1947 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

Referenced by bm::combine_count_operation_with_block().

bool bm::is_bits_one | ( | const bm::wordop_t * | start,
|  | const bm::wordop_t * | end |
| ) |  |  | `[inline]`

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

Definition at line 3102 of file bmfunc.h.

References bm::all_bits_mask.

void bm::or_bit_block | ( | unsigned * | dest,
|  | unsigned | bitpos,
|  | unsigned | bitcount |
| ) |  |  | `[inline]`

Sets bits to 1 in the bitblock.

Parameters:

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

Definition at line 1491 of file bmfunc.h.

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

Referenced by bm::gap_add_to_bitset_l().

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

Set 1 bit in a block.

Definition at line 1461 of file bmfunc.h.

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

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

void bm::sub_bit_block | ( | unsigned * | dest,
|  | unsigned | bitpos,
|  | unsigned | bitcount |
| ) |  |  | `[inline]`

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

Parameters:

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

Definition at line 1553 of file bmfunc.h.

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

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

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

Test 1 bit in a block.

Definition at line 1474 of file bmfunc.h.

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

template<typename T , unsigned BPC, unsigned BPS>

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

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

Parameters:

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

Definition at line 352 of file bmtrans.h.

References bm::bit_block_calc_count(), and BM_INCWORD_BITCOUNT.

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

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

Returns bit count

Definition at line 165 of file bmfunc.h.

Referenced by bm::serial_stream_iterator< DEC >::get_bit_block_COUNT(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_AND(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_OR(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_SUB_AB(), bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_SUB_BA(), and bm::serial_stream_iterator< DEC >::get_bit_block_COUNT_XOR().

template<typename T >

int bm::wordcmp | ( | T | a,
|  | T | b |
| ) |  |  | `[inline]`

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

Parameters:

  | buf1 | - First word.
  | buf2 | - Second word.

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

Definition at line 371 of file bmfunc.h.

template<typename T >

int bm::wordcmp0 | ( | T | w1,
|  | T | w2 |
| ) |  |  | `[inline]`

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

Parameters:

  | buf1 | - First word.
  | buf2 | - Second word.

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

Definition at line 341 of file bmfunc.h.

void bm::xor_bit_block | ( | unsigned * | dest,
|  | unsigned | bitpos,
|  | unsigned | bitcount |
| ) |  |  | `[inline]`

XOR bit interval to 1 in the bitblock.

Parameters:

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

Definition at line 1615 of file bmfunc.h.

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

Referenced by bm::gap_xor_to_bitset().