ROSE  0.11.2.0
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  const Word* theData = data();
255  assert(theData != NULL);
256  return BitVectorSupport::get(theData, idx);
257  }
258 
264  BitVector& clear(const BitRange &range) {
265  checkRange(range);
266  BitVectorSupport::clear(data(), range);
267  return *this;
268  }
269 
277  return *this;
278  }
279 
284  BitVector& set(const BitRange &range) {
285  checkRange(range);
286  BitVectorSupport::set(data(), range);
287  return *this;
288  }
289 
296  return *this;
297  }
298 
302  BitVector& setValue(const BitRange &range, bool value) {
303  checkRange(range);
304  BitVectorSupport::setValue(data(), range, value);
305  return *this;
306  }
307 
311  BitVector& setValue(bool value) {
312  BitVectorSupport::setValue(data(), hull(), value);
313  return *this;
314  }
315 
323  BitVector& copy(const BitRange &to, const BitVector &other, const BitRange &from) {
324  checkRange(to);
325  other.checkRange(from);
326  BitVectorSupport::copy(other.data(), from, data(), to);
327  return *this;
328  }
329 
335  BitVector& copy(const BitRange &to, const BitRange &from) {
336  checkRange(to);
337  checkRange(from);
338  BitVectorSupport::copy(data(), from, data(), to);
339  return *this;
340  }
341 
347  BitVector& swap(const BitRange &range1, BitVector &other, const BitRange &range2) {
348  checkRange(range1);
349  other.checkRange(range2);
350  BitVectorSupport::swap(data(), range1, other.data(), range2);
351  return *this;
352  }
353 
358  BitVector& swap(const BitRange &range1, const BitRange &range2) {
359  checkRange(range1);
360  checkRange(range2);
361  BitVectorSupport::swap(data(), range1, data(), range2);
362  return *this;
363  }
364 
368  bool equalTo(const BitRange &range1, BitVector &other, const BitRange &range2) const {
369  checkRange(range1);
370  other.checkRange(range2);
371  return BitVectorSupport::equalTo(data(), range1, other.data(), range2);
372  }
373 
378  bool equalTo(const BitRange &range1, const BitRange &range2) const {
379  checkRange(range1);
380  checkRange(range2);
381  return BitVectorSupport::equalTo(data(), range1, data(), range2);
382  }
383 
388  bool equalTo(const BitVector &other) const {
389  if (size() != other.size())
390  return false;
391  return BitVectorSupport::equalTo(data(), hull(), other.data(), other.hull());
392  }
393 
395  // Counting/searching
397 
403  Optional<size_t> leastSignificantSetBit(const BitRange &range) const {
404  checkRange(range);
406  }
407 
414  }
415 
421  Optional<size_t> leastSignificantClearBit(const BitRange &range) const {
422  checkRange(range);
424  }
425 
432  }
433 
439  Optional<size_t> mostSignificantSetBit(const BitRange &range) const {
440  checkRange(range);
442  }
443 
450  }
451 
457  Optional<size_t> mostSignificantClearBit(const BitRange &range) const {
458  checkRange(range);
460  }
461 
468  }
469 
474  bool isAllSet(const BitRange &range) const {
475  checkRange(range);
476  return BitVectorSupport::isAllSet(data(), range);
477  }
478 
482  bool isAllSet() const {
483  return BitVectorSupport::isAllSet(data(), hull());
484  }
485 
492  bool isAllClear(const BitRange &range) const {
493  checkRange(range);
494  return BitVectorSupport::isAllClear(data(), range);
495  }
496 
502  bool isAllClear() const {
504  }
505 
509  size_t nSet(const BitRange &range) const {
510  checkRange(range);
511  return BitVectorSupport::nSet(data(), range);
512  }
513 
517  size_t nSet() const {
518  return BitVectorSupport::nSet(data(), hull());
519  }
520 
524  size_t nClear(const BitRange &range) const {
525  checkRange(range);
526  return BitVectorSupport::nClear(data(), range);
527  }
528 
532  size_t nClear() const {
533  return BitVectorSupport::nClear(data(), hull());
534  }
535 
546  Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitVector &other,
547  const BitRange &range2) const {
548  checkRange(range1);
549  other.checkRange(range2);
550  return BitVectorSupport::mostSignificantDifference(data(), range1, other.data(), range2);
551  }
552 
561  Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitRange &range2) const {
562  checkRange(range1);
563  checkRange(range2);
564  return BitVectorSupport::mostSignificantDifference(data(), range1, data(), range2);
565  }
566 
573  return BitVectorSupport::mostSignificantDifference(data(), hull(), other.data(), other.hull());
574  }
575 
586  Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitVector &other,
587  const BitRange &range2) const {
588  checkRange(range1);
589  other.checkRange(range2);
590  return BitVectorSupport::leastSignificantDifference(data(), range1, other.data(), range2);
591  }
592 
601  Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitRange &range2) const {
602  checkRange(range1);
603  checkRange(range2);
604  return BitVectorSupport::leastSignificantDifference(data(), range1, data(), range2);
605  }
606 
613  return BitVectorSupport::leastSignificantDifference(data(), hull(), other.data(), other.hull());
614  }
615 
617  // Shift/rotate
619 
627  BitVector& shiftLeft(const BitRange &range, size_t nShift, bool newBits = 0) {
628  checkRange(range);
629  BitVectorSupport::shiftLeft(data(), range, nShift, newBits);
630  return *this;
631  }
632 
640  BitVector& shiftLeft(size_t nShift, bool newBits = 0) {
641  BitVectorSupport::shiftLeft(data(), hull(), nShift, newBits);
642  return *this;
643  }
644 
652  BitVector& shiftRight(const BitRange &range, size_t nShift, bool newBits = 0) {
653  checkRange(range);
654  BitVectorSupport::shiftRight(data(), range, nShift, newBits);
655  return *this;
656  }
657 
665  BitVector& shiftRight(size_t nShift, bool newBits = 0) {
666  BitVectorSupport::shiftRight(data(), hull(), nShift, newBits);
667  return *this;
668  }
669 
678  BitVector& shiftRightArithmetic(const BitRange &range, size_t nShift) {
679  checkRange(range);
681  return *this;
682  }
683 
692  BitVector& shiftRightArithmetic(size_t nShift) {
694  return *this;
695  }
696 
702  BitVector& rotateRight(const BitRange &range, size_t nShift) {
703  checkRange(range);
704  BitVectorSupport::rotateRight(data(), range, nShift);
705  return *this;
706  }
707 
713  BitVector& rotateRight(size_t nShift) {
715  return *this;
716  }
717 
723  BitVector& rotateLeft(const BitRange &range, size_t nShift) {
724  checkRange(range);
725  BitVectorSupport::rotateLeft(data(), range, nShift);
726  return *this;
727  }
728 
734  BitVector& rotateLeft(size_t nShift) {
735  BitVectorSupport::rotateLeft(data(), hull(), nShift);
736  return *this;
737  }
738 
740  // Arithmetic
742 
747  BitVector& negate(const BitRange &range1) {
748  checkRange(range1);
749  BitVectorSupport::negate(data(), range1);
750  return *this;
751  }
752 
759  return *this;
760  }
761 
767  bool increment(const BitRange &range1) {
768  checkRange(range1);
769  return BitVectorSupport::increment(data(), range1);
770  }
771 
776  bool increment() {
778  }
779 
785  bool decrement(const BitRange &range1) {
786  checkRange(range1);
787  return BitVectorSupport::decrement(data(), range1);
788  }
789 
794  bool decrement() {
796  }
797 
804  bool add(const BitRange &range1, const BitVector &other, const BitRange &range2) {
805  checkRange(range1);
806  other.checkRange(range2);
807  return BitVectorSupport::add(other.data(), range2, data(), range1, false);
808  }
809 
815  bool add(const BitRange &range1, const BitRange &range2) {
816  checkRange(range1);
817  checkRange(range2);
818  return BitVectorSupport::add(data(), range2, data(), range1, false);
819  }
820 
827  bool add(const BitVector &other) {
828  return BitVectorSupport::add(other.data(), other.hull(), data(), hull(), false);
829  }
830 
840  bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2) {
841  checkRange(range1);
842  other.checkRange(range2);
843  return BitVectorSupport::subtract(other.data(), range2, data(), range1);
844  }
845 
854  bool subtract(const BitRange &range1, const BitRange &range2) {
855  checkRange(range1);
856  checkRange(range2);
857  return BitVectorSupport::subtract(data(), range2, data(), range1);
858  }
859 
865  bool subtract(const BitVector &other) {
866  return BitVectorSupport::subtract(other.data(), other.hull(), data(), hull());
867  }
868 
875  BitVector& signExtend(const BitRange &range1, const BitVector &other, const BitRange &range2) {
876  checkRange(range1);
877  other.checkRange(range2);
878  BitVectorSupport::signExtend(other.data(), range2, data(), range1);
879  return *this;
880  }
881 
887  BitVector& signExtend(const BitRange &range1, const BitRange &range2) {
888  checkRange(range1);
889  checkRange(range2);
890  BitVectorSupport::signExtend(data(), range2, data(), range1);
891  return *this;
892  }
893 
898  BitVector& signExtend(const BitVector &other) {
899  BitVectorSupport::signExtend(other.data(), other.hull(), data(), hull());
900  return *this;
901  }
902 
909  return *this;
910  }
911 
916  BitVector& multiply10(const BitRange &range) {
918  return *this;
919  }
920 
925  BitVector multiply(const BitVector &other) const {
926  BitVector product(size() + other.size());
927  BitVector addend = other;
928  addend.resize(product.size());
929  for (size_t i = 0; i < size(); ++i) {
930  if (get(i))
931  product.add(addend);
932  addend.shiftLeft(1);
933  }
934  return product;
935  }
936 
941  BitVector multiplySigned(const BitVector &other) const {
942  // Unoptimized version using simple elementary school long multiply. The Wikipedia "Binary multiplier" article has a good
943  // description of a more optimized approach.
944  BitVector product(size() + other.size());
945 
946  // Absolute value of A
947  BitVector a = *this;
948  bool aIsNeg = false;
949  if (a.size() > 1 && a.get(a.size()-1)) {
950  aIsNeg = true;
951  a.negate();
952  }
953 
954  // Absolute value of B, and extended to result width
955  BitVector b = other;
956  bool bIsNeg = false;
957  if (b.size() > 1 && b.get(b.size()-1)) {
958  bIsNeg = true;
959  b.negate();
960  }
961  b.resize(product.size());
962 
963  // Long multiplication
964  for (size_t i = 0; i < a.size(); ++i) {
965  if (a.get(i))
966  product.add(b);
967  b.shiftLeft(1);
968  }
969 
970  // Correct the result sign
971  if (aIsNeg != bIsNeg)
972  product.negate();
973 
974  return product;
975  }
976 
977  // FIXME[Robb Matzke 2014-05-01]: we should also have zeroExtend, which is like copy but allows the source and destination
978  // to be different sizes.
979 
981  // Bit-wise Boolean logic
983 
987  BitVector& invert(const BitRange &range) {
988  checkRange(range);
989  BitVectorSupport::invert(data(), range);
990  return *this;
991  }
992 
998  return *this;
999  }
1000 
1006  BitVector& bitwiseAnd(const BitRange &range1, const BitVector &other, const BitRange &range2) {
1007  checkRange(range1);
1008  other.checkRange(range2);
1009  BitVectorSupport::bitwiseAnd(other.data(), range2, data(), range1);
1010  return *this;
1011  }
1012 
1017  BitVector& bitwiseAnd(const BitRange &range1, const BitRange &range2) {
1018  checkRange(range1);
1019  checkRange(range2);
1020  BitVectorSupport::bitwiseAnd(data(), range2, data(), range1);
1021  return *this;
1022  }
1023 
1028  BitVector& bitwiseAnd(const BitVector &other) {
1029  BitVectorSupport::bitwiseAnd(other.data(), other.hull(), data(), hull());
1030  return *this;
1031  }
1032 
1038  BitVector& bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2) {
1039  checkRange(range1);
1040  other.checkRange(range2);
1041  BitVectorSupport::bitwiseOr(other.data(), range2, data(), range1);
1042  return *this;
1043  }
1044 
1049  BitVector& bitwiseOr(const BitRange &range1, const BitRange &range2) {
1050  checkRange(range1);
1051  checkRange(range2);
1052  BitVectorSupport::bitwiseOr(data(), range2, data(), range1);
1053  return *this;
1054  }
1055 
1060  BitVector& bitwiseOr(const BitVector &other) {
1061  BitVectorSupport::bitwiseOr(other.data(), other.hull(), data(), hull());
1062  return *this;
1063  }
1064 
1070  BitVector& bitwiseXor(const BitRange &range1, const BitVector &other, const BitRange &range2) {
1071  checkRange(range1);
1072  other.checkRange(range2);
1073  BitVectorSupport::bitwiseXor(other.data(), range2, data(), range1);
1074  return *this;
1075  }
1076 
1081  BitVector& bitwiseXor(const BitRange &range1, const BitRange &range2) {
1082  checkRange(range1);
1083  checkRange(range2);
1084  BitVectorSupport::bitwiseXor(data(), range2, data(), range1);
1085  return *this;
1086  }
1087 
1092  BitVector& bitwiseXor(const BitVector &other) {
1093  BitVectorSupport::bitwiseXor(other.data(), other.hull(), data(), hull());
1094  return *this;
1095  }
1096 
1098  // Numeric comparisons
1100 
1107  bool isEqualToZero(const BitRange &range) const {
1108  checkRange(range);
1109  return BitVectorSupport::isEqualToZero(data(), range);
1110  }
1111 
1117  bool isEqualToZero() const {
1119  }
1120 
1129  int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1130  checkRange(range1);
1131  other.checkRange(range2);
1132  return BitVectorSupport::compare(data(), range1, other.data(), range2);
1133  }
1134 
1142  int compare(const BitRange &range1, const BitRange &range2) const {
1143  checkRange(range1);
1144  checkRange(range2);
1145  return BitVectorSupport::compare(data(), range1, data(), range2);
1146  }
1147 
1155  int compare(const BitVector &other) const {
1156  return BitVectorSupport::compare(data(), hull(), other.data(), other.hull());
1157  }
1158 
1168  int compareSigned(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1169  checkRange(range1);
1170  other.checkRange(range2);
1171  return BitVectorSupport::compareSigned(data(), range1, other.data(), range2);
1172  }
1173 
1182  int compareSigned(const BitRange &range1, const BitRange &range2) const {
1183  checkRange(range1);
1184  checkRange(range2);
1185  return BitVectorSupport::compareSigned(data(), range1, data(), range2);
1186  }
1187 
1195  int compareSigned(const BitVector &other) const {
1196  return BitVectorSupport::compareSigned(data(), hull(), other.data(), other.hull());
1197  }
1198 
1200  // Conversion
1202 
1207  boost::uint64_t toInteger(const BitRange &range) const {
1208  checkRange(range);
1209  return BitVectorSupport::toInteger(data(), range);
1210  }
1211 
1216  boost::uint64_t toInteger() const {
1217  if (size() <= 64)
1218  return BitVectorSupport::toInteger(data(), size());
1219  return BitVectorSupport::toInteger(data(), hull());
1220  }
1221 
1228  boost::int64_t toSignedInteger(const BitRange &range) const {
1229  checkRange(range);
1230  return BitVectorSupport::toInteger(data(), range);
1231  }
1232 
1239  boost::int64_t toSignedInteger() const {
1240  if (size() <= 64)
1243  }
1244 
1251  std::string toHex(const BitRange &range) const {
1252  return BitVectorSupport::toHex(data(), range);
1253  }
1254 
1261  std::string toHex() const {
1262  return BitVectorSupport::toHex(data(), hull());
1263  }
1264 
1271  std::string toOctal(const BitRange &range) const {
1272  return BitVectorSupport::toOctal(data(), range);
1273  }
1274 
1280  std::string toOctal() const {
1281  return BitVectorSupport::toOctal(data(), hull());
1282  }
1283 
1290  std::string toBinary(const BitRange &range) const {
1291  return BitVectorSupport::toBinary(data(), range);
1292  }
1293 
1299  std::string toBinary() const {
1300  return BitVectorSupport::toBinary(data(), hull());
1301  }
1302 
1308  BitVector& fromInteger(const BitRange &range, boost::uint64_t value) {
1309  checkRange(range);
1310  BitVectorSupport::fromInteger(data(), range, value);
1311  return *this;
1312  }
1313 
1321  BitVector& fromInteger(boost::uint64_t value) {
1323  return *this;
1324  }
1325 
1335  BitVector& fromDecimal(const BitRange &range, const std::string &input) {
1336  checkRange(range);
1337  BitVectorSupport::fromDecimal(data(), range, input);
1338  return *this;
1339  }
1340 
1349  BitVector& fromDecimal(const std::string &input) {
1351  return *this;
1352  }
1353 
1362  BitVector& fromHex(const BitRange &range, const std::string &input) {
1363  checkRange(range);
1364  BitVectorSupport::fromHex(data(), range, input);
1365  return *this;
1366  }
1367 
1376  BitVector& fromHex(const std::string &input) {
1377  BitVectorSupport::fromHex(data(), hull(), input);
1378  return *this;
1379  }
1380 
1389  BitVector& fromOctal(const BitRange &range, const std::string &input) {
1390  checkRange(range);
1391  BitVectorSupport::fromOctal(data(), range, input);
1392  return *this;
1393  }
1394 
1403  BitVector& fromOctal(const std::string &input) {
1404  BitVectorSupport::fromOctal(data(), hull(), input);
1405  return *this;
1406  }
1407 
1416  BitVector& fromBinary(const BitRange &range, const std::string &input) {
1417  checkRange(range);
1418  BitVectorSupport::fromBinary(data(), range, input);
1419  return *this;
1420  }
1421 
1430  BitVector& fromBinary(const std::string &input) {
1431  BitVectorSupport::fromBinary(data(), hull(), input);
1432  return *this;
1433  }
1434 
1436  // Utility
1438 
1443  void checkRange(const BitRange &range) const {
1444  ASSERT_always_require(hull().isContaining(range)); // so range is always used
1445  }
1446 
1453  Word* data() {
1454  return words_.empty() ? NULL : &words_[0];
1455  }
1456 
1457  const Word* data() const {
1458  return words_.empty() ? NULL : &words_[0];
1459  }
1465  size_t dataSize() const {
1466  return words_.size();
1467  }
1468 };
1469 
1470 } // namespace
1471 } // namespace
1472 #endif
bool equalTo(const BitRange &range1, BitVector &other, const BitRange &range2) const
Checks whether two ranges are equal.
Definition: BitVector.h:368
BitVector & bitwiseOr(const BitVector &other)
Bit-wise OR.
Definition: BitVector.h:1060
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:294
bool equalTo(const BitVector &other) const
Checks whether the bits of one vector are equal to the bits of the other.
Definition: BitVector.h:388
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:1453
boost::int64_t toSignedInteger(const Word *words, const BitRange &range)
Convert a bit vector to a signed integer.
Optional< size_t > leastSignificantDifference(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Find least significant difference.
Definition: BitVector.h:586
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:1168
BitVector & operator=(const BitVector &other)
Assignment.
Definition: BitVector.h:175
bool decrement(Word *vec1, const BitRange &range1)
Decrement.
boost::int64_t toSignedInteger() const
Interpret bits as a signed integer.
Definition: BitVector.h:1239
bool equalTo(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Compare bits for equality.
BitVector & fromHex(const std::string &input)
Obtain bits from a hexadecimal representation.
Definition: BitVector.h:1376
size_t nSet(const BitRange &range) const
Number of set bits.
Definition: BitVector.h:509
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:1280
bool add(const BitRange &range1, const BitRange &range2)
Add bits as integers.
Definition: BitVector.h:815
BitVector & copy(const BitRange &to, const BitVector &other, const BitRange &from)
Copy some bits.
Definition: BitVector.h:323
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:652
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:572
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:1006
BitVector & set(const BitRange &range)
Assign true to some bits.
Definition: BitVector.h:284
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:887
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:1403
bool isEqualToZero() const
Compare to zero.
Definition: BitVector.h:1117
std::string toBinary(const BitRange &range) const
Convert to a binary string.
Definition: BitVector.h:1290
BitVector & fromDecimal(const BitRange &range, const std::string &input)
Obtains bits from a decimal representation.
Definition: BitVector.h:1335
BitVector & fromHex(const BitRange &range, const std::string &input)
Obtain bits from a hexadecimal representation.
Definition: BitVector.h:1362
BitVector & clear(const BitRange &range)
Assign zero to some bits.
Definition: BitVector.h:264
void checkRange(const BitRange &range) const
Assert valid range.
Definition: BitVector.h:1443
BitVector & setValue(bool value)
Assign true/false to all bits.
Definition: BitVector.h:311
int compareSigned(const BitRange &range1, const BitRange &range2) const
Compare bits as signed integers.
Definition: BitVector.h:1182
BitVector & rotateRight(size_t nShift)
Rotate bits right.
Definition: BitVector.h:713
size_t nClear() const
Number of clear bits.
Definition: BitVector.h:532
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:702
bool get(size_t idx) const
Retrieve one bit.
Definition: BitVector.h:252
BitVector & bitwiseAnd(const BitRange &range1, const BitRange &range2)
Bit-wise AND.
Definition: BitVector.h:1017
boost::int64_t toSignedInteger(const BitRange &range) const
Interpret bits as a signed integer.
Definition: BitVector.h:1228
BitVector & fromBinary(const BitRange &range, const std::string &input)
Obtain bits from a binary representation.
Definition: BitVector.h:1416
bool increment(Word *vec1, const BitRange &range1)
Increment.
BitVector & multiply10()
Multiply by 10.
Definition: BitVector.h:907
BitVector & fromInteger(boost::uint64_t value)
Obtain bits from an integer.
Definition: BitVector.h:1321
BitVector multiplySigned(const BitVector &other) const
Multiply two signed integers.
Definition: BitVector.h:941
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:358
BitVector & invert(const BitRange &range)
Invert bits.
Definition: BitVector.h:987
bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2)
Subtract bits as integers.
Definition: BitVector.h:840
BitVector & shiftRightArithmetic(const BitRange &range, size_t nShift)
Shift bits right.
Definition: BitVector.h:678
BitVector & fromDecimal(const std::string &input)
Obtain bits from a decimal representation.
Definition: BitVector.h:1349
Optional< size_t > leastSignificantClearBit() const
Find the least significant clear bit.
Definition: BitVector.h:430
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:692
Optional< size_t > leastSignificantDifference(const BitVector &other) const
Find least significant difference.
Definition: BitVector.h:612
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:1308
Name space for the entire library.
BitVector & swap(const BitRange &range1, BitVector &other, const BitRange &range2)
Swap some bits.
Definition: BitVector.h:347
BitVector & multiply10(const BitRange &range)
Multiply by 10.
Definition: BitVector.h:916
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:747
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:466
BitVector & shiftRight(size_t nShift, bool newBits=0)
Shift bits right.
Definition: BitVector.h:665
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:898
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:517
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:785
BitVector & invert()
Invert bits.
Definition: BitVector.h:996
std::string toOctal(const BitRange &range) const
Convert to an octal string.
Definition: BitVector.h:1271
BitVector & shiftLeft(size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:640
int compare(const BitVector &other) const
Compare bits as integers.
Definition: BitVector.h:1155
size_t dataSize() const
Raw data size.
Definition: BitVector.h:1465
BitVector & bitwiseOr(const BitRange &range1, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:1049
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:1028
size_t nClear(const BitRange &range) const
Number of clear bits.
Definition: BitVector.h:524
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:767
Optional< size_t > mostSignificantClearBit(const BitRange &range) const
Find the most significant clear bit.
Definition: BitVector.h:457
bool isAllSet(const BitRange &range) const
True if all bits are set.
Definition: BitVector.h:474
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:1195
bool subtract(const BitVector &other)
Subtract bits as integers.
Definition: BitVector.h:865
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:448
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:1070
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:546
Optional< size_t > leastSignificantDifference(const BitRange &range1, const BitRange &range2) const
Find least significant difference.
Definition: BitVector.h:601
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:854
boost::uint64_t toInteger(const BitRange &range) const
Interpret bits as an unsigned integer.
Definition: BitVector.h:1207
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:421
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:794
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:439
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:561
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:1216
BitVector & clear()
Assign zero to all bits.
Definition: BitVector.h:275
Optional< size_t > leastSignificantSetBit() const
Find the least significant set bit.
Definition: BitVector.h:412
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:1430
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:875
BitVector & rotateLeft(const BitRange &range, size_t nShift)
Rotate bits left.
Definition: BitVector.h:723
bool add(const BitRange &range1, const BitVector &other, const BitRange &range2)
Add bits as integers.
Definition: BitVector.h:804
BitVector & bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:1038
const Word * data() const
Raw data for vector.
Definition: BitVector.h:1457
void set(Word *words, const BitRange &where)
Set some bits.
bool isEqualToZero(const BitRange &range) const
Compare to zero.
Definition: BitVector.h:1107
Optional< size_t > leastSignificantSetBit(const BitRange &range) const
Find the least significant set bit.
Definition: BitVector.h:403
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:1142
BitVector & setValue(const BitRange &range, bool value)
Assign true/false to some bits.
Definition: BitVector.h:302
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:1389
BitVector & shiftLeft(const BitRange &range, size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:627
std::string toBinary(const Word *vec, const BitRange &range)
Binary representation.
BitVector & rotateLeft(size_t nShift)
Rotate bits left.
Definition: BitVector.h:734
BitVector & bitwiseXor(const BitVector &other)
Bit-wise XOR.
Definition: BitVector.h:1092
BitVector & bitwiseXor(const BitRange &range1, const BitRange &range2)
Bit-wise XOR.
Definition: BitVector.h:1081
int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Compare bits as integers.
Definition: BitVector.h:1129
bool isAllSet() const
True if all bits are set.
Definition: BitVector.h:482
void multiply10(Word *vec, const BitRange &range)
Multiply by 10.
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:1299
size_t nSet(const Word *words, const BitRange &range)
Number of set bits.
BitVector & negate()
Negates bits as integer.
Definition: BitVector.h:757
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:827
bool equalTo(const BitRange &range1, const BitRange &range2) const
Checks whether the bits of two ranges are equal.
Definition: BitVector.h:378
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:502
bool isAllClear(const BitRange &range) const
True if all bits are clear.
Definition: BitVector.h:492
BitVector & copy(const BitRange &to, const BitRange &from)
Copy some bits.
Definition: BitVector.h:335
bool increment()
Increment bits as integer.
Definition: BitVector.h:776
BitVector multiply(const BitVector &other) const
Multiply two bit vectors.
Definition: BitVector.h:925
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:1251
size_t capacity() const
Maximum size before reallocation.
Definition: BitVector.h:217
std::string toHex() const
Convert to a hexadecimal string.
Definition: BitVector.h:1261