ROSE  0.9.10.91
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  BitRange tmpRange = BitRange::baseSize(offsetInWord, range1.size());
277  nonoverlappingCopy(vec1, range1, tmp, tmpRange);
278 
279  // Do the traversal. The first iteration's words are offset by offsetInWord bits, the remainder start at bit zero. All the
280  // words except possibly the first and last are the full size.
281  const size_t vec2WordOffset = wordIndex<Word2>(range2.least());
282  size_t nRemaining = range2.size();
283  bool done = false;
284  for (size_t wordIdx=0; !done && nRemaining > 0; ++wordIdx) {
285  ASSERT_require(wordIdx < nWordsTmp);
286  size_t nbits = std::min(bitsPerWord<Word2>::value - offsetInWord, nRemaining);
287  ASSERT_require(nbits > 0);
288  done = processWord(processor, *const_cast<Word1*>(tmp+wordIdx), vec2[wordIdx+vec2WordOffset], offsetInWord, nbits);
289  offsetInWord = 0; // only the first word has an internal bit offset
290  nRemaining -= nbits;
291  }
292 
293  // Copy tmp back into vec1, but only if vec1 is non-const
294  conditionalCopy(tmp, tmpRange, vec1, range1);
295 }
296 
298 template<class Processor, class Word1, class Word2>
299 void traverse2(Processor &processor, Word1 *vec1, const BitRange &range1, Word2 *vec2, const BitRange &range2, HighToLow) {
300  ASSERT_require(sizeof(Word1)==sizeof(Word2)); // may differ in constness
301  ASSERT_require((range1.isEmpty() && range2.isEmpty()) || (!range1.isEmpty() && !range2.isEmpty()));
302  if (range1.isEmpty())
303  return;
304  ASSERT_require(range1.size() == range2.size());
305 
306  // Make a copy of the source and give it the same bit alignment as the destination. This not only makes traversal easier
307  // (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
308  // the source and destination overlap.
309  const size_t offsetInWord = bitIndex<Word2>(range2.least());
310  const size_t nWordsTmp = numberOfWords<Word2>(offsetInWord + range2.size());
311  SAWYER_VARIABLE_LENGTH_ARRAY(typename RemoveConst<Word1>::Base, tmp, nWordsTmp);
312  BitRange tmpRange = BitRange::baseSize(offsetInWord, range1.size());
313  nonoverlappingCopy(vec1, range1, tmp, tmpRange);
314 
315  // Traversal high-to-low.
316  size_t nRemaining = range2.size();
317  bool done = false;
318  const size_t vec2WordOffset = wordIndex<Word2>(range2.least());
319  for (size_t wordIdx=nWordsTmp-1; !done && nRemaining>0; --wordIdx) {
320  size_t nbits;
321  if (wordIdx == 0) {
322  ASSERT_require(nRemaining <= bitsPerWord<Word2>::value);
323  nbits = nRemaining;
324  } else if (wordIdx < nWordsTmp-1) {
325  ASSERT_require(nRemaining > bitsPerWord<Word2>::value);
327  } else {
328  ASSERT_require(wordIdx==nWordsTmp-1);
329  ASSERT_require(wordIdx>0);
330  size_t nBitsToLeft = (bitsPerWord<Word2>::value - offsetInWord) + (nWordsTmp-2) * bitsPerWord<Word2>::value;
331  ASSERT_require(nRemaining > nBitsToLeft);
332  nbits = nRemaining - nBitsToLeft;
333  ASSERT_require(nbits <= bitsPerWord<Word2>::value);
334  }
335  done = processWord(processor, *const_cast<Word1*>(tmp+wordIdx), vec2[wordIdx+vec2WordOffset],
336  wordIdx==0 ? offsetInWord : 0, nbits);
337  nRemaining -= nbits;
338  }
339 
340  // Copy tmp back into vec1, but only if vec1 is non-const
341  conditionalCopy(tmp, tmpRange, vec1, range1);
342 }
343 
344 template<class Processor, class Word>
345 void traverse(Processor &processor,
346  const Word *vec1, const BitRange &range1,
347  const Word *vec2, const BitRange &range2,
348  HighToLow dir) {
349  traverse2(processor, vec1, range1, vec2, range2, dir);
350 }
351 
352 template<class Processor, class Word>
353 void traverse(Processor &processor,
354  const Word *vec1, const BitRange &range1,
355  const Word *vec2, const BitRange &range2,
356  LowToHigh dir) {
357  traverse2(processor, vec1, range1, vec2, range2, dir);
358 }
359 template<class Processor, class Word>
360 void traverse(Processor &processor,
361  const Word *vec1, const BitRange &range1,
362  Word *vec2, const BitRange &range2,
363  LowToHigh dir) {
364  traverse2(processor, vec1, range1, vec2, range2, dir);
365 }
366 template<class Processor, class Word>
367 void traverse(Processor &processor,
368  Word *vec1, const BitRange &range1,
369  Word *vec2, const BitRange &range2,
370  LowToHigh dir) {
371  traverse2(processor, vec1, range1, vec2, range2, dir);
372 }
373 
374 
375 
377 // Bit accessors
379 
383 template<class Word>
384 bool get(const Word *words, size_t idx) {
385  return 0 != (words[wordIndex<Word>(idx)] & bitMask<Word>(bitIndex<Word>(idx), 1));
386 }
387 
388 template<class Word>
389 struct ClearBits {
390  bool operator()(Word &word, size_t nbits) {
391  word &= ~bitMask<Word>(0, nbits);
392  return false;
393  }
394 };
395 
399 template<class Word>
400 void clear(Word *words, const BitRange &where) {
401  ClearBits<Word> visitor;
402  traverse(visitor, words, where, LowToHigh());
403 }
404 
405 template<class Word>
406 struct SetBits {
407  bool operator()(Word &word, size_t nbits) {
408  word |= bitMask<Word>(0, nbits);
409  return false;
410  }
411 };
412 
416 template<class Word>
417 void set(Word *words, const BitRange &where) {
418  SetBits<Word> visitor;
419  traverse(visitor, words, where, LowToHigh());
420 }
421 
425 template<class Word>
426 void setValue(Word *words, const BitRange &where, bool value) {
427  if (value) {
428  set(words, where);
429  } else {
430  clear(words, where);
431  }
432 }
433 
434 template<class Word>
435 struct CopyBits {
436  bool operator()(const Word &src, Word &dst, size_t nbits) {
437  dst &= ~bitMask<Word>(0, nbits);
438  dst |= src & bitMask<Word>(0, nbits);
439  return false;
440  }
441 };
442 
447 template<class Word>
448 void copy(const Word *src, const BitRange &srcRange, Word *dst, const BitRange &dstRange) {
449  CopyBits<Word> visitor;
450  traverse(visitor, src, srcRange, dst, dstRange, LowToHigh());
451 }
452 
453 template<class Word>
454 struct SwapBits {
455  bool operator()(Word &w1, Word &w2, size_t nbits) {
456  Word tmp = w1, mask = bitMask<Word>(0, nbits);
457  w1 &= ~mask;
458  w1 |= w2 & mask;
459  w2 &= ~mask;
460  w2 |= tmp & mask;
461  return false;
462  }
463 };
464 
469 template<class Word>
470 void swap(Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
471  SwapBits<Word> visitor;
472  ASSERT_require(vec1!=vec2 || !range1.isOverlapping(range2));
473  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
474 }
475 
476 
478 // Counting/searching
480 
481 
482 template<class Word>
484  size_t offset;
485  Optional<size_t> result;
486  LeastSignificantSetBit(): offset(0) {}
487  bool operator()(const Word &word, size_t nbits) {
488  if (0 != (word & bitMask<Word>(0, nbits))) {
489  for (size_t i=0; i<nbits; ++i) {
490  if (0 != (word & bitMask<Word>(i, 1))) {
491  result = offset + i;
492  return true;
493  }
494  }
495  }
496  offset += nbits;
497  return false;
498  }
499 };
500 
505 template<class Word>
506 Optional<size_t> leastSignificantSetBit(const Word *words, const BitRange &range) {
508  traverse(visitor, words, range, LowToHigh());
509  if (visitor.result)
510  return range.least() + *visitor.result;
511  return Nothing();
512 }
513 
514 template<class Word>
516  size_t offset;
517  Optional<size_t> result;
518  LeastSignificantClearBit(): offset(0) {}
519  bool operator()(const Word &word, size_t nbits) {
520  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
521  for (size_t i=0; i<nbits; ++i) {
522  if (0 == (word & bitMask<Word>(i, 1))) {
523  result = offset + i;
524  return true;
525  }
526  }
527  }
528  offset += nbits;
529  return false;
530  }
531 };
532 
537 template<class Word>
538 Optional<size_t> leastSignificantClearBit(const Word *words, const BitRange &range) {
540  traverse(visitor, words, range, LowToHigh());
541  if (visitor.result)
542  return range.least() + *visitor.result;
543  return Nothing();
544 }
545 
546 template<class Word>
548  size_t offset;
549  Optional<size_t> result;
550  MostSignificantSetBit(size_t nbits): offset(nbits) {}
551  bool operator()(const Word &word, size_t nbits) {
552  ASSERT_require(nbits <= offset);
553  offset -= nbits;
554  if (0 != (word & bitMask<Word>(0, nbits))) {
555  for (size_t i=nbits; i>0; --i) {
556  if (0 != (word & bitMask<Word>(i-1, 1))) {
557  result = offset + i-1;
558  return true;
559  }
560  }
561  }
562  return false;
563  }
564 };
565 
570 template<class Word>
571 Optional<size_t> mostSignificantSetBit(const Word *words, const BitRange &range) {
572  MostSignificantSetBit<Word> visitor(range.size());
573  traverse(visitor, words, range, HighToLow());
574  if (visitor.result)
575  return range.least() + *visitor.result;
576  return Nothing();
577 }
578 
579 template<class Word>
581  size_t offset;
582  Optional<size_t> result;
583  MostSignificantClearBit(size_t nbits): offset(nbits) {}
584  bool operator()(const Word &word, size_t nbits) {
585  ASSERT_require(nbits <= offset);
586  offset -= nbits;
587  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
588  for (size_t i=nbits; i>0; --i) {
589  if (0 == (word & bitMask<Word>(i-1, 1))) {
590  result = offset + i-1;
591  return true;
592  }
593  }
594  }
595  return false;
596  }
597 };
598 
603 template<class Word>
604 Optional<size_t> mostSignificantClearBit(const Word *words, const BitRange &range) {
605  MostSignificantClearBit<Word> visitor(range.size());
606  traverse(visitor, words, range, HighToLow());
607  if (visitor.result)
608  return range.least() + *visitor.result;
609  return Nothing();
610 }
611 
615 template<class Word>
616 bool isAllSet(const Word *words, const BitRange &range) {
617  return leastSignificantClearBit(words, range) ? false : true;
618 }
619 
623 template<class Word>
624 bool isAllClear(const Word *words, const BitRange &range) {
625  return leastSignificantSetBit(words, range) ? false : true;
626 }
627 
628 template<class Word>
629 struct CountSetBits {
630  size_t result;
631  CountSetBits(): result(0) {}
632  bool operator()(const Word &word, size_t nbits) {
633  if (0 != (word & bitMask<Word>(0, nbits))) {
634  for (size_t i=0; i<nbits; ++i) {
635  if (0 != (word & bitMask<Word>(i, 1)))
636  ++result;
637  }
638  }
639  return false;
640  }
641 };
642 
646 template<class Word>
647 size_t nSet(const Word *words, const BitRange &range) {
648  CountSetBits<Word> visitor;
649  traverse(visitor, words, range, LowToHigh());
650  return visitor.result;
651 }
652 
653 template<class Word>
655  size_t result;
656  CountClearBits(): result(0) {}
657  bool operator()(const Word &word, size_t nbits) {
658  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
659  for (size_t i=0; i<nbits; ++i) {
660  if (0 == (word & bitMask<Word>(i, 1)))
661  ++result;
662  }
663  }
664  return false;
665  }
666 };
667 
671 template<class Word>
672 size_t nClear(const Word *words, const BitRange &range) {
673  CountClearBits<Word> visitor;
674  traverse(visitor, words, range, LowToHigh());
675  return visitor.result;
676 }
677 
678 template<class Word>
680  size_t offset;
681  Optional<size_t> result;
682  LeastSignificantDifference(): offset(0) {}
683  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
684  Word mask = bitMask<Word>(0, nbits);
685  if ((w1 & mask) != (w2 & mask)) {
686  for (size_t i=0; i<nbits; ++i) {
687  if ((w1 ^ w2) & bitMask<Word>(i, 1)) {
688  result = offset + i;
689  return true;
690  }
691  }
692  }
693  offset += nbits;
694  return false;
695  }
696 };
697 
703 template<class Word>
704 Optional<size_t> leastSignificantDifference(const Word *vec1, const BitRange &range1,
705  const Word *vec2, const BitRange &range2) {
707  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
708  return visitor.result;
709 }
710 
711 template<class Word>
713  size_t offset;
714  Optional<size_t> result;
715  MostSignificantDifference(size_t nbits): offset(nbits) {}
716  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
717  ASSERT_require(nbits <= offset);
718  offset -= nbits;
719  Word mask = bitMask<Word>(0, nbits);
720  if ((w1 & mask) != (w2 & mask)) {
721  for (size_t i=nbits; i>0; --i) {
722  if ((w1 ^ w2) & bitMask<Word>(i-1, 1)) {
723  result = offset + i-1;
724  return true;
725  }
726  }
727  }
728  return false;
729  }
730 };
731 
737 template<class Word>
738 Optional<size_t> mostSignificantDifference(const Word *vec1, const BitRange &range1,
739  const Word *vec2, const BitRange &range2) {
740  MostSignificantDifference<Word> visitor(range1.size());
741  traverse(visitor, vec1, range1, vec2, range2, HighToLow());
742  return visitor.result;
743 }
744 
749 template<class Word>
750 bool areEqual(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
751  if (range1.size()!=range2.size())
752  return false;
753  return leastSignificantDifference(vec1, range1, vec2, range2) ? false : true;
754 }
755 
757 // Shift/rotate
759 
764 template<class Word>
765 void shiftLeft(Word *words, const BitRange &range, size_t nShift, bool newBits=0) {
766  if (nShift < range.size()) {
767  size_t nbits = range.size() - nShift; // number of bits to move
768  BitRange shiftedFrom = BitRange::baseSize(range.least(), nbits);
769  BitRange shiftedTo = BitRange::baseSize(range.least() + nShift, nbits);
770  BitRange introduced = BitRange::baseSize(range.least(), nShift);
771  copy(words, shiftedFrom, words, shiftedTo);
772  setValue(words, introduced, newBits);
773  } else {
774  setValue(words, range, newBits);
775  }
776 }
777 
782 template<class Word>
783 void shiftRight(Word *words, const BitRange &range, size_t nShift, bool newBits=0) {
784  if (nShift < range.size()) {
785  size_t nbits = range.size() - nShift; // number of bits to move
786  BitRange shiftedFrom = BitRange::baseSize(range.least() + nShift, nbits);
787  BitRange shiftedTo = BitRange::baseSize(range.least(), nbits);
788  BitRange introduced = BitRange::baseSize(range.least() + nbits, nShift);
789  copy(words, shiftedFrom, words, shiftedTo);
790  setValue(words, introduced, newBits);
791  } else {
792  setValue(words, range, newBits);
793  }
794 }
795 
800 template<class Word>
801 void shiftRightArithmetic(Word *words, const BitRange &range, size_t nShift) {
802  if (!range.isEmpty()) {
803  bool newBits = get(words, range.greatest());
804  shiftRight(words, range, nShift, newBits);
805  }
806 }
807 
812 template<class Word>
813 void rotateRight(Word *words, const BitRange &range, size_t nShift) {
814  if (range.isEmpty())
815  return;
816  nShift %= range.size();
817  if (0==nShift)
818  return;
819 
820  // Save the low-order bits that will be shifted off
821  size_t nSavedWords = numberOfWords<Word>(nShift);
822  SAWYER_VARIABLE_LENGTH_ARRAY(Word, saved, nSavedWords);
823  BitRange savedRange = BitRange::baseSize(0, nShift);
824  copy(words, BitRange::baseSize(range.least(), nShift), saved, savedRange);
825 
826  shiftRight(words, range, nShift);
827 
828  BitRange introduced = BitRange::baseSize(range.least()+range.size()-nShift, nShift);
829  copy(saved, savedRange, words, introduced);
830 }
831 
836 template<class Word>
837 void rotateLeft(Word *words, const BitRange &range, size_t nShift) {
838  if (range.isEmpty())
839  return;
840  nShift %= range.size();
841  rotateRight(words, range, range.size()-nShift);
842 }
843 
844 
846 // Bit-wise Boolean logic
848 
849 template<class Word>
850 struct InvertBits {
851  bool operator()(Word &word, size_t nbits) {
852  word ^= bitMask<Word>(0, nbits);
853  return false;
854  }
855 };
856 
860 template<class Word>
861 void invert(Word *words, const BitRange &range) {
862  InvertBits<Word> visitor;
863  traverse(visitor, words, range, LowToHigh());
864 }
865 
866 template<class Word>
867 struct AndBits {
868  bool operator()(const Word &w1, Word &w2, size_t nbits) {
869  w2 &= w1 | ~bitMask<Word>(0, nbits);
870  return false;
871  }
872 };
873 
878 template<class Word>
879 void bitwiseAnd(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
880  AndBits<Word> visitor;
881  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
882 }
883 
884 template<class Word>
885 struct OrBits {
886  bool operator()(const Word &w1, Word &w2, size_t nbits) {
887  w2 |= w1 & bitMask<Word>(0, nbits);
888  return false;
889  }
890 };
891 
896 template<class Word>
897 void bitwiseOr(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
898  OrBits<Word> visitor;
899  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
900 }
901 
902 template<class Word>
903 struct XorBits {
904  bool operator()(const Word &w1, Word &w2, size_t nbits) {
905  w2 ^= w1 & bitMask<Word>(0, nbits);
906  return false;
907  }
908 };
909 
914 template<class Word>
915 void bitwiseXor(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
916  XorBits<Word> visitor;
917  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
918 }
919 
920 
922 // Arithmetic
924 
928 template<class Word>
929 void fromInteger(Word *words, const BitRange &range, boost::uint64_t value) {
930  ASSERT_require(8==sizeof value);
931  if (range.isEmpty())
932  return;
933 
934  // Create a bit vector that is just the value
935  size_t nbits = std::min(range.size(), (size_t)64); // number of significant bits to copy, not fill
936  Word wordMask = bitMask<Word>(0, bitsPerWord<Word>::value);
937  size_t nTmpWords = numberOfWords<Word>(nbits);
938  SAWYER_VARIABLE_LENGTH_ARRAY(Word, tmp, nTmpWords);
939  for (size_t i=0; i<nTmpWords; ++i)
940  tmp[i] = (Word)((value >> (i * bitsPerWord<Word>::value)) & wordMask);
941 
942  // Copy the value's bit vector to the destination and zero-fill
943  copy(tmp, BitRange::baseSize(0, nbits), words, BitRange::baseSize(range.least(), nbits));
944  if (range.size() >= 64) {
945  BitRange hi = BitRange::baseSize(range.least() + 64, range.size() - 64);
946  clear(words, hi);
947  }
948 }
949 
954 template<class Word>
955 boost::uint64_t toInteger(const Word *words, const BitRange &range) {
956  boost::uint64_t result = 0;
957  ASSERT_require(8==sizeof result);
958 
959  // Copy the bits into the low bits of a temporary bit vector
960  size_t nbits = std::min(range.size(), (size_t)64);
961  size_t nTmpWords = numberOfWords<Word>(nbits);
962  SAWYER_VARIABLE_LENGTH_ARRAY(typename RemoveConst<Word>::Base, tmp, nTmpWords);
963  BitRange lo = BitRange::baseSize(range.least(), nbits);
964  copy(words, lo, tmp, BitRange::baseSize(0, nbits));
965 
966  // Convert the temporary bit vector to an integer
967  for (size_t i=0; i<nTmpWords; ++i)
968  result |= (boost::uint64_t)tmp[i] << (i * bitsPerWord<Word>::value);
969  return result;
970 }
971 
975 template<class Word>
976 boost::uint64_t toInteger(const Word *words, size_t nbits) {
977  boost::uint64_t result = 0;
978  ASSERT_require(nbits <= 64);
979  size_t nTmpWords = numberOfWords<Word>(nbits);
980  for (size_t i=0; i<nTmpWords; ++i)
981  result |= (boost::uint64_t)words[i] << (i * bitsPerWord<Word>::value);
982  if (nbits < 64)
983  result &= ~((~(boost::uint64_t)0) << nbits);
984  return result;
985 }
986 
987 template<class Word>
988 struct Increment {
989  bool carry;
990  Increment(): carry(true) {}
991  bool operator()(Word &word, size_t nbits) {
992  ASSERT_require(carry);
993  Word mask = bitMask<Word>(0, nbits);
994  Word arg1 = word & mask;
995  Word sum = arg1 + 1;
996  word &= ~mask;
997  word |= sum & mask;
998  carry = (sum & mask) < arg1;
999  return !carry; // terminate traversal when carry is false
1000  }
1001 };
1002 
1006 template<class Word>
1007 bool increment(Word *vec1, const BitRange &range1) {
1008  Increment<Word> visitor;
1009  traverse(visitor, vec1, range1, LowToHigh());
1010  return visitor.carry;
1011 }
1012 
1013 template<class Word>
1014 struct Decrement {
1015  bool borrowed;
1016  Decrement(): borrowed(true) {}
1017  bool operator()(Word &word, size_t nbits) {
1018  ASSERT_require(borrowed);
1019  Word mask = bitMask<Word>(0, nbits);
1020  Word arg1 = word & mask;
1021  borrowed = 0==arg1;
1022  Word difference = (arg1 - 1) & mask;
1023  word &= ~mask;
1024  word |= difference;
1025  return !borrowed; // terminate traversal unless we borrowed
1026  }
1027 };
1028 
1033 template<class Word>
1034 bool decrement(Word *vec1, const BitRange &range1) {
1035  Decrement<Word> visitor;
1036  traverse(visitor, vec1, range1, LowToHigh());
1037  return visitor.borrowed;
1038 }
1039 
1043 template<class Word>
1044 void negate(Word *vec1, const BitRange &range) {
1045  invert(vec1, range);
1046  increment(vec1, range);
1047 }
1048 
1049 template<class Word>
1050 struct AddBits {
1051  bool carry;
1052  AddBits(bool carry): carry(carry) {}
1053  bool operator()(const Word &w1, Word &w2, size_t nbits) {
1054  Word mask = bitMask<Word>(0, nbits);
1055  Word addend1(carry ? 1 : 0);
1056  Word addend2(w1 & mask);
1057  Word addend3(w2 & mask);
1058  Word sum = addend1 + addend2 + addend3;
1059  w2 &= ~mask;
1060  w2 |= sum & mask;
1061  if (nbits == bitsPerWord<Word>::value) {
1062  carry = sum < addend2 || (sum==addend2 && carry);
1063  } else {
1064  carry = 0 != (sum & bitMask<Word>(nbits, 1));
1065  }
1066  return false;
1067  }
1068 };
1069 
1074 template<class Word>
1075 bool add(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2, bool carryIn=false) {
1076  AddBits<Word> visitor(carryIn);
1077  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
1078  return visitor.carry;
1079 }
1080 
1087 template<class Word>
1088 bool subtract(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
1089  size_t nTempWords = numberOfWords<Word>(range1.size());
1090  SAWYER_VARIABLE_LENGTH_ARRAY(Word, temp, nTempWords);
1091  BitRange tempRange = BitRange::baseSize(0, range1.size());
1092  copy(vec1, range1, temp, tempRange);
1093  invert(temp, tempRange);
1094  return add(temp, tempRange, vec2, range2, true);
1095 }
1096 
1103 template<class Word>
1104 bool signExtend(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
1105  if (range2.isEmpty()) {
1106  return false;
1107  } else if (range1.isEmpty()) {
1108  clear(vec2, range2);
1109  return false;
1110  } else if (range1.size() < range2.size()) { // sign extension
1111  bool oldSign = get(vec1, range1.greatest());
1112  copy(vec1, range1, vec2, BitRange::baseSize(range2.least(), range1.size()));
1113  setValue(vec2, BitRange::hull(range2.least()+range1.size(), range2.greatest()), oldSign);
1114  return oldSign;
1115  } else { // truncation or plain copy
1116  ASSERT_require(range1.size() >= range2.size());
1117  BitRange copyFrom = BitRange::baseSize(range1.least(), range2.size());
1118  copy(vec1, copyFrom, vec2, range2);
1119  return get(vec2, range2.greatest());
1120  }
1121 }
1122 
1126 template<class Word>
1127 void multiply10(Word *vec, const BitRange &range) {
1128  // n * 10 == n * (8 + 2) == n*8 + n*2 == (n<<3) + (n<<1)
1129  const size_t nWords = numberOfWords<Word>(range.size());
1130  BitRange partRange = BitRange::baseSize(0, range.size());
1131  SAWYER_VARIABLE_LENGTH_ARRAY(Word, part, nWords);
1132  copy(vec, range, part, partRange);
1133  shiftLeft(vec, range, 3);
1134  shiftLeft(part, partRange, 1);
1135  add(part, partRange, vec, range);
1136 }
1137 
1139 // Numeric comparison
1141 
1145 template<class Word>
1146 bool isEqualToZero(const Word *vec1, const BitRange &range1) {
1147  return isAllClear(vec1, range1);
1148 }
1149 
1150 template<class Word>
1151 struct CompareBits {
1152  int result;
1153  CompareBits(): result(0) {}
1154  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
1155  Word mask = bitMask<Word>(0, nbits);
1156  Word tmp1 = w1 & mask;
1157  Word tmp2 = w2 & mask;
1158  if (tmp1 < tmp2) {
1159  result = -1;
1160  return true;
1161  } else if (tmp1 > tmp2) {
1162  result = 1;
1163  return true;
1164  } else {
1165  return false;
1166  }
1167  }
1168 };
1169 
1176 template<class Word>
1177 int compare(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
1178  if (range1.isEmpty() && range2.isEmpty()) {
1179  return 0;
1180  } else if (range1.isEmpty()) {
1181  return isEqualToZero(vec2, range2) ? 0 : -1;
1182  } else if (range2.isEmpty()) {
1183  return isEqualToZero(vec1, range1) ? 0 : 1;
1184  } else if (range1.size() < range2.size()) {
1185  BitRange hi = BitRange::hull(range2.least() + range1.size(), range2.greatest());
1186  if (!isEqualToZero(vec2, hi))
1187  return -1;
1188  BitRange lo = BitRange::baseSize(range2.least(), range1.size());
1189  return compare(vec1, range1, vec2, lo);
1190  } else if (range1.size() > range2.size()) {
1191  BitRange hi = BitRange::hull(range1.least() + range2.size(), range1.greatest());
1192  if (!isEqualToZero(vec1, hi))
1193  return 1;
1194  BitRange lo = BitRange::baseSize(range1.least(), range2.size());
1195  return compare(vec1, lo, vec2, range2);
1196  } else {
1197  ASSERT_require(!range1.isEmpty() && !range2.isEmpty());
1198  ASSERT_require(range1.size() == range2.size());
1199  CompareBits<Word> visitor;
1200  traverse(visitor, vec1, range1, vec2, range2, HighToLow());
1201  return visitor.result;
1202  }
1203 }
1204 
1211 template<class Word>
1212 int compareSigned(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
1213  if (range1.isEmpty() && range2.isEmpty()) {
1214  return 0;
1215  } else if (range1.isEmpty()) {
1216  if (Optional<size_t> mssb = mostSignificantSetBit(vec2, range2)) {
1217  return *mssb == range2.greatest() ? 1 : -1;
1218  } else {
1219  return 0;
1220  }
1221  } else if (range2.isEmpty()) {
1222  if (Optional<size_t> mssb = mostSignificantSetBit(vec1, range1)) {
1223  return *mssb == range1.greatest() ? -1 : 1;
1224  } else {
1225  return 0;
1226  }
1227  } else if (range1.size() < range2.size()) {
1228  BitRange hi = BitRange::hull(range2.least()+range1.size(), range2.greatest());
1229  bool neg1 = get(vec1, range1.greatest());
1230  bool neg2 = get(vec2, range2.greatest());
1231  if (!neg1 && !neg2) { // both are non-negative, so leverage unsigned comparison
1232  return compare(vec1, range1, vec2, range2);
1233  } else if (neg1 && neg2) { // both are negative
1234  if (nSet(vec2, hi)==hi.size() && get(vec2, hi.least()-1)) {
1235  return compareSigned(vec1, range1, vec2, BitRange::baseSize(range2.least(), range1.size()));
1236  } else {
1237  return 1; // vec2 is less than vec1
1238  }
1239  } else if (neg1) { // vec1 is negative but vec2 isn't
1240  return -1;
1241  } else { // vec2 is negative but vec1 isn't
1242  return 1;
1243  }
1244  } else if (range1.size() > range2.size()) { // call recursively to trigger previous case
1245  return -1 * compareSigned(vec2, range2, vec1, range1);
1246  } else {
1247  ASSERT_require(range1.size()==range2.size());
1248  bool neg1 = get(vec1, range1.greatest());
1249  bool neg2 = get(vec2, range2.greatest());
1250  if (!neg1 && !neg2) {
1251  return compare(vec1, range1, vec2, range2);
1252  } else if (neg1 && neg2) {
1253  if (Optional<size_t> diff = mostSignificantDifference(vec1, range1, vec2, range2)) {
1254  return get(vec1, range1.least() + *diff) ? 1 : -1;
1255  } else {
1256  return 0;
1257  }
1258  } else if (neg1) {
1259  return -1;
1260  } else {
1261  return 1;
1262  }
1263  }
1264 }
1265 
1267 // String representation
1269 
1270 // Can handle binary, base-4, octal, or hexadecimal
1271 template<class Word, size_t bitsPerDigit>
1272 struct ToString {
1273  Word remaining; // left over bits from a previous iteration
1274  size_t nremaining; // number valid low-order bits in "remaining" data member
1275  std::string reversed; // resulting string with the least significant digit first
1276 
1277  ToString(): remaining(0), nremaining(0) {
1278  ASSERT_require(bitsPerDigit >= 1 && bitsPerDigit <= 4);
1279  ASSERT_require(bitsPerDigit <= bitsPerWord<Word>::value);
1280  }
1281 
1282  bool operator()(const Word &word, size_t nbits) {
1283  static const char digits[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
1284  Word tmp = word & bitMask<Word>(0, nbits);
1285  ASSERT_require(nremaining < bitsPerDigit);
1286  while (nremaining+nbits >= bitsPerDigit) {
1287  size_t nrem = std::min(nremaining, bitsPerDigit); // number left-over bits to use
1288  size_t nnew = bitsPerDigit - nrem; // number of new bits to use
1289  Word digit = (remaining & bitMask<Word>(0, nrem)) | ((tmp & bitMask<Word>(0, nnew)) << nrem);
1290  reversed += digits[digit];
1291  nremaining = 0;
1292  nbits -= nnew;
1293  tmp >>= nnew;
1294  }
1295  nremaining = nbits;
1296  remaining = tmp;
1297  return false;
1298  }
1299 
1300  std::string result() {
1301  if (nremaining > 0) {
1302  ASSERT_require(nremaining <= 3); // digits '0' through '7'
1303  reversed += '0' + (remaining & bitMask<Word>(0, nremaining));
1304  nremaining = 0;
1305  }
1306  std::string s;
1307  std::swap(s, reversed);
1308  std::reverse(s.begin(), s.end());
1309  return s;
1310  }
1311 };
1312 
1319 template<class Word>
1320 std::string toHex(const Word *vec, const BitRange &range) {
1321  ToString<Word, 4> visitor;
1322  traverse(visitor, vec, range, LowToHigh());
1323  return visitor.result();
1324 }
1325 
1331 template<class Word>
1332 std::string toOctal(const Word *vec, const BitRange &range) {
1333  ToString<Word, 3> visitor;
1334  traverse(visitor, vec, range, LowToHigh());
1335  return visitor.result();
1336 }
1337 
1343 template<class Word>
1344 std::string toBinary(const Word *vec, const BitRange &range) {
1345  ToString<Word, 1> visitor;
1346  traverse(visitor, vec, range, LowToHigh());
1347  return visitor.result();
1348 }
1349 
1351 // Parsing
1353 
1354 template<class Word>
1355 Word charToDigit(char ch) {
1356  Word digit;
1357  if (ch >= '0' && ch <= '9') {
1358  digit = ch - '0';
1359  } else if (ch >= 'a' && ch <= 'f') {
1360  digit = ch - 'a' + 10;
1361  } else if (ch >= 'A' && ch <= 'F') {
1362  digit = ch - 'A' + 10;
1363  } else {
1364  digit = 16; // signals an invalid character
1365  }
1366  return digit;
1367 }
1368 
1369 template<class Word, size_t bitsPerDigit>
1370 void fromString(Word *vec, const BitRange &range, const std::string &input) {
1371  ASSERT_require(bitsPerDigit >= 1 && bitsPerDigit <= 4);
1372  ASSERT_require(bitsPerDigit <= bitsPerWord<Word>::value);
1373 
1374  // Check that all characters of the string are valid.
1375  for (size_t idx=0; idx<input.size(); ++idx) {
1376  if ('_'!=input[idx] && charToDigit<Word>(input[idx]) >= Word(1) << bitsPerDigit) {
1377  throw std::runtime_error(std::string("invalid character '") + input[idx] + "' at index " +
1378  boost::lexical_cast<std::string>(idx) + " in base-" +
1379  boost::lexical_cast<std::string>(1 << bitsPerDigit) + " input string");
1380  }
1381  }
1382 
1383  // Copy digits into the vector
1384  size_t offset = 0; // bit offset from range.least()
1385  for (size_t idx=input.size(); idx>0 && offset<range.size(); --idx) {
1386  if ('_'!=input[idx-1]) {
1387  Word digit = charToDigit<Word>(input[idx-1]);
1388  size_t nbits = std::min(bitsPerDigit, range.size()-offset);// number of bits of digit to copy into vector
1389  copy(&digit, BitRange::baseSize(0, std::min(bitsPerDigit, nbits)),
1390  vec, BitRange::baseSize(range.least()+offset, nbits));
1391  offset += bitsPerDigit;
1392  }
1393  }
1394 
1395  // Zero fill high order stuff that we didn't already initialize
1396  if (offset < range.size())
1397  clear(vec, BitRange::hull(range.least()+offset, range.greatest()));
1398 }
1399 
1407 template<class Word>
1408 void fromDecimal(Word *vec, const BitRange &range, const std::string &input) {
1409  // First try parsing a value that fits in 64 bits.
1410  boost::uint64_t v = 0;
1411  bool hadOverflow = false;
1412  BOOST_FOREACH (char ch, input) {
1413  if (isdigit(ch)) {
1414  boost::uint64_t tmp = v * 10 + (ch - '0');
1415  if (tmp < v) {
1416  hadOverflow = true;
1417  break;
1418  }
1419  v = tmp;
1420  } else if (ch != '_') {
1421  throw std::runtime_error("invalid decimal digit \"" + std::string(1, ch) + "\"");
1422  }
1423  }
1424  if (!hadOverflow) {
1425  fromInteger(vec, range, v);
1426  return;
1427  }
1428 
1429  // If 64 bits isn't wide enough, do it the slow way.
1430  const size_t nWords = numberOfWords<Word>(range.size());
1431  SAWYER_VARIABLE_LENGTH_ARRAY(Word, accumulator, nWords);
1432  SAWYER_VARIABLE_LENGTH_ARRAY(Word, digit, nWords);
1433  BitRange accumulatorRange = BitRange::baseSize(0, range.size());
1434  BOOST_FOREACH (char ch, input) {
1435  multiply10(accumulator, accumulatorRange);
1436  fromInteger(digit, accumulatorRange, ch - '0');
1437  add(digit, accumulatorRange, accumulator, accumulatorRange);
1438  }
1439  copy(accumulator, accumulatorRange, vec, range);
1440 }
1441 
1449 template<class Word>
1450 void fromHex(Word *vec, const BitRange &range, const std::string &input) {
1451  fromString<Word, 4>(vec, range, input);
1452 }
1453 
1460 template<class Word>
1461 void fromOctal(Word *vec, const BitRange &range, const std::string &input) {
1462  fromString<Word, 3>(vec, range, input);
1463 }
1464 
1471 template<class Word>
1472 void fromBinary(Word *vec, const BitRange &range, const std::string &input) {
1473  fromString<Word, 1>(vec, range, input);
1474 }
1475 
1476 
1477 } // namespace
1478 } // namespace
1479 } // namespace
1480 #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.
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:13
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
void multiply10(Word *vec, const BitRange &range)
Multiply by 10.
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.