Line | Count | Source (jump to first uncovered line) |
1 | | /* mpn_pow_1 -- Compute powers R = U^exp. |
2 | | |
3 | | THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY. THEY'RE ALMOST |
4 | | CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN |
5 | | FUTURE GNU MP RELEASES. |
6 | | |
7 | | Copyright 2002, 2014 Free Software Foundation, Inc. |
8 | | |
9 | | This file is part of the GNU MP Library. |
10 | | |
11 | | The GNU MP Library is free software; you can redistribute it and/or modify |
12 | | it under the terms of either: |
13 | | |
14 | | * the GNU Lesser General Public License as published by the Free |
15 | | Software Foundation; either version 3 of the License, or (at your |
16 | | option) any later version. |
17 | | |
18 | | or |
19 | | |
20 | | * the GNU General Public License as published by the Free Software |
21 | | Foundation; either version 2 of the License, or (at your option) any |
22 | | later version. |
23 | | |
24 | | or both in parallel, as here. |
25 | | |
26 | | The GNU MP Library is distributed in the hope that it will be useful, but |
27 | | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
28 | | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
29 | | for more details. |
30 | | |
31 | | You should have received copies of the GNU General Public License and the |
32 | | GNU Lesser General Public License along with the GNU MP Library. If not, |
33 | | see https://www.gnu.org/licenses/. */ |
34 | | |
35 | | |
36 | | #include "gmp-impl.h" |
37 | | #include "longlong.h" |
38 | | |
39 | | mp_size_t |
40 | | mpn_pow_1 (mp_ptr rp, mp_srcptr bp, mp_size_t bn, mp_limb_t exp, mp_ptr tp) |
41 | 1.42k | { |
42 | 1.42k | mp_limb_t x; |
43 | 1.42k | int cnt, i; |
44 | 1.42k | mp_size_t rn; |
45 | 1.42k | int par; |
46 | | |
47 | 1.42k | ASSERT (bn >= 1); |
48 | | /* FIXME: Add operand overlap criteria */ |
49 | | |
50 | 1.42k | if (exp <= 1) |
51 | 0 | { |
52 | 0 | if (exp == 0) |
53 | 0 | { |
54 | 0 | rp[0] = 1; |
55 | 0 | return 1; |
56 | 0 | } |
57 | 0 | else |
58 | 0 | { |
59 | 0 | MPN_COPY (rp, bp, bn); |
60 | 0 | return bn; |
61 | 0 | } |
62 | 0 | } |
63 | | |
64 | | /* Count number of bits in exp, and compute where to put initial square in |
65 | | order to magically get results in the entry rp. Use simple code, |
66 | | optimized for small exp. For large exp, the bignum operations will take |
67 | | so much time that the slowness of this code will be negligible. */ |
68 | 1.42k | par = 0; |
69 | 1.42k | cnt = GMP_LIMB_BITS; |
70 | 1.42k | x = exp; |
71 | 1.42k | do |
72 | 2.84k | { |
73 | 2.84k | par ^= x; |
74 | 2.84k | cnt--; |
75 | 2.84k | x >>= 1; |
76 | 2.84k | } while (x != 0); |
77 | 1.42k | exp <<= cnt; |
78 | | |
79 | 1.42k | if (bn == 1) |
80 | 778 | { |
81 | 778 | mp_limb_t rl, rh, bl = bp[0]; |
82 | | |
83 | 778 | if ((cnt & 1) != 0) |
84 | 0 | MP_PTR_SWAP (rp, tp); |
85 | | |
86 | 778 | umul_ppmm (rh, rl, bl, bl << GMP_NAIL_BITS); |
87 | 778 | rp[0] = rl >> GMP_NAIL_BITS; |
88 | 778 | rp[1] = rh; |
89 | 778 | rn = 1 + (rh != 0); |
90 | | |
91 | 778 | for (i = GMP_LIMB_BITS - cnt - 1;;) |
92 | 778 | { |
93 | 778 | exp <<= 1; |
94 | 778 | if ((exp & GMP_LIMB_HIGHBIT) != 0) |
95 | 26 | { |
96 | 26 | rp[rn] = rh = mpn_mul_1 (rp, rp, rn, bl); |
97 | 26 | rn += rh != 0; |
98 | 26 | } |
99 | | |
100 | 778 | if (--i == 0) |
101 | 778 | break; |
102 | | |
103 | 0 | mpn_sqr (tp, rp, rn); |
104 | 0 | rn = 2 * rn; rn -= tp[rn - 1] == 0; |
105 | 0 | MP_PTR_SWAP (rp, tp); |
106 | 0 | } |
107 | 778 | } |
108 | 643 | else |
109 | 643 | { |
110 | 643 | if (((par ^ cnt) & 1) == 0) |
111 | 139 | MP_PTR_SWAP (rp, tp); |
112 | | |
113 | 643 | mpn_sqr (rp, bp, bn); |
114 | 643 | rn = 2 * bn; rn -= rp[rn - 1] == 0; |
115 | | |
116 | 643 | for (i = GMP_LIMB_BITS - cnt - 1;;) |
117 | 643 | { |
118 | 643 | exp <<= 1; |
119 | 643 | if ((exp & GMP_LIMB_HIGHBIT) != 0) |
120 | 139 | { |
121 | 139 | rn = rn + bn - (mpn_mul (tp, rp, rn, bp, bn) == 0); |
122 | 139 | MP_PTR_SWAP (rp, tp); |
123 | 139 | } |
124 | | |
125 | 643 | if (--i == 0) |
126 | 643 | break; |
127 | | |
128 | 0 | mpn_sqr (tp, rp, rn); |
129 | 0 | rn = 2 * rn; rn -= tp[rn - 1] == 0; |
130 | 0 | MP_PTR_SWAP (rp, tp); |
131 | 0 | } |
132 | 643 | } |
133 | | |
134 | 1.42k | return rn; |
135 | 1.42k | } |