1/* mpi-add.c  -  MPI functions
  2 *	Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
  3 *	Copyright (C) 1994, 1996 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
 32/****************
 33 * Add the unsigned integer V to the mpi-integer U and store the
 34 * result in W. U and V may be the same.
 35 */
 36int mpi_add_ui(MPI w, const MPI u, unsigned long v)
 37{
 38	mpi_ptr_t wp, up;
 39	mpi_size_t usize, wsize;
 40	int usign, wsign;
 41
 42	usize = u->nlimbs;
 43	usign = u->sign;
 44	wsign = 0;
 45
 46	/* If not space for W (and possible carry), increase space.  */
 47	wsize = usize + 1;
 48	if (w->alloced < wsize)
 49		if (mpi_resize(w, wsize) < 0)
 50			return -ENOMEM;
 51
 52	/* These must be after realloc (U may be the same as W).  */
 53	up = u->d;
 54	wp = w->d;
 55
 56	if (!usize) {		/* simple */
 57		wp[0] = v;
 58		wsize = v ? 1 : 0;
 59	} else if (!usign) {	/* mpi is not negative */
 60		mpi_limb_t cy;
 61		cy = mpihelp_add_1(wp, up, usize, v);
 62		wp[usize] = cy;
 63		wsize = usize + cy;
 64	} else {		/* The signs are different.  Need exact comparison to determine
 65				 * which operand to subtract from which.  */
 66		if (usize == 1 && up[0] < v) {
 67			wp[0] = v - up[0];
 68			wsize = 1;
 69		} else {
 70			mpihelp_sub_1(wp, up, usize, v);
 71			/* Size can decrease with at most one limb. */
 72			wsize = usize - (wp[usize - 1] == 0);
 73			wsign = 1;
 74		}
 75	}
 76
 77	w->nlimbs = wsize;
 78	w->sign = wsign;
 79	return 0;
 80}
 81
 82int mpi_add(MPI w, MPI u, MPI v)
 83{
 84	mpi_ptr_t wp, up, vp;
 85	mpi_size_t usize, vsize, wsize;
 86	int usign, vsign, wsign;
 87
 88	if (u->nlimbs < v->nlimbs) {	/* Swap U and V. */
 89		usize = v->nlimbs;
 90		usign = v->sign;
 91		vsize = u->nlimbs;
 92		vsign = u->sign;
 93		wsize = usize + 1;
 94		if (RESIZE_IF_NEEDED(w, wsize) < 0)
 95			return -ENOMEM;
 96		/* These must be after realloc (u or v may be the same as w).  */
 97		up = v->d;
 98		vp = u->d;
 99	} else {
100		usize = u->nlimbs;
101		usign = u->sign;
102		vsize = v->nlimbs;
103		vsign = v->sign;
104		wsize = usize + 1;
105		if (RESIZE_IF_NEEDED(w, wsize) < 0)
106			return -ENOMEM;
107		/* These must be after realloc (u or v may be the same as w).  */
108		up = u->d;
109		vp = v->d;
110	}
111	wp = w->d;
112	wsign = 0;
113
114	if (!vsize) {		/* simple */
115		MPN_COPY(wp, up, usize);
116		wsize = usize;
117		wsign = usign;
118	} else if (usign != vsign) {	/* different sign */
119		/* This test is right since USIZE >= VSIZE */
120		if (usize != vsize) {
121			mpihelp_sub(wp, up, usize, vp, vsize);
122			wsize = usize;
123			MPN_NORMALIZE(wp, wsize);
124			wsign = usign;
125		} else if (mpihelp_cmp(up, vp, usize) < 0) {
126			mpihelp_sub_n(wp, vp, up, usize);
127			wsize = usize;
128			MPN_NORMALIZE(wp, wsize);
129			if (!usign)
130				wsign = 1;
131		} else {
132			mpihelp_sub_n(wp, up, vp, usize);
133			wsize = usize;
134			MPN_NORMALIZE(wp, wsize);
135			if (usign)
136				wsign = 1;
137		}
138	} else {		/* U and V have same sign. Add them. */
139		mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
140		wp[usize] = cy;
141		wsize = usize + cy;
142		if (usign)
143			wsign = 1;
144	}
145
146	w->nlimbs = wsize;
147	w->sign = wsign;
148	return 0;
149}
150
151/****************
152 * Subtract the unsigned integer V from the mpi-integer U and store the
153 * result in W.
154 */
155int mpi_sub_ui(MPI w, MPI u, unsigned long v)
156{
157	mpi_ptr_t wp, up;
158	mpi_size_t usize, wsize;
159	int usign, wsign;
160
161	usize = u->nlimbs;
162	usign = u->sign;
163	wsign = 0;
164
165	/* If not space for W (and possible carry), increase space.  */
166	wsize = usize + 1;
167	if (w->alloced < wsize)
168		if (mpi_resize(w, wsize) < 0)
169			return -ENOMEM;
170
171	/* These must be after realloc (U may be the same as W).  */
172	up = u->d;
173	wp = w->d;
174
175	if (!usize) {		/* simple */
176		wp[0] = v;
177		wsize = v ? 1 : 0;
178		wsign = 1;
179	} else if (usign) {	/* mpi and v are negative */
180		mpi_limb_t cy;
181		cy = mpihelp_add_1(wp, up, usize, v);
182		wp[usize] = cy;
183		wsize = usize + cy;
184	} else {		/* The signs are different.  Need exact comparison to determine
185				 * which operand to subtract from which.  */
186		if (usize == 1 && up[0] < v) {
187			wp[0] = v - up[0];
188			wsize = 1;
189			wsign = 1;
190		} else {
191			mpihelp_sub_1(wp, up, usize, v);
192			/* Size can decrease with at most one limb. */
193			wsize = usize - (wp[usize - 1] == 0);
194		}
195	}
196
197	w->nlimbs = wsize;
198	w->sign = wsign;
199	return 0;
200}
201
202int mpi_sub(MPI w, MPI u, MPI v)
203{
204	int rc;
205
206	if (w == v) {
207		MPI vv;
208		if (mpi_copy(&vv, v) < 0)
209			return -ENOMEM;
210		vv->sign = !vv->sign;
211		rc = mpi_add(w, u, vv);
212		mpi_free(vv);
213	} else {
214		/* fixme: this is not thread-save (we temp. modify v) */
215		v->sign = !v->sign;
216		rc = mpi_add(w, u, v);
217		v->sign = !v->sign;
218	}
219	return rc;
220}
221
222int mpi_addm(MPI w, MPI u, MPI v, MPI m)
223{
224	if (mpi_add(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
225		return -ENOMEM;
226	return 0;
227}
228
229int mpi_subm(MPI w, MPI u, MPI v, MPI m)
230{
231	if (mpi_sub(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
232		return -ENOMEM;
233	return 0;
234}