2 * sshbn.h: the assorted conditional definitions of BignumInt and
3 * multiply macros used throughout the bignum code to treat numbers as
4 * arrays of the most conveniently sized word for the target machine.
5 * Exported so that other code (e.g. poly1305) can use it too.
7 * This file must export, in whatever ifdef branch it ends up in:
9 * - two types: 'BignumInt' and 'BignumCarry'. BignumInt is an
10 * unsigned integer type which will be used as the base word size
11 * for all bignum operations. BignumCarry is an unsigned integer
12 * type used to hold the carry flag taken as input and output by
13 * the BignumADC macro (see below).
15 * - four constant macros: BIGNUM_INT_BITS, BIGNUM_INT_BYTES,
16 * BIGNUM_TOP_BIT, BIGNUM_INT_MASK. These should be more or less
17 * self-explanatory, but just in case, they give the number of bits
18 * in BignumInt, the number of bytes that works out to, the
19 * BignumInt value consisting of only the top bit, and the
20 * BignumInt value with all bits set.
22 * - four statement macros: BignumADC, BignumMUL, BignumMULADD,
23 * BignumMULADD2. These do various kinds of multi-word arithmetic,
24 * and all produce two output values.
25 * * BignumADC(ret,retc,a,b,c) takes input BignumInt values a,b
26 * and a BignumCarry c, and outputs a BignumInt ret = a+b+c and
27 * a BignumCarry retc which is the carry off the top of that
29 * * BignumMUL(rh,rl,a,b) returns the two halves of the
30 * double-width product a*b.
31 * * BignumMULADD(rh,rl,a,b,addend) returns the two halves of the
32 * double-width value a*b + addend.
33 * * BignumMULADD2(rh,rl,a,b,addend1,addend2) returns the two
34 * halves of the double-width value a*b + addend1 + addend2.
36 * Every branch of the main ifdef below defines the type BignumInt and
37 * the value BIGNUM_INT_BITS. The other three constant macros are
38 * filled in by common code further down.
40 * Most branches also define a macro DEFINE_BIGNUMDBLINT containing a
41 * typedef statement which declares a type _twice_ the length of a
42 * BignumInt. This causes the common code further down to produce a
43 * default implementation of the four statement macros in terms of
44 * that double-width type, and also to defined BignumCarry to be
47 * However, if a particular compile target does not have a type twice
48 * the length of the BignumInt you want to use but it does provide
49 * some alternative means of doing add-with-carry and double-word
50 * multiply, then the ifdef branch in question can just define
51 * BignumCarry and the four statement macros itself, and that's fine
55 #if defined __SIZEOF_INT128__
58 * 64-bit BignumInt using gcc/clang style 128-bit BignumDblInt.
60 * gcc and clang both provide a __uint128_t type on 64-bit targets
61 * (and, when they do, indicate its presence by the above macro),
62 * using the same 'two machine registers' kind of code generation
63 * that 32-bit targets use for 64-bit ints.
66 typedef unsigned long long BignumInt;
67 #define BIGNUM_INT_BITS 64
68 #define DEFINE_BIGNUMDBLINT typedef __uint128_t BignumDblInt
70 #elif defined __GNUC__ || defined _LLP64 || __STDC__ >= 199901L
72 /* 32-bit BignumInt, using C99 unsigned long long as BignumDblInt */
74 typedef unsigned int BignumInt;
75 #define BIGNUM_INT_BITS 32
76 #define DEFINE_BIGNUMDBLINT typedef unsigned long long BignumDblInt
78 #elif defined _MSC_VER && defined _M_IX86
80 /* 32-bit BignumInt, using Visual Studio __int64 as BignumDblInt */
82 typedef unsigned int BignumInt;
83 #define BIGNUM_INT_BITS 32
84 #define DEFINE_BIGNUMDBLINT typedef unsigned __int64 BignumDblInt
89 * 32-bit BignumInt, using unsigned long itself as BignumDblInt.
91 * Only for platforms where long is 64 bits, of course.
94 typedef unsigned int BignumInt;
95 #define BIGNUM_INT_BITS 32
96 #define DEFINE_BIGNUMDBLINT typedef unsigned long BignumDblInt
101 * 16-bit BignumInt, using unsigned long as BignumDblInt.
103 * This is the final fallback for real emergencies: C89 guarantees
104 * unsigned short/long to be at least the required sizes, so this
105 * should work on any C implementation at all. But it'll be
106 * noticeably slow, so if you find yourself in this case you
107 * probably want to move heaven and earth to find an alternative!
110 typedef unsigned short BignumInt;
111 #define BIGNUM_INT_BITS 16
112 #define DEFINE_BIGNUMDBLINT typedef unsigned long BignumDblInt
117 * Common code across all branches of that ifdef: define the three
118 * easy constant macros in terms of BIGNUM_INT_BITS.
120 #define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)
121 #define BIGNUM_TOP_BIT (((BignumInt)1) << (BIGNUM_INT_BITS-1))
122 #define BIGNUM_INT_MASK (BIGNUM_TOP_BIT | (BIGNUM_TOP_BIT-1))
125 * Common code across _most_ branches of the ifdef: define a set of
126 * statement macros in terms of the BignumDblInt type provided. In
127 * this case, we also define BignumCarry to be the same thing as
128 * BignumInt, for simplicity.
130 #ifdef DEFINE_BIGNUMDBLINT
132 typedef BignumInt BignumCarry;
133 #define BignumADC(ret, retc, a, b, c) do \
135 DEFINE_BIGNUMDBLINT; \
136 BignumDblInt ADC_temp = (BignumInt)(a); \
137 ADC_temp += (BignumInt)(b); \
139 (ret) = (BignumInt)ADC_temp; \
140 (retc) = (BignumCarry)(ADC_temp >> BIGNUM_INT_BITS); \
143 #define BignumMUL(rh, rl, a, b) do \
145 DEFINE_BIGNUMDBLINT; \
146 BignumDblInt MUL_temp = (BignumInt)(a); \
147 MUL_temp *= (BignumInt)(b); \
148 (rh) = (BignumInt)(MUL_temp >> BIGNUM_INT_BITS); \
149 (rl) = (BignumInt)(MUL_temp); \
152 #define BignumMULADD(rh, rl, a, b, addend) do \
154 DEFINE_BIGNUMDBLINT; \
155 BignumDblInt MUL_temp = (BignumInt)(a); \
156 MUL_temp *= (BignumInt)(b); \
157 MUL_temp += (BignumInt)(addend); \
158 (rh) = (BignumInt)(MUL_temp >> BIGNUM_INT_BITS); \
159 (rl) = (BignumInt)(MUL_temp); \
162 #define BignumMULADD2(rh, rl, a, b, addend1, addend2) do \
164 DEFINE_BIGNUMDBLINT; \
165 BignumDblInt MUL_temp = (BignumInt)(a); \
166 MUL_temp *= (BignumInt)(b); \
167 MUL_temp += (BignumInt)(addend1); \
168 MUL_temp += (BignumInt)(addend2); \
169 (rh) = (BignumInt)(MUL_temp >> BIGNUM_INT_BITS); \
170 (rl) = (BignumInt)(MUL_temp); \
173 #endif /* DEFINE_BIGNUMDBLINT */