Coverage Report

Created: 2024-11-21 07:03

/src/libgcrypt/mpi/mpi-internal.h
Line
Count
Source (jump to first uncovered line)
1
/* mpi-internal.h  -  Internal to the Multi Precision Integers
2
 * Copyright (C) 1994, 1996, 1998, 2000, 2002,
3
 *               2003 Free Software Foundation, Inc.
4
 *
5
 * This file is part of Libgcrypt.
6
 *
7
 * Libgcrypt is free software; you can redistribute it and/or modify
8
 * it under the terms of the GNU Lesser General Public License as
9
 * published by the Free Software Foundation; either version 2.1 of
10
 * the License, or (at your option) any later version.
11
 *
12
 * Libgcrypt is distributed in the hope that it will be useful,
13
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
 * GNU Lesser General Public License for more details.
16
 *
17
 * You should have received a copy of the GNU Lesser General Public
18
 * License along with this program; if not, see <https://www.gnu.org/licenses/>.
19
 * SPDX-License-Identifier: LGPL-2.1-or-later
20
 *
21
 * Note: This code is heavily based on the GNU MP Library.
22
 *   Actually it's the same code with only minor changes in the
23
 *   way the data is stored; this is to support the abstraction
24
 *   of an optional secure memory allocation which may be used
25
 *   to avoid revealing of sensitive data due to paging etc.
26
 */
27
28
#ifndef G10_MPI_INTERNAL_H
29
#define G10_MPI_INTERNAL_H
30
31
#include "mpi-asm-defs.h"
32
33
#ifndef BITS_PER_MPI_LIMB
34
#if BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_INT
35
  typedef unsigned int mpi_limb_t;
36
  typedef   signed int mpi_limb_signed_t;
37
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG
38
  typedef unsigned long int mpi_limb_t;
39
  typedef   signed long int mpi_limb_signed_t;
40
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_LONG_LONG
41
  typedef unsigned long long int mpi_limb_t;
42
  typedef   signed long long int mpi_limb_signed_t;
43
#elif BYTES_PER_MPI_LIMB == SIZEOF_UNSIGNED_SHORT
44
  typedef unsigned short int mpi_limb_t;
45
  typedef   signed short int mpi_limb_signed_t;
46
#else
47
#error BYTES_PER_MPI_LIMB does not match any C type
48
#endif
49
4.12G
#define BITS_PER_MPI_LIMB    (8*BYTES_PER_MPI_LIMB)
50
#endif /*BITS_PER_MPI_LIMB*/
51
52
#include "mpi.h"
53
#include "const-time.h"
54
55
/* If KARATSUBA_THRESHOLD is not already defined, define it to a
56
 * value which is good on most machines.  */
57
58
/* tested 4, 16, 32 and 64, where 16 gave the best performance when
59
 * checking a 768 and a 1024 bit ElGamal signature.
60
 * (wk 22.12.97) */
61
#ifndef KARATSUBA_THRESHOLD
62
220M
#define KARATSUBA_THRESHOLD 16
63
#endif
64
65
/* The code can't handle KARATSUBA_THRESHOLD smaller than 2.  */
66
#if KARATSUBA_THRESHOLD < 2
67
#undef KARATSUBA_THRESHOLD
68
#define KARATSUBA_THRESHOLD 2
69
#endif
70
71
72
typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */
73
typedef int mpi_size_t;        /* (must be a signed type) */
74
75
#define ABS(x) (x >= 0 ? x : -x)
76
#define MIN(l,o) ((l) < (o) ? (l) : (o))
77
#define MAX(h,i) ((h) > (i) ? (h) : (i))
78
#define RESIZE_IF_NEEDED(a,b) \
79
15.7M
    do {        \
80
15.7M
  if( (a)->alloced < (b) )   \
81
15.7M
      mpi_resize((a), (b));  \
82
15.7M
    } while(0)
83
#define RESIZE_AND_CLEAR_IF_NEEDED(a,b) \
84
28.1M
    do {        \
85
28.1M
  if( (a)->nlimbs < (b) )   \
86
28.1M
      mpi_resize((a), (b));  \
87
28.1M
    } while(0)
88
89
/* Copy N limbs from S to D.  */
90
#define MPN_COPY( d, s, n) \
91
134M
    do {       \
92
134M
  mpi_size_t _i;      \
93
1.96G
  for( _i = 0; _i < (n); _i++ )  \
94
1.83G
      (d)[_i] = (s)[_i];   \
95
134M
    } while(0)
96
97
#define MPN_COPY_INCR( d, s, n)   \
98
0
    do {       \
99
0
  mpi_size_t _i;      \
100
0
  for( _i = 0; _i < (n); _i++ )  \
101
0
      (d)[_i] = (s)[_i];   \
102
0
    } while (0)
103
104
#define MPN_COPY_DECR( d, s, n ) \
105
2
    do {       \
106
2
  mpi_size_t _i;      \
107
54
  for( _i = (n)-1; _i >= 0; _i--) \
108
52
     (d)[_i] = (s)[_i];   \
109
2
    } while(0)
110
111
/* Zero N limbs at D */
112
#define MPN_ZERO(d, n) \
113
2.95M
    do {         \
114
2.95M
  int  _i;        \
115
26.1M
  for( _i = 0; _i < (n); _i++ )  \
116
23.1M
      (d)[_i] = 0;       \
117
2.95M
    } while (0)
118
119
#define MPN_NORMALIZE(d, n)  \
120
56.5M
    do {          \
121
60.0M
  while( (n) > 0 ) {     \
122
59.6M
      if( (d)[(n)-1] ) \
123
59.6M
    break;        \
124
59.6M
      (n)--;         \
125
3.48M
  }           \
126
56.5M
    } while(0)
127
128
#define MPN_NORMALIZE_NOT_ZERO(d, n) \
129
    do {            \
130
  for(;;) {         \
131
      if( (d)[(n)-1] )        \
132
    break;          \
133
      (n)--;          \
134
  }           \
135
    } while(0)
136
137
#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
138
    do {            \
139
  if( (size) < KARATSUBA_THRESHOLD )    \
140
      mul_n_basecase (prodp, up, vp, size); \
141
  else            \
142
      mul_n (prodp, up, vp, size, tspace);  \
143
    } while (0)
144
145
146
/* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
147
 * limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
148
 * If this would yield overflow, DI should be the largest possible number
149
 * (i.e., only ones).  For correct operation, the most significant bit of D
150
 * has to be set.  Put the quotient in Q and the remainder in R.
151
 */
152
#define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \
153
0
    do {                 \
154
0
        mpi_limb_t _ql GCC_ATTR_UNUSED;                               \
155
0
  mpi_limb_t _q, _r;                                          \
156
0
  mpi_limb_t _xh, _xl;              \
157
0
  umul_ppmm (_q, _ql, (nh), (di));         \
158
0
  _q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */  \
159
0
  umul_ppmm (_xh, _xl, _q, (d));           \
160
0
  sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);       \
161
0
  if( _xh ) {               \
162
0
      sub_ddmmss (_xh, _r, _xh, _r, 0, (d));        \
163
0
      _q++;               \
164
0
      if( _xh) {               \
165
0
    sub_ddmmss (_xh, _r, _xh, _r, 0, (d));        \
166
0
    _q++;               \
167
0
      }                 \
168
0
  }                 \
169
0
  if( _r >= (d) ) {             \
170
0
      _r -= (d);                \
171
0
      _q++;               \
172
0
  }                  \
173
0
  (r) = _r;               \
174
0
  (q) = _q;               \
175
0
    } while (0)
176
177
178
/*-- mpiutil.c --*/
179
18.3M
#define mpi_alloc_limb_space(n,f)  _gcry_mpi_alloc_limb_space((n),(f))
180
mpi_ptr_t _gcry_mpi_alloc_limb_space( unsigned nlimbs, int sec );
181
void _gcry_mpi_free_limb_space( mpi_ptr_t a, unsigned int nlimbs );
182
void _gcry_mpi_assign_limb_space( gcry_mpi_t a, mpi_ptr_t ap, unsigned nlimbs );
183
184
/*-- mpi-bit.c --*/
185
94
#define mpi_rshift_limbs(a,n)  _gcry_mpi_rshift_limbs ((a), (n))
186
71
#define mpi_lshift_limbs(a,n)  _gcry_mpi_lshift_limbs ((a), (n))
187
188
void _gcry_mpi_rshift_limbs( gcry_mpi_t a, unsigned int count );
189
void _gcry_mpi_lshift_limbs( gcry_mpi_t a, unsigned int count );
190
191
192
/*-- mpih-add.c --*/
193
mpi_limb_t _gcry_mpih_add_1(mpi_ptr_t res_ptr,  mpi_ptr_t s1_ptr,
194
       mpi_size_t s1_size, mpi_limb_t s2_limb );
195
mpi_limb_t _gcry_mpih_add_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
196
        mpi_ptr_t s2_ptr,  mpi_size_t size);
197
mpi_limb_t _gcry_mpih_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
198
           mpi_ptr_t s2_ptr, mpi_size_t s2_size);
199
200
/*-- mpih-sub.c --*/
201
mpi_limb_t _gcry_mpih_sub_1( mpi_ptr_t res_ptr,  mpi_ptr_t s1_ptr,
202
        mpi_size_t s1_size, mpi_limb_t s2_limb );
203
mpi_limb_t _gcry_mpih_sub_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
204
        mpi_ptr_t s2_ptr, mpi_size_t size);
205
mpi_limb_t _gcry_mpih_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
206
           mpi_ptr_t s2_ptr, mpi_size_t s2_size);
207
208
/*-- mpih-cmp.c --*/
209
int _gcry_mpih_cmp( mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size );
210
211
/*-- mpih-mul.c --*/
212
213
struct karatsuba_ctx {
214
    struct karatsuba_ctx *next;
215
    mpi_ptr_t tspace;
216
    unsigned int tspace_nlimbs;
217
    mpi_size_t tspace_size;
218
    mpi_ptr_t tp;
219
    unsigned int tp_nlimbs;
220
    mpi_size_t tp_size;
221
};
222
223
void _gcry_mpih_release_karatsuba_ctx( struct karatsuba_ctx *ctx );
224
225
mpi_limb_t _gcry_mpih_addmul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
226
           mpi_size_t s1_size, mpi_limb_t s2_limb);
227
mpi_limb_t _gcry_mpih_submul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
228
           mpi_size_t s1_size, mpi_limb_t s2_limb);
229
void _gcry_mpih_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
230
               mpi_size_t size);
231
mpi_limb_t _gcry_mpih_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
232
           mpi_ptr_t vp, mpi_size_t vsize);
233
void _gcry_mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size );
234
void _gcry_mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size,
235
            mpi_ptr_t tspace);
236
237
void _gcry_mpih_mul_karatsuba_case( mpi_ptr_t prodp,
238
         mpi_ptr_t up, mpi_size_t usize,
239
         mpi_ptr_t vp, mpi_size_t vsize,
240
         struct karatsuba_ctx *ctx );
241
242
243
/*-- mpih-mul_1.c (or xxx/cpu/ *.S) --*/
244
mpi_limb_t _gcry_mpih_mul_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
245
        mpi_size_t s1_size, mpi_limb_t s2_limb);
246
247
/*-- mpih-div.c --*/
248
mpi_limb_t _gcry_mpih_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
249
             mpi_limb_t divisor_limb);
250
mpi_limb_t _gcry_mpih_divrem( mpi_ptr_t qp, mpi_size_t qextra_limbs,
251
         mpi_ptr_t np, mpi_size_t nsize,
252
         mpi_ptr_t dp, mpi_size_t dsize);
253
mpi_limb_t _gcry_mpih_divmod_1( mpi_ptr_t quot_ptr,
254
           mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
255
           mpi_limb_t divisor_limb);
256
257
/*-- mpih-shift.c --*/
258
mpi_limb_t _gcry_mpih_lshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
259
                 unsigned cnt);
260
mpi_limb_t _gcry_mpih_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
261
                 unsigned cnt);
262
263
/*-- mpih-const-time.c --*/
264
8.87M
#define mpih_set_cond(w,u,s,o) _gcry_mpih_set_cond ((w),(u),(s),(o))
265
23.0M
#define mpih_add_n_cond(w,u,v,s,o) _gcry_mpih_add_n_cond ((w),(u),(v),(s),(o))
266
14.5M
#define mpih_sub_n_cond(w,u,v,s,o) _gcry_mpih_sub_n_cond ((w),(u),(v),(s),(o))
267
7.29M
#define mpih_swap_cond(u,v,s,o) _gcry_mpih_swap_cond ((u),(v),(s),(o))
268
7.29M
#define mpih_abs_cond(w,u,s,o) _gcry_mpih_abs_cond ((w),(u),(s),(o))
269
#define mpih_mod(v,vs,u,us) _gcry_mpih_mod ((v),(vs),(u),(us))
270
271
DEFINE_CT_TYPE_GEN_MASK(limb, mpi_limb_t)
272
DEFINE_CT_TYPE_GEN_INV_MASK(limb, mpi_limb_t)
273
274
static inline int
275
mpih_limb_is_zero (mpi_limb_t a)
276
4.35M
{
277
  /* Sign bit set if A == 0. */
278
4.35M
  a = ~a & ~(-a);
279
280
4.35M
  return a >> (BITS_PER_MPI_LIMB - 1);
281
4.35M
}
Unexecuted instantiation: mpi-add.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-bit.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-cmp.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-div.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-gcd.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-inv.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-mod.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-mpow.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-mul.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-pow.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-scan.c:mpih_limb_is_zero
Unexecuted instantiation: mpicoder.c:mpih_limb_is_zero
mpih-const-time.c:mpih_limb_is_zero
Line
Count
Source
276
50.5k
{
277
  /* Sign bit set if A == 0. */
278
50.5k
  a = ~a & ~(-a);
279
280
50.5k
  return a >> (BITS_PER_MPI_LIMB - 1);
281
50.5k
}
Unexecuted instantiation: mpih-div.c:mpih_limb_is_zero
Unexecuted instantiation: mpih-mul.c:mpih_limb_is_zero
Unexecuted instantiation: mpiutil.c:mpih_limb_is_zero
ec.c:mpih_limb_is_zero
Line
Count
Source
276
4.30M
{
277
  /* Sign bit set if A == 0. */
278
4.30M
  a = ~a & ~(-a);
279
280
4.30M
  return a >> (BITS_PER_MPI_LIMB - 1);
281
4.30M
}
Unexecuted instantiation: ecc-curves.c:mpih_limb_is_zero
Unexecuted instantiation: mpi-inline.c:mpih_limb_is_zero
Unexecuted instantiation: poly1305.c:mpih_limb_is_zero
Unexecuted instantiation: ec-nist.c:mpih_limb_is_zero
282
283
static inline int
284
mpih_limb_is_not_zero (mpi_limb_t a)
285
8.74M
{
286
  /* Sign bit set if A != 0. */
287
8.74M
  a = a | (-a);
288
289
8.74M
  return a >> (BITS_PER_MPI_LIMB - 1);
290
8.74M
}
Unexecuted instantiation: mpi-add.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-bit.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-cmp.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-div.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-gcd.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-inv.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-mod.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-mpow.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-mul.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-pow.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-scan.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpicoder.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpih-const-time.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpih-div.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpih-mul.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpiutil.c:mpih_limb_is_not_zero
ec.c:mpih_limb_is_not_zero
Line
Count
Source
285
4.30M
{
286
  /* Sign bit set if A != 0. */
287
4.30M
  a = a | (-a);
288
289
4.30M
  return a >> (BITS_PER_MPI_LIMB - 1);
290
4.30M
}
Unexecuted instantiation: ecc-curves.c:mpih_limb_is_not_zero
Unexecuted instantiation: mpi-inline.c:mpih_limb_is_not_zero
Unexecuted instantiation: poly1305.c:mpih_limb_is_not_zero
ec-nist.c:mpih_limb_is_not_zero
Line
Count
Source
285
4.43M
{
286
  /* Sign bit set if A != 0. */
287
4.43M
  a = a | (-a);
288
289
4.43M
  return a >> (BITS_PER_MPI_LIMB - 1);
290
4.43M
}
291
292
void _gcry_mpih_set_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
293
                          unsigned long op_enable);
294
mpi_limb_t _gcry_mpih_add_n_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_ptr_t vp,
295
                                  mpi_size_t usize, unsigned long op_enable);
296
mpi_limb_t _gcry_mpih_sub_n_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_ptr_t vp,
297
                                  mpi_size_t usize, unsigned long op_enable);
298
void _gcry_mpih_swap_cond (mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t usize,
299
                           unsigned long op_enable);
300
void _gcry_mpih_abs_cond (mpi_ptr_t wp, mpi_ptr_t up,
301
                          mpi_size_t usize, unsigned long op_enable);
302
mpi_ptr_t _gcry_mpih_mod (mpi_ptr_t vp, mpi_size_t vsize,
303
                          mpi_ptr_t up, mpi_size_t usize);
304
int _gcry_mpih_cmp_ui (mpi_ptr_t up, mpi_size_t usize, unsigned long v);
305
306
307
/* Define stuff for longlong.h.  */
308
#define W_TYPE_SIZE BITS_PER_MPI_LIMB
309
  typedef mpi_limb_t   UWtype;
310
  typedef unsigned int UHWtype;
311
#if defined (__GNUC__)
312
  typedef unsigned int UQItype    __attribute__ ((mode (QI)));
313
  typedef    int SItype   __attribute__ ((mode (SI)));
314
  typedef unsigned int USItype    __attribute__ ((mode (SI)));
315
  typedef    int DItype   __attribute__ ((mode (DI)));
316
  typedef unsigned int UDItype    __attribute__ ((mode (DI)));
317
#else
318
  typedef unsigned char UQItype;
319
  typedef    long SItype;
320
  typedef unsigned long USItype;
321
#endif
322
323
#ifdef __GNUC__
324
#include "mpi-inline.h"
325
#endif
326
327
#endif /*G10_MPI_INTERNAL_H*/