ROSE  0.9.10.54
BitVector.h
1 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
2 // be clobbered by the next update from Sawyer. The Sawyer repository is at
3 // https://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 #ifndef Sawyer_BitVector_H
9 #define Sawyer_BitVector_H
10 
11 #include <Sawyer/Assert.h>
12 #include <Sawyer/BitVectorSupport.h>
13 #include <Sawyer/Optional.h>
14 #include <Sawyer/Sawyer.h>
15 
16 #include <boost/algorithm/string/predicate.hpp>
17 #include <boost/cstdint.hpp>
18 #include <boost/serialization/access.hpp>
19 #include <boost/serialization/nvp.hpp>
20 #include <boost/serialization/vector.hpp>
21 
22 namespace Sawyer {
23 namespace Container {
24 
25 #ifdef BOOST_WINDOWS
26 
29 inline double log2(double n) {
30  return log(n) / log(2.0);
31 }
32 #endif
33 
64 class BitVector {
65 public:
66  typedef unsigned Word;
69 private:
70  std::vector<Word> words_;
71  size_t size_;
72 
73 private:
74  friend class boost::serialization::access;
75  template<class S>
76  void serialize(S &s, const unsigned /*version*/) {
77  s & BOOST_SERIALIZATION_NVP(size_);
78  s & BOOST_SERIALIZATION_NVP(words_);
79  }
80 
81 public:
83  BitVector(): size_(0) {}
84 
86  BitVector(const BitVector &other): words_(other.words_), size_(other.size_) {}
87 
91  explicit BitVector(size_t nbits, bool newBits = false): size_(0) {
92  resize(nbits, newBits);
93  }
94 
106  static BitVector parse(std::string str) {
107  // Radix information
108  size_t bitsPerDigit = 0;
109  const char *digits = NULL;
110  if (boost::starts_with(str, "0x")) {
111  bitsPerDigit = 4;
112  digits = "0123456789abcdefABCDEF";
113  str = str.substr(2);
114  } else if (boost::starts_with(str, "0b")) {
115  bitsPerDigit = 1;
116  digits = "01";
117  str = str.substr(2);
118  } else if (boost::ends_with(str, "h")) {
119  bitsPerDigit = 4;
120  digits = "0123456789abcdefABCDEF";
121  str = str.substr(0, str.size()-1);
122  } else if (boost::starts_with(str, "0")) {
123  bitsPerDigit = 2;
124  digits = "01234567";
125  str = str.substr(1);
126  } else {
127  bitsPerDigit = 0; // special case
128  digits = "0123456789";
129  }
130 
131  // Count digits
132  size_t nDigits = 0;
133  for (const char *t=str.c_str(); *t; ++t) {
134  if (strchr(digits, *t))
135  ++nDigits;
136  }
137  if (0==nDigits)
138  throw std::runtime_error("BitVector::parse: no valid digits");
139 
140  // Number of bits
141  size_t nBits = 0;
142  if (bitsPerDigit) {
143  nBits = bitsPerDigit * nDigits;
144  } else {
145  nBits = ceil(log2(pow(10.0, (double)nDigits)));
146  }
147 
148  // Parse the string
149  BitVector result(nBits);
150  switch (bitsPerDigit) {
151  case 0:
152  result.fromDecimal(str);
153  break;
154  case 2:
155  result.fromBinary(str);
156  break;
157  case 3:
158  result.fromOctal(str);
159  break;
160  case 4:
161  result.fromHex(str);
162  break;
163  default:
164  assert(!"invalid radix");
165  break;
166  }
167  return result;
168  }
169 
175  BitVector& operator=(const BitVector &other) {
176  words_ = other.words_;
177  size_ = other.size_;
178  return *this;
179  }
180 
184  bool isEmpty() const { return 0 == size_; }
185 
189  size_t size() const { return size_; }
190 
196  BitVector& resize(size_t newSize, bool newBits=false) {
197  if (0==newSize) {
198  words_.clear();
199  size_ = 0;
200  } else if (newSize > size_) {
201  size_t nwords = BitVectorSupport::numberOfWords<Word>(newSize);
202  words_.resize(nwords, Word(0));
203  BitVectorSupport::setValue(data(), BitRange::hull(size_, newSize-1), newBits);
204  size_ = newSize;
205  } else {
206  size_t nwords = BitVectorSupport::numberOfWords<Word>(newSize);
207  words_.resize(nwords);
208  size_ = newSize;
209  }
210  return *this;
211  }
212 
217  size_t capacity() const {
218  return BitVectorSupport::bitsPerWord<Word>::value * words_.capacity();
219  }
220 
224  BitRange hull() const {
225  return 0==size_ ? BitRange() : BitRange::hull(0, size_-1);
226  }
227 
232  static BitRange baseSize(size_t base, size_t size) {
233  return BitRange::baseSize(base, size);
234  }
235 
240  static BitRange hull(size_t minOffset, size_t maxOffset) {
241  return BitRange::hull(minOffset, maxOffset);
242  }
243 
245  // Value access
247 
252  bool get(size_t idx) const {
253  checkRange(idx);
254  return BitVectorSupport::get(data(), idx);
255  }
256 
262  BitVector& clear(const BitRange &range) {
263  checkRange(range);
264  BitVectorSupport::clear(data(), range);
265  return *this;
266  }
267 
275  return *this;
276  }
277 
282  BitVector& set(const BitRange &range) {
283  checkRange(range);
284  BitVectorSupport::set(data(), range);
285  return *this;
286  }
287 
294  return *this;
295  }
296 
300  BitVector& setValue(const BitRange &range, bool value) {
301  checkRange(range);
302  BitVectorSupport::setValue(data(), range, value);
303  return *this;
304  }
305 
309  BitVector& setValue(bool value) {
310  BitVectorSupport::setValue(data(), hull(), value);
311  return *this;
312  }
313 
321  BitVector& copy(const BitRange &to, const BitVector &other, const BitRange &from) {
322  checkRange(to);
323  other.checkRange(from);
324  BitVectorSupport::copy(other.data(), from, data(), to);
325  return *this;
326  }
327 
333  BitVector& copy(const BitRange &to, const BitRange &from) {
334  checkRange(to);
335  checkRange(from);
336  BitVectorSupport::copy(data(), from, data(), to);
337  return *this;
338  }
339 
345  BitVector& swap(const BitRange &range1, BitVector &other, const BitRange &range2) {
346  checkRange(range1);
347  other.checkRange(range2);
348  BitVectorSupport::swap(data(), range1, other.data(), range2);
349  return *this;
350  }
351 
356  BitVector& swap(const BitRange &range1, const BitRange &range2) {
357  checkRange(range1);
358  checkRange(range2);
359  BitVectorSupport::swap(data(), range1, data(), range2);
360  return *this;
361  }
362 
364  // Counting/searching
366 
372  Optional<size_t> leastSignificantSetBit(const BitRange &range) const {
373  checkRange(range);
375  }
376 
383  }
384 
390  Optional<size_t> leastSignificantClearBit(const BitRange &range) const {
391  checkRange(range);
393  }
394 
401  }
402 
408  Optional<size_t> mostSignificantSetBit(const BitRange &range) const {
409  checkRange(range);
411  }
412 
419  }
420 
426  Optional<size_t> mostSignificantClearBit(const BitRange &range) const {
427  checkRange(range);
429  }
430 
437  }
438 
443  bool isAllSet(const BitRange &range) const {
444  checkRange(range);
445  return BitVectorSupport::isAllSet(data(), range);
446  }
447 
451  bool isAllSet() const {
452  return BitVectorSupport::isAllSet(data(), hull());
453  }
454 
461  bool isAllClear(const BitRange &range) const {
462  checkRange(range);
463  return BitVectorSupport::isAllClear(data(), range);
464  }
465 
471  bool isAllClear() const {
473  }
474 
478  size_t nSet(const BitRange &range) const {
479  checkRange(range);
480  return BitVectorSupport::nSet(data(), range);
481  }
482 
486  size_t nSet() const {
487  return BitVectorSupport::nSet(data(), hull());
488  }
489 
493  size_t nClear(const BitRange &range) const {
494  checkRange(range);
495  return BitVectorSupport::nClear(data(), range);
496  }
497 
501  size_t nClear() const {
502  return BitVectorSupport::nClear(data(), hull());
503  }
504 
515  Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitVector &other,
516  const BitRange &range2) const {
517  checkRange(range1);
518  other.checkRange(range2);
519  return BitVectorSupport::mostSignificantDifference(data(), range1, other.data(), range2);
520  }
521 
530  Optional<size_t> mostSignificantDifference(const BitRange &range1, const BitRange &range2) const {
531  checkRange(range1);
532  checkRange(range2);
533  return BitVectorSupport::mostSignificantDifference(data(), range1, data(), range2);
534  }
535 
542  return BitVectorSupport::mostSignificantDifference(data(), hull(), other.data(), other.hull());
543  }
544 
555  Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitVector &other,
556  const BitRange &range2) const {
557  checkRange(range1);
558  other.checkRange(range2);
559  return BitVectorSupport::leastSignificantDifference(data(), range1, other.data(), range2);
560  }
561 
570  Optional<size_t> leastSignificantDifference(const BitRange &range1, const BitRange &range2) const {
571  checkRange(range1);
572  checkRange(range2);
573  return BitVectorSupport::leastSignificantDifference(data(), range1, data(), range2);
574  }
575 
582  return BitVectorSupport::leastSignificantDifference(data(), hull(), other.data(), other.hull());
583  }
584 
586  // Shift/rotate
588 
596  BitVector& shiftLeft(const BitRange &range, size_t nShift, bool newBits = 0) {
597  checkRange(range);
598  BitVectorSupport::shiftLeft(data(), range, nShift, newBits);
599  return *this;
600  }
601 
609  BitVector& shiftLeft(size_t nShift, bool newBits = 0) {
610  BitVectorSupport::shiftLeft(data(), hull(), nShift, newBits);
611  return *this;
612  }
613 
621  BitVector& shiftRight(const BitRange &range, size_t nShift, bool newBits = 0) {
622  checkRange(range);
623  BitVectorSupport::shiftRight(data(), range, nShift, newBits);
624  return *this;
625  }
626 
634  BitVector& shiftRight(size_t nShift, bool newBits = 0) {
635  BitVectorSupport::shiftRight(data(), hull(), nShift, newBits);
636  return *this;
637  }
638 
647  BitVector& shiftRightArithmetic(const BitRange &range, size_t nShift) {
648  checkRange(range);
650  return *this;
651  }
652 
661  BitVector& shiftRightArithmetic(size_t nShift) {
663  return *this;
664  }
665 
671  BitVector& rotateRight(const BitRange &range, size_t nShift) {
672  checkRange(range);
673  BitVectorSupport::rotateRight(data(), range, nShift);
674  return *this;
675  }
676 
682  BitVector& rotateRight(size_t nShift) {
684  return *this;
685  }
686 
692  BitVector& rotateLeft(const BitRange &range, size_t nShift) {
693  checkRange(range);
694  BitVectorSupport::rotateLeft(data(), range, nShift);
695  return *this;
696  }
697 
703  BitVector& rotateLeft(size_t nShift) {
704  BitVectorSupport::rotateLeft(data(), hull(), nShift);
705  return *this;
706  }
707 
709  // Arithmetic
711 
716  BitVector& negate(const BitRange &range1) {
717  checkRange(range1);
718  BitVectorSupport::negate(data(), range1);
719  return *this;
720  }
721 
728  return *this;
729  }
730 
736  bool increment(const BitRange &range1) {
737  checkRange(range1);
738  return BitVectorSupport::increment(data(), range1);
739  }
740 
745  bool increment() {
747  }
748 
754  bool decrement(const BitRange &range1) {
755  checkRange(range1);
756  return BitVectorSupport::decrement(data(), range1);
757  }
758 
763  bool decrement() {
765  }
766 
773  bool add(const BitRange &range1, const BitVector &other, const BitRange &range2) {
774  checkRange(range1);
775  other.checkRange(range2);
776  return BitVectorSupport::add(other.data(), range2, data(), range1, false);
777  }
778 
784  bool add(const BitRange &range1, const BitRange &range2) {
785  checkRange(range1);
786  checkRange(range2);
787  return BitVectorSupport::add(data(), range2, data(), range1, false);
788  }
789 
796  bool add(const BitVector &other) {
797  return BitVectorSupport::add(other.data(), other.hull(), data(), hull(), false);
798  }
799 
809  bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2) {
810  checkRange(range1);
811  other.checkRange(range2);
812  return BitVectorSupport::subtract(other.data(), range2, data(), range1);
813  }
814 
823  bool subtract(const BitRange &range1, const BitRange &range2) {
824  checkRange(range1);
825  checkRange(range2);
826  return BitVectorSupport::subtract(data(), range2, data(), range1);
827  }
828 
834  bool subtract(const BitVector &other) {
835  return BitVectorSupport::subtract(other.data(), other.hull(), data(), hull());
836  }
837 
844  BitVector& signExtend(const BitRange &range1, const BitVector &other, const BitRange &range2) {
845  checkRange(range1);
846  other.checkRange(range2);
847  BitVectorSupport::signExtend(other.data(), range2, data(), range1);
848  return *this;
849  }
850 
856  BitVector& signExtend(const BitRange &range1, const BitRange &range2) {
857  checkRange(range1);
858  checkRange(range2);
859  BitVectorSupport::signExtend(data(), range2, data(), range1);
860  return *this;
861  }
862 
867  BitVector& signExtend(const BitVector &other) {
868  BitVectorSupport::signExtend(other.data(), other.hull(), data(), hull());
869  return *this;
870  }
871 
878  return *this;
879  }
880 
885  BitVector& multiply10(const BitRange &range) {
887  return *this;
888  }
889 
890 
891  // FIXME[Robb Matzke 2014-05-01]: we should also have zeroExtend, which is like copy but allows the source and destination
892  // to be different sizes.
893 
895  // Bit-wise Boolean logic
897 
901  BitVector& invert(const BitRange &range) {
902  checkRange(range);
903  BitVectorSupport::invert(data(), range);
904  return *this;
905  }
906 
912  return *this;
913  }
914 
920  BitVector& bitwiseAnd(const BitRange &range1, const BitVector &other, const BitRange &range2) {
921  checkRange(range1);
922  other.checkRange(range2);
923  BitVectorSupport::bitwiseAnd(other.data(), range2, data(), range1);
924  return *this;
925  }
926 
931  BitVector& bitwiseAnd(const BitRange &range1, const BitRange &range2) {
932  checkRange(range1);
933  checkRange(range2);
934  BitVectorSupport::bitwiseAnd(data(), range2, data(), range1);
935  return *this;
936  }
937 
942  BitVector& bitwiseAnd(const BitVector &other) {
943  BitVectorSupport::bitwiseAnd(other.data(), other.hull(), data(), hull());
944  return *this;
945  }
946 
952  BitVector& bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2) {
953  checkRange(range1);
954  other.checkRange(range2);
955  BitVectorSupport::bitwiseOr(other.data(), range2, data(), range1);
956  return *this;
957  }
958 
963  BitVector& bitwiseOr(const BitRange &range1, const BitRange &range2) {
964  checkRange(range1);
965  checkRange(range2);
966  BitVectorSupport::bitwiseOr(data(), range2, data(), range1);
967  return *this;
968  }
969 
974  BitVector& bitwiseOr(const BitVector &other) {
975  BitVectorSupport::bitwiseOr(other.data(), other.hull(), data(), hull());
976  return *this;
977  }
978 
984  BitVector& bitwiseXor(const BitRange &range1, const BitVector &other, const BitRange &range2) {
985  checkRange(range1);
986  other.checkRange(range2);
987  BitVectorSupport::bitwiseXor(other.data(), range2, data(), range1);
988  return *this;
989  }
990 
995  BitVector& bitwiseXor(const BitRange &range1, const BitRange &range2) {
996  checkRange(range1);
997  checkRange(range2);
998  BitVectorSupport::bitwiseXor(data(), range2, data(), range1);
999  return *this;
1000  }
1001 
1006  BitVector& bitwiseXor(const BitVector &other) {
1007  BitVectorSupport::bitwiseXor(other.data(), other.hull(), data(), hull());
1008  return *this;
1009  }
1010 
1012  // Numeric comparisons
1014 
1021  bool isEqualToZero(const BitRange &range) const {
1022  checkRange(range);
1023  return BitVectorSupport::isEqualToZero(data(), range);
1024  }
1025 
1031  bool isEqualToZero() const {
1033  }
1034 
1043  int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1044  checkRange(range1);
1045  other.checkRange(range2);
1046  return BitVectorSupport::compare(data(), range1, other.data(), range2);
1047  }
1048 
1056  int compare(const BitRange &range1, const BitRange &range2) const {
1057  checkRange(range1);
1058  checkRange(range2);
1059  return BitVectorSupport::compare(data(), range1, data(), range2);
1060  }
1061 
1069  int compare(const BitVector &other) const {
1070  return BitVectorSupport::compare(data(), hull(), other.data(), other.hull());
1071  }
1072 
1082  int compareSigned(const BitRange &range1, const BitVector &other, const BitRange &range2) const {
1083  checkRange(range1);
1084  other.checkRange(range2);
1085  return BitVectorSupport::compareSigned(data(), range1, other.data(), range2);
1086  }
1087 
1096  int compareSigned(const BitRange &range1, const BitRange &range2) const {
1097  checkRange(range1);
1098  checkRange(range2);
1099  return BitVectorSupport::compareSigned(data(), range1, data(), range2);
1100  }
1101 
1109  int compareSigned(const BitVector &other) const {
1110  return BitVectorSupport::compareSigned(data(), hull(), other.data(), other.hull());
1111  }
1112 
1114  // Conversion
1116 
1121  boost::uint64_t toInteger(const BitRange &range) const {
1122  checkRange(range);
1123  return BitVectorSupport::toInteger(data(), range);
1124  }
1125 
1130  boost::uint64_t toInteger() const {
1131  if (size() <= 64)
1132  return BitVectorSupport::toInteger(data(), size());
1133  return BitVectorSupport::toInteger(data(), hull());
1134  }
1135 
1142  std::string toHex(const BitRange &range) const {
1143  return BitVectorSupport::toHex(data(), range);
1144  }
1145 
1152  std::string toHex() const {
1153  return BitVectorSupport::toHex(data(), hull());
1154  }
1155 
1162  std::string toOctal(const BitRange &range) const {
1163  return BitVectorSupport::toOctal(data(), range);
1164  }
1165 
1171  std::string toOctal() const {
1172  return BitVectorSupport::toOctal(data(), hull());
1173  }
1174 
1181  std::string toBinary(const BitRange &range) const {
1182  return BitVectorSupport::toBinary(data(), range);
1183  }
1184 
1190  std::string toBinary() const {
1191  return BitVectorSupport::toBinary(data(), hull());
1192  }
1193 
1199  BitVector& fromInteger(const BitRange &range, boost::uint64_t value) {
1200  checkRange(range);
1201  BitVectorSupport::fromInteger(data(), range, value);
1202  return *this;
1203  }
1204 
1212  BitVector& fromInteger(boost::uint64_t value) {
1214  return *this;
1215  }
1216 
1226  BitVector& fromDecimal(const BitRange &range, const std::string &input) {
1227  checkRange(range);
1228  BitVectorSupport::fromDecimal(data(), range, input);
1229  return *this;
1230  }
1231 
1240  BitVector& fromDecimal(const std::string &input) {
1242  return *this;
1243  }
1244 
1253  BitVector& fromHex(const BitRange &range, const std::string &input) {
1254  checkRange(range);
1255  BitVectorSupport::fromHex(data(), range, input);
1256  return *this;
1257  }
1258 
1267  BitVector& fromHex(const std::string &input) {
1268  BitVectorSupport::fromHex(data(), hull(), input);
1269  return *this;
1270  }
1271 
1280  BitVector& fromOctal(const BitRange &range, const std::string &input) {
1281  checkRange(range);
1282  BitVectorSupport::fromOctal(data(), range, input);
1283  return *this;
1284  }
1285 
1294  BitVector& fromOctal(const std::string &input) {
1295  BitVectorSupport::fromOctal(data(), hull(), input);
1296  return *this;
1297  }
1298 
1307  BitVector& fromBinary(const BitRange &range, const std::string &input) {
1308  checkRange(range);
1309  BitVectorSupport::fromBinary(data(), range, input);
1310  return *this;
1311  }
1312 
1321  BitVector& fromBinary(const std::string &input) {
1322  BitVectorSupport::fromBinary(data(), hull(), input);
1323  return *this;
1324  }
1325 
1327  // Utility
1329 
1334  void checkRange(const BitRange &range) const {
1335  ASSERT_always_require(hull().isContaining(range)); // so range is always used
1336  }
1337 
1344  Word* data() {
1345  return words_.empty() ? NULL : &words_[0];
1346  }
1347 
1348  const Word* data() const {
1349  return words_.empty() ? NULL : &words_[0];
1350  }
1356  size_t dataSize() const {
1357  return words_.size();
1358  }
1359 };
1360 
1361 } // namespace
1362 } // namespace
1363 #endif
BitVector & bitwiseOr(const BitVector &other)
Bit-wise OR.
Definition: BitVector.h:974
void fromInteger(Word *words, const BitRange &range, boost::uint64_t value)
Assign an unsigned value to a bit range.
BitVector & set()
Assign true to all bits.
Definition: BitVector.h:292
static BitRange baseSize(size_t base, size_t size)
Create a bit range from a starting offset and size.
Definition: BitVector.h:232
Word * data()
Raw data for vector.
Definition: BitVector.h:1344
Optional< size_t > leastSignificantDifference(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Find least significant difference.
Definition: BitVector.h:555
bool subtract(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Subtract bits.
int compareSigned(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Compare bits as signed integers.
Definition: BitVector.h:1082
BitVector & operator=(const BitVector &other)
Assignment.
Definition: BitVector.h:175
bool decrement(Word *vec1, const BitRange &range1)
Decrement.
BitVector & fromHex(const std::string &input)
Obtain bits from a hexadecimal representation.
Definition: BitVector.h:1267
size_t nSet(const BitRange &range) const
Number of set bits.
Definition: BitVector.h:478
std::string toOctal(const Word *vec, const BitRange &range)
Octal representation.
void copy(const Word *src, const BitRange &srcRange, Word *dst, const BitRange &dstRange)
Copy some bits.
Optional< size_t > leastSignificantDifference(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Find least significant different bits.
std::string toOctal() const
Convert to an octal string.
Definition: BitVector.h:1171
bool add(const BitRange &range1, const BitRange &range2)
Add bits as integers.
Definition: BitVector.h:784
BitVector & copy(const BitRange &to, const BitVector &other, const BitRange &from)
Copy some bits.
Definition: BitVector.h:321
void fromDecimal(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a decimal representation.
BitVector & shiftRight(const BitRange &range, size_t nShift, bool newBits=0)
Shift bits right.
Definition: BitVector.h:621
BitVector(size_t nbits, bool newBits=false)
Create a vector of specified size.
Definition: BitVector.h:91
bool isAllSet(const Word *words, const BitRange &range)
True if all bits are set.
Optional< size_t > mostSignificantDifference(const BitVector &other) const
Find most significant difference.
Definition: BitVector.h:541
void fromBinary(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a binary representation.
BitVector & bitwiseAnd(const BitRange &range1, const BitVector &other, const BitRange &range2)
Bit-wise AND.
Definition: BitVector.h:920
BitVector & set(const BitRange &range)
Assign true to some bits.
Definition: BitVector.h:282
unsigned Word
Base storage type.
Definition: BitVector.h:66
void invert(Word *words, const BitRange &range)
Invert bits.
BitVector & signExtend(const BitRange &range1, const BitRange &range2)
Copy bits and sign extend.
Definition: BitVector.h:856
bool get(const Word *words, size_t idx)
Return a single bit.
BitVector & fromOctal(const std::string &input)
Obtain bits from an octal representation.
Definition: BitVector.h:1294
bool isEqualToZero() const
Compare to zero.
Definition: BitVector.h:1031
std::string toBinary(const BitRange &range) const
Convert to a binary string.
Definition: BitVector.h:1181
BitVector & fromDecimal(const BitRange &range, const std::string &input)
Obtains bits from a decimal representation.
Definition: BitVector.h:1226
BitVector & fromHex(const BitRange &range, const std::string &input)
Obtain bits from a hexadecimal representation.
Definition: BitVector.h:1253
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:1334
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:1096
BitVector & rotateRight(size_t nShift)
Rotate bits right.
Definition: BitVector.h:682
size_t nClear() const
Number of clear bits.
Definition: BitVector.h:501
void setValue(Word *words, const BitRange &where, bool value)
Set or clear some bits.
Optional< size_t > mostSignificantClearBit(const Word *words, const BitRange &range)
Index of most significant clear bit.
BitVector & rotateRight(const BitRange &range, size_t nShift)
Rotate bits right.
Definition: BitVector.h:671
BitVector & bitwiseAnd(const BitRange &range1, const BitRange &range2)
Bit-wise AND.
Definition: BitVector.h:931
BitVector & fromBinary(const BitRange &range, const std::string &input)
Obtain bits from a binary representation.
Definition: BitVector.h:1307
bool increment(Word *vec1, const BitRange &range1)
Increment.
BitVector & multiply10()
Multiply by 10.
Definition: BitVector.h:876
BitVector & fromInteger(boost::uint64_t value)
Obtain bits from an integer.
Definition: BitVector.h:1212
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:901
bool subtract(const BitRange &range1, const BitVector &other, const BitRange &range2)
Subtract bits as integers.
Definition: BitVector.h:809
BitVector & shiftRightArithmetic(const BitRange &range, size_t nShift)
Shift bits right.
Definition: BitVector.h:647
BitVector & fromDecimal(const std::string &input)
Obtain bits from a decimal representation.
Definition: BitVector.h:1240
Optional< size_t > leastSignificantClearBit() const
Find the least significant clear bit.
Definition: BitVector.h:399
static BitVector parse(std::string str)
Create a bit vector by reading a string.
Definition: BitVector.h:106
BitVector & shiftRightArithmetic(size_t nShift)
Shift bits right.
Definition: BitVector.h:661
Optional< size_t > leastSignificantDifference(const BitVector &other) const
Find least significant difference.
Definition: BitVector.h:581
void shiftRight(Word *words, const BitRange &range, size_t nShift, bool newBits=0)
Shift bits right.
BitVector & fromInteger(const BitRange &range, boost::uint64_t value)
Obtain bits from an integer.
Definition: BitVector.h:1199
Name space for the entire library.
Definition: Access.h:13
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:885
BitVector()
Default construct an empty vector.
Definition: BitVector.h:83
void shiftLeft(Word *words, const BitRange &range, size_t nShift, bool newBits=0)
Shift bits left.
BitVector & negate(const BitRange &range1)
Negates bits as integer.
Definition: BitVector.h:716
Optional< size_t > leastSignificantClearBit(const Word *words, const BitRange &range)
Index of least significant zero bit.
Optional< size_t > mostSignificantClearBit() const
Find the most significant clear bit.
Definition: BitVector.h:435
BitVector & shiftRight(size_t nShift, bool newBits=0)
Shift bits right.
Definition: BitVector.h:634
static Interval baseSize(size_t lo, size_t size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:161
BitVector & signExtend(const BitVector &other)
Copy bits and sign extend.
Definition: BitVector.h:867
BitVectorSupport::BitRange BitRange
Describes an inclusive interval of bit indices.
Definition: BitVector.h:67
size_t nSet() const
Number of set bits.
Definition: BitVector.h:486
size_t size() const
Size of vector in bits.
Definition: BitVector.h:189
size_t nClear(const Word *words, const BitRange &range)
Number of clear bits.
bool decrement(const BitRange &range1)
Decrement bits as integer.
Definition: BitVector.h:754
BitVector & invert()
Invert bits.
Definition: BitVector.h:910
std::string toOctal(const BitRange &range) const
Convert to an octal string.
Definition: BitVector.h:1162
BitVector & shiftLeft(size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:609
int compare(const BitVector &other) const
Compare bits as integers.
Definition: BitVector.h:1069
size_t dataSize() const
Raw data size.
Definition: BitVector.h:1356
BitVector & bitwiseOr(const BitRange &range1, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:963
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:942
size_t nClear(const BitRange &range) const
Number of clear bits.
Definition: BitVector.h:493
void rotateLeft(Word *words, const BitRange &range, size_t nShift)
Rotate bits to the left.
bool increment(const BitRange &range1)
Increment bits as integer.
Definition: BitVector.h:736
Optional< size_t > mostSignificantClearBit(const BitRange &range) const
Find the most significant clear bit.
Definition: BitVector.h:426
bool isAllSet(const BitRange &range) const
True if all bits are set.
Definition: BitVector.h:443
void swap(Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Swap some bits.
int compareSigned(const BitVector &other) const
Compare bits as signed integers.
Definition: BitVector.h:1109
bool subtract(const BitVector &other)
Subtract bits as integers.
Definition: BitVector.h:834
static Interval hull(size_t v1, size_t v2)
Construct an interval from two endpoints.
Definition: Interval.h:150
void shiftRightArithmetic(Word *words, const BitRange &range, size_t nShift)
Shift bits right arithmetically.
void bitwiseXor(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Bit-wise XOR.
Optional< size_t > mostSignificantSetBit() const
Find the most significant set bit.
Definition: BitVector.h:417
Optional< size_t > leastSignificantSetBit(const Word *words, const BitRange &range)
Index of least significant set bit.
BitVector & bitwiseXor(const BitRange &range1, const BitVector &other, const BitRange &range2)
Bit-wise XOR.
Definition: BitVector.h:984
std::string toHex(const Word *vec, const BitRange &range)
Hexadecimal representation.
Optional< size_t > mostSignificantDifference(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Find most significant difference.
Definition: BitVector.h:515
Optional< size_t > leastSignificantDifference(const BitRange &range1, const BitRange &range2) const
Find least significant difference.
Definition: BitVector.h:570
int compare(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Unsigned comparison.
bool subtract(const BitRange &range1, const BitRange &range2)
Subtract bits as integers.
Definition: BitVector.h:823
boost::uint64_t toInteger(const BitRange &range) const
Interpret bits as an unsigned integer.
Definition: BitVector.h:1121
Optional< size_t > mostSignificantSetBit(const Word *words, const BitRange &range)
Index of most significant set bit.
boost::uint64_t toInteger(const Word *words, const BitRange &range)
Convert a bit vector to an integer.
Optional< size_t > leastSignificantClearBit(const BitRange &range) const
Find the least significant clear bit.
Definition: BitVector.h:390
bool add(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2, bool carryIn=false)
Add bits.
bool signExtend(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Sign extend.
bool decrement()
Decrement bits as integer.
Definition: BitVector.h:763
bool isAllClear(const Word *words, const BitRange &range)
True if all bits are clear.
Optional< size_t > mostSignificantSetBit(const BitRange &range) const
Find the most significant set bit.
Definition: BitVector.h:408
BitVector(const BitVector &other)
Copy constructor.
Definition: BitVector.h:86
Optional< size_t > mostSignificantDifference(const BitRange &range1, const BitRange &range2) const
Find most significant difference.
Definition: BitVector.h:530
void fromHex(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a hexadecimal representation.
boost::uint64_t toInteger() const
Interpret bits as an unsigned integer.
Definition: BitVector.h:1130
BitVector & clear()
Assign zero to all bits.
Definition: BitVector.h:273
Optional< size_t > leastSignificantSetBit() const
Find the least significant set bit.
Definition: BitVector.h:381
int compareSigned(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Signed comparison.
BitVector & fromBinary(const std::string &input)
Obtain bits from a binary representation.
Definition: BitVector.h:1321
void clear(Word *words, const BitRange &where)
Clear some bits.
BitVector & signExtend(const BitRange &range1, const BitVector &other, const BitRange &range2)
Copy bits and sign extend.
Definition: BitVector.h:844
BitVector & rotateLeft(const BitRange &range, size_t nShift)
Rotate bits left.
Definition: BitVector.h:692
bool add(const BitRange &range1, const BitVector &other, const BitRange &range2)
Add bits as integers.
Definition: BitVector.h:773
BitVector & bitwiseOr(const BitRange &range1, const BitVector &other, const BitRange &range2)
Bit-wise OR.
Definition: BitVector.h:952
const Word * data() const
Raw data for vector.
Definition: BitVector.h:1348
void set(Word *words, const BitRange &where)
Set some bits.
bool isEqualToZero(const BitRange &range) const
Compare to zero.
Definition: BitVector.h:1021
Optional< size_t > leastSignificantSetBit(const BitRange &range) const
Find the least significant set bit.
Definition: BitVector.h:372
void bitwiseAnd(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Bit-wise AND.
int compare(const BitRange &range1, const BitRange &range2) const
Compare bits as integers.
Definition: BitVector.h:1056
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:1280
BitVector & shiftLeft(const BitRange &range, size_t nShift, bool newBits=0)
Shift bits left.
Definition: BitVector.h:596
std::string toBinary(const Word *vec, const BitRange &range)
Binary representation.
BitVector & rotateLeft(size_t nShift)
Rotate bits left.
Definition: BitVector.h:703
BitVector & bitwiseXor(const BitVector &other)
Bit-wise XOR.
Definition: BitVector.h:1006
BitVector & bitwiseXor(const BitRange &range1, const BitRange &range2)
Bit-wise XOR.
Definition: BitVector.h:995
int compare(const BitRange &range1, const BitVector &other, const BitRange &range2) const
Compare bits as integers.
Definition: BitVector.h:1043
bool isAllSet() const
True if all bits are set.
Definition: BitVector.h:451
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:1190
size_t nSet(const Word *words, const BitRange &range)
Number of set bits.
BitVector & negate()
Negates bits as integer.
Definition: BitVector.h:726
bool isEqualToZero(const Word *vec1, const BitRange &range1)
Compares with zero.
void bitwiseOr(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Bit-wise OR.
bool add(const BitVector &other)
Add bits as integers.
Definition: BitVector.h:796
BitVector & resize(size_t newSize, bool newBits=false)
Change vector size.
Definition: BitVector.h:196
bool isAllClear() const
True if all bits are clear.
Definition: BitVector.h:471
bool isAllClear(const BitRange &range) const
True if all bits are clear.
Definition: BitVector.h:461
BitVector & copy(const BitRange &to, const BitRange &from)
Copy some bits.
Definition: BitVector.h:333
bool increment()
Increment bits as integer.
Definition: BitVector.h:745
Optional< size_t > mostSignificantDifference(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Find most significant different bits.
std::string toHex(const BitRange &range) const
Convert to a hexadecimal string.
Definition: BitVector.h:1142
size_t capacity() const
Maximum size before reallocation.
Definition: BitVector.h:217
std::string toHex() const
Convert to a hexadecimal string.
Definition: BitVector.h:1152