1#ifndef BMALGO_IMPL__H__INCLUDED__
2#define BMALGO_IMPL__H__INCLUDED__
26#pragma warning( push )
27#pragma warning( disable : 4311 4312 4127)
309 dmd.
result += (*gfunc)(blk, arg_blk);
637 return unsigned(dmd.
result);
707 const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
708 const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
710 bool is_all_and =
true;
713 bm::word_t*** blk_root = bman1.top_blocks_root();
714 typename BV::size_type block_idx = 0;
720 unsigned top_block_size = bman1.top_block_size();
721 unsigned ebs2 = bman2.top_block_size();
723 if (ebs2 > top_block_size)
726 top_size = top_block_size;
728 for (i = 0; i < top_size; ++i)
730 bm::word_t** blk_blk = (blk_root && (i < top_block_size)) ? blk_root[i] : 0;
739 const bm::word_t*
const* bvbb = bman2.get_topblock(i);
749 arg_blk = bman2.get_block(i, j);
761 blk = bman1.get_block(i, j);
762 if (blk == 0 && is_all_and)
765 arg_blk = bman2.get_block(i, j);
792 const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
793 const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
795 if (!bman1.is_init() || !bman2.is_init())
798 bm::word_t*** blk_root = bman1.top_blocks_root();
799 bm::word_t*** blk_root_arg = bman2.top_blocks_root();
800 typename BV::size_type count = 0;
802 unsigned top_block_size =
803 bm::min_value(bman1.top_block_size(),bman2.top_block_size());
805 for (
unsigned i = 0; i < top_block_size; ++i)
809 if ((blk_blk = blk_root[i]) == 0 || (blk_blk_arg= blk_root_arg[i]) == 0)
819 (blk_blk[j] && blk_blk_arg[j]) ?
822 (blk_blk[j+1] && blk_blk_arg[j+1]) ?
825 (blk_blk[j+2] && blk_blk_arg[j+2]) ?
828 (blk_blk[j+3] && blk_blk_arg[j+3]) ?
863 const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
864 const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
866 bool is_all_and =
true;
869 bm::word_t*** blk_root = bman1.top_blocks_root();
870 unsigned block_idx = 0;
878 unsigned top_block_size = bman1.top_block_size();
879 unsigned ebs2 = bman2.top_block_size();
881 if (ebs2 > top_block_size)
884 top_size = top_block_size;
886 for (i = 0; i < top_size; ++i)
888 bm::word_t** blk_blk = (blk_root && (i < top_block_size)) ? blk_root[i] : 0;
898 const bm::word_t*
const* bvbb = bman2.get_topblock(i);
910 arg_blk = bman2.get_block(i, j);
920 bool all_resolved =
false;
926 all_resolved =
false;
930 }
while (it < dmit_end);
940 blk = bman1.get_block(i, j);
941 if (blk == 0 && is_all_and)
944 arg_blk = bman2.get_block(i, j);
946 if (blk == 0 && arg_blk == 0)
957 bool all_resolved =
true;
963 all_resolved =
false;
967 }
while (it < dmit_end);
982template<
typename It,
typename SIZE_TYPE>
984 SIZE_TYPE nblock, SIZE_TYPE* max_id)
BMNOEXCEPT
986 SIZE_TYPE m = *max_id;
988 for (right = first; right != last; ++right)
990 SIZE_TYPE v = SIZE_TYPE(*right);
1015template<
class BV,
class It>
1018 typedef typename BV::size_type size_type;
1019 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1020 if (!bman.is_init())
1023 size_type max_id = 0;
1025 while (first < last)
1029 if (max_id >= bv.size())
1032 bv.resize(max_id + 1);
1041 bman.check_allocate_block(nblock,
1043 bv.get_new_blocks_strat(),
1048 if (block_type == 1)
1053 for (; first < right; ++first)
1058 unsigned new_block_len =
1060 if (new_block_len > threshold)
1062 bman.extend_gap_block(nblock, gap_blk);
1070 for (; first < right; ++first)
1072 size_type pos = *first;
1076 blk[nword] |= (1u << nbit);
1096template<
class BV,
class It>
1099 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1100 if (!bman.is_init())
1103 typename BV::size_type max_id = 0;
1105 while (first < last)
1110 if (max_id >= bv.size())
1113 bv.resize(max_id + 1);
1122 bman.check_allocate_block(nblock,
1124 bv.get_new_blocks_strat(),
1129 if (block_type == 1)
1134 for (; first < right; ++first)
1143 unsigned new_block_len =
1145 if (new_block_len > threshold)
1147 bman.extend_gap_block(nblock, gap_blk);
1155 for (; first < right; ++first)
1160 blk[nword] ^= (1u << nbit);
1183template<
class BV,
class It>
1186 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1187 if (!bman.is_init())
1190 typename BV::size_type max_id = 0;
1192 while (first < last)
1197 if (max_id >= bv.size())
1200 bv.resize(max_id + 1);
1209 bman.check_allocate_block(nblock,
1211 bv.get_new_blocks_strat(),
1217 if (block_type == 1)
1222 for (; first < right; ++first)
1231 unsigned new_block_len =
1233 if (new_block_len > threshold)
1235 bman.extend_gap_block(nblock, gap_blk);
1243 for (; first < right; ++first)
1268template<
class BV,
class It>
1271 typename BV::size_type prev = 0;
1272 for ( ;first < last; ++first)
1274 typename BV::size_type
id = *first;
1276 bv.set_bit_and(
id,
true);
1279 bv.set_range(prev,
id-1,
false);
1300template<
class BV,
class It>
1327 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1329 if (!bman.is_init())
1332 bm::word_t*** blk_root = bman.top_blocks_root();
1333 typename BV::blocks_manager_type::block_count_change_func func(bman);
1334 typename BV::blocks_manager_type::block_idx_type st = 0;
1337 typename BV::size_type intervals = func.count();
1340 intervals -= last_bit_set;
1358template<
typename BV,
class It>
1361 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1362 if (!bman.is_init())
1365 unsigned inp_word_size =
sizeof(*first);
1366 size_t array_size = size_t(last - first);
1367 size_t bit_cnt = array_size * inp_word_size * 8;
1372 if (bit_cnt >= bv.size())
1375 bv.set_range((
typename BV::size_type)bit_cnt, bv.size() - 1,
false);
1376 switch (inp_word_size)
1380 size_t word_cnt = array_size / 4;
1384 bman.check_allocate_block(i,
1389 if (block_type == 1)
1391 blk = bman.deoptimize_block(i);
1400 tmp = b1 | (b2 << 8u) | (b3 << 16u) | (b4 << 24u);
1402 }
while (wrd_ptr < wrd_end);
1407 size_t to_convert = size_t(last - first);
1408 for (
size_t j = 0; j < to_convert / 4; ++j)
1412 tmp = b1 | (b2 << 8u) | (b3 << 16u) | (b4 << 24u);
1417 if (first == last)
break;
1419 if (first == last)
break;
1421 if (first == last)
break;
1423 if (first == last)
break;
1428 if (first == last)
break;
1434 size_t word_cnt = array_size / 2;
1438 bman.check_allocate_block(i,
1444 blk = bman.deoptimize_block(i);
1451 tmp = b1 | (b2 << 16);
1453 }
while (wrd_ptr < wrd_end);
1458 size_t to_convert = size_t(last - first);
1459 for (
unsigned j = 0; j < to_convert / 2; ++j)
1462 tmp = b1 | (b2 << 16u);
1467 if (first == last)
break;
1469 if (first == last)
break;
1474 if (first == last)
break;
1480 size_t word_cnt = array_size;
1484 bman.check_allocate_block(i,
1489 if (block_type == 1)
1490 blk = bman.deoptimize_block(i);
1498 }
while (wrd_ptr < wrd_end);
1505 if (first == last)
break;
1510 if (first == last)
break;
1531template<
typename Func,
typename SIZE_TYPE>
1543 SIZE_TYPE offs = offset;
1550 bit_functor.add_bits(offs, bits, cnt);
1553 }
while (block < block_end);
1568template<
typename Func,
typename SIZE_TYPE>
1570 unsigned left,
unsigned right,
1579 unsigned sz = right - left + 1;
1580 bit_functor.add_range(offset + left, sz);
1585 unsigned cnt, nword, nbit, bitcount, temp;
1591 if ((*word >> nbit) & 1u)
1593 bits[0] = (
unsigned char)nbit;
1594 bit_functor.add_bits(offset + (nword * 32), bits, 1);
1599 bitcount = right - left + 1u;
1602 unsigned right_margin = nbit + right - left;
1603 if (right_margin < 32)
1608 temp = (*word & mask);
1611 bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1618 bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1619 bitcount -= 32 - nbit;
1624 bitcount = right - left + 1u;
1629 for ( ;bitcount >= 128;
1635 bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1638 for ( ;bitcount >= 32; bitcount-=32, ++word)
1643 bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1654 bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1671template<
typename T,
typename Func,
typename SIZE_TYPE>
1675 const T* pcurr = buf + 1;
1676 const T* pend = buf + (*buf >> 3);
1680 bit_functor.add_range(offset, *pcurr + 1);
1683 for (++pcurr; pcurr <= pend; pcurr += 2)
1685 T prev = *(pcurr-1);
1686 bit_functor.add_range(offset + prev + 1, *pcurr - prev);
1702template<
typename T,
typename Func,
typename SIZE_TYPE>
1705 unsigned left,
unsigned right,
1717 if (right <= *pcurr)
1719 bit_functor.add_range(offset + left, (right + 1)-left);
1722 bit_functor.add_range(offset + left, (*pcurr + 1)-left);
1726 const T*
BMRESTRICT pend = buf + (*buf >> 3);
1727 for (++pcurr; pcurr <= pend; pcurr += 2)
1729 T prev = *(pcurr-1);
1730 if (right <= *pcurr)
1732 int sz = int(right) - int(prev);
1734 bit_functor.add_range(offset + prev + 1,
unsigned(sz));
1737 bit_functor.add_range(offset + prev + 1, *pcurr - prev);
1746template<
typename T,
typename N,
typename F>
1748 N top_size, N nb_from, N nb_to, F& f)
1751 if (nb_from > nb_to)
1758 if (i_from >= top_size)
1760 if (i_to >= top_size)
1762 i_to = unsigned(top_size-1);
1766 for (
unsigned i = i_from; i <= i_to; ++i)
1768 T** blk_blk = root[i];
1773 unsigned j = (i == i_from) ? j_from : 0;
1774 if (!j && (i != i_to))
1785 if ((i == i_to) && (j == j_to))
1792 unsigned j = (i == i_from) ? j_from : 0;
1799 if (0 != (block = blk_blk[j]))
1812 if ((i == i_to) && (j == j_to))
1824template<
class BV,
class Func>
1826 typename BV::size_type left,
1827 typename BV::size_type right,
1830 typedef typename BV::size_type size_type;
1831 typedef typename BV::block_idx_type block_idx_type;
1833 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1834 bm::word_t*** blk_root = bman.top_blocks_root();
1843 const bm::word_t* block = bman.get_block_ptr(i0, j0);
1847 if (nblock_left == nblock_right)
1855 nbit_left, nbit_right, bit_functor);
1865 if (nbit_left && block)
1882 block_idx_type top_blocks_size = bman.top_block_size();
1884 nblock_left, nblock_right-1, bit_functor);
1889 block = bman.get_block_ptr(i0, j0);
1897 0, nbit_right, bit_functor);
1911#pragma warning( pop )
#define IS_FULL_BLOCK(addr)
#define BLOCK_ADDR_SAN(addr)
#define FULL_BLOCK_FAKE_ADDR
#define BM_VECT_ALIGN_ATTR
#define FULL_SUB_BLOCK_REAL_ADDR
Bit manipulation primitives (internal)
bm::id_t bit_operation_and_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock AND operation test.
bm::id_t bit_operation_or_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock OR operation test.
bm::id_t bit_block_count(const bm::word_t *block) BMNOEXCEPT
Bitcount for bit block.
bm::id_t bit_operation_xor_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock XOR operation test.
bm::id_t bit_operation_sub_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock test of SUB operation.
unsigned short bitscan_wave(const bm::word_t *BMRESTRICT w_ptr, unsigned char *BMRESTRICT bits) BMNOEXCEPT
Unpacks word wave (Nx 32-bit words)
void 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
bool bit_is_all_zero(const bm::word_t *BMRESTRICT start) BMNOEXCEPT
Returns "true" if all bits in the block are 0.
unsigned short bitscan_popcnt(bm::id_t w, B *bits, unsigned short offs) BMNOEXCEPT
Unpacks word into list of ON bit indexes using popcnt method.
bm::id_t bit_operation_and_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock AND operation and calculates bitcount of the result.
bm::id_t bit_operation_sub_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock SUB operation and calculates bitcount of the result.
set_operation
Codes of set operations.
@ BM_BIT
No GAP compression strategy. All new blocks are bit blocks.
void distance_operation(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Distance computing template function.
void distance_operation_any(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Distance screening template function.
distance_metric
Distance metrics codes defined for vectors A and B.
BV::size_type distance_and_operation(const BV &bv1, const BV &bv2) BMNOEXCEPT
Distance AND computing template function.
distance_metric operation2metric(set_operation op) BMNOEXCEPT
Convert set operation into compatible distance metric.
@ COUNT_XOR
(A ^ B).count()
@ COUNT_SUB_AB
(A - B).count()
@ COUNT_AND
(A & B).count()
@ COUNT_OR
(A | B).count()
@ COUNT_SUB_BA
(B - A).count()
gap_word_t * gap_operation_or(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
GAP OR operation.
unsigned gap_test_unr(const T *BMRESTRICT buf, const unsigned pos) BMNOEXCEPT
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
BMFORCEINLINE unsigned gap_operation_any_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP XOR operation test.
void for_each_gap_blk_range(const T *BMRESTRICT buf, SIZE_TYPE offset, unsigned left, unsigned right, Func &bit_functor)
for-each visitor, calls a special visitor functor for each 1 bit range
unsigned gap_bit_count_unr(const T *buf) BMNOEXCEPT
Calculates number of bits ON in GAP buffer. Loop unrolled version.
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Sets or clears bit in the GAP buffer.
bm::id_t gap_bitset_or_any(const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
Compute bitcount test of bit block OR masked by GAP block.
bm::id_t gap_bitset_xor_count(const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
Compute bitcount of bit block XOR masked by GAP block.
bm::id_t gap_bitset_and_count(const unsigned *BMRESTRICT block, const T *BMRESTRICT pcurr) BMNOEXCEPT
Compute bitcount of bit block AND masked by GAP block.
BMFORCEINLINE unsigned gap_operation_any_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP SUB operation test.
bm::id_t gap_bitset_sub_count(const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
Compute bitcount of bit block SUB masked by GAP block.
BMFORCEINLINE unsigned gap_operation_any_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP AND operation test.
BMFORCEINLINE unsigned gap_count_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP bitcount XOR operation test.
bm::id_t gap_bitset_sub_any(const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
Compute bitcount test of bit block SUB masked by GAP block.
void for_each_gap_blk(const T *buf, SIZE_TYPE offset, Func &bit_functor)
for-each visitor, calls a special visitor functor for each 1 bit range
bm::id_t gap_bitset_xor_any(const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
Compute bitcount test of bit block XOR masked by GAP block.
bm::id_t gap_bitset_or_count(const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
Compute bitcount of bit block OR masked by GAP block.
unsigned gap_count_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP bitcount AND operation test.
BMFORCEINLINE bool gap_is_all_zero(const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
Checks if GAP block is all-zero.
void gap_convert_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT buf) BMNOEXCEPT
GAP block to bitblock conversion.
BMFORCEINLINE unsigned gap_count_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP bitcount SUB (AND NOT) operation test.
bm::id_t gap_bitset_and_any(const unsigned *BMRESTRICT block, const T *BMRESTRICT pcurr) BMNOEXCEPT
Bitcount test of bit block AND masked by GAP block.
unsigned gap_limit(const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
Returs GAP block capacity limit.
BMFORCEINLINE unsigned gap_count_or(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP bitcount OR operation test.
void combine_and_sorted(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
void export_array(BV &bv, It first, It last)
Export bitset from an array of binary data representing the bit vector.
void combine_and(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
void combine_sub(BV &bv, It first, It last)
SUB Combine bitvector and the iterable sequence.
void combine_xor(BV &bv, It first, It last)
XOR Combine bitvector and the iterable sequence.
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
BV::size_type count_intervals(const BV &bv)
Compute number of bit intervals (GAPs) in the bitvector.
const unsigned set_array_mask
It block_range_scan(It first, It last, SIZE_TYPE nblock, SIZE_TYPE *max_id) BMNOEXCEPT
Internal algorithms scans the input for the block range limit.
bm::id_t(* bit_operation_count_func_type)(const bm::word_t *BMRESTRICT, const bm::word_t *BMRESTRICT)
void for_each_bit_block_range(T ***root, N top_size, N nb_from, N nb_to, F &f)
const unsigned set_block_mask
unsigned gap_bfind(const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
BMFORCEINLINE RTYPE get_block_start(unsigned i, unsigned j) BMNOEXCEPT
Compute bit address of the first bit in a block.
const unsigned set_sub_array_size
void combine_count_operation_with_block(const bm::word_t *blk, const bm::word_t *arg_blk, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Internal function computes different distance metrics.
const unsigned set_total_blocks
void combine_any_operation_with_block(const bm::word_t *blk, unsigned gap, const bm::word_t *arg_blk, unsigned arg_gap, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Internal function computes different existense of distance metric.
const unsigned set_word_shift
const unsigned set_sub_total_bits
const unsigned set_block_size
unsigned long long int id64_t
void distance_stage(const distance_metric_descriptor *dmit, const distance_metric_descriptor *dmit_end, bool *is_all_and) BMNOEXCEPT
Staging function for distance operation.
const unsigned gap_max_buff_len
T min_value(T v1, T v2) BMNOEXCEPT
Get minimum of 2 values.
BMFORCEINLINE RTYPE get_super_block_start(unsigned i) BMNOEXCEPT
Compute bit address of the first bit in a superblock.
const unsigned short set_bitscan_wave_size
Size of bit decode wave in words.
const unsigned set_array_shift
unsigned short gap_word_t
const unsigned gap_max_bits
void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
void for_each_block(T ***root, unsigned size1, F &f, BLOCK_IDX start)
const unsigned set_block_shift
unsigned combine_count_and_operation_with_block(const bm::word_t *blk, const bm::word_t *arg_blk) BMNOEXCEPT
Internal function computes AND distance.
const unsigned set_word_mask
const unsigned bits_in_block
void for_each_bit_range_no_check(const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
Implementation of for_each_bit_range without boilerplave checks.
bool is_const_set_operation(set_operation op) BMNOEXCEPT
Returns true if set operation is constant (bitcount)
Structure keeps all-left/right ON bits masks.
Distance metric descriptor, holds metric code and result.
distance_metric_descriptor(distance_metric m) BMNOEXCEPT
distance_metric_descriptor() BMNOEXCEPT
void reset() BMNOEXCEPT
Sets metric result to 0.
static bit_operation_count_func_type bit_operation_count(unsigned i)