ROSE  0.9.12.19
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 
919 
920  // FIXME[Robb Matzke 2014-05-01]: we should also have zeroExtend, which is like copy but allows the source and destination
921  // to be different sizes.
922 
924  // Bit-wise Boolean logic
926 
930  BitVector& invert(const BitRange &range) {
931  checkRange(range);
932  BitVectorSupport::invert(data(), range);
933  return *this;
934  }
935 
941  return *this;
942  }
943 
949  BitVector& bitwiseAnd(const BitRange &range1, const BitVector &other, const BitRange &range2) {
950  checkRange(range1);
951  other.checkRange(range2);
952  BitVectorSupport::bitwiseAnd(other.data(), range2, data(), range1);
953  return *this;
954  }
955 
960  BitVector& bitwiseAnd(const BitRange &range1, const BitRange &range2) {
961  checkRange(range1);
962  checkRange(range2);
963  BitVectorSupport::bitwiseAnd(data(), range2, data(), range1);
964  return *this;
965  }
966 
971  BitVector& bitwiseAnd(const BitVector &other) {
972  BitVectorSupport::bitwiseAnd(other.data(), other.hull(), data(), hull());
973  return *this;
974  }
975 
981  BitVector& bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2) {
982  checkRange(range1);
983  other.checkRange(range2);
984  BitVectorSupport::bitwiseOr(other.data(), range2, data(), range1);
985  return *this;
986  }
987 
992  BitVector& bitwiseOr(const BitRange &range1, const BitRange &range2) {
993  checkRange(range1);
994  checkRange(range2);
995  BitVectorSupport::bitwiseOr(data(), range2, data(), range1);
996  return *this;
997  }
998 
1003  BitVector& bitwiseOr(const BitVector &other) {
1004  BitVectorSupport::bitwiseOr(other.data(), other.hull(), data(), hull());
1005  return *this;
1006  }
1007 
1013  BitVector& bitwiseXor(const BitRange &range1, const BitVector &other, const BitRange &range2) {
1014  checkRange(range1);
1015  other.checkRange(range2);
1016  BitVectorSupport::bitwiseXor(other.data(), range2, data(), range1);
1017  return *this;
1018  }
1019 
1024  BitVector& bitwiseXor(const BitRange &range1, const BitRange &range2) {
1025  checkRange(range1);
1026  checkRange(range2);
1027  BitVectorSupport::bitwiseXor(data(), range2, data(), range1);
1028  return *this;
1029  }
1030 
1035  BitVector& bitwiseXor(const BitVector &other) {
1036  BitVectorSupport::bitwiseXor(other.data(), other.hull(), data(), hull());
1037  return *this;
1038  }
1039 
1041  // Numeric comparisons
1043 
1050  bool isEqualToZero(const BitRange &range) const {
1051  checkRange(range);
1052  return BitVectorSupport::isEqualToZero(data(), range);
1053  }
1054 
1060  bool isEqualToZero() const {
1062  }
1063 
1072  int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1073  checkRange(range1);
1074  other.checkRange(range2);
1075  return BitVectorSupport::compare(data(), range1, other.data(), range2);
1076  }
1077 
1085  int compare(const BitRange &range1, const BitRange &range2) const {
1086  checkRange(range1);
1087  checkRange(range2);
1088  return BitVectorSupport::compare(data(), range1, data(), range2);
1089  }
1090 
1098  int compare(const BitVector &other) const {
1099  return BitVectorSupport::compare(data(), hull(), other.data(), other.hull());
1100  }
1101 
1111  int compareSigned(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1112  checkRange(range1);
1113  other.checkRange(range2);
1114  return BitVectorSupport::compareSigned(data(), range1, other.data(), range2);
1115  }
1116 
1125  int compareSigned(const BitRange &range1, const BitRange &range2) const {
1126  checkRange(range1);
1127  checkRange(range2);
1128  return BitVectorSupport::compareSigned(data(), range1, data(), range2);
1129  }
1130 
1138  int compareSigned(const BitVector &other) const {
1139  return BitVectorSupport::compareSigned(data(), hull(), other.data(), other.hull());
1140  }
1141 
1143  // Conversion
1145 
1150  boost::uint64_t toInteger(const BitRange &range) const {
1151  checkRange(range);
1152  return BitVectorSupport::toInteger(data(), range);
1153  }
1154 
1159  boost::uint64_t toInteger() const {
1160  if (size() <= 64)
1161  return BitVectorSupport::toInteger(data(), size());
1162  return BitVectorSupport::toInteger(data(), hull());
1163  }
1164 
1171  boost::int64_t toSignedInteger(const BitRange &range) const {
1172  checkRange(range);
1173  return BitVectorSupport::toInteger(data(), range);
1174  }
1175 
1182  boost::int64_t toSignedInteger() const {
1183  if (size() <= 64)
1186  }
1187 
1194  std::string toHex(const BitRange &range) const {
1195  return BitVectorSupport::toHex(data(), range);
1196  }
1197 
1204  std::string toHex() const {
1205  return BitVectorSupport::toHex(data(), hull());
1206  }
1207 
1214  std::string toOctal(const BitRange &range) const {
1215  return BitVectorSupport::toOctal(data(), range);
1216  }
1217 
1223  std::string toOctal() const {
1224  return BitVectorSupport::toOctal(data(), hull());
1225  }
1226 
1233  std::string toBinary(const BitRange &range) const {
1234  return BitVectorSupport::toBinary(data(), range);
1235  }
1236 
1242  std::string toBinary() const {
1243  return BitVectorSupport::toBinary(data(), hull());
1244  }
1245 
1251  BitVector& fromInteger(const BitRange &range, boost::uint64_t value) {
1252  checkRange(range);
1253  BitVectorSupport::fromInteger(data(), range, value);
1254  return *this;
1255  }
1256 
1264  BitVector& fromInteger(boost::uint64_t value) {
1266  return *this;
1267  }
1268 
1278  BitVector& fromDecimal(const BitRange &range, const std::string &input) {
1279  checkRange(range);
1280  BitVectorSupport::fromDecimal(data(), range, input);
1281  return *this;
1282  }
1283 
1292  BitVector& fromDecimal(const std::string &input) {
1294  return *this;
1295  }
1296 
1305  BitVector& fromHex(const BitRange &range, const std::string &input) {
1306  checkRange(range);
1307  BitVectorSupport::fromHex(data(), range, input);
1308  return *this;
1309  }
1310 
1319  BitVector& fromHex(const std::string &input) {
1320  BitVectorSupport::fromHex(data(), hull(), input);
1321  return *this;
1322  }
1323 
1332  BitVector& fromOctal(const BitRange &range, const std::string &input) {
1333  checkRange(range);
1334  BitVectorSupport::fromOctal(data(), range, input);
1335  return *this;
1336  }
1337 
1346  BitVector& fromOctal(const std::string &input) {
1347  BitVectorSupport::fromOctal(data(), hull(), input);
1348  return *this;
1349  }
1350 
1359  BitVector& fromBinary(const BitRange &range, const std::string &input) {
1360  checkRange(range);
1361  BitVectorSupport::fromBinary(data(), range, input);
1362  return *this;
1363  }
1364 
1373  BitVector& fromBinary(const std::string &input) {
1374  BitVectorSupport::fromBinary(data(), hull(), input);
1375  return *this;
1376  }
1377 
1379  // Utility
1381 
1386  void checkRange(const BitRange &range) const {
1387  ASSERT_always_require(hull().isContaining(range)); // so range is always used
1388  }
1389 
1396  Word* data() {
1397  return words_.empty() ? NULL : &words_[0];
1398  }
1399 
1400  const Word* data() const {
1401  return words_.empty() ? NULL : &words_[0];
1402  }
1408  size_t dataSize() const {
1409  return words_.size();
1410  }
1411 };
1412 
1413 } // namespace
1414 } // namespace
1415 #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:1003
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:1396
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:1111
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:1182
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:1319
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:1223
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:949
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:1346
bool isEqualToZero() const
Compare to zero.
Definition: BitVector.h:1060
std::string toBinary(const BitRange &range) const
Convert to a binary string.
Definition: BitVector.h:1233
BitVector & fromDecimal(const BitRange &range, const std::string &input)
Obtains bits from a decimal representation.
Definition: BitVector.h:1278
BitVector & fromHex(const BitRange &range, const std::string &input)
Obtain bits from a hexadecimal representation.
Definition: BitVector.h:1305
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:1386
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:1125
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
BitVector & bitwiseAnd(const BitRange &range1, const BitRange &range2)
Bit-wise AND.
Definition: BitVector.h:960
boost::int64_t toSignedInteger(const BitRange &range) const
Interpret bits as a signed integer.
Definition: BitVector.h:1171
BitVector & fromBinary(const BitRange &range, const std::string &input)
Obtain bits from a binary representation.
Definition: BitVector.h:1359
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:1264
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:930
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:1292
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:1251
Name space for the entire library.
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:161
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:939
std::string toOctal(const BitRange &range) const
Convert to an octal string.
Definition: BitVector.h:1214
BitVector & shiftLeft(size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:638
int compare(const BitVector &other) const
Compare bits as integers.
Definition: BitVector.h:1098
size_t dataSize() const
Raw data size.
Definition: BitVector.h:1408
BitVector & bitwiseOr(const BitRange &range1, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:992
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:971
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:1138
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: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: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:1013
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:1150
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:1159
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:1373
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
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:981
const Word * data() const
Raw data for vector.
Definition: BitVector.h:1400
void set(Word *words, const BitRange &where)
Set some bits.
bool isEqualToZero(const BitRange &range) const
Compare to zero.
Definition: BitVector.h:1050
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:1085
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:1332
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:1035
BitVector & bitwiseXor(const BitRange &range1, const BitRange &range2)
Bit-wise XOR.
Definition: BitVector.h:1024
int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Compare bits as integers.
Definition: BitVector.h:1072
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:1242
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
bool increment()
Increment bits as integer.
Definition: BitVector.h:774
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:1194
size_t capacity() const
Maximum size before reallocation.
Definition: BitVector.h:217
std::string toHex() const
Convert to a hexadecimal string.
Definition: BitVector.h:1204