1/* mpi-mul.c  -  MPI functions
  2 *	Copyright (C) 1994, 1996 Free Software Foundation, Inc.
  3 *	Copyright (C) 1998, 2001 Free Software Foundation, Inc.
  4 *
  5 * This file is part of GnuPG.
  6 *
  7 * GnuPG is free software; you can redistribute it and/or modify
  8 * it under the terms of the GNU General Public License as published by
  9 * the Free Software Foundation; either version 2 of the License, or
 10 * (at your option) any later version.
 11 *
 12 * GnuPG is distributed in the hope that it will be useful,
 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 15 * GNU General Public License for more details.
 16 *
 17 * You should have received a copy of the GNU General Public License
 18 * along with this program; if not, write to the Free Software
 19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 20 *
 21 * Note: This code is heavily based on the GNU MP Library.
 22 *	 Actually it's the same code with only minor changes in the
 23 *	 way the data is stored; this is to support the abstraction
 24 *	 of an optional secure memory allocation which may be used
 25 *	 to avoid revealing of sensitive data due to paging etc.
 26 *	 The GNU MP Library itself is published under the LGPL;
 27 *	 however I decided to publish this code under the plain GPL.
 28 */
 29
 30#include "mpi-internal.h"
 31
 32int mpi_mul_ui(MPI prod, MPI mult, unsigned long small_mult)
 33{
 34	mpi_size_t size, prod_size;
 35	mpi_ptr_t prod_ptr;
 36	mpi_limb_t cy;
 37	int sign;
 38
 39	size = mult->nlimbs;
 40	sign = mult->sign;
 41
 42	if (!size || !small_mult) {
 43		prod->nlimbs = 0;
 44		prod->sign = 0;
 45		return 0;
 46	}
 47
 48	prod_size = size + 1;
 49	if (prod->alloced < prod_size)
 50		if (mpi_resize(prod, prod_size) < 0)
 51			return -ENOMEM;
 52	prod_ptr = prod->d;
 53
 54	cy = mpihelp_mul_1(prod_ptr, mult->d, size, (mpi_limb_t) small_mult);
 55	if (cy)
 56		prod_ptr[size++] = cy;
 57	prod->nlimbs = size;
 58	prod->sign = sign;
 59	return 0;
 60}
 61
 62int mpi_mul_2exp(MPI w, MPI u, unsigned long cnt)
 63{
 64	mpi_size_t usize, wsize, limb_cnt;
 65	mpi_ptr_t wp;
 66	mpi_limb_t wlimb;
 67	int usign, wsign;
 68
 69	usize = u->nlimbs;
 70	usign = u->sign;
 71
 72	if (!usize) {
 73		w->nlimbs = 0;
 74		w->sign = 0;
 75		return 0;
 76	}
 77
 78	limb_cnt = cnt / BITS_PER_MPI_LIMB;
 79	wsize = usize + limb_cnt + 1;
 80	if (w->alloced < wsize)
 81		if (mpi_resize(w, wsize) < 0)
 82			return -ENOMEM;
 83	wp = w->d;
 84	wsize = usize + limb_cnt;
 85	wsign = usign;
 86
 87	cnt %= BITS_PER_MPI_LIMB;
 88	if (cnt) {
 89		wlimb = mpihelp_lshift(wp + limb_cnt, u->d, usize, cnt);
 90		if (wlimb) {
 91			wp[wsize] = wlimb;
 92			wsize++;
 93		}
 94	} else {
 95		MPN_COPY_DECR(wp + limb_cnt, u->d, usize);
 96	}
 97
 98	/* Zero all whole limbs at low end.  Do it here and not before calling
 99	 * mpn_lshift, not to lose for U == W.  */
100	MPN_ZERO(wp, limb_cnt);
101
102	w->nlimbs = wsize;
103	w->sign = wsign;
104	return 0;
105}
106
107int mpi_mul(MPI w, MPI u, MPI v)
108{
109	int rc = -ENOMEM;
110	mpi_size_t usize, vsize, wsize;
111	mpi_ptr_t up, vp, wp;
112	mpi_limb_t cy;
113	int usign, vsign, sign_product;
114	int assign_wp = 0;
115	mpi_ptr_t tmp_limb = NULL;
116
117	if (u->nlimbs < v->nlimbs) {	/* Swap U and V. */
118		usize = v->nlimbs;
119		usign = v->sign;
120		up = v->d;
121		vsize = u->nlimbs;
122		vsign = u->sign;
123		vp = u->d;
124	} else {
125		usize = u->nlimbs;
126		usign = u->sign;
127		up = u->d;
128		vsize = v->nlimbs;
129		vsign = v->sign;
130		vp = v->d;
131	}
132	sign_product = usign ^ vsign;
133	wp = w->d;
134
135	/* Ensure W has space enough to store the result.  */
136	wsize = usize + vsize;
137	if (w->alloced < (size_t) wsize) {
138		if (wp == up || wp == vp) {
139			wp = mpi_alloc_limb_space(wsize);
140			if (!wp)
141				goto nomem;
142			assign_wp = 1;
143		} else {
144			if (mpi_resize(w, wsize) < 0)
145				goto nomem;
146			wp = w->d;
147		}
148	} else {		/* Make U and V not overlap with W.      */
149		if (wp == up) {
150			/* W and U are identical.  Allocate temporary space for U.      */
151			up = tmp_limb = mpi_alloc_limb_space(usize);
152			if (!up)
153				goto nomem;
154			/* Is V identical too?  Keep it identical with U.  */
155			if (wp == vp)
156				vp = up;
157			/* Copy to the temporary space.  */
158			MPN_COPY(up, wp, usize);
159		} else if (wp == vp) {
160			/* W and V are identical.  Allocate temporary space for V.      */
161			vp = tmp_limb = mpi_alloc_limb_space(vsize);
162			if (!vp)
163				goto nomem;
164			/* Copy to the temporary space.  */
165			MPN_COPY(vp, wp, vsize);
166		}
167	}
168
169	if (!vsize)
170		wsize = 0;
171	else {
172		if (mpihelp_mul(wp, up, usize, vp, vsize, &cy) < 0)
173			goto nomem;
174		wsize -= cy ? 0 : 1;
175	}
176
177	if (assign_wp)
178		mpi_assign_limb_space(w, wp, wsize);
179
180	w->nlimbs = wsize;
181	w->sign = sign_product;
182	rc = 0;
183nomem:
184	if (tmp_limb)
185		mpi_free_limb_space(tmp_limb);
186	return rc;
187}
188
189int mpi_mulm(MPI w, MPI u, MPI v, MPI m)
190{
191	if (mpi_mul(w, u, v) < 0)
192		return -ENOMEM;
193	return mpi_fdiv_r(w, w, m);
194}