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