^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* mpi-bit.c - MPI bit level functions
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * This file is part of GnuPG.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * GnuPG is free software; you can redistribute it and/or modify
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * it under the terms of the GNU General Public License as published by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * the Free Software Foundation; either version 2 of the License, or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * (at your option) any later version.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * GnuPG is distributed in the hope that it will be useful,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * but WITHOUT ANY WARRANTY; without even the implied warranty of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * GNU General Public License for more details.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * You should have received a copy of the GNU General Public License
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * along with this program; if not, write to the Free Software
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #include "mpi-internal.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) #include "longlong.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #define A_LIMB_1 ((mpi_limb_t) 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * Sometimes we have MSL (most significant limbs) which are 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * this is for some reasons not good, so this function removes them.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) void mpi_normalize(MPI a)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) EXPORT_SYMBOL_GPL(mpi_normalize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) * Return the number of bits in A.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) unsigned mpi_get_nbits(MPI a)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) unsigned n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) mpi_normalize(a);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) if (a->nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) mpi_limb_t alimb = a->d[a->nlimbs - 1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) if (alimb)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) n = count_leading_zeros(alimb);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) n = BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) n = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) return n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) EXPORT_SYMBOL_GPL(mpi_get_nbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * Test whether bit N is set.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) int mpi_test_bit(MPI a, unsigned int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) unsigned int limbno, bitno;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) mpi_limb_t limb;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) limbno = n / BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) bitno = n % BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) if (limbno >= a->nlimbs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) return 0; /* too far left: this is a 0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) limb = a->d[limbno];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) EXPORT_SYMBOL_GPL(mpi_test_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) * Set bit N of A.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) void mpi_set_bit(MPI a, unsigned int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) unsigned int i, limbno, bitno;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) limbno = n / BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) bitno = n % BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) if (limbno >= a->nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) for (i = a->nlimbs; i < a->alloced; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) a->d[i] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) mpi_resize(a, limbno+1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) a->nlimbs = limbno+1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) a->d[limbno] |= (A_LIMB_1<<bitno);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) * Set bit N of A. and clear all bits above
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) void mpi_set_highbit(MPI a, unsigned int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) unsigned int i, limbno, bitno;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) limbno = n / BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) bitno = n % BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) if (limbno >= a->nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) for (i = a->nlimbs; i < a->alloced; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) a->d[i] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) mpi_resize(a, limbno+1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) a->nlimbs = limbno+1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) a->d[limbno] |= (A_LIMB_1<<bitno);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) a->d[limbno] &= ~(A_LIMB_1 << bitno);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) a->nlimbs = limbno+1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) EXPORT_SYMBOL_GPL(mpi_set_highbit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) * clear bit N of A and all bits above
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) void mpi_clear_highbit(MPI a, unsigned int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) unsigned int limbno, bitno;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) limbno = n / BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) bitno = n % BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) if (limbno >= a->nlimbs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) return; /* not allocated, therefore no need to clear bits :-) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) for ( ; bitno < BITS_PER_MPI_LIMB; bitno++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) a->d[limbno] &= ~(A_LIMB_1 << bitno);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) a->nlimbs = limbno+1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) * Clear bit N of A.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) void mpi_clear_bit(MPI a, unsigned int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) unsigned int limbno, bitno;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) limbno = n / BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) bitno = n % BITS_PER_MPI_LIMB;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) if (limbno >= a->nlimbs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) return; /* Don't need to clear this bit, it's far too left. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) a->d[limbno] &= ~(A_LIMB_1 << bitno);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) EXPORT_SYMBOL_GPL(mpi_clear_bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) * Shift A by COUNT limbs to the right
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) * This is used only within the MPI library
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) void mpi_rshift_limbs(MPI a, unsigned int count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) mpi_ptr_t ap = a->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) mpi_size_t n = a->nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) if (count >= n) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) a->nlimbs = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) for (i = 0; i < n - count; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) ap[i] = ap[i+count];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) ap[i] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) a->nlimbs -= count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) * Shift A by N bits to the right.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) void mpi_rshift(MPI x, MPI a, unsigned int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) mpi_size_t xsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) unsigned int nbits = (n%BITS_PER_MPI_LIMB);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) if (x == a) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) /* In-place operation. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) if (nlimbs >= x->nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) x->nlimbs = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) if (nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) for (i = 0; i < x->nlimbs - nlimbs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) x->d[i] = x->d[i+nlimbs];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) x->d[i] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) x->nlimbs -= nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) if (x->nlimbs && nbits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) } else if (nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) /* Copy and shift by more or equal bits than in a limb. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) xsize = a->nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) x->sign = a->sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) RESIZE_IF_NEEDED(x, xsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) x->nlimbs = xsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) for (i = 0; i < a->nlimbs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) x->d[i] = a->d[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) x->nlimbs = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) if (nlimbs >= x->nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) x->nlimbs = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) if (nlimbs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) for (i = 0; i < x->nlimbs - nlimbs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) x->d[i] = x->d[i+nlimbs];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) x->d[i] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) x->nlimbs -= nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) if (x->nlimbs && nbits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) /* Copy and shift by less than bits in a limb. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) xsize = a->nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) x->sign = a->sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) RESIZE_IF_NEEDED(x, xsize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) x->nlimbs = xsize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) if (xsize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) if (nbits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) /* The rshift helper function is not specified for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) * NBITS==0, thus we do a plain copy here.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) for (i = 0; i < x->nlimbs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) x->d[i] = a->d[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) MPN_NORMALIZE(x->d, x->nlimbs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) /****************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) * Shift A by COUNT limbs to the left
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) * This is used only within the MPI library
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) void mpi_lshift_limbs(MPI a, unsigned int count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) mpi_ptr_t ap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) int n = a->nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) if (!count || !n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) RESIZE_IF_NEEDED(a, n+count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) ap = a->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) for (i = n-1; i >= 0; i--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) ap[i+count] = ap[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) for (i = 0; i < count; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) ap[i] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) a->nlimbs += count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) * Shift A by N bits to the left.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) void mpi_lshift(MPI x, MPI a, unsigned int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) unsigned int nbits = (n%BITS_PER_MPI_LIMB);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) if (x == a && !n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) return; /* In-place shift with an amount of zero. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) if (x != a) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) /* Copy A to X. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) unsigned int alimbs = a->nlimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) int asign = a->sign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) mpi_ptr_t xp, ap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) RESIZE_IF_NEEDED(x, alimbs+nlimbs+1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) xp = x->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) ap = a->d;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) MPN_COPY(xp, ap, alimbs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) x->nlimbs = alimbs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) x->flags = a->flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) x->sign = asign;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) if (nlimbs && !nbits) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) /* Shift a full number of limbs. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) mpi_lshift_limbs(x, nlimbs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) } else if (n) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) /* We use a very dump approach: Shift left by the number of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) * limbs plus one and than fix it up by an rshift.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) mpi_lshift_limbs(x, nlimbs+1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) mpi_rshift(x, x, BITS_PER_MPI_LIMB - nbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) MPN_NORMALIZE(x->d, x->nlimbs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags