cscrypt/bn_sqr.c

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