diff options
Diffstat (limited to 'openssl/crypto/bn/bn_sqr.c')
| -rw-r--r-- | openssl/crypto/bn/bn_sqr.c | 369 |
1 files changed, 182 insertions, 187 deletions
diff --git a/openssl/crypto/bn/bn_sqr.c b/openssl/crypto/bn/bn_sqr.c index 65bbf165d..3ca69879e 100644 --- a/openssl/crypto/bn/bn_sqr.c +++ b/openssl/crypto/bn/bn_sqr.c @@ -5,21 +5,21 @@ * This package is an SSL implementation written * by Eric Young (eay@cryptsoft.com). * The implementation was written so as to conform with Netscapes SSL. - * + * * This library is free for commercial and non-commercial use as long as * the following conditions are aheared to. The following conditions * apply to all code found in this distribution, be it the RC4, RSA, * lhash, DES, etc., code; not just the SSL code. The SSL documentation * included with this distribution is covered by the same copyright terms * except that the holder is Tim Hudson (tjh@cryptsoft.com). - * + * * Copyright remains Eric Young's, and as such any Copyright notices in * the code are not to be removed. * If this package is used in a product, Eric Young should be given attribution * as the author of the parts of the library used. * This can be in the form of a textual message at program startup or * in documentation (online or textual) provided with the package. - * + * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: @@ -34,10 +34,10 @@ * Eric Young (eay@cryptsoft.com)" * The word 'cryptographic' can be left out if the rouines from the library * being used are not cryptographic related :-). - * 4. If you include any Windows specific code (or a derivative thereof) from + * 4. If you include any Windows specific code (or a derivative thereof) from * the apps directory (application code) you must include an acknowledgement: * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" - * + * * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE @@ -49,7 +49,7 @@ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. - * + * * The licence and distribution terms for any publically available version or * derivative of this code cannot be changed. i.e. this code cannot simply be * copied and put under another distribution licence @@ -61,140 +61,137 @@ #include "bn_lcl.h" /* r must not be a */ -/* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */ +/* + * I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 + */ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) - { - int max,al; - int ret = 0; - BIGNUM *tmp,*rr; +{ + int max, al; + int ret = 0; + BIGNUM *tmp, *rr; #ifdef BN_COUNT - fprintf(stderr,"BN_sqr %d * %d\n",a->top,a->top); + fprintf(stderr, "BN_sqr %d * %d\n", a->top, a->top); #endif - bn_check_top(a); + bn_check_top(a); - al=a->top; - if (al <= 0) - { - r->top=0; - r->neg = 0; - return 1; - } + al = a->top; + if (al <= 0) { + r->top = 0; + r->neg = 0; + return 1; + } - BN_CTX_start(ctx); - rr=(a != r) ? r : BN_CTX_get(ctx); - tmp=BN_CTX_get(ctx); - if (!rr || !tmp) goto err; + BN_CTX_start(ctx); + rr = (a != r) ? r : BN_CTX_get(ctx); + tmp = BN_CTX_get(ctx); + if (!rr || !tmp) + goto err; - max = 2 * al; /* Non-zero (from above) */ - if (bn_wexpand(rr,max) == NULL) goto err; + max = 2 * al; /* Non-zero (from above) */ + if (bn_wexpand(rr, max) == NULL) + goto err; - if (al == 4) - { + if (al == 4) { #ifndef BN_SQR_COMBA - BN_ULONG t[8]; - bn_sqr_normal(rr->d,a->d,4,t); + BN_ULONG t[8]; + bn_sqr_normal(rr->d, a->d, 4, t); #else - bn_sqr_comba4(rr->d,a->d); + bn_sqr_comba4(rr->d, a->d); #endif - } - else if (al == 8) - { + } else if (al == 8) { #ifndef BN_SQR_COMBA - BN_ULONG t[16]; - bn_sqr_normal(rr->d,a->d,8,t); + BN_ULONG t[16]; + bn_sqr_normal(rr->d, a->d, 8, t); #else - bn_sqr_comba8(rr->d,a->d); + bn_sqr_comba8(rr->d, a->d); #endif - } - else - { + } else { #if defined(BN_RECURSION) - if (al < BN_SQR_RECURSIVE_SIZE_NORMAL) - { - BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL*2]; - bn_sqr_normal(rr->d,a->d,al,t); - } - else - { - int j,k; + if (al < BN_SQR_RECURSIVE_SIZE_NORMAL) { + BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL * 2]; + bn_sqr_normal(rr->d, a->d, al, t); + } else { + int j, k; - j=BN_num_bits_word((BN_ULONG)al); - j=1<<(j-1); - k=j+j; - if (al == j) - { - if (bn_wexpand(tmp,k*2) == NULL) goto err; - bn_sqr_recursive(rr->d,a->d,al,tmp->d); - } - else - { - if (bn_wexpand(tmp,max) == NULL) goto err; - bn_sqr_normal(rr->d,a->d,al,tmp->d); - } - } + j = BN_num_bits_word((BN_ULONG)al); + j = 1 << (j - 1); + k = j + j; + if (al == j) { + if (bn_wexpand(tmp, k * 2) == NULL) + goto err; + bn_sqr_recursive(rr->d, a->d, al, tmp->d); + } else { + if (bn_wexpand(tmp, max) == NULL) + goto err; + bn_sqr_normal(rr->d, a->d, al, tmp->d); + } + } #else - if (bn_wexpand(tmp,max) == NULL) goto err; - bn_sqr_normal(rr->d,a->d,al,tmp->d); + if (bn_wexpand(tmp, max) == NULL) + goto err; + bn_sqr_normal(rr->d, a->d, al, tmp->d); #endif - } + } - rr->neg=0; - /* If the most-significant half of the top word of 'a' is zero, then - * the square of 'a' will max-1 words. */ - if(a->d[al - 1] == (a->d[al - 1] & BN_MASK2l)) - rr->top = max - 1; - else - rr->top = max; - if (rr != r) BN_copy(r,rr); - ret = 1; + rr->neg = 0; + /* + * If the most-significant half of the top word of 'a' is zero, then the + * square of 'a' will max-1 words. + */ + if (a->d[al - 1] == (a->d[al - 1] & BN_MASK2l)) + rr->top = max - 1; + else + rr->top = max; + if (rr != r) + BN_copy(r, rr); + ret = 1; err: - bn_check_top(rr); - bn_check_top(tmp); - BN_CTX_end(ctx); - return(ret); - } + bn_check_top(rr); + bn_check_top(tmp); + BN_CTX_end(ctx); + return (ret); +} /* tmp must have 2*n words */ void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp) - { - int i,j,max; - const BN_ULONG *ap; - BN_ULONG *rp; +{ + int i, j, max; + const BN_ULONG *ap; + BN_ULONG *rp; - max=n*2; - ap=a; - rp=r; - rp[0]=rp[max-1]=0; - rp++; - j=n; + max = n * 2; + ap = a; + rp = r; + rp[0] = rp[max - 1] = 0; + rp++; + j = n; - if (--j > 0) - { - ap++; - rp[j]=bn_mul_words(rp,ap,j,ap[-1]); - rp+=2; - } + if (--j > 0) { + ap++; + rp[j] = bn_mul_words(rp, ap, j, ap[-1]); + rp += 2; + } - for (i=n-2; i>0; i--) - { - j--; - ap++; - rp[j]=bn_mul_add_words(rp,ap,j,ap[-1]); - rp+=2; - } + for (i = n - 2; i > 0; i--) { + j--; + ap++; + rp[j] = bn_mul_add_words(rp, ap, j, ap[-1]); + rp += 2; + } - bn_add_words(r,r,r,max); + bn_add_words(r, r, r, max); - /* There will not be a carry */ + /* There will not be a carry */ - bn_sqr_words(tmp,a,n); + bn_sqr_words(tmp, a, n); - bn_add_words(r,r,tmp,max); - } + bn_add_words(r, r, tmp, max); +} #ifdef BN_RECURSION -/* r is 2*n words in size, +/*- + * r is 2*n words in size, * a and b are both n words in size. (There's not actually a 'b' here ...) * n must be a power of 2. * We multiply and return the result. @@ -205,91 +202,89 @@ void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp) * a[1]*b[1] */ void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t) - { - int n=n2/2; - int zero,c1; - BN_ULONG ln,lo,*p; +{ + int n = n2 / 2; + int zero, c1; + BN_ULONG ln, lo, *p; -#ifdef BN_COUNT - fprintf(stderr," bn_sqr_recursive %d * %d\n",n2,n2); -#endif - if (n2 == 4) - { -#ifndef BN_SQR_COMBA - bn_sqr_normal(r,a,4,t); -#else - bn_sqr_comba4(r,a); -#endif - return; - } - else if (n2 == 8) - { -#ifndef BN_SQR_COMBA - bn_sqr_normal(r,a,8,t); -#else - bn_sqr_comba8(r,a); -#endif - return; - } - if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) - { - bn_sqr_normal(r,a,n2,t); - return; - } - /* r=(a[0]-a[1])*(a[1]-a[0]) */ - c1=bn_cmp_words(a,&(a[n]),n); - zero=0; - if (c1 > 0) - bn_sub_words(t,a,&(a[n]),n); - else if (c1 < 0) - bn_sub_words(t,&(a[n]),a,n); - else - zero=1; +# ifdef BN_COUNT + fprintf(stderr, " bn_sqr_recursive %d * %d\n", n2, n2); +# endif + if (n2 == 4) { +# ifndef BN_SQR_COMBA + bn_sqr_normal(r, a, 4, t); +# else + bn_sqr_comba4(r, a); +# endif + return; + } else if (n2 == 8) { +# ifndef BN_SQR_COMBA + bn_sqr_normal(r, a, 8, t); +# else + bn_sqr_comba8(r, a); +# endif + return; + } + if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) { + bn_sqr_normal(r, a, n2, t); + return; + } + /* r=(a[0]-a[1])*(a[1]-a[0]) */ + c1 = bn_cmp_words(a, &(a[n]), n); + zero = 0; + if (c1 > 0) + bn_sub_words(t, a, &(a[n]), n); + else if (c1 < 0) + bn_sub_words(t, &(a[n]), a, n); + else + zero = 1; - /* The result will always be negative unless it is zero */ - p= &(t[n2*2]); + /* The result will always be negative unless it is zero */ + p = &(t[n2 * 2]); - if (!zero) - bn_sqr_recursive(&(t[n2]),t,n,p); - else - memset(&(t[n2]),0,n2*sizeof(BN_ULONG)); - bn_sqr_recursive(r,a,n,p); - bn_sqr_recursive(&(r[n2]),&(a[n]),n,p); + if (!zero) + bn_sqr_recursive(&(t[n2]), t, n, p); + else + memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG)); + bn_sqr_recursive(r, a, n, p); + bn_sqr_recursive(&(r[n2]), &(a[n]), n, p); - /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - */ + /*- + * t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero + * r[10] holds (a[0]*b[0]) + * r[32] holds (b[1]*b[1]) + */ - c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); + c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); - /* t[32] is negative */ - c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); + /* t[32] is negative */ + c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); - /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1]) - * r[10] holds (a[0]*a[0]) - * r[32] holds (a[1]*a[1]) - * c1 holds the carry bits - */ - c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); - if (c1) - { - p= &(r[n+n2]); - lo= *p; - ln=(lo+c1)&BN_MASK2; - *p=ln; + /*- + * t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1]) + * r[10] holds (a[0]*a[0]) + * r[32] holds (a[1]*a[1]) + * c1 holds the carry bits + */ + c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); + if (c1) { + p = &(r[n + n2]); + lo = *p; + ln = (lo + c1) & BN_MASK2; + *p = ln; - /* The overflow will stop before we over write - * words we should not overwrite */ - if (ln < (BN_ULONG)c1) - { - do { - p++; - lo= *p; - ln=(lo+1)&BN_MASK2; - *p=ln; - } while (ln == 0); - } - } - } + /* + * The overflow will stop before we over write words we should not + * overwrite + */ + if (ln < (BN_ULONG)c1) { + do { + p++; + lo = *p; + ln = (lo + 1) & BN_MASK2; + *p = ln; + } while (ln == 0); + } + } +} #endif |