kernel/calc.cc

   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 #include "kernel/rtlil.h"
  21 #include "libs/bigint/BigIntegerLibrary.hh"
  22 #include <assert.h>
  23
  24 static BigInteger const2big(const RTLIL::Const &val, bool as_signed, int &undef_bit_pos)
  25 {
  26         BigInteger result = 0, this_bit = 1;
  27         for (size_t i = 0; i < val.bits.size(); i++) {
  28                 if (val.bits[i] == RTLIL::State::S1) {
  29                         if (as_signed && i+1 == val.bits.size())
  30                                 result -= this_bit;
  31                         else
  32                                 result += this_bit;
  33                 }
  34                 else if (val.bits[i] != RTLIL::State::S0) {
  35                         if (undef_bit_pos < 0)
  36                                 undef_bit_pos = i;
  37                 }
  38                 this_bit *= 2;
  39         }
  40         return result;
  41 }
  42
  43 static RTLIL::Const big2const(const BigInteger &val, int result_len, int undef_bit_pos)
  44 {
  45         BigUnsigned mag = val.getMagnitude();
  46         RTLIL::Const result(0, result_len);
  47
  48         if (!mag.isZero())
  49         {
  50                 if (val.getSign() < 0)
  51                 {
  52                         mag--;
  53                         for (int i = 0; i < result_len; i++)
  54                                 result.bits[i] = mag.getBit(i) ? RTLIL::State::S0 : RTLIL::State::S1;
  55                 }
  56                 else
  57                 {
  58                         for (int i = 0; i < result_len; i++)
  59                                 result.bits[i] = mag.getBit(i) ? RTLIL::State::S1 : RTLIL::State::S0;
  60                 }
  61         }
  62
  63         if (undef_bit_pos >= 0)
  64                 for (int i = undef_bit_pos; i < result_len; i++)
  65                         result.bits[i] = RTLIL::State::Sx;
  66
  67         return result;
  68 }
  69
  70 static RTLIL::State logic_and(RTLIL::State a, RTLIL::State b)
  71 {
  72         if (a == RTLIL::State::S0) return RTLIL::State::S0;
  73         if (b == RTLIL::State::S0) return RTLIL::State::S0;
  74         if (a != RTLIL::State::S1) return RTLIL::State::Sx;
  75         if (b != RTLIL::State::S1) return RTLIL::State::Sx;
  76         return RTLIL::State::S1;
  77 }
  78
  79 static RTLIL::State logic_or(RTLIL::State a, RTLIL::State b)
  80 {
  81         if (a == RTLIL::State::S1) return RTLIL::State::S1;
  82         if (b == RTLIL::State::S1) return RTLIL::State::S1;
  83         if (a != RTLIL::State::S0) return RTLIL::State::Sx;
  84         if (b != RTLIL::State::S0) return RTLIL::State::Sx;
  85         return RTLIL::State::S0;
  86 }
  87
  88 static RTLIL::State logic_xor(RTLIL::State a, RTLIL::State b)
  89 {
  90         if (a != RTLIL::State::S0 && a != RTLIL::State::S1) return RTLIL::State::Sx;
  91         if (b != RTLIL::State::S0 && b != RTLIL::State::S1) return RTLIL::State::Sx;
  92         return a != b ? RTLIL::State::S1 : RTLIL::State::S0;
  93 }
  94
  95 static RTLIL::State logic_xnor(RTLIL::State a, RTLIL::State b)
  96 {
  97         if (a != RTLIL::State::S0 && a != RTLIL::State::S1) return RTLIL::State::Sx;
  98         if (b != RTLIL::State::S0 && b != RTLIL::State::S1) return RTLIL::State::Sx;
  99         return a == b ? RTLIL::State::S1 : RTLIL::State::S0;
 100 }
 101
 102 RTLIL::Const RTLIL::const_not(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 103 {
 104         if (result_len < 0)
 105                 result_len = arg1.bits.size();
 106
 107         RTLIL::Const arg1_ext = arg1;
 108         while (int(arg1_ext.bits.size()) < result_len)
 109                 arg1_ext.bits.push_back(signed1 && arg1_ext.bits.size() ? arg1_ext.bits.back() : RTLIL::State::S0);
 110
 111         RTLIL::Const result(RTLIL::State::Sx, result_len);
 112         for (size_t i = 0; i < size_t(result_len); i++) {
 113                 if (i >= arg1_ext.bits.size())
 114                         result.bits[i] = RTLIL::State::S0;
 115                 else if (arg1_ext.bits[i] == RTLIL::State::S0)
 116                         result.bits[i] = RTLIL::State::S1;
 117                 else if (arg1_ext.bits[i] == RTLIL::State::S1)
 118                         result.bits[i] = RTLIL::State::S0;
 119         }
 120
 121         return result;
 122 }
 123
 124 static RTLIL::Const logic_wrapper(RTLIL::State(*logic_func)(RTLIL::State, RTLIL::State),
 125                 RTLIL::Const arg1, RTLIL::Const arg2, bool signed1, bool signed2, int result_len = -1)
 126 {
 127         if (result_len < 0)
 128                 result_len = std::max(arg1.bits.size(), arg2.bits.size());
 129
 130         while (int(arg1.bits.size()) < result_len)
 131                 arg1.bits.push_back(signed1 && arg1.bits.size() ? arg1.bits.back() : RTLIL::State::S0);
 132
 133         while (int(arg2.bits.size()) < result_len)
 134                 arg2.bits.push_back(signed2 && arg2.bits.size() ? arg2.bits.back() : RTLIL::State::S0);
 135
 136         RTLIL::Const result(RTLIL::State::Sx, result_len);
 137         for (size_t i = 0; i < size_t(result_len); i++) {
 138                 RTLIL::State a = i < arg1.bits.size() ? arg1.bits[i] : RTLIL::State::S0;
 139                 RTLIL::State b = i < arg2.bits.size() ? arg2.bits[i] : RTLIL::State::S0;
 140                 result.bits[i] = logic_func(a, b);
 141         }
 142
 143         return result;
 144 }
 145
 146 RTLIL::Const RTLIL::const_and(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 147 {
 148         return logic_wrapper(logic_and, arg1, arg2, signed1, signed2, result_len);
 149 }
 150
 151 RTLIL::Const RTLIL::const_or(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 152 {
 153         return logic_wrapper(logic_or, arg1, arg2, signed1, signed2, result_len);
 154 }
 155
 156 RTLIL::Const RTLIL::const_xor(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 157 {
 158         return logic_wrapper(logic_xor, arg1, arg2, signed1, signed2, result_len);
 159 }
 160
 161 RTLIL::Const RTLIL::const_xnor(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 162 {
 163         return logic_wrapper(logic_xnor, arg1, arg2, signed1, signed2, result_len);
 164 }
 165
 166 static RTLIL::Const logic_reduce_wrapper(RTLIL::State initial, RTLIL::State(*logic_func)(RTLIL::State, RTLIL::State), const RTLIL::Const &arg1)
 167 {
 168         RTLIL::State temp = initial;
 169
 170         for (size_t i = 0; i < arg1.bits.size(); i++)
 171                 temp = logic_func(temp, arg1.bits[i]);
 172
 173         return RTLIL::Const(temp);
 174 }
 175
 176 RTLIL::Const RTLIL::const_reduce_and(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int)
 177 {
 178         return logic_reduce_wrapper(RTLIL::State::S1, logic_and, arg1);
 179 }
 180
 181 RTLIL::Const RTLIL::const_reduce_or(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int)
 182 {
 183         return logic_reduce_wrapper(RTLIL::State::S0, logic_or, arg1);
 184 }
 185
 186 RTLIL::Const RTLIL::const_reduce_xor(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int)
 187 {
 188         return logic_reduce_wrapper(RTLIL::State::S0, logic_xor, arg1);
 189 }
 190
 191 RTLIL::Const RTLIL::const_reduce_xnor(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int)
 192 {
 193         RTLIL::Const not_y = logic_reduce_wrapper(RTLIL::State::S0, logic_xor, arg1);
 194         if (not_y.bits.front() == RTLIL::State::S0) return RTLIL::State::S1;
 195         if (not_y.bits.front() == RTLIL::State::S1) return RTLIL::State::S0;
 196         return RTLIL::State::Sx;
 197 }
 198
 199 RTLIL::Const RTLIL::const_reduce_bool(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int)
 200 {
 201         return logic_reduce_wrapper(RTLIL::State::S0, logic_or, arg1);
 202 }
 203
 204 RTLIL::Const RTLIL::const_logic_not(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int)
 205 {
 206         int undef_bit_pos_a = -1;
 207         BigInteger a = const2big(arg1, signed1, undef_bit_pos_a);
 208
 209         if (a.isZero()) {
 210                 if (undef_bit_pos_a >= 0)
 211                         return RTLIL::Const(RTLIL::State::Sx);
 212                 return RTLIL::Const(RTLIL::State::S1);
 213         }
 214
 215         return RTLIL::Const(RTLIL::State::S0);
 216 }
 217
 218 RTLIL::Const RTLIL::const_logic_and(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int)
 219 {
 220         int undef_bit_pos_a = -1, undef_bit_pos_b = -1;
 221         BigInteger a = const2big(arg1, signed1, undef_bit_pos_a);
 222         BigInteger b = const2big(arg2, signed2, undef_bit_pos_b);
 223
 224         if (a.isZero() || b.isZero()) {
 225                 if (undef_bit_pos_a >= 0 && undef_bit_pos_b >= 0)
 226                         return RTLIL::Const(RTLIL::State::Sx);
 227                 return RTLIL::Const(RTLIL::State::S0);
 228         }
 229
 230         return RTLIL::Const(RTLIL::State::S1);
 231 }
 232
 233 RTLIL::Const RTLIL::const_logic_or(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int)
 234 {
 235         int undef_bit_pos_a = -1, undef_bit_pos_b = -1;
 236         BigInteger a = const2big(arg1, signed1, undef_bit_pos_a);
 237         BigInteger b = const2big(arg2, signed2, undef_bit_pos_b);
 238
 239         if (a.isZero() && b.isZero()) {
 240                 if (undef_bit_pos_a >= 0 || undef_bit_pos_b >= 0)
 241                         return RTLIL::Const(RTLIL::State::Sx);
 242                 return RTLIL::Const(RTLIL::State::S0);
 243         }
 244
 245         return RTLIL::Const(RTLIL::State::S1);
 246 }
 247
 248 static RTLIL::Const const_shift(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool sign_ext, int direction, int result_len)
 249 {
 250         int undef_bit_pos = -1;
 251         BigInteger offset = const2big(arg2, false, undef_bit_pos) * direction;
 252
 253         if (result_len < 0)
 254                 result_len = arg1.bits.size();
 255
 256         RTLIL::Const result(RTLIL::State::Sx, result_len);
 257         if (undef_bit_pos >= 0)
 258                 return result;
 259
 260         for (int i = 0; i < result_len; i++) {
 261                 BigInteger pos = BigInteger(i) + offset;
 262                 if (pos < 0)
 263                         result.bits[i] = RTLIL::State::S0;
 264                 else if (pos >= arg1.bits.size())
 265                         result.bits[i] = sign_ext ? arg1.bits.back() : RTLIL::State::S0;
 266                 else
 267                         result.bits[i] = arg1.bits[pos.toInt()];
 268         }
 269
 270         return result;
 271 }
 272
 273 RTLIL::Const RTLIL::const_shl(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool, int result_len)
 274 {
 275         RTLIL::Const arg1_ext = arg1;
 276         while (int(arg1_ext.bits.size()) < result_len)
 277                 arg1_ext.bits.push_back(signed1 && arg1_ext.bits.size() ? arg1_ext.bits.back() : RTLIL::State::S0);
 278         return const_shift(arg1_ext, arg2, false, -1, result_len);
 279 }
 280
 281 RTLIL::Const RTLIL::const_shr(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool, int result_len)
 282 {
 283         RTLIL::Const arg1_ext = arg1;
 284         while (int(arg1_ext.bits.size()) < result_len)
 285                 arg1_ext.bits.push_back(signed1 && arg1_ext.bits.size() ? arg1_ext.bits.back() : RTLIL::State::S0);
 286         return const_shift(arg1_ext, arg2, false, +1, result_len);
 287 }
 288
 289 RTLIL::Const RTLIL::const_sshl(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool, bool, int result_len)
 290 {
 291         return const_shift(arg1, arg2, true, -1, result_len);
 292 }
 293
 294 RTLIL::Const RTLIL::const_sshr(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool, bool, int result_len)
 295 {
 296         return const_shift(arg1, arg2, true, +1, result_len);
 297 }
 298
 299 RTLIL::Const RTLIL::const_lt(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int)
 300 {
 301         int undef_bit_pos = -1;
 302         bool y = const2big(arg1, signed1, undef_bit_pos) < const2big(arg2, signed2, undef_bit_pos);
 303         return RTLIL::Const(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 304 }
 305
 306 RTLIL::Const RTLIL::const_le(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int)
 307 {
 308         int undef_bit_pos = -1;
 309         bool y = const2big(arg1, signed1, undef_bit_pos) <= const2big(arg2, signed2, undef_bit_pos);
 310         return RTLIL::Const(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 311 }
 312
 313 RTLIL::Const RTLIL::const_eq(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int)
 314 {
 315         int undef_bit_pos = -1;
 316         bool y = const2big(arg1, signed1, undef_bit_pos) == const2big(arg2, signed2, undef_bit_pos);
 317         return RTLIL::Const(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 318 }
 319
 320 RTLIL::Const RTLIL::const_ne(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int)
 321 {
 322         int undef_bit_pos = -1;
 323         bool y = const2big(arg1, signed1, undef_bit_pos) != const2big(arg2, signed2, undef_bit_pos);
 324         return RTLIL::Const(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 325 }
 326
 327 RTLIL::Const RTLIL::const_ge(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int)
 328 {
 329         int undef_bit_pos = -1;
 330         bool y = const2big(arg1, signed1, undef_bit_pos) >= const2big(arg2, signed2, undef_bit_pos);
 331         return RTLIL::Const(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 332 }
 333
 334 RTLIL::Const RTLIL::const_gt(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int)
 335 {
 336         int undef_bit_pos = -1;
 337         bool y = const2big(arg1, signed1, undef_bit_pos) > const2big(arg2, signed2, undef_bit_pos);
 338         return RTLIL::Const(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 339 }
 340
 341 RTLIL::Const RTLIL::const_add(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 342 {
 343         int undef_bit_pos = -1;
 344         BigInteger y = const2big(arg1, signed1, undef_bit_pos) + const2big(arg2, signed2, undef_bit_pos);
 345         return big2const(y, result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), undef_bit_pos);
 346 }
 347
 348 RTLIL::Const RTLIL::const_sub(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 349 {
 350         int undef_bit_pos = -1;
 351         BigInteger y = const2big(arg1, signed1, undef_bit_pos) - const2big(arg2, signed2, undef_bit_pos);
 352         return big2const(y, result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), undef_bit_pos);
 353 }
 354
 355 RTLIL::Const RTLIL::const_mul(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 356 {
 357         int undef_bit_pos = -1;
 358         BigInteger y = const2big(arg1, signed1, undef_bit_pos) * const2big(arg2, signed2, undef_bit_pos);
 359         return big2const(y, result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), std::min(undef_bit_pos, 0));
 360 }
 361
 362 RTLIL::Const RTLIL::const_div(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 363 {
 364         int undef_bit_pos = -1;
 365         BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 366         BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 367         if (b.isZero())
 368                 return RTLIL::Const(RTLIL::State::Sx, result_len);
 369         bool result_neg = (a.getSign() == BigInteger::negative) != (b.getSign() == BigInteger::negative);
 370         a = a.getSign() == BigInteger::negative ? -a : a;
 371         b = b.getSign() == BigInteger::negative ? -b : b;
 372         return big2const(result_neg ? -(a / b) : (a / b), result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), std::min(undef_bit_pos, 0));
 373 }
 374
 375 RTLIL::Const RTLIL::const_mod(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 376 {
 377         int undef_bit_pos = -1;
 378         BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 379         BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 380         if (b.isZero())
 381                 return RTLIL::Const(RTLIL::State::Sx, result_len);
 382         bool result_neg = a.getSign() == BigInteger::negative;
 383         a = a.getSign() == BigInteger::negative ? -a : a;
 384         b = b.getSign() == BigInteger::negative ? -b : b;
 385         return big2const(result_neg ? -(a % b) : (a % b), result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), std::min(undef_bit_pos, 0));
 386 }
 387
 388 RTLIL::Const RTLIL::const_pow(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 389 {
 390         int undef_bit_pos = -1;
 391
 392         BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 393         BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 394         BigInteger y = 1;
 395
 396         if (b < 0 || a == 0) {
 397                 y = 0;
 398         } else {
 399                 while (b > 0) {
 400                         y = y * a;
 401                         if (y.getLength() > 0x10000) {
 402                                 undef_bit_pos = 0;
 403                                 break;
 404                         }
 405                         b--;
 406                 }
 407         }
 408
 409         return big2const(y, result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), std::min(undef_bit_pos, 0));
 410 }
 411
 412 RTLIL::Const RTLIL::const_pos(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 413 {
 414         RTLIL::Const arg1_ext = arg1;
 415         while (int(arg1_ext.bits.size()) < result_len)
 416                 arg1_ext.bits.push_back(signed1 && arg1_ext.bits.size() ? arg1_ext.bits.back() : RTLIL::State::S0);
 417
 418         RTLIL::Const zero(RTLIL::State::S0, 1);
 419         return RTLIL::const_add(zero, arg1_ext, false, signed1, result_len);
 420 }
 421
 422 RTLIL::Const RTLIL::const_neg(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 423 {
 424         RTLIL::Const arg1_ext = arg1;
 425         while (int(arg1_ext.bits.size()) < result_len)
 426                 arg1_ext.bits.push_back(signed1 && arg1_ext.bits.size() ? arg1_ext.bits.back() : RTLIL::State::S0);
 427
 428         RTLIL::Const zero(RTLIL::State::S0, 1);
 429         return RTLIL::const_sub(zero, arg1_ext, false, signed1, result_len);
 430 }
 431