Coverage Report

Created: 2024-06-28 06:39

/src/nettle-with-libgmp/ecc-mod.c
Line
Count
Source
1
/* ecc-mod.c
2
3
   Copyright (C) 2013 Niels Möller
4
5
   This file is part of GNU Nettle.
6
7
   GNU Nettle is free software: you can redistribute it and/or
8
   modify it under the terms of either:
9
10
     * the GNU Lesser General Public License as published by the Free
11
       Software Foundation; either version 3 of the License, or (at your
12
       option) any later version.
13
14
   or
15
16
     * the GNU General Public License as published by the Free
17
       Software Foundation; either version 2 of the License, or (at your
18
       option) any later version.
19
20
   or both in parallel, as here.
21
22
   GNU Nettle is distributed in the hope that it will be useful,
23
   but WITHOUT ANY WARRANTY; without even the implied warranty of
24
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25
   General Public License for more details.
26
27
   You should have received copies of the GNU General Public License and
28
   the GNU Lesser General Public License along with this program.  If
29
   not, see http://www.gnu.org/licenses/.
30
*/
31
32
/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
33
34
#if HAVE_CONFIG_H
35
# include "config.h"
36
#endif
37
38
#include <assert.h>
39
40
#include "ecc-internal.h"
41
42
/* Computes r <-- x mod m, input 2*m->size, output m->size. It's
43
 * allowed to have rp == xp or rp == xp + m->size, but no other kind
44
 * of overlap is allowed. */
45
void
46
ecc_mod (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp)
47
1.57k
{
48
1.57k
  mp_limb_t hi;
49
1.57k
  mp_size_t mn = m->size;
50
1.57k
  mp_size_t bn = m->B_size;
51
1.57k
  mp_size_t sn = mn - bn;
52
1.57k
  mp_size_t rn = 2*mn;
53
1.57k
  mp_size_t i;
54
1.57k
  unsigned shift;
55
56
1.57k
  assert (bn < mn);
57
58
  /* FIXME: Could use mpn_addmul_2. */
59
  /* Eliminate sn limbs at a time */
60
1.57k
  if (m->B[bn-1] < ((mp_limb_t) 1 << (GMP_NUMB_BITS - 1)))
61
1.35k
    {
62
      /* Multiply sn + 1 limbs at a time, so we get a mn+1 limb
63
   product. Then we can absorb the carry in the high limb */
64
4.07k
      while (rn > 2 * mn - bn)
65
2.72k
  {
66
2.72k
    rn -= sn;
67
68
11.5k
    for (i = 0; i <= sn; i++)
69
8.82k
      xp[rn+i-1] = mpn_addmul_1 (xp + rn - mn - 1 + i, m->B, bn, xp[rn+i-1]);
70
2.72k
    xp[rn-1] = xp[rn+sn-1]
71
2.72k
      + mpn_add_n (xp + rn - sn - 1, xp + rn - sn - 1, xp + rn - 1, sn);
72
2.72k
  }
73
1.35k
    }
74
220
  else
75
220
    {
76
440
      while (rn > 2 * mn - bn)
77
220
  {
78
220
    rn -= sn;
79
80
1.10k
    for (i = 0; i < sn; i++)
81
880
      xp[rn+i] = mpn_addmul_1 (xp + rn - mn + i, m->B, bn, xp[rn+i]);
82
             
83
220
    hi = mpn_add_n (xp + rn - sn, xp + rn - sn, xp + rn, sn);
84
220
    hi = mpn_cnd_add_n (hi, xp + rn - mn, xp + rn - mn, m->B, mn);
85
220
    assert_maybe (hi == 0);
86
220
  }
87
220
    }
88
89
1.57k
  assert (rn > mn);
90
1.57k
  rn -= mn;
91
1.57k
  assert (rn <= sn);
92
93
4.14k
  for (i = 0; i < rn; i++)
94
2.57k
    xp[mn+i] = mpn_addmul_1 (xp + i, m->B, bn, xp[mn+i]);
95
96
1.57k
  hi = mpn_add_n (xp + bn, xp + bn, xp + mn, rn);
97
1.57k
  if (rn < sn)
98
504
    hi = sec_add_1 (xp + bn + rn, xp + bn + rn, sn - rn, hi);
99
100
1.57k
  shift = m->size * GMP_NUMB_BITS - m->bit_size;
101
1.57k
  if (shift > 0)
102
702
    {
103
      /* Combine hi with top bits, add in */
104
702
      hi = (hi << shift) | (xp[mn-1] >> (GMP_NUMB_BITS - shift));
105
702
      xp[mn-1] = (xp[mn-1] & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
106
702
  + mpn_addmul_1 (xp, m->B_shifted, mn-1, hi);
107
      /* FIXME: Can this copying be eliminated? */
108
702
      if (rp != xp)
109
543
  mpn_copyi (rp, xp, mn);
110
702
    }
111
868
  else
112
868
    {
113
868
      hi = mpn_cnd_add_n (hi, rp, xp, m->B, mn);
114
868
      assert_maybe (hi == 0);
115
868
    }
116
1.57k
}