2 * bn_lcl.h: Big Number local header file.
4 * Code copied from openssl distribution and
5 * Modified just enough so that compiles and runs standalone
7 * Copyright (C) 2010, Broadcom Corporation. All Rights Reserved.
9 * Permission to use, copy, modify, and/or distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
16 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
18 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
19 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 * $Id: bn_lcl.h,v 1.3 2006-06-15 10:09:43 Exp $
23 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
24 * All rights reserved.
26 * This package is an SSL implementation written
27 * by Eric Young (eay@cryptsoft.com).
28 * The implementation was written so as to conform with Netscapes SSL.
30 * This library is free for commercial and non-commercial use as long as
31 * the following conditions are aheared to. The following conditions
32 * apply to all code found in this distribution, be it the RC4, RSA,
33 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
34 * included with this distribution is covered by the same copyright terms
35 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
37 * Copyright remains Eric Young's, and as such any Copyright notices in
38 * the code are not to be removed.
39 * If this package is used in a product, Eric Young should be given attribution
40 * as the author of the parts of the library used.
41 * This can be in the form of a textual message at program startup or
42 * in documentation (online or textual) provided with the package.
44 * Redistribution and use in source and binary forms, with or without
45 * modification, are permitted provided that the following conditions
47 * 1. Redistributions of source code must retain the copyright
48 * notice, this list of conditions and the following disclaimer.
49 * 2. Redistributions in binary form must reproduce the above copyright
50 * notice, this list of conditions and the following disclaimer in the
51 * documentation and/or other materials provided with the distribution.
52 * 3. All advertising materials mentioning features or use of this software
53 * must display the following acknowledgement:
54 * "This product includes cryptographic software written by
55 * Eric Young (eay@cryptsoft.com)"
56 * The word 'cryptographic' can be left out if the rouines from the library
57 * being used are not cryptographic related :-).
58 * 4. If you include any Windows specific code (or a derivative thereof) from
59 * the apps directory (application code) you must include an acknowledgement:
60 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
62 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
63 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
64 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
65 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
66 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
67 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
68 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
69 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
70 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
71 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
74 * The licence and distribution terms for any publically available version or
75 * derivative of this code cannot be changed. i.e. this code cannot simply be
76 * copied and put under another distribution licence
77 * [including the GNU Public Licence.]
79 /* ====================================================================
80 * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
82 * Redistribution and use in source and binary forms, with or without
83 * modification, are permitted provided that the following conditions
86 * 1. Redistributions of source code must retain the above copyright
87 * notice, this list of conditions and the following disclaimer.
89 * 2. Redistributions in binary form must reproduce the above copyright
90 * notice, this list of conditions and the following disclaimer in
91 * the documentation and/or other materials provided with the
94 * 3. All advertising materials mentioning features or use of this
95 * software must display the following acknowledgment:
96 * "This product includes software developed by the OpenSSL Project
97 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
99 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
100 * endorse or promote products derived from this software without
101 * prior written permission. For written permission, please contact
102 * openssl-core@openssl.org.
104 * 5. Products derived from this software may not be called "OpenSSL"
105 * nor may "OpenSSL" appear in their names without prior written
106 * permission of the OpenSSL Project.
108 * 6. Redistributions of any form whatsoever must retain the following
110 * "This product includes software developed by the OpenSSL Project
111 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
113 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
114 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
115 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
116 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
117 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
118 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
119 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
120 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
121 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
122 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
123 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
124 * OF THE POSSIBILITY OF SUCH DAMAGE.
125 * ====================================================================
127 * This product includes cryptographic software written by Eric Young
128 * (eay@cryptsoft.com). This product includes software written by Tim
129 * Hudson (tjh@cryptsoft.com).
133 #ifndef HEADER_BN_LCL_H
134 #define HEADER_BN_LCL_H
141 /* Used for temp variables */
142 #define BN_CTX_NUM 32
143 #define BN_CTX_NUM_POS 12
147 BIGNUM bn
[BN_CTX_NUM
];
150 int pos
[BN_CTX_NUM_POS
];
156 * BN_window_bits_for_exponent_size -- macro for sliding window mod_exp functions
159 * For window size 'w' (w >= 2) and a random 'b' bits exponent,
160 * the number of multiplications is a constant plus on average
162 * 2^(w-1) + (b-w)/(w+1);
164 * here 2^(w-1) is for precomputing the table (we actually need
165 * entries only for windows that have the lowest bit set), and
166 * (b-w)/(w+1) is an approximation for the expected number of
167 * w-bit windows, not counting the first one.
172 * w = 5 if 671 > b > 239
173 * w = 4 if 239 > b > 79
174 * w = 3 if 79 > b > 23
177 * (with draws in between). Very small exponents are often selected
178 * with low Hamming weight, so we use w = 1 for b <= 23.
180 #define BN_window_bits_for_exponent_size(b) \
187 /* Pentium pro 16, 16, 16, 32, 64 */
188 /* Alpha 16, 16, 16, 16.64 */
189 #define BN_MULL_SIZE_NORMAL (16) /* 32 */
190 #define BN_MUL_RECURSIVE_SIZE_NORMAL (16) /* 32 less than */
191 #define BN_SQR_RECURSIVE_SIZE_NORMAL (16) /* 32 */
192 #define BN_MUL_LOW_RECURSIVE_SIZE_NORMAL (32) /* 32 */
193 #define BN_MONT_CTX_SET_SIZE_WORD (64) /* 32 */
195 #if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) && !defined(PEDANTIC)
197 * BN_UMULT_HIGH section.
199 * No, I'm not trying to overwhelm you when stating that the
200 * product of N-bit numbers is 2*N bits wide:-) No, I don't expect
201 * you to be impressed when I say that if the compiler doesn't
202 * support 2*N integer type, then you have to replace every N*N
203 * multiplication with 4 (N/2)*(N/2) accompanied by some shifts
204 * and additions which unavoidably results in severe performance
205 * penalties. Of course provided that the hardware is capable of
206 * producing 2*N result... That's when you normally start
207 * considering assembler implementation. However! It should be
208 * pointed out that some CPUs (most notably Alpha, PowerPC and
209 * upcoming IA-64 family:-) provide *separate* instruction
210 * calculating the upper half of the product placing the result
211 * into a general purpose register. Now *if* the compiler supports
212 * inline assembler, then it's not impossible to implement the
213 * "bignum" routines (and have the compiler optimize 'em)
214 * exhibiting "native" performance in C. That's what BN_UMULT_HIGH
217 * <appro@fy.chalmers.se>
219 # if defined(__alpha) && (defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT))
222 # define BN_UMULT_HIGH(a, b) (BN_ULONG)asm("umulh %a0, %a1, %v0", (a), (b))
223 # elif defined(__GNUC__)
224 # define BN_UMULT_HIGH(a, b) ({ \
225 register BN_ULONG ret; \
226 asm("umulh %1, %2, %0" \
230 # endif /* compiler */
231 # elif defined(_ARCH_PPC) && defined(__64BIT__) && defined(SIXTY_FOUR_BIT_LONG)
232 # if defined(__GNUC__)
233 # define BN_UMULT_HIGH(a, b) ({ \
234 register BN_ULONG ret; \
235 asm("mulhdu %0, %1, %2" \
239 # endif /* compiler */
240 # elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG)
241 # if defined(__GNUC__)
242 # define BN_UMULT_HIGH(a, b) ({ \
243 register BN_ULONG ret, discard; \
245 : "=a"(discard), "=d"(ret) \
249 # define BN_UMULT_LOHI(low, high, a, b) \
251 : "=a"(low), "=d"(high) \
256 #endif /* OPENSSL_NO_ASM */
258 /*************************************************************
259 * Using the long long type
261 #define Lw(t) (((BN_ULONG)(t))&BN_MASK2)
262 #define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2)
264 /* This is used for internal error checking and is not normally used */
267 # define bn_check_top(a) assert ((a)->top >= 0 && (a)->top <= (a)->dmax);
269 # define bn_check_top(a)
272 /* This macro is to add extra stuff for development checking */
274 #define bn_set_max(r) ((r)->max = (r)->top, BN_set_flags((r), BN_FLG_STATIC_DATA))
276 #define bn_set_max(r)
279 /* These macros are used to 'take' a section of a bignum for read only use */
280 #define bn_set_low(r, a, n) { \
281 (r)->top = ((a)->top > (n))?(n):(a)->top; \
283 (r)->neg = (a)->neg; \
284 (r)->flags |= BN_FLG_STATIC_DATA; \
288 #define bn_set_high(r, a, n) { \
289 if ((a)->top > (n)) { \
290 (r)->top = (a)->top-n; \
291 (r)->d = &((a)->d[n]); \
294 (r)->neg = (a)->neg; \
295 (r)->flags |= BN_FLG_STATIC_DATA; \
300 #define mul_add(r, a, w, c) { \
302 t = (BN_ULLONG)w * (a) + (r) + (c); \
307 #define mul(r, a, w, c) { \
309 t = (BN_ULLONG)w * (a) + (c); \
314 #define sqr(r0, r1, a) { \
316 t = (BN_ULLONG)(a)*(a); \
321 #elif defined(BN_UMULT_HIGH)
322 #define mul_add(r, a, w, c) { \
323 BN_ULONG high, low, ret, tmp = (a); \
325 high = BN_UMULT_HIGH(w, tmp); \
328 (c) = (ret < (c)) ? 1 : 0; \
331 (c) += (ret < low) ? 1 : 0; \
335 #define mul(r, a, w, c) { \
336 BN_ULONG high, low, ret, ta = (a); \
338 high = BN_UMULT_HIGH(w, ta); \
341 (c) += (ret < low) ? 1 : 0; \
345 #define sqr(r0, r1, a) { \
346 BN_ULONG tmp = (a); \
348 (r1) = BN_UMULT_HIGH(tmp, tmp); \
352 /* No long long type */
354 #define LBITS(a) ((a) & BN_MASK2l)
355 #define HBITS(a) (((a) >> BN_BITS4) & BN_MASK2l)
356 #define L2HBITS(a) (((a) << BN_BITS4) & BN_MASK2)
358 #define LLBITS(a) ((a) & BN_MASKl)
359 #define LHBITS(a) (((a) >> BN_BITS2) & BN_MASKl)
360 #define LL2HBITS(a) ((BN_ULLONG)((a) & BN_MASKl) << BN_BITS2)
362 #define mul64(l, h, bl, bh) { \
363 BN_ULONG m, m1, lt, ht; \
370 m = (m + m1) & BN_MASK2; \
372 ht += L2HBITS((BN_ULONG)1); \
375 lt = (lt + m1) & BN_MASK2; \
382 #define sqr64(lo, ho, in) { \
390 h += (m & BN_MASK2h1) >> (BN_BITS4 - 1); \
391 m = (m & BN_MASK2l) << (BN_BITS4 + 1); \
392 l = (l + m) & BN_MASK2; \
399 #define mul_add(r, a, bl, bh, c) { \
404 mul64(l, h, (bl), (bh)); \
405 /* non-multiply part */ \
406 l = (l + (c)) & BN_MASK2; \
410 l = (l + (c)) & BN_MASK2; \
413 (c) = h & BN_MASK2; \
417 #define mul(r, a, bl, bh, c) { \
422 mul64(l, h, (bl), (bh)); \
423 /* non-multiply part */ \
425 if ((l & BN_MASK2) < (c)) \
427 (c) = h & BN_MASK2; \
428 (r) = l & BN_MASK2; \
430 #endif /* !BN_LLONG */
432 void bn_mul_normal(BN_ULONG
*r
, BN_ULONG
*a
, int na
, BN_ULONG
*b
, int nb
);
433 void bn_mul_comba8(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
);
434 void bn_mul_comba4(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
);
435 void bn_sqr_normal(BN_ULONG
*r
, const BN_ULONG
*a
, int n
, BN_ULONG
*tmp
);
436 void bn_sqr_comba8(BN_ULONG
*r
, const BN_ULONG
*a
);
437 void bn_sqr_comba4(BN_ULONG
*r
, const BN_ULONG
*a
);
438 int bn_cmp_words(const BN_ULONG
*a
, const BN_ULONG
*b
, int n
);
439 int bn_cmp_part_words(const BN_ULONG
*a
, const BN_ULONG
*b
, int cl
, int dl
);
440 void bn_sqr_recursive(BN_ULONG
*r
, const BN_ULONG
*a
, int n2
, BN_ULONG
*t
);
441 void bn_mul_low_normal(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
, int n
);
442 void bn_mul_low_recursive(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
, int n2
,
444 void bn_mul_high(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
, BN_ULONG
*l
, int n2
,
451 #endif /* HEADER_BN_LCL_H */