ROSE  0.11.145.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  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 
366  bool equalTo(const BitRange &range1, BitVector &other, const BitRange &range2) const {
367  checkRange(range1);
368  other.checkRange(range2);
369  return BitVectorSupport::equalTo(data(), range1, other.data(), range2);
370  }
371 
376  bool equalTo(const BitRange &range1, const BitRange &range2) const {
377  checkRange(range1);
378  checkRange(range2);
379  return BitVectorSupport::equalTo(data(), range1, data(), range2);
380  }
381 
386  bool equalTo(const BitVector &other) const {
387  if (size() != other.size())
388  return false;
389  return BitVectorSupport::equalTo(data(), hull(), other.data(), other.hull());
390  }
391 
393  // Counting/searching
395 
401  Optional<size_t> leastSignificantSetBit(const BitRange &range) const {
402  checkRange(range);
404  }
405 
412  }
413 
419  Optional<size_t> leastSignificantClearBit(const BitRange &range) const {
420  checkRange(range);
422  }
423 
430  }
431 
437  Optional<size_t> mostSignificantSetBit(const BitRange &range) const {
438  checkRange(range);
440  }
441 
448  }
449 
455  Optional<size_t> mostSignificantClearBit(const BitRange &range) const {
456  checkRange(range);
458  }
459 
466  }
467 
472  bool isAllSet(const BitRange &range) const {
473  checkRange(range);
474  return BitVectorSupport::isAllSet(data(), range);
475  }
476 
480  bool isAllSet() const {
481  return BitVectorSupport::isAllSet(data(), hull());
482  }
483 
490  bool isAllClear(const BitRange &range) const {
491  checkRange(range);
492  return BitVectorSupport::isAllClear(data(), range);
493  }
494 
500  bool isAllClear() const {
502  }
503 
507  size_t nSet(const BitRange &range) const {
508  checkRange(range);
509  return BitVectorSupport::nSet(data(), range);
510  }
511 
515  size_t nSet() const {
516  return BitVectorSupport::nSet(data(), hull());
517  }
518 
522  size_t nClear(const BitRange &range) const {
523  checkRange(range);
524  return BitVectorSupport::nClear(data(), range);
525  }
526 
530  size_t nClear() const {
531  return BitVectorSupport::nClear(data(), hull());
532  }
533 
544  Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitVector &other,
545  const BitRange &range2) const {
546  checkRange(range1);
547  other.checkRange(range2);
548  return BitVectorSupport::mostSignificantDifference(data(), range1, other.data(), range2);
549  }
550 
559  Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitRange &range2) const {
560  checkRange(range1);
561  checkRange(range2);
562  return BitVectorSupport::mostSignificantDifference(data(), range1, data(), range2);
563  }
564 
571  return BitVectorSupport::mostSignificantDifference(data(), hull(), other.data(), other.hull());
572  }
573 
584  Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitVector &other,
585  const BitRange &range2) const {
586  checkRange(range1);
587  other.checkRange(range2);
588  return BitVectorSupport::leastSignificantDifference(data(), range1, other.data(), range2);
589  }
590 
599  Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitRange &range2) const {
600  checkRange(range1);
601  checkRange(range2);
602  return BitVectorSupport::leastSignificantDifference(data(), range1, data(), range2);
603  }
604 
611  return BitVectorSupport::leastSignificantDifference(data(), hull(), other.data(), other.hull());
612  }
613 
615  // Shift/rotate
617 
625  BitVector& shiftLeft(const BitRange &range, size_t nShift, bool newBits = 0) {
626  checkRange(range);
627  BitVectorSupport::shiftLeft(data(), range, nShift, newBits);
628  return *this;
629  }
630 
638  BitVector& shiftLeft(size_t nShift, bool newBits = 0) {
639  BitVectorSupport::shiftLeft(data(), hull(), nShift, newBits);
640  return *this;
641  }
642 
650  BitVector& shiftRight(const BitRange &range, size_t nShift, bool newBits = 0) {
651  checkRange(range);
652  BitVectorSupport::shiftRight(data(), range, nShift, newBits);
653  return *this;
654  }
655 
663  BitVector& shiftRight(size_t nShift, bool newBits = 0) {
664  BitVectorSupport::shiftRight(data(), hull(), nShift, newBits);
665  return *this;
666  }
667 
676  BitVector& shiftRightArithmetic(const BitRange &range, size_t nShift) {
677  checkRange(range);
679  return *this;
680  }
681 
690  BitVector& shiftRightArithmetic(size_t nShift) {
692  return *this;
693  }
694 
700  BitVector& rotateRight(const BitRange &range, size_t nShift) {
701  checkRange(range);
702  BitVectorSupport::rotateRight(data(), range, nShift);
703  return *this;
704  }
705 
711  BitVector& rotateRight(size_t nShift) {
713  return *this;
714  }
715 
721  BitVector& rotateLeft(const BitRange &range, size_t nShift) {
722  checkRange(range);
723  BitVectorSupport::rotateLeft(data(), range, nShift);
724  return *this;
725  }
726 
732  BitVector& rotateLeft(size_t nShift) {
733  BitVectorSupport::rotateLeft(data(), hull(), nShift);
734  return *this;
735  }
736 
738  // Arithmetic
740 
745  BitVector& negate(const BitRange &range1) {
746  checkRange(range1);
747  BitVectorSupport::negate(data(), range1);
748  return *this;
749  }
750 
757  return *this;
758  }
759 
765  bool increment(const BitRange &range1) {
766  checkRange(range1);
767  return BitVectorSupport::increment(data(), range1);
768  }
769 
774  bool increment() {
776  }
777 
783  bool decrement(const BitRange &range1) {
784  checkRange(range1);
785  return BitVectorSupport::decrement(data(), range1);
786  }
787 
792  bool decrement() {
794  }
795 
802  bool add(const BitRange &range1, const BitVector &other, const BitRange &range2) {
803  checkRange(range1);
804  other.checkRange(range2);
805  return BitVectorSupport::add(other.data(), range2, data(), range1, false);
806  }
807 
813  bool add(const BitRange &range1, const BitRange &range2) {
814  checkRange(range1);
815  checkRange(range2);
816  return BitVectorSupport::add(data(), range2, data(), range1, false);
817  }
818 
825  bool add(const BitVector &other) {
826  return BitVectorSupport::add(other.data(), other.hull(), data(), hull(), false);
827  }
828 
838  bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2) {
839  checkRange(range1);
840  other.checkRange(range2);
841  return BitVectorSupport::subtract(other.data(), range2, data(), range1);
842  }
843 
852  bool subtract(const BitRange &range1, const BitRange &range2) {
853  checkRange(range1);
854  checkRange(range2);
855  return BitVectorSupport::subtract(data(), range2, data(), range1);
856  }
857 
863  bool subtract(const BitVector &other) {
864  return BitVectorSupport::subtract(other.data(), other.hull(), data(), hull());
865  }
866 
873  BitVector& signExtend(const BitRange &range1, const BitVector &other, const BitRange &range2) {
874  checkRange(range1);
875  other.checkRange(range2);
876  BitVectorSupport::signExtend(other.data(), range2, data(), range1);
877  return *this;
878  }
879 
885  BitVector& signExtend(const BitRange &range1, const BitRange &range2) {
886  checkRange(range1);
887  checkRange(range2);
888  BitVectorSupport::signExtend(data(), range2, data(), range1);
889  return *this;
890  }
891 
896  BitVector& signExtend(const BitVector &other) {
897  BitVectorSupport::signExtend(other.data(), other.hull(), data(), hull());
898  return *this;
899  }
900 
907  return *this;
908  }
909 
914  BitVector& multiply10(const BitRange &range) {
916  return *this;
917  }
918 
923  BitVector multiply(const BitVector &other) const {
924  BitVector product(size() + other.size());
925  BitVector addend = other;
926  addend.resize(product.size());
927  for (size_t i = 0; i < size(); ++i) {
928  if (get(i))
929  product.add(addend);
930  addend.shiftLeft(1);
931  }
932  return product;
933  }
934 
939  BitVector multiplySigned(const BitVector &other) const {
940  // Unoptimized version using simple elementary school long multiply. The Wikipedia "Binary multiplier" article has a good
941  // description of a more optimized approach.
942  BitVector product(size() + other.size());
943 
944  // Absolute value of A
945  BitVector a = *this;
946  bool aIsNeg = false;
947  if (a.size() > 1 && a.get(a.size()-1)) {
948  aIsNeg = true;
949  a.negate();
950  }
951 
952  // Absolute value of B, and extended to result width
953  BitVector b = other;
954  bool bIsNeg = false;
955  if (b.size() > 1 && b.get(b.size()-1)) {
956  bIsNeg = true;
957  b.negate();
958  }
959  b.resize(product.size());
960 
961  // Long multiplication
962  for (size_t i = 0; i < a.size(); ++i) {
963  if (a.get(i))
964  product.add(b);
965  b.shiftLeft(1);
966  }
967 
968  // Correct the result sign
969  if (aIsNeg != bIsNeg)
970  product.negate();
971 
972  return product;
973  }
974 
975  // FIXME[Robb Matzke 2014-05-01]: we should also have zeroExtend, which is like copy but allows the source and destination
976  // to be different sizes.
977 
979  // Bit-wise Boolean logic
981 
985  BitVector& invert(const BitRange &range) {
986  checkRange(range);
987  BitVectorSupport::invert(data(), range);
988  return *this;
989  }
990 
996  return *this;
997  }
998 
1004  BitVector& bitwiseAnd(const BitRange &range1, const BitVector &other, const BitRange &range2) {
1005  checkRange(range1);
1006  other.checkRange(range2);
1007  BitVectorSupport::bitwiseAnd(other.data(), range2, data(), range1);
1008  return *this;
1009  }
1010 
1015  BitVector& bitwiseAnd(const BitRange &range1, const BitRange &range2) {
1016  checkRange(range1);
1017  checkRange(range2);
1018  BitVectorSupport::bitwiseAnd(data(), range2, data(), range1);
1019  return *this;
1020  }
1021 
1026  BitVector& bitwiseAnd(const BitVector &other) {
1027  BitVectorSupport::bitwiseAnd(other.data(), other.hull(), data(), hull());
1028  return *this;
1029  }
1030 
1036  BitVector& bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2) {
1037  checkRange(range1);
1038  other.checkRange(range2);
1039  BitVectorSupport::bitwiseOr(other.data(), range2, data(), range1);
1040  return *this;
1041  }
1042 
1047  BitVector& bitwiseOr(const BitRange &range1, const BitRange &range2) {
1048  checkRange(range1);
1049  checkRange(range2);
1050  BitVectorSupport::bitwiseOr(data(), range2, data(), range1);
1051  return *this;
1052  }
1053 
1058  BitVector& bitwiseOr(const BitVector &other) {
1059  BitVectorSupport::bitwiseOr(other.data(), other.hull(), data(), hull());
1060  return *this;
1061  }
1062 
1068  BitVector& bitwiseXor(const BitRange &range1, const BitVector &other, const BitRange &range2) {
1069  checkRange(range1);
1070  other.checkRange(range2);
1071  BitVectorSupport::bitwiseXor(other.data(), range2, data(), range1);
1072  return *this;
1073  }
1074 
1079  BitVector& bitwiseXor(const BitRange &range1, const BitRange &range2) {
1080  checkRange(range1);
1081  checkRange(range2);
1082  BitVectorSupport::bitwiseXor(data(), range2, data(), range1);
1083  return *this;
1084  }
1085 
1090  BitVector& bitwiseXor(const BitVector &other) {
1091  BitVectorSupport::bitwiseXor(other.data(), other.hull(), data(), hull());
1092  return *this;
1093  }
1094 
1096  // Numeric comparisons
1098 
1105  bool isEqualToZero(const BitRange &range) const {
1106  checkRange(range);
1107  return BitVectorSupport::isEqualToZero(data(), range);
1108  }
1109 
1115  bool isEqualToZero() const {
1117  }
1118 
1127  int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1128  checkRange(range1);
1129  other.checkRange(range2);
1130  return BitVectorSupport::compare(data(), range1, other.data(), range2);
1131  }
1132 
1140  int compare(const BitRange &range1, const BitRange &range2) const {
1141  checkRange(range1);
1142  checkRange(range2);
1143  return BitVectorSupport::compare(data(), range1, data(), range2);
1144  }
1145 
1153  int compare(const BitVector &other) const {
1154  return BitVectorSupport::compare(data(), hull(), other.data(), other.hull());
1155  }
1156 
1166  int compareSigned(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1167  checkRange(range1);
1168  other.checkRange(range2);
1169  return BitVectorSupport::compareSigned(data(), range1, other.data(), range2);
1170  }
1171 
1180  int compareSigned(const BitRange &range1, const BitRange &range2) const {
1181  checkRange(range1);
1182  checkRange(range2);
1183  return BitVectorSupport::compareSigned(data(), range1, data(), range2);
1184  }
1185 
1193  int compareSigned(const BitVector &other) const {
1194  return BitVectorSupport::compareSigned(data(), hull(), other.data(), other.hull());
1195  }
1196 
1198  // Conversion
1200 
1205  boost::uint64_t toInteger(const BitRange &range) const {
1206  checkRange(range);
1207  return BitVectorSupport::toInteger(data(), range);
1208  }
1209 
1214  boost::uint64_t toInteger() const {
1215  if (size() <= 64)
1216  return BitVectorSupport::toInteger(data(), size());
1217  return BitVectorSupport::toInteger(data(), hull());
1218  }
1219 
1226  boost::int64_t toSignedInteger(const BitRange &range) const {
1227  checkRange(range);
1228  return BitVectorSupport::toInteger(data(), range);
1229  }
1230 
1237  boost::int64_t toSignedInteger() const {
1238  if (size() <= 64)
1241  }
1242 
1249  std::string toHex(const BitRange &range) const {
1250  return BitVectorSupport::toHex(data(), range);
1251  }
1252 
1259  std::string toHex() const {
1260  return BitVectorSupport::toHex(data(), hull());
1261  }
1262 
1269  std::string toOctal(const BitRange &range) const {
1270  return BitVectorSupport::toOctal(data(), range);
1271  }
1272 
1278  std::string toOctal() const {
1279  return BitVectorSupport::toOctal(data(), hull());
1280  }
1281 
1288  std::string toBinary(const BitRange &range) const {
1289  return BitVectorSupport::toBinary(data(), range);
1290  }
1291 
1297  std::string toBinary() const {
1298  return BitVectorSupport::toBinary(data(), hull());
1299  }
1300 
1308  std::vector<uint8_t> toBytes() const {
1309  return BitVectorSupport::toBytes(data(), hull());
1310  }
1311  std::vector<uint8_t> toBytes(const BitRange &range) const {
1312  return BitVectorSupport::toBytes(data(), range);
1313  }
1321  BitVector& fromInteger(const BitRange &range, boost::uint64_t value) {
1322  checkRange(range);
1323  BitVectorSupport::fromInteger(data(), range, value);
1324  return *this;
1325  }
1326 
1334  BitVector& fromInteger(boost::uint64_t value) {
1336  return *this;
1337  }
1338 
1348  BitVector& fromDecimal(const BitRange &range, const std::string &input) {
1349  checkRange(range);
1350  BitVectorSupport::fromDecimal(data(), range, input);
1351  return *this;
1352  }
1353 
1362  BitVector& fromDecimal(const std::string &input) {
1364  return *this;
1365  }
1366 
1375  BitVector& fromHex(const BitRange &range, const std::string &input) {
1376  checkRange(range);
1377  BitVectorSupport::fromHex(data(), range, input);
1378  return *this;
1379  }
1380 
1389  BitVector& fromHex(const std::string &input) {
1390  BitVectorSupport::fromHex(data(), hull(), input);
1391  return *this;
1392  }
1393 
1402  BitVector& fromOctal(const BitRange &range, const std::string &input) {
1403  checkRange(range);
1404  BitVectorSupport::fromOctal(data(), range, input);
1405  return *this;
1406  }
1407 
1416  BitVector& fromOctal(const std::string &input) {
1417  BitVectorSupport::fromOctal(data(), hull(), input);
1418  return *this;
1419  }
1420 
1429  BitVector& fromBinary(const BitRange &range, const std::string &input) {
1430  checkRange(range);
1431  BitVectorSupport::fromBinary(data(), range, input);
1432  return *this;
1433  }
1434 
1443  BitVector& fromBinary(const std::string &input) {
1444  BitVectorSupport::fromBinary(data(), hull(), input);
1445  return *this;
1446  }
1447 
1455  BitVector& fromBytes(const std::vector<uint8_t> &input) {
1456  BitVectorSupport::fromBytes(data(), hull(), input);
1457  return *this;
1458  }
1459  BitVector& fromBytes(const BitRange &range, const std::vector<uint8_t> &input) {
1460  BitVectorSupport::fromBytes(data(), range, input);
1461  return *this;
1462  }
1465  // Utility
1468 
1473  void checkRange(const BitRange &range) const {
1474  ASSERT_always_require(hull().contains(range)); // so range is always used
1475  }
1476 
1483  Word* data() {
1484  return words_.empty() ? NULL : &words_[0];
1485  }
1486 
1487  const Word* data() const {
1488  return words_.empty() ? NULL : &words_[0];
1489  }
1495  size_t dataSize() const {
1496  return words_.size();
1497  }
1498 };
1499 
1500 } // namespace
1501 } // namespace
1502 #endif
bool equalTo(const BitRange &range1, BitVector &other, const BitRange &range2) const
Checks whether two ranges are equal.
Definition: BitVector.h:366
BitVector & bitwiseOr(const BitVector &other)
Bit-wise OR.
Definition: BitVector.h:1058
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
bool equalTo(const BitVector &other) const
Checks whether the bits of one vector are equal to the bits of the other.
Definition: BitVector.h:386
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:1483
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:584
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:1166
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:1237
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:1389
size_t nSet(const BitRange &range) const
Number of set bits.
Definition: BitVector.h:507
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:1278
bool add(const BitRange &range1, const BitRange &range2)
Add bits as integers.
Definition: BitVector.h:813
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:650
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:570
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:1004
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:885
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:1416
bool isEqualToZero() const
Compare to zero.
Definition: BitVector.h:1115
std::string toBinary(const BitRange &range) const
Convert to a binary string.
Definition: BitVector.h:1288
BitVector & fromDecimal(const BitRange &range, const std::string &input)
Obtains bits from a decimal representation.
Definition: BitVector.h:1348
BitVector & fromHex(const BitRange &range, const std::string &input)
Obtain bits from a hexadecimal representation.
Definition: BitVector.h:1375
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:1473
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:1180
BitVector & rotateRight(size_t nShift)
Rotate bits right.
Definition: BitVector.h:711
size_t nClear() const
Number of clear bits.
Definition: BitVector.h:530
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:700
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:1015
boost::int64_t toSignedInteger(const BitRange &range) const
Interpret bits as a signed integer.
Definition: BitVector.h:1226
BitVector & fromBinary(const BitRange &range, const std::string &input)
Obtain bits from a binary representation.
Definition: BitVector.h:1429
bool increment(Word *vec1, const BitRange &range1)
Increment.
BitVector & multiply10()
Multiply by 10.
Definition: BitVector.h:905
BitVector & fromInteger(boost::uint64_t value)
Obtain bits from an integer.
Definition: BitVector.h:1334
BitVector multiplySigned(const BitVector &other) const
Multiply two signed integers.
Definition: BitVector.h:939
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:985
bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2)
Subtract bits as integers.
Definition: BitVector.h:838
BitVector & shiftRightArithmetic(const BitRange &range, size_t nShift)
Shift bits right.
Definition: BitVector.h:676
BitVector & fromDecimal(const std::string &input)
Obtain bits from a decimal representation.
Definition: BitVector.h:1362
Optional< size_t > leastSignificantClearBit() const
Find the least significant clear bit.
Definition: BitVector.h:428
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:690
Optional< size_t > leastSignificantDifference(const BitVector &other) const
Find least significant difference.
Definition: BitVector.h:610
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:1321
Name space for the entire library.
Definition: FeasiblePath.h:767
BitVector & swap(const BitRange &range1, BitVector &other, const BitRange &range2)
Swap some bits.
Definition: BitVector.h:345
BitVector & multiply10(const BitRange &range)
Multiply by 10.
Definition: BitVector.h:914
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:745
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:464
BitVector & shiftRight(size_t nShift, bool newBits=0)
Shift bits right.
Definition: BitVector.h:663
static Interval baseSize(size_t lo, size_t size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:162
BitVector & signExtend(const BitVector &other)
Copy bits and sign extend.
Definition: BitVector.h:896
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:515
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:783
BitVector & invert()
Invert bits.
Definition: BitVector.h:994
std::string toOctal(const BitRange &range) const
Convert to an octal string.
Definition: BitVector.h:1269
BitVector & shiftLeft(size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:638
std::vector< uint8_t > toBytes(const BitRange &range) const
Convert to a vector of bytes.
Definition: BitVector.h:1311
int compare(const BitVector &other) const
Compare bits as integers.
Definition: BitVector.h:1153
size_t dataSize() const
Raw data size.
Definition: BitVector.h:1495
BitVector & bitwiseOr(const BitRange &range1, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:1047
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:1026
size_t nClear(const BitRange &range) const
Number of clear bits.
Definition: BitVector.h:522
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:765
Optional< size_t > mostSignificantClearBit(const BitRange &range) const
Find the most significant clear bit.
Definition: BitVector.h:455
bool isAllSet(const BitRange &range) const
True if all bits are set.
Definition: BitVector.h:472
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:1193
bool subtract(const BitVector &other)
Subtract bits as integers.
Definition: BitVector.h:863
static Interval hull(size_t v1, size_t v2)
Construct an interval from two endpoints.
Definition: Interval.h:151
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:446
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:1068
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:544
Optional< size_t > leastSignificantDifference(const BitRange &range1, const BitRange &range2) const
Find least significant difference.
Definition: BitVector.h:599
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:852
boost::uint64_t toInteger(const BitRange &range) const
Interpret bits as an unsigned integer.
Definition: BitVector.h:1205
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:419
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:792
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:437
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:559
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:1214
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:410
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:1443
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:873
std::vector< uint8_t > toBytes() const
Convert to a vector of bytes.
Definition: BitVector.h:1308
BitVector & rotateLeft(const BitRange &range, size_t nShift)
Rotate bits left.
Definition: BitVector.h:721
bool add(const BitRange &range1, const BitVector &other, const BitRange &range2)
Add bits as integers.
Definition: BitVector.h:802
BitVector & bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:1036
const Word * data() const
Raw data for vector.
Definition: BitVector.h:1487
void set(Word *words, const BitRange &where)
Set some bits.
bool isEqualToZero(const BitRange &range) const
Compare to zero.
Definition: BitVector.h:1105
Optional< size_t > leastSignificantSetBit(const BitRange &range) const
Find the least significant set bit.
Definition: BitVector.h:401
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:1140
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:1402
BitVector & shiftLeft(const BitRange &range, size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:625
std::string toBinary(const Word *vec, const BitRange &range)
Binary representation.
BitVector & rotateLeft(size_t nShift)
Rotate bits left.
Definition: BitVector.h:732
BitVector & bitwiseXor(const BitVector &other)
Bit-wise XOR.
Definition: BitVector.h:1090
BitVector & bitwiseXor(const BitRange &range1, const BitRange &range2)
Bit-wise XOR.
Definition: BitVector.h:1079
int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Compare bits as integers.
Definition: BitVector.h:1127
bool isAllSet() const
True if all bits are set.
Definition: BitVector.h:480
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:1297
size_t nSet(const Word *words, const BitRange &range)
Number of set bits.
BitVector & negate()
Negates bits as integer.
Definition: BitVector.h:755
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:825
bool equalTo(const BitRange &range1, const BitRange &range2) const
Checks whether the bits of two ranges are equal.
Definition: BitVector.h:376
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:500
bool isAllClear(const BitRange &range) const
True if all bits are clear.
Definition: BitVector.h:490
BitVector & copy(const BitRange &to, const BitRange &from)
Copy some bits.
Definition: BitVector.h:333
BitVector & fromBytes(const BitRange &range, const std::vector< uint8_t > &input)
Obtain bits from a byte vector.
Definition: BitVector.h:1459
bool increment()
Increment bits as integer.
Definition: BitVector.h:774
BitVector multiply(const BitVector &other) const
Multiply two bit vectors.
Definition: BitVector.h:923
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:1249
size_t capacity() const
Maximum size before reallocation.
Definition: BitVector.h:217
BitVector & fromBytes(const std::vector< uint8_t > &input)
Obtain bits from a byte vector.
Definition: BitVector.h:1455
std::string toHex() const
Convert to a hexadecimal string.
Definition: BitVector.h:1259