1 | /* SPDX-License-Identifier: GPL-2.0-or-later */ |
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 | * |
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 | |
55 | #define RESIZE_IF_NEEDED(a, b) \ |
56 | do { \ |
57 | if ((a)->alloced < (b)) \ |
58 | mpi_resize((a), (b)); \ |
59 | } while (0) |
60 | |
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 | |
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 | |
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 | |
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 | |
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 { \ |
117 | mpi_limb_t _ql __maybe_unused; \ |
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 | |
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 | |
146 | static inline mpi_limb_t mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, |
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); |
150 | static inline mpi_limb_t mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, |
151 | mpi_ptr_t s2_ptr, mpi_size_t s2_size); |
152 | |
153 | static inline mpi_limb_t mpihelp_sub_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, |
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); |
157 | static inline mpi_limb_t mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size, |
158 | mpi_ptr_t s2_ptr, mpi_size_t s2_size); |
159 | |
160 | /*-- mpih-cmp.c --*/ |
161 | int mpihelp_cmp(mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size); |
162 | |
163 | /*-- mpih-mul.c --*/ |
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); |
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); |
184 | void mpihelp_mul_n(mpi_ptr_t prodp, |
185 | mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size); |
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 | |
192 | /*-- generic_mpih-mul1.c --*/ |
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 | |
196 | /*-- mpih-div.c --*/ |
197 | mpi_limb_t mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size, |
198 | mpi_limb_t divisor_limb); |
199 | mpi_limb_t mpihelp_divrem(mpi_ptr_t qp, mpi_size_t , |
200 | mpi_ptr_t np, mpi_size_t nsize, |
201 | mpi_ptr_t dp, mpi_size_t dsize); |
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); |
205 | |
206 | /*-- generic_mpih-[lr]shift.c --*/ |
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 */ |
233 | |