/src/dropbear/libtommath/bn_mp_sqrt.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_MP_SQRT_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | /* this function is less generic than mp_n_root, simpler and faster */ |
7 | | mp_err mp_sqrt(const mp_int *arg, mp_int *ret) |
8 | 5 | { |
9 | 5 | mp_err err; |
10 | 5 | mp_int t1, t2; |
11 | | |
12 | | /* must be positive */ |
13 | 5 | if (arg->sign == MP_NEG) { |
14 | 0 | return MP_VAL; |
15 | 0 | } |
16 | | |
17 | | /* easy out */ |
18 | 5 | if (MP_IS_ZERO(arg)) { |
19 | 0 | mp_zero(ret); |
20 | 0 | return MP_OKAY; |
21 | 0 | } |
22 | | |
23 | 5 | if ((err = mp_init_copy(&t1, arg)) != MP_OKAY) { |
24 | 0 | return err; |
25 | 0 | } |
26 | | |
27 | 5 | if ((err = mp_init(&t2)) != MP_OKAY) { |
28 | 0 | goto E2; |
29 | 0 | } |
30 | | |
31 | | /* First approx. (not very bad for large arg) */ |
32 | 5 | mp_rshd(&t1, t1.used/2); |
33 | | |
34 | | /* t1 > 0 */ |
35 | 5 | if ((err = mp_div(arg, &t1, &t2, NULL)) != MP_OKAY) { |
36 | 0 | goto E1; |
37 | 0 | } |
38 | 5 | if ((err = mp_add(&t1, &t2, &t1)) != MP_OKAY) { |
39 | 0 | goto E1; |
40 | 0 | } |
41 | 5 | if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) { |
42 | 0 | goto E1; |
43 | 0 | } |
44 | | /* And now t1 > sqrt(arg) */ |
45 | 136 | do { |
46 | 136 | if ((err = mp_div(arg, &t1, &t2, NULL)) != MP_OKAY) { |
47 | 0 | goto E1; |
48 | 0 | } |
49 | 136 | if ((err = mp_add(&t1, &t2, &t1)) != MP_OKAY) { |
50 | 0 | goto E1; |
51 | 0 | } |
52 | 136 | if ((err = mp_div_2(&t1, &t1)) != MP_OKAY) { |
53 | 0 | goto E1; |
54 | 0 | } |
55 | | /* t1 >= sqrt(arg) >= t2 at this point */ |
56 | 136 | } while (mp_cmp_mag(&t1, &t2) == MP_GT); |
57 | | |
58 | 5 | mp_exch(&t1, ret); |
59 | | |
60 | 5 | E1: |
61 | 5 | mp_clear(&t2); |
62 | 5 | E2: |
63 | 5 | mp_clear(&t1); |
64 | 5 | return err; |
65 | 5 | } |
66 | | |
67 | | #endif |