ROSE  0.9.9.139
BitVector.h
1 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
2 // be clobbered by the next update from Sawyer. The Sawyer repository is at
3 // https://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 #ifndef Sawyer_BitVector_H
9 #define Sawyer_BitVector_H
10 
11 #include <Sawyer/Assert.h>
12 #include <Sawyer/BitVectorSupport.h>
13 #include <Sawyer/Optional.h>
14 #include <Sawyer/Sawyer.h>
15 
16 #include <boost/algorithm/string/predicate.hpp>
17 #include <boost/cstdint.hpp>
18 #include <boost/serialization/access.hpp>
19 #include <boost/serialization/nvp.hpp>
20 #include <boost/serialization/vector.hpp>
21 
22 namespace Sawyer {
23 namespace Container {
24 
25 #ifdef BOOST_WINDOWS
26 
29 inline double log2(double n) {
30  return log(n) / log(2.0);
31 }
32 #endif
33 
64 class BitVector {
65 public:
66  typedef unsigned Word;
69 private:
70  std::vector<Word> words_;
71  size_t size_;
72 
73 private:
74  friend class boost::serialization::access;
75  template<class S>
76  void serialize(S &s, const unsigned /*version*/) {
77  s & BOOST_SERIALIZATION_NVP(size_);
78  s & BOOST_SERIALIZATION_NVP(words_);
79  }
80 
81 public:
83  BitVector(): size_(0) {}
84 
86  BitVector(const BitVector &other): words_(other.words_), size_(other.size_) {}
87 
91  explicit BitVector(size_t nbits, bool newBits = false): size_(0) {
92  resize(nbits, newBits);
93  }
94 
106  static BitVector parse(std::string str) {
107  // Radix information
108  size_t bitsPerDigit = 0;
109  const char *digits = NULL;
110  if (boost::starts_with(str, "0x")) {
111  bitsPerDigit = 4;
112  digits = "0123456789abcdefABCDEF";
113  str = str.substr(2);
114  } else if (boost::starts_with(str, "0b")) {
115  bitsPerDigit = 1;
116  digits = "01";
117  str = str.substr(2);
118  } else if (boost::ends_with(str, "h")) {
119  bitsPerDigit = 4;
120  digits = "0123456789abcdefABCDEF";
121  str = str.substr(0, str.size()-1);
122  } else if (boost::starts_with(str, "0")) {
123  bitsPerDigit = 2;
124  digits = "01234567";
125  str = str.substr(1);
126  } else {
127  bitsPerDigit = 0; // special case
128  digits = "0123456789";
129  }
130 
131  // Count digits
132  size_t nDigits = 0;
133  for (const char *t=str.c_str(); *t; ++t) {
134  if (strchr(digits, *t))
135  ++nDigits;
136  }
137  if (0==nDigits)
138  throw std::runtime_error("BitVector::parse: no valid digits");
139 
140  // Number of bits
141  size_t nBits = 0;
142  if (bitsPerDigit) {
143  nBits = bitsPerDigit * nDigits;
144  } else {
145  nBits = ceil(log2(pow(10.0, (double)nDigits)));
146  }
147 
148  // Parse the string
149  BitVector result(nBits);
150  switch (bitsPerDigit) {
151  case 0:
152  result.fromDecimal(str);
153  break;
154  case 2:
155  result.fromBinary(str);
156  break;
157  case 3:
158  result.fromOctal(str);
159  break;
160  case 4:
161  result.fromHex(str);
162  break;
163  default:
164  assert(!"invalid radix");
165  break;
166  }
167  return result;
168  }
169 
175  BitVector& operator=(const BitVector &other) {
176  words_ = other.words_;
177  size_ = other.size_;
178  return *this;
179  }
180 
184  bool isEmpty() const { return 0 == size_; }
185 
189  size_t size() const { return size_; }
190 
196  BitVector& resize(size_t newSize, bool newBits=false) {
197  if (0==newSize) {
198  words_.clear();
199  size_ = 0;
200  } else if (newSize > size_) {
201  size_t nwords = BitVectorSupport::numberOfWords<Word>(newSize);
202  words_.resize(nwords, Word(0));
203  BitVectorSupport::setValue(data(), BitRange::hull(size_, newSize-1), newBits);
204  size_ = newSize;
205  } else {
206  size_t nwords = BitVectorSupport::numberOfWords<Word>(newSize);
207  words_.resize(nwords);
208  size_ = newSize;
209  }
210  return *this;
211  }
212 
217  size_t capacity() const {
218  return BitVectorSupport::bitsPerWord<Word>::value * words_.capacity();
219  }
220 
224  BitRange hull() const {
225  return 0==size_ ? BitRange() : BitRange::hull(0, size_-1);
226  }
227 
232  static BitRange baseSize(size_t base, size_t size) {
233  return BitRange::baseSize(base, size);
234  }
235 
240  static BitRange hull(size_t minOffset, size_t maxOffset) {
241  return BitRange::hull(minOffset, maxOffset);
242  }
243 
245  // Value access
247 
252  bool get(size_t idx) const {
253  checkRange(idx);
254  return BitVectorSupport::get(data(), idx);
255  }
256 
262  BitVector& clear(const BitRange &range) {
263  checkRange(range);
264  BitVectorSupport::clear(data(), range);
265  return *this;
266  }
267 
275  return *this;
276  }
277 
282  BitVector& set(const BitRange &range) {
283  checkRange(range);
284  BitVectorSupport::set(data(), range);
285  return *this;
286  }
287 
294  return *this;
295  }
296 
300  BitVector& setValue(const BitRange &range, bool value) {
301  checkRange(range);
302  BitVectorSupport::setValue(data(), range, value);
303  return *this;
304  }
305 
309  BitVector& setValue(bool value) {
310  BitVectorSupport::setValue(data(), hull(), value);
311  return *this;
312  }
313 
321  BitVector& copy(const BitRange &to, const BitVector &other, const BitRange &from) {
322  checkRange(to);
323  other.checkRange(from);
324  BitVectorSupport::copy(other.data(), from, data(), to);
325  return *this;
326  }
327 
333  BitVector& copy(const BitRange &to, const BitRange &from) {
334  checkRange(to);
335  checkRange(from);
336  BitVectorSupport::copy(data(), from, data(), to);
337  return *this;
338  }
339 
345  BitVector& swap(const BitRange &range1, BitVector &other, const BitRange &range2) {
346  checkRange(range1);
347  other.checkRange(range2);
348  BitVectorSupport::swap(data(), range1, other.data(), range2);
349  return *this;
350  }
351 
356  BitVector& swap(const BitRange &range1, const BitRange &range2) {
357  checkRange(range1);
358  checkRange(range2);
359  BitVectorSupport::swap(data(), range1, data(), range2);
360  return *this;
361  }
362 
364  // Counting/searching
366 
372  Optional<size_t> leastSignificantSetBit(const BitRange &range) const {
373  checkRange(range);
375  }
376 
383  }
384 
390  Optional<size_t> leastSignificantClearBit(const BitRange &range) const {
391  checkRange(range);
393  }
394 
401  }
402 
408  Optional<size_t> mostSignificantSetBit(const BitRange &range) const {
409  checkRange(range);
411  }
412 
419  }
420 
426  Optional<size_t> mostSignificantClearBit(const BitRange &range) const {
427  checkRange(range);
429  }
430 
437  }
438 
443  bool isAllSet(const BitRange &range) const {
444  checkRange(range);
445  return BitVectorSupport::isAllSet(data(), range);
446  }
447 
451  bool isAllSet() const {
452  return BitVectorSupport::isAllSet(data(), hull());
453  }
454 
461  bool isAllClear(const BitRange &range) const {
462  checkRange(range);
463  return BitVectorSupport::isAllClear(data(), range);
464  }
465 
471  bool isAllClear() const {
473  }
474 
478  size_t nSet(const BitRange &range) const {
479  checkRange(range);
480  return BitVectorSupport::nSet(data(), range);
481  }
482 
486  size_t nSet() const {
487  return BitVectorSupport::nSet(data(), hull());
488  }
489 
493  size_t nClear(const BitRange &range) const {
494  checkRange(range);
495  return BitVectorSupport::nClear(data(), range);
496  }
497 
501  size_t nClear() const {
502  return BitVectorSupport::nClear(data(), hull());
503  }
504 
515  Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitVector &other,
516  const BitRange &range2) const {
517  checkRange(range1);
518  other.checkRange(range2);
519  return BitVectorSupport::mostSignificantDifference(data(), range1, other.data(), range2);
520  }
521 
530  Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitRange &range2) const {
531  checkRange(range1);
532  checkRange(range2);
533  return BitVectorSupport::mostSignificantDifference(data(), range1, data(), range2);
534  }
535 
542  return BitVectorSupport::mostSignificantDifference(data(), hull(), other.data(), other.hull());
543  }
544 
555  Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitVector &other,
556  const BitRange &range2) const {
557  checkRange(range1);
558  other.checkRange(range2);
559  return BitVectorSupport::leastSignificantDifference(data(), range1, other.data(), range2);
560  }
561 
570  Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitRange &range2) const {
571  checkRange(range1);
572  checkRange(range2);
573  return BitVectorSupport::leastSignificantDifference(data(), range1, data(), range2);
574  }
575 
582  return BitVectorSupport::leastSignificantDifference(data(), hull(), other.data(), other.hull());
583  }
584 
586  // Shift/rotate
588 
596  BitVector& shiftLeft(const BitRange &range, size_t nShift, bool newBits = 0) {
597  checkRange(range);
598  BitVectorSupport::shiftLeft(data(), range, nShift, newBits);
599  return *this;
600  }
601 
609  BitVector& shiftLeft(size_t nShift, bool newBits = 0) {
610  BitVectorSupport::shiftLeft(data(), hull(), nShift, newBits);
611  return *this;
612  }
613 
621  BitVector& shiftRight(const BitRange &range, size_t nShift, bool newBits = 0) {
622  checkRange(range);
623  BitVectorSupport::shiftRight(data(), range, nShift, newBits);
624  return *this;
625  }
626 
634  BitVector& shiftRight(size_t nShift, bool newBits = 0) {
635  BitVectorSupport::shiftRight(data(), hull(), nShift, newBits);
636  return *this;
637  }
638 
647  BitVector& shiftRightArithmetic(const BitRange &range, size_t nShift) {
648  checkRange(range);
650  return *this;
651  }
652 
661  BitVector& shiftRightArithmetic(size_t nShift) {
663  return *this;
664  }
665 
671  BitVector& rotateRight(const BitRange &range, size_t nShift) {
672  checkRange(range);
673  BitVectorSupport::rotateRight(data(), range, nShift);
674  return *this;
675  }
676 
682  BitVector& rotateRight(size_t nShift) {
684  return *this;
685  }
686 
692  BitVector& rotateLeft(const BitRange &range, size_t nShift) {
693  checkRange(range);
694  BitVectorSupport::rotateLeft(data(), range, nShift);
695  return *this;
696  }
697 
703  BitVector& rotateLeft(size_t nShift) {
704  BitVectorSupport::rotateLeft(data(), hull(), nShift);
705  return *this;
706  }
707 
709  // Arithmetic
711 
716  BitVector& negate(const BitRange &range1) {
717  checkRange(range1);
718  BitVectorSupport::negate(data(), range1);
719  return *this;
720  }
721 
728  return *this;
729  }
730 
736  bool increment(const BitRange &range1) {
737  checkRange(range1);
738  return BitVectorSupport::increment(data(), range1);
739  }
740 
745  bool increment() {
747  }
748 
754  bool decrement(const BitRange &range1) {
755  checkRange(range1);
756  return BitVectorSupport::decrement(data(), range1);
757  }
758 
763  bool decrement() {
765  }
766 
773  bool add(const BitRange &range1, const BitVector &other, const BitRange &range2) {
774  checkRange(range1);
775  other.checkRange(range2);
776  return BitVectorSupport::add(other.data(), range2, data(), range1, false);
777  }
778 
784  bool add(const BitRange &range1, const BitRange &range2) {
785  checkRange(range1);
786  checkRange(range2);
787  return BitVectorSupport::add(data(), range2, data(), range1, false);
788  }
789 
796  bool add(const BitVector &other) {
797  return BitVectorSupport::add(other.data(), other.hull(), data(), hull(), false);
798  }
799 
809  bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2) {
810  checkRange(range1);
811  other.checkRange(range2);
812  return BitVectorSupport::subtract(other.data(), range2, data(), range1);
813  }
814 
823  bool subtract(const BitRange &range1, const BitRange &range2) {
824  checkRange(range1);
825  checkRange(range2);
826  return BitVectorSupport::subtract(data(), range2, data(), range1);
827  }
828 
834  bool subtract(const BitVector &other) {
835  return BitVectorSupport::subtract(other.data(), other.hull(), data(), hull());
836  }
837 
844  BitVector& signExtend(const BitRange &range1, const BitVector &other, const BitRange &range2) {
845  checkRange(range1);
846  other.checkRange(range2);
847  BitVectorSupport::signExtend(other.data(), range2, data(), range1);
848  return *this;
849  }
850 
856  BitVector& signExtend(const BitRange &range1, const BitRange &range2) {
857  checkRange(range1);
858  checkRange(range2);
859  BitVectorSupport::signExtend(data(), range2, data(), range1);
860  return *this;
861  }
862 
867  BitVector& signExtend(const BitVector &other) {
868  BitVectorSupport::signExtend(other.data(), other.hull(), data(), hull());
869  return *this;
870  }
871 
872  // FIXME[Robb Matzke 2014-05-01]: we should also have zeroExtend, which is like copy but allows the source and destination
873  // to be different sizes.
874 
876  // Bit-wise Boolean logic
878 
882  BitVector& invert(const BitRange &range) {
883  checkRange(range);
884  BitVectorSupport::invert(data(), range);
885  return *this;
886  }
887 
893  return *this;
894  }
895 
901  BitVector& bitwiseAnd(const BitRange &range1, const BitVector &other, const BitRange &range2) {
902  checkRange(range1);
903  other.checkRange(range2);
904  BitVectorSupport::bitwiseAnd(other.data(), range2, data(), range1);
905  return *this;
906  }
907 
912  BitVector& bitwiseAnd(const BitRange &range1, const BitRange &range2) {
913  checkRange(range1);
914  checkRange(range2);
915  BitVectorSupport::bitwiseAnd(data(), range2, data(), range1);
916  return *this;
917  }
918 
923  BitVector& bitwiseAnd(const BitVector &other) {
924  BitVectorSupport::bitwiseAnd(other.data(), other.hull(), data(), hull());
925  return *this;
926  }
927 
933  BitVector& bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2) {
934  checkRange(range1);
935  other.checkRange(range2);
936  BitVectorSupport::bitwiseOr(other.data(), range2, data(), range1);
937  return *this;
938  }
939 
944  BitVector& bitwiseOr(const BitRange &range1, const BitRange &range2) {
945  checkRange(range1);
946  checkRange(range2);
947  BitVectorSupport::bitwiseOr(data(), range2, data(), range1);
948  return *this;
949  }
950 
955  BitVector& bitwiseOr(const BitVector &other) {
956  BitVectorSupport::bitwiseOr(other.data(), other.hull(), data(), hull());
957  return *this;
958  }
959 
965  BitVector& bitwiseXor(const BitRange &range1, const BitVector &other, const BitRange &range2) {
966  checkRange(range1);
967  other.checkRange(range2);
968  BitVectorSupport::bitwiseXor(other.data(), range2, data(), range1);
969  return *this;
970  }
971 
976  BitVector& bitwiseXor(const BitRange &range1, const BitRange &range2) {
977  checkRange(range1);
978  checkRange(range2);
979  BitVectorSupport::bitwiseXor(data(), range2, data(), range1);
980  return *this;
981  }
982 
987  BitVector& bitwiseXor(const BitVector &other) {
988  BitVectorSupport::bitwiseXor(other.data(), other.hull(), data(), hull());
989  return *this;
990  }
991 
993  // Numeric comparisons
995 
1002  bool isEqualToZero(const BitRange &range) const {
1003  checkRange(range);
1004  return BitVectorSupport::isEqualToZero(data(), range);
1005  }
1006 
1012  bool isEqualToZero() const {
1014  }
1015 
1024  int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1025  checkRange(range1);
1026  other.checkRange(range2);
1027  return BitVectorSupport::compare(data(), range1, other.data(), range2);
1028  }
1029 
1037  int compare(const BitRange &range1, const BitRange &range2) const {
1038  checkRange(range1);
1039  checkRange(range2);
1040  return BitVectorSupport::compare(data(), range1, data(), range2);
1041  }
1042 
1050  int compare(const BitVector &other) const {
1051  return BitVectorSupport::compare(data(), hull(), other.data(), other.hull());
1052  }
1053 
1063  int compareSigned(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1064  checkRange(range1);
1065  other.checkRange(range2);
1066  return BitVectorSupport::compareSigned(data(), range1, other.data(), range2);
1067  }
1068 
1077  int compareSigned(const BitRange &range1, const BitRange &range2) const {
1078  checkRange(range1);
1079  checkRange(range2);
1080  return BitVectorSupport::compareSigned(data(), range1, data(), range2);
1081  }
1082 
1090  int compareSigned(const BitVector &other) const {
1091  return BitVectorSupport::compareSigned(data(), hull(), other.data(), other.hull());
1092  }
1093 
1095  // Conversion
1097 
1102  boost::uint64_t toInteger(const BitRange &range) const {
1103  checkRange(range);
1104  return BitVectorSupport::toInteger(data(), range);
1105  }
1106 
1111  boost::uint64_t toInteger() const {
1112  if (size() <= 64)
1113  return BitVectorSupport::toInteger(data(), size());
1114  return BitVectorSupport::toInteger(data(), hull());
1115  }
1116 
1123  std::string toHex(const BitRange &range) const {
1124  return BitVectorSupport::toHex(data(), range);
1125  }
1126 
1133  std::string toHex() const {
1134  return BitVectorSupport::toHex(data(), hull());
1135  }
1136 
1143  std::string toOctal(const BitRange &range) const {
1144  return BitVectorSupport::toOctal(data(), range);
1145  }
1146 
1152  std::string toOctal() const {
1153  return BitVectorSupport::toOctal(data(), hull());
1154  }
1155 
1162  std::string toBinary(const BitRange &range) const {
1163  return BitVectorSupport::toBinary(data(), range);
1164  }
1165 
1171  std::string toBinary() const {
1172  return BitVectorSupport::toBinary(data(), hull());
1173  }
1174 
1180  BitVector& fromInteger(const BitRange &range, boost::uint64_t value) {
1181  checkRange(range);
1182  BitVectorSupport::fromInteger(data(), range, value);
1183  return *this;
1184  }
1185 
1193  BitVector& fromInteger(boost::uint64_t value) {
1195  return *this;
1196  }
1197 
1207  BitVector& fromDecimal(const BitRange &range, const std::string &input) {
1208  checkRange(range);
1209  BitVectorSupport::fromDecimal(data(), range, input);
1210  return *this;
1211  }
1212 
1221  BitVector& fromDecimal(const std::string &input) {
1223  return *this;
1224  }
1225 
1234  BitVector& fromHex(const BitRange &range, const std::string &input) {
1235  checkRange(range);
1236  BitVectorSupport::fromHex(data(), range, input);
1237  return *this;
1238  }
1239 
1248  BitVector& fromHex(const std::string &input) {
1249  BitVectorSupport::fromHex(data(), hull(), input);
1250  return *this;
1251  }
1252 
1261  BitVector& fromOctal(const BitRange &range, const std::string &input) {
1262  checkRange(range);
1263  BitVectorSupport::fromOctal(data(), range, input);
1264  return *this;
1265  }
1266 
1275  BitVector& fromOctal(const std::string &input) {
1276  BitVectorSupport::fromOctal(data(), hull(), input);
1277  return *this;
1278  }
1279 
1288  BitVector& fromBinary(const BitRange &range, const std::string &input) {
1289  checkRange(range);
1290  BitVectorSupport::fromBinary(data(), range, input);
1291  return *this;
1292  }
1293 
1302  BitVector& fromBinary(const std::string &input) {
1303  BitVectorSupport::fromBinary(data(), hull(), input);
1304  return *this;
1305  }
1306 
1308  // Utility
1310 
1315  void checkRange(const BitRange &range) const {
1316  ASSERT_always_require(hull().isContaining(range)); // so range is always used
1317  }
1318 
1325  Word* data() {
1326  return words_.empty() ? NULL : &words_[0];
1327  }
1328 
1329  const Word* data() const {
1330  return words_.empty() ? NULL : &words_[0];
1331  }
1337  size_t dataSize() const {
1338  return words_.size();
1339  }
1340 };
1341 
1342 } // namespace
1343 } // namespace
1344 #endif
BitVector & bitwiseOr(const BitVector &other)
Bit-wise OR.
Definition: BitVector.h:955
void fromInteger(Word *words, const BitRange &range, boost::uint64_t value)
Assign an unsigned value to a bit range.
BitVector & set()
Assign true to all bits.
Definition: BitVector.h:292
static BitRange baseSize(size_t base, size_t size)
Create a bit range from a starting offset and size.
Definition: BitVector.h:232
Word * data()
Raw data for vector.
Definition: BitVector.h:1325
Optional< size_t > leastSignificantDifference(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Find least significant difference.
Definition: BitVector.h:555
bool subtract(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Subtract bits.
int compareSigned(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Compare bits as signed integers.
Definition: BitVector.h:1063
BitVector & operator=(const BitVector &other)
Assignment.
Definition: BitVector.h:175
bool decrement(Word *vec1, const BitRange &range1)
Decrement.
BitVector & fromHex(const std::string &input)
Obtain bits from a hexadecimal representation.
Definition: BitVector.h:1248
size_t nSet(const BitRange &range) const
Number of set bits.
Definition: BitVector.h:478
std::string toOctal(const Word *vec, const BitRange &range)
Octal representation.
void copy(const Word *src, const BitRange &srcRange, Word *dst, const BitRange &dstRange)
Copy some bits.
Optional< size_t > leastSignificantDifference(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Find least significant different bits.
std::string toOctal() const
Convert to an octal string.
Definition: BitVector.h:1152
bool add(const BitRange &range1, const BitRange &range2)
Add bits as integers.
Definition: BitVector.h:784
BitVector & copy(const BitRange &to, const BitVector &other, const BitRange &from)
Copy some bits.
Definition: BitVector.h:321
void fromDecimal(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a decimal representation.
BitVector & shiftRight(const BitRange &range, size_t nShift, bool newBits=0)
Shift bits right.
Definition: BitVector.h:621
BitVector(size_t nbits, bool newBits=false)
Create a vector of specified size.
Definition: BitVector.h:91
bool isAllSet(const Word *words, const BitRange &range)
True if all bits are set.
Optional< size_t > mostSignificantDifference(const BitVector &other) const
Find most significant difference.
Definition: BitVector.h:541
void fromBinary(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a binary representation.
BitVector & bitwiseAnd(const BitRange &range1, const BitVector &other, const BitRange &range2)
Bit-wise AND.
Definition: BitVector.h:901
BitVector & set(const BitRange &range)
Assign true to some bits.
Definition: BitVector.h:282
unsigned Word
Base storage type.
Definition: BitVector.h:66
void invert(Word *words, const BitRange &range)
Invert bits.
BitVector & signExtend(const BitRange &range1, const BitRange &range2)
Copy bits and sign extend.
Definition: BitVector.h:856
bool get(const Word *words, size_t idx)
Return a single bit.
BitVector & fromOctal(const std::string &input)
Obtain bits from an octal representation.
Definition: BitVector.h:1275
bool isEqualToZero() const
Compare to zero.
Definition: BitVector.h:1012
std::string toBinary(const BitRange &range) const
Convert to a binary string.
Definition: BitVector.h:1162
BitVector & fromDecimal(const BitRange &range, const std::string &input)
Obtains bits from a decimal representation.
Definition: BitVector.h:1207
BitVector & fromHex(const BitRange &range, const std::string &input)
Obtain bits from a hexadecimal representation.
Definition: BitVector.h:1234
BitVector & clear(const BitRange &range)
Assign zero to some bits.
Definition: BitVector.h:262
void checkRange(const BitRange &range) const
Assert valid range.
Definition: BitVector.h:1315
BitVector & setValue(bool value)
Assign true/false to all bits.
Definition: BitVector.h:309
int compareSigned(const BitRange &range1, const BitRange &range2) const
Compare bits as signed integers.
Definition: BitVector.h:1077
BitVector & rotateRight(size_t nShift)
Rotate bits right.
Definition: BitVector.h:682
size_t nClear() const
Number of clear bits.
Definition: BitVector.h:501
void setValue(Word *words, const BitRange &where, bool value)
Set or clear some bits.
Optional< size_t > mostSignificantClearBit(const Word *words, const BitRange &range)
Index of most significant clear bit.
BitVector & rotateRight(const BitRange &range, size_t nShift)
Rotate bits right.
Definition: BitVector.h:671
BitVector & bitwiseAnd(const BitRange &range1, const BitRange &range2)
Bit-wise AND.
Definition: BitVector.h:912
BitVector & fromBinary(const BitRange &range, const std::string &input)
Obtain bits from a binary representation.
Definition: BitVector.h:1288
bool increment(Word *vec1, const BitRange &range1)
Increment.
BitVector & fromInteger(boost::uint64_t value)
Obtain bits from an integer.
Definition: BitVector.h:1193
void negate(Word *vec1, const BitRange &range)
Negate bits as an integer.
BitVector & swap(const BitRange &range1, const BitRange &range2)
Swap some bits.
Definition: BitVector.h:356
BitVector & invert(const BitRange &range)
Invert bits.
Definition: BitVector.h:882
bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2)
Subtract bits as integers.
Definition: BitVector.h:809
BitVector & shiftRightArithmetic(const BitRange &range, size_t nShift)
Shift bits right.
Definition: BitVector.h:647
BitVector & fromDecimal(const std::string &input)
Obtain bits from a decimal representation.
Definition: BitVector.h:1221
Optional< size_t > leastSignificantClearBit() const
Find the least significant clear bit.
Definition: BitVector.h:399
static BitVector parse(std::string str)
Create a bit vector by reading a string.
Definition: BitVector.h:106
BitVector & shiftRightArithmetic(size_t nShift)
Shift bits right.
Definition: BitVector.h:661
Optional< size_t > leastSignificantDifference(const BitVector &other) const
Find least significant difference.
Definition: BitVector.h:581
void shiftRight(Word *words, const BitRange &range, size_t nShift, bool newBits=0)
Shift bits right.
BitVector & fromInteger(const BitRange &range, boost::uint64_t value)
Obtain bits from an integer.
Definition: BitVector.h:1180
Name space for the entire library.
Definition: Access.h:11
BitVector & swap(const BitRange &range1, BitVector &other, const BitRange &range2)
Swap some bits.
Definition: BitVector.h:345
BitVector()
Default construct an empty vector.
Definition: BitVector.h:83
void shiftLeft(Word *words, const BitRange &range, size_t nShift, bool newBits=0)
Shift bits left.
BitVector & negate(const BitRange &range1)
Negates bits as integer.
Definition: BitVector.h:716
Optional< size_t > leastSignificantClearBit(const Word *words, const BitRange &range)
Index of least significant zero bit.
Optional< size_t > mostSignificantClearBit() const
Find the most significant clear bit.
Definition: BitVector.h:435
BitVector & shiftRight(size_t nShift, bool newBits=0)
Shift bits right.
Definition: BitVector.h:634
static Interval baseSize(size_t lo, size_t size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:161
BitVector & signExtend(const BitVector &other)
Copy bits and sign extend.
Definition: BitVector.h:867
BitVectorSupport::BitRange BitRange
Describes an inclusive interval of bit indices.
Definition: BitVector.h:67
size_t nSet() const
Number of set bits.
Definition: BitVector.h:486
size_t size() const
Size of vector in bits.
Definition: BitVector.h:189
size_t nClear(const Word *words, const BitRange &range)
Number of clear bits.
bool decrement(const BitRange &range1)
Decrement bits as integer.
Definition: BitVector.h:754
BitVector & invert()
Invert bits.
Definition: BitVector.h:891
std::string toOctal(const BitRange &range) const
Convert to an octal string.
Definition: BitVector.h:1143
BitVector & shiftLeft(size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:609
int compare(const BitVector &other) const
Compare bits as integers.
Definition: BitVector.h:1050
size_t dataSize() const
Raw data size.
Definition: BitVector.h:1337
BitVector & bitwiseOr(const BitRange &range1, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:944
void rotateRight(Word *words, const BitRange &range, size_t nShift)
Rotate bits to the right.
void fromOctal(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from an octal representation.
BitVector & bitwiseAnd(const BitVector &other)
Bit-wise AND.
Definition: BitVector.h:923
size_t nClear(const BitRange &range) const
Number of clear bits.
Definition: BitVector.h:493
void rotateLeft(Word *words, const BitRange &range, size_t nShift)
Rotate bits to the left.
bool increment(const BitRange &range1)
Increment bits as integer.
Definition: BitVector.h:736
Optional< size_t > mostSignificantClearBit(const BitRange &range) const
Find the most significant clear bit.
Definition: BitVector.h:426
bool isAllSet(const BitRange &range) const
True if all bits are set.
Definition: BitVector.h:443
void swap(Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Swap some bits.
int compareSigned(const BitVector &other) const
Compare bits as signed integers.
Definition: BitVector.h:1090
bool subtract(const BitVector &other)
Subtract bits as integers.
Definition: BitVector.h:834
static Interval hull(size_t v1, size_t v2)
Construct an interval from two endpoints.
Definition: Interval.h:150
void shiftRightArithmetic(Word *words, const BitRange &range, size_t nShift)
Shift bits right arithmetically.
void bitwiseXor(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Bit-wise XOR.
Optional< size_t > mostSignificantSetBit() const
Find the most significant set bit.
Definition: BitVector.h:417
Optional< size_t > leastSignificantSetBit(const Word *words, const BitRange &range)
Index of least significant set bit.
BitVector & bitwiseXor(const BitRange &range1, const BitVector &other, const BitRange &range2)
Bit-wise XOR.
Definition: BitVector.h:965
std::string toHex(const Word *vec, const BitRange &range)
Hexadecimal representation.
Optional< size_t > mostSignificantDifference(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Find most significant difference.
Definition: BitVector.h:515
Optional< size_t > leastSignificantDifference(const BitRange &range1, const BitRange &range2) const
Find least significant difference.
Definition: BitVector.h:570
int compare(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Unsigned comparison.
bool subtract(const BitRange &range1, const BitRange &range2)
Subtract bits as integers.
Definition: BitVector.h:823
boost::uint64_t toInteger(const BitRange &range) const
Interpret bits as an unsigned integer.
Definition: BitVector.h:1102
Optional< size_t > mostSignificantSetBit(const Word *words, const BitRange &range)
Index of most significant set bit.
boost::uint64_t toInteger(const Word *words, const BitRange &range)
Convert a bit vector to an integer.
Optional< size_t > leastSignificantClearBit(const BitRange &range) const
Find the least significant clear bit.
Definition: BitVector.h:390
bool add(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2, bool carryIn=false)
Add bits.
bool signExtend(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Sign extend.
bool decrement()
Decrement bits as integer.
Definition: BitVector.h:763
bool isAllClear(const Word *words, const BitRange &range)
True if all bits are clear.
Optional< size_t > mostSignificantSetBit(const BitRange &range) const
Find the most significant set bit.
Definition: BitVector.h:408
BitVector(const BitVector &other)
Copy constructor.
Definition: BitVector.h:86
Optional< size_t > mostSignificantDifference(const BitRange &range1, const BitRange &range2) const
Find most significant difference.
Definition: BitVector.h:530
void fromHex(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a hexadecimal representation.
boost::uint64_t toInteger() const
Interpret bits as an unsigned integer.
Definition: BitVector.h:1111
BitVector & clear()
Assign zero to all bits.
Definition: BitVector.h:273
Optional< size_t > leastSignificantSetBit() const
Find the least significant set bit.
Definition: BitVector.h:381
int compareSigned(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Signed comparison.
BitVector & fromBinary(const std::string &input)
Obtain bits from a binary representation.
Definition: BitVector.h:1302
void clear(Word *words, const BitRange &where)
Clear some bits.
BitVector & signExtend(const BitRange &range1, const BitVector &other, const BitRange &range2)
Copy bits and sign extend.
Definition: BitVector.h:844
BitVector & rotateLeft(const BitRange &range, size_t nShift)
Rotate bits left.
Definition: BitVector.h:692
bool add(const BitRange &range1, const BitVector &other, const BitRange &range2)
Add bits as integers.
Definition: BitVector.h:773
BitVector & bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:933
const Word * data() const
Raw data for vector.
Definition: BitVector.h:1329
void set(Word *words, const BitRange &where)
Set some bits.
bool isEqualToZero(const BitRange &range) const
Compare to zero.
Definition: BitVector.h:1002
Optional< size_t > leastSignificantSetBit(const BitRange &range) const
Find the least significant set bit.
Definition: BitVector.h:372
void bitwiseAnd(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Bit-wise AND.
int compare(const BitRange &range1, const BitRange &range2) const
Compare bits as integers.
Definition: BitVector.h:1037
BitVector & setValue(const BitRange &range, bool value)
Assign true/false to some bits.
Definition: BitVector.h:300
BitRange hull() const
Interval representing the entire vector.
Definition: BitVector.h:224
bool isEmpty() const
Determines if the vector is empty.
Definition: BitVector.h:184
BitVector & fromOctal(const BitRange &range, const std::string &input)
Obtain bits from an octal representation.
Definition: BitVector.h:1261
BitVector & shiftLeft(const BitRange &range, size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:596
std::string toBinary(const Word *vec, const BitRange &range)
Binary representation.
BitVector & rotateLeft(size_t nShift)
Rotate bits left.
Definition: BitVector.h:703
BitVector & bitwiseXor(const BitVector &other)
Bit-wise XOR.
Definition: BitVector.h:987
BitVector & bitwiseXor(const BitRange &range1, const BitRange &range2)
Bit-wise XOR.
Definition: BitVector.h:976
int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Compare bits as integers.
Definition: BitVector.h:1024
bool isAllSet() const
True if all bits are set.
Definition: BitVector.h:451
static BitRange hull(size_t minOffset, size_t maxOffset)
Create a bit range from min and max positions.
Definition: BitVector.h:240
std::string toBinary() const
Convert to an binary string.
Definition: BitVector.h:1171
size_t nSet(const Word *words, const BitRange &range)
Number of set bits.
BitVector & negate()
Negates bits as integer.
Definition: BitVector.h:726
bool isEqualToZero(const Word *vec1, const BitRange &range1)
Compares with zero.
void bitwiseOr(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Bit-wise OR.
bool add(const BitVector &other)
Add bits as integers.
Definition: BitVector.h:796
BitVector & resize(size_t newSize, bool newBits=false)
Change vector size.
Definition: BitVector.h:196
bool isAllClear() const
True if all bits are clear.
Definition: BitVector.h:471
bool isAllClear(const BitRange &range) const
True if all bits are clear.
Definition: BitVector.h:461
BitVector & copy(const BitRange &to, const BitRange &from)
Copy some bits.
Definition: BitVector.h:333
bool increment()
Increment bits as integer.
Definition: BitVector.h:745
Optional< size_t > mostSignificantDifference(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Find most significant different bits.
std::string toHex(const BitRange &range) const
Convert to a hexadecimal string.
Definition: BitVector.h:1123
size_t capacity() const
Maximum size before reallocation.
Definition: BitVector.h:217
std::string toHex() const
Convert to a hexadecimal string.
Definition: BitVector.h:1133