SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
util.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef INCLUDED_SDSL_UTIL
9#define INCLUDED_SDSL_UTIL
10
11#include <algorithm>
12#include <cassert>
13#include <chrono>
14#include <cstdlib>
15#include <errno.h>
16#include <iomanip>
17#include <map>
18#include <numeric>
19#include <random>
20#include <sstream> // for to_string method
21#include <stdexcept> // for std::logic_error
22#include <stdint.h> // for uint64_t uint32_t declaration
23#include <string.h> // for strlen and strdup
24#include <string>
25#include <type_traits>
26#include <typeinfo> // for typeid
27#include <utility>
28
29#include <sdsl/bits.hpp>
30#include <sdsl/config.hpp> // for constants
31#include <sdsl/ram_fs.hpp>
32
33#include <sys/stat.h> // for file_size
34
35// macros to transform a defined name to a string
36#define SDSL_STR(x) #x
37#define SDSL_XSTR(s) SDSL_STR(s)
38
39#include <vector>
40
41#ifndef MSVC_COMPILER
42# include <cxxabi.h>
43#endif
44
45#ifndef _WIN32
46# include <libgen.h> // for basename
47# include <unistd.h> // for getpid, file_size, clock_gettime
48#else
49# include <iso646.h>
50# include <process.h>
51#endif
52
54namespace sdsl
55{
56
58namespace util
59{
60
61//============= Debug information =========================
62
63SDSL_UNUSED static bool verbose = false;
64
65inline void set_verbose()
66{
67 verbose = true;
68}
69
70//============ Manipulating int_vectors ===================
71
73
78template <class t_int_vec>
79void set_random_bits(t_int_vec & v, int seed = 0);
81template <class t_int_vec>
82void _set_zero_bits(t_int_vec & v);
84template <class t_int_vec>
85void _set_one_bits(t_int_vec & v);
86
88
92template <class t_int_vec>
93void bit_compress(t_int_vec & v);
94
96template <class t_int_vec>
97void expand_width(t_int_vec & v, uint8_t new_width);
98
100template <class t_int_vec>
101void mod(t_int_vec & v, typename t_int_vec::size_type m);
102
103inline void cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width);
104
106
112template <class t_int_vec>
113void set_to_value(t_int_vec & v, uint64_t k);
114
116
123template <class t_int_vec, class t_int_vec_iterator>
124void set_to_value(t_int_vec & v, uint64_t k, t_int_vec_iterator it);
125
127template <class t_int_vec>
128void set_to_id(t_int_vec & v);
129
131
134template <class t_int_vec>
135typename t_int_vec::size_type cnt_one_bits(t_int_vec const & v);
136
138
140template <class t_int_vec>
141typename t_int_vec::size_type cnt_onezero_bits(t_int_vec const & v);
142
144
146template <class t_int_vec>
147typename t_int_vec::size_type cnt_zeroone_bits(t_int_vec const & v);
148
150
155template <class t_int_vec>
156typename t_int_vec::size_type next_bit(t_int_vec const & v, uint64_t idx);
157
159
164template <class t_int_vec>
165typename t_int_vec::size_type prev_bit(t_int_vec const & v, uint64_t idx);
166
167//============= Handling files =============================
168
170
173inline size_t file_size(std::string const & file)
174{
175 if (is_ram_file(file))
176 {
177 return ram_fs::file_size(file);
178 }
179 else
180 {
181 struct stat fs;
182 stat(file.c_str(), &fs);
183 return fs.st_size;
184 }
185}
186
188
191inline std::string basename(std::string file)
192{
193 file = disk_file_name(file); // remove RAM-prefix
194#ifdef _WIN32
195 char * c = _strdup((char const *)file.c_str());
196 char file_name[_MAX_FNAME] = {0};
197# ifdef MSVC_COMPILER
198 ::_splitpath_s(c, NULL, 0, NULL, NULL, file_name, _MAX_FNAME, NULL, 0);
199# else
200 ::_splitpath(c, NULL, NULL, file_name, NULL);
201# endif
202 std::string res(file_name);
203#else
204 char * c = strdup((char const *)file.c_str());
205 std::string res = std::string(::basename(c));
206#endif
207 free(c);
208 return res;
209}
210
212
215inline std::string dirname(std::string file)
216{
217 bool ram_file = is_ram_file(file);
218 file = disk_file_name(file); // remove RAM-prefix
219#ifdef _WIN32
220 char * c = _strdup((char const *)file.c_str());
221 char dir_name[_MAX_DIR] = {0};
222 char drive[_MAX_DRIVE] = {0};
223# ifdef MSVC_COMPILER
224 ::_splitpath_s(c, drive, _MAX_DRIVE, dir_name, _MAX_DIR, NULL, 0, NULL, 0);
225# else
226 ::_splitpath(c, drive, dir_name, NULL, NULL);
227# endif
228 std::string res = std::string(drive) + std::string(dir_name);
229#else
230 char * c = strdup((char const *)file.c_str());
231 std::string res = std::string(::dirname(c));
232 auto it = res.begin();
233 auto next_it = res.begin() + 1;
234 while (it != res.end() and next_it != res.end())
235 {
236 if (*next_it != '/' or *it != '/')
237 {
238 *(++it) = *next_it;
239 }
240 ++next_it;
241 }
242 res.resize(it - res.begin() + 1);
243#endif
244 free(c);
245 if (ram_file)
246 {
247 if ("." == res)
248 {
249 res = ram_file_name("");
250 }
251 else if ("/" == res)
252 {
253 res = ram_file_name(res);
254 }
255 }
256 return res;
257}
258
260
263inline std::string demangle(std::string const & name)
264{
265#ifndef _WIN32
266 char buf[4096];
267 size_t size = 4096;
268 int status = 0;
269 abi::__cxa_demangle(name.c_str(), buf, &size, &status);
270 if (status == 0)
271 return std::string(buf);
272 return name;
273#else
274 return name;
275#endif
276}
277
279inline std::string demangle2(std::string const & name)
280{
281 std::string result = demangle(name);
282 std::vector<std::string> words_to_delete;
283 words_to_delete.push_back("sdsl::");
284 words_to_delete.push_back("(unsigned char)");
285 words_to_delete.push_back(", unsigned long");
286
287 for (size_t k = 0; k < words_to_delete.size(); ++k)
288 {
289 std::string w = words_to_delete[k];
290 for (size_t i = result.find(w); i != std::string::npos; i = result.find(w, i))
291 {
292 result.erase(i, w.length());
293 ++i;
294 }
295 }
296 size_t index = 0;
297 std::string to_replace = "int_vector<1>";
298 while ((index = result.find(to_replace, index)) != std::string::npos)
299 {
300 result.replace(index, to_replace.size(), "bit_vector");
301 }
302 return result;
303}
304
306template <typename T>
307std::string to_string(T const & t, int w);
308
310template <class T>
311uint64_t hashvalue_of_classname(T const &)
312{
313 std::hash<std::string> str_hash;
314 return str_hash(sdsl::util::demangle2(typeid(T).name()));
315}
316
318template <class T>
319std::string class_to_hash(T const & t)
320{
321 return to_string(hashvalue_of_classname(t));
322}
323
324template <class T>
325std::string class_name(T const & t)
326{
327 std::string result = demangle2(typeid(t).name());
328 size_t template_pos = result.find("<");
329 if (template_pos != std::string::npos)
330 {
331 result = result.erase(template_pos);
332 }
333 return result;
334}
335
336// convert an errno number to a readable msg
337inline char * str_from_errno()
338{
339#ifdef MSVC_COMPILER
340# pragma warning(disable : 4996)
341 return strerror(errno);
342# pragma warning(default : 4996)
343#else
344 return strerror(errno);
345#endif
346}
347
348struct _id_helper_struct
349{
350 uint64_t id = 0;
351};
352
353extern inline uint64_t _id_helper()
354{
355 static _id_helper_struct data;
356 return data.id++;
357}
358
360inline uint64_t pid()
361{
362#ifdef MSVC_COMPILER
363 return _getpid();
364#else
365 return getpid();
366#endif
367}
368
370inline uint64_t id()
371{
372 return _id_helper();
373}
374
375template <typename T>
376std::string to_latex_string(T const & t);
377
378inline std::string to_latex_string(unsigned char c)
379{
380 if (c == '_')
381 return "\\_";
382 else if (c == '\0')
383 return "\\$";
384 else
385 return to_string(c);
386}
387
389inline void delete_all_files(tMSS & file_map)
390{
391 for (auto file_pair : file_map)
392 {
393 sdsl::remove(file_pair.second);
394 }
395 file_map.clear();
396}
397
399
402template <class T>
403void clear(T & x)
404{
405 T y;
406 x = std::move(y);
407}
408
410
418template <class S, class P>
419void swap_support(S & s1, S & s2, P const * p1, P const * p2)
420{
421 std::swap(s1, s2);
422 s1.set_vector(p1);
423 s2.set_vector(p2);
424}
425
427
430template <class S, class X>
431void init_support(S & s, X const * x)
432{
433 S temp(x); // generate a temporary support object
434 s = std::move(temp); // swap its content with the target object
435 s.set_vector(x); // set the support object's pointer to x
436}
437
439/*
440 */
441template <class t_int_vec>
442t_int_vec rnd_positions(uint8_t log_s, uint64_t & mask, uint64_t mod = 0, uint64_t seed = 17)
443{
444 mask = (1 << log_s) - 1;
445 t_int_vec rands(1 << log_s, 0);
446 set_random_bits(rands, seed);
447 if (mod > 0)
448 {
449 util::mod(rands, mod);
450 }
451 return rands;
452}
453
455/* static_assert(is_regular<YOUR_TYPE>::value);
456 * Code is from a talk of Aerix Consulting
457 */
458template <typename T>
459struct is_regular :
460 std::integral_constant<bool,
461 std::is_default_constructible<T>::value && std::is_copy_constructible<T>::value
462 && std::is_move_constructible<T>::value && std::is_copy_assignable<T>::value
463 && std::is_move_assignable<T>::value>
464{};
465
466} // end namespace util
467
468//==================== Template functions ====================
469
470template <class t_int_vec>
471void util::set_random_bits(t_int_vec & v, int seed)
472{
473 std::mt19937_64 rng;
474 if (0 == seed)
475 {
476 rng.seed(std::chrono::system_clock::now().time_since_epoch().count() + util::id());
477 }
478 else
479 rng.seed(seed);
480
481 uint64_t * data = v.data();
482 if (v.empty())
483 return;
484 *data = rng();
485 for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
486 {
487 *(++data) = rng();
488 }
489}
490
491// all elements of vector v modulo m
492template <class t_int_vec>
493void util::mod(t_int_vec & v, typename t_int_vec::size_type m)
494{
495 for (typename t_int_vec::size_type i = 0; i < v.size(); ++i)
496 {
497 v[i] = v[i] % m;
498 }
499}
500
501template <class t_int_vec>
502void util::bit_compress(t_int_vec & v)
503{
504 auto max_elem = std::max_element(v.begin(), v.end());
505 uint64_t max = 0;
506 if (max_elem != v.end())
507 {
508 max = *max_elem;
509 }
510 uint8_t min_width = bits::hi(max) + 1;
511 uint8_t old_width = v.width();
512 if (old_width > min_width)
513 {
514 uint64_t const * read_data = v.data();
515 uint64_t * write_data = v.data();
516 uint8_t read_offset = 0;
517 uint8_t write_offset = 0;
518 for (typename t_int_vec::size_type i = 0; i < v.size(); ++i)
519 {
520 uint64_t x = bits::read_int_and_move(read_data, read_offset, old_width);
521 bits::write_int_and_move(write_data, x, write_offset, min_width);
522 }
523 v.bit_resize(v.size() * min_width);
524 v.width(min_width);
525 // v.shrink_to_fit(); TODO(cpockrandt): comment in once int_vector_mapper has the same interface
526 }
527}
528
529template <class t_int_vec>
530void util::expand_width(t_int_vec & v, uint8_t new_width)
531{
532 uint8_t old_width = v.width();
533 typename t_int_vec::size_type n = v.size();
534 if (new_width > old_width)
535 {
536 if (n > 0)
537 {
538 typename t_int_vec::size_type i, old_pos, new_pos;
539 new_pos = (n - 1) * new_width;
540 old_pos = (n - 1) * old_width;
541 v.bit_resize(v.size() * new_width);
542 for (i = 0; i < n; ++i, new_pos -= new_width, old_pos -= old_width)
543 {
544 v.set_int(new_pos, v.get_int(old_pos, old_width), new_width);
545 }
546 }
547 v.width(new_width);
548 }
549}
550
551template <class t_int_vec>
552void util::_set_zero_bits(t_int_vec & v)
553{
554 std::for_each(v.data(),
555 v.data() + ((v.bit_size() + 63) >> 6),
556 [](uint64_t & value)
557 {
558 value = 0ULL;
559 });
560}
561
562template <class t_int_vec>
563void util::_set_one_bits(t_int_vec & v)
564{
565 std::for_each(v.data(),
566 v.data() + ((v.bit_size() + 63) >> 6),
567 [](uint64_t & value)
568 {
569 value = -1ULL;
570 });
571}
572
573inline void util::cyclic_shifts(uint64_t * vec, uint8_t & n, uint64_t k, uint8_t int_width)
574{
575 n = 0;
576 vec[0] = 0;
577 uint8_t offset = 0;
578 k &= 0xFFFFFFFFFFFFFFFFULL >> (64 - int_width);
579 do
580 { // loop terminates after at most 64 iterations
581 vec[n] |= k << offset;
582 offset += int_width;
583 if (offset >= 64)
584 {
585 ++n;
586 if (int_width == 64)
587 return;
588 assert(int_width - (offset - 64) < 64);
589 vec[n] = k >> (int_width - (offset - 64));
590 offset -= 64;
591 }
592 }
593 while (offset != 0);
594}
595
596template <class t_int_vec>
597void util::set_to_value(t_int_vec & v, uint64_t k)
598{
599 uint64_t * data = v.data();
600 if (v.empty())
601 return;
602 uint8_t int_width = v.width();
603 if (int_width == 0)
604 {
605 throw std::logic_error("util::set_to_value can not be performed with int_width=0!");
606 }
607 if (0 == k)
608 {
610 return;
611 }
612 if (bits::lo_set[int_width] == k)
613 {
614 _set_one_bits(v);
615 return;
616 }
617 uint8_t n;
618 uint64_t vec[65];
619 util::cyclic_shifts(vec, n, k, int_width);
620
621 typename t_int_vec::size_type n64 = (v.bit_size() + 63) >> 6;
622 for (typename t_int_vec::size_type i = 0; i < n64;)
623 {
624 for (uint64_t ii = 0; ii < n and i < n64; ++ii, ++i)
625 {
626 *(data++) = vec[ii];
627 }
628 }
629}
630
631template <class t_int_vec, class t_int_vec_iterator>
632void util::set_to_value(t_int_vec & v, uint64_t k, t_int_vec_iterator it)
633{
634 typedef typename t_int_vec::size_type size_type;
635
636 if (v.empty())
637 return;
638 uint8_t int_width = v.width();
639 if (int_width == 0)
640 {
641 throw std::logic_error("util::set_to_value can not be performed with int_width=0!");
642 }
643 uint8_t n;
644 uint64_t vec[65];
645 util::cyclic_shifts(vec, n, k, int_width);
646
647 size_type words = (v.bit_size() + 63) >> 6;
648 size_type word_pos = ((it - v.begin()) * int_width) >> 6;
649 uint8_t pos_in_word = ((it - v.begin()) * int_width) - (word_pos << 6); // ((it - v.begin()) * int_width) % 64
650 uint8_t cyclic_shift = word_pos % n;
651
652 uint64_t * data = v.data() + word_pos;
653 *(data) &= bits::lo_set[pos_in_word]; // unset first bits
654 *(data) |= bits::lo_unset[pos_in_word] & vec[cyclic_shift++]; // set last bits
655 ++word_pos;
656
657 while (word_pos < words)
658 {
659 for (; cyclic_shift < n && word_pos < words; ++cyclic_shift, ++word_pos)
660 {
661 *(++data) = vec[cyclic_shift];
662 }
663 cyclic_shift = 0;
664 }
665}
666
668template <class t_int_vec>
669void util::set_to_id(t_int_vec & v)
670{
671 std::iota(v.begin(), v.end(), 0ULL);
672}
673
674template <class t_int_vec>
675typename t_int_vec::size_type util::cnt_one_bits(t_int_vec const & v)
676{
677 uint64_t const * data = v.data();
678 if (v.empty())
679 return 0;
680 typename t_int_vec::size_type result = bits::cnt(*data);
681 for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
682 {
683 result += bits::cnt(*(++data));
684 }
685 if (v.bit_size() & 0x3F)
686 {
687 result -= bits::cnt((*data) & (~bits::lo_set[v.bit_size() & 0x3F]));
688 }
689 return result;
690}
691
692template <class t_int_vec>
693typename t_int_vec::size_type util::cnt_onezero_bits(t_int_vec const & v)
694{
695 uint64_t const * data = v.data();
696 if (v.empty())
697 return 0;
698 uint64_t carry = 0, oldcarry = 0;
699 typename t_int_vec::size_type result = bits::cnt10(*data, carry);
700 for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
701 {
702 oldcarry = carry;
703 result += bits::cnt10(*(++data), carry);
704 }
705 if (v.bit_size() & 0x3F)
706 { // if bit_size is not a multiple of 64, subtract the counts of the additional bits
707 result -= bits::cnt(bits::map10(*data, oldcarry) & bits::lo_unset[v.bit_size() & 0x3F]);
708 }
709 return result;
710}
711
712template <class t_int_vec>
713typename t_int_vec::size_type util::cnt_zeroone_bits(t_int_vec const & v)
714{
715 uint64_t const * data = v.data();
716 if (v.empty())
717 return 0;
718 uint64_t carry = 1, oldcarry = 1;
719 typename t_int_vec::size_type result = bits::cnt01(*data, carry);
720 for (typename t_int_vec::size_type i = 1; i < ((v.bit_size() + 63) >> 6); ++i)
721 {
722 oldcarry = carry;
723 result += bits::cnt01(*(++data), carry);
724 }
725 if (v.bit_size() & 0x3F)
726 { // if bit_size is not a multiple of 64, subtract the counts of the additional bits
727 result -= bits::cnt(bits::map01(*data, oldcarry) & bits::lo_unset[v.bit_size() & 0x3F]);
728 }
729 return result;
730}
731
732template <class t_int_vec>
733typename t_int_vec::size_type util::next_bit(t_int_vec const & v, uint64_t idx)
734{
735 uint64_t pos = idx >> 6;
736 uint64_t node = v.data()[pos];
737 node >>= (idx & 0x3F);
738 if (node)
739 {
740 return idx + bits::lo(node);
741 }
742 else
743 {
744 ++pos;
745 while ((pos << 6) < v.bit_size())
746 {
747 if (v.data()[pos])
748 {
749 return (pos << 6) | bits::lo(v.data()[pos]);
750 }
751 ++pos;
752 }
753 return v.bit_size();
754 }
755}
756
757template <class t_int_vec>
758typename t_int_vec::size_type util::prev_bit(t_int_vec const & v, uint64_t idx)
759{
760 uint64_t pos = idx >> 6;
761 uint64_t node = v.data()[pos];
762 node <<= 63 - (idx & 0x3F);
763 if (node)
764 {
765 return bits::hi(node) + (pos << 6) - (63 - (idx & 0x3F));
766 }
767 else
768 {
769 --pos;
770 while ((pos << 6) < v.bit_size())
771 {
772 if (v.data()[pos])
773 {
774 return (pos << 6) | bits::hi(v.data()[pos]);
775 }
776 --pos;
777 }
778 return v.bit_size();
779 }
780}
781
782template <typename T>
783std::string util::to_string(T const & t, int w)
784{
785 std::stringstream ss;
786 ss << std::setw(w) << t;
787 return ss.str();
788}
789
790template <typename T>
791std::string util::to_latex_string(T const & t)
792{
793 return to_string(t);
794}
795
796} // end namespace sdsl
797#endif
bits.hpp contains the sdsl::bits class.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
#define SDSL_UNUSED
Definition config.hpp:12
size_t file_size(std::string const &name)
Get the file size.
Definition ram_fs.hpp:52
void set_to_id(t_int_vec &v)
Sets each entry of the numerical vector v at position $fi .
Returns the directory of a file A trailing will be removed std::string dirname(std::string file)
Definition util.hpp:215
Returns the basename of a file std::string basename(std::string file)
Definition util.hpp:191
uint64_t id()
void set_random_bits(t_int_vec &v, int seed=0)
Sets all bits of the int_vector to pseudo-random bits.
Definition util.hpp:471
Number of set bits in v t_int_vec::size_type cnt_one_bits(t_int_vec const &v)
void mod(t_int_vec &v, typename t_int_vec::size_type m)
All elements of v modulo m.
Definition util.hpp:493
void expand_width(t_int_vec &v, uint8_t new_width)
Expands the integer width to new_width >= v.width()
Definition util.hpp:530
void cyclic_shifts(uint64_t *vec, uint8_t &n, uint64_t k, uint8_t int_width)
Definition util.hpp:573
Get the smallest position f$i geq idx f$ where a bit is set t_int_vec::size_type next_bit(t_int_vec const &v, uint64_t idx)
Get the size of a file in bytes size_t file_size(std::string const &file)
Definition util.hpp:173
void set_verbose()
Definition util.hpp:65
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_zeroone_bits(t_int_vec const &v)
uint64_t pid()
std::string to_string(T const &t, int w=1)
void bit_compress(t_int_vec &v)
Bit compress the int_vector.
Definition util.hpp:502
void _set_one_bits(t_int_vec &v)
Sets all bits of the int_vector to 1-bits.
Definition util.hpp:563
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition util.hpp:597
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_onezero_bits(t_int_vec const &v)
void _set_zero_bits(t_int_vec &v)
Sets all bits of the int_vector to 0-bits.
Definition util.hpp:552
Get the greatest position f$i leq idx f$ where a bit is set t_int_vec::size_type prev_bit(t_int_vec const &v, uint64_t idx)
Namespace for the succinct data structure library.
std::string disk_file_name(std::string const &file)
Returns for a RAM-file the corresponding disk file name.
Definition ram_fs.hpp:208
int remove(std::string const &)
Remove a file.
Definition ram_fs.hpp:221
std::map< std::string, std::string > tMSS
Definition config.hpp:49
std::string ram_file_name(std::string const &file)
Returns the corresponding RAM-file name for file.
Definition ram_fs.hpp:195
uint64_t count(t_k2_treap const &treap, k2_treap_ns::point_type p1, k2_treap_ns::point_type p2)
Count how many points are in the rectangle (p1,p2)
bool is_ram_file(std::string const &file)
Determines if the given file is a RAM-file.
Definition ram_fs.hpp:176
int_vector ::size_type size(range_type const &r)
Size of a range.
ram_fs.hpp
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition bits.hpp:689
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
static constexpr uint64_t lo_unset[65]
lo_unset[i] is a 64-bit word with the i least significant bits not set and the high bits set.
Definition bits.hpp:216
static constexpr uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
Definition bits.hpp:572
static constexpr void write_int_and_move(uint64_t *&word, uint64_t x, uint8_t &offset, const uint8_t len)
Writes value x to an bit position in an array and moves the bit-pointer.
Definition bits.hpp:749
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition bits.hpp:486
static constexpr uint64_t map01(uint64_t x, uint64_t c=1)
Map all 01 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
Definition bits.hpp:580
static constexpr uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word x.
Definition bits.hpp:558
static constexpr uint64_t read_int_and_move(uint64_t const *&word, uint8_t &offset, const uint8_t len=64)
Reads a value from a bit position in an array and moved the bit-pointer.
Definition bits.hpp:799
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition bits.hpp:194
static constexpr uint64_t map10(uint64_t x, uint64_t c=0)
Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
Definition bits.hpp:566