More BN_mod_... functions.

[openssl.git] / crypto / bn / bn_mod.c

diff --git a/crypto/bn/bn_mod.c b/crypto/bn/bn_mod.c
index 72f09c2c2f0ebf00ab0f44a6d3b53d92b677dca6..92fe11684c8c914a7a006fc72f5693841c8fcb87 100644 (file)
--- a/crypto/bn/bn_mod.c
+++ b/crypto/bn/bn_mod.c
@@ -124,40 +124,62 @@ int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
 #endif
 
 
-int BN_nnmod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
+int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
        {
        /* like BN_mod, but returns non-negative remainder
-        * (i.e.,  0 <= rem < |d|  always holds) */
+        * (i.e.,  0 <= r < |d|  always holds) */
 
-       if (!(BN_mod(rem,m,d,ctx)))
+       if (!(BN_mod(r,m,d,ctx)))
                return 0;
-       if (!rem->neg)
+       if (!r->neg)
                return 1;
-       /* now   -|d| < rem < 0,  so we have to set  rem := rem + |d| */
-       return (d->neg ? BN_sub : BN_add)(rem, rem, d);
+       /* now   -|d| < r < 0,  so we have to set  r := r + |d| */
+       return (d->neg ? BN_sub : BN_add)(r, r, d);
 }
 
 
-int BN_mod_add(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) 
+int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
        {
-       if (!BN_add(ret, a, b)) return 0;
-       return BN_nnmod(ret, ret, m, ctx);
+       if (!BN_add(r, a, b)) return 0;
+       return BN_nnmod(r, r, m, ctx);
        }
 
 
-int BN_mod_sub(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) 
+/* BN_mod_add variant that may be used if both  a  and  b  are non-negative
+ * and less than  m */
+int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
        {
-       if (!BN_sub(ret, a, b)) return 0;
-       return BN_nnmod(ret, ret, m, ctx);
+       if (!BN_add(r, a, b)) return 0;
+       if (BN_cmp(r, m) >= 0)
+               return BN_sub(r, r, m);
+       return 1;
+       }
+
+
+int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
+       {
+       if (!BN_sub(r, a, b)) return 0;
+       return BN_nnmod(r, r, m, ctx);
+       }
+
+
+/* BN_mod_sub variant that may be used if both  a  and  b  are non-negative
+ * and less than  m */
+int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
+       {
+       if (!BN_sub(r, a, b)) return 0;
+       if (r->neg)
+               return BN_add(r, r, m);
+       return 1;
        }
 
 
 /* slow but works */
-int BN_mod_mul(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
+int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
        BN_CTX *ctx)
        {
        BIGNUM *t;
-       int r=0;
+       int ret=0;
 
        bn_check_top(a);
        bn_check_top(b);
@@ -169,17 +191,106 @@ int BN_mod_mul(BIGNUM *ret, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
                { if (!BN_sqr(t,a,ctx)) goto err; }
        else
                { if (!BN_mul(t,a,b,ctx)) goto err; }
-       if (!BN_nnmod(ret,t,m,ctx)) goto err;
-       r=1;
+       if (!BN_nnmod(r,t,m,ctx)) goto err;
+       ret=1;
 err:
        BN_CTX_end(ctx);
-       return(r);
+       return(ret);
        }
 
 
-int BN_mod_sqr(BIGNUM *ret, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
+int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
        {
-       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_sqr(r, a, ctx)) return 0;
+       /* r->neg == 0,  thus we don't need BN_nnmod */
+       return BN_mod(r, r, m, ctx);
+       }
+
+
+int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
+       {
+       if (!BN_lshift1(r, a)) return 0;
+       return BN_nnmod(r, r, m, ctx);
+       }
+
+
+/* BN_mod_lshift1 variant that may be used if  a  is non-negative
+ * and less than  m */
+int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
+       {
+       if (!BN_lshift1(r, a)) return 0;
+       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));
+
+       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;
+                       }
+               }
+       
+       return 1;
        }