Coverage Report

Created: 2025-07-23 06:43

/src/nettle/ecc-mul-g.c
Line
Count
Source
1
/* ecc-mul-g.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.h"
41
#include "ecc-internal.h"
42
#include "nettle-internal.h"
43
44
void
45
ecc_mul_g (const struct ecc_curve *ecc, mp_limb_t *r,
46
     const mp_limb_t *np, mp_limb_t *scratch)
47
58.9k
{
48
  /* Scratch need determined by the ecc_add_jja call. Current total is
49
     8 * ecc->p.size, at most 576 bytes. */
50
13.0M
#define tp scratch
51
2.60M
#define scratch_out (scratch + 3*ecc->p.size)
52
53
58.9k
  unsigned k, c;
54
58.9k
  unsigned i, j;
55
58.9k
  unsigned bit_rows;
56
57
58.9k
  int is_zero;
58
59
58.9k
  k = ecc->pippenger_k;
60
58.9k
  c = ecc->pippenger_c;
61
62
58.9k
  bit_rows = (ecc->p.bit_size + k - 1) / k;
63
  
64
58.9k
  mpn_zero (r, 3*ecc->p.size);
65
  
66
719k
  for (i = k, is_zero = 1; i-- > 0; )
67
660k
    {
68
660k
      ecc_dup_jj (ecc, r, r, scratch);
69
3.26M
      for (j = 0; j * c < bit_rows; j++)
70
2.60M
  {
71
2.60M
    unsigned bits;
72
    /* Avoid the mp_bitcnt_t type for compatibility with older GMP
73
       versions. */
74
2.60M
    unsigned bit_index;
75
2.60M
    int bits_is_zero;
76
77
    /* Extract c bits from n, stride k, starting at i + kcj,
78
       ending at i + k (cj + c - 1)*/
79
18.2M
    for (bits = 0, bit_index = i + k*(c*j+c); bit_index > i + k*c*j; )
80
15.6M
      {
81
15.6M
        mp_size_t limb_index;
82
15.6M
        unsigned shift;
83
        
84
15.6M
        bit_index -= k;
85
86
15.6M
        limb_index = bit_index / GMP_NUMB_BITS;
87
15.6M
        if (limb_index >= ecc->p.size)
88
467k
    continue;
89
90
15.1M
        shift = bit_index % GMP_NUMB_BITS;
91
15.1M
        bits = (bits << 1) | ((np[limb_index] >> shift) & 1);
92
15.1M
      }
93
2.60M
    mpn_sec_tabselect (tp,
94
2.60M
           (ecc->pippenger_table
95
2.60M
            + (2*ecc->p.size * (mp_size_t) j << c)),
96
2.60M
            2*ecc->p.size, 1<<c, bits);
97
2.60M
    cnd_copy (is_zero, r, tp, 2*ecc->p.size);
98
2.60M
    cnd_copy (is_zero, r + 2*ecc->p.size, ecc->unit, ecc->p.size);
99
    
100
2.60M
    ecc_add_jja (ecc, tp, r, tp, scratch_out);
101
2.60M
    bits_is_zero = IS_ZERO_SMALL (bits);
102
103
    /* Use the sum when valid. ecc_add_jja produced garbage if
104
       is_zero or bits_is_zero. */
105
2.60M
    cnd_copy (1 - (bits_is_zero | is_zero), r, tp, 3*ecc->p.size);
106
2.60M
    is_zero &= bits_is_zero;
107
2.60M
  }
108
660k
    }
109
58.9k
#undef tp
110
58.9k
#undef scratch_out
111
58.9k
}