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