summaryrefslogtreecommitdiffstats
path: root/libtommath
diff options
context:
space:
mode:
Diffstat (limited to 'libtommath')
-rw-r--r--libtommath/bn_mp_div_d.c25
-rw-r--r--libtommath/bn_mp_get_long_long.c6
-rw-r--r--libtommath/bn_mp_set_long_long.c2
-rw-r--r--libtommath/bn_mp_sqrt.c88
-rw-r--r--libtommath/tommath.h8
-rw-r--r--libtommath/tommath_private.h2
-rwxr-xr-xlibtommath/updatemakes.sh33
7 files changed, 92 insertions, 72 deletions
diff --git a/libtommath/bn_mp_div_d.c b/libtommath/bn_mp_div_d.c
index db4a0a2..c408602 100644
--- a/libtommath/bn_mp_div_d.c
+++ b/libtommath/bn_mp_div_d.c
@@ -15,24 +15,6 @@
* Tom St Denis, tstdenis82@gmail.com, http://libtom.org
*/
-static int s_is_power_of_two(mp_digit b, int *p)
-{
- int x;
-
- /* fast return if no power of two */
- if ((b == 0) || ((b & (b-1)) != 0)) {
- return 0;
- }
-
- for (x = 0; x < DIGIT_BIT; x++) {
- if (b == (((mp_digit)1)<<x)) {
- *p = x;
- return 1;
- }
- }
- return 0;
-}
-
/* single digit division (based on routine from MPI) */
int mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d)
{
@@ -58,7 +40,12 @@ int mp_div_d(const mp_int *a, mp_digit b, mp_int *c, mp_digit *d)
}
/* power of two ? */
- if (s_is_power_of_two(b, &ix) == 1) {
+ if (((b & (b-1)) == 0)) {
+ for (ix = 1; ix < DIGIT_BIT; ix++) {
+ if (b == (((mp_digit)1)<<ix)) {
+ break;
+ }
+ }
if (d != NULL) {
*d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
}
diff --git a/libtommath/bn_mp_get_long_long.c b/libtommath/bn_mp_get_long_long.c
index 838c3c3..a363f60 100644
--- a/libtommath/bn_mp_get_long_long.c
+++ b/libtommath/bn_mp_get_long_long.c
@@ -16,17 +16,17 @@
*/
/* get the lower unsigned long long of an mp_int, platform dependent */
-unsigned long long mp_get_long_long(const mp_int *a)
+Tcl_WideUInt mp_get_long_long(const mp_int *a)
{
int i;
- unsigned long long res;
+ Tcl_WideUInt res;
if (a->used == 0) {
return 0;
}
/* get number of digits of the lsb we have to read */
- i = MIN(a->used, (int)(((sizeof(unsigned long long) * CHAR_BIT) + DIGIT_BIT - 1) / DIGIT_BIT)) - 1;
+ i = MIN(a->used, (int)(((sizeof(Tcl_WideUInt) * CHAR_BIT) + DIGIT_BIT - 1) / DIGIT_BIT)) - 1;
/* get most significant digit of result */
res = DIGIT(a, i);
diff --git a/libtommath/bn_mp_set_long_long.c b/libtommath/bn_mp_set_long_long.c
index 3566b45..0b8be33 100644
--- a/libtommath/bn_mp_set_long_long.c
+++ b/libtommath/bn_mp_set_long_long.c
@@ -16,7 +16,7 @@
*/
/* set a platform dependent unsigned long long int */
-MP_SET_XLONG(mp_set_long_long, unsigned long long)
+MP_SET_XLONG(mp_set_long_long, Tcl_WideUInt)
#endif
/* ref: $Format:%D$ */
diff --git a/libtommath/bn_mp_sqrt.c b/libtommath/bn_mp_sqrt.c
index d70c523..49a1bd0 100644
--- a/libtommath/bn_mp_sqrt.c
+++ b/libtommath/bn_mp_sqrt.c
@@ -15,11 +15,20 @@
* Tom St Denis, tstdenis82@gmail.com, http://libtom.org
*/
+#ifndef NO_FLOATING_POINT
+#include <math.h>
+#endif
+
/* this function is less generic than mp_n_root, simpler and faster */
int mp_sqrt(const mp_int *arg, mp_int *ret)
{
int res;
- mp_int t1, t2;
+ mp_int t1,t2;
+ int i, j, k;
+#ifndef NO_FLOATING_POINT
+ volatile double d;
+ mp_digit dig;
+#endif
/* must be positive */
if (arg->sign == MP_NEG) {
@@ -32,7 +41,9 @@ int mp_sqrt(const mp_int *arg, mp_int *ret)
return MP_OKAY;
}
- if ((res = mp_init_copy(&t1, arg)) != MP_OKAY) {
+ i = (arg->used / 2) - 1;
+ j = 2 * i;
+ if ((res = mp_init_size(&t1, i+2)) != MP_OKAY) {
return res;
}
@@ -40,34 +51,87 @@ int mp_sqrt(const mp_int *arg, mp_int *ret)
goto E2;
}
- /* First approx. (not very bad for large arg) */
- mp_rshd(&t1, t1.used/2);
+ for (k = 0; k < i; ++k) {
+ t1.dp[k] = (mp_digit) 0;
+ }
+
+#ifndef NO_FLOATING_POINT
+
+ /* Estimate the square root using the hardware floating point unit. */
+
+ d = 0.0;
+ for (k = arg->used-1; k >= j; --k) {
+ d = ldexp(d, DIGIT_BIT) + (double)(arg->dp[k]);
+ }
+
+ /*
+ * At this point, d is the nearest floating point number to the most
+ * significant 1 or 2 mp_digits of arg. Extract its square root.
+ */
+
+ d = sqrt(d);
+
+ /* dig is the most significant mp_digit of the square root */
+
+ dig = (mp_digit) ldexp(d, -DIGIT_BIT);
+
+ /*
+ * If the most significant digit is nonzero, find the next digit down
+ * by subtracting DIGIT_BIT times thie most significant digit.
+ * Subtract one from the result so that our initial estimate is always
+ * low.
+ */
+
+ if (dig) {
+ t1.used = i+2;
+ d -= ldexp((double) dig, DIGIT_BIT);
+ if (d >= 1.0) {
+ t1.dp[i+1] = dig;
+ t1.dp[i] = ((mp_digit) d) - 1;
+ } else {
+ t1.dp[i+1] = dig-1;
+ t1.dp[i] = MP_DIGIT_MAX;
+ }
+ } else {
+ t1.used = i+1;
+ t1.dp[i] = ((mp_digit) d) - 1;
+ }
+
+#else
+
+ /* Estimate the square root as having 1 in the most significant place. */
+
+ t1.used = i + 2;
+ t1.dp[i+1] = (mp_digit) 1;
+ t1.dp[i] = (mp_digit) 0;
+
+#endif
/* t1 > 0 */
- if ((res = mp_div(arg, &t1, &t2, NULL)) != MP_OKAY) {
+ if ((res = mp_div(arg,&t1,&t2,NULL)) != MP_OKAY) {
goto E1;
}
- if ((res = mp_add(&t1, &t2, &t1)) != MP_OKAY) {
+ if ((res = mp_add(&t1,&t2,&t1)) != MP_OKAY) {
goto E1;
}
- if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) {
+ if ((res = mp_div_2(&t1,&t1)) != MP_OKAY) {
goto E1;
}
/* And now t1 > sqrt(arg) */
do {
- if ((res = mp_div(arg, &t1, &t2, NULL)) != MP_OKAY) {
+ if ((res = mp_div(arg,&t1,&t2,NULL)) != MP_OKAY) {
goto E1;
}
- if ((res = mp_add(&t1, &t2, &t1)) != MP_OKAY) {
+ if ((res = mp_add(&t1,&t2,&t1)) != MP_OKAY) {
goto E1;
}
- if ((res = mp_div_2(&t1, &t1)) != MP_OKAY) {
+ if ((res = mp_div_2(&t1,&t1)) != MP_OKAY) {
goto E1;
}
/* t1 >= sqrt(arg) >= t2 at this point */
- } while (mp_cmp_mag(&t1, &t2) == MP_GT);
+ } while (mp_cmp_mag(&t1,&t2) == MP_GT);
- mp_exch(&t1, ret);
+ mp_exch(&t1,ret);
E1:
mp_clear(&t2);
diff --git a/libtommath/tommath.h b/libtommath/tommath.h
index 591076e..50a3a81 100644
--- a/libtommath/tommath.h
+++ b/libtommath/tommath.h
@@ -33,11 +33,13 @@ extern "C" {
defined(__sparcv9) || defined(__sparc_v9__) || defined(__sparc64__) || \
defined(__ia64) || defined(__ia64__) || defined(__itanium__) || defined(_M_IA64) || \
defined(__LP64__) || defined(_LP64) || defined(__64BIT__)
-# if !(defined(MP_32BIT) || defined(MP_16BIT) || defined(MP_8BIT))
+# if !(defined(MP_32BIT) || defined(MP_16BIT) || defined(MP_8BIT) || defined(_MSC_VER))
# define MP_64BIT
# endif
#endif
+typedef unsigned long long Tcl_WideUInt;
+
/* some default configurations.
*
* A "mp_digit" must be able to hold DIGIT_BIT + 1 bits
@@ -220,7 +222,7 @@ int mp_set_int(mp_int *a, unsigned long b);
int mp_set_long(mp_int *a, unsigned long b);
/* set a platform dependent unsigned long long value */
-int mp_set_long_long(mp_int *a, unsigned long long b);
+int mp_set_long_long(mp_int *a, Tcl_WideUInt b);
/* get a 32-bit value */
unsigned long mp_get_int(const mp_int *a);
@@ -229,7 +231,7 @@ unsigned long mp_get_int(const mp_int *a);
unsigned long mp_get_long(const mp_int *a);
/* get a platform dependent unsigned long long value */
-unsigned long long mp_get_long_long(const mp_int *a);
+Tcl_WideUInt mp_get_long_long(const mp_int *a);
/* initialize and set a digit */
int mp_init_set(mp_int *a, mp_digit b);
diff --git a/libtommath/tommath_private.h b/libtommath/tommath_private.h
index 087ddcd..be065cd 100644
--- a/libtommath/tommath_private.h
+++ b/libtommath/tommath_private.h
@@ -46,7 +46,7 @@ extern "C" {
# define XFREE free
# define XREALLOC realloc
# define XCALLOC calloc
-#else
+#elif 0
/* prototypes for our heap functions */
extern void *XMALLOC(size_t n);
extern void *XREALLOC(void *p, size_t n);
diff --git a/libtommath/updatemakes.sh b/libtommath/updatemakes.sh
deleted file mode 100755
index 0f9520e..0000000
--- a/libtommath/updatemakes.sh
+++ /dev/null
@@ -1,33 +0,0 @@
-#!/bin/bash
-
-bash genlist.sh > tmplist
-
-perl filter.pl makefile tmplist
-sed -e 's/ *$//' < tmp.delme > makefile
-rm -f tmp.delme
-
-perl filter.pl makefile.icc tmplist
-sed -e 's/ *$//' < tmp.delme > makefile.icc
-rm -f tmp.delme
-
-perl filter.pl makefile.shared tmplist
-sed -e 's/ *$//' < tmp.delme > makefile.shared
-rm -f tmp.delme
-
-perl filter.pl makefile.cygwin_dll tmplist
-sed -e 's/ *$//' < tmp.delme > makefile.cygwin_dll
-rm -f tmp.delme
-
-perl filter.pl makefile.bcc tmplist
-sed -e 's/\.o /.obj /g' -e 's/ *$//' < tmp.delme > makefile.bcc
-rm -f tmp.delme
-
-perl filter.pl makefile.msvc tmplist
-sed -e 's/\.o /.obj /g' -e 's/ *$//' < tmp.delme > makefile.msvc
-rm -f tmp.delme
-
-rm -f tmplist
-
-# ref: $Format:%D$
-# git commit: $Format:%H$
-# commit time: $Format:%ai$
generated by cgit v0.12 at 2024-06-26 08:37:59 (GMT)