crypto/bn: fix debug build
[openssl.git] / crypto / bn / bn_local.h
1 /*
2  * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #ifndef OSSL_CRYPTO_BN_LOCAL_H
11 # define OSSL_CRYPTO_BN_LOCAL_H
12
13 /*
14  * The EDK2 build doesn't use bn_conf.h; it sets THIRTY_TWO_BIT or
15  * SIXTY_FOUR_BIT in its own environment since it doesn't re-run our
16  * Configure script and needs to support both 32-bit and 64-bit.
17  */
18 # include <openssl/opensslconf.h>
19
20 # if !defined(OPENSSL_SYS_UEFI)
21 #  include "crypto/bn_conf.h"
22 # endif
23
24 # include "crypto/bn.h"
25 # include "internal/cryptlib.h"
26
27 /*
28  * These preprocessor symbols control various aspects of the bignum headers
29  * and library code. They're not defined by any "normal" configuration, as
30  * they are intended for development and testing purposes. NB: defining all
31  * three can be useful for debugging application code as well as openssl
32  * itself. BN_DEBUG - turn on various debugging alterations to the bignum
33  * code BN_DEBUG_RAND - uses random poisoning of unused words to trip up
34  * mismanagement of bignum internals. You must also define BN_DEBUG.
35  */
36 /* #define BN_DEBUG */
37 /* #define BN_DEBUG_RAND */
38
39 # ifndef OPENSSL_SMALL_FOOTPRINT
40 #  define BN_MUL_COMBA
41 #  define BN_SQR_COMBA
42 #  define BN_RECURSION
43 # endif
44
45 /*
46  * This next option uses the C libraries (2 word)/(1 word) function. If it is
47  * not defined, I use my C version (which is slower). The reason for this
48  * flag is that when the particular C compiler library routine is used, and
49  * the library is linked with a different compiler, the library is missing.
50  * This mostly happens when the library is built with gcc and then linked
51  * using normal cc.  This would be a common occurrence because gcc normally
52  * produces code that is 2 times faster than system compilers for the big
53  * number stuff. For machines with only one compiler (or shared libraries),
54  * this should be on.  Again this in only really a problem on machines using
55  * "long long's", are 32bit, and are not using my assembler code.
56  */
57 # if defined(OPENSSL_SYS_MSDOS) || defined(OPENSSL_SYS_WINDOWS) || \
58     defined(OPENSSL_SYS_WIN32) || defined(linux)
59 #  define BN_DIV2W
60 # endif
61
62 /*
63  * 64-bit processor with LP64 ABI
64  */
65 # ifdef SIXTY_FOUR_BIT_LONG
66 #  define BN_ULLONG       unsigned long long
67 #  define BN_BITS4        32
68 #  define BN_MASK2        (0xffffffffffffffffL)
69 #  define BN_MASK2l       (0xffffffffL)
70 #  define BN_MASK2h       (0xffffffff00000000L)
71 #  define BN_MASK2h1      (0xffffffff80000000L)
72 #  define BN_DEC_CONV     (10000000000000000000UL)
73 #  define BN_DEC_NUM      19
74 #  define BN_DEC_FMT1     "%lu"
75 #  define BN_DEC_FMT2     "%019lu"
76 # endif
77
78 /*
79  * 64-bit processor other than LP64 ABI
80  */
81 # ifdef SIXTY_FOUR_BIT
82 #  undef BN_LLONG
83 #  undef BN_ULLONG
84 #  define BN_BITS4        32
85 #  define BN_MASK2        (0xffffffffffffffffLL)
86 #  define BN_MASK2l       (0xffffffffL)
87 #  define BN_MASK2h       (0xffffffff00000000LL)
88 #  define BN_MASK2h1      (0xffffffff80000000LL)
89 #  define BN_DEC_CONV     (10000000000000000000ULL)
90 #  define BN_DEC_NUM      19
91 #  define BN_DEC_FMT1     "%llu"
92 #  define BN_DEC_FMT2     "%019llu"
93 # endif
94
95 # ifdef THIRTY_TWO_BIT
96 #  ifdef BN_LLONG
97 #   if defined(_WIN32) && !defined(__GNUC__)
98 #    define BN_ULLONG     unsigned __int64
99 #   else
100 #    define BN_ULLONG     unsigned long long
101 #   endif
102 #  endif
103 #  define BN_BITS4        16
104 #  define BN_MASK2        (0xffffffffL)
105 #  define BN_MASK2l       (0xffff)
106 #  define BN_MASK2h1      (0xffff8000L)
107 #  define BN_MASK2h       (0xffff0000L)
108 #  define BN_DEC_CONV     (1000000000L)
109 #  define BN_DEC_NUM      9
110 #  define BN_DEC_FMT1     "%u"
111 #  define BN_DEC_FMT2     "%09u"
112 # endif
113
114
115 /*-
116  * Bignum consistency macros
117  * There is one "API" macro, bn_fix_top(), for stripping leading zeroes from
118  * bignum data after direct manipulations on the data. There is also an
119  * "internal" macro, bn_check_top(), for verifying that there are no leading
120  * zeroes. Unfortunately, some auditing is required due to the fact that
121  * bn_fix_top() has become an overabused duct-tape because bignum data is
122  * occasionally passed around in an inconsistent state. So the following
123  * changes have been made to sort this out;
124  * - bn_fix_top()s implementation has been moved to bn_correct_top()
125  * - if BN_DEBUG isn't defined, bn_fix_top() maps to bn_correct_top(), and
126  *   bn_check_top() is as before.
127  * - if BN_DEBUG *is* defined;
128  *   - bn_check_top() tries to pollute unused words even if the bignum 'top' is
129  *     consistent. (ed: only if BN_DEBUG_RAND is defined)
130  *   - bn_fix_top() maps to bn_check_top() rather than "fixing" anything.
131  * The idea is to have debug builds flag up inconsistent bignums when they
132  * occur. If that occurs in a bn_fix_top(), we examine the code in question; if
133  * the use of bn_fix_top() was appropriate (ie. it follows directly after code
134  * that manipulates the bignum) it is converted to bn_correct_top(), and if it
135  * was not appropriate, we convert it permanently to bn_check_top() and track
136  * down the cause of the bug. Eventually, no internal code should be using the
137  * bn_fix_top() macro. External applications and libraries should try this with
138  * their own code too, both in terms of building against the openssl headers
139  * with BN_DEBUG defined *and* linking with a version of OpenSSL built with it
140  * defined. This not only improves external code, it provides more test
141  * coverage for openssl's own code.
142  */
143
144 # ifdef BN_DEBUG
145 /*
146  * The new BN_FLG_FIXED_TOP flag marks vectors that were not treated with
147  * bn_correct_top, in other words such vectors are permitted to have zeros
148  * in most significant limbs. Such vectors are used internally to achieve
149  * execution time invariance for critical operations with private keys.
150  * It's BN_DEBUG-only flag, because user application is not supposed to
151  * observe it anyway. Moreover, optimizing compiler would actually remove
152  * all operations manipulating the bit in question in non-BN_DEBUG build.
153  */
154 #  define BN_FLG_FIXED_TOP 0x10000
155 #  ifdef BN_DEBUG_RAND
156 #   define bn_pollute(a) \
157         do { \
158             const BIGNUM *_bnum1 = (a); \
159             if (_bnum1->top < _bnum1->dmax) { \
160                 unsigned char _tmp_char; \
161                 /* We cast away const without the compiler knowing, any \
162                  * *genuinely* constant variables that aren't mutable \
163                  * wouldn't be constructed with top!=dmax. */ \
164                 BN_ULONG *_not_const; \
165                 memcpy(&_not_const, &_bnum1->d, sizeof(_not_const)); \
166                 RAND_bytes(&_tmp_char, 1); /* Debug only - safe to ignore error return */\
167                 memset(_not_const + _bnum1->top, _tmp_char, \
168                        sizeof(*_not_const) * (_bnum1->dmax - _bnum1->top)); \
169             } \
170         } while(0)
171 #  else
172 #   define bn_pollute(a)
173 #  endif
174 #  define bn_check_top(a) \
175         do { \
176                 const BIGNUM *_bnum2 = (a); \
177                 if (_bnum2 != NULL) { \
178                         int _top = _bnum2->top; \
179                         (void)ossl_assert((_top == 0 && !_bnum2->neg) || \
180                                   (_top && ((_bnum2->flags & BN_FLG_FIXED_TOP) \
181                                             || _bnum2->d[_top - 1] != 0))); \
182                         bn_pollute(_bnum2); \
183                 } \
184         } while(0)
185
186 #  define bn_fix_top(a)           bn_check_top(a)
187
188 #  define bn_check_size(bn, bits) bn_wcheck_size(bn, ((bits+BN_BITS2-1))/BN_BITS2)
189 #  define bn_wcheck_size(bn, words) \
190         do { \
191                 const BIGNUM *_bnum2 = (bn); \
192                 assert((words) <= (_bnum2)->dmax && \
193                        (words) >= (_bnum2)->top); \
194                 /* avoid unused variable warning with NDEBUG */ \
195                 (void)(_bnum2); \
196         } while(0)
197
198 # else                          /* !BN_DEBUG */
199
200 #  define BN_FLG_FIXED_TOP 0
201 #  define bn_pollute(a)
202 #  define bn_check_top(a)
203 #  define bn_fix_top(a)           bn_correct_top(a)
204 #  define bn_check_size(bn, bits)
205 #  define bn_wcheck_size(bn, words)
206
207 # endif
208
209 BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num,
210                           BN_ULONG w);
211 BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w);
212 void bn_sqr_words(BN_ULONG *rp, const BN_ULONG *ap, int num);
213 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
214 BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
215                       int num);
216 BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
217                       int num);
218
219 struct bignum_st {
220     BN_ULONG *d;                /* Pointer to an array of 'BN_BITS2' bit
221                                  * chunks. */
222     int top;                    /* Index of last used d +1. */
223     /* The next are internal book keeping for bn_expand. */
224     int dmax;                   /* Size of the d array. */
225     int neg;                    /* one if the number is negative */
226     int flags;
227 };
228
229 /* Used for montgomery multiplication */
230 struct bn_mont_ctx_st {
231     int ri;                     /* number of bits in R */
232     BIGNUM RR;                  /* used to convert to montgomery form,
233                                    possibly zero-padded */
234     BIGNUM N;                   /* The modulus */
235     BIGNUM Ni;                  /* R*(1/R mod N) - N*Ni = 1 (Ni is only
236                                  * stored for bignum algorithm) */
237     BN_ULONG n0[2];             /* least significant word(s) of Ni; (type
238                                  * changed with 0.9.9, was "BN_ULONG n0;"
239                                  * before) */
240     int flags;
241 };
242
243 /*
244  * Used for reciprocal division/mod functions It cannot be shared between
245  * threads
246  */
247 struct bn_recp_ctx_st {
248     BIGNUM N;                   /* the divisor */
249     BIGNUM Nr;                  /* the reciprocal */
250     int num_bits;
251     int shift;
252     int flags;
253 };
254
255 /* Used for slow "generation" functions. */
256 struct bn_gencb_st {
257     unsigned int ver;           /* To handle binary (in)compatibility */
258     void *arg;                  /* callback-specific data */
259     union {
260         /* if (ver==1) - handles old style callbacks */
261         void (*cb_1) (int, int, void *);
262         /* if (ver==2) - new callback style */
263         int (*cb_2) (int, int, BN_GENCB *);
264     } cb;
265 };
266
267 /*-
268  * BN_window_bits_for_exponent_size -- macro for sliding window mod_exp functions
269  *
270  *
271  * For window size 'w' (w >= 2) and a random 'b' bits exponent,
272  * the number of multiplications is a constant plus on average
273  *
274  *    2^(w-1) + (b-w)/(w+1);
275  *
276  * here  2^(w-1)  is for precomputing the table (we actually need
277  * entries only for windows that have the lowest bit set), and
278  * (b-w)/(w+1)  is an approximation for the expected number of
279  * w-bit windows, not counting the first one.
280  *
281  * Thus we should use
282  *
283  *    w >= 6  if        b > 671
284  *     w = 5  if  671 > b > 239
285  *     w = 4  if  239 > b >  79
286  *     w = 3  if   79 > b >  23
287  *    w <= 2  if   23 > b
288  *
289  * (with draws in between).  Very small exponents are often selected
290  * with low Hamming weight, so we use  w = 1  for b <= 23.
291  */
292 # define BN_window_bits_for_exponent_size(b) \
293                 ((b) > 671 ? 6 : \
294                  (b) > 239 ? 5 : \
295                  (b) >  79 ? 4 : \
296                  (b) >  23 ? 3 : 1)
297
298 /*
299  * BN_mod_exp_mont_consttime is based on the assumption that the L1 data cache
300  * line width of the target processor is at least the following value.
301  */
302 # define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH      ( 64 )
303 # define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK       (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1)
304
305 /*
306  * Window sizes optimized for fixed window size modular exponentiation
307  * algorithm (BN_mod_exp_mont_consttime). To achieve the security goals of
308  * BN_mode_exp_mont_consttime, the maximum size of the window must not exceed
309  * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH). Window size thresholds are
310  * defined for cache line sizes of 32 and 64, cache line sizes where
311  * log_2(32)=5 and log_2(64)=6 respectively. A window size of 7 should only be
312  * used on processors that have a 128 byte or greater cache line size.
313  */
314 # if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64
315
316 #  define BN_window_bits_for_ctime_exponent_size(b) \
317                 ((b) > 937 ? 6 : \
318                  (b) > 306 ? 5 : \
319                  (b) >  89 ? 4 : \
320                  (b) >  22 ? 3 : 1)
321 #  define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE    (6)
322
323 # elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32
324
325 #  define BN_window_bits_for_ctime_exponent_size(b) \
326                 ((b) > 306 ? 5 : \
327                  (b) >  89 ? 4 : \
328                  (b) >  22 ? 3 : 1)
329 #  define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE    (5)
330
331 # endif
332
333 /* Pentium pro 16,16,16,32,64 */
334 /* Alpha       16,16,16,16.64 */
335 # define BN_MULL_SIZE_NORMAL                     (16)/* 32 */
336 # define BN_MUL_RECURSIVE_SIZE_NORMAL            (16)/* 32 less than */
337 # define BN_SQR_RECURSIVE_SIZE_NORMAL            (16)/* 32 */
338 # define BN_MUL_LOW_RECURSIVE_SIZE_NORMAL        (32)/* 32 */
339 # define BN_MONT_CTX_SET_SIZE_WORD               (64)/* 32 */
340
341 /*
342  * 2011-02-22 SMS. In various places, a size_t variable or a type cast to
343  * size_t was used to perform integer-only operations on pointers.  This
344  * failed on VMS with 64-bit pointers (CC /POINTER_SIZE = 64) because size_t
345  * is still only 32 bits.  What's needed in these cases is an integer type
346  * with the same size as a pointer, which size_t is not certain to be. The
347  * only fix here is VMS-specific.
348  */
349 # if defined(OPENSSL_SYS_VMS)
350 #  if __INITIAL_POINTER_SIZE == 64
351 #   define PTR_SIZE_INT long long
352 #  else                         /* __INITIAL_POINTER_SIZE == 64 */
353 #   define PTR_SIZE_INT int
354 #  endif                        /* __INITIAL_POINTER_SIZE == 64 [else] */
355 # elif !defined(PTR_SIZE_INT)   /* defined(OPENSSL_SYS_VMS) */
356 #  define PTR_SIZE_INT size_t
357 # endif                         /* defined(OPENSSL_SYS_VMS) [else] */
358
359 # if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) && !defined(PEDANTIC)
360 /*
361  * BN_UMULT_HIGH section.
362  * If the compiler doesn't support 2*N integer type, then you have to
363  * replace every N*N multiplication with 4 (N/2)*(N/2) accompanied by some
364  * shifts and additions which unavoidably results in severe performance
365  * penalties. Of course provided that the hardware is capable of producing
366  * 2*N result... That's when you normally start considering assembler
367  * implementation. However! It should be pointed out that some CPUs (e.g.,
368  * PowerPC, Alpha, and IA-64) provide *separate* instruction calculating
369  * the upper half of the product placing the result into a general
370  * purpose register. Now *if* the compiler supports inline assembler,
371  * then it's not impossible to implement the "bignum" routines (and have
372  * the compiler optimize 'em) exhibiting "native" performance in C. That's
373  * what BN_UMULT_HIGH macro is about:-) Note that more recent compilers do
374  * support 2*64 integer type, which is also used here.
375  */
376 #  if defined(__SIZEOF_INT128__) && __SIZEOF_INT128__==16 && \
377       (defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG))
378 #   define BN_UMULT_HIGH(a,b)          (((__uint128_t)(a)*(b))>>64)
379 #   define BN_UMULT_LOHI(low,high,a,b) ({       \
380         __uint128_t ret=(__uint128_t)(a)*(b);   \
381         (high)=ret>>64; (low)=ret;      })
382 #  elif defined(__alpha) && (defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT))
383 #   if defined(__DECC)
384 #    include <c_asm.h>
385 #    define BN_UMULT_HIGH(a,b)   (BN_ULONG)asm("umulh %a0,%a1,%v0",(a),(b))
386 #   elif defined(__GNUC__) && __GNUC__>=2
387 #    define BN_UMULT_HIGH(a,b)   ({     \
388         register BN_ULONG ret;          \
389         asm ("umulh     %1,%2,%0"       \
390              : "=r"(ret)                \
391              : "r"(a), "r"(b));         \
392         ret;                      })
393 #   endif                       /* compiler */
394 #  elif defined(_ARCH_PPC64) && defined(SIXTY_FOUR_BIT_LONG)
395 #   if defined(__GNUC__) && __GNUC__>=2
396 #    define BN_UMULT_HIGH(a,b)   ({     \
397         register BN_ULONG ret;          \
398         asm ("mulhdu    %0,%1,%2"       \
399              : "=r"(ret)                \
400              : "r"(a), "r"(b));         \
401         ret;                      })
402 #   endif                       /* compiler */
403 #  elif (defined(__x86_64) || defined(__x86_64__)) && \
404        (defined(SIXTY_FOUR_BIT_LONG) || defined(SIXTY_FOUR_BIT))
405 #   if defined(__GNUC__) && __GNUC__>=2
406 #    define BN_UMULT_HIGH(a,b)   ({     \
407         register BN_ULONG ret,discard;  \
408         asm ("mulq      %3"             \
409              : "=a"(discard),"=d"(ret)  \
410              : "a"(a), "g"(b)           \
411              : "cc");                   \
412         ret;                      })
413 #    define BN_UMULT_LOHI(low,high,a,b) \
414         asm ("mulq      %3"             \
415                 : "=a"(low),"=d"(high)  \
416                 : "a"(a),"g"(b)         \
417                 : "cc");
418 #   endif
419 #  elif (defined(_M_AMD64) || defined(_M_X64)) && defined(SIXTY_FOUR_BIT)
420 #   if defined(_MSC_VER) && _MSC_VER>=1400
421 unsigned __int64 __umulh(unsigned __int64 a, unsigned __int64 b);
422 unsigned __int64 _umul128(unsigned __int64 a, unsigned __int64 b,
423                           unsigned __int64 *h);
424 #    pragma intrinsic(__umulh,_umul128)
425 #    define BN_UMULT_HIGH(a,b)           __umulh((a),(b))
426 #    define BN_UMULT_LOHI(low,high,a,b)  ((low)=_umul128((a),(b),&(high)))
427 #   endif
428 #  elif defined(__mips) && (defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG))
429 #   if defined(__GNUC__) && __GNUC__>=2
430 #    define BN_UMULT_HIGH(a,b) ({       \
431         register BN_ULONG ret;          \
432         asm ("dmultu    %1,%2"          \
433              : "=h"(ret)                \
434              : "r"(a), "r"(b) : "l");   \
435         ret;                    })
436 #    define BN_UMULT_LOHI(low,high,a,b) \
437         asm ("dmultu    %2,%3"          \
438              : "=l"(low),"=h"(high)     \
439              : "r"(a), "r"(b));
440 #   endif
441 #  elif defined(__aarch64__) && defined(SIXTY_FOUR_BIT_LONG)
442 #   if defined(__GNUC__) && __GNUC__>=2
443 #    define BN_UMULT_HIGH(a,b)   ({     \
444         register BN_ULONG ret;          \
445         asm ("umulh     %0,%1,%2"       \
446              : "=r"(ret)                \
447              : "r"(a), "r"(b));         \
448         ret;                      })
449 #   endif
450 #  endif                        /* cpu */
451 # endif                         /* OPENSSL_NO_ASM */
452
453 # ifdef BN_DEBUG_RAND
454 #  define bn_clear_top2max(a) \
455         { \
456         int      ind = (a)->dmax - (a)->top; \
457         BN_ULONG *ftl = &(a)->d[(a)->top-1]; \
458         for (; ind != 0; ind--) \
459                 *(++ftl) = 0x0; \
460         }
461 # else
462 #  define bn_clear_top2max(a)
463 # endif
464
465 # ifdef BN_LLONG
466 /*******************************************************************
467  * Using the long long type, has to be twice as wide as BN_ULONG...
468  */
469 #  define Lw(t)    (((BN_ULONG)(t))&BN_MASK2)
470 #  define Hw(t)    (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2)
471
472 #  define mul_add(r,a,w,c) { \
473         BN_ULLONG t; \
474         t=(BN_ULLONG)w * (a) + (r) + (c); \
475         (r)= Lw(t); \
476         (c)= Hw(t); \
477         }
478
479 #  define mul(r,a,w,c) { \
480         BN_ULLONG t; \
481         t=(BN_ULLONG)w * (a) + (c); \
482         (r)= Lw(t); \
483         (c)= Hw(t); \
484         }
485
486 #  define sqr(r0,r1,a) { \
487         BN_ULLONG t; \
488         t=(BN_ULLONG)(a)*(a); \
489         (r0)=Lw(t); \
490         (r1)=Hw(t); \
491         }
492
493 # elif defined(BN_UMULT_LOHI)
494 #  define mul_add(r,a,w,c) {              \
495         BN_ULONG high,low,ret,tmp=(a);  \
496         ret =  (r);                     \
497         BN_UMULT_LOHI(low,high,w,tmp);  \
498         ret += (c);                     \
499         (c) =  (ret<(c))?1:0;           \
500         (c) += high;                    \
501         ret += low;                     \
502         (c) += (ret<low)?1:0;           \
503         (r) =  ret;                     \
504         }
505
506 #  define mul(r,a,w,c)    {               \
507         BN_ULONG high,low,ret,ta=(a);   \
508         BN_UMULT_LOHI(low,high,w,ta);   \
509         ret =  low + (c);               \
510         (c) =  high;                    \
511         (c) += (ret<low)?1:0;           \
512         (r) =  ret;                     \
513         }
514
515 #  define sqr(r0,r1,a)    {               \
516         BN_ULONG tmp=(a);               \
517         BN_UMULT_LOHI(r0,r1,tmp,tmp);   \
518         }
519
520 # elif defined(BN_UMULT_HIGH)
521 #  define mul_add(r,a,w,c) {              \
522         BN_ULONG high,low,ret,tmp=(a);  \
523         ret =  (r);                     \
524         high=  BN_UMULT_HIGH(w,tmp);    \
525         ret += (c);                     \
526         low =  (w) * tmp;               \
527         (c) =  (ret<(c))?1:0;           \
528         (c) += high;                    \
529         ret += low;                     \
530         (c) += (ret<low)?1:0;           \
531         (r) =  ret;                     \
532         }
533
534 #  define mul(r,a,w,c)    {               \
535         BN_ULONG high,low,ret,ta=(a);   \
536         low =  (w) * ta;                \
537         high=  BN_UMULT_HIGH(w,ta);     \
538         ret =  low + (c);               \
539         (c) =  high;                    \
540         (c) += (ret<low)?1:0;           \
541         (r) =  ret;                     \
542         }
543
544 #  define sqr(r0,r1,a)    {               \
545         BN_ULONG tmp=(a);               \
546         (r0) = tmp * tmp;               \
547         (r1) = BN_UMULT_HIGH(tmp,tmp);  \
548         }
549
550 # else
551 /*************************************************************
552  * No long long type
553  */
554
555 #  define LBITS(a)        ((a)&BN_MASK2l)
556 #  define HBITS(a)        (((a)>>BN_BITS4)&BN_MASK2l)
557 #  define L2HBITS(a)      (((a)<<BN_BITS4)&BN_MASK2)
558
559 #  define LLBITS(a)       ((a)&BN_MASKl)
560 #  define LHBITS(a)       (((a)>>BN_BITS2)&BN_MASKl)
561 #  define LL2HBITS(a)     ((BN_ULLONG)((a)&BN_MASKl)<<BN_BITS2)
562
563 #  define mul64(l,h,bl,bh) \
564         { \
565         BN_ULONG m,m1,lt,ht; \
566  \
567         lt=l; \
568         ht=h; \
569         m =(bh)*(lt); \
570         lt=(bl)*(lt); \
571         m1=(bl)*(ht); \
572         ht =(bh)*(ht); \
573         m=(m+m1)&BN_MASK2; if (m < m1) ht+=L2HBITS((BN_ULONG)1); \
574         ht+=HBITS(m); \
575         m1=L2HBITS(m); \
576         lt=(lt+m1)&BN_MASK2; if (lt < m1) ht++; \
577         (l)=lt; \
578         (h)=ht; \
579         }
580
581 #  define sqr64(lo,ho,in) \
582         { \
583         BN_ULONG l,h,m; \
584  \
585         h=(in); \
586         l=LBITS(h); \
587         h=HBITS(h); \
588         m =(l)*(h); \
589         l*=l; \
590         h*=h; \
591         h+=(m&BN_MASK2h1)>>(BN_BITS4-1); \
592         m =(m&BN_MASK2l)<<(BN_BITS4+1); \
593         l=(l+m)&BN_MASK2; if (l < m) h++; \
594         (lo)=l; \
595         (ho)=h; \
596         }
597
598 #  define mul_add(r,a,bl,bh,c) { \
599         BN_ULONG l,h; \
600  \
601         h= (a); \
602         l=LBITS(h); \
603         h=HBITS(h); \
604         mul64(l,h,(bl),(bh)); \
605  \
606         /* non-multiply part */ \
607         l=(l+(c))&BN_MASK2; if (l < (c)) h++; \
608         (c)=(r); \
609         l=(l+(c))&BN_MASK2; if (l < (c)) h++; \
610         (c)=h&BN_MASK2; \
611         (r)=l; \
612         }
613
614 #  define mul(r,a,bl,bh,c) { \
615         BN_ULONG l,h; \
616  \
617         h= (a); \
618         l=LBITS(h); \
619         h=HBITS(h); \
620         mul64(l,h,(bl),(bh)); \
621  \
622         /* non-multiply part */ \
623         l+=(c); if ((l&BN_MASK2) < (c)) h++; \
624         (c)=h&BN_MASK2; \
625         (r)=l&BN_MASK2; \
626         }
627 # endif                         /* !BN_LLONG */
628
629 void BN_RECP_CTX_init(BN_RECP_CTX *recp);
630 void BN_MONT_CTX_init(BN_MONT_CTX *ctx);
631
632 void bn_init(BIGNUM *a);
633 void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb);
634 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
635 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b);
636 void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp);
637 void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a);
638 void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a);
639 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n);
640 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl);
641 void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
642                       int dna, int dnb, BN_ULONG *t);
643 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b,
644                            int n, int tna, int tnb, BN_ULONG *t);
645 void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t);
646 void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n);
647 void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2,
648                           BN_ULONG *t);
649 BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
650                            int cl, int dl);
651 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
652                 const BN_ULONG *np, const BN_ULONG *n0, int num);
653
654 BIGNUM *int_bn_mod_inverse(BIGNUM *in,
655                            const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,
656                            int *noinv);
657
658 static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits)
659 {
660     if (bits > (INT_MAX - BN_BITS2 + 1))
661         return NULL;
662
663     if (((bits+BN_BITS2-1)/BN_BITS2) <= (a)->dmax)
664         return a;
665
666     return bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2);
667 }
668
669 int bn_check_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx,
670                       int do_trial_division, BN_GENCB *cb);
671
672 #endif