mpi-genesis 1
mpi-genesis 2 * Copyright (C) 1994, 1996, 1998, 1999,
mpi-genesis 3 * 2000 Free Software Foundation, Inc.
mpi-genesis 4 *
mpi-genesis 5 * This file is part of GnuPG.
mpi-genesis 6 *
mpi-genesis 7 * GnuPG is free software; you can redistribute it and/or modify
mpi-genesis 8 * it under the terms of the GNU General Public License as published by
mpi-genesis 9 * the Free Software Foundation; either version 3 of the License, or
mpi-genesis 10 * (at your option) any later version.
mpi-genesis 11 *
mpi-genesis 12 * GnuPG is distributed in the hope that it will be useful,
mpi-genesis 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
mpi-genesis 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
mpi-genesis 15 * GNU General Public License for more details.
mpi-genesis 16 *
mpi-genesis 17 * You should have received a copy of the GNU General Public License
mpi-genesis 18 * along with this program; if not, see <http:
mpi-genesis 19 *
mpi-genesis 20 * Note: This code is heavily based on the GNU MP Library.
mpi-genesis 21 * Actually it's the same code with only minor changes in the
mpi-genesis 22 * way the data is stored; this is to support the abstraction
mpi-genesis 23 * of an optional secure memory allocation which may be used
mpi-genesis 24 * to avoid revealing of sensitive data due to paging etc.
mpi-genesis 25 * The GNU MP Library itself is published under the LGPL;
mpi-genesis 26 * however I decided to publish this code under the plain GPL.
mpi-genesis 27 */
mpi-genesis 28
mpi-genesis 29 #include <config.h>
mpi-genesis 30 #include <stdio.h>
mpi-genesis 31 #include <stdlib.h>
mpi-genesis 32 #include <string.h>
mpi-genesis 33 #include "mpi-internal.h"
mpi-genesis 34 #include "longlong.h"
mpi-genesis 35
mpi-genesis 36
mpi-genesis 37
mpi-genesis 38 #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
mpi-genesis 39 do { \
mpi-genesis 40 if( (size) < KARATSUBA_THRESHOLD ) \
mpi-genesis 41 mul_n_basecase (prodp, up, vp, size); \
mpi-genesis 42 else \
mpi-genesis 43 mul_n (prodp, up, vp, size, tspace); \
mpi-genesis 44 } while (0);
mpi-genesis 45
mpi-genesis 46 #define MPN_SQR_N_RECURSE(prodp, up, size, tspace) \
mpi-genesis 47 do { \
mpi-genesis 48 if ((size) < KARATSUBA_THRESHOLD) \
mpi-genesis 49 mpih_sqr_n_basecase (prodp, up, size); \
mpi-genesis 50 else \
mpi-genesis 51 mpih_sqr_n (prodp, up, size, tspace); \
mpi-genesis 52 } while (0);
mpi-genesis 53
mpi-genesis 54
mpi-genesis 55
mpi-genesis 56
mpi-genesis 57
mpi-genesis 58 * both with SIZE limbs, and store the result at PRODP. 2 * SIZE limbs are
mpi-genesis 59 * always stored. Return the most significant limb.
mpi-genesis 60 *
mpi-genesis 61 * Argument constraints:
mpi-genesis 62 * 1. PRODP != UP and PRODP != VP, i.e. the destination
mpi-genesis 63 * must be distinct from the multiplier and the multiplicand.
mpi-genesis 64 *
mpi-genesis 65 *
mpi-genesis 66 * Handle simple cases with traditional multiplication.
mpi-genesis 67 *
mpi-genesis 68 * This is the most critical code of multiplication. All multiplies rely
mpi-genesis 69 * on this, both small and huge. Small ones arrive here immediately. Huge
mpi-genesis 70 * ones arrive here as this is the base case for Karatsuba's recursive
mpi-genesis 71 * algorithm below.
mpi-genesis 72 */
mpi-genesis 73
mpi-genesis 74 static mpi_limb_t
mpi-genesis 75 mul_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up,
mpi-genesis 76 mpi_ptr_t vp, mpi_size_t size)
mpi-genesis 77 {
mpi-genesis 78 mpi_size_t i;
mpi-genesis 79 mpi_limb_t cy;
mpi-genesis 80 mpi_limb_t v_limb;
mpi-genesis 81
mpi-genesis 82
mpi-genesis 83 * stored (not added) to PROD. We also avoid a loop for zeroing. */
mpi-genesis 84 v_limb = vp[0];
mpi-genesis 85 if( v_limb <= 1 ) {
mpi-genesis 86 if( v_limb == 1 )
mpi-genesis 87 MPN_COPY( prodp, up, size );
mpi-genesis 88 else
mpi-genesis 89 MPN_ZERO( prodp, size );
mpi-genesis 90 cy = 0;
mpi-genesis 91 }
mpi-genesis 92 else
mpi-genesis 93 cy = mpihelp_mul_1( prodp, up, size, v_limb );
mpi-genesis 94
mpi-genesis 95 prodp[size] = cy;
mpi-genesis 96 prodp++;
mpi-genesis 97
mpi-genesis 98
mpi-genesis 99 * U with one limb from V, and add it to PROD. */
mpi-genesis 100 for( i = 1; i < size; i++ ) {
mpi-genesis 101 v_limb = vp[i];
mpi-genesis 102 if( v_limb <= 1 ) {
mpi-genesis 103 cy = 0;
mpi-genesis 104 if( v_limb == 1 )
mpi-genesis 105 cy = mpihelp_add_n(prodp, prodp, up, size);
mpi-genesis 106 }
mpi-genesis 107 else
mpi-genesis 108 cy = mpihelp_addmul_1(prodp, up, size, v_limb);
mpi-genesis 109
mpi-genesis 110 prodp[size] = cy;
mpi-genesis 111 prodp++;
mpi-genesis 112 }
mpi-genesis 113
mpi-genesis 114 return cy;
mpi-genesis 115 }
mpi-genesis 116
mpi-genesis 117
mpi-genesis 118 static void
mpi-genesis 119 mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp,
mpi-genesis 120 mpi_size_t size, mpi_ptr_t tspace )
mpi-genesis 121 {
mpi-genesis 122 if( size & 1 ) {
mpi-genesis 123
mpi-genesis 124 * Multiply the least significant (size - 1) limbs with a recursive
mpi-genesis 125 * call, and handle the most significant limb of S1 and S2
mpi-genesis 126 * separately.
mpi-genesis 127 * A slightly faster way to do this would be to make the Karatsuba
mpi-genesis 128 * code below behave as if the size were even, and let it check for
mpi-genesis 129 * odd size in the end. I.e., in essence move this code to the end.
mpi-genesis 130 * Doing so would save us a recursive call, and potentially make the
mpi-genesis 131 * stack grow a lot less.
mpi-genesis 132 */
mpi-genesis 133 mpi_size_t esize = size - 1;
mpi-genesis 134 mpi_limb_t cy_limb;
mpi-genesis 135
mpi-genesis 136 MPN_MUL_N_RECURSE( prodp, up, vp, esize, tspace );
mpi-genesis 137 cy_limb = mpihelp_addmul_1( prodp + esize, up, esize, vp[esize] );
mpi-genesis 138 prodp[esize + esize] = cy_limb;
mpi-genesis 139 cy_limb = mpihelp_addmul_1( prodp + esize, vp, size, up[esize] );
mpi-genesis 140 prodp[esize + size] = cy_limb;
mpi-genesis 141 }
mpi-genesis 142 else {
mpi-genesis 143
mpi-genesis 144 *
mpi-genesis 145 * Split U in two pieces, U1 and U0, such that
mpi-genesis 146 * U = U0 + U1*(B**n),
mpi-genesis 147 * and V in V1 and V0, such that
mpi-genesis 148 * V = V0 + V1*(B**n).
mpi-genesis 149 *
mpi-genesis 150 * UV is then computed recursively using the identity
mpi-genesis 151 *
mpi-genesis 152 * 2n n n n
mpi-genesis 153 * UV = (B + B )U V + B (U -U )(V -V ) + (B + 1)U V
mpi-genesis 154 * 1 1 1 0 0 1 0 0
mpi-genesis 155 *
mpi-genesis 156 * Where B = 2**BITS_PER_MP_LIMB.
mpi-genesis 157 */
mpi-genesis 158 mpi_size_t hsize = size >> 1;
mpi-genesis 159 mpi_limb_t cy;
mpi-genesis 160 int negflg;
mpi-genesis 161
mpi-genesis 162
mpi-genesis 163 * |_____U1 x V1____||____U0 x V0_____|
mpi-genesis 164 * Put result in upper part of PROD and pass low part of TSPACE
mpi-genesis 165 * as new TSPACE.
mpi-genesis 166 */
mpi-genesis 167 MPN_MUL_N_RECURSE(prodp + size, up + hsize, vp + hsize, hsize, tspace);
mpi-genesis 168
mpi-genesis 169
mpi-genesis 170 * |_(U1-U0)(V0-V1)_|
mpi-genesis 171 */
mpi-genesis 172 if( mpihelp_cmp(up + hsize, up, hsize) >= 0 ) {
mpi-genesis 173 mpihelp_sub_n(prodp, up + hsize, up, hsize);
mpi-genesis 174 negflg = 0;
mpi-genesis 175 }
mpi-genesis 176 else {
mpi-genesis 177 mpihelp_sub_n(prodp, up, up + hsize, hsize);
mpi-genesis 178 negflg = 1;
mpi-genesis 179 }
mpi-genesis 180 if( mpihelp_cmp(vp + hsize, vp, hsize) >= 0 ) {
mpi-genesis 181 mpihelp_sub_n(prodp + hsize, vp + hsize, vp, hsize);
mpi-genesis 182 negflg ^= 1;
mpi-genesis 183 }
mpi-genesis 184 else {
mpi-genesis 185 mpihelp_sub_n(prodp + hsize, vp, vp + hsize, hsize);
mpi-genesis 186
mpi-genesis 187 }
mpi-genesis 188
mpi-genesis 189 * Put result in low part of TSPACE using upper part of TSPACE
mpi-genesis 190 * as new TSPACE.
mpi-genesis 191 */
mpi-genesis 192 MPN_MUL_N_RECURSE(tspace, prodp, prodp + hsize, hsize, tspace + size);
mpi-genesis 193
mpi-genesis 194
mpi-genesis 195 MPN_COPY (prodp + hsize, prodp + size, hsize);
mpi-genesis 196 cy = mpihelp_add_n( prodp + size, prodp + size,
mpi-genesis 197 prodp + size + hsize, hsize);
mpi-genesis 198
mpi-genesis 199
mpi-genesis 200 if(negflg)
mpi-genesis 201 cy -= mpihelp_sub_n(prodp + hsize, prodp + hsize, tspace, size);
mpi-genesis 202 else
mpi-genesis 203 cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
mpi-genesis 204
mpi-genesis 205
mpi-genesis 206 * |________________||____U0 x V0_____|
mpi-genesis 207 * Read temporary operands from low part of PROD.
mpi-genesis 208 * Put result in low part of TSPACE using upper part of TSPACE
mpi-genesis 209 * as new TSPACE.
mpi-genesis 210 */
mpi-genesis 211 MPN_MUL_N_RECURSE(tspace, up, vp, hsize, tspace + size);
mpi-genesis 212
mpi-genesis 213
mpi-genesis 214
mpi-genesis 215 cy += mpihelp_add_n(prodp + hsize, prodp + hsize, tspace, size);
mpi-genesis 216 if( cy )
mpi-genesis 217 mpihelp_add_1(prodp + hsize + size, prodp + hsize + size, hsize, cy);
mpi-genesis 218
mpi-genesis 219 MPN_COPY(prodp, tspace, hsize);
mpi-genesis 220 cy = mpihelp_add_n(prodp + hsize, prodp + hsize, tspace + hsize, hsize);
mpi-genesis 221 if( cy )
mpi-genesis 222 mpihelp_add_1(prodp + size, prodp + size, size, 1);
mpi-genesis 223 }
mpi-genesis 224 }
mpi-genesis 225
mpi-genesis 226
mpi-genesis 227 void
mpi-genesis 228 mpih_sqr_n_basecase( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size )
mpi-genesis 229 {
mpi-genesis 230 mpi_size_t i;
mpi-genesis 231 mpi_limb_t cy_limb;
mpi-genesis 232 mpi_limb_t v_limb;
mpi-genesis 233
mpi-genesis 234
mpi-genesis 235 * stored (not added) to PROD. We also avoid a loop for zeroing. */
mpi-genesis 236 v_limb = up[0];
mpi-genesis 237 if( v_limb <= 1 ) {
mpi-genesis 238 if( v_limb == 1 )
mpi-genesis 239 MPN_COPY( prodp, up, size );
mpi-genesis 240 else
mpi-genesis 241 MPN_ZERO(prodp, size);
mpi-genesis 242 cy_limb = 0;
mpi-genesis 243 }
mpi-genesis 244 else
mpi-genesis 245 cy_limb = mpihelp_mul_1( prodp, up, size, v_limb );
mpi-genesis 246
mpi-genesis 247 prodp[size] = cy_limb;
mpi-genesis 248 prodp++;
mpi-genesis 249
mpi-genesis 250
mpi-genesis 251 * U with one limb from V, and add it to PROD. */
mpi-genesis 252 for( i=1; i < size; i++) {
mpi-genesis 253 v_limb = up[i];
mpi-genesis 254 if( v_limb <= 1 ) {
mpi-genesis 255 cy_limb = 0;
mpi-genesis 256 if( v_limb == 1 )
mpi-genesis 257 cy_limb = mpihelp_add_n(prodp, prodp, up, size);
mpi-genesis 258 }
mpi-genesis 259 else
mpi-genesis 260 cy_limb = mpihelp_addmul_1(prodp, up, size, v_limb);
mpi-genesis 261
mpi-genesis 262 prodp[size] = cy_limb;
mpi-genesis 263 prodp++;
mpi-genesis 264 }
mpi-genesis 265 }
mpi-genesis 266
mpi-genesis 267
mpi-genesis 268 void
mpi-genesis 269 mpih_sqr_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size, mpi_ptr_t tspace)
mpi-genesis 270 {
mpi-genesis 271 if( size & 1 ) {
mpi-genesis 272
mpi-genesis 273 * Multiply the least significant (size - 1) limbs with a recursive
mpi-genesis 274 * call, and handle the most significant limb of S1 and S2
mpi-genesis 275 * separately.
mpi-genesis 276 * A slightly faster way to do this would be to make the Karatsuba
mpi-genesis 277 * code below behave as if the size were even, and let it check for
mpi-genesis 278 * odd size in the end. I.e., in essence move this code to the end.
mpi-genesis 279 * Doing so would save us a recursive call, and potentially make the
mpi-genesis 280 * stack grow a lot less.
mpi-genesis 281 */
mpi-genesis 282 mpi_size_t esize = size - 1;
mpi-genesis 283 mpi_limb_t cy_limb;
mpi-genesis 284
mpi-genesis 285 MPN_SQR_N_RECURSE( prodp, up, esize, tspace );
mpi-genesis 286 cy_limb = mpihelp_addmul_1( prodp + esize, up, esize, up[esize] );
mpi-genesis 287 prodp[esize + esize] = cy_limb;
mpi-genesis 288 cy_limb = mpihelp_addmul_1( prodp + esize, up, size, up[esize] );
mpi-genesis 289
mpi-genesis 290 prodp[esize + size] = cy_limb;
mpi-genesis 291 }
mpi-genesis 292 else {
mpi-genesis 293 mpi_size_t hsize = size >> 1;
mpi-genesis 294 mpi_limb_t cy;
mpi-genesis 295
mpi-genesis 296
mpi-genesis 297 * |_____U1 x U1____||____U0 x U0_____|
mpi-genesis 298 * Put result in upper part of PROD and pass low part of TSPACE
mpi-genesis 299 * as new TSPACE.
mpi-genesis 300 */
mpi-genesis 301 MPN_SQR_N_RECURSE(prodp + size, up + hsize, hsize, tspace);
mpi-genesis 302
mpi-genesis 303
mpi-genesis 304 * |_(U1-U0)(U0-U1)_|
mpi-genesis 305 */
mpi-genesis 306 if( mpihelp_cmp( up + hsize, up, hsize) >= 0 )
mpi-genesis 307 mpihelp_sub_n( prodp, up + hsize, up, hsize);
mpi-genesis 308 else
mpi-genesis 309 mpihelp_sub_n (prodp, up, up + hsize, hsize);
mpi-genesis 310
mpi-genesis 311
mpi-genesis 312 * Put result in low part of TSPACE using upper part of TSPACE
mpi-genesis 313 * as new TSPACE. */
mpi-genesis 314 MPN_SQR_N_RECURSE(tspace, prodp, hsize, tspace + size);
mpi-genesis 315
mpi-genesis 316
mpi-genesis 317 MPN_COPY(prodp + hsize, prodp + size, hsize);
mpi-genesis 318 cy = mpihelp_add_n(prodp + size, prodp + size,
mpi-genesis 319 prodp + size + hsize, hsize);
mpi-genesis 320
mpi-genesis 321
mpi-genesis 322 cy -= mpihelp_sub_n (prodp + hsize, prodp + hsize, tspace, size);
mpi-genesis 323
mpi-genesis 324
mpi-genesis 325 * |________________||____U0 x U0_____|
mpi-genesis 326 * Read temporary operands from low part of PROD.
mpi-genesis 327 * Put result in low part of TSPACE using upper part of TSPACE
mpi-genesis 328 * as new TSPACE. */
mpi-genesis 329 MPN_SQR_N_RECURSE (tspace, up, hsize, tspace + size);
mpi-genesis 330
mpi-genesis 331
mpi-genesis 332 cy += mpihelp_add_n (prodp + hsize, prodp + hsize, tspace, size);
mpi-genesis 333 if( cy )
mpi-genesis 334 mpihelp_add_1(prodp + hsize + size, prodp + hsize + size,
mpi-genesis 335 hsize, cy);
mpi-genesis 336
mpi-genesis 337 MPN_COPY(prodp, tspace, hsize);
mpi-genesis 338 cy = mpihelp_add_n (prodp + hsize, prodp + hsize, tspace + hsize, hsize);
mpi-genesis 339 if( cy )
mpi-genesis 340 mpihelp_add_1 (prodp + size, prodp + size, size, 1);
mpi-genesis 341 }
mpi-genesis 342 }
mpi-genesis 343
mpi-genesis 344
mpi-genesis 345
mpi-genesis 346 void
mpi-genesis 347 mpihelp_mul_n( mpi_ptr_t prodp, mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size)
mpi-genesis 348 {
mpi-genesis 349 int secure;
mpi-genesis 350
mpi-genesis 351 if( up == vp ) {
mpi-genesis 352 if( size < KARATSUBA_THRESHOLD )
mpi-genesis 353 mpih_sqr_n_basecase( prodp, up, size );
mpi-genesis 354 else {
mpi-genesis 355 mpi_ptr_t tspace;
mpi-genesis 356 secure = m_is_secure( up );
mpi-genesis 357 tspace = mpi_alloc_limb_space( 2 * size, secure );
mpi-genesis 358 mpih_sqr_n( prodp, up, size, tspace );
mpi-genesis 359 mpi_free_limb_space( tspace );
mpi-genesis 360 }
mpi-genesis 361 }
mpi-genesis 362 else {
mpi-genesis 363 if( size < KARATSUBA_THRESHOLD )
mpi-genesis 364 mul_n_basecase( prodp, up, vp, size );
mpi-genesis 365 else {
mpi-genesis 366 mpi_ptr_t tspace;
mpi-genesis 367 secure = m_is_secure( up ) || m_is_secure( vp );
mpi-genesis 368 tspace = mpi_alloc_limb_space( 2 * size, secure );
mpi-genesis 369 mul_n (prodp, up, vp, size, tspace);
mpi-genesis 370 mpi_free_limb_space( tspace );
mpi-genesis 371 }
mpi-genesis 372 }
mpi-genesis 373 }
mpi-genesis 374
mpi-genesis 375
mpi-genesis 376
mpi-genesis 377 void
mpi-genesis 378 mpihelp_mul_karatsuba_case( mpi_ptr_t prodp,
mpi-genesis 379 mpi_ptr_t up, mpi_size_t usize,
mpi-genesis 380 mpi_ptr_t vp, mpi_size_t vsize,
mpi-genesis 381 struct karatsuba_ctx *ctx )
mpi-genesis 382 {
mpi-genesis 383 mpi_limb_t cy;
mpi-genesis 384
mpi-genesis 385 if( !ctx->tspace || ctx->tspace_size < vsize ) {
mpi-genesis 386 if( ctx->tspace )
mpi-genesis 387 mpi_free_limb_space( ctx->tspace );
mpi-genesis 388 ctx->tspace = mpi_alloc_limb_space( 2 * vsize,
mpi-genesis 389 m_is_secure( up ) || m_is_secure( vp ) );
mpi-genesis 390 ctx->tspace_size = vsize;
mpi-genesis 391 }
mpi-genesis 392
mpi-genesis 393 MPN_MUL_N_RECURSE( prodp, up, vp, vsize, ctx->tspace );
mpi-genesis 394
mpi-genesis 395 prodp += vsize;
mpi-genesis 396 up += vsize;
mpi-genesis 397 usize -= vsize;
mpi-genesis 398 if( usize >= vsize ) {
mpi-genesis 399 if( !ctx->tp || ctx->tp_size < vsize ) {
mpi-genesis 400 if( ctx->tp )
mpi-genesis 401 mpi_free_limb_space( ctx->tp );
mpi-genesis 402 ctx->tp = mpi_alloc_limb_space( 2 * vsize, m_is_secure( up )
mpi-genesis 403 || m_is_secure( vp ) );
mpi-genesis 404 ctx->tp_size = vsize;
mpi-genesis 405 }
mpi-genesis 406
mpi-genesis 407 do {
mpi-genesis 408 MPN_MUL_N_RECURSE( ctx->tp, up, vp, vsize, ctx->tspace );
mpi-genesis 409 cy = mpihelp_add_n( prodp, prodp, ctx->tp, vsize );
mpi-genesis 410 mpihelp_add_1( prodp + vsize, ctx->tp + vsize, vsize, cy );
mpi-genesis 411 prodp += vsize;
mpi-genesis 412 up += vsize;
mpi-genesis 413 usize -= vsize;
mpi-genesis 414 } while( usize >= vsize );
mpi-genesis 415 }
mpi-genesis 416
mpi-genesis 417 if( usize ) {
mpi-genesis 418 if( usize < KARATSUBA_THRESHOLD ) {
mpi-genesis 419 mpihelp_mul( ctx->tspace, vp, vsize, up, usize );
mpi-genesis 420 }
mpi-genesis 421 else {
mpi-genesis 422 if( !ctx->next ) {
mpi-genesis 423 ctx->next = xmalloc_clear( sizeof *ctx );
mpi-genesis 424 }
mpi-genesis 425 mpihelp_mul_karatsuba_case( ctx->tspace,
mpi-genesis 426 vp, vsize,
mpi-genesis 427 up, usize,
mpi-genesis 428 ctx->next );
mpi-genesis 429 }
mpi-genesis 430
mpi-genesis 431 cy = mpihelp_add_n( prodp, prodp, ctx->tspace, vsize);
mpi-genesis 432 mpihelp_add_1( prodp + vsize, ctx->tspace + vsize, usize, cy );
mpi-genesis 433 }
mpi-genesis 434 }
mpi-genesis 435
mpi-genesis 436
mpi-genesis 437 void
mpi-genesis 438 mpihelp_release_karatsuba_ctx( struct karatsuba_ctx *ctx )
mpi-genesis 439 {
mpi-genesis 440 struct karatsuba_ctx *ctx2;
mpi-genesis 441
mpi-genesis 442 if( ctx->tp )
mpi-genesis 443 mpi_free_limb_space( ctx->tp );
mpi-genesis 444 if( ctx->tspace )
mpi-genesis 445 mpi_free_limb_space( ctx->tspace );
mpi-genesis 446 for( ctx=ctx->next; ctx; ctx = ctx2 ) {
mpi-genesis 447 ctx2 = ctx->next;
mpi-genesis 448 if( ctx->tp )
mpi-genesis 449 mpi_free_limb_space( ctx->tp );
mpi-genesis 450 if( ctx->tspace )
mpi-genesis 451 mpi_free_limb_space( ctx->tspace );
mpi-genesis 452 xfree( ctx );
mpi-genesis 453 }
mpi-genesis 454 }
mpi-genesis 455
mpi-genesis 456
mpi-genesis 457 * and v (pointed to by VP, with VSIZE limbs), and store the result at
mpi-genesis 458 * PRODP. USIZE + VSIZE limbs are always stored, but if the input
mpi-genesis 459 * operands are normalized. Return the most significant limb of the
mpi-genesis 460 * result.
mpi-genesis 461 *
mpi-genesis 462 * NOTE: The space pointed to by PRODP is overwritten before finished
mpi-genesis 463 * with U and V, so overlap is an error.
mpi-genesis 464 *
mpi-genesis 465 * Argument constraints:
mpi-genesis 466 * 1. USIZE >= VSIZE.
mpi-genesis 467 * 2. PRODP != UP and PRODP != VP, i.e. the destination
mpi-genesis 468 * must be distinct from the multiplier and the multiplicand.
mpi-genesis 469 */
mpi-genesis 470
mpi-genesis 471 mpi_limb_t
mpi-genesis 472 mpihelp_mul( mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
mpi-genesis 473 mpi_ptr_t vp, mpi_size_t vsize)
mpi-genesis 474 {
mpi-genesis 475 mpi_ptr_t prod_endp = prodp + usize + vsize - 1;
mpi-genesis 476 mpi_limb_t cy;
mpi-genesis 477 struct karatsuba_ctx ctx;
mpi-genesis 478
mpi-genesis 479 if( vsize < KARATSUBA_THRESHOLD ) {
mpi-genesis 480 mpi_size_t i;
mpi-genesis 481 mpi_limb_t v_limb;
mpi-genesis 482
mpi-genesis 483 if( !vsize )
mpi-genesis 484 return 0;
mpi-genesis 485
mpi-genesis 486
mpi-genesis 487 * stored (not added) to PROD. We also avoid a loop for zeroing. */
mpi-genesis 488 v_limb = vp[0];
mpi-genesis 489 if( v_limb <= 1 ) {
mpi-genesis 490 if( v_limb == 1 )
mpi-genesis 491 MPN_COPY( prodp, up, usize );
mpi-genesis 492 else
mpi-genesis 493 MPN_ZERO( prodp, usize );
mpi-genesis 494 cy = 0;
mpi-genesis 495 }
mpi-genesis 496 else
mpi-genesis 497 cy = mpihelp_mul_1( prodp, up, usize, v_limb );
mpi-genesis 498
mpi-genesis 499 prodp[usize] = cy;
mpi-genesis 500 prodp++;
mpi-genesis 501
mpi-genesis 502
mpi-genesis 503 * U with one limb from V, and add it to PROD. */
mpi-genesis 504 for( i = 1; i < vsize; i++ ) {
mpi-genesis 505 v_limb = vp[i];
mpi-genesis 506 if( v_limb <= 1 ) {
mpi-genesis 507 cy = 0;
mpi-genesis 508 if( v_limb == 1 )
mpi-genesis 509 cy = mpihelp_add_n(prodp, prodp, up, usize);
mpi-genesis 510 }
mpi-genesis 511 else
mpi-genesis 512 cy = mpihelp_addmul_1(prodp, up, usize, v_limb);
mpi-genesis 513
mpi-genesis 514 prodp[usize] = cy;
mpi-genesis 515 prodp++;
mpi-genesis 516 }
mpi-genesis 517
mpi-genesis 518 return cy;
mpi-genesis 519 }
mpi-genesis 520
mpi-genesis 521 memset( &ctx, 0, sizeof ctx );
mpi-genesis 522 mpihelp_mul_karatsuba_case( prodp, up, usize, vp, vsize, &ctx );
mpi-genesis 523 mpihelp_release_karatsuba_ctx( &ctx );
mpi-genesis 524 return *prod_endp;
mpi-genesis 525 }
mpi-genesis 526
mpi-genesis 527