crypto/bn/bn_word.c

   1 /* crypto/bn/bn_word.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58
  59 #include <stdio.h>
  60 #include "cryptlib.h"
  61 #include "bn_lcl.h"
  62
  63 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w)
  64 {
  65 #ifndef BN_LLONG
  66     BN_ULONG ret = 0;
  67 #else
  68     BN_ULLONG ret = 0;
  69 #endif
  70     int i;
  71
  72     if (w == 0)
  73         return (BN_ULONG)-1;
  74
  75 #ifndef BN_LLONG
  76     /*
  77      * If |w| is too long and we don't have BN_ULLONG then we need to fall
  78      * back to using BN_div_word
  79      */
  80     if (w > ((BN_ULONG)1 << BN_BITS4)) {
  81         BIGNUM *tmp = BN_dup(a);
  82         if (tmp == NULL)
  83             return (BN_ULONG)-1;
  84
  85         ret = BN_div_word(tmp, w);
  86         BN_free(tmp);
  87
  88         return ret;
  89     }
  90 #endif
  91
  92     bn_check_top(a);
  93     w &= BN_MASK2;
  94     for (i = a->top - 1; i >= 0; i--) {
  95 #ifndef BN_LLONG
  96         /*
  97          * We can assume here that | w <= ((BN_ULONG)1 << BN_BITS4) | and so
  98          * | ret < ((BN_ULONG)1 << BN_BITS4) | and therefore the shifts here are
  99          * safe and will not overflow
 100          */
 101         ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
 102         ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w;
 103 #else
 104         ret = (BN_ULLONG) (((ret << (BN_ULLONG) BN_BITS2) | a->d[i]) %
 105                            (BN_ULLONG) w);
 106 #endif
 107     }
 108     return ((BN_ULONG)ret);
 109 }
 110
 111 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
 112 {
 113     BN_ULONG ret = 0;
 114     int i, j;
 115
 116     bn_check_top(a);
 117     w &= BN_MASK2;
 118
 119     if (!w)
 120         /* actually this an error (division by zero) */
 121         return (BN_ULONG)-1;
 122     if (a->top == 0)
 123         return 0;
 124
 125     /* normalize input (so bn_div_words doesn't complain) */
 126     j = BN_BITS2 - BN_num_bits_word(w);
 127     w <<= j;
 128     if (!BN_lshift(a, a, j))
 129         return (BN_ULONG)-1;
 130
 131     for (i = a->top - 1; i >= 0; i--) {
 132         BN_ULONG l, d;
 133
 134         l = a->d[i];
 135         d = bn_div_words(ret, l, w);
 136         ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
 137         a->d[i] = d;
 138     }
 139     if ((a->top > 0) && (a->d[a->top - 1] == 0))
 140         a->top--;
 141     ret >>= j;
 142     bn_check_top(a);
 143     return (ret);
 144 }
 145
 146 int BN_add_word(BIGNUM *a, BN_ULONG w)
 147 {
 148     BN_ULONG l;
 149     int i;
 150
 151     bn_check_top(a);
 152     w &= BN_MASK2;
 153
 154     /* degenerate case: w is zero */
 155     if (!w)
 156         return 1;
 157     /* degenerate case: a is zero */
 158     if (BN_is_zero(a))
 159         return BN_set_word(a, w);
 160     /* handle 'a' when negative */
 161     if (a->neg) {
 162         a->neg = 0;
 163         i = BN_sub_word(a, w);
 164         if (!BN_is_zero(a))
 165             a->neg = !(a->neg);
 166         return (i);
 167     }
 168     for (i = 0; w != 0 && i < a->top; i++) {
 169         a->d[i] = l = (a->d[i] + w) & BN_MASK2;
 170         w = (w > l) ? 1 : 0;
 171     }
 172     if (w && i == a->top) {
 173         if (bn_wexpand(a, a->top + 1) == NULL)
 174             return 0;
 175         a->top++;
 176         a->d[i] = w;
 177     }
 178     bn_check_top(a);
 179     return (1);
 180 }
 181
 182 int BN_sub_word(BIGNUM *a, BN_ULONG w)
 183 {
 184     int i;
 185
 186     bn_check_top(a);
 187     w &= BN_MASK2;
 188
 189     /* degenerate case: w is zero */
 190     if (!w)
 191         return 1;
 192     /* degenerate case: a is zero */
 193     if (BN_is_zero(a)) {
 194         i = BN_set_word(a, w);
 195         if (i != 0)
 196             BN_set_negative(a, 1);
 197         return i;
 198     }
 199     /* handle 'a' when negative */
 200     if (a->neg) {
 201         a->neg = 0;
 202         i = BN_add_word(a, w);
 203         a->neg = 1;
 204         return (i);
 205     }
 206
 207     if ((a->top == 1) && (a->d[0] < w)) {
 208         a->d[0] = w - a->d[0];
 209         a->neg = 1;
 210         return (1);
 211     }
 212     i = 0;
 213     for (;;) {
 214         if (a->d[i] >= w) {
 215             a->d[i] -= w;
 216             break;
 217         } else {
 218             a->d[i] = (a->d[i] - w) & BN_MASK2;
 219             i++;
 220             w = 1;
 221         }
 222     }
 223     if ((a->d[i] == 0) && (i == (a->top - 1)))
 224         a->top--;
 225     bn_check_top(a);
 226     return (1);
 227 }
 228
 229 int BN_mul_word(BIGNUM *a, BN_ULONG w)
 230 {
 231     BN_ULONG ll;
 232
 233     bn_check_top(a);
 234     w &= BN_MASK2;
 235     if (a->top) {
 236         if (w == 0)
 237             BN_zero(a);
 238         else {
 239             ll = bn_mul_words(a->d, a->d, a->top, w);
 240             if (ll) {
 241                 if (bn_wexpand(a, a->top + 1) == NULL)
 242                     return (0);
 243                 a->d[a->top++] = ll;
 244             }
 245         }
 246     }
 247     bn_check_top(a);
 248     return (1);
 249 }