ROSE  0.9.9.109
BitPattern.h
1 #ifndef ROSE_BitPattern_H
2 #define ROSE_BitPattern_H
3 
4 #include "integerOps.h"
5 #include "StringUtility.h"
6 
7 #include <iostream>
8 #include <vector>
9 
50 template<typename T>
51 class BitPattern {
52  typedef std::vector<T> Words;
53  typedef std::vector<Words> Alternatives;
54  Words mask_; // significant bits
55  Alternatives patterns_; // set of alternative patterns; each pattern has the same size as the mask
56 
57 public:
60 
63  BitPattern(T msk, T pat, size_t wordnum) {
64  insert(msk, pat, wordnum);
65  }
66 
70  BitPattern(size_t lo_bit, size_t hi_bit, T pat, size_t wordnum) {
71  bits(lo_bit, hi_bit, pat, wordnum);
72  }
73 
75  bool is_consistent() const {
76  for (size_t i=0; i<patterns_.size(); ++i) {
77  if (patterns_[i].size()!=mask_.size()) {
78  std::cerr <<"BitPattern::is_consistent failed\n"
79  <<" mask_.size() = " <<mask_.size() <<"\n"
80  <<" patterns_[" <<i <<"].size() = " <<patterns_[i].size() <<"\n"
81  <<" these two vectors should have been the same size\n";
82  std::cerr <<" this = " <<*this <<"\n"; // printing might fail
83  return false;
84  }
85  }
86  return true;
87  }
88 
90  size_t nsignificant() const {
91  size_t retval = 0;
92  for (size_t i=0; i<mask_.size(); ++i)
93  retval += IntegerOps::countSet(mask_[i]);
94  return retval;
95  }
96 
99  size_t nwords() const {
100  return mask_.size();
101  }
102 
105  size_t width() const {
106  if (0==mask_.size())
107  return 0;
108  assert(mask_.back()!=0);
109  return 8*sizeof(T)*(mask_.size()-1) + IntegerOps::msb_set(mask_.back()).get() + 1;
110  }
111 
113  T mask(size_t wordnum) {
114  if (wordnum >= mask_.size())
115  return 0;
116  return mask_[wordnum];
117  }
118 
124  std::pair<T, T> invariants(T msk, size_t wordnum) {
125  if (msk==0 || wordnum>mask_.size() || patterns_.empty())
126  return std::pair<T, T>(0, 0);
127  T retmsk = msk & mask_[wordnum];
128  T retpat = retmsk & patterns_[0][wordnum];
129  for (size_t i=1; i<patterns_.size() && retmsk!=0; ++i)
130  retmsk &= ~(retpat ^ patterns_[i][wordnum]); // retmsk reduced to set of bits that are the same
131  return std::pair<T, T>(retpat & retmsk, retmsk);
132  }
133 
135  size_t nalternatives() const {
136  return patterns_.size();
137  }
138 
142  T conflict(T msk, T pat, size_t wordnum, size_t altnum) const {
143  if (wordnum < mask_.size()) {
144  if (T overlap = mask_[wordnum] & msk) {
145  assert(altnum < patterns_.size());
146  if (T differ = (patterns_[altnum][wordnum] & overlap) ^ (pat & overlap))
147  return differ;
148  }
149  }
150  return 0;
151  }
152 
156  T conflict(T msk, T pat, size_t wordnum) const {
157  if (wordnum < mask_.size()) {
158  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
159  if (T differ = conflict(msk, pat, wordnum, altnum))
160  return differ;
161  }
162  }
163  return 0;
164  }
165 
168  void check_insertion(T msk, T pat, size_t wordnum) const {
169  if (0!=msk && wordnum<mask_.size()) {
170  if (T differ = conflict(msk, pat, wordnum)) {
171  std::cerr <<"BitPattern::insert(msk=" <<Rose::StringUtility::addrToString(msk, 8*sizeof(T))
172  <<", pat=" <<Rose::StringUtility::addrToString(pat, 8*sizeof(T))
173  <<", wordnum=" <<wordnum <<") conflicts with existing pattern " <<*this
174  <<" at bits " <<Rose::StringUtility::addrToString(differ, 8*sizeof(T)) <<"\n";
175  assert(!"new bit pattern conflicts with existing pattern");
176  abort();
177  }
178  }
179  }
180 
183  bool any_same(const BitPattern &other, std::pair<size_t, size_t> *alternatives=NULL) const {
184  if (nwords()!=other.nwords())
185  return false;
186  for (size_t wordnum=0; wordnum<nwords(); ++wordnum) {
187  if (mask_[wordnum]!=other.mask_[wordnum])
188  return false;
189  }
190  for (size_t a1=0; a1<nalternatives(); ++a1) {
191  for (size_t a2=0; a2<other.nalternatives(); ++a2) {
192  bool are_same = true;
193  for (size_t wordnum=0; are_same && wordnum<nwords(); ++wordnum)
194  are_same = patterns_[a1][wordnum] == other.patterns_[a2][wordnum];
195  if (are_same) {
196  if (alternatives!=NULL)
197  *alternatives = std::make_pair(a1, a2);
198  return true;
199  }
200  }
201  }
202  return false;
203  }
204 
207  BitPattern& insert(T msk, T pat, size_t wordnum=0) {
208  assert(is_consistent());
209  assert(0 == (pat & ~msk));
210  check_insertion(msk, pat, wordnum);
211  if (msk != 0) {
212  if (wordnum >= mask_.size())
213  mask_.resize(wordnum+1, T(0));
214  mask_[wordnum] |= msk;
215  if (patterns_.empty()) {
216  patterns_.resize(1);
217  patterns_[0].resize(wordnum+1, T(0));
218  patterns_[0][wordnum] = pat;
219  } else {
220  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
221  if (wordnum >= patterns_[altnum].size())
222  patterns_[altnum].resize(wordnum+1, T(0));
223  patterns_[altnum][wordnum] |= pat;
224  }
225  }
226  }
227  assert(is_consistent());
228  return *this;
229  }
230 
234  BitPattern& bits(size_t lo_bit, size_t hi_bit, T value, size_t wordnum) {
235  T msk = IntegerOps::genMask<T>(lo_bit, hi_bit);
236  value = IntegerOps::shiftLeft2(value, lo_bit);
237  return insert(msk, value, wordnum);
238  }
239 
241  BitPattern shift_left(size_t nbits) const {
242 #if 0 /*DEBUGGING [Robb P. Matzke 2013-10-02]*/
243  std::cerr <<"BitPattern::shift_left: nbits=" <<nbits <<"; this=" <<*this <<"\n";
244 #endif
245  assert(is_consistent());
246  if (0==nbits || patterns_.empty())
247  return *this;
248  static const size_t word_size = 8*sizeof(T);
249  size_t need_nbits = width() + nbits;
250  size_t need_nwords = (need_nbits + word_size - 1) / word_size;
251  size_t word_delta = nbits / word_size;
252  size_t bit_delta_lt = nbits % word_size;
253  size_t bit_delta_rt = word_size - bit_delta_lt;
254  BitPattern retval;
255 
256  // shift the mask
257  retval.mask_.resize(need_nwords, 0);
258  for (size_t i=0; i<mask_.size(); ++i) {
259  retval.mask_[i+word_delta] |= IntegerOps::shiftLeft2(mask_[i], bit_delta_lt);
260  if (i+word_delta+1<need_nwords)
261  retval.mask_[i+word_delta+1] = IntegerOps::shiftRightLogical2(mask_[i], bit_delta_rt);
262  }
263 
264  // shift each pattern
265  retval.patterns_.resize(patterns_.size());
266  for (size_t i=0; i<patterns_.size(); ++i) {
267  retval.patterns_[i].resize(need_nwords, 0);
268  for (size_t j=0; j<patterns_[i].size(); ++j) {
269  retval.patterns_[i][j+word_delta] |= IntegerOps::shiftLeft2(patterns_[i][j], bit_delta_lt);
270  if (j+word_delta+1<need_nwords)
271  retval.patterns_[i][j+word_delta+1] = IntegerOps::shiftRightLogical2(patterns_[i][j], bit_delta_rt);
272  }
273  }
274  assert(is_consistent());
275 #if 0 /*DEBUGGING [Robb P. Matzke 2013-10-02]*/
276  std::cerr <<" shift_left result=" <<retval <<"\n";
277 #endif
278  return retval;
279  }
280 
287 #if 0 /*DEBUGGING [Robb P. Matzke 2013-10-02]*/
288  std::cerr <<"BitPattern::conjunction:\n"
289  <<" this = " <<*this <<"\n"
290  <<" other = " <<other <<"\n";
291 #endif
292  assert(is_consistent());
293  assert(other.is_consistent());
294  // check that the operation is possible
295  for (size_t altnum=0; altnum<other.nalternatives(); ++altnum) {
296  for (size_t wordnum=0; wordnum<other.nwords(); ++wordnum)
297  check_insertion(other.mask_[wordnum], other.patterns_[altnum][wordnum], wordnum);
298  }
299 
300  // merge masks
301  size_t this_nwords = mask_.size();
302  size_t result_nwords = std::max(this_nwords, other.mask_.size());
303  mask_.resize(result_nwords, T(0));
304  for (size_t wordnum=0; wordnum<other.mask_.size(); ++wordnum)
305  mask_[wordnum] |= other.mask_[wordnum];
306 
307  // do the conjunction
308  Alternatives retval;
309  for (size_t a1=0; a1<patterns_.size(); ++a1) {
310  for (size_t a2=0; a2<other.patterns_.size(); ++a2) {
311  retval.push_back(Words(result_nwords, T(0)));
312  for (size_t i=0; i<this_nwords; ++i)
313  retval.back()[i] = patterns_[a1][i];
314  for (size_t i=0; i<other.nwords(); ++i)
315  retval.back()[i] |= other.patterns_[a2][i];
316 
317  // check for and remove duplicate pattern
318  for (size_t a3=0; a3+1<retval.size(); ++a3) {
319  bool isdup = true;
320  for (size_t i=0; isdup && i<result_nwords; ++i)
321  isdup = retval[a3][i] == retval.back()[i];
322  if (isdup) {
323  retval.pop_back();
324  break;
325  }
326  }
327  }
328  }
329  patterns_ = retval;
330  assert(is_consistent());
331 #if 0 /*DEBUGGING [Robb P. Matzke 2013-10-02]*/
332  std::cerr <<" conjunction result = " <<*this <<"\n";
333 #endif
334  return *this;
335  }
336 
341  assert(is_consistent());
342  assert(other.is_consistent());
343  if (0==nalternatives()) {
344  *this = other;
345  } else if (0==other.nalternatives()) {
346  // void
347  } else {
348  assert(nwords()==other.nwords());
349  for (size_t wordnum=0; wordnum<nwords(); ++wordnum)
350  assert(mask_[wordnum]==other.mask_[wordnum]);
351  size_t na = nalternatives();
352  for (size_t a1=0; a1<other.nalternatives(); ++a1) {
353  bool isdup = false;
354  for (size_t a2=0; !isdup && a2<na; ++a2) {
355  isdup = true;
356  for (size_t wordnum=0; isdup && wordnum<nwords(); ++wordnum)
357  isdup = patterns_[a2][wordnum] == other.patterns_[a1][wordnum];
358  }
359  if (!isdup)
360  patterns_.push_back(other.patterns_[a1]);
361  }
362  }
363  assert(is_consistent());
364  return *this;
365  }
366 
370  BitPattern operator&(const BitPattern &other) const {
371  BitPattern retval = *this;
372  return retval.conjunction(other);
373  }
375  return conjunction(other);
376  }
382  BitPattern operator|(const BitPattern &other) const {
383  BitPattern retval = *this;
384  return retval.disjunction(other);
385  }
387  return disjunction(other);
388  }
393  bool matches(const std::vector<T> value_words) const {
394  if (0==nalternatives())
395  return true;
396  if (value_words.size() < nwords())
397  return false;
398  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
399  bool eq = true;
400  for (size_t wordnum=0; eq && wordnum<nwords(); ++wordnum)
401  eq = (value_words[wordnum] & mask_[wordnum]) == (patterns_[altnum][wordnum] & mask_[wordnum]);
402  if (eq)
403  return true;
404  }
405  return false;
406  }
407  bool matches(const T *value_words, size_t sz) const {
408  std::vector<T> vv;
409  for (size_t i=0; i<sz; ++i)
410  vv.push_back(value_words[i]);
411  return matches(vv);
412  }
416  bool matches_word(T value, size_t wordnum) const {
417  if (0==nalternatives() || wordnum>=nwords())
418  return true;
419  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
420  if ((value & mask_[wordnum]) == (patterns_[altnum][wordnum] & mask_[wordnum]))
421  return true;
422  }
423  return false;
424  }
425 
427  void print(std::ostream &o, size_t altnum, bool with_mask=true) const {
428  assert(altnum<nalternatives());
429  o <<(1==nwords()?"":"{");
430  for (size_t wordnum=0; wordnum<nwords(); ++wordnum) {
431  o <<(0==wordnum?"":",") <<Rose::StringUtility::addrToString(patterns_[altnum][wordnum], 8*sizeof(T));
432  if (with_mask)
433  o <<"/" <<Rose::StringUtility::addrToString(mask_[wordnum], 8*sizeof(T));
434  }
435  o <<(1==nwords()?"":"}");
436  }
437 
439  void print(std::ostream &o) const {
440  if (0==nwords()) {
441  o <<"empty";
442  } else {
443  o <<(1==nalternatives()?"":"(");
444  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
445  o <<(0==altnum?"":" | ");
446  print(o, altnum, false);
447  }
448  o <<(1==nalternatives()?"":")");
449  o <<"/" <<(1==nwords()?"":"{");
450  for (size_t wordnum=0; wordnum<nwords(); ++wordnum)
451  o <<(wordnum>0?",":"") <<Rose::StringUtility::addrToString(mask_[wordnum], 8*sizeof(T));
452  o <<(1==nwords()?"":"}");
453  }
454  }
455 };
456 
457 template<typename T>
458 std::ostream& operator<<(std::ostream &o, const BitPattern<T> &bp)
459 {
460  bp.print(o);
461  return o;
462 }
463 
464 #endif
bool matches(const std::vector< T > value_words) const
Returns true if this pattern matches the specified values.
Definition: BitPattern.h:393
BitPattern operator&(const BitPattern &other) const
Creates a new BitPattern that is the conjunction of two bit patterns.
Definition: BitPattern.h:370
size_t width() const
Returns the size of the pattern in bits.
Definition: BitPattern.h:105
size_t nwords() const
Returns the number of words in the pattern.
Definition: BitPattern.h:99
T conflict(T msk, T pat, size_t wordnum, size_t altnum) const
Determines if the specified bits conflict with a particular pattern alternative.
Definition: BitPattern.h:142
void print(std::ostream &o, size_t altnum, bool with_mask=true) const
Print one pattern alternative.
Definition: BitPattern.h:427
bool any_same(const BitPattern &other, std::pair< size_t, size_t > *alternatives=NULL) const
Determines whether two patterns can match the same input.
Definition: BitPattern.h:183
void print(std::ostream &o) const
Print all alternatives of the pattern.
Definition: BitPattern.h:439
bool matches_word(T value, size_t wordnum) const
Returns true if one word of this pattern matches the specified value.
Definition: BitPattern.h:416
bool matches(const T *value_words, size_t sz) const
Returns true if this pattern matches the specified values.
Definition: BitPattern.h:407
std::pair< T, T > invariants(T msk, size_t wordnum)
Returns invariant bits.
Definition: BitPattern.h:124
size_t countSet(T val)
Counts how many bits are set (one).
Definition: integerOps.h:279
BitPattern shift_left(size_t nbits) const
Return a new BitPattern with the pattern bits shifted left by the indicated amount.
Definition: BitPattern.h:241
BitPattern & bits(size_t lo_bit, size_t hi_bit, T value, size_t wordnum)
Adds significant bits to all alternatives of a pattern.
Definition: BitPattern.h:234
BitPattern & operator&=(const BitPattern &other)
Creates a new BitPattern that is the conjunction of two bit patterns.
Definition: BitPattern.h:374
T conflict(T msk, T pat, size_t wordnum) const
Determines if the specified significant bits conflict with any of the existing pattern alternatives...
Definition: BitPattern.h:156
bool is_consistent() const
Verify internal consistency.
Definition: BitPattern.h:75
ROSE_UTIL_API std::string addrToString(uint64_t value, size_t nbits=0)
Convert a virtual address to a string.
BitPattern(T msk, T pat, size_t wordnum)
Creates a new bit pattern for a single word using a mask and value.
Definition: BitPattern.h:63
BitPattern operator|(const BitPattern &other) const
Creates a new BitPattern that is the inclusive disjunction of two bit patterns.
Definition: BitPattern.h:382
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.
Definition: BitPattern.h:70
Describes a pattern of bits in a finite number of words.
Definition: BitPattern.h:51
BitPattern & disjunction(const BitPattern &other)
Combines this BitPattern with another by forming their disjunction.
Definition: BitPattern.h:340
T shiftRightLogical2(T value, size_t count, size_t width=8 *sizeof(T))
Shifts bits of value right by count bits without sign extension.
Definition: integerOps.h:122
boost::optional< size_t > msb_set(T val)
Optionally returns the zero-origin position of the most significant set bit.
Definition: integerOps.h:303
void check_insertion(T msk, T pat, size_t wordnum) const
Check that a pattern insertion does not conflict with an existing pattern.
Definition: BitPattern.h:168
BitPattern & operator|=(const BitPattern &other)
Creates a new BitPattern that is the inclusive disjunction of two bit patterns.
Definition: BitPattern.h:386
BitPattern & conjunction(const BitPattern &other)
Combines this BitPattern with another by forming their conjunction.
Definition: BitPattern.h:286
BitPattern & insert(T msk, T pat, size_t wordnum=0)
Creates a new pattern by adding significant bits to all alternatives of a pattern.
Definition: BitPattern.h:207
BitPattern()
Creates a new, empty bit pattern.
Definition: BitPattern.h:59
size_t nsignificant() const
Returns the number of significant bits.
Definition: BitPattern.h:90
size_t nalternatives() const
Returns the number of alternatives.
Definition: BitPattern.h:135
T mask(size_t wordnum)
Returns the mask for the specified word.
Definition: BitPattern.h:113
T shiftLeft2(T value, size_t count, size_t width=8 *sizeof(T))
Shifts bits of value left by count bits.
Definition: integerOps.h:108