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