1 |
/* crypto/bn/bn_lcl.h */ |
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 |
* Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. |
60 |
* |
61 |
* Redistribution and use in source and binary forms, with or without |
62 |
* modification, are permitted provided that the following conditions |
63 |
* are met: |
64 |
* |
65 |
* 1. Redistributions of source code must retain the above copyright |
66 |
* notice, this list of conditions and the following disclaimer. |
67 |
* |
68 |
* 2. Redistributions in binary form must reproduce the above copyright |
69 |
* notice, this list of conditions and the following disclaimer in |
70 |
* the documentation and/or other materials provided with the |
71 |
* distribution. |
72 |
* |
73 |
* 3. All advertising materials mentioning features or use of this |
74 |
* software must display the following acknowledgment: |
75 |
* "This product includes software developed by the OpenSSL Project |
76 |
* for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
77 |
* |
78 |
* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
79 |
* endorse or promote products derived from this software without |
80 |
* prior written permission. For written permission, please contact |
81 |
* openssl-core@openssl.org. |
82 |
* |
83 |
* 5. Products derived from this software may not be called "OpenSSL" |
84 |
* nor may "OpenSSL" appear in their names without prior written |
85 |
* permission of the OpenSSL Project. |
86 |
* |
87 |
* 6. Redistributions of any form whatsoever must retain the following |
88 |
* acknowledgment: |
89 |
* "This product includes software developed by the OpenSSL Project |
90 |
* for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
91 |
* |
92 |
* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
93 |
* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
94 |
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
95 |
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
96 |
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
97 |
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
98 |
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
99 |
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
100 |
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
101 |
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
102 |
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
103 |
* OF THE POSSIBILITY OF SUCH DAMAGE. |
104 |
* ==================================================================== |
105 |
* |
106 |
* This product includes cryptographic software written by Eric Young |
107 |
* (eay@cryptsoft.com). This product includes software written by Tim |
108 |
* Hudson (tjh@cryptsoft.com). |
109 |
* |
110 |
*/ |
111 |
|
112 |
#ifndef HEADER_BN_LCL_H |
113 |
#define HEADER_BN_LCL_H |
114 |
|
115 |
#include "bn.h" |
116 |
|
117 |
#ifdef __cplusplus |
118 |
extern "C" { |
119 |
#endif |
120 |
|
121 |
|
122 |
/* |
123 |
* BN_window_bits_for_exponent_size -- macro for sliding window mod_exp functions |
124 |
* |
125 |
* |
126 |
* For window size 'w' (w >= 2) and a random 'b' bits exponent, |
127 |
* the number of multiplications is a constant plus on average |
128 |
* |
129 |
* 2^(w-1) + (b-w)/(w+1); |
130 |
* |
131 |
* here 2^(w-1) is for precomputing the table (we actually need |
132 |
* entries only for windows that have the lowest bit set), and |
133 |
* (b-w)/(w+1) is an approximation for the expected number of |
134 |
* w-bit windows, not counting the first one. |
135 |
* |
136 |
* Thus we should use |
137 |
* |
138 |
* w >= 6 if b > 671 |
139 |
* w = 5 if 671 > b > 239 |
140 |
* w = 4 if 239 > b > 79 |
141 |
* w = 3 if 79 > b > 23 |
142 |
* w <= 2 if 23 > b |
143 |
* |
144 |
* (with draws in between). Very small exponents are often selected |
145 |
* with low Hamming weight, so we use w = 1 for b <= 23. |
146 |
*/ |
147 |
#if 1 |
148 |
#define BN_window_bits_for_exponent_size(b) \ |
149 |
((b) > 671 ? 6 : \ |
150 |
(b) > 239 ? 5 : \ |
151 |
(b) > 79 ? 4 : \ |
152 |
(b) > 23 ? 3 : 1) |
153 |
#else |
154 |
/* Old SSLeay/OpenSSL table. |
155 |
* Maximum window size was 5, so this table differs for b==1024; |
156 |
* but it coincides for other interesting values (b==160, b==512). |
157 |
*/ |
158 |
#define BN_window_bits_for_exponent_size(b) \ |
159 |
((b) > 255 ? 5 : \ |
160 |
(b) > 127 ? 4 : \ |
161 |
(b) > 17 ? 3 : 1) |
162 |
#endif |
163 |
|
164 |
|
165 |
|
166 |
/* Pentium pro 16,16,16,32,64 */ |
167 |
/* Alpha 16,16,16,16.64 */ |
168 |
#define BN_MULL_SIZE_NORMAL (16) /* 32 */ |
169 |
#define BN_MUL_RECURSIVE_SIZE_NORMAL (16) /* 32 less than */ |
170 |
#define BN_SQR_RECURSIVE_SIZE_NORMAL (16) /* 32 */ |
171 |
#define BN_MUL_LOW_RECURSIVE_SIZE_NORMAL (32) /* 32 */ |
172 |
#define BN_MONT_CTX_SET_SIZE_WORD (64) /* 32 */ |
173 |
|
174 |
#if !defined(NO_ASM) && !defined(NO_INLINE_ASM) && !defined(PEDANTIC) |
175 |
/* |
176 |
* BN_UMULT_HIGH section. |
177 |
* |
178 |
* No, I'm not trying to overwhelm you when stating that the |
179 |
* product of N-bit numbers is 2*N bits wide:-) No, I don't expect |
180 |
* you to be impressed when I say that if the compiler doesn't |
181 |
* support 2*N integer type, then you have to replace every N*N |
182 |
* multiplication with 4 (N/2)*(N/2) accompanied by some shifts |
183 |
* and additions which unavoidably results in severe performance |
184 |
* penalties. Of course provided that the hardware is capable of |
185 |
* producing 2*N result... That's when you normally start |
186 |
* considering assembler implementation. However! It should be |
187 |
* pointed out that some CPUs (most notably Alpha, PowerPC and |
188 |
* upcoming IA-64 family:-) provide *separate* instruction |
189 |
* calculating the upper half of the product placing the result |
190 |
* into a general purpose register. Now *if* the compiler supports |
191 |
* inline assembler, then it's not impossible to implement the |
192 |
* "bignum" routines (and have the compiler optimize 'em) |
193 |
* exhibiting "native" performance in C. That's what BN_UMULT_HIGH |
194 |
* macro is about:-) |
195 |
* |
196 |
* <appro@fy.chalmers.se> |
197 |
*/ |
198 |
# if defined(__alpha) && (defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT)) |
199 |
# if defined(__DECC) |
200 |
# include <c_asm.h> |
201 |
# define BN_UMULT_HIGH(a,b) (BN_ULONG)asm("umulh %a0,%a1,%v0",(a),(b)) |
202 |
# elif defined(__GNUC__) |
203 |
# define BN_UMULT_HIGH(a,b) ({ \ |
204 |
register BN_ULONG ret; \ |
205 |
asm ("umulh %1,%2,%0" \ |
206 |
: "=r"(ret) \ |
207 |
: "r"(a), "r"(b)); \ |
208 |
ret; }) |
209 |
# endif /* compiler */ |
210 |
# elif defined(_ARCH_PPC) && defined(__64BIT__) && defined(SIXTY_FOUR_BIT_LONG) |
211 |
# if defined(__GNUC__) |
212 |
# define BN_UMULT_HIGH(a,b) ({ \ |
213 |
register BN_ULONG ret; \ |
214 |
asm ("mulhdu %0,%1,%2" \ |
215 |
: "=r"(ret) \ |
216 |
: "r"(a), "r"(b)); \ |
217 |
ret; }) |
218 |
# endif /* compiler */ |
219 |
# endif /* cpu */ |
220 |
#endif /* NO_ASM */ |
221 |
|
222 |
/************************************************************* |
223 |
* Using the long long type |
224 |
*/ |
225 |
#define Lw(t) (((BN_ULONG)(t))&BN_MASK2) |
226 |
#define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2) |
227 |
|
228 |
/* This is used for internal error checking and is not normally used */ |
229 |
#ifdef BN_DEBUG |
230 |
# include <assert.h> |
231 |
# define bn_check_top(a) assert ((a)->top >= 0 && (a)->top <= (a)->dmax); |
232 |
#else |
233 |
# define bn_check_top(a) |
234 |
#endif |
235 |
|
236 |
/* This macro is to add extra stuff for development checking */ |
237 |
#ifdef BN_DEBUG |
238 |
#define bn_set_max(r) ((r)->max=(r)->top,BN_set_flags((r),BN_FLG_STATIC_DATA)) |
239 |
#else |
240 |
#define bn_set_max(r) |
241 |
#endif |
242 |
|
243 |
/* These macros are used to 'take' a section of a bignum for read only use */ |
244 |
#define bn_set_low(r,a,n) \ |
245 |
{ \ |
246 |
(r)->top=((a)->top > (n))?(n):(a)->top; \ |
247 |
(r)->d=(a)->d; \ |
248 |
(r)->neg=(a)->neg; \ |
249 |
(r)->flags|=BN_FLG_STATIC_DATA; \ |
250 |
bn_set_max(r); \ |
251 |
} |
252 |
|
253 |
#define bn_set_high(r,a,n) \ |
254 |
{ \ |
255 |
if ((a)->top > (n)) \ |
256 |
{ \ |
257 |
(r)->top=(a)->top-n; \ |
258 |
(r)->d= &((a)->d[n]); \ |
259 |
} \ |
260 |
else \ |
261 |
(r)->top=0; \ |
262 |
(r)->neg=(a)->neg; \ |
263 |
(r)->flags|=BN_FLG_STATIC_DATA; \ |
264 |
bn_set_max(r); \ |
265 |
} |
266 |
|
267 |
#ifdef BN_LLONG |
268 |
#define mul_add(r,a,w,c) { \ |
269 |
BN_ULLONG t; \ |
270 |
t=(BN_ULLONG)w * (a) + (r) + (c); \ |
271 |
(r)= Lw(t); \ |
272 |
(c)= Hw(t); \ |
273 |
} |
274 |
|
275 |
#define mul(r,a,w,c) { \ |
276 |
BN_ULLONG t; \ |
277 |
t=(BN_ULLONG)w * (a) + (c); \ |
278 |
(r)= Lw(t); \ |
279 |
(c)= Hw(t); \ |
280 |
} |
281 |
|
282 |
#define sqr(r0,r1,a) { \ |
283 |
BN_ULLONG t; \ |
284 |
t=(BN_ULLONG)(a)*(a); \ |
285 |
(r0)=Lw(t); \ |
286 |
(r1)=Hw(t); \ |
287 |
} |
288 |
|
289 |
#elif defined(BN_UMULT_HIGH) |
290 |
#define mul_add(r,a,w,c) { \ |
291 |
BN_ULONG high,low,ret,tmp=(a); \ |
292 |
ret = (r); \ |
293 |
high= BN_UMULT_HIGH(w,tmp); \ |
294 |
ret += (c); \ |
295 |
low = (w) * tmp; \ |
296 |
(c) = (ret<(c))?1:0; \ |
297 |
(c) += high; \ |
298 |
ret += low; \ |
299 |
(c) += (ret<low)?1:0; \ |
300 |
(r) = ret; \ |
301 |
} |
302 |
|
303 |
#define mul(r,a,w,c) { \ |
304 |
BN_ULONG high,low,ret,ta=(a); \ |
305 |
low = (w) * ta; \ |
306 |
high= BN_UMULT_HIGH(w,ta); \ |
307 |
ret = low + (c); \ |
308 |
(c) = high; \ |
309 |
(c) += (ret<low)?1:0; \ |
310 |
(r) = ret; \ |
311 |
} |
312 |
|
313 |
#define sqr(r0,r1,a) { \ |
314 |
BN_ULONG tmp=(a); \ |
315 |
(r0) = tmp * tmp; \ |
316 |
(r1) = BN_UMULT_HIGH(tmp,tmp); \ |
317 |
} |
318 |
|
319 |
#else |
320 |
/************************************************************* |
321 |
* No long long type |
322 |
*/ |
323 |
|
324 |
#define LBITS(a) ((a)&BN_MASK2l) |
325 |
#define HBITS(a) (((a)>>BN_BITS4)&BN_MASK2l) |
326 |
#define L2HBITS(a) ((BN_ULONG)((a)&BN_MASK2l)<<BN_BITS4) |
327 |
|
328 |
#define LLBITS(a) ((a)&BN_MASKl) |
329 |
#define LHBITS(a) (((a)>>BN_BITS2)&BN_MASKl) |
330 |
#define LL2HBITS(a) ((BN_ULLONG)((a)&BN_MASKl)<<BN_BITS2) |
331 |
|
332 |
#define mul64(l,h,bl,bh) \ |
333 |
{ \ |
334 |
BN_ULONG m,m1,lt,ht; \ |
335 |
\ |
336 |
lt=l; \ |
337 |
ht=h; \ |
338 |
m =(bh)*(lt); \ |
339 |
lt=(bl)*(lt); \ |
340 |
m1=(bl)*(ht); \ |
341 |
ht =(bh)*(ht); \ |
342 |
m=(m+m1)&BN_MASK2; if (m < m1) ht+=L2HBITS(1L); \ |
343 |
ht+=HBITS(m); \ |
344 |
m1=L2HBITS(m); \ |
345 |
lt=(lt+m1)&BN_MASK2; if (lt < m1) ht++; \ |
346 |
(l)=lt; \ |
347 |
(h)=ht; \ |
348 |
} |
349 |
|
350 |
#define sqr64(lo,ho,in) \ |
351 |
{ \ |
352 |
BN_ULONG l,h,m; \ |
353 |
\ |
354 |
h=(in); \ |
355 |
l=LBITS(h); \ |
356 |
h=HBITS(h); \ |
357 |
m =(l)*(h); \ |
358 |
l*=l; \ |
359 |
h*=h; \ |
360 |
h+=(m&BN_MASK2h1)>>(BN_BITS4-1); \ |
361 |
m =(m&BN_MASK2l)<<(BN_BITS4+1); \ |
362 |
l=(l+m)&BN_MASK2; if (l < m) h++; \ |
363 |
(lo)=l; \ |
364 |
(ho)=h; \ |
365 |
} |
366 |
|
367 |
#define mul_add(r,a,bl,bh,c) { \ |
368 |
BN_ULONG l,h; \ |
369 |
\ |
370 |
h= (a); \ |
371 |
l=LBITS(h); \ |
372 |
h=HBITS(h); \ |
373 |
mul64(l,h,(bl),(bh)); \ |
374 |
\ |
375 |
/* non-multiply part */ \ |
376 |
l=(l+(c))&BN_MASK2; if (l < (c)) h++; \ |
377 |
(c)=(r); \ |
378 |
l=(l+(c))&BN_MASK2; if (l < (c)) h++; \ |
379 |
(c)=h&BN_MASK2; \ |
380 |
(r)=l; \ |
381 |
} |
382 |
|
383 |
#define mul(r,a,bl,bh,c) { \ |
384 |
BN_ULONG l,h; \ |
385 |
\ |
386 |
h= (a); \ |
387 |
l=LBITS(h); \ |
388 |
h=HBITS(h); \ |
389 |
mul64(l,h,(bl),(bh)); \ |
390 |
\ |
391 |
/* non-multiply part */ \ |
392 |
l+=(c); if ((l&BN_MASK2) < (c)) h++; \ |
393 |
(c)=h&BN_MASK2; \ |
394 |
(r)=l&BN_MASK2; \ |
395 |
} |
396 |
#endif /* !BN_LLONG */ |
397 |
|
398 |
void bn_mul_normal(BN_ULONG *r,BN_ULONG *a,int na,BN_ULONG *b,int nb); |
399 |
void bn_mul_comba8(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b); |
400 |
void bn_mul_comba4(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b); |
401 |
void bn_sqr_normal(BN_ULONG *r, BN_ULONG *a, int n, BN_ULONG *tmp); |
402 |
void bn_sqr_comba8(BN_ULONG *r,BN_ULONG *a); |
403 |
void bn_sqr_comba4(BN_ULONG *r,BN_ULONG *a); |
404 |
int bn_cmp_words(BN_ULONG *a,BN_ULONG *b,int n); |
405 |
void bn_mul_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,int n2,BN_ULONG *t); |
406 |
void bn_mul_part_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b, |
407 |
int tn, int n,BN_ULONG *t); |
408 |
void bn_sqr_recursive(BN_ULONG *r,BN_ULONG *a, int n2, BN_ULONG *t); |
409 |
void bn_mul_low_normal(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b, int n); |
410 |
void bn_mul_low_recursive(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,int n2, |
411 |
BN_ULONG *t); |
412 |
void bn_mul_high(BN_ULONG *r,BN_ULONG *a,BN_ULONG *b,BN_ULONG *l,int n2, |
413 |
BN_ULONG *t); |
414 |
|
415 |
#ifdef __cplusplus |
416 |
} |
417 |
#endif |
418 |
|
419 |
#endif |