bn_word.c revision 296465 
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
63BN_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    bn_check_top(a);
76    w &= BN_MASK2;
77    for (i = a->top - 1; i >= 0; i--) {
78#ifndef BN_LLONG
79        ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
80        ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w;
81#else
82        ret = (BN_ULLONG) (((ret << (BN_ULLONG) BN_BITS2) | a->d[i]) %
83                           (BN_ULLONG) w);
84#endif
85    }
86    return ((BN_ULONG)ret);
87}
88
89BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
90{
91    BN_ULONG ret = 0;
92    int i, j;
93
94    bn_check_top(a);
95    w &= BN_MASK2;
96
97    if (!w)
98        /* actually this an error (division by zero) */
99        return (BN_ULONG)-1;
100    if (a->top == 0)
101        return 0;
102
103    /* normalize input (so bn_div_words doesn't complain) */
104    j = BN_BITS2 - BN_num_bits_word(w);
105    w <<= j;
106    if (!BN_lshift(a, a, j))
107        return (BN_ULONG)-1;
108
109    for (i = a->top - 1; i >= 0; i--) {
110        BN_ULONG l, d;
111
112        l = a->d[i];
113        d = bn_div_words(ret, l, w);
114        ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
115        a->d[i] = d;
116    }
117    if ((a->top > 0) && (a->d[a->top - 1] == 0))
118        a->top--;
119    ret >>= j;
120    bn_check_top(a);
121    return (ret);
122}
123
124int BN_add_word(BIGNUM *a, BN_ULONG w)
125{
126    BN_ULONG l;
127    int i;
128
129    bn_check_top(a);
130    w &= BN_MASK2;
131
132    /* degenerate case: w is zero */
133    if (!w)
134        return 1;
135    /* degenerate case: a is zero */
136    if (BN_is_zero(a))
137        return BN_set_word(a, w);
138    /* handle 'a' when negative */
139    if (a->neg) {
140        a->neg = 0;
141        i = BN_sub_word(a, w);
142        if (!BN_is_zero(a))
143            a->neg = !(a->neg);
144        return (i);
145    }
146    for (i = 0; w != 0 && i < a->top; i++) {
147        a->d[i] = l = (a->d[i] + w) & BN_MASK2;
148        w = (w > l) ? 1 : 0;
149    }
150    if (w && i == a->top) {
151        if (bn_wexpand(a, a->top + 1) == NULL)
152            return 0;
153        a->top++;
154        a->d[i] = w;
155    }
156    bn_check_top(a);
157    return (1);
158}
159
160int BN_sub_word(BIGNUM *a, BN_ULONG w)
161{
162    int i;
163
164    bn_check_top(a);
165    w &= BN_MASK2;
166
167    /* degenerate case: w is zero */
168    if (!w)
169        return 1;
170    /* degenerate case: a is zero */
171    if (BN_is_zero(a)) {
172        i = BN_set_word(a, w);
173        if (i != 0)
174            BN_set_negative(a, 1);
175        return i;
176    }
177    /* handle 'a' when negative */
178    if (a->neg) {
179        a->neg = 0;
180        i = BN_add_word(a, w);
181        a->neg = 1;
182        return (i);
183    }
184
185    if ((a->top == 1) && (a->d[0] < w)) {
186        a->d[0] = w - a->d[0];
187        a->neg = 1;
188        return (1);
189    }
190    i = 0;
191    for (;;) {
192        if (a->d[i] >= w) {
193            a->d[i] -= w;
194            break;
195        } else {
196            a->d[i] = (a->d[i] - w) & BN_MASK2;
197            i++;
198            w = 1;
199        }
200    }
201    if ((a->d[i] == 0) && (i == (a->top - 1)))
202        a->top--;
203    bn_check_top(a);
204    return (1);
205}
206
207int BN_mul_word(BIGNUM *a, BN_ULONG w)
208{
209    BN_ULONG ll;
210
211    bn_check_top(a);
212    w &= BN_MASK2;
213    if (a->top) {
214        if (w == 0)
215            BN_zero(a);
216        else {
217            ll = bn_mul_words(a->d, a->d, a->top, w);
218            if (ll) {
219                if (bn_wexpand(a, a->top + 1) == NULL)
220                    return (0);
221                a->d[a->top++] = ll;
222            }
223        }
224    }
225    bn_check_top(a);
226    return (1);
227}
228