- BN_RECP_CTX *recp, BN_CTX *ctx)
- {
- int i,j,ret=0;
- BIGNUM *a,*b,*d,*r;
-
- BN_CTX_start(ctx);
- a=BN_CTX_get(ctx);
- b=BN_CTX_get(ctx);
- if (dv != NULL)
- d=dv;
- else
- d=BN_CTX_get(ctx);
- if (rem != NULL)
- r=rem;
- else
- r=BN_CTX_get(ctx);
- if (a == NULL || b == NULL || d == NULL || r == NULL) goto err;
-
- if (BN_ucmp(m,&(recp->N)) < 0)
- {
- if (!BN_zero(d)) return 0;
- if (!BN_copy(r,m)) return 0;
- BN_CTX_end(ctx);
- return(1);
- }
-
- /* We want the remainder
- * Given input of ABCDEF / ab
- * we need multiply ABCDEF by 3 digests of the reciprocal of ab
- *
- */
-
- /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
- i=BN_num_bits(m);
- j=recp->num_bits<<1;
- if (j>i) i=j;
-
- /* Nr := round(2^i / N) */
- if (i != recp->shift)
- recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N),
- i,ctx); /* BN_reciprocal returns i, or -1 for an error */
- if (recp->shift == -1) goto err;
-
- /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
- * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
- * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
- * = |m/N|
- */
- if (!BN_rshift(a,m,recp->num_bits)) goto err;
- if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err;
- if (!BN_rshift(d,b,i-recp->num_bits)) goto err;
- d->neg=0;
-
- if (!BN_mul(b,&(recp->N),d,ctx)) goto err;
- if (!BN_usub(r,m,b)) goto err;
- r->neg=0;
-
-#if 1
- j=0;
- while (BN_ucmp(r,&(recp->N)) >= 0)
- {
- if (j++ > 2)
- {
- BNerr(BN_F_BN_MOD_MUL_RECIPROCAL,BN_R_BAD_RECIPROCAL);
- goto err;
- }
- if (!BN_usub(r,r,&(recp->N))) goto err;
- if (!BN_add_word(d,1)) goto err;
- }
-#endif
-
- r->neg=BN_is_zero(r)?0:m->neg;
- d->neg=m->neg^recp->N.neg;
- ret=1;
-err:
- BN_CTX_end(ctx);
- return(ret);
- }
-
-/* len is the expected size of the result
- * We actually calculate with an extra word of precision, so
- * we can do faster division if the remainder is not required.
+ BN_RECP_CTX *recp, BN_CTX *ctx)
+{
+ int i, j, ret = 0;
+ BIGNUM *a, *b, *d, *r;
+
+ BN_CTX_start(ctx);
+ a = BN_CTX_get(ctx);
+ b = BN_CTX_get(ctx);
+ if (dv != NULL)
+ d = dv;
+ else
+ d = BN_CTX_get(ctx);
+ if (rem != NULL)
+ r = rem;
+ else
+ r = BN_CTX_get(ctx);
+ if (a == NULL || b == NULL || d == NULL || r == NULL)
+ goto err;
+
+ if (BN_ucmp(m, &(recp->N)) < 0) {
+ BN_zero(d);
+ if (!BN_copy(r, m)) {
+ BN_CTX_end(ctx);
+ return 0;
+ }
+ BN_CTX_end(ctx);
+ return (1);
+ }
+
+ /*
+ * We want the remainder Given input of ABCDEF / ab we need multiply
+ * ABCDEF by 3 digests of the reciprocal of ab
+ */
+
+ /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */
+ i = BN_num_bits(m);
+ j = recp->num_bits << 1;
+ if (j > i)
+ i = j;
+
+ /* Nr := round(2^i / N) */
+ if (i != recp->shift)
+ recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);
+ /* BN_reciprocal could have returned -1 for an error */
+ if (recp->shift == -1)
+ goto err;
+
+ /*-
+ * d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
+ * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
+ * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
+ * = |m/N|
+ */
+ if (!BN_rshift(a, m, recp->num_bits))
+ goto err;
+ if (!BN_mul(b, a, &(recp->Nr), ctx))
+ goto err;
+ if (!BN_rshift(d, b, i - recp->num_bits))
+ goto err;
+ d->neg = 0;
+
+ if (!BN_mul(b, &(recp->N), d, ctx))
+ goto err;
+ if (!BN_usub(r, m, b))
+ goto err;
+ r->neg = 0;
+
+ j = 0;
+ while (BN_ucmp(r, &(recp->N)) >= 0) {
+ if (j++ > 2) {
+ BNerr(BN_F_BN_DIV_RECP, BN_R_BAD_RECIPROCAL);
+ goto err;
+ }
+ if (!BN_usub(r, r, &(recp->N)))
+ goto err;
+ if (!BN_add_word(d, 1))
+ goto err;
+ }
+
+ r->neg = BN_is_zero(r) ? 0 : m->neg;
+ d->neg = m->neg ^ recp->N.neg;
+ ret = 1;
+ err:
+ BN_CTX_end(ctx);
+ bn_check_top(dv);
+ bn_check_top(rem);
+ return (ret);
+}
+
+/*
+ * len is the expected size of the result We actually calculate with an extra
+ * word of precision, so we can do faster division if the remainder is not
+ * required.