From fc6dc0d7b8d3580df50558473c5d6365fd303191 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Thu, 7 Nov 2013 22:20:00 +0100
Subject: [PATCH] Fixed handling of power operator

---
 frontends/ast/genrtlil.cc | 28 +++++++++++++++-------
 frontends/ast/simplify.cc |  4 ++--
 kernel/calc.cc            | 50 ++++++++++++++++++++++++++++++++-------
 tests/simple/constpower.v | 15 ++++++++++++
 4 files changed, 78 insertions(+), 19 deletions(-)
 create mode 100644 tests/simple/constpower.v

diff --git a/frontends/ast/genrtlil.cc b/frontends/ast/genrtlil.cc
index 0c9c9be73..2e8ab7492 100644
--- a/frontends/ast/genrtlil.cc
+++ b/frontends/ast/genrtlil.cc
@@ -1070,6 +1070,23 @@ RTLIL::SigSpec AstNode::genRTLIL(int width_hint, bool sign_hint)
 			return binop2rtlil(this, type_name, width, left, right);
 		}
 
+	// generate cells for binary operations: $pow
+	case AST_POW:
+		{
+			int right_width;
+			bool right_signed;
+			children[1]->detectSignWidth(right_width, right_signed);
+			if (width_hint < 0)
+				detectSignWidth(width_hint, sign_hint);
+			RTLIL::SigSpec left = children[0]->genRTLIL(width_hint, sign_hint);
+			RTLIL::SigSpec right = children[1]->genRTLIL(right_width, right_signed);
+			int width = width_hint > 0 ? width_hint : left.width;
+			is_signed = children[0]->is_signed;
+			if (!flag_noopt && left.is_fully_const() && left.as_int() == 2 && !right_signed)
+				return binop2rtlil(this, "$shl", width, RTLIL::SigSpec(1, left.width), right);
+			return binop2rtlil(this, "$pow", width, left, right);
+		}
+
 	// generate cells for binary operations: $lt, $le, $eq, $ne, $ge, $gt
 	if (0) { case AST_LT: type_name = "$lt"; }
 	if (0) { case AST_LE: type_name = "$le"; }
@@ -1088,19 +1105,18 @@ RTLIL::SigSpec AstNode::genRTLIL(int width_hint, bool sign_hint)
 			return sig;
 		}
 
-	// generate cells for binary operations: $add, $sub, $mul, $div, $mod, $pow
+	// generate cells for binary operations: $add, $sub, $mul, $div, $mod
 	if (0) { case AST_ADD: type_name = "$add"; }
 	if (0) { case AST_SUB: type_name = "$sub"; }
 	if (0) { case AST_MUL: type_name = "$mul"; }
 	if (0) { case AST_DIV: type_name = "$div"; }
 	if (0) { case AST_MOD: type_name = "$mod"; }
-	if (0) { case AST_POW: type_name = "$pow"; }
 		{
 			if (width_hint < 0)
 				detectSignWidth(width_hint, sign_hint);
 			RTLIL::SigSpec left = children[0]->genRTLIL(width_hint, sign_hint);
-			RTLIL::SigSpec right = type == AST_POW ? children[1]->genRTLIL() : children[1]->genRTLIL(width_hint, sign_hint);
-			int width = type == AST_POW ? left.width : std::max(left.width, right.width);
+			RTLIL::SigSpec right = children[1]->genRTLIL(width_hint, sign_hint);
+			int width = std::max(left.width, right.width);
 			if (width > width_hint && width_hint > 0)
 				width = width_hint;
 			if (width < width_hint) {
@@ -1110,12 +1126,8 @@ RTLIL::SigSpec AstNode::genRTLIL(int width_hint, bool sign_hint)
 					width = width_hint;
 				if (type == AST_MUL)
 					width = std::min(left.width + right.width, width_hint);
-				if (type == AST_POW)
-					width = width_hint;
 			}
 			is_signed = children[0]->is_signed && children[1]->is_signed;
-			if (!flag_noopt && type == AST_POW && left.is_fully_const() && left.as_int() == 2)
-				return binop2rtlil(this, "$shl", width, RTLIL::SigSpec(1, left.width), right);
 			return binop2rtlil(this, type_name, width, left, right);
 		}
 
diff --git a/frontends/ast/simplify.cc b/frontends/ast/simplify.cc
index 449ade434..5c0130d42 100644
--- a/frontends/ast/simplify.cc
+++ b/frontends/ast/simplify.cc
@@ -1017,9 +1017,10 @@ skip_dynamic_range_lvalue_expansion:;
 		if (0) { case AST_SHIFT_RIGHT:  const_func = RTLIL::const_shr;  }
 		if (0) { case AST_SHIFT_SLEFT:  const_func = RTLIL::const_sshl; }
 		if (0) { case AST_SHIFT_SRIGHT: const_func = RTLIL::const_sshr; }
+		if (0) { case AST_POW:          const_func = RTLIL::const_pow; }
 			if (children[0]->type == AST_CONSTANT && children[1]->type == AST_CONSTANT) {
 				RTLIL::Const y = const_func(children[0]->bitsAsConst(width_hint, sign_hint),
-						RTLIL::Const(children[1]->bits), sign_hint, false, width_hint);
+						RTLIL::Const(children[1]->bits), sign_hint, type == AST_POW ? sign_hint : false, width_hint);
 				newNode = mkconst_bits(y.bits, sign_hint);
 			}
 			break;
@@ -1042,7 +1043,6 @@ skip_dynamic_range_lvalue_expansion:;
 		if (0) { case AST_MUL: const_func = RTLIL::const_mul; }
 		if (0) { case AST_DIV: const_func = RTLIL::const_div; }
 		if (0) { case AST_MOD: const_func = RTLIL::const_mod; }
-		if (0) { case AST_POW: const_func = RTLIL::const_pow; }
 			if (children[0]->type == AST_CONSTANT && children[1]->type == AST_CONSTANT) {
 				RTLIL::Const y = const_func(children[0]->bitsAsConst(width_hint, sign_hint),
 						children[1]->bitsAsConst(width_hint, sign_hint), sign_hint, sign_hint, width_hint);
diff --git a/kernel/calc.cc b/kernel/calc.cc
index 605b1c13a..61a75c79f 100644
--- a/kernel/calc.cc
+++ b/kernel/calc.cc
@@ -17,6 +17,10 @@
  *
  */
 
+// [[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/log.h"
 #include "kernel/rtlil.h"
 #include "libs/bigint/BigIntegerLibrary.hh"
@@ -450,21 +454,49 @@ RTLIL::Const RTLIL::const_pow(const RTLIL::Const &arg1, const RTLIL::Const &arg2
 {
 	int undef_bit_pos = -1;
 
+	log("--POW--\n");
 	BigInteger a = const2big(arg1, signed1, undef_bit_pos);
 	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));
diff --git a/tests/simple/constpower.v b/tests/simple/constpower.v
new file mode 100644
index 000000000..451866a63
--- /dev/null
+++ b/tests/simple/constpower.v
@@ -0,0 +1,15 @@
+module constpower(ys, yu);
+
+output [8*8*8-1:0] ys, yu;
+
+genvar i, j;
+
+generate
+	for (i = 0; i < 8; i = i+1)
+	for (j = 0; j < 8; j = j+1) begin:V
+		assign ys[i*8 + j*64 + 7 : i*8 + j*64] = $signed(i-4) ** $signed(j-4);
+		assign yu[i*8 + j*64 + 7 : i*8 + j*64] = $unsigned(i) ** $unsigned(j);
+	end
+endgenerate
+
+endmodule
-- 
2.30.2