Commit | Line | Data |
---|---|---|
465ae836 | 1 | /* SPDX-License-Identifier: GPL-2.0-or-later */ |
5ce3e312 DK |
2 | /* mpi-internal.h - Internal to the Multi Precision Integers |
3 | * Copyright (C) 1994, 1996 Free Software Foundation, Inc. | |
4 | * Copyright (C) 1998, 2000 Free Software Foundation, Inc. | |
5 | * | |
6 | * This file is part of GnuPG. | |
7 | * | |
5ce3e312 DK |
8 | * Note: This code is heavily based on the GNU MP Library. |
9 | * Actually it's the same code with only minor changes in the | |
10 | * way the data is stored; this is to support the abstraction | |
11 | * of an optional secure memory allocation which may be used | |
12 | * to avoid revealing of sensitive data due to paging etc. | |
13 | * The GNU MP Library itself is published under the LGPL; | |
14 | * however I decided to publish this code under the plain GPL. | |
15 | */ | |
16 | ||
17 | #ifndef G10_MPI_INTERNAL_H | |
18 | #define G10_MPI_INTERNAL_H | |
19 | ||
20 | #include <linux/module.h> | |
21 | #include <linux/kernel.h> | |
22 | #include <linux/slab.h> | |
23 | #include <linux/string.h> | |
24 | #include <linux/mpi.h> | |
25 | #include <linux/errno.h> | |
26 | ||
27 | #define log_debug printk | |
28 | #define log_bug printk | |
29 | ||
30 | #define assert(x) \ | |
31 | do { \ | |
32 | if (!x) \ | |
33 | log_bug("failed assertion\n"); \ | |
34 | } while (0); | |
35 | ||
36 | /* If KARATSUBA_THRESHOLD is not already defined, define it to a | |
37 | * value which is good on most machines. */ | |
38 | ||
39 | /* tested 4, 16, 32 and 64, where 16 gave the best performance when | |
40 | * checking a 768 and a 1024 bit ElGamal signature. | |
41 | * (wk 22.12.97) */ | |
42 | #ifndef KARATSUBA_THRESHOLD | |
43 | #define KARATSUBA_THRESHOLD 16 | |
44 | #endif | |
45 | ||
46 | /* The code can't handle KARATSUBA_THRESHOLD smaller than 2. */ | |
47 | #if KARATSUBA_THRESHOLD < 2 | |
48 | #undef KARATSUBA_THRESHOLD | |
49 | #define KARATSUBA_THRESHOLD 2 | |
50 | #endif | |
51 | ||
52 | typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */ | |
53 | typedef int mpi_size_t; /* (must be a signed type) */ | |
54 | ||
a8ea8bdd TZ |
55 | #define RESIZE_IF_NEEDED(a, b) \ |
56 | do { \ | |
57 | if ((a)->alloced < (b)) \ | |
58 | mpi_resize((a), (b)); \ | |
59 | } while (0) | |
60 | ||
5ce3e312 DK |
61 | /* Copy N limbs from S to D. */ |
62 | #define MPN_COPY(d, s, n) \ | |
63 | do { \ | |
64 | mpi_size_t _i; \ | |
65 | for (_i = 0; _i < (n); _i++) \ | |
66 | (d)[_i] = (s)[_i]; \ | |
67 | } while (0) | |
68 | ||
a8ea8bdd TZ |
69 | #define MPN_COPY_INCR(d, s, n) \ |
70 | do { \ | |
71 | mpi_size_t _i; \ | |
72 | for (_i = 0; _i < (n); _i++) \ | |
73 | (d)[_i] = (s)[_i]; \ | |
74 | } while (0) | |
75 | ||
76 | ||
5ce3e312 DK |
77 | #define MPN_COPY_DECR(d, s, n) \ |
78 | do { \ | |
79 | mpi_size_t _i; \ | |
80 | for (_i = (n)-1; _i >= 0; _i--) \ | |
81 | (d)[_i] = (s)[_i]; \ | |
82 | } while (0) | |
83 | ||
84 | /* Zero N limbs at D */ | |
85 | #define MPN_ZERO(d, n) \ | |
86 | do { \ | |
87 | int _i; \ | |
88 | for (_i = 0; _i < (n); _i++) \ | |
89 | (d)[_i] = 0; \ | |
90 | } while (0) | |
91 | ||
92 | #define MPN_NORMALIZE(d, n) \ | |
93 | do { \ | |
94 | while ((n) > 0) { \ | |
95 | if ((d)[(n)-1]) \ | |
96 | break; \ | |
97 | (n)--; \ | |
98 | } \ | |
99 | } while (0) | |
100 | ||
5ce3e312 DK |
101 | #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \ |
102 | do { \ | |
103 | if ((size) < KARATSUBA_THRESHOLD) \ | |
104 | mul_n_basecase(prodp, up, vp, size); \ | |
105 | else \ | |
106 | mul_n(prodp, up, vp, size, tspace); \ | |
107 | } while (0); | |
108 | ||
a8ea8bdd TZ |
109 | /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest |
110 | * limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB). | |
111 | * If this would yield overflow, DI should be the largest possible number | |
112 | * (i.e., only ones). For correct operation, the most significant bit of D | |
113 | * has to be set. Put the quotient in Q and the remainder in R. | |
114 | */ | |
115 | #define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \ | |
116 | do { \ | |
ae6ee6ae | 117 | mpi_limb_t _ql __maybe_unused; \ |
a8ea8bdd TZ |
118 | mpi_limb_t _q, _r; \ |
119 | mpi_limb_t _xh, _xl; \ | |
120 | umul_ppmm(_q, _ql, (nh), (di)); \ | |
121 | _q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */ \ | |
122 | umul_ppmm(_xh, _xl, _q, (d)); \ | |
123 | sub_ddmmss(_xh, _r, (nh), (nl), _xh, _xl); \ | |
124 | if (_xh) { \ | |
125 | sub_ddmmss(_xh, _r, _xh, _r, 0, (d)); \ | |
126 | _q++; \ | |
127 | if (_xh) { \ | |
128 | sub_ddmmss(_xh, _r, _xh, _r, 0, (d)); \ | |
129 | _q++; \ | |
130 | } \ | |
131 | } \ | |
132 | if (_r >= (d)) { \ | |
133 | _r -= (d); \ | |
134 | _q++; \ | |
135 | } \ | |
136 | (r) = _r; \ | |
137 | (q) = _q; \ | |
138 | } while (0) | |
139 | ||
140 | ||
5ce3e312 DK |
141 | /*-- mpiutil.c --*/ |
142 | mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs); | |
143 | void mpi_free_limb_space(mpi_ptr_t a); | |
144 | void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs); | |
145 | ||
9c6bd0c2 | 146 | static inline mpi_limb_t mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, |
5ce3e312 DK |
147 | mpi_size_t s1_size, mpi_limb_t s2_limb); |
148 | mpi_limb_t mpihelp_add_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, | |
149 | mpi_ptr_t s2_ptr, mpi_size_t size); | |
9c6bd0c2 | 150 | static inline mpi_limb_t mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, |
5ce3e312 DK |
151 | mpi_ptr_t s2_ptr, mpi_size_t s2_size); |
152 | ||
9c6bd0c2 | 153 | static inline mpi_limb_t mpihelp_sub_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, |
5ce3e312 DK |
154 | mpi_size_t s1_size, mpi_limb_t s2_limb); |
155 | mpi_limb_t mpihelp_sub_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, | |
156 | mpi_ptr_t s2_ptr, mpi_size_t size); | |
9c6bd0c2 | 157 | static inline mpi_limb_t mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, |
5ce3e312 DK |
158 | mpi_ptr_t s2_ptr, mpi_size_t s2_size); |
159 | ||
cbdc61ae | 160 | /*-- mpih-cmp.c --*/ |
5ce3e312 DK |
161 | int mpihelp_cmp(mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size); |
162 | ||
cbdc61ae | 163 | /*-- mpih-mul.c --*/ |
5ce3e312 DK |
164 | |
165 | struct karatsuba_ctx { | |
166 | struct karatsuba_ctx *next; | |
167 | mpi_ptr_t tspace; | |
168 | mpi_size_t tspace_size; | |
169 | mpi_ptr_t tp; | |
170 | mpi_size_t tp_size; | |
171 | }; | |
172 | ||
173 | void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx); | |
174 | ||
175 | mpi_limb_t mpihelp_addmul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, | |
176 | mpi_size_t s1_size, mpi_limb_t s2_limb); | |
177 | mpi_limb_t mpihelp_submul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, | |
178 | mpi_size_t s1_size, mpi_limb_t s2_limb); | |
5ce3e312 DK |
179 | int mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize, |
180 | mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result); | |
181 | void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size); | |
182 | void mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, | |
183 | mpi_ptr_t tspace); | |
a8ea8bdd TZ |
184 | void mpihelp_mul_n(mpi_ptr_t prodp, |
185 | mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size); | |
5ce3e312 DK |
186 | |
187 | int mpihelp_mul_karatsuba_case(mpi_ptr_t prodp, | |
188 | mpi_ptr_t up, mpi_size_t usize, | |
189 | mpi_ptr_t vp, mpi_size_t vsize, | |
190 | struct karatsuba_ctx *ctx); | |
191 | ||
cbdc61ae | 192 | /*-- generic_mpih-mul1.c --*/ |
5ce3e312 DK |
193 | mpi_limb_t mpihelp_mul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, |
194 | mpi_size_t s1_size, mpi_limb_t s2_limb); | |
195 | ||
cbdc61ae | 196 | /*-- mpih-div.c --*/ |
a8ea8bdd TZ |
197 | mpi_limb_t mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, |
198 | mpi_limb_t divisor_limb); | |
5ce3e312 DK |
199 | mpi_limb_t mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs, |
200 | mpi_ptr_t np, mpi_size_t nsize, | |
201 | mpi_ptr_t dp, mpi_size_t dsize); | |
a8ea8bdd TZ |
202 | mpi_limb_t mpihelp_divmod_1(mpi_ptr_t quot_ptr, |
203 | mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, | |
204 | mpi_limb_t divisor_limb); | |
5ce3e312 | 205 | |
cbdc61ae | 206 | /*-- generic_mpih-[lr]shift.c --*/ |
5ce3e312 DK |
207 | mpi_limb_t mpihelp_lshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, |
208 | unsigned cnt); | |
209 | mpi_limb_t mpihelp_rshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, | |
210 | unsigned cnt); | |
211 | ||
212 | /* Define stuff for longlong.h. */ | |
213 | #define W_TYPE_SIZE BITS_PER_MPI_LIMB | |
214 | typedef mpi_limb_t UWtype; | |
215 | typedef unsigned int UHWtype; | |
216 | #if defined(__GNUC__) | |
217 | typedef unsigned int UQItype __attribute__ ((mode(QI))); | |
218 | typedef int SItype __attribute__ ((mode(SI))); | |
219 | typedef unsigned int USItype __attribute__ ((mode(SI))); | |
220 | typedef int DItype __attribute__ ((mode(DI))); | |
221 | typedef unsigned int UDItype __attribute__ ((mode(DI))); | |
222 | #else | |
223 | typedef unsigned char UQItype; | |
224 | typedef long SItype; | |
225 | typedef unsigned long USItype; | |
226 | #endif | |
227 | ||
228 | #ifdef __GNUC__ | |
229 | #include "mpi-inline.h" | |
230 | #endif | |
231 | ||
232 | #endif /*G10_MPI_INTERNAL_H */ |