BitMagic-C++
Data Structures | Namespaces | Typedefs | Functions | Variables
bmfunc.h File Reference

Bit manipulation primitives (internal) More...

#include <memory.h>
#include "bmdef.h"
#include "bmutil.h"
Include dependency graph for bmfunc.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  bm::bv_statistics
 Structure with statistical information about memory allocation footprint, serialization projection, number of vectors. More...
 
struct  bm::pair< First, Second >
 Pair type. More...
 
struct  bm::bit_decode_cache
 bit-decode cache structure More...
 
struct  bm::conditional< b >
 ad-hoc conditional expressions More...
 
struct  bm::conditional< false >
 
class  bm::copy_to_array_functor< B >
 Adaptor to copy 1 bits to array. More...
 
struct  bm::all_set< T >
 Structure carries pointer on bit block with all bits 1. More...
 
struct  bm::all_set< T >::all_set_block
 
struct  bm::d_copy_func< T >
 d-Gap copy functor More...
 
class  bm::bitblock_get_adapter
 Bit-block get adapter, takes bitblock and represents it as a get_32() accessor function. More...
 
class  bm::bitblock_store_adapter
 Bit-block store adapter, takes bitblock and saves results into it. More...
 
class  bm::bitblock_sum_adapter
 Bit-block sum adapter, takes values and sums it /internal. More...
 
class  bm::decoder_range_adapter< DEC >
 Adapter to get words from a range stream (see range serialized bit-block) More...
 
struct  bm::bit_AND< W >
 Bit AND functor. More...
 
struct  bm::bit_OR< W >
 Bit OR functor. More...
 
struct  bm::bit_SUB< W >
 Bit SUB functor. More...
 
struct  bm::bit_XOR< W >
 Bit XOR functor. More...
 
struct  bm::bit_ASSIGN< W >
 Bit ASSIGN functor. More...
 
struct  bm::bit_COUNT< W >
 Bit COUNT functor. More...
 
struct  bm::bit_COUNT_AND< W >
 Bit COUNT AND functor. More...
 
struct  bm::bit_COUNT_XOR< W >
 Bit COUNT XOR functor. More...
 
struct  bm::bit_COUNT_OR< W >
 Bit COUNT OR functor. More...
 
struct  bm::bit_COUNT_SUB_AB< W >
 Bit COUNT SUB AB functor. More...
 
struct  bm::bit_COUNT_SUB_BA< W >
 Bit SUB BA functor. More...
 
struct  bm::bit_COUNT_A< W >
 Bit COUNT A functor. More...
 
struct  bm::bit_COUNT_B< W >
 Bit COUNT B functor. More...
 
struct  bm::operation_functions< T >
 
union  bm::ptr_payload_t
 helper union to interpret pointer as integers More...
 

Namespaces

 bm
 

Typedefs

typedef void(* bm::gap_operation_to_bitset_func_type) (unsigned *, const gap_word_t *)
 
typedef gap_word_t *(* bm::gap_operation_func_type) (const gap_word_t *BMRESTRICT, const gap_word_t *BMRESTRICT, gap_word_t *BMRESTRICT, unsigned &)
 
typedef bm::id_t(* bm::bit_operation_count_func_type) (const bm::word_t *BMRESTRICT, const bm::word_t *BMRESTRICT)
 

Functions

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 BI_TYPE >
void bm::get_block_coord (BI_TYPE nb, unsigned &i, unsigned &j)
 Recalc linear bvector block index into 2D matrix coordinates. More...
 
template<class T >
unsigned bm::bit_scan_reverse (T value)
 
BMFORCEINLINE bm::id_t bm::word_bitcount (bm::id_t w)
 
int bm::parallel_popcnt_32 (unsigned int n)
 
BMFORCEINLINE unsigned bm::word_bitcount64 (bm::id64_t x)
 
unsigned bm::bitcount64_4way (bm::id64_t x, bm::id64_t y, bm::id64_t u, bm::id64_t v)
 
template<typename T , typename F >
void bm::bit_for_each_4 (T w, F &func)
 Templated algorithm to unpacks octet based word into list of ON bit indexes. More...
 
template<typename T , typename F >
void bm::bit_for_each (T w, F &func)
 Templated algorithm to unpacks word into list of ON bit indexes. More...
 
template<typename T , typename B >
unsigned bm::bit_list (T w, B *bits)
 Unpacks word into list of ON bit indexes. More...
 
template<typename T , typename B >
unsigned bm::bit_list_4 (T w, B *bits)
 Unpacks word into list of ON bit indexes (quad-bit based) More...
 
template<typename B >
unsigned short bm::bitscan_popcnt (bm::id_t w, B *bits, unsigned short offs)
 Unpacks word into list of ON bit indexes using popcnt method. More...
 
template<typename B >
unsigned short bm::bitscan_popcnt (bm::id_t w, B *bits)
 Unpacks word into list of ON bit indexes using popcnt method. More...
 
template<typename B >
unsigned short bm::bitscan_popcnt64 (bm::id64_t w, B *bits)
 Unpacks 64-bit word into list of ON bit indexes using popcnt method. More...
 
template<typename V , typename B >
unsigned short bm::bitscan (V w, B *bits)
 
unsigned bm::word_select64_linear (bm::id64_t w, unsigned rank)
 word find index of the rank-th bit set by bit-testing More...
 
unsigned bm::word_select64_bitscan (bm::id64_t w, unsigned rank)
 word find index of the rank-th bit set by bit-testing More...
 
unsigned bm::word_select64 (bm::id64_t w, unsigned rank)
 word find index of the rank-th bit set by bit-testing More...
 
BMFORCEINLINE bm::id64_t bm::widx_to_digest_mask (unsigned w_idx)
 Compute digest mask for word address in block. More...
 
BMFORCEINLINE bm::id64_t bm::digest_mask (unsigned from, unsigned to)
 Compute digest mask for [from..to] positions. More...
 
bool bm::check_zero_digest (bm::id64_t digest, unsigned bitpos_from, unsigned bitpos_to)
 check if all digest bits for the range [from..to] are 0 More...
 
void bm::block_init_digest0 (bm::word_t *const block, bm::id64_t digest)
 Init block with 000111000 pattren based on digest. More...
 
bm::id64_t bm::calc_block_digest0 (const bm::word_t *const block)
 Compute digest for 64 non-zero areas. More...
 
bm::id64_t bm::update_block_digest0 (const bm::word_t *const block, bm::id64_t digest)
 Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas) More...
 
bool bm::is_const_set_operation (set_operation op)
 Returns true if set operation is constant (bitcount) More...
 
bm::operation bm::setop2op (bm::set_operation op)
 Convert set operation to operation. More...
 
template<typename W >
void bm::xor_swap (W &x, W &y)
 XOR swap two scalar variables. More...
 
template<typename N >
bool bm::find_not_null_ptr (bm::word_t ***arr, N start, N size, N *pos)
 
template<typename T >
int bm::wordcmp0 (T w1, T w2)
 Lexicographical comparison of two words as bit strings (reference) Auxiliary implementation for testing and reference purposes. More...
 
template<typename T >
int bm::wordcmp (T a, T b)
 Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes. More...
 
bool bm::bit_is_all_zero (const bm::word_t *BMRESTRICT start)
 Returns "true" if all bits in the block are 0. More...
 
BMFORCEINLINE bool bm::gap_is_all_zero (const bm::gap_word_t *buf)
 Checks if GAP block is all-zero. More...
 
BMFORCEINLINE bool bm::gap_is_all_one (const bm::gap_word_t *buf)
 Checks if GAP block is all-one. More...
 
BMFORCEINLINE bm::gap_word_t bm::gap_length (const bm::gap_word_t *buf)
 Returs GAP block length. More...
 
template<typename T >
unsigned bm::gap_capacity (const T *buf, const T *glevel_len)
 Returs GAP block capacity. More...
 
template<typename T >
unsigned bm::gap_limit (const T *buf, const T *glevel_len)
 Returs GAP block capacity limit. More...
 
template<typename T >
bm::gap_level (const T *buf)
 Returs GAP blocks capacity level. More...
 
template<typename T >
unsigned bm::gap_find_last (const T *buf, unsigned *last)
 GAP block find the last set bit. More...
 
template<typename T >
unsigned bm::gap_find_first (const T *buf, unsigned *first)
 GAP block find the first set bit. More...
 
template<typename T >
unsigned bm::gap_bfind (const T *buf, unsigned pos, unsigned *is_set)
 
template<typename T >
unsigned bm::gap_test (const T *buf, unsigned pos)
 Tests if bit = pos is true. More...
 
template<typename T >
unsigned bm::gap_test_unr (const T *buf, const unsigned pos)
 Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling. More...
 
template<typename T , typename N , typename F >
void bm::for_each_nzblock_range (T ***root, N top_size, N nb_from, N nb_to, F &f)
 
template<class T , class F >
void bm::for_each_nzblock (T ***root, unsigned size1, F &f)
 
template<class T , class F >
void bm::for_each_nzblock2 (T ***root, unsigned size1, F &f)
 
template<typename T , typename BI , typename F >
bool bm::for_each_nzblock_if (T ***root, BI size1, F &f)
 
template<class T , class F , typename BLOCK_IDX >
void bm::for_each_block (T ***root, unsigned size1, F &f, BLOCK_IDX start)
 
template<class T , class F >
bm::bmfor_each (T first, T last, F f)
 
template<typename T >
bm::id64_t bm::sum_arr (T *first, T *last)
 
template<typename T >
unsigned bm::gap_bit_count (const T *buf, unsigned dsize=0)
 Calculates number of bits ON in GAP buffer. More...
 
template<typename T >
unsigned bm::gap_bit_count_unr (const T *buf)
 Calculates number of bits ON in GAP buffer. Loop unrolled version. More...
 
template<typename T >
unsigned bm::gap_bit_count_range (const T *const buf, unsigned left, unsigned right)
 Counts 1 bits in GAP buffer in the closed [left, right] range. More...
 
template<typename T , typename SIZE_TYPE >
SIZE_TYPE bm::gap_find_rank (const T *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos)
 GAP block find position for the rank. More...
 
template<typename T >
unsigned bm::gap_bit_count_to (const T *const buf, T right)
 Counts 1 bits in GAP buffer in the closed [0, right] range. More...
 
template<class T , class Func >
void bm::for_each_dgap (const T *gap_buf, Func &func)
 
template<typename T >
T * bm::gap_2_dgap (const T *gap_buf, T *dgap_buf, bool copy_head=true)
 Convert GAP buffer into D-GAP buffer. More...
 
template<typename T >
void bm::dgap_2_gap (const T *dgap_buf, T *gap_buf, T gap_header=0)
 Convert D-GAP buffer into GAP buffer. More...
 
template<typename T >
int bm::gapcmp (const T *buf1, const T *buf2)
 Lexicographical comparison of GAP buffers. More...
 
template<typename T , class F >
void bm::gap_buff_op (T *BMRESTRICT dest, const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, F &f, unsigned &dlen)
 Abstract operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T , class F >
unsigned bm::gap_buff_any_op (const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, F f)
 Abstract distance test operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T , class F >
unsigned bm::gap_buff_count_op (const T *vect1, const T *vect2, F f)
 Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T >
unsigned bm::gap_set_value (unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned bm::gap_add_value (T *buf, unsigned pos)
 Add new value to the end of GAP buffer. More...
 
template<typename T >
bool bm::gap_shift_r1 (T *buf, unsigned co_flag, unsigned *new_len)
 Right shift GAP block by 1 bit. More...
 
template<typename T >
bool bm::gap_shift_l1 (T *buf, unsigned co_flag, unsigned *new_len)
 Left shift GAP block by 1 bit. More...
 
template<typename T >
unsigned bm::gap_set_array (T *buf, const T *arr, unsigned len)
 Convert array to GAP buffer. More...
 
template<typename T >
unsigned bm::bit_array_compute_gaps (const T *arr, unsigned len)
 Compute number of GAPs in bit-array. More...
 
template<typename T >
unsigned bm::gap_block_find (const T *buf, unsigned nbit, bm::id_t *prev)
 Searches for the next 1 bit in the GAP block. More...
 
BMFORCEINLINE void bm::set_bit (unsigned *dest, unsigned bitpos)
 Set 1 bit in a block. More...
 
BMFORCEINLINE void bm::clear_bit (unsigned *dest, unsigned bitpos)
 Set 1 bit in a block. More...
 
BMFORCEINLINE unsigned bm::test_bit (const unsigned *block, unsigned bitpos)
 Test 1 bit in a block. More...
 
void bm::or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
 Sets bits to 1 in the bitblock. More...
 
void bm::sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
 SUB (AND NOT) bit interval to 1 in the bitblock. More...
 
void bm::xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount)
 XOR bit interval to 1 in the bitblock. More...
 
template<typename T >
void bm::gap_sub_to_bitset (unsigned *dest, const T *pcurr)
 SUB (AND NOT) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_sub_to_bitset (unsigned *dest, const T *pcurr, bm::id64_t digest0)
 SUB (AND NOT) GAP block to bitblock with digest assist. More...
 
template<typename T >
void bm::gap_xor_to_bitset (unsigned *dest, const T *pcurr)
 XOR GAP block to bitblock. More...
 
template<typename T >
void bm::gap_add_to_bitset (unsigned *dest, const T *pcurr, unsigned len)
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_add_to_bitset (unsigned *dest, const T *pcurr)
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_and_to_bitset (unsigned *dest, const T *pcurr)
 ANDs GAP block to bitblock. More...
 
template<typename T >
void bm::gap_and_to_bitset (unsigned *dest, const T *pcurr, bm::id64_t digest0)
 ANDs GAP block to bitblock with digest assist. More...
 
template<typename T >
bm::id_t bm::gap_bitset_and_count (const unsigned *block, const T *pcurr)
 Compute bitcount of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_and_any (const unsigned *block, const T *pcurr)
 Bitcount test of bit block AND masked by GAP block. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
void bm::bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value)
 Bitblock memset operation. More...
 
template<typename T >
void bm::gap_convert_to_bitset (unsigned *dest, const T *buf)
 GAP block to bitblock conversion. More...
 
template<typename T >
unsigned * bm::gap_convert_to_bitset_smart (unsigned *dest, const T *buf, id_t set_max)
 Smart GAP block to bitblock conversion. More...
 
template<typename T >
unsigned bm::gap_control_sum (const T *buf)
 Calculates sum of all words in GAP block. (For debugging purposes) More...
 
template<class T >
void bm::gap_set_all (T *buf, unsigned set_max, unsigned value)
 Sets all bits to 0 or 1 (GAP) More...
 
template<class T >
void bm::gap_init_range_block (T *buf, T from, T to, T value)
 Init gap block so it has block in it (can be whole block) More...
 
template<typename T >
void bm::gap_invert (T *buf)
 Inverts all bits in the GAP buffer. More...
 
template<typename T >
void bm::set_gap_level (T *buf, int level)
 Sets GAP block capacity level. More...
 
template<typename T >
int bm::gap_calc_level (unsigned len, const T *glevel_len)
 Calculates GAP block capacity level. More...
 
template<typename T >
unsigned bm::gap_free_elements (const T *buf, const T *glevel_len)
 Returns number of free elements in GAP block array. Difference between GAP block capacity on this level and actual GAP length. More...
 
template<typename T >
int bm::bitcmp (const T *buf1, const T *buf2, unsigned len)
 Lexicographical comparison of BIT buffers. More...
 
unsigned bm::bit_block_to_gap (gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len)
 Converts bit block to GAP. More...
 
unsigned bm::bit_to_gap (gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len)
 
template<class T , class F >
void bm::for_each_gap_dbit (const T *buf, F &func)
 Iterate gap block as delta-bits with a functor. More...
 
template<typename D , typename T >
bm::gap_convert_to_arr (D *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned dest_len, bool invert=false)
 Convert gap block into array of ints corresponding to 1 bits. More...
 
bm::id_t bm::bit_block_count (const bm::word_t *block)
 Bitcount for bit block. More...
 
bm::id_t bm::bit_block_count (const bm::word_t *const block, bm::id64_t digest)
 Bitcount for bit block. More...
 
bm::id_t bm::bit_block_calc_count (const bm::word_t *block, const bm::word_t *block_end)
 Bitcount for bit string. More...
 
bm::id_t bm::bit_count_change (bm::word_t w)
 
unsigned bm::bit_block_change32 (const bm::word_t *block)
 
void bm::bit_block_change_bc32 (const bm::word_t *block, unsigned *gc, unsigned *bc)
 
unsigned bm::bit_block_calc_change (const bm::word_t *block)
 
bm::id_t bm::bit_block_calc_count_to (const bm::word_t *block, bm::word_t right)
 
void bm::bit_block_rotate_left_1 (bm::word_t *block)
 
void bm::bit_block_rotate_left_1_unr (bm::word_t *block)
 Unrolled cyclic rotation of bit-block left by 1 bit. More...
 
bm::word_t bm::bit_block_insert (bm::word_t *block, unsigned bitpos, bool value)
 insert bit into position and shift the rest right with carryover More...
 
bool bm::bit_block_shift_r1 (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag)
 Right bit-shift bitblock by 1 bit (reference) More...
 
bool bm::bit_block_shift_r1_unr (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag)
 Right bit-shift of bit-block by 1 bit (loop unrolled) More...
 
bool bm::bit_block_shift_l1 (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag)
 Left bit-shift bitblock by 1 bit (reference) More...
 
bool bm::bit_block_shift_l1_unr (bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag)
 Left bit-shift of bit-block by 1 bit (loop unrolled) More...
 
void bm::bit_block_erase (bm::word_t *block, unsigned bitpos, bool carry_over)
 erase bit from position and shift the rest right with carryover More...
 
bool bm::bit_block_shift_r1_and (bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest)
 Right bit-shift of bit-block by 1 bit (reference) + AND. More...
 
bool bm::bit_block_shift_r1_and_unr (bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest)
 Right bit-shift bitblock by 1 bit (reference) + AND. More...
 
template<typename T >
void bm::bit_invert (T *start)
 
bool bm::is_bits_one (const bm::wordop_t *start)
 Returns "true" if all bits in the block are 1. More...
 
BMFORCEINLINE unsigned bm::and_op (unsigned v1, unsigned v2)
 GAP and functor. More...
 
BMFORCEINLINE unsigned bm::xor_op (unsigned v1, unsigned v2)
 GAP xor functor. More...
 
BMFORCEINLINE unsigned bm::or_op (unsigned v1, unsigned v2)
 GAP or functor. More...
 
BMFORCEINLINE unsigned bm::sub_op (unsigned v1, unsigned v2)
 GAP or functor. More...
 
BMFORCEINLINE gap_word_t * bm::gap_operation_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
 GAP AND operation. More...
 
BMFORCEINLINE unsigned bm::gap_operation_any_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP AND operation test. More...
 
BMFORCEINLINE unsigned bm::gap_count_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP bitcount AND operation test. More...
 
BMFORCEINLINE gap_word_t * bm::gap_operation_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
 GAP XOR operation. More...
 
BMFORCEINLINE unsigned bm::gap_operation_any_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP XOR operation test. More...
 
BMFORCEINLINE unsigned bm::gap_count_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP bitcount XOR operation test. More...
 
gap_word_t * bm::gap_operation_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
 GAP OR operation. More...
 
BMFORCEINLINE unsigned bm::gap_count_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP bitcount OR operation test. More...
 
gap_word_t * bm::gap_operation_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
 GAP SUB (AND NOT) operation. More...
 
BMFORCEINLINE unsigned bm::gap_operation_any_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP SUB operation test. More...
 
BMFORCEINLINE unsigned bm::gap_count_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP bitcount SUB (AND NOT) operation test. More...
 
void bm::bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Bitblock copy operation. More...
 
void bm::bit_block_stream (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Bitblock copy/stream operation. More...
 
bm::id64_t bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Plain bitblock AND operation. Function does not analyse availability of source and destination blocks. More...
 
bm::id64_t bm::bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest)
 digest based bit-block AND More...
 
bm::id64_t bm::bit_block_and_5way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src0, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, bm::id64_t digest)
 digest based bit-block AND 5-way More...
 
bm::id64_t bm::bit_block_and_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest)
 digest based bit-block AND More...
 
unsigned bm::bit_block_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_and_any (const bm::word_t *src1, const bm::word_t *src2)
 Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_or_count (const bm::word_t *src1, const bm::word_t *src2)
 Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. More...
 
unsigned bm::bit_block_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. More...
 
bm::word_tbm::bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock AND operation. More...
 
bm::id_t bm::bit_operation_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock AND operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_and_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock AND operation test. More...
 
bm::id_t bm::bit_operation_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock SUB operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_sub_count_inv (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs inverted bitblock SUB operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock test of SUB operation. More...
 
bm::id_t bm::bit_operation_or_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock OR operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock OR operation test. More...
 
bool bm::bit_block_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Plain bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bool bm::bit_block_or_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 2 way (target := source1 | source2) bitblock OR operation. More...
 
bm::id64_t bm::bit_block_xor_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 2 way (target := source1 ^ source2) bitblock XOR operation. More...
 
bool bm::bit_block_or_3way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bool bm::bit_block_or_5way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, const bm::word_t *BMRESTRICT src4)
 5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of source and destination blocks. More...
 
bm::word_tbm::bit_operation_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Block OR operation. Makes analysis if block is 0 or FULL. More...
 
bm::id64_t bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks. More...
 
bm::id64_t bm::bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src, bm::id64_t digest)
 digest based bitblock SUB (AND NOT) operation More...
 
bm::id64_t bm::bit_block_sub_2way (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest)
 digest based bitblock SUB (AND NOT) operation (3 operand) More...
 
bm::word_tbm::bit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock SUB operation. More...
 
bm::id64_t bm::bit_block_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks. More...
 
void bm::bit_andnot_arr_ffmask (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock AND NOT with constant ~0 mask operation. More...
 
bm::word_tbm::bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src)
 bitblock XOR operation. More...
 
bm::id_t bm::bit_operation_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock XOR operation and calculates bitcount of the result. More...
 
bm::id_t bm::bit_operation_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
 Performs bitblock XOR operation test. More...
 
template<class T >
unsigned bm::bit_count_nonzero_size (const T *blk, unsigned data_size)
 Inspects block for full zero words. More...
 
unsigned bm::bit_block_find (const bm::word_t *block, unsigned nbit, unsigned *pos)
 Searches for the next 1 bit in the BIT block. More...
 
unsigned bm::bit_find_last (const bm::word_t *block, unsigned *last)
 BIT block find the last set bit (backward search) More...
 
unsigned bm::bit_find_first (const bm::word_t *block, unsigned *first)
 BIT block find the first set bit. More...
 
unsigned bm::bit_find_first (const bm::word_t *block, unsigned *first, bm::id64_t digest)
 BIT block find the first set bit. More...
 
bool bm::bit_find_first_if_1 (const bm::word_t *block, unsigned *first, bm::id64_t digest)
 BIT block find the first set bit if only 1 bit is set. More...
 
template<typename SIZE_TYPE >
SIZE_TYPE bm::bit_find_rank (const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos)
 BIT block find position for the rank. More...
 
template<typename SIZE_TYPE >
SIZE_TYPE bm::block_find_rank (const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos)
 Find rank in block (GAP or BIT) More...
 
bm::set_representation bm::best_representation (unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size)
 Choose best representation for a bit-block. More...
 
template<typename T >
bm::bit_convert_to_arr (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len, unsigned mask=0)
 Convert bit block into an array of ints corresponding to 1 bits. More...
 
bool bm::check_block_zero (const bm::word_t *blk, bool deep_scan)
 Checks all conditions and returns true if block consists of only 0 bits. More...
 
bool bm::check_block_one (const bm::word_t *blk, bool deep_scan)
 Checks if block has only 1 bits. More...
 
template<typename T >
unsigned bm::gap_overhead (const T *length, const T *length_end, const T *glevel_len)
 Calculates memory overhead for number of gap blocks sharing the same memory allocation table (level lengths table). More...
 
template<typename T >
bool bm::improve_gap_levels (const T *length, const T *length_end, T *glevel_len)
 Finds optimal gap blocks lengths. More...
 
template<class It1 , class It2 , class BinaryOp , class Encoder >
void bm::bit_recomb (It1 &it1, It2 &it2, BinaryOp &op, Encoder &enc, unsigned block_size=bm::set_block_size)
 
unsigned short bm::bitscan_wave (const bm::word_t *w_ptr, unsigned char *bits)
 Unpacks word wave (Nx 32-bit words) More...
 
void bm::bit_block_gather_scatter (unsigned *arr, const bm::word_t *blk, const unsigned *idx, unsigned size, unsigned start, unsigned bit_idx)
 bit index to word gather-scatter algorithm (SIMD) More...
 
template<typename TRGW , typename IDX , typename SZ >
void bm::bit_block_gather_scatter (TRGW *arr, const bm::word_t *blk, const IDX *idx, SZ size, SZ start, unsigned bit_idx)
 bit index to word gather-scatter algorithm More...
 
bm::id64_t bm::idx_arr_block_lookup_u64 (const bm::id64_t *idx, bm::id64_t size, bm::id64_t nb, bm::id64_t start)
 block boundaries look ahead U32 More...
 
unsigned bm::idx_arr_block_lookup_u32 (const unsigned *idx, unsigned size, unsigned nb, unsigned start)
 block boundaries look ahead U32 More...
 
void bm::set_block_bits_u64 (bm::word_t *BMRESTRICT block, const bm::id64_t *BMRESTRICT idx, bm::id64_t start, bm::id64_t stop)
 set bits in a bit-block using global index More...
 
void bm::set_block_bits_u32 (bm::word_t *BMRESTRICT block, const unsigned *BMRESTRICT idx, unsigned start, unsigned stop)
 set bits in a bit-block using global index More...
 
bool bm::block_ptr_array_range (bm::word_t **arr, unsigned &left, unsigned &right)
 array range detector More...
 
unsigned bm::lower_bound_linear_u32 (const unsigned *arr, unsigned target, unsigned from, unsigned to)
 Linear lower bound search in unsigned array. More...
 
unsigned bm::lower_bound_linear_u64 (const unsigned long long *arr, unsigned long long target, unsigned from, unsigned to)
 Linear lower bound search in unsigned LONG array. More...
 
unsigned bm::lower_bound_u32 (const unsigned *arr, unsigned target, unsigned from, unsigned to)
 Hybrid, binary-linear lower bound search in unsigned array. More...
 
unsigned bm::lower_bound_u64 (const unsigned long long *arr, unsigned long long target, unsigned from, unsigned to)
 Hybrid, binary-linear lower bound search in unsigned LONG array. More...
 
bm::id_t bm::block_to_global_index (unsigned i, unsigned j, unsigned block_idx)
 calculate bvector<> global bit-index from block-local coords More...
 
bm::id64_t bm::ptrp_test (ptr_payload_t ptr, bm::gap_word_t v)
 

Variables

const unsigned short bm::set_bitscan_wave_size = 2
 

Detailed Description

Bit manipulation primitives (internal)

Definition in file bmfunc.h.