LXR linux/lib/mpi/mpi-bit.c

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