X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=kernel%2Fcalc.cc;h=4a48407717f0342ba8f5d7d70528e7856b20b177;hb=f975cf39cbedbca0482109b7aa625570a3857ee6;hp=e998e5b3a62cdb72389384e3cb6a95147c39342b;hpb=8c523ef81d615515a2bf56e0886c5fad1aae85ad;p=yosys.git

diff --git a/kernel/calc.cc b/kernel/calc.cc
index e998e5b3a..4a4840771 100644
--- a/kernel/calc.cc
+++ b/kernel/calc.cc
@@ -2,11 +2,11 @@
  *  yosys -- Yosys Open SYnthesis Suite
  *
  *  Copyright (C) 2012  Clifford Wolf <clifford@clifford.at>
- *  
+ *
  *  Permission to use, copy, modify, and/or distribute this software for any
  *  purpose with or without fee is hereby granted, provided that the above
  *  copyright notice and this permission notice appear in all copies.
- *  
+ *
  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
@@ -17,43 +17,59 @@
  *
  */
 
-#include "kernel/log.h"
-#include "kernel/rtlil.h"
+// [[CITE]] Power-Modulus Algorithm
+// Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C,
+// Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4, page 244
+
+#include "kernel/yosys.h"
 #include "libs/bigint/BigIntegerLibrary.hh"
-#include <assert.h>
 
-static void extend(RTLIL::Const &arg, int width, bool is_signed)
+YOSYS_NAMESPACE_BEGIN
+
+static void extend_u0(RTLIL::Const &arg, int width, bool is_signed)
 {
 	RTLIL::State padding = RTLIL::State::S0;
 
-	if (arg.bits.size() > 0 && (is_signed || arg.bits.back() > RTLIL::State::S1))
+	if (arg.bits.size() > 0 && is_signed)
 		padding = arg.bits.back();
 
 	while (int(arg.bits.size()) < width)
 		arg.bits.push_back(padding);
+
+	arg.bits.resize(width);
 }
 
 static BigInteger const2big(const RTLIL::Const &val, bool as_signed, int &undef_bit_pos)
 {
-	BigInteger result = 0, this_bit = 1;
-	for (size_t i = 0; i < val.bits.size(); i++) {
-		if (val.bits[i] == RTLIL::State::S1) {
-			if (as_signed && i+1 == val.bits.size())
-				result -= this_bit;
-			else
-				result += this_bit;
-		}
-		else if (val.bits[i] != RTLIL::State::S0) {
-			if (undef_bit_pos < 0)
-				undef_bit_pos = i;
-		}
-		this_bit *= 2;
+	BigUnsigned mag;
+
+	BigInteger::Sign sign = BigInteger::positive;
+	State inv_sign_bit = RTLIL::State::S1;
+	size_t num_bits = val.bits.size();
+
+	if (as_signed && num_bits && val.bits[num_bits-1] == RTLIL::State::S1) {
+		inv_sign_bit = RTLIL::State::S0;
+		sign = BigInteger::negative;
+		num_bits--;
 	}
-	return result;
+
+	for (size_t i = 0; i < num_bits; i++)
+		if (val.bits[i] == RTLIL::State::S0 || val.bits[i] == RTLIL::State::S1)
+			mag.setBit(i, val.bits[i] == inv_sign_bit);
+		else if (undef_bit_pos < 0)
+			undef_bit_pos = i;
+
+	if (sign == BigInteger::negative)
+		mag += 1;
+
+	return BigInteger(mag, sign);
 }
 
 static RTLIL::Const big2const(const BigInteger &val, int result_len, int undef_bit_pos)
 {
+	if (undef_bit_pos >= 0)
+		return RTLIL::Const(RTLIL::State::Sx, result_len);
+
 	BigUnsigned mag = val.getMagnitude();
 	RTLIL::Const result(0, result_len);
 
@@ -72,9 +88,11 @@ static RTLIL::Const big2const(const BigInteger &val, int result_len, int undef_b
 		}
 	}
 
+#if 0
 	if (undef_bit_pos >= 0)
 		for (int i = undef_bit_pos; i < result_len; i++)
 			result.bits[i] = RTLIL::State::Sx;
+#endif
 
 	return result;
 }
@@ -117,7 +135,7 @@ RTLIL::Const RTLIL::const_not(const RTLIL::Const &arg1, const RTLIL::Const&, boo
 		result_len = arg1.bits.size();
 
 	RTLIL::Const arg1_ext = arg1;
-	extend(arg1_ext, result_len, signed1);
+	extend_u0(arg1_ext, result_len, signed1);
 
 	RTLIL::Const result(RTLIL::State::Sx, result_len);
 	for (size_t i = 0; i < size_t(result_len); i++) {
@@ -136,10 +154,10 @@ static RTLIL::Const logic_wrapper(RTLIL::State(*logic_func)(RTLIL::State, RTLIL:
 		RTLIL::Const arg1, RTLIL::Const arg2, bool signed1, bool signed2, int result_len = -1)
 {
 	if (result_len < 0)
-		result_len = std::max(arg1.bits.size(), arg2.bits.size());
+		result_len = max(arg1.bits.size(), arg2.bits.size());
 
-	extend(arg1, result_len, signed1);
-	extend(arg2, result_len, signed2);
+	extend_u0(arg1, result_len, signed1);
+	extend_u0(arg2, result_len, signed2);
 
 	RTLIL::Const result(RTLIL::State::Sx, result_len);
 	for (size_t i = 0; i < size_t(result_len); i++) {
@@ -257,7 +275,7 @@ RTLIL::Const RTLIL::const_logic_or(const RTLIL::Const &arg1, const RTLIL::Const
 	return result;
 }
 
-static RTLIL::Const const_shift(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool sign_ext, int direction, int result_len)
+static RTLIL::Const const_shift_worker(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool sign_ext, int direction, int result_len)
 {
 	int undef_bit_pos = -1;
 	BigInteger offset = const2big(arg2, false, undef_bit_pos) * direction;
@@ -273,7 +291,7 @@ static RTLIL::Const const_shift(const RTLIL::Const &arg1, const RTLIL::Const &ar
 		BigInteger pos = BigInteger(i) + offset;
 		if (pos < 0)
 			result.bits[i] = RTLIL::State::S0;
-		else if (pos >= arg1.bits.size())
+		else if (pos >= BigInteger(int(arg1.bits.size())))
 			result.bits[i] = sign_ext ? arg1.bits.back() : RTLIL::State::S0;
 		else
 			result.bits[i] = arg1.bits[pos.toInt()];
@@ -285,29 +303,62 @@ static RTLIL::Const const_shift(const RTLIL::Const &arg1, const RTLIL::Const &ar
 RTLIL::Const RTLIL::const_shl(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool, int result_len)
 {
 	RTLIL::Const arg1_ext = arg1;
-	extend(arg1_ext, result_len, signed1);
-	return const_shift(arg1_ext, arg2, false, -1, result_len);
+	extend_u0(arg1_ext, result_len, signed1);
+	return const_shift_worker(arg1_ext, arg2, false, -1, result_len);
 }
 
 RTLIL::Const RTLIL::const_shr(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool, int result_len)
 {
 	RTLIL::Const arg1_ext = arg1;
-	extend(arg1_ext, result_len, signed1);
-	return const_shift(arg1_ext, arg2, false, +1, result_len);
+	extend_u0(arg1_ext, max(result_len, GetSize(arg1)), signed1);
+	return const_shift_worker(arg1_ext, arg2, false, +1, result_len);
 }
 
 RTLIL::Const RTLIL::const_sshl(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 {
 	if (!signed1)
 		return const_shl(arg1, arg2, signed1, signed2, result_len);
-	return const_shift(arg1, arg2, true, -1, result_len);
+	return const_shift_worker(arg1, arg2, true, -1, result_len);
 }
 
 RTLIL::Const RTLIL::const_sshr(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 {
 	if (!signed1)
 		return const_shr(arg1, arg2, signed1, signed2, result_len);
-	return const_shift(arg1, arg2, true, +1, result_len);
+	return const_shift_worker(arg1, arg2, true, +1, result_len);
+}
+
+static RTLIL::Const const_shift_shiftx(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool, bool signed2, int result_len, RTLIL::State other_bits)
+{
+	int undef_bit_pos = -1;
+	BigInteger offset = const2big(arg2, signed2, undef_bit_pos);
+
+	if (result_len < 0)
+		result_len = arg1.bits.size();
+
+	RTLIL::Const result(RTLIL::State::Sx, result_len);
+	if (undef_bit_pos >= 0)
+		return result;
+
+	for (int i = 0; i < result_len; i++) {
+		BigInteger pos = BigInteger(i) + offset;
+		if (pos < 0 || pos >= BigInteger(int(arg1.bits.size())))
+			result.bits[i] = other_bits;
+		else
+			result.bits[i] = arg1.bits[pos.toInt()];
+	}
+
+	return result;
+}
+
+RTLIL::Const RTLIL::const_shift(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
+{
+	return const_shift_shiftx(arg1, arg2, signed1, signed2, result_len, RTLIL::State::S0);
+}
+
+RTLIL::Const RTLIL::const_shiftx(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
+{
+	return const_shift_shiftx(arg1, arg2, signed1, signed2, result_len, RTLIL::State::Sx);
 }
 
 RTLIL::Const RTLIL::const_lt(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
@@ -338,11 +389,9 @@ RTLIL::Const RTLIL::const_eq(const RTLIL::Const &arg1, const RTLIL::Const &arg2,
 	RTLIL::Const arg2_ext = arg2;
 	RTLIL::Const result(RTLIL::State::S0, result_len);
 
-	while (arg1_ext.bits.size() < arg2_ext.bits.size())
-		arg1_ext.bits.push_back(signed1 && signed2 && arg1_ext.bits.size() > 0 ? arg1_ext.bits.back() : RTLIL::State::S0);
-
-	while (arg2_ext.bits.size() < arg1_ext.bits.size())
-		arg2_ext.bits.push_back(signed1 && signed2 && arg2_ext.bits.size() > 0 ? arg2_ext.bits.back() : RTLIL::State::S0);
+	int width = max(arg1_ext.bits.size(), arg2_ext.bits.size());
+	extend_u0(arg1_ext, width, signed1 && signed2);
+	extend_u0(arg2_ext, width, signed1 && signed2);
 
 	RTLIL::State matched_status = RTLIL::State::S1;
 	for (size_t i = 0; i < arg1_ext.bits.size(); i++) {
@@ -368,6 +417,35 @@ RTLIL::Const RTLIL::const_ne(const RTLIL::Const &arg1, const RTLIL::Const &arg2,
 	return result;
 }
 
+RTLIL::Const RTLIL::const_eqx(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
+{
+	RTLIL::Const arg1_ext = arg1;
+	RTLIL::Const arg2_ext = arg2;
+	RTLIL::Const result(RTLIL::State::S0, result_len);
+
+	int width = max(arg1_ext.bits.size(), arg2_ext.bits.size());
+	extend_u0(arg1_ext, width, signed1 && signed2);
+	extend_u0(arg2_ext, width, signed1 && signed2);
+
+	for (size_t i = 0; i < arg1_ext.bits.size(); i++) {
+		if (arg1_ext.bits.at(i) != arg2_ext.bits.at(i))
+			return result;
+	}
+
+	result.bits.front() = RTLIL::State::S1;
+	return result;
+}
+
+RTLIL::Const RTLIL::const_nex(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
+{
+	RTLIL::Const result = RTLIL::const_eqx(arg1, arg2, signed1, signed2, result_len);
+	if (result.bits.front() == RTLIL::State::S0)
+		result.bits.front() = RTLIL::State::S1;
+	else if (result.bits.front() == RTLIL::State::S1)
+		result.bits.front() = RTLIL::State::S0;
+	return result;
+}
+
 RTLIL::Const RTLIL::const_ge(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 {
 	int undef_bit_pos = -1;
@@ -394,21 +472,21 @@ RTLIL::Const RTLIL::const_add(const RTLIL::Const &arg1, const RTLIL::Const &arg2
 {
 	int undef_bit_pos = -1;
 	BigInteger y = const2big(arg1, signed1, undef_bit_pos) + const2big(arg2, signed2, undef_bit_pos);
-	return big2const(y, result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), undef_bit_pos);
+	return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), undef_bit_pos);
 }
 
 RTLIL::Const RTLIL::const_sub(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 {
 	int undef_bit_pos = -1;
 	BigInteger y = const2big(arg1, signed1, undef_bit_pos) - const2big(arg2, signed2, undef_bit_pos);
-	return big2const(y, result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), undef_bit_pos);
+	return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), undef_bit_pos);
 }
 
 RTLIL::Const RTLIL::const_mul(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
 {
 	int undef_bit_pos = -1;
 	BigInteger y = const2big(arg1, signed1, undef_bit_pos) * const2big(arg2, signed2, undef_bit_pos);
-	return big2const(y, result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), std::min(undef_bit_pos, 0));
+	return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0));
 }
 
 RTLIL::Const RTLIL::const_div(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
@@ -421,7 +499,7 @@ RTLIL::Const RTLIL::const_div(const RTLIL::Const &arg1, const RTLIL::Const &arg2
 	bool result_neg = (a.getSign() == BigInteger::negative) != (b.getSign() == BigInteger::negative);
 	a = a.getSign() == BigInteger::negative ? -a : a;
 	b = b.getSign() == BigInteger::negative ? -b : b;
-	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));
+	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));
 }
 
 RTLIL::Const RTLIL::const_mod(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
@@ -434,7 +512,7 @@ RTLIL::Const RTLIL::const_mod(const RTLIL::Const &arg1, const RTLIL::Const &arg2
 	bool result_neg = a.getSign() == BigInteger::negative;
 	a = a.getSign() == BigInteger::negative ? -a : a;
 	b = b.getSign() == BigInteger::negative ? -b : b;
-	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));
+	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));
 }
 
 RTLIL::Const RTLIL::const_pow(const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
@@ -445,26 +523,53 @@ RTLIL::Const RTLIL::const_pow(const RTLIL::Const &arg1, const RTLIL::Const &arg2
 	BigInteger b = const2big(arg2, signed2, undef_bit_pos);
 	BigInteger y = 1;
 
-	if (b < 0 || a == 0) {
-		y = 0;
-	} else { 
+	if (a == 0 && b < 0)
+		return RTLIL::Const(RTLIL::State::Sx, result_len);
+
+	if (a == 0 && b > 0)
+		return RTLIL::Const(RTLIL::State::S0, result_len);
+
+	if (b < 0)
+	{
+		if (a < -1 || a > 1)
+			y = 0;
+		if (a == -1)
+			y = (-b % 2) == 0 ? 1 : -1;
+	}
+
+	if (b > 0)
+	{
+		// Power-modulo with 2^result_len as modulus
+		BigInteger modulus = 1;
+		int modulus_bits = (result_len >= 0 ? result_len : 1024);
+		for (int i = 0; i < modulus_bits; i++)
+			modulus *= 2;
+
+		bool flip_result_sign = false;
+		if (a < 0) {
+			a *= -1;
+			if (b % 2 == 1)
+				flip_result_sign = true;
+		}
+
 		while (b > 0) {
-			y = y * a;
-			if (y.getLength() > 0x10000) {
-				undef_bit_pos = 0;
-				break;
-			}
-			b--;
+			if (b % 2 == 1)
+				y = (y * a) % modulus;
+			b = b / 2;
+			a = (a * a) % modulus;
 		}
+
+		if (flip_result_sign)
+			y *= -1;
 	}
 
-	return big2const(y, result_len >= 0 ? result_len : std::max(arg1.bits.size(), arg2.bits.size()), std::min(undef_bit_pos, 0));
+	return big2const(y, result_len >= 0 ? result_len : max(arg1.bits.size(), arg2.bits.size()), min(undef_bit_pos, 0));
 }
 
 RTLIL::Const RTLIL::const_pos(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 {
 	RTLIL::Const arg1_ext = arg1;
-	extend(arg1_ext, result_len, signed1);
+	extend_u0(arg1_ext, result_len, signed1);
 
 	return arg1_ext;
 }
@@ -472,9 +577,10 @@ RTLIL::Const RTLIL::const_pos(const RTLIL::Const &arg1, const RTLIL::Const&, boo
 RTLIL::Const RTLIL::const_neg(const RTLIL::Const &arg1, const RTLIL::Const&, bool signed1, bool, int result_len)
 {
 	RTLIL::Const arg1_ext = arg1;
-	extend(arg1_ext, result_len, signed1);
-
 	RTLIL::Const zero(RTLIL::State::S0, 1);
-	return RTLIL::const_sub(zero, arg1_ext, false, signed1, result_len);
+
+	return RTLIL::const_sub(zero, arg1_ext, true, signed1, result_len);
 }
 
+YOSYS_NAMESPACE_END
+