lib/mpi/mpi-bit.c

0001 /* mpi-bit.c  -  MPI bit level functions
0002  * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
0003  *
0004  * This file is part of GnuPG.
0005  *
0006  * GnuPG is free software; you can redistribute it and/or modify
0007  * it under the terms of the GNU General Public License as published by
0008  * the Free Software Foundation; either version 2 of the License, or
0009  * (at your option) any later version.
0010  *
0011  * GnuPG is distributed in the hope that it will be useful,
0012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0014  * GNU General Public License for more details.
0015  *
0016  * You should have received a copy of the GNU General Public License
0017  * along with this program; if not, write to the Free Software
0018  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
0019  */
0020
0021 #include "mpi-internal.h"
0022 #include "longlong.h"
0023
0024 #define A_LIMB_1 ((mpi_limb_t) 1)
0025
0026 /****************
0027  * Sometimes we have MSL (most significant limbs) which are 0;
0028  * this is for some reasons not good, so this function removes them.
0029  */
0030 void mpi_normalize(MPI a)
0031 {
0032     for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
0033         ;
0034 }
0035 EXPORT_SYMBOL_GPL(mpi_normalize);
0036
0037 /****************
0038  * Return the number of bits in A.
0039  */
0040 unsigned mpi_get_nbits(MPI a)
0041 {
0042     unsigned n;
0043
0044     mpi_normalize(a);
0045
0046     if (a->nlimbs) {
0047         mpi_limb_t alimb = a->d[a->nlimbs - 1];
0048         if (alimb)
0049             n = count_leading_zeros(alimb);
0050         else
0051             n = BITS_PER_MPI_LIMB;
0052         n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
0053     } else
0054         n = 0;
0055     return n;
0056 }
0057 EXPORT_SYMBOL_GPL(mpi_get_nbits);
0058
0059 /****************
0060  * Test whether bit N is set.
0061  */
0062 int mpi_test_bit(MPI a, unsigned int n)
0063 {
0064     unsigned int limbno, bitno;
0065     mpi_limb_t limb;
0066
0067     limbno = n / BITS_PER_MPI_LIMB;
0068     bitno  = n % BITS_PER_MPI_LIMB;
0069
0070     if (limbno >= a->nlimbs)
0071         return 0; /* too far left: this is a 0 */
0072     limb = a->d[limbno];
0073     return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
0074 }
0075 EXPORT_SYMBOL_GPL(mpi_test_bit);
0076
0077 /****************
0078  * Set bit N of A.
0079  */
0080 void mpi_set_bit(MPI a, unsigned int n)
0081 {
0082     unsigned int i, limbno, bitno;
0083
0084     limbno = n / BITS_PER_MPI_LIMB;
0085     bitno  = n % BITS_PER_MPI_LIMB;
0086
0087     if (limbno >= a->nlimbs) {
0088         for (i = a->nlimbs; i < a->alloced; i++)
0089             a->d[i] = 0;
0090         mpi_resize(a, limbno+1);
0091         a->nlimbs = limbno+1;
0092     }
0093     a->d[limbno] |= (A_LIMB_1<<bitno);
0094 }
0095
0096 /****************
0097  * Set bit N of A. and clear all bits above
0098  */
0099 void mpi_set_highbit(MPI a, unsigned int n)
0100 {
0101     unsigned int i, limbno, bitno;
0102
0103     limbno = n / BITS_PER_MPI_LIMB;
0104     bitno  = n % BITS_PER_MPI_LIMB;
0105
0106     if (limbno >= a->nlimbs) {
0107         for (i = a->nlimbs; i < a->alloced; i++)
0108             a->d[i] = 0;
0109         mpi_resize(a, limbno+1);
0110         a->nlimbs = limbno+1;
0111     }
0112     a->d[limbno] |= (A_LIMB_1<<bitno);
0113     for (bitno++; bitno < BITS_PER_MPI_LIMB; bitno++)
0114         a->d[limbno] &= ~(A_LIMB_1 << bitno);
0115     a->nlimbs = limbno+1;
0116 }
0117 EXPORT_SYMBOL_GPL(mpi_set_highbit);
0118
0119 /****************
0120  * clear bit N of A and all bits above
0121  */
0122 void mpi_clear_highbit(MPI a, unsigned int n)
0123 {
0124     unsigned int limbno, bitno;
0125
0126     limbno = n / BITS_PER_MPI_LIMB;
0127     bitno  = n % BITS_PER_MPI_LIMB;
0128
0129     if (limbno >= a->nlimbs)
0130         return; /* not allocated, therefore no need to clear bits :-) */
0131
0132     for ( ; bitno < BITS_PER_MPI_LIMB; bitno++)
0133         a->d[limbno] &= ~(A_LIMB_1 << bitno);
0134     a->nlimbs = limbno+1;
0135 }
0136
0137 /****************
0138  * Clear bit N of A.
0139  */
0140 void mpi_clear_bit(MPI a, unsigned int n)
0141 {
0142     unsigned int limbno, bitno;
0143
0144     limbno = n / BITS_PER_MPI_LIMB;
0145     bitno  = n % BITS_PER_MPI_LIMB;
0146
0147     if (limbno >= a->nlimbs)
0148         return; /* Don't need to clear this bit, it's far too left.  */
0149     a->d[limbno] &= ~(A_LIMB_1 << bitno);
0150 }
0151 EXPORT_SYMBOL_GPL(mpi_clear_bit);
0152
0153
0154 /****************
0155  * Shift A by COUNT limbs to the right
0156  * This is used only within the MPI library
0157  */
0158 void mpi_rshift_limbs(MPI a, unsigned int count)
0159 {
0160     mpi_ptr_t ap = a->d;
0161     mpi_size_t n = a->nlimbs;
0162     unsigned int i;
0163
0164     if (count >= n) {
0165         a->nlimbs = 0;
0166         return;
0167     }
0168
0169     for (i = 0; i < n - count; i++)
0170         ap[i] = ap[i+count];
0171     ap[i] = 0;
0172     a->nlimbs -= count;
0173 }
0174
0175 /*
0176  * Shift A by N bits to the right.
0177  */
0178 void mpi_rshift(MPI x, MPI a, unsigned int n)
0179 {
0180     mpi_size_t xsize;
0181     unsigned int i;
0182     unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
0183     unsigned int nbits = (n%BITS_PER_MPI_LIMB);
0184
0185     if (x == a) {
0186         /* In-place operation.  */
0187         if (nlimbs >= x->nlimbs) {
0188             x->nlimbs = 0;
0189             return;
0190         }
0191
0192         if (nlimbs) {
0193             for (i = 0; i < x->nlimbs - nlimbs; i++)
0194                 x->d[i] = x->d[i+nlimbs];
0195             x->d[i] = 0;
0196             x->nlimbs -= nlimbs;
0197         }
0198         if (x->nlimbs && nbits)
0199             mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
0200     } else if (nlimbs) {
0201         /* Copy and shift by more or equal bits than in a limb. */
0202         xsize = a->nlimbs;
0203         x->sign = a->sign;
0204         RESIZE_IF_NEEDED(x, xsize);
0205         x->nlimbs = xsize;
0206         for (i = 0; i < a->nlimbs; i++)
0207             x->d[i] = a->d[i];
0208         x->nlimbs = i;
0209
0210         if (nlimbs >= x->nlimbs) {
0211             x->nlimbs = 0;
0212             return;
0213         }
0214
0215         if (nlimbs) {
0216             for (i = 0; i < x->nlimbs - nlimbs; i++)
0217                 x->d[i] = x->d[i+nlimbs];
0218             x->d[i] = 0;
0219             x->nlimbs -= nlimbs;
0220         }
0221
0222         if (x->nlimbs && nbits)
0223             mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
0224     } else {
0225         /* Copy and shift by less than bits in a limb.  */
0226         xsize = a->nlimbs;
0227         x->sign = a->sign;
0228         RESIZE_IF_NEEDED(x, xsize);
0229         x->nlimbs = xsize;
0230
0231         if (xsize) {
0232             if (nbits)
0233                 mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
0234             else {
0235                 /* The rshift helper function is not specified for
0236                  * NBITS==0, thus we do a plain copy here.
0237                  */
0238                 for (i = 0; i < x->nlimbs; i++)
0239                     x->d[i] = a->d[i];
0240             }
0241         }
0242     }
0243     MPN_NORMALIZE(x->d, x->nlimbs);
0244 }
0245 EXPORT_SYMBOL_GPL(mpi_rshift);
0246
0247 /****************
0248  * Shift A by COUNT limbs to the left
0249  * This is used only within the MPI library
0250  */
0251 void mpi_lshift_limbs(MPI a, unsigned int count)
0252 {
0253     mpi_ptr_t ap;
0254     int n = a->nlimbs;
0255     int i;
0256
0257     if (!count || !n)
0258         return;
0259
0260     RESIZE_IF_NEEDED(a, n+count);
0261
0262     ap = a->d;
0263     for (i = n-1; i >= 0; i--)
0264         ap[i+count] = ap[i];
0265     for (i = 0; i < count; i++)
0266         ap[i] = 0;
0267     a->nlimbs += count;
0268 }
0269
0270 /*
0271  * Shift A by N bits to the left.
0272  */
0273 void mpi_lshift(MPI x, MPI a, unsigned int n)
0274 {
0275     unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
0276     unsigned int nbits = (n%BITS_PER_MPI_LIMB);
0277
0278     if (x == a && !n)
0279         return;  /* In-place shift with an amount of zero.  */
0280
0281     if (x != a) {
0282         /* Copy A to X.  */
0283         unsigned int alimbs = a->nlimbs;
0284         int asign = a->sign;
0285         mpi_ptr_t xp, ap;
0286
0287         RESIZE_IF_NEEDED(x, alimbs+nlimbs+1);
0288         xp = x->d;
0289         ap = a->d;
0290         MPN_COPY(xp, ap, alimbs);
0291         x->nlimbs = alimbs;
0292         x->flags = a->flags;
0293         x->sign = asign;
0294     }
0295
0296     if (nlimbs && !nbits) {
0297         /* Shift a full number of limbs.  */
0298         mpi_lshift_limbs(x, nlimbs);
0299     } else if (n) {
0300         /* We use a very dump approach: Shift left by the number of
0301          * limbs plus one and than fix it up by an rshift.
0302          */
0303         mpi_lshift_limbs(x, nlimbs+1);
0304         mpi_rshift(x, x, BITS_PER_MPI_LIMB - nbits);
0305     }
0306
0307     MPN_NORMALIZE(x->d, x->nlimbs);
0308 }