[hackers] [libzahl] Optimised zdivmod || Mattias Andrée

[git]

commit b9debec106f2ac6e15d6dff88260f133d9eafcb2
Author:     Mattias Andrée <maand...@kth.se>
AuthorDate: Thu Mar 3 13:59:54 2016 +0100
Commit:     Mattias Andrée <maand...@kth.se>
CommitDate: Thu Mar 3 13:59:54 2016 +0100

    Optimised zdivmod
    
    Signed-off-by: Mattias Andrée <maand...@kth.se>

diff --git a/src/internals.h b/src/internals.h
index 89d98e1..2ab5cc7 100644
--- 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
index 052e343..bf5dfa6 100644
--- 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
index f7c1912..78cfa3b 100644
--- 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
index e2d91f6..3f3ccf6 100644
--- 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]);
        }
 }