ROSE  0.9.9.139
Classes | Typedefs | Functions
Sawyer::Container::BitVectorSupport Namespace Reference

Description

Support functions for bit vectors.

Classes

struct  AddBits
 
struct  AndBits
 
struct  bitsPerWord
 Number of bits per word. More...
 
struct  ClearBits
 
struct  CompareBits
 
struct  CopyBits
 
struct  CountClearBits
 
struct  CountSetBits
 
struct  Decrement
 
struct  HighToLow
 
struct  Increment
 
struct  InvertBits
 
struct  LeastSignificantClearBit
 
struct  LeastSignificantDifference
 
struct  LeastSignificantSetBit
 
struct  LowToHigh
 Tags for traversal directions. More...
 
struct  MostSignificantClearBit
 
struct  MostSignificantDifference
 
struct  MostSignificantSetBit
 
struct  OrBits
 
struct  RemoveConst
 For removing const qualifiers. More...
 
struct  RemoveConst< const T >
 
struct  SetBits
 
struct  SwapBits
 
struct  ToString
 
struct  XorBits
 

Typedefs

typedef Interval< size_t > BitRange
 

Functions

template<class Word >
size_t wordIndex (size_t idx)
 Index to bit vector word. More...
 
template<class Word >
size_t bitIndex (size_t idx)
 Index to bit within word. More...
 
template<class Word >
size_t numberOfWords (size_t nbits)
 Number of words to hold indicated number of bits. More...
 
template<class Word >
Word bitMask (size_t offset, size_t nbits)
 Creates a mask. More...
 
template<class Word >
void nonoverlappingCopy (const Word *src, const BitRange &srcRange, Word *dst, const BitRange &dstRange)
 
template<class Src , class Dst >
void conditionalCopy (const Src *src, const BitRange &srcRange, Dst *dst, const BitRange &dstRange)
 
template<class Src , class Dst >
void conditionalCopy (const Src *, const BitRange &, const Dst *, const BitRange &)
 
template<class Processor , class Word >
void traverse (Processor &processor, Word *words, const BitRange &range, LowToHigh)
 Traverses a range of bits. More...
 
template<class Processor , class Word >
void traverse (Processor &processor, Word *words, const BitRange &range, HighToLow)
 Traverse one range of bits starting with the most significant bit. More...
 
template<class Processor , class Word1 , class Word2 >
void traverse2 (Processor &processor, Word1 *vec1, const BitRange &range1, Word2 *vec2, const BitRange &range2, LowToHigh)
 Traverse two ranges of bits from low to high. More...
 
template<class Processor , class Word1 , class Word2 >
void traverse2 (Processor &processor, Word1 *vec1, const BitRange &range1, Word2 *vec2, const BitRange &range2, HighToLow)
 Traverse two ranges of bits from high to low. More...
 
template<class Processor , class Word >
void traverse (Processor &processor, const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2, HighToLow dir)
 
template<class Processor , class Word >
void traverse (Processor &processor, const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2, LowToHigh dir)
 
template<class Processor , class Word >
void traverse (Processor &processor, const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2, LowToHigh dir)
 
template<class Processor , class Word >
void traverse (Processor &processor, Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2, LowToHigh dir)
 
template<class Word >
bool get (const Word *words, size_t idx)
 Return a single bit. More...
 
template<class Word >
void clear (Word *words, const BitRange &where)
 Clear some bits. More...
 
template<class Word >
void set (Word *words, const BitRange &where)
 Set some bits. More...
 
template<class Word >
void setValue (Word *words, const BitRange &where, bool value)
 Set or clear some bits. More...
 
template<class Word >
void copy (const Word *src, const BitRange &srcRange, Word *dst, const BitRange &dstRange)
 Copy some bits. More...
 
template<class Word >
void swap (Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
 Swap some bits. More...
 
template<class Word >
Optional< size_t > leastSignificantSetBit (const Word *words, const BitRange &range)
 Index of least significant set bit. More...
 
template<class Word >
Optional< size_t > leastSignificantClearBit (const Word *words, const BitRange &range)
 Index of least significant zero bit. More...
 
template<class Word >
Optional< size_t > mostSignificantSetBit (const Word *words, const BitRange &range)
 Index of most significant set bit. More...
 
template<class Word >
Optional< size_t > mostSignificantClearBit (const Word *words, const BitRange &range)
 Index of most significant clear bit. More...
 
template<class Word >
bool isAllSet (const Word *words, const BitRange &range)
 True if all bits are set. More...
 
template<class Word >
bool isAllClear (const Word *words, const BitRange &range)
 True if all bits are clear. More...
 
template<class Word >
size_t nSet (const Word *words, const BitRange &range)
 Number of set bits. More...
 
template<class Word >
size_t nClear (const Word *words, const BitRange &range)
 Number of clear bits. More...
 
template<class Word >
Optional< size_t > leastSignificantDifference (const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
 Find least significant different bits. More...
 
template<class Word >
Optional< size_t > mostSignificantDifference (const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
 Find most significant different bits. More...
 
template<class Word >
bool areEqual (const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
 Equality predicate. More...
 
template<class Word >
void shiftLeft (Word *words, const BitRange &range, size_t nShift, bool newBits=0)
 Shift bits left. More...
 
template<class Word >
void shiftRight (Word *words, const BitRange &range, size_t nShift, bool newBits=0)
 Shift bits right. More...
 
template<class Word >
void shiftRightArithmetic (Word *words, const BitRange &range, size_t nShift)
 Shift bits right arithmetically. More...
 
template<class Word >
void rotateRight (Word *words, const BitRange &range, size_t nShift)
 Rotate bits to the right. More...
 
template<class Word >
void rotateLeft (Word *words, const BitRange &range, size_t nShift)
 Rotate bits to the left. More...
 
template<class Word >
void invert (Word *words, const BitRange &range)
 Invert bits. More...
 
template<class Word >
void bitwiseAnd (const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
 Bit-wise AND. More...
 
template<class Word >
void bitwiseOr (const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
 Bit-wise OR. More...
 
template<class Word >
void bitwiseXor (const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
 Bit-wise XOR. More...
 
template<class Word >
void fromInteger (Word *words, const BitRange &range, boost::uint64_t value)
 Assign an unsigned value to a bit range. More...
 
template<class Word >
boost::uint64_t toInteger (const Word *words, const BitRange &range)
 Convert a bit vector to an integer. More...
 
template<class Word >
boost::uint64_t toInteger (const Word *words, size_t nbits)
 Convert a small bit vector to an integer. More...
 
template<class Word >
bool increment (Word *vec1, const BitRange &range1)
 Increment. More...
 
template<class Word >
bool decrement (Word *vec1, const BitRange &range1)
 Decrement. More...
 
template<class Word >
void negate (Word *vec1, const BitRange &range)
 Negate bits as an integer. More...
 
template<class Word >
bool add (const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2, bool carryIn=false)
 Add bits. More...
 
template<class Word >
bool subtract (const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
 Subtract bits. More...
 
template<class Word >
bool signExtend (const Word *vec1, const BitRange &range1, Word *vec2, const BitRange &range2)
 Sign extend. More...
 
template<class Word >
bool isEqualToZero (const Word *vec1, const BitRange &range1)
 Compares with zero. More...
 
template<class Word >
int compare (const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
 Unsigned comparison. More...
 
template<class Word >
int compareSigned (const Word *vec1, const BitRange &range1, const Word *vec2, const BitRange &range2)
 Signed comparison. More...
 
template<class Word >
std::string toHex (const Word *vec, const BitRange &range)
 Hexadecimal representation. More...
 
template<class Word >
std::string toOctal (const Word *vec, const BitRange &range)
 Octal representation. More...
 
template<class Word >
std::string toBinary (const Word *vec, const BitRange &range)
 Binary representation. More...
 
template<class Word >
Word charToDigit (char ch)
 
template<class Word , size_t bitsPerDigit>
void fromString (Word *vec, const BitRange &range, const std::string &input)
 
template<class Word >
void fromDecimal (Word *vec, const BitRange &range, const std::string &input)
 Obtain bits from a decimal representation. More...
 
template<class Word >
void fromHex (Word *vec, const BitRange &range, const std::string &input)
 Obtain bits from a hexadecimal representation. More...
 
template<class Word >
void fromOctal (Word *vec, const BitRange &range, const std::string &input)
 Obtain bits from an octal representation. More...
 
template<class Word >
void fromBinary (Word *vec, const BitRange &range, const std::string &input)
 Obtain bits from a binary representation. More...
 
template<class Processor , class Word >
bool processWord (Processor &processor, const Word &word, size_t shift, size_t nbits)
 Invoke the a processor for a vector traversal. More...
 
template<class Processor , class Word >
bool processWord (Processor &processor, Word &word, size_t shift, size_t nbits)
 Invoke the a processor for a vector traversal. More...
 
template<class Processor , class Word >
bool processWord (Processor &processor, const Word &src, Word &dst, size_t shift, size_t nbits)
 Invoke the a processor for a vector traversal. More...
 
template<class Processor , class Word >
bool processWord (Processor &processor, Word &w1, Word &w2, size_t shift, size_t nbits)
 Invoke the a processor for a vector traversal. More...
 
template<class Processor , class Word >
bool processWord (Processor &processor, const Word &w1, const Word &w2, size_t shift, size_t nbits)
 Invoke the a processor for a vector traversal. More...
 

Function Documentation

template<class Word >
size_t Sawyer::Container::BitVectorSupport::wordIndex ( size_t  idx)

Index to bit vector word.

Returns the index to a bit vector word. Bit zero of the bit vector is in word index zero.

Definition at line 49 of file BitVectorSupport.h.

template<class Word >
size_t Sawyer::Container::BitVectorSupport::bitIndex ( size_t  idx)

Index to bit within word.

Returns the index of a bit within a word. Bit zero is the least significant bit of the word.

Definition at line 57 of file BitVectorSupport.h.

template<class Word >
size_t Sawyer::Container::BitVectorSupport::numberOfWords ( size_t  nbits)

Number of words to hold indicated number of bits.

Definition at line 63 of file BitVectorSupport.h.

template<class Word >
Word Sawyer::Container::BitVectorSupport::bitMask ( size_t  offset,
size_t  nbits 
)

Creates a mask.

Returns a mask which contains all zeros except for nbits consecutive bits set beginning at offset and continuing in a more-significant direction.

Definition at line 72 of file BitVectorSupport.h.

template<class Processor , class Word >
bool Sawyer::Container::BitVectorSupport::processWord ( Processor &  processor,
const Word &  word,
size_t  shift,
size_t  nbits 
)

Invoke the a processor for a vector traversal.

Returns true when the word is "found" and the traversal can abort.

Definition at line 84 of file BitVectorSupport.h.

Referenced by traverse(), and traverse2().

template<class Processor , class Word >
bool Sawyer::Container::BitVectorSupport::processWord ( Processor &  processor,
Word &  word,
size_t  shift,
size_t  nbits 
)

Invoke the a processor for a vector traversal.

Returns true when the word is "found" and the traversal can abort.

Definition at line 92 of file BitVectorSupport.h.

template<class Processor , class Word >
bool Sawyer::Container::BitVectorSupport::processWord ( Processor &  processor,
const Word &  src,
Word &  dst,
size_t  shift,
size_t  nbits 
)

Invoke the a processor for a vector traversal.

Returns true when the word is "found" and the traversal can abort.

Definition at line 102 of file BitVectorSupport.h.

template<class Processor , class Word >
bool Sawyer::Container::BitVectorSupport::processWord ( Processor &  processor,
Word &  w1,
Word &  w2,
size_t  shift,
size_t  nbits 
)

Invoke the a processor for a vector traversal.

Returns true when the word is "found" and the traversal can abort.

Definition at line 113 of file BitVectorSupport.h.

template<class Processor , class Word >
bool Sawyer::Container::BitVectorSupport::processWord ( Processor &  processor,
const Word &  w1,
const Word &  w2,
size_t  shift,
size_t  nbits 
)

Invoke the a processor for a vector traversal.

Returns true when the word is "found" and the traversal can abort.

Definition at line 127 of file BitVectorSupport.h.

template<class Processor , class Word >
void Sawyer::Container::BitVectorSupport::traverse ( Processor &  processor,
Word *  words,
const BitRange range,
LowToHigh   
)

Traverses a range of bits.

Traverses a subset of the bits in the words array by invoking the processor function on each word. The least significant traversed word will be right-shifted if necessary so that the least significant bit of the range will be at bit index zero when the processor is invoked. The visit method must not modify the word.

Definition at line 214 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::isEmpty(), Sawyer::Container::Interval< T >::least(), processWord(), and Sawyer::Container::Interval< T >::size().

Referenced by add(), bitwiseAnd(), bitwiseOr(), bitwiseXor(), clear(), compare(), copy(), decrement(), increment(), invert(), leastSignificantClearBit(), leastSignificantDifference(), leastSignificantSetBit(), mostSignificantClearBit(), mostSignificantDifference(), mostSignificantSetBit(), nClear(), nSet(), set(), swap(), toBinary(), toHex(), and toOctal().

template<class Processor , class Word >
void Sawyer::Container::BitVectorSupport::traverse ( Processor &  processor,
Word *  words,
const BitRange range,
HighToLow   
)
template<class Processor , class Word1 , class Word2 >
void Sawyer::Container::BitVectorSupport::traverse2 ( Processor &  processor,
Word1 *  vec1,
const BitRange range1,
Word2 *  vec2,
const BitRange range2,
LowToHigh   
)
template<class Processor , class Word1 , class Word2 >
void Sawyer::Container::BitVectorSupport::traverse2 ( Processor &  processor,
Word1 *  vec1,
const BitRange range1,
Word2 *  vec2,
const BitRange range2,
HighToLow   
)
template<class Word >
bool Sawyer::Container::BitVectorSupport::get ( const Word *  words,
size_t  idx 
)

Return a single bit.

Returns the bit at the specified index.

Definition at line 385 of file BitVectorSupport.h.

Referenced by Sawyer::Container::BitVector::get().

template<class Word >
void Sawyer::Container::BitVectorSupport::clear ( Word *  words,
const BitRange where 
)

Clear some bits.

Clears all bits in the specified index range.

Definition at line 401 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::clear(), fromInteger(), setValue(), and signExtend().

template<class Word >
void Sawyer::Container::BitVectorSupport::set ( Word *  words,
const BitRange where 
)

Set some bits.

Sets all bits in the specified index range.

Definition at line 418 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::set(), and setValue().

template<class Word >
void Sawyer::Container::BitVectorSupport::setValue ( Word *  words,
const BitRange where,
bool  value 
)

Set or clear some bits.

Sets or clears all bits in the specified index range.

Definition at line 427 of file BitVectorSupport.h.

References clear(), and set().

Referenced by Sawyer::Container::BitVector::resize(), Sawyer::Container::BitVector::setValue(), shiftLeft(), shiftRight(), and signExtend().

template<class Word >
void Sawyer::Container::BitVectorSupport::copy ( const Word *  src,
const BitRange srcRange,
Word *  dst,
const BitRange dstRange 
)

Copy some bits.

Copies bits from src to dst according to the ranges srcRange and dstRange. The size of the two address ranges must be the same. The ranges may overlap, and the src and dst may be the same pointer.

Definition at line 449 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::copy(), fromInteger(), rotateRight(), shiftLeft(), shiftRight(), signExtend(), subtract(), and toInteger().

template<class Word >
void Sawyer::Container::BitVectorSupport::swap ( Word *  vec1,
const BitRange range1,
Word *  vec2,
const BitRange range2 
)

Swap some bits.

Swaps bits from part of one vector with bits from part of another (or the same). The size of the two address ranges must be equal and they may not overlap within a single vector.

Definition at line 471 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::isOverlapping(), and traverse().

Referenced by Sawyer::Container::BitVector::swap().

template<class Word >
Optional<size_t> Sawyer::Container::BitVectorSupport::leastSignificantSetBit ( const Word *  words,
const BitRange range 
)

Index of least significant set bit.

Returns the index of the least significant set bit within the specified range of bits. The return value is the absolute bit number in the entire vector. If none of the bits in the range are set then nothing is returned.

Definition at line 507 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::least(), and traverse().

Referenced by isAllClear(), and Sawyer::Container::BitVector::leastSignificantSetBit().

template<class Word >
Optional<size_t> Sawyer::Container::BitVectorSupport::leastSignificantClearBit ( const Word *  words,
const BitRange range 
)

Index of least significant zero bit.

Returns the index of the least significant clear bit within the specified range of bits. The return value is the absolute bit number in the entire vector. If none of the bits in the range are clear then nothing is returned.

Definition at line 539 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::least(), and traverse().

Referenced by isAllSet(), and Sawyer::Container::BitVector::leastSignificantClearBit().

template<class Word >
Optional<size_t> Sawyer::Container::BitVectorSupport::mostSignificantSetBit ( const Word *  words,
const BitRange range 
)

Index of most significant set bit.

Returns the index of the most significant set bit within the specified range of bits. The return value is the absolute bit number in the entire vector. If none of the bits in the range are set then nothing is returned.

Definition at line 572 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::least(), Sawyer::Container::Interval< T >::size(), and traverse().

Referenced by compareSigned(), and Sawyer::Container::BitVector::mostSignificantSetBit().

template<class Word >
Optional<size_t> Sawyer::Container::BitVectorSupport::mostSignificantClearBit ( const Word *  words,
const BitRange range 
)

Index of most significant clear bit.

Returns the index of the most significant zero bit within the specified range of bits. The return value is the absolute bit number in the entire vector. If none of the bits in the range are set then nothing is returned.

Definition at line 605 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::least(), Sawyer::Container::Interval< T >::size(), and traverse().

Referenced by Sawyer::Container::BitVector::mostSignificantClearBit().

template<class Word >
bool Sawyer::Container::BitVectorSupport::isAllSet ( const Word *  words,
const BitRange range 
)

True if all bits are set.

Returns true if the indicated range does not contain a clear bit; an empty range returns true.

Definition at line 617 of file BitVectorSupport.h.

References leastSignificantClearBit().

Referenced by Sawyer::Container::BitVector::isAllSet().

template<class Word >
bool Sawyer::Container::BitVectorSupport::isAllClear ( const Word *  words,
const BitRange range 
)

True if all bits are clear.

Returns true if the indicated range does not contain a set bit; an empty range returns true.

Definition at line 625 of file BitVectorSupport.h.

References leastSignificantSetBit().

Referenced by Sawyer::Container::BitVector::isAllClear(), and isEqualToZero().

template<class Word >
size_t Sawyer::Container::BitVectorSupport::nSet ( const Word *  words,
const BitRange range 
)

Number of set bits.

Returns the number of bits that are set in the specified range.

Definition at line 648 of file BitVectorSupport.h.

References traverse().

Referenced by compareSigned(), and Sawyer::Container::BitVector::nSet().

template<class Word >
size_t Sawyer::Container::BitVectorSupport::nClear ( const Word *  words,
const BitRange range 
)

Number of clear bits.

Returns the number of bits that are clear in the specified range.

Definition at line 673 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::nClear().

template<class Word >
Optional<size_t> Sawyer::Container::BitVectorSupport::leastSignificantDifference ( const Word *  vec1,
const BitRange range1,
const Word *  vec2,
const BitRange range2 
)

Find least significant different bits.

Finds the least significant bit of two sub-vectors where the value is different. The return value is the offset relative to the beginning of the sub-vectors where the first difference is found; it is not a bit index within the either vector-as-a-whole (unless the ranges start at zero). If no difference is found then nothing is returned.

Definition at line 705 of file BitVectorSupport.h.

References traverse().

Referenced by areEqual(), and Sawyer::Container::BitVector::leastSignificantDifference().

template<class Word >
Optional<size_t> Sawyer::Container::BitVectorSupport::mostSignificantDifference ( const Word *  vec1,
const BitRange range1,
const Word *  vec2,
const BitRange range2 
)

Find most significant different bits.

Finds the most significant bit of two sub-vectors where the value is different. The return value is the offset relative to the beginning of the sub-vectors where the first difference is found; it is not a bit index within the either vector-as-a-whole (unless the ranges start at zero). If no difference is found then nothing is returned.

Definition at line 739 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::size(), and traverse().

Referenced by compareSigned(), and Sawyer::Container::BitVector::mostSignificantDifference().

template<class Word >
bool Sawyer::Container::BitVectorSupport::areEqual ( const Word *  vec1,
const BitRange range1,
const Word *  vec2,
const BitRange range2 
)

Equality predicate.

Returns true if two vectors are equal. An empty vector is equal to another empty vector, but not equal to any non-empty vector. See also, compare, which treats vectors numerically and can be used in cases when they are different sizes.

Definition at line 751 of file BitVectorSupport.h.

References leastSignificantDifference(), and Sawyer::Container::Interval< T >::size().

template<class Word >
void Sawyer::Container::BitVectorSupport::shiftLeft ( Word *  words,
const BitRange range,
size_t  nShift,
bool  newBits = 0 
)

Shift bits left.

Shifts the bits in the specified range left by nShift places, discarding the high-order bits and introducing low-order bits with the value newBits.

Definition at line 766 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), copy(), Sawyer::Container::Interval< T >::least(), setValue(), and Sawyer::Container::Interval< T >::size().

Referenced by Sawyer::Container::BitVector::shiftLeft().

template<class Word >
void Sawyer::Container::BitVectorSupport::shiftRight ( Word *  words,
const BitRange range,
size_t  nShift,
bool  newBits = 0 
)

Shift bits right.

Shifts the bits in the specified range right by nShift places, discarding the low-order bits and introducing high-order bits with the value newBits.

Definition at line 784 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), copy(), Sawyer::Container::Interval< T >::least(), setValue(), and Sawyer::Container::Interval< T >::size().

Referenced by rotateRight(), Sawyer::Container::BitVector::shiftRight(), and shiftRightArithmetic().

template<class Word >
void Sawyer::Container::BitVectorSupport::shiftRightArithmetic ( Word *  words,
const BitRange range,
size_t  nShift 
)

Shift bits right arithmetically.

Shifts the bits in the specified range right by nShift places, discarding the low-order bits and introducing high-order bits with the same value as the original high-order bit within the range.

Definition at line 802 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::greatest(), Sawyer::Container::Interval< T >::isEmpty(), and shiftRight().

Referenced by Sawyer::Container::BitVector::shiftRightArithmetic().

template<class Word >
void Sawyer::Container::BitVectorSupport::rotateRight ( Word *  words,
const BitRange range,
size_t  nShift 
)

Rotate bits to the right.

Rotates the bits of the specified range to the right by nShift places, introducing high-order bits that are the same as the low-order bits that were removed.

Definition at line 814 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), copy(), Sawyer::Container::Interval< T >::isEmpty(), Sawyer::Container::Interval< T >::least(), shiftRight(), and Sawyer::Container::Interval< T >::size().

Referenced by rotateLeft(), and Sawyer::Container::BitVector::rotateRight().

template<class Word >
void Sawyer::Container::BitVectorSupport::rotateLeft ( Word *  words,
const BitRange range,
size_t  nShift 
)

Rotate bits to the left.

Rotates the bits of the specified range to the left by nShift places, introducing low-order bits that are the same as the high-order bits that were removed.

Definition at line 838 of file BitVectorSupport.h.

References Sawyer::Container::Interval< T >::isEmpty(), rotateRight(), and Sawyer::Container::Interval< T >::size().

Referenced by Sawyer::Container::BitVector::rotateLeft().

template<class Word >
void Sawyer::Container::BitVectorSupport::invert ( Word *  words,
const BitRange range 
)

Invert bits.

Inverts all bits in the specified range.

Definition at line 862 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::invert(), negate(), and subtract().

template<class Word >
void Sawyer::Container::BitVectorSupport::bitwiseAnd ( const Word *  vec1,
const BitRange range1,
Word *  vec2,
const BitRange range2 
)

Bit-wise AND.

Computes the bitwise AND of equal-size sub-vectors vec1 and vec2 and stores the result in vec2. The sub-vectors may overlap.

Definition at line 880 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::bitwiseAnd().

template<class Word >
void Sawyer::Container::BitVectorSupport::bitwiseOr ( const Word *  vec1,
const BitRange range1,
Word *  vec2,
const BitRange range2 
)

Bit-wise OR.

Computes the bitwise OR of equal-size sub-vectors vec1 and vec2 and stores the result in vec2. The sub-vectors may overlap.

Definition at line 898 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::bitwiseOr().

template<class Word >
void Sawyer::Container::BitVectorSupport::bitwiseXor ( const Word *  vec1,
const BitRange range1,
Word *  vec2,
const BitRange range2 
)

Bit-wise XOR.

Computes the bitwise exclusive-OR of equal-size sub-vectors vec1 and vec2 and stores the result in vec2. The sub-vectors may overlap.

Definition at line 916 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::bitwiseXor().

template<class Word >
void Sawyer::Container::BitVectorSupport::fromInteger ( Word *  words,
const BitRange range,
boost::uint64_t  value 
)

Assign an unsigned value to a bit range.

Zero extends or truncates value to the same width as range and copies it into the bit vector.

Definition at line 930 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), clear(), copy(), Sawyer::Container::Interval< T >::isEmpty(), Sawyer::Container::Interval< T >::least(), and Sawyer::Container::Interval< T >::size().

Referenced by fromDecimal(), and Sawyer::Container::BitVector::fromInteger().

template<class Word >
boost::uint64_t Sawyer::Container::BitVectorSupport::toInteger ( const Word *  words,
const BitRange range 
)

Convert a bit vector to an integer.

Converts the specified range to an unsigned 64-bit value and returns that value. Returns zero if the range is empty. If the range is wider than 64 bits then all of its high-order bits are ignored and only the lowest 64 bits are used.

Definition at line 956 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), copy(), Sawyer::Container::Interval< T >::least(), and Sawyer::Container::Interval< T >::size().

Referenced by Sawyer::Container::BitVector::toInteger().

template<class Word >
boost::uint64_t Sawyer::Container::BitVectorSupport::toInteger ( const Word *  words,
size_t  nbits 
)

Convert a small bit vector to an integer.

Faster version of toInteger for instances where the range offset is zero, and the size is not greater than 64 bits.

Definition at line 978 of file BitVectorSupport.h.

template<class Word >
bool Sawyer::Container::BitVectorSupport::increment ( Word *  vec1,
const BitRange range1 
)

Increment.

Interprets range of vec1 as an integer and increments the value by one. The return value is the carry-out bit.

Definition at line 1009 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::increment(), and negate().

template<class Word >
bool Sawyer::Container::BitVectorSupport::decrement ( Word *  vec1,
const BitRange range1 
)

Decrement.

Interprets range of vec1 as an integer and decrements the value by one. Returns true if the original value was zero or empty.

Definition at line 1036 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::decrement().

template<class Word >
void Sawyer::Container::BitVectorSupport::negate ( Word *  vec1,
const BitRange range 
)

Negate bits as an integer.

Interprets range of vec1 as a two's complement integer and negates its value.

Definition at line 1046 of file BitVectorSupport.h.

References increment(), and invert().

Referenced by Sawyer::Container::BitVector::negate().

template<class Word >
bool Sawyer::Container::BitVectorSupport::add ( const Word *  vec1,
const BitRange range1,
Word *  vec2,
const BitRange range2,
bool  carryIn = false 
)

Add bits.

Treats two sub-vectors as unsigned values and add them together, storing the result in the second vector. Both ranges must be the same size, and the sub-vectors are permitted to overlap. The return value is the carry-out bit.

Definition at line 1077 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::add(), and subtract().

template<class Word >
bool Sawyer::Container::BitVectorSupport::subtract ( const Word *  vec1,
const BitRange range1,
Word *  vec2,
const BitRange range2 
)

Subtract bits.

Treats two sub-vectors as unsigned values and subtracts vec1 from vec2 and stores the result in vec2. Both ranges must be the same size, and the sub-vectors are permitted to overlap. The return value is false only when an overflow occurs (i.e., vec2 is unsigned-greater-than vec1). If the vectors are interpreted as 2's complement signed integers then an overflow is indicated whan both operands ahve the same sign and the result has a different sign.

Definition at line 1090 of file BitVectorSupport.h.

References add(), Sawyer::Container::Interval< size_t >::baseSize(), copy(), invert(), and Sawyer::Container::Interval< T >::size().

Referenced by Sawyer::Container::BitVector::subtract().

template<class Word >
bool Sawyer::Container::BitVectorSupport::signExtend ( const Word *  vec1,
const BitRange range1,
Word *  vec2,
const BitRange range2 
)

Sign extend.

Performs sign extension while copying bits from range1 to range2, which may overlap. If range1 is empty then range2 is cleared. If range2 is smaller than range1 then the not all bits are copied (high-order bits in range1 are omitted). If range1 is non-empty and range2 is empty then nothing is copied. The return value is the new high-order (sign) bit of range2, or false if range2 is empty.

Definition at line 1106 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), clear(), copy(), Sawyer::Container::Interval< T >::greatest(), Sawyer::Container::Interval< size_t >::hull(), Sawyer::Container::Interval< T >::isEmpty(), Sawyer::Container::Interval< T >::least(), setValue(), and Sawyer::Container::Interval< T >::size().

Referenced by Sawyer::Container::BitVector::signExtend().

template<class Word >
bool Sawyer::Container::BitVectorSupport::isEqualToZero ( const Word *  vec1,
const BitRange range1 
)

Compares with zero.

Returns true if the vector is equal to zero.

Definition at line 1134 of file BitVectorSupport.h.

References isAllClear().

Referenced by compare(), and Sawyer::Container::BitVector::isEqualToZero().

template<class Word >
int Sawyer::Container::BitVectorSupport::compare ( const Word *  vec1,
const BitRange range1,
const Word *  vec2,
const BitRange range2 
)

Unsigned comparison.

Interprests two sub-vectors as unsigned integers and returns an integer whose sign indicates the relationship between those two integers. Returns negative if vec1 is less than vec2; returns zero if vec1 is equal to vec2; returns positive if vec1 is greater than vec2. The ranges need not be the same size–the smaller of the two ranges will act as if it were zero padded on its most-significant side. Two empty vectors are interpreted as zero.

Definition at line 1165 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), Sawyer::Container::Interval< T >::greatest(), Sawyer::Container::Interval< size_t >::hull(), Sawyer::Container::Interval< T >::isEmpty(), isEqualToZero(), Sawyer::Container::Interval< T >::least(), Sawyer::Container::Interval< T >::size(), and traverse().

Referenced by Sawyer::Container::BitVector::compare(), and compareSigned().

template<class Word >
int Sawyer::Container::BitVectorSupport::compareSigned ( const Word *  vec1,
const BitRange range1,
const Word *  vec2,
const BitRange range2 
)

Signed comparison.

Interprests two sub-vectors as 2's complement signed integers and returns an integer whose sign indicates the relationship between those two integers. Returns negative if vec1 is less than vec2; returns zero if vec1 is equal to vec2; returns positive if vec1 is greater than vec2. The ranges need not be the same size–the smaller of the two ranges will act as if it were sign-extended to the same size as the other. Empty vectors are interpreted as zero.

Definition at line 1200 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), compare(), Sawyer::Container::Interval< T >::greatest(), Sawyer::Container::Interval< size_t >::hull(), Sawyer::Container::Interval< T >::isEmpty(), Sawyer::Container::Interval< T >::least(), mostSignificantDifference(), mostSignificantSetBit(), nSet(), and Sawyer::Container::Interval< T >::size().

Referenced by Sawyer::Container::BitVector::compareSigned().

template<class Word >
std::string Sawyer::Container::BitVectorSupport::toHex ( const Word *  vec,
const BitRange range 
)

Hexadecimal representation.

Returns a string which is the hexadecimal representation of the bits in the specified range. No prefix or suffix is added (i.e., no leading "0x" or trailing "h"). The number of digits in the return value is the minimum required to explicitly represent the value, including leading zeros; an empty range will return an empty string. The returned string is lower case.

Definition at line 1308 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::toHex().

template<class Word >
std::string Sawyer::Container::BitVectorSupport::toOctal ( const Word *  vec,
const BitRange range 
)

Octal representation.

Returns a string which is the octal representation of the bits in the specified range. No prefix or suffix is added (i.e., no leading "0" or trailing "o"). The number of digits in the return value is the minimum required to explicitly represent the value, including leading zeros. An empty range will return an empty string.

Definition at line 1320 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::toOctal().

template<class Word >
std::string Sawyer::Container::BitVectorSupport::toBinary ( const Word *  vec,
const BitRange range 
)

Binary representation.

Returns a string which is the binary representation of the bits in the specified range. No prefix or suffix is added. The number of digits in the return value is the minimum required to explicitly represent the value, including leading zeros. An empty range will return an empty string.

Definition at line 1332 of file BitVectorSupport.h.

References traverse().

Referenced by Sawyer::Container::BitVector::toBinary().

template<class Word >
void Sawyer::Container::BitVectorSupport::fromDecimal ( Word *  vec,
const BitRange range,
const std::string &  input 
)

Obtain bits from a decimal representation.

The input string must contain only valid decimal digits '0' through '9' or the underscore character (to make long strings more readable), or else an std::runtime_error is thrown. If the number of supplied digits is larger than what is required to initialize the specified sub-vector, then extra data is discarded. On the other hand, if the length of the string is insufficient to initialize the entire sub-vector then the high order bits of the sub-vector are cleared.

Definition at line 1399 of file BitVectorSupport.h.

References fromInteger().

Referenced by Sawyer::Container::BitVector::fromDecimal().

template<class Word >
void Sawyer::Container::BitVectorSupport::fromHex ( Word *  vec,
const BitRange range,
const std::string &  input 
)

Obtain bits from a hexadecimal representation.

The input string must contain only valid hexadecimal digits '0' through '9', 'a' through 'f', and 'A' through 'F', or the underscore character (to make long strings more readable), or else an std::runtime_error is thrown. If the number of supplied digits is larger than what is required to initialize the specified sub-vector, then extra data is discarded. On the other hand, if the length of the string is insufficient to initialize the entire sub-vector then the high order bits of the sub-vector are cleared.

Definition at line 1422 of file BitVectorSupport.h.

Referenced by Sawyer::Container::BitVector::fromHex().

template<class Word >
void Sawyer::Container::BitVectorSupport::fromOctal ( Word *  vec,
const BitRange range,
const std::string &  input 
)

Obtain bits from an octal representation.

The input string must contain only valid octal digits '0' through '7' or the underscore (to make long strings more readable), or else an std::runtime_error is thrown. If the number of supplied digits is larger than what is required to initialize the specified sub-vector, then extra data is discarded. On the other hand, if the length of the string is insufficient to initialize the entire sub-vector then the high order bits of the sub-vector are cleared.

Definition at line 1433 of file BitVectorSupport.h.

Referenced by Sawyer::Container::BitVector::fromOctal().

template<class Word >
void Sawyer::Container::BitVectorSupport::fromBinary ( Word *  vec,
const BitRange range,
const std::string &  input 
)

Obtain bits from a binary representation.

The input string must contain only valid binary digits '0' and '1' or the underscore (to make long strings more readable), or else an std::runtime_error is thrown. If the number of supplied digits is larger than what is required to initialize the specified sub-vector, then extra data is discarded. On the other hand, if the length of the string is insufficient to initialize the entire sub-vector then the high order bits of the sub-vector are cleared.

Definition at line 1444 of file BitVectorSupport.h.

Referenced by Sawyer::Container::BitVector::fromBinary().