-
Notifications
You must be signed in to change notification settings - Fork 704
/
limbs.inl
162 lines (149 loc) · 5.03 KB
/
limbs.inl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
/* Copyright 2016 Brian Smith.
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY
* SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
* OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
* CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
#include "limbs.h"
#include "ring-core/check.h"
#if defined(_MSC_VER) && !defined(__clang__)
#pragma warning(push, 3)
#include <intrin.h>
#pragma warning(pop)
/* MSVC 2015 RC, when compiling for x86 with /Ox (at least), miscompiles
* _addcarry_u32(c, 0, prod_hi, &x) like so:
*
* add eax,esi ; The previous add that might have set the carry flag.
* xor esi,esi ; OOPS! Carry flag is now reset!
* mov dword ptr [edi-4],eax
* adc esi,dword ptr [prod_hi]
*
* We test with MSVC 2015 update 2, so make sure we're using a version at least
* as new as that. */
#if _MSC_FULL_VER < 190023918
#error "MSVC 2015 Update 2 or later is required."
#endif
typedef uint8_t Carry;
#if LIMB_BITS == 64
#pragma intrinsic(_addcarry_u64, _subborrow_u64)
#define RING_CORE_ADDCARRY_INTRINSIC _addcarry_u64
#define RING_CORE_SUBBORROW_INTRINSIC _subborrow_u64
#elif LIMB_BITS == 32
#pragma intrinsic(_addcarry_u32, _subborrow_u32)
#define RING_CORE_ADDCARRY_INTRINSIC _addcarry_u32
#define RING_CORE_SUBBORROW_INTRINSIC _subborrow_u32
typedef uint64_t DoubleLimb;
#endif
#else
typedef Limb Carry;
#if LIMB_BITS == 64
typedef __uint128_t DoubleLimb;
#elif LIMB_BITS == 32
typedef uint64_t DoubleLimb;
#endif
#endif
/* |*r = a + b + carry_in|, returning carry out bit. |carry_in| must be 0 or 1.
*/
static inline Carry limb_adc(Limb *r, Limb a, Limb b, Carry carry_in) {
dev_assert_secret(carry_in == 0 || carry_in == 1);
Carry ret;
#if defined(RING_CORE_ADDCARRY_INTRINSIC)
ret = RING_CORE_ADDCARRY_INTRINSIC(carry_in, a, b, r);
#else
DoubleLimb x = (DoubleLimb)a + b + carry_in;
*r = (Limb)x;
ret = (Carry)(x >> LIMB_BITS);
#endif
dev_assert_secret(ret == 0 || ret == 1);
return ret;
}
/* |*r = a + b|, returning carry bit. */
static inline Carry limb_add(Limb *r, Limb a, Limb b) {
Carry ret;
#if defined(RING_CORE_ADDCARRY_INTRINSIC)
ret = RING_CORE_ADDCARRY_INTRINSIC(0, a, b, r);
#else
DoubleLimb x = (DoubleLimb)a + b;
*r = (Limb)x;
ret = (Carry)(x >> LIMB_BITS);
#endif
dev_assert_secret(ret == 0 || ret == 1);
return ret;
}
/* |*r = a - b - borrow_in|, returning the borrow out bit. |borrow_in| must be
* 0 or 1. */
static inline Carry limb_sbb(Limb *r, Limb a, Limb b, Carry borrow_in) {
dev_assert_secret(borrow_in == 0 || borrow_in == 1);
Carry ret;
#if defined(RING_CORE_SUBBORROW_INTRINSIC)
ret = RING_CORE_SUBBORROW_INTRINSIC(borrow_in, a, b, r);
#else
DoubleLimb x = (DoubleLimb)a - b - borrow_in;
*r = (Limb)x;
ret = (Carry)((x >> LIMB_BITS) & 1);
#endif
dev_assert_secret(ret == 0 || ret == 1);
return ret;
}
/* |*r = a - b|, returning borrow bit. */
static inline Carry limb_sub(Limb *r, Limb a, Limb b) {
Carry ret;
#if defined(RING_CORE_SUBBORROW_INTRINSIC)
ret = RING_CORE_SUBBORROW_INTRINSIC(0, a, b, r);
#else
DoubleLimb x = (DoubleLimb)a - b;
*r = (Limb)x;
ret = (Carry)((x >> LIMB_BITS) & 1);
#endif
dev_assert_secret(ret == 0 || ret == 1);
return ret;
}
static inline Carry limbs_add(Limb r[], const Limb a[], const Limb b[],
size_t num_limbs) {
debug_assert_nonsecret(num_limbs >= 1);
Carry carry = limb_add(&r[0], a[0], b[0]);
for (size_t i = 1; i < num_limbs; ++i) {
carry = limb_adc(&r[i], a[i], b[i], carry);
}
return carry;
}
/* |r -= s|, returning the borrow. */
static inline Carry limbs_sub(Limb r[], const Limb a[], const Limb b[],
size_t num_limbs) {
debug_assert_nonsecret(num_limbs >= 1);
Carry borrow = limb_sub(&r[0], a[0], b[0]);
for (size_t i = 1; i < num_limbs; ++i) {
borrow = limb_sbb(&r[i], a[i], b[i], borrow);
}
return borrow;
}
static inline void limbs_copy(Limb r[], const Limb a[], size_t num_limbs) {
for (size_t i = 0; i < num_limbs; ++i) {
r[i] = a[i];
}
}
static inline void limbs_select(Limb r[], const Limb table[],
size_t num_limbs, size_t num_entries,
crypto_word index) {
for (size_t i = 0; i < num_limbs; ++i) {
r[i] = 0;
}
for (size_t e = 0; e < num_entries; ++e) {
Limb equal = constant_time_eq_w(index, e);
for (size_t i = 0; i < num_limbs; ++i) {
r[i] = constant_time_select_w(equal, table[(e * num_limbs) + i], r[i]);
}
}
}
static inline void limbs_zero(Limb r[], size_t num_limbs) {
for (size_t i = 0; i < num_limbs; ++i) {
r[i] = 0;
}
}