source: filezilla/trunk/fuentes/src/putty/sshbn.h @ 3185

Last change on this file since 3185 was 3185, checked in by jrpelegrina, 3 years ago

Update new version: 3.15.02

File size: 9.6 KB
Line 
1/*
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.
6 *
7 * This file must export, in whatever ifdef branch it ends up in:
8 *
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).
14 *
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.
21 *
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
28 *       addition.
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.
35 *
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.
39 *
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
45 * BignumInt.
46 *
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
52 * too.
53 */
54
55#if defined __SIZEOF_INT128__
56
57  /*
58   * 64-bit BignumInt using gcc/clang style 128-bit BignumDblInt.
59   *
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.
64   */
65
66  typedef unsigned long long BignumInt;
67  #define BIGNUM_INT_BITS 64
68  #define DEFINE_BIGNUMDBLINT typedef __uint128_t BignumDblInt
69
70#elif defined _MSC_VER && defined _M_AMD64
71
72  /*
73   * 64-bit BignumInt, using Visual Studio x86-64 compiler intrinsics.
74   *
75   * 64-bit Visual Studio doesn't provide very much in the way of help
76   * here: there's no int128 type, and also no inline assembler giving
77   * us direct access to the x86-64 MUL or ADC instructions. However,
78   * there are compiler intrinsics giving us that access, so we can
79   * use those - though it turns out we have to be a little careful,
80   * since they seem to generate wrong code if their pointer-typed
81   * output parameters alias their inputs. Hence all the internal temp
82   * variables inside the macros.
83   */
84
85  #include <intrin.h>
86  typedef unsigned char BignumCarry; /* the type _addcarry_u64 likes to use */
87  typedef unsigned __int64 BignumInt;
88  #define BIGNUM_INT_BITS 64
89  #define BignumADC(ret, retc, a, b, c) do                \
90      {                                                   \
91          BignumInt ADC_tmp;                              \
92          (retc) = _addcarry_u64(c, a, b, &ADC_tmp);      \
93          (ret) = ADC_tmp;                                \
94      } while (0)
95  #define BignumMUL(rh, rl, a, b) do              \
96      {                                           \
97          BignumInt MULADD_hi;                    \
98          (rl) = _umul128(a, b, &MULADD_hi);      \
99          (rh) = MULADD_hi;                       \
100      } while (0)
101  #define BignumMULADD(rh, rl, a, b, addend) do                           \
102      {                                                                   \
103          BignumInt MULADD_lo, MULADD_hi;                                 \
104          MULADD_lo = _umul128(a, b, &MULADD_hi);                         \
105          MULADD_hi += _addcarry_u64(0, MULADD_lo, (addend), &(rl));     \
106          (rh) = MULADD_hi;                                               \
107      } while (0)
108  #define BignumMULADD2(rh, rl, a, b, addend1, addend2) do                \
109      {                                                                   \
110          BignumInt MULADD_lo1, MULADD_lo2, MULADD_hi;                    \
111          MULADD_lo1 = _umul128(a, b, &MULADD_hi);                        \
112          MULADD_hi += _addcarry_u64(0, MULADD_lo1, (addend1), &MULADD_lo2); \
113          MULADD_hi += _addcarry_u64(0, MULADD_lo2, (addend2), &(rl));    \
114          (rh) = MULADD_hi;                                               \
115      } while (0)
116
117#elif defined __GNUC__ || defined _LLP64 || __STDC__ >= 199901L
118
119  /* 32-bit BignumInt, using C99 unsigned long long as BignumDblInt */
120
121  typedef unsigned int BignumInt;
122  #define BIGNUM_INT_BITS 32
123  #define DEFINE_BIGNUMDBLINT typedef unsigned long long BignumDblInt
124
125#elif defined _MSC_VER && defined _M_IX86
126
127  /* 32-bit BignumInt, using Visual Studio __int64 as BignumDblInt */
128
129  typedef unsigned int BignumInt;
130  #define BIGNUM_INT_BITS  32
131  #define DEFINE_BIGNUMDBLINT typedef unsigned __int64 BignumDblInt
132
133#elif defined _LP64
134
135  /*
136   * 32-bit BignumInt, using unsigned long itself as BignumDblInt.
137   *
138   * Only for platforms where long is 64 bits, of course.
139   */
140
141  typedef unsigned int BignumInt;
142  #define BIGNUM_INT_BITS  32
143  #define DEFINE_BIGNUMDBLINT typedef unsigned long BignumDblInt
144
145#else
146
147  /*
148   * 16-bit BignumInt, using unsigned long as BignumDblInt.
149   *
150   * This is the final fallback for real emergencies: C89 guarantees
151   * unsigned short/long to be at least the required sizes, so this
152   * should work on any C implementation at all. But it'll be
153   * noticeably slow, so if you find yourself in this case you
154   * probably want to move heaven and earth to find an alternative!
155   */
156
157  typedef unsigned short BignumInt;
158  #define BIGNUM_INT_BITS  16
159  #define DEFINE_BIGNUMDBLINT typedef unsigned long BignumDblInt
160
161#endif
162
163/*
164 * Common code across all branches of that ifdef: define the three
165 * easy constant macros in terms of BIGNUM_INT_BITS.
166 */
167#define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)
168#define BIGNUM_TOP_BIT (((BignumInt)1) << (BIGNUM_INT_BITS-1))
169#define BIGNUM_INT_MASK (BIGNUM_TOP_BIT | (BIGNUM_TOP_BIT-1))
170
171/*
172 * Common code across _most_ branches of the ifdef: define a set of
173 * statement macros in terms of the BignumDblInt type provided. In
174 * this case, we also define BignumCarry to be the same thing as
175 * BignumInt, for simplicity.
176 */
177#ifdef DEFINE_BIGNUMDBLINT
178
179  typedef BignumInt BignumCarry;
180  #define BignumADC(ret, retc, a, b, c) do                        \
181      {                                                           \
182          DEFINE_BIGNUMDBLINT;                                    \
183          BignumDblInt ADC_temp = (BignumInt)(a);                 \
184          ADC_temp += (BignumInt)(b);                             \
185          ADC_temp += (c);                                        \
186          (ret) = (BignumInt)ADC_temp;                            \
187          (retc) = (BignumCarry)(ADC_temp >> BIGNUM_INT_BITS);    \
188      } while (0)
189 
190  #define BignumMUL(rh, rl, a, b) do                              \
191      {                                                           \
192          DEFINE_BIGNUMDBLINT;                                    \
193          BignumDblInt MUL_temp = (BignumInt)(a);                 \
194          MUL_temp *= (BignumInt)(b);                             \
195          (rh) = (BignumInt)(MUL_temp >> BIGNUM_INT_BITS);        \
196          (rl) = (BignumInt)(MUL_temp);                           \
197      } while (0)
198 
199  #define BignumMULADD(rh, rl, a, b, addend) do                   \
200      {                                                           \
201          DEFINE_BIGNUMDBLINT;                                    \
202          BignumDblInt MUL_temp = (BignumInt)(a);                 \
203          MUL_temp *= (BignumInt)(b);                             \
204          MUL_temp += (BignumInt)(addend);                        \
205          (rh) = (BignumInt)(MUL_temp >> BIGNUM_INT_BITS);        \
206          (rl) = (BignumInt)(MUL_temp);                           \
207      } while (0)
208 
209  #define BignumMULADD2(rh, rl, a, b, addend1, addend2) do        \
210      {                                                           \
211          DEFINE_BIGNUMDBLINT;                                    \
212          BignumDblInt MUL_temp = (BignumInt)(a);                 \
213          MUL_temp *= (BignumInt)(b);                             \
214          MUL_temp += (BignumInt)(addend1);                       \
215          MUL_temp += (BignumInt)(addend2);                       \
216          (rh) = (BignumInt)(MUL_temp >> BIGNUM_INT_BITS);        \
217          (rl) = (BignumInt)(MUL_temp);                           \
218      } while (0)
219
220#endif /* DEFINE_BIGNUMDBLINT */
Note: See TracBrowser for help on using the repository browser.