/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 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*/ |