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