Merge branch 'for-linus' of git://selinuxproject.org/~jmorris/linux-security
[linux-3.10.git] / lib / 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 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 }