diff options
Diffstat (limited to 'crypto/bn/stuff/div.c')
| -rw-r--r-- | crypto/bn/stuff/div.c | 340 |
1 files changed, 340 insertions, 0 deletions
diff --git a/crypto/bn/stuff/div.c b/crypto/bn/stuff/div.c new file mode 100644 index 0000000000..3d6e08622d --- /dev/null +++ b/crypto/bn/stuff/div.c @@ -0,0 +1,340 @@ +/* crypto/bn/div.c */ + +#include <stdio.h> +#include "cryptlib.h" +#include "bn.h" + +BN_ULONG bn_div_2word(); + +int BN_div2(dv, rm, num, div,ctx) +BIGNUM *dv; +BIGNUM *rm; +BIGNUM *num; +BIGNUM *div; +BN_CTX *ctx; + { + int norm_shift,i,j,nm,nd,loop; + BIGNUM *tmp,wnum,*snum,*sdiv,*res; + BN_ULONG *resp,*wnump; + BN_ULONG d0,d1; + int num_n,div_n; + +#ifdef DEBUG +BN_print(stdout,num); printf(" number\n"); +BN_print(stdout,div); printf(" divisor\n"); +#endif + if (BN_is_zero(num)) + { + BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO); + return(0); + } + + if (BN_cmp(num,div) < 0) + { + if (rm != NULL) + { if (BN_copy(rm,num) == NULL) return(0); } + if (dv != NULL) BN_zero(dv); + return(1); + } + + tmp=ctx->bn[ctx->tos]; + snum=ctx->bn[ctx->tos+1]; + sdiv=ctx->bn[ctx->tos+2]; + if (dv == NULL) + res=ctx->bn[ctx->tos+3]; + else res=dv; + + /* First we normalise the numbers */ + norm_shift=BN_BITS2-((BN_num_bits(div))%BN_BITS2); + BN_lshift(sdiv,div,norm_shift); + norm_shift+=BN_BITS2; + BN_lshift(snum,num,norm_shift); + div_n=sdiv->top; + num_n=snum->top; + loop=num_n-div_n; +#ifdef DEBUG +BN_print(stdout,snum); printf(" shifted num, forget last word\n"); +BN_print(stdout,sdiv); printf(" shifted div\n"); +#endif + + /* Lets setup a 'win'dow into snum + * This is the part that corresponds to the current + * 'area' being divided */ + wnum.d= &(snum->d[loop]); + wnum.top= div_n; + wnum.max= snum->max; /* a bit of a lie */ + wnum.neg= 0; + + /* Get the top 2 words of sdiv */ + i=sdiv->top; + d0=sdiv->d[div_n-1]; + d1=sdiv->d[div_n-2]; + + /* pointer to the 'top' of snum */ + wnump= &(snum->d[num_n-1]); + + /* Setup to 'res' */ + res->neg=0; + res->top=loop; + resp= &(res->d[loop-1]); + bn_expand(res,(loop+1)*BN_BITS2); + + /* space for temp */ + bn_expand(tmp,(div_n+1)*BN_BITS2); + +#ifdef DEBUG +printf("wnum="); BN_print(stdout,&wnum); printf(" initial sub check\n"); +printf("div ="); BN_print(stdout,sdiv); printf(" loop=%d\n",loop); +#endif + if (BN_cmp(&wnum,sdiv) >= 0) + { + BN_sub(&wnum,&wnum,sdiv); + *resp=1; + res->d[res->top-1]=1; + } + else + res->top--; + resp--; +#ifdef DEBUG +BN_print(stdout,res); printf(" initial result\n"); +BN_print(stdout,&wnum); printf(" wnum\n"); +#endif + + for (i=0; i<loop-1; i++) + { + BN_ULONG q,n0; + BN_ULLONG t1,t2,t3; + BN_ULONG l0; + + wnum.d--; + wnum.top++; + +#ifdef DEBUG +BN_print(stderr,&wnum); printf(" to divide\n"); +#endif + + q=0; + n0=wnump[0]; + t1=((BN_ULLONG)n0<<BN_BITS2)|wnump[-1]; + if (n0 == d0) + q=BN_MASK2; + else + { + t2=(t1/d0); + q=(t2&BN_MASK2); +#ifdef DEBUG +printf("t1=%08X / d0=%08X = %X (%X)\n",t1,d0,q,t2); +#endif + } + for (;;) + { + t2=(BN_ULLONG)d1*q; + t3=t1-(BN_ULLONG)q*d0; +#ifdef DEBUG +printf("d1*q= %X n01-q*d0 = %X\n",t2,t3); +#endif + if ((t3>>BN_BITS2) || + (t2 <= ((t3<<BN_BITS2)+wnump[-2]))) + break; +#ifdef DEBUG +printf("reduce q\n"); +#endif + q--; + } + l0=bn_mul_word(tmp->d,sdiv->d,div_n,q); + if (l0) + tmp->d[div_n]=l0; + else + tmp->d[div_n]=0; + for (j=div_n+1; j>0; j--) + if (tmp->d[j-1]) break; + tmp->top=j; + +#ifdef DEBUG +printf("q=%08X\n",q); +BN_print(stdout,&wnum); printf(" number\n"); +BN_print(stdout,tmp); printf(" subtract\n"); + +BN_print(stdout,snum); printf(" shifted number before\n"); +BN_print(stdout,&wnum); printf(" wnum before\n"); +#endif + j=wnum.top; + BN_sub(&wnum,&wnum,tmp); + snum->top=snum->top+wnum.top-j; + +#ifdef DEBUG +BN_print(stdout,&wnum); printf(" wnum after\n"); +BN_print(stdout,snum); printf(" shifted number after\n"); +#endif + + if (wnum.neg) + { + q--; + j=wnum.top; + BN_add(&wnum,&wnum,sdiv); + snum->top+=wnum.top-j; + fprintf(stderr,"addback\n"); +#ifdef DEBUG +BN_print(stdout,snum); printf("after addback************************:\n"); +#endif + } + *(resp--)=q; +#ifdef DEBUG +BN_print(stdout,res); printf(" result\n"); +#endif + wnump--; + } + if (rm != NULL) + BN_rshift(rm,snum,norm_shift); + return(1); + } + +main() + { + BIGNUM *a,*b,*c,*d; + BIGNUM *cc,*dd; + BN_CTX *ctx; + int i,x; + + a=BN_new(); + b=BN_new(); + c=BN_new(); + d=BN_new(); + cc=BN_new(); + dd=BN_new(); + ctx=BN_CTX_new(); + +for (i=0; i<10240; i++) + { + BN_rand(a,80,0,0); + BN_rand(b,60,0,0); + + BN_div2(d,c,a,b,ctx); + BN_div(dd,cc,a,b,ctx); + if ((BN_cmp(d,dd) != 0) || (BN_cmp(c,cc) != 0)) + { + BN_print(stderr,a); fprintf(stderr," / "); + BN_print(stderr,b); fprintf(stderr," d="); + BN_print(stderr,d); fprintf(stderr," r= "); + BN_print(stderr,c); fprintf(stderr,"\nd="); + BN_print(stderr,dd); fprintf(stderr," r= "); + BN_print(stderr,cc); fprintf(stderr,"\n"); + } + + } + +#ifdef undef +/* + BN_rand(a,600,0,0); + BN_rand(b,400,0,0); + for (i=0; i<2000000; i++) + { + BN_div2(d,c,a,b,ctx); + } +*/ +/* for (i=0;;) */ +/* for (i=0; i<0xffffffff; i++) + { + BN_ULONG rr,r,a,b,c; + BN_ULLONG l; + + a=rand()&BN_MASK2; + b=rand()&BN_MASK2; + for (;;) + { + c=rand()&BN_MASK2; + if (c) break; + } +/* for (x=1; x<256*256; x++) */ + { + c=x; + a=i>>8; + b=i&0xff; + a&= ~(0xFFFFFF<<(BN_num_bits_word(c))); + + r=bn_div_2word(a,b,c); + + rr=(BN_ULONG)((((BN_ULLONG)a<<BN_BITS2)|b)/c); + + if ((i & 0xfffff) == 0) fprintf(stderr,"%d\n",i,r,rr); +/*if (x == 255) + fprintf(stderr,"%6d/%3d = %4d %4d\n",(a<<8)|b,c,r,rr); */ + if (rr != r) + { + fprintf(stderr,"%8d %02X%02X / %02X = %02X %02X\n", + i,a,b,c,rr,r); + abort(); + } + } + } +#endif + } + +/* Divide h-l by d and return the result. */ +BN_ULONG bn_div_2word(l,h,d) +BN_ULONG l,h,d; + { + BN_ULONG dh,dl,q,ret=0,th,tl,t,top; + int i,count=2; + + if (d == 0) return(-1); + + i=BN_num_bits_word(d); + if ((i != BN_BITS2) && (h > 1<<i)) + { + fprintf(stderr,"Division would overflow\n"); + abort(); + } + i=BN_BITS2-i; + if (h >= d) h-=d; + + if (i) + { + d<<=i; + h=(h<<i)|(l>>(BN_BITS2-i)); + l<<=i; + } + dh=(d&BN_MASK2h)>>BN_BITS4; + dl=(d&BN_MASK2l); + for (;;) + { + if ((h>>BN_BITS4) == dh) + q=BN_MASK2l; + else + q=h/dh; + + for (;;) + { + t=(h-q*dh); + if ((t&BN_MASK2h) || + ((dl*q) <= ( + (t<<BN_BITS4)+ + ((l&BN_MASK2h)>>BN_BITS4)))) + break; + q--; + } + th=q*dh; + tl=q*dl; + t=(tl>>BN_BITS4); + tl=(tl<<BN_BITS4)&BN_MASK2h; + th+=t; + + if (l < tl) th++; + l-=tl; + if (h < th) + { + fprintf(stderr,"add back\n"); + h+=d; + q--; + } + h-=th; + + if (--count == 0) break; + + ret=q<<BN_BITS4; + h=((h<<BN_BITS4)|(l>>BN_BITS4))&BN_MASK2; + l=(l&BN_MASK2l)<<BN_BITS4; + } + ret|=q; + return(ret); + } |