[hackers] [libzahl] Optimise zpow and zmodpow || Mattias Andrée

[git]

commit 0e905d00aceaa79849c25d359d7b7a6ee79175d7
Author:     Mattias Andrée <maand...@kth.se>
AuthorDate: Thu Mar 3 10:53:26 2016 +0100
Commit:     Mattias Andrée <maand...@kth.se>
CommitDate: Thu Mar 3 10:53:26 2016 +0100

    Optimise zpow and zmodpow
    
    Signed-off-by: Mattias Andrée <maand...@kth.se>

diff --git a/src/zmodpow.c b/src/zmodpow.c
index 42bed2f..c92ca18 100644
--- 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
index bc071f8..c359ac3 100644
--- 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);
+               }
        }
 }