crypto/bn/bn_word.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "internal/cryptlib.h"
  11 #include "bn_local.h"
  12
  13 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w)
  14 {
  15 #ifndef BN_LLONG
  16     BN_ULONG ret = 0;
  17 #else
  18     BN_ULLONG ret = 0;
  19 #endif
  20     int i;
  21
  22     if (w == 0)
  23         return (BN_ULONG)-1;
  24
  25 #ifndef BN_LLONG
  26     /*
  27      * If |w| is too long and we don't have BN_ULLONG then we need to fall
  28      * back to using BN_div_word
  29      */
  30     if (w > ((BN_ULONG)1 << BN_BITS4)) {
  31         BIGNUM *tmp = BN_dup(a);
  32         if (tmp == NULL)
  33             return (BN_ULONG)-1;
  34
  35         ret = BN_div_word(tmp, w);
  36         BN_free(tmp);
  37
  38         return ret;
  39     }
  40 #endif
  41
  42     bn_check_top(a);
  43     w &= BN_MASK2;
  44     for (i = a->top - 1; i >= 0; i--) {
  45 #ifndef BN_LLONG
  46         /*
  47          * We can assume here that | w <= ((BN_ULONG)1 << BN_BITS4) | and so
  48          * | ret < ((BN_ULONG)1 << BN_BITS4) | and therefore the shifts here are
  49          * safe and will not overflow
  50          */
  51         ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
  52         ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w;
  53 #else
  54         ret = (BN_ULLONG) (((ret << (BN_ULLONG) BN_BITS2) | a->d[i]) %
  55                            (BN_ULLONG) w);
  56 #endif
  57     }
  58     return (BN_ULONG)ret;
  59 }
  60
  61 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
  62 {
  63     BN_ULONG ret = 0;
  64     int i, j;
  65
  66     bn_check_top(a);
  67     w &= BN_MASK2;
  68
  69     if (!w)
  70         /* actually this an error (division by zero) */
  71         return (BN_ULONG)-1;
  72     if (a->top == 0)
  73         return 0;
  74
  75     /* normalize input (so bn_div_words doesn't complain) */
  76     j = BN_BITS2 - BN_num_bits_word(w);
  77     w <<= j;
  78     if (!BN_lshift(a, a, j))
  79         return (BN_ULONG)-1;
  80
  81     for (i = a->top - 1; i >= 0; i--) {
  82         BN_ULONG l, d;
  83
  84         l = a->d[i];
  85         d = bn_div_words(ret, l, w);
  86         ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
  87         a->d[i] = d;
  88     }
  89     if ((a->top > 0) && (a->d[a->top - 1] == 0))
  90         a->top--;
  91     ret >>= j;
  92     if (!a->top)
  93         a->neg = 0; /* don't allow negative zero */
  94     bn_check_top(a);
  95     return ret;
  96 }
  97
  98 int BN_add_word(BIGNUM *a, BN_ULONG w)
  99 {
 100     BN_ULONG l;
 101     int i;
 102
 103     bn_check_top(a);
 104     w &= BN_MASK2;
 105
 106     /* degenerate case: w is zero */
 107     if (!w)
 108         return 1;
 109     /* degenerate case: a is zero */
 110     if (BN_is_zero(a))
 111         return BN_set_word(a, w);
 112     /* handle 'a' when negative */
 113     if (a->neg) {
 114         a->neg = 0;
 115         i = BN_sub_word(a, w);
 116         if (!BN_is_zero(a))
 117             a->neg = !(a->neg);
 118         return i;
 119     }
 120     for (i = 0; w != 0 && i < a->top; i++) {
 121         a->d[i] = l = (a->d[i] + w) & BN_MASK2;
 122         w = (w > l) ? 1 : 0;
 123     }
 124     if (w && i == a->top) {
 125         if (bn_wexpand(a, a->top + 1) == NULL)
 126             return 0;
 127         a->top++;
 128         a->d[i] = w;
 129     }
 130     bn_check_top(a);
 131     return 1;
 132 }
 133
 134 int BN_sub_word(BIGNUM *a, BN_ULONG w)
 135 {
 136     int i;
 137
 138     bn_check_top(a);
 139     w &= BN_MASK2;
 140
 141     /* degenerate case: w is zero */
 142     if (!w)
 143         return 1;
 144     /* degenerate case: a is zero */
 145     if (BN_is_zero(a)) {
 146         i = BN_set_word(a, w);
 147         if (i != 0)
 148             BN_set_negative(a, 1);
 149         return i;
 150     }
 151     /* handle 'a' when negative */
 152     if (a->neg) {
 153         a->neg = 0;
 154         i = BN_add_word(a, w);
 155         a->neg = 1;
 156         return i;
 157     }
 158
 159     if ((a->top == 1) && (a->d[0] < w)) {
 160         a->d[0] = w - a->d[0];
 161         a->neg = 1;
 162         return 1;
 163     }
 164     i = 0;
 165     for (;;) {
 166         if (a->d[i] >= w) {
 167             a->d[i] -= w;
 168             break;
 169         } else {
 170             a->d[i] = (a->d[i] - w) & BN_MASK2;
 171             i++;
 172             w = 1;
 173         }
 174     }
 175     if ((a->d[i] == 0) && (i == (a->top - 1)))
 176         a->top--;
 177     bn_check_top(a);
 178     return 1;
 179 }
 180
 181 int BN_mul_word(BIGNUM *a, BN_ULONG w)
 182 {
 183     BN_ULONG ll;
 184
 185     bn_check_top(a);
 186     w &= BN_MASK2;
 187     if (a->top) {
 188         if (w == 0)
 189             BN_zero(a);
 190         else {
 191             ll = bn_mul_words(a->d, a->d, a->top, w);
 192             if (ll) {
 193                 if (bn_wexpand(a, a->top + 1) == NULL)
 194                     return 0;
 195                 a->d[a->top++] = ll;
 196             }
 197         }
 198     }
 199     bn_check_top(a);
 200     return 1;
 201 }