Line data Source code
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 0 : 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 0 : if (w == 0)
73 : return (BN_ULONG)-1;
74 :
75 : bn_check_top(a);
76 : w &= BN_MASK2;
77 0 : for (i = a->top - 1; i >= 0; i--) {
78 : #ifndef BN_LLONG
79 0 : ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
80 0 : 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 :
89 0 : BN_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 0 : if (!w)
98 : /* actually this an error (division by zero) */
99 : return (BN_ULONG)-1;
100 0 : if (a->top == 0)
101 : return 0;
102 :
103 : /* normalize input (so bn_div_words doesn't complain) */
104 0 : j = BN_BITS2 - BN_num_bits_word(w);
105 0 : w <<= j;
106 0 : if (!BN_lshift(a, a, j))
107 : return (BN_ULONG)-1;
108 :
109 0 : for (i = a->top - 1; i >= 0; i--) {
110 : BN_ULONG l, d;
111 :
112 0 : l = a->d[i];
113 0 : d = bn_div_words(ret, l, w);
114 0 : ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
115 0 : a->d[i] = d;
116 : }
117 0 : if ((a->top > 0) && (a->d[a->top - 1] == 0))
118 0 : a->top--;
119 0 : ret >>= j;
120 : bn_check_top(a);
121 0 : return (ret);
122 : }
123 :
124 1278 : int 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 1278 : if (!w)
134 : return 1;
135 : /* degenerate case: a is zero */
136 1278 : if (BN_is_zero(a))
137 0 : return BN_set_word(a, w);
138 : /* handle 'a' when negative */
139 1278 : if (a->neg) {
140 0 : a->neg = 0;
141 0 : i = BN_sub_word(a, w);
142 0 : if (!BN_is_zero(a))
143 0 : a->neg = !(a->neg);
144 0 : return (i);
145 : }
146 1278 : for (i = 0; w != 0 && i < a->top; i++) {
147 1278 : a->d[i] = l = (a->d[i] + w) & BN_MASK2;
148 1278 : w = (w > l) ? 1 : 0;
149 : }
150 1278 : if (w && i == a->top) {
151 0 : if (bn_wexpand(a, a->top + 1) == NULL)
152 : return 0;
153 0 : a->top++;
154 0 : a->d[i] = w;
155 : }
156 : bn_check_top(a);
157 : return (1);
158 : }
159 :
160 3338 : int 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 3338 : if (!w)
169 : return 1;
170 : /* degenerate case: a is zero */
171 3338 : if (BN_is_zero(a)) {
172 0 : i = BN_set_word(a, w);
173 0 : if (i != 0)
174 0 : BN_set_negative(a, 1);
175 0 : return i;
176 : }
177 : /* handle 'a' when negative */
178 3338 : if (a->neg) {
179 0 : a->neg = 0;
180 0 : i = BN_add_word(a, w);
181 0 : a->neg = 1;
182 0 : return (i);
183 : }
184 :
185 3338 : if ((a->top == 1) && (a->d[0] < w)) {
186 0 : a->d[0] = w - a->d[0];
187 0 : a->neg = 1;
188 0 : return (1);
189 : }
190 : i = 0;
191 : for (;;) {
192 6670 : if (a->d[i] >= w) {
193 3338 : a->d[i] -= w;
194 : break;
195 : } else {
196 3332 : a->d[i] = (a->d[i] - w) & BN_MASK2;
197 3332 : i++;
198 : w = 1;
199 : }
200 3332 : }
201 3338 : if ((a->d[i] == 0) && (i == (a->top - 1)))
202 0 : a->top--;
203 : bn_check_top(a);
204 : return (1);
205 : }
206 :
207 0 : int BN_mul_word(BIGNUM *a, BN_ULONG w)
208 : {
209 : BN_ULONG ll;
210 :
211 : bn_check_top(a);
212 : w &= BN_MASK2;
213 0 : if (a->top) {
214 0 : if (w == 0)
215 0 : BN_zero(a);
216 : else {
217 0 : ll = bn_mul_words(a->d, a->d, a->top, w);
218 0 : if (ll) {
219 0 : if (bn_wexpand(a, a->top + 1) == NULL)
220 : return (0);
221 0 : a->d[a->top++] = ll;
222 : }
223 : }
224 : }
225 : bn_check_top(a);
226 : return (1);
227 : }
|
