libzahl

commit b9debec106f2ac6e15d6dff88260f133d9eafcb2
parent 6cc727a4a17c6b037f665433cc47b37aa926b92b
Author: Mattias Andrée <maandree@kth.se>
Date:   Thu,  3 Mar 2016 13:59:54 +0100

Optimised zdivmod

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

Diffstat:
M
src/internals.h
 | 
1
+
M
src/zdivmod.c
 | 
41
+++++++++++++++++++++++++++++++----------
M
src/zsetup.c
 | 
4
++++
M
src/zunsetup.c
 | 
3
+++

4 files changed, 39 insertions(+), 10 deletions(-)
diff --git a/src/internals.h b/src/internals.h
@@ -39,6 +39,7 @@ LIST_TEMPS
 LIST_CONSTS
 #undef X
 
+extern z_t libzahl_tmp_divmod_ds[BITS_PER_CHAR];
 extern jmp_buf libzahl_jmp_buf;
 extern int libzahl_set_up;
 
diff --git a/src/zdivmod.c b/src/zdivmod.c
@@ -1,9 +1,10 @@
 /* See LICENSE file for copyright and license details. */
 #include "internals"
 
-#define ta  libzahl_tmp_divmod_a
-#define tb  libzahl_tmp_divmod_b
-#define td  libzahl_tmp_divmod_d
+#define ta   libzahl_tmp_divmod_a
+#define tb   libzahl_tmp_divmod_b
+#define td   libzahl_tmp_divmod_d
+#define tds  libzahl_tmp_divmod_ds
 
 
 void
@@ -57,15 +58,35 @@ zdivmod(z_t a, z_t b, z_t c, z_t d)
 	SET_SIGNUM(ta, 0);
 	zabs(tb, c);
 
-	for (;;) {
-		if (zcmpmag(td, tb) <= 0) {
-			zsub(tb, tb, td);
-			zbset(ta, ta, bit, 1);
+	if (bit < BITS_PER_CHAR) {
+		for (;;) {
+			if (zcmpmag(td, tb) <= 0) {
+				zsub(tb, tb, td);
+				zbset(ta, ta, bit, 1);
+			}
+			if (!bit--)
+				goto done;
+			zrsh(td, td, 1);
+		}
+	} else {
+		size_t i;
+		for (i = 0; i < BITS_PER_CHAR; i++)
+			zrsh(tds[i], td, i);
+		for (;;) {
+			for (i = 0; i < BITS_PER_CHAR; i++) {
+				if (zcmpmag(td[i], tb) <= 0) {
+					zsub(tb, tb, td[i]);
+					zbset(ta, ta, bit, 1);
+				}
+				if (!bit--)
+					goto done;
+				zrsh(td[i], td[i], 1);
+			}
+			for (i = bit < BITS_PER_CHAR ? bit : BITS_PER_CHAR; i--;)
+				zrsh(tds[i], tds[i], BITS_PER_CHAR);
 		}
-		if (!bit--)
-			break;
-		zrsh(td, td, 1);
 	}
+done:
 
 	zset(a, ta);
 	zset(b, tb);
diff --git a/src/zsetup.c b/src/zsetup.c
@@ -8,6 +8,7 @@ LIST_TEMPS
 LIST_CONSTS
 #undef X
 
+z_t libzahl_tmp_divmod_ds[BITS_PER_CHAR];
 jmp_buf libzahl_jmp_buf;
 int libzahl_set_up = 0;
 
@@ -15,6 +16,7 @@ int libzahl_set_up = 0;
 void
 zsetup(jmp_buf env)
 {
+	size_t i;
 	libzahl_jmp_buf = jmp_buf;
 
 	if (!libzahl_set_up) {
@@ -27,5 +29,7 @@ zsetup(jmp_buf env)
 		zinit(x), f(x, v);
 		LIST_CONSTS;
 #undef X
+		for (i = BITS_PER_CHAR; i--;)
+			zinit(libzahl_tmp_divmod_ds[i]);
 	}
 }
diff --git a/src/zunsetup.c b/src/zunsetup.c
@@ -5,6 +5,7 @@
 void
 zunsetup(jmp_buf env)
 {
+	size_t i;
 	if (libzahl_set_up) {
 		libzahl_set_up = 0;
 #define X(x)\
@@ -15,5 +16,7 @@ zunsetup(jmp_buf env)
 		zfree(x);
 		LIST_CONSTS;
 #undef X
+		for (i = BITS_PER_CHAR; i--;)
+			zfree(libzahl_tmp_divmod_ds[i]);
 	}
 }