sshbn.h

   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 */