Branch data Line data Source code
1 : : /* crypto/bn/bn_sqr.c */
2 : : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 : : * All rights reserved.
4 : : *
5 : : * This package is an SSL implementation written
6 : : * by Eric Young (eay@cryptsoft.com).
7 : : * The implementation was written so as to conform with Netscapes SSL.
8 : : *
9 : : * This library is free for commercial and non-commercial use as long as
10 : : * the following conditions are aheared to. The following conditions
11 : : * apply to all code found in this distribution, be it the RC4, RSA,
12 : : * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 : : * included with this distribution is covered by the same copyright terms
14 : : * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 : : *
16 : : * Copyright remains Eric Young's, and as such any Copyright notices in
17 : : * the code are not to be removed.
18 : : * If this package is used in a product, Eric Young should be given attribution
19 : : * as the author of the parts of the library used.
20 : : * This can be in the form of a textual message at program startup or
21 : : * in documentation (online or textual) provided with the package.
22 : : *
23 : : * Redistribution and use in source and binary forms, with or without
24 : : * modification, are permitted provided that the following conditions
25 : : * are met:
26 : : * 1. Redistributions of source code must retain the copyright
27 : : * notice, this list of conditions and the following disclaimer.
28 : : * 2. Redistributions in binary form must reproduce the above copyright
29 : : * notice, this list of conditions and the following disclaimer in the
30 : : * documentation and/or other materials provided with the distribution.
31 : : * 3. All advertising materials mentioning features or use of this software
32 : : * must display the following acknowledgement:
33 : : * "This product includes cryptographic software written by
34 : : * Eric Young (eay@cryptsoft.com)"
35 : : * The word 'cryptographic' can be left out if the rouines from the library
36 : : * being used are not cryptographic related :-).
37 : : * 4. If you include any Windows specific code (or a derivative thereof) from
38 : : * the apps directory (application code) you must include an acknowledgement:
39 : : * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 : : *
41 : : * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 : : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 : : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 : : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 : : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 : : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 : : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 : : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 : : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 : : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 : : * SUCH DAMAGE.
52 : : *
53 : : * The licence and distribution terms for any publically available version or
54 : : * derivative of this code cannot be changed. i.e. this code cannot simply be
55 : : * copied and put under another distribution licence
56 : : * [including the GNU Public Licence.]
57 : : */
58 : :
59 : : #include <stdio.h>
60 : : #include "cryptlib.h"
61 : : #include "bn_lcl.h"
62 : :
63 : : /* r must not be a */
64 : : /* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */
65 : 196473 : int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
66 : : {
67 : : int max,al;
68 : 196473 : int ret = 0;
69 : : BIGNUM *tmp,*rr;
70 : :
71 : : #ifdef BN_COUNT
72 : : fprintf(stderr,"BN_sqr %d * %d\n",a->top,a->top);
73 : : #endif
74 : : bn_check_top(a);
75 : :
76 : 196473 : al=a->top;
77 [ + + ]: 196473 : if (al <= 0)
78 : : {
79 : 10 : r->top=0;
80 : 10 : r->neg = 0;
81 : 10 : return 1;
82 : : }
83 : :
84 : 196463 : BN_CTX_start(ctx);
85 [ + + ]: 196463 : rr=(a != r) ? r : BN_CTX_get(ctx);
86 : 196463 : tmp=BN_CTX_get(ctx);
87 [ + - ]: 196463 : if (!rr || !tmp) goto err;
88 : :
89 : 196463 : max = 2 * al; /* Non-zero (from above) */
90 [ + + ][ + - ]: 196463 : if (bn_wexpand(rr,max) == NULL) goto err;
91 : :
92 [ + + ]: 196463 : if (al == 4)
93 : : {
94 : : #ifndef BN_SQR_COMBA
95 : : BN_ULONG t[8];
96 : : bn_sqr_normal(rr->d,a->d,4,t);
97 : : #else
98 : 7253 : bn_sqr_comba4(rr->d,a->d);
99 : : #endif
100 : : }
101 [ + + ]: 189210 : else if (al == 8)
102 : : {
103 : : #ifndef BN_SQR_COMBA
104 : : BN_ULONG t[16];
105 : : bn_sqr_normal(rr->d,a->d,8,t);
106 : : #else
107 : 111909 : bn_sqr_comba8(rr->d,a->d);
108 : : #endif
109 : : }
110 : : else
111 : : {
112 : : #if defined(BN_RECURSION)
113 [ + + ]: 77301 : if (al < BN_SQR_RECURSIVE_SIZE_NORMAL)
114 : : {
115 : : BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL*2];
116 : 74810 : bn_sqr_normal(rr->d,a->d,al,t);
117 : : }
118 : : else
119 : : {
120 : : int j,k;
121 : :
122 : 2491 : j=BN_num_bits_word((BN_ULONG)al);
123 : 2491 : j=1<<(j-1);
124 : 2491 : k=j+j;
125 [ + + ]: 2491 : if (al == j)
126 : : {
127 [ + + ][ + - ]: 2490 : if (bn_wexpand(tmp,k*2) == NULL) goto err;
128 : 2490 : bn_sqr_recursive(rr->d,a->d,al,tmp->d);
129 : : }
130 : : else
131 : : {
132 [ - + ][ + - ]: 1 : if (bn_wexpand(tmp,max) == NULL) goto err;
133 : 1 : bn_sqr_normal(rr->d,a->d,al,tmp->d);
134 : : }
135 : : }
136 : : #else
137 : : if (bn_wexpand(tmp,max) == NULL) goto err;
138 : : bn_sqr_normal(rr->d,a->d,al,tmp->d);
139 : : #endif
140 : : }
141 : :
142 : 196463 : rr->neg=0;
143 : : /* If the most-significant half of the top word of 'a' is zero, then
144 : : * the square of 'a' will max-1 words. */
145 [ + + ]: 196463 : if(a->d[al - 1] == (a->d[al - 1] & BN_MASK2l))
146 : 66347 : rr->top = max - 1;
147 : : else
148 : 130116 : rr->top = max;
149 [ + + ]: 196463 : if (rr != r) BN_copy(r,rr);
150 : : ret = 1;
151 : : err:
152 : : bn_check_top(rr);
153 : : bn_check_top(tmp);
154 : 196463 : BN_CTX_end(ctx);
155 : 196463 : return(ret);
156 : : }
157 : :
158 : : /* tmp must have 2*n words */
159 : 74811 : void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp)
160 : : {
161 : : int i,j,max;
162 : : const BN_ULONG *ap;
163 : : BN_ULONG *rp;
164 : :
165 : 74811 : max=n*2;
166 : 74811 : ap=a;
167 : 74811 : rp=r;
168 : 74811 : rp[0]=rp[max-1]=0;
169 : 74811 : rp++;
170 : 74811 : j=n;
171 : :
172 [ + + ]: 74811 : if (--j > 0)
173 : : {
174 : 66946 : ap++;
175 : 66946 : rp[j]=bn_mul_words(rp,ap,j,ap[-1]);
176 : 66946 : rp+=2;
177 : : }
178 : :
179 [ + + ]: 284067 : for (i=n-2; i>0; i--)
180 : : {
181 : 209256 : j--;
182 : 209256 : ap++;
183 : 209256 : rp[j]=bn_mul_add_words(rp,ap,j,ap[-1]);
184 : 209256 : rp+=2;
185 : : }
186 : :
187 : 74811 : bn_add_words(r,r,r,max);
188 : :
189 : : /* There will not be a carry */
190 : :
191 : 74811 : bn_sqr_words(tmp,a,n);
192 : :
193 : 74811 : bn_add_words(r,r,tmp,max);
194 : 74811 : }
195 : :
196 : : #ifdef BN_RECURSION
197 : : /* r is 2*n words in size,
198 : : * a and b are both n words in size. (There's not actually a 'b' here ...)
199 : : * n must be a power of 2.
200 : : * We multiply and return the result.
201 : : * t must be 2*n words in size
202 : : * We calculate
203 : : * a[0]*b[0]
204 : : * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
205 : : * a[1]*b[1]
206 : : */
207 : 13578 : void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t)
208 : : {
209 : 13578 : int n=n2/2;
210 : : int zero,c1;
211 : : BN_ULONG ln,lo,*p;
212 : :
213 : : #ifdef BN_COUNT
214 : : fprintf(stderr," bn_sqr_recursive %d * %d\n",n2,n2);
215 : : #endif
216 [ - + ]: 13578 : if (n2 == 4)
217 : : {
218 : : #ifndef BN_SQR_COMBA
219 : : bn_sqr_normal(r,a,4,t);
220 : : #else
221 : 0 : bn_sqr_comba4(r,a);
222 : : #endif
223 : 0 : return;
224 : : }
225 [ + + ]: 13578 : else if (n2 == 8)
226 : : {
227 : : #ifndef BN_SQR_COMBA
228 : : bn_sqr_normal(r,a,8,t);
229 : : #else
230 : 9882 : bn_sqr_comba8(r,a);
231 : : #endif
232 : 9882 : return;
233 : : }
234 [ - + ]: 3696 : if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL)
235 : : {
236 : 0 : bn_sqr_normal(r,a,n2,t);
237 : 0 : return;
238 : : }
239 : : /* r=(a[0]-a[1])*(a[1]-a[0]) */
240 : 3696 : c1=bn_cmp_words(a,&(a[n]),n);
241 : 3696 : zero=0;
242 [ + + ]: 3696 : if (c1 > 0)
243 : 2417 : bn_sub_words(t,a,&(a[n]),n);
244 [ + - ]: 1279 : else if (c1 < 0)
245 : 1279 : bn_sub_words(t,&(a[n]),a,n);
246 : : else
247 : : zero=1;
248 : :
249 : : /* The result will always be negative unless it is zero */
250 : 3696 : p= &(t[n2*2]);
251 : :
252 [ + - ]: 3696 : if (!zero)
253 : 3696 : bn_sqr_recursive(&(t[n2]),t,n,p);
254 : : else
255 : 0 : memset(&(t[n2]),0,n2*sizeof(BN_ULONG));
256 : 3696 : bn_sqr_recursive(r,a,n,p);
257 : 3696 : bn_sqr_recursive(&(r[n2]),&(a[n]),n,p);
258 : :
259 : : /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
260 : : * r[10] holds (a[0]*b[0])
261 : : * r[32] holds (b[1]*b[1])
262 : : */
263 : :
264 : 3696 : c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
265 : :
266 : : /* t[32] is negative */
267 : 3696 : c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
268 : :
269 : : /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
270 : : * r[10] holds (a[0]*a[0])
271 : : * r[32] holds (a[1]*a[1])
272 : : * c1 holds the carry bits
273 : : */
274 : 3696 : c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
275 [ + + ]: 3696 : if (c1)
276 : : {
277 : 1202 : p= &(r[n+n2]);
278 : 1202 : lo= *p;
279 : 1202 : ln=(lo+c1)&BN_MASK2;
280 : 1202 : *p=ln;
281 : :
282 : : /* The overflow will stop before we over write
283 : : * words we should not overwrite */
284 [ - + ]: 1202 : if (ln < (BN_ULONG)c1)
285 : : {
286 : : do {
287 : 0 : p++;
288 : 0 : lo= *p;
289 : 0 : ln=(lo+1)&BN_MASK2;
290 : 0 : *p=ln;
291 [ # # ]: 0 : } while (ln == 0);
292 : : }
293 : : }
294 : : }
295 : : #endif
|
