]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - lib/mpi/mpih-mul.c
1 /* mpihelp-mul.c - MPI helper functions
2 * Copyright (C) 1994, 1996, 1998, 1999,
3 * 2000 Free Software Foundation, Inc.
5 * This file is part of GnuPG.
7 * GnuPG is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * GnuPG 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 General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
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 * The GNU MP Library itself is published under the LGPL;
27 * however I decided to publish this code under the plain GPL.
30 #include <linux/string.h>
31 #include "mpi-internal.h"
34 #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
36 if ((size) < KARATSUBA_THRESHOLD) \
37 mul_n_basecase(prodp, up, vp, size); \
39 mul_n(prodp, up, vp, size, tspace); \
42 #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
44 if ((size) < KARATSUBA_THRESHOLD) \
45 mpih_sqr_n_basecase(prodp, up, size); \
47 mpih_sqr_n(prodp, up, size, tspace); \
50 /* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP),
51 * both with SIZE limbs, and store the result at PRODP. 2 * SIZE limbs are
52 * always stored. Return the most significant limb.
54 * Argument constraints:
55 * 1. PRODP != UP and PRODP != VP, i.e. the destination
56 * must be distinct from the multiplier and the multiplicand.
59 * Handle simple cases with traditional multiplication.
61 * This is the most critical code of multiplication. All multiplies rely
62 * on this, both small and huge. Small ones arrive here immediately. Huge
63 * ones arrive here as this is the base case for Karatsuba's recursive
68 mul_n_basecase(mpi_ptr_t prodp
, mpi_ptr_t up
, mpi_ptr_t vp
, mpi_size_t size
)
74 /* Multiply by the first limb in V separately, as the result can be
75 * stored (not added) to PROD. We also avoid a loop for zeroing. */
79 MPN_COPY(prodp
, up
, size
);
81 MPN_ZERO(prodp
, size
);
84 cy
= mpihelp_mul_1(prodp
, up
, size
, v_limb
);
89 /* For each iteration in the outer loop, multiply one limb from
90 * U with one limb from V, and add it to PROD. */
91 for (i
= 1; i
< size
; i
++) {
96 cy
= mpihelp_add_n(prodp
, prodp
, up
, size
);
98 cy
= mpihelp_addmul_1(prodp
, up
, size
, v_limb
);
108 mul_n(mpi_ptr_t prodp
, mpi_ptr_t up
, mpi_ptr_t vp
,
109 mpi_size_t size
, mpi_ptr_t tspace
)
112 /* The size is odd, and the code below doesn't handle that.
113 * Multiply the least significant (size - 1) limbs with a recursive
114 * call, and handle the most significant limb of S1 and S2
116 * A slightly faster way to do this would be to make the Karatsuba
117 * code below behave as if the size were even, and let it check for
118 * odd size in the end. I.e., in essence move this code to the end.
119 * Doing so would save us a recursive call, and potentially make the
120 * stack grow a lot less.
122 mpi_size_t esize
= size
- 1; /* even size */
125 MPN_MUL_N_RECURSE(prodp
, up
, vp
, esize
, tspace
);
126 cy_limb
= mpihelp_addmul_1(prodp
+ esize
, up
, esize
, vp
[esize
]);
127 prodp
[esize
+ esize
] = cy_limb
;
128 cy_limb
= mpihelp_addmul_1(prodp
+ esize
, vp
, size
, up
[esize
]);
129 prodp
[esize
+ size
] = cy_limb
;
131 /* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm.
133 * Split U in two pieces, U1 and U0, such that
134 * U = U0 + U1*(B**n),
135 * and V in V1 and V0, such that
136 * V = V0 + V1*(B**n).
138 * UV is then computed recursively using the identity
141 * UV = (B + B )U V + B (U -U )(V -V ) + (B + 1)U V
144 * Where B = 2**BITS_PER_MP_LIMB.
146 mpi_size_t hsize
= size
>> 1;
150 /* Product H. ________________ ________________
151 * |_____U1 x V1____||____U0 x V0_____|
152 * Put result in upper part of PROD and pass low part of TSPACE
155 MPN_MUL_N_RECURSE(prodp
+ size
, up
+ hsize
, vp
+ hsize
, hsize
,
158 /* Product M. ________________
161 if (mpihelp_cmp(up
+ hsize
, up
, hsize
) >= 0) {
162 mpihelp_sub_n(prodp
, up
+ hsize
, up
, hsize
);
165 mpihelp_sub_n(prodp
, up
, up
+ hsize
, hsize
);
168 if (mpihelp_cmp(vp
+ hsize
, vp
, hsize
) >= 0) {
169 mpihelp_sub_n(prodp
+ hsize
, vp
+ hsize
, vp
, hsize
);
172 mpihelp_sub_n(prodp
+ hsize
, vp
, vp
+ hsize
, hsize
);
173 /* No change of NEGFLG. */
175 /* Read temporary operands from low part of PROD.
176 * Put result in low part of TSPACE using upper part of TSPACE
179 MPN_MUL_N_RECURSE(tspace
, prodp
, prodp
+ hsize
, hsize
,
182 /* Add/copy product H. */
183 MPN_COPY(prodp
+ hsize
, prodp
+ size
, hsize
);
184 cy
= mpihelp_add_n(prodp
+ size
, prodp
+ size
,
185 prodp
+ size
+ hsize
, hsize
);
187 /* Add product M (if NEGFLG M is a negative number) */
190 mpihelp_sub_n(prodp
+ hsize
, prodp
+ hsize
, tspace
,
194 mpihelp_add_n(prodp
+ hsize
, prodp
+ hsize
, tspace
,
197 /* Product L. ________________ ________________
198 * |________________||____U0 x V0_____|
199 * Read temporary operands from low part of PROD.
200 * Put result in low part of TSPACE using upper part of TSPACE
203 MPN_MUL_N_RECURSE(tspace
, up
, vp
, hsize
, tspace
+ size
);
205 /* Add/copy Product L (twice) */
207 cy
+= mpihelp_add_n(prodp
+ hsize
, prodp
+ hsize
, tspace
, size
);
209 mpihelp_add_1(prodp
+ hsize
+ size
,
210 prodp
+ hsize
+ size
, hsize
, cy
);
212 MPN_COPY(prodp
, tspace
, hsize
);
213 cy
= mpihelp_add_n(prodp
+ hsize
, prodp
+ hsize
, tspace
+ hsize
,
216 mpihelp_add_1(prodp
+ size
, prodp
+ size
, size
, 1);
220 void mpih_sqr_n_basecase(mpi_ptr_t prodp
, mpi_ptr_t up
, mpi_size_t size
)
226 /* Multiply by the first limb in V separately, as the result can be
227 * stored (not added) to PROD. We also avoid a loop for zeroing. */
231 MPN_COPY(prodp
, up
, size
);
233 MPN_ZERO(prodp
, size
);
236 cy_limb
= mpihelp_mul_1(prodp
, up
, size
, v_limb
);
238 prodp
[size
] = cy_limb
;
241 /* For each iteration in the outer loop, multiply one limb from
242 * U with one limb from V, and add it to PROD. */
243 for (i
= 1; i
< size
; i
++) {
248 cy_limb
= mpihelp_add_n(prodp
, prodp
, up
, size
);
250 cy_limb
= mpihelp_addmul_1(prodp
, up
, size
, v_limb
);
252 prodp
[size
] = cy_limb
;
258 mpih_sqr_n(mpi_ptr_t prodp
, mpi_ptr_t up
, mpi_size_t size
, mpi_ptr_t tspace
)
261 /* The size is odd, and the code below doesn't handle that.
262 * Multiply the least significant (size - 1) limbs with a recursive
263 * call, and handle the most significant limb of S1 and S2
265 * A slightly faster way to do this would be to make the Karatsuba
266 * code below behave as if the size were even, and let it check for
267 * odd size in the end. I.e., in essence move this code to the end.
268 * Doing so would save us a recursive call, and potentially make the
269 * stack grow a lot less.
271 mpi_size_t esize
= size
- 1; /* even size */
274 MPN_SQR_N_RECURSE(prodp
, up
, esize
, tspace
);
275 cy_limb
= mpihelp_addmul_1(prodp
+ esize
, up
, esize
, up
[esize
]);
276 prodp
[esize
+ esize
] = cy_limb
;
277 cy_limb
= mpihelp_addmul_1(prodp
+ esize
, up
, size
, up
[esize
]);
279 prodp
[esize
+ size
] = cy_limb
;
281 mpi_size_t hsize
= size
>> 1;
284 /* Product H. ________________ ________________
285 * |_____U1 x U1____||____U0 x U0_____|
286 * Put result in upper part of PROD and pass low part of TSPACE
289 MPN_SQR_N_RECURSE(prodp
+ size
, up
+ hsize
, hsize
, tspace
);
291 /* Product M. ________________
294 if (mpihelp_cmp(up
+ hsize
, up
, hsize
) >= 0)
295 mpihelp_sub_n(prodp
, up
+ hsize
, up
, hsize
);
297 mpihelp_sub_n(prodp
, up
, up
+ hsize
, hsize
);
299 /* Read temporary operands from low part of PROD.
300 * Put result in low part of TSPACE using upper part of TSPACE
302 MPN_SQR_N_RECURSE(tspace
, prodp
, hsize
, tspace
+ size
);
304 /* Add/copy product H */
305 MPN_COPY(prodp
+ hsize
, prodp
+ size
, hsize
);
306 cy
= mpihelp_add_n(prodp
+ size
, prodp
+ size
,
307 prodp
+ size
+ hsize
, hsize
);
309 /* Add product M (if NEGFLG M is a negative number). */
310 cy
-= mpihelp_sub_n(prodp
+ hsize
, prodp
+ hsize
, tspace
, size
);
312 /* Product L. ________________ ________________
313 * |________________||____U0 x U0_____|
314 * Read temporary operands from low part of PROD.
315 * Put result in low part of TSPACE using upper part of TSPACE
317 MPN_SQR_N_RECURSE(tspace
, up
, hsize
, tspace
+ size
);
319 /* Add/copy Product L (twice). */
320 cy
+= mpihelp_add_n(prodp
+ hsize
, prodp
+ hsize
, tspace
, size
);
322 mpihelp_add_1(prodp
+ hsize
+ size
,
323 prodp
+ hsize
+ size
, hsize
, cy
);
325 MPN_COPY(prodp
, tspace
, hsize
);
326 cy
= mpihelp_add_n(prodp
+ hsize
, prodp
+ hsize
, tspace
+ hsize
,
329 mpihelp_add_1(prodp
+ size
, prodp
+ size
, size
, 1);
334 mpihelp_mul_karatsuba_case(mpi_ptr_t prodp
,
335 mpi_ptr_t up
, mpi_size_t usize
,
336 mpi_ptr_t vp
, mpi_size_t vsize
,
337 struct karatsuba_ctx
*ctx
)
341 if (!ctx
->tspace
|| ctx
->tspace_size
< vsize
) {
343 mpi_free_limb_space(ctx
->tspace
);
344 ctx
->tspace
= mpi_alloc_limb_space(2 * vsize
);
347 ctx
->tspace_size
= vsize
;
350 MPN_MUL_N_RECURSE(prodp
, up
, vp
, vsize
, ctx
->tspace
);
355 if (usize
>= vsize
) {
356 if (!ctx
->tp
|| ctx
->tp_size
< vsize
) {
358 mpi_free_limb_space(ctx
->tp
);
359 ctx
->tp
= mpi_alloc_limb_space(2 * vsize
);
362 mpi_free_limb_space(ctx
->tspace
);
366 ctx
->tp_size
= vsize
;
370 MPN_MUL_N_RECURSE(ctx
->tp
, up
, vp
, vsize
, ctx
->tspace
);
371 cy
= mpihelp_add_n(prodp
, prodp
, ctx
->tp
, vsize
);
372 mpihelp_add_1(prodp
+ vsize
, ctx
->tp
+ vsize
, vsize
,
377 } while (usize
>= vsize
);
381 if (usize
< KARATSUBA_THRESHOLD
) {
383 if (mpihelp_mul(ctx
->tspace
, vp
, vsize
, up
, usize
, &tmp
)
388 ctx
->next
= kzalloc(sizeof *ctx
, GFP_KERNEL
);
392 if (mpihelp_mul_karatsuba_case(ctx
->tspace
,
399 cy
= mpihelp_add_n(prodp
, prodp
, ctx
->tspace
, vsize
);
400 mpihelp_add_1(prodp
+ vsize
, ctx
->tspace
+ vsize
, usize
, cy
);
406 void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx
*ctx
)
408 struct karatsuba_ctx
*ctx2
;
411 mpi_free_limb_space(ctx
->tp
);
413 mpi_free_limb_space(ctx
->tspace
);
414 for (ctx
= ctx
->next
; ctx
; ctx
= ctx2
) {
417 mpi_free_limb_space(ctx
->tp
);
419 mpi_free_limb_space(ctx
->tspace
);
424 /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
425 * and v (pointed to by VP, with VSIZE limbs), and store the result at
426 * PRODP. USIZE + VSIZE limbs are always stored, but if the input
427 * operands are normalized. Return the most significant limb of the
430 * NOTE: The space pointed to by PRODP is overwritten before finished
431 * with U and V, so overlap is an error.
433 * Argument constraints:
435 * 2. PRODP != UP and PRODP != VP, i.e. the destination
436 * must be distinct from the multiplier and the multiplicand.
440 mpihelp_mul(mpi_ptr_t prodp
, mpi_ptr_t up
, mpi_size_t usize
,
441 mpi_ptr_t vp
, mpi_size_t vsize
, mpi_limb_t
*_result
)
443 mpi_ptr_t prod_endp
= prodp
+ usize
+ vsize
- 1;
445 struct karatsuba_ctx ctx
;
447 if (vsize
< KARATSUBA_THRESHOLD
) {
456 /* Multiply by the first limb in V separately, as the result can be
457 * stored (not added) to PROD. We also avoid a loop for zeroing. */
461 MPN_COPY(prodp
, up
, usize
);
463 MPN_ZERO(prodp
, usize
);
466 cy
= mpihelp_mul_1(prodp
, up
, usize
, v_limb
);
471 /* For each iteration in the outer loop, multiply one limb from
472 * U with one limb from V, and add it to PROD. */
473 for (i
= 1; i
< vsize
; i
++) {
478 cy
= mpihelp_add_n(prodp
, prodp
, up
,
481 cy
= mpihelp_addmul_1(prodp
, up
, usize
, v_limb
);
491 memset(&ctx
, 0, sizeof ctx
);
492 if (mpihelp_mul_karatsuba_case(prodp
, up
, usize
, vp
, vsize
, &ctx
) < 0)
494 mpihelp_release_karatsuba_ctx(&ctx
);
495 *_result
= *prod_endp
;