bn_sqr.c revision 65c4736d9c0ebc6d9b1d991593b55566909da9cd
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff/* crypto/bn/bn_sqr.c */
ddad35552931651426ad70912d29d9ab7d2a8d80Automatic Updater/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * All rights reserved.
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence *
ec5347e2c775f027573ce5648b910361aa926c01Automatic Updater * This package is an SSL implementation written
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * by Eric Young (eay@cryptsoft.com).
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * The implementation was written so as to conform with Netscapes SSL.
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence *
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * This library is free for commercial and non-commercial use as long as
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * the following conditions are aheared to. The following conditions
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * apply to all code found in this distribution, be it the RC4, RSA,
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * lhash, DES, etc., code; not just the SSL code. The SSL documentation
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * included with this distribution is covered by the same copyright terms
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * except that the holder is Tim Hudson (tjh@cryptsoft.com).
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews *
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * Copyright remains Eric Young's, and as such any Copyright notices in
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * the code are not to be removed.
321b1c0501d6d97c852ae02e13bdfef6f0bbe776Automatic Updater * If this package is used in a product, Eric Young should be given attribution
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * as the author of the parts of the library used.
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * This can be in the form of a textual message at program startup or
9c3531d72aeaad6c5f01efe6a1c82023e1379e4dDavid Lawrence * in documentation (online or textual) provided with the package.
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff *
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * Redistribution and use in source and binary forms, with or without
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * modification, are permitted provided that the following conditions
07072c9456f1112705db701bb35f12dbdcb217b0Mark Andrews * are met:
07072c9456f1112705db701bb35f12dbdcb217b0Mark Andrews * 1. Redistributions of source code must retain the copyright
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * notice, this list of conditions and the following disclaimer.
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * 2. Redistributions in binary form must reproduce the above copyright
80617c8faa03b2c425e320597eb768073fd0b987Michael Graff * notice, this list of conditions and the following disclaimer in the
a8dcebd0419f27234664e89b9cd48bc54cad08a7Michael Graff * documentation and/or other materials provided with the distribution.
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff * 3. All advertising materials mentioning features or use of this software
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * must display the following acknowledgement:
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence * "This product includes cryptographic software written by
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * Eric Young (eay@cryptsoft.com)"
3d181bc9f12154a56bfbb536198a6c481cbcd525David Lawrence * The word 'cryptographic' can be left out if the rouines from the library
32eddfc189108fa93e31761e13150594c7a79d2bDavid Lawrence * being used are not cryptographic related :-).
a095cd0ef599eb04d74fb9f9bc46ae13081c5bcbMark Andrews * 4. If you include any Windows specific code (or a derivative thereof) from
440be4c866f6935ac069db79a414304507a664c2Michael Graff * the apps directory (application code) you must include an acknowledgement:
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
e21d199dca95aff5d50f133d6b064309e209af00Brian Wellington *
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
20c266cbc999c724e03e6edd437fb4181b92f095Michael Graff * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20c266cbc999c724e03e6edd437fb4181b92f095Michael Graff * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
8d1943e8ffa991d54c5406342e44d7134762e7eaMichael Graff * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
b312748a11d27fe387984973ba79975a9d6863c4Mark Andrews * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
8907d8fa04fdaa65baf0bc6b01230b2ebde93106Mark Andrews * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
c6066a8e67f40c7c12925c5634485f55713c06d6Michael Graff * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews * SUCH DAMAGE.
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 *
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * The licence and distribution terms for any publically available version or
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * derivative of this code cannot be changed. i.e. this code cannot simply be
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * copied and put under another distribution licence
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * [including the GNU Public Licence.]
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 */
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉#include <stdio.h>
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉#include "cryptlib.h"
07072c9456f1112705db701bb35f12dbdcb217b0Mark Andrews#include "bn_lcl.h"
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews/* r must not be a */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinint BN_sqr(BIGNUM *r, BIGNUM *a, BN_CTX *ctx)
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein int max,al;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 BIGNUM *tmp,*rr;
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews#ifdef BN_COUNT
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graffprintf("BN_sqr %d * %d\n",a->top,a->top);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff#endif
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff bn_check_top(a);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff tmp= &(ctx->bn[ctx->tos]);
e21d199dca95aff5d50f133d6b064309e209af00Brian Wellington rr=(a != r)?r: (&ctx->bn[ctx->tos+1]);
b312748a11d27fe387984973ba79975a9d6863c4Mark Andrews
8907d8fa04fdaa65baf0bc6b01230b2ebde93106Mark Andrews al=a->top;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (al <= 0)
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff {
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff r->top=0;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff return(1);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff }
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff
8affb49a70de247206cb04aae87730f2b4c90dd0Mark Andrews max=(al+al);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (bn_wexpand(rr,max+1) == NULL) return(0);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 r->neg=0;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (al == 4)
8affb49a70de247206cb04aae87730f2b4c90dd0Mark Andrews {
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews#ifndef BN_SQR_COMBA
8affb49a70de247206cb04aae87730f2b4c90dd0Mark Andrews BN_ULONG t[8];
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein bn_sqr_normal(rr->d,a->d,4,t);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#else
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein bn_sqr_comba4(rr->d,a->d);
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff#endif
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff }
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff else if (al == 8)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#ifndef BN_SQR_COMBA
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein BN_ULONG t[16];
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein bn_sqr_normal(rr->d,a->d,8,t);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉#else
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 bn_sqr_comba8(rr->d,a->d);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉#endif
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 }
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 else
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉#if defined(BN_RECURSION)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (al < BN_SQR_RECURSIVE_SIZE_NORMAL)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL*2];
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 bn_sqr_normal(rr->d,a->d,al,t);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 }
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 else
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 int j,k;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 j=BN_num_bits_word((BN_ULONG)al);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 j=1<<(j-1);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 k=j+j;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (al == j)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff if (bn_wexpand(a,k*2) == NULL) return(0);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff if (bn_wexpand(tmp,k*2) == NULL) return(0);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff bn_sqr_recursive(rr->d,a->d,al,tmp->d);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff }
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff else
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff {
1ec39fc7a8b6ad92de3363d4c50b75e24fcd6accMichael Graff if (bn_wexpand(tmp,max) == NULL) return(0);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 bn_sqr_normal(rr->d,a->d,al,tmp->d);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 }
ab0e5066083abcbec62513a3cc041d1f1eb9098aMichael Graff }
a8dcebd0419f27234664e89b9cd48bc54cad08a7Michael Graff#else
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff if (bn_wexpand(tmp,max) == NULL) return(0);
038a3e6bfe6e15479b0469bd87de3a7139ad1109Brian Wellington bn_sqr_normal(rr->d,a->d,al,tmp->d);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉#endif
a8dcebd0419f27234664e89b9cd48bc54cad08a7Michael Graff }
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
ab0e5066083abcbec62513a3cc041d1f1eb9098aMichael Graff rr->top=max;
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff if ((max > 0) && (rr->d[max-1] == 0)) rr->top--;
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff if (rr != r) BN_copy(r,rr);
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff return(1);
1ec39fc7a8b6ad92de3363d4c50b75e24fcd6accMichael Graff }
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
ab0e5066083abcbec62513a3cc041d1f1eb9098aMichael Graff/* tmp must have 2*n words */
1ec39fc7a8b6ad92de3363d4c50b75e24fcd6accMichael Graffvoid bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 int i,j,max;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 BN_ULONG *ap,*rp;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 max=n*2;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 ap=a;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 rp=r;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 rp[0]=rp[max-1]=0;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 rp++;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 j=n;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (--j > 0)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 ap++;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 rp[j]=bn_mul_words(rp,ap,j,ap[-1]);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 rp+=2;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 }
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 for (i=n-2; i>0; i--)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 j--;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 ap++;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 rp[j]=bn_mul_add_words(rp,ap,j,ap[-1]);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 rp+=2;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 }
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 bn_add_words(r,r,r,max);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 /* There will not be a carry */
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 bn_sqr_words(tmp,a,n);
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff
ab0e5066083abcbec62513a3cc041d1f1eb9098aMichael Graff bn_add_words(r,r,tmp,max);
607dc8013a8cb34cd03b59292aa1ac01e008c9c1Michael Graff }
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉#ifdef BN_RECURSION
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉/* r is 2*n words in size,
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * a and b are both n words in size.
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * n must be a power of 2.
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * We multiply and return the result.
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * t must be 2*n words in size
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * We calulate
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * a[0]*b[0]
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein * a[1]*b[1]
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein */
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉void bn_sqr_recursive(BN_ULONG *r, BN_ULONG *a, int n2, BN_ULONG *t)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 int n=n2/2;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 int zero,c1;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 BN_ULONG ln,lo,*p;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉#ifdef BN_COUNT
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austeinprintf(" bn_sqr_recursive %d * %d\n",n2,n2);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#endif
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (n2 == 4)
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein {
35f06ab0e6d5ad26176b7584de7b4d405272ba68Brian Wellington#ifndef BN_SQR_COMBA
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff bn_sqr_normal(r,a,4,t);
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#else
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff bn_sqr_comba4(r,a);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff#endif
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff return;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein }
ce5bd92088923d1c76e26d313d1d8c0b8bbe38feMichael Graff else if (n2 == 8)
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff {
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein#ifndef BN_SQR_COMBA
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein bn_sqr_normal(r,a,8,t);
1ec39fc7a8b6ad92de3363d4c50b75e24fcd6accMichael Graff#else
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff bn_sqr_comba8(r,a);
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff#endif
f98d6edb191348477c9c5a156003df627d9bc42cBrian Wellington return;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein }
6f1422b81ed2c5142092e2ced8e3faf0e61f3ba0Michael Graff if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 bn_sqr_normal(r,a,n2,t);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 return;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein }
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein /* r=(a[0]-a[1])*(a[1]-a[0]) */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein c1=bn_cmp_words(a,&(a[n]),n);
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews zero=0;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (c1 > 0)
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff bn_sub_words(t,a,&(a[n]),n);
83f8c56f43852bf9a9c6964eae285284b23f9d8dMichael Graff else if (c1 < 0)
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews bn_sub_words(t,&(a[n]),a,n);
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews else
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews zero=1;
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff /* The result will always be negative unless it is zero */
a8dcebd0419f27234664e89b9cd48bc54cad08a7Michael Graff p= &(t[n2*2]);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (!zero)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 bn_sqr_recursive(&(t[n2]),t,n,p);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff else
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff memset(&(t[n2]),0,n*sizeof(BN_ULONG));
a8dcebd0419f27234664e89b9cd48bc54cad08a7Michael Graff bn_sqr_recursive(r,a,n,p);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff bn_sqr_recursive(&(r[n2]),&(a[n]),n,p);
ca9739800f045cd4d39014f98b920d4354b5bd14Michael Graff
a8dcebd0419f27234664e89b9cd48bc54cad08a7Michael Graff /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews * r[10] holds (a[0]*b[0])
a7c76f1924d5fc914c579fd3b0276ffbddd2f65aMark Andrews * r[32] holds (b[1]*b[1])
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 */
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 c1=(int)(bn_add_words(t,r,&(r[n2]),n2));
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 /* t[32] is negative */
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2));
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * r[10] holds (a[0]*a[0])
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * r[32] holds (a[1]*a[1])
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * c1 holds the carry bits
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 */
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2));
8d1943e8ffa991d54c5406342e44d7134762e7eaMichael Graff if (c1)
3d181bc9f12154a56bfbb536198a6c481cbcd525David Lawrence {
8d1943e8ffa991d54c5406342e44d7134762e7eaMichael Graff p= &(r[n+n2]);
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 lo= *p;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 ln=(lo+c1)&BN_MASK2;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 *p=ln;
46993e1d9d18410a5852b7d990338b70b158855cMichael Graff
35f06ab0e6d5ad26176b7584de7b4d405272ba68Brian Wellington /* The overflow will stop before we over write
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 * words we should not overwrite */
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 if (ln < (BN_ULONG)c1)
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 do {
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 p++;
0a9fedafec59fd3ec2eeadc3f123db163e71c0fbMichael Graff lo= *p;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 ln=(lo+1)&BN_MASK2;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 *p=ln;
386d3a99c190bad55edf44d076e6bd087e230ab8Tatuya JINMEI 神明達哉 } while (ln == 0);
0a9fedafec59fd3ec2eeadc3f123db163e71c0fbMichael Graff }
8470db5b12c18cfb32a757e265ce4e7789052c92Michael Graff }
0a9fedafec59fd3ec2eeadc3f123db163e71c0fbMichael Graff }
0a9fedafec59fd3ec2eeadc3f123db163e71c0fbMichael Graff#endif
d8c2b1787119de43dd6b7e3927ff193ed5df682fMark Andrews