fe00c5f69a01025918a5b06e271cfb52f269e415
[openssl.git] / crypto / bn / bn_sqr.c
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 int BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx)
66         {
67         int max,al;
68         int ret = 0;
69         BIGNUM *tmp,*rr;
70
71 #ifdef BN_COUNT
72 printf("BN_sqr %d * %d\n",a->top,a->top);
73 #endif
74         bn_check_top(a);
75
76         al=a->top;
77         if (al <= 0)
78                 {
79                 r->top=0;
80                 return(1);
81                 }
82
83         BN_CTX_start(ctx);
84         rr=(a != r) ? r : BN_CTX_get(ctx);
85         tmp=BN_CTX_get(ctx);
86         if (tmp == NULL) goto err;
87
88         max=(al+al);
89         if (bn_wexpand(rr,max+1) == NULL) goto err;
90
91         r->neg=0;
92         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                 bn_sqr_comba4(rr->d,a->d);
99 #endif
100                 }
101         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                 bn_sqr_comba8(rr->d,a->d);
108 #endif
109                 }
110         else 
111                 {
112 #if defined(BN_RECURSION)
113                 if (al < BN_SQR_RECURSIVE_SIZE_NORMAL)
114                         {
115                         BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL*2];
116                         bn_sqr_normal(rr->d,a->d,al,t);
117                         }
118                 else
119                         {
120                         int j,k;
121
122                         j=BN_num_bits_word((BN_ULONG)al);
123                         j=1<<(j-1);
124                         k=j+j;
125                         if (al == j)
126                                 {
127                                 if (bn_wexpand(a,k*2) == NULL) goto err;
128                                 if (bn_wexpand(tmp,k*2) == NULL) goto err;
129                                 bn_sqr_recursive(rr->d,a->d,al,tmp->d);
130                                 }
131                         else
132                                 {
133                                 if (bn_wexpand(tmp,max) == NULL) goto err;
134                                 bn_sqr_normal(rr->d,a->d,al,tmp->d);
135                                 }
136                         }
137 #else
138                 if (bn_wexpand(tmp,max) == NULL) goto err;
139                 bn_sqr_normal(rr->d,a->d,al,tmp->d);
140 #endif
141                 }
142
143         rr->top=max;
144         if ((max > 0) && (rr->d[max-1] == 0)) rr->top--;
145         if (rr != r) BN_copy(r,rr);
146         ret = 1;
147  err:
148         BN_CTX_end(ctx);
149         return(ret);
150         }
151
152 /* tmp must have 2*n words */
153 void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp)
154         {
155         int i,j,max;
156         BN_ULONG *ap,*rp;
157
158         max=n*2;
159         ap=a;
160         rp=r;
161         rp[0]=rp[max-1]=0;
162         rp++;
163         j=n;
164
165         if (--j > 0)
166                 {
167                 ap++;
168                 rp[j]=bn_mul_words(rp,ap,j,ap[-1]);
169                 rp+=2;
170                 }
171
172         for (i=n-2; i>0; i--)
173                 {
174                 j--;
175                 ap++;
176                 rp[j]=bn_mul_add_words(rp,ap,j,ap[-1]);
177                 rp+=2;
178                 }
179
180         bn_add_words(r,r,r,max);
181
182         /* There will not be a carry */
183
184         bn_sqr_words(tmp,a,n);
185
186         bn_add_words(r,r,tmp,max);
187         }
188
189 #ifdef BN_RECURSION
190 /* r is 2*n words in size,
191  * a and b are both n words in size.
192  * n must be a power of 2.
193  * We multiply and return the result.
194  * t must be 2*n words in size
195  * We calculate
196  * a[0]*b[0]
197  * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
198  * a[1]*b[1]
199  */
200 void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *t)
201         {
202         int n=n2/2;
203         int zero,c1;
204         BN_ULONG ln,lo,*p;
205
206 #ifdef BN_COUNT
207 printf(" bn_sqr_recursive %d * %d\n",n2,n2);
208 #endif
209         if (n2 == 4)
210                 {
211 #ifndef BN_SQR_COMBA
212                 bn_sqr_normal(r,a,4,t);
213 #else
214                 bn_sqr_comba4(r,a);
215 #endif
216                 return;
217                 }
218         else if (n2 == 8)
219                 {
220 #ifndef BN_SQR_COMBA
221                 bn_sqr_normal(r,a,8,t);
222 #else
223                 bn_sqr_comba8(r,a);
224 #endif
225                 return;
226                 }
227         if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL)
228                 {
229                 bn_sqr_normal(r,a,n2,t);
230                 return;
231                 }
232         /* r=(a[0]-a[1])*(a[1]-a[0]) */
233         c1=bn_cmp_words(a,&(a[n]),n);
234         zero=0;
235         if (c1 > 0)
236                 bn_sub_words(t,a,&(a[n]),n);
237         else if (c1 < 0)
238                 bn_sub_words(t,&(a[n]),a,n);
239         else
240                 zero=1;
241
242         /* The result will always be negative unless it is zero */
243         p= &(t[n2*2]);
244
245         if (!zero)
246                 bn_sqr_recursive(&(t[n2]),t,n,p);
247         else
248                 memset(&(t[n2]),0,n*sizeof(BN_ULONG));
249         bn_sqr_recursive(r,a,n,p);
250         bn_sqr_recursive(&(r[n2]),&(a[n]),n,p);
251
252         /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
253          * r[10] holds (a[0]*b[0])
254          * r[32] holds (b[1]*b[1])
255          */
256
257         c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
258
259         /* t[32] is negative */
260         c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
261
262         /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
263          * r[10] holds (a[0]*a[0])
264          * r[32] holds (a[1]*a[1])
265          * c1 holds the carry bits
266          */
267         c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
268         if (c1)
269                 {
270                 p= &(r[n+n2]);
271                 lo= *p;
272                 ln=(lo+c1)&BN_MASK2;
273                 *p=ln;
274
275                 /* The overflow will stop before we over write
276                  * words we should not overwrite */
277                 if (ln < (BN_ULONG)c1)
278                         {
279                         do      {
280                                 p++;
281                                 lo= *p;
282                                 ln=(lo+1)&BN_MASK2;
283                                 *p=ln;
284                                 } while (ln == 0);
285                         }
286                 }
287         }
288 #endif