kernel/bitpattern.h

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Claire Xenia Wolf <claire@yosyshq.com>
   5  *
   6  *  Permission to use, copy, modify, and/or distribute this software for any
   7  *  purpose with or without fee is hereby granted, provided that the above
   8  *  copyright notice and this permission notice appear in all copies.
   9  *
  10  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  *
  18  */
  19
  20 #ifndef BITPATTERN_H
  21 #define BITPATTERN_H
  22
  23 #include "kernel/log.h"
  24 #include "kernel/rtlil.h"
  25
  26 YOSYS_NAMESPACE_BEGIN
  27
  28 struct BitPatternPool
  29 {
  30         int width;
  31         struct bits_t {
  32                 std::vector<RTLIL::State> bitdata;
  33                 mutable unsigned int cached_hash;
  34                 bits_t(int width = 0) : bitdata(width), cached_hash(0) { }
  35                 RTLIL::State &operator[](int index) {
  36                         return bitdata[index];
  37                 }
  38                 const RTLIL::State &operator[](int index) const {
  39                         return bitdata[index];
  40                 }
  41                 bool operator==(const bits_t &other) const {
  42                         if (hash() != other.hash())
  43                                 return false;
  44                         return bitdata == other.bitdata;
  45                 }
  46                 unsigned int hash() const {
  47                         if (!cached_hash)
  48                                 cached_hash = hash_ops<std::vector<RTLIL::State>>::hash(bitdata);
  49                         return cached_hash;
  50                 }
  51         };
  52         pool<bits_t> database;
  53
  54         BitPatternPool(RTLIL::SigSpec sig)
  55         {
  56                 width = sig.size();
  57                 if (width > 0) {
  58                         bits_t pattern(width);
  59                         for (int i = 0; i < width; i++) {
  60                                 if (sig[i].wire == NULL && sig[i].data <= RTLIL::State::S1)
  61                                         pattern[i] = sig[i].data;
  62                                 else
  63                                         pattern[i] = RTLIL::State::Sa;
  64                         }
  65                         database.insert(pattern);
  66                 }
  67         }
  68
  69         BitPatternPool(int width)
  70         {
  71                 this->width = width;
  72                 if (width > 0) {
  73                         bits_t pattern(width);
  74                         for (int i = 0; i < width; i++)
  75                                 pattern[i] = RTLIL::State::Sa;
  76                         database.insert(pattern);
  77                 }
  78         }
  79
  80         bits_t sig2bits(RTLIL::SigSpec sig)
  81         {
  82                 bits_t bits;
  83                 bits.bitdata = sig.as_const().bits;
  84                 for (auto &b : bits.bitdata)
  85                         if (b > RTLIL::State::S1)
  86                                 b = RTLIL::State::Sa;
  87                 return bits;
  88         }
  89
  90         bool match(bits_t a, bits_t b)
  91         {
  92                 log_assert(int(a.bitdata.size()) == width);
  93                 log_assert(int(b.bitdata.size()) == width);
  94                 for (int i = 0; i < width; i++)
  95                         if (a[i] <= RTLIL::State::S1 && b[i] <= RTLIL::State::S1 && a[i] != b[i])
  96                                 return false;
  97                 return true;
  98         }
  99
 100         bool has_any(RTLIL::SigSpec sig)
 101         {
 102                 bits_t bits = sig2bits(sig);
 103                 for (auto &it : database)
 104                         if (match(it, bits))
 105                                 return true;
 106                 return false;
 107         }
 108
 109         bool has_all(RTLIL::SigSpec sig)
 110         {
 111                 bits_t bits = sig2bits(sig);
 112                 for (auto &it : database)
 113                         if (match(it, bits)) {
 114                                 for (int i = 0; i < width; i++)
 115                                         if (bits[i] > RTLIL::State::S1 && it[i] <= RTLIL::State::S1)
 116                                                 goto next_database_entry;
 117                                 return true;
 118         next_database_entry:;
 119                         }
 120                 return false;
 121         }
 122
 123         bool take(RTLIL::SigSpec sig)
 124         {
 125                 bool status = false;
 126                 bits_t bits = sig2bits(sig);
 127                 for (auto it = database.begin(); it != database.end();)
 128                         if (match(*it, bits)) {
 129                                 for (int i = 0; i < width; i++) {
 130                                         if ((*it)[i] != RTLIL::State::Sa || bits[i] == RTLIL::State::Sa)
 131                                                 continue;
 132                                         bits_t new_pattern;
 133                                         new_pattern.bitdata = it->bitdata;
 134                                         new_pattern[i] = bits[i] == RTLIL::State::S1 ? RTLIL::State::S0 : RTLIL::State::S1;
 135                                         database.insert(new_pattern);
 136                                 }
 137                                 it = database.erase(it);
 138                                 status = true;
 139                                 continue;
 140                         } else
 141                                 ++it;
 142                 return status;
 143         }
 144
 145         bool take_all()
 146         {
 147                 if (database.empty())
 148                         return false;
 149                 database.clear();
 150                 return true;
 151         }
 152
 153         bool empty()
 154         {
 155                 return database.empty();
 156         }
 157 };
 158
 159 YOSYS_NAMESPACE_END
 160
 161 #endif