crypto/bn/bn_word.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (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_lcl.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     bn_check_top(a);
  93     return (ret);
  94 }
  95
  96 int BN_add_word(BIGNUM *a, BN_ULONG w)
  97 {
  98     BN_ULONG l;
  99     int i;
 100
 101     bn_check_top(a);
 102     w &= BN_MASK2;
 103
 104     /* degenerate case: w is zero */
 105     if (!w)
 106         return 1;
 107     /* degenerate case: a is zero */
 108     if (BN_is_zero(a))
 109         return BN_set_word(a, w);
 110     /* handle 'a' when negative */
 111     if (a->neg) {
 112         a->neg = 0;
 113         i = BN_sub_word(a, w);
 114         if (!BN_is_zero(a))
 115             a->neg = !(a->neg);
 116         return (i);
 117     }
 118     for (i = 0; w != 0 && i < a->top; i++) {
 119         a->d[i] = l = (a->d[i] + w) & BN_MASK2;
 120         w = (w > l) ? 1 : 0;
 121     }
 122     if (w && i == a->top) {
 123         if (bn_wexpand(a, a->top + 1) == NULL)
 124             return 0;
 125         a->top++;
 126         a->d[i] = w;
 127     }
 128     bn_check_top(a);
 129     return (1);
 130 }
 131
 132 int BN_sub_word(BIGNUM *a, BN_ULONG w)
 133 {
 134     int i;
 135
 136     bn_check_top(a);
 137     w &= BN_MASK2;
 138
 139     /* degenerate case: w is zero */
 140     if (!w)
 141         return 1;
 142     /* degenerate case: a is zero */
 143     if (BN_is_zero(a)) {
 144         i = BN_set_word(a, w);
 145         if (i != 0)
 146             BN_set_negative(a, 1);
 147         return i;
 148     }
 149     /* handle 'a' when negative */
 150     if (a->neg) {
 151         a->neg = 0;
 152         i = BN_add_word(a, w);
 153         a->neg = 1;
 154         return (i);
 155     }
 156
 157     if ((a->top == 1) && (a->d[0] < w)) {
 158         a->d[0] = w - a->d[0];
 159         a->neg = 1;
 160         return (1);
 161     }
 162     i = 0;
 163     for (;;) {
 164         if (a->d[i] >= w) {
 165             a->d[i] -= w;
 166             break;
 167         } else {
 168             a->d[i] = (a->d[i] - w) & BN_MASK2;
 169             i++;
 170             w = 1;
 171         }
 172     }
 173     if ((a->d[i] == 0) && (i == (a->top - 1)))
 174         a->top--;
 175     bn_check_top(a);
 176     return (1);
 177 }
 178
 179 int BN_mul_word(BIGNUM *a, BN_ULONG w)
 180 {
 181     BN_ULONG ll;
 182
 183     bn_check_top(a);
 184     w &= BN_MASK2;
 185     if (a->top) {
 186         if (w == 0)
 187             BN_zero(a);
 188         else {
 189             ll = bn_mul_words(a->d, a->d, a->top, w);
 190             if (ll) {
 191                 if (bn_wexpand(a, a->top + 1) == NULL)
 192                     return (0);
 193                 a->d[a->top++] = ll;
 194             }
 195         }
 196     }
 197     bn_check_top(a);
 198     return (1);
 199 }