Tree @b7f589b (Download .tar.gz)
- ..
- bn_error.c
- bn_fast_mp_invmod.c
- bn_fast_mp_montgomery_reduce.c
- bn_fast_s_mp_mul_digs.c
- bn_fast_s_mp_mul_high_digs.c
- bn_fast_s_mp_sqr.c
- bn_mp_2expt.c
- bn_mp_abs.c
- bn_mp_add.c
- bn_mp_add_d.c
- bn_mp_addmod.c
- bn_mp_and.c
- bn_mp_clamp.c
- bn_mp_clear.c
- bn_mp_clear_multi.c
- bn_mp_cmp.c
- bn_mp_cmp_d.c
- bn_mp_cmp_mag.c
- bn_mp_cnt_lsb.c
- bn_mp_complement.c
- bn_mp_copy.c
- bn_mp_count_bits.c
- bn_mp_div.c
- bn_mp_div_2.c
- bn_mp_div_2d.c
- bn_mp_div_3.c
- bn_mp_div_d.c
- bn_mp_dr_is_modulus.c
- bn_mp_dr_reduce.c
- bn_mp_dr_setup.c
- bn_mp_exch.c
- bn_mp_export.c
- bn_mp_expt_d.c
- bn_mp_expt_d_ex.c
- bn_mp_exptmod.c
- bn_mp_exptmod_fast.c
- bn_mp_exteuclid.c
- bn_mp_fread.c
- bn_mp_fwrite.c
- bn_mp_gcd.c
- bn_mp_get_bit.c
- bn_mp_get_int.c
- bn_mp_get_long.c
- bn_mp_grow.c
- bn_mp_import.c
- bn_mp_init.c
- bn_mp_init_copy.c
- bn_mp_init_multi.c
- bn_mp_init_set.c
- bn_mp_init_set_int.c
- bn_mp_init_size.c
- bn_mp_invmod.c
- bn_mp_invmod_slow.c
- bn_mp_is_square.c
- bn_mp_jacobi.c
- bn_mp_karatsuba_mul.c
- bn_mp_karatsuba_sqr.c
- bn_mp_kronecker.c
- bn_mp_lcm.c
- bn_mp_lshd.c
- bn_mp_mod.c
- bn_mp_mod_2d.c
- bn_mp_mod_d.c
- bn_mp_montgomery_calc_normalization.c
- bn_mp_montgomery_reduce.c
- bn_mp_montgomery_setup.c
- bn_mp_mul.c
- bn_mp_mul_2.c
- bn_mp_mul_2d.c
- bn_mp_mul_d.c
- bn_mp_mulmod.c
- bn_mp_n_root.c
- bn_mp_n_root_ex.c
- bn_mp_neg.c
- bn_mp_or.c
- bn_mp_prime_fermat.c
- bn_mp_prime_frobenius_underwood.c
- bn_mp_prime_is_divisible.c
- bn_mp_prime_is_prime.c
- bn_mp_prime_miller_rabin.c
- bn_mp_prime_next_prime.c
- bn_mp_prime_rabin_miller_trials.c
- bn_mp_prime_random_ex.c
- bn_mp_prime_strong_lucas_selfridge.c
- bn_mp_radix_size.c
- bn_mp_radix_smap.c
- bn_mp_rand.c
- bn_mp_read_radix.c
- bn_mp_read_signed_bin.c
- bn_mp_read_unsigned_bin.c
- bn_mp_reduce.c
- bn_mp_reduce_2k.c
- bn_mp_reduce_2k_l.c
- bn_mp_reduce_2k_setup.c
- bn_mp_reduce_2k_setup_l.c
- bn_mp_reduce_is_2k.c
- bn_mp_reduce_is_2k_l.c
- bn_mp_reduce_setup.c
- bn_mp_rshd.c
- bn_mp_set.c
- bn_mp_set_int.c
- bn_mp_set_long.c
- bn_mp_shrink.c
- bn_mp_signed_bin_size.c
- bn_mp_sqr.c
- bn_mp_sqrmod.c
- bn_mp_sqrt.c
- bn_mp_sqrtmod_prime.c
- bn_mp_sub.c
- bn_mp_sub_d.c
- bn_mp_submod.c
- bn_mp_tc_and.c
- bn_mp_tc_div_2d.c
- bn_mp_tc_or.c
- bn_mp_tc_xor.c
- bn_mp_to_signed_bin.c
- bn_mp_to_signed_bin_n.c
- bn_mp_to_unsigned_bin.c
- bn_mp_to_unsigned_bin_n.c
- bn_mp_toom_mul.c
- bn_mp_toom_sqr.c
- bn_mp_toradix.c
- bn_mp_toradix_n.c
- bn_mp_unsigned_bin_size.c
- bn_mp_xor.c
- bn_mp_zero.c
- bn_prime_tab.c
- bn_reverse.c
- bn_s_mp_add.c
- bn_s_mp_exptmod.c
- bn_s_mp_mul_digs.c
- bn_s_mp_mul_high_digs.c
- bn_s_mp_sqr.c
- bn_s_mp_sub.c
- bncore.c
- tommath.h
- tommath_class.h
- tommath_private.h
- tommath_superclass.h
bn_fast_s_mp_mul_digs.c @b7f589b — raw · history · blame
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #include "tommath_private.h" #ifdef BN_FAST_S_MP_MUL_DIGS_C /* LibTomMath, multiple-precision integer library -- Tom St Denis * * LibTomMath is a library that provides multiple-precision * integer arithmetic as well as number theoretic functionality. * * The library was designed directly after the MPI library by * Michael Fromberger but has been written from scratch with * additional optimizations in place. * * SPDX-License-Identifier: Unlicense */ /* Fast (comba) multiplier * * This is the fast column-array [comba] multiplier. It is * designed to compute the columns of the product first * then handle the carries afterwards. This has the effect * of making the nested loops that compute the columns very * simple and schedulable on super-scalar processors. * * This has been modified to produce a variable number of * digits of output so if say only a half-product is required * you don't have to compute the upper half (a feature * required for fast Barrett reduction). * * Based on Algorithm 14.12 on pp.595 of HAC. * */ int fast_s_mp_mul_digs(const mp_int *a, const mp_int *b, mp_int *c, int digs) { int olduse, res, pa, ix, iz; mp_digit W[MP_WARRAY]; mp_word _W; /* grow the destination as required */ if (c->alloc < digs) { if ((res = mp_grow(c, digs)) != MP_OKAY) { return res; } } /* number of output digits to produce */ pa = MIN(digs, a->used + b->used); /* clear the carry */ _W = 0; for (ix = 0; ix < pa; ix++) { int tx, ty; int iy; mp_digit *tmpx, *tmpy; /* get offsets into the two bignums */ ty = MIN(b->used-1, ix); tx = ix - ty; /* setup temp aliases */ tmpx = a->dp + tx; tmpy = b->dp + ty; /* this is the number of times the loop will iterrate, essentially while (tx++ < a->used && ty-- >= 0) { ... } */ iy = MIN(a->used-tx, ty+1); /* execute loop */ for (iz = 0; iz < iy; ++iz) { _W += (mp_word)*tmpx++ * (mp_word)*tmpy--; } /* store term */ W[ix] = (mp_digit)_W & MP_MASK; /* make next carry */ _W = _W >> (mp_word)DIGIT_BIT; } /* setup dest */ olduse = c->used; c->used = pa; { mp_digit *tmpc; tmpc = c->dp; for (ix = 0; ix < pa; ix++) { /* now extract the previous digit [below the carry] */ *tmpc++ = W[ix]; } /* clear unused digits [that existed in the old copy of c] */ for (; ix < olduse; ix++) { *tmpc++ = 0; } } mp_clamp(c); return MP_OKAY; } #endif /* ref: $Format:%D$ */ /* git commit: $Format:%H$ */ /* commit time: $Format:%ai$ */ |