AppleCSP/open_ssl/bn/bn_sqr.c

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