1 /* crypto/bn/bn_div.c */ 2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58 59 #include <stdio.h> 60 #include <openssl/bn.h> 61 #include "cryptlib.h" 62 #include "bn_lcl.h" 63 64 /* The old slow way */ 65 #if 0 66 int BN_div(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx) 67 { 68 int i,nm,nd; 69 BIGNUM *D; 70 71 bn_check_top(m); 72 bn_check_top(d); 73 if (BN_is_zero(d)) 74 { 75 BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO); 76 return(0); 77 } 78 79 if (BN_ucmp(m,d) < 0) 80 { 81 if (rem != NULL) 82 { if (BN_copy(rem,m) == NULL) return(0); } 83 if (dv != NULL) BN_zero(dv); 84 return(1); 85 } 86 87 D= &(ctx->bn[ctx->tos]); 88 if (dv == NULL) dv= &(ctx->bn[ctx->tos+1]); 89 if (rem == NULL) rem= &(ctx->bn[ctx->tos+2]); 90 91 nd=BN_num_bits(d); 92 nm=BN_num_bits(m); 93 if (BN_copy(D,d) == NULL) return(0); 94 if (BN_copy(rem,m) == NULL) return(0); 95 96 /* The next 2 are needed so we can do a dv->d[0]|=1 later 97 * since BN_lshift1 will only work once there is a value :-) */ 98 BN_zero(dv); 99 bn_wexpand(dv,1); 100 dv->top=1; 101 102 if (!BN_lshift(D,D,nm-nd)) return(0); 103 for (i=nm-nd; i>=0; i--) 104 { 105 if (!BN_lshift1(dv,dv)) return(0); 106 if (BN_ucmp(rem,D) >= 0) 107 { 108 dv->d[0]|=1; 109 if (!BN_usub(rem,rem,D)) return(0); 110 } 111 /* CAN IMPROVE (and have now :=) */ 112 if (!BN_rshift1(D,D)) return(0); 113 } 114 rem->neg=BN_is_zero(rem)?0:m->neg; 115 dv->neg=m->neg^d->neg; 116 return(1); 117 } 118 119 #else 120 121 int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 122 BN_CTX *ctx) 123 { 124 int norm_shift,i,j,loop; 125 BIGNUM *tmp,wnum,*snum,*sdiv,*res; 126 BN_ULONG *resp,*wnump; 127 BN_ULONG d0,d1; 128 int num_n,div_n; 129 130 bn_check_top(num); 131 bn_check_top(divisor); 132 133 if (BN_is_zero(divisor)) 134 { 135 BNerr(BN_F_BN_DIV,BN_R_DIV_BY_ZERO); 136 return(0); 137 } 138 139 if (BN_ucmp(num,divisor) < 0) 140 { 141 if (rm != NULL) 142 { if (BN_copy(rm,num) == NULL) return(0); } 143 if (dv != NULL) BN_zero(dv); 144 return(1); 145 } 146 147 tmp= &(ctx->bn[ctx->tos]); 148 tmp->neg=0; 149 snum= &(ctx->bn[ctx->tos+1]); 150 sdiv= &(ctx->bn[ctx->tos+2]); 151 if (dv == NULL) 152 res= &(ctx->bn[ctx->tos+3]); 153 else res=dv; 154 155 /* First we normalise the numbers */ 156 norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); 157 BN_lshift(sdiv,divisor,norm_shift); 158 sdiv->neg=0; 159 norm_shift+=BN_BITS2; 160 BN_lshift(snum,num,norm_shift); 161 snum->neg=0; 162 div_n=sdiv->top; 163 num_n=snum->top; 164 loop=num_n-div_n; 165 166 /* Lets setup a 'window' into snum 167 * This is the part that corresponds to the current 168 * 'area' being divided */ 169 BN_init(&wnum); 170 wnum.d= &(snum->d[loop]); 171 wnum.top= div_n; 172 wnum.max= snum->max+1; /* a bit of a lie */ 173 174 /* Get the top 2 words of sdiv */ 175 /* i=sdiv->top; */ 176 d0=sdiv->d[div_n-1]; 177 d1=(div_n == 1)?0:sdiv->d[div_n-2]; 178 179 /* pointer to the 'top' of snum */ 180 wnump= &(snum->d[num_n-1]); 181 182 /* Setup to 'res' */ 183 res->neg= (num->neg^divisor->neg); 184 if (!bn_wexpand(res,(loop+1))) goto err; 185 res->top=loop; 186 resp= &(res->d[loop-1]); 187 188 /* space for temp */ 189 if (!bn_wexpand(tmp,(div_n+1))) goto err; 190 191 if (BN_ucmp(&wnum,sdiv) >= 0) 192 { 193 if (!BN_usub(&wnum,&wnum,sdiv)) goto err; 194 *resp=1; 195 res->d[res->top-1]=1; 196 } 197 else 198 res->top--; 199 resp--; 200 201 for (i=0; i<loop-1; i++) 202 { 203 BN_ULONG q,l0; 204 #ifdef BN_DIV3W 205 q=bn_div_3_words(wnump,d0,d1); 206 #else 207 208 #if !defined(NO_ASM) && !defined(PEDANTIC) 209 # if defined(__GNUC__) && __GNUC__>=2 210 # if defined(__i386) 211 /* 212 * There were two reasons for implementing this template: 213 * - GNU C generates a call to a function (__udivdi3 to be exact) 214 * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to 215 * understand why...); 216 * - divl doesn't only calculate quotient, but also leaves 217 * remainder in %edx which we can definitely use here:-) 218 * 219 * <appro@fy.chalmers.se> 220 */ 221 # define bn_div_words(n0,n1,d0) \ 222 ({ asm volatile ( \ 223 "divl %4" \ 224 : "=a"(q), "=d"(rem) \ 225 : "a"(n1), "d"(n0), "g"(d0) \ 226 : "cc"); \ 227 q; \ 228 }) 229 # define REMINDER_IS_ALREADY_CALCULATED 230 # endif /* __<cpu> */ 231 # endif /* __GNUC__ */ 232 #endif /* NO_ASM */ 233 BN_ULONG n0,n1,rem=0; 234 235 n0=wnump[0]; 236 n1=wnump[-1]; 237 if (n0 == d0) 238 q=BN_MASK2; 239 else 240 #if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) 241 q=((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0; 242 #else 243 q=bn_div_words(n0,n1,d0); 244 #endif 245 { 246 #ifdef BN_LLONG 247 BN_ULLONG t2; 248 249 #ifndef REMINDER_IS_ALREADY_CALCULATED 250 /* 251 * rem doesn't have to be BN_ULLONG. The least we 252 * know it's less that d0, isn't it? 253 */ 254 rem=(n1-q*d0)&BN_MASK2; 255 #endif 256 t2=(BN_ULLONG)d1*q; 257 258 for (;;) 259 { 260 if (t2 <= ((((BN_ULLONG)rem)<<BN_BITS2)|wnump[-2])) 261 break; 262 q--; 263 rem += d0; 264 if (rem < d0) break; /* don't let rem overflow */ 265 t2 -= d1; 266 } 267 #else 268 BN_ULONG t2l,t2h,ql,qh; 269 270 #ifndef REMINDER_IS_ALREADY_CALCULATED 271 /* 272 * It's more than enough with the only multiplication. 273 * See the comment above in BN_LLONG section... 274 */ 275 rem=(n1-q*d0)&BN_MASK2; 276 #endif 277 t2l=LBITS(d1); t2h=HBITS(d1); 278 ql =LBITS(q); qh =HBITS(q); 279 mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */ 280 281 for (;;) 282 { 283 if ((t2h < rem) || 284 ((t2h == rem) && (t2l <= wnump[-2]))) 285 break; 286 q--; 287 rem += d0; 288 if (rem < d0) break; /* don't let rem overflow */ 289 if (t2l < d1) t2h--; t2l -= d1; 290 } 291 #endif 292 } 293 #endif /* !BN_DIV3W */ 294 wnum.d--; wnum.top++; 295 l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); 296 tmp->d[div_n]=l0; 297 for (j=div_n+1; j>0; j--) 298 if (tmp->d[j-1]) break; 299 tmp->top=j; 300 301 j=wnum.top; 302 BN_sub(&wnum,&wnum,tmp); 303 304 snum->top=snum->top+wnum.top-j; 305 306 if (wnum.neg) 307 { 308 q--; 309 j=wnum.top; 310 BN_add(&wnum,&wnum,sdiv); 311 snum->top+=wnum.top-j; 312 } 313 *(resp--)=q; 314 wnump--; 315 } 316 if (rm != NULL) 317 { 318 BN_rshift(rm,snum,norm_shift); 319 rm->neg=num->neg; 320 } 321 return(1); 322 err: 323 return(0); 324 } 325 326 #endif 327 328 /* rem != m */ 329 int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 330 { 331 #if 0 /* The old slow way */ 332 int i,nm,nd; 333 BIGNUM *dv; 334 335 if (BN_ucmp(m,d) < 0) 336 return((BN_copy(rem,m) == NULL)?0:1); 337 338 dv= &(ctx->bn[ctx->tos]); 339 340 if (!BN_copy(rem,m)) return(0); 341 342 nm=BN_num_bits(rem); 343 nd=BN_num_bits(d); 344 if (!BN_lshift(dv,d,nm-nd)) return(0); 345 for (i=nm-nd; i>=0; i--) 346 { 347 if (BN_cmp(rem,dv) >= 0) 348 { 349 if (!BN_sub(rem,rem,dv)) return(0); 350 } 351 if (!BN_rshift1(dv,dv)) return(0); 352 } 353 return(1); 354 #else 355 return(BN_div(NULL,rem,m,d,ctx)); 356 #endif 357 } 358 359