1 /* mpi-add.c - MPI functions
2 * Copyright (C) 1994, 1996, 1998, 2001, 2002, 2003 Free Software Foundation, Inc.
3 *
4 * This file is part of Libgcrypt.
5 *
6 * Libgcrypt is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 2.1 of
9 * the License, or (at your option) any later version.
10 *
11 * Libgcrypt 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 Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License 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 * Note: This code is heavily based on the GNU MP Library.
21 * Actually it's the same code with only minor changes in the
22 * way the data is stored; this is to support the abstraction
23 * of an optional secure memory allocation which may be used
24 * to avoid revealing of sensitive data due to paging etc.
25 */
26
27 #include <config.h>
28 #include <stdio.h>
29 #include <stdlib.h>
30
31 #include "mpi-internal.h"
32
33
34 /****************
35 * Add the unsigned integer V to the mpi-integer U and store the
36 * result in W. U and V may be the same.
37 */
38 void
_gcry_mpi_add_ui(gcry_mpi_t w,gcry_mpi_t u,unsigned long v)39 _gcry_mpi_add_ui (gcry_mpi_t w, gcry_mpi_t u, unsigned long v )
40 {
41 mpi_ptr_t wp, up;
42 mpi_size_t usize, wsize;
43 int usign, wsign;
44
45 usize = u->nlimbs;
46 usign = u->sign;
47 wsign = 0;
48
49 /* If not space for W (and possible carry), increase space. */
50 wsize = usize + 1;
51 if( w->alloced < wsize )
52 mpi_resize(w, wsize);
53
54 /* These must be after realloc (U may be the same as W). */
55 up = u->d;
56 wp = w->d;
57
58 if( !usize ) { /* simple */
59 wp[0] = v;
60 wsize = v? 1:0;
61 }
62 else if( !usign ) { /* mpi is not negative */
63 mpi_limb_t cy;
64 cy = _gcry_mpih_add_1(wp, up, usize, v);
65 wp[usize] = cy;
66 wsize = usize + cy;
67 }
68 else { /* The signs are different. Need exact comparison to determine
69 * which operand to subtract from which. */
70 if( usize == 1 && up[0] < v ) {
71 wp[0] = v - up[0];
72 wsize = 1;
73 }
74 else {
75 _gcry_mpih_sub_1(wp, up, usize, v);
76 /* Size can decrease with at most one limb. */
77 wsize = usize - (wp[usize-1]==0);
78 wsign = 1;
79 }
80 }
81
82 w->nlimbs = wsize;
83 w->sign = wsign;
84 }
85
86
87 void
_gcry_mpi_add(gcry_mpi_t w,gcry_mpi_t u,gcry_mpi_t v)88 _gcry_mpi_add(gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v)
89 {
90 mpi_ptr_t wp, up, vp;
91 mpi_size_t usize, vsize, wsize;
92 int usign, vsign, wsign;
93
94 if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */
95 usize = v->nlimbs;
96 usign = v->sign;
97 vsize = u->nlimbs;
98 vsign = u->sign;
99 wsize = usize + 1;
100 RESIZE_IF_NEEDED(w, wsize);
101 /* These must be after realloc (u or v may be the same as w). */
102 up = v->d;
103 vp = u->d;
104 }
105 else {
106 usize = u->nlimbs;
107 usign = u->sign;
108 vsize = v->nlimbs;
109 vsign = v->sign;
110 wsize = usize + 1;
111 RESIZE_IF_NEEDED(w, wsize);
112 /* These must be after realloc (u or v may be the same as w). */
113 up = u->d;
114 vp = v->d;
115 }
116 wp = w->d;
117 wsign = 0;
118
119 if( !vsize ) { /* simple */
120 MPN_COPY(wp, up, usize );
121 wsize = usize;
122 wsign = usign;
123 }
124 else if( usign != vsign ) { /* different sign */
125 /* This test is right since USIZE >= VSIZE */
126 if( usize != vsize ) {
127 _gcry_mpih_sub(wp, up, usize, vp, vsize);
128 wsize = usize;
129 MPN_NORMALIZE(wp, wsize);
130 wsign = usign;
131 }
132 else if( _gcry_mpih_cmp(up, vp, usize) < 0 ) {
133 _gcry_mpih_sub_n(wp, vp, up, usize);
134 wsize = usize;
135 MPN_NORMALIZE(wp, wsize);
136 if( !usign )
137 wsign = 1;
138 }
139 else {
140 _gcry_mpih_sub_n(wp, up, vp, usize);
141 wsize = usize;
142 MPN_NORMALIZE(wp, wsize);
143 if( usign )
144 wsign = 1;
145 }
146 }
147 else { /* U and V have same sign. Add them. */
148 mpi_limb_t cy = _gcry_mpih_add(wp, up, usize, vp, vsize);
149 wp[usize] = cy;
150 wsize = usize + cy;
151 if( usign )
152 wsign = 1;
153 }
154
155 w->nlimbs = wsize;
156 w->sign = wsign;
157 }
158
159
160 /****************
161 * Subtract the unsigned integer V from the mpi-integer U and store the
162 * result in W.
163 */
164 void
_gcry_mpi_sub_ui(gcry_mpi_t w,gcry_mpi_t u,unsigned long v)165 _gcry_mpi_sub_ui(gcry_mpi_t w, gcry_mpi_t u, unsigned long v )
166 {
167 mpi_ptr_t wp, up;
168 mpi_size_t usize, wsize;
169 int usign, wsign;
170
171 usize = u->nlimbs;
172 usign = u->sign;
173 wsign = 0;
174
175 /* If not space for W (and possible carry), increase space. */
176 wsize = usize + 1;
177 if( w->alloced < wsize )
178 mpi_resize(w, wsize);
179
180 /* These must be after realloc (U may be the same as W). */
181 up = u->d;
182 wp = w->d;
183
184 if( !usize ) { /* simple */
185 wp[0] = v;
186 wsize = v? 1:0;
187 wsign = 1;
188 }
189 else if( usign ) { /* mpi and v are negative */
190 mpi_limb_t cy;
191 cy = _gcry_mpih_add_1(wp, up, usize, v);
192 wp[usize] = cy;
193 wsize = usize + cy;
194 }
195 else { /* The signs are different. Need exact comparison to determine
196 * which operand to subtract from which. */
197 if( usize == 1 && up[0] < v ) {
198 wp[0] = v - up[0];
199 wsize = 1;
200 wsign = 1;
201 }
202 else {
203 _gcry_mpih_sub_1(wp, up, usize, v);
204 /* Size can decrease with at most one limb. */
205 wsize = usize - (wp[usize-1]==0);
206 }
207 }
208
209 w->nlimbs = wsize;
210 w->sign = wsign;
211 }
212
213 void
_gcry_mpi_sub(gcry_mpi_t w,gcry_mpi_t u,gcry_mpi_t v)214 _gcry_mpi_sub(gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v)
215 {
216 gcry_mpi_t vv = mpi_copy (v);
217 vv->sign = ! vv->sign;
218 mpi_add (w, u, vv);
219 mpi_free (vv);
220 }
221
222
223 void
_gcry_mpi_addm(gcry_mpi_t w,gcry_mpi_t u,gcry_mpi_t v,gcry_mpi_t m)224 _gcry_mpi_addm( gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)
225 {
226 mpi_add (w, u, v);
227 mpi_mod (w, w, m);
228 }
229
230 void
_gcry_mpi_subm(gcry_mpi_t w,gcry_mpi_t u,gcry_mpi_t v,gcry_mpi_t m)231 _gcry_mpi_subm( gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)
232 {
233 mpi_sub (w, u, v);
234 mpi_mod (w, w, m);
235 }
236