libzahl

commit 0e905d00aceaa79849c25d359d7b7a6ee79175d7
parent 0d98678c1b2c3db9c6bd1860e9740c1928470c87
Author: Mattias Andrée <maandree@kth.se>
Date:   Thu,  3 Mar 2016 10:53:26 +0100

Optimise zpow and zmodpow

Signed-off-by: Mattias Andrée <maandree@kth.se>

Diffstat:
M
src/zmodpow.c
 | 
15
++++++++++-----
M
src/zpow.c
 | 
15
++++++++++-----

2 files changed, 20 insertions(+), 10 deletions(-)
diff --git a/src/zmodpow.c b/src/zmodpow.c
@@ -11,7 +11,8 @@
 void
 zmodpow(z_t a, z_t b, z_t c, z_t d)
 {
-	size_t i, n;
+	size_t i, j, n, bits;
+	zahl_char_t x;
 
 	if (zsignum(c) <= 0) {
 		if (zzero(c)) {
@@ -35,7 +36,8 @@ zmodpow(z_t a, z_t b, z_t c, z_t d)
 		return;
 	}
 
-	n = zbits(c);
+	bits = zbits(c);
+	n = FLOOR_BITS_TO_CHARS(bits);
 
 	zmod(tb, b, d);
 	zset(tc, c);
@@ -43,8 +45,11 @@ zmodpow(z_t a, z_t b, z_t c, z_t d)
 	zsetu(a, 1);
 
 	for (i = 0; i < n; i++) {
-		if (zbtest(tc, i))
-			zmodmul(a, a, tb, td);
-		zmodsqr(tb, tb, td);
+		x = tc->chars[i];
+		for (j = BITS_PER_CHAR; j--; x >>= 1) {
+			if (x & 1)
+				zmodmul(a, a, tb, td);
+			zmodsqr(tb, tb, td);
+		}
 	}
 }
diff --git a/src/zpow.c b/src/zpow.c
@@ -10,7 +10,8 @@
 void
 zpow(z_t a, z_t b, z_t c)
 {
-	size_t i, n;
+	size_t i, j, n, bits;
+	zahl_char_t x;
 
 	if (zsignum(c) <= 0) {
 		if (zzero(c)) {
@@ -31,15 +32,19 @@ zpow(z_t a, z_t b, z_t c)
 		return;
 	}
 
-	n = zbits(c);
+	bits = zbits(c);
+	n = FLOOR_BITS_TO_CHARS(bits);
 
 	zset(tb, b);
 	zset(tc, c);
 	zsetu(a, 1);
 
 	for (i = 0; i < n; i++) {
-		if (zbtest(tc, i))
-			zmul(a, a, tb);
-		zsqr(tb, tb);
+		x = tc->chars[i];
+		for (j = BITS_PER_CHAR; j--; x >>= 1, j) {
+			if (x & 1)
+				zmul(a, a, tb);
+			zsqr(tb, tb);
+		}
 	}
 }