^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-or-later
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /* mpi-pow.c - MPI functions
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Copyright (C) 1994, 1996, 1998, 2000 Free Software Foundation, Inc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * This file is part of GnuPG.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * Note: This code is heavily based on the GNU MP Library.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * Actually it's the same code with only minor changes in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * way the data is stored; this is to support the abstraction
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * of an optional secure memory allocation which may be used
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * to avoid revealing of sensitive data due to paging etc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * The GNU MP Library itself is published under the LGPL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * however I decided to publish this code under the plain GPL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) #include <linux/sched.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #include <linux/string.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) #include "mpi-internal.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) #include "longlong.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * RES = BASE ^ EXP mod MOD
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) mpi_ptr_t mp_marker = NULL, bp_marker = NULL, ep_marker = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) struct karatsuba_ctx karactx = {};
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) mpi_ptr_t xp_marker = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) mpi_ptr_t tspace = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) mpi_ptr_t rp, ep, mp, bp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) mpi_size_t esize, msize, bsize, rsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) int msign, bsign, rsign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) mpi_size_t size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) int mod_shift_cnt;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) int negative_result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) int assign_rp = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) mpi_size_t tsize = 0; /* to avoid compiler warning */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) /* fixme: we should check that the warning is void */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) int rc = -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) esize = exp->nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) msize = mod->nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) size = 2 * msize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) msign = mod->sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) rp = res->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) ep = exp->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) if (!msize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) if (!esize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) /* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) * depending on if MOD equals 1. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) if (res->nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) if (mpi_resize(res, 1) < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) rp = res->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) rp[0] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) res->sign = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) goto leave;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) /* Normalize MOD (i.e. make its most significant bit set) as required by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) * mpn_divrem. This will make the intermediate values in the calculation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) * slightly larger, but the correct result is obtained after a final
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) * reduction using the original MOD value. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) mp = mp_marker = mpi_alloc_limb_space(msize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) if (!mp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) if (mod_shift_cnt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) MPN_COPY(mp, mod->d, msize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) bsize = base->nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) bsign = base->sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) if (bsize > msize) { /* The base is larger than the module. Reduce it. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) /* Allocate (BSIZE + 1) with space for remainder and quotient.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) * (The quotient is (bsize - msize + 1) limbs.) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) bp = bp_marker = mpi_alloc_limb_space(bsize + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) if (!bp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) MPN_COPY(bp, base->d, bsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) /* We don't care about the quotient, store it above the remainder,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) * at BP + MSIZE. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) mpihelp_divrem(bp + msize, 0, bp, bsize, mp, msize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) bsize = msize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) /* Canonicalize the base, since we are going to multiply with it
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) * quite a few times. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) MPN_NORMALIZE(bp, bsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) bp = base->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) if (!bsize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) res->nlimbs = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) res->sign = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) goto leave;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) if (res->alloced < size) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) /* We have to allocate more space for RES. If any of the input
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) * parameters are identical to RES, defer deallocation of the old
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) * space. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) if (rp == ep || rp == mp || rp == bp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) rp = mpi_alloc_limb_space(size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) if (!rp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) assign_rp = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) if (mpi_resize(res, size) < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) rp = res->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) } else { /* Make BASE, EXP and MOD not overlap with RES. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) if (rp == bp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) /* RES and BASE are identical. Allocate temp. space for BASE. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) BUG_ON(bp_marker);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) bp = bp_marker = mpi_alloc_limb_space(bsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) if (!bp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) MPN_COPY(bp, rp, bsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) if (rp == ep) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) /* RES and EXP are identical. Allocate temp. space for EXP. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) ep = ep_marker = mpi_alloc_limb_space(esize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) if (!ep)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) MPN_COPY(ep, rp, esize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) if (rp == mp) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) /* RES and MOD are identical. Allocate temporary space for MOD. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) BUG_ON(mp_marker);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) mp = mp_marker = mpi_alloc_limb_space(msize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) if (!mp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) MPN_COPY(mp, rp, msize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) MPN_COPY(rp, bp, bsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) rsize = bsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) rsign = bsign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) mpi_size_t i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) mpi_ptr_t xp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) int c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) mpi_limb_t e;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) mpi_limb_t carry_limb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) xp = xp_marker = mpi_alloc_limb_space(2 * (msize + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) if (!xp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) negative_result = (ep[0] & 1) && base->sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) i = esize - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) e = ep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) c = count_leading_zeros(e);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) e = (e << c) << 1; /* shift the exp bits to the left, lose msb */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) c = BITS_PER_MPI_LIMB - 1 - c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) /* Main loop.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) * Make the result be pointed to alternately by XP and RP. This
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) * helps us avoid block copying, which would otherwise be necessary
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) * with the overlap restrictions of mpihelp_divmod. With 50% probability
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) * the result after this loop will be in the area originally pointed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) * by RP (==RES->d), and with 50% probability in the area originally
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) * pointed to by XP.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) while (c) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) mpi_ptr_t tp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) mpi_size_t xsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) /*if (mpihelp_mul_n(xp, rp, rp, rsize) < 0) goto enomem */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) if (rsize < KARATSUBA_THRESHOLD)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) mpih_sqr_n_basecase(xp, rp, rsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) if (!tspace) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) tsize = 2 * rsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) tspace =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) mpi_alloc_limb_space(tsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) if (!tspace)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) } else if (tsize < (2 * rsize)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) mpi_free_limb_space(tspace);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) tsize = 2 * rsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) tspace =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) mpi_alloc_limb_space(tsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) if (!tspace)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) mpih_sqr_n(xp, rp, rsize, tspace);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) xsize = 2 * rsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) if (xsize > msize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) mpihelp_divrem(xp + msize, 0, xp, xsize,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) mp, msize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) xsize = msize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) tp = rp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) rp = xp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) xp = tp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) rsize = xsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) if ((mpi_limb_signed_t) e < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) /*mpihelp_mul( xp, rp, rsize, bp, bsize ); */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) if (bsize < KARATSUBA_THRESHOLD) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) mpi_limb_t tmp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) if (mpihelp_mul
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) (xp, rp, rsize, bp, bsize,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) &tmp) < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) if (mpihelp_mul_karatsuba_case
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) (xp, rp, rsize, bp, bsize,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) &karactx) < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) goto enomem;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) xsize = rsize + bsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) if (xsize > msize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) mpihelp_divrem(xp + msize, 0,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) xp, xsize, mp,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) msize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) xsize = msize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) tp = rp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) rp = xp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) xp = tp;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) rsize = xsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) e <<= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) c--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) cond_resched();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) i--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) if (i < 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) e = ep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) c = BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) /* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) * steps. Adjust the result by reducing it with the original MOD.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) * Also make sure the result is put in RES->d (where it already
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) * might be, see above).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) if (mod_shift_cnt) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) carry_limb =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) mpihelp_lshift(res->d, rp, rsize, mod_shift_cnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) rp = res->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) if (carry_limb) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) rp[rsize] = carry_limb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) rsize++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) MPN_COPY(res->d, rp, rsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) rp = res->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) if (rsize >= msize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) rsize = msize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) /* Remove any leading zero words from the result. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) if (mod_shift_cnt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) mpihelp_rshift(rp, rp, rsize, mod_shift_cnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) MPN_NORMALIZE(rp, rsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) if (negative_result && rsize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) if (mod_shift_cnt)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) mpihelp_rshift(mp, mp, msize, mod_shift_cnt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) mpihelp_sub(rp, mp, msize, rp, rsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) rsize = msize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) rsign = msign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) MPN_NORMALIZE(rp, rsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) res->nlimbs = rsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) res->sign = rsign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) leave:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) rc = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) enomem:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) mpihelp_release_karatsuba_ctx(&karactx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) if (assign_rp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) mpi_assign_limb_space(res, rp, size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) if (mp_marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) mpi_free_limb_space(mp_marker);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) if (bp_marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) mpi_free_limb_space(bp_marker);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) if (ep_marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) mpi_free_limb_space(ep_marker);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) if (xp_marker)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) mpi_free_limb_space(xp_marker);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) if (tspace)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) mpi_free_limb_space(tspace);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) return rc;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) EXPORT_SYMBOL_GPL(mpi_powm);
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags