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	EqualTo

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.

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.

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.

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.

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 >
bool	equalTo (const Word vec1, const BitRange &range1, const Word vec2, const BitRange &range2)
	Compare bits for equality. 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 >
boost::int64_t	toSignedInteger (const Word *words, const BitRange &range)
	Convert a bit vector to a signed integer. More...

template<class Word >
boost::int64_t	toSignedInteger (const Word *words, size_t nBits)
	Convert a small bit vector to a signed 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 >
void	multiply10 (Word *vec, const BitRange &range)
	Multiply by 10. 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...

Function Documentation

◆ wordIndex()

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.

◆ bitIndex()

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.

◆ bitMask()

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.

◆ processWord() [1/5]

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().

Here is the caller graph for this function:

◆ processWord() [2/5]

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.

◆ processWord() [3/5]

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.

◆ processWord() [4/5]

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.

◆ processWord() [5/5]

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.

◆ traverse()

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(), equalTo(), increment(), invert(), leastSignificantClearBit(), leastSignificantDifference(), leastSignificantSetBit(), mostSignificantClearBit(), mostSignificantDifference(), mostSignificantSetBit(), nClear(), nSet(), set(), swap(), toBinary(), toHex(), and toOctal().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get()

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 384 of file BitVectorSupport.h.

Referenced by compareSigned(), Sawyer::Container::BitVector::get(), shiftRightArithmetic(), and signExtend().

Here is the caller graph for this function:

◆ clear()

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 400 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set()

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 417 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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 426 of file BitVectorSupport.h.

References clear(), and set().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ copy()

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 448 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ swap()

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 470 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ equalTo()

template<class Word >

bool Sawyer::Container::BitVectorSupport::equalTo	(	const Word *	vec1,
		const BitRange &	range1,
		const Word *	vec2,
		const BitRange &	range2
	)

Compare bits for equality.

Returns true if and only if the ranges are the same size and contain the same bit values in the same order.

Definition at line 497 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ leastSignificantSetBit()

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 534 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ leastSignificantClearBit()

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 566 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mostSignificantSetBit()

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 599 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().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mostSignificantClearBit()

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 632 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isAllSet()

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 644 of file BitVectorSupport.h.

References leastSignificantClearBit().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isAllClear()

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 652 of file BitVectorSupport.h.

References leastSignificantSetBit().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nSet()

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 675 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ nClear()

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 700 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ leastSignificantDifference()

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 732 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mostSignificantDifference()

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 766 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ areEqual()

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 778 of file BitVectorSupport.h.

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

Here is the call graph for this function:

◆ shiftLeft()

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 793 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 multiply10(), and Sawyer::Container::BitVector::shiftLeft().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ shiftRight()

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 811 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().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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 829 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rotateRight()

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 841 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().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rotateLeft()

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 865 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ invert()

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 889 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitwiseAnd()

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 907 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitwiseOr()

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 925 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ bitwiseXor()

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 943 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fromInteger()

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 957 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().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toInteger() [1/2]

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 983 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(), and Sawyer::Container::BitVector::toSignedInteger().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toInteger() [2/2]

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 1004 of file BitVectorSupport.h.

◆ toSignedInteger() [1/2]

template<class Word >

boost::int64_t Sawyer::Container::BitVectorSupport::toSignedInteger	(	const Word *	words,
		const BitRange &	range
	)

Convert a bit vector to a signed integer.

Converts the specified range to a signed 64-bit value and returns it. If the size of the range is one then the return value is either zero or one; if the size of the range is less than or equal to 64 bits then the bits are sign-extended to 64 bits and returned; otherwise when the size of the range is larger than 64 bits the low-order 64 bits are returned.

Definition at line 1021 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toSignedInteger() [2/2]

template<class Word >

boost::int64_t Sawyer::Container::BitVectorSupport::toSignedInteger	(	const Word *	words,
		size_t	nBits
	)

Convert a small bit vector to a signed integer.

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

Definition at line 1037 of file BitVectorSupport.h.

◆ increment()

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 1067 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ decrement()

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 1094 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ negate()

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 1104 of file BitVectorSupport.h.

References increment(), and invert().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ add()

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 1135 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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 1148 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().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ signExtend()

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 1164 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), clear(), copy(), get(), 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().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ multiply10()

template<class Word >

void Sawyer::Container::BitVectorSupport::multiply10	(	Word *	vec,
		const BitRange &	range
	)

Multiply by 10.

Treats the specified range of the vector as an unsigned integer and multiplies it by 10.

Definition at line 1187 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ isEqualToZero()

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 1206 of file BitVectorSupport.h.

References isAllClear().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compare()

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 1237 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().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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 1272 of file BitVectorSupport.h.

References Sawyer::Container::Interval< size_t >::baseSize(), compare(), get(), 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().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toHex()

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 1380 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toOctal()

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 1392 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toBinary()

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 1404 of file BitVectorSupport.h.

References traverse().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fromDecimal()

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 1468 of file BitVectorSupport.h.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fromHex()

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 1510 of file BitVectorSupport.h.

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

Here is the caller graph for this function:

◆ fromOctal()

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 1521 of file BitVectorSupport.h.

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

Here is the caller graph for this function:

◆ fromBinary()

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 1532 of file BitVectorSupport.h.

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

Here is the caller graph for this function:

Description

Classes

Typedefs

Functions

Function Documentation

◆ wordIndex()

◆ bitIndex()

◆ bitMask()

◆ processWord() [1/5]

◆ processWord() [2/5]

◆ processWord() [3/5]

◆ processWord() [4/5]

◆ processWord() [5/5]

◆ traverse()

◆ get()

◆ clear()

◆ set()

◆ setValue()

◆ copy()

◆ swap()

◆ equalTo()

◆ leastSignificantSetBit()

◆ leastSignificantClearBit()

◆ mostSignificantSetBit()

◆ mostSignificantClearBit()

◆ isAllSet()

◆ isAllClear()

◆ nSet()

◆ nClear()

◆ leastSignificantDifference()

◆ mostSignificantDifference()

◆ areEqual()

◆ shiftLeft()

◆ shiftRight()

◆ shiftRightArithmetic()

◆ rotateRight()

◆ rotateLeft()

◆ invert()

◆ bitwiseAnd()

◆ bitwiseOr()

◆ bitwiseXor()

◆ fromInteger()

◆ toInteger() [1/2]

◆ toInteger() [2/2]

◆ toSignedInteger() [1/2]

◆ toSignedInteger() [2/2]

◆ increment()

◆ decrement()

◆ negate()

◆ add()

◆ subtract()

◆ signExtend()

◆ multiply10()

◆ isEqualToZero()

◆ compare()

◆ compareSigned()

◆ toHex()

◆ toOctal()

◆ toBinary()

◆ fromDecimal()

◆ fromHex()

◆ fromOctal()

◆ fromBinary()