ROSE  0.9.11.56
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 
10 namespace Rose {
11 
52 template<typename T>
53 class BitPattern {
54  typedef std::vector<T> Words;
55  typedef std::vector<Words> Alternatives;
56  Words mask_; // significant bits
57  Alternatives patterns_; // set of alternative patterns; each pattern has the same size as the mask
58 
59 public:
62 
65  BitPattern(T msk, T pat, size_t wordnum) {
66  insert(msk, pat, wordnum);
67  }
68 
72  BitPattern(size_t lo_bit, size_t hi_bit, T pat, size_t wordnum) {
73  bits(lo_bit, hi_bit, pat, wordnum);
74  }
75 
77  bool is_consistent() const {
78  for (size_t i=0; i<patterns_.size(); ++i) {
79  if (patterns_[i].size()!=mask_.size()) {
80  std::cerr <<"BitPattern::is_consistent failed\n"
81  <<" mask_.size() = " <<mask_.size() <<"\n"
82  <<" patterns_[" <<i <<"].size() = " <<patterns_[i].size() <<"\n"
83  <<" these two vectors should have been the same size\n";
84  std::cerr <<" this = ";
85  print(std::cerr); // printing might fail
86  std::cerr <<"\n";
87  return false;
88  }
89  }
90  return true;
91  }
92 
94  size_t nsignificant() const {
95  size_t retval = 0;
96  for (size_t i=0; i<mask_.size(); ++i)
97  retval += IntegerOps::countSet(mask_[i]);
98  return retval;
99  }
100 
103  size_t nwords() const {
104  return mask_.size();
105  }
106 
109  size_t width() const {
110  if (0==mask_.size())
111  return 0;
112  assert(mask_.back()!=0);
113  return 8*sizeof(T)*(mask_.size()-1) + IntegerOps::msb_set(mask_.back()).get() + 1;
114  }
115 
117  T mask(size_t wordnum) {
118  if (wordnum >= mask_.size())
119  return 0;
120  return mask_[wordnum];
121  }
122 
128  std::pair<T, T> invariants(T msk, size_t wordnum) {
129  if (msk==0 || wordnum>mask_.size() || patterns_.empty())
130  return std::pair<T, T>(0, 0);
131  T retmsk = msk & mask_[wordnum];
132  T retpat = retmsk & patterns_[0][wordnum];
133  for (size_t i=1; i<patterns_.size() && retmsk!=0; ++i)
134  retmsk &= ~(retpat ^ patterns_[i][wordnum]); // retmsk reduced to set of bits that are the same
135  return std::pair<T, T>(retpat & retmsk, retmsk);
136  }
137 
139  size_t nalternatives() const {
140  return patterns_.size();
141  }
142 
146  T conflict(T msk, T pat, size_t wordnum, size_t altnum) const {
147  if (wordnum < mask_.size()) {
148  if (T overlap = mask_[wordnum] & msk) {
149  assert(altnum < patterns_.size());
150  if (T differ = (patterns_[altnum][wordnum] & overlap) ^ (pat & overlap))
151  return differ;
152  }
153  }
154  return 0;
155  }
156 
160  T conflict(T msk, T pat, size_t wordnum) const {
161  if (wordnum < mask_.size()) {
162  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
163  if (T differ = conflict(msk, pat, wordnum, altnum))
164  return differ;
165  }
166  }
167  return 0;
168  }
169 
172  void check_insertion(T msk, T pat, size_t wordnum) const {
173  if (0!=msk && wordnum<mask_.size()) {
174  if (T differ = conflict(msk, pat, wordnum)) {
175  std::cerr <<"BitPattern::insert(msk=" <<Rose::StringUtility::addrToString(msk, 8*sizeof(T))
176  <<", pat=" <<Rose::StringUtility::addrToString(pat, 8*sizeof(T))
177  <<", wordnum=" <<wordnum <<") conflicts with existing pattern ";
178  print(std::cerr);
179  std::cerr <<" at bits " <<Rose::StringUtility::addrToString(differ, 8*sizeof(T)) <<"\n";
180  assert(!"new bit pattern conflicts with existing pattern");
181  abort();
182  }
183  }
184  }
185 
188  bool any_same(const BitPattern &other, std::pair<size_t, size_t> *alternatives=NULL) const {
189  if (nwords()!=other.nwords())
190  return false;
191  for (size_t wordnum=0; wordnum<nwords(); ++wordnum) {
192  if (mask_[wordnum]!=other.mask_[wordnum])
193  return false;
194  }
195  for (size_t a1=0; a1<nalternatives(); ++a1) {
196  for (size_t a2=0; a2<other.nalternatives(); ++a2) {
197  bool are_same = true;
198  for (size_t wordnum=0; are_same && wordnum<nwords(); ++wordnum)
199  are_same = patterns_[a1][wordnum] == other.patterns_[a2][wordnum];
200  if (are_same) {
201  if (alternatives!=NULL)
202  *alternatives = std::make_pair(a1, a2);
203  return true;
204  }
205  }
206  }
207  return false;
208  }
209 
212  BitPattern& insert(T msk, T pat, size_t wordnum=0) {
213  assert(is_consistent());
214  assert(0 == (pat & ~msk));
215  check_insertion(msk, pat, wordnum);
216  if (msk != 0) {
217  if (wordnum >= mask_.size())
218  mask_.resize(wordnum+1, T(0));
219  mask_[wordnum] |= msk;
220  if (patterns_.empty()) {
221  patterns_.resize(1);
222  patterns_[0].resize(wordnum+1, T(0));
223  patterns_[0][wordnum] = pat;
224  } else {
225  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
226  if (wordnum >= patterns_[altnum].size())
227  patterns_[altnum].resize(wordnum+1, T(0));
228  patterns_[altnum][wordnum] |= pat;
229  }
230  }
231  }
232  assert(is_consistent());
233  return *this;
234  }
235 
239  BitPattern& bits(size_t lo_bit, size_t hi_bit, T value, size_t wordnum) {
240  T msk = IntegerOps::genMask<T>(lo_bit, hi_bit);
241  value = IntegerOps::shiftLeft2(value, lo_bit);
242  return insert(msk, value, wordnum);
243  }
244 
246  BitPattern shift_left(size_t nbits) const {
247  assert(is_consistent());
248  if (0==nbits || patterns_.empty())
249  return *this;
250  static const size_t word_size = 8*sizeof(T);
251  size_t need_nbits = width() + nbits;
252  size_t need_nwords = (need_nbits + word_size - 1) / word_size;
253  size_t word_delta = nbits / word_size;
254  size_t bit_delta_lt = nbits % word_size;
255  size_t bit_delta_rt = word_size - bit_delta_lt;
256  BitPattern retval;
257 
258  // shift the mask
259  retval.mask_.resize(need_nwords, 0);
260  for (size_t i=0; i<mask_.size(); ++i) {
261  retval.mask_[i+word_delta] |= IntegerOps::shiftLeft2(mask_[i], bit_delta_lt);
262  if (i+word_delta+1<need_nwords)
263  retval.mask_[i+word_delta+1] = IntegerOps::shiftRightLogical2(mask_[i], bit_delta_rt);
264  }
265 
266  // shift each pattern
267  retval.patterns_.resize(patterns_.size());
268  for (size_t i=0; i<patterns_.size(); ++i) {
269  retval.patterns_[i].resize(need_nwords, 0);
270  for (size_t j=0; j<patterns_[i].size(); ++j) {
271  retval.patterns_[i][j+word_delta] |= IntegerOps::shiftLeft2(patterns_[i][j], bit_delta_lt);
272  if (j+word_delta+1<need_nwords)
273  retval.patterns_[i][j+word_delta+1] = IntegerOps::shiftRightLogical2(patterns_[i][j], bit_delta_rt);
274  }
275  }
276  assert(is_consistent());
277  return retval;
278  }
279 
286  assert(is_consistent());
287  assert(other.is_consistent());
288  // check that the operation is possible
289  for (size_t altnum=0; altnum<other.nalternatives(); ++altnum) {
290  for (size_t wordnum=0; wordnum<other.nwords(); ++wordnum)
291  check_insertion(other.mask_[wordnum], other.patterns_[altnum][wordnum], wordnum);
292  }
293 
294  // merge masks
295  size_t this_nwords = mask_.size();
296  size_t result_nwords = std::max(this_nwords, other.mask_.size());
297  mask_.resize(result_nwords, T(0));
298  for (size_t wordnum=0; wordnum<other.mask_.size(); ++wordnum)
299  mask_[wordnum] |= other.mask_[wordnum];
300 
301  // do the conjunction
302  Alternatives retval;
303  for (size_t a1=0; a1<patterns_.size(); ++a1) {
304  for (size_t a2=0; a2<other.patterns_.size(); ++a2) {
305  retval.push_back(Words(result_nwords, T(0)));
306  for (size_t i=0; i<this_nwords; ++i)
307  retval.back()[i] = patterns_[a1][i];
308  for (size_t i=0; i<other.nwords(); ++i)
309  retval.back()[i] |= other.patterns_[a2][i];
310 
311  // check for and remove duplicate pattern
312  for (size_t a3=0; a3+1<retval.size(); ++a3) {
313  bool isdup = true;
314  for (size_t i=0; isdup && i<result_nwords; ++i)
315  isdup = retval[a3][i] == retval.back()[i];
316  if (isdup) {
317  retval.pop_back();
318  break;
319  }
320  }
321  }
322  }
323  patterns_ = retval;
324  assert(is_consistent());
325  return *this;
326  }
327 
332  assert(is_consistent());
333  assert(other.is_consistent());
334  if (0==nalternatives()) {
335  *this = other;
336  } else if (0==other.nalternatives()) {
337  // void
338  } else {
339  assert(nwords()==other.nwords());
340  for (size_t wordnum=0; wordnum<nwords(); ++wordnum)
341  assert(mask_[wordnum]==other.mask_[wordnum]);
342  size_t na = nalternatives();
343  for (size_t a1=0; a1<other.nalternatives(); ++a1) {
344  bool isdup = false;
345  for (size_t a2=0; !isdup && a2<na; ++a2) {
346  isdup = true;
347  for (size_t wordnum=0; isdup && wordnum<nwords(); ++wordnum)
348  isdup = patterns_[a2][wordnum] == other.patterns_[a1][wordnum];
349  }
350  if (!isdup)
351  patterns_.push_back(other.patterns_[a1]);
352  }
353  }
354  assert(is_consistent());
355  return *this;
356  }
357 
361  BitPattern operator&(const BitPattern &other) const {
362  BitPattern retval = *this;
363  return retval.conjunction(other);
364  }
366  return conjunction(other);
367  }
373  BitPattern operator|(const BitPattern &other) const {
374  BitPattern retval = *this;
375  return retval.disjunction(other);
376  }
378  return disjunction(other);
379  }
384  bool matches(const std::vector<T> value_words) const {
385  if (0==nalternatives())
386  return true;
387  if (value_words.size() < nwords())
388  return false;
389  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
390  bool eq = true;
391  for (size_t wordnum=0; eq && wordnum<nwords(); ++wordnum)
392  eq = (value_words[wordnum] & mask_[wordnum]) == (patterns_[altnum][wordnum] & mask_[wordnum]);
393  if (eq)
394  return true;
395  }
396  return false;
397  }
398  bool matches(const T *value_words, size_t sz) const {
399  std::vector<T> vv;
400  for (size_t i=0; i<sz; ++i)
401  vv.push_back(value_words[i]);
402  return matches(vv);
403  }
407  bool matches_word(T value, size_t wordnum) const {
408  if (0==nalternatives() || wordnum>=nwords())
409  return true;
410  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
411  if ((value & mask_[wordnum]) == (patterns_[altnum][wordnum] & mask_[wordnum]))
412  return true;
413  }
414  return false;
415  }
416 
418  void print(std::ostream &o, size_t altnum, bool with_mask=true) const {
419  assert(altnum<nalternatives());
420  o <<(1==nwords()?"":"{");
421  for (size_t wordnum=0; wordnum<nwords(); ++wordnum) {
422  o <<(0==wordnum?"":",") <<Rose::StringUtility::addrToString(patterns_[altnum][wordnum], 8*sizeof(T));
423  if (with_mask)
424  o <<"/" <<Rose::StringUtility::addrToString(mask_[wordnum], 8*sizeof(T));
425  }
426  o <<(1==nwords()?"":"}");
427  }
428 
430  void print(std::ostream &o) const {
431  if (0==nwords()) {
432  o <<"empty";
433  } else {
434  o <<(1==nalternatives()?"":"(");
435  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
436  o <<(0==altnum?"":" | ");
437  print(o, altnum, false);
438  }
439  o <<(1==nalternatives()?"":")");
440  o <<"/" <<(1==nwords()?"":"{");
441  for (size_t wordnum=0; wordnum<nwords(); ++wordnum)
442  o <<(wordnum>0?",":"") <<Rose::StringUtility::addrToString(mask_[wordnum], 8*sizeof(T));
443  o <<(1==nwords()?"":"}");
444  }
445  }
446 };
447 
448 } // namespace
449 
450 template<typename T>
451 std::ostream& operator<<(std::ostream &o, const Rose::BitPattern<T> &bp)
452 {
453  bp.print(o);
454  return o;
455 }
456 
457 #endif
bool matches(const T *value_words, size_t sz) const
Returns true if this pattern matches the specified values.
Definition: BitPattern.h:398
bool matches_word(T value, size_t wordnum) const
Returns true if one word of this pattern matches the specified value.
Definition: BitPattern.h:407
size_t nwords() const
Returns the number of words in the pattern.
Definition: BitPattern.h:103
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:160
size_t width() const
Returns the size of the pattern in bits.
Definition: BitPattern.h:109
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:239
Main namespace for the ROSE library.
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:72
BitPattern operator|(const BitPattern &other) const
Creates a new BitPattern that is the inclusive disjunction of two bit patterns.
Definition: BitPattern.h:373
void print(std::ostream &o) const
Print all alternatives of the pattern.
Definition: BitPattern.h:430
T mask(size_t wordnum)
Returns the mask for the specified word.
Definition: BitPattern.h:117
size_t countSet(T val)
Counts how many bits are set (one).
Definition: integerOps.h:279
size_t nsignificant() const
Returns the number of significant bits.
Definition: BitPattern.h:94
BitPattern operator&(const BitPattern &other) const
Creates a new BitPattern that is the conjunction of two bit patterns.
Definition: BitPattern.h:361
BitPattern & operator|=(const BitPattern &other)
Creates a new BitPattern that is the inclusive disjunction of two bit patterns.
Definition: BitPattern.h:377
BitPattern shift_left(size_t nbits) const
Return a new BitPattern with the pattern bits shifted left by the indicated amount.
Definition: BitPattern.h:246
BitPattern()
Creates a new, empty bit pattern.
Definition: BitPattern.h:61
ROSE_UTIL_API std::string addrToString(uint64_t value, size_t nbits=0)
Convert a virtual address to a string.
BitPattern & operator&=(const BitPattern &other)
Creates a new BitPattern that is the conjunction of two bit patterns.
Definition: BitPattern.h:365
Describes a pattern of bits in a finite number of words.
Definition: BitPattern.h:53
std::pair< T, T > invariants(T msk, size_t wordnum)
Returns invariant bits.
Definition: BitPattern.h:128
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:65
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
void print(std::ostream &o, size_t altnum, bool with_mask=true) const
Print one pattern alternative.
Definition: BitPattern.h:418
size_t nalternatives() const
Returns the number of alternatives.
Definition: BitPattern.h:139
boost::optional< size_t > msb_set(T val)
Optionally returns the zero-origin position of the most significant set bit.
Definition: integerOps.h:303
BitPattern & disjunction(const BitPattern &other)
Combines this BitPattern with another by forming their disjunction.
Definition: BitPattern.h:331
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:146
bool is_consistent() const
Verify internal consistency.
Definition: BitPattern.h:77
BitPattern & conjunction(const BitPattern &other)
Combines this BitPattern with another by forming their conjunction.
Definition: BitPattern.h:285
bool matches(const std::vector< T > value_words) const
Returns true if this pattern matches the specified values.
Definition: BitPattern.h:384
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:172
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:212
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:188
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