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     bn_check_top(a);
  26     w &= BN_MASK2;
  27     for (i = a->top - 1; i >= 0; i--) {
  28 #ifndef BN_LLONG
  29         ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
  30         ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w;
  31 #else
  32         ret = (BN_ULLONG) (((ret << (BN_ULLONG) BN_BITS2) | a->d[i]) %
  33                            (BN_ULLONG) w);
  34 #endif
  35     }
  36     return ((BN_ULONG)ret);
  37 }
  38
  39 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
  40 {
  41     BN_ULONG ret = 0;
  42     int i, j;
  43
  44     bn_check_top(a);
  45     w &= BN_MASK2;
  46
  47     if (!w)
  48         /* actually this an error (division by zero) */
  49         return (BN_ULONG)-1;
  50     if (a->top == 0)
  51         return 0;
  52
  53     /* normalize input (so bn_div_words doesn't complain) */
  54     j = BN_BITS2 - BN_num_bits_word(w);
  55     w <<= j;
  56     if (!BN_lshift(a, a, j))
  57         return (BN_ULONG)-1;
  58
  59     for (i = a->top - 1; i >= 0; i--) {
  60         BN_ULONG l, d;
  61
  62         l = a->d[i];
  63         d = bn_div_words(ret, l, w);
  64         ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
  65         a->d[i] = d;
  66     }
  67     if ((a->top > 0) && (a->d[a->top - 1] == 0))
  68         a->top--;
  69     ret >>= j;
  70     bn_check_top(a);
  71     return (ret);
  72 }
  73
  74 int BN_add_word(BIGNUM *a, BN_ULONG w)
  75 {
  76     BN_ULONG l;
  77     int i;
  78
  79     bn_check_top(a);
  80     w &= BN_MASK2;
  81
  82     /* degenerate case: w is zero */
  83     if (!w)
  84         return 1;
  85     /* degenerate case: a is zero */
  86     if (BN_is_zero(a))
  87         return BN_set_word(a, w);
  88     /* handle 'a' when negative */
  89     if (a->neg) {
  90         a->neg = 0;
  91         i = BN_sub_word(a, w);
  92         if (!BN_is_zero(a))
  93             a->neg = !(a->neg);
  94         return (i);
  95     }
  96     for (i = 0; w != 0 && i < a->top; i++) {
  97         a->d[i] = l = (a->d[i] + w) & BN_MASK2;
  98         w = (w > l) ? 1 : 0;
  99     }
 100     if (w && i == a->top) {
 101         if (bn_wexpand(a, a->top + 1) == NULL)
 102             return 0;
 103         a->top++;
 104         a->d[i] = w;
 105     }
 106     bn_check_top(a);
 107     return (1);
 108 }
 109
 110 int BN_sub_word(BIGNUM *a, BN_ULONG w)
 111 {
 112     int i;
 113
 114     bn_check_top(a);
 115     w &= BN_MASK2;
 116
 117     /* degenerate case: w is zero */
 118     if (!w)
 119         return 1;
 120     /* degenerate case: a is zero */
 121     if (BN_is_zero(a)) {
 122         i = BN_set_word(a, w);
 123         if (i != 0)
 124             BN_set_negative(a, 1);
 125         return i;
 126     }
 127     /* handle 'a' when negative */
 128     if (a->neg) {
 129         a->neg = 0;
 130         i = BN_add_word(a, w);
 131         a->neg = 1;
 132         return (i);
 133     }
 134
 135     if ((a->top == 1) && (a->d[0] < w)) {
 136         a->d[0] = w - a->d[0];
 137         a->neg = 1;
 138         return (1);
 139     }
 140     i = 0;
 141     for (;;) {
 142         if (a->d[i] >= w) {
 143             a->d[i] -= w;
 144             break;
 145         } else {
 146             a->d[i] = (a->d[i] - w) & BN_MASK2;
 147             i++;
 148             w = 1;
 149         }
 150     }
 151     if ((a->d[i] == 0) && (i == (a->top - 1)))
 152         a->top--;
 153     bn_check_top(a);
 154     return (1);
 155 }
 156
 157 int BN_mul_word(BIGNUM *a, BN_ULONG w)
 158 {
 159     BN_ULONG ll;
 160
 161     bn_check_top(a);
 162     w &= BN_MASK2;
 163     if (a->top) {
 164         if (w == 0)
 165             BN_zero(a);
 166         else {
 167             ll = bn_mul_words(a->d, a->d, a->top, w);
 168             if (ll) {
 169                 if (bn_wexpand(a, a->top + 1) == NULL)
 170                     return (0);
 171                 a->d[a->top++] = ll;
 172             }
 173         }
 174     }
 175     bn_check_top(a);
 176     return (1);
 177 }