kernel/bitpattern.h

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
   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 struct BitPatternPool
  27 {
  28         int width;
  29         typedef std::vector<RTLIL::State> bits_t;
  30         std::set<bits_t> pool;
  31
  32         BitPatternPool(RTLIL::SigSpec sig)
  33         {
  34                 width = sig.size();
  35                 if (width > 0) {
  36                         std::vector<RTLIL::State> pattern(width);
  37                         sig.optimize();
  38                         for (int i = 0; i < width; i++) {
  39                                 RTLIL::SigSpec s = sig.extract(i, 1);
  40                                 s.optimize();
  41                                 assert(s.chunks().size() == 1);
  42                                 if (s.chunks()[0].wire == NULL && s.chunks()[0].data.bits[0] <= RTLIL::State::S1)
  43                                         pattern[i] = s.chunks()[0].data.bits[0];
  44                                 else
  45                                         pattern[i] = RTLIL::State::Sa;
  46                         }
  47                         pool.insert(pattern);
  48                 }
  49         }
  50
  51         BitPatternPool(int width)
  52         {
  53                 this->width = width;
  54                 if (width > 0) {
  55                         std::vector<RTLIL::State> pattern(width);
  56                         for (int i = 0; i < width; i++)
  57                                 pattern[i] = RTLIL::State::Sa;
  58                         pool.insert(pattern);
  59                 }
  60         }
  61
  62         bits_t sig2bits(RTLIL::SigSpec sig)
  63         {
  64                 sig.optimize();
  65                 assert(sig.is_fully_const());
  66                 assert(sig.chunks().size() == 1);
  67                 bits_t bits = sig.chunks()[0].data.bits;
  68                 for (auto &b : bits)
  69                         if (b > RTLIL::State::S1)
  70                                 b = RTLIL::State::Sa;
  71                 return bits;
  72         }
  73
  74         bool match(bits_t a, bits_t b)
  75         {
  76                 assert(int(a.size()) == width);
  77                 assert(int(b.size()) == width);
  78                 for (int i = 0; i < width; i++)
  79                         if (a[i] <= RTLIL::State::S1 && b[i] <= RTLIL::State::S1 && a[i] != b[i])
  80                                 return false;
  81                 return true;
  82         }
  83
  84         bool has_any(RTLIL::SigSpec sig)
  85         {
  86                 bits_t bits = sig2bits(sig);
  87                 for (auto &it : pool)
  88                         if (match(it, bits))
  89                                 return true;
  90                 return false;
  91         }
  92
  93         bool has_all(RTLIL::SigSpec sig)
  94         {
  95                 bits_t bits = sig2bits(sig);
  96                 for (auto &it : pool)
  97                         if (match(it, bits)) {
  98                                 for (int i = 0; i < width; i++)
  99                                         if (bits[i] > RTLIL::State::S1 && it[i] <= RTLIL::State::S1)
 100                                                 goto next_pool_entry;
 101                                 return true;
 102         next_pool_entry:;
 103                         }
 104                 return false;
 105         }
 106
 107         bool take(RTLIL::SigSpec sig)
 108         {
 109                 bool status = false;
 110                 bits_t bits = sig2bits(sig);
 111                 std::vector<bits_t> pattern_list;
 112                 for (auto &it : pool)
 113                         if (match(it, bits))
 114                                 pattern_list.push_back(it);
 115                 for (auto pattern : pattern_list) {
 116                         pool.erase(pattern);
 117                         for (int i = 0; i < width; i++) {
 118                                 if (pattern[i] != RTLIL::State::Sa || bits[i] == RTLIL::State::Sa)
 119                                         continue;
 120                                 bits_t new_pattern = pattern;
 121                                 new_pattern[i] = bits[i] == RTLIL::State::S1 ? RTLIL::State::S0 : RTLIL::State::S1;
 122                                 pool.insert(new_pattern);
 123                         }
 124                         status = true;
 125                 }
 126                 return status;
 127         }
 128
 129         bool take_all()
 130         {
 131                 if (pool.empty())
 132                         return false;
 133                 pool.clear();
 134                 return true;
 135         }
 136
 137         bool empty()
 138         {
 139                 return pool.empty();
 140         }
 141 };
 142
 143 #endif