Coverage Report

Created: 2024-11-21 07:03

/src/libgmp/mpn/pow_1.c
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
}