From 0d7fd2585e8daec77870f19264644a204e0a8ed4 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sat, 13 Feb 2016 16:52:16 +0100 Subject: [PATCH] Added "int ceil_log2(int)" function --- backends/btor/btor.cc | 16 ++++++++-------- kernel/yosys.cc | 25 +++++++++++++++++++++++++ kernel/yosys.h | 1 + libs/ezsat/ezsat.cc | 24 +++++++++++++++++++++++- passes/fsm/fsm_recode.cc | 2 +- 5 files changed, 58 insertions(+), 10 deletions(-) diff --git a/backends/btor/btor.cc b/backends/btor/btor.cc index 26585f43b..465723f1a 100644 --- a/backends/btor/btor.cc +++ b/backends/btor/btor.cc @@ -260,7 +260,7 @@ struct BtorDumper if(it==std::end(line_ref)) { ++line_num; - int address_bits = ceil(log(memory->size)/log(2)); + int address_bits = ceil_log2(memory->size); str = stringf("%d array %d %d", line_num, memory->width, address_bits); line_ref[memory->name]=line_num; f << stringf("%s\n", str.c_str()); @@ -272,7 +272,7 @@ struct BtorDumper int dump_memory_next(const RTLIL::Memory* memory) { auto mem_it = line_ref.find(memory->name); - int address_bits = ceil(log(memory->size)/log(2)); + int address_bits = ceil_log2(memory->size); if(mem_it==std::end(line_ref)) { log("can not write next of a memory that is not dumped yet\n"); @@ -593,18 +593,18 @@ struct BtorDumper bool l1_signed = cell->parameters.at(RTLIL::IdString("\\A_SIGNED")).as_bool(); //bool l2_signed = cell->parameters.at(RTLIL::IdString("\\B_SIGNED")).as_bool(); int l1_width = cell->parameters.at(RTLIL::IdString("\\A_WIDTH")).as_int(); - l1_width = pow(2, ceil(log(l1_width)/log(2))); + l1_width = 1 << ceil_log2(l1_width); int l2_width = cell->parameters.at(RTLIL::IdString("\\B_WIDTH")).as_int(); - //log_assert(l2_width <= ceil(log(l1_width)/log(2)) ); + //log_assert(l2_width <= ceil_log2(l1_width)) ); int l1 = dump_sigspec(&cell->getPort(RTLIL::IdString("\\A")), l1_width); - int l2 = dump_sigspec(&cell->getPort(RTLIL::IdString("\\B")), ceil(log(l1_width)/log(2))); + int l2 = dump_sigspec(&cell->getPort(RTLIL::IdString("\\B")), ceil_log2(l1_width)); int cell_output = ++line_num; str = stringf ("%d %s %d %d %d", line_num, cell_type_translation.at(cell->type.str()).c_str(), l1_width, l1, l2); f << stringf("%s\n", str.c_str()); - if(l2_width > ceil(log(l1_width)/log(2))) + if(l2_width > ceil_log2(l1_width)) { - int extra_width = l2_width - ceil(log(l1_width)/log(2)); + int extra_width = l2_width - ceil_log2(l1_width); l2 = dump_sigspec(&cell->getPort(RTLIL::IdString("\\B")), l2_width); ++line_num; str = stringf ("%d slice %d %d %d %d;6", line_num, extra_width, l2, l2_width-1, l2_width-extra_width); @@ -821,7 +821,7 @@ struct BtorDumper ++line_num; str = cell->parameters.at(RTLIL::IdString("\\MEMID")).decode_string(); RTLIL::Memory *memory = module->memories.at(RTLIL::IdString(str.c_str())); - int address_bits = ceil(log(memory->size)/log(2)); + int address_bits = ceil_log2(memory->size); str = stringf("%d array %d %d", line_num, memory->width, address_bits); f << stringf("%s\n", str.c_str()); ++line_num; diff --git a/kernel/yosys.cc b/kernel/yosys.cc index 109918816..4bfbe3614 100644 --- a/kernel/yosys.cc +++ b/kernel/yosys.cc @@ -124,6 +124,31 @@ void yosys_banner() log("\n"); } +int ceil_log2(int x) +{ + if (x <= 0) + return 0; + + int y = (x & (x - 1)); + y = (y | -y) >> 31; + + x |= (x >> 1); + x |= (x >> 2); + x |= (x >> 4); + x |= (x >> 8); + x |= (x >> 16); + + x >>= 1; + x -= ((x >> 1) & 0x55555555); + x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); + x = (((x >> 4) + x) & 0x0f0f0f0f); + x += (x >> 8); + x += (x >> 16); + x = x & 0x0000003f; + + return x - y; +} + std::string stringf(const char *fmt, ...) { std::string string; diff --git a/kernel/yosys.h b/kernel/yosys.h index 92fa6ac19..c8bc46b65 100644 --- a/kernel/yosys.h +++ b/kernel/yosys.h @@ -222,6 +222,7 @@ extern bool memhasher_active; inline void memhasher() { if (memhasher_active) memhasher_do(); } void yosys_banner(); +int ceil_log2(int x); std::string stringf(const char *fmt, ...) YS_ATTRIBUTE(format(printf, 1, 2)); std::string vstringf(const char *fmt, va_list ap); int readsome(std::istream &f, char *s, int n); diff --git a/libs/ezsat/ezsat.cc b/libs/ezsat/ezsat.cc index da36fb74e..177bcd8a3 100644 --- a/libs/ezsat/ezsat.cc +++ b/libs/ezsat/ezsat.cc @@ -1337,6 +1337,28 @@ void ezSAT::printInternalState(FILE *f) const fprintf(f, "--8<-- snap --8<--\n"); } +static int clog2(int x) +{ + int y = (x & (x - 1)); + y = (y | -y) >> 31; + + x |= (x >> 1); + x |= (x >> 2); + x |= (x >> 4); + x |= (x >> 8); + x |= (x >> 16); + + x >>= 1; + x -= ((x >> 1) & 0x55555555); + x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); + x = (((x >> 4) + x) & 0x0f0f0f0f); + x += (x >> 8); + x += (x >> 16); + x = x & 0x0000003f; + + return x - y; +} + int ezSAT::onehot(const std::vector &vec, bool max_only) { // Mixed one-hot/binary encoding as described by Claessen in Sec. 4.2 of @@ -1350,7 +1372,7 @@ int ezSAT::onehot(const std::vector &vec, bool max_only) formula.push_back(expression(OpOr, vec)); // create binary vector - int num_bits = ceil(log2(vec.size())); + int num_bits = clog2(vec.size()); std::vector bits; for (int k = 0; k < num_bits; k++) bits.push_back(literal()); diff --git a/passes/fsm/fsm_recode.cc b/passes/fsm/fsm_recode.cc index aa1e99bef..a4b45295e 100644 --- a/passes/fsm/fsm_recode.cc +++ b/passes/fsm/fsm_recode.cc @@ -85,7 +85,7 @@ static void fsm_recode(RTLIL::Cell *cell, RTLIL::Module *module, FILE *fm_set_fs fsm_data.state_bits = fsm_data.state_table.size(); } else if (encoding == "binary") { - int new_num_state_bits = ceil(log2(fsm_data.state_table.size())); + int new_num_state_bits = ceil_log2(fsm_data.state_table.size()); if (fsm_data.state_bits == new_num_state_bits) { log(" existing encoding is already a packed binary encoding.\n"); return; -- 2.30.2