Mercurial > dropbear
comparison libtommath/bn_mp_sqrt.c @ 1739:13d834efc376 fuzz
merge from main
author | Matt Johnston <matt@ucc.asn.au> |
---|---|
date | Thu, 15 Oct 2020 19:55:15 +0800 |
parents | 1051e4eea25a |
children |
comparison
equal
deleted
inserted
replaced
1562:768ebf737aa0 | 1739:13d834efc376 |
---|---|
1 #include <tommath_private.h> | 1 #include "tommath_private.h" |
2 #ifdef BN_MP_SQRT_C | 2 #ifdef BN_MP_SQRT_C |
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis | 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 * | 4 /* SPDX-License-Identifier: Unlicense */ |
5 * LibTomMath is a library that provides multiple-precision | |
6 * integer arithmetic as well as number theoretic functionality. | |
7 * | |
8 * The library was designed directly after the MPI library by | |
9 * Michael Fromberger but has been written from scratch with | |
10 * additional optimizations in place. | |
11 * | |
12 * The library is free for all purposes without any express | |
13 * guarantee it works. | |
14 * | |
15 * Tom St Denis, [email protected], http://libtom.org | |
16 */ | |
17 | 5 |
18 /* this function is less generic than mp_n_root, simpler and faster */ | 6 /* this function is less generic than mp_n_root, simpler and faster */ |
19 int mp_sqrt(mp_int *arg, mp_int *ret) | 7 mp_err mp_sqrt(const mp_int *arg, mp_int *ret) |
20 { | 8 { |
21 int res; | 9 mp_err err; |
22 mp_int t1,t2; | 10 mp_int t1, t2; |
23 | 11 |
24 /* must be positive */ | 12 /* must be positive */ |
25 if (arg->sign == MP_NEG) { | 13 if (arg->sign == MP_NEG) { |
26 return MP_VAL; | 14 return MP_VAL; |
27 } | 15 } |
28 | 16 |
29 /* easy out */ | 17 /* easy out */ |
30 if (mp_iszero(arg) == MP_YES) { | 18 if (MP_IS_ZERO(arg)) { |
31 mp_zero(ret); | 19 mp_zero(ret); |
32 return MP_OKAY; | 20 return MP_OKAY; |
33 } | 21 } |
34 | 22 |
35 if ((res = mp_init_copy(&t1, arg)) != MP_OKAY) { | 23 if ((err = mp_init_copy(&t1, arg)) != MP_OKAY) { |
36 return res; | 24 return err; |
37 } | 25 } |
38 | 26 |
39 if ((res = mp_init(&t2)) != MP_OKAY) { | 27 if ((err = mp_init(&t2)) != MP_OKAY) { |
40 goto E2; | 28 goto E2; |
41 } | 29 } |
42 | 30 |
43 /* First approx. (not very bad for large arg) */ | 31 /* First approx. (not very bad for large arg) */ |
44 mp_rshd (&t1,t1.used/2); | 32 mp_rshd(&t1, t1.used/2); |
45 | 33 |
46 /* t1 > 0 */ | 34 /* t1 > 0 */ |
47 if ((res = mp_div(arg,&t1,&t2,NULL)) != MP_OKAY) { | 35 if ((err = mp_div(arg, &t1, &t2, NULL)) != MP_OKAY) { |
48 goto E1; | |
49 } | |
50 if ((res = mp_add(&t1,&t2,&t1)) != MP_OKAY) { | |
51 goto E1; | |
52 } | |
53 if ((res = mp_div_2(&t1,&t1)) != MP_OKAY) { | |
54 goto E1; | |
55 } | |
56 /* And now t1 > sqrt(arg) */ | |
57 do { | |
58 if ((res = mp_div(arg,&t1,&t2,NULL)) != MP_OKAY) { | |
59 goto E1; | 36 goto E1; |
60 } | 37 } |
61 if ((res = mp_add(&t1,&t2,&t1)) != MP_OKAY) { | 38 if ((err = mp_add(&t1, &t2, &t1)) != MP_OKAY) { |
62 goto E1; | 39 goto E1; |
63 } | 40 } |
64 if ((res = mp_div_2(&t1,&t1)) != MP_OKAY) { | 41 if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) { |
65 goto E1; | 42 goto E1; |
66 } | 43 } |
67 /* t1 >= sqrt(arg) >= t2 at this point */ | 44 /* And now t1 > sqrt(arg) */ |
68 } while (mp_cmp_mag(&t1,&t2) == MP_GT); | 45 do { |
46 if ((err = mp_div(arg, &t1, &t2, NULL)) != MP_OKAY) { | |
47 goto E1; | |
48 } | |
49 if ((err = mp_add(&t1, &t2, &t1)) != MP_OKAY) { | |
50 goto E1; | |
51 } | |
52 if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) { | |
53 goto E1; | |
54 } | |
55 /* t1 >= sqrt(arg) >= t2 at this point */ | |
56 } while (mp_cmp_mag(&t1, &t2) == MP_GT); | |
69 | 57 |
70 mp_exch(&t1,ret); | 58 mp_exch(&t1, ret); |
71 | 59 |
72 E1: mp_clear(&t2); | 60 E1: |
73 E2: mp_clear(&t1); | 61 mp_clear(&t2); |
74 return res; | 62 E2: |
63 mp_clear(&t1); | |
64 return err; | |
75 } | 65 } |
76 | 66 |
77 #endif | 67 #endif |
78 | |
79 /* ref: $Format:%D$ */ | |
80 /* git commit: $Format:%H$ */ | |
81 /* commit time: $Format:%ai$ */ |