Line data Source code
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
39 37277 : _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 37277 : usize = u->nlimbs;
46 37277 : usign = u->sign;
47 37277 : wsign = 0;
48 :
49 : /* If not space for W (and possible carry), increase space. */
50 37277 : wsize = usize + 1;
51 37277 : if( w->alloced < wsize )
52 727 : mpi_resize(w, wsize);
53 :
54 : /* These must be after realloc (U may be the same as W). */
55 37277 : up = u->d;
56 37277 : wp = w->d;
57 :
58 37277 : if( !usize ) { /* simple */
59 0 : wp[0] = v;
60 0 : wsize = v? 1:0;
61 : }
62 37277 : else if( !usign ) { /* mpi is not negative */
63 : mpi_limb_t cy;
64 37276 : cy = _gcry_mpih_add_1(wp, up, usize, v);
65 37276 : wp[usize] = cy;
66 37276 : wsize = usize + cy;
67 : }
68 : else { /* The signs are different. Need exact comparison to determine
69 : * which operand to subtract from which. */
70 1 : if( usize == 1 && up[0] < v ) {
71 0 : wp[0] = v - up[0];
72 0 : wsize = 1;
73 : }
74 : else {
75 1 : _gcry_mpih_sub_1(wp, up, usize, v);
76 : /* Size can decrease with at most one limb. */
77 1 : wsize = usize - (wp[usize-1]==0);
78 1 : wsign = 1;
79 : }
80 : }
81 :
82 37277 : w->nlimbs = wsize;
83 37277 : w->sign = wsign;
84 37277 : }
85 :
86 :
87 : void
88 37096388 : _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 37096388 : if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */
95 1113679 : usize = v->nlimbs;
96 1113679 : usign = v->sign;
97 1113679 : vsize = u->nlimbs;
98 1113679 : vsign = u->sign;
99 1113679 : wsize = usize + 1;
100 1113679 : RESIZE_IF_NEEDED(w, wsize);
101 : /* These must be after realloc (u or v may be the same as w). */
102 1113679 : up = v->d;
103 1113679 : vp = u->d;
104 : }
105 : else {
106 35982709 : usize = u->nlimbs;
107 35982709 : usign = u->sign;
108 35982709 : vsize = v->nlimbs;
109 35982709 : vsign = v->sign;
110 35982709 : wsize = usize + 1;
111 35982709 : RESIZE_IF_NEEDED(w, wsize);
112 : /* These must be after realloc (u or v may be the same as w). */
113 35982709 : up = u->d;
114 35982709 : vp = v->d;
115 : }
116 37096388 : wp = w->d;
117 37096388 : wsign = 0;
118 :
119 37096388 : if( !vsize ) { /* simple */
120 88612 : MPN_COPY(wp, up, usize );
121 88612 : wsize = usize;
122 88612 : wsign = usign;
123 : }
124 37007776 : else if( usign != vsign ) { /* different sign */
125 : /* This test is right since USIZE >= VSIZE */
126 26290050 : if( usize != vsize ) {
127 1076983 : _gcry_mpih_sub(wp, up, usize, vp, vsize);
128 1076983 : wsize = usize;
129 1076983 : MPN_NORMALIZE(wp, wsize);
130 1076983 : wsign = usign;
131 : }
132 25213067 : else if( _gcry_mpih_cmp(up, vp, usize) < 0 ) {
133 14611353 : _gcry_mpih_sub_n(wp, vp, up, usize);
134 14611353 : wsize = usize;
135 14611353 : MPN_NORMALIZE(wp, wsize);
136 14611353 : if( !usign )
137 7867507 : wsign = 1;
138 : }
139 : else {
140 10601714 : _gcry_mpih_sub_n(wp, up, vp, usize);
141 10601714 : wsize = usize;
142 10601714 : MPN_NORMALIZE(wp, wsize);
143 10601714 : if( usign )
144 33190 : wsign = 1;
145 : }
146 : }
147 : else { /* U and V have same sign. Add them. */
148 10717726 : mpi_limb_t cy = _gcry_mpih_add(wp, up, usize, vp, vsize);
149 10717726 : wp[usize] = cy;
150 10717726 : wsize = usize + cy;
151 10717726 : if( usign )
152 33483 : wsign = 1;
153 : }
154 :
155 37096388 : w->nlimbs = wsize;
156 37096388 : w->sign = wsign;
157 37096388 : }
158 :
159 :
160 : /****************
161 : * Subtract the unsigned integer V from the mpi-integer U and store the
162 : * result in W.
163 : */
164 : void
165 19457 : _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 19457 : usize = u->nlimbs;
172 19457 : usign = u->sign;
173 19457 : wsign = 0;
174 :
175 : /* If not space for W (and possible carry), increase space. */
176 19457 : wsize = usize + 1;
177 19457 : if( w->alloced < wsize )
178 4529 : mpi_resize(w, wsize);
179 :
180 : /* These must be after realloc (U may be the same as W). */
181 19457 : up = u->d;
182 19457 : wp = w->d;
183 :
184 19457 : if( !usize ) { /* simple */
185 1 : wp[0] = v;
186 1 : wsize = v? 1:0;
187 1 : wsign = 1;
188 : }
189 19456 : else if( usign ) { /* mpi and v are negative */
190 : mpi_limb_t cy;
191 0 : cy = _gcry_mpih_add_1(wp, up, usize, v);
192 0 : wp[usize] = cy;
193 0 : wsize = usize + cy;
194 : }
195 : else { /* The signs are different. Need exact comparison to determine
196 : * which operand to subtract from which. */
197 19456 : if( usize == 1 && up[0] < v ) {
198 0 : wp[0] = v - up[0];
199 0 : wsize = 1;
200 0 : wsign = 1;
201 : }
202 : else {
203 19456 : _gcry_mpih_sub_1(wp, up, usize, v);
204 : /* Size can decrease with at most one limb. */
205 19456 : wsize = usize - (wp[usize-1]==0);
206 : }
207 : }
208 :
209 19457 : w->nlimbs = wsize;
210 19457 : w->sign = wsign;
211 19457 : }
212 :
213 : void
214 19305792 : _gcry_mpi_sub(gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v)
215 : {
216 19305792 : gcry_mpi_t vv = mpi_copy (v);
217 19305792 : vv->sign = ! vv->sign;
218 19305792 : mpi_add (w, u, vv);
219 19305792 : mpi_free (vv);
220 19305792 : }
221 :
222 :
223 : void
224 1205 : _gcry_mpi_addm( gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)
225 : {
226 1205 : mpi_add (w, u, v);
227 1205 : mpi_mod (w, w, m);
228 1205 : }
229 :
230 : void
231 55 : _gcry_mpi_subm( gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)
232 : {
233 55 : mpi_sub (w, u, v);
234 55 : mpi_mod (w, w, m);
235 55 : }
|
