diff options
author | Miloslav Trmač <mitr@redhat.com> | 2010-09-06 15:00:17 +0200 |
---|---|---|
committer | Miloslav Trmač <mitr@redhat.com> | 2010-09-06 15:00:17 +0200 |
commit | c61c13594953d462597ed18d6c77e736878ff9d9 (patch) | |
tree | 583b7cb956cb9fce6c630cc634e772942e3bbaf7 /crypto/userspace/libtommath | |
parent | 9cab3a1a9660ed5f798b063aa7e827eb0c95ba94 (diff) | |
parent | 8afc069c742f80d3e383ba3d0e38697aeeeb147b (diff) | |
download | kernel-crypto-c61c13594953d462597ed18d6c77e736878ff9d9.tar.gz kernel-crypto-c61c13594953d462597ed18d6c77e736878ff9d9.tar.xz kernel-crypto-c61c13594953d462597ed18d6c77e736878ff9d9.zip |
Merge branch 'standalone-master' into standalone-renamencr-standalone-rename
Conflicts:
crypto/userspace/libtomcrypt/misc/qsort.c
crypto/userspace/libtommath/bn_mp_and.c
crypto/userspace/libtommath/bn_mp_exteuclid.c
crypto/userspace/libtommath/bn_mp_jacobi.c
crypto/userspace/libtommath/bn_mp_or.c
crypto/userspace/libtommath/bn_mp_prime_fermat.c
crypto/userspace/libtommath/bn_mp_radix_size.c
crypto/userspace/libtommath/bn_mp_radix_smap.c
crypto/userspace/libtommath/bn_mp_read_radix.c
crypto/userspace/libtommath/bn_mp_sqrt.c
crypto/userspace/libtommath/bn_mp_toradix.c
crypto/userspace/libtommath/bn_mp_toradix_n.c
crypto/userspace/libtommath/bn_mp_xor.c
examples/Makefile
examples/ncr.c
examples/pk.c
Diffstat (limited to 'crypto/userspace/libtommath')
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_and.c | 57 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_div.c | 2 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_div_3.c | 2 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_div_d.c | 2 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_exteuclid.c | 82 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_jacobi.c | 105 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_or.c | 50 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_prime_fermat.c | 62 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_radix_size.c | 78 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_radix_smap.c | 24 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_read_radix.c | 85 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_sqrt.c | 81 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_toradix.c | 75 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_toradix_n.c | 88 | ||||
-rw-r--r-- | crypto/userspace/libtommath/bn_mp_xor.c | 51 | ||||
-rw-r--r-- | crypto/userspace/libtommath/tommath.h | 19 |
16 files changed, 19 insertions, 844 deletions
diff --git a/crypto/userspace/libtommath/bn_mp_and.c b/crypto/userspace/libtommath/bn_mp_and.c deleted file mode 100644 index 8ea22878f91..00000000000 --- a/crypto/userspace/libtommath/bn_mp_and.c +++ /dev/null @@ -1,57 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_AND_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* AND two ints together */ -int -mp_and (mp_int * a, mp_int * b, mp_int * c) -{ - int res, ix, px; - mp_int t, *x; - - if (a->used > b->used) { - if ((res = mp_init_copy (&t, a)) != MP_OKAY) { - return res; - } - px = b->used; - x = b; - } else { - if ((res = mp_init_copy (&t, b)) != MP_OKAY) { - return res; - } - px = a->used; - x = a; - } - - for (ix = 0; ix < px; ix++) { - t.dp[ix] &= x->dp[ix]; - } - - /* zero digits above the last from the smallest mp_int */ - for (; ix < t.used; ix++) { - t.dp[ix] = 0; - } - - mp_clamp (&t); - mp_exch (c, &t); - mp_clear (&t); - return MP_OKAY; -} -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_and.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_div.c b/crypto/userspace/libtommath/bn_mp_div.c index aee9c94324d..723c8b503dd 100644 --- a/crypto/userspace/libtommath/bn_mp_div.c +++ b/crypto/userspace/libtommath/bn_mp_div.c @@ -195,7 +195,7 @@ int mp_div (mp_int * a, mp_int * b, mp_int * c, mp_int * d) mp_word tmp; tmp = ((mp_word) x.dp[i]) << ((mp_word) DIGIT_BIT); tmp |= ((mp_word) x.dp[i - 1]); - tmp /= ((mp_word) y.dp[t]); + tmp = word_div_int(tmp, (int)y.dp[t]); if (tmp > (mp_word) MP_MASK) tmp = MP_MASK; q.dp[i - t - 1] = (mp_digit) (tmp & (mp_word) (MP_MASK)); diff --git a/crypto/userspace/libtommath/bn_mp_div_3.c b/crypto/userspace/libtommath/bn_mp_div_3.c index 3c60269ecea..608e759e366 100644 --- a/crypto/userspace/libtommath/bn_mp_div_3.c +++ b/crypto/userspace/libtommath/bn_mp_div_3.c @@ -25,7 +25,7 @@ mp_div_3 (mp_int * a, mp_int *c, mp_digit * d) int res, ix; /* b = 2**DIGIT_BIT / 3 */ - b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3); + b = word_div_int (((mp_word)1) << DIGIT_BIT, 3); if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { return res; diff --git a/crypto/userspace/libtommath/bn_mp_div_d.c b/crypto/userspace/libtommath/bn_mp_div_d.c index 6a26d4f0cf6..63efc2cfa69 100644 --- a/crypto/userspace/libtommath/bn_mp_div_d.c +++ b/crypto/userspace/libtommath/bn_mp_div_d.c @@ -87,7 +87,7 @@ int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d) w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]); if (w >= b) { - t = (mp_digit)(w / b); + t = (mp_digit)(word_div_int(w, b)); w -= ((mp_word)t) * ((mp_word)b); } else { t = 0; diff --git a/crypto/userspace/libtommath/bn_mp_exteuclid.c b/crypto/userspace/libtommath/bn_mp_exteuclid.c deleted file mode 100644 index e6c4ce2b853..00000000000 --- a/crypto/userspace/libtommath/bn_mp_exteuclid.c +++ /dev/null @@ -1,82 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_EXTEUCLID_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* Extended euclidean algorithm of (a, b) produces - a*u1 + b*u2 = u3 - */ -int mp_exteuclid(mp_int *a, mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3) -{ - mp_int u1,u2,u3,v1,v2,v3,t1,t2,t3,q,tmp; - int err; - - if ((err = mp_init_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL)) != MP_OKAY) { - return err; - } - - /* initialize, (u1,u2,u3) = (1,0,a) */ - mp_set(&u1, 1); - if ((err = mp_copy(a, &u3)) != MP_OKAY) { goto _ERR; } - - /* initialize, (v1,v2,v3) = (0,1,b) */ - mp_set(&v2, 1); - if ((err = mp_copy(b, &v3)) != MP_OKAY) { goto _ERR; } - - /* loop while v3 != 0 */ - while (mp_iszero(&v3) == MP_NO) { - /* q = u3/v3 */ - if ((err = mp_div(&u3, &v3, &q, NULL)) != MP_OKAY) { goto _ERR; } - - /* (t1,t2,t3) = (u1,u2,u3) - (v1,v2,v3)q */ - if ((err = mp_mul(&v1, &q, &tmp)) != MP_OKAY) { goto _ERR; } - if ((err = mp_sub(&u1, &tmp, &t1)) != MP_OKAY) { goto _ERR; } - if ((err = mp_mul(&v2, &q, &tmp)) != MP_OKAY) { goto _ERR; } - if ((err = mp_sub(&u2, &tmp, &t2)) != MP_OKAY) { goto _ERR; } - if ((err = mp_mul(&v3, &q, &tmp)) != MP_OKAY) { goto _ERR; } - if ((err = mp_sub(&u3, &tmp, &t3)) != MP_OKAY) { goto _ERR; } - - /* (u1,u2,u3) = (v1,v2,v3) */ - if ((err = mp_copy(&v1, &u1)) != MP_OKAY) { goto _ERR; } - if ((err = mp_copy(&v2, &u2)) != MP_OKAY) { goto _ERR; } - if ((err = mp_copy(&v3, &u3)) != MP_OKAY) { goto _ERR; } - - /* (v1,v2,v3) = (t1,t2,t3) */ - if ((err = mp_copy(&t1, &v1)) != MP_OKAY) { goto _ERR; } - if ((err = mp_copy(&t2, &v2)) != MP_OKAY) { goto _ERR; } - if ((err = mp_copy(&t3, &v3)) != MP_OKAY) { goto _ERR; } - } - - /* make sure U3 >= 0 */ - if (u3.sign == MP_NEG) { - mp_neg(&u1, &u1); - mp_neg(&u2, &u2); - mp_neg(&u3, &u3); - } - - /* copy result out */ - if (U1 != NULL) { mp_exch(U1, &u1); } - if (U2 != NULL) { mp_exch(U2, &u2); } - if (U3 != NULL) { mp_exch(U3, &u3); } - - err = MP_OKAY; -_ERR: mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL); - return err; -} -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_exteuclid.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_jacobi.c b/crypto/userspace/libtommath/bn_mp_jacobi.c deleted file mode 100644 index 91cfeeade4c..00000000000 --- a/crypto/userspace/libtommath/bn_mp_jacobi.c +++ /dev/null @@ -1,105 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_JACOBI_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* computes the jacobi c = (a | n) (or Legendre if n is prime) - * HAC pp. 73 Algorithm 2.149 - */ -int mp_jacobi (mp_int * a, mp_int * p, int *c) -{ - mp_int a1, p1; - int k, s, r, res; - mp_digit residue; - - /* if p <= 0 return MP_VAL */ - if (mp_cmp_d(p, 0) != MP_GT) { - return MP_VAL; - } - - /* step 1. if a == 0, return 0 */ - if (mp_iszero (a) == 1) { - *c = 0; - return MP_OKAY; - } - - /* step 2. if a == 1, return 1 */ - if (mp_cmp_d (a, 1) == MP_EQ) { - *c = 1; - return MP_OKAY; - } - - /* default */ - s = 0; - - /* step 3. write a = a1 * 2**k */ - if ((res = mp_init_copy (&a1, a)) != MP_OKAY) { - return res; - } - - if ((res = mp_init (&p1)) != MP_OKAY) { - goto LBL_A1; - } - - /* divide out larger power of two */ - k = mp_cnt_lsb(&a1); - if ((res = mp_div_2d(&a1, k, &a1, NULL)) != MP_OKAY) { - goto LBL_P1; - } - - /* step 4. if e is even set s=1 */ - if ((k & 1) == 0) { - s = 1; - } else { - /* else set s=1 if p = 1/7 (mod 8) or s=-1 if p = 3/5 (mod 8) */ - residue = p->dp[0] & 7; - - if (residue == 1 || residue == 7) { - s = 1; - } else if (residue == 3 || residue == 5) { - s = -1; - } - } - - /* step 5. if p == 3 (mod 4) *and* a1 == 3 (mod 4) then s = -s */ - if ( ((p->dp[0] & 3) == 3) && ((a1.dp[0] & 3) == 3)) { - s = -s; - } - - /* if a1 == 1 we're done */ - if (mp_cmp_d (&a1, 1) == MP_EQ) { - *c = s; - } else { - /* n1 = n mod a1 */ - if ((res = mp_mod (p, &a1, &p1)) != MP_OKAY) { - goto LBL_P1; - } - if ((res = mp_jacobi (&p1, &a1, &r)) != MP_OKAY) { - goto LBL_P1; - } - *c = s * r; - } - - /* done */ - res = MP_OKAY; -LBL_P1:mp_clear (&p1); -LBL_A1:mp_clear (&a1); - return res; -} -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_jacobi.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_or.c b/crypto/userspace/libtommath/bn_mp_or.c deleted file mode 100644 index bff49954896..00000000000 --- a/crypto/userspace/libtommath/bn_mp_or.c +++ /dev/null @@ -1,50 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_OR_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* OR two ints together */ -int mp_or (mp_int * a, mp_int * b, mp_int * c) -{ - int res, ix, px; - mp_int t, *x; - - if (a->used > b->used) { - if ((res = mp_init_copy (&t, a)) != MP_OKAY) { - return res; - } - px = b->used; - x = b; - } else { - if ((res = mp_init_copy (&t, b)) != MP_OKAY) { - return res; - } - px = a->used; - x = a; - } - - for (ix = 0; ix < px; ix++) { - t.dp[ix] |= x->dp[ix]; - } - mp_clamp (&t); - mp_exch (c, &t); - mp_clear (&t); - return MP_OKAY; -} -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_or.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_prime_fermat.c b/crypto/userspace/libtommath/bn_mp_prime_fermat.c deleted file mode 100644 index c23d77f6de7..00000000000 --- a/crypto/userspace/libtommath/bn_mp_prime_fermat.c +++ /dev/null @@ -1,62 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_PRIME_FERMAT_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* performs one Fermat test. - * - * If "a" were prime then b**a == b (mod a) since the order of - * the multiplicative sub-group would be phi(a) = a-1. That means - * it would be the same as b**(a mod (a-1)) == b**1 == b (mod a). - * - * Sets result to 1 if the congruence holds, or zero otherwise. - */ -int mp_prime_fermat (mp_int * a, mp_int * b, int *result) -{ - mp_int t; - int err; - - /* default to composite */ - *result = MP_NO; - - /* ensure b > 1 */ - if (mp_cmp_d(b, 1) != MP_GT) { - return MP_VAL; - } - - /* init t */ - if ((err = mp_init (&t)) != MP_OKAY) { - return err; - } - - /* compute t = b**a mod a */ - if ((err = mp_exptmod (b, a, a, &t)) != MP_OKAY) { - goto LBL_T; - } - - /* is it equal to b? */ - if (mp_cmp (&t, b) == MP_EQ) { - *result = MP_YES; - } - - err = MP_OKAY; -LBL_T:mp_clear (&t); - return err; -} -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_prime_fermat.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_radix_size.c b/crypto/userspace/libtommath/bn_mp_radix_size.c deleted file mode 100644 index 1b61e3a1be9..00000000000 --- a/crypto/userspace/libtommath/bn_mp_radix_size.c +++ /dev/null @@ -1,78 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_RADIX_SIZE_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* returns size of ASCII reprensentation */ -int mp_radix_size (mp_int * a, int radix, int *size) -{ - int res, digs; - mp_int t; - mp_digit d; - - *size = 0; - - /* special case for binary */ - if (radix == 2) { - *size = mp_count_bits (a) + (a->sign == MP_NEG ? 1 : 0) + 1; - return MP_OKAY; - } - - /* make sure the radix is in range */ - if (radix < 2 || radix > 64) { - return MP_VAL; - } - - if (mp_iszero(a) == MP_YES) { - *size = 2; - return MP_OKAY; - } - - /* digs is the digit count */ - digs = 0; - - /* if it's negative add one for the sign */ - if (a->sign == MP_NEG) { - ++digs; - } - - /* init a copy of the input */ - if ((res = mp_init_copy (&t, a)) != MP_OKAY) { - return res; - } - - /* force temp to positive */ - t.sign = MP_ZPOS; - - /* fetch out all of the digits */ - while (mp_iszero (&t) == MP_NO) { - if ((res = mp_div_d (&t, (mp_digit) radix, &t, &d)) != MP_OKAY) { - mp_clear (&t); - return res; - } - ++digs; - } - mp_clear (&t); - - /* return digs + 1, the 1 is for the NULL byte that would be required. */ - *size = digs + 1; - return MP_OKAY; -} - -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_radix_size.c,v $ */ -/* $Revision: 1.5 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_radix_smap.c b/crypto/userspace/libtommath/bn_mp_radix_smap.c deleted file mode 100644 index 7d72feb84e6..00000000000 --- a/crypto/userspace/libtommath/bn_mp_radix_smap.c +++ /dev/null @@ -1,24 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_RADIX_SMAP_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* chars used in radix conversions */ -const char *mp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/"; -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_radix_smap.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_read_radix.c b/crypto/userspace/libtommath/bn_mp_read_radix.c deleted file mode 100644 index 91c46c22f74..00000000000 --- a/crypto/userspace/libtommath/bn_mp_read_radix.c +++ /dev/null @@ -1,85 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_READ_RADIX_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* read a string [ASCII] in a given radix */ -int mp_read_radix (mp_int * a, const char *str, int radix) -{ - int y, res, neg; - char ch; - - /* zero the digit bignum */ - mp_zero(a); - - /* make sure the radix is ok */ - if (radix < 2 || radix > 64) { - return MP_VAL; - } - - /* if the leading digit is a - * minus set the sign to negative. - */ - if (*str == '-') { - ++str; - neg = MP_NEG; - } else { - neg = MP_ZPOS; - } - - /* set the integer to the default of zero */ - mp_zero (a); - - /* process each digit of the string */ - while (*str) { - /* if the radix < 36 the conversion is case insensitive - * this allows numbers like 1AB and 1ab to represent the same value - * [e.g. in hex] - */ - ch = (char) ((radix < 36) ? toupper (*str) : *str); - for (y = 0; y < 64; y++) { - if (ch == mp_s_rmap[y]) { - break; - } - } - - /* if the char was found in the map - * and is less than the given radix add it - * to the number, otherwise exit the loop. - */ - if (y < radix) { - if ((res = mp_mul_d (a, (mp_digit) radix, a)) != MP_OKAY) { - return res; - } - if ((res = mp_add_d (a, (mp_digit) y, a)) != MP_OKAY) { - return res; - } - } else { - break; - } - ++str; - } - - /* set the sign only if a != 0 */ - if (mp_iszero(a) != 1) { - a->sign = neg; - } - return MP_OKAY; -} -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_read_radix.c,v $ */ -/* $Revision: 1.5 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_sqrt.c b/crypto/userspace/libtommath/bn_mp_sqrt.c deleted file mode 100644 index 8fd057ceedb..00000000000 --- a/crypto/userspace/libtommath/bn_mp_sqrt.c +++ /dev/null @@ -1,81 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_SQRT_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* this function is less generic than mp_n_root, simpler and faster */ -int mp_sqrt(mp_int *arg, mp_int *ret) -{ - int res; - mp_int t1,t2; - - /* must be positive */ - if (arg->sign == MP_NEG) { - return MP_VAL; - } - - /* easy out */ - if (mp_iszero(arg) == MP_YES) { - mp_zero(ret); - return MP_OKAY; - } - - if ((res = mp_init_copy(&t1, arg)) != MP_OKAY) { - return res; - } - - if ((res = mp_init(&t2)) != MP_OKAY) { - goto E2; - } - - /* First approx. (not very bad for large arg) */ - mp_rshd (&t1,t1.used/2); - - /* t1 > 0 */ - if ((res = mp_div(arg,&t1,&t2,NULL)) != MP_OKAY) { - goto E1; - } - if ((res = mp_add(&t1,&t2,&t1)) != MP_OKAY) { - goto E1; - } - 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) { - goto E1; - } - if ((res = mp_add(&t1,&t2,&t1)) != MP_OKAY) { - goto E1; - } - 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); - - mp_exch(&t1,ret); - -E1: mp_clear(&t2); -E2: mp_clear(&t1); - return res; -} - -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_sqrt.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_toradix.c b/crypto/userspace/libtommath/bn_mp_toradix.c deleted file mode 100644 index 0adc28d2fdb..00000000000 --- a/crypto/userspace/libtommath/bn_mp_toradix.c +++ /dev/null @@ -1,75 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_TORADIX_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* stores a bignum as a ASCII string in a given radix (2..64) */ -int mp_toradix (mp_int * a, char *str, int radix) -{ - int res, digs; - mp_int t; - mp_digit d; - char *_s = str; - - /* check range of the radix */ - if (radix < 2 || radix > 64) { - return MP_VAL; - } - - /* quick out if its zero */ - if (mp_iszero(a) == 1) { - *str++ = '0'; - *str = '\0'; - return MP_OKAY; - } - - if ((res = mp_init_copy (&t, a)) != MP_OKAY) { - return res; - } - - /* if it is negative output a - */ - if (t.sign == MP_NEG) { - ++_s; - *str++ = '-'; - t.sign = MP_ZPOS; - } - - digs = 0; - while (mp_iszero (&t) == 0) { - if ((res = mp_div_d (&t, (mp_digit) radix, &t, &d)) != MP_OKAY) { - mp_clear (&t); - return res; - } - *str++ = mp_s_rmap[d]; - ++digs; - } - - /* reverse the digits of the string. In this case _s points - * to the first digit [exluding the sign] of the number] - */ - bn_reverse ((unsigned char *)_s, digs); - - /* append a NULL so the string is properly terminated */ - *str = '\0'; - - mp_clear (&t); - return MP_OKAY; -} - -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_toradix.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_toradix_n.c b/crypto/userspace/libtommath/bn_mp_toradix_n.c deleted file mode 100644 index 796ed55c65e..00000000000 --- a/crypto/userspace/libtommath/bn_mp_toradix_n.c +++ /dev/null @@ -1,88 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_TORADIX_N_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* stores a bignum as a ASCII string in a given radix (2..64) - * - * Stores upto maxlen-1 chars and always a NULL byte - */ -int mp_toradix_n(mp_int * a, char *str, int radix, int maxlen) -{ - int res, digs; - mp_int t; - mp_digit d; - char *_s = str; - - /* check range of the maxlen, radix */ - if (maxlen < 2 || radix < 2 || radix > 64) { - return MP_VAL; - } - - /* quick out if its zero */ - if (mp_iszero(a) == MP_YES) { - *str++ = '0'; - *str = '\0'; - return MP_OKAY; - } - - if ((res = mp_init_copy (&t, a)) != MP_OKAY) { - return res; - } - - /* if it is negative output a - */ - if (t.sign == MP_NEG) { - /* we have to reverse our digits later... but not the - sign!! */ - ++_s; - - /* store the flag and mark the number as positive */ - *str++ = '-'; - t.sign = MP_ZPOS; - - /* subtract a char */ - --maxlen; - } - - digs = 0; - while (mp_iszero (&t) == 0) { - if (--maxlen < 1) { - /* no more room */ - break; - } - if ((res = mp_div_d (&t, (mp_digit) radix, &t, &d)) != MP_OKAY) { - mp_clear (&t); - return res; - } - *str++ = mp_s_rmap[d]; - ++digs; - } - - /* reverse the digits of the string. In this case _s points - * to the first digit [exluding the sign] of the number - */ - bn_reverse ((unsigned char *)_s, digs); - - /* append a NULL so the string is properly terminated */ - *str = '\0'; - - mp_clear (&t); - return MP_OKAY; -} - -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_toradix_n.c,v $ */ -/* $Revision: 1.5 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/bn_mp_xor.c b/crypto/userspace/libtommath/bn_mp_xor.c deleted file mode 100644 index 59ff2e18320..00000000000 --- a/crypto/userspace/libtommath/bn_mp_xor.c +++ /dev/null @@ -1,51 +0,0 @@ -#include <tommath.h> -#ifdef BN_MP_XOR_C -/* LibTomMath, multiple-precision integer library -- Tom St Denis - * - * LibTomMath is a library that provides multiple-precision - * integer arithmetic as well as number theoretic functionality. - * - * The library was designed directly after the MPI library by - * Michael Fromberger but has been written from scratch with - * additional optimizations in place. - * - * The library is free for all purposes without any express - * guarantee it works. - * - * Tom St Denis, tomstdenis@gmail.com, http://libtom.org - */ - -/* XOR two ints together */ -int -mp_xor (mp_int * a, mp_int * b, mp_int * c) -{ - int res, ix, px; - mp_int t, *x; - - if (a->used > b->used) { - if ((res = mp_init_copy (&t, a)) != MP_OKAY) { - return res; - } - px = b->used; - x = b; - } else { - if ((res = mp_init_copy (&t, b)) != MP_OKAY) { - return res; - } - px = a->used; - x = a; - } - - for (ix = 0; ix < px; ix++) { - t.dp[ix] ^= x->dp[ix]; - } - mp_clamp (&t); - mp_exch (c, &t); - mp_clear (&t); - return MP_OKAY; -} -#endif - -/* $Source: /cvs/libtom/libtommath/bn_mp_xor.c,v $ */ -/* $Revision: 1.4 $ */ -/* $Date: 2006/12/28 01:25:13 $ */ diff --git a/crypto/userspace/libtommath/tommath.h b/crypto/userspace/libtommath/tommath.h index 31ded829977..3fa7ae89853 100644 --- a/crypto/userspace/libtommath/tommath.h +++ b/crypto/userspace/libtommath/tommath.h @@ -20,6 +20,7 @@ #include <linux/slab.h> #include <linux/random.h> #include <linux/ctype.h> +#include <linux/math64.h> #define CHAR_BIT sizeof(uint8_t)*8 @@ -64,16 +65,23 @@ extern "C" { * At the very least a mp_digit must be able to hold 7 bits * [any size beyond that is ok provided it doesn't overflow the data type] */ -#if BITS_PER_LONG <= 32 + +/* FIXME: This can be improved, but requires to use 128bit division + * on 64bit machines, which is not available in kernel now. + */ +#if BITS_PER_LONG < 32 typedef uint16_t mp_digit; typedef uint32_t mp_word; # define DIGIT_BIT 15 -#elif BITS_PER_LONG == 64 - +#elif BITS_PER_LONG <= 64 + typedef uint32_t mp_digit; typedef uint64_t mp_word; + +# define word_div_int(x,y) div_u64((x),(y)) + # define DIGIT_BIT 31 #endif @@ -88,6 +96,11 @@ extern "C" { #endif +#ifndef word_div_int +# define word_div_int(x,y) ((x)/(y)) +#endif + + /* define heap macros */ #ifndef XMALLOC # define XMALLOC(x) kmalloc(x, GFP_KERNEL) |