diff options
Diffstat (limited to 'crypto/bn/stuff/wei_mulw.c')
| -rw-r--r-- | crypto/bn/stuff/wei_mulw.c | 410 |
1 files changed, 0 insertions, 410 deletions
diff --git a/crypto/bn/stuff/wei_mulw.c b/crypto/bn/stuff/wei_mulw.c deleted file mode 100644 index 7f8a1e58fe..0000000000 --- a/crypto/bn/stuff/wei_mulw.c +++ /dev/null @@ -1,410 +0,0 @@ -/* crypto/bn/wei_mulw.c */ - -#include <stdio.h> -#include "cryptlib.h" -#include "bn.h" -#include "bn_lcl.h" - -BN_ULONG bn_add_word(BN_ULONG *a,BN_ULONG c,int num); -BN_ULONG bn_add_words(BN_ULONG *ret,BN_ULONG *a,BN_ULONG *b,int num); -BN_ULONG bn_sub_words(BN_ULONG *ret,BN_ULONG *a,BN_ULONG *b,int num); - -void BN_mul_4words(BN_ULONG *ret,BN_ULONG a0,BN_ULONG a1, - BN_ULONG b0,BN_ULONG b1); - -void pr(a,n,s) -BN_ULONG *a; -int n; - { - while (n--) - fprintf(stdout,"%02X",a[n]); - fprintf(stdout,"%s",s); - } - - -BN_ULONG bn_add_word(a,w,num) -BN_ULONG *a; -BN_ULONG w; -int num; - { - BN_ULONG t; - -#ifdef DEBUG -{ BN_ULONG *aa=a; int i; for (i=num; i>0; i--) fprintf(stdout,"%02X",aa[i-1]); -fprintf(stdout," + %X - ",w); i=num; -#endif - -loop: - t= *a; - t=(t+w)&BN_MASK2; - *(a++)=t; - w=(t < w); - if (w && --num) goto loop; - -#ifdef DEBUG -for (; i>0; i--) fprintf(stdout,"%02X",aa[i-1]); -fprintf(stdout,"\n"); -} -#endif - - return(w); - } - -BN_ULONG bn_add_words(r,a,b,num) -BN_ULONG *r; -BN_ULONG *a; -BN_ULONG *b; -int num; - { -#if defined(BN_LLONG) - BN_ULLONG t; - BN_ULONG c=0; - int i; - - if (num&1) abort(); - - for (i=0; i<num; i+=2) - { - t=(BN_ULLONG)a[i]+b[i]+c; - r[i+0]=L(t); - t=(BN_ULLONG) H(t)+a[i+1]+b[i+1]; - r[i+1]=L(t); - c=H(t); - } - return(c); -#else - BN_ULONG c=0,t1,t2; - - for ( ; num; num--) - { - t1= *(a++); - t2= *(b++); - - if (c) - { - c=(t2 >= ((~t1)&BN_MASK2)); - (*r++)=(t1+t2+1)&BN_MASK2; - } - else - { - t2=(t1+t2)&BN_MASK2; - c=(t2 < t1); - (*r++)=t2; - } - } - return(c); -#endif - } - -BN_ULONG bn_sub_words(r,a,b,num) -BN_ULONG *r; -BN_ULONG *a; -BN_ULONG *b; -int num; - { -#if defined(BN_LLONG) - BN_ULLONG t; - BN_ULONG c=0; - int i; - - if (num&1) abort(); - - for (i=0; i<num; i+=2) - { - t=(BN_ULLONG)a[i]-b[i]-c; - r[i+0]=L(t); - t=(BN_ULLONG)a[i+1]-b[i+1]-(0-H(t))&BN_MASK2; - r[i+1]=L(t); - c=H(t); - } - return(c); -#else - BN_ULONG c=0,t1,t2; - - for ( ; num; num--) - { - t1= *(a++); - t2= *(b++); - - if (c) - { - c=(t1 <= t2); - t1=(t1-t2-1); - } - else - { - c=(t1 < t2); - t1=(t1-t2); - } - (*r++)=t1&BN_MASK2; - } - return(c); -#endif - } - - -/* ret[3,2,1,0] = a1,a0 * b1,b0 */ -void BN_mul_4words(ret,a0,a1,b0,b1) -BN_ULONG *ret; -BN_ULONG a0,a1,b0,b1; - { - BN_ULONG s,u; - BN_ULLONG fix,a0b0,a1b1,tmp; - - if (a1 >= a0) - { - s=(a1-a0); - u=(b0-b1); - fix=(BN_ULLONG)s*u; - if (b0 >= b1) s=0; - } - else - { - BN_ULONG u; - - if (b0 > b1) - { - s=(b0-b1); - u=(a1-a0); - fix=(BN_ULLONG)s*u; - } - else - { - u=(a0-a1); - s=(b1-b0); - fix=(BN_ULLONG)s*u; - s=0; - } - } - - a0b0=(BN_ULLONG)a0*b0; - ret[0]=L(a0b0); - - a1b1=(BN_ULLONG)a1*b1; - tmp=(BN_ULLONG) H(a0b0) + L(a0b0) + L(fix) + L(a1b1); - ret[1]=L(tmp); - - tmp=(BN_ULLONG) a1b1 + H(tmp) + H(a0b0) + H(fix) + H(a1b1) - s; - ret[2]=L(tmp); - ret[3]=H(tmp); - } - -/* ret[3,2,1,0] += a1,a0 * b1,b0 */ -BN_ULONG BN_mul_add_4words(ret,a0,a1,b0,b1) -BN_ULONG *ret; -BN_ULONG a0,a1,b0,b1; - { - BN_ULONG s,u; - BN_ULLONG fix,a0b0,a1b1,tmp; - -#ifdef DEBUG -fprintf(stdout,"%02X%02X%02X%02X",ret[3],ret[2],ret[1],ret[0]); -fprintf(stdout," + ( %02X%02X * %02X%02X ) - ",a1,a0,b1,b0); -#endif - if (a1 >= a0) - { - s=(a1-a0); - u=(b0-b1); - fix=(BN_ULLONG)s*u; - if (b0 >= b1) s=0; - } - else - { - if (b0 > b1) - { - s=(b0-b1); - u=(a1-a0); - fix=(BN_ULLONG)s*u; - } - else - { - u=(a0-a1); - s=(b1-b0); - fix=(BN_ULLONG)s*u; - s=0; - } - } - - a0b0=(BN_ULLONG)a0*b0; - tmp=a0b0+ret[0]; - ret[0]=L(tmp); - - a1b1=(BN_ULLONG)a1*b1; - tmp=(BN_ULLONG) H(tmp) + L(a0b0) + L(fix) + L(a1b1) + ret[1]; - ret[1]=L(tmp); - - tmp=(BN_ULLONG) H(tmp) + L(a1b1) + H(a0b0) + - H(fix) + H(a1b1) -s + ret[2]; - ret[2]=L(tmp); - - tmp=(BN_ULLONG) H(tmp) + H(a1b1) + ret[3]; - ret[3]=L(tmp); -#ifdef DEBUG -fprintf(stdout,"%02X%02X%02X%02X%02X\n",H(tmp),ret[3],ret[2],ret[1],ret[0]); -#endif - return(H(tmp)); - } - -/* ret[3,2,1,0] += a1,a0 * a1,a0 */ -void BN_sqr_4words(ret,a0,a1) -BN_ULONG *ret; -BN_ULONG a0,a1; - { - BN_ULONG s,u; - BN_ULLONG tmp,tmp2; - - tmp=(BN_ULLONG)a0*a0; - ret[0]=L(tmp); - - tmp2=(BN_ULLONG)a0*a1; - tmp=(BN_ULLONG)H(tmp)+L(tmp2)*2; - ret[1]=L(tmp); - - tmp=(BN_ULLONG)a1*a1+H(tmp)+H(tmp2)*2; - ret[2]=L(tmp); - ret[3]=L(tmp); - } - -#define N0 (0) -#define N1 (half) -#define N2 (num) -#define N3 (num+half) - -#define word_cmp(r,a,b,num) \ - { \ - int n=num; \ -\ - (r)=0; \ - while (n--) \ - { \ - if ((a)[(n)] > (b)[(n)]) \ - { (r)=1; break; } \ - else if ((a)[(n)] < (b)[(n)]) \ - { (r)= -1; break; } \ - } \ - } - - -/* (a->top == b->top) && (a->top >= 2) && !(a->top & 1) */ -void bn_recursize_mul(r,t,a,b,num) -BN_ULONG *r,*t,*a,*b; -int num; - { - if ((num < 2) || (num&1)) - abort(); - -/* fprintf(stderr,"num=%d half=%d\n",num,num/2);*/ - if (num == 2) - BN_mul_4words(r,a[0],a[1],b[0],b[1]); - else if (num == 4) - { - BN_ULONG c,tmp; - - BN_mul_4words(&(r[0]),a[0],a[1],b[0],b[1]); - BN_mul_4words(&(r[4]),a[2],a[3],b[2],b[3]); - - c =BN_mul_add_4words(&(r[2]),a[0],a[1],b[2],b[3]); - c+=BN_mul_add_4words(&(r[2]),a[2],a[3],b[0],b[1]); - - bn_add_word(&(r[6]),c,2); - } - else - { - int half=num/2; - int carry,cmp_a,cmp_b; - - word_cmp(cmp_a,&(a[0]),&(a[half]),half); - word_cmp(cmp_b,&(b[0]),&(b[half]),half); - - switch (cmp_a*2+cmp_a+cmp_b) - { - case -4: - bn_sub_words(&(t[N0]),&(a[N1]),&(a[N0]),half); - bn_sub_words(&(t[N1]),&(b[N0]),&(b[N1]),half); - bn_recursize_mul(&(r[N1]),&(t[N2]), - &(t[N0]),&(t[N1]),half); - bn_sub_words(&(r[N2]),&(r[N2]),&(t[N0]),half); - carry= -1; - break; - case -2: - bn_sub_words(&(t[N0]),&(a[N1]),&(a[N0]),half); - bn_sub_words(&(t[N1]),&(b[N0]),&(b[N1]),half); - bn_recursize_mul(&(r[N1]),&(t[N2]), - &(t[N0]),&(t[N1]),half); - carry=0; - break; - case 2: - bn_sub_words(&(t[N0]),&(a[N0]),&(a[N1]),half); - bn_sub_words(&(t[N1]),&(b[N1]),&(b[N0]),half); - bn_recursize_mul(&(r[N1]),&(t[N2]), - &(t[N0]),&(t[N1]),half); - carry=0; - break; - case 4: - bn_sub_words(&(t[N0]),&(a[N1]),&(a[N0]),half); - bn_sub_words(&(t[N1]),&(b[N0]),&(b[N1]),half); - bn_recursize_mul(&(r[N1]),&(t[N2]), - &(t[N0]),&(t[N1]),half); - bn_sub_words(&(r[N2]),&(r[N2]),&(t[N1]),half); - carry= -1; - break; - default: - memset(&(r[N1]),0,sizeof(BN_ULONG)*num); - break; - } - - bn_recursize_mul(&(t[N0]),&(t[N2]),&(a[N0]),&(b[N0]),half); -#ifdef DEBUG - pr(a,half," * "); - pr(b,half," - "); - pr(t,num," - 0\n"); -#endif - memcpy(&(r[N0]),&(t[N0]),half*sizeof(BN_ULONG)); - if (bn_add_words(&(r[N1]),&(r[N1]),&(t[N1]),half)) - { bn_add_word(&(t[N1]),1,half); } - - carry+=bn_add_words(&(r[N1]),&(r[N1]),&(t[N0]),num); - - bn_recursize_mul(&(t[N0]),&(t[N2]),&(a[N1]),&(b[N1]),half); - - carry+=bn_add_words(&(r[N1]),&(r[N1]),&(t[N0]),num); - carry+=bn_add_words(&(r[N2]),&(r[N2]),&(t[N0]),half); - memcpy(&(r[N3]),&(t[N1]),half*sizeof(BN_ULONG)); - - bn_add_word(&(r[N3]),carry,half); - } - } - -main() - { - BIGNUM *a,*b,*r,*t; - int i,j; - - a=BN_new(); - b=BN_new(); - r=BN_new(); - t=BN_new(); - -#define BITS 1024 - bn_expand(r,BITS*2); - bn_expand(t,BITS*2); - fprintf(stdout,"obase=16\n"); - fprintf(stdout,"ibase=16\n"); - for (i=0; i<10; i++) - { - BN_rand(a,BITS,0,0); - BN_rand(b,BITS,0,0); - r->top=(BITS*2)/BN_BITS2; - memset(r->d,0,sizeof(r->top)*sizeof(BN_ULONG)); - memset(t->d,0,sizeof(r->top)*sizeof(BN_ULONG)); - for (j=0; j<1000; j++) - { - -/* BN_mul(r,a,b); /**/ - bn_recursize_mul(r->d,t->d,a->d,b->d,a->top); /**/ - } - BN_print(stdout,a); fprintf(stdout," * "); - BN_print(stdout,b); fprintf(stdout," - "); - BN_print(stdout,r); fprintf(stdout,"\n"); - } - } |