source: trunk/cscrypt/bn_sqr.c@ 3181

Last change on this file since 3181 was 3181, checked in by dingo35, 10 years ago

Adding threadsafety FIXMEs, feel free to join checking..

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