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}
 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		else
 50			n = BITS_PER_MPI_LIMB;
 51		n = BITS_PER_MPI_LIMB - n + (a->nlimbs - 1) * BITS_PER_MPI_LIMB;
 52	} else
 53		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}
 98EXPORT_SYMBOL_GPL(mpi_set_bit);
 99
100/*
101 * Shift A by N bits to the right.
102 */
103int mpi_rshift(MPI x, MPI a, unsigned int n)
104{
105	mpi_size_t xsize;
106	unsigned int i;
107	unsigned int nlimbs = (n/BITS_PER_MPI_LIMB);
108	unsigned int nbits = (n%BITS_PER_MPI_LIMB);
109	int err;
110
111	if (x == a) {
112		/* In-place operation.  */
113		if (nlimbs >= x->nlimbs) {
114			x->nlimbs = 0;
115			return 0;
116		}
117
118		if (nlimbs) {
119			for (i = 0; i < x->nlimbs - nlimbs; i++)
120				x->d[i] = x->d[i+nlimbs];
121			x->d[i] = 0;
122			x->nlimbs -= nlimbs;
123		}
124		if (x->nlimbs && nbits)
125			mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
126	} else if (nlimbs) {
127		/* Copy and shift by more or equal bits than in a limb. */
128		xsize = a->nlimbs;
129		x->sign = a->sign;
130		err = RESIZE_IF_NEEDED(x, xsize);
131		if (err)
132			return err;
133		x->nlimbs = xsize;
134		for (i = 0; i < a->nlimbs; i++)
135			x->d[i] = a->d[i];
136		x->nlimbs = i;
137
138		if (nlimbs >= x->nlimbs) {
139			x->nlimbs = 0;
140			return 0;
141		}
142
143		for (i = 0; i < x->nlimbs - nlimbs; i++)
144			x->d[i] = x->d[i+nlimbs];
145		x->d[i] = 0;
146		x->nlimbs -= nlimbs;
147
148		if (x->nlimbs && nbits)
149			mpihelp_rshift(x->d, x->d, x->nlimbs, nbits);
150	} else {
151		/* Copy and shift by less than bits in a limb.  */
152		xsize = a->nlimbs;
153		x->sign = a->sign;
154		err = RESIZE_IF_NEEDED(x, xsize);
155		if (err)
156			return err;
157		x->nlimbs = xsize;
158
159		if (xsize) {
160			if (nbits)
161				mpihelp_rshift(x->d, a->d, x->nlimbs, nbits);
162			else {
163				/* The rshift helper function is not specified for
164				 * NBITS==0, thus we do a plain copy here.
165				 */
166				for (i = 0; i < x->nlimbs; i++)
167					x->d[i] = a->d[i];
168			}
169		}
170	}
171	MPN_NORMALIZE(x->d, x->nlimbs);
172
173	return 0;
174}
175EXPORT_SYMBOL_GPL(mpi_rshift);