ROSE  0.9.9.109
BitVectorSupport.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_BitVectorSupport_H
9 #define Sawyer_BitVectorSupport_H
10 
11 #include <algorithm>
12 #include <boost/cstdint.hpp>
13 #include <boost/foreach.hpp>
14 #include <boost/lexical_cast.hpp>
15 #include <cstring>
16 #include <Sawyer/Assert.h>
17 #include <Sawyer/Interval.h>
18 #include <Sawyer/Optional.h>
19 #include <Sawyer/Sawyer.h>
20 #include <string>
21 #include <vector>
22 
23 namespace Sawyer {
24 namespace Container {
25 
27 namespace BitVectorSupport {
28 
30 template<class T> struct RemoveConst { typedef T Base; };
31 template<class T> struct RemoveConst<const T> { typedef T Base; };
32 
34 
36 struct LowToHigh {};
37 struct HighToLow {};
38 
40 template<class Word>
41 struct bitsPerWord {
42  enum { value = 8 * sizeof(Word) };
43 };
44 
48 template<class Word>
49 size_t wordIndex(size_t idx) {
50  return idx / bitsPerWord<Word>::value;
51 }
52 
56 template<class Word>
57 size_t bitIndex(size_t idx) {
58  return idx % bitsPerWord<Word>::value;
59 }
60 
62 template<class Word>
63 size_t numberOfWords(size_t nbits) {
65 }
66 
71 template<class Word>
72 Word bitMask(size_t offset, size_t nbits) {
73  ASSERT_require(offset + nbits <= bitsPerWord<Word>::value);
74  Word mask = nbits == bitsPerWord<Word>::value ? Word(-1) : (Word(1) << nbits) - 1;
75  return mask << offset;
76 }
77 
83 template<class Processor, class Word>
84 bool processWord(Processor &processor, const Word &word, size_t shift, size_t nbits) {
85  ASSERT_require(shift < bitsPerWord<Word>::value);
86  ASSERT_require(nbits <= bitsPerWord<Word>::value);
87  const Word tmp = word >> shift;
88  return processor(tmp, nbits);
89 }
90 
91 template<class Processor, class Word>
92 bool processWord(Processor &processor, Word &word, size_t shift, size_t nbits) {
93  ASSERT_require(shift < bitsPerWord<Word>::value);
94  Word tmp = word >> shift;
95  bool retval = processor(tmp, nbits);
96  word &= ~bitMask<Word>(shift, nbits);
97  word |= (tmp & bitMask<Word>(0, nbits)) << shift;
98  return retval;
99 }
100 
101 template<class Processor, class Word>
102 bool processWord(Processor &processor, const Word &src, Word &dst, size_t shift, size_t nbits) {
103  ASSERT_require(shift < bitsPerWord<Word>::value);
104  ASSERT_require(nbits <= bitsPerWord<Word>::value);
105  const Word tmpSrc = src >> shift;
106  Word tmpDst = dst >> shift;
107  bool retval = processor(tmpSrc, tmpDst, nbits);
108  dst &= ~bitMask<Word>(shift, nbits);
109  dst |= (tmpDst & bitMask<Word>(0, nbits)) << shift;
110  return retval;
111 }
112 template<class Processor, class Word>
113 bool processWord(Processor &processor, Word &w1, Word &w2, size_t shift, size_t nbits) {
114  ASSERT_require(shift < bitsPerWord<Word>::value);
115  ASSERT_require(nbits <= bitsPerWord<Word>::value);
116  Word tmp1 = w1 >> shift;
117  Word tmp2 = w2 >> shift;
118  bool retval = processor(tmp1, tmp2, nbits);
119  Word mask = bitMask<Word>(shift, nbits);
120  w1 &= ~mask;
121  w1 |= (tmp1 << shift) & mask;
122  w2 &= ~mask;
123  w2 |= (tmp2 << shift) & mask;
124  return retval;
125 }
126 template<class Processor, class Word>
127 bool processWord(Processor &processor, const Word &w1, const Word &w2, size_t shift, size_t nbits) {
128  ASSERT_require(shift < bitsPerWord<Word>::value);
129  ASSERT_require(nbits <= bitsPerWord<Word>::value);
130  Word tmp1 = w1 >> shift;
131  Word tmp2 = w2 >> shift;
132  return processor(tmp1, tmp2, nbits);
133 }
136 // Internal function to copy bits from one place to another. The two places must not overlap.
137 template<class Word>
138 void nonoverlappingCopy(const Word *src, const BitRange &srcRange, Word *dst, const BitRange &dstRange) {
139  ASSERT_require(srcRange.size()==dstRange.size());
140  ASSERT_require(src != dst);
141 
142  size_t dstFirstIdx = wordIndex<Word>(dstRange.least());
143  size_t dstLastIdx = wordIndex<Word>(dstRange.greatest());
144  size_t srcFirstIdx = wordIndex<Word>(srcRange.least());
145  size_t srcLastIdx = wordIndex<Word>(srcRange.greatest());
146 
147  size_t srcOffset = srcFirstIdx - dstFirstIdx; // overflow is okay
148 
149  size_t srcBitIdx = bitIndex<Word>(srcRange.least());
150  size_t dstBitIdx = bitIndex<Word>(dstRange.least());
151 
152  if (srcBitIdx < dstBitIdx) {
153  // This is effectively a left shift, taking data from lower src elements
154  const size_t leftShiftAmount = dstBitIdx - srcBitIdx;
155  const size_t rightShiftAmount = bitsPerWord<Word>::value - leftShiftAmount;
156 
157  for (size_t i=dstFirstIdx; i<=dstLastIdx; ++i) {
158  const Word tmp = (i+srcOffset > srcFirstIdx ? (src[i+srcOffset-1] >> rightShiftAmount) : Word(0)) |
159  (i+srcOffset > srcLastIdx ? Word(0) : (src[i+srcOffset] << leftShiftAmount));
160  Word mask = bitMask<Word>(0, bitsPerWord<Word>::value);
161  if (i==dstFirstIdx)
162  mask &= ~bitMask<Word>(0, bitIndex<Word>(dstRange.least()));
163  if (i==dstLastIdx)
164  mask &= bitMask<Word>(0, bitIndex<Word>(dstRange.greatest())+1);
165  dst[i] &= ~mask;
166  dst[i] |= tmp & mask;
167  }
168  } else if (srcBitIdx > dstBitIdx) {
169  // This is effectively a right shift, taking data from higher src elements
170  const size_t rightShiftAmount = srcBitIdx - dstBitIdx;
171  const size_t leftShiftAmount = bitsPerWord<Word>::value - rightShiftAmount;
172 
173  for (size_t i=dstFirstIdx; i<=dstLastIdx; ++i) {
174  const Word tmp = (src[i+srcOffset] >> rightShiftAmount) |
175  (i+srcOffset+1 <= srcLastIdx ? (src[i+srcOffset+1] << leftShiftAmount) : Word(0));
176  Word mask = bitMask<Word>(0, bitsPerWord<Word>::value);
177  if (i==dstFirstIdx)
178  mask &= ~bitMask<Word>(0, bitIndex<Word>(dstRange.least()));
179  if (i==dstLastIdx)
180  mask &= bitMask<Word>(0, bitIndex<Word>(dstRange.greatest())+1);
181  dst[i] &= ~mask;
182  dst[i] |= tmp & mask;
183  }
184  } else {
185  // No shifting necessary
186  for (size_t i=dstFirstIdx; i<=dstLastIdx; ++i) {
187  const Word tmp = src[i+srcOffset];
188  Word mask = bitMask<Word>(0, bitsPerWord<Word>::value);
189  if (i==dstFirstIdx)
190  mask &= ~bitMask<Word>(0, bitIndex<Word>(dstRange.least()));
191  if (i==dstLastIdx)
192  mask &= bitMask<Word>(0, bitIndex<Word>(dstRange.greatest())+1);
193  dst[i] &= ~mask;
194  dst[i] |= tmp & mask;
195  }
196  }
197 }
198 
199 template<class Src, class Dst>
200 void conditionalCopy(const Src *src, const BitRange &srcRange, Dst *dst, const BitRange &dstRange) {
201  nonoverlappingCopy(src, srcRange, dst, dstRange);
202 }
203 template<class Src, class Dst>
204 void conditionalCopy(const Src */*src*/, const BitRange &/*srcRange*/, const Dst */*dst*/, const BitRange &/*dstRange*/) {
205  // do not copy when dst is const
206 }
207 
213 template<class Processor, class Word>
214 void traverse(Processor &processor, Word *words, const BitRange &range, LowToHigh) {
215  if (range.isEmpty())
216  return;
217  size_t nRemaining = range.size();
218  size_t offsetInWord = bitIndex<Word>(range.least());
219  bool done = false;
220  for (size_t wordIdx = wordIndex<Word>(range.least()); !done && nRemaining > 0; ++wordIdx) {
221  size_t nbits = std::min(bitsPerWord<Word>::value - offsetInWord, nRemaining);
222  ASSERT_require(nbits > 0);
223  done = processWord(processor, words[wordIdx], offsetInWord, nbits);
224  offsetInWord = 0; // only the first word has an internal bit offset
225  nRemaining -= nbits;
226  }
227 }
228 
230 template<class Processor, class Word>
231 void traverse(Processor &processor, Word *words, const BitRange &range, HighToLow) {
232  if (range.isEmpty())
233  return;
234  size_t nRemaining = range.size();
235  size_t offsetInWord = bitIndex<Word>(range.least());
236  bool done = false;
237  size_t firstWordIdx = wordIndex<Word>(range.least());
238  size_t lastWordIdx = wordIndex<Word>(range.greatest());
239  for (size_t wordIdx=lastWordIdx; !done && nRemaining > 0; --wordIdx) {
240  size_t nbits;
241  if (wordIdx == firstWordIdx) {
242  ASSERT_require(nRemaining <= bitsPerWord<Word>::value);
243  nbits = nRemaining;
244  } else if (wordIdx < lastWordIdx) {
245  ASSERT_require(nRemaining > bitsPerWord<Word>::value);
246  nbits = bitsPerWord<Word>::value;
247  } else {
248  ASSERT_require(wordIdx==lastWordIdx);
249  ASSERT_require(wordIdx>firstWordIdx);
250  size_t nBitsToLeft = (bitsPerWord<Word>::value - offsetInWord) +
251  (lastWordIdx-firstWordIdx-1) * bitsPerWord<Word>::value;
252  ASSERT_require(nRemaining > nBitsToLeft);
253  nbits = nRemaining - nBitsToLeft;
254  ASSERT_require(nbits <= bitsPerWord<Word>::value);
255  }
256  done = processWord(processor, words[wordIdx], wordIdx==firstWordIdx ? offsetInWord : 0, nbits);
257  nRemaining -= nbits;
258  }
259 }
260 
262 template<class Processor, class Word1, class Word2>
263 void traverse2(Processor &processor, Word1 *vec1, const BitRange &range1, Word2 *vec2, const BitRange &range2, LowToHigh) {
264  ASSERT_require(sizeof(Word1)==sizeof(Word2)); // may differ in constness
265  ASSERT_require((range1.isEmpty() && range2.isEmpty()) || (!range1.isEmpty() && !range2.isEmpty()));
266  if (range1.isEmpty())
267  return;
268  ASSERT_require(range1.size() == range2.size());
269 
270  // Make a copy of the source and give it the same bit alignment as the destination. This not only makes traversal easier
271  // (since we can traverse whole words at a time) but it also makes it so we don't need to worry about traversal order when
272  // the source and destination overlap.
273  size_t offsetInWord = bitIndex<Word2>(range2.least());
274  const size_t nWordsTmp = numberOfWords<Word2>(offsetInWord + range2.size());
275  SAWYER_VARIABLE_LENGTH_ARRAY(typename RemoveConst<Word1>::Base, tmp, nWordsTmp);
276  memset(tmp, 0, nWordsTmp*sizeof(*tmp)); // only for making debugging easier
277  BitRange tmpRange = BitRange::baseSize(offsetInWord, range1.size());
278  nonoverlappingCopy(vec1, range1, tmp, tmpRange);
279 
280  // Do the traversal. The first iteration's words are offset by offsetInWord bits, the remainder start at bit zero. All the
281  // words except possibly the first and last are the full size.
282  const size_t vec2WordOffset = wordIndex<Word2>(range2.least());
283  size_t nRemaining = range2.size();
284  bool done = false;
285  for (size_t wordIdx=0; !done && nRemaining > 0; ++wordIdx) {
286  ASSERT_require(wordIdx < nWordsTmp);
287  size_t nbits = std::min(bitsPerWord<Word2>::value - offsetInWord, nRemaining);
288  ASSERT_require(nbits > 0);
289  done = processWord(processor, *const_cast<Word1*>(tmp+wordIdx), vec2[wordIdx+vec2WordOffset], offsetInWord, nbits);
290  offsetInWord = 0; // only the first word has an internal bit offset
291  nRemaining -= nbits;
292  }
293 
294  // Copy tmp back into vec1, but only if vec1 is non-const
295  conditionalCopy(tmp, tmpRange, vec1, range1);
296 }
297 
299 template<class Processor, class Word1, class Word2>
300 void traverse2(Processor &processor, Word1 *vec1, const BitRange &range1, Word2 *vec2, const BitRange &range2, HighToLow) {
301  ASSERT_require(sizeof(Word1)==sizeof(Word2)); // may differ in constness
302  ASSERT_require((range1.isEmpty() && range2.isEmpty()) || (!range1.isEmpty() && !range2.isEmpty()));
303  if (range1.isEmpty())
304  return;
305  ASSERT_require(range1.size() == range2.size());
306 
307  // Make a copy of the source and give it the same bit alignment as the destination. This not only makes traversal easier
308  // (since we can traverse whole words at a time) but it also makes it so we don't need to worry about traversal order when
309  // the source and destination overlap.
310  const size_t offsetInWord = bitIndex<Word2>(range2.least());
311  const size_t nWordsTmp = numberOfWords<Word2>(offsetInWord + range2.size());
312  SAWYER_VARIABLE_LENGTH_ARRAY(typename RemoveConst<Word1>::Base, tmp, nWordsTmp);
313  BitRange tmpRange = BitRange::baseSize(offsetInWord, range1.size());
314  nonoverlappingCopy(vec1, range1, tmp, tmpRange);
315 
316  // Traversal high-to-low.
317  size_t nRemaining = range2.size();
318  bool done = false;
319  const size_t vec2WordOffset = wordIndex<Word2>(range2.least());
320  for (size_t wordIdx=nWordsTmp-1; !done && nRemaining>0; --wordIdx) {
321  size_t nbits;
322  if (wordIdx == 0) {
323  ASSERT_require(nRemaining <= bitsPerWord<Word2>::value);
324  nbits = nRemaining;
325  } else if (wordIdx < nWordsTmp-1) {
326  ASSERT_require(nRemaining > bitsPerWord<Word2>::value);
328  } else {
329  ASSERT_require(wordIdx==nWordsTmp-1);
330  ASSERT_require(wordIdx>0);
331  size_t nBitsToLeft = (bitsPerWord<Word2>::value - offsetInWord) + (nWordsTmp-2) * bitsPerWord<Word2>::value;
332  ASSERT_require(nRemaining > nBitsToLeft);
333  nbits = nRemaining - nBitsToLeft;
334  ASSERT_require(nbits <= bitsPerWord<Word2>::value);
335  }
336  done = processWord(processor, *const_cast<Word1*>(tmp+wordIdx), vec2[wordIdx+vec2WordOffset],
337  wordIdx==0 ? offsetInWord : 0, nbits);
338  nRemaining -= nbits;
339  }
340 
341  // Copy tmp back into vec1, but only if vec1 is non-const
342  conditionalCopy(tmp, tmpRange, vec1, range1);
343 }
344 
345 template<class Processor, class Word>
346 void traverse(Processor &processor,
347  const Word *vec1, const BitRange &range1,
348  const Word *vec2, const BitRange &range2,
349  HighToLow dir) {
350  traverse2(processor, vec1, range1, vec2, range2, dir);
351 }
352 
353 template<class Processor, class Word>
354 void traverse(Processor &processor,
355  const Word *vec1, const BitRange &range1,
356  const Word *vec2, const BitRange &range2,
357  LowToHigh dir) {
358  traverse2(processor, vec1, range1, vec2, range2, dir);
359 }
360 template<class Processor, class Word>
361 void traverse(Processor &processor,
362  const Word *vec1, const BitRange &range1,
363  Word *vec2, const BitRange &range2,
364  LowToHigh dir) {
365  traverse2(processor, vec1, range1, vec2, range2, dir);
366 }
367 template<class Processor, class Word>
368 void traverse(Processor &processor,
369  Word *vec1, const BitRange &range1,
370  Word *vec2, const BitRange &range2,
371  LowToHigh dir) {
372  traverse2(processor, vec1, range1, vec2, range2, dir);
373 }
374 
375 
376 
378 // Bit accessors
380 
384 template<class Word>
385 bool get(const Word *words, size_t idx) {
386  return 0 != (words[wordIndex<Word>(idx)] & bitMask<Word>(bitIndex<Word>(idx), 1));
387 }
388 
389 template<class Word>
390 struct ClearBits {
391  bool operator()(Word &word, size_t nbits) {
392  word &= ~bitMask<Word>(0, nbits);
393  return false;
394  }
395 };
396 
400 template<class Word>
401 void clear(Word *words, const BitRange &where) {
402  ClearBits<Word> visitor;
403  traverse(visitor, words, where, LowToHigh());
404 }
405 
406 template<class Word>
407 struct SetBits {
408  bool operator()(Word &word, size_t nbits) {
409  word |= bitMask<Word>(0, nbits);
410  return false;
411  }
412 };
413 
417 template<class Word>
418 void set(Word *words, const BitRange &where) {
419  SetBits<Word> visitor;
420  traverse(visitor, words, where, LowToHigh());
421 }
422 
426 template<class Word>
427 void setValue(Word *words, const BitRange &where, bool value) {
428  if (value) {
429  set(words, where);
430  } else {
431  clear(words, where);
432  }
433 }
434 
435 template<class Word>
436 struct CopyBits {
437  bool operator()(const Word &src, Word &dst, size_t nbits) {
438  dst &= ~bitMask<Word>(0, nbits);
439  dst |= src & bitMask<Word>(0, nbits);
440  return false;
441  }
442 };
443 
448 template<class Word>
449 void copy(const Word *src, const BitRange &srcRange, Word *dst, const BitRange &dstRange) {
450  CopyBits<Word> visitor;
451  traverse(visitor, src, srcRange, dst, dstRange, LowToHigh());
452 }
453 
454 template<class Word>
455 struct SwapBits {
456  bool operator()(Word &w1, Word &w2, size_t nbits) {
457  Word tmp = w1, mask = bitMask<Word>(0, nbits);
458  w1 &= ~mask;
459  w1 |= w2 & mask;
460  w2 &= ~mask;
461  w2 |= tmp & mask;
462  return false;
463  }
464 };
465 
470 template<class Word>
471 void swap(Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
472  SwapBits<Word> visitor;
473  ASSERT_require(vec1!=vec2 || !range1.isOverlapping(range2));
474  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
475 }
476 
477 
479 // Counting/searching
481 
482 
483 template<class Word>
485  size_t offset;
486  Optional<size_t> result;
487  LeastSignificantSetBit(): offset(0) {}
488  bool operator()(const Word &word, size_t nbits) {
489  if (0 != (word & bitMask<Word>(0, nbits))) {
490  for (size_t i=0; i<nbits; ++i) {
491  if (0 != (word & bitMask<Word>(i, 1))) {
492  result = offset + i;
493  return true;
494  }
495  }
496  }
497  offset += nbits;
498  return false;
499  }
500 };
501 
506 template<class Word>
507 Optional<size_t> leastSignificantSetBit(const Word *words, const BitRange &range) {
509  traverse(visitor, words, range, LowToHigh());
510  if (visitor.result)
511  return range.least() + *visitor.result;
512  return Nothing();
513 }
514 
515 template<class Word>
517  size_t offset;
518  Optional<size_t> result;
519  LeastSignificantClearBit(): offset(0) {}
520  bool operator()(const Word &word, size_t nbits) {
521  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
522  for (size_t i=0; i<nbits; ++i) {
523  if (0 == (word & bitMask<Word>(i, 1))) {
524  result = offset + i;
525  return true;
526  }
527  }
528  }
529  offset += nbits;
530  return false;
531  }
532 };
533 
538 template<class Word>
539 Optional<size_t> leastSignificantClearBit(const Word *words, const BitRange &range) {
541  traverse(visitor, words, range, LowToHigh());
542  if (visitor.result)
543  return range.least() + *visitor.result;
544  return Nothing();
545 }
546 
547 template<class Word>
549  size_t offset;
550  Optional<size_t> result;
551  MostSignificantSetBit(size_t nbits): offset(nbits) {}
552  bool operator()(const Word &word, size_t nbits) {
553  ASSERT_require(nbits <= offset);
554  offset -= nbits;
555  if (0 != (word & bitMask<Word>(0, nbits))) {
556  for (size_t i=nbits; i>0; --i) {
557  if (0 != (word & bitMask<Word>(i-1, 1))) {
558  result = offset + i-1;
559  return true;
560  }
561  }
562  }
563  return false;
564  }
565 };
566 
571 template<class Word>
572 Optional<size_t> mostSignificantSetBit(const Word *words, const BitRange &range) {
573  MostSignificantSetBit<Word> visitor(range.size());
574  traverse(visitor, words, range, HighToLow());
575  if (visitor.result)
576  return range.least() + *visitor.result;
577  return Nothing();
578 }
579 
580 template<class Word>
582  size_t offset;
583  Optional<size_t> result;
584  MostSignificantClearBit(size_t nbits): offset(nbits) {}
585  bool operator()(const Word &word, size_t nbits) {
586  ASSERT_require(nbits <= offset);
587  offset -= nbits;
588  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
589  for (size_t i=nbits; i>0; --i) {
590  if (0 == (word & bitMask<Word>(i-1, 1))) {
591  result = offset + i-1;
592  return true;
593  }
594  }
595  }
596  return false;
597  }
598 };
599 
604 template<class Word>
605 Optional<size_t> mostSignificantClearBit(const Word *words, const BitRange &range) {
606  MostSignificantClearBit<Word> visitor(range.size());
607  traverse(visitor, words, range, HighToLow());
608  if (visitor.result)
609  return range.least() + *visitor.result;
610  return Nothing();
611 }
612 
616 template<class Word>
617 bool isAllSet(const Word *words, const BitRange &range) {
618  return leastSignificantClearBit(words, range) ? false : true;
619 }
620 
624 template<class Word>
625 bool isAllClear(const Word *words, const BitRange &range) {
626  return leastSignificantSetBit(words, range) ? false : true;
627 }
628 
629 template<class Word>
630 struct CountSetBits {
631  size_t result;
632  CountSetBits(): result(0) {}
633  bool operator()(const Word &word, size_t nbits) {
634  if (0 != (word & bitMask<Word>(0, nbits))) {
635  for (size_t i=0; i<nbits; ++i) {
636  if (0 != (word & bitMask<Word>(i, 1)))
637  ++result;
638  }
639  }
640  return false;
641  }
642 };
643 
647 template<class Word>
648 size_t nSet(const Word *words, const BitRange &range) {
649  CountSetBits<Word> visitor;
650  traverse(visitor, words, range, LowToHigh());
651  return visitor.result;
652 }
653 
654 template<class Word>
656  size_t result;
657  CountClearBits(): result(0) {}
658  bool operator()(const Word &word, size_t nbits) {
659  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
660  for (size_t i=0; i<nbits; ++i) {
661  if (0 == (word & bitMask<Word>(i, 1)))
662  ++result;
663  }
664  }
665  return false;
666  }
667 };
668 
672 template<class Word>
673 size_t nClear(const Word *words, const BitRange &range) {
674  CountClearBits<Word> visitor;
675  traverse(visitor, words, range, LowToHigh());
676  return visitor.result;
677 }
678 
679 template<class Word>
681  size_t offset;
682  Optional<size_t> result;
683  LeastSignificantDifference(): offset(0) {}
684  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
685  Word mask = bitMask<Word>(0, nbits);
686  if ((w1 & mask) != (w2 & mask)) {
687  for (size_t i=0; i<nbits; ++i) {
688  if ((w1 ^ w2) & bitMask<Word>(i, 1)) {
689  result = offset + i;
690  return true;
691  }
692  }
693  }
694  offset += nbits;
695  return false;
696  }
697 };
698 
704 template<class Word>
705 Optional<size_t> leastSignificantDifference(const Word *vec1, const BitRange &range1,
706  const Word *vec2, const BitRange &range2) {
708  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
709  return visitor.result;
710 }
711 
712 template<class Word>
714  size_t offset;
715  Optional<size_t> result;
716  MostSignificantDifference(size_t nbits): offset(nbits) {}
717  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
718  ASSERT_require(nbits <= offset);
719  offset -= nbits;
720  Word mask = bitMask<Word>(0, nbits);
721  if ((w1 & mask) != (w2 & mask)) {
722  for (size_t i=nbits; i>0; --i) {
723  if ((w1 ^ w2) & bitMask<Word>(i-1, 1)) {
724  result = offset + i-1;
725  return true;
726  }
727  }
728  }
729  return false;
730  }
731 };
732 
738 template<class Word>
739 Optional<size_t> mostSignificantDifference(const Word *vec1, const BitRange &range1,
740  const Word *vec2, const BitRange &range2) {
741  MostSignificantDifference<Word> visitor(range1.size());
742  traverse(visitor, vec1, range1, vec2, range2, HighToLow());
743  return visitor.result;
744 }
745 
750 template<class Word>
751 bool areEqual(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
752  if (range1.size()!=range2.size())
753  return false;
754  return leastSignificantDifference(vec1, range1, vec2, range2) ? false : true;
755 }
756 
758 // Shift/rotate
760 
765 template<class Word>
766 void shiftLeft(Word *words, const BitRange &range, size_t nShift, bool newBits=0) {
767  if (nShift < range.size()) {
768  size_t nbits = range.size() - nShift; // number of bits to move
769  BitRange shiftedFrom = BitRange::baseSize(range.least(), nbits);
770  BitRange shiftedTo = BitRange::baseSize(range.least() + nShift, nbits);
771  BitRange introduced = BitRange::baseSize(range.least(), nShift);
772  copy(words, shiftedFrom, words, shiftedTo);
773  setValue(words, introduced, newBits);
774  } else {
775  setValue(words, range, newBits);
776  }
777 }
778 
783 template<class Word>
784 void shiftRight(Word *words, const BitRange &range, size_t nShift, bool newBits=0) {
785  if (nShift < range.size()) {
786  size_t nbits = range.size() - nShift; // number of bits to move
787  BitRange shiftedFrom = BitRange::baseSize(range.least() + nShift, nbits);
788  BitRange shiftedTo = BitRange::baseSize(range.least(), nbits);
789  BitRange introduced = BitRange::baseSize(range.least() + nbits, nShift);
790  copy(words, shiftedFrom, words, shiftedTo);
791  setValue(words, introduced, newBits);
792  } else {
793  setValue(words, range, newBits);
794  }
795 }
796 
801 template<class Word>
802 void shiftRightArithmetic(Word *words, const BitRange &range, size_t nShift) {
803  if (!range.isEmpty()) {
804  bool newBits = get(words, range.greatest());
805  shiftRight(words, range, nShift, newBits);
806  }
807 }
808 
813 template<class Word>
814 void rotateRight(Word *words, const BitRange &range, size_t nShift) {
815  if (range.isEmpty())
816  return;
817  nShift %= range.size();
818  if (0==nShift)
819  return;
820 
821  // Save the low-order bits that will be shifted off
822  size_t nSavedWords = numberOfWords<Word>(nShift);
823  SAWYER_VARIABLE_LENGTH_ARRAY(Word, saved, nSavedWords);
824  BitRange savedRange = BitRange::baseSize(0, nShift);
825  copy(words, BitRange::baseSize(range.least(), nShift), saved, savedRange);
826 
827  shiftRight(words, range, nShift);
828 
829  BitRange introduced = BitRange::baseSize(range.least()+range.size()-nShift, nShift);
830  copy(saved, savedRange, words, introduced);
831 }
832 
837 template<class Word>
838 void rotateLeft(Word *words, const BitRange &range, size_t nShift) {
839  if (range.isEmpty())
840  return;
841  nShift %= range.size();
842  rotateRight(words, range, range.size()-nShift);
843 }
844 
845 
847 // Bit-wise Boolean logic
849 
850 template<class Word>
851 struct InvertBits {
852  bool operator()(Word &word, size_t nbits) {
853  word ^= bitMask<Word>(0, nbits);
854  return false;
855  }
856 };
857 
861 template<class Word>
862 void invert(Word *words, const BitRange &range) {
863  InvertBits<Word> visitor;
864  traverse(visitor, words, range, LowToHigh());
865 }
866 
867 template<class Word>
868 struct AndBits {
869  bool operator()(const Word &w1, Word &w2, size_t nbits) {
870  w2 &= w1 | ~bitMask<Word>(0, nbits);
871  return false;
872  }
873 };
874 
879 template<class Word>
880 void bitwiseAnd(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
881  AndBits<Word> visitor;
882  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
883 }
884 
885 template<class Word>
886 struct OrBits {
887  bool operator()(const Word &w1, Word &w2, size_t nbits) {
888  w2 |= w1 & bitMask<Word>(0, nbits);
889  return false;
890  }
891 };
892 
897 template<class Word>
898 void bitwiseOr(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
899  OrBits<Word> visitor;
900  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
901 }
902 
903 template<class Word>
904 struct XorBits {
905  bool operator()(const Word &w1, Word &w2, size_t nbits) {
906  w2 ^= w1 & bitMask<Word>(0, nbits);
907  return false;
908  }
909 };
910 
915 template<class Word>
916 void bitwiseXor(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
917  XorBits<Word> visitor;
918  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
919 }
920 
921 
923 // Arithmetic
925 
929 template<class Word>
930 void fromInteger(Word *words, const BitRange &range, boost::uint64_t value) {
931  ASSERT_require(8==sizeof value);
932  if (range.isEmpty())
933  return;
934 
935  // Create a bit vector that is just the value
936  size_t nbits = std::min(range.size(), (size_t)64); // number of significant bits to copy, not fill
937  Word wordMask = bitMask<Word>(0, bitsPerWord<Word>::value);
938  size_t nTmpWords = numberOfWords<Word>(nbits);
939  SAWYER_VARIABLE_LENGTH_ARRAY(Word, tmp, nTmpWords);
940  for (size_t i=0; i<nTmpWords; ++i)
941  tmp[i] = (Word)((value >> (i * bitsPerWord<Word>::value)) & wordMask);
942 
943  // Copy the value's bit vector to the destination and zero-fill
944  copy(tmp, BitRange::baseSize(0, nbits), words, BitRange::baseSize(range.least(), nbits));
945  if (range.size() >= 64) {
946  BitRange hi = BitRange::baseSize(range.least() + 64, range.size() - 64);
947  clear(words, hi);
948  }
949 }
950 
955 template<class Word>
956 boost::uint64_t toInteger(const Word *words, const BitRange &range) {
957  boost::uint64_t result = 0;
958  ASSERT_require(8==sizeof result);
959 
960  // Copy the bits into the low bits of a temporary bit vector
961  size_t nbits = std::min(range.size(), (size_t)64);
962  size_t nTmpWords = numberOfWords<Word>(nbits);
963  SAWYER_VARIABLE_LENGTH_ARRAY(typename RemoveConst<Word>::Base, tmp, nTmpWords);
964  memset(tmp, 0, nTmpWords*sizeof(*tmp));
965  BitRange lo = BitRange::baseSize(range.least(), nbits);
966  copy(words, lo, tmp, BitRange::baseSize(0, nbits));
967 
968  // Convert the temporary bit vector to an integer
969  for (size_t i=0; i<nTmpWords; ++i)
970  result |= (boost::uint64_t)tmp[i] << (i * bitsPerWord<Word>::value);
971  return result;
972 }
973 
977 template<class Word>
978 boost::uint64_t toInteger(const Word *words, size_t nbits) {
979  boost::uint64_t result = 0;
980  ASSERT_require(nbits <= 64);
981  size_t nTmpWords = numberOfWords<Word>(nbits);
982  for (size_t i=0; i<nTmpWords; ++i)
983  result |= (boost::uint64_t)words[i] << (i * bitsPerWord<Word>::value);
984  if (nbits < 64)
985  result &= ~((~(boost::uint64_t)0) << nbits);
986  return result;
987 }
988 
989 template<class Word>
990 struct Increment {
991  bool carry;
992  Increment(): carry(true) {}
993  bool operator()(Word &word, size_t nbits) {
994  ASSERT_require(carry);
995  Word mask = bitMask<Word>(0, nbits);
996  Word arg1 = word & mask;
997  Word sum = arg1 + 1;
998  word &= ~mask;
999  word |= sum & mask;
1000  carry = (sum & mask) < arg1;
1001  return !carry; // terminate traversal when carry is false
1002  }
1003 };
1004 
1008 template<class Word>
1009 bool increment(Word *vec1, const BitRange &range1) {
1010  Increment<Word> visitor;
1011  traverse(visitor, vec1, range1, LowToHigh());
1012  return visitor.carry;
1013 }
1014 
1015 template<class Word>
1016 struct Decrement {
1017  bool borrowed;
1018  Decrement(): borrowed(true) {}
1019  bool operator()(Word &word, size_t nbits) {
1020  ASSERT_require(borrowed);
1021  Word mask = bitMask<Word>(0, nbits);
1022  Word arg1 = word & mask;
1023  borrowed = 0==arg1;
1024  Word difference = (arg1 - 1) & mask;
1025  word &= ~mask;
1026  word |= difference;
1027  return !borrowed; // terminate traversal unless we borrowed
1028  }
1029 };
1030 
1035 template<class Word>
1036 bool decrement(Word *vec1, const BitRange &range1) {
1037  Decrement<Word> visitor;
1038  traverse(visitor, vec1, range1, LowToHigh());
1039  return visitor.borrowed;
1040 }
1041 
1045 template<class Word>
1046 void negate(Word *vec1, const BitRange &range) {
1047  invert(vec1, range);
1048  increment(vec1, range);
1049 }
1050 
1051 template<class Word>
1052 struct AddBits {
1053  bool carry;
1054  AddBits(bool carry): carry(carry) {}
1055  bool operator()(const Word &w1, Word &w2, size_t nbits) {
1056  Word mask = bitMask<Word>(0, nbits);
1057  Word addend1(carry ? 1 : 0);
1058  Word addend2(w1 & mask);
1059  Word addend3(w2 & mask);
1060  Word sum = addend1 + addend2 + addend3;
1061  w2 &= ~mask;
1062  w2 |= sum & mask;
1063  if (nbits == bitsPerWord<Word>::value) {
1064  carry = sum < addend2 || (sum==addend2 && carry);
1065  } else {
1066  carry = 0 != (sum & bitMask<Word>(nbits, 1));
1067  }
1068  return false;
1069  }
1070 };
1071 
1076 template<class Word>
1077 bool add(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2, bool carryIn=false) {
1078  AddBits<Word> visitor(carryIn);
1079  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
1080  return visitor.carry;
1081 }
1082 
1089 template<class Word>
1090 bool subtract(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
1091  size_t nTempWords = numberOfWords<Word>(range1.size());
1092  SAWYER_VARIABLE_LENGTH_ARRAY(Word, temp, nTempWords);
1093  BitRange tempRange = BitRange::baseSize(0, range1.size());
1094  copy(vec1, range1, temp, tempRange);
1095  invert(temp, tempRange);
1096  return add(temp, tempRange, vec2, range2, true);
1097 }
1098 
1105 template<class Word>
1106 bool signExtend(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
1107  if (range2.isEmpty()) {
1108  return false;
1109  } else if (range1.isEmpty()) {
1110  clear(vec2, range2);
1111  return false;
1112  } else if (range1.size() < range2.size()) { // sign extension
1113  bool oldSign = get(vec1, range1.greatest());
1114  copy(vec1, range1, vec2, BitRange::baseSize(range2.least(), range1.size()));
1115  setValue(vec2, BitRange::hull(range2.least()+range1.size(), range2.greatest()), oldSign);
1116  return oldSign;
1117  } else { // truncation or plain copy
1118  ASSERT_require(range1.size() >= range2.size());
1119  BitRange copyFrom = BitRange::baseSize(range1.least(), range2.size());
1120  copy(vec1, copyFrom, vec2, range2);
1121  return get(vec2, range2.greatest());
1122  }
1123 }
1124 
1125 
1127 // Numeric comparison
1129 
1133 template<class Word>
1134 bool isEqualToZero(const Word *vec1, const BitRange &range1) {
1135  return isAllClear(vec1, range1);
1136 }
1137 
1138 template<class Word>
1139 struct CompareBits {
1140  int result;
1141  CompareBits(): result(0) {}
1142  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
1143  Word mask = bitMask<Word>(0, nbits);
1144  Word tmp1 = w1 & mask;
1145  Word tmp2 = w2 & mask;
1146  if (tmp1 < tmp2) {
1147  result = -1;
1148  return true;
1149  } else if (tmp1 > tmp2) {
1150  result = 1;
1151  return true;
1152  } else {
1153  return false;
1154  }
1155  }
1156 };
1157 
1164 template<class Word>
1165 int compare(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
1166  if (range1.isEmpty() && range2.isEmpty()) {
1167  return 0;
1168  } else if (range1.isEmpty()) {
1169  return isEqualToZero(vec2, range2) ? 0 : -1;
1170  } else if (range2.isEmpty()) {
1171  return isEqualToZero(vec1, range1) ? 0 : 1;
1172  } else if (range1.size() < range2.size()) {
1173  BitRange hi = BitRange::hull(range2.least() + range1.size(), range2.greatest());
1174  if (!isEqualToZero(vec2, hi))
1175  return -1;
1176  BitRange lo = BitRange::baseSize(range2.least(), range1.size());
1177  return compare(vec1, range1, vec2, lo);
1178  } else if (range1.size() > range2.size()) {
1179  BitRange hi = BitRange::hull(range1.least() + range2.size(), range1.greatest());
1180  if (!isEqualToZero(vec1, hi))
1181  return 1;
1182  BitRange lo = BitRange::baseSize(range1.least(), range2.size());
1183  return compare(vec1, lo, vec2, range2);
1184  } else {
1185  ASSERT_require(!range1.isEmpty() && !range2.isEmpty());
1186  ASSERT_require(range1.size() == range2.size());
1187  CompareBits<Word> visitor;
1188  traverse(visitor, vec1, range1, vec2, range2, HighToLow());
1189  return visitor.result;
1190  }
1191 }
1192 
1199 template<class Word>
1200 int compareSigned(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
1201  if (range1.isEmpty() && range2.isEmpty()) {
1202  return 0;
1203  } else if (range1.isEmpty()) {
1204  if (Optional<size_t> mssb = mostSignificantSetBit(vec2, range2)) {
1205  return *mssb == range2.greatest() ? 1 : -1;
1206  } else {
1207  return 0;
1208  }
1209  } else if (range2.isEmpty()) {
1210  if (Optional<size_t> mssb = mostSignificantSetBit(vec1, range1)) {
1211  return *mssb == range1.greatest() ? -1 : 1;
1212  } else {
1213  return 0;
1214  }
1215  } else if (range1.size() < range2.size()) {
1216  BitRange hi = BitRange::hull(range2.least()+range1.size(), range2.greatest());
1217  bool neg1 = get(vec1, range1.greatest());
1218  bool neg2 = get(vec2, range2.greatest());
1219  if (!neg1 && !neg2) { // both are non-negative, so leverage unsigned comparison
1220  return compare(vec1, range1, vec2, range2);
1221  } else if (neg1 && neg2) { // both are negative
1222  if (nSet(vec2, hi)==hi.size() && get(vec2, hi.least()-1)) {
1223  return compareSigned(vec1, range1, vec2, BitRange::baseSize(range2.least(), range1.size()));
1224  } else {
1225  return 1; // vec2 is less than vec1
1226  }
1227  } else if (neg1) { // vec1 is negative but vec2 isn't
1228  return -1;
1229  } else { // vec2 is negative but vec1 isn't
1230  return 1;
1231  }
1232  } else if (range1.size() > range2.size()) { // call recursively to trigger previous case
1233  return -1 * compareSigned(vec2, range2, vec1, range1);
1234  } else {
1235  ASSERT_require(range1.size()==range2.size());
1236  bool neg1 = get(vec1, range1.greatest());
1237  bool neg2 = get(vec2, range2.greatest());
1238  if (!neg1 && !neg2) {
1239  return compare(vec1, range1, vec2, range2);
1240  } else if (neg1 && neg2) {
1241  if (Optional<size_t> diff = mostSignificantDifference(vec1, range1, vec2, range2)) {
1242  return get(vec1, range1.least() + *diff) ? 1 : -1;
1243  } else {
1244  return 0;
1245  }
1246  } else if (neg1) {
1247  return -1;
1248  } else {
1249  return 1;
1250  }
1251  }
1252 }
1253 
1255 // String representation
1257 
1258 // Can handle binary, base-4, octal, or hexadecimal
1259 template<class Word, size_t bitsPerDigit>
1260 struct ToString {
1261  Word remaining; // left over bits from a previous iteration
1262  size_t nremaining; // number valid low-order bits in "remaining" data member
1263  std::string reversed; // resulting string with the least significant digit first
1264 
1265  ToString(): remaining(0), nremaining(0) {
1266  ASSERT_require(bitsPerDigit >= 1 && bitsPerDigit <= 4);
1267  ASSERT_require(bitsPerDigit <= bitsPerWord<Word>::value);
1268  }
1269 
1270  bool operator()(const Word &word, size_t nbits) {
1271  static const char digits[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
1272  Word tmp = word & bitMask<Word>(0, nbits);
1273  ASSERT_require(nremaining < bitsPerDigit);
1274  while (nremaining+nbits >= bitsPerDigit) {
1275  size_t nrem = std::min(nremaining, bitsPerDigit); // number left-over bits to use
1276  size_t nnew = bitsPerDigit - nrem; // number of new bits to use
1277  Word digit = (remaining & bitMask<Word>(0, nrem)) | ((tmp & bitMask<Word>(0, nnew)) << nrem);
1278  reversed += digits[digit];
1279  nremaining = 0;
1280  nbits -= nnew;
1281  tmp >>= nnew;
1282  }
1283  nremaining = nbits;
1284  remaining = tmp;
1285  return false;
1286  }
1287 
1288  std::string result() {
1289  if (nremaining > 0) {
1290  ASSERT_require(nremaining <= 3); // digits '0' through '7'
1291  reversed += '0' + (remaining & bitMask<Word>(0, nremaining));
1292  nremaining = 0;
1293  }
1294  std::string s;
1295  std::swap(s, reversed);
1296  std::reverse(s.begin(), s.end());
1297  return s;
1298  }
1299 };
1300 
1307 template<class Word>
1308 std::string toHex(const Word *vec, const BitRange &range) {
1309  ToString<Word, 4> visitor;
1310  traverse(visitor, vec, range, LowToHigh());
1311  return visitor.result();
1312 }
1313 
1319 template<class Word>
1320 std::string toOctal(const Word *vec, const BitRange &range) {
1321  ToString<Word, 3> visitor;
1322  traverse(visitor, vec, range, LowToHigh());
1323  return visitor.result();
1324 }
1325 
1331 template<class Word>
1332 std::string toBinary(const Word *vec, const BitRange &range) {
1333  ToString<Word, 1> visitor;
1334  traverse(visitor, vec, range, LowToHigh());
1335  return visitor.result();
1336 }
1337 
1339 // Parsing
1341 
1342 template<class Word>
1343 Word charToDigit(char ch) {
1344  Word digit;
1345  if (ch >= '0' && ch <= '9') {
1346  digit = ch - '0';
1347  } else if (ch >= 'a' && ch <= 'f') {
1348  digit = ch - 'a' + 10;
1349  } else if (ch >= 'A' && ch <= 'F') {
1350  digit = ch - 'A' + 10;
1351  } else {
1352  digit = 16; // signals an invalid character
1353  }
1354  return digit;
1355 }
1356 
1357 template<class Word, size_t bitsPerDigit>
1358 void fromString(Word *vec, const BitRange &range, const std::string &input) {
1359  ASSERT_require(bitsPerDigit >= 1 && bitsPerDigit <= 4);
1360  ASSERT_require(bitsPerDigit <= bitsPerWord<Word>::value);
1361 
1362  // Check that all characters of the string are valid.
1363  for (size_t idx=0; idx<input.size(); ++idx) {
1364  if ('_'!=input[idx] && charToDigit<Word>(input[idx]) >= Word(1) << bitsPerDigit) {
1365  throw std::runtime_error(std::string("invalid character '") + input[idx] + "' at index " +
1366  boost::lexical_cast<std::string>(idx) + " in base-" +
1367  boost::lexical_cast<std::string>(1 << bitsPerDigit) + " input string");
1368  }
1369  }
1370 
1371  // Copy digits into the vector
1372  size_t offset = 0; // bit offset from range.least()
1373  for (size_t idx=input.size(); idx>0 && offset<range.size(); --idx) {
1374  if ('_'!=input[idx-1]) {
1375  Word digit = charToDigit<Word>(input[idx-1]);
1376  size_t nbits = std::min(bitsPerDigit, range.size()-offset);// number of bits of digit to copy into vector
1377  copy(&digit, BitRange::baseSize(0, std::min(bitsPerDigit, nbits)),
1378  vec, BitRange::baseSize(range.least()+offset, nbits));
1379  offset += bitsPerDigit;
1380  }
1381  }
1382 
1383  // Zero fill high order stuff that we didn't already initialize
1384  if (offset < range.size())
1385  clear(vec, BitRange::hull(range.least()+offset, range.greatest()));
1386 }
1387 
1398 template<class Word>
1399 void fromDecimal(Word *vec, const BitRange &range, const std::string &input) {
1400  boost::uint64_t v = 0;
1401  BOOST_FOREACH (char ch, input) {
1402  if (isdigit(ch)) {
1403  boost::uint64_t tmp = v * 10 + (ch - '0');
1404  if (tmp < v)
1405  throw std::runtime_error("overflow parsing decimal string");
1406  v = tmp;
1407  } else if (ch != '_') {
1408  throw std::runtime_error("invalid decimal digit \"" + std::string(1, ch) + "\"");
1409  }
1410  }
1411  fromInteger(vec, range, v);
1412 }
1413 
1421 template<class Word>
1422 void fromHex(Word *vec, const BitRange &range, const std::string &input) {
1423  fromString<Word, 4>(vec, range, input);
1424 }
1425 
1432 template<class Word>
1433 void fromOctal(Word *vec, const BitRange &range, const std::string &input) {
1434  fromString<Word, 3>(vec, range, input);
1435 }
1436 
1443 template<class Word>
1444 void fromBinary(Word *vec, const BitRange &range, const std::string &input) {
1445  fromString<Word, 1>(vec, range, input);
1446 }
1447 
1448 
1449 } // namespace
1450 } // namespace
1451 } // namespace
1452 #endif
void fromInteger(Word *words, const BitRange &range, boost::uint64_t value)
Assign an unsigned value to a bit range.
void traverse(Processor &processor, Word *words, const BitRange &range, LowToHigh)
Traverses a range of bits.
bool subtract(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Subtract bits.
Sum< T >::Ptr sum()
Factory for value agumenter.
Definition: CommandLine.h:1900
bool decrement(Word *vec1, const BitRange &range1)
Decrement.
bool isOverlapping(const Interval &other) const
True if two intervals overlap.
Definition: Interval.h:208
Value size() const
Size of interval.
Definition: Interval.h:257
size_t wordIndex(size_t idx)
Index to bit vector word.
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.
bool processWord(Processor &processor, const Word &word, size_t shift, size_t nbits)
Invoke the a processor for a vector traversal.
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:197
void fromDecimal(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a decimal representation.
bool isAllSet(const Word *words, const BitRange &range)
True if all bits are set.
bool areEqual(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Equality predicate.
void fromBinary(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a binary representation.
void invert(Word *words, const BitRange &range)
Invert bits.
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.
bool increment(Word *vec1, const BitRange &range1)
Increment.
void negate(Word *vec1, const BitRange &range)
Negate bits as an integer.
void shiftRight(Word *words, const BitRange &range, size_t nShift, bool newBits=0)
Shift bits right.
Name space for the entire library.
Definition: Access.h:11
void shiftLeft(Word *words, const BitRange &range, size_t nShift, bool newBits=0)
Shift bits left.
Optional< size_t > leastSignificantClearBit(const Word *words, const BitRange &range)
Index of least significant zero bit.
static Interval baseSize(size_t lo, size_t size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:161
T least() const
Returns lower limit.
Definition: Interval.h:185
size_t nClear(const Word *words, const BitRange &range)
Number of clear bits.
Word bitMask(size_t offset, size_t nbits)
Creates a mask.
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.
void rotateLeft(Word *words, const BitRange &range, size_t nShift)
Rotate bits to the left.
void swap(Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Swap some bits.
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 > leastSignificantSetBit(const Word *words, const BitRange &range)
Index of least significant set bit.
std::string toHex(const Word *vec, const BitRange &range)
Hexadecimal representation.
int compare(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Unsigned comparison.
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.
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 isAllClear(const Word *words, const BitRange &range)
True if all bits are clear.
size_t bitIndex(size_t idx)
Index to bit within word.
void fromHex(Word *vec, const BitRange &range, const std::string &input)
Obtain bits from a hexadecimal representation.
void fromString(source_position &, const std::string &input)
Parse a string (such as 12.10, 13, 0 etc )into source position data structure.
int compareSigned(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Signed comparison.
void clear(Word *words, const BitRange &where)
Clear some bits.
void set(Word *words, const BitRange &where)
Set some bits.
void bitwiseAnd(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Bit-wise AND.
size_t numberOfWords(size_t nbits)
Number of words to hold indicated number of bits.
std::string toBinary(const Word *vec, const BitRange &range)
Binary representation.
Represents no value.
Definition: Optional.h:32
T greatest() const
Returns upper limit.
Definition: Interval.h:191
size_t nSet(const Word *words, const BitRange &range)
Number of set bits.
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.
Optional< size_t > mostSignificantDifference(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Find most significant different bits.
void traverse2(Processor &processor, Word1 *vec1, const BitRange &range1, Word2 *vec2, const BitRange &range2, LowToHigh)
Traverse two ranges of bits from low to high.