175 lines · c
1/* mpi-bit.c - MPI bit level functions2 * Copyright (C) 1998, 1999 Free Software Foundation, Inc.3 *4 * This file is part of GnuPG.5 *6 * GnuPG is free software; you can redistribute it and/or modify7 * it under the terms of the GNU General Public License as published by8 * the Free Software Foundation; either version 2 of the License, or9 * (at your option) any later version.10 *11 * GnuPG is distributed in the hope that it will be useful,12 * but WITHOUT ANY WARRANTY; without even the implied warranty of13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the14 * GNU General Public License for more details.15 *16 * You should have received a copy of the GNU General Public License17 * along with this program; if not, write to the Free Software18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA19 */20 21#include "mpi-internal.h"22#include "longlong.h"23 24#define A_LIMB_1 ((mpi_limb_t) 1)25 26/****************27 * Sometimes we have MSL (most significant limbs) which are 0;28 * this is for some reasons not good, so this function removes them.29 */30void mpi_normalize(MPI a)31{32 for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)33 ;34}35 36/****************37 * Return the number of bits in A.38 */39unsigned mpi_get_nbits(MPI a)40{41 unsigned n;42 43 mpi_normalize(a);44 45 if (a->nlimbs) {46 mpi_limb_t alimb = a->d[a->nlimbs - 1];47 if (alimb)48 n = count_leading_zeros(alimb);49 else50 n = BITS_PER_MPI_LIMB;51 n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;52 } else53 n = 0;54 return n;55}56EXPORT_SYMBOL_GPL(mpi_get_nbits);57 58/****************59 * Test whether bit N is set.60 */61int mpi_test_bit(MPI a, unsigned int n)62{63 unsigned int limbno, bitno;64 mpi_limb_t limb;65 66 limbno = n / BITS_PER_MPI_LIMB;67 bitno = n % BITS_PER_MPI_LIMB;68 69 if (limbno >= a->nlimbs)70 return 0; /* too far left: this is a 0 */71 limb = a->d[limbno];72 return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;73}74EXPORT_SYMBOL_GPL(mpi_test_bit);75 76/****************77 * Set bit N of A.78 */79int mpi_set_bit(MPI a, unsigned int n)80{81 unsigned int i, limbno, bitno;82 int err;83 84 limbno = n / BITS_PER_MPI_LIMB;85 bitno = n % BITS_PER_MPI_LIMB;86 87 if (limbno >= a->nlimbs) {88 for (i = a->nlimbs; i < a->alloced; i++)89 a->d[i] = 0;90 err = mpi_resize(a, limbno+1);91 if (err)92 return err;93 a->nlimbs = limbno+1;94 }95 a->d[limbno] |= (A_LIMB_1<<bitno);96 return 0;97}98 99/*100 * Shift A by N bits to the right.101 */102int mpi_rshift(MPI x, MPI a, unsigned int n)103{104 mpi_size_t xsize;105 unsigned int i;106 unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);107 unsigned int nbits = (n%BITS_PER_MPI_LIMB);108 int err;109 110 if (x == a) {111 /* In-place operation. */112 if (nlimbs >= x->nlimbs) {113 x->nlimbs = 0;114 return 0;115 }116 117 if (nlimbs) {118 for (i = 0; i < x->nlimbs - nlimbs; i++)119 x->d[i] = x->d[i+nlimbs];120 x->d[i] = 0;121 x->nlimbs -= nlimbs;122 }123 if (x->nlimbs && nbits)124 mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);125 } else if (nlimbs) {126 /* Copy and shift by more or equal bits than in a limb. */127 xsize = a->nlimbs;128 x->sign = a->sign;129 err = RESIZE_IF_NEEDED(x, xsize);130 if (err)131 return err;132 x->nlimbs = xsize;133 for (i = 0; i < a->nlimbs; i++)134 x->d[i] = a->d[i];135 x->nlimbs = i;136 137 if (nlimbs >= x->nlimbs) {138 x->nlimbs = 0;139 return 0;140 }141 142 for (i = 0; i < x->nlimbs - nlimbs; i++)143 x->d[i] = x->d[i+nlimbs];144 x->d[i] = 0;145 x->nlimbs -= nlimbs;146 147 if (x->nlimbs && nbits)148 mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);149 } else {150 /* Copy and shift by less than bits in a limb. */151 xsize = a->nlimbs;152 x->sign = a->sign;153 err = RESIZE_IF_NEEDED(x, xsize);154 if (err)155 return err;156 x->nlimbs = xsize;157 158 if (xsize) {159 if (nbits)160 mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);161 else {162 /* The rshift helper function is not specified for163 * NBITS==0, thus we do a plain copy here.164 */165 for (i = 0; i < x->nlimbs; i++)166 x->d[i] = a->d[i];167 }168 }169 }170 MPN_NORMALIZE(x->d, x->nlimbs);171 172 return 0;173}174EXPORT_SYMBOL_GPL(mpi_rshift);175