From 29066202fecf3c7c1741f4c854dc3dfea55d63cb Mon Sep 17 00:00:00 2001
From: Arran Cudbard-Bell <a.cudbardb@freeradius.org>
Date: Mon, 2 Dec 2013 18:39:38 +0000
Subject: [PATCH] Add power operator to expr

Who needs left shift when you can do %{expr:(%{Acct-Output-Gigawords} * (2 ^ 32)) + %{Acct-Input-Octets}}}. Ok bad example, but i'm sure someone will find it useful.
---
 src/include/libradius.h         |  1 +
 src/lib/misc.c                  | 84 +++++++++++++++++++++++++++++++++
 src/modules/rlm_expr/rlm_expr.c | 30 ++++++++----
 3 files changed, 105 insertions(+), 10 deletions(-)

diff --git a/src/include/libradius.h b/src/include/libradius.h
index 3f5819b2dc..3be21d9c87 100644
--- a/src/include/libradius.h
+++ b/src/include/libradius.h
@@ -581,6 +581,7 @@ int fr_ipaddr2sockaddr(fr_ipaddr_t const *ipaddr, int port,
 int fr_sockaddr2ipaddr(struct sockaddr_storage const *sa, socklen_t salen,
 		       fr_ipaddr_t *ipaddr, int * port);
 ssize_t		fr_utf8_to_ucs2(uint8_t *out, size_t outlen, char const *in, size_t inlen);
+int64_t		fr_pow(int32_t base, uint8_t exp);
 int		fr_get_time(char const *date_str, time_t *date);
 
 /*
diff --git a/src/lib/misc.c b/src/lib/misc.c
index de8d13d9d5..d50cba5c45 100644
--- a/src/lib/misc.c
+++ b/src/lib/misc.c
@@ -814,6 +814,90 @@ ssize_t fr_utf8_to_ucs2(uint8_t *out, size_t outlen, char const *in, size_t inle
 	return out - start;
 }
 
+/** Calculate powers
+ *
+ * @author Orson Peters
+ * @note Borrowed from the gist here: https://gist.github.com/nightcracker/3551590.
+ *
+ * @param base a 32bit signed integer.
+ * @param exp amount to raise base by.
+ * @return base ^ pow, or 0 on underflow/overflow.
+ */
+int64_t fr_pow(int32_t base, uint8_t exp) {
+	static const uint8_t highest_bit_set[] = {
+		0, 1, 2, 2, 3, 3, 3, 3,
+		4, 4, 4, 4, 4, 4, 4, 4,
+		5, 5, 5, 5, 5, 5, 5, 5,
+		5, 5, 5, 5, 5, 5, 5, 5,
+		6, 6, 6, 6, 6, 6, 6, 6,
+		6, 6, 6, 6, 6, 6, 6, 6,
+		6, 6, 6, 6, 6, 6, 6, 6,
+		6, 6, 6, 6, 6, 6, 6, 255, // anything past 63 is a guaranteed overflow with base > 1
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+		255, 255, 255, 255, 255, 255, 255, 255,
+	};
+
+	uint64_t result = 1;
+
+	switch (highest_bit_set[exp]) {
+	case 255: // we use 255 as an overflow marker and return 0 on overflow/underflow
+		if (base == 1) {
+			return 1;
+		}
+
+		if (base == -1) {
+			return 1 - 2 * (exp & 1);
+		}
+		return 0;
+	case 6:
+		if (exp & 1) result *= base;
+		exp >>= 1;
+		base *= base;
+	case 5:
+		if (exp & 1) result *= base;
+		exp >>= 1;
+		base *= base;
+	case 4:
+		if (exp & 1) result *= base;
+		exp >>= 1;
+		base *= base;
+	case 3:
+		if (exp & 1) result *= base;
+		exp >>= 1;
+		base *= base;
+	case 2:
+		if (exp & 1) result *= base;
+		exp >>= 1;
+		base *= base;
+	case 1:
+		if (exp & 1) result *= base;
+	default:
+		return result;
+	}
+}
+
 /*
  *	Sort of strtok/strsep function.
  */
diff --git a/src/modules/rlm_expr/rlm_expr.c b/src/modules/rlm_expr/rlm_expr.c
index 5c55035bb7..be2b2d2fb5 100644
--- a/src/modules/rlm_expr/rlm_expr.c
+++ b/src/modules/rlm_expr/rlm_expr.c
@@ -49,16 +49,17 @@ static const CONF_PARSER module_config[] = {
 };
 
 typedef enum expr_token_t {
-  TOKEN_NONE = 0,
-  TOKEN_INTEGER,
-  TOKEN_ADD,
-  TOKEN_SUBTRACT,
-  TOKEN_DIVIDE,
-  TOKEN_REMAINDER,
-  TOKEN_MULTIPLY,
-  TOKEN_AND,
-  TOKEN_OR,
-  TOKEN_LAST
+	TOKEN_NONE = 0,
+	TOKEN_INTEGER,
+	TOKEN_ADD,
+	TOKEN_SUBTRACT,
+	TOKEN_DIVIDE,
+	TOKEN_REMAINDER,
+	TOKEN_MULTIPLY,
+	TOKEN_AND,
+	TOKEN_OR,
+	TOKEN_POWER,
+	TOKEN_LAST
 } expr_token_t;
 
 typedef struct expr_map_t {
@@ -75,6 +76,7 @@ static expr_map_t map[] =
 	{'%',	TOKEN_REMAINDER },
 	{'&',	TOKEN_AND },
 	{'|',	TOKEN_OR },
+	{'^',	TOKEN_POWER },
 	{0,	TOKEN_LAST}
 };
 
@@ -226,6 +228,14 @@ static int get_number(REQUEST *request, char const **string, int64_t *answer)
 		case TOKEN_OR:
 			result |= x;
 			break;
+
+		case TOKEN_POWER:
+			if ((x > 255) || (x < 0)) {
+				REDEBUG("Exponent must be between 0-255");
+				return -1;
+			}
+			x = fr_pow((int32_t) result, (uint8_t) x);
+			break;
 		}
 
 		/*
-- 
2.47.3