Ignore:
Timestamp:
Jan 9, 2017, 11:09:38 AM (3 years ago)
Author:
jrpelegrina
Message:

Update new version: 3.15.02

File:
1 edited

Legend:

Unmodified
Added
Removed
  • filezilla/trunk/fuentes/src/putty/sshbn.h

    r130 r3185  
    11/*
    22 * 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 *    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.
    753 */
    854
     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
    9163/*
    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.
    21166 */
    22 
    23 #if defined __SIZEOF_INT128__
    24 /* gcc and clang both provide a __uint128_t type on 64-bit targets
    25  * (and, when they do, indicate its presence by the above macro),
    26  * using the same 'two machine registers' kind of code generation that
    27  * 32-bit targets use for 64-bit ints. If we have one of these, we can
    28  * use a 64-bit BignumInt and a 128-bit BignumDblInt. */
    29 typedef unsigned long long BignumInt;
    30 typedef __uint128_t BignumDblInt;
    31 #define BIGNUM_INT_MASK  0xFFFFFFFFFFFFFFFFULL
    32 #define BIGNUM_TOP_BIT   0x8000000000000000ULL
    33 #define BIGNUM_INT_BITS  64
    34 #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  0xFFFFFFFFUL
    44 #define BIGNUM_TOP_BIT   0x80000000UL
    45 #define BIGNUM_INT_BITS  32
    46 #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_IX86
    52 typedef unsigned __int32 BignumInt;
    53 typedef unsigned __int64 BignumDblInt;
    54 #define BIGNUM_INT_MASK  0xFFFFFFFFUL
    55 #define BIGNUM_TOP_BIT   0x80000000UL
    56 #define BIGNUM_INT_BITS  32
    57 #define MUL_WORD(w1, w2) ((BignumDblInt)w1 * w2)
    58 /* Note: MASM interprets array subscripts in the macro arguments as
    59  * assembler syntax, which gives the wrong answer. Don't supply them.
    60  * <http://msdn2.microsoft.com/en-us/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 _LP64
    69 /* 64-bit architectures can do 32x32->64 chunks at a time */
    70 typedef unsigned int BignumInt;
    71 typedef unsigned long BignumDblInt;
    72 #define BIGNUM_INT_MASK  0xFFFFFFFFU
    73 #define BIGNUM_TOP_BIT   0x80000000U
    74 #define BIGNUM_INT_BITS  32
    75 #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 _LLP64
    82 /* 64-bit 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  0xFFFFFFFFUL
    86 #define BIGNUM_TOP_BIT   0x80000000UL
    87 #define BIGNUM_INT_BITS  32
    88 #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 #else
    95 /* Fallback for all other cases */
    96 typedef unsigned short BignumInt;
    97 typedef unsigned long BignumDblInt;
    98 #define BIGNUM_INT_MASK  0xFFFFU
    99 #define BIGNUM_TOP_BIT   0x8000U
    100 #define BIGNUM_INT_BITS  16
    101 #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 #endif
    108 
    109167#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 TracChangeset for help on using the changeset viewer.