1#ifndef BMFUNC__H__INCLUDED__
2#define BMFUNC__H__INCLUDED__
32# pragma warning( disable: 4146 )
79 size_t mem_used = (capacity *
sizeof(
gap_word_t));
120template<
typename First,
typename Second>
146template<
typename BI_TYPE>
157template<
typename RTYPE>
167template<
typename RTYPE>
170 RTYPE idx = bm::get_super_block_start<RTYPE>(i);
199#if defined(BMSSE42OPT) || defined(BMAVX2OPT)
202 #if defined(BM_USE_GCC_BUILD)
203 return (
bm::id_t)__builtin_popcount(w);
219 tmp = n - ((n >> 1) & 033333333333)
220 - ((n >> 2) & 011111111111);
221 return ((tmp + (tmp >> 3)) & 030707070707) % 63;
232#if defined(BMSSE42OPT) || defined(BMAVX2OPT)
233#if defined(BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
234 return unsigned(_mm_popcnt_u64(x));
236 return _mm_popcnt_u32(x >> 32) + _mm_popcnt_u32((
unsigned)x);
239 #if defined(BM_USE_GCC_BUILD)
240 return (
unsigned)__builtin_popcountll(x);
242 x = x - ((x >> 1) & 0x5555555555555555);
243 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
244 x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
262 x = x - ((x >> 1) & m1);
263 y = y - ((y >> 1) & m1);
264 u = u - ((u >> 1) & m1);
265 v = v - ((v >> 1) & m1);
266 x = (x & m2) + ((x >> 2) & m2);
267 y = (y & m2) + ((y >> 2) & m2);
268 u = (u & m2) + ((u >> 2) & m2);
269 v = (v & m2) + ((v >> 2) & m2);
272 x = (x & m3) + ((x >> 4) & m3);
273 u = (u & m3) + ((u >> 4) & m3);
279 return x & 0x000001FFU;
294template<
typename T,
typename F>
297 for (
unsigned sub_octet = 0; w != 0; w >>= 4, sub_octet += 4)
310 func(sub_octet, sub_octet + 1);
316 func(sub_octet, sub_octet + 2);
319 func(sub_octet + 1, sub_octet + 2);
322 func(sub_octet, sub_octet + 1, sub_octet + 2);
328 func(sub_octet, sub_octet + 3);
331 func(sub_octet + 1, sub_octet + 3);
334 func(sub_octet, sub_octet + 1, sub_octet + 3);
337 func(sub_octet + 2, sub_octet + 3);
340 func(sub_octet, sub_octet + 2, sub_octet + 3);
343 func(sub_octet + 1, sub_octet + 2, sub_octet + 3);
346 func(sub_octet, sub_octet + 1, sub_octet + 2, sub_octet + 3);
364template<
typename T,
typename F>
368 for (
unsigned octet = 0; w != 0; w >>= 8, octet += 8)
370 if (w & 1) func(octet + 0);
371 if (w & 2) func(octet + 1);
372 if (w & 4) func(octet + 2);
373 if (w & 8) func(octet + 3);
374 if (w & 16) func(octet + 4);
375 if (w & 32) func(octet + 5);
376 if (w & 64) func(octet + 6);
377 if (w & 128) func(octet + 7);
399 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
407 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1; bp_[2] = (B)bit_idx2;
416 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
417 bp_[2] = (B)bit_idx2; bp_[3] = (B)bit_idx3;
437template<
typename T,
typename B>
442 return (
unsigned)(func.
ptr() - bits);
455template<
typename T,
typename B>
460 return (
unsigned)(func.
ptr() - bits);
484 return (
unsigned short)pos;
506 return (
unsigned short)pos;
520 unsigned short pos = 0;
542 unsigned short pos = 0;
553template<
typename V,
typename B>
579 for (
unsigned count = 0; w; w >>=1ull, ++count)
581 rank -= unsigned(w & 1ull);
626#if defined(BMI2_SELECT64)
627 return BMI2_SELECT64(w, rank);
629 #if defined(BMI1_SELECT64)
630 return BMI2_SELECT64(w, rank);
672 return ((maskFF) >> (63 - (digest_to - digest_from))) << digest_from;
689 unsigned bitpos_from,
unsigned bitpos_to)
BMNOEXCEPT
692 return !(digest & mask);
707 for (
unsigned i = 0; i < 64; ++i)
711#if defined(VECT_BLOCK_SET_DIGEST)
716 block[off+j+0] = block[off+j+1] =
717 block[off+j+2] = block[off+j+3] = mask;
739 for (
unsigned i = 0; i < 64; ++i)
742 #if defined(VECT_IS_DIGEST_ZERO)
750 block[off+j+0] | block[off+j+1] | block[off+j+2] | block[off+j+3];
753 digest0 |= (mask << i);
788 #if defined(VECT_IS_DIGEST_ZERO)
790 digest &= all_zero ? ~(mask << wave) : digest;
799 src_u->w64[j+0] | src_u->w64[j+1] | src_u->w64[j+2] | src_u->w64[j+3];
802 digest &= w64 ? digest : ~(mask << wave);
852 ::memset(_p, 0xFF,
sizeof(_p));
855 const unsigned long long magic_mask = 0xFFFFfffeFFFFfffe;
856 ::memcpy(&_p_fullp, &magic_mask,
sizeof(magic_mask));
858 _s[i] =
reinterpret_cast<bm::word_t*
>(magic_mask);
862 const unsigned magic_mask = 0xFFFFfffe;
863 ::memcpy(&_p_fullp, &magic_mask,
sizeof(magic_mask));
865 _s[i] =
reinterpret_cast<bm::word_t*
>(magic_mask);
878 bm::id64_t w =
reinterpret_cast<unsigned long long>(bp);
881 type = type ? type : w;
885 unsigned w =
reinterpret_cast<unsigned long>(bp);
888 type = type ? type : w;
930 const unsigned unroll_factor = 4;
931 const unsigned len = (size - start);
932 const unsigned len_unr = len - (len % unroll_factor);
936 for (k = 0; k < len_unr; k+=unroll_factor)
938 if (!avx2_test_all_zero_wave(arr+k))
947 *pos = k + start + 1;
952 *pos = k + start + 2;
957 *pos = k + start + 3;
972 for (; start < size; ++start)
1002 int res = (w1 & 1) - (w2 & 1);
1003 if (res != 0)
return res;
1030 return diff? ( (a & diff & -diff)? 1 : -1 ) : 0;
1047#if defined(VECT_IS_ZERO_BLOCK)
1054 if (blk[0] | blk[1] | blk[2] | blk[3])
1057 }
while (blk < blk_end);
1116 return glevel_len[(*buf >> 1) & 3];
1132 return glevel_len[(*buf >> 1) & 3]-4;
1146 return T((*buf >> 1) & 3u);
1166 T is_set = (*buf) & 1u;
1167 T end = T((*buf) >> 3u);
1171 is_set ^= T((end-1) & 1u);
1197 T is_set = (*buf) & 1u;
1205 *first = buf[1] + 1;
1224 #undef VECT_GAP_BFIND
1225 #ifdef VECT_GAP_BFIND
1228 *is_set = (*buf) & 1;
1231 unsigned end = 1 + ((*buf) >> 3);
1233 while ( start != end )
1235 unsigned curr = (start + end) >> 1;
1236 if ( buf[curr] < pos )
1241 *is_set ^= ((start-1) & 1);
1260 unsigned end = 1 + ((*buf) >> 3);
1261 if (end - start < 10)
1263 unsigned sv = *buf & 1;
1264 unsigned sv1= sv ^ 1;
1265 if (buf[1] >= pos)
return sv;
1266 if (buf[2] >= pos)
return sv1;
1267 if (buf[3] >= pos)
return sv;
1268 if (buf[4] >= pos)
return sv1;
1269 if (buf[5] >= pos)
return sv;
1270 if (buf[6] >= pos)
return sv1;
1271 if (buf[7] >= pos)
return sv;
1272 if (buf[8] >= pos)
return sv1;
1273 if (buf[9] >= pos)
return sv;
1278 while (start != end)
1280 unsigned curr = (start + end) >> 1;
1281 if (buf[curr] < pos)
1287 return ((*buf) & 1) ^ ((--start) & 1);
1306#if defined(BMSSE2OPT)
1309#elif defined(BMSSE42OPT)
1312#elif defined(BMAVX2OPT)
1313 unsigned res = bm::avx2_gap_test(buf, pos);
1324template<
typename T,
typename N,
typename F>
1326 N top_size, N nb_from, N nb_to, F& f)
BMNOEXCEPT
1329 if (nb_from > nb_to)
1336 if (i_from >= top_size)
1338 if (i_to >= top_size)
1340 i_to = unsigned(top_size-1);
1344 for (
unsigned i = i_from; i <= i_to; ++i)
1346 T** blk_blk = root[i];
1351 unsigned j = (i == i_from) ? j_from : 0;
1352 if (!j && (i != i_to))
1359 if ((i == i_to) && (j == j_to))
1366 unsigned j = (i == i_from) ? j_from : 0;
1371 if ((i == i_to) && (j == j_to))
1381template<
class T,
class F>
1384 typedef typename F::size_type size_type;
1385 for (
unsigned i = 0; i < size1; ++i)
1387 T** blk_blk = root[i];
1393 f.on_non_empty_top(i);
1405 unsigned non_empty_top = 0;
1410#if defined(BM64_AVX2) || defined(BM64_AVX512)
1411 if (!avx2_test_all_zero_wave(blk_blk + j))
1414 T* blk0 = blk_blk[j + 0];
1415 T* blk1 = blk_blk[j + 1];
1416 T* blk2 = blk_blk[j + 2];
1417 T* blk3 = blk_blk[j + 3];
1419 size_type block_idx = r + j + 0;
1423 f.on_empty_block(block_idx);
1426 f(blk1, block_idx + 1);
1428 f.on_empty_block(block_idx + 1);
1431 f(blk2, block_idx + 2);
1433 f.on_empty_block(block_idx + 2);
1436 f(blk3, block_idx + 3);
1438 f.on_empty_block(block_idx + 3);
1442 f.on_empty_block(r + j + 0); f.on_empty_block(r + j + 1);
1443 f.on_empty_block(r + j + 2); f.on_empty_block(r + j + 3);
1446#elif defined(BM64_SSE4)
1450 T* blk0 = blk_blk[j + 0];
1451 T* blk1 = blk_blk[j + 1];
1453 size_type block_idx = r + j + 0;
1457 f.on_empty_block(block_idx);
1463 f.on_empty_block(block_idx);
1467 f.on_empty_block(r + j + 0);
1468 f.on_empty_block(r + j + 1);
1474 f(blk_blk[j], r + j);
1478 f.on_empty_block(r + j);
1483 if (non_empty_top == 0)
1490template<
class T,
class F>
1494 for (
unsigned i = 0; i < size1; ++i)
1497 if ((blk_blk = root[i])!=0)
1511 w0 = _mm_loadu_si128((__m128i*)(blk_blk + j));
1512 if (!_mm_testz_si128(w0, w0))
1514 T* blk0 = blk_blk[j + 0];
1515 T* blk1 = blk_blk[j + 1];
1522 w0 = _mm_loadu_si128((__m128i*)(blk_blk + j + 2));
1523 if (!_mm_testz_si128(w0, w0))
1525 T* blk0 = blk_blk[j + 2];
1526 T* blk1 = blk_blk[j + 3];
1536#elif defined(BM64_AVX2) || defined(BM64_AVX512)
1537 for (
unsigned i = 0; i < size1; ++i)
1540 if ((blk_blk = root[i]) != 0)
1553 __m256i w0 = _mm256_loadu_si256((__m256i*)(blk_blk + j));
1554 if (!_mm256_testz_si256(w0, w0))
1558 T* blk0 = blk_blk[j + 0];
1559 T* blk1 = blk_blk[j + 1];
1560 T* blk2 = blk_blk[j + 2];
1561 T* blk3 = blk_blk[j + 3];
1577 for (
unsigned i = 0; i < size1; ++i)
1580 if ((blk_blk = root[i])!=0)
1612template<
typename T,
typename BI,
typename F>
1616 for (BI i = 0; i < size1; ++i)
1618 T** blk_blk = root[i];
1637 if (f(blk_blk[j], block_idx))
1646template<
class T,
class F,
typename BLOCK_IDX>
1649 BLOCK_IDX block_idx = start;
1650 for (
unsigned i = 0; i < size1; ++i)
1652 T** blk_blk = root[i];
1665 f(blk_blk[j], block_idx);
1688 }
while (first < last);
1698 for (;first < last; ++first)
1714 T* arr0, T* arr1, T& arr0_cnt, T& arr1_cnt)
BMNOEXCEPT
1716 const T* pcurr = buf;
1717 unsigned len = (*pcurr >> 3);
1718 const T* pend = pcurr + len;
1722 unsigned is_set = (*buf & 1);
1728 arr1[cnt1] = *pcurr;
1733 arr0[cnt0] = *pcurr;
1740 while (pcurr <= pend)
1743 T delta = *pcurr - prev;
1775 const T* pcurr = buf;
1777 dsize = (*pcurr >> 3);
1779 const T* pend = pcurr + dsize;
1781 unsigned bits_counter = 0;
1786 bits_counter += *pcurr + 1;
1789 for (++pcurr; pcurr <= pend; pcurr += 2)
1790 bits_counter += *pcurr - *(pcurr-1);
1791 return bits_counter;
1803 const T* pcurr = buf;
1804 unsigned dsize = (*pcurr >> 3);
1808 T first_one = *buf & 1;
1816 #if defined(BMAVX2OPT) || defined(BMAVX512OPT)
1819 const unsigned unr_factor = 32;
1820 unsigned waves = (dsize-2) / unr_factor;
1821 pcurr = avx2_gap_sum_arr(pcurr, waves, &cnt);
1823 #elif defined(BMSSE42OPT) || defined(BMSSE2OPT)
1826 const unsigned unr_factor = 16;
1827 unsigned waves = (dsize - 2) / unr_factor;
1833 const unsigned unr_factor = 8;
1834 unsigned waves = (dsize - 2) / unr_factor;
1835 for (
unsigned i = 0; i < waves; i += unr_factor)
1837 cnt += pcurr[0] - pcurr[0 - 1];
1838 cnt += pcurr[2] - pcurr[2 - 1];
1839 cnt += pcurr[4] - pcurr[4 - 1];
1840 cnt += pcurr[6] - pcurr[6 - 1];
1842 pcurr += unr_factor;
1847 const T* pend = buf + dsize;
1848 for ( ; pcurr <= pend ; pcurr+=2)
1850 cnt += *pcurr - *(pcurr - 1);
1873 const T* pcurr = buf;
1874 const T* pend = pcurr + (*pcurr >> 3);
1876 unsigned bits_counter = 0;
1879 is_set = ~(is_set - 1u);
1881 pcurr = buf + start_pos;
1882 if (right <= *pcurr)
1884 bits_counter = unsigned(right - left + 1u) & is_set;
1885 return bits_counter;
1887 bits_counter += unsigned(*pcurr - left + 1u) & is_set;
1889 unsigned prev_gap = *pcurr++;
1890 for (is_set ^= ~0u; right > *pcurr; is_set ^= ~0u)
1892 bits_counter += (*pcurr - prev_gap) & is_set;
1894 return bits_counter;
1895 prev_gap = *pcurr++;
1897 bits_counter += unsigned(right - prev_gap) & is_set;
1898 return bits_counter;
1920 const T*
const pcurr = buf + start_pos;
1921 return (right <= *pcurr);
1941 const T*
const pcurr = buf + start_pos;
1945 if (right <= *pcurr)
1972 const T* pcurr = buf + start_pos;
1973 if (!is_set || (right != *pcurr) || (start_pos <= 1))
1976 if (*pcurr != left-1)
2001 *pos = buf[start_pos];
2030 *pos = buf[start_pos]+1;
2048template<
typename T,
typename SIZE_TYPE>
2057 const T* pcurr = block;
2058 const T* pend = pcurr + (*pcurr >> 3);
2060 unsigned bits_counter = 0;
2062 unsigned start_pos =
bm::gap_bfind(block, nbit_from, &is_set);
2063 is_set = ~(is_set - 1u);
2065 pcurr = block + start_pos;
2066 bits_counter += unsigned(*pcurr - nbit_from + 1u) & is_set;
2067 if (bits_counter >= rank)
2069 nbit_pos = nbit_from + unsigned(rank) - 1u;
2072 rank -= bits_counter;
2073 unsigned prev_gap = *pcurr++;
2074 for (is_set ^= ~0u; pcurr <= pend; is_set ^= ~0u)
2076 bits_counter = (*pcurr - prev_gap) & is_set;
2077 if (bits_counter >= rank)
2079 nbit_pos = prev_gap + unsigned(rank);
2082 rank -= bits_counter;
2083 prev_gap = *pcurr++;
2104 const T* pcurr = buf;
2105 const T* pend = pcurr + (*pcurr >> 3);
2107 unsigned bits_counter = 0;
2108 unsigned is_set = ~((unsigned(*buf) & 1u) - 1u);
2109 BM_ASSERT(is_set == 0u || is_set == ~0u);
2112 if (right <= *pcurr)
2114 bits_counter = (right + 1u) & is_set;
2115 bits_counter -= (is_set & is_corrected);
2116 return bits_counter;
2118 bits_counter += (*pcurr + 1u) & is_set;
2120 unsigned prev_gap = *pcurr++;
2121 for (is_set ^= ~0u; right > *pcurr; is_set ^= ~0u)
2123 bits_counter += (*pcurr - prev_gap) & is_set;
2126 bits_counter -= (is_set & is_corrected);
2127 return bits_counter;
2129 prev_gap = *pcurr++;
2131 bits_counter += (right - prev_gap) & is_set;
2132 bits_counter -= (is_set & is_corrected);
2133 return bits_counter;
2146template<
class T,
class Func>
2149 const T* pcurr = gap_buf;
2150 const T* pend = pcurr + (*pcurr >> 3);
2154 func((T)(prev + 1));
2158 func((T)(*pcurr - prev));
2160 }
while (++pcurr < pend);
2193 *dgap_buf++ = *gap_buf;
2197 for_each_dgap<T, d_copy_func<T> >(gap_buf, copy_func);
2217 const T* pcurr = dgap_buf;
2222 *gap_buf++ = *pcurr++;
2226 len = gap_header >> 3;
2227 *gap_buf++ = gap_header;
2230 const T* pend = pcurr + len;
2232 *gap_buf = *pcurr++;
2236 *gap_buf = T(*gap_buf - 1);
2238 for (++gap_buf; pcurr < pend; ++pcurr)
2240 T prev = *(gap_buf-1);
2241 *gap_buf++ = T(*pcurr + prev);
2258 const T* pcurr1 = buf1;
2259 const T* pend1 = pcurr1 + (*pcurr1 >> 3);
2260 unsigned bitval1 = *buf1 & 1;
2263 const T* pcurr2 = buf2;
2264 unsigned bitval2 = *buf2 & 1;
2267 while (pcurr1 <= pend1)
2269 if (*pcurr1 == *pcurr2)
2271 if (bitval1 != bitval2)
2273 return (bitval1) ? 1 : -1;
2278 if (bitval1 == bitval2)
2282 return (*pcurr1 < *pcurr2) ? -1 : 1;
2286 return (*pcurr1 < *pcurr2) ? 1 : -1;
2291 return (bitval1) ? 1 : -1;
2320 const T* pcurr1 = buf1;
2321 const T* pend1 = pcurr1 + (*pcurr1 >> 3);
2322 const T* pcurr2 = buf2;
2323 for (++pcurr1, ++pcurr2; pcurr1 <= pend1; ++pcurr1, ++pcurr2)
2325 if (*pcurr1 != *pcurr2)
2327 *pos = 1 + ((*pcurr1 < *pcurr2) ? *pcurr1 : *pcurr2);
2354template<
typename T,
class F>
2357 unsigned vect1_mask,
2359 unsigned vect2_mask,
2363 const T* cur1 = vect1;
2364 const T* cur2 = vect2;
2366 T bitval1 = (T)((*cur1++ & 1) ^ vect1_mask);
2367 T bitval2 = (T)((*cur2++ & 1) ^ vect2_mask);
2369 T bitval = (T) f(bitval1, bitval2);
2370 T bitval_prev = bitval;
2376 T c1 = *cur1; T c2 = *cur2;
2379 bitval = (T) f(bitval1, bitval2);
2384 res += (bitval != bitval_prev);
2385 bitval_prev = bitval;
2405 bitval1 ^= 1; bitval2 ^= 1;
2411 dlen = (unsigned)(res - dest);
2412 *dest = (T)((*dest & 7) + (dlen << 3));
2433template<
typename T,
class F>
2440 const T* cur1 = vect1;
2441 const T* cur2 = vect2;
2443 T bitval1 = (T)((*cur1++ & 1));
2444 T bitval2 = (T)((*cur2++ & 1));
2446 T bitval = (T) f(bitval1, bitval2);
2447 T bitval_prev = bitval;
2451 T c1 = *cur1; T c2 = *cur2;
2454 bitval = (T) f(bitval1, bitval2);
2459 len += (bitval != bitval_prev);
2462 bitval_prev = bitval;
2480 bitval1 ^= 1; bitval2 ^= 1;
2506template<
typename T,
class F>
2508 unsigned vect1_mask,
2510 unsigned vect2_mask,
2513 const T* cur1 = vect1;
2514 const T* cur2 = vect2;
2516 unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
2517 unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
2519 unsigned bitval = f(bitval1, bitval2);
2522 unsigned bitval_prev = bitval;
2526 bitval = f(bitval1, bitval2);
2530 if (bitval != bitval_prev)
2531 bitval_prev = bitval;
2575template<
typename T,
class F>
2579 const T* cur1 = vect1;
2580 const T* cur2 = vect2;
2582 unsigned bitval1 = (*cur1++ & 1);
2583 unsigned bitval2 = (*cur2++ & 1);
2584 unsigned bitval = count = f(bitval1, bitval2);
2585 unsigned bitval_prev = bitval;
2594 bitval = f(bitval1, bitval2);
2598 if (bitval != bitval_prev)
2600 bitval_prev = bitval;
2609 count += res - res_prev;
2612 ++cur1; bitval1 ^= 1;
2619 count += res - res_prev;
2632 bitval1 ^= 1; bitval2 ^= 1;
2644#pragma GCC diagnostic push
2645#pragma GCC diagnostic ignored "-Wconversion"
2669 T end = (T)(*buf >> 3);
2677 T* pcurr = buf + curr;
2678 T* pprev = pcurr - 1;
2679 T* pend = buf + end;
2688 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
2694 pprev = buf + 1; pcurr = pprev + 1;
2699 if (curr > 1 && ((
unsigned)(*pprev))+1 == pos)
2702 if (*pprev == *pcurr)
2710 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
2718 end += (pcurr == pend);
2723 ::memmove(pcurr+2, pcurr, (end - curr + 1)*(
sizeof(T)));
2725 pcurr[0] = (T)(pos-1);
2730 *buf = (T)((*buf & 7) + (end << 3));
2754 T end = (T)(*buf >> 3);
2758 T* pcurr = buf + curr;
2759 T* pprev = pcurr - 1;
2760 T* pend = buf + end;
2769 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
2775 pprev = buf + 1; pcurr = pprev + 1;
2780 if (curr > 1 && ((
unsigned)(*pprev))+1 == pos)
2783 if (*pprev == *pcurr)
2791 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
2799 end += (pcurr == pend);
2804 ::memmove(pcurr+2, pcurr, (end - curr + 1)*(
sizeof(T)));
2806 pcurr[0] = (T)(pos-1);
2811 *buf = (T)((*buf & 7) + (end << 3));
2831 T end = (T)(*buf >> 3);
2833 T* pcurr = buf + end;
2835 T* pprev = pcurr - 1;
2844 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
2850 pprev = buf + 1; pcurr = pprev + 1;
2852 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
2855 else if (((
unsigned)(*pprev))+1 == pos && (curr > 1) )
2858 if (*pprev == *pcurr)
2864 else if (*pcurr == pos)
2867 end += (pcurr == pend);
2871 pcurr[0] = (T)(pos-1);
2877 *buf = (T)((*buf & 7) + (end << 3));
2883#pragma GCC diagnostic pop
2904 unsigned bitval = *buf & 1;
2911 unsigned len = (*buf >> 3);
2913 for (; i < len; ++i)
2923 *buf = (T)((*buf & 7) + (len << 3));
2954 unsigned bitval = *buf & 1;
2964 BM_ASSERT(bitval ==
unsigned(*buf & 1u));
2976 unsigned len = (*buf >> 3);
2978 for (; i < len; ++i)
3007 *buf = (T)((*buf & 6u) + (1u << 3));
3015 *pcurr = (T)(curr - 1);
3025 for (i = 1; i < len; ++i)
3028 if (curr == prev + 1)
3037 *pcurr++ = (T)(curr-1);
3048 unsigned gap_len = unsigned(pcurr - buf);
3049 BM_ASSERT(gap_len == ((gap_len << 3) >> 3));
3051 *buf = (T)((*buf & 7) + (gap_len << 3));
3068 unsigned gap_count = 1;
3072 for (
unsigned i = 1; i < len; ++i)
3075 if (curr != prev + 1)
3112 unsigned val = buf[gap_idx] + 1;
3130 dest[nword] |= unsigned(1u << nbit);
3143 dest[nword] &= ~(unsigned(1u << nbit));
3157 return (block[nword] >> nbit) & 1u;
3172 const unsigned maskFF = ~0u;
3179 *dest |= (1u << bitpos);
3185 unsigned mask_r = maskFF << bitpos;
3186 unsigned right_margin = bitpos + bitcount;
3187 if (right_margin < 32)
3189 *dest |= (maskFF >> (32 - right_margin)) & mask_r;
3193 bitcount -= 32 - bitpos;
3195 for ( ;bitcount >= 64; bitcount-=64, dest+=2)
3196 dest[0] = dest[1] = maskFF;
3199 *dest++ = maskFF; bitcount -= 32;
3203 *dest |= maskFF >> (32 - bitcount);
3219 const unsigned maskFF = ~0u;
3226 *dest &= ~(1u << bitpos);
3232 unsigned mask_r = maskFF << bitpos;
3233 unsigned right_margin = bitpos + bitcount;
3234 if (right_margin < 32)
3236 *dest &= ~((maskFF >> (32 - right_margin)) & mask_r);
3240 bitcount -= 32 - bitpos;
3242 for ( ;bitcount >= 64; bitcount-=64, dest+=2)
3243 dest[0] = dest[1] = 0u;
3246 *dest++ = 0u; bitcount -= 32;
3250 *dest &= ~(maskFF >> (32 - bitcount));
3276 *word ^= unsigned(1 << nbit);
3282 unsigned right_margin = nbit + bitcount;
3287 if (right_margin < 32)
3296 bitcount -= 32 - nbit;
3299 for ( ;bitcount >= 64; bitcount-=64, word+=2)
3301 word[0] ^= ~0u; word[1] ^= ~0u;
3305 *word++ ^= ~0u; bitcount -= 32;
3325 const T* pend = pcurr + (*pcurr >> 3);
3331 for (pcurr += 2; pcurr <= pend; pcurr += 2)
3354 const T* pend = pcurr + (*pcurr >> 3);
3369 for (; pcurr <= pend; pcurr += 2)
3371 if (*pcurr >= start_pos)
3381 for (; pcurr <= pend; pcurr += 2)
3413 const T* pend = pcurr + (*pcurr >> 3);
3419 for (pcurr += 2; pcurr <= pend; pcurr += 2)
3441 const T* pend = pcurr + len;
3451 for (; pcurr <= pend; )
3454 pos = 1u + pcurr[-1];
3455 bc = *pcurr - pcurr[-1];
3473 unsigned len = (*pcurr >> 3);
3491 const T* pend = pcurr + (*pcurr >> 3);
3501 for (; pcurr <= pend; )
3504 pos = 1u + pcurr[-1];
3505 bc = *pcurr - pcurr[-1];
3528 const T* pend = pcurr + (*pcurr >> 3);
3543 for (; pcurr <= pend; pcurr += 2)
3545 if (*pcurr >= start_pos)
3555 for (; pcurr <= pend; pcurr += 2)
3587 const T* pend = pcurr + (*pcurr >> 3);
3594 for (pcurr +=2 ;pcurr <= pend; pcurr += 2)
3616 const T* pend = pcurr + (*pcurr >> 3);
3623 for (pcurr +=2 ;!count && pcurr <= pend; pcurr += 2)
3646 const T* pcurr = buf;
3647 const T* pend = pcurr + (*pcurr >> 3);
3659 for (;pcurr <= pend; pcurr+=2)
3681 const T* pcurr = buf;
3682 const T* pend = pcurr + (*pcurr >> 3);
3696 for (; !count && pcurr <= pend; pcurr+=2)
3719 const T* pcurr = buf;
3720 const T* pend = pcurr + (*pcurr >> 3);
3723 unsigned bitval = *buf & 1;
3728 count = *pcurr + 1 - count;
3731 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
3733 T prev = (T)(*(pcurr-1)+1);
3737 c = (*pcurr - prev + 1) - c;
3757 const T* pcurr = buf;
3758 const T* pend = pcurr + (*pcurr >> 3);
3761 unsigned bitval = *buf & 1;
3765 count = *pcurr + 1 - count;
3767 for (bitval^=1, ++pcurr; !count && pcurr <= pend; bitval^=1, ++pcurr)
3769 T prev = (T)(*(pcurr-1)+1);
3773 c = (*pcurr - prev + 1) - c;
3794 const T* pcurr = buf;
3795 const T* pend = pcurr + (*pcurr >> 3);
3798 unsigned bitval = *buf & 1;
3800 bm::id_t count = bitval ? *pcurr + 1
3802 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
3804 T prev = (T)(*(pcurr-1)+1);
3806 bitval ? (*pcurr - prev + 1)
3885 if (buf[1] == set_max - 1)
3904 unsigned end = *buf >> 3;
3906 const T* pcurr = buf;
3907 const T* pend = pcurr + (*pcurr >> 3);
3915 while (pcurr <= pend)
3936 *buf = (T)((*buf & 6u) + (1u << 3) + value);
3937 *(++buf) = (T)(set_max - 1);
3962 if (to == set_max - 1)
3970 buf[2] = (T)(set_max - 1);
3971 buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
3978 if (to == set_max - 1)
3981 buf[1] = (T)(from - 1);
3982 buf[2] = (T)(set_max - 1);
3987 buf[1] = (T) (from - 1);
3989 buf[3] = (T)(set_max - 1);
3991 buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
4008#pragma GCC diagnostic push
4009#pragma GCC diagnostic ignored "-Wconversion"
4025 *buf = (T)(((level & 3) << 1) | (*buf & 1) | (*buf & ~7));
4028#pragma GCC diagnostic pop
4044 if (len <=
unsigned(glevel_len[0]-4))
return 0;
4045 if (len <=
unsigned(glevel_len[1]-4))
return 1;
4046 if (len <=
unsigned(glevel_len[2]-4))
return 2;
4047 if (len <=
unsigned(glevel_len[3]-4))
return 3;
4068 return capacity - len;
4084 const T* pend1 = buf1 + len;
4091 return (w1 & diff & -diff) ? 1 : -1;
4092 }
while (buf1 < pend1);
4111#ifdef VECT_BIT_FIND_DIFF
4128 *pos = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::wordop_t))));
4140 *pos = unsigned(idx + (i * 8u *
sizeof(
bm::word_t)));
4171 unsigned bitval = (*block) & 1u;
4174 unsigned bit_idx = 0;
4178 unsigned val = *block;
4179 while (!val || val == ~0u)
4181 if (bitval !=
unsigned(
bool(val)))
4185 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4188 bit_idx += unsigned(
sizeof(*block) * 8);
4189 if (++block >= block_end)
4196 unsigned bits_consumed = 0;
4200 if (bitval != (val & 1u))
4204 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4214 bits_consumed += tz;
4220 if (bits_consumed < 32u)
4224 bit_idx += 32u - bits_consumed;
4225 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4232 }
while(++block < block_end);
4236 unsigned len = (unsigned)(pcurr - dest);
4237 *dest = (
gap_word_t)((*dest & 7) + (len << 3));
4252#if defined(VECT_BIT_TO_GAP)
4253 return VECT_BIT_TO_GAP(dest, block, dest_len);
4264template<
class T,
class F>
4267 const T* pcurr = buf;
4268 const T* pend = pcurr + (*pcurr >> 3);
4278 unsigned to = *pcurr;
4279 for (
unsigned i = 0; i <= to; ++i)
4292 while (pcurr <= pend)
4294 unsigned from = *(pcurr-1)+1;
4295 unsigned to = *pcurr;
4298 func(from - prev + first_inc);
4306 for (
unsigned i = from+1; i <= to; ++i)
4319template<
typename D,
typename T>
4326 const T* pend = pcurr + (*pcurr >> 3);
4331 int bitval = (*buf) & 1;
4337 if (
unsigned(*pcurr + 1) >= dest_len)
4350 while (pcurr <= pend)
4352 unsigned pending = *pcurr - *(pcurr-1);
4353 if (pending >= dest_len)
4355 dest_len -= pending;
4356 T from = (T)(*(pcurr-1)+1);
4358 for (T i = from; ;++i)
4365 return (D) (dest_curr - dest);
4424 }
while (block < block_end);
4497 }
while (block < block_end);
4523 count -= (w >> ((
sizeof(w) * 8) - 1));
4535 unsigned gap_count = 1;
4540 const int w_shift = int(
sizeof(w) * 8 - 1);
4543 gap_count -= (w_prev = (w0 >> w_shift));
4546 for (++block; block < block_end; ++block)
4552 gap_count -= !w_prev;
4561 gap_count -= (w0 >> w_shift);
4562 gap_count -= !(w_prev ^ w_l);
4564 w_prev = (w0 >> w_shift);
4587 #ifdef VECT_BLOCK_CHANGE_BC
4609#if defined(VECT_BLOCK_CHANGE)
4628 unsigned nword, nbit, bitcount, temp;
4633 return (*word >> nbit) & 1u;
4637 unsigned right_margin = nbit + right - left;
4638 if (right_margin < 32)
4643 return mask == (*word & mask);
4648 bitcount = (right - left + 1u) - (32 - nbit);
4653 bitcount = right - left + 1u;
4662 for ( ;bitcount >= 128; bitcount-=128, word+=4)
4666 if ((w64_0 ^ maskFF64) | (w64_1 ^ maskFF64))
4670 for ( ;bitcount >= 32; bitcount-=32, ++word)
4672 if (*word != maskFF)
4705 unsigned nword, nbit, bitcount, count;
4711 return (*word >> nbit) & 1u;
4715 bitcount = right - left + 1u;
4718 unsigned right_margin = nbit + right - left;
4719 if (right_margin < 32)
4727 bitcount -= 32 - nbit;
4733 #if defined(BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
4734 for ( ;bitcount >= 64; bitcount-=64)
4737 count += unsigned(_mm_popcnt_u64(w64));
4746 for ( ;bitcount >= 32; bitcount-=32, ++word)
4775 unsigned bitcount = right + 1;
4778 #if defined(BMAVX2OPT) || defined(BMAVX512OPT)
4779 BM_AVX2_POPCNT_PROLOG
4781 __m256i cnt = _mm256_setzero_si256();
4784 for ( ;bitcount >= 256; bitcount -= 256)
4786 const __m256i* src = (__m256i*)block;
4787 __m256i xmm256 = _mm256_load_si256(src);
4788 BM_AVX2_BIT_COUNT(bc, xmm256);
4789 cnt = _mm256_add_epi64(cnt, bc);
4794 count += (unsigned)(cnt64[0] + cnt64[1] + cnt64[2] + cnt64[3]);
4797 for ( ;bitcount >= 64; bitcount -= 64)
4829 block[i] = (block[i] << 1) | (block[i + 1] >> 31);
4843 const unsigned unroll_factor = 4;
4849 w0 = block[i + 1] >> 31;
4850 w1 = block[i + 2] >> 31;
4851 w2 = block[i + 3] >> 31;
4852 w3 = block[i + 4] >> 31;
4854 block[0 + i] = (block[0 + i] << 1) | w0;
4855 block[1 + i] = (block[1 + i] << 1) | w1;
4856 block[2 + i] = (block[2 + i] << 1) | w2;
4857 block[3 + i] = (block[3 + i] << 1) | w3;
4859 block[i] = (block[i] << 1) | (block[i + 1] >> 31);
4860 block[i + 1] = (block[i + 1] << 1) | (block[i + 2] >> 31);
4861 block[i + 2] = (block[i + 2] << 1) | (block[i + 3] >> 31);
4894 block[nword] = w | (unsigned(value) << nbit) | wl;
4906 w = (w << 1u) | co_flag;
4937 acc |= w = (w << 1u) | co_flag;
4961 #if defined(VECT_SHIFT_R1)
4991 acc |= w = (w >> 1u) | (co_flag << 31u);
5016 #if defined(VECT_SHIFT_L1)
5056 w = (w >> 1u) | (co_flag << 31u);
5068 w |= wl | (co_flag << 31u);
5073 block[nword] = (block[nword] >> 1u) | (co_flag << 31u);
5108 for (; di < 64; ++di)
5121 w = (w << 1u) | co_flag;
5122 acc |= block[i] = w & mask_block[i];
5138 block[d_base] = co_flag & mask_block[d_base];
5170 #if defined(VECT_SHIFT_R1_AND)
5192 unsigned nbit = left;
5200 return (*word >> nbit) & 1;
5203 unsigned bitcount = right - left + 1;
5207 unsigned right_margin = nbit + (right - left);
5208 if (right_margin < 32)
5213 return *word & mask;
5220 bitcount -= 32 - nbit;
5228 for ( ;bitcount >= 128; bitcount-=128, word+=4)
5230 acc = word[0] | word[1] | word[2] | word[3];
5236 for ( ;bitcount >= 32; bitcount -= 32)
5262 start[0] = ~start[0];
5263 start[1] = ~start[1];
5264 start[2] = ~start[2];
5265 start[3] = ~start[3];
5267 }
while (start < end);
5279#if defined(BMSSE42OPT) || defined(BMAVX2OPT)
5287 start[0] & start[1] & start[2] & start[3];
5291 }
while (start < end);
5332 bool is_left, is_right, all_one;
5345 if (is_left ==
false)
5349 if (is_right ==
false)
5382 w &= (1u << bit_pos);
5397 w = (~block[nword]) >> bit_pos;
5402 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))-1);
5412 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))-1);
5478 w &= (1u << bit_pos);
5497 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))+1);
5503 for (--nword;
true; --nword)
5509 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))+1);
5539 if (b && *found_nbit == 0)
5550 if (b && *found_nbit == 0)
5920#ifdef VECT_STREAM_BLOCK
5956 for (
unsigned i = 0; i < arr_sz; i+=4)
5958 acc |= dst_u->w64[i] &= src_u->w64[i];
5959 acc |= dst_u->w64[i+1] &= src_u->w64[i+1];
5960 acc |= dst_u->w64[i+2] &= src_u->w64[i+2];
5961 acc |= dst_u->w64[i+3] &= src_u->w64[i+3];
5996 #if defined(VECT_AND_DIGEST)
5999 digest &= ~(mask << wave);
6008 acc |= dst_u->w64[j+0] &= src_u->w64[j+0];
6009 acc |= dst_u->w64[j+1] &= src_u->w64[j+1];
6010 acc |= dst_u->w64[j+2] &= src_u->w64[j+2];
6011 acc |= dst_u->w64[j+3] &= src_u->w64[j+3];
6016 digest &= ~(mask << wave);
6042 BM_ASSERT(src0 && src1 && src2 && src3);
6053#if defined(VECT_AND_DIGEST_5WAY)
6054 bool all_zero =
VECT_AND_DIGEST_5WAY(&dst[off], &src0[off], &src1[off], &src2[off], &src3[off]);
6056 digest &= ~(mask << wave);
6068 acc |= dst_u->w64[j + 0] &= src_u0->w64[j + 0] & src_u1->w64[j + 0] & src_u2->w64[j + 0] & src_u3->w64[j + 0];
6069 acc |= dst_u->w64[j + 1] &= src_u0->w64[j + 1] & src_u1->w64[j + 1] & src_u2->w64[j + 1] & src_u3->w64[j + 1];
6070 acc |= dst_u->w64[j + 2] &= src_u0->w64[j + 2] & src_u1->w64[j + 2] & src_u2->w64[j + 2] & src_u3->w64[j + 2];
6071 acc |= dst_u->w64[j + 3] &= src_u0->w64[j + 3] & src_u1->w64[j + 3] & src_u2->w64[j + 3] & src_u3->w64[j + 3];
6076 digest &= ~(mask << wave);
6119 #if defined(VECT_AND_DIGEST_2WAY)
6122 digest &= ~(mask << wave);
6135 acc |= dst_u->w64[j+0] = src_u1->w64[j+0] & src_u2->w64[j+0];
6136 acc |= dst_u->w64[j+1] = src_u1->w64[j+1] & src_u2->w64[j+1];
6137 acc |= dst_u->w64[j+2] = src_u1->w64[j+2] & src_u2->w64[j+2];
6138 acc |= dst_u->w64[j+3] = src_u1->w64[j+3] & src_u2->w64[j+3];
6143 digest &= ~(mask << wave);
6185 }
while (b1 < b1_end);
6196 }
while (src1 < src1_end);
6220 count = (src1[0] & src2[0]) |
6221 (src1[1] & src2[1]) |
6222 (src1[2] & src2[2]) |
6223 (src1[3] & src2[3]);
6226 }
while ((src1 < src1_end) && !count);
6264 }
while (b1 < b1_end);
6275 }
while (src1 < src1_end);
6299 count = (src1[0] ^ src2[0]) |
6300 (src1[1] ^ src2[1]) |
6301 (src1[2] ^ src2[2]) |
6302 (src1[3] ^ src2[3]);
6305 }
while (!count && (src1 < src1_end));
6340 }
while (b1 < b1_end);
6351 }
while (src1 < src1_end);
6375 count = (src1[0] & ~src2[0]) |
6376 (src1[1] & ~src2[1]) |
6377 (src1[2] & ~src2[2]) |
6378 (src1[3] & ~src2[3]);
6381 }
while ((src1 < src1_end) && (count == 0));
6417 }
while (b1 < b1_end);
6428 }
while (src1 < src1_end);
6451 count = (src1[0] | src2[0]) |
6452 (src1[1] | src2[1]) |
6453 (src1[2] | src2[2]) |
6454 (src1[3] | src2[3]);
6457 }
while (!count && (src1 < src1_end));
6764 acc &= (dst_ptr[0] |= wrd_ptr[0]);
6765 acc &= (dst_ptr[1] |= wrd_ptr[1]);
6766 acc &= (dst_ptr[2] |= wrd_ptr[2]);
6767 acc &= (dst_ptr[3] |= wrd_ptr[3]);
6769 dst_ptr+=4;wrd_ptr+=4;
6771 }
while (wrd_ptr < wrd_end);
6772 return acc == not_acc;
6802 acc &= (dst_ptr[0] = wrd_ptr1[0] | wrd_ptr2[0]);
6803 acc &= (dst_ptr[1] = wrd_ptr1[1] | wrd_ptr2[1]);
6804 acc &= (dst_ptr[2] = wrd_ptr1[2] | wrd_ptr2[2]);
6805 acc &= (dst_ptr[3] = wrd_ptr1[3] | wrd_ptr2[3]);
6807 dst_ptr+=4; wrd_ptr1+=4; wrd_ptr2+=4;
6809 }
while (wrd_ptr1 < wrd_end1);
6810 return acc == not_acc;
6840 acc |= (dst_ptr[0] = wrd_ptr1[0] ^ wrd_ptr2[0]);
6841 acc |= (dst_ptr[1] = wrd_ptr1[1] ^ wrd_ptr2[1]);
6842 acc |= (dst_ptr[2] = wrd_ptr1[2] ^ wrd_ptr2[2]);
6843 acc |= (dst_ptr[3] = wrd_ptr1[3] ^ wrd_ptr2[3]);
6845 dst_ptr+=4; wrd_ptr1+=4; wrd_ptr2+=4;
6847 }
while (wrd_ptr1 < wrd_end1);
6882 acc &= (dst_ptr[0] |= wrd_ptr1[0] | wrd_ptr2[0]);
6883 acc &= (dst_ptr[1] |= wrd_ptr1[1] | wrd_ptr2[1]);
6884 acc &= (dst_ptr[2] |= wrd_ptr1[2] | wrd_ptr2[2]);
6885 acc &= (dst_ptr[3] |= wrd_ptr1[3] | wrd_ptr2[3]);
6887 dst_ptr+=4; wrd_ptr1+=4;wrd_ptr2+=4;
6889 }
while (wrd_ptr1 < wrd_end1);
6890 return acc == not_acc;
6930 acc &= (dst_ptr[0] |= wrd_ptr1[0] | wrd_ptr2[0] | wrd_ptr3[0] | wrd_ptr4[0]);
6931 acc &= (dst_ptr[1] |= wrd_ptr1[1] | wrd_ptr2[1] | wrd_ptr3[1] | wrd_ptr4[1]);
6932 acc &= (dst_ptr[2] |= wrd_ptr1[2] | wrd_ptr2[2] | wrd_ptr3[2] | wrd_ptr4[2]);
6933 acc &= (dst_ptr[3] |= wrd_ptr1[3] | wrd_ptr2[3] | wrd_ptr3[3] | wrd_ptr4[3]);
6936 wrd_ptr1+=4;wrd_ptr2+=4;wrd_ptr3+=4;wrd_ptr4+=4;
6938 }
while (wrd_ptr1 < wrd_end1);
6939 return acc == not_acc;
7032 for (
unsigned i = 0; i < arr_sz; i+=4)
7034 acc |= dst_u->w64[i] &= ~src_u->w64[i];
7035 acc |= dst_u->w64[i+1] &= ~src_u->w64[i+1];
7036 acc |= dst_u->w64[i+2] &= ~src_u->w64[i+2];
7037 acc |= dst_u->w64[i+3] &= ~src_u->w64[i+3];
7073 #if defined(VECT_SUB_DIGEST)
7076 digest &= ~(mask << wave);
7085 acc |= dst_u->w64[j+0] &= ~src_u->w64[j+0];
7086 acc |= dst_u->w64[j+1] &= ~src_u->w64[j+1];
7087 acc |= dst_u->w64[j+2] &= ~src_u->w64[j+2];
7088 acc |= dst_u->w64[j+3] &= ~src_u->w64[j+3];
7093 digest &= ~(mask << wave);
7134 #if defined(VECT_SUB_DIGEST_2WAY)
7137 digest &= ~(mask << wave);
7150 acc |= dst_u->w64[j+0] = src_u1->w64[j+0] & ~src_u2->w64[j+0];
7151 acc |= dst_u->w64[j+1] = src_u1->w64[j+1] & ~src_u2->w64[j+1];
7152 acc |= dst_u->w64[j+2] = src_u1->w64[j+2] & ~src_u2->w64[j+2];
7153 acc |= dst_u->w64[j+3] = src_u1->w64[j+3] & ~src_u2->w64[j+3];
7158 digest &= ~(mask << wave);
7256 for (
unsigned i = 0; i < arr_sz; i+=4)
7258 acc |= dst_u->w64[i] ^= src_u->w64[i];
7259 acc |= dst_u->w64[i+1] ^= src_u->w64[i+1];
7260 acc |= dst_u->w64[i+2] ^= src_u->w64[i+2];
7261 acc |= dst_u->w64[i+3] ^= src_u->w64[i+3];
7293 dst_ptr+=4; wrd_ptr+=4;
7294 }
while (wrd_ptr < wrd_end);
7315 if (src == dst)
return 0;
7321 if (!src)
return dst;
7327 if (!src)
return dst;
7411 const T* blk_end = blk + data_size - 2;
7417 const T* blk_j = blk + 1;
7418 for (; blk_j < blk_end; ++blk_j)
7429 const T* blk_j = blk + 1;
7430 for ( ; blk_j < blk_end; ++blk_j)
7435 if (blk_j[1] | blk_j[2])
7446 count += unsigned(blk_j - blk) * unsigned(
sizeof(T));
7451 while(blk < blk_end);
7452 return count + unsigned(2 *
sizeof(T));
7477 w &= (1u << bit_pos);
7483 w = block[nword] >> bit_pos;
7488 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
7498 *pos = unsigned(bit_pos + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
7532 *last = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
7558#ifdef VECT_BIT_FIND_FIRST
7567 *pos = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
7605 *first = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
7652 *first = unsigned(idx + (i * 8u *
sizeof(
bm::word_t)));
7681template<
typename SIZE_TYPE>
7693 unsigned pos = nbit_from;
7703 rank -= bc; pos += unsigned(32u - nbit);
7709 nbit_pos = pos + idx;
7723 nbit_pos = pos + idx;
7737 rank -= bc; pos += 32u;
7741 nbit_pos = pos + idx;
7760template<
typename SIZE_TYPE>
7786 unsigned total_possible_bitcount,
7794 if ((gap_size < block_size) && (gap_size < arr_size) && (gap_size < inv_arr_size))
7799 if (arr_size < inv_arr_size)
7801 if ((arr_size < block_size) && (arr_size < gap_size))
7808 if ((inv_arr_size < block_size) && (inv_arr_size < gap_size))
7829 for (
unsigned bit_idx=0; bit_idx < bits;
7830 ++src,bit_idx += unsigned(
sizeof(*src) * 8))
7832 unsigned val = *src ^ mask;
7835 if (pcurr +
unsigned(
sizeof(val)*8) >= dest + dest_len)
7845 return (T)(pcurr - dest);
7860 if (!blk)
return true;
7884 if (blk == 0)
return false;
7906 const T* length_end,
7909 BM_ASSERT(length && length_end && glevel_len);
7911 unsigned overhead = 0;
7912 for (;length < length_end; ++length)
7914 unsigned len = *length;
7917 unsigned capacity = glevel_len[level];
7919 overhead += capacity - len;
7933 const T* length_end,
7936 BM_ASSERT(length && length_end && glevel_len);
7938 size_t lsize = size_t(length_end - length);
7944 for (i = 0; i < lsize; ++i)
7946 if (length[i] > max_len)
7947 max_len = length[i];
7951 glevel_len[0] = T(max_len + 4);
7961 unsigned min_overhead =
gap_overhead(length, length_end, glevel_len);
7962 bool is_improved =
false;
7968 unsigned opt_len = 0;
7970 bool imp_flag =
false;
7972 for (j = 0; j < lsize; ++j)
7974 glevel_len[i] = T(length[j] + 4);
7975 unsigned ov =
gap_overhead(length, length_end, glevel_len);
7976 if (ov <= min_overhead)
7979 opt_len = length[j]+4;
7985 glevel_len[i] = (T)opt_len;
7990 glevel_len[i] = gap_saved_value;
7998 T val = *glevel_len;
8000 T* res = glevel_len;
8037 if (!blk || !arg_blk)
8180 if (cnt_ < from_ || cnt_ > to_)
8185 return decoder_.get_32();
8200template<
class It1,
class It2,
class BinaryOp,
class Encoder>
8206 for (
unsigned i = 0; i < block_size; ++i)
8381 &gap_and_to_bitset<bm::gap_word_t>,
8382 &gap_add_to_bitset<bm::gap_word_t>,
8383 &gap_sub_to_bitset<bm::gap_word_t>,
8384 &gap_xor_to_bitset<bm::gap_word_t>,
8437 unsigned short cnt0;
8442#if defined(BMAVX512OPT) || defined(BMAVX2OPT) || defined(BMSSE42OPT)
8464#if defined (BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
8474 unsigned size,
unsigned start,
8477typedef unsigned TRGW;
8478typedef unsigned IDX;
8479#if defined(BM64_SSE4)
8486#elif defined(BM64_AVX2) || defined(BM64_AVX512)
8489 avx2_bit_block_gather_scatter(arr, blk, idx, size, start, bit_idx);
8503template<
typename TRGW,
typename IDX,
typename SZ>
8507 SZ size, SZ start,
unsigned bit_idx)
BMNOEXCEPT
8512 const SZ len = (size - start);
8513 const SZ len_unr = len - (len % 2);
8515 for (; k < len_unr; k+=2)
8517 const SZ base = start + k;
8525 for (; k < len; ++k)
8553 for (;(start < size) &&
8573 unsigned size,
unsigned nb,
unsigned start)
BMNOEXCEPT
8578#if defined(VECT_ARR_BLOCK_LOOKUP)
8581 for (;(start < size) &&
8616 block[nword] |= (1u << nbit);
8639#if defined(VECT_SET_BLOCK_BITS)
8642 for (
unsigned i = start; i < stop; ++i)
8644 unsigned n = idx[i];
8648 block[nword] |= (1u << nbit);
8703#if defined(VECT_LOWER_BOUND_SCAN_U32)
8706 for (; from <= to; ++from)
8708 if (arr[from] >= target)
8721 unsigned long long target,
8728 for (; from <= to; ++from)
8730 if (arr[from] >= target)
8750 const unsigned linear_cutoff = 32;
8752 unsigned l = from;
unsigned r = to;
8753 unsigned dist = r - l;
8754 if (dist < linear_cutoff)
8761 unsigned mid = (r-l)/2+l;
8762 if (arr[mid] < target)
8767 if (dist < linear_cutoff)
8781 unsigned long long target,
8786 const unsigned linear_cutoff = 32;
8788 unsigned l = from;
unsigned r = to;
8789 unsigned dist = r - l;
8790 if (dist < linear_cutoff)
8797 unsigned mid = (r - l) / 2 + l;
8798 if (arr[mid] < target)
8803 if (dist < linear_cutoff)
8824 return block_idx + base_idx;
8833 return block_idx + base_idx;
8861 return (ptr.i16[1] == 0);
8863 bm::id64_t r = (ptr.i16[1] == v) | (ptr.i16[2] == v) | (ptr.i16[3] == v);
#define IS_FULL_BLOCK(addr)
#define IS_VALID_ADDR(addr)
#define FULL_BLOCK_FAKE_ADDR
#define IS_EMPTY_BLOCK(addr)
#define FULL_BLOCK_REAL_ADDR
#define VECT_SET_BLOCK(dst, value)
#define VECT_BITCOUNT_OR(first, last, mask)
#define VECT_BIT_FIND_DIFF(src1, src2, pos)
#define VECT_AND_DIGEST_5WAY(dst, src1, src2, src3, src4)
#define VECT_OR_BLOCK_5WAY(dst, src1, src2, src3, src4)
#define VECT_COPY_BLOCK(dst, src)
#define VECT_BITCOUNT_AND(first, last, mask)
#define VECT_SHIFT_R1(b, acc, co)
#define VECT_XOR_BLOCK_2WAY(dst, src1, src2)
#define VECT_IS_ONE_BLOCK(dst)
#define VECT_STREAM_BLOCK(dst, src)
#define VECT_OR_BLOCK(dst, src)
#define VECT_SHIFT_R1_AND(b, co, m, digest)
#define VECT_SUB_BLOCK(dst, src)
#define VECT_IS_ZERO_BLOCK(dst)
#define VECT_SUB_DIGEST_2WAY(dst, src1, src2)
#define VECT_XOR_BLOCK(dst, src)
#define VECT_IS_DIGEST_ZERO(start)
#define VECT_ANDNOT_ARR_2_MASK(dst, src, src_end, mask)
#define VECT_BLOCK_CHANGE_BC(block, gc, bc)
#define VECT_SHIFT_L1(b, acc, co)
#define VECT_LOWER_BOUND_SCAN_U32(arr, target, from, to)
#define VECT_SET_BLOCK_BITS(block, idx, start, stop)
#define VECT_BITCOUNT_SUB(first, last, mask)
#define VECT_BITCOUNT_XOR(first, last, mask)
#define VECT_AND_DIGEST(dst, src)
#define VECT_BIT_FIND_FIRST(src, pos)
#define VECT_GAP_BFIND(buf, pos, is_set)
#define VECT_INVERT_BLOCK(first)
#define VECT_BLOCK_CHANGE(block, size)
#define VECT_AND_DIGEST_2WAY(dst, src1, src2)
#define VECT_BLOCK_SET_DIGEST(dst, val)
#define VECT_ARR_BLOCK_LOOKUP(idx, size, nb, start)
#define VECT_BITCOUNT(first, last)
#define VECT_SUB_DIGEST(dst, src)
#define VECT_OR_BLOCK_3WAY(dst, src1, src2)
#define VECT_OR_BLOCK_2WAY(dst, src1, src2)
#define VECT_AND_BLOCK(dst, src)
Bit manipulation primitives (internal)
Bit-block get adapter, takes bitblock and represents it as a get_32() accessor function.
bitblock_get_adapter(const bm::word_t *bit_block)
BMFORCEINLINE bm::word_t get_32() BMNOEXCEPT
Bit-block store adapter, takes bitblock and saves results into it.
BMFORCEINLINE void push_back(bm::word_t w)
bitblock_store_adapter(bm::word_t *bit_block)
Bit-block sum adapter, takes values and sums it /internal.
BMFORCEINLINE void push_back(bm::word_t w) BMNOEXCEPT
bm::word_t sum() const BMNOEXCEPT
Get accumulated sum.
Adaptor to copy 1 bits to array.
copy_to_array_functor(B *bits)
void operator()(unsigned bit_idx0, unsigned bit_idx1, unsigned bit_idx2) BMNOEXCEPT
void operator()(unsigned bit_idx0, unsigned bit_idx1, unsigned bit_idx2, unsigned bit_idx3) BMNOEXCEPT
void operator()(unsigned bit_idx0, unsigned bit_idx1) BMNOEXCEPT
void operator()(unsigned bit_idx) BMNOEXCEPT
Adapter to get words from a range stream (see range serialized bit-block)
bm::word_t get_32() BMNOEXCEPT
decoder_range_adapter(DEC &dec, unsigned from_idx, unsigned to_idx)
unsigned sse2_gap_test(const unsigned short *BMRESTRICT buf, unsigned pos)
Hybrid binary search, starts as binary, then switches to scan.
unsigned sse42_gap_test(const unsigned short *BMRESTRICT buf, unsigned pos)
Hybrid binary search, starts as binary, then switches to scan.
BMFORCEINLINE bool sse42_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
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_block_calc_count_range(const bm::word_t *block, bm::word_t left, bm::word_t right) BMNOEXCEPT
bm::id64_t 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) BMNOEXCEPT
digest based bit-block AND 5-way
unsigned bit_block_find(const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
Searches for the next 1 bit in the BIT block.
bool bit_block_or_2way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
2 way (target := source1 | source2) bitblock OR operation.
bm::id_t bit_operation_sub_count_inv(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs inverted bitblock SUB operation and calculates bitcount of the result.
BMFORCEINLINE bm::id_t word_bitcount(bm::id_t w) BMNOEXCEPT
unsigned bit_block_and_any(const bm::word_t *src1, const bm::word_t *src2) BMNOEXCEPT
Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source b...
unsigned bit_block_sub_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of sour...
unsigned bit_block_calc_change(const bm::word_t *block) BMNOEXCEPT
void bit_block_copy(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Bitblock copy operation.
bool 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) BMNOEXCEPT
Right bit-shift of bit-block by 1 bit (reference) + AND.
T bit_convert_to_arr(T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len, unsigned mask=0) BMNOEXCEPT
Convert bit block into an array of ints corresponding to 1 bits.
unsigned bit_count_nonzero_size(const T *blk, unsigned data_size) BMNOEXCEPT
Inspects block for full zero words.
bm::id_t bit_count_change(bm::word_t w) BMNOEXCEPT
unsigned bit_block_and_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of sour...
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::id64_t 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) BMNOEXCEPT
digest based bitblock SUB (AND NOT) operation (3 operand)
void block_init_digest0(bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT
Init block with 000111000 pattren based on digest.
bool check_zero_digest(bm::id64_t digest, unsigned bitpos_from, unsigned bitpos_to) BMNOEXCEPT
check if all digest bits for the range [from..to] are 0
void or_bit_block(unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
Sets bits to 1 in the bitblock.
bm::id64_t bit_block_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks...
bm::id_t bit_block_count(const bm::word_t *block) BMNOEXCEPT
Bitcount for bit block.
bool bit_block_is_all_one_range(const bm::word_t *const BMRESTRICT block, bm::word_t left, bm::word_t right) BMNOEXCEPT
bool 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) BMNOEXCEPT
5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of sou...
BMFORCEINLINE void clear_bit(unsigned *dest, unsigned bitpos) BMNOEXCEPT
Set 1 bit in a block.
void xor_bit_block(unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
XOR bit interval to 1 in the bitblock.
BMFORCEINLINE bm::id64_t widx_to_digest_mask(unsigned w_idx) BMNOEXCEPT
Compute digest mask for word address in block.
void bit_block_gather_scatter(unsigned *BMRESTRICT arr, const bm::word_t *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx) BMNOEXCEPT
bit index to word gather-scatter algorithm (SIMD)
bm::id_t bit_block_calc_count(const bm::word_t *block, const bm::word_t *block_end) BMNOEXCEPT
Bitcount for bit string.
int wordcmp0(T w1, T w2)
Lexicographical comparison of two words as bit strings (reference) Auxiliary implementation for testi...
bm::word_t * bit_operation_xor(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
bitblock XOR operation.
bool bit_block_shift_r1_unr(bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::word_t co_flag) BMNOEXCEPT
Right bit-shift of bit-block by 1 bit (loop unrolled)
bm::set_representation best_representation(unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size) BMNOEXCEPT
Choose best representation for a bit-block.
bm::id_t bit_operation_or_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock OR operation and calculates bitcount of the result.
bool 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) BMNOEXCEPT
Right bit-shift bitblock by 1 bit (reference) + AND.
BMFORCEINLINE unsigned word_bitcount64(bm::id64_t x) BMNOEXCEPT
SIZE_TYPE bit_find_rank(const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) BMNOEXCEPT
BIT block find position for the rank.
BMFORCEINLINE void set_bit(unsigned *dest, unsigned bitpos) BMNOEXCEPT
Set 1 bit in a block.
bm::id_t bit_block_calc_count_to(const bm::word_t *block, bm::word_t right) BMNOEXCEPT
void bit_block_erase(bm::word_t *block, unsigned bitpos, bool carry_over) BMNOEXCEPT
erase bit from position and shift the rest right with carryover
bool bit_block_find_interval_end(const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
Searches for the last 1 bit in the 111 interval of a 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.
void bit_for_each_4(T w, F &func)
Templated algorithm to unpacks octet based word into list of ON bit indexes.
unsigned bit_block_xor_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of sour...
bm::word_t * bit_operation_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Block OR operation. Makes analysis if block is 0 or FULL.
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.
bool bit_block_shift_l1_unr(bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) BMNOEXCEPT
Left bit-shift of bit-block by 1 bit (loop unrolled)
bm::id64_t calc_block_digest0(const bm::word_t *const block) BMNOEXCEPT
Compute digest for 64 non-zero areas.
bm::id64_t 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) BMNOEXCEPT
digest based bit-block AND
void sub_bit_block(unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
SUB (AND NOT) bit interval to 1 in the bitblock.
unsigned bit_scan_reverse(T value) BMNOEXCEPT
#define BM_INCWORD_BITCOUNT(cnt, w)
bm::word_t * bit_operation_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
bitblock SUB operation.
void bit_for_each(T w, F &func)
Templated algorithm to unpacks word into list of ON bit indexes.
unsigned short bitscan_wave(const bm::word_t *BMRESTRICT w_ptr, unsigned char *BMRESTRICT bits) BMNOEXCEPT
Unpacks word wave (Nx 32-bit words)
bool bit_find_first(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT pos) BMNOEXCEPT
BIT block find the first set bit.
void bit_invert(T *start) BMNOEXCEPT
unsigned bit_block_sub_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of sour...
bool bit_find_first_diff(const bm::word_t *BMRESTRICT blk1, const bm::word_t *BMRESTRICT blk2, unsigned *BMRESTRICT pos) BMNOEXCEPT
Find first bit which is different between two bit-blocks.
unsigned short bitscan_popcnt64(bm::id64_t w, B *bits) BMNOEXCEPT
Unpacks 64-bit word into list of ON bit indexes using popcnt method.
bool bit_block_or_3way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of s...
int bitcmp(const T *buf1, const T *buf2, unsigned len) BMNOEXCEPT
Lexicographical comparison of BIT buffers.
unsigned bit_list_4(T w, B *bits) BMNOEXCEPT
Unpacks word into list of ON bit indexes (quad-bit based)
unsigned bit_block_or_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of sourc...
bm::id64_t bit_block_xor(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks...
bm::word_t * bit_operation_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
bitblock AND operation.
void bit_block_set(bm::word_t *BMRESTRICT dst, bm::word_t value) BMNOEXCEPT
Bitblock memset operation.
BMFORCEINLINE unsigned test_bit(const unsigned *block, unsigned bitpos) BMNOEXCEPT
Test 1 bit in a block.
void bit_block_rotate_left_1_unr(bm::word_t *block) BMNOEXCEPT
Unrolled cyclic rotation of bit-block left by 1 bit.
BMFORCEINLINE bm::id64_t digest_mask(unsigned from, unsigned to) BMNOEXCEPT
Compute digest mask for [from..to] positions.
bool bit_block_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.
bool bit_is_all_zero(const bm::word_t *BMRESTRICT start) BMNOEXCEPT
Returns "true" if all bits in the block are 0.
unsigned bit_find_last(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT last) BMNOEXCEPT
BIT block find the last set bit (backward search)
bool bit_find_first_if_1(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT first, bm::id64_t digest) BMNOEXCEPT
BIT block find the first set bit if only 1 bit is set.
bm::id64_t update_block_digest0(const bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT
Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas)
bool bit_block_shift_r1(bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::word_t co_flag) BMNOEXCEPT
Right bit-shift bitblock by 1 bit (reference)
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_xor_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock XOR operation and calculates bitcount of the result.
unsigned bit_list(T w, B *bits) BMNOEXCEPT
Unpacks word into list of ON bit indexes.
void bit_block_rotate_left_1(bm::word_t *block) BMNOEXCEPT
unsigned bit_block_or_count(const bm::word_t *src1, const bm::word_t *src2) BMNOEXCEPT
Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of sourc...
void bit_andnot_arr_ffmask(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
bitblock AND NOT with constant ~0 mask operation.
unsigned bit_block_xor_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of sour...
void bit_block_stream(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Bitblock copy/stream operation.
bm::word_t bit_block_insert(bm::word_t *BMRESTRICT block, unsigned bitpos, bool value) BMNOEXCEPT
insert bit into position and shift the rest right with carryover
bool bit_block_find_interval_start(const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
Searches for the first 1 bit in the 111 interval of a BIT block.
bm::id64_t bit_block_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destinat...
int wordcmp(T a, T b)
Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and refe...
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.
bm::id64_t bit_block_xor_2way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
2 way (target := source1 ^ source2) bitblock XOR operation.
bool is_bits_one(const bm::wordop_t *start) BMNOEXCEPT
Returns "true" if all bits in the block are 1.
bool bit_block_shift_l1(bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) BMNOEXCEPT
Left bit-shift bitblock by 1 bit (reference)
set_operation
Codes of set operations.
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.
unsigned gap_find_last(const T *BMRESTRICT buf, unsigned *BMRESTRICT last) BMNOEXCEPT
GAP block find the last set bit.
unsigned gap_bit_count_unr(const T *buf) BMNOEXCEPT
Calculates number of bits ON in GAP buffer. Loop unrolled version.
D gap_convert_to_arr(D *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned dest_len, bool invert=false) BMNOEXCEPT
Convert gap block into array of ints corresponding to 1 bits.
void gap_and_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
ANDs GAP block to bitblock.
gap_word_t * gap_operation_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
GAP XOR operation.
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Sets or clears bit in the GAP buffer.
T gap_level(const T *BMRESTRICT buf) BMNOEXCEPT
Returs GAP blocks capacity level.
bool gap_operation_dry_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, unsigned &dsize, unsigned limit) BMNOEXCEPT
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.
void gap_split(const T *buf, T *arr0, T *arr1, T &arr0_cnt, T &arr1_cnt) BMNOEXCEPT
bool gap_find_interval_end(const T *const BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
Searches for the last 1 bit in the 111 interval of a 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.
void gap_xor_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
XOR GAP block to bitblock.
bool gap_shift_r1(T *BMRESTRICT buf, unsigned co_flag, unsigned *BMRESTRICT new_len) BMNOEXCEPT
Right shift GAP block by 1 bit.
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.
int gapcmp(const T *buf1, const T *buf2) BMNOEXCEPT
Lexicographical comparison of GAP buffers.
unsigned gap_bit_count_to(const T *const buf, T right, bool is_corrected=false) BMNOEXCEPT
Counts 1 bits in GAP buffer in the closed [0, right] range.
BMFORCEINLINE unsigned gap_operation_any_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP SUB operation test.
unsigned gap_find_first(const T *BMRESTRICT buf, unsigned *BMRESTRICT first) BMNOEXCEPT
GAP block find the first set bit.
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.
void for_each_gap_dbit(const T *buf, F &func)
Iterate gap block as delta-bits with a functor.
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.
bool gap_find_interval_start(const T *const BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
Searches for the first 1 bit in the 111 interval of a GAP block.
unsigned gap_free_elements(const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
Returns number of free elements in GAP block array. Difference between GAP block capacity on this lev...
unsigned gap_test(const T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
Tests if bit = pos is true.
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 gap_invert(T *buf) BMNOEXCEPT
Inverts all bits in the GAP buffer.
unsigned * gap_convert_to_bitset_smart(unsigned *BMRESTRICT dest, const T *BMRESTRICT buf, id_t set_max) BMNOEXCEPT
Smart GAP block to bitblock conversion.
unsigned gap_set_array(T *buf, const T *arr, unsigned len) BMNOEXCEPT
Convert array to GAP buffer.
void set_gap_level(T *buf, int level) BMNOEXCEPT
Sets GAP block capacity level.
void gap_sub_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
SUB (AND NOT) GAP block to bitblock.
unsigned gap_block_find(const T *BMRESTRICT buf, unsigned nbit, bm::id_t *BMRESTRICT prev) BMNOEXCEPT
Searches for the next 1 bit in the GAP block.
void gap_init_range_block(T *buf, T from, T to, T value) BMNOEXCEPT
Init gap block so it has block in it (can be whole block)
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.
unsigned gap_control_sum(const T *buf) BMNOEXCEPT
Calculates sum of all words in GAP block. (For debugging purposes)
BMFORCEINLINE bool gap_is_all_zero(const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
Checks if GAP block is all-zero.
SIZE_TYPE gap_find_rank(const T *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) BMNOEXCEPT
GAP block find position for the rank.
BMFORCEINLINE bool gap_is_all_one(const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
Checks if GAP block is all-one.
unsigned gap_bit_count(const T *buf, unsigned dsize=0) BMNOEXCEPT
Calculates number of bits ON in GAP buffer.
bool gap_shift_l1(T *BMRESTRICT buf, unsigned co_flag, unsigned *BMRESTRICT new_len) BMNOEXCEPT
Left shift GAP block by 1 bit.
void gap_add_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, unsigned len) BMNOEXCEPT
Adds(OR) GAP block to bitblock.
unsigned gap_overhead(const T *length, const T *length_end, const T *glevel_len) BMNOEXCEPT
Calculates memory overhead for number of gap blocks sharing the same memory allocation table (level l...
bool gap_any_range(const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
Test if any bits are 1 in GAP buffer in the [left, right] range.
bool gap_is_all_one_range(const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
Test if all bits are 1 in GAP buffer in the [left, right] range.
BMFORCEINLINE gap_word_t * gap_operation_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
GAP AND operation.
bool gap_find_first_diff(const T *BMRESTRICT buf1, const T *BMRESTRICT buf2, unsigned *BMRESTRICT pos) BMNOEXCEPT
Find first bit which is different between two GAP-blocks.
void gap_convert_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT buf) BMNOEXCEPT
GAP block to bitblock conversion.
void gap_set_all(T *buf, unsigned set_max, unsigned value) BMNOEXCEPT
Sets all bits to 0 or 1 (GAP)
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.
unsigned bit_array_compute_gaps(const T *arr, unsigned len) BMNOEXCEPT
Compute number of GAPs in bit-array.
unsigned gap_bit_count_range(const T *const buf, unsigned left, unsigned right) BMNOEXCEPT
Counts 1 bits in GAP buffer in the closed [left, right] range.
unsigned gap_add_value(T *buf, unsigned pos) BMNOEXCEPT
Add new value to the end of GAP buffer.
unsigned bit_block_to_gap(gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
Converts bit block to GAP.
int gap_calc_level(unsigned len, const T *glevel_len) BMNOEXCEPT
Calculates GAP block capacity level.
bool gap_is_interval(const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
Test if any bits are 1 in GAP buffer in the [left, right] range and flanked with 0s.
gap_word_t * gap_operation_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
GAP SUB (AND NOT) operation.
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.
bool improve_gap_levels(const T *length, const T *length_end, T *glevel_len) BMNOEXCEPT
Finds optimal gap blocks lengths.
unsigned gap_capacity(const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
Returs GAP block capacity.
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.
unsigned gap_buff_any_op(const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, F f) BMNOEXCEPT2
Abstract distance test operation for GAP buffers. Receives functor F as a template argument.
BMFORCEINLINE bm::gap_word_t gap_length(const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
Returs GAP block length.
unsigned gap_buff_count_op(const T *vect1, const T *vect2, F f) BMNOEXCEPT2
Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument.
const unsigned set_array_mask
bool block_any(const bm::word_t *const BMRESTRICT block) BMNOEXCEPT
Returns "true" if one bit is set in the block Function check for block varieties.
bm::id_t(* bit_operation_count_func_type)(const bm::word_t *BMRESTRICT, const bm::word_t *BMRESTRICT)
unsigned lower_bound_u32(const unsigned *arr, unsigned target, unsigned from, unsigned to) BMNOEXCEPT
Hybrid, binary-linear lower bound search in unsigned array.
const id64_t all_bits_mask
const unsigned set_block_digest_wave_size
void for_each_nzblock(T ***root, unsigned size1, F &f)
void bit_block_change_bc(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT gc, unsigned *BMRESTRICT bc) BMNOEXCEPT
unsigned bitcount64_4way(bm::id64_t x, bm::id64_t y, bm::id64_t u, bm::id64_t v) BMNOEXCEPT
void gap_buff_op(T *BMRESTRICT dest, const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, F &f, unsigned &dlen) BMNOEXCEPT2
Abstract operation for GAP buffers. Receives functor F as a template argument.
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
bool gap_buff_dry_op(const T *BMRESTRICT vect1, const T *BMRESTRICT vect2, F &f, unsigned &dlen, unsigned limit) BMNOEXCEPT2
Abstract operation for GAP buffers (predicts legth) Receives functor F as a template argument.
bool block_is_interval(const bm::word_t *const BMRESTRICT block, unsigned left, unsigned right) BMNOEXCEPT
Returns "true" if all bits are 1 in the block [left, right] and border bits are 0.
bool check_block_zero(const bm::word_t *blk, bool deep_scan) BMNOEXCEPT
Checks all conditions and returns true if block consists of only 0 bits.
bool block_is_all_one_range(const bm::word_t *const BMRESTRICT block, unsigned left, unsigned right) BMNOEXCEPT
Returns "true" if all bits are 1 in the block [left, right] Function check for block varieties.
const bm::gap_word_t * sse2_gap_sum_arr(const bm::gap_word_t *BMRESTRICT pbuf, unsigned sse_vect_waves, unsigned *sum)
Gap block population count (array sum) utility.
const unsigned set_block_mask
T * gap_2_dgap(const T *BMRESTRICT gap_buf, T *BMRESTRICT dgap_buf, bool copy_head=true) BMNOEXCEPT
Convert GAP buffer into D-GAP buffer.
bm::id_t bit_block_any_range(const bm::word_t *block, bm::word_t left, bm::word_t right) BMNOEXCEPT
BMFORCEINLINE unsigned and_op(unsigned v1, unsigned v2) BMNOEXCEPT2
GAP and functor.
bm::id64_t sum_arr(const T *first, const T *last) BMNOEXCEPT
unsigned short bitscan(V w, B *bits) BMNOEXCEPT
bool check_block_one(const bm::word_t *blk, bool deep_scan) BMNOEXCEPT
Checks if block has only 1 bits.
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.
unsigned bit_to_gap(gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
Convert bit block to GAP representation.
const unsigned set_sub_array_size
void for_each_dgap(const T *gap_buf, Func &func)
unsigned bit_block_change32(const bm::word_t *block, unsigned size) BMNOEXCEPT
unsigned lower_bound_u64(const unsigned long long *arr, unsigned long long target, unsigned from, unsigned to) BMNOEXCEPT
Hybrid, binary-linear lower bound search in unsigned LONG array.
unsigned word_select64_bitscan(bm::id64_t w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
set_representation
set representation variants
@ set_bitset
Simple bitset.
@ set_gap
GAP-RLE compression.
@ set_array1
array of set 1 values
@ set_array0
array of 0 values
bool block_ptr_array_range(bm::word_t **arr, unsigned &left, unsigned &right) BMNOEXCEPT
array range detector
unsigned word_select64(bm::id64_t w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
unsigned block_find_interval_start(const bm::word_t *BMRESTRICT block, unsigned nbit_from, unsigned *BMRESTRICT found_nbit) BMNOEXCEPT
Find start of the current 111 interval.
gap_word_t *(* gap_operation_func_type)(const gap_word_t *BMRESTRICT, const gap_word_t *BMRESTRICT, gap_word_t *BMRESTRICT, unsigned &)
bool block_find_first_diff(const bm::word_t *BMRESTRICT blk, const bm::word_t *BMRESTRICT arg_blk, unsigned *BMRESTRICT pos) BMNOEXCEPT
Find first bit which is different between two blocks (GAP or bit)
const unsigned gap_levels
void for_each_nzblock2(T ***root, unsigned size1, F &f)
F bmfor_each(T first, T last, F f)
bool find_not_null_ptr(bm::word_t ***arr, N start, N size, N *pos) BMNOEXCEPT
void bit_recomb(It1 &it1, It2 &it2, BinaryOp &op, Encoder &enc, unsigned block_size=bm::set_block_size) BMNOEXCEPT
unsigned bit_scan_reverse32(unsigned value) BMNOEXCEPT
bm::operation setop2op(bm::set_operation op) BMNOEXCEPT
Convert set operation to operation.
const unsigned set_word_shift
bm::id64_t idx_arr_block_lookup_u64(const bm::id64_t *idx, bm::id64_t size, bm::id64_t nb, bm::id64_t start) BMNOEXCEPT
block boundaries look ahead U32
const unsigned set_sub_total_bits
const unsigned set_block_digest_pos_shift
unsigned count_leading_zeros_u64(bm::id64_t w) BMNOEXCEPT
64-bit bit-scan reverse
const unsigned set_block_size
unsigned long long int id64_t
bool block_any_range(const bm::word_t *const BMRESTRICT block, unsigned left, unsigned right) BMNOEXCEPT
Returns "true" if one bit is set in the block [left, right] Function check for block varieties.
unsigned lower_bound_linear_u64(const unsigned long long *arr, unsigned long long target, unsigned from, unsigned to) BMNOEXCEPT
Linear lower bound search in unsigned LONG array.
const unsigned gap_max_buff_len
int parallel_popcnt_32(unsigned int n) BMNOEXCEPT
BMFORCEINLINE RTYPE get_super_block_start(unsigned i) BMNOEXCEPT
Compute bit address of the first bit in a superblock.
void set_block_bits_u32(bm::word_t *BMRESTRICT block, const unsigned *BMRESTRICT idx, unsigned start, unsigned stop) BMNOEXCEPT
set bits in a bit-block using global index
unsigned idx_arr_block_lookup_u32(const unsigned *idx, unsigned size, unsigned nb, unsigned start) BMNOEXCEPT
block boundaries look ahead U32
BMFORCEINLINE unsigned long long bmi_bslr_u64(unsigned long long w) BMNOEXCEPT
bm::id64_t ptrp_test(ptr_payload_t ptr, bm::gap_word_t v) BMNOEXCEPT
const unsigned short set_bitscan_wave_size
Size of bit decode wave in words.
const unsigned set_array_shift
void dgap_2_gap(const T *BMRESTRICT dgap_buf, T *BMRESTRICT gap_buf, T gap_header=0) BMNOEXCEPT
Convert D-GAP buffer into GAP buffer.
bm::id_t block_to_global_index(unsigned i, unsigned j, unsigned block_idx) BMNOEXCEPT
calculate bvector<> global bit-index from block-local coords
unsigned short gap_word_t
unsigned count_trailing_zeros_u64(bm::id64_t w) BMNOEXCEPT
64-bit bit-scan fwd
void(* gap_operation_to_bitset_func_type)(unsigned *, const 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 sse4_bit_block_gather_scatter(unsigned *BMRESTRICT arr, const unsigned *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx)
unsigned word_select64_linear(bm::id64_t w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
void for_each_block(T ***root, unsigned size1, F &f, BLOCK_IDX start)
unsigned lower_bound_linear_u32(const unsigned *arr, unsigned target, unsigned from, unsigned to) BMNOEXCEPT
Linear lower bound search in unsigned array.
const unsigned set_block_shift
void for_each_nzblock_range(T ***root, N top_size, N nb_from, N nb_to, F &f) BMNOEXCEPT
const unsigned set_word_mask
BMFORCEINLINE unsigned long long bmi_blsi_u64(unsigned long long w)
const unsigned bits_in_block
unsigned block_find_interval_end(const bm::word_t *BMRESTRICT block, unsigned nbit_from, unsigned *BMRESTRICT found_nbit) BMNOEXCEPT
Find end of the current 111 interval.
BMFORCEINLINE unsigned or_op(unsigned v1, unsigned v2) BMNOEXCEPT2
GAP or functor.
BMFORCEINLINE unsigned xor_op(unsigned v1, unsigned v2) BMNOEXCEPT2
GAP xor functor.
unsigned bit_scan_forward32(unsigned value) BMNOEXCEPT
BMFORCEINLINE unsigned sub_op(unsigned v1, unsigned v2) BMNOEXCEPT2
GAP or functor.
void set_block_bits_u64(bm::word_t *BMRESTRICT block, const bm::id64_t *BMRESTRICT idx, bm::id64_t start, bm::id64_t stop) BMNOEXCEPT
set bits in a bit-block using global index
bool for_each_nzblock_if(T ***root, BI size1, F &f) BMNOEXCEPT
SIZE_TYPE block_find_rank(const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) BMNOEXCEPT
Find rank in block (GAP or BIT)
bool is_const_set_operation(set_operation op) BMNOEXCEPT
Returns true if set operation is constant (bitcount)
bm::word_t BM_VECT_ALIGN _p[bm::set_block_size] BM_VECT_ALIGN_ATTR
bm::word_t BM_VECT_ALIGN *_s[bm::set_sub_array_size] BM_VECT_ALIGN_ATTR
Structure carries pointer on bit block with all bits 1.
static BMFORCEINLINE bool is_valid_block_addr(const bm::word_t *bp) BMNOEXCEPT
static all_set_block _block
static BMFORCEINLINE bool is_full_block(const bm::word_t *bp) BMNOEXCEPT
static bm::id64_t block_type(const bm::word_t *bp) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W) BMNOEXCEPT
W operator()(W, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
Bit COUNT SUB AB functor.
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
bit-block array wrapped into union for correct interpretation of 32-bit vs 64-bit access vs SIMD
Structure to aid in counting bits table contains count of bits in 0-255 diapason of numbers.
bit-decode cache structure
Structure keeps all-left/right ON bits masks.
Structure with statistical information about memory allocation footprint, serialization projection,...
size_t gap_cap_overhead
gap memory overhead between length and capacity
size_t ptr_sub_blocks
Number of sub-blocks.
unsigned long long gaps_by_level[bm::gap_levels]
number of GAP blocks at each level
size_t gap_blocks
Number of GAP blocks.
size_t bit_blocks
Number of bit blocks.
size_t bv_count
Number of bit-vectors.
void add_gap_block(unsigned capacity, unsigned length) BMNOEXCEPT
count gap block
gap_word_t gap_levels[bm::gap_levels]
GAP block lengths in the bvect.
size_t max_serialize_mem
estimated maximum memory for serialization
void reset() BMNOEXCEPT
Reset statisctics.
void add_bit_block() BMNOEXCEPT
cound bit block
size_t memory_used
memory usage for all blocks and service tables
void add(const bv_statistics &st) BMNOEXCEPT
Sum data from another sttructure.
ad-hoc conditional expressions
static bit_operation_count_func_type bit_operation_count(unsigned i)
static gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
static bit_operation_count_func_type bit_op_count_table_[bm::set_END]
static gap_operation_func_type gap_operation(unsigned i)
static gap_operation_func_type gapop_table_[bm::set_END]
static gap_operation_to_bitset_func_type gap2bit_table_[bm::set_END]
helper union to interpret pointer as integers