Coverage Report

Created: 2024-11-21 07:00

/src/nettle-with-mini-gmp/ecc-mul-a.c
Line
Count
Source (jump to first uncovered line)
1
/* ecc-mul-a.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
/* Binary algorithm needs 6*ecc->p.size + scratch for ecc_add_jja.
45
   Current total is 12 ecc->p.size, at most 864 bytes.
46
47
   Window algorithm needs (3<<w) * ecc->p.size for the table,
48
   3*ecc->p.size for a temporary point, and scratch for
49
   ecc_add_jjj. */
50
51
#if ECC_MUL_A_WBITS == 0
52
void
53
ecc_mul_a (const struct ecc_curve *ecc,
54
     mp_limb_t *r,
55
     const mp_limb_t *np, const mp_limb_t *p,
56
     mp_limb_t *scratch)
57
{
58
#define tp scratch
59
#define pj (scratch + 3*ecc->p.size)
60
#define scratch_out (scratch + 6*ecc->p.size)
61
62
  int is_zero;
63
64
  unsigned i;
65
66
  ecc_a_to_j (ecc, pj, p);
67
  mpn_zero (r, 3*ecc->p.size);
68
  
69
  for (i = ecc->p.size, is_zero = 1; i-- > 0; )
70
    {
71
      mp_limb_t w = np[i] << (GMP_LIMB_BITS - GMP_NUMB_BITS);
72
      unsigned j;
73
74
      for (j = 0; j < GMP_NUMB_BITS; j++, w <<= 1)
75
  {
76
    int bit;
77
78
    ecc_dup_jj (ecc, r, r, scratch_out);
79
    ecc_add_jja (ecc, tp, r, pj, scratch_out);
80
81
    bit = w >> (GMP_LIMB_BITS - 1);
82
    /* If is_zero is set, r is the zero point,
83
       and ecc_add_jja produced garbage. */
84
    cnd_copy (is_zero, tp, pj, 3*ecc->p.size);
85
    is_zero &= 1 - bit;
86
    /* If we had a one-bit, use the sum. */
87
    cnd_copy (bit, r, tp, 3*ecc->p.size);
88
  }
89
    }
90
}
91
#else /* ECC_MUL_A_WBITS > 1 */
92
93
110k
#define TABLE_SIZE (1U << ECC_MUL_A_WBITS)
94
54.7k
#define TABLE_MASK (TABLE_SIZE - 1)
95
96
25.9k
#define TABLE(j) (table + (j) * 3*ecc->p.size)
97
98
static void
99
table_init (const struct ecc_curve *ecc,
100
      mp_limb_t *table, unsigned bits,
101
      const mp_limb_t *p,
102
      mp_limb_t *scratch)
103
701
{
104
701
  unsigned size = 1 << bits;
105
701
  unsigned j;
106
107
701
  mpn_zero (TABLE(0), 3*ecc->p.size);
108
701
  ecc_a_to_j (ecc, TABLE(1), p);
109
110
5.60k
  for (j = 2; j < size; j += 2)
111
4.90k
    {
112
4.90k
      ecc_dup_jj (ecc, TABLE(j), TABLE(j/2), scratch);
113
4.90k
      ecc_add_jja (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch);
114
4.90k
    }  
115
701
}
116
117
void
118
ecc_mul_a (const struct ecc_curve *ecc,
119
     mp_limb_t *r,
120
     const mp_limb_t *np, const mp_limb_t *p,
121
     mp_limb_t *scratch)
122
701
{
123
273k
#define tp scratch
124
56.8k
#define table (scratch + 3*ecc->p.size)
125
701
  mp_limb_t *scratch_out = table + (3*ecc->p.size << ECC_MUL_A_WBITS);
126
701
  int is_zero = 0;
127
128
  /* Avoid the mp_bitcnt_t type for compatibility with older GMP
129
     versions. */
130
701
  unsigned blocks = (ecc->p.bit_size + ECC_MUL_A_WBITS - 1) / ECC_MUL_A_WBITS;
131
701
  unsigned bit_index = (blocks-1) * ECC_MUL_A_WBITS;
132
133
701
  mp_size_t limb_index = bit_index / GMP_NUMB_BITS;
134
701
  unsigned shift = bit_index % GMP_NUMB_BITS;
135
701
  mp_limb_t w, bits;
136
137
701
  table_init (ecc, table, ECC_MUL_A_WBITS, p, scratch_out);
138
139
701
  w = np[limb_index];
140
701
  bits = w >> shift;
141
701
  if (limb_index < ecc->p.size - 1)
142
0
    bits |= np[limb_index + 1] << (GMP_NUMB_BITS - shift);
143
144
701
  assert (bits < TABLE_SIZE);
145
146
701
  mpn_sec_tabselect (r, table, 3*ecc->p.size, TABLE_SIZE, bits);
147
701
  is_zero = IS_ZERO_SMALL (bits);
148
149
701
  for (;;)
150
55.4k
    {
151
55.4k
      int bits_is_zero;
152
55.4k
      unsigned j;
153
55.4k
      if (shift >= ECC_MUL_A_WBITS)
154
51.8k
  {
155
51.8k
    shift -= ECC_MUL_A_WBITS;
156
51.8k
    bits = w >> shift;
157
51.8k
  }
158
3.60k
      else
159
3.60k
  {
160
3.60k
    if (limb_index == 0)
161
701
      {
162
701
        assert (shift == 0);
163
701
        break;
164
701
      }
165
2.89k
    bits = w << (ECC_MUL_A_WBITS - shift);
166
2.89k
    w = np[--limb_index];
167
2.89k
    shift = shift + GMP_NUMB_BITS - ECC_MUL_A_WBITS;
168
2.89k
    bits |= w >> shift;
169
2.89k
  }
170
273k
      for (j = 0; j < ECC_MUL_A_WBITS; j++)
171
218k
  ecc_dup_jj (ecc, r, r, scratch_out);
172
173
54.7k
      bits &= TABLE_MASK;
174
54.7k
      mpn_sec_tabselect (tp, table, 3*ecc->p.size, TABLE_SIZE, bits);
175
54.7k
      cnd_copy (is_zero, r, tp, 3*ecc->p.size);
176
54.7k
      ecc_add_jjj (ecc, tp, tp, r, scratch_out);
177
54.7k
      bits_is_zero = IS_ZERO_SMALL (bits);
178
179
      /* Use the sum when valid. ecc_add_jja produced garbage if
180
   is_zero or bits_is_zero. */
181
54.7k
      cnd_copy (1 - (bits_is_zero | is_zero), r, tp, 3*ecc->p.size);
182
54.7k
      is_zero &= bits_is_zero;
183
54.7k
    }
184
701
#undef table
185
701
#undef tp
186
701
}
187
188
#endif /* ECC_MUL_A_WBITS > 1 */