kernel/calc.cc

   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 // [[CITE]] Power-Modulus Algorithm
  21 // Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C,
  22 // Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4, page 244
  23
  24 #include "kernel/yosys.h"
  25 #include "libs/bigint/BigIntegerLibrary.hh"
  26
  27 YOSYS_NAMESPACE_BEGIN
  28
  29 static void extend_u0(RTLIL::Const &arg, int width, bool is_signed)
  30 {
  31         RTLIL::State padding = RTLIL::State::S0;
  32
  33         if (arg.bits.size() > 0 && is_signed)
  34                 padding = arg.bits.back();
  35
  36         while (int(arg.bits.size()) < width)
  37                 arg.bits.push_back(padding);
  38
  39         arg.bits.resize(width);
  40 }
  41
  42 static BigInteger const2big(const RTLIL::Const &val, bool as_signed, int &undef_bit_pos)
  43 {
  44         BigUnsigned mag;
  45
  46         BigInteger::Sign sign = BigInteger::positive;
  47         State inv_sign_bit = RTLIL::State::S1;
  48         size_t num_bits = val.bits.size();
  49
  50         if (as_signed && num_bits && val.bits[num_bits-1] == RTLIL::State::S1) {
  51                 inv_sign_bit = RTLIL::State::S0;
  52                 sign = BigInteger::negative;
  53                 num_bits--;
  54         }
  55
  56         for (size_t i = 0; i < num_bits; i++)
  57                 if (val.bits[i] == RTLIL::State::S0 || val.bits[i] == RTLIL::State::S1)
  58                         mag.setBit(i, val.bits[i] == inv_sign_bit);
  59                 else if (undef_bit_pos < 0)
  60                         undef_bit_pos = i;
  61
  62         if (sign == BigInteger::negative)
  63                 mag += 1;
  64
  65         return BigInteger(mag, sign);
  66 }
  67
  68 static RTLIL::Const big2const(const BigInteger &val, int result_len, int undef_bit_pos)
  69 {
  70         if (undef_bit_pos >= 0)
  71                 return RTLIL::Const(RTLIL::State::Sx, result_len);
  72
  73         BigUnsigned mag = val.getMagnitude();
  74         RTLIL::Const result(0, result_len);
  75
  76         if (!mag.isZero())
  77         {
  78                 if (val.getSign() < 0)
  79                 {
  80                         mag--;
  81                         for (int i = 0; i < result_len; i++)
  82                                 result.bits[i] = mag.getBit(i) ? RTLIL::State::S0 : RTLIL::State::S1;
  83                 }
  84                 else
  85                 {
  86                         for (int i = 0; i < result_len; i++)
  87                                 result.bits[i] = mag.getBit(i) ? RTLIL::State::S1 : RTLIL::State::S0;
  88                 }
  89         }
  90
  91 #if 0
  92         if (undef_bit_pos >= 0)
  93                 for (int i = undef_bit_pos; i < result_len; i++)
  94                         result.bits[i] = RTLIL::State::Sx;
  95 #endif
  96
  97         return result;
  98 }
  99
 100 static RTLIL::State logic_and(RTLIL::State a, RTLIL::State b)
 101 {
 102         if (a == RTLIL::State::S0) return RTLIL::State::S0;
 103         if (b == RTLIL::State::S0) return RTLIL::State::S0;
 104         if (a != RTLIL::State::S1) return RTLIL::State::Sx;
 105         if (b != RTLIL::State::S1) return RTLIL::State::Sx;
 106         return RTLIL::State::S1;
 107 }
 108
 109 static RTLIL::State logic_or(RTLIL::State a, RTLIL::State b)
 110 {
 111         if (a == RTLIL::State::S1) return RTLIL::State::S1;
 112         if (b == RTLIL::State::S1) return RTLIL::State::S1;
 113         if (a != RTLIL::State::S0) return RTLIL::State::Sx;
 114         if (b != RTLIL::State::S0) return RTLIL::State::Sx;
 115         return RTLIL::State::S0;
 116 }
 117
 118 static RTLIL::State logic_xor(RTLIL::State a, RTLIL::State b)
 119 {
 120         if (a != RTLIL::State::S0 && a != RTLIL::State::S1) return RTLIL::State::Sx;
 121         if (b != RTLIL::State::S0 && b != RTLIL::State::S1) return RTLIL::State::Sx;
 122         return a != b ? RTLIL::State::S1 : RTLIL::State::S0;
 123 }
 124
 125 static RTLIL::State logic_xnor(RTLIL::State a, RTLIL::State b)
 126 {
 127         if (a != RTLIL::State::S0 && a != RTLIL::State::S1) return RTLIL::State::Sx;
 128         if (b != RTLIL::State::S0 && b != RTLIL::State::S1) return RTLIL::State::Sx;
 129         return a == b ? RTLIL::State::S1 : RTLIL::State::S0;
 130 }
 131
 132 RTLIL::Const RTLIL::const_not(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 133 {
 134         if (result_len < 0)
 135                 result_len = arg1.bits.size();
 136
 137         RTLIL::Const arg1_ext = arg1;
 138         extend_u0(arg1_ext, result_len, signed1);
 139
 140         RTLIL::Const result(RTLIL::State::Sx, result_len);
 141         for (size_t i = 0; i < size_t(result_len); i++) {
 142                 if (i >= arg1_ext.bits.size())
 143                         result.bits[i] = RTLIL::State::S0;
 144                 else if (arg1_ext.bits[i] == RTLIL::State::S0)
 145                         result.bits[i] = RTLIL::State::S1;
 146                 else if (arg1_ext.bits[i] == RTLIL::State::S1)
 147                         result.bits[i] = RTLIL::State::S0;
 148         }
 149
 150         return result;
 151 }
 152
 153 static RTLIL::Const logic_wrapper(RTLIL::State(*logic_func)(RTLIL::State, RTLIL::State),
 154                 RTLIL::Const arg1, RTLIL::Const arg2, bool signed1, bool signed2, int result_len = -1)
 155 {
 156         if (result_len < 0)
 157                 result_len = max(arg1.bits.size(), arg2.bits.size());
 158
 159         extend_u0(arg1, result_len, signed1);
 160         extend_u0(arg2, result_len, signed2);
 161
 162         RTLIL::Const result(RTLIL::State::Sx, result_len);
 163         for (size_t i = 0; i < size_t(result_len); i++) {
 164                 RTLIL::State a = i < arg1.bits.size() ? arg1.bits[i] : RTLIL::State::S0;
 165                 RTLIL::State b = i < arg2.bits.size() ? arg2.bits[i] : RTLIL::State::S0;
 166                 result.bits[i] = logic_func(a, b);
 167         }
 168
 169         return result;
 170 }
 171
 172 RTLIL::Const RTLIL::const_and(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 173 {
 174         return logic_wrapper(logic_and, arg1, arg2, signed1, signed2, result_len);
 175 }
 176
 177 RTLIL::Const RTLIL::const_or(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 178 {
 179         return logic_wrapper(logic_or, arg1, arg2, signed1, signed2, result_len);
 180 }
 181
 182 RTLIL::Const RTLIL::const_xor(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 183 {
 184         return logic_wrapper(logic_xor, arg1, arg2, signed1, signed2, result_len);
 185 }
 186
 187 RTLIL::Const RTLIL::const_xnor(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 188 {
 189         return logic_wrapper(logic_xnor, arg1, arg2, signed1, signed2, result_len);
 190 }
 191
 192 static RTLIL::Const logic_reduce_wrapper(RTLIL::State initial, RTLIL::State(*logic_func)(RTLIL::State, RTLIL::State), const RTLIL::Const &arg1, int result_len)
 193 {
 194         RTLIL::State temp = initial;
 195
 196         for (size_t i = 0; i < arg1.bits.size(); i++)
 197                 temp = logic_func(temp, arg1.bits[i]);
 198
 199         RTLIL::Const result(temp);
 200         while (int(result.bits.size()) < result_len)
 201                 result.bits.push_back(RTLIL::State::S0);
 202         return result;
 203 }
 204
 205 RTLIL::Const RTLIL::const_reduce_and(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int result_len)
 206 {
 207         return logic_reduce_wrapper(RTLIL::State::S1, logic_and, arg1, result_len);
 208 }
 209
 210 RTLIL::Const RTLIL::const_reduce_or(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int result_len)
 211 {
 212         return logic_reduce_wrapper(RTLIL::State::S0, logic_or, arg1, result_len);
 213 }
 214
 215 RTLIL::Const RTLIL::const_reduce_xor(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int result_len)
 216 {
 217         return logic_reduce_wrapper(RTLIL::State::S0, logic_xor, arg1, result_len);
 218 }
 219
 220 RTLIL::Const RTLIL::const_reduce_xnor(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int result_len)
 221 {
 222         RTLIL::Const buffer = logic_reduce_wrapper(RTLIL::State::S0, logic_xor, arg1, result_len);
 223         if (!buffer.bits.empty()) {
 224                 if (buffer.bits.front() == RTLIL::State::S0)
 225                         buffer.bits.front() = RTLIL::State::S1;
 226                 else if (buffer.bits.front() == RTLIL::State::S1)
 227                         buffer.bits.front() = RTLIL::State::S0;
 228         }
 229         return buffer;
 230 }
 231
 232 RTLIL::Const RTLIL::const_reduce_bool(const RTLIL::Const &arg1, const RTLIL::Const&, bool, bool, int result_len)
 233 {
 234         return logic_reduce_wrapper(RTLIL::State::S0, logic_or, arg1, result_len);
 235 }
 236
 237 RTLIL::Const RTLIL::const_logic_not(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 238 {
 239         int undef_bit_pos_a = -1;
 240         BigInteger a = const2big(arg1, signed1, undef_bit_pos_a);
 241         RTLIL::Const result(a.isZero() ? undef_bit_pos_a >= 0 ? RTLIL::State::Sx : RTLIL::State::S1 : RTLIL::State::S0);
 242
 243         while (int(result.bits.size()) < result_len)
 244                 result.bits.push_back(RTLIL::State::S0);
 245         return result;
 246 }
 247
 248 RTLIL::Const RTLIL::const_logic_and(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 249 {
 250         int undef_bit_pos_a = -1, undef_bit_pos_b = -1;
 251         BigInteger a = const2big(arg1, signed1, undef_bit_pos_a);
 252         BigInteger b = const2big(arg2, signed2, undef_bit_pos_b);
 253
 254         RTLIL::State bit_a = a.isZero() ? undef_bit_pos_a >= 0 ? RTLIL::State::Sx : RTLIL::State::S0 : RTLIL::State::S1;
 255         RTLIL::State bit_b = b.isZero() ? undef_bit_pos_b >= 0 ? RTLIL::State::Sx : RTLIL::State::S0 : RTLIL::State::S1;
 256         RTLIL::Const result(logic_and(bit_a, bit_b));
 257
 258         while (int(result.bits.size()) < result_len)
 259                 result.bits.push_back(RTLIL::State::S0);
 260         return result;
 261 }
 262
 263 RTLIL::Const RTLIL::const_logic_or(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 264 {
 265         int undef_bit_pos_a = -1, undef_bit_pos_b = -1;
 266         BigInteger a = const2big(arg1, signed1, undef_bit_pos_a);
 267         BigInteger b = const2big(arg2, signed2, undef_bit_pos_b);
 268
 269         RTLIL::State bit_a = a.isZero() ? undef_bit_pos_a >= 0 ? RTLIL::State::Sx : RTLIL::State::S0 : RTLIL::State::S1;
 270         RTLIL::State bit_b = b.isZero() ? undef_bit_pos_b >= 0 ? RTLIL::State::Sx : RTLIL::State::S0 : RTLIL::State::S1;
 271         RTLIL::Const result(logic_or(bit_a, bit_b));
 272
 273         while (int(result.bits.size()) < result_len)
 274                 result.bits.push_back(RTLIL::State::S0);
 275         return result;
 276 }
 277
 278 // Shift `arg1` by `arg2` bits.
 279 // If `direction` is +1, `arg1` is shifted right by `arg2` bits; if `direction` is -1, `arg1` is shifted left by `arg2` bits.
 280 // If `signed2` is true, `arg2` is interpreted as a signed integer; a negative `arg2` will cause a shift in the opposite direction.
 281 // Any required bits outside the bounds of `arg1` are padded with `vacant_bits` unless `sign_ext` is true, in which case any bits outside the left
 282 // bounds are filled with the leftmost bit of `arg1` (arithmetic shift).
 283 static RTLIL::Const const_shift_worker(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool sign_ext, bool signed2, int direction, int result_len, RTLIL::State vacant_bits = RTLIL::State::S0)
 284 {
 285         int undef_bit_pos = -1;
 286         BigInteger offset = const2big(arg2, signed2, undef_bit_pos) * direction;
 287
 288         if (result_len < 0)
 289                 result_len = arg1.bits.size();
 290
 291         RTLIL::Const result(RTLIL::State::Sx, result_len);
 292         if (undef_bit_pos >= 0)
 293                 return result;
 294
 295         for (int i = 0; i < result_len; i++) {
 296                 BigInteger pos = BigInteger(i) + offset;
 297                 if (pos < 0)
 298                         result.bits[i] = vacant_bits;
 299                 else if (pos >= BigInteger(int(arg1.bits.size())))
 300                         result.bits[i] = sign_ext ? arg1.bits.back() : vacant_bits;
 301                 else
 302                         result.bits[i] = arg1.bits[pos.toInt()];
 303         }
 304
 305         return result;
 306 }
 307
 308 RTLIL::Const RTLIL::const_shl(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool, int result_len)
 309 {
 310         RTLIL::Const arg1_ext = arg1;
 311         extend_u0(arg1_ext, result_len, signed1);
 312         return const_shift_worker(arg1_ext, arg2, false, false, -1, result_len);
 313 }
 314
 315 RTLIL::Const RTLIL::const_shr(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool, int result_len)
 316 {
 317         RTLIL::Const arg1_ext = arg1;
 318         extend_u0(arg1_ext, max(result_len, GetSize(arg1)), signed1);
 319         return const_shift_worker(arg1_ext, arg2, false, false, +1, result_len);
 320 }
 321
 322 RTLIL::Const RTLIL::const_sshl(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool, int result_len)
 323 {
 324         return const_shift_worker(arg1, arg2, signed1, false, -1, result_len);
 325 }
 326
 327 RTLIL::Const RTLIL::const_sshr(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool, int result_len)
 328 {
 329         return const_shift_worker(arg1, arg2, signed1, false, +1, result_len);
 330 }
 331
 332 RTLIL::Const RTLIL::const_shift(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 333 {
 334         RTLIL::Const arg1_ext = arg1;
 335         extend_u0(arg1_ext, max(result_len, GetSize(arg1)), signed1);
 336         return const_shift_worker(arg1_ext, arg2, false, signed2, +1, result_len);
 337 }
 338
 339 RTLIL::Const RTLIL::const_shiftx(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool, bool signed2, int result_len)
 340 {
 341         return const_shift_worker(arg1, arg2, false, signed2, +1, result_len, RTLIL::State::Sx);
 342 }
 343
 344 RTLIL::Const RTLIL::const_lt(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 345 {
 346         int undef_bit_pos = -1;
 347         bool y = const2big(arg1, signed1, undef_bit_pos) < const2big(arg2, signed2, undef_bit_pos);
 348         RTLIL::Const result(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 349
 350         while (int(result.bits.size()) < result_len)
 351                 result.bits.push_back(RTLIL::State::S0);
 352         return result;
 353 }
 354
 355 RTLIL::Const RTLIL::const_le(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 356 {
 357         int undef_bit_pos = -1;
 358         bool y = const2big(arg1, signed1, undef_bit_pos) <= const2big(arg2, signed2, undef_bit_pos);
 359         RTLIL::Const result(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 360
 361         while (int(result.bits.size()) < result_len)
 362                 result.bits.push_back(RTLIL::State::S0);
 363         return result;
 364 }
 365
 366 RTLIL::Const RTLIL::const_eq(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 367 {
 368         RTLIL::Const arg1_ext = arg1;
 369         RTLIL::Const arg2_ext = arg2;
 370         RTLIL::Const result(RTLIL::State::S0, result_len);
 371
 372         int width = max(arg1_ext.bits.size(), arg2_ext.bits.size());
 373         extend_u0(arg1_ext, width, signed1 && signed2);
 374         extend_u0(arg2_ext, width, signed1 && signed2);
 375
 376         RTLIL::State matched_status = RTLIL::State::S1;
 377         for (size_t i = 0; i < arg1_ext.bits.size(); i++) {
 378                 if (arg1_ext.bits.at(i) == RTLIL::State::S0 && arg2_ext.bits.at(i) == RTLIL::State::S1)
 379                         return result;
 380                 if (arg1_ext.bits.at(i) == RTLIL::State::S1 && arg2_ext.bits.at(i) == RTLIL::State::S0)
 381                         return result;
 382                 if (arg1_ext.bits.at(i) > RTLIL::State::S1 || arg2_ext.bits.at(i) > RTLIL::State::S1)
 383                         matched_status = RTLIL::State::Sx;
 384         }
 385
 386         result.bits.front() = matched_status;
 387         return result;
 388 }
 389
 390 RTLIL::Const RTLIL::const_ne(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 391 {
 392         RTLIL::Const result = RTLIL::const_eq(arg1, arg2, signed1, signed2, result_len);
 393         if (result.bits.front() == RTLIL::State::S0)
 394                 result.bits.front() = RTLIL::State::S1;
 395         else if (result.bits.front() == RTLIL::State::S1)
 396                 result.bits.front() = RTLIL::State::S0;
 397         return result;
 398 }
 399
 400 RTLIL::Const RTLIL::const_eqx(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 401 {
 402         RTLIL::Const arg1_ext = arg1;
 403         RTLIL::Const arg2_ext = arg2;
 404         RTLIL::Const result(RTLIL::State::S0, result_len);
 405
 406         int width = max(arg1_ext.bits.size(), arg2_ext.bits.size());
 407         extend_u0(arg1_ext, width, signed1 && signed2);
 408         extend_u0(arg2_ext, width, signed1 && signed2);
 409
 410         for (size_t i = 0; i < arg1_ext.bits.size(); i++) {
 411                 if (arg1_ext.bits.at(i) != arg2_ext.bits.at(i))
 412                         return result;
 413         }
 414
 415         result.bits.front() = RTLIL::State::S1;
 416         return result;
 417 }
 418
 419 RTLIL::Const RTLIL::const_nex(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 420 {
 421         RTLIL::Const result = RTLIL::const_eqx(arg1, arg2, signed1, signed2, result_len);
 422         if (result.bits.front() == RTLIL::State::S0)
 423                 result.bits.front() = RTLIL::State::S1;
 424         else if (result.bits.front() == RTLIL::State::S1)
 425                 result.bits.front() = RTLIL::State::S0;
 426         return result;
 427 }
 428
 429 RTLIL::Const RTLIL::const_ge(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 430 {
 431         int undef_bit_pos = -1;
 432         bool y = const2big(arg1, signed1, undef_bit_pos) >= const2big(arg2, signed2, undef_bit_pos);
 433         RTLIL::Const result(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 434
 435         while (int(result.bits.size()) < result_len)
 436                 result.bits.push_back(RTLIL::State::S0);
 437         return result;
 438 }
 439
 440 RTLIL::Const RTLIL::const_gt(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 441 {
 442         int undef_bit_pos = -1;
 443         bool y = const2big(arg1, signed1, undef_bit_pos) > const2big(arg2, signed2, undef_bit_pos);
 444         RTLIL::Const result(undef_bit_pos >= 0 ? RTLIL::State::Sx : y ? RTLIL::State::S1 : RTLIL::State::S0);
 445
 446         while (int(result.bits.size()) < result_len)
 447                 result.bits.push_back(RTLIL::State::S0);
 448         return result;
 449 }
 450
 451 RTLIL::Const RTLIL::const_add(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 452 {
 453         int undef_bit_pos = -1;
 454         BigInteger y = const2big(arg1, signed1, undef_bit_pos) + const2big(arg2, signed2, undef_bit_pos);
 455         return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), undef_bit_pos);
 456 }
 457
 458 RTLIL::Const RTLIL::const_sub(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 459 {
 460         int undef_bit_pos = -1;
 461         BigInteger y = const2big(arg1, signed1, undef_bit_pos) - const2big(arg2, signed2, undef_bit_pos);
 462         return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), undef_bit_pos);
 463 }
 464
 465 RTLIL::Const RTLIL::const_mul(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 466 {
 467         int undef_bit_pos = -1;
 468         BigInteger y = const2big(arg1, signed1, undef_bit_pos) * const2big(arg2, signed2, undef_bit_pos);
 469         return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0));
 470 }
 471
 472 // truncating division
 473 RTLIL::Const RTLIL::const_div(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 474 {
 475         int undef_bit_pos = -1;
 476         BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 477         BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 478         if (b.isZero())
 479                 return RTLIL::Const(RTLIL::State::Sx, result_len);
 480         bool result_neg = (a.getSign() == BigInteger::negative) != (b.getSign() == BigInteger::negative);
 481         a = a.getSign() == BigInteger::negative ? -a : a;
 482         b = b.getSign() == BigInteger::negative ? -b : b;
 483         return big2const(result_neg ? -(a / b) : (a / b), result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0));
 484 }
 485
 486 // truncating modulo
 487 RTLIL::Const RTLIL::const_mod(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 488 {
 489         int undef_bit_pos = -1;
 490         BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 491         BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 492         if (b.isZero())
 493                 return RTLIL::Const(RTLIL::State::Sx, result_len);
 494         bool result_neg = a.getSign() == BigInteger::negative;
 495         a = a.getSign() == BigInteger::negative ? -a : a;
 496         b = b.getSign() == BigInteger::negative ? -b : b;
 497         return big2const(result_neg ? -(a % b) : (a % b), result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0));
 498 }
 499
 500 RTLIL::Const RTLIL::const_divfloor(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 501 {
 502         int undef_bit_pos = -1;
 503         BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 504         BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 505         if (b.isZero())
 506                 return RTLIL::Const(RTLIL::State::Sx, result_len);
 507
 508         bool result_pos = (a.getSign() == BigInteger::negative) == (b.getSign() == BigInteger::negative);
 509         a = a.getSign() == BigInteger::negative ? -a : a;
 510         b = b.getSign() == BigInteger::negative ? -b : b;
 511         BigInteger result;
 512
 513         if (result_pos || a == 0) {
 514                 result = a / b;
 515         } else {
 516                 // bigint division with negative numbers is wonky, make sure we only negate at the very end
 517                 result = -((a + b - 1) / b);
 518         }
 519         return big2const(result, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0));
 520 }
 521
 522 RTLIL::Const RTLIL::const_modfloor(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 523 {
 524         int undef_bit_pos = -1;
 525         BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 526         BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 527         if (b.isZero())
 528                 return RTLIL::Const(RTLIL::State::Sx, result_len);
 529
 530         BigInteger::Sign a_sign = a.getSign();
 531         BigInteger::Sign b_sign = b.getSign();
 532         a = a_sign == BigInteger::negative ? -a : a;
 533         b = b_sign == BigInteger::negative ? -b : b;
 534         BigInteger truncated = a_sign == BigInteger::negative ? -(a % b) : (a % b);
 535         BigInteger modulo;
 536
 537         if (truncated == 0 || (a_sign == b_sign)) {
 538                 modulo = truncated;
 539         } else {
 540                 modulo = b_sign == BigInteger::negative ? truncated - b : truncated + b;
 541         }
 542         return big2const(modulo, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0));
 543 }
 544
 545 RTLIL::Const RTLIL::const_pow(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 546 {
 547         int undef_bit_pos = -1;
 548
 549         BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 550         BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 551         BigInteger y = 1;
 552
 553         if (a == 0 && b < 0)
 554                 return RTLIL::Const(RTLIL::State::Sx, result_len);
 555
 556         if (a == 0 && b > 0)
 557                 return RTLIL::Const(RTLIL::State::S0, result_len);
 558
 559         if (b < 0)
 560         {
 561                 if (a < -1 || a > 1)
 562                         y = 0;
 563                 if (a == -1)
 564                         y = (-b % 2) == 0 ? 1 : -1;
 565         }
 566
 567         if (b > 0)
 568         {
 569                 // Power-modulo with 2^result_len as modulus
 570                 BigInteger modulus = 1;
 571                 int modulus_bits = (result_len >= 0 ? result_len : 1024);
 572                 for (int i = 0; i < modulus_bits; i++)
 573                         modulus *= 2;
 574
 575                 bool flip_result_sign = false;
 576                 if (a < 0) {
 577                         a *= -1;
 578                         if (b % 2 == 1)
 579                                 flip_result_sign = true;
 580                 }
 581
 582                 while (b > 0) {
 583                         if (b % 2 == 1)
 584                                 y = (y * a) % modulus;
 585                         b = b / 2;
 586                         a = (a * a) % modulus;
 587                 }
 588
 589                 if (flip_result_sign)
 590                         y *= -1;
 591         }
 592
 593         return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0));
 594 }
 595
 596 RTLIL::Const RTLIL::const_pos(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 597 {
 598         RTLIL::Const arg1_ext = arg1;
 599         extend_u0(arg1_ext, result_len, signed1);
 600
 601         return arg1_ext;
 602 }
 603
 604 RTLIL::Const RTLIL::const_neg(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 605 {
 606         RTLIL::Const arg1_ext = arg1;
 607         RTLIL::Const zero(RTLIL::State::S0, 1);
 608
 609         return RTLIL::const_sub(zero, arg1_ext, true, signed1, result_len);
 610 }
 611
 612 RTLIL::Const RTLIL::const_bmux(const RTLIL::Const &arg1, const RTLIL::Const &arg2)
 613 {
 614         std::vector<RTLIL::State> t = arg1.bits;
 615
 616         for (int i = GetSize(arg2)-1; i >= 0; i--)
 617         {
 618                 RTLIL::State sel = arg2.bits.at(i);
 619                 std::vector<RTLIL::State> new_t;
 620                 if (sel == State::S0)
 621                         new_t = std::vector<RTLIL::State>(t.begin(), t.begin() + GetSize(t)/2);
 622                 else if (sel == State::S1)
 623                         new_t = std::vector<RTLIL::State>(t.begin() + GetSize(t)/2, t.end());
 624                 else
 625                         for (int j = 0; j < GetSize(t)/2; j++)
 626                                 new_t.push_back(t[j] == t[j + GetSize(t)/2] ? t[j] : RTLIL::Sx);
 627                 t.swap(new_t);
 628         }
 629
 630         return t;
 631 }
 632
 633 RTLIL::Const RTLIL::const_demux(const RTLIL::Const &arg1, const RTLIL::Const &arg2)
 634 {
 635         int width = GetSize(arg1);
 636         int s_width = GetSize(arg2);
 637         std::vector<RTLIL::State> res;
 638         for (int i = 0; i < (1 << s_width); i++)
 639         {
 640                 bool ne = false;
 641                 bool x = false;
 642                 for (int j = 0; j < s_width; j++) {
 643                         bool bit = i & 1 << j;
 644                         if (arg2[j] == (bit ? RTLIL::S0 : RTLIL::S1))
 645                                 ne = true;
 646                         else if (arg2[j] != RTLIL::S0 && arg2[j] != RTLIL::S1)
 647                                 x = true;
 648                 }
 649                 if (ne) {
 650                         for (int j = 0; j < width; j++)
 651                                 res.push_back(State::S0);
 652                 } else if (x) {
 653                         for (int j = 0; j < width; j++)
 654                                 res.push_back(arg1.bits[j] == State::S0 ? State::S0 : State::Sx);
 655                 } else {
 656                         for (int j = 0; j < width; j++)
 657                                 res.push_back(arg1.bits[j]);
 658                 }
 659         }
 660         return res;
 661 }
 662
 663 YOSYS_NAMESPACE_END
 664