summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_div.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_div.c')
-rw-r--r--src/lib/libcrypto/bn/bn_div.c206
1 files changed, 114 insertions, 92 deletions
diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c
index 150dd289a5..07af1d3b44 100644
--- a/src/lib/libcrypto/bn/bn_div.c
+++ b/src/lib/libcrypto/bn/bn_div.c
@@ -63,9 +63,11 @@
63 63
64/* The old slow way */ 64/* The old slow way */
65#if 0 65#if 0
66int BN_div(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx) 66int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d,
67 BN_CTX *ctx)
67 { 68 {
68 int i,nm,nd; 69 int i,nm,nd;
70 int ret = 0;
69 BIGNUM *D; 71 BIGNUM *D;
70 72
71 bn_check_top(m); 73 bn_check_top(m);
@@ -84,14 +86,17 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx)
84 return(1); 86 return(1);
85 } 87 }
86 88
87 D= &(ctx->bn[ctx->tos]); 89 BN_CTX_start(ctx);
88 if (dv == NULL) dv= &(ctx->bn[ctx->tos+1]); 90 D = BN_CTX_get(ctx);
89 if (rem == NULL) rem= &(ctx->bn[ctx->tos+2]); 91 if (dv == NULL) dv = BN_CTX_get(ctx);
92 if (rem == NULL) rem = BN_CTX_get(ctx);
93 if (D == NULL || dv == NULL || rem == NULL)
94 goto end;
90 95
91 nd=BN_num_bits(d); 96 nd=BN_num_bits(d);
92 nm=BN_num_bits(m); 97 nm=BN_num_bits(m);
93 if (BN_copy(D,d) == NULL) return(0); 98 if (BN_copy(D,d) == NULL) goto end;
94 if (BN_copy(rem,m) == NULL) return(0); 99 if (BN_copy(rem,m) == NULL) goto end;
95 100
96 /* The next 2 are needed so we can do a dv->d[0]|=1 later 101 /* 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 :-) */ 102 * since BN_lshift1 will only work once there is a value :-) */
@@ -99,25 +104,54 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BIGNUM *d, BN_CTX *ctx)
99 bn_wexpand(dv,1); 104 bn_wexpand(dv,1);
100 dv->top=1; 105 dv->top=1;
101 106
102 if (!BN_lshift(D,D,nm-nd)) return(0); 107 if (!BN_lshift(D,D,nm-nd)) goto end;
103 for (i=nm-nd; i>=0; i--) 108 for (i=nm-nd; i>=0; i--)
104 { 109 {
105 if (!BN_lshift1(dv,dv)) return(0); 110 if (!BN_lshift1(dv,dv)) goto end;
106 if (BN_ucmp(rem,D) >= 0) 111 if (BN_ucmp(rem,D) >= 0)
107 { 112 {
108 dv->d[0]|=1; 113 dv->d[0]|=1;
109 if (!BN_usub(rem,rem,D)) return(0); 114 if (!BN_usub(rem,rem,D)) goto end;
110 } 115 }
111/* CAN IMPROVE (and have now :=) */ 116/* CAN IMPROVE (and have now :=) */
112 if (!BN_rshift1(D,D)) return(0); 117 if (!BN_rshift1(D,D)) goto end;
113 } 118 }
114 rem->neg=BN_is_zero(rem)?0:m->neg; 119 rem->neg=BN_is_zero(rem)?0:m->neg;
115 dv->neg=m->neg^d->neg; 120 dv->neg=m->neg^d->neg;
116 return(1); 121 ret = 1;
122 end:
123 BN_CTX_end(ctx);
124 return(ret);
117 } 125 }
118 126
119#else 127#else
120 128
129#if !defined(NO_ASM) && !defined(NO_INLINE_ASM) && !defined(PEDANTIC) && !defined(BN_DIV3W)
130# if defined(__GNUC__) && __GNUC__>=2
131# if defined(__i386)
132 /*
133 * There were two reasons for implementing this template:
134 * - GNU C generates a call to a function (__udivdi3 to be exact)
135 * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to
136 * understand why...);
137 * - divl doesn't only calculate quotient, but also leaves
138 * remainder in %edx which we can definitely use here:-)
139 *
140 * <appro@fy.chalmers.se>
141 */
142# define bn_div_words(n0,n1,d0) \
143 ({ asm volatile ( \
144 "divl %4" \
145 : "=a"(q), "=d"(rem) \
146 : "a"(n1), "d"(n0), "g"(d0) \
147 : "cc"); \
148 q; \
149 })
150# define REMAINDER_IS_ALREADY_CALCULATED
151# endif /* __<cpu> */
152# endif /* __GNUC__ */
153#endif /* NO_ASM */
154
121int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 155int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
122 BN_CTX *ctx) 156 BN_CTX *ctx)
123 { 157 {
@@ -144,13 +178,15 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
144 return(1); 178 return(1);
145 } 179 }
146 180
147 tmp= &(ctx->bn[ctx->tos]); 181 BN_CTX_start(ctx);
182 tmp=BN_CTX_get(ctx);
148 tmp->neg=0; 183 tmp->neg=0;
149 snum= &(ctx->bn[ctx->tos+1]); 184 snum=BN_CTX_get(ctx);
150 sdiv= &(ctx->bn[ctx->tos+2]); 185 sdiv=BN_CTX_get(ctx);
151 if (dv == NULL) 186 if (dv == NULL)
152 res= &(ctx->bn[ctx->tos+3]); 187 res=BN_CTX_get(ctx);
153 else res=dv; 188 else res=dv;
189 if (res == NULL) goto err;
154 190
155 /* First we normalise the numbers */ 191 /* First we normalise the numbers */
156 norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2); 192 norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
@@ -202,97 +238,76 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
202 { 238 {
203 BN_ULONG q,l0; 239 BN_ULONG q,l0;
204#ifdef BN_DIV3W 240#ifdef BN_DIV3W
205 q=bn_div_3_words(wnump,d0,d1); 241 q=bn_div_3_words(wnump,d1,d0);
206#else 242#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; 243 BN_ULONG n0,n1,rem=0;
234 244
235 n0=wnump[0]; 245 n0=wnump[0];
236 n1=wnump[-1]; 246 n1=wnump[-1];
237 if (n0 == d0) 247 if (n0 == d0)
238 q=BN_MASK2; 248 q=BN_MASK2;
239 else 249 else /* n0 < d0 */
250 {
251#ifdef BN_LLONG
252 BN_ULLONG t2;
253
240#if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) 254#if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words)
241 q=((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0; 255 q=(BN_ULONG)(((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0);
242#else 256#else
243 q=bn_div_words(n0,n1,d0); 257 q=bn_div_words(n0,n1,d0);
244#endif 258#endif
245 { 259
246#ifdef BN_LLONG 260#ifndef REMAINDER_IS_ALREADY_CALCULATED
247 BN_ULLONG t2; 261 /*
248 262 * rem doesn't have to be BN_ULLONG. The least we
249#ifndef REMINDER_IS_ALREADY_CALCULATED 263 * know it's less that d0, isn't it?
250 /* 264 */
251 * rem doesn't have to be BN_ULLONG. The least we 265 rem=(n1-q*d0)&BN_MASK2;
252 * know it's less that d0, isn't it?
253 */
254 rem=(n1-q*d0)&BN_MASK2;
255#endif 266#endif
256 t2=(BN_ULLONG)d1*q; 267 t2=(BN_ULLONG)d1*q;
268
269 for (;;)
270 {
271 if (t2 <= ((((BN_ULLONG)rem)<<BN_BITS2)|wnump[-2]))
272 break;
273 q--;
274 rem += d0;
275 if (rem < d0) break; /* don't let rem overflow */
276 t2 -= d1;
277 }
278#else /* !BN_LLONG */
279 BN_ULONG t2l,t2h,ql,qh;
257 280
258 for (;;) 281 q=bn_div_words(n0,n1,d0);
259 { 282#ifndef REMAINDER_IS_ALREADY_CALCULATED
260 if (t2 <= ((((BN_ULLONG)rem)<<BN_BITS2)|wnump[-2])) 283 rem=(n1-q*d0)&BN_MASK2;
261 break; 284#endif
262 q--; 285
263 rem += d0; 286#ifdef BN_UMULT_HIGH
264 if (rem < d0) break; /* don't let rem overflow */ 287 t2l = d1 * q;
265 t2 -= d1; 288 t2h = BN_UMULT_HIGH(d1,q);
266 }
267#else 289#else
268 BN_ULONG t2l,t2h,ql,qh; 290 t2l=LBITS(d1); t2h=HBITS(d1);
269 291 ql =LBITS(q); qh =HBITS(q);
270#ifndef REMINDER_IS_ALREADY_CALCULATED 292 mul64(t2l,t2h,ql,qh); /* t2=(BN_ULLONG)d1*q; */
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 293#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 294
281 for (;;) 295 for (;;)
282 { 296 {
283 if ((t2h < rem) || 297 if ((t2h < rem) ||
284 ((t2h == rem) && (t2l <= wnump[-2]))) 298 ((t2h == rem) && (t2l <= wnump[-2])))
285 break; 299 break;
286 q--; 300 q--;
287 rem += d0; 301 rem += d0;
288 if (rem < d0) break; /* don't let rem overflow */ 302 if (rem < d0) break; /* don't let rem overflow */
289 if (t2l < d1) t2h--; t2l -= d1; 303 if (t2l < d1) t2h--; t2l -= d1;
304 }
305#endif /* !BN_LLONG */
290 } 306 }
291#endif
292 }
293#endif /* !BN_DIV3W */ 307#endif /* !BN_DIV3W */
294 wnum.d--; wnum.top++; 308
295 l0=bn_mul_words(tmp->d,sdiv->d,div_n,q); 309 l0=bn_mul_words(tmp->d,sdiv->d,div_n,q);
310 wnum.d--; wnum.top++;
296 tmp->d[div_n]=l0; 311 tmp->d[div_n]=l0;
297 for (j=div_n+1; j>0; j--) 312 for (j=div_n+1; j>0; j--)
298 if (tmp->d[j-1]) break; 313 if (tmp->d[j-1]) break;
@@ -318,8 +333,10 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
318 BN_rshift(rm,snum,norm_shift); 333 BN_rshift(rm,snum,norm_shift);
319 rm->neg=num->neg; 334 rm->neg=num->neg;
320 } 335 }
336 BN_CTX_end(ctx);
321 return(1); 337 return(1);
322err: 338err:
339 BN_CTX_end(ctx);
323 return(0); 340 return(0);
324 } 341 }
325 342
@@ -335,22 +352,27 @@ int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
335 if (BN_ucmp(m,d) < 0) 352 if (BN_ucmp(m,d) < 0)
336 return((BN_copy(rem,m) == NULL)?0:1); 353 return((BN_copy(rem,m) == NULL)?0:1);
337 354
338 dv= &(ctx->bn[ctx->tos]); 355 BN_CTX_start(ctx);
356 dv=BN_CTX_get(ctx);
339 357
340 if (!BN_copy(rem,m)) return(0); 358 if (!BN_copy(rem,m)) goto err;
341 359
342 nm=BN_num_bits(rem); 360 nm=BN_num_bits(rem);
343 nd=BN_num_bits(d); 361 nd=BN_num_bits(d);
344 if (!BN_lshift(dv,d,nm-nd)) return(0); 362 if (!BN_lshift(dv,d,nm-nd)) goto err;
345 for (i=nm-nd; i>=0; i--) 363 for (i=nm-nd; i>=0; i--)
346 { 364 {
347 if (BN_cmp(rem,dv) >= 0) 365 if (BN_cmp(rem,dv) >= 0)
348 { 366 {
349 if (!BN_sub(rem,rem,dv)) return(0); 367 if (!BN_sub(rem,rem,dv)) goto err;
350 } 368 }
351 if (!BN_rshift1(dv,dv)) return(0); 369 if (!BN_rshift1(dv,dv)) goto err;
352 } 370 }
371 BN_CTX_end(ctx);
353 return(1); 372 return(1);
373 err:
374 BN_CTX_end(ctx);
375 return(0);
354#else 376#else
355 return(BN_div(NULL,rem,m,d,ctx)); 377 return(BN_div(NULL,rem,m,d,ctx));
356#endif 378#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-15 05:07:22 +0000