ROSE  0.11.145.0
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.overlaps(range2));
473  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
474 }
475 
476 template<class Word>
477 struct EqualTo {
478  bool wasEqv;
479 
480  EqualTo()
481  : wasEqv(true) {}
482 
483  bool operator()(const Word &w1, Word &w2, size_t nbits) {
484  if (wasEqv) {
485  Word a = w1 & bitMask<Word>(0, nbits);
486  Word b = w2 & bitMask<Word>(0, nbits);
487  wasEqv = a == b;
488  }
489  return false;
490  }
491 };
492 
496 template<class Word>
497 bool equalTo(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
498  if (range1.size() != range2.size())
499  return false;
500  EqualTo<Word> visitor;
501  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
502  return visitor.wasEqv;
503 }
504 
506 // Counting/searching
508 
509 
510 template<class Word>
512  size_t offset;
513  Optional<size_t> result;
514  LeastSignificantSetBit(): offset(0) {}
515  bool operator()(const Word &word, size_t nbits) {
516  if (0 != (word & bitMask<Word>(0, nbits))) {
517  for (size_t i=0; i<nbits; ++i) {
518  if (0 != (word & bitMask<Word>(i, 1))) {
519  result = offset + i;
520  return true;
521  }
522  }
523  }
524  offset += nbits;
525  return false;
526  }
527 };
528 
533 template<class Word>
534 Optional<size_t> leastSignificantSetBit(const Word *words, const BitRange &range) {
536  traverse(visitor, words, range, LowToHigh());
537  if (visitor.result)
538  return range.least() + *visitor.result;
539  return Nothing();
540 }
541 
542 template<class Word>
544  size_t offset;
545  Optional<size_t> result;
546  LeastSignificantClearBit(): offset(0) {}
547  bool operator()(const Word &word, size_t nbits) {
548  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
549  for (size_t i=0; i<nbits; ++i) {
550  if (0 == (word & bitMask<Word>(i, 1))) {
551  result = offset + i;
552  return true;
553  }
554  }
555  }
556  offset += nbits;
557  return false;
558  }
559 };
560 
565 template<class Word>
566 Optional<size_t> leastSignificantClearBit(const Word *words, const BitRange &range) {
568  traverse(visitor, words, range, LowToHigh());
569  if (visitor.result)
570  return range.least() + *visitor.result;
571  return Nothing();
572 }
573 
574 template<class Word>
576  size_t offset;
577  Optional<size_t> result;
578  MostSignificantSetBit(size_t nbits): offset(nbits) {}
579  bool operator()(const Word &word, size_t nbits) {
580  ASSERT_require(nbits <= offset);
581  offset -= nbits;
582  if (0 != (word & bitMask<Word>(0, nbits))) {
583  for (size_t i=nbits; i>0; --i) {
584  if (0 != (word & bitMask<Word>(i-1, 1))) {
585  result = offset + i-1;
586  return true;
587  }
588  }
589  }
590  return false;
591  }
592 };
593 
598 template<class Word>
599 Optional<size_t> mostSignificantSetBit(const Word *words, const BitRange &range) {
600  MostSignificantSetBit<Word> visitor(range.size());
601  traverse(visitor, words, range, HighToLow());
602  if (visitor.result)
603  return range.least() + *visitor.result;
604  return Nothing();
605 }
606 
607 template<class Word>
609  size_t offset;
610  Optional<size_t> result;
611  MostSignificantClearBit(size_t nbits): offset(nbits) {}
612  bool operator()(const Word &word, size_t nbits) {
613  ASSERT_require(nbits <= offset);
614  offset -= nbits;
615  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
616  for (size_t i=nbits; i>0; --i) {
617  if (0 == (word & bitMask<Word>(i-1, 1))) {
618  result = offset + i-1;
619  return true;
620  }
621  }
622  }
623  return false;
624  }
625 };
626 
631 template<class Word>
632 Optional<size_t> mostSignificantClearBit(const Word *words, const BitRange &range) {
633  MostSignificantClearBit<Word> visitor(range.size());
634  traverse(visitor, words, range, HighToLow());
635  if (visitor.result)
636  return range.least() + *visitor.result;
637  return Nothing();
638 }
639 
643 template<class Word>
644 bool isAllSet(const Word *words, const BitRange &range) {
645  return leastSignificantClearBit(words, range) ? false : true;
646 }
647 
651 template<class Word>
652 bool isAllClear(const Word *words, const BitRange &range) {
653  return leastSignificantSetBit(words, range) ? false : true;
654 }
655 
656 template<class Word>
657 struct CountSetBits {
658  size_t result;
659  CountSetBits(): result(0) {}
660  bool operator()(const Word &word, size_t nbits) {
661  if (0 != (word & bitMask<Word>(0, nbits))) {
662  for (size_t i=0; i<nbits; ++i) {
663  if (0 != (word & bitMask<Word>(i, 1)))
664  ++result;
665  }
666  }
667  return false;
668  }
669 };
670 
674 template<class Word>
675 size_t nSet(const Word *words, const BitRange &range) {
676  CountSetBits<Word> visitor;
677  traverse(visitor, words, range, LowToHigh());
678  return visitor.result;
679 }
680 
681 template<class Word>
683  size_t result;
684  CountClearBits(): result(0) {}
685  bool operator()(const Word &word, size_t nbits) {
686  if (bitMask<Word>(0, nbits) != (word & bitMask<Word>(0, nbits))) {
687  for (size_t i=0; i<nbits; ++i) {
688  if (0 == (word & bitMask<Word>(i, 1)))
689  ++result;
690  }
691  }
692  return false;
693  }
694 };
695 
699 template<class Word>
700 size_t nClear(const Word *words, const BitRange &range) {
701  CountClearBits<Word> visitor;
702  traverse(visitor, words, range, LowToHigh());
703  return visitor.result;
704 }
705 
706 template<class Word>
708  size_t offset;
709  Optional<size_t> result;
710  LeastSignificantDifference(): offset(0) {}
711  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
712  Word mask = bitMask<Word>(0, nbits);
713  if ((w1 & mask) != (w2 & mask)) {
714  for (size_t i=0; i<nbits; ++i) {
715  if ((w1 ^ w2) & bitMask<Word>(i, 1)) {
716  result = offset + i;
717  return true;
718  }
719  }
720  }
721  offset += nbits;
722  return false;
723  }
724 };
725 
731 template<class Word>
732 Optional<size_t> leastSignificantDifference(const Word *vec1, const BitRange &range1,
733  const Word *vec2, const BitRange &range2) {
735  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
736  return visitor.result;
737 }
738 
739 template<class Word>
741  size_t offset;
742  Optional<size_t> result;
743  MostSignificantDifference(size_t nbits): offset(nbits) {}
744  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
745  ASSERT_require(nbits <= offset);
746  offset -= nbits;
747  Word mask = bitMask<Word>(0, nbits);
748  if ((w1 & mask) != (w2 & mask)) {
749  for (size_t i=nbits; i>0; --i) {
750  if ((w1 ^ w2) & bitMask<Word>(i-1, 1)) {
751  result = offset + i-1;
752  return true;
753  }
754  }
755  }
756  return false;
757  }
758 };
759 
765 template<class Word>
766 Optional<size_t> mostSignificantDifference(const Word *vec1, const BitRange &range1,
767  const Word *vec2, const BitRange &range2) {
768  MostSignificantDifference<Word> visitor(range1.size());
769  traverse(visitor, vec1, range1, vec2, range2, HighToLow());
770  return visitor.result;
771 }
772 
777 template<class Word>
778 bool areEqual(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
779  if (range1.size()!=range2.size())
780  return false;
781  return leastSignificantDifference(vec1, range1, vec2, range2) ? false : true;
782 }
783 
785 // Shift/rotate
787 
792 template<class Word>
793 void shiftLeft(Word *words, const BitRange &range, size_t nShift, bool newBits=0) {
794  if (nShift < range.size()) {
795  size_t nbits = range.size() - nShift; // number of bits to move
796  BitRange shiftedFrom = BitRange::baseSize(range.least(), nbits);
797  BitRange shiftedTo = BitRange::baseSize(range.least() + nShift, nbits);
798  BitRange introduced = BitRange::baseSize(range.least(), nShift);
799  copy(words, shiftedFrom, words, shiftedTo);
800  setValue(words, introduced, newBits);
801  } else {
802  setValue(words, range, newBits);
803  }
804 }
805 
810 template<class Word>
811 void shiftRight(Word *words, const BitRange &range, size_t nShift, bool newBits=0) {
812  if (nShift < range.size()) {
813  size_t nbits = range.size() - nShift; // number of bits to move
814  BitRange shiftedFrom = BitRange::baseSize(range.least() + nShift, nbits);
815  BitRange shiftedTo = BitRange::baseSize(range.least(), nbits);
816  BitRange introduced = BitRange::baseSize(range.least() + nbits, nShift);
817  copy(words, shiftedFrom, words, shiftedTo);
818  setValue(words, introduced, newBits);
819  } else {
820  setValue(words, range, newBits);
821  }
822 }
823 
828 template<class Word>
829 void shiftRightArithmetic(Word *words, const BitRange &range, size_t nShift) {
830  if (!range.isEmpty()) {
831  bool newBits = get(words, range.greatest());
832  shiftRight(words, range, nShift, newBits);
833  }
834 }
835 
840 template<class Word>
841 void rotateRight(Word *words, const BitRange &range, size_t nShift) {
842  if (range.isEmpty())
843  return;
844  nShift %= range.size();
845  if (0==nShift)
846  return;
847 
848  // Save the low-order bits that will be shifted off
849  size_t nSavedWords = numberOfWords<Word>(nShift);
850  SAWYER_VARIABLE_LENGTH_ARRAY(Word, saved, nSavedWords);
851  BitRange savedRange = BitRange::baseSize(0, nShift);
852  copy(words, BitRange::baseSize(range.least(), nShift), saved, savedRange);
853 
854  shiftRight(words, range, nShift);
855 
856  BitRange introduced = BitRange::baseSize(range.least()+range.size()-nShift, nShift);
857  copy(saved, savedRange, words, introduced);
858 }
859 
864 template<class Word>
865 void rotateLeft(Word *words, const BitRange &range, size_t nShift) {
866  if (range.isEmpty())
867  return;
868  nShift %= range.size();
869  rotateRight(words, range, range.size()-nShift);
870 }
871 
872 
874 // Bit-wise Boolean logic
876 
877 template<class Word>
878 struct InvertBits {
879  bool operator()(Word &word, size_t nbits) {
880  word ^= bitMask<Word>(0, nbits);
881  return false;
882  }
883 };
884 
888 template<class Word>
889 void invert(Word *words, const BitRange &range) {
890  InvertBits<Word> visitor;
891  traverse(visitor, words, range, LowToHigh());
892 }
893 
894 template<class Word>
895 struct AndBits {
896  bool operator()(const Word &w1, Word &w2, size_t nbits) {
897  w2 &= w1 | ~bitMask<Word>(0, nbits);
898  return false;
899  }
900 };
901 
906 template<class Word>
907 void bitwiseAnd(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
908  AndBits<Word> visitor;
909  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
910 }
911 
912 template<class Word>
913 struct OrBits {
914  bool operator()(const Word &w1, Word &w2, size_t nbits) {
915  w2 |= w1 & bitMask<Word>(0, nbits);
916  return false;
917  }
918 };
919 
924 template<class Word>
925 void bitwiseOr(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
926  OrBits<Word> visitor;
927  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
928 }
929 
930 template<class Word>
931 struct XorBits {
932  bool operator()(const Word &w1, Word &w2, size_t nbits) {
933  w2 ^= w1 & bitMask<Word>(0, nbits);
934  return false;
935  }
936 };
937 
942 template<class Word>
943 void bitwiseXor(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
944  XorBits<Word> visitor;
945  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
946 }
947 
948 
950 // Arithmetic
952 
956 template<class Word>
957 void fromInteger(Word *words, const BitRange &range, boost::uint64_t value) {
958  ASSERT_require(8==sizeof value);
959  if (range.isEmpty())
960  return;
961 
962  // Create a bit vector that is just the value
963  size_t nbits = std::min(range.size(), (size_t)64); // number of significant bits to copy, not fill
964  Word wordMask = bitMask<Word>(0, bitsPerWord<Word>::value);
965  size_t nTmpWords = numberOfWords<Word>(nbits);
966  SAWYER_VARIABLE_LENGTH_ARRAY(Word, tmp, nTmpWords);
967  for (size_t i=0; i<nTmpWords; ++i)
968  tmp[i] = (Word)((value >> (i * bitsPerWord<Word>::value)) & wordMask);
969 
970  // Copy the value's bit vector to the destination and zero-fill
971  copy(tmp, BitRange::baseSize(0, nbits), words, BitRange::baseSize(range.least(), nbits));
972  if (range.size() >= 64) {
973  BitRange hi = BitRange::baseSize(range.least() + 64, range.size() - 64);
974  clear(words, hi);
975  }
976 }
977 
982 template<class Word>
983 boost::uint64_t toInteger(const Word *words, const BitRange &range) {
984  boost::uint64_t result = 0;
985  ASSERT_require(8==sizeof result);
986 
987  // Copy the bits into the low bits of a temporary bit vector
988  size_t nbits = std::min(range.size(), (size_t)64);
989  size_t nTmpWords = numberOfWords<Word>(nbits);
990  SAWYER_VARIABLE_LENGTH_ARRAY(typename RemoveConst<Word>::Base, tmp, nTmpWords);
991  BitRange lo = BitRange::baseSize(range.least(), nbits);
992  copy(words, lo, tmp, BitRange::baseSize(0, nbits));
993 
994  // Convert the temporary bit vector to an integer
995  for (size_t i=0; i<nTmpWords; ++i)
996  result |= (boost::uint64_t)tmp[i] << (i * bitsPerWord<Word>::value);
997  return result;
998 }
999 
1003 template<class Word>
1004 boost::uint64_t toInteger(const Word *words, size_t nbits) {
1005  boost::uint64_t result = 0;
1006  ASSERT_require(nbits <= 64);
1007  size_t nTmpWords = numberOfWords<Word>(nbits);
1008  for (size_t i=0; i<nTmpWords; ++i)
1009  result |= (boost::uint64_t)words[i] << (i * bitsPerWord<Word>::value);
1010  if (nbits < 64)
1011  result &= ~((~(boost::uint64_t)0) << nbits);
1012  return result;
1013 }
1014 
1020 template<class Word>
1021 boost::int64_t toSignedInteger(const Word *words, const BitRange &range) {
1022  boost::uint64_t u = toInteger<Word>(words, range);
1023  const size_t nBits = range.size();
1024  if (nBits > 1 && nBits < 64) {
1025  bool isNegative = (u & (boost::uint64_t(1) << (nBits-1))) != 0;
1026  if (isNegative)
1027  u |= boost::uint64_t(-1) << nBits;
1028  }
1029  return boost::int64_t(u);
1030 }
1031 
1036 template<class Word>
1037 boost::int64_t toSignedInteger(const Word *words, size_t nBits) {
1038  boost::uint64_t u = toInteger<Word>(words, nBits);
1039  if (nBits > 1 && nBits < 64) {
1040  bool isNegative = (u & (boost::uint64_t(1) << (nBits-1))) != 0;
1041  if (isNegative)
1042  u |= boost::uint64_t(-1) << nBits;
1043  }
1044  return boost::int64_t(u);
1045 }
1046 
1047 template<class Word>
1048 struct Increment {
1049  bool carry;
1050  Increment(): carry(true) {}
1051  bool operator()(Word &word, size_t nbits) {
1052  ASSERT_require(carry);
1053  Word mask = bitMask<Word>(0, nbits);
1054  Word arg1 = word & mask;
1055  Word sum = arg1 + 1;
1056  word &= ~mask;
1057  word |= sum & mask;
1058  carry = (sum & mask) < arg1;
1059  return !carry; // terminate traversal when carry is false
1060  }
1061 };
1062 
1066 template<class Word>
1067 bool increment(Word *vec1, const BitRange &range1) {
1068  Increment<Word> visitor;
1069  traverse(visitor, vec1, range1, LowToHigh());
1070  return visitor.carry;
1071 }
1072 
1073 template<class Word>
1074 struct Decrement {
1075  bool borrowed;
1076  Decrement(): borrowed(true) {}
1077  bool operator()(Word &word, size_t nbits) {
1078  ASSERT_require(borrowed);
1079  Word mask = bitMask<Word>(0, nbits);
1080  Word arg1 = word & mask;
1081  borrowed = 0==arg1;
1082  Word difference = (arg1 - 1) & mask;
1083  word &= ~mask;
1084  word |= difference;
1085  return !borrowed; // terminate traversal unless we borrowed
1086  }
1087 };
1088 
1093 template<class Word>
1094 bool decrement(Word *vec1, const BitRange &range1) {
1095  Decrement<Word> visitor;
1096  traverse(visitor, vec1, range1, LowToHigh());
1097  return visitor.borrowed;
1098 }
1099 
1103 template<class Word>
1104 void negate(Word *vec1, const BitRange &range) {
1105  invert(vec1, range);
1106  increment(vec1, range);
1107 }
1108 
1109 template<class Word>
1110 struct AddBits {
1111  bool carry;
1112  AddBits(bool carry): carry(carry) {}
1113  bool operator()(const Word &w1, Word &w2, size_t nbits) {
1114  Word mask = bitMask<Word>(0, nbits);
1115  Word addend1(carry ? 1 : 0);
1116  Word addend2(w1 & mask);
1117  Word addend3(w2 & mask);
1118  Word sum = addend1 + addend2 + addend3;
1119  w2 &= ~mask;
1120  w2 |= sum & mask;
1121  if (nbits == bitsPerWord<Word>::value) {
1122  carry = sum < addend2 || (sum==addend2 && carry);
1123  } else {
1124  carry = 0 != (sum & bitMask<Word>(nbits, 1));
1125  }
1126  return false;
1127  }
1128 };
1129 
1134 template<class Word>
1135 bool add(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2, bool carryIn=false) {
1136  AddBits<Word> visitor(carryIn);
1137  traverse(visitor, vec1, range1, vec2, range2, LowToHigh());
1138  return visitor.carry;
1139 }
1140 
1147 template<class Word>
1148 bool subtract(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
1149  size_t nTempWords = numberOfWords<Word>(range1.size());
1150  SAWYER_VARIABLE_LENGTH_ARRAY(Word, temp, nTempWords);
1151  BitRange tempRange = BitRange::baseSize(0, range1.size());
1152  copy(vec1, range1, temp, tempRange);
1153  invert(temp, tempRange);
1154  return add(temp, tempRange, vec2, range2, true);
1155 }
1156 
1163 template<class Word>
1164 bool signExtend(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2) {
1165  if (range2.isEmpty()) {
1166  return false;
1167  } else if (range1.isEmpty()) {
1168  clear(vec2, range2);
1169  return false;
1170  } else if (range1.size() < range2.size()) { // sign extension
1171  bool oldSign = get(vec1, range1.greatest());
1172  copy(vec1, range1, vec2, BitRange::baseSize(range2.least(), range1.size()));
1173  setValue(vec2, BitRange::hull(range2.least()+range1.size(), range2.greatest()), oldSign);
1174  return oldSign;
1175  } else { // truncation or plain copy
1176  ASSERT_require(range1.size() >= range2.size());
1177  BitRange copyFrom = BitRange::baseSize(range1.least(), range2.size());
1178  copy(vec1, copyFrom, vec2, range2);
1179  return get(vec2, range2.greatest());
1180  }
1181 }
1182 
1186 template<class Word>
1187 void multiply10(Word *vec, const BitRange &range) {
1188  // n * 10 == n * (8 + 2) == n*8 + n*2 == (n<<3) + (n<<1)
1189  const size_t nWords = numberOfWords<Word>(range.size());
1190  BitRange partRange = BitRange::baseSize(0, range.size());
1191  SAWYER_VARIABLE_LENGTH_ARRAY(Word, part, nWords);
1192  copy(vec, range, part, partRange);
1193  shiftLeft(vec, range, 3);
1194  shiftLeft(part, partRange, 1);
1195  add(part, partRange, vec, range);
1196 }
1197 
1199 // Numeric comparison
1201 
1205 template<class Word>
1206 bool isEqualToZero(const Word *vec1, const BitRange &range1) {
1207  return isAllClear(vec1, range1);
1208 }
1209 
1210 template<class Word>
1211 struct CompareBits {
1212  int result;
1213  CompareBits(): result(0) {}
1214  bool operator()(const Word &w1, const Word &w2, size_t nbits) {
1215  Word mask = bitMask<Word>(0, nbits);
1216  Word tmp1 = w1 & mask;
1217  Word tmp2 = w2 & mask;
1218  if (tmp1 < tmp2) {
1219  result = -1;
1220  return true;
1221  } else if (tmp1 > tmp2) {
1222  result = 1;
1223  return true;
1224  } else {
1225  return false;
1226  }
1227  }
1228 };
1229 
1236 template<class Word>
1237 int compare(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
1238  if (range1.isEmpty() && range2.isEmpty()) {
1239  return 0;
1240  } else if (range1.isEmpty()) {
1241  return isEqualToZero(vec2, range2) ? 0 : -1;
1242  } else if (range2.isEmpty()) {
1243  return isEqualToZero(vec1, range1) ? 0 : 1;
1244  } else if (range1.size() < range2.size()) {
1245  BitRange hi = BitRange::hull(range2.least() + range1.size(), range2.greatest());
1246  if (!isEqualToZero(vec2, hi))
1247  return -1;
1248  BitRange lo = BitRange::baseSize(range2.least(), range1.size());
1249  return compare(vec1, range1, vec2, lo);
1250  } else if (range1.size() > range2.size()) {
1251  BitRange hi = BitRange::hull(range1.least() + range2.size(), range1.greatest());
1252  if (!isEqualToZero(vec1, hi))
1253  return 1;
1254  BitRange lo = BitRange::baseSize(range1.least(), range2.size());
1255  return compare(vec1, lo, vec2, range2);
1256  } else {
1257  ASSERT_require(!range1.isEmpty() && !range2.isEmpty());
1258  ASSERT_require(range1.size() == range2.size());
1259  CompareBits<Word> visitor;
1260  traverse(visitor, vec1, range1, vec2, range2, HighToLow());
1261  return visitor.result;
1262  }
1263 }
1264 
1271 template<class Word>
1272 int compareSigned(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2) {
1273  if (range1.isEmpty() && range2.isEmpty()) {
1274  return 0;
1275  } else if (range1.isEmpty()) {
1276  if (Optional<size_t> mssb = mostSignificantSetBit(vec2, range2)) {
1277  return *mssb == range2.greatest() ? 1 : -1;
1278  } else {
1279  return 0;
1280  }
1281  } else if (range2.isEmpty()) {
1282  if (Optional<size_t> mssb = mostSignificantSetBit(vec1, range1)) {
1283  return *mssb == range1.greatest() ? -1 : 1;
1284  } else {
1285  return 0;
1286  }
1287  } else if (range1.size() < range2.size()) {
1288  BitRange hi = BitRange::hull(range2.least()+range1.size(), range2.greatest());
1289  bool neg1 = get(vec1, range1.greatest());
1290  bool neg2 = get(vec2, range2.greatest());
1291  if (!neg1 && !neg2) { // both are non-negative, so leverage unsigned comparison
1292  return compare(vec1, range1, vec2, range2);
1293  } else if (neg1 && neg2) { // both are negative
1294  if (nSet(vec2, hi)==hi.size() && get(vec2, hi.least()-1)) {
1295  return compareSigned(vec1, range1, vec2, BitRange::baseSize(range2.least(), range1.size()));
1296  } else {
1297  return 1; // vec2 is less than vec1
1298  }
1299  } else if (neg1) { // vec1 is negative but vec2 isn't
1300  return -1;
1301  } else { // vec2 is negative but vec1 isn't
1302  return 1;
1303  }
1304  } else if (range1.size() > range2.size()) { // call recursively to trigger previous case
1305  return -1 * compareSigned(vec2, range2, vec1, range1);
1306  } else {
1307  ASSERT_require(range1.size()==range2.size());
1308  bool neg1 = get(vec1, range1.greatest());
1309  bool neg2 = get(vec2, range2.greatest());
1310  if (!neg1 && !neg2) {
1311  return compare(vec1, range1, vec2, range2);
1312  } else if (neg1 && neg2) {
1313  if (Optional<size_t> diff = mostSignificantDifference(vec1, range1, vec2, range2)) {
1314  return get(vec1, range1.least() + *diff) ? 1 : -1;
1315  } else {
1316  return 0;
1317  }
1318  } else if (neg1) {
1319  return -1;
1320  } else {
1321  return 1;
1322  }
1323  }
1324 }
1325 
1327 // Byte representation
1329 template<class Word>
1330 struct ToBytes {
1331  Word remaining = 0; // left over bits from a previous iteration
1332  size_t nremaining = 0; // number valid low-order bits in "remaining" data member
1333  std::vector<uint8_t> bytes; // resulting bytes in little endian order.
1334 
1335  ToBytes(size_t nBitsTotal) {
1336  const size_t nBytes = (nBitsTotal + 7) / 8;
1337  bytes.reserve(nBytes);
1338  }
1339 
1340  bool operator()(const Word &word, size_t nbits) {
1341  Word tmp = word;
1342  ASSERT_require(nremaining < size_t(8));
1343  while (nremaining + nbits >= size_t(8)) {
1344  const size_t nrem = nremaining; // number left-over bits to use
1345  const size_t nnew = size_t(8) - nrem; // number of new bits to use
1346  const Word byte = (remaining & bitMask<Word>(0, nrem)) | ((tmp & bitMask<Word>(0, nnew)) << nrem);
1347  bytes.push_back(byte);
1348  nremaining = 0;
1349  nbits -= nnew;
1350  tmp >>= nnew;
1351  }
1352  nremaining = nbits;
1353  remaining = tmp;
1354  return false;
1355  }
1356 
1357  std::vector<uint8_t> result() {
1358  if (nremaining > 0) {
1359  ASSERT_require(nremaining <= 7);
1360  const uint8_t byte = remaining & bitMask<Word>(0, nremaining);
1361  bytes.push_back(byte);
1362  }
1363  return std::move(bytes);
1364  }
1365 };
1366 
1367 template<class Word>
1368 std::vector<uint8_t>
1369 toBytes(const Word *vec, const BitRange &range) {
1370  ToBytes<Word> visitor(range.size());
1371  traverse(visitor, vec, range, LowToHigh());
1372  return visitor.result();
1373 }
1374 
1375 template<class Word>
1376 void fromBytes(Word *vec, const BitRange &range, const std::vector<uint8_t> &input) {
1377  // Copy bytes into the vector
1378  size_t offset = 0; // bit offset from range.least()
1379  for (size_t idx = 0; idx < input.size() && offset < range.size(); ++idx) {
1380  const Word byte = input[idx];
1381  const size_t nbits = std::min(size_t(8), range.size() - offset); // number of bits to copy
1382  copy(&byte, BitRange::baseSize(0, nbits), vec, BitRange::baseSize(range.least() + offset, nbits));
1383  offset += nbits;
1384  }
1385 
1386  // Zero fill high order stuff that we didn't already initialize
1387  if (offset < range.size())
1388  clear(vec, BitRange::hull(range.least() + offset, range.greatest()));
1389 }
1390 
1392 // String representation
1394 
1395 // Can handle binary, base-4, octal, or hexadecimal
1396 template<class Word, size_t bitsPerDigit>
1397 struct ToString {
1398  Word remaining; // left over bits from a previous iteration
1399  size_t nremaining; // number valid low-order bits in "remaining" data member
1400  std::string reversed; // resulting string with the least significant digit first
1401 
1402  ToString(): remaining(0), nremaining(0) {
1403  ASSERT_require(bitsPerDigit >= 1 && bitsPerDigit <= 4);
1404  ASSERT_require(bitsPerDigit <= bitsPerWord<Word>::value);
1405  }
1406 
1407  bool operator()(const Word &word, size_t nbits) {
1408  static const char digits[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
1409  Word tmp = word & bitMask<Word>(0, nbits);
1410  ASSERT_require(nremaining < bitsPerDigit);
1411  while (nremaining+nbits >= bitsPerDigit) {
1412  size_t nrem = std::min(nremaining, bitsPerDigit); // number left-over bits to use
1413  size_t nnew = bitsPerDigit - nrem; // number of new bits to use
1414  Word digit = (remaining & bitMask<Word>(0, nrem)) | ((tmp & bitMask<Word>(0, nnew)) << nrem);
1415  reversed += digits[digit];
1416  nremaining = 0;
1417  nbits -= nnew;
1418  tmp >>= nnew;
1419  }
1420  nremaining = nbits;
1421  remaining = tmp;
1422  return false;
1423  }
1424 
1425  std::string result() {
1426  if (nremaining > 0) {
1427  ASSERT_require(nremaining <= 3); // digits '0' through '7'
1428  reversed += '0' + (remaining & bitMask<Word>(0, nremaining));
1429  nremaining = 0;
1430  }
1431  std::string s;
1432  std::swap(s, reversed);
1433  std::reverse(s.begin(), s.end());
1434  return s;
1435  }
1436 };
1437 
1444 template<class Word>
1445 std::string toHex(const Word *vec, const BitRange &range) {
1446  ToString<Word, 4> visitor;
1447  traverse(visitor, vec, range, LowToHigh());
1448  return visitor.result();
1449 }
1450 
1456 template<class Word>
1457 std::string toOctal(const Word *vec, const BitRange &range) {
1458  ToString<Word, 3> visitor;
1459  traverse(visitor, vec, range, LowToHigh());
1460  return visitor.result();
1461 }
1462 
1468 template<class Word>
1469 std::string toBinary(const Word *vec, const BitRange &range) {
1470  ToString<Word, 1> visitor;
1471  traverse(visitor, vec, range, LowToHigh());
1472  return visitor.result();
1473 }
1474 
1476 // Parsing
1478 
1479 template<class Word>
1480 Word charToDigit(char ch) {
1481  Word digit;
1482  if (ch >= '0' && ch <= '9') {
1483  digit = ch - '0';
1484  } else if (ch >= 'a' && ch <= 'f') {
1485  digit = ch - 'a' + 10;
1486  } else if (ch >= 'A' && ch <= 'F') {
1487  digit = ch - 'A' + 10;
1488  } else {
1489  digit = 16; // signals an invalid character
1490  }
1491  return digit;
1492 }
1493 
1494 template<class Word, size_t bitsPerDigit>
1495 void fromString(Word *vec, const BitRange &range, const std::string &input) {
1496  ASSERT_require(bitsPerDigit >= 1 && bitsPerDigit <= 4);
1497  ASSERT_require(bitsPerDigit <= bitsPerWord<Word>::value);
1498 
1499  // Check that all characters of the string are valid.
1500  for (size_t idx=0; idx<input.size(); ++idx) {
1501  if ('_'!=input[idx] && charToDigit<Word>(input[idx]) >= Word(1) << bitsPerDigit) {
1502  throw std::runtime_error(std::string("invalid character '") + input[idx] + "' at index " +
1503  boost::lexical_cast<std::string>(idx) + " in base-" +
1504  boost::lexical_cast<std::string>(1 << bitsPerDigit) + " input string");
1505  }
1506  }
1507 
1508  // Copy digits into the vector
1509  size_t offset = 0; // bit offset from range.least()
1510  for (size_t idx=input.size(); idx>0 && offset<range.size(); --idx) {
1511  if ('_'!=input[idx-1]) {
1512  Word digit = charToDigit<Word>(input[idx-1]);
1513  size_t nbits = std::min(bitsPerDigit, range.size()-offset);// number of bits of digit to copy into vector
1514  copy(&digit, BitRange::baseSize(0, std::min(bitsPerDigit, nbits)),
1515  vec, BitRange::baseSize(range.least()+offset, nbits));
1516  offset += bitsPerDigit;
1517  }
1518  }
1519 
1520  // Zero fill high order stuff that we didn't already initialize
1521  if (offset < range.size())
1522  clear(vec, BitRange::hull(range.least()+offset, range.greatest()));
1523 }
1524 
1532 template<class Word>
1533 void fromDecimal(Word *vec, const BitRange &range, const std::string &input) {
1534  // First try parsing a value that fits in 64 bits.
1535  boost::uint64_t v = 0;
1536  bool hadOverflow = false;
1537  BOOST_FOREACH (char ch, input) {
1538  if (isdigit(ch)) {
1539  boost::uint64_t tmp = v * 10 + (ch - '0');
1540  if (tmp < v) {
1541  hadOverflow = true;
1542  break;
1543  }
1544  v = tmp;
1545  } else if (ch != '_') {
1546  throw std::runtime_error("invalid decimal digit \"" + std::string(1, ch) + "\"");
1547  }
1548  }
1549  if (!hadOverflow) {
1550  fromInteger(vec, range, v);
1551  return;
1552  }
1553 
1554  // If 64 bits isn't wide enough, do it the slow way.
1555  const size_t nWords = numberOfWords<Word>(range.size());
1556  SAWYER_VARIABLE_LENGTH_ARRAY(Word, accumulator, nWords);
1557  SAWYER_VARIABLE_LENGTH_ARRAY(Word, digit, nWords);
1558  BitRange accumulatorRange = BitRange::baseSize(0, range.size());
1559  BOOST_FOREACH (char ch, input) {
1560  multiply10(accumulator, accumulatorRange);
1561  fromInteger(digit, accumulatorRange, ch - '0');
1562  add(digit, accumulatorRange, accumulator, accumulatorRange);
1563  }
1564  copy(accumulator, accumulatorRange, vec, range);
1565 }
1566 
1574 template<class Word>
1575 void fromHex(Word *vec, const BitRange &range, const std::string &input) {
1576  fromString<Word, 4>(vec, range, input);
1577 }
1578 
1585 template<class Word>
1586 void fromOctal(Word *vec, const BitRange &range, const std::string &input) {
1587  fromString<Word, 3>(vec, range, input);
1588 }
1589 
1596 template<class Word>
1597 void fromBinary(Word *vec, const BitRange &range, const std::string &input) {
1598  fromString<Word, 1>(vec, range, input);
1599 }
1600 
1601 
1602 } // namespace
1603 } // namespace
1604 } // namespace
1605 #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.
boost::int64_t toSignedInteger(const Word *words, const BitRange &range)
Convert a bit vector to a signed integer.
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 equalTo(const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
Compare bits for equality.
Value size() const
Size of interval.
Definition: Interval.h:291
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:219
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: FeasiblePath.h:767
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:162
T least() const
Returns lower limit.
Definition: Interval.h:207
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:151
void shiftRightArithmetic(Word *words, const BitRange &range, size_t nShift)
Shift bits right arithmetically.
void bitwiseXor(const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
Bit-wise XOR.
Optional< size_t > 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.
bool overlaps(const Interval &other) const
True if two intervals overlap.
Definition: Interval.h:232
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:213
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.