Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-or-later
2 : : /* mpihelp-mul.c - MPI helper functions
3 : : * Copyright (C) 1994, 1996, 1998, 1999,
4 : : * 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 : : #include <linux/string.h>
18 : : #include "mpi-internal.h"
19 : : #include "longlong.h"
20 : :
21 : : #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
22 : : do { \
23 : : if ((size) < KARATSUBA_THRESHOLD) \
24 : : mul_n_basecase(prodp, up, vp, size); \
25 : : else \
26 : : mul_n(prodp, up, vp, size, tspace); \
27 : : } while (0);
28 : :
29 : : #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
30 : : do { \
31 : : if ((size) < KARATSUBA_THRESHOLD) \
32 : : mpih_sqr_n_basecase(prodp, up, size); \
33 : : else \
34 : : mpih_sqr_n(prodp, up, size, tspace); \
35 : : } while (0);
36 : :
37 : : /* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP),
38 : : * both with SIZE limbs, and store the result at PRODP. 2 * SIZE limbs are
39 : : * always stored. Return the most significant limb.
40 : : *
41 : : * Argument constraints:
42 : : * 1. PRODP != UP and PRODP != VP, i.e. the destination
43 : : * must be distinct from the multiplier and the multiplicand.
44 : : *
45 : : *
46 : : * Handle simple cases with traditional multiplication.
47 : : *
48 : : * This is the most critical code of multiplication. All multiplies rely
49 : : * on this, both small and huge. Small ones arrive here immediately. Huge
50 : : * ones arrive here as this is the base case for Karatsuba's recursive
51 : : * algorithm below.
52 : : */
53 : :
54 : : static mpi_limb_t
55 : 99 : mul_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
56 : : {
57 : 99 : mpi_size_t i;
58 : 99 : mpi_limb_t cy;
59 : 99 : mpi_limb_t v_limb;
60 : :
61 : : /* Multiply by the first limb in V separately, as the result can be
62 : : * stored (not added) to PROD. We also avoid a loop for zeroing. */
63 : 99 : v_limb = vp[0];
64 [ - + ]: 99 : if (v_limb <= 1) {
65 [ # # ]: 0 : if (v_limb == 1)
66 [ # # ]: 0 : MPN_COPY(prodp, up, size);
67 : : else
68 [ # # ]: 0 : MPN_ZERO(prodp, size);
69 : : cy = 0;
70 : : } else
71 : 99 : cy = mpihelp_mul_1(prodp, up, size, v_limb);
72 : :
73 : 99 : prodp[size] = cy;
74 : 99 : prodp++;
75 : :
76 : : /* For each iteration in the outer loop, multiply one limb from
77 : : * U with one limb from V, and add it to PROD. */
78 [ + + ]: 792 : for (i = 1; i < size; i++) {
79 : 693 : v_limb = vp[i];
80 [ - + ]: 693 : if (v_limb <= 1) {
81 : 0 : cy = 0;
82 [ # # ]: 0 : if (v_limb == 1)
83 : 0 : cy = mpihelp_add_n(prodp, prodp, up, size);
84 : : } else
85 : 693 : cy = mpihelp_addmul_1(prodp, up, size, v_limb);
86 : :
87 : 693 : prodp[size] = cy;
88 : 693 : prodp++;
89 : : }
90 : :
91 : 99 : return cy;
92 : : }
93 : :
94 : : static void
95 : 44 : mul_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
96 : : mpi_size_t size, mpi_ptr_t tspace)
97 : : {
98 [ - + ]: 44 : if (size & 1) {
99 : : /* The size is odd, and the code below doesn't handle that.
100 : : * Multiply the least significant (size - 1) limbs with a recursive
101 : : * call, and handle the most significant limb of S1 and S2
102 : : * separately.
103 : : * A slightly faster way to do this would be to make the Karatsuba
104 : : * code below behave as if the size were even, and let it check for
105 : : * odd size in the end. I.e., in essence move this code to the end.
106 : : * Doing so would save us a recursive call, and potentially make the
107 : : * stack grow a lot less.
108 : : */
109 : 0 : mpi_size_t esize = size - 1; /* even size */
110 : 0 : mpi_limb_t cy_limb;
111 : :
112 [ # # ]: 0 : MPN_MUL_N_RECURSE(prodp, up, vp, esize, tspace);
113 : 0 : cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, vp[esize]);
114 : 0 : prodp[esize + esize] = cy_limb;
115 : 0 : cy_limb = mpihelp_addmul_1(prodp + esize, vp, size, up[esize]);
116 : 0 : prodp[esize + size] = cy_limb;
117 : : } else {
118 : : /* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm.
119 : : *
120 : : * Split U in two pieces, U1 and U0, such that
121 : : * U = U0 + U1*(B**n),
122 : : * and V in V1 and V0, such that
123 : : * V = V0 + V1*(B**n).
124 : : *
125 : : * UV is then computed recursively using the identity
126 : : *
127 : : * 2n n n n
128 : : * UV = (B + B )U V + B (U -U )(V -V ) + (B + 1)U V
129 : : * 1 1 1 0 0 1 0 0
130 : : *
131 : : * Where B = 2**BITS_PER_MP_LIMB.
132 : : */
133 : 44 : mpi_size_t hsize = size >> 1;
134 : 44 : mpi_limb_t cy;
135 : 44 : int negflg;
136 : :
137 : : /* Product H. ________________ ________________
138 : : * |_____U1 x V1____||____U0 x V0_____|
139 : : * Put result in upper part of PROD and pass low part of TSPACE
140 : : * as new TSPACE.
141 : : */
142 [ + + ]: 44 : MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize,
143 : 44 : tspace);
144 : :
145 : : /* Product M. ________________
146 : : * |_(U1-U0)(V0-V1)_|
147 : : */
148 [ + + ]: 44 : if (mpihelp_cmp(up + hsize, up, hsize) >= 0) {
149 : 11 : mpihelp_sub_n(prodp, up + hsize, up, hsize);
150 : 11 : negflg = 0;
151 : : } else {
152 : 33 : mpihelp_sub_n(prodp, up, up + hsize, hsize);
153 : 33 : negflg = 1;
154 : : }
155 [ + + ]: 44 : if (mpihelp_cmp(vp + hsize, vp, hsize) >= 0) {
156 : 33 : mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize);
157 : 33 : negflg ^= 1;
158 : : } else {
159 : 11 : mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize);
160 : : /* No change of NEGFLG. */
161 : : }
162 : : /* Read temporary operands from low part of PROD.
163 : : * Put result in low part of TSPACE using upper part of TSPACE
164 : : * as new TSPACE.
165 : : */
166 [ + + ]: 44 : MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize,
167 : : tspace + size);
168 : :
169 : : /* Add/copy product H. */
170 [ + + ]: 484 : MPN_COPY(prodp + hsize, prodp + size, hsize);
171 : 44 : cy = mpihelp_add_n(prodp + size, prodp + size,
172 : 44 : prodp + size + hsize, hsize);
173 : :
174 : : /* Add product M (if NEGFLG M is a negative number) */
175 [ + + ]: 44 : if (negflg)
176 : 22 : cy -=
177 : 22 : mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace,
178 : : size);
179 : : else
180 : 22 : cy +=
181 : 22 : mpihelp_add_n(prodp + hsize, prodp + hsize, tspace,
182 : : size);
183 : :
184 : : /* Product L. ________________ ________________
185 : : * |________________||____U0 x V0_____|
186 : : * Read temporary operands from low part of PROD.
187 : : * Put result in low part of TSPACE using upper part of TSPACE
188 : : * as new TSPACE.
189 : : */
190 [ + + ]: 44 : MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size);
191 : :
192 : : /* Add/copy Product L (twice) */
193 : :
194 : 44 : cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
195 [ + + ]: 44 : if (cy)
196 : 11 : mpihelp_add_1(prodp + hsize + size,
197 : : prodp + hsize + size, hsize, cy);
198 : :
199 [ + + ]: 484 : MPN_COPY(prodp, tspace, hsize);
200 : 44 : cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize,
201 : : hsize);
202 [ + + ]: 44 : if (cy)
203 : 22 : mpihelp_add_1(prodp + size, prodp + size, size, 1);
204 : : }
205 : 44 : }
206 : :
207 : 1584 : void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size)
208 : : {
209 : 1584 : mpi_size_t i;
210 : 1584 : mpi_limb_t cy_limb;
211 : 1584 : mpi_limb_t v_limb;
212 : :
213 : : /* Multiply by the first limb in V separately, as the result can be
214 : : * stored (not added) to PROD. We also avoid a loop for zeroing. */
215 : 1584 : v_limb = up[0];
216 [ - + ]: 1584 : if (v_limb <= 1) {
217 [ # # ]: 0 : if (v_limb == 1)
218 [ # # ]: 0 : MPN_COPY(prodp, up, size);
219 : : else
220 [ # # ]: 0 : MPN_ZERO(prodp, size);
221 : : cy_limb = 0;
222 : : } else
223 : 1584 : cy_limb = mpihelp_mul_1(prodp, up, size, v_limb);
224 : :
225 : 1584 : prodp[size] = cy_limb;
226 : 1584 : prodp++;
227 : :
228 : : /* For each iteration in the outer loop, multiply one limb from
229 : : * U with one limb from V, and add it to PROD. */
230 [ + + ]: 12672 : for (i = 1; i < size; i++) {
231 : 11088 : v_limb = up[i];
232 [ - + ]: 11088 : if (v_limb <= 1) {
233 : 0 : cy_limb = 0;
234 [ # # ]: 0 : if (v_limb == 1)
235 : 0 : cy_limb = mpihelp_add_n(prodp, prodp, up, size);
236 : : } else
237 : 11088 : cy_limb = mpihelp_addmul_1(prodp, up, size, v_limb);
238 : :
239 : 11088 : prodp[size] = cy_limb;
240 : 11088 : prodp++;
241 : : }
242 : 1584 : }
243 : :
244 : : void
245 : 704 : mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
246 : : {
247 [ - + ]: 704 : if (size & 1) {
248 : : /* The size is odd, and the code below doesn't handle that.
249 : : * Multiply the least significant (size - 1) limbs with a recursive
250 : : * call, and handle the most significant limb of S1 and S2
251 : : * separately.
252 : : * A slightly faster way to do this would be to make the Karatsuba
253 : : * code below behave as if the size were even, and let it check for
254 : : * odd size in the end. I.e., in essence move this code to the end.
255 : : * Doing so would save us a recursive call, and potentially make the
256 : : * stack grow a lot less.
257 : : */
258 : 0 : mpi_size_t esize = size - 1; /* even size */
259 : 0 : mpi_limb_t cy_limb;
260 : :
261 [ # # ]: 0 : MPN_SQR_N_RECURSE(prodp, up, esize, tspace);
262 : 0 : cy_limb = mpihelp_addmul_1(prodp + esize, up, esize, up[esize]);
263 : 0 : prodp[esize + esize] = cy_limb;
264 : 0 : cy_limb = mpihelp_addmul_1(prodp + esize, up, size, up[esize]);
265 : :
266 : 0 : prodp[esize + size] = cy_limb;
267 : : } else {
268 : 704 : mpi_size_t hsize = size >> 1;
269 : 704 : mpi_limb_t cy;
270 : :
271 : : /* Product H. ________________ ________________
272 : : * |_____U1 x U1____||____U0 x U0_____|
273 : : * Put result in upper part of PROD and pass low part of TSPACE
274 : : * as new TSPACE.
275 : : */
276 [ + + ]: 704 : MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace);
277 : :
278 : : /* Product M. ________________
279 : : * |_(U1-U0)(U0-U1)_|
280 : : */
281 [ + + ]: 704 : if (mpihelp_cmp(up + hsize, up, hsize) >= 0)
282 : 275 : mpihelp_sub_n(prodp, up + hsize, up, hsize);
283 : : else
284 : 429 : mpihelp_sub_n(prodp, up, up + hsize, hsize);
285 : :
286 : : /* Read temporary operands from low part of PROD.
287 : : * Put result in low part of TSPACE using upper part of TSPACE
288 : : * as new TSPACE. */
289 [ + + ]: 704 : MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size);
290 : :
291 : : /* Add/copy product H */
292 [ + + ]: 7744 : MPN_COPY(prodp + hsize, prodp + size, hsize);
293 : 704 : cy = mpihelp_add_n(prodp + size, prodp + size,
294 : 704 : prodp + size + hsize, hsize);
295 : :
296 : : /* Add product M (if NEGFLG M is a negative number). */
297 : 704 : cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size);
298 : :
299 : : /* Product L. ________________ ________________
300 : : * |________________||____U0 x U0_____|
301 : : * Read temporary operands from low part of PROD.
302 : : * Put result in low part of TSPACE using upper part of TSPACE
303 : : * as new TSPACE. */
304 [ + + ]: 704 : MPN_SQR_N_RECURSE(tspace, up, hsize, tspace + size);
305 : :
306 : : /* Add/copy Product L (twice). */
307 : 704 : cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
308 [ + + ]: 704 : if (cy)
309 : 286 : mpihelp_add_1(prodp + hsize + size,
310 : : prodp + hsize + size, hsize, cy);
311 : :
312 [ + + ]: 7744 : MPN_COPY(prodp, tspace, hsize);
313 : 704 : cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize,
314 : : hsize);
315 [ + + ]: 704 : if (cy)
316 : 275 : mpihelp_add_1(prodp + size, prodp + size, size, 1);
317 : : }
318 : 704 : }
319 : :
320 : : int
321 : 11 : mpihelp_mul_karatsuba_case(mpi_ptr_t prodp,
322 : : mpi_ptr_t up, mpi_size_t usize,
323 : : mpi_ptr_t vp, mpi_size_t vsize,
324 : : struct karatsuba_ctx *ctx)
325 : : {
326 : 11 : mpi_limb_t cy;
327 : :
328 [ - + - - ]: 11 : if (!ctx->tspace || ctx->tspace_size < vsize) {
329 [ - + ]: 11 : if (ctx->tspace)
330 : 0 : mpi_free_limb_space(ctx->tspace);
331 : 11 : ctx->tspace = mpi_alloc_limb_space(2 * vsize);
332 [ + - ]: 11 : if (!ctx->tspace)
333 : : return -ENOMEM;
334 : 11 : ctx->tspace_size = vsize;
335 : : }
336 : :
337 [ - + ]: 11 : MPN_MUL_N_RECURSE(prodp, up, vp, vsize, ctx->tspace);
338 : :
339 : 11 : prodp += vsize;
340 : 11 : up += vsize;
341 : 11 : usize -= vsize;
342 [ - + ]: 11 : if (usize >= vsize) {
343 [ # # # # ]: 0 : if (!ctx->tp || ctx->tp_size < vsize) {
344 [ # # ]: 0 : if (ctx->tp)
345 : 0 : mpi_free_limb_space(ctx->tp);
346 : 0 : ctx->tp = mpi_alloc_limb_space(2 * vsize);
347 [ # # ]: 0 : if (!ctx->tp) {
348 [ # # ]: 0 : if (ctx->tspace)
349 : 0 : mpi_free_limb_space(ctx->tspace);
350 : 0 : ctx->tspace = NULL;
351 : 0 : return -ENOMEM;
352 : : }
353 : 0 : ctx->tp_size = vsize;
354 : : }
355 : :
356 : 0 : do {
357 [ # # ]: 0 : MPN_MUL_N_RECURSE(ctx->tp, up, vp, vsize, ctx->tspace);
358 : 0 : cy = mpihelp_add_n(prodp, prodp, ctx->tp, vsize);
359 : 0 : mpihelp_add_1(prodp + vsize, ctx->tp + vsize, vsize,
360 : : cy);
361 : 0 : prodp += vsize;
362 : 0 : up += vsize;
363 : 0 : usize -= vsize;
364 [ # # ]: 0 : } while (usize >= vsize);
365 : : }
366 : :
367 [ - + ]: 11 : if (usize) {
368 [ # # ]: 0 : if (usize < KARATSUBA_THRESHOLD) {
369 : 0 : mpi_limb_t tmp;
370 [ # # ]: 0 : if (mpihelp_mul(ctx->tspace, vp, vsize, up, usize, &tmp)
371 : : < 0)
372 : 0 : return -ENOMEM;
373 : : } else {
374 [ # # ]: 0 : if (!ctx->next) {
375 : 0 : ctx->next = kzalloc(sizeof *ctx, GFP_KERNEL);
376 [ # # ]: 0 : if (!ctx->next)
377 : : return -ENOMEM;
378 : : }
379 [ # # ]: 0 : if (mpihelp_mul_karatsuba_case(ctx->tspace,
380 : : vp, vsize,
381 : : up, usize,
382 : : ctx->next) < 0)
383 : : return -ENOMEM;
384 : : }
385 : :
386 : 0 : cy = mpihelp_add_n(prodp, prodp, ctx->tspace, vsize);
387 : 0 : mpihelp_add_1(prodp + vsize, ctx->tspace + vsize, usize, cy);
388 : : }
389 : :
390 : : return 0;
391 : : }
392 : :
393 : 11 : void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx)
394 : : {
395 : 11 : struct karatsuba_ctx *ctx2;
396 : :
397 [ - + ]: 11 : if (ctx->tp)
398 : 0 : mpi_free_limb_space(ctx->tp);
399 [ + - ]: 11 : if (ctx->tspace)
400 : 11 : mpi_free_limb_space(ctx->tspace);
401 [ - + ]: 11 : for (ctx = ctx->next; ctx; ctx = ctx2) {
402 : 0 : ctx2 = ctx->next;
403 [ # # ]: 0 : if (ctx->tp)
404 : 0 : mpi_free_limb_space(ctx->tp);
405 [ # # ]: 0 : if (ctx->tspace)
406 : 0 : mpi_free_limb_space(ctx->tspace);
407 : 0 : kfree(ctx);
408 : : }
409 : 11 : }
410 : :
411 : : /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
412 : : * and v (pointed to by VP, with VSIZE limbs), and store the result at
413 : : * PRODP. USIZE + VSIZE limbs are always stored, but if the input
414 : : * operands are normalized. Return the most significant limb of the
415 : : * result.
416 : : *
417 : : * NOTE: The space pointed to by PRODP is overwritten before finished
418 : : * with U and V, so overlap is an error.
419 : : *
420 : : * Argument constraints:
421 : : * 1. USIZE >= VSIZE.
422 : : * 2. PRODP != UP and PRODP != VP, i.e. the destination
423 : : * must be distinct from the multiplier and the multiplicand.
424 : : */
425 : :
426 : : int
427 : 0 : mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
428 : : mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result)
429 : : {
430 : 0 : mpi_ptr_t prod_endp = prodp + usize + vsize - 1;
431 : 0 : mpi_limb_t cy;
432 : 0 : struct karatsuba_ctx ctx;
433 : :
434 [ # # ]: 0 : if (vsize < KARATSUBA_THRESHOLD) {
435 : 0 : mpi_size_t i;
436 : 0 : mpi_limb_t v_limb;
437 : :
438 [ # # ]: 0 : if (!vsize) {
439 : 0 : *_result = 0;
440 : 0 : return 0;
441 : : }
442 : :
443 : : /* Multiply by the first limb in V separately, as the result can be
444 : : * stored (not added) to PROD. We also avoid a loop for zeroing. */
445 : 0 : v_limb = vp[0];
446 [ # # ]: 0 : if (v_limb <= 1) {
447 [ # # ]: 0 : if (v_limb == 1)
448 [ # # ]: 0 : MPN_COPY(prodp, up, usize);
449 : : else
450 [ # # ]: 0 : MPN_ZERO(prodp, usize);
451 : : cy = 0;
452 : : } else
453 : 0 : cy = mpihelp_mul_1(prodp, up, usize, v_limb);
454 : :
455 : 0 : prodp[usize] = cy;
456 : 0 : prodp++;
457 : :
458 : : /* For each iteration in the outer loop, multiply one limb from
459 : : * U with one limb from V, and add it to PROD. */
460 [ # # ]: 0 : for (i = 1; i < vsize; i++) {
461 : 0 : v_limb = vp[i];
462 [ # # ]: 0 : if (v_limb <= 1) {
463 : 0 : cy = 0;
464 [ # # ]: 0 : if (v_limb == 1)
465 : 0 : cy = mpihelp_add_n(prodp, prodp, up,
466 : : usize);
467 : : } else
468 : 0 : cy = mpihelp_addmul_1(prodp, up, usize, v_limb);
469 : :
470 : 0 : prodp[usize] = cy;
471 : 0 : prodp++;
472 : : }
473 : :
474 : 0 : *_result = cy;
475 : 0 : return 0;
476 : : }
477 : :
478 : 0 : memset(&ctx, 0, sizeof ctx);
479 [ # # ]: 0 : if (mpihelp_mul_karatsuba_case(prodp, up, usize, vp, vsize, &ctx) < 0)
480 : : return -ENOMEM;
481 : 0 : mpihelp_release_karatsuba_ctx(&ctx);
482 : 0 : *_result = *prod_endp;
483 : 0 : return 0;
484 : : }
|
