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 <linux/export.h>
 22
 23#include "mpi-internal.h"
 24#include "longlong.h"
 25
 26#define A_LIMB_1 ((mpi_limb_t) 1)
 27
 28/****************
 29 * Sometimes we have MSL (most significant limbs) which are 0;
 30 * this is for some reasons not good, so this function removes them.
 31 */
 32void mpi_normalize(MPI a)
 33{
 34	for (; a->nlimbs && !a->d[a->nlimbs - 1]; a->nlimbs--)
 35		;
 36}
 37
 38/****************
 39 * Return the number of bits in A.
 40 */
 41unsigned mpi_get_nbits(MPI a)
 42{
 43	unsigned n;
 44
 45	mpi_normalize(a);
 46
 47	if (a->nlimbs) {
 48		mpi_limb_t alimb = a->d[a->nlimbs - 1];
 49		if (alimb)
 50			n = count_leading_zeros(alimb);
 51		else
 52			n = BITS_PER_MPI_LIMB;
 53		n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
 54	} else
 55		n = 0;
 56	return n;
 57}
 58EXPORT_SYMBOL_GPL(mpi_get_nbits);
 59
 60/****************
 61 * Test whether bit N is set.
 62 */
 63int mpi_test_bit(MPI a, unsigned int n)
 64{
 65	unsigned int limbno, bitno;
 66	mpi_limb_t limb;
 67
 68	limbno = n / BITS_PER_MPI_LIMB;
 69	bitno  = n % BITS_PER_MPI_LIMB;
 70
 71	if (limbno >= a->nlimbs)
 72		return 0; /* too far left: this is a 0 */
 73	limb = a->d[limbno];
 74	return (limb & (A_LIMB_1 << bitno)) ? 1 : 0;
 75}
 76EXPORT_SYMBOL_GPL(mpi_test_bit);
 77
 78/****************
 79 * Set bit N of A.
 80 */
 81int mpi_set_bit(MPI a, unsigned int n)
 82{
 83	unsigned int i, limbno, bitno;
 84	int err;
 85
 86	limbno = n / BITS_PER_MPI_LIMB;
 87	bitno  = n % BITS_PER_MPI_LIMB;
 88
 89	if (limbno >= a->nlimbs) {
 90		for (i = a->nlimbs; i < a->alloced; i++)
 91			a->d[i] = 0;
 92		err = mpi_resize(a, limbno+1);
 93		if (err)
 94			return err;
 95		a->nlimbs = limbno+1;
 96	}
 97	a->d[limbno] |= (A_LIMB_1<<bitno);
 98	return 0;
 99}
100EXPORT_SYMBOL_GPL(mpi_set_bit);
101
102/*
103 * Shift A by N bits to the right.
104 */
105int mpi_rshift(MPI x, MPI a, unsigned int n)
106{
107	mpi_size_t xsize;
108	unsigned int i;
109	unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
110	unsigned int nbits = (n%BITS_PER_MPI_LIMB);
111	int err;
112
113	if (x == a) {
114		/* In-place operation.  */
115		if (nlimbs >= x->nlimbs) {
116			x->nlimbs = 0;
117			return 0;
118		}
119
120		if (nlimbs) {
121			for (i = 0; i < x->nlimbs - nlimbs; i++)
122				x->d[i] = x->d[i+nlimbs];
123			x->d[i] = 0;
124			x->nlimbs -= nlimbs;
125		}
126		if (x->nlimbs && nbits)
127			mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
128	} else if (nlimbs) {
129		/* Copy and shift by more or equal bits than in a limb. */
130		xsize = a->nlimbs;
131		x->sign = a->sign;
132		err = RESIZE_IF_NEEDED(x, xsize);
133		if (err)
134			return err;
135		x->nlimbs = xsize;
136		for (i = 0; i < a->nlimbs; i++)
137			x->d[i] = a->d[i];
138		x->nlimbs = i;
139
140		if (nlimbs >= x->nlimbs) {
141			x->nlimbs = 0;
142			return 0;
143		}
144
145		for (i = 0; i < x->nlimbs - nlimbs; i++)
146			x->d[i] = x->d[i+nlimbs];
147		x->d[i] = 0;
148		x->nlimbs -= nlimbs;
149
150		if (x->nlimbs && nbits)
151			mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
152	} else {
153		/* Copy and shift by less than bits in a limb.  */
154		xsize = a->nlimbs;
155		x->sign = a->sign;
156		err = RESIZE_IF_NEEDED(x, xsize);
157		if (err)
158			return err;
159		x->nlimbs = xsize;
160
161		if (xsize) {
162			if (nbits)
163				mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
164			else {
165				/* The rshift helper function is not specified for
166				 * NBITS==0, thus we do a plain copy here.
167				 */
168				for (i = 0; i < x->nlimbs; i++)
169					x->d[i] = a->d[i];
170			}
171		}
172	}
173	MPN_NORMALIZE(x->d, x->nlimbs);
174
175	return 0;
176}
177EXPORT_SYMBOL_GPL(mpi_rshift);