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