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.
34
#include "mpi-internal.h"
39
#define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
41
if( (size) < KARATSUBA_THRESHOLD ) \
42
mul_n_basecase (prodp, up, vp, size); \
44
mul_n (prodp, up, vp, size, tspace); \
47
#define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
49
if ((size) < KARATSUBA_THRESHOLD) \
50
mpih_sqr_n_basecase (prodp, up, size); \
52
mpih_sqr_n (prodp, up, size, tspace); \
58
/* Multiply the natural numbers u (pointed to by UP) and v (pointed to by VP),
59
* both with SIZE limbs, and store the result at PRODP. 2 * SIZE limbs are
60
* always stored. Return the most significant limb.
62
* Argument constraints:
63
* 1. PRODP != UP and PRODP != VP, i.e. the destination
64
* must be distinct from the multiplier and the multiplicand.
67
* Handle simple cases with traditional multiplication.
69
* This is the most critical code of multiplication. All multiplies rely
70
* on this, both small and huge. Small ones arrive here immediately. Huge
71
* ones arrive here as this is the base case for Karatsuba's recursive
76
mul_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up,
77
mpi_ptr_t vp, mpi_size_t size)
83
/* Multiply by the first limb in V separately, as the result can be
84
* stored (not added) to PROD. We also avoid a loop for zeroing. */
88
MPN_COPY( prodp, up, size );
90
MPN_ZERO( prodp, size );
94
cy = mpihelp_mul_1( prodp, up, size, v_limb );
99
/* For each iteration in the outer loop, multiply one limb from
100
* U with one limb from V, and add it to PROD. */
101
for( i = 1; i < size; i++ ) {
106
cy = mpihelp_add_n(prodp, prodp, up, size);
109
cy = mpihelp_addmul_1(prodp, up, size, v_limb);
120
mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
121
mpi_size_t size, mpi_ptr_t tspace )
124
/* The size is odd, and the code below doesn't handle that.
125
* Multiply the least significant (size - 1) limbs with a recursive
126
* call, and handle the most significant limb of S1 and S2
128
* A slightly faster way to do this would be to make the Karatsuba
129
* code below behave as if the size were even, and let it check for
130
* odd size in the end. I.e., in essence move this code to the end.
131
* Doing so would save us a recursive call, and potentially make the
132
* stack grow a lot less.
134
mpi_size_t esize = size - 1; /* even size */
137
MPN_MUL_N_RECURSE( prodp, up, vp, esize, tspace );
138
cy_limb = mpihelp_addmul_1( prodp + esize, up, esize, vp[esize] );
139
prodp[esize + esize] = cy_limb;
140
cy_limb = mpihelp_addmul_1( prodp + esize, vp, size, up[esize] );
141
prodp[esize + size] = cy_limb;
144
/* Anatolij Alekseevich Karatsuba's divide-and-conquer algorithm.
146
* Split U in two pieces, U1 and U0, such that
147
* U = U0 + U1*(B**n),
148
* and V in V1 and V0, such that
149
* V = V0 + V1*(B**n).
151
* UV is then computed recursively using the identity
154
* UV = (B + B )U V + B (U -U )(V -V ) + (B + 1)U V
157
* Where B = 2**BITS_PER_MP_LIMB.
159
mpi_size_t hsize = size >> 1;
163
/* Product H. ________________ ________________
164
* |_____U1 x V1____||____U0 x V0_____|
165
* Put result in upper part of PROD and pass low part of TSPACE
168
MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize, tspace);
170
/* Product M. ________________
173
if( mpihelp_cmp(up + hsize, up, hsize) >= 0 ) {
174
mpihelp_sub_n(prodp, up + hsize, up, hsize);
178
mpihelp_sub_n(prodp, up, up + hsize, hsize);
181
if( mpihelp_cmp(vp + hsize, vp, hsize) >= 0 ) {
182
mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize);
186
mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize);
187
/* No change of NEGFLG. */
189
/* Read temporary operands from low part of PROD.
190
* Put result in low part of TSPACE using upper part of TSPACE
193
MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize, tspace + size);
195
/* Add/copy product H. */
196
MPN_COPY (prodp + hsize, prodp + size, hsize);
197
cy = mpihelp_add_n( prodp + size, prodp + size,
198
prodp + size + hsize, hsize);
200
/* Add product M (if NEGFLG M is a negative number) */
202
cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size);
204
cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
206
/* Product L. ________________ ________________
207
* |________________||____U0 x V0_____|
208
* Read temporary operands from low part of PROD.
209
* Put result in low part of TSPACE using upper part of TSPACE
212
MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size);
214
/* Add/copy Product L (twice) */
216
cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
218
mpihelp_add_1(prodp + hsize + size, prodp + hsize + size, hsize, cy);
220
MPN_COPY(prodp, tspace, hsize);
221
cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize, hsize);
223
mpihelp_add_1(prodp + size, prodp + size, size, 1);
229
mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size )
235
/* Multiply by the first limb in V separately, as the result can be
236
* stored (not added) to PROD. We also avoid a loop for zeroing. */
240
MPN_COPY( prodp, up, size );
242
MPN_ZERO(prodp, size);
246
cy_limb = mpihelp_mul_1( prodp, up, size, v_limb );
248
prodp[size] = cy_limb;
251
/* For each iteration in the outer loop, multiply one limb from
252
* U with one limb from V, and add it to PROD. */
253
for( i=1; i < size; i++) {
258
cy_limb = mpihelp_add_n(prodp, prodp, up, size);
261
cy_limb = mpihelp_addmul_1(prodp, up, size, v_limb);
263
prodp[size] = cy_limb;
270
mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
273
/* The size is odd, and the code below doesn't handle that.
274
* Multiply the least significant (size - 1) limbs with a recursive
275
* call, and handle the most significant limb of S1 and S2
277
* A slightly faster way to do this would be to make the Karatsuba
278
* code below behave as if the size were even, and let it check for
279
* odd size in the end. I.e., in essence move this code to the end.
280
* Doing so would save us a recursive call, and potentially make the
281
* stack grow a lot less.
283
mpi_size_t esize = size - 1; /* even size */
286
MPN_SQR_N_RECURSE( prodp, up, esize, tspace );
287
cy_limb = mpihelp_addmul_1( prodp + esize, up, esize, up[esize] );
288
prodp[esize + esize] = cy_limb;
289
cy_limb = mpihelp_addmul_1( prodp + esize, up, size, up[esize] );
291
prodp[esize + size] = cy_limb;
294
mpi_size_t hsize = size >> 1;
297
/* Product H. ________________ ________________
298
* |_____U1 x U1____||____U0 x U0_____|
299
* Put result in upper part of PROD and pass low part of TSPACE
302
MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace);
304
/* Product M. ________________
307
if( mpihelp_cmp( up + hsize, up, hsize) >= 0 )
308
mpihelp_sub_n( prodp, up + hsize, up, hsize);
310
mpihelp_sub_n (prodp, up, up + hsize, hsize);
312
/* Read temporary operands from low part of PROD.
313
* Put result in low part of TSPACE using upper part of TSPACE
315
MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size);
317
/* Add/copy product H */
318
MPN_COPY(prodp + hsize, prodp + size, hsize);
319
cy = mpihelp_add_n(prodp + size, prodp + size,
320
prodp + size + hsize, hsize);
322
/* Add product M (if NEGFLG M is a negative number). */
323
cy -= mpihelp_sub_n (prodp + hsize, prodp + hsize, tspace, size);
325
/* Product L. ________________ ________________
326
* |________________||____U0 x U0_____|
327
* Read temporary operands from low part of PROD.
328
* Put result in low part of TSPACE using upper part of TSPACE
330
MPN_SQR_N_RECURSE (tspace, up, hsize, tspace + size);
332
/* Add/copy Product L (twice). */
333
cy += mpihelp_add_n (prodp + hsize, prodp + hsize, tspace, size);
335
mpihelp_add_1(prodp + hsize + size, prodp + hsize + size,
338
MPN_COPY(prodp, tspace, hsize);
339
cy = mpihelp_add_n (prodp + hsize, prodp + hsize, tspace + hsize, hsize);
341
mpihelp_add_1 (prodp + size, prodp + size, size, 1);
346
/* This should be made into an inline function in gmp.h. */
348
mpihelp_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
353
if( size < KARATSUBA_THRESHOLD )
354
mpih_sqr_n_basecase( prodp, up, size );
357
secure = m_is_secure( up );
358
tspace = mpi_alloc_limb_space( 2 * size, secure );
359
mpih_sqr_n( prodp, up, size, tspace );
360
mpi_free_limb_space( tspace );
364
if( size < KARATSUBA_THRESHOLD )
365
mul_n_basecase( prodp, up, vp, size );
368
secure = m_is_secure( up ) || m_is_secure( vp );
369
tspace = mpi_alloc_limb_space( 2 * size, secure );
370
mul_n (prodp, up, vp, size, tspace);
371
mpi_free_limb_space( tspace );
379
mpihelp_mul_karatsuba_case( mpi_ptr_t prodp,
380
mpi_ptr_t up, mpi_size_t usize,
381
mpi_ptr_t vp, mpi_size_t vsize,
382
struct karatsuba_ctx *ctx )
386
if( !ctx->tspace || ctx->tspace_size < vsize ) {
388
mpi_free_limb_space( ctx->tspace );
389
ctx->tspace = mpi_alloc_limb_space( 2 * vsize,
390
m_is_secure( up ) || m_is_secure( vp ) );
391
ctx->tspace_size = vsize;
394
MPN_MUL_N_RECURSE( prodp, up, vp, vsize, ctx->tspace );
399
if( usize >= vsize ) {
400
if( !ctx->tp || ctx->tp_size < vsize ) {
402
mpi_free_limb_space( ctx->tp );
403
ctx->tp = mpi_alloc_limb_space( 2 * vsize, m_is_secure( up )
404
|| m_is_secure( vp ) );
405
ctx->tp_size = vsize;
409
MPN_MUL_N_RECURSE( ctx->tp, up, vp, vsize, ctx->tspace );
410
cy = mpihelp_add_n( prodp, prodp, ctx->tp, vsize );
411
mpihelp_add_1( prodp + vsize, ctx->tp + vsize, vsize, cy );
415
} while( usize >= vsize );
419
if( usize < KARATSUBA_THRESHOLD ) {
420
mpihelp_mul( ctx->tspace, vp, vsize, up, usize );
424
ctx->next = m_alloc_clear( sizeof *ctx );
426
mpihelp_mul_karatsuba_case( ctx->tspace,
432
cy = mpihelp_add_n( prodp, prodp, ctx->tspace, vsize);
433
mpihelp_add_1( prodp + vsize, ctx->tspace + vsize, usize, cy );
439
mpihelp_release_karatsuba_ctx( struct karatsuba_ctx *ctx )
441
struct karatsuba_ctx *ctx2;
444
mpi_free_limb_space( ctx->tp );
446
mpi_free_limb_space( ctx->tspace );
447
for( ctx=ctx->next; ctx; ctx = ctx2 ) {
450
mpi_free_limb_space( ctx->tp );
452
mpi_free_limb_space( ctx->tspace );
457
/* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
458
* and v (pointed to by VP, with VSIZE limbs), and store the result at
459
* PRODP. USIZE + VSIZE limbs are always stored, but if the input
460
* operands are normalized. Return the most significant limb of the
463
* NOTE: The space pointed to by PRODP is overwritten before finished
464
* with U and V, so overlap is an error.
466
* Argument constraints:
468
* 2. PRODP != UP and PRODP != VP, i.e. the destination
469
* must be distinct from the multiplier and the multiplicand.
473
mpihelp_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
474
mpi_ptr_t vp, mpi_size_t vsize)
476
mpi_ptr_t prod_endp = prodp + usize + vsize - 1;
478
struct karatsuba_ctx ctx;
480
if( vsize < KARATSUBA_THRESHOLD ) {
487
/* Multiply by the first limb in V separately, as the result can be
488
* stored (not added) to PROD. We also avoid a loop for zeroing. */
492
MPN_COPY( prodp, up, usize );
494
MPN_ZERO( prodp, usize );
498
cy = mpihelp_mul_1( prodp, up, usize, v_limb );
503
/* For each iteration in the outer loop, multiply one limb from
504
* U with one limb from V, and add it to PROD. */
505
for( i = 1; i < vsize; i++ ) {
510
cy = mpihelp_add_n(prodp, prodp, up, usize);
513
cy = mpihelp_addmul_1(prodp, up, usize, v_limb);
522
memset( &ctx, 0, sizeof ctx );
523
mpihelp_mul_karatsuba_case( prodp, up, usize, vp, vsize, &ctx );
524
mpihelp_release_karatsuba_ctx( &ctx );
added
removed
mpi/mpih-mul.c
