1#ifndef BMFUNC__H__INCLUDED__
2#define BMFUNC__H__INCLUDED__
33# pragma warning( disable: 4146 )
40template<
bool LWA=false,
bool RWA=false>
84 size_t mem_used = (capacity *
sizeof(
gap_word_t));
152template<
typename First,
typename Second>
178template<
typename BI_TYPE>
190template<
typename RTYPE>
200template<
typename RTYPE>
236 tmp = n - ((n >> 1) & 033333333333)
237 - ((n >> 2) & 011111111111);
238 return ((tmp + (tmp >> 3)) & 030707070707) % 63;
256 x = x - ((x >> 1) & m1);
257 y = y - ((y >> 1) & m1);
258 u = u - ((u >> 1) & m1);
259 v = v - ((v >> 1) & m1);
260 x = (x & m2) + ((x >> 2) & m2);
261 y = (y & m2) + ((y >> 2) & m2);
262 u = (u & m2) + ((u >> 2) & m2);
263 v = (v & m2) + ((v >> 2) & m2);
266 x = (x & m3) + ((x >> 4) & m3);
267 u = (u & m3) + ((u >> 4) & m3);
273 return x & 0x000001FFU;
288template<
typename T,
typename F>
291 for (
unsigned sub_octet = 0; w != 0; w >>= 4, sub_octet += 4)
304 func(sub_octet, sub_octet + 1);
310 func(sub_octet, sub_octet + 2);
313 func(sub_octet + 1, sub_octet + 2);
316 func(sub_octet, sub_octet + 1, sub_octet + 2);
322 func(sub_octet, sub_octet + 3);
325 func(sub_octet + 1, sub_octet + 3);
328 func(sub_octet, sub_octet + 1, sub_octet + 3);
331 func(sub_octet + 2, sub_octet + 3);
334 func(sub_octet, sub_octet + 2, sub_octet + 3);
337 func(sub_octet + 1, sub_octet + 2, sub_octet + 3);
340 func(sub_octet, sub_octet + 1, sub_octet + 2, sub_octet + 3);
358template<
typename T,
typename F>
362 for (
unsigned octet = 0; w != 0; w >>= 8, octet += 8)
364 if (w & 1) func(octet + 0);
365 if (w & 2) func(octet + 1);
366 if (w & 4) func(octet + 2);
367 if (w & 8) func(octet + 3);
368 if (w & 16) func(octet + 4);
369 if (w & 32) func(octet + 5);
370 if (w & 64) func(octet + 6);
371 if (w & 128) func(octet + 7);
385 for (
unsigned sub_octet = 0; w; w >>= 4, sub_octet+=4)
392 bits[cnt++] = 0 + sub_octet;
395 bits[cnt++] = 1 + sub_octet;
398 bits[cnt] = 0 + sub_octet;
399 bits[cnt+1] = 1 + sub_octet;
403 bits[cnt++] = 2 + sub_octet;
406 bits[cnt+0] = 0 + sub_octet;
407 bits[cnt+1] = 2 + sub_octet;
411 bits[cnt+0] = 1 + sub_octet;
412 bits[cnt+1] = 2 + sub_octet;
416 bits[cnt+0] = 0 + sub_octet;
417 bits[cnt+1] = 1 + sub_octet;
418 bits[cnt+2] = 2 + sub_octet;
422 bits[cnt++] = 3 + sub_octet;
425 bits[cnt+0] = 0 + sub_octet;
426 bits[cnt+1] = 3 + sub_octet;
430 bits[cnt+0] = 1 + sub_octet;
431 bits[cnt+1] = 3 + sub_octet;
435 bits[cnt+0] = 0 + sub_octet;
436 bits[cnt+1] = 1 + sub_octet;
437 bits[cnt+2] = 3 + sub_octet;
441 bits[cnt+0] = 2 + sub_octet;
442 bits[cnt+1] = 3 + sub_octet;
446 bits[cnt+0] = 0 + sub_octet;
447 bits[cnt+1] = 2 + sub_octet;
448 bits[cnt+2] = 3 + sub_octet;
452 bits[cnt+0] = 1 + sub_octet;
453 bits[cnt+1] = 2 + sub_octet;
454 bits[cnt+2] = 3 + sub_octet;
458 bits[cnt+0] = 0 + sub_octet;
459 bits[cnt+1] = 1 + sub_octet;
460 bits[cnt+2] = 2 + sub_octet;
461 bits[cnt+3] = 3 + sub_octet;
471#ifdef BM_NONSTANDARD_EXTENTIONS
479unsigned bitscan_nibble_gcc(
unsigned w,
unsigned* bits)
BMNOEXCEPT
481 static void* d_table[] = { &&l0,
482 &&l1, &&l3_1, &&l3, &&l7_1, &&l5, &&l7_0, &&l7, &&l15_1,
483 &&l9, &&l11_0, &&l11, &&l15_0, &&l13, &&l14, &&l15 };
486 for (
unsigned sub_octet = 0; w; w >>= 4, sub_octet+=4)
488 goto *d_table[w & 15];
490 bits[cnt++] = sub_octet;
493 bits[cnt++] = sub_octet;
495 bits[cnt++] = 1 + sub_octet;
498 bits[cnt++] = sub_octet;
501 bits[cnt++] = sub_octet;
503 bits[cnt++] = 1 + sub_octet;
505 bits[cnt++] = 2 + sub_octet;
508 bits[cnt++] = sub_octet;
512 bits[cnt++] = sub_octet;
514 bits[cnt++] = 1 + sub_octet;
515 bits[cnt++] = 3 + sub_octet;
518 bits[cnt++] = sub_octet;
521 bits[cnt++] = 1 + sub_octet;
524 bits[cnt++] = 0 + sub_octet;
525 bits[cnt++] = 1 + sub_octet;
527 bits[cnt++] = 2 + sub_octet;
529 bits[cnt++] = 3 + sub_octet;
556 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
564 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1; bp_[2] = (B)bit_idx2;
573 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
574 bp_[2] = (B)bit_idx2; bp_[3] = (B)bit_idx3;
594template<
typename T,
typename B>
599 return (
unsigned)(func.
ptr() - bits);
612template<
typename T,
typename B>
617 return (
unsigned)(func.
ptr() - bits);
641 return (
unsigned short)pos;
663 return (
unsigned short)pos;
677 unsigned short pos = 0;
699 unsigned short pos = 0;
708template<
typename B,
typename OT>
711 unsigned short pos = 0;
732 unsigned short pos = 0;
754 unsigned short pos = 0;
768template<
typename V,
typename B>
771 static_assert(std::is_unsigned<V>::value,
"BM: unsigned type is required");
772#if (defined(__arm__) || defined(__aarch64__))
773 if constexpr (
sizeof(V) == 8)
778 if constexpr (
sizeof(V) == 8)
804 for (
unsigned count = 0; w; w >>=1ull, ++count)
806 rank -= unsigned(w & 1ull);
940#if defined(BMI2_SELECT64)
941 return BMI2_SELECT64(w, rank);
943 #if defined(BMI1_SELECT64)
944 return BMI2_SELECT64(w, rank);
946 #if (defined(__arm__) || defined(__aarch64__))
967#if defined(BMI2_SELECT64)
968 return BMI2_SELECT64(w, rank);
970 #if defined(BMI1_SELECT64)
971 return BMI2_SELECT64(w, rank);
973 #if (defined(__arm__) || defined(__aarch64__))
1010 for (
unsigned i = from; i <= to; ++i)
1011 m |= (1ull << (i / 1024));
1033 ((~0ull) >> (63 - (digest_to - digest_from))) << digest_from;
1055 unsigned bitpos_from,
unsigned bitpos_to)
BMNOEXCEPT
1058 return !(digest & mask);
1071 bool prev = digest & mask;
1072 unsigned cnt = prev;
1073 for (mask <<= 1; mask; mask <<= 1)
1075 bool curr = digest & mask;
1076 if (curr && curr != prev)
1094 for (
unsigned i = 0; i < 64; ++i)
1097 bm::word_t mask = 0u - unsigned(digest & 1u);
1098 BM_ASSERT(mask == ((digest & 1) ? ~0u : 0u));
1099#if defined(VECT_BLOCK_SET_DIGEST)
1104 block[off] = block[off+1] = block[off+2] = block[off+3] = mask;
1125 for (
unsigned i = 0; i < 64; ++i)
1128 #if defined(VECT_IS_DIGEST_ZERO)
1135 bm::word_t w = block[off+j+0] | block[off+j+1] |
1136 block[off+j+2] | block[off+j+3];
1139 digest0 |= (mask << i);
1175 #if defined(VECT_IS_DIGEST_ZERO)
1177 digest &= all_zero ? ~(mask << wave) : digest;
1186 src_u->w64[j+0] | src_u->w64[j+1] | src_u->w64[j+2] | src_u->w64[j+3];
1189 digest &= w64 ? digest : ~(mask << wave);
1216 unsigned t_wave = 0;
1231 for (; sub_block < sub_block_end; t_sub_block+=4, sub_block+=4)
1233 t_sub_block[0] = sub_block[0];
1234 t_sub_block[1] = sub_block[1];
1235 t_sub_block[2] = sub_block[2];
1236 t_sub_block[3] = sub_block[3];
1253 for (; t_sub_block < t_sub_block_end; t_sub_block+=4)
1283 unsigned s_wave = 0;
1297 for (; sub_block < sub_block_end; t_sub_block+=4, sub_block+=4)
1299 t_sub_block[0] = sub_block[0];
1300 t_sub_block[1] = sub_block[1];
1301 t_sub_block[2] = sub_block[2];
1302 t_sub_block[3] = sub_block[3];
1313 for (; t_sub_block < t_sub_block_end; t_sub_block+=4)
1315 t_sub_block[0] = 0; t_sub_block[1] = 0;
1316 t_sub_block[2] = 0; t_sub_block[3] = 0;
1365 ::memset(
_p, 0xFF,
sizeof(
_p));
1366 if constexpr (
sizeof(
void*) == 8)
1368 const unsigned long long magic_mask = 0xFFFFfffeFFFFfffe;
1369 ::memcpy(&
_p_fullp, &magic_mask,
sizeof(magic_mask));
1371 _s[i] =
reinterpret_cast<bm::word_t*
>(magic_mask);
1375 const unsigned magic_mask = 0xFFFFfffe;
1376 ::memcpy(&
_p_fullp, &magic_mask,
sizeof(magic_mask));
1378 _s[i] =
reinterpret_cast<bm::word_t*
>(magic_mask);
1389 if constexpr (
sizeof(
void*) == 8)
1391 bm::id64_t w =
reinterpret_cast<unsigned long long>(bp);
1393 ((bp ==
_block._p) << 1);
1394 type = type ? type : w;
1398 unsigned w =
reinterpret_cast<unsigned long>(bp);
1400 ((bp ==
_block._p) << 1);
1401 type = type ? type : w;
1412 {
return (bp && !(bp ==
_block._p || bp ==
_block._p_fullp)); }
1435 const unsigned unroll_factor = 4;
1436 const unsigned len = (size - start);
1437 const unsigned len_unr = len - (len % unroll_factor);
1441 for (k = 0; k < len_unr; k+=unroll_factor)
1452 *pos = k + start + 1;
1457 *pos = k + start + 2;
1462 *pos = k + start + 3;
1468 for (; k < len; ++k)
1477 for (; start < size; ++start)
1507 int res = (w1 & 1) - (w2 & 1);
1508 if (res != 0)
return res;
1535 return diff? ( (a & diff & -diff)? 1 : -1 ) : 0;
1552#if defined(VECT_IS_ZERO_BLOCK)
1559 if (blk[0] | blk[1] | blk[2] | blk[3])
1562 }
while (blk < blk_end);
1621 return glevel_len[(*buf >> 1) & 3];
1637 return glevel_len[(*buf >> 1) & 3]-4;
1651 return T((*buf >> 1) & 3u);
1671 T is_set = (*buf) & 1u;
1672 T end = T((*buf) >> 3u);
1676 is_set ^= T((end-1) & 1u);
1702 T is_set = (*buf) & 1u;
1710 *first = buf[1] + 1;
1730 #if defined(VECT_GAP_BFIND)
1734 unsigned end = ((*buf) >> 3);
1736 unsigned size = end - start;
1737 for (; size >= 64; size = end - start)
1739 unsigned mid = (start + end) >> 1;
1744 if (buf[mid = (start + end) >> 1] < pos)
1748 if (buf[mid = (start + end) >> 1] < pos)
1752 if (buf[mid = (start + end) >> 1] < pos)
1758 for (; size >= 16; size = end - start)
1760 if (
unsigned mid = (start + end) >> 1; buf[mid] < pos)
1764 if (
unsigned mid = (start + end) >> 1; buf[mid] < pos)
1770 for(;
true; ++start)
1771 if (buf[start] >= pos)
1774 *is_set = ((*buf) & 1) ^ ((start-1) & 1);
1795 unsigned end = 1 + ((*buf) >> 3);
1796 if (end - start < 10)
1798 unsigned sv = *buf & 1;
1799 unsigned sv1= sv ^ 1;
1800 if (buf[1] >= pos)
return sv;
1801 if (buf[2] >= pos)
return sv1;
1802 if (buf[3] >= pos)
return sv;
1803 if (buf[4] >= pos)
return sv1;
1804 if (buf[5] >= pos)
return sv;
1805 if (buf[6] >= pos)
return sv1;
1806 if (buf[7] >= pos)
return sv;
1807 if (buf[8] >= pos)
return sv1;
1816 if (
unsigned mid = (start + end) >> 1; buf[mid] < pos)
1820 }
while (start != end);
1822 return ((*buf) & 1) ^ ((--start) & 1);
1838#if defined(VECT_GAP_TEST)
1850template<
typename T,
typename N,
typename F>
1852 N top_size, N nb_from, N nb_to, F& f)
BMNOEXCEPT
1855 if (nb_from > nb_to)
1862 if (i_from >= top_size)
1864 if (i_to >= top_size)
1866 i_to = unsigned(top_size-1);
1870 for (
unsigned i = i_from; i <= i_to; ++i)
1872 T** blk_blk = root[i];
1877 unsigned j = (i == i_from) ? j_from : 0;
1878 if (!j && (i != i_to))
1885 if ((i == i_to) && (j == j_to))
1892 unsigned j = (i == i_from) ? j_from : 0;
1897 if ((i == i_to) && (j == j_to))
1907template<
class T,
class F>
1910 typedef typename F::size_type
size_type;
1911 for (
unsigned i = 0; i < size1; ++i)
1913 T** blk_blk = root[i];
1919 f.on_non_empty_top(i);
1931 unsigned non_empty_top = 0;
1936#if defined(BM64_AVX2) || defined(BM64_AVX512)
1940 T* blk0 = blk_blk[j + 0];
1941 T* blk1 = blk_blk[j + 1];
1942 T* blk2 = blk_blk[j + 2];
1943 T* blk3 = blk_blk[j + 3];
1949 f.on_empty_block(block_idx);
1952 f(blk1, block_idx + 1);
1954 f.on_empty_block(block_idx + 1);
1957 f(blk2, block_idx + 2);
1959 f.on_empty_block(block_idx + 2);
1962 f(blk3, block_idx + 3);
1964 f.on_empty_block(block_idx + 3);
1968 f.on_empty_block(r + j + 0); f.on_empty_block(r + j + 1);
1969 f.on_empty_block(r + j + 2); f.on_empty_block(r + j + 3);
1972#elif defined(BM64_SSE4)
1976 T* blk0 = blk_blk[j + 0];
1977 T* blk1 = blk_blk[j + 1];
1983 f.on_empty_block(block_idx);
1989 f.on_empty_block(block_idx);
1993 f.on_empty_block(r + j + 0);
1994 f.on_empty_block(r + j + 1);
2000 f(blk_blk[j], r + j);
2004 f.on_empty_block(r + j);
2009 if (non_empty_top == 0)
2016template<
class T,
class F>
2020 for (
unsigned i = 0; i < size1; ++i)
2023 if ((blk_blk = root[i])!=0)
2037 w0 = _mm_loadu_si128((__m128i*)(blk_blk + j));
2038 if (!_mm_testz_si128(w0, w0))
2040 T* blk0 = blk_blk[j + 0];
2041 T* blk1 = blk_blk[j + 1];
2048 w0 = _mm_loadu_si128((__m128i*)(blk_blk + j + 2));
2049 if (!_mm_testz_si128(w0, w0))
2051 T* blk0 = blk_blk[j + 2];
2052 T* blk1 = blk_blk[j + 3];
2062#elif defined(BM64_AVX2) || defined(BM64_AVX512)
2063 for (
unsigned i = 0; i < size1; ++i)
2066 if ((blk_blk = root[i]) != 0)
2079 __m256i w0 = _mm256_loadu_si256((__m256i*)(blk_blk + j));
2080 if (!_mm256_testz_si256(w0, w0))
2084 T* blk0 = blk_blk[j + 0];
2085 T* blk1 = blk_blk[j + 1];
2086 T* blk2 = blk_blk[j + 2];
2087 T* blk3 = blk_blk[j + 3];
2103 for (
unsigned i = 0; i < size1; ++i)
2106 if ((blk_blk = root[i])!=0)
2138template<
typename T,
typename BI,
typename F>
2142 for (BI i = 0; i < size1; ++i)
2144 T** blk_blk = root[i];
2163 if (f(blk_blk[j], block_idx))
2172template<
class T,
class F,
typename BLOCK_IDX>
2175 BLOCK_IDX block_idx = start;
2176 for (
unsigned i = 0; i < size1; ++i)
2178 T** blk_blk = root[i];
2191 f(blk_blk[j], block_idx);
2214 }
while (first < last);
2224 for (;first < last; ++first)
2240 T* arr0, T* arr1, T& arr0_cnt, T& arr1_cnt)
BMNOEXCEPT
2242 const T* pcurr = buf;
2243 unsigned len = (*pcurr >> 3);
2244 const T* pend = pcurr + len;
2248 unsigned is_set = (*buf & 1);
2254 arr1[cnt1] = *pcurr;
2259 arr0[cnt0] = *pcurr;
2266 while (pcurr <= pend)
2269 T delta = *pcurr - prev;
2301 const T* pcurr = buf;
2303 dsize = (*pcurr >> 3);
2305 const T* pend = pcurr + dsize;
2307 unsigned bits_counter = 0;
2312 bits_counter += *pcurr + 1;
2315 for (++pcurr; pcurr <= pend; pcurr += 2)
2316 bits_counter += *pcurr - *(pcurr-1);
2317 return bits_counter;
2329 const T* pcurr = buf;
2330 unsigned dsize = (*pcurr >> 3);
2334 T first_one = *buf & 1;
2342 #if defined(BMAVX2OPT) || defined(BMAVX512OPT)
2345 const unsigned unr_factor = 32;
2346 unsigned waves = (dsize-2) / unr_factor;
2349 #elif defined(BMSSE42OPT) || defined(BMSSE2OPT)
2352 const unsigned unr_factor = 16;
2353 unsigned waves = (dsize - 2) / unr_factor;
2359 const unsigned unr_factor = 8;
2360 unsigned waves = (dsize - 2) / unr_factor;
2361 for (
unsigned i = 0; i < waves; i += unr_factor)
2363 cnt += pcurr[0] - pcurr[0 - 1];
2364 cnt += pcurr[2] - pcurr[2 - 1];
2365 cnt += pcurr[4] - pcurr[4 - 1];
2366 cnt += pcurr[6] - pcurr[6 - 1];
2368 pcurr += unr_factor;
2373 const T* pend = buf + dsize;
2374 for ( ; pcurr <= pend ; pcurr+=2)
2375 cnt += *pcurr - *(pcurr - 1);
2392template<
typename T,
bool RIGHT_END = false>
2399 unsigned is_set, bits_counter, prev_gap;
2401 is_set = ~(is_set - 1u);
2403 const T* pcurr = buf + start_pos;
2404 if (right <= *pcurr)
2405 bits_counter = unsigned(right - left + 1u) & is_set;
2408 bits_counter = unsigned(*pcurr - left + 1u) & is_set;
2409 if constexpr (RIGHT_END)
2412 for (prev_gap = *pcurr++ ;
true; prev_gap = *pcurr++)
2414 bits_counter += (is_set ^= ~0u) & (*pcurr - prev_gap);
2421 for (prev_gap = *pcurr++; right > *pcurr; prev_gap = *pcurr++)
2422 bits_counter += (is_set ^= ~0u) & (*pcurr - prev_gap);
2423 bits_counter += unsigned(right - prev_gap) & (is_set ^ ~0u);
2426 return bits_counter;
2442 unsigned left,
unsigned right,
unsigned hint)
BMNOEXCEPT
2447 unsigned is_set, bits_counter, prev_gap;
2451 is_set = ~(is_set - 1u);
2452 unsigned start_pos = hint >> 1;
2454 unsigned is_set_c; (void)is_set_c;
2455 unsigned pos; (void)pos;
2457 BM_ASSERT(
bool(is_set) ==
bool(is_set_c));
2460 const T* pcurr = buf + start_pos;
2461 if (right <= *pcurr)
2462 bits_counter = unsigned(right - left + 1u) & is_set;
2465 bits_counter = unsigned(*pcurr - left + 1u) & is_set;
2466 for (prev_gap = *pcurr++; right > *pcurr; prev_gap = *pcurr++)
2467 bits_counter += (is_set ^= ~0u) & (*pcurr - prev_gap);
2468 bits_counter += unsigned(right - prev_gap) & (is_set ^ ~0u);
2470 return bits_counter;
2493 const T*
const pcurr = buf + start_pos;
2494 return (right <= *pcurr);
2514 const T*
const pcurr = buf + start_pos;
2518 if (right <= *pcurr)
2545 const T* pcurr = buf + start_pos;
2546 if (!is_set || (right != *pcurr) || (start_pos <= 1))
2549 if (*pcurr != left-1)
2574 *pos = buf[start_pos];
2603 *pos = buf[start_pos]+1;
2634 *pos = buf[start_pos];
2653template<
typename T,
typename SIZE_TYPE>
2662 const T* pcurr = block;
2663 const T* pend = pcurr + (*pcurr >> 3);
2665 unsigned bits_counter = 0;
2667 unsigned start_pos =
bm::gap_bfind(block, nbit_from, &is_set);
2668 is_set = ~(is_set - 1u);
2670 pcurr = block + start_pos;
2671 bits_counter += unsigned(*pcurr - nbit_from + 1u) & is_set;
2672 if (bits_counter >= rank)
2674 nbit_pos = nbit_from + unsigned(rank) - 1u;
2677 rank -= bits_counter;
2678 unsigned prev_gap = *pcurr++;
2679 for (is_set ^= ~0u; pcurr <= pend; is_set ^= ~0u)
2681 bits_counter = (*pcurr - prev_gap) & is_set;
2682 if (bits_counter >= rank)
2684 nbit_pos = prev_gap + unsigned(rank);
2687 rank -= bits_counter;
2688 prev_gap = *pcurr++;
2695template<
typename T,
bool TCORRECT=false>
2700 unsigned bits_counter, prev_gap;
2702 unsigned is_set = ~((unsigned(*buf) & 1u) - 1u);
2703 const T* pcurr = buf + 1;
2704 if (right <= *pcurr)
2706 bits_counter = (right + 1u) & is_set;
2710 bits_counter = (*pcurr + 1u) & is_set;
2711 prev_gap = *pcurr++;
2712 for (is_set ^= ~0u; right > *pcurr; is_set ^= ~0u, prev_gap = *pcurr++)
2714 bits_counter += (*pcurr - prev_gap) & is_set;
2718 bits_counter += (right - prev_gap) & is_set;
2722 if constexpr (TCORRECT)
2723 bits_counter -= (is_set &
unsigned(TCORRECT));
2724 return bits_counter;
2738template<
class T,
class Func>
2741 const T* pcurr = gap_buf;
2742 const T* pend = pcurr + (*pcurr >> 3);
2746 func((T)(prev + 1));
2750 func((T)(*pcurr - prev));
2752 }
while (++pcurr < pend);
2785 *dgap_buf++ = *gap_buf;
2809 const T* pcurr = dgap_buf;
2814 *gap_buf++ = *pcurr++;
2818 len = gap_header >> 3;
2819 *gap_buf++ = gap_header;
2822 const T* pend = pcurr + len;
2824 *gap_buf = *pcurr++;
2828 *gap_buf = T(*gap_buf - 1);
2830 for (++gap_buf; pcurr < pend; ++pcurr)
2832 T prev = *(gap_buf-1);
2833 *gap_buf++ = T(*pcurr + prev);
2850 const T* pcurr1 = buf1;
2851 const T* pend1 = pcurr1 + (*pcurr1 >> 3);
2852 unsigned bitval1 = *buf1 & 1;
2855 const T* pcurr2 = buf2;
2856 unsigned bitval2 = *buf2 & 1;
2859 while (pcurr1 <= pend1)
2861 if (*pcurr1 == *pcurr2)
2863 if (bitval1 != bitval2)
2865 return (bitval1) ? 1 : -1;
2870 if (bitval1 == bitval2)
2874 return (*pcurr1 < *pcurr2) ? -1 : 1;
2878 return (*pcurr1 < *pcurr2) ? 1 : -1;
2883 return (bitval1) ? 1 : -1;
2910 const T* pcurr1 = buf1;
2911 const T* pend1 = pcurr1 + (*pcurr1 >> 3);
2912 const T* pcurr2 = buf2;
2913 for (++pcurr1, ++pcurr2; pcurr1 <= pend1; ++pcurr1, ++pcurr2)
2915 if (*pcurr1 != *pcurr2)
2917 *pos = 1 + ((*pcurr1 < *pcurr2) ? *pcurr1 : *pcurr2);
2943template<
typename T,
class F>
2946 unsigned vect1_mask,
2948 unsigned vect2_mask,
2951 const T* cur1 = vect1;
2952 const T* cur2 = vect2;
2954 T bitval1 = (T)((*cur1++ & 1) ^ vect1_mask);
2955 T bitval2 = (T)((*cur2++ & 1) ^ vect2_mask);
2957 T bitval = (T) F::op(bitval1, bitval2);
2958 T bitval_prev = bitval;
2964 T c1 = *cur1; T c2 = *cur2;
2967 bitval = (T) F::op(bitval1, bitval2);
2972 res += (bitval != bitval_prev);
2973 bitval_prev = bitval;
2993 bitval1 ^= 1; bitval2 ^= 1;
2999 dlen = (unsigned)(res - dest);
3000 *dest = (T)((*dest & 7) + (dlen << 3));
3018template<
typename T,
class F>
3020 unsigned vect1_mask,
3024 const T* cur1 = vect1;
3025 const T* cur2 = vect2;
3027 unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
3028 unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
3030 unsigned bitval = F::op(bitval1, bitval2);
3033 unsigned bitval_prev = bitval;
3037 bitval = F::op(bitval1, bitval2);
3041 if (bitval != bitval_prev)
3042 bitval_prev = bitval;
3062 bitval1 ^= 1; bitval2 ^= 1;
3083template<
typename T,
class F>
3087 const T* cur1 = vect1;
3088 const T* cur2 = vect2;
3090 unsigned bitval1 = (*cur1++ & 1);
3091 unsigned bitval2 = (*cur2++ & 1);
3092 unsigned bitval = count = F::op(bitval1, bitval2);
3093 unsigned bitval_prev = bitval;
3100 bitval = F::op(bitval1, bitval2);
3103 if (bitval != bitval_prev)
3105 bitval_prev = bitval;
3114 count += res - res_prev;
3117 ++cur1; bitval1 ^= 1;
3124 count += res - res_prev;
3137 bitval1 ^= 1; bitval2 ^= 1;
3149#pragma GCC diagnostic push
3150#pragma GCC diagnostic ignored "-Wconversion"
3174 T end = (T)(*buf >> 3);
3182 T* pcurr = buf + curr;
3183 T* pprev = pcurr - 1;
3184 T* pend = buf + end;
3193 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
3199 pprev = buf + 1; pcurr = pprev + 1;
3204 if (curr > 1 && ((
unsigned)(*pprev))+1 == pos)
3207 if (*pprev == *pcurr)
3215 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
3223 end += (pcurr == pend);
3228 ::memmove(pcurr+2, pcurr, (end - curr + 1)*(
sizeof(T)));
3230 pcurr[0] = (T)(pos-1);
3235 *buf = (T)((*buf & 7) + (end << 3));
3288 T end = (T)(*buf >> 3);
3292 T* pcurr = buf + curr;
3293 T* pprev = pcurr - 1;
3294 T* pend = buf + end;
3303 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
3309 pprev = buf + 1; pcurr = pprev + 1;
3314 if (curr > 1 && ((
unsigned)(*pprev))+1 == pos)
3317 if (*pprev == *pcurr)
3325 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
3333 end += (pcurr == pend);
3338 ::memmove(pcurr+2, pcurr, (end - curr + 1)*(
sizeof(T)));
3340 pcurr[0] = (T)(pos-1);
3345 *buf = (T)((*buf & 7) + (end << 3));
3365 T end = (T)(*buf >> 3);
3367 T* pcurr = buf + end;
3369 T* pprev = pcurr - 1;
3378 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
3384 pprev = buf + 1; pcurr = pprev + 1;
3386 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
3389 else if (((
unsigned)(*pprev))+1 == pos && (curr > 1) )
3392 if (*pprev == *pcurr)
3398 else if (*pcurr == pos)
3401 end += (pcurr == pend);
3405 pcurr[0] = (T)(pos-1);
3411 *buf = (T)((*buf & 7) + (end << 3));
3417#pragma GCC diagnostic pop
3437 bool co, gap_set_flag;
3438 unsigned len = (*buf >> 3);
3441 unsigned bitval = *buf & 1;
3442 gap_set_flag = (bitval != co_flag);
3448 for (; i < len; ++i)
3458 *buf = (T)((*buf & 7) + (len << 3));
3490 bool co, gap_set_flag;
3495 gap_set_flag = (val != is_set);
3496 unsigned len = (*buf >> 3);
3506 for (; i < len; ++i)
3516 *buf = (T)((*buf & 7) + (len << 3));
3550 unsigned bitval = *buf & 1;
3560 BM_ASSERT(bitval ==
unsigned(*buf & 1u));
3572 unsigned len = (*buf >> 3);
3574 for (; i < len; ++i)
3603 *buf = (T)((*buf & 6u) + (1u << 3));
3611 *pcurr = (T)(curr - 1);
3621 for (i = 1; i < len; ++i)
3624 if (curr == prev + 1)
3633 *pcurr++ = (T)(curr-1);
3644 unsigned gap_len = unsigned(pcurr - buf);
3645 BM_ASSERT(gap_len == ((gap_len << 3) >> 3));
3647 *buf = (T)((*buf & 7) + (gap_len << 3));
3664 unsigned gap_count = 1;
3668 for (
unsigned i = 1; i < len; ++i)
3671 if (curr != prev + 1)
3708 unsigned val = buf[gap_idx] + 1;
3726 dest[nword] |= unsigned(1u << nbit);
3739 dest[nword] &= ~(unsigned(1u << nbit));
3753 return (block[nword] >> nbit) & 1u;
3773 *dest |= (1u << bitpos);
3777 const unsigned maskFF = ~0u;
3780 unsigned mask_r = maskFF << bitpos;
3781 if (
unsigned right_margin = bitpos + bitcount; right_margin < 32)
3783 *dest |= (maskFF >> (32 - right_margin)) & mask_r;
3787 bitcount -= 32 - bitpos;
3789 for ( ;bitcount >= 64; bitcount-=64, dest+=2)
3790 dest[0] = dest[1] = maskFF;
3793 *dest++ = maskFF; bitcount -= 32;
3797 *dest |= maskFF >> (32 - bitcount);
3819 *dest &= ~(bitcount << bitpos);
3822 const unsigned maskFF = ~0u;
3825 unsigned mask_r = maskFF << bitpos;
3826 if (
unsigned right_margin = bitpos + bitcount; right_margin < 32)
3828 *dest &= ~((maskFF >> (32 - right_margin)) & mask_r);
3832 bitcount -= 32 - bitpos;
3834 for ( ;bitcount >= 64; bitcount-=64, dest+=2)
3835 dest[0] = dest[1] = 0u;
3838 *dest++ = 0u; bitcount -= 32;
3841 *dest &= ~(maskFF >> (32 - bitcount));
3866 *word ^= unsigned(1 << nbit);
3872 unsigned right_margin = nbit + bitcount;
3877 if (right_margin < 32)
3881 unsigned mask = mask_r & mask_l;
3886 bitcount -= 32 - nbit;
3889 for ( ;bitcount >= 64; bitcount-=64, word+=2)
3891 word[0] ^= ~0u; word[1] ^= ~0u;
3895 *word++ ^= ~0u; bitcount -= 32;
3917 const T* pend = pcurr + (*pcurr >> 3);
3923 for (pcurr += 2; pcurr <= pend; pcurr += 2)
3949 const unsigned len = (*pcurr >> 3);
3968 unsigned found_pos =
bm::gap_bfind(pbuf, start_pos, &is_set);
3971 found_pos += !is_set;
3972 pcurr = pbuf + found_pos;
3974 BM_ASSERT (pcurr > pend || *pcurr >= start_pos);
3978 for (; pcurr <= pend; pcurr += 2)
3979 if (*pcurr >= start_pos)
3987 for (T prev; pcurr <= pend; pcurr += 2)
3991 unsigned pos = 1u + prev;
4016 const T* pend = pcurr + (*pcurr >> 3);
4022 for (pcurr += 2; pcurr <= pend; pcurr += 2)
4044 const T* pend = pcurr + len;
4055 for (; pcurr <= pend; )
4058 pos = 1u + pcurr[-1];
4059 bc = *pcurr - pcurr[-1];
4077 unsigned len = (*pcurr >> 3);
4095 const T* pend = pcurr + (*pcurr >> 3);
4105 for (; pcurr <= pend; )
4108 pos = 1u + pcurr[-1];
4109 bc = *pcurr - pcurr[-1];
4134 const unsigned len = (*pcurr >> 3);
4153 unsigned found_pos =
bm::gap_bfind(pbuf, start_pos, &is_set);
4156 found_pos += is_set;
4157 pcurr = pbuf + found_pos;
4159 BM_ASSERT (pcurr > pend || *pcurr >= start_pos);
4163 for (; pcurr <= pend; pcurr += 2)
4164 if (*pcurr >= start_pos)
4173 for (T prev; pcurr <= pend; pcurr += 2)
4177 unsigned pos = 1u + prev;
4202 const T* pend = pcurr + (*pcurr >> 3);
4209 for (pcurr +=2 ;pcurr <= pend; pcurr += 2)
4231 const T* pend = pcurr + (*pcurr >> 3);
4238 for (pcurr +=2 ;!count && pcurr <= pend; pcurr += 2)
4261 const T* pcurr = buf;
4262 const T* pend = pcurr + (*pcurr >> 3);
4274 for (;pcurr <= pend; pcurr+=2)
4296 const T* pcurr = buf;
4297 const T* pend = pcurr + (*pcurr >> 3);
4311 for (; !count && pcurr <= pend; pcurr+=2)
4334 const T* pcurr = buf;
4335 const T* pend = pcurr + (*pcurr >> 3);
4338 unsigned bitval = *buf & 1;
4343 count = *pcurr + 1 - count;
4346 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
4348 T prev = (T)(*(pcurr-1)+1);
4352 c = (*pcurr - prev + 1) - c;
4372 const T* pcurr = buf;
4373 const T* pend = pcurr + (*pcurr >> 3);
4376 unsigned bitval = *buf & 1;
4380 count = *pcurr + 1 - count;
4382 for (bitval^=1, ++pcurr; !count && pcurr <= pend; bitval^=1, ++pcurr)
4384 T prev = (T)(*(pcurr-1)+1);
4388 c = (*pcurr - prev + 1) - c;
4409 const T* pcurr = buf;
4410 const T* pend = pcurr + (*pcurr >> 3);
4413 unsigned bitval = *buf & 1;
4415 bm::id_t count = bitval ? *pcurr + 1
4417 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
4419 T prev = (T)(*(pcurr-1)+1);
4421 bitval ? (*pcurr - prev + 1)
4504 if (buf[1] == set_max - 1)
4523 unsigned end = *buf >> 3;
4525 const T* pcurr = buf;
4526 const T* pend = pcurr + (*pcurr >> 3);
4534 while (pcurr <= pend)
4555 *buf = (T)((*buf & 6u) + (1u << 3) + value);
4556 *(++buf) = (T)(set_max - 1);
4581 if (to == set_max - 1)
4589 buf[2] = (T)(set_max - 1);
4590 buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
4597 if (to == set_max - 1)
4600 buf[1] = (T)(from - 1);
4601 buf[2] = (T)(set_max - 1);
4606 buf[1] = (T) (from - 1);
4608 buf[3] = (T)(set_max - 1);
4610 buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
4627#pragma GCC diagnostic push
4628#pragma GCC diagnostic ignored "-Wconversion"
4644 *buf = (T)(((level & 3) << 1) | (*buf & 1) | (*buf & ~7));
4647#pragma GCC diagnostic pop
4663 if (len <=
unsigned(glevel_len[0]-4))
return 0;
4664 if (len <=
unsigned(glevel_len[1]-4))
return 1;
4665 if (len <=
unsigned(glevel_len[2]-4))
return 2;
4666 if (len <=
unsigned(glevel_len[3]-4))
return 3;
4687 return capacity - len;
4703 const T* pend1 = buf1 + len;
4710 return (w1 & diff & -diff) ? 1 : -1;
4711 }
while (buf1 < pend1);
4730#ifdef VECT_BIT_FIND_DIFF
4750 *pos = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::wordop_t))));
4762 *pos = unsigned(idx + (i * 8u *
sizeof(
bm::word_t)));
4793 unsigned bitval = (*block) & 1u;
4796 unsigned bit_idx = 0;
4800 unsigned val = *block;
4801 while (!val || val == ~0u)
4803 if (bitval !=
unsigned(
bool(val)))
4807 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4810 bit_idx += unsigned(
sizeof(*block) * 8);
4811 if (++block >= block_end)
4818 unsigned bits_consumed = 0;
4822 if (bitval != (val & 1u))
4826 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4836 bits_consumed += tz;
4842 if (bits_consumed < 32u)
4846 bit_idx += 32u - bits_consumed;
4847 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4854 }
while(++block < block_end);
4858 unsigned len = (unsigned)(pcurr - dest);
4859 *dest = (
gap_word_t)((*dest & 7) + (len << 3));
4874#if defined(VECT_BIT_TO_GAP)
4886template<
class T,
class F>
4889 const T* pcurr = buf;
4890 const T* pend = pcurr + (*pcurr >> 3);
4900 unsigned to = *pcurr;
4901 for (
unsigned i = 0; i <= to; ++i)
4914 while (pcurr <= pend)
4916 unsigned from = *(pcurr-1)+1;
4917 unsigned to = *pcurr;
4920 func(from - prev + first_inc);
4928 for (
unsigned i = from+1; i <= to; ++i)
4941template<
typename D,
typename T>
4948 const T* pend = pcurr + (*pcurr >> 3);
4953 int bitval = (*buf) & 1;
4959 if (
unsigned(*pcurr + 1) >= dest_len)
4972 while (pcurr <= pend)
4974 unsigned pending = *pcurr - *(pcurr-1);
4975 if (pending >= dest_len)
4977 dest_len -= pending;
4978 T from = (T)(*(pcurr-1)+1);
4980 for (T i = from; ;++i)
4987 return (D) (dest_curr - dest);
5009 #if defined(BM_USE_GCC_BUILD)
5010 count += unsigned(__builtin_popcountll(x) + __builtin_popcountll(y)
5011 + __builtin_popcountll(u) + __builtin_popcountll(v));
5023 }
while (block < block_end);
5034 }
while (block < block_end);
5073#ifdef VECT_BIT_COUNT_DIGEST
5096 #if defined(BM_USE_GCC_BUILD)
5097 count += unsigned(__builtin_popcountll(x) + __builtin_popcountll(y)
5098 + __builtin_popcountll(u) + __builtin_popcountll(v));
5123 }
while (blk < blk_end);
5151 count -= (w >> ((
sizeof(w) * 8) - 1));
5164 unsigned gap_count = 1;
5169 const int w_shift = int(
sizeof(w) * 8 - 1);
5172 gap_count -= (w_prev = (w0 >> w_shift));
5175 for (++block; block < block_end; ++block)
5181 gap_count -= !w_prev;
5189 gap_count -= (w0 >> w_shift);
5190 gap_count -= !(w_prev ^ w_l);
5192 w_prev = (w0 >> w_shift);
5206 unsigned gap_count = 1;
5212 const int w_shift = int(
sizeof(w) * 8 - 1);
5215 gap_count -= unsigned(w_prev = (w0 >> w_shift));
5217 const bm::id64_t* block_end = block + (size/2);
5218 for (++block; block < block_end; ++block)
5224 gap_count -= !w_prev;
5232 gap_count -= unsigned(w0 >> w_shift);
5233 gap_count -= !(w_prev ^ w_l);
5234 w_prev = (w0 >> w_shift);
5258 #ifdef VECT_BLOCK_CHANGE_BC
5285#if defined(VECT_BLOCK_CHANGE)
5308 unsigned nword, nbit, bitcount, temp;
5313 return (*word >> nbit) & 1u;
5317 unsigned right_margin = nbit + right - left;
5318 if (right_margin < 32)
5322 unsigned mask = mask_r & mask_l;
5323 return mask == (*word & mask);
5327 temp = *word & mask_r;
5330 bitcount = (right - left + 1u) - (32 - nbit);
5335 bitcount = right - left + 1u;
5342 #if defined(BM64OPT) || defined(BM64_SSE4) || defined(BMAVX2OPT) || defined(BMAVX512OPT)
5344 for ( ;bitcount >= 128; bitcount-=128, word+=4)
5348 if ((w64_0 ^ maskFF64) | (w64_1 ^ maskFF64))
5352 for ( ;bitcount >= 128; bitcount-=128, word+=4)
5354 bm::word_t m = (word[0] != maskFF) || (word[1] != maskFF) |
5355 (word[2] != maskFF) || (word[3] != maskFF);
5361 for ( ;bitcount >= 32; bitcount-=32, ++word)
5363 if (*word != maskFF)
5370 temp = *word & mask_l;
5389template<
bool LWA,
bool RWA>
5397 unsigned nword, nbit, bitcount, count, right_margin;
5401 return (*block >> nbit) & 1u;
5403 bitcount = 1u + (right_margin = (right - left));
5412 right_margin += nbit;
5414 if (right_margin < 32)
5420 bitcount -= 32 - nbit;
5427 #if defined(BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
5428 for ( ;bitcount >= 128; bitcount-=128)
5433 count += unsigned(_mm_popcnt_u64(w64_0));
5434 count += unsigned(_mm_popcnt_u64(w64_1));
5437 for ( ;bitcount >= 64; bitcount-=64)
5440 count += unsigned(_mm_popcnt_u64(w64));
5449 for ( ;bitcount >= 32; bitcount-=32)
5484 unsigned bitcount = right + 1;
5487 #if defined(BMAVX2OPT) || defined(BMAVX512OPT)
5490 __m256i cnt = _mm256_setzero_si256();
5493 for ( ;bitcount >= 256; bitcount -= 256)
5495 const __m256i* src = (__m256i*)block;
5496 __m256i xmm256 = _mm256_load_si256(src);
5498 cnt = _mm256_add_epi64(cnt, bc);
5503 count += (unsigned)(cnt64[0] + cnt64[1] + cnt64[2] + cnt64[3]);
5506 for ( ;bitcount >= 64; bitcount -= 64)
5538 block[i] = (block[i] << 1) | (block[i + 1] >> 31);
5552 const unsigned unroll_factor = 4;
5558 w0 = block[i + 1] >> 31;
5559 w1 = block[i + 2] >> 31;
5560 w2 = block[i + 3] >> 31;
5561 w3 = block[i + 4] >> 31;
5563 block[0 + i] = (block[0 + i] << 1) | w0;
5564 block[1 + i] = (block[1 + i] << 1) | w1;
5565 block[2 + i] = (block[2 + i] << 1) | w2;
5566 block[3 + i] = (block[3 + i] << 1) | w3;
5568 block[i] = (block[i] << 1) | (block[i + 1] >> 31);
5569 block[i + 1] = (block[i + 1] << 1) | (block[i + 2] >> 31);
5570 block[i + 2] = (block[i + 2] << 1) | (block[i + 3] >> 31);
5603 block[nword] = w | (unsigned(value) << nbit) | wl;
5615 w = (w << 1u) | co_flag;
5646 acc |= w = (w << 1u) | co_flag;
5682 acc0 |= w = (w << 1u) | co_flag;
5688 acc1 |= w = (w << 1u) | co_flag;
5693 *empty_acc = bool(acc0 | acc1);
5717 #if defined(VECT_SHIFT_R1)
5747 acc |= w = (w >> 1u) | (co_flag << 31u);
5775 w0 = block[i]; w1 = block[i-1];
5777 acc |= w0 = (w0 >> 1u) | (co_flag << 31u);
5781 acc |= w1 = (w1 >> 1u) | (co_flag << 31u);
5786 w0 = block[i]; w1 = block[i-1];
5788 acc |= w0 = (w0 >> 1u) | (co_flag << 31u);
5792 acc |= w1 = (w1 >> 1u) | (co_flag << 31u);
5817 #if defined(VECT_SHIFT_L1)
5857 w = (w >> 1u) | (co_flag << 31u);
5869 w |= wl | (co_flag << 31u);
5874 block[nword] = (block[nword] >> 1u) | (co_flag << 31u);
5909 for (; di < 64; ++di)
5922 w = (w << 1u) | co_flag;
5923 acc |= block[i] = w & mask_block[i];
5939 block[d_base] = co_flag & mask_block[d_base];
5971 #if defined(VECT_SHIFT_R1_AND)
5993 unsigned nbit = left;
6001 return (*word >> nbit) & 1;
6004 unsigned bitcount = right - left + 1;
6008 unsigned right_margin = nbit + (right - left);
6009 if (right_margin < 32)
6013 unsigned mask = mask_r & mask_l;
6014 return *word & mask;
6019 acc = *word & mask_r;
6022 bitcount -= 32 - nbit;
6030 for ( ;bitcount >= 128; bitcount-=128, word+=4)
6032 acc = word[0] | word[1] | word[2] | word[3];
6038 for ( ;bitcount >= 32; bitcount -= 32)
6046 acc |= (*word) & mask_l;
6066 start[0] = ~start[0];
6067 start[1] = ~start[1];
6068 start[2] = ~start[2];
6069 start[3] = ~start[3];
6071 }
while (start < end);
6083#if defined(VECT_IS_ONE_BLOCK)
6091 start[0] & start[1] & start[2] & start[3];
6095 }
while (start < end);
6136 bool is_left, is_right, all_one;
6149 if (is_left ==
false)
6153 if (is_right ==
false)
6186 w &= (1u << bit_pos);
6201 w = (~block[nword]) >> bit_pos;
6206 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))-1);
6216 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))-1);
6282 w &= (1u << bit_pos);
6298 w = (~block[nword]) & mask_l;
6302 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))+1);
6308 for (--nword;
true; --nword)
6314 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))+1);
6346 w &= (1u << bit_pos);
6349 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
6361 w = block[nword] & mask_l;
6365 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
6371 for (--nword;
true; --nword)
6378 unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
6407 if (b && *found_nbit == 0)
6418 if (b && *found_nbit == 0)
6446 *found_nbit = nbit_from;
6524 tmp_buf, vect1, 0, vect2, 0, dsize);
6591 tmp_buf, vect1, 0, vect2, 0, dsize);
6718 tmp_buf, vect1, 0, vect2, 1, dsize);
6743 vect1, 0, vect2, 1);
6798#ifdef VECT_COPY_BLOCK_UNALIGN
6819#ifdef VECT_STREAM_BLOCK
6837#ifdef VECT_STREAM_BLOCK_UNALIGN
6872 for (
unsigned i = 0; i < arr_sz; i+=4)
6874 acc |= (dst_u->w64[i] &= src_u->w64[i]) |
6875 (dst_u->w64[i+1] &= src_u->w64[i+1]) |
6876 (dst_u->w64[i+2] &= src_u->w64[i+2]) |
6877 (dst_u->w64[i+3] &= src_u->w64[i+3]);
6913 #if defined(VECT_AND_DIGEST)
6916 digest &= ~(mask << wave);
6925 acc |= dst_u->w64[j+0] &= src_u->w64[j+0];
6926 acc |= dst_u->w64[j+1] &= src_u->w64[j+1];
6927 acc |= dst_u->w64[j+2] &= src_u->w64[j+2];
6928 acc |= dst_u->w64[j+3] &= src_u->w64[j+3];
6933 digest &= ~(mask << wave);
6957 BM_ASSERT(src0 && src1 && src2 && src3);
6968#if defined(VECT_AND_DIGEST_5WAY)
6969 bool all_zero =
VECT_AND_DIGEST_5WAY(&dst[off], &src0[off], &src1[off], &src2[off], &src3[off]);
6971 digest &= ~(mask << wave);
6983 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];
6984 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];
6985 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];
6986 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];
6990 digest &= ~(mask << wave);
7030 #if defined(VECT_AND_DIGEST_3WAY)
7033 digest &= ~(mask << wave);
7044 acc |= dst_u->w64[j] &= src_u1->w64[j] & src_u2->w64[j];
7045 acc |= dst_u->w64[j+1] &= src_u1->w64[j+1] & src_u2->w64[j+1];
7046 acc |= dst_u->w64[j+2] &= src_u1->w64[j+2] & src_u2->w64[j+2];
7047 acc |= dst_u->w64[j+3] &= src_u1->w64[j+3] & src_u2->w64[j+3];
7052 digest &= ~(mask << wave);
7095 #if defined(VECT_AND_DIGEST_2WAY)
7098 digest &= ~(mask << wave);
7109 acc |= dst_u->w64[j] = src_u1->w64[j] & src_u2->w64[j];
7110 acc |= dst_u->w64[j+1] = src_u1->w64[j+1] & src_u2->w64[j+1];
7111 acc |= dst_u->w64[j+2] = src_u1->w64[j+2] & src_u2->w64[j+2];
7112 acc |= dst_u->w64[j+3] = src_u1->w64[j+3] & src_u2->w64[j+3];
7117 digest &= ~(mask << wave);
7147 for (
unsigned i = 0; i < 64; ++i)
7152 #if defined(VECT_AND_DIGEST_2WAY)
7167 acc |= dst_u->w64[j] = src_u1->w64[j] & src_u2->w64[j];
7168 acc |= dst_u->w64[j+1] = src_u1->w64[j+1] & src_u2->w64[j+1];
7169 acc |= dst_u->w64[j+2] = src_u1->w64[j+2] & src_u2->w64[j+2];
7170 acc |= dst_u->w64[j+3] = src_u1->w64[j+3] & src_u2->w64[j+3];
7181 #if defined(VECT_BLOCK_SET_DIGEST)
7186 dst[off] = dst[off+1] = dst[off+2] = dst[off+3] = 0u;
7228 #if defined(VECT_AND_OR_DIGEST_2WAY)
7232 digest &= ~(mask << wave);
7245 acc |= dst_u->w64[j+0] |= src_u1->w64[j+0] & src_u2->w64[j+0];
7246 acc |= dst_u->w64[j+1] |= src_u1->w64[j+1] & src_u2->w64[j+1];
7247 acc |= dst_u->w64[j+2] |= src_u1->w64[j+2] & src_u2->w64[j+2];
7248 acc |= dst_u->w64[j+3] |= src_u1->w64[j+3] & src_u2->w64[j+3];
7253 digest &= ~(mask << wave);
7294 }
while (b1 < b1_end);
7304 }
while (src1 < src1_end);
7328 count = (src1[0] & src2[0]) |
7329 (src1[1] & src2[1]) |
7330 (src1[2] & src2[2]) |
7331 (src1[3] & src2[3]);
7333 }
while ((src1 < src1_end) && !count);
7371 }
while (b1 < b1_end);
7381 }
while (src1 < src1_end);
7405 count = (src1[0] ^ src2[0]) |
7406 (src1[1] ^ src2[1]) |
7407 (src1[2] ^ src2[2]) |
7408 (src1[3] ^ src2[3]);
7410 }
while (!count && (src1 < src1_end));
7444 }
while (b1 < b1_end);
7454 }
while (src1 < src1_end);
7478 count = (src1[0] & ~src2[0]) |
7479 (src1[1] & ~src2[1]) |
7480 (src1[2] & ~src2[2]) |
7481 (src1[3] & ~src2[3]);
7483 }
while ((src1 < src1_end) && (count == 0));
7519 }
while (b1 < b1_end);
7529 }
while (src1 < src1_end);
7552 count = (src1[0] | src2[0]) |
7553 (src1[1] | src2[1]) |
7554 (src1[2] | src2[2]) |
7555 (src1[3] | src2[3]);
7558 }
while (!count && (src1 < src1_end));
7850 acc &= (dst_ptr[0] |= wrd_ptr[0]);
7851 acc &= (dst_ptr[1] |= wrd_ptr[1]);
7852 acc &= (dst_ptr[2] |= wrd_ptr[2]);
7853 acc &= (dst_ptr[3] |= wrd_ptr[3]);
7855 dst_ptr+=4;wrd_ptr+=4;
7857 }
while (wrd_ptr < wrd_end);
7858 return acc == not_acc;
7888 acc &= (dst_ptr[0] = wrd_ptr1[0] | wrd_ptr2[0]);
7889 acc &= (dst_ptr[1] = wrd_ptr1[1] | wrd_ptr2[1]);
7890 acc &= (dst_ptr[2] = wrd_ptr1[2] | wrd_ptr2[2]);
7891 acc &= (dst_ptr[3] = wrd_ptr1[3] | wrd_ptr2[3]);
7893 dst_ptr+=4; wrd_ptr1+=4; wrd_ptr2+=4;
7895 }
while (wrd_ptr1 < wrd_end1);
7896 return acc == not_acc;
7926 acc |= (dst_ptr[0] = wrd_ptr1[0] ^ wrd_ptr2[0]);
7927 acc |= (dst_ptr[1] = wrd_ptr1[1] ^ wrd_ptr2[1]);
7928 acc |= (dst_ptr[2] = wrd_ptr1[2] ^ wrd_ptr2[2]);
7929 acc |= (dst_ptr[3] = wrd_ptr1[3] ^ wrd_ptr2[3]);
7931 dst_ptr+=4; wrd_ptr1+=4; wrd_ptr2+=4;
7933 }
while (wrd_ptr1 < wrd_end1);
7968 acc &= (dst_ptr[0] |= wrd_ptr1[0] | wrd_ptr2[0]);
7969 acc &= (dst_ptr[1] |= wrd_ptr1[1] | wrd_ptr2[1]);
7970 acc &= (dst_ptr[2] |= wrd_ptr1[2] | wrd_ptr2[2]);
7971 acc &= (dst_ptr[3] |= wrd_ptr1[3] | wrd_ptr2[3]);
7973 dst_ptr+=4; wrd_ptr1+=4;wrd_ptr2+=4;
7975 }
while (wrd_ptr1 < wrd_end1);
7976 return acc == not_acc;
8016 acc &= (dst_ptr[0] |= wrd_ptr1[0] | wrd_ptr2[0] | wrd_ptr3[0] | wrd_ptr4[0]);
8017 acc &= (dst_ptr[1] |= wrd_ptr1[1] | wrd_ptr2[1] | wrd_ptr3[1] | wrd_ptr4[1]);
8018 acc &= (dst_ptr[2] |= wrd_ptr1[2] | wrd_ptr2[2] | wrd_ptr3[2] | wrd_ptr4[2]);
8019 acc &= (dst_ptr[3] |= wrd_ptr1[3] | wrd_ptr2[3] | wrd_ptr3[3] | wrd_ptr4[3]);
8022 wrd_ptr1+=4;wrd_ptr2+=4;wrd_ptr3+=4;wrd_ptr4+=4;
8024 }
while (wrd_ptr1 < wrd_end1);
8025 return acc == not_acc;
8118 for (
unsigned i = 0; i < arr_sz; i+=4)
8120 acc |= (dst_u->w64[i] &= ~src_u->w64[i]) |
8121 (dst_u->w64[i+1] &= ~src_u->w64[i+1]) |
8122 (dst_u->w64[i+2] &= ~src_u->w64[i+2]) |
8123 (dst_u->w64[i+3] &= ~src_u->w64[i+3]);
8160 #if defined(VECT_SUB_DIGEST)
8163 digest &= ~(mask << wave);
8172 acc |= dst_u->w64[j+0] &= ~src_u->w64[j+0];
8173 acc |= dst_u->w64[j+1] &= ~src_u->w64[j+1];
8174 acc |= dst_u->w64[j+2] &= ~src_u->w64[j+2];
8175 acc |= dst_u->w64[j+3] &= ~src_u->w64[j+3];
8180 digest &= ~(mask << wave);
8221 #if defined(VECT_SUB_DIGEST_2WAY)
8224 digest &= ~(mask << wave);
8237 acc |= dst_u->w64[j+0] = src_u1->w64[j+0] & ~src_u2->w64[j+0];
8238 acc |= dst_u->w64[j+1] = src_u1->w64[j+1] & ~src_u2->w64[j+1];
8239 acc |= dst_u->w64[j+2] = src_u1->w64[j+2] & ~src_u2->w64[j+2];
8240 acc |= dst_u->w64[j+3] = src_u1->w64[j+3] & ~src_u2->w64[j+3];
8245 digest &= ~(mask << wave);
8267 BM_ASSERT(src0 && src1 && src2 && src3);
8279#if defined(VECT_SUB_DIGEST_5WAY)
8280 bool all_zero =
VECT_SUB_DIGEST_5WAY(&dst[off], &src0[off], &src1[off], &src2[off], &src3[off]);
8282 digest &= ~(mask << wave);
8294 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];
8295 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];
8296 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];
8297 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];
8302 digest &= ~(mask << wave);
8334#if defined(VECT_SUB_DIGEST_3WAY)
8337 digest &= ~(mask << wave);
8347 acc |= dst_u->w64[j + 0] &= ~src_u0->w64[j + 0] & ~src_u1->w64[j + 0];
8348 acc |= dst_u->w64[j + 1] &= ~src_u0->w64[j + 1] & ~src_u1->w64[j + 1];
8349 acc |= dst_u->w64[j + 2] &= ~src_u0->w64[j + 2] & ~src_u1->w64[j + 2];
8350 acc |= dst_u->w64[j + 3] &= ~src_u0->w64[j + 3] & ~src_u1->w64[j + 3];
8355 digest &= ~(mask << wave);
8450 for (
unsigned i = 0; i < arr_sz; i+=4)
8452 acc |= dst_u->w64[i] ^= src_u->w64[i];
8453 acc |= dst_u->w64[i+1] ^= src_u->w64[i+1];
8454 acc |= dst_u->w64[i+2] ^= src_u->w64[i+2];
8455 acc |= dst_u->w64[i+3] ^= src_u->w64[i+3];
8487 dst_ptr+=4; wrd_ptr+=4;
8488 }
while (wrd_ptr < wrd_end);
8509 if (src == dst)
return 0;
8515 if (!src)
return dst;
8521 if (!src)
return dst;
8605 const T* blk_end = blk + data_size - 2;
8610 const T* blk_j = blk + 1;
8611 for (; blk_j < blk_end; ++blk_j)
8621 const T* blk_j = blk + 1;
8622 for ( ; blk_j < blk_end; ++blk_j)
8626 if (blk_j[1] | blk_j[2])
8636 count += unsigned(blk_j - blk) * unsigned(
sizeof(T));
8641 while(blk < blk_end);
8642 return count + unsigned(2 *
sizeof(T));
8667 w &= (1u << bit_pos);
8673 w = block[nword] >> bit_pos;
8678 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
8688 *pos = unsigned(bit_pos + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
8722 *last = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
8748#ifdef VECT_BIT_FIND_FIRST
8757 *pos = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
8789#ifdef VECT_BIT_FIND_FIRST
8797 unsigned base = i * 8u * unsigned(
sizeof(
bm::word_t));
8807 w64 = block[i] | block[i+1];
8810 unsigned base = i * 8u * unsigned(
sizeof(
bm::word_t));
8850#if defined(BMSSE42OPT) || defined(BMAVX2OPT) || defined(BMAVX512OPT)
8853 __m128i wA = _mm_load_si128((__m128i*)&block[i]);
8854 if (_mm_test_all_zeros(wA, wA))
8856 const unsigned cnt = i + 4;
8865 for (++i; i < cnt; ++i)
8872 }
while (++i < cnt);
8876 wA = _mm_load_si128((__m128i*)&block[i]);
8877 if (!_mm_test_all_zeros(wA, wA))
8885 if (
auto w = block[i])
8915template<
typename SIZE_TYPE>
8927 unsigned pos = nbit_from;
8937 rank -= bc; pos += unsigned(32u - nbit);
8943 nbit_pos = pos + idx;
8948 #if defined(BM64OPT) || defined(BM64_SSE4) || defined(BMAVX2OPT) || defined(BMAVX512OPT)
8958 nbit_pos = pos + idx;
8973 rank -= bc; pos += 32u;
8977 nbit_pos = pos + idx;
8996template<
typename SIZE_TYPE>
9022 unsigned total_possible_bitcount,
9030 if ((gap_size < block_size) && (gap_size < arr_size) && (gap_size < inv_arr_size))
9035 if (arr_size < inv_arr_size)
9037 if ((arr_size < block_size) && (arr_size < gap_size))
9044 if ((inv_arr_size < block_size) && (inv_arr_size < gap_size))
9071 src+=2, bit_idx += unsigned(
sizeof(*src) * 8 * 2))
9082 return (
unsigned)(pcurr - dest);
9098 if (!blk)
return true;
9122 if (blk == 0)
return false;
9144 const T* length_end,
9147 BM_ASSERT(length && length_end && glevel_len);
9149 unsigned overhead = 0;
9150 for (;length < length_end; ++length)
9152 unsigned len = *length;
9155 unsigned capacity = glevel_len[level];
9157 overhead += capacity - len;
9171 const T* length_end,
9174 BM_ASSERT(length && length_end && glevel_len);
9176 size_t lsize = size_t(length_end - length);
9182 for (i = 0; i < lsize; ++i)
9184 if (length[i] > max_len)
9185 max_len = length[i];
9189 glevel_len[0] = T(max_len + 4);
9199 unsigned min_overhead =
gap_overhead(length, length_end, glevel_len);
9200 bool is_improved =
false;
9206 unsigned opt_len = 0;
9208 bool imp_flag =
false;
9210 for (j = 0; j < lsize; ++j)
9212 glevel_len[i] = T(length[j] + 4);
9213 unsigned ov =
gap_overhead(length, length_end, glevel_len);
9214 if (ov <= min_overhead)
9217 opt_len = length[j]+4;
9223 glevel_len[i] = (T)opt_len;
9228 glevel_len[i] = gap_saved_value;
9236 T val = *glevel_len;
9238 T* res = glevel_len;
9275 if (!blk || !arg_blk)
9418 if (cnt_ < from_ || cnt_ > to_)
9423 return decoder_.get_32();
9438template<
class It1,
class It2,
class BinaryOp,
class Encoder>
9444 for (
unsigned i = 0; i < block_size; ++i)
9641 w0 = w_ptr[0]; w1 = w_ptr[1];
9643#if defined(BMAVX512OPT) || defined(BMAVX2OPT) || defined(BM64OPT) || defined(BM64_SSE4)
9648 w0 = w_ptr[2]; w1 = w_ptr[3];
9652 #if (defined(__arm__) || defined(__aarch64__))
9656 w0 = w_ptr[2]; w1 = w_ptr[3];
9664 w0 = w_ptr[2]; w1 = w_ptr[3];
9669 return static_cast<unsigned short>(cnt0);
9672#if defined (BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
9682 unsigned size,
unsigned start,
9685typedef unsigned TRGW;
9686typedef unsigned IDX;
9687#if defined(BM64_SSE4)
9690 if constexpr (
sizeof(TRGW)==4 &&
sizeof(IDX)==4)
9695#elif defined(BM64_AVX2) || defined(BM64_AVX512)
9696 if constexpr (
sizeof(TRGW)==4 &&
sizeof(IDX)==4)
9712template<
typename TRGW,
typename IDX,
typename SZ>
9716 SZ size, SZ start,
unsigned bit_idx)
BMNOEXCEPT
9721 const SZ len = (size - start);
9722 const SZ len_unr = len - (len % 2);
9724 for (; k < len_unr; k+=2)
9726 const SZ base = start + k;
9734 for (; k < len; ++k)
9762 for (;(start < size) &&
9782 unsigned size,
unsigned nb,
unsigned start)
BMNOEXCEPT
9787#if defined(VECT_ARR_BLOCK_LOOKUP)
9790 for (;(start < size) &&
9825 block[nword] |= (1u << nbit);
9849#if defined(VECT_SET_BLOCK_BITS)
9854 unsigned n = idx[start++];
9858 block[nword] |= (1u << nbit);
9859 }
while (start < stop);
9911#if defined(VECT_LOWER_BOUND_SCAN_U32)
9914 for (; from <= to; ++from)
9916 if (arr[from] >= target)
9929 unsigned long long target,
9936 for (; from <= to; ++from)
9938 if (arr[from] >= target)
9958 const unsigned linear_cutoff = 32;
9960 unsigned l = from;
unsigned r = to;
9961 unsigned dist = r - l;
9962 if (dist < linear_cutoff)
9969 unsigned mid = (r-l)/2+l;
9970 if (arr[mid] < target)
9975 if (dist < linear_cutoff)
9989 unsigned long long target,
9994 const unsigned linear_cutoff = 32;
9996 unsigned l = from;
unsigned r = to;
9997 unsigned dist = r - l;
9998 if (dist < linear_cutoff)
10005 unsigned mid = (r - l) / 2 + l;
10006 if (arr[mid] < target)
10011 if (dist < linear_cutoff)
10029 for (
size_t i = 0; i < arr_size; ++i)
10030 if (ptr == p_arr[i])
10032 *idx = i;
return true;
10050 return block_idx + base_idx;
10059 return block_idx + base_idx;
10073 unsigned md = arr[1] - arr[0];
10074 for (
size_t i = 1; i < arr_size; ++i)
10076 unsigned prev = arr[i-1];
10077 unsigned curr = arr[i];
10079 unsigned delta = curr - prev;
10102 for (
size_t i = 1; i < arr_size; ++i)
10113template<
typename VT,
typename SZ>
10116 bool found =
false;
10118 for (SZ i = 0; i < arr_size; ++i)
10123 max_v = v; *found_idx = i;
10134template<
typename VT,
typename SZ>
10137 for (SZ i = 0; i < arr_size; ++i)
10153template<
typename VT,
typename SZ>
10157 for (SZ i = 0; i < arr_size; ++i)
10158 cnt += (arr[i] != 0);
10194 float bie_bits_per_int,
10202 if (bc == max_bits)
10208 unsigned ibc = max_bits - bc;
10214 float cost_in_bits = float(gc) * bie_bits_per_int;
10215 if (cost_in_bits >=
float(max_bits))
10225 float cost_in_bits = float(bc) * bie_bits_per_int;
10226 if (cost_in_bits >=
float(max_bits))
10231 *best_metric = ibc;
10232 float cost_in_bits = float(ibc) * bie_bits_per_int;
10233 if (cost_in_bits >=
float(max_bits))
10256 unsigned arr_idx = idx >> 1;
10259 unsigned char old_val = arr[arr_idx];
10261 arr[arr_idx] = (
unsigned char)(old_val | (v << 4));
10265 unsigned char old_val = arr[arr_idx];
10267 arr[arr_idx] = (
unsigned char)(old_val | (v & 0xF));
10283 unsigned char v = arr[idx >> 1];
10284 v >>= (idx & 1) * 4;
10314 return (ptr.i16[1] == 0);
10316 bm::id64_t r = (ptr.i16[1] == v) | (ptr.i16[2] == v) | (ptr.i16[3] == v);
#define VECT_STREAM_BLOCK_UNALIGN(dst, src)
#define VECT_COPY_BLOCK_UNALIGN(dst, src)
#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_BIT_FIND_FIRST(src1, off, pos)
#define VECT_COPY_BLOCK(dst, src)
#define VECT_SUB_DIGEST_5WAY(dst, src1, src2, src3, src4)
#define BM_AVX2_POPCNT_PROLOG
#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_GAP_TEST(buf, pos)
#define VECT_IS_ZERO_BLOCK(dst)
#define VECT_BIT_TO_GAP(dest, src, dest_len)
#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_BIT_COUNT_DIGEST(blk, d)
#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_GAP_BFIND(buf, pos, is_set)
#define VECT_INVERT_BLOCK(first)
#define VECT_BLOCK_CHANGE(block, size)
#define VECT_SUB_DIGEST_3WAY(dst, src1, src2)
#define VECT_AND_DIGEST_2WAY(dst, src1, src2)
#define VECT_AND_OR_DIGEST_2WAY(dst, src1, src2)
#define VECT_BLOCK_SET_DIGEST(dst, val)
#define VECT_AND_DIGEST_3WAY(dst, src1, src2)
#define BM_AVX2_BIT_COUNT(ret, v)
#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)
#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
Bit manipulation primitives (internal).
bitblock_get_adapter(const bm::word_t *bit_block)
BMFORCEINLINE bm::word_t get_32() BMNOEXCEPT
BMFORCEINLINE void push_back(bm::word_t w)
bitblock_store_adapter(bm::word_t *bit_block)
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
bm::word_t get_32() BMNOEXCEPT
decoder_range_adapter(DEC &dec, unsigned from_idx, unsigned to_idx)
BMFORCEINLINE bool avx2_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
BMFORCEINLINE bool sse42_test_all_zero_wave(const void *ptr) BMNOEXCEPT
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::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.
unsigned bitcount64_4way(bm::id64_t x, bm::id64_t y, bm::id64_t u, bm::id64_t v) BMNOEXCEPT
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 word_select32(unsigned w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
BMFORCEINLINE unsigned bit_count_min_unroll(const bm::word_t *BMRESTRICT block, const bm::word_t *BMRESTRICT block_end) BMNOEXCEPT
Bitcount for bit block without agressive unrolling.
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 word_select64_bitscan_tz(bm::id64_t w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
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.
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 short bitscan_bsf(unsigned w, B *bits) BMNOEXCEPT
Unpacks word into list of ON bits (BSF/__builtin_ctz).
unsigned short bitscan(V w, B *bits) BMNOEXCEPT
Templated Bitscan with dynamic dispatch for best type.
bool bit_block_shift_r1_unr_min(bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::id64_t co_flag) BMNOEXCEPT
Right bit-shift bitblock by 1 bit (minimum unroll).
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.
unsigned word_select32_bitscan_popcnt(unsigned w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
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_shift_l1_unr_min(bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, unsigned co_flag) BMNOEXCEPT
Left bit-shift bitblock by 1 bit (minimum unroll).
bm::id64_t bit_block_and_3way(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
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::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.
bool bit_block_find_prev(const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
Reverse search for the previous 1 bit.
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.
void block_expand_by_digest(bm::word_t *t_block, const bm::word_t *block, bm::id64_t digest, bool zero_subs) BMNOEXCEPT
expand sub-blocks by digest (rank expansion)
unsigned word_select64(bm::id64_t w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
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.
unsigned bit_block_convert_to_arr(T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bool inverted) BMNOEXCEPT
Convert bit block into an array of ints corresponding to 1 bits.
unsigned word_select32_bitscan_tz(unsigned w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
bm::id_t bit_block_calc_count_to(const bm::word_t *block, bm::word_t right) BMNOEXCEPT
int wordcmp(T a, T b) BMNOEXCEPT
Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and refe...
bm::id64_t bit_block_init_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 (0 elements of digest will be zeroed)
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).
unsigned word_select64_bitscan_popcnt(bm::id64_t w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
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.
void bit_block_stream_unalign(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Bitblock copy/stream operation (unaligned src).
unsigned bit_scan_reverse(T value) BMNOEXCEPT
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).
int wordcmp0(T w1, T w2) BMNOEXCEPT
Lexicographical comparison of two words as bit strings (reference) Auxiliary implementation for testi...
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.
bm::id64_t bit_block_and_or_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 - OR
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...
BMFORCEINLINE 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
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.
bm::id64_t bit_block_sub_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 SUB 5-way
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_copy_unalign(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Bitblock copy operation (unaligned src).
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...
bm::id_t bit_block_calc_count_range(const bm::word_t *block, bm::word_t left, bm::word_t right) BMNOEXCEPT
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...
unsigned word_select64_linear(bm::id64_t w, unsigned rank) BMNOEXCEPT
word find index of the rank-th bit set by bit-testing
void block_compact_by_digest(bm::word_t *t_block, const bm::word_t *block, bm::id64_t digest, bool zero_tail) BMNOEXCEPT
Compact sub-blocks by digest (rank compaction).
void bit_block_stream(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Bitblock copy/stream operation.
bm::id64_t bit_block_sub_3way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src0, const bm::word_t *BMRESTRICT src1, bm::id64_t digest) BMNOEXCEPT
digest based bit-block SUB 3-way
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...
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.
unsigned short bitscan_bsf64(bm::id64_t w, B *bits) BMNOEXCEPT
Unpacks word into list of ON bits (BSF/__builtin_ctz).
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.
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.
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.
bool gap_find_prev(const T *const BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
reverse search for the first 1 bit of a GAP block
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.
unsigned gap_buff_any_op(const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask) BMNOEXCEPT2
Abstract distance test operation for GAP buffers. Receives functor F as a template argument.
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.
unsigned gap_buff_count_op(const T *vect1, const T *vect2) BMNOEXCEPT2
Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument.
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_operation_any_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP AND operation test.
void gap_convert_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned len=0) BMNOEXCEPT
GAP block to bitblock conversion.
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.
bool gap_insert(T *BMRESTRICT buf, unsigned pos, unsigned val, unsigned *BMRESTRICT new_len) BMNOEXCEPT
isnert bit into GAP compressed block
BMFORCEINLINE unsigned gap_count_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP bitcount XOR operation test.
unsigned gap_operation_any_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
GAP SUB 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).
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.
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.
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.
unsigned gap_bit_count_range_hint(const T *const buf, unsigned left, unsigned right, unsigned hint) BMNOEXCEPT
Counts 1 bits in GAP buffer in the closed [left, right] range using position hint to avoid bfind.
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_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.
BMFORCEINLINE bm::gap_word_t gap_length(const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
Returs GAP block length.
unsigned gap_set_value_cpos(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set, unsigned curr) BMNOEXCEPT
Sets or clears bit in the GAP buffer.
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
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 find_first_nz(const VT *arr, SZ arr_size, SZ *found_idx) BMNOEXCEPT
Find max non-zero value in an array.
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.
void set_nibble(unsigned char *arr, unsigned idx, unsigned char v) BMNOEXCEPT
set nibble in the array
void min_delta_apply(unsigned *arr, size_t arr_size, unsigned delta) BMNOEXCEPT
Recalculate the array to decrement delta as arr[i] = arr[i] - delta + 1 so that array remains monoton...
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 unsigned set_block_mask
const bm::gap_word_t * avx2_gap_sum_arr(const bm::gap_word_t *pbuf, unsigned avx_vect_waves, unsigned *sum)
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 bit_scan_forward32(unsigned w) BMNOEXCEPT
bm::id64_t sum_arr(const T *first, const T *last) BMNOEXCEPT
unsigned gap_bit_count_to(const T *const buf, T right) 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
SZ count_nz(const VT *arr, SZ arr_size) BMNOEXCEPT
Find count of non-zero elements in the array.
const char _copyright< T >::_p[]
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
unsigned bit_block_change64(const bm::word_t *BMRESTRICT in_block, unsigned size) BMNOEXCEPT
void sse4_bit_block_gather_scatter(unsigned *BMRESTRICT arr, const unsigned *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx) BMNOEXCEPT
void for_each_dgap(const T *gap_buf, Func &func)
BMFORCEINLINE void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
BMFORCEINLINE unsigned mask_l_u32(unsigned nbit) 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.
BMFORCEINLINE unsigned bit_scan_reverse32(unsigned w) BMNOEXCEPT
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
unsigned char get_nibble(const unsigned char *arr, unsigned idx) BMNOEXCEPT
get nibble from the array
bool block_ptr_array_range(bm::word_t **arr, unsigned &left, unsigned &right) BMNOEXCEPT
array range detector
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)
void bit_recomb(It1 &it1, It2 &it2, BinaryOp &op, Encoder &enc, unsigned block_size=bm::set_block_size) 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
bool is_digest_one_range(bm::id64_t digest) BMNOEXCEPT
Is one range of 1s ( 0000110000 - one range, 000011000010 - more than one).
unsigned long long int id64_t
const unsigned block_waves
unsigned bit_block_change32(const bm::word_t *BMRESTRICT block, unsigned size) BMNOEXCEPT
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.
BMFORCEINLINE unsigned mask_r_u32(unsigned nbit) BMNOEXCEPT
const unsigned gap_max_buff_len
const bm::gap_word_t * sse2_gap_sum_arr(const bm::gap_word_t *BMRESTRICT pbuf, unsigned sse_vect_waves, unsigned *sum) BMNOEXCEPT
Gap block population count (array sum) utility.
int parallel_popcnt_32(unsigned int n) BMNOEXCEPT
32-bit paralle, bitcount
BMFORCEINLINE RTYPE get_super_block_start(unsigned i) BMNOEXCEPT
Compute bit address of the first bit in a superblock.
bit_representation
Possible representations for bit sets.
@ e_bit_bit
uncompressed bit-block
@ e_bit_IINT
Inverted int list.
@ e_bit_0
all 0s (empty block)
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
void gap_buff_op(T *BMRESTRICT dest, const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, unsigned &dlen) BMNOEXCEPT2
Abstract operation for GAP buffers. Receives functor F as a template argument.
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
bool find_ptr(const void *const *p_arr, size_t arr_size, const void *ptr, size_t *idx) BMNOEXCEPT
Scan search for pointer value in unordered array.
const unsigned short set_bitscan_wave_size
Size of bit decode wave in words.
bm::id64_t dm_control(unsigned from, unsigned to) BMNOEXCEPT
digest mask control generation (for debug and test only)
const unsigned set_array_shift
unsigned min_delta_u32(const unsigned *arr, size_t arr_size)
Calculate minimal delta between elements of sorted array.
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
bool find_max_nz(const VT *arr, SZ arr_size, SZ *found_idx) BMNOEXCEPT
Find max non-zero value in an array.
unsigned count_trailing_zeros_u64(bm::id64_t w) BMNOEXCEPT
64-bit bit-scan fwd
unsigned bitscan_nibble(unsigned w, unsigned *bits) BMNOEXCEPT
portable, switch based bitscan
void(* gap_operation_to_bitset_func_type)(unsigned *, const gap_word_t *)
const unsigned gap_max_bits
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
void avx2_bit_block_gather_scatter(unsigned *BMRESTRICT arr, const unsigned *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx)
const unsigned set_word_mask
bool find_not_null_ptr(const bm::word_t *const *const *arr, N start, N size, N *pos) BMNOEXCEPT
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.
bool block_find_reverse(const bm::word_t *BMRESTRICT block, unsigned nbit_from, unsigned *BMRESTRICT found_nbit) BMNOEXCEPT
Reverse find 1.
unsigned count_trailing_zeros_u32(unsigned w) BMNOEXCEPT
32-bit bit-scan fwd
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).
all_set_block() BMNOEXCEPT
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 with statistical information about memory allocation for arena based vectors.
size_t bit_blocks_sz
Total size of bit blocks.
size_t gap_blocks_sz
Total size of gap blocks.
size_t ptr_sub_blocks_sz
Total size of sub-blocks ptrs.
size_t get_alloc_size() const BMNOEXCEPT
Get allocation size in bytes.
void reset() BMNOEXCEPT
Reset statisctics.
unsigned top_block_size
size of top descriptor
size_t gap_cap_overhead
gap memory overhead between length and capacity
size_t ptr_sub_blocks
Number of sub-blocks.
bv_statistics() BMNOEXCEPT
void add_gap_block(unsigned capacity, unsigned length, unsigned level) BMNOEXCEPT
count gap block
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.
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.
static const gap_word_t _len[bm::gap_levels]
static gap_operation_func_type gapop_table_[bm::set_END]
static gap_operation_to_bitset_func_type gap2bit_table_[bm::set_END]
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 gap_operation_func_type gap_operation(unsigned i)
static bit_operation_count_func_type bit_op_count_table_[bm::set_END]
helper union to interpret pointer as integers