ROSE  0.9.10.44
Public Member Functions | List of all members
BitPattern< T > Class Template Reference

Description

template<typename T>
class BitPattern< T >

Describes a pattern of bits in a finite number of words.

A BitPattern is a set of one or more alternative values for certain significant bits in a finite sequence of words. The words have type T and are numbered starting at zero. The bits are numbered independently in each word so that the least significant bit of a word is bit number zero.

A BitPattern matches a sequence of value words if, for each pattern word that has significant bits, the value of those bits matches the corresponding bits in the value words. A BitPattern that has no significant bits matches all sequences of value words.

A BitPattern may have multiple sets of pattern words that serve as alternative values to match. A BitPattern will match a sequence of value words if any of the pattern word sets match. All pattern word sets use the same significant bits.

Here are examples of creating a BitPattern for a single 32-bit word where the high order byte must be the value 0x33 and the low-order byte must be the value 0x66.

BitPattern<uint32_t> bp1(0xff0000ff, 0x33000066, 0);
BitPattern<uint32_t> bp2 = BitPattern<uint32_t>(0, 8, 0x66, 0) & BitPattern<uint32_t>(24, 32, 0x33, 0);

The following example uses the same pattern, but treats the input as four separate 8-bit values:

BitPattern<uint8_t> bp3 = BitPattern<uint8_t>(0xff, 0x66, 0) & BitPattern<uint32_t>(0xff, 0x33, 3);

Matching these patterns against actual data proceeds like follows. Since the 32-bit word pattern has only one word, we can use the more convenient match_word() method. On the other hand, we need to supply four words at a time for the 8-bit word pattern.

uint32_t w32 = ...;
bool m1 = bp1.matches_word(w32);
std::vector<uint8_t> w8a = ...;
bool m2 = bp3.matches(w8a);
uint8_t w8b[4] = {...};
bool m3 = bp3.matches(w8b, 4);

Definition at line 51 of file BitPattern.h.

#include <BitPattern.h>

Inheritance diagram for BitPattern< T >:
Inheritance graph
[legend]

Public Member Functions

 BitPattern ()
 Creates a new, empty bit pattern. More...
 
 BitPattern (T msk, T pat, size_t wordnum)
 Creates a new bit pattern for a single word using a mask and value. More...
 
 BitPattern (size_t lo_bit, size_t hi_bit, T pat, size_t wordnum)
 Create a new bit pattern for a single word using bit offsets. More...
 
bool is_consistent () const
 Verify internal consistency. More...
 
size_t nsignificant () const
 Returns the number of significant bits. More...
 
size_t nwords () const
 Returns the number of words in the pattern. More...
 
size_t width () const
 Returns the size of the pattern in bits. More...
 
mask (size_t wordnum)
 Returns the mask for the specified word. More...
 
std::pair< T, T > invariants (T msk, size_t wordnum)
 Returns invariant bits. More...
 
size_t nalternatives () const
 Returns the number of alternatives. More...
 
conflict (T msk, T pat, size_t wordnum, size_t altnum) const
 Determines if the specified bits conflict with a particular pattern alternative. More...
 
conflict (T msk, T pat, size_t wordnum) const
 Determines if the specified significant bits conflict with any of the existing pattern alternatives. More...
 
void check_insertion (T msk, T pat, size_t wordnum) const
 Check that a pattern insertion does not conflict with an existing pattern. More...
 
bool any_same (const BitPattern &other, std::pair< size_t, size_t > *alternatives=NULL) const
 Determines whether two patterns can match the same input. More...
 
BitPatterninsert (T msk, T pat, size_t wordnum=0)
 Creates a new pattern by adding significant bits to all alternatives of a pattern. More...
 
BitPatternbits (size_t lo_bit, size_t hi_bit, T value, size_t wordnum)
 Adds significant bits to all alternatives of a pattern. More...
 
BitPattern shift_left (size_t nbits) const
 Return a new BitPattern with the pattern bits shifted left by the indicated amount. More...
 
BitPatternconjunction (const BitPattern &other)
 Combines this BitPattern with another by forming their conjunction. More...
 
BitPatterndisjunction (const BitPattern &other)
 Combines this BitPattern with another by forming their disjunction. More...
 
bool matches_word (T value, size_t wordnum) const
 Returns true if one word of this pattern matches the specified value. More...
 
void print (std::ostream &o, size_t altnum, bool with_mask=true) const
 Print one pattern alternative. More...
 
void print (std::ostream &o) const
 Print all alternatives of the pattern. More...
 
BitPattern operator& (const BitPattern &other) const
 Creates a new BitPattern that is the conjunction of two bit patterns. More...
 
BitPatternoperator&= (const BitPattern &other)
 Creates a new BitPattern that is the conjunction of two bit patterns. More...
 
BitPattern operator| (const BitPattern &other) const
 Creates a new BitPattern that is the inclusive disjunction of two bit patterns. More...
 
BitPatternoperator|= (const BitPattern &other)
 Creates a new BitPattern that is the inclusive disjunction of two bit patterns. More...
 
bool matches (const std::vector< T > value_words) const
 Returns true if this pattern matches the specified values.
 
bool matches (const T *value_words, size_t sz) const
 Returns true if this pattern matches the specified values.
 

Constructor & Destructor Documentation

template<typename T>
BitPattern< T >::BitPattern ( )
inline

Creates a new, empty bit pattern.

An empty pattern matches all values.

Definition at line 59 of file BitPattern.h.

template<typename T>
BitPattern< T >::BitPattern ( msk,
pat,
size_t  wordnum 
)
inline

Creates a new bit pattern for a single word using a mask and value.

The pattern is bit-wise AND'd with the mask, and none of its other bits should be set.

Definition at line 63 of file BitPattern.h.

template<typename T>
BitPattern< T >::BitPattern ( size_t  lo_bit,
size_t  hi_bit,
pat,
size_t  wordnum 
)
inline

Create a new bit pattern for a single word using bit offsets.

The pattern is left shifted into the specified bits, and none of its higher order bits should be set. The range of significant bits is from lo_bit through hi_bit, inclusive.

Definition at line 70 of file BitPattern.h.

Member Function Documentation

template<typename T>
bool BitPattern< T >::is_consistent ( ) const
inline

Verify internal consistency.

This is asserted at the beginning and end of methods that modify a bit pattern.

Definition at line 75 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::conjunction(), BitPattern< uint16_t >::disjunction(), BitPattern< uint16_t >::insert(), and BitPattern< uint16_t >::shift_left().

template<typename T>
size_t BitPattern< T >::nsignificant ( ) const
inline

Returns the number of significant bits.

Returns zero if the pattern is empty.

Definition at line 90 of file BitPattern.h.

template<typename T>
size_t BitPattern< T >::nwords ( ) const
inline

Returns the number of words in the pattern.

Although the final word of the pattern will have at least one significant bit, the previous pattern words might not be significant.

Definition at line 99 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::any_same(), BitPattern< uint16_t >::disjunction(), BitPattern< uint16_t >::matches(), BitPattern< uint16_t >::matches_word(), and BitPattern< uint16_t >::print().

template<typename T>
size_t BitPattern< T >::width ( ) const
inline

Returns the size of the pattern in bits.

If the pattern has no significant bits, then zero is returned. Otherwise the return value is the one-origin position of the most significant bit of the pattern mask.

Definition at line 105 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::shift_left().

template<typename T>
T BitPattern< T >::mask ( size_t  wordnum)
inline

Returns the mask for the specified word.

The mask determines which bits the pattern cares about.

Definition at line 113 of file BitPattern.h.

template<typename T>
std::pair<T, T> BitPattern< T >::invariants ( msk,
size_t  wordnum 
)
inline

Returns invariant bits.

Given a set of of bits and a word number, this method returns values for bits that must be set or cleared and a mask indicating which bits are invariant. For instance, if a pattern's alternatives all require that bits at positions 24 (inclusive) to 32 (exclusive) have the value 0xbe, don't care about bits at positions 8 to 24, and each alternative is different in bits 0-8, then the return value wil be the value 0xbe000000 (first member of the returned pair) and mask 0xff000000 (second member of the pair).

Definition at line 124 of file BitPattern.h.

template<typename T>
size_t BitPattern< T >::nalternatives ( ) const
inline
template<typename T>
T BitPattern< T >::conflict ( msk,
pat,
size_t  wordnum,
size_t  altnum 
) const
inline

Determines if the specified bits conflict with a particular pattern alternative.

If the new pattern (the arguments) conflicts with an existing pattern, then a mask describing the bits in conflict is returned. This function returns zero if there is no conflict with the specified alternative.

Definition at line 142 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::check_insertion(), and BitPattern< uint16_t >::conflict().

template<typename T>
T BitPattern< T >::conflict ( msk,
pat,
size_t  wordnum 
) const
inline

Determines if the specified significant bits conflict with any of the existing pattern alternatives.

If the new pattern (the arguments) conflicts with an existing pattern, then a mask describing the bits in conflict is returned. If there is no conflict, then this function returns zero.

Definition at line 156 of file BitPattern.h.

template<typename T>
void BitPattern< T >::check_insertion ( msk,
pat,
size_t  wordnum 
) const
inline

Check that a pattern insertion does not conflict with an existing pattern.

If a conflict is present, print information about the conflict to stderr and abort.

Definition at line 168 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::conjunction(), and BitPattern< uint16_t >::insert().

template<typename T>
bool BitPattern< T >::any_same ( const BitPattern< T > &  other,
std::pair< size_t, size_t > *  alternatives = NULL 
) const
inline

Determines whether two patterns can match the same input.

Returns true if this pattern can match at least one of the same input values as the other BitPattern.

Definition at line 183 of file BitPattern.h.

template<typename T>
BitPattern& BitPattern< T >::insert ( msk,
pat,
size_t  wordnum = 0 
)
inline

Creates a new pattern by adding significant bits to all alternatives of a pattern.

The msk and pat are a mask and bits for the specified word.

Definition at line 207 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::BitPattern(), and BitPattern< uint16_t >::bits().

template<typename T>
BitPattern& BitPattern< T >::bits ( size_t  lo_bit,
size_t  hi_bit,
value,
size_t  wordnum 
)
inline

Adds significant bits to all alternatives of a pattern.

The pattern is over the inclusive range of bits for the specified word. E.g., when called as "bits(8,11,0xc,1)", the pattern will match where bits 8 and 9 of word 1 are clear and bits 10 and 11 of word 1 are set.

Definition at line 234 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::BitPattern().

template<typename T>
BitPattern BitPattern< T >::shift_left ( size_t  nbits) const
inline

Return a new BitPattern with the pattern bits shifted left by the indicated amount.

Definition at line 241 of file BitPattern.h.

template<typename T>
BitPattern& BitPattern< T >::conjunction ( const BitPattern< T > &  other)
inline

Combines this BitPattern with another by forming their conjunction.

After this operation, this BitPattern will match values where both original patterns matched the value. The two original bit patterns need not have the same mask; in fact, it's most useful when their masks don't overlap. Either (or both) original patterns can have multiple alternatives; the number of alternatives in the result will be on the order of the product of the number of alternatives in the originals.

Definition at line 286 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::operator&(), and BitPattern< uint16_t >::operator&=().

template<typename T>
BitPattern& BitPattern< T >::disjunction ( const BitPattern< T > &  other)
inline

Combines this BitPattern with another by forming their disjunction.

After the operation, this BitPattern will match values where either of the original patterns matched. The two original bit patterns (and thus the result) must have the same set of significant bits.

Definition at line 340 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::operator|(), and BitPattern< uint16_t >::operator|=().

template<typename T>
BitPattern BitPattern< T >::operator& ( const BitPattern< T > &  other) const
inline

Creates a new BitPattern that is the conjunction of two bit patterns.

The new pattern matches wherever both of the original patterns matched.

Definition at line 370 of file BitPattern.h.

template<typename T>
BitPattern& BitPattern< T >::operator&= ( const BitPattern< T > &  other)
inline

Creates a new BitPattern that is the conjunction of two bit patterns.

The new pattern matches wherever both of the original patterns matched.

Definition at line 374 of file BitPattern.h.

template<typename T>
BitPattern BitPattern< T >::operator| ( const BitPattern< T > &  other) const
inline

Creates a new BitPattern that is the inclusive disjunction of two bit patterns.

The new pattern matches wherever either of the original patterns matched.

Definition at line 382 of file BitPattern.h.

template<typename T>
BitPattern& BitPattern< T >::operator|= ( const BitPattern< T > &  other)
inline

Creates a new BitPattern that is the inclusive disjunction of two bit patterns.

The new pattern matches wherever either of the original patterns matched.

Definition at line 386 of file BitPattern.h.

template<typename T>
bool BitPattern< T >::matches_word ( value,
size_t  wordnum 
) const
inline

Returns true if one word of this pattern matches the specified value.

Definition at line 416 of file BitPattern.h.

template<typename T>
void BitPattern< T >::print ( std::ostream &  o,
size_t  altnum,
bool  with_mask = true 
) const
inline

Print one pattern alternative.

Definition at line 427 of file BitPattern.h.

Referenced by BitPattern< uint16_t >::print().

template<typename T>
void BitPattern< T >::print ( std::ostream &  o) const
inline

Print all alternatives of the pattern.

Definition at line 439 of file BitPattern.h.


The documentation for this class was generated from the following file: