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