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