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
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
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.
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 __uint64_t 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; \
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) \
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 { \
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; \
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; \
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; \
109 #define BIGNUM_INT_BYTES (BIGNUM_INT_BITS / 8)