From 3e3b44d087ab616089402129b2bc4c4831c6b33a Mon Sep 17 00:00:00 2001
From: Mattias Andrée <maandree@kth.se>
Date: Wed, 16 Mar 2016 14:30:29 +0100
Subject: Optimise zsqr, zmul, zstr, zdivmod, zpow, and zpowu
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Signed-off-by: Mattias Andrée <maandree@kth.se>
---
 src/zdivmod.c | 93 ++++++++++++++++++++++++++++++++---------------------------
 1 file changed, 51 insertions(+), 42 deletions(-)

(limited to 'src/zdivmod.c')

diff --git a/src/zdivmod.c b/src/zdivmod.c
index 55d0e06..d907450 100644
--- a/src/zdivmod.c
+++ b/src/zdivmod.c
@@ -1,44 +1,17 @@
 /* See LICENSE file for copyright and license details. */
 #include "internals.h"
 
-#define ta   libzahl_tmp_divmod_a
-#define tb   libzahl_tmp_divmod_b
-#define td   libzahl_tmp_divmod_d
-#define tds  libzahl_tmp_divmod_ds
+#define ta          libzahl_tmp_divmod_a
+#define tb          libzahl_tmp_divmod_b
+#define td          libzahl_tmp_divmod_d
+#define tds_proper  libzahl_tmp_divmod_ds
 
 
-void
-zdivmod(z_t a, z_t b, z_t c, z_t d)
+static inline void
+zdivmod_impl(z_t a, z_t b, z_t c, z_t d)
 {
-	size_t c_bits, d_bits, bit;
-	int sign, cmpmag;
-
-	sign = zsignum(c) * zsignum(d);
-
-	if (unlikely(!sign)) {
-		if (zzero(c)) {
-			if (zzero(d)) {
-				libzahl_failure(-ZERROR_0_DIV_0);
-			} else {
-				SET_SIGNUM(a, 0);
-				SET_SIGNUM(b, 0);
-			}
-		} else {
-			libzahl_failure(-ZERROR_DIV_0);
-		}
-		return;
-	} else if (unlikely((cmpmag = zcmpmag(c, d)) <= 0)) {
-	  	if (cmpmag == 0) {
-			zseti(a, sign);
-			SET_SIGNUM(b, 0);
-			return;
-		} else {
-			SET(b, c);
-		}
-		SET_SIGNUM(b, 1);
-		SET_SIGNUM(a, 0);
-		return;
-	}
+	size_t c_bits, d_bits, bit, i;
+	static z_t tds[BITS_PER_CHAR];
 
 	c_bits = zbits(c);
 	d_bits = zbits(d);
@@ -54,10 +27,10 @@ zdivmod(z_t a, z_t b, z_t c, z_t d)
 	SET_SIGNUM(ta, 0);
 	zabs(tb, c);
 
-	if (bit < BITS_PER_CHAR) {
+	if (unlikely(bit <= BITS_PER_CHAR)) {
 		for (;;) {
 			if (zcmpmag(td, tb) <= 0) {
-				zsub(tb, tb, td);
+				zsub_unsigned(tb, tb, td);
 				zbset(ta, ta, bit, 1);
 			}
 			if (!bit-- || zzero(tb))
@@ -65,25 +38,61 @@ zdivmod(z_t a, z_t b, z_t c, z_t d)
 			zrsh(td, td, 1);
 		}
 	} else {
-		size_t i;
-		for (i = 0; i < BITS_PER_CHAR; i++)
-			zrsh(tds[i], td, i);
+		for (i = 0; i < BITS_PER_CHAR; i++) {
+			zrsh(tds_proper[i], td, i);
+			tds[i]->used = tds_proper[i]->used;
+			tds[i]->sign = tds_proper[i]->sign;
+			tds[i]->chars = tds_proper[i]->chars;
+		}
 		for (;;) {
 			for (i = 0; i < BITS_PER_CHAR; i++) {
 				if (zcmpmag(tds[i], tb) <= 0) {
-					zsub(tb, tb, tds[i]);
+					zsub_unsigned(tb, tb, tds[i]);
 					zbset(ta, ta, bit, 1);
 				}
 				if (!bit-- || zzero(tb))
 					goto done;
 			}
 			for (i = MIN(bit, BITS_PER_CHAR - 1) + 1; i--;)
-				zrsh(tds[i], tds[i], BITS_PER_CHAR);
+				zrsh_taint(tds[i], BITS_PER_CHAR);
 		}
 	}
 done:
 
 	zswap(a, ta);
 	zswap(b, tb);
+}
+
+
+void
+zdivmod(z_t a, z_t b, z_t c, z_t d)
+{
+	int sign, cmpmag;
+
+	sign = zsignum(c) * zsignum(d);
+
+	if (unlikely(!sign)) {
+		if (unlikely(!zzero(c))) {
+			libzahl_failure(-ZERROR_DIV_0);
+		} else if (unlikely(zzero(d))) {
+			libzahl_failure(-ZERROR_0_DIV_0);
+		} else {
+			SET_SIGNUM(a, 0);
+			SET_SIGNUM(b, 0);
+		}
+		return;
+	} else if (cmpmag = zcmpmag(c, d), unlikely(cmpmag <= 0)) {
+		if (unlikely(cmpmag == 0)) {
+			zseti(a, sign);
+			SET_SIGNUM(b, 0);
+		} else {
+			SET(b, c);
+			SET_SIGNUM(b, 1);
+			SET_SIGNUM(a, 0);
+		}
+		return;
+	}
+
+	zdivmod_impl(a, b, c, d);
 	SET_SIGNUM(a, sign);
 }
-- 
cgit v1.2.3-70-g09d2