- if (!BN_sqr(ret, a, ctx)) return 0;
- /* ret->neg == 0, thus we don't need BN_nnmod */
- return BN_mod(ret, ret, m, ctx);
+ if (!BN_lshift1(r, a)) return 0;
+ bn_check_top(r);
+ if (BN_cmp(r, m) >= 0)
+ return BN_sub(r, r, m);
+ return 1;
+ }
+
+
+int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx)
+ {
+ BIGNUM *abs_m = NULL;
+ int ret;
+
+ if (!BN_nnmod(r, a, m, ctx)) return 0;
+
+ if (m->neg)
+ {
+ abs_m = BN_dup(m);
+ if (abs_m == NULL) return 0;
+ abs_m->neg = 0;
+ }
+
+ ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
+ bn_check_top(r);
+
+ if (abs_m)
+ BN_free(abs_m);
+ return ret;
+ }
+
+
+/* BN_mod_lshift variant that may be used if a is non-negative
+ * and less than m */
+int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
+ {
+ if (r != a)
+ {
+ if (BN_copy(r, a) == NULL) return 0;
+ }
+
+ while (n > 0)
+ {
+ int max_shift;
+
+ /* 0 < r < m */
+ max_shift = BN_num_bits(m) - BN_num_bits(r);
+ /* max_shift >= 0 */
+
+ if (max_shift < 0)
+ {
+ BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
+ return 0;
+ }
+
+ if (max_shift > n)
+ max_shift = n;
+
+ if (max_shift)
+ {
+ if (!BN_lshift(r, r, max_shift)) return 0;
+ n -= max_shift;
+ }
+ else
+ {
+ if (!BN_lshift1(r, r)) return 0;
+ --n;
+ }
+
+ /* BN_num_bits(r) <= BN_num_bits(m) */
+
+ if (BN_cmp(r, m) >= 0)
+ {
+ if (!BN_sub(r, r, m)) return 0;
+ }
+ }
+ bn_check_top(r);
+
+ return 1;