From 0e905d00aceaa79849c25d359d7b7a6ee79175d7 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Thu, 3 Mar 2016 10:53:26 +0100 Subject: Optimise zpow and zmodpow MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/zmodpow.c | 15 ++++++++++----- src/zpow.c | 15 ++++++++++----- 2 files changed, 20 insertions(+), 10 deletions(-) (limited to 'src') 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); + } } } -- cgit v1.2.3-70-g09d2