aboutsummaryrefslogtreecommitdiffstats
path: root/crypto/bn/stuff/wei_mulw.c
diff options
context:
space:
mode:
Diffstat (limited to 'crypto/bn/stuff/wei_mulw.c')
-rw-r--r--crypto/bn/stuff/wei_mulw.c410
1 files changed, 410 insertions, 0 deletions
diff --git a/crypto/bn/stuff/wei_mulw.c b/crypto/bn/stuff/wei_mulw.c
new file mode 100644
index 0000000000..7f8a1e58fe
--- /dev/null
+++ b/crypto/bn/stuff/wei_mulw.c
@@ -0,0 +1,410 @@
+/* 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");
+ }
+ }
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-14 00:57:39 +0000