Commit 87b4e51794036cbcb7dc5c01b5a7b5b30bc69af2
2019-10-23T09:06:04
move out s_mp_log_pow2, fix limitation of base
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
diff --git a/libtommath_VS2008.vcproj b/libtommath_VS2008.vcproj
index 481b542..1f444cb 100644
--- a/libtommath_VS2008.vcproj
+++ b/libtommath_VS2008.vcproj
@@ -901,6 +901,10 @@
>
</File>
<File
+ RelativePath="s_mp_log_pow2.c"
+ >
+ </File>
+ <File
RelativePath="s_mp_montgomery_reduce_fast.c"
>
</File>
diff --git a/makefile b/makefile
index 7715004..179176b 100644
--- a/makefile
+++ b/makefile
@@ -47,7 +47,7 @@ mp_sqrmod.o mp_sqrt.o mp_sqrtmod_prime.o mp_sub.o mp_sub_d.o mp_submod.o mp_to_r
mp_to_ubin.o mp_ubin_size.o mp_unpack.o mp_xor.o mp_zero.o s_mp_add.o s_mp_balance_mul.o \
s_mp_div_recursive.o s_mp_div_school.o s_mp_div_small.o s_mp_exptmod.o s_mp_exptmod_fast.o s_mp_get_bit.o \
s_mp_invmod_fast.o s_mp_invmod_slow.o s_mp_karatsuba_mul.o s_mp_karatsuba_sqr.o s_mp_log.o s_mp_log_d.o \
-s_mp_montgomery_reduce_fast.o s_mp_mul_digs.o s_mp_mul_digs_fast.o s_mp_mul_high_digs.o \
+s_mp_log_pow2.o s_mp_montgomery_reduce_fast.o s_mp_mul_digs.o s_mp_mul_digs_fast.o s_mp_mul_high_digs.o \
s_mp_mul_high_digs_fast.o s_mp_prime_is_divisible.o s_mp_rand_jenkins.o s_mp_rand_platform.o \
s_mp_reverse.o s_mp_sqr.o s_mp_sqr_fast.o s_mp_sub.o s_mp_toom_mul.o s_mp_toom_sqr.o
diff --git a/makefile.mingw b/makefile.mingw
index 3c3fcf7..8f542f0 100644
--- a/makefile.mingw
+++ b/makefile.mingw
@@ -50,7 +50,7 @@ mp_sqrmod.o mp_sqrt.o mp_sqrtmod_prime.o mp_sub.o mp_sub_d.o mp_submod.o mp_to_r
mp_to_ubin.o mp_ubin_size.o mp_unpack.o mp_xor.o mp_zero.o s_mp_add.o s_mp_balance_mul.o \
s_mp_div_recursive.o s_mp_div_school.o s_mp_div_small.o s_mp_exptmod.o s_mp_exptmod_fast.o s_mp_get_bit.o \
s_mp_invmod_fast.o s_mp_invmod_slow.o s_mp_karatsuba_mul.o s_mp_karatsuba_sqr.o s_mp_log.o s_mp_log_d.o \
-s_mp_montgomery_reduce_fast.o s_mp_mul_digs.o s_mp_mul_digs_fast.o s_mp_mul_high_digs.o \
+s_mp_log_pow2.o s_mp_montgomery_reduce_fast.o s_mp_mul_digs.o s_mp_mul_digs_fast.o s_mp_mul_high_digs.o \
s_mp_mul_high_digs_fast.o s_mp_prime_is_divisible.o s_mp_rand_jenkins.o s_mp_rand_platform.o \
s_mp_reverse.o s_mp_sqr.o s_mp_sqr_fast.o s_mp_sub.o s_mp_toom_mul.o s_mp_toom_sqr.o
diff --git a/makefile.msvc b/makefile.msvc
index c42ca12..3050b6c 100644
--- a/makefile.msvc
+++ b/makefile.msvc
@@ -42,7 +42,7 @@ mp_sqrmod.obj mp_sqrt.obj mp_sqrtmod_prime.obj mp_sub.obj mp_sub_d.obj mp_submod
mp_to_ubin.obj mp_ubin_size.obj mp_unpack.obj mp_xor.obj mp_zero.obj s_mp_add.obj s_mp_balance_mul.obj \
s_mp_div_recursive.obj s_mp_div_school.obj s_mp_div_small.obj s_mp_exptmod.obj s_mp_exptmod_fast.obj s_mp_get_bit.obj \
s_mp_invmod_fast.obj s_mp_invmod_slow.obj s_mp_karatsuba_mul.obj s_mp_karatsuba_sqr.obj s_mp_log.obj s_mp_log_d.obj \
-s_mp_montgomery_reduce_fast.obj s_mp_mul_digs.obj s_mp_mul_digs_fast.obj s_mp_mul_high_digs.obj \
+s_mp_log_pow2.obj s_mp_montgomery_reduce_fast.obj s_mp_mul_digs.obj s_mp_mul_digs_fast.obj s_mp_mul_high_digs.obj \
s_mp_mul_high_digs_fast.obj s_mp_prime_is_divisible.obj s_mp_rand_jenkins.obj s_mp_rand_platform.obj \
s_mp_reverse.obj s_mp_sqr.obj s_mp_sqr_fast.obj s_mp_sub.obj s_mp_toom_mul.obj s_mp_toom_sqr.obj
diff --git a/makefile.shared b/makefile.shared
index 2c9c0e3..cad1196 100644
--- a/makefile.shared
+++ b/makefile.shared
@@ -44,7 +44,7 @@ mp_sqrmod.o mp_sqrt.o mp_sqrtmod_prime.o mp_sub.o mp_sub_d.o mp_submod.o mp_to_r
mp_to_ubin.o mp_ubin_size.o mp_unpack.o mp_xor.o mp_zero.o s_mp_add.o s_mp_balance_mul.o \
s_mp_div_recursive.o s_mp_div_school.o s_mp_div_small.o s_mp_exptmod.o s_mp_exptmod_fast.o s_mp_get_bit.o \
s_mp_invmod_fast.o s_mp_invmod_slow.o s_mp_karatsuba_mul.o s_mp_karatsuba_sqr.o s_mp_log.o s_mp_log_d.o \
-s_mp_montgomery_reduce_fast.o s_mp_mul_digs.o s_mp_mul_digs_fast.o s_mp_mul_high_digs.o \
+s_mp_log_pow2.o s_mp_montgomery_reduce_fast.o s_mp_mul_digs.o s_mp_mul_digs_fast.o s_mp_mul_high_digs.o \
s_mp_mul_high_digs_fast.o s_mp_prime_is_divisible.o s_mp_rand_jenkins.o s_mp_rand_platform.o \
s_mp_reverse.o s_mp_sqr.o s_mp_sqr_fast.o s_mp_sub.o s_mp_toom_mul.o s_mp_toom_sqr.o
diff --git a/makefile.unix b/makefile.unix
index d9d7727..bde330f 100644
--- a/makefile.unix
+++ b/makefile.unix
@@ -51,7 +51,7 @@ mp_sqrmod.o mp_sqrt.o mp_sqrtmod_prime.o mp_sub.o mp_sub_d.o mp_submod.o mp_to_r
mp_to_ubin.o mp_ubin_size.o mp_unpack.o mp_xor.o mp_zero.o s_mp_add.o s_mp_balance_mul.o \
s_mp_div_recursive.o s_mp_div_school.o s_mp_div_small.o s_mp_exptmod.o s_mp_exptmod_fast.o s_mp_get_bit.o \
s_mp_invmod_fast.o s_mp_invmod_slow.o s_mp_karatsuba_mul.o s_mp_karatsuba_sqr.o s_mp_log.o s_mp_log_d.o \
-s_mp_montgomery_reduce_fast.o s_mp_mul_digs.o s_mp_mul_digs_fast.o s_mp_mul_high_digs.o \
+s_mp_log_pow2.o s_mp_montgomery_reduce_fast.o s_mp_mul_digs.o s_mp_mul_digs_fast.o s_mp_mul_high_digs.o \
s_mp_mul_high_digs_fast.o s_mp_prime_is_divisible.o s_mp_rand_jenkins.o s_mp_rand_platform.o \
s_mp_reverse.o s_mp_sqr.o s_mp_sqr_fast.o s_mp_sub.o s_mp_toom_mul.o s_mp_toom_sqr.o
diff --git a/mp_log_u32.c b/mp_log_u32.c
index 2b49fe1..5568568 100644
--- a/mp_log_u32.c
+++ b/mp_log_u32.c
@@ -17,14 +17,8 @@ mp_err mp_log_u32(const mp_int *a, uint32_t base, uint32_t *c)
return MP_VAL;
}
- /* A small shortcut for bases that are powers of two. */
- if ((base & (base - 1u)) == 0u) {
- int y, bit_count;
- for (y=0; (y < 7) && ((base & 1u) == 0u); y++) {
- base >>= 1;
- }
- bit_count = mp_count_bits(a) - 1;
- *c = (uint32_t)(bit_count/y);
+ if (MP_HAS(S_MP_LOG_POW2) && (base & (base - 1u)) == 0u) {
+ *c = s_mp_log_pow2(a, base);
return MP_OKAY;
}
diff --git a/s_mp_log_pow2.c b/s_mp_log_pow2.c
new file mode 100644
index 0000000..74271c6
--- /dev/null
+++ b/s_mp_log_pow2.c
@@ -0,0 +1,12 @@
+#include "tommath_private.h"
+#ifdef S_MP_LOG_POW2_C
+/* LibTomMath, multiple-precision integer library -- Tom St Denis */
+/* SPDX-License-Identifier: Unlicense */
+
+uint32_t s_mp_log_pow2(const mp_int *a, uint32_t base)
+{
+ int y;
+ for (y = 0; (base & 1u) == 0u; y++, base >>= 1) {}
+ return (uint32_t)((mp_count_bits(a) - 1) / y);
+}
+#endif
diff --git a/tommath_class.h b/tommath_class.h
index 5373d91..480c24a 100644
--- a/tommath_class.h
+++ b/tommath_class.h
@@ -158,6 +158,7 @@
# define S_MP_KARATSUBA_SQR_C
# define S_MP_LOG_C
# define S_MP_LOG_D_C
+# define S_MP_LOG_POW2_C
# define S_MP_MONTGOMERY_REDUCE_FAST_C
# define S_MP_MUL_DIGS_C
# define S_MP_MUL_DIGS_FAST_C
@@ -522,9 +523,9 @@
#endif
#if defined(MP_LOG_U32_C)
-# define MP_COUNT_BITS_C
# define S_MP_LOG_C
# define S_MP_LOG_D_C
+# define S_MP_LOG_POW2_C
#endif
#if defined(MP_LSHD_C)
@@ -1174,6 +1175,10 @@
#if defined(S_MP_LOG_D_C)
#endif
+#if defined(S_MP_LOG_POW2_C)
+# define MP_COUNT_BITS_C
+#endif
+
#if defined(S_MP_MONTGOMERY_REDUCE_FAST_C)
# define MP_CLAMP_C
# define MP_CMP_MAG_C
diff --git a/tommath_private.h b/tommath_private.h
index f1211a1..f3aeb8f 100644
--- a/tommath_private.h
+++ b/tommath_private.h
@@ -213,6 +213,7 @@ MP_PRIVATE void s_mp_reverse(unsigned char *s, size_t len);
MP_PRIVATE mp_err s_mp_prime_is_divisible(const mp_int *a, mp_bool *result);
MP_PRIVATE mp_digit s_mp_log_d(mp_digit base, mp_digit n);
MP_PRIVATE mp_err s_mp_log(const mp_int *a, uint32_t base, uint32_t *c);
+MP_PRIVATE uint32_t s_mp_log_pow2(const mp_int *a, uint32_t base);
MP_PRIVATE mp_err s_mp_div_recursive(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r);