sshbn.h

   1 /*
   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.
   7  */
   8
   9 /*
  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.
  21  */
  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
 109 #define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)