From 41bd4e38da467b22655ca4b81fda22bd3afd6f95 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Fri, 5 Apr 2019 20:04:40 -0700 Subject: mpi: use integer math for radix length. * mpi/logtab.h: Regenerated. (s_logv_2): Now table of scaled integers. (MP_LOG_SCALE): New constant. * mpi/make-logtab.txr (scale, type): New variables. Generate integer table with log2 values scaled by the scale factor, rounded up. * mpi/config.h (MP_LOGTAB): Removed. We always use the table. * mpi/mpi.c: Unconditionally include logtab.h. (LOG_V_2): Macro removed. (s_mp_outlen): Rewritten using scaled integer math. Overflow is avoided by splitting the input into a part that is an exact multiple of the scale factor, and a remaining part. Only the remaining part need be multiplied by a value from the table before dividing by the scale factor. --- mpi/mpi.c | 16 +++++----------- 1 file changed, 5 insertions(+), 11 deletions(-) (limited to 'mpi/mpi.c') diff --git a/mpi/mpi.c b/mpi/mpi.c index 579a43a6..9ece8047 100644 --- a/mpi/mpi.c +++ b/mpi/mpi.c @@ -43,17 +43,7 @@ extern mem_t *chk_calloc(size_t n, size_t size); #define DIAG(T,V) #endif -/* If MP_LOGTAB is not defined, use the math library to compute the - * logarithms on the fly. Otherwise, use the static table below. - * Pick which works best for your system. - */ -#if MP_LOGTAB #include "logtab.h" -#define LOG_V_2(R) s_logv_2[(R)] -#else -#include -#define LOG_V_2(R) (log(2.0)/log(R)) -#endif /* Default precision for newly created mp_int's */ static mp_size s_mp_defprec = MP_DEFPREC; @@ -4147,5 +4137,9 @@ char s_mp_todigit(int val, int r, int low) */ size_t s_mp_outlen(mp_size bits, int r) { - return convert(size_t, convert(double, bits) * LOG_V_2(r) + 0.5); + mp_size units = bits / MP_LOG_SCALE; + mp_size rem = bits % MP_LOG_SCALE; + mp_size log2 = s_logv_2[r]; + + return convert(size_t, units * log2 + (rem * log2 + (MP_LOG_SCALE - 1)) / MP_LOG_SCALE); } -- cgit v1.2.3