[linux.git] / lib / mpi / mpi-add.c

/* mpi-add.c  -  MPI functions
 *	Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
 *	Copyright (C) 1994, 1996 Free Software Foundation, Inc.
 *
 * This file is part of GnuPG.
 *
 * GnuPG is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * GnuPG is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 *
 * Note: This code is heavily based on the GNU MP Library.
 *	 Actually it's the same code with only minor changes in the
 *	 way the data is stored; this is to support the abstraction
 *	 of an optional secure memory allocation which may be used
 *	 to avoid revealing of sensitive data due to paging etc.
 *	 The GNU MP Library itself is published under the LGPL;
 *	 however I decided to publish this code under the plain GPL.
 */

#include "mpi-internal.h"

/****************
 * Add the unsigned integer V to the mpi-integer U and store the
 * result in W. U and V may be the same.
 */
int mpi_add_ui(MPI w, const MPI u, unsigned long v)
{
	mpi_ptr_t wp, up;
	mpi_size_t usize, wsize;
	int usign, wsign;

	usize = u->nlimbs;
	usign = u->sign;
	wsign = 0;

	/* If not space for W (and possible carry), increase space.  */
	wsize = usize + 1;
	if (w->alloced < wsize)
		if (mpi_resize(w, wsize) < 0)
			return -ENOMEM;

	/* These must be after realloc (U may be the same as W).  */
	up = u->d;
	wp = w->d;

	if (!usize) {		/* simple */
		wp[0] = v;
		wsize = v ? 1 : 0;
	} else if (!usign) {	/* mpi is not negative */
		mpi_limb_t cy;
		cy = mpihelp_add_1(wp, up, usize, v);
		wp[usize] = cy;
		wsize = usize + cy;
	} else {		/* The signs are different.  Need exact comparison to determine
				 * which operand to subtract from which.  */
		if (usize == 1 && up[0] < v) {
			wp[0] = v - up[0];
			wsize = 1;
		} else {
			mpihelp_sub_1(wp, up, usize, v);
			/* Size can decrease with at most one limb. */
			wsize = usize - (wp[usize - 1] == 0);
			wsign = 1;
		}
	}

	w->nlimbs = wsize;
	w->sign = wsign;
	return 0;
}

int mpi_add(MPI w, MPI u, MPI v)
{
	mpi_ptr_t wp, up, vp;
	mpi_size_t usize, vsize, wsize;
	int usign, vsign, wsign;

	if (u->nlimbs < v->nlimbs) {	/* Swap U and V. */
		usize = v->nlimbs;
		usign = v->sign;
		vsize = u->nlimbs;
		vsign = u->sign;
		wsize = usize + 1;
		if (RESIZE_IF_NEEDED(w, wsize) < 0)
			return -ENOMEM;
		/* These must be after realloc (u or v may be the same as w).  */
		up = v->d;
		vp = u->d;
	} else {
		usize = u->nlimbs;
		usign = u->sign;
		vsize = v->nlimbs;
		vsign = v->sign;
		wsize = usize + 1;
		if (RESIZE_IF_NEEDED(w, wsize) < 0)
			return -ENOMEM;
		/* These must be after realloc (u or v may be the same as w).  */
		up = u->d;
		vp = v->d;
	}
	wp = w->d;
	wsign = 0;

	if (!vsize) {		/* simple */
		MPN_COPY(wp, up, usize);
		wsize = usize;
		wsign = usign;
	} else if (usign != vsign) {	/* different sign */
		/* This test is right since USIZE >= VSIZE */
		if (usize != vsize) {
			mpihelp_sub(wp, up, usize, vp, vsize);
			wsize = usize;
			MPN_NORMALIZE(wp, wsize);
			wsign = usign;
		} else if (mpihelp_cmp(up, vp, usize) < 0) {
			mpihelp_sub_n(wp, vp, up, usize);
			wsize = usize;
			MPN_NORMALIZE(wp, wsize);
			if (!usign)
				wsign = 1;
		} else {
			mpihelp_sub_n(wp, up, vp, usize);
			wsize = usize;
			MPN_NORMALIZE(wp, wsize);
			if (usign)
				wsign = 1;
		}
	} else {		/* U and V have same sign. Add them. */
		mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize);
		wp[usize] = cy;
		wsize = usize + cy;
		if (usign)
			wsign = 1;
	}

	w->nlimbs = wsize;
	w->sign = wsign;
	return 0;
}

/****************
 * Subtract the unsigned integer V from the mpi-integer U and store the
 * result in W.
 */
int mpi_sub_ui(MPI w, MPI u, unsigned long v)
{
	mpi_ptr_t wp, up;
	mpi_size_t usize, wsize;
	int usign, wsign;

	usize = u->nlimbs;
	usign = u->sign;
	wsign = 0;

	/* If not space for W (and possible carry), increase space.  */
	wsize = usize + 1;
	if (w->alloced < wsize)
		if (mpi_resize(w, wsize) < 0)
			return -ENOMEM;

	/* These must be after realloc (U may be the same as W).  */
	up = u->d;
	wp = w->d;

	if (!usize) {		/* simple */
		wp[0] = v;
		wsize = v ? 1 : 0;
		wsign = 1;
	} else if (usign) {	/* mpi and v are negative */
		mpi_limb_t cy;
		cy = mpihelp_add_1(wp, up, usize, v);
		wp[usize] = cy;
		wsize = usize + cy;
	} else {		/* The signs are different.  Need exact comparison to determine
				 * which operand to subtract from which.  */
		if (usize == 1 && up[0] < v) {
			wp[0] = v - up[0];
			wsize = 1;
			wsign = 1;
		} else {
			mpihelp_sub_1(wp, up, usize, v);
			/* Size can decrease with at most one limb. */
			wsize = usize - (wp[usize - 1] == 0);
		}
	}

	w->nlimbs = wsize;
	w->sign = wsign;
	return 0;
}

int mpi_sub(MPI w, MPI u, MPI v)
{
	int rc;

	if (w == v) {
		MPI vv;
		if (mpi_copy(&vv, v) < 0)
			return -ENOMEM;
		vv->sign = !vv->sign;
		rc = mpi_add(w, u, vv);
		mpi_free(vv);
	} else {
		/* fixme: this is not thread-save (we temp. modify v) */
		v->sign = !v->sign;
		rc = mpi_add(w, u, v);
		v->sign = !v->sign;
	}
	return rc;
}

int mpi_addm(MPI w, MPI u, MPI v, MPI m)
{
	if (mpi_add(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
		return -ENOMEM;
	return 0;
}

int mpi_subm(MPI w, MPI u, MPI v, MPI m)
{
	if (mpi_sub(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0)
		return -ENOMEM;
	return 0;
}
Commit	Line	Data
7e8dec91 DK	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	*/
	36	int 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
82	int 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	*/
155	int 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
202	int 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
222	int 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
229	int 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	}