X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fbn_div.c;h=580d1201bc253f7257f0abdd0be5497dac45922e;hp=3505221a9667c2f1200ecf61d4aba32c3b83ef62;hb=3c801fa4603e0bb1efa6f33c540605ba14c4ec60;hpb=9b141126d4b6f0636bc047e81b846c193ae26611 diff --git a/crypto/bn/bn_div.c b/crypto/bn/bn_div.c index 3505221a96..580d1201bc 100644 --- a/crypto/bn/bn_div.c +++ b/crypto/bn/bn_div.c @@ -61,8 +61,9 @@ #include "cryptlib.h" #include "bn_lcl.h" + /* The old slow way */ -#if 1 +#if 0 int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) { @@ -126,6 +127,55 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, #else +#if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ + && !defined(PEDANTIC) && !defined(BN_DIV3W) +# if defined(__GNUC__) && __GNUC__>=2 +# if defined(__i386) || defined (__i386__) + /* + * There were two reasons for implementing this template: + * - GNU C generates a call to a function (__udivdi3 to be exact) + * in reply to ((((BN_ULLONG)n0)< + */ +# define bn_div_words(n0,n1,d0) \ + ({ asm volatile ( \ + "divl %4" \ + : "=a"(q), "=d"(rem) \ + : "a"(n1), "d"(n0), "g"(d0) \ + : "cc"); \ + q; \ + }) +# define REMAINDER_IS_ALREADY_CALCULATED +# elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG) + /* + * Same story here, but it's 128-bit by 64-bit division. Wow! + * + */ +# define bn_div_words(n0,n1,d0) \ + ({ asm volatile ( \ + "divq %4" \ + : "=a"(q), "=d"(rem) \ + : "a"(n1), "d"(n0), "g"(d0) \ + : "cc"); \ + q; \ + }) +# define REMAINDER_IS_ALREADY_CALCULATED +# endif /* __ */ +# endif /* __GNUC__ */ +#endif /* OPENSSL_NO_ASM */ + + +/* BN_div computes dv := num / divisor, rounding towards zero, and sets up + * rm such that dv*divisor + rm = num holds. + * Thus: + * dv->neg == num->neg ^ divisor->neg (unless the result is zero) + * rm->neg == num->neg (unless the remainder is zero) + * If 'dv' or 'rm' is NULL, the respective value is not returned. + */ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx) { @@ -154,20 +204,20 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX_start(ctx); tmp=BN_CTX_get(ctx); - tmp->neg=0; snum=BN_CTX_get(ctx); sdiv=BN_CTX_get(ctx); if (dv == NULL) res=BN_CTX_get(ctx); else res=dv; - if (res == NULL) goto err; + if (sdiv == NULL || res == NULL) goto err; + tmp->neg=0; /* First we normalise the numbers */ norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); - BN_lshift(sdiv,divisor,norm_shift); + if (!(BN_lshift(sdiv,divisor,norm_shift))) goto err; sdiv->neg=0; norm_shift+=BN_BITS2; - BN_lshift(snum,num,norm_shift); + if (!(BN_lshift(snum,num,norm_shift))) goto err; snum->neg=0; div_n=sdiv->top; num_n=snum->top; @@ -179,7 +229,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_init(&wnum); wnum.d= &(snum->d[loop]); wnum.top= div_n; - wnum.max= snum->max+1; /* a bit of a lie */ + wnum.dmax= snum->dmax+1; /* a bit of a lie */ /* Get the top 2 words of sdiv */ /* i=sdiv->top; */ @@ -206,111 +256,95 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, } else res->top--; + if (res->top == 0) + res->neg = 0; resp--; for (i=0; i=2 -# if defined(__i386) - /* - * There were two reasons for implementing this template: - * - GNU C generates a call to a function (__udivdi3 to be exact) - * in reply to ((((BN_ULLONG)n0)< - */ -# define bn_div_words(n0,n1,d0) \ - ({ asm volatile ( \ - "divl %4" \ - : "=a"(q), "=d"(rem) \ - : "a"(n1), "d"(n0), "g"(d0) \ - : "cc"); \ - q; \ - }) -# define REMAINDER_IS_ALREADY_CALCULATED -# endif /* __ */ -# endif /* __GNUC__ */ -#endif /* NO_ASM */ BN_ULONG n0,n1,rem=0; n0=wnump[0]; n1=wnump[-1]; if (n0 == d0) - { q=BN_MASK2; -#ifdef REMAINDER_IS_ALREADY_CALCULATED /* in this case it isn't */ - rem=(n1-q*d0)&BN_MASK2; -#endif - } - else /* n0 < d0 */ + else /* n0 < d0 */ + { +#ifdef BN_LLONG + BN_ULLONG t2; + #if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) q=(BN_ULONG)(((((BN_ULLONG)n0)< 0x%08X\n", + n0, n1, d0, q); +#endif #endif - { -#ifdef BN_LLONG - BN_ULLONG t2; #ifndef REMAINDER_IS_ALREADY_CALCULATED - /* - * rem doesn't have to be BN_ULLONG. The least we - * know it's less that d0, isn't it? - */ - rem=(n1-q*d0)&BN_MASK2; + /* + * rem doesn't have to be BN_ULLONG. The least we + * know it's less that d0, isn't it? + */ + rem=(n1-q*d0)&BN_MASK2; #endif - t2=(BN_ULLONG)d1*q; - - for (;;) - { - if (t2 <= ((((BN_ULLONG)rem)< 0x%08X\n", + n0, n1, d0, q); +#endif #ifndef REMAINDER_IS_ALREADY_CALCULATED - /* - * It's more than enough with the only multiplication. - * See the comment above in BN_LLONG section... - */ - rem=(n1-q*d0)&BN_MASK2; + rem=(n1-q*d0)&BN_MASK2; #endif -#ifdef BN_UMULT_HIGH - t2l = d1 * q; - t2h = BN_UMULT_HIGH(d1,q); + +#if defined(BN_UMULT_LOHI) + BN_UMULT_LOHI(t2l,t2h,d1,q); +#elif defined(BN_UMULT_HIGH) + t2l = d1 * q; + t2h = BN_UMULT_HIGH(d1,q); #else - t2l=LBITS(d1); t2h=HBITS(d1); - ql =LBITS(q); qh =HBITS(q); - mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */ + t2l=LBITS(d1); t2h=HBITS(d1); + ql =LBITS(q); qh =HBITS(q); + mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */ #endif - for (;;) - { - if ((t2h < rem) || - ((t2h == rem) && (t2l <= wnump[-2]))) - break; - q--; - rem += d0; - if (rem < d0) break; /* don't let rem overflow */ - if (t2l < d1) t2h--; t2l -= d1; + for (;;) + { + if ((t2h < rem) || + ((t2h == rem) && (t2l <= wnump[-2]))) + break; + q--; + rem += d0; + if (rem < d0) break; /* don't let rem overflow */ + if (t2l < d1) t2h--; t2l -= d1; + } +#endif /* !BN_LLONG */ } -#endif - } #endif /* !BN_DIV3W */ + l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); wnum.d--; wnum.top++; tmp->d[div_n]=l0; @@ -319,7 +353,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, tmp->top=j; j=wnum.top; - BN_sub(&wnum,&wnum,tmp); + if (!BN_sub(&wnum,&wnum,tmp)) goto err; snum->top=snum->top+wnum.top-j; @@ -327,7 +361,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, { q--; j=wnum.top; - BN_add(&wnum,&wnum,sdiv); + if (!BN_add(&wnum,&wnum,sdiv)) goto err; snum->top+=wnum.top-j; } *(resp--)=q; @@ -335,51 +369,19 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, } if (rm != NULL) { + /* Keep a copy of the neg flag in num because if rm==num + * BN_rshift() will overwrite it. + */ + int neg = num->neg; BN_rshift(rm,snum,norm_shift); - rm->neg=num->neg; + if (!BN_is_zero(rm)) + rm->neg = neg; } BN_CTX_end(ctx); return(1); err: - BN_CX_end(ctx); - return(0); - } - -#endif - -/* rem != m */ -int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) - { -#if 0 /* The old slow way */ - int i,nm,nd; - BIGNUM *dv; - - if (BN_ucmp(m,d) < 0) - return((BN_copy(rem,m) == NULL)?0:1); - - BN_CTX_start(ctx); - dv=BN_CTX_get(ctx); - - if (!BN_copy(rem,m)) goto err; - - nm=BN_num_bits(rem); - nd=BN_num_bits(d); - if (!BN_lshift(dv,d,nm-nd)) goto err; - for (i=nm-nd; i>=0; i--) - { - if (BN_cmp(rem,dv) >= 0) - { - if (!BN_sub(rem,rem,dv)) goto err; - } - if (!BN_rshift1(dv,dv)) goto err; - } - BN_CTX_end(ctx); - return(1); - err: BN_CTX_end(ctx); return(0); -#else - return(BN_div(NULL,rem,m,d,ctx)); -#endif } +#endif