1#ifndef BMFUNC__H__INCLUDED__
2#define BMFUNC__H__INCLUDED__
33# pragma warning( disable: 4146 )
40template<
bool LWA=false,
bool RWA=false>
82 size_t mem_used = (capacity *
sizeof(
gap_word_t));
144template<
typename First,
typename Second>
170template<
typename BI_TYPE>
182template<
typename RTYPE>
192template<
typename RTYPE>
195 RTYPE idx = bm::get_super_block_start<RTYPE>(i);
228 tmp = n - ((n >> 1) & 033333333333)
229 - ((n >> 2) & 011111111111);
230 return ((tmp + (tmp >> 3)) & 030707070707) % 63;
248 x = x - ((x >> 1) & m1);
249 y = y - ((y >> 1) & m1);
250 u = u - ((u >> 1) & m1);
251 v = v - ((v >> 1) & m1);
252 x = (x & m2) + ((x >> 2) & m2);
253 y = (y & m2) + ((y >> 2) & m2);
254 u = (u & m2) + ((u >> 2) & m2);
255 v = (v & m2) + ((v >> 2) & m2);
258 x = (x & m3) + ((x >> 4) & m3);
259 u = (u & m3) + ((u >> 4) & m3);
265 return x & 0x000001FFU;
280template<
typename T,
typename F>
283 for (
unsigned sub_octet = 0; w != 0; w >>= 4, sub_octet += 4)
296 func(sub_octet, sub_octet + 1);
302 func(sub_octet, sub_octet + 2);
305 func(sub_octet + 1, sub_octet + 2);
308 func(sub_octet, sub_octet + 1, sub_octet + 2);
314 func(sub_octet, sub_octet + 3);
317 func(sub_octet + 1, sub_octet + 3);
320 func(sub_octet, sub_octet + 1, sub_octet + 3);
323 func(sub_octet + 2, sub_octet + 3);
326 func(sub_octet, sub_octet + 2, sub_octet + 3);
329 func(sub_octet + 1, sub_octet + 2, sub_octet + 3);
332 func(sub_octet, sub_octet + 1, sub_octet + 2, sub_octet + 3);
350template<
typename T,
typename F>
354 for (
unsigned octet = 0; w != 0; w >>= 8, octet += 8)
356 if (w & 1) func(octet + 0);
357 if (w & 2) func(octet + 1);
358 if (w & 4) func(octet + 2);
359 if (w & 8) func(octet + 3);
360 if (w & 16) func(octet + 4);
361 if (w & 32) func(octet + 5);
362 if (w & 64) func(octet + 6);
363 if (w & 128) func(octet + 7);
377 for (
unsigned sub_octet = 0; w; w >>= 4, sub_octet+=4)
384 bits[cnt++] = 0 + sub_octet;
387 bits[cnt++] = 1 + sub_octet;
390 bits[cnt] = 0 + sub_octet;
391 bits[cnt+1] = 1 + sub_octet;
395 bits[cnt++] = 2 + sub_octet;
398 bits[cnt+0] = 0 + sub_octet;
399 bits[cnt+1] = 2 + sub_octet;
403 bits[cnt+0] = 1 + sub_octet;
404 bits[cnt+1] = 2 + sub_octet;
408 bits[cnt+0] = 0 + sub_octet;
409 bits[cnt+1] = 1 + sub_octet;
410 bits[cnt+2] = 2 + sub_octet;
414 bits[cnt++] = 3 + sub_octet;
417 bits[cnt+0] = 0 + sub_octet;
418 bits[cnt+1] = 3 + sub_octet;
422 bits[cnt+0] = 1 + sub_octet;
423 bits[cnt+1] = 3 + sub_octet;
427 bits[cnt+0] = 0 + sub_octet;
428 bits[cnt+1] = 1 + sub_octet;
429 bits[cnt+2] = 3 + sub_octet;
433 bits[cnt+0] = 2 + sub_octet;
434 bits[cnt+1] = 3 + sub_octet;
438 bits[cnt+0] = 0 + sub_octet;
439 bits[cnt+1] = 2 + sub_octet;
440 bits[cnt+2] = 3 + sub_octet;
444 bits[cnt+0] = 1 + sub_octet;
445 bits[cnt+1] = 2 + sub_octet;
446 bits[cnt+2] = 3 + sub_octet;
450 bits[cnt+0] = 0 + sub_octet;
451 bits[cnt+1] = 1 + sub_octet;
452 bits[cnt+2] = 2 + sub_octet;
453 bits[cnt+3] = 3 + sub_octet;
463#ifdef BM_NONSTANDARD_EXTENTIONS
471unsigned bitscan_nibble_gcc(
unsigned w,
unsigned* bits)
BMNOEXCEPT
473 static void* d_table[] = { &&l0,
474 &&l1, &&l3_1, &&l3, &&l7_1, &&l5, &&l7_0, &&l7, &&l15_1,
475 &&l9, &&l11_0, &&l11, &&l15_0, &&l13, &&l14, &&l15 };
478 for (
unsigned sub_octet = 0; w; w >>= 4, sub_octet+=4)
480 goto *d_table[w & 15];
482 bits[cnt++] = sub_octet;
485 bits[cnt++] = sub_octet;
487 bits[cnt++] = 1 + sub_octet;
490 bits[cnt++] = sub_octet;
493 bits[cnt++] = sub_octet;
495 bits[cnt++] = 1 + sub_octet;
497 bits[cnt++] = 2 + sub_octet;
500 bits[cnt++] = sub_octet;
504 bits[cnt++] = sub_octet;
506 bits[cnt++] = 1 + sub_octet;
507 bits[cnt++] = 3 + sub_octet;
510 bits[cnt++] = sub_octet;
513 bits[cnt++] = 1 + sub_octet;
516 bits[cnt++] = 0 + sub_octet;
517 bits[cnt++] = 1 + sub_octet;
519 bits[cnt++] = 2 + sub_octet;
521 bits[cnt++] = 3 + sub_octet;
548 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
556 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1; bp_[2] = (B)bit_idx2;
565 bp_[0] = (B)bit_idx0; bp_[1] = (B)bit_idx1;
566 bp_[2] = (B)bit_idx2; bp_[3] = (B)bit_idx3;
586template<
typename T,
typename B>
591 return (
unsigned)(func.
ptr() - bits);
604template<
typename T,
typename B>
609 return (
unsigned)(func.
ptr() - bits);
633 return (
unsigned short)pos;
655 return (
unsigned short)pos;
669 unsigned short pos = 0;
691 unsigned short pos = 0;
700template<
typename B,
typename OT>
703 unsigned short pos = 0;
724 unsigned short pos = 0;
746 unsigned short pos = 0;
760template<
typename V,
typename B>
763 static_assert(std::is_unsigned<V>::value,
"BM: unsigned type is required");
764#if (defined(__arm__) || defined(__aarch64__))
765 if constexpr (
sizeof(V) == 8)
770 if constexpr (
sizeof(V) == 8)
796 for (
unsigned count = 0; w; w >>=1ull, ++count)
798 rank -= unsigned(w & 1ull);
932#if defined(BMI2_SELECT64)
933 return BMI2_SELECT64(w, rank);
935 #if defined(BMI1_SELECT64)
936 return BMI2_SELECT64(w, rank);
938 #if (defined(__arm__) || defined(__aarch64__))
959#if defined(BMI2_SELECT64)
960 return BMI2_SELECT64(w, rank);
962 #if defined(BMI1_SELECT64)
963 return BMI2_SELECT64(w, rank);
965 #if (defined(__arm__) || defined(__aarch64__))
1002 for (
unsigned i = from; i <= to; ++i)
1003 m |= (1ull << (i / 1024));
1025 mask = (mask >> (63 - (digest_to - digest_from))) << digest_from;
1047 unsigned bitpos_from,
unsigned bitpos_to)
BMNOEXCEPT
1050 return !(digest & mask);
1065 for (
unsigned i = 0; i < 64; ++i)
1069#if defined(VECT_BLOCK_SET_DIGEST)
1074 block[off+j+0] = block[off+j+1] =
1075 block[off+j+2] = block[off+j+3] = mask;
1097 for (
unsigned i = 0; i < 64; ++i)
1100 #if defined(VECT_IS_DIGEST_ZERO)
1107 bm::word_t w = block[off+j+0] | block[off+j+1] |
1108 block[off+j+2] | block[off+j+3];
1111 digest0 |= (mask << i);
1146 #if defined(VECT_IS_DIGEST_ZERO)
1148 digest &= all_zero ? ~(mask << wave) : digest;
1157 src_u->w64[j+0] | src_u->w64[j+1] | src_u->w64[j+2] | src_u->w64[j+3];
1160 digest &= w64 ? digest : ~(mask << wave);
1188 unsigned t_wave = 0;
1203 for (; sub_block < sub_block_end; t_sub_block+=4, sub_block+=4)
1205 t_sub_block[0] = sub_block[0];
1206 t_sub_block[1] = sub_block[1];
1207 t_sub_block[2] = sub_block[2];
1208 t_sub_block[3] = sub_block[3];
1225 for (; t_sub_block < t_sub_block_end; t_sub_block+=4)
1255 unsigned s_wave = 0;
1269 for (; sub_block < sub_block_end; t_sub_block+=4, sub_block+=4)
1271 t_sub_block[0] = sub_block[0];
1272 t_sub_block[1] = sub_block[1];
1273 t_sub_block[2] = sub_block[2];
1274 t_sub_block[3] = sub_block[3];
1285 for (; t_sub_block < t_sub_block_end; t_sub_block+=4)
1287 t_sub_block[0] = 0; t_sub_block[1] = 0;
1288 t_sub_block[2] = 0; t_sub_block[3] = 0;
1337 ::memset(_p, 0xFF,
sizeof(_p));
1338 if constexpr (
sizeof(
void*) == 8)
1340 const unsigned long long magic_mask = 0xFFFFfffeFFFFfffe;
1341 ::memcpy(&_p_fullp, &magic_mask,
sizeof(magic_mask));
1343 _s[i] =
reinterpret_cast<bm::word_t*
>(magic_mask);
1347 const unsigned magic_mask = 0xFFFFfffe;
1348 ::memcpy(&_p_fullp, &magic_mask,
sizeof(magic_mask));
1350 _s[i] =
reinterpret_cast<bm::word_t*
>(magic_mask);
1361 if constexpr (
sizeof(
void*) == 8)
1363 bm::id64_t w =
reinterpret_cast<unsigned long long>(bp);
1365 ((bp ==
_block._p) << 1);
1366 type = type ? type : w;
1370 unsigned w =
reinterpret_cast<unsigned long>(bp);
1372 ((bp ==
_block._p) << 1);
1373 type = type ? type : w;
1407 const unsigned unroll_factor = 4;
1408 const unsigned len = (size - start);
1409 const unsigned len_unr = len - (len % unroll_factor);
1413 for (k = 0; k < len_unr; k+=unroll_factor)
1424 *pos = k + start + 1;
1429 *pos = k + start + 2;
1434 *pos = k + start + 3;
1440 for (; k < len; ++k)
1449 for (; start < size; ++start)
1479 int res = (w1 & 1) - (w2 & 1);
1480 if (res != 0)
return res;
1507 return diff? ( (a & diff & -diff)? 1 : -1 ) : 0;
1524#if defined(VECT_IS_ZERO_BLOCK)
1531 if (blk[0] | blk[1] | blk[2] | blk[3])
1534 }
while (blk < blk_end);
1593 return glevel_len[(*buf >> 1) & 3];
1609 return glevel_len[(*buf >> 1) & 3]-4;
1623 return T((*buf >> 1) & 3u);
1643 T is_set = (*buf) & 1u;
1644 T end = T((*buf) >> 3u);
1648 is_set ^= T((end-1) & 1u);
1674 T is_set = (*buf) & 1u;
1682 *first = buf[1] + 1;
1701 #undef VECT_GAP_BFIND
1702 #ifdef VECT_GAP_BFIND
1705 *is_set = (*buf) & 1;
1707 unsigned end = 1 + ((*buf) >> 3);
1708 while (start != end)
1710 if ((end - start) < 16)
1714 if (buf[start] >= pos)
1720 unsigned curr = (start + end) >> 1;
1721 if ( buf[curr] < pos )
1727 *is_set ^= ((start-1) & 1);
1746 unsigned end = 1 + ((*buf) >> 3);
1747 if (end - start < 10)
1749 unsigned sv = *buf & 1;
1750 unsigned sv1= sv ^ 1;
1751 if (buf[1] >= pos)
return sv;
1752 if (buf[2] >= pos)
return sv1;
1753 if (buf[3] >= pos)
return sv;
1754 if (buf[4] >= pos)
return sv1;
1755 if (buf[5] >= pos)
return sv;
1756 if (buf[6] >= pos)
return sv1;
1757 if (buf[7] >= pos)
return sv;
1758 if (buf[8] >= pos)
return sv1;
1759 if (buf[9] >= pos)
return sv;
1764 while (start != end)
1766 unsigned curr = (start + end) >> 1;
1767 if (buf[curr] < pos)
1773 return ((*buf) & 1) ^ ((--start) & 1);
1792#if defined(BMSSE2OPT)
1795#elif defined(BMSSE42OPT)
1798#elif defined(BMAVX2OPT)
1810template<
typename T,
typename N,
typename F>
1812 N top_size, N nb_from, N nb_to, F& f)
BMNOEXCEPT
1815 if (nb_from > nb_to)
1822 if (i_from >= top_size)
1824 if (i_to >= top_size)
1826 i_to = unsigned(top_size-1);
1830 for (
unsigned i = i_from; i <= i_to; ++i)
1832 T** blk_blk = root[i];
1837 unsigned j = (i == i_from) ? j_from : 0;
1838 if (!j && (i != i_to))
1845 if ((i == i_to) && (j == j_to))
1852 unsigned j = (i == i_from) ? j_from : 0;
1857 if ((i == i_to) && (j == j_to))
1867template<
class T,
class F>
1870 typedef typename F::size_type size_type;
1871 for (
unsigned i = 0; i < size1; ++i)
1873 T** blk_blk = root[i];
1879 f.on_non_empty_top(i);
1891 unsigned non_empty_top = 0;
1896#if defined(BM64_AVX2) || defined(BM64_AVX512)
1900 T* blk0 = blk_blk[j + 0];
1901 T* blk1 = blk_blk[j + 1];
1902 T* blk2 = blk_blk[j + 2];
1903 T* blk3 = blk_blk[j + 3];
1905 size_type block_idx = r + j + 0;
1909 f.on_empty_block(block_idx);
1912 f(blk1, block_idx + 1);
1914 f.on_empty_block(block_idx + 1);
1917 f(blk2, block_idx + 2);
1919 f.on_empty_block(block_idx + 2);
1922 f(blk3, block_idx + 3);
1924 f.on_empty_block(block_idx + 3);
1928 f.on_empty_block(r + j + 0); f.on_empty_block(r + j + 1);
1929 f.on_empty_block(r + j + 2); f.on_empty_block(r + j + 3);
1932#elif defined(BM64_SSE4)
1936 T* blk0 = blk_blk[j + 0];
1937 T* blk1 = blk_blk[j + 1];
1939 size_type block_idx = r + j + 0;
1943 f.on_empty_block(block_idx);
1949 f.on_empty_block(block_idx);
1953 f.on_empty_block(r + j + 0);
1954 f.on_empty_block(r + j + 1);
1960 f(blk_blk[j], r + j);
1964 f.on_empty_block(r + j);
1969 if (non_empty_top == 0)
1976template<
class T,
class F>
1980 for (
unsigned i = 0; i < size1; ++i)
1983 if ((blk_blk = root[i])!=0)
1997 w0 = _mm_loadu_si128((__m128i*)(blk_blk + j));
1998 if (!_mm_testz_si128(w0, w0))
2000 T* blk0 = blk_blk[j + 0];
2001 T* blk1 = blk_blk[j + 1];
2008 w0 = _mm_loadu_si128((__m128i*)(blk_blk + j + 2));
2009 if (!_mm_testz_si128(w0, w0))
2011 T* blk0 = blk_blk[j + 2];
2012 T* blk1 = blk_blk[j + 3];
2022#elif defined(BM64_AVX2) || defined(BM64_AVX512)
2023 for (
unsigned i = 0; i < size1; ++i)
2026 if ((blk_blk = root[i]) != 0)
2039 __m256i w0 = _mm256_loadu_si256((__m256i*)(blk_blk + j));
2040 if (!_mm256_testz_si256(w0, w0))
2044 T* blk0 = blk_blk[j + 0];
2045 T* blk1 = blk_blk[j + 1];
2046 T* blk2 = blk_blk[j + 2];
2047 T* blk3 = blk_blk[j + 3];
2063 for (
unsigned i = 0; i < size1; ++i)
2066 if ((blk_blk = root[i])!=0)
2098template<
typename T,
typename BI,
typename F>
2102 for (BI i = 0; i < size1; ++i)
2104 T** blk_blk = root[i];
2123 if (f(blk_blk[j], block_idx))
2132template<
class T,
class F,
typename BLOCK_IDX>
2135 BLOCK_IDX block_idx = start;
2136 for (
unsigned i = 0; i < size1; ++i)
2138 T** blk_blk = root[i];
2151 f(blk_blk[j], block_idx);
2174 }
while (first < last);
2184 for (;first < last; ++first)
2200 T* arr0, T* arr1, T& arr0_cnt, T& arr1_cnt)
BMNOEXCEPT
2202 const T* pcurr = buf;
2203 unsigned len = (*pcurr >> 3);
2204 const T* pend = pcurr + len;
2208 unsigned is_set = (*buf & 1);
2214 arr1[cnt1] = *pcurr;
2219 arr0[cnt0] = *pcurr;
2226 while (pcurr <= pend)
2229 T delta = *pcurr - prev;
2261 const T* pcurr = buf;
2263 dsize = (*pcurr >> 3);
2265 const T* pend = pcurr + dsize;
2267 unsigned bits_counter = 0;
2272 bits_counter += *pcurr + 1;
2275 for (++pcurr; pcurr <= pend; pcurr += 2)
2276 bits_counter += *pcurr - *(pcurr-1);
2277 return bits_counter;
2289 const T* pcurr = buf;
2290 unsigned dsize = (*pcurr >> 3);
2294 T first_one = *buf & 1;
2302 #if defined(BMAVX2OPT) || defined(BMAVX512OPT)
2305 const unsigned unr_factor = 32;
2306 unsigned waves = (dsize-2) / unr_factor;
2309 #elif defined(BMSSE42OPT) || defined(BMSSE2OPT)
2312 const unsigned unr_factor = 16;
2313 unsigned waves = (dsize - 2) / unr_factor;
2319 const unsigned unr_factor = 8;
2320 unsigned waves = (dsize - 2) / unr_factor;
2321 for (
unsigned i = 0; i < waves; i += unr_factor)
2323 cnt += pcurr[0] - pcurr[0 - 1];
2324 cnt += pcurr[2] - pcurr[2 - 1];
2325 cnt += pcurr[4] - pcurr[4 - 1];
2326 cnt += pcurr[6] - pcurr[6 - 1];
2328 pcurr += unr_factor;
2333 const T* pend = buf + dsize;
2334 for ( ; pcurr <= pend ; pcurr+=2)
2335 cnt += *pcurr - *(pcurr - 1);
2352template<
typename T,
bool RIGHT_END = false>
2359 unsigned is_set, bits_counter, prev_gap;
2361 is_set = ~(is_set - 1u);
2363 const T* pcurr = buf + start_pos;
2364 if (right <= *pcurr)
2365 bits_counter = unsigned(right - left + 1u) & is_set;
2368 bits_counter = unsigned(*pcurr - left + 1u) & is_set;
2369 if constexpr (RIGHT_END)
2372 for (prev_gap = *pcurr++ ;
true; prev_gap = *pcurr++)
2374 bits_counter += (is_set ^= ~0u) & (*pcurr - prev_gap);
2381 for (prev_gap = *pcurr++; right > *pcurr; prev_gap = *pcurr++)
2382 bits_counter += (is_set ^= ~0u) & (*pcurr - prev_gap);
2383 bits_counter += unsigned(right - prev_gap) & (is_set ^ ~0u);
2386 return bits_counter;
2402 unsigned left,
unsigned right,
unsigned hint)
BMNOEXCEPT
2407 unsigned is_set, bits_counter, prev_gap;
2411 is_set = ~(is_set - 1u);
2412 unsigned start_pos = hint >> 1;
2414 unsigned is_set_c; (void)is_set_c;
2415 unsigned pos; (void)pos;
2417 BM_ASSERT(
bool(is_set) ==
bool(is_set_c));
2420 const T* pcurr = buf + start_pos;
2421 if (right <= *pcurr)
2422 bits_counter = unsigned(right - left + 1u) & is_set;
2425 bits_counter = unsigned(*pcurr - left + 1u) & is_set;
2426 for (prev_gap = *pcurr++; right > *pcurr; prev_gap = *pcurr++)
2427 bits_counter += (is_set ^= ~0u) & (*pcurr - prev_gap);
2428 bits_counter += unsigned(right - prev_gap) & (is_set ^ ~0u);
2430 return bits_counter;
2453 const T*
const pcurr = buf + start_pos;
2454 return (right <= *pcurr);
2474 const T*
const pcurr = buf + start_pos;
2478 if (right <= *pcurr)
2505 const T* pcurr = buf + start_pos;
2506 if (!is_set || (right != *pcurr) || (start_pos <= 1))
2509 if (*pcurr != left-1)
2534 *pos = buf[start_pos];
2563 *pos = buf[start_pos]+1;
2594 *pos = buf[start_pos];
2613template<
typename T,
typename SIZE_TYPE>
2622 const T* pcurr = block;
2623 const T* pend = pcurr + (*pcurr >> 3);
2625 unsigned bits_counter = 0;
2627 unsigned start_pos =
bm::gap_bfind(block, nbit_from, &is_set);
2628 is_set = ~(is_set - 1u);
2630 pcurr = block + start_pos;
2631 bits_counter += unsigned(*pcurr - nbit_from + 1u) & is_set;
2632 if (bits_counter >= rank)
2634 nbit_pos = nbit_from + unsigned(rank) - 1u;
2637 rank -= bits_counter;
2638 unsigned prev_gap = *pcurr++;
2639 for (is_set ^= ~0u; pcurr <= pend; is_set ^= ~0u)
2641 bits_counter = (*pcurr - prev_gap) & is_set;
2642 if (bits_counter >= rank)
2644 nbit_pos = prev_gap + unsigned(rank);
2647 rank -= bits_counter;
2648 prev_gap = *pcurr++;
2702template<
typename T,
bool TCORRECT=false>
2707 unsigned bits_counter, prev_gap;
2709 unsigned is_set = ~((unsigned(*buf) & 1u) - 1u);
2710 const T* pcurr = buf + 1;
2711 if (right <= *pcurr)
2713 bits_counter = (right + 1u) & is_set;
2717 bits_counter = (*pcurr + 1u) & is_set;
2718 prev_gap = *pcurr++;
2719 for (is_set ^= ~0u; right > *pcurr; is_set ^= ~0u, prev_gap = *pcurr++)
2721 bits_counter += (*pcurr - prev_gap) & is_set;
2725 bits_counter += (right - prev_gap) & is_set;
2729 if constexpr (TCORRECT)
2730 bits_counter -= (is_set & unsigned(TCORRECT));
2731 return bits_counter;
2745template<
class T,
class Func>
2748 const T* pcurr = gap_buf;
2749 const T* pend = pcurr + (*pcurr >> 3);
2753 func((T)(prev + 1));
2757 func((T)(*pcurr - prev));
2759 }
while (++pcurr < pend);
2792 *dgap_buf++ = *gap_buf;
2796 for_each_dgap<T, d_copy_func<T> >(gap_buf, copy_func);
2816 const T* pcurr = dgap_buf;
2821 *gap_buf++ = *pcurr++;
2825 len = gap_header >> 3;
2826 *gap_buf++ = gap_header;
2829 const T* pend = pcurr + len;
2831 *gap_buf = *pcurr++;
2835 *gap_buf = T(*gap_buf - 1);
2837 for (++gap_buf; pcurr < pend; ++pcurr)
2839 T prev = *(gap_buf-1);
2840 *gap_buf++ = T(*pcurr + prev);
2857 const T* pcurr1 = buf1;
2858 const T* pend1 = pcurr1 + (*pcurr1 >> 3);
2859 unsigned bitval1 = *buf1 & 1;
2862 const T* pcurr2 = buf2;
2863 unsigned bitval2 = *buf2 & 1;
2866 while (pcurr1 <= pend1)
2868 if (*pcurr1 == *pcurr2)
2870 if (bitval1 != bitval2)
2872 return (bitval1) ? 1 : -1;
2877 if (bitval1 == bitval2)
2881 return (*pcurr1 < *pcurr2) ? -1 : 1;
2885 return (*pcurr1 < *pcurr2) ? 1 : -1;
2890 return (bitval1) ? 1 : -1;
2917 const T* pcurr1 = buf1;
2918 const T* pend1 = pcurr1 + (*pcurr1 >> 3);
2919 const T* pcurr2 = buf2;
2920 for (++pcurr1, ++pcurr2; pcurr1 <= pend1; ++pcurr1, ++pcurr2)
2922 if (*pcurr1 != *pcurr2)
2924 *pos = 1 + ((*pcurr1 < *pcurr2) ? *pcurr1 : *pcurr2);
2950template<
typename T,
class F>
2953 unsigned vect1_mask,
2955 unsigned vect2_mask,
2958 const T* cur1 = vect1;
2959 const T* cur2 = vect2;
2961 T bitval1 = (T)((*cur1++ & 1) ^ vect1_mask);
2962 T bitval2 = (T)((*cur2++ & 1) ^ vect2_mask);
2964 T bitval = (T) F::op(bitval1, bitval2);
2965 T bitval_prev = bitval;
2971 T c1 = *cur1; T c2 = *cur2;
2974 bitval = (T) F::op(bitval1, bitval2);
2979 res += (bitval != bitval_prev);
2980 bitval_prev = bitval;
3000 bitval1 ^= 1; bitval2 ^= 1;
3006 dlen = (unsigned)(res - dest);
3007 *dest = (T)((*dest & 7) + (dlen << 3));
3025template<
typename T,
class F>
3027 unsigned vect1_mask,
3031 const T* cur1 = vect1;
3032 const T* cur2 = vect2;
3034 unsigned bitval1 = (*cur1++ & 1) ^ vect1_mask;
3035 unsigned bitval2 = (*cur2++ & 1) ^ vect2_mask;
3037 unsigned bitval = F::op(bitval1, bitval2);
3040 unsigned bitval_prev = bitval;
3044 bitval = F::op(bitval1, bitval2);
3048 if (bitval != bitval_prev)
3049 bitval_prev = bitval;
3069 bitval1 ^= 1; bitval2 ^= 1;
3090template<
typename T,
class F>
3094 const T* cur1 = vect1;
3095 const T* cur2 = vect2;
3097 unsigned bitval1 = (*cur1++ & 1);
3098 unsigned bitval2 = (*cur2++ & 1);
3099 unsigned bitval = count = F::op(bitval1, bitval2);
3100 unsigned bitval_prev = bitval;
3107 bitval = F::op(bitval1, bitval2);
3110 if (bitval != bitval_prev)
3112 bitval_prev = bitval;
3121 count += res - res_prev;
3124 ++cur1; bitval1 ^= 1;
3131 count += res - res_prev;
3144 bitval1 ^= 1; bitval2 ^= 1;
3156#pragma GCC diagnostic push
3157#pragma GCC diagnostic ignored "-Wconversion"
3181 T end = (T)(*buf >> 3);
3189 T* pcurr = buf + curr;
3190 T* pprev = pcurr - 1;
3191 T* pend = buf + end;
3200 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
3206 pprev = buf + 1; pcurr = pprev + 1;
3211 if (curr > 1 && ((
unsigned)(*pprev))+1 == pos)
3214 if (*pprev == *pcurr)
3222 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
3230 end += (pcurr == pend);
3235 ::memmove(pcurr+2, pcurr, (end - curr + 1)*(
sizeof(T)));
3237 pcurr[0] = (T)(pos-1);
3242 *buf = (T)((*buf & 7) + (end << 3));
3270 T end = (T)(*buf >> 3);
3274 T* pcurr = buf + curr;
3275 T* pprev = pcurr - 1;
3276 T* pend = buf + end;
3285 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
3291 pprev = buf + 1; pcurr = pprev + 1;
3296 if (curr > 1 && ((
unsigned)(*pprev))+1 == pos)
3299 if (*pprev == *pcurr)
3307 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
3315 end += (pcurr == pend);
3320 ::memmove(pcurr+2, pcurr, (end - curr + 1)*(
sizeof(T)));
3322 pcurr[0] = (T)(pos-1);
3327 *buf = (T)((*buf & 7) + (end << 3));
3347 T end = (T)(*buf >> 3);
3349 T* pcurr = buf + end;
3351 T* pprev = pcurr - 1;
3360 ::memmove(&buf[2], &buf[1], (end - 1) *
sizeof(
gap_word_t));
3366 pprev = buf + 1; pcurr = pprev + 1;
3368 do { *pprev++ = *pcurr++; }
while (pcurr < pend);
3371 else if (((
unsigned)(*pprev))+1 == pos && (curr > 1) )
3374 if (*pprev == *pcurr)
3380 else if (*pcurr == pos)
3383 end += (pcurr == pend);
3387 pcurr[0] = (T)(pos-1);
3393 *buf = (T)((*buf & 7) + (end << 3));
3399#pragma GCC diagnostic pop
3419 bool co, gap_set_flag;
3420 unsigned len = (*buf >> 3);
3423 unsigned bitval = *buf & 1;
3424 gap_set_flag = (bitval != co_flag);
3430 for (; i < len; ++i)
3440 *buf = (T)((*buf & 7) + (len << 3));
3472 bool co, gap_set_flag;
3477 gap_set_flag = (val != is_set);
3478 unsigned len = (*buf >> 3);
3488 for (; i < len; ++i)
3498 *buf = (T)((*buf & 7) + (len << 3));
3532 unsigned bitval = *buf & 1;
3542 BM_ASSERT(bitval ==
unsigned(*buf & 1u));
3554 unsigned len = (*buf >> 3);
3556 for (; i < len; ++i)
3585 *buf = (T)((*buf & 6u) + (1u << 3));
3593 *pcurr = (T)(curr - 1);
3603 for (i = 1; i < len; ++i)
3606 if (curr == prev + 1)
3615 *pcurr++ = (T)(curr-1);
3626 unsigned gap_len = unsigned(pcurr - buf);
3627 BM_ASSERT(gap_len == ((gap_len << 3) >> 3));
3629 *buf = (T)((*buf & 7) + (gap_len << 3));
3646 unsigned gap_count = 1;
3650 for (
unsigned i = 1; i < len; ++i)
3653 if (curr != prev + 1)
3690 unsigned val = buf[gap_idx] + 1;
3708 dest[nword] |= unsigned(1u << nbit);
3721 dest[nword] &= ~(unsigned(1u << nbit));
3735 return (block[nword] >> nbit) & 1u;
3750 const unsigned maskFF = ~0u;
3757 *dest |= (1u << bitpos);
3763 unsigned mask_r = maskFF << bitpos;
3764 unsigned right_margin = bitpos + bitcount;
3765 if (right_margin < 32)
3767 *dest |= (maskFF >> (32 - right_margin)) & mask_r;
3771 bitcount -= 32 - bitpos;
3773 for ( ;bitcount >= 64; bitcount-=64, dest+=2)
3774 dest[0] = dest[1] = maskFF;
3777 *dest++ = maskFF; bitcount -= 32;
3781 *dest |= maskFF >> (32 - bitcount);
3797 const unsigned maskFF = ~0u;
3804 *dest &= ~(1u << bitpos);
3810 unsigned mask_r = maskFF << bitpos;
3811 unsigned right_margin = bitpos + bitcount;
3812 if (right_margin < 32)
3814 *dest &= ~((maskFF >> (32 - right_margin)) & mask_r);
3817 *dest++ &= ~~mask_r;
3818 bitcount -= 32 - bitpos;
3820 for ( ;bitcount >= 64; bitcount-=64, dest+=2)
3821 dest[0] = dest[1] = 0u;
3824 *dest++ = 0u; bitcount -= 32;
3828 *dest &= ~(maskFF >> (32 - bitcount));
3854 *word ^= unsigned(1 << nbit);
3860 unsigned right_margin = nbit + bitcount;
3865 if (right_margin < 32)
3869 unsigned mask = mask_r & mask_l;
3874 bitcount -= 32 - nbit;
3877 for ( ;bitcount >= 64; bitcount-=64, word+=2)
3879 word[0] ^= ~0u; word[1] ^= ~0u;
3883 *word++ ^= ~0u; bitcount -= 32;
3905 const T* pend = pcurr + (*pcurr >> 3);
3911 for (pcurr += 2; pcurr <= pend; pcurr += 2)
3934 const T* pend = pcurr + (*pcurr >> 3);
3949 for (; pcurr <= pend; pcurr += 2)
3951 if (*pcurr >= start_pos)
3961 for (; pcurr <= pend; pcurr += 2)
3993 const T* pend = pcurr + (*pcurr >> 3);
3999 for (pcurr += 2; pcurr <= pend; pcurr += 2)
4021 const T* pend = pcurr + len;
4032 for (; pcurr <= pend; )
4035 pos = 1u + pcurr[-1];
4036 bc = *pcurr - pcurr[-1];
4054 unsigned len = (*pcurr >> 3);
4072 const T* pend = pcurr + (*pcurr >> 3);
4082 for (; pcurr <= pend; )
4085 pos = 1u + pcurr[-1];
4086 bc = *pcurr - pcurr[-1];
4109 const T* pend = pcurr + (*pcurr >> 3);
4124 for (; pcurr <= pend; pcurr += 2)
4126 if (*pcurr >= start_pos)
4136 for (; pcurr <= pend; pcurr += 2)
4168 const T* pend = pcurr + (*pcurr >> 3);
4175 for (pcurr +=2 ;pcurr <= pend; pcurr += 2)
4197 const T* pend = pcurr + (*pcurr >> 3);
4204 for (pcurr +=2 ;!count && pcurr <= pend; pcurr += 2)
4227 const T* pcurr = buf;
4228 const T* pend = pcurr + (*pcurr >> 3);
4240 for (;pcurr <= pend; pcurr+=2)
4262 const T* pcurr = buf;
4263 const T* pend = pcurr + (*pcurr >> 3);
4277 for (; !count && pcurr <= pend; pcurr+=2)
4300 const T* pcurr = buf;
4301 const T* pend = pcurr + (*pcurr >> 3);
4304 unsigned bitval = *buf & 1;
4309 count = *pcurr + 1 - count;
4312 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
4314 T prev = (T)(*(pcurr-1)+1);
4318 c = (*pcurr - prev + 1) - c;
4338 const T* pcurr = buf;
4339 const T* pend = pcurr + (*pcurr >> 3);
4342 unsigned bitval = *buf & 1;
4346 count = *pcurr + 1 - count;
4348 for (bitval^=1, ++pcurr; !count && pcurr <= pend; bitval^=1, ++pcurr)
4350 T prev = (T)(*(pcurr-1)+1);
4354 c = (*pcurr - prev + 1) - c;
4375 const T* pcurr = buf;
4376 const T* pend = pcurr + (*pcurr >> 3);
4379 unsigned bitval = *buf & 1;
4381 bm::id_t count = bitval ? *pcurr + 1
4383 for (bitval^=1, ++pcurr; pcurr <= pend; bitval^=1, ++pcurr)
4385 T prev = (T)(*(pcurr-1)+1);
4387 bitval ? (*pcurr - prev + 1)
4470 if (buf[1] == set_max - 1)
4489 unsigned end = *buf >> 3;
4491 const T* pcurr = buf;
4492 const T* pend = pcurr + (*pcurr >> 3);
4500 while (pcurr <= pend)
4521 *buf = (T)((*buf & 6u) + (1u << 3) + value);
4522 *(++buf) = (T)(set_max - 1);
4547 if (to == set_max - 1)
4555 buf[2] = (T)(set_max - 1);
4556 buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
4563 if (to == set_max - 1)
4566 buf[1] = (T)(from - 1);
4567 buf[2] = (T)(set_max - 1);
4572 buf[1] = (T) (from - 1);
4574 buf[3] = (T)(set_max - 1);
4576 buf[0] = (T)((*buf & 6u) + (gap_len << 3) + value);
4593#pragma GCC diagnostic push
4594#pragma GCC diagnostic ignored "-Wconversion"
4610 *buf = (T)(((level & 3) << 1) | (*buf & 1) | (*buf & ~7));
4613#pragma GCC diagnostic pop
4629 if (len <=
unsigned(glevel_len[0]-4))
return 0;
4630 if (len <=
unsigned(glevel_len[1]-4))
return 1;
4631 if (len <=
unsigned(glevel_len[2]-4))
return 2;
4632 if (len <=
unsigned(glevel_len[3]-4))
return 3;
4653 return capacity - len;
4669 const T* pend1 = buf1 + len;
4676 return (w1 & diff & -diff) ? 1 : -1;
4677 }
while (buf1 < pend1);
4696#ifdef VECT_BIT_FIND_DIFF
4716 *pos = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::wordop_t))));
4728 *pos = unsigned(idx + (i * 8u *
sizeof(
bm::word_t)));
4759 unsigned bitval = (*block) & 1u;
4762 unsigned bit_idx = 0;
4766 unsigned val = *block;
4767 while (!val || val == ~0u)
4769 if (bitval !=
unsigned(
bool(val)))
4773 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4776 bit_idx += unsigned(
sizeof(*block) * 8);
4777 if (++block >= block_end)
4784 unsigned bits_consumed = 0;
4788 if (bitval != (val & 1u))
4792 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4802 bits_consumed += tz;
4808 if (bits_consumed < 32u)
4812 bit_idx += 32u - bits_consumed;
4813 BM_ASSERT((pcurr-1) == (dest+1) || *(pcurr-1) > *(pcurr-2));
4820 }
while(++block < block_end);
4824 unsigned len = (unsigned)(pcurr - dest);
4825 *dest = (
gap_word_t)((*dest & 7) + (len << 3));
4840#if defined(VECT_BIT_TO_GAP)
4852template<
class T,
class F>
4855 const T* pcurr = buf;
4856 const T* pend = pcurr + (*pcurr >> 3);
4866 unsigned to = *pcurr;
4867 for (
unsigned i = 0; i <= to; ++i)
4880 while (pcurr <= pend)
4882 unsigned from = *(pcurr-1)+1;
4883 unsigned to = *pcurr;
4886 func(from - prev + first_inc);
4894 for (
unsigned i = from+1; i <= to; ++i)
4907template<
typename D,
typename T>
4914 const T* pend = pcurr + (*pcurr >> 3);
4919 int bitval = (*buf) & 1;
4925 if (
unsigned(*pcurr + 1) >= dest_len)
4938 while (pcurr <= pend)
4940 unsigned pending = *pcurr - *(pcurr-1);
4941 if (pending >= dest_len)
4943 dest_len -= pending;
4944 T from = (T)(*(pcurr-1)+1);
4946 for (T i = from; ;++i)
4953 return (D) (dest_curr - dest);
4975 #if defined(BM_USE_GCC_BUILD)
4976 count += unsigned(__builtin_popcountll(x) + __builtin_popcountll(y)
4977 + __builtin_popcountll(u) + __builtin_popcountll(v));
4989 }
while (block < block_end);
5000 }
while (block < block_end);
5039#ifdef VECT_BIT_COUNT_DIGEST
5062 #if defined(BM_USE_GCC_BUILD)
5063 count += unsigned(__builtin_popcountll(x) + __builtin_popcountll(y)
5064 + __builtin_popcountll(u) + __builtin_popcountll(v));
5089 }
while (blk < blk_end);
5117 count -= (w >> ((
sizeof(w) * 8) - 1));
5130 unsigned gap_count = 1;
5135 const int w_shift = int(
sizeof(w) * 8 - 1);
5138 gap_count -= (w_prev = (w0 >> w_shift));
5141 for (++block; block < block_end; ++block)
5147 gap_count -= !w_prev;
5155 gap_count -= (w0 >> w_shift);
5156 gap_count -= !(w_prev ^ w_l);
5158 w_prev = (w0 >> w_shift);
5172 unsigned gap_count = 1;
5178 const int w_shift = int(
sizeof(w) * 8 - 1);
5181 gap_count -= unsigned(w_prev = (w0 >> w_shift));
5183 const bm::id64_t* block_end = block + (size/2);
5184 for (++block; block < block_end; ++block)
5190 gap_count -= !w_prev;
5198 gap_count -= unsigned(w0 >> w_shift);
5199 gap_count -= !(w_prev ^ w_l);
5200 w_prev = (w0 >> w_shift);
5224 #ifdef VECT_BLOCK_CHANGE_BC
5251#if defined(VECT_BLOCK_CHANGE)
5274 unsigned nword, nbit, bitcount, temp;
5279 return (*word >> nbit) & 1u;
5283 unsigned right_margin = nbit + right - left;
5284 if (right_margin < 32)
5288 unsigned mask = mask_r & mask_l;
5289 return mask == (*word & mask);
5293 temp = *word & mask_r;
5296 bitcount = (right - left + 1u) - (32 - nbit);
5301 bitcount = right - left + 1u;
5308 #if defined(BM64OPT) || defined(BM64_SSE4) || defined(BMAVX2OPT) || defined(BMAVX512OPT)
5310 for ( ;bitcount >= 128; bitcount-=128, word+=4)
5314 if ((w64_0 ^ maskFF64) | (w64_1 ^ maskFF64))
5318 for ( ;bitcount >= 128; bitcount-=128, word+=4)
5320 bm::word_t m = (word[0] != maskFF) || (word[1] != maskFF) |
5321 (word[2] != maskFF) || (word[3] != maskFF);
5327 for ( ;bitcount >= 32; bitcount-=32, ++word)
5329 if (*word != maskFF)
5336 temp = *word & mask_l;
5355template<
bool LWA,
bool RWA>
5363 unsigned nword, nbit, bitcount, count, right_margin;
5367 return (*block >> nbit) & 1u;
5369 bitcount = 1u + (right_margin = (right - left));
5378 right_margin += nbit;
5380 if (right_margin < 32)
5386 bitcount -= 32 - nbit;
5393 #if defined(BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
5394 for ( ;bitcount >= 128; bitcount-=128)
5399 count += unsigned(_mm_popcnt_u64(w64_0));
5400 count += unsigned(_mm_popcnt_u64(w64_1));
5403 for ( ;bitcount >= 64; bitcount-=64)
5406 count += unsigned(_mm_popcnt_u64(w64));
5415 for ( ;bitcount >= 32; bitcount-=32)
5450 unsigned bitcount = right + 1;
5453 #if defined(BMAVX2OPT) || defined(BMAVX512OPT)
5456 __m256i cnt = _mm256_setzero_si256();
5459 for ( ;bitcount >= 256; bitcount -= 256)
5461 const __m256i* src = (__m256i*)block;
5462 __m256i xmm256 = _mm256_load_si256(src);
5464 cnt = _mm256_add_epi64(cnt, bc);
5469 count += (unsigned)(cnt64[0] + cnt64[1] + cnt64[2] + cnt64[3]);
5472 for ( ;bitcount >= 64; bitcount -= 64)
5504 block[i] = (block[i] << 1) | (block[i + 1] >> 31);
5518 const unsigned unroll_factor = 4;
5524 w0 = block[i + 1] >> 31;
5525 w1 = block[i + 2] >> 31;
5526 w2 = block[i + 3] >> 31;
5527 w3 = block[i + 4] >> 31;
5529 block[0 + i] = (block[0 + i] << 1) | w0;
5530 block[1 + i] = (block[1 + i] << 1) | w1;
5531 block[2 + i] = (block[2 + i] << 1) | w2;
5532 block[3 + i] = (block[3 + i] << 1) | w3;
5534 block[i] = (block[i] << 1) | (block[i + 1] >> 31);
5535 block[i + 1] = (block[i + 1] << 1) | (block[i + 2] >> 31);
5536 block[i + 2] = (block[i + 2] << 1) | (block[i + 3] >> 31);
5569 block[nword] = w | (unsigned(value) << nbit) | wl;
5581 w = (w << 1u) | co_flag;
5612 acc |= w = (w << 1u) | co_flag;
5648 acc0 |= w = (w << 1u) | co_flag;
5654 acc1 |= w = (w << 1u) | co_flag;
5659 *empty_acc = bool(acc0 | acc1);
5683 #if defined(VECT_SHIFT_R1)
5713 acc |= w = (w >> 1u) | (co_flag << 31u);
5741 w0 = block[i]; w1 = block[i-1];
5743 acc |= w0 = (w0 >> 1u) | (co_flag << 31u);
5747 acc |= w1 = (w1 >> 1u) | (co_flag << 31u);
5752 w0 = block[i]; w1 = block[i-1];
5754 acc |= w0 = (w0 >> 1u) | (co_flag << 31u);
5758 acc |= w1 = (w1 >> 1u) | (co_flag << 31u);
5783 #if defined(VECT_SHIFT_L1)
5823 w = (w >> 1u) | (co_flag << 31u);
5835 w |= wl | (co_flag << 31u);
5840 block[nword] = (block[nword] >> 1u) | (co_flag << 31u);
5875 for (; di < 64; ++di)
5888 w = (w << 1u) | co_flag;
5889 acc |= block[i] = w & mask_block[i];
5905 block[d_base] = co_flag & mask_block[d_base];
5937 #if defined(VECT_SHIFT_R1_AND)
5959 unsigned nbit = left;
5967 return (*word >> nbit) & 1;
5970 unsigned bitcount = right - left + 1;
5974 unsigned right_margin = nbit + (right - left);
5975 if (right_margin < 32)
5979 unsigned mask = mask_r & mask_l;
5980 return *word & mask;
5985 acc = *word & mask_r;
5988 bitcount -= 32 - nbit;
5996 for ( ;bitcount >= 128; bitcount-=128, word+=4)
5998 acc = word[0] | word[1] | word[2] | word[3];
6004 for ( ;bitcount >= 32; bitcount -= 32)
6012 acc |= (*word) & mask_l;
6032 start[0] = ~~start[0];
6033 start[1] = ~~start[1];
6034 start[2] = ~~start[2];
6035 start[3] = ~~start[3];
6037 }
while (start < end);
6049#if defined(VECT_IS_ONE_BLOCK)
6057 start[0] & start[1] & start[2] & start[3];
6061 }
while (start < end);
6102 bool is_left, is_right, all_one;
6115 if (is_left ==
false)
6119 if (is_right ==
false)
6152 w &= (1u << bit_pos);
6167 w = (~~block[nword]) >> bit_pos;
6172 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))-1);
6182 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))-1);
6248 w &= (1u << bit_pos);
6264 w = (~~block[nword]) & mask_l;
6268 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))+1);
6274 for (--nword;
true; --nword)
6280 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t)))+1);
6312 w &= (1u << bit_pos);
6315 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
6327 w = block[nword] & mask_l;
6331 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
6337 for (--nword;
true; --nword)
6344 unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
6373 if (b && *found_nbit == 0)
6384 if (b && *found_nbit == 0)
6412 *found_nbit = nbit_from;
6489 bm::gap_buff_op<bm::gap_word_t, bm::and_func>(
6490 tmp_buf, vect1, 0, vect2, 0, dsize);
6512 return gap_buff_any_op<bm::gap_word_t, bm::and_func>(vect1, 0, vect2, 0);
6529 return bm::gap_buff_count_op<bm::gap_word_t, bm::and_func>(vect1, vect2);
6556 bm::gap_buff_op<bm::gap_word_t, bm::xor_func>(
6557 tmp_buf, vect1, 0, vect2, 0, dsize);
6594 return gap_buff_any_op<bm::gap_word_t, bm::xor_func>(vect1, 0, vect2, 0);
6610 return bm::gap_buff_count_op<bm::gap_word_t, bm::xor_func>(vect1, vect2);
6637 bm::gap_buff_op<bm::gap_word_t, bm::and_func>(tmp_buf, vect1, 1, vect2, 1, dsize);
6655 return gap_buff_count_op<bm::gap_word_t, bm::or_func>(vect1, vect2);
6683 bm::gap_buff_op<bm::gap_word_t, bm::and_func>(
6684 tmp_buf, vect1, 0, vect2, 1, dsize);
6708 bm::gap_buff_any_op<bm::gap_word_t, bm::and_func>(
6709 vect1, 0, vect2, 1);
6726 return bm::gap_buff_count_op<bm::gap_word_t, bm::sub_func>(vect1, vect2);
6764#ifdef VECT_COPY_BLOCK_UNALIGN
6785#ifdef VECT_STREAM_BLOCK
6803#ifdef VECT_STREAM_BLOCK_UNALIGN
6838 for (
unsigned i = 0; i < arr_sz; i+=4)
6840 acc |= (dst_u->w64[i] &= src_u->w64[i]) |
6841 (dst_u->w64[i+1] &= src_u->w64[i+1]) |
6842 (dst_u->w64[i+2] &= src_u->w64[i+2]) |
6843 (dst_u->w64[i+3] &= src_u->w64[i+3]);
6878 #if defined(VECT_AND_DIGEST)
6881 digest &= ~(mask << wave);
6890 acc |= dst_u->w64[j+0] &= src_u->w64[j+0];
6891 acc |= dst_u->w64[j+1] &= src_u->w64[j+1];
6892 acc |= dst_u->w64[j+2] &= src_u->w64[j+2];
6893 acc |= dst_u->w64[j+3] &= src_u->w64[j+3];
6898 digest &= ~(mask << wave);
6924 BM_ASSERT(src0 && src1 && src2 && src3);
6935#if defined(VECT_AND_DIGEST_5WAY)
6936 bool all_zero =
VECT_AND_DIGEST_5WAY(&dst[off], &src0[off], &src1[off], &src2[off], &src3[off]);
6938 digest &= ~(mask << wave);
6950 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];
6951 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];
6952 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];
6953 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];
6958 digest &= ~(mask << wave);
7001 #if defined(VECT_AND_DIGEST_2WAY)
7004 digest &= ~(mask << wave);
7017 acc |= dst_u->w64[j+0] = src_u1->w64[j+0] & src_u2->w64[j+0];
7018 acc |= dst_u->w64[j+1] = src_u1->w64[j+1] & src_u2->w64[j+1];
7019 acc |= dst_u->w64[j+2] = src_u1->w64[j+2] & src_u2->w64[j+2];
7020 acc |= dst_u->w64[j+3] = src_u1->w64[j+3] & src_u2->w64[j+3];
7025 digest &= ~(mask << wave);
7068 #if defined(VECT_AND_OR_DIGEST_2WAY)
7072 digest &= ~(mask << wave);
7085 acc |= dst_u->w64[j+0] |= src_u1->w64[j+0] & src_u2->w64[j+0];
7086 acc |= dst_u->w64[j+1] |= src_u1->w64[j+1] & src_u2->w64[j+1];
7087 acc |= dst_u->w64[j+2] |= src_u1->w64[j+2] & src_u2->w64[j+2];
7088 acc |= dst_u->w64[j+3] |= src_u1->w64[j+3] & src_u2->w64[j+3];
7093 digest &= ~(mask << wave);
7134 }
while (b1 < b1_end);
7144 }
while (src1 < src1_end);
7168 count = (src1[0] & src2[0]) |
7169 (src1[1] & src2[1]) |
7170 (src1[2] & src2[2]) |
7171 (src1[3] & src2[3]);
7173 }
while ((src1 < src1_end) && !count);
7211 }
while (b1 < b1_end);
7221 }
while (src1 < src1_end);
7245 count = (src1[0] ^ src2[0]) |
7246 (src1[1] ^ src2[1]) |
7247 (src1[2] ^ src2[2]) |
7248 (src1[3] ^ src2[3]);
7250 }
while (!count && (src1 < src1_end));
7284 }
while (b1 < b1_end);
7294 }
while (src1 < src1_end);
7318 count = (src1[0] & ~~src2[0]) |
7319 (src1[1] & ~src2[1]) |
7320 (src1[2] & ~~src2[2]) |
7321 (src1[3] & ~src2[3]);
7323 }
while ((src1 < src1_end) && (count == 0));
7359 }
while (b1 < b1_end);
7369 }
while (src1 < src1_end);
7392 count = (src1[0] | src2[0]) |
7393 (src1[1] | src2[1]) |
7394 (src1[2] | src2[2]) |
7395 (src1[3] | src2[3]);
7398 }
while (!count && (src1 < src1_end));
7690 acc &= (dst_ptr[0] |= wrd_ptr[0]);
7691 acc &= (dst_ptr[1] |= wrd_ptr[1]);
7692 acc &= (dst_ptr[2] |= wrd_ptr[2]);
7693 acc &= (dst_ptr[3] |= wrd_ptr[3]);
7695 dst_ptr+=4;wrd_ptr+=4;
7697 }
while (wrd_ptr < wrd_end);
7698 return acc == not_acc;
7728 acc &= (dst_ptr[0] = wrd_ptr1[0] | wrd_ptr2[0]);
7729 acc &= (dst_ptr[1] = wrd_ptr1[1] | wrd_ptr2[1]);
7730 acc &= (dst_ptr[2] = wrd_ptr1[2] | wrd_ptr2[2]);
7731 acc &= (dst_ptr[3] = wrd_ptr1[3] | wrd_ptr2[3]);
7733 dst_ptr+=4; wrd_ptr1+=4; wrd_ptr2+=4;
7735 }
while (wrd_ptr1 < wrd_end1);
7736 return acc == not_acc;
7766 acc |= (dst_ptr[0] = wrd_ptr1[0] ^ wrd_ptr2[0]);
7767 acc |= (dst_ptr[1] = wrd_ptr1[1] ^ wrd_ptr2[1]);
7768 acc |= (dst_ptr[2] = wrd_ptr1[2] ^ wrd_ptr2[2]);
7769 acc |= (dst_ptr[3] = wrd_ptr1[3] ^ wrd_ptr2[3]);
7771 dst_ptr+=4; wrd_ptr1+=4; wrd_ptr2+=4;
7773 }
while (wrd_ptr1 < wrd_end1);
7808 acc &= (dst_ptr[0] |= wrd_ptr1[0] | wrd_ptr2[0]);
7809 acc &= (dst_ptr[1] |= wrd_ptr1[1] | wrd_ptr2[1]);
7810 acc &= (dst_ptr[2] |= wrd_ptr1[2] | wrd_ptr2[2]);
7811 acc &= (dst_ptr[3] |= wrd_ptr1[3] | wrd_ptr2[3]);
7813 dst_ptr+=4; wrd_ptr1+=4;wrd_ptr2+=4;
7815 }
while (wrd_ptr1 < wrd_end1);
7816 return acc == not_acc;
7856 acc &= (dst_ptr[0] |= wrd_ptr1[0] | wrd_ptr2[0] | wrd_ptr3[0] | wrd_ptr4[0]);
7857 acc &= (dst_ptr[1] |= wrd_ptr1[1] | wrd_ptr2[1] | wrd_ptr3[1] | wrd_ptr4[1]);
7858 acc &= (dst_ptr[2] |= wrd_ptr1[2] | wrd_ptr2[2] | wrd_ptr3[2] | wrd_ptr4[2]);
7859 acc &= (dst_ptr[3] |= wrd_ptr1[3] | wrd_ptr2[3] | wrd_ptr3[3] | wrd_ptr4[3]);
7862 wrd_ptr1+=4;wrd_ptr2+=4;wrd_ptr3+=4;wrd_ptr4+=4;
7864 }
while (wrd_ptr1 < wrd_end1);
7865 return acc == not_acc;
7958 for (
unsigned i = 0; i < arr_sz; i+=4)
7960 acc |= (dst_u->w64[i] &= ~~src_u->w64[i]) |
7961 (dst_u->w64[i+1] &= ~src_u->w64[i+1]) |
7962 (dst_u->w64[i+2] &= ~~src_u->w64[i+2]) |
7963 (dst_u->w64[i+3] &= ~src_u->w64[i+3]);
7999 #if defined(VECT_SUB_DIGEST)
8002 digest &= ~(mask << wave);
8011 acc |= dst_u->w64[j+0] &= ~~src_u->w64[j+0];
8012 acc |= dst_u->w64[j+1] &= ~~src_u->w64[j+1];
8013 acc |= dst_u->w64[j+2] &= ~~src_u->w64[j+2];
8014 acc |= dst_u->w64[j+3] &= ~~src_u->w64[j+3];
8019 digest &= ~(mask << wave);
8060 #if defined(VECT_SUB_DIGEST_2WAY)
8063 digest &= ~(mask << wave);
8076 acc |= dst_u->w64[j+0] = src_u1->w64[j+0] & ~~src_u2->w64[j+0];
8077 acc |= dst_u->w64[j+1] = src_u1->w64[j+1] & ~~src_u2->w64[j+1];
8078 acc |= dst_u->w64[j+2] = src_u1->w64[j+2] & ~~src_u2->w64[j+2];
8079 acc |= dst_u->w64[j+3] = src_u1->w64[j+3] & ~~src_u2->w64[j+3];
8084 digest &= ~(mask << wave);
8182 for (
unsigned i = 0; i < arr_sz; i+=4)
8184 acc |= dst_u->w64[i] ^= src_u->w64[i];
8185 acc |= dst_u->w64[i+1] ^= src_u->w64[i+1];
8186 acc |= dst_u->w64[i+2] ^= src_u->w64[i+2];
8187 acc |= dst_u->w64[i+3] ^= src_u->w64[i+3];
8219 dst_ptr+=4; wrd_ptr+=4;
8220 }
while (wrd_ptr < wrd_end);
8241 if (src == dst)
return 0;
8247 if (!src)
return dst;
8253 if (!src)
return dst;
8337 const T* blk_end = blk + data_size - 2;
8342 const T* blk_j = blk + 1;
8343 for (; blk_j < blk_end; ++blk_j)
8353 const T* blk_j = blk + 1;
8354 for ( ; blk_j < blk_end; ++blk_j)
8358 if (blk_j[1] | blk_j[2])
8368 count += unsigned(blk_j - blk) * unsigned(
sizeof(T));
8373 while(blk < blk_end);
8374 return count + unsigned(2 *
sizeof(T));
8399 w &= (1u << bit_pos);
8405 w = block[nword] >> bit_pos;
8410 *pos = unsigned(bit_pos + (nword * 8u *
unsigned(
sizeof(
bm::word_t))));
8420 *pos = unsigned(bit_pos + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
8454 *last = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
8480#ifdef VECT_BIT_FIND_FIRST
8489 *pos = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
8527 *first = unsigned(idx + (i * 8u *
unsigned(
sizeof(
bm::word_t))));
8571 *first = unsigned(idx + (i * 8u *
sizeof(
bm::word_t)));
8600template<
typename SIZE_TYPE>
8612 unsigned pos = nbit_from;
8622 rank -= bc; pos += unsigned(32u - nbit);
8628 nbit_pos = pos + idx;
8633 #if defined(BM64OPT) || defined(BM64_SSE4) || defined(BMAVX2OPT) || defined(BMAVX512OPT)
8643 nbit_pos = pos + idx;
8658 rank -= bc; pos += 32u;
8662 nbit_pos = pos + idx;
8681template<
typename SIZE_TYPE>
8707 unsigned total_possible_bitcount,
8715 if ((gap_size < block_size) && (gap_size < arr_size) && (gap_size < inv_arr_size))
8720 if (arr_size < inv_arr_size)
8722 if ((arr_size < block_size) && (arr_size < gap_size))
8729 if ((inv_arr_size < block_size) && (inv_arr_size < gap_size))
8756 src+=2, bit_idx += unsigned(
sizeof(*src) * 8 * 2))
8767 return (
unsigned)(pcurr - dest);
8783 if (!blk)
return true;
8807 if (blk == 0)
return false;
8829 const T* length_end,
8832 BM_ASSERT(length && length_end && glevel_len);
8834 unsigned overhead = 0;
8835 for (;length < length_end; ++length)
8837 unsigned len = *length;
8840 unsigned capacity = glevel_len[level];
8842 overhead += capacity - len;
8856 const T* length_end,
8859 BM_ASSERT(length && length_end && glevel_len);
8861 size_t lsize = size_t(length_end - length);
8867 for (i = 0; i < lsize; ++i)
8869 if (length[i] > max_len)
8870 max_len = length[i];
8874 glevel_len[0] = T(max_len + 4);
8884 unsigned min_overhead =
gap_overhead(length, length_end, glevel_len);
8885 bool is_improved =
false;
8891 unsigned opt_len = 0;
8893 bool imp_flag =
false;
8895 for (j = 0; j < lsize; ++j)
8897 glevel_len[i] = T(length[j] + 4);
8898 unsigned ov =
gap_overhead(length, length_end, glevel_len);
8899 if (ov <= min_overhead)
8902 opt_len = length[j]+4;
8908 glevel_len[i] = (T)opt_len;
8913 glevel_len[i] = gap_saved_value;
8921 T val = *glevel_len;
8923 T* res = glevel_len;
8960 if (!blk || !arg_blk)
9103 if (cnt_ < from_ || cnt_ > to_)
9108 return decoder_.get_32();
9123template<
class It1,
class It2,
class BinaryOp,
class Encoder>
9129 for (
unsigned i = 0; i < block_size; ++i)
9268 &gap_and_to_bitset<bm::gap_word_t>,
9269 &gap_add_to_bitset<bm::gap_word_t>,
9270 &gap_sub_to_bitset<bm::gap_word_t>,
9271 &gap_xor_to_bitset<bm::gap_word_t>,
9326 w0 = w_ptr[0]; w1 = w_ptr[1];
9328#if defined(BMAVX512OPT) || defined(BMAVX2OPT) || defined(BM64OPT) || defined(BM64_SSE4)
9333 w0 = w_ptr[2]; w1 = w_ptr[3];
9337 #if (defined(__arm__) || defined(__aarch64__))
9341 w0 = w_ptr[2]; w1 = w_ptr[3];
9349 w0 = w_ptr[2]; w1 = w_ptr[3];
9354 return static_cast<unsigned short>(cnt0);
9357#if defined (BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
9367 unsigned size,
unsigned start,
9370typedef unsigned TRGW;
9371typedef unsigned IDX;
9372#if defined(BM64_SSE4)
9375 if constexpr (
sizeof(TRGW)==4 &&
sizeof(IDX)==4)
9380#elif defined(BM64_AVX2) || defined(BM64_AVX512)
9381 if constexpr (
sizeof(TRGW)==4 &&
sizeof(IDX)==4)
9397template<
typename TRGW,
typename IDX,
typename SZ>
9401 SZ size, SZ start,
unsigned bit_idx)
BMNOEXCEPT
9406 const SZ len = (size - start);
9407 const SZ len_unr = len - (len % 2);
9409 for (; k < len_unr; k+=2)
9411 const SZ base = start + k;
9419 for (; k < len; ++k)
9447 for (;(start < size) &&
9467 unsigned size,
unsigned nb,
unsigned start)
BMNOEXCEPT
9472#if defined(VECT_ARR_BLOCK_LOOKUP)
9475 for (;(start < size) &&
9510 block[nword] |= (1u << nbit);
9534#if defined(VECT_SET_BLOCK_BITS)
9539 unsigned n = idx[start++];
9543 block[nword] |= (1u << nbit);
9544 }
while (start < stop);
9596#if defined(VECT_LOWER_BOUND_SCAN_U32)
9599 for (; from <= to; ++from)
9601 if (arr[from] >= target)
9614 unsigned long long target,
9621 for (; from <= to; ++from)
9623 if (arr[from] >= target)
9643 const unsigned linear_cutoff = 32;
9645 unsigned l = from;
unsigned r = to;
9646 unsigned dist = r - l;
9647 if (dist < linear_cutoff)
9654 unsigned mid = (r-l)/2+l;
9655 if (arr[mid] < target)
9660 if (dist < linear_cutoff)
9674 unsigned long long target,
9679 const unsigned linear_cutoff = 32;
9681 unsigned l = from;
unsigned r = to;
9682 unsigned dist = r - l;
9683 if (dist < linear_cutoff)
9690 unsigned mid = (r - l) / 2 + l;
9691 if (arr[mid] < target)
9696 if (dist < linear_cutoff)
9710bool find_ptr(
const void*
const * p_arr,
size_t arr_size,
9714 for (
size_t i = 0; i < arr_size; ++i)
9715 if (ptr == p_arr[i])
9717 *idx = i;
return true;
9735 return block_idx + base_idx;
9744 return block_idx + base_idx;
9758 unsigned md = arr[1] - arr[0];
9759 for (
size_t i = 1; i < arr_size; ++i)
9761 unsigned prev = arr[i-1];
9762 unsigned curr = arr[i];
9764 unsigned delta = curr - prev;
9787 for (
size_t i = 1; i < arr_size; ++i)
9798template<
typename VT,
typename SZ>
9803 for (SZ i = 0; i < arr_size; ++i)
9808 max_v = v; *found_idx = i;
9819template<
typename VT,
typename SZ>
9822 for (SZ i = 0; i < arr_size; ++i)
9838template<
typename VT,
typename SZ>
9842 for (SZ i = 0; i < arr_size; ++i)
9843 cnt += (arr[i] != 0);
9879 float bie_bits_per_int,
9893 unsigned ibc = max_bits - bc;
9899 float cost_in_bits = float(gc) * bie_bits_per_int;
9900 if (cost_in_bits >=
float(max_bits))
9910 float cost_in_bits = float(bc) * bie_bits_per_int;
9911 if (cost_in_bits >=
float(max_bits))
9917 float cost_in_bits = float(ibc) * bie_bits_per_int;
9918 if (cost_in_bits >=
float(max_bits))
9941 unsigned arr_idx = idx >> 1;
9944 unsigned char old_val = arr[arr_idx];
9946 arr[arr_idx] = (
unsigned char)(old_val | (v << 4));
9950 unsigned char old_val = arr[arr_idx];
9952 arr[arr_idx] = (
unsigned char)(old_val | (v & 0xF));
9968 unsigned char v = arr[idx >> 1];
9969 v >>= (idx & 1) * 4;
9999 return (ptr.i16[1] == 0);
10001 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_COPY_BLOCK(dst, src)
#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_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_BIT_FIND_FIRST(src1, pos)
#define VECT_GAP_BFIND(buf, pos, is_set)
#define VECT_INVERT_BLOCK(first)
#define VECT_BLOCK_CHANGE(block, size)
#define VECT_AND_DIGEST_2WAY(dst, src1, src2)
#define VECT_AND_OR_DIGEST_2WAY(dst, src1, src2)
#define VECT_BLOCK_SET_DIGEST(dst, val)
#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)
Bit-block get adapter, takes bitblock and represents it as a get_32() accessor function.
bitblock_get_adapter(const bm::word_t *bit_block)
BMFORCEINLINE bm::word_t get_32() BMNOEXCEPT
Bit-block store adapter, takes bitblock and saves results into it.
BMFORCEINLINE void push_back(bm::word_t w)
bitblock_store_adapter(bm::word_t *bit_block)
Bit-block sum adapter, takes values and sums it /internal.
BMFORCEINLINE void push_back(bm::word_t w) BMNOEXCEPT
bm::word_t sum() const BMNOEXCEPT
Get accumulated sum.
Adaptor to copy 1 bits to array.
copy_to_array_functor(B *bits)
void operator()(unsigned bit_idx0, unsigned bit_idx1, unsigned bit_idx2) BMNOEXCEPT
void operator()(unsigned bit_idx0, unsigned bit_idx1, unsigned bit_idx2, unsigned bit_idx3) BMNOEXCEPT
void operator()(unsigned bit_idx0, unsigned bit_idx1) BMNOEXCEPT
void operator()(unsigned bit_idx) BMNOEXCEPT
Adapter to get words from a range stream (see range serialized bit-block)
bm::word_t get_32() BMNOEXCEPT
decoder_range_adapter(DEC &dec, unsigned from_idx, unsigned to_idx)
BMFORCEINLINE bool avx2_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
unsigned avx2_gap_test(const unsigned short *BMRESTRICT buf, unsigned pos)
Hybrid binary search, starts as binary, then switches to scan.
unsigned sse2_gap_test(const unsigned short *BMRESTRICT buf, unsigned pos)
Hybrid binary search, starts as binary, then switches to scan.
BMFORCEINLINE bool sse42_test_all_zero_wave(const void *ptr) BMNOEXCEPT
check if wave of pointers is all NULL
unsigned sse42_gap_test(const unsigned short *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
Hybrid binary search, starts as binary, then switches to scan.
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::word_t * bit_operation_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
bitblock SUB operation.
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::word_t * bit_operation_xor(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
bitblock XOR operation.
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
bool check_zero_digest(bm::id64_t digest, unsigned bitpos_from, unsigned bitpos_to) BMNOEXCEPT
check if all digest bits for the range [from..to] are 0
void or_bit_block(unsigned *dest, unsigned bitpos, unsigned bitcount) BMNOEXCEPT
Sets bits to 1 in the bitblock.
bm::id64_t bit_block_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks...
bm::id_t bit_block_count(const bm::word_t *block) BMNOEXCEPT
Bitcount for bit block.
bool bit_block_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)
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)
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.
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.
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...
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::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
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...
void bit_block_set(bm::word_t *BMRESTRICT dst, bm::word_t value) BMNOEXCEPT
Bitblock memset operation.
BMFORCEINLINE unsigned test_bit(const unsigned *block, unsigned bitpos) BMNOEXCEPT
Test 1 bit in a block.
void bit_block_rotate_left_1_unr(bm::word_t *block) BMNOEXCEPT
Unrolled cyclic rotation of bit-block left by 1 bit.
BMFORCEINLINE bm::id64_t digest_mask(unsigned from, unsigned to) BMNOEXCEPT
Compute digest mask for [from..to] positions.
bool bit_block_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.
bool bit_is_all_zero(const bm::word_t *BMRESTRICT start) BMNOEXCEPT
Returns "true" if all bits in the block are 0.
unsigned bit_find_last(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT last) BMNOEXCEPT
BIT block find the last set bit (backward search)
bool bit_find_first_if_1(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT first, bm::id64_t digest) BMNOEXCEPT
BIT block find the first set bit if only 1 bit is set.
bm::id64_t update_block_digest0(const bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT
Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas)
bool bit_block_shift_r1(bm::word_t *BMRESTRICT block, bm::word_t *BMRESTRICT empty_acc, bm::word_t co_flag) BMNOEXCEPT
Right bit-shift bitblock by 1 bit (reference)
unsigned short bitscan_popcnt(bm::id_t w, B *bits, unsigned short offs) BMNOEXCEPT
Unpacks word into list of ON bit indexes using popcnt method.
bm::id_t bit_operation_xor_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
Performs bitblock XOR operation and calculates bitcount of the result.
unsigned bit_list(T w, B *bits) BMNOEXCEPT
Unpacks word into list of ON bit indexes.
void bit_block_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::word_t * bit_operation_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
bitblock AND operation.
bm::word_t bit_block_insert(bm::word_t *BMRESTRICT block, unsigned bitpos, bool value) BMNOEXCEPT
insert bit into position and shift the rest right with carryover
bool bit_block_find_interval_start(const bm::word_t *BMRESTRICT block, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
Searches for the first 1 bit in the 111 interval of a BIT block.
bm::id64_t bit_block_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destinat...
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.
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.
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.
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.
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Sets or clears bit in the GAP buffer.
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.
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.
unsigned gap_bit_count_to(const T *const buf, T right) BMNOEXCEPT
Counts 1 bits in GAP buffer in the closed [0, right] range.
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_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.
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.
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_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_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.
unsigned * gap_convert_to_bitset_smart(unsigned *BMRESTRICT dest, const T *BMRESTRICT buf, id_t set_max) BMNOEXCEPT
Smart GAP block to bitblock conversion.
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.
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.
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
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
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.
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
gap_word_t *(* gap_operation_func_type)(const gap_word_t *BMRESTRICT, const gap_word_t *BMRESTRICT, gap_word_t *BMRESTRICT, unsigned &)
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.
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
const bm::gap_word_t * avx2_gap_sum_arr(const bm::gap_word_t *pbuf, unsigned avx_vect_waves, unsigned *sum)
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
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
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.
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.
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 _p[bm::set_block_size] BM_VECT_ALIGN_ATTR
bm::word_t BM_VECT_ALIGN *_s[bm::set_sub_array_size] BM_VECT_ALIGN_ATTR
Structure carries pointer on bit block with all bits 1.
static BMFORCEINLINE bool is_valid_block_addr(const bm::word_t *bp) BMNOEXCEPT
static all_set_block _block
static BMFORCEINLINE bool is_full_block(const bm::word_t *bp) BMNOEXCEPT
static bm::id64_t block_type(const bm::word_t *bp) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W) BMNOEXCEPT
W operator()(W, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
Bit COUNT SUB AB functor.
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
W operator()(W w1, W w2) BMNOEXCEPT
bit-block array wrapped into union for correct interpretation of 32-bit vs 64-bit access vs SIMD
bit-decode cache structure
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
Structure with statistical information about memory allocation footprint, serialization projection,...
size_t gap_cap_overhead
gap memory overhead between length and capacity
size_t ptr_sub_blocks
Number of sub-blocks.
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 bit_operation_count_func_type bit_operation_count(unsigned i)
static gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
static bit_operation_count_func_type bit_op_count_table_[bm::set_END]
static gap_operation_func_type gap_operation(unsigned i)
static gap_operation_func_type gapop_table_[bm::set_END]
static gap_operation_to_bitset_func_type gap2bit_table_[bm::set_END]
helper union to interpret pointer as integers