Changeset 3185 for filezilla/trunk/fuentes/src/putty/sshbn.h
 Timestamp:
 Jan 9, 2017, 11:09:38 AM (3 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

filezilla/trunk/fuentes/src/putty/sshbn.h
r130 r3185 1 1 /* 2 2 * sshbn.h: the assorted conditional definitions of BignumInt and 3 * multiply/divide macros used throughout the bignum code to treat 4 * numbers as arrays of the most conveniently sized word for the 5 * target machine. Exported so that other code (e.g. poly1305) can use 6 * it too. 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 * selfexplanatory, 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 multiword 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 * doublewidth product a*b. 31 * * BignumMULADD(rh,rl,a,b,addend) returns the two halves of the 32 * doublewidth value a*b + addend. 33 * * BignumMULADD2(rh,rl,a,b,addend1,addend2) returns the two 34 * halves of the doublewidth 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 doublewidth 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 addwithcarry and doubleword 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. 7 53 */ 8 54 55 #if defined __SIZEOF_INT128__ 56 57 /* 58 * 64bit BignumInt using gcc/clang style 128bit BignumDblInt. 59 * 60 * gcc and clang both provide a __uint128_t type on 64bit 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 32bit targets use for 64bit 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 * 64bit BignumInt, using Visual Studio x8664 compiler intrinsics. 74 * 75 * 64bit 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 x8664 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 pointertyped 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 /* 32bit 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 /* 32bit 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 * 32bit 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 * 16bit 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 9 163 /* 10 * Usage notes: 11 * * Do not call the DIVMOD_WORD macro with expressions such as array 12 * subscripts, as some implementations object to this (see below). 13 * * Note that none of the division methods below will cope if the 14 * quotient won't fit into BIGNUM_INT_BITS. Callers should be careful 15 * to avoid this case. 16 * If this condition occurs, in the case of the x86 DIV instruction, 17 * an overflow exception will occur, which (according to a correspondent) 18 * will manifest on Windows as something like 19 * 0xC0000095: Integer overflow 20 * The C variant won't give the right answer, either. 164 * Common code across all branches of that ifdef: define the three 165 * easy constant macros in terms of BIGNUM_INT_BITS. 21 166 */ 22 23 #if defined __SIZEOF_INT128__24 /* gcc and clang both provide a __uint128_t type on 64bit targets25 * (and, when they do, indicate its presence by the above macro),26 * using the same 'two machine registers' kind of code generation that27 * 32bit targets use for 64bit ints. If we have one of these, we can28 * use a 64bit BignumInt and a 128bit BignumDblInt. */29 typedef unsigned long long BignumInt;30 typedef __uint128_t BignumDblInt;31 #define BIGNUM_INT_MASK 0xFFFFFFFFFFFFFFFFULL32 #define BIGNUM_TOP_BIT 0x8000000000000000ULL33 #define BIGNUM_INT_BITS 6434 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)35 #define DIVMOD_WORD(q, r, hi, lo, w) do { \36 BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS)  lo; \37 q = n / w; \38 r = n % w; \39 } while (0)40 #elif defined __GNUC__ && defined __i386__41 typedef unsigned long BignumInt;42 typedef unsigned long long BignumDblInt;43 #define BIGNUM_INT_MASK 0xFFFFFFFFUL44 #define BIGNUM_TOP_BIT 0x80000000UL45 #define BIGNUM_INT_BITS 3246 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)47 #define DIVMOD_WORD(q, r, hi, lo, w) \48 __asm__("div %2" : \49 "=d" (r), "=a" (q) : \50 "r" (w), "d" (hi), "a" (lo))51 #elif defined _MSC_VER && defined _M_IX8652 typedef unsigned __int32 BignumInt;53 typedef unsigned __int64 BignumDblInt;54 #define BIGNUM_INT_MASK 0xFFFFFFFFUL55 #define BIGNUM_TOP_BIT 0x80000000UL56 #define BIGNUM_INT_BITS 3257 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)58 /* Note: MASM interprets array subscripts in the macro arguments as59 * assembler syntax, which gives the wrong answer. Don't supply them.60 * <http://msdn2.microsoft.com/enus/library/bf1dw62z.aspx> */61 #define DIVMOD_WORD(q, r, hi, lo, w) do { \62 __asm mov edx, hi \63 __asm mov eax, lo \64 __asm div w \65 __asm mov r, edx \66 __asm mov q, eax \67 } while(0)68 #elif defined _LP6469 /* 64bit architectures can do 32x32>64 chunks at a time */70 typedef unsigned int BignumInt;71 typedef unsigned long BignumDblInt;72 #define BIGNUM_INT_MASK 0xFFFFFFFFU73 #define BIGNUM_TOP_BIT 0x80000000U74 #define BIGNUM_INT_BITS 3275 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)76 #define DIVMOD_WORD(q, r, hi, lo, w) do { \77 BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS)  lo; \78 q = n / w; \79 r = n % w; \80 } while (0)81 #elif defined _LLP6482 /* 64bit architectures in which unsigned long is 32 bits, not 64 */83 typedef unsigned long BignumInt;84 typedef unsigned long long BignumDblInt;85 #define BIGNUM_INT_MASK 0xFFFFFFFFUL86 #define BIGNUM_TOP_BIT 0x80000000UL87 #define BIGNUM_INT_BITS 3288 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)89 #define DIVMOD_WORD(q, r, hi, lo, w) do { \90 BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS)  lo; \91 q = n / w; \92 r = n % w; \93 } while (0)94 #else95 /* Fallback for all other cases */96 typedef unsigned short BignumInt;97 typedef unsigned long BignumDblInt;98 #define BIGNUM_INT_MASK 0xFFFFU99 #define BIGNUM_TOP_BIT 0x8000U100 #define BIGNUM_INT_BITS 16101 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)102 #define DIVMOD_WORD(q, r, hi, lo, w) do { \103 BignumDblInt n = (((BignumDblInt)hi) << BIGNUM_INT_BITS)  lo; \104 q = n / w; \105 r = n % w; \106 } while (0)107 #endif108 109 167 #define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8) 168 #define BIGNUM_TOP_BIT (((BignumInt)1) << (BIGNUM_INT_BITS1)) 169 #define BIGNUM_INT_MASK (BIGNUM_TOP_BIT  (BIGNUM_TOP_BIT1)) 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 TracChangeset
for help on using the changeset viewer.