ROSE  0.11.2.0
BitPattern.h
1 #ifndef ROSE_BitPattern_H
2 #define ROSE_BitPattern_H
3 
4 #include <rosePublicConfig.h>
5 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
6 
7 #include "integerOps.h"
8 #include "StringUtility.h"
9 
10 #include <iostream>
11 #include <vector>
12 
13 namespace Rose {
14 
55 template<typename T>
56 class BitPattern {
57  typedef std::vector<T> Words;
58  typedef std::vector<Words> Alternatives;
59  Words mask_; // significant bits
60  Alternatives patterns_; // set of alternative patterns; each pattern has the same size as the mask
61 
62 public:
65 
68  BitPattern(T msk, T pat, size_t wordnum) {
69  insert(msk, pat, wordnum);
70  }
71 
75  BitPattern(size_t lo_bit, size_t hi_bit, T pat, size_t wordnum) {
76  bits(lo_bit, hi_bit, pat, wordnum);
77  }
78 
80  bool is_consistent() const {
81  for (size_t i=0; i<patterns_.size(); ++i) {
82  if (patterns_[i].size()!=mask_.size()) {
83  std::cerr <<"BitPattern::is_consistent failed\n"
84  <<" mask_.size() = " <<mask_.size() <<"\n"
85  <<" patterns_[" <<i <<"].size() = " <<patterns_[i].size() <<"\n"
86  <<" these two vectors should have been the same size\n";
87  std::cerr <<" this = ";
88  print(std::cerr); // printing might fail
89  std::cerr <<"\n";
90  return false;
91  }
92  }
93  return true;
94  }
95 
97  size_t nsignificant() const {
98  size_t retval = 0;
99  for (size_t i=0; i<mask_.size(); ++i)
100  retval += IntegerOps::countSet(mask_[i]);
101  return retval;
102  }
103 
106  size_t nwords() const {
107  return mask_.size();
108  }
109 
112  size_t width() const {
113  if (0==mask_.size())
114  return 0;
115  assert(mask_.back()!=0);
116  return 8*sizeof(T)*(mask_.size()-1) + IntegerOps::msb_set(mask_.back()).get() + 1;
117  }
118 
120  T mask(size_t wordnum) {
121  if (wordnum >= mask_.size())
122  return 0;
123  return mask_[wordnum];
124  }
125 
131  std::pair<T, T> invariants(T msk, size_t wordnum) {
132  if (msk==0 || wordnum>mask_.size() || patterns_.empty())
133  return std::pair<T, T>(0, 0);
134  T retmsk = msk & mask_[wordnum];
135  T retpat = retmsk & patterns_[0][wordnum];
136  for (size_t i=1; i<patterns_.size() && retmsk!=0; ++i)
137  retmsk &= ~(retpat ^ patterns_[i][wordnum]); // retmsk reduced to set of bits that are the same
138  return std::pair<T, T>(retpat & retmsk, retmsk);
139  }
140 
142  size_t nalternatives() const {
143  return patterns_.size();
144  }
145 
149  T conflict(T msk, T pat, size_t wordnum, size_t altnum) const {
150  if (wordnum < mask_.size()) {
151  if (T overlap = mask_[wordnum] & msk) {
152  assert(altnum < patterns_.size());
153  if (T differ = (patterns_[altnum][wordnum] & overlap) ^ (pat & overlap))
154  return differ;
155  }
156  }
157  return 0;
158  }
159 
163  T conflict(T msk, T pat, size_t wordnum) const {
164  if (wordnum < mask_.size()) {
165  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
166  if (T differ = conflict(msk, pat, wordnum, altnum))
167  return differ;
168  }
169  }
170  return 0;
171  }
172 
175  void check_insertion(T msk, T pat, size_t wordnum) const {
176  if (0!=msk && wordnum<mask_.size()) {
177  if (T differ = conflict(msk, pat, wordnum)) {
178  std::cerr <<"BitPattern::insert(msk=" <<Rose::StringUtility::addrToString(msk, 8*sizeof(T))
179  <<", pat=" <<Rose::StringUtility::addrToString(pat, 8*sizeof(T))
180  <<", wordnum=" <<wordnum <<") conflicts with existing pattern ";
181  print(std::cerr);
182  std::cerr <<" at bits " <<Rose::StringUtility::addrToString(differ, 8*sizeof(T)) <<"\n";
183  assert(!"new bit pattern conflicts with existing pattern");
184  abort();
185  }
186  }
187  }
188 
191  bool any_same(const BitPattern &other, std::pair<size_t, size_t> *alternatives=NULL) const {
192  if (nwords()!=other.nwords())
193  return false;
194  for (size_t wordnum=0; wordnum<nwords(); ++wordnum) {
195  if (mask_[wordnum]!=other.mask_[wordnum])
196  return false;
197  }
198  for (size_t a1=0; a1<nalternatives(); ++a1) {
199  for (size_t a2=0; a2<other.nalternatives(); ++a2) {
200  bool are_same = true;
201  for (size_t wordnum=0; are_same && wordnum<nwords(); ++wordnum)
202  are_same = patterns_[a1][wordnum] == other.patterns_[a2][wordnum];
203  if (are_same) {
204  if (alternatives!=NULL)
205  *alternatives = std::make_pair(a1, a2);
206  return true;
207  }
208  }
209  }
210  return false;
211  }
212 
215  BitPattern& insert(T msk, T pat, size_t wordnum=0) {
216  assert(is_consistent());
217  assert(0 == (pat & ~msk));
218  check_insertion(msk, pat, wordnum);
219  if (msk != 0) {
220  if (wordnum >= mask_.size())
221  mask_.resize(wordnum+1, T(0));
222  mask_[wordnum] |= msk;
223  if (patterns_.empty()) {
224  patterns_.resize(1);
225  patterns_[0].resize(wordnum+1, T(0));
226  patterns_[0][wordnum] = pat;
227  } else {
228  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
229  if (wordnum >= patterns_[altnum].size())
230  patterns_[altnum].resize(wordnum+1, T(0));
231  patterns_[altnum][wordnum] |= pat;
232  }
233  }
234  }
235  assert(is_consistent());
236  return *this;
237  }
238 
242  BitPattern& bits(size_t lo_bit, size_t hi_bit, T value, size_t wordnum) {
243  T msk = IntegerOps::genMask<T>(lo_bit, hi_bit);
244  value = IntegerOps::shiftLeft2(value, lo_bit);
245  return insert(msk, value, wordnum);
246  }
247 
249  BitPattern shift_left(size_t nbits) const {
250  assert(is_consistent());
251  if (0==nbits || patterns_.empty())
252  return *this;
253  static const size_t word_size = 8*sizeof(T);
254  size_t need_nbits = width() + nbits;
255  size_t need_nwords = (need_nbits + word_size - 1) / word_size;
256  size_t word_delta = nbits / word_size;
257  size_t bit_delta_lt = nbits % word_size;
258  size_t bit_delta_rt = word_size - bit_delta_lt;
259  BitPattern retval;
260 
261  // shift the mask
262  retval.mask_.resize(need_nwords, 0);
263  for (size_t i=0; i<mask_.size(); ++i) {
264  retval.mask_[i+word_delta] |= IntegerOps::shiftLeft2(mask_[i], bit_delta_lt);
265  if (i+word_delta+1<need_nwords)
266  retval.mask_[i+word_delta+1] = IntegerOps::shiftRightLogical2(mask_[i], bit_delta_rt);
267  }
268 
269  // shift each pattern
270  retval.patterns_.resize(patterns_.size());
271  for (size_t i=0; i<patterns_.size(); ++i) {
272  retval.patterns_[i].resize(need_nwords, 0);
273  for (size_t j=0; j<patterns_[i].size(); ++j) {
274  retval.patterns_[i][j+word_delta] |= IntegerOps::shiftLeft2(patterns_[i][j], bit_delta_lt);
275  if (j+word_delta+1<need_nwords)
276  retval.patterns_[i][j+word_delta+1] = IntegerOps::shiftRightLogical2(patterns_[i][j], bit_delta_rt);
277  }
278  }
279  assert(is_consistent());
280  return retval;
281  }
282 
289  assert(is_consistent());
290  assert(other.is_consistent());
291  // check that the operation is possible
292  for (size_t altnum=0; altnum<other.nalternatives(); ++altnum) {
293  for (size_t wordnum=0; wordnum<other.nwords(); ++wordnum)
294  check_insertion(other.mask_[wordnum], other.patterns_[altnum][wordnum], wordnum);
295  }
296 
297  // merge masks
298  size_t this_nwords = mask_.size();
299  size_t result_nwords = std::max(this_nwords, other.mask_.size());
300  mask_.resize(result_nwords, T(0));
301  for (size_t wordnum=0; wordnum<other.mask_.size(); ++wordnum)
302  mask_[wordnum] |= other.mask_[wordnum];
303 
304  // do the conjunction
305  Alternatives retval;
306  for (size_t a1=0; a1<patterns_.size(); ++a1) {
307  for (size_t a2=0; a2<other.patterns_.size(); ++a2) {
308  retval.push_back(Words(result_nwords, T(0)));
309  for (size_t i=0; i<this_nwords; ++i)
310  retval.back()[i] = patterns_[a1][i];
311  for (size_t i=0; i<other.nwords(); ++i)
312  retval.back()[i] |= other.patterns_[a2][i];
313 
314  // check for and remove duplicate pattern
315  for (size_t a3=0; a3+1<retval.size(); ++a3) {
316  bool isdup = true;
317  for (size_t i=0; isdup && i<result_nwords; ++i)
318  isdup = retval[a3][i] == retval.back()[i];
319  if (isdup) {
320  retval.pop_back();
321  break;
322  }
323  }
324  }
325  }
326  patterns_ = retval;
327  assert(is_consistent());
328  return *this;
329  }
330 
335  assert(is_consistent());
336  assert(other.is_consistent());
337  if (0==nalternatives()) {
338  *this = other;
339  } else if (0==other.nalternatives()) {
340  // void
341  } else {
342  assert(nwords()==other.nwords());
343  for (size_t wordnum=0; wordnum<nwords(); ++wordnum)
344  assert(mask_[wordnum]==other.mask_[wordnum]);
345  size_t na = nalternatives();
346  for (size_t a1=0; a1<other.nalternatives(); ++a1) {
347  bool isdup = false;
348  for (size_t a2=0; !isdup && a2<na; ++a2) {
349  isdup = true;
350  for (size_t wordnum=0; isdup && wordnum<nwords(); ++wordnum)
351  isdup = patterns_[a2][wordnum] == other.patterns_[a1][wordnum];
352  }
353  if (!isdup)
354  patterns_.push_back(other.patterns_[a1]);
355  }
356  }
357  assert(is_consistent());
358  return *this;
359  }
360 
364  BitPattern operator&(const BitPattern &other) const {
365  BitPattern retval = *this;
366  return retval.conjunction(other);
367  }
369  return conjunction(other);
370  }
376  BitPattern operator|(const BitPattern &other) const {
377  BitPattern retval = *this;
378  return retval.disjunction(other);
379  }
381  return disjunction(other);
382  }
387  bool matches(const std::vector<T> value_words) const {
388  if (0==nalternatives())
389  return true;
390  if (value_words.size() < nwords())
391  return false;
392  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
393  bool eq = true;
394  for (size_t wordnum=0; eq && wordnum<nwords(); ++wordnum)
395  eq = (value_words[wordnum] & mask_[wordnum]) == (patterns_[altnum][wordnum] & mask_[wordnum]);
396  if (eq)
397  return true;
398  }
399  return false;
400  }
401  bool matches(const T *value_words, size_t sz) const {
402  std::vector<T> vv;
403  for (size_t i=0; i<sz; ++i)
404  vv.push_back(value_words[i]);
405  return matches(vv);
406  }
410  bool matches_word(T value, size_t wordnum) const {
411  if (0==nalternatives() || wordnum>=nwords())
412  return true;
413  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
414  if ((value & mask_[wordnum]) == (patterns_[altnum][wordnum] & mask_[wordnum]))
415  return true;
416  }
417  return false;
418  }
419 
421  void print(std::ostream &o, size_t altnum, bool with_mask=true) const {
422  assert(altnum<nalternatives());
423  o <<(1==nwords()?"":"{");
424  for (size_t wordnum=0; wordnum<nwords(); ++wordnum) {
425  o <<(0==wordnum?"":",") <<Rose::StringUtility::addrToString(patterns_[altnum][wordnum], 8*sizeof(T));
426  if (with_mask)
427  o <<"/" <<Rose::StringUtility::addrToString(mask_[wordnum], 8*sizeof(T));
428  }
429  o <<(1==nwords()?"":"}");
430  }
431 
433  void print(std::ostream &o) const {
434  if (0==nwords()) {
435  o <<"empty";
436  } else {
437  o <<(1==nalternatives()?"":"(");
438  for (size_t altnum=0; altnum<nalternatives(); ++altnum) {
439  o <<(0==altnum?"":" | ");
440  print(o, altnum, false);
441  }
442  o <<(1==nalternatives()?"":")");
443  o <<"/" <<(1==nwords()?"":"{");
444  for (size_t wordnum=0; wordnum<nwords(); ++wordnum)
445  o <<(wordnum>0?",":"") <<Rose::StringUtility::addrToString(mask_[wordnum], 8*sizeof(T));
446  o <<(1==nwords()?"":"}");
447  }
448  }
449 };
450 
451 } // namespace
452 
453 template<typename T>
454 std::ostream& operator<<(std::ostream &o, const Rose::BitPattern<T> &bp)
455 {
456  bp.print(o);
457  return o;
458 }
459 
460 #endif
461 #endif
bool matches(const T *value_words, size_t sz) const
Returns true if this pattern matches the specified values.
Definition: BitPattern.h:401
bool matches_word(T value, size_t wordnum) const
Returns true if one word of this pattern matches the specified value.
Definition: BitPattern.h:410
size_t nwords() const
Returns the number of words in the pattern.
Definition: BitPattern.h:106
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:163
size_t width() const
Returns the size of the pattern in bits.
Definition: BitPattern.h:112
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:242
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:75
BitPattern operator|(const BitPattern &other) const
Creates a new BitPattern that is the inclusive disjunction of two bit patterns.
Definition: BitPattern.h:376
void print(std::ostream &o) const
Print all alternatives of the pattern.
Definition: BitPattern.h:433
T mask(size_t wordnum)
Returns the mask for the specified word.
Definition: BitPattern.h:120
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:97
BitPattern operator&(const BitPattern &other) const
Creates a new BitPattern that is the conjunction of two bit patterns.
Definition: BitPattern.h:364
BitPattern & operator|=(const BitPattern &other)
Creates a new BitPattern that is the inclusive disjunction of two bit patterns.
Definition: BitPattern.h:380
BitPattern shift_left(size_t nbits) const
Return a new BitPattern with the pattern bits shifted left by the indicated amount.
Definition: BitPattern.h:249
BitPattern()
Creates a new, empty bit pattern.
Definition: BitPattern.h:64
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:368
Describes a pattern of bits in a finite number of words.
Definition: BitPattern.h:56
std::pair< T, T > invariants(T msk, size_t wordnum)
Returns invariant bits.
Definition: BitPattern.h:131
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:68
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:421
size_t nalternatives() const
Returns the number of alternatives.
Definition: BitPattern.h:142
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:334
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:149
bool is_consistent() const
Verify internal consistency.
Definition: BitPattern.h:80
BitPattern & conjunction(const BitPattern &other)
Combines this BitPattern with another by forming their conjunction.
Definition: BitPattern.h:288
bool matches(const std::vector< T > value_words) const
Returns true if this pattern matches the specified values.
Definition: BitPattern.h:387
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:175
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:215
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:191
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