int256.h 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500
  1. /*
  2. * Copyright 2018 Google LLC.
  3. * Licensed under the Apache License, Version 2.0 (the "License");
  4. * you may not use this file except in compliance with the License.
  5. * You may obtain a copy of the License at
  6. *
  7. * https://www.apache.org/licenses/LICENSE-2.0
  8. *
  9. * Unless required by applicable law or agreed to in writing, software
  10. * distributed under the License is distributed on an "AS IS" BASIS,
  11. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. * See the License for the specific language governing permissions and
  13. * limitations under the License.
  14. */
  15. #ifndef RLWE_INT256_H_
  16. #define RLWE_INT256_H_
  17. #include "absl/numeric/int128.h"
  18. #include "integral_types.h"
  19. #include "third_party/shell-encryption/base/shell_encryption_export.h"
  20. #include "third_party/shell-encryption/base/shell_encryption_export_template.h"
  21. namespace rlwe {
  22. struct uint256_pod;
  23. // An unsigned 256-bit integer type. Thread-compatible.
  24. class SHELL_ENCRYPTION_EXPORT uint256 {
  25. public:
  26. constexpr uint256();
  27. constexpr uint256(absl::uint128 top, absl::uint128 bottom);
  28. // Implicit type conversion is allowed so these behave like familiar int types
  29. #ifndef SWIG
  30. constexpr uint256(int bottom);
  31. constexpr uint256(Uint32 bottom);
  32. #endif
  33. constexpr uint256(Uint8 bottom);
  34. constexpr uint256(unsigned long bottom);
  35. constexpr uint256(unsigned long long bottom);
  36. constexpr uint256(absl::uint128 bottom);
  37. constexpr uint256(const uint256_pod &val);
  38. // Conversion operators to other arithmetic types
  39. constexpr explicit operator bool() const;
  40. constexpr explicit operator char() const;
  41. constexpr explicit operator signed char() const;
  42. constexpr explicit operator unsigned char() const;
  43. constexpr explicit operator char16_t() const;
  44. constexpr explicit operator char32_t() const;
  45. constexpr explicit operator short() const;
  46. constexpr explicit operator unsigned short() const;
  47. constexpr explicit operator int() const;
  48. constexpr explicit operator unsigned int() const;
  49. constexpr explicit operator long() const;
  50. constexpr explicit operator unsigned long() const;
  51. constexpr explicit operator long long() const;
  52. constexpr explicit operator unsigned long long() const;
  53. constexpr explicit operator absl::int128() const;
  54. constexpr explicit operator absl::uint128() const;
  55. explicit operator float() const;
  56. explicit operator double() const;
  57. explicit operator long double() const;
  58. // Trivial copy constructor, assignment operator and destructor.
  59. void Initialize(absl::uint128 top, absl::uint128 bottom);
  60. // Arithmetic operators.
  61. uint256& operator+=(const uint256& b);
  62. uint256& operator-=(const uint256& b);
  63. uint256& operator*=(const uint256& b);
  64. // Long division/modulo for uint256.
  65. SHELL_ENCRYPTION_EXPORT uint256& operator/=(const uint256& b);
  66. SHELL_ENCRYPTION_EXPORT uint256& operator%=(const uint256& b);
  67. uint256 operator++(int);
  68. uint256 operator--(int);
  69. SHELL_ENCRYPTION_EXPORT uint256& operator<<=(int);
  70. uint256& operator>>=(int);
  71. uint256& operator&=(const uint256& b);
  72. uint256& operator|=(const uint256& b);
  73. uint256& operator^=(const uint256& b);
  74. uint256& operator++();
  75. uint256& operator--();
  76. friend absl::uint128 Uint256Low128(const uint256& v);
  77. friend absl::uint128 Uint256High128(const uint256& v);
  78. // We add "std::" to avoid including all of port.h.
  79. friend SHELL_ENCRYPTION_EXPORT std::ostream& operator<<(std::ostream& o, const uint256& b);
  80. private:
  81. static void DivModImpl(uint256 dividend, uint256 divisor,
  82. uint256* quotient_ret, uint256* remainder_ret);
  83. // Little-endian memory order optimizations can benefit from
  84. // having lo_ first, hi_ last.
  85. // See util/endian/endian.h and Load256/Store256 for storing a uint256.
  86. // Adding any new members will cause sizeof(uint256) tests to fail.
  87. absl::uint128 lo_;
  88. absl::uint128 hi_;
  89. // Uint256Max()
  90. //
  91. // Returns the highest value for a 256-bit unsigned integer.
  92. friend constexpr uint256 Uint256Max();
  93. // Not implemented, just declared for catching automatic type conversions.
  94. uint256(Uint16);
  95. uint256(float v);
  96. uint256(double v);
  97. };
  98. constexpr uint256 Uint256Max() {
  99. return uint256((std::numeric_limits<absl::uint128>::max)(),
  100. (std::numeric_limits<absl::uint128>::max)());
  101. }
  102. // This is a POD form of uint256 which can be used for static variables which
  103. // need to be operated on as uint256.
  104. struct SHELL_ENCRYPTION_EXPORT uint256_pod {
  105. // Note: The ordering of fields is different than 'class uint256' but the
  106. // same as its 2-arg constructor. This enables more obvious initialization
  107. // of static instances, which is the primary reason for this struct in the
  108. // first place. This does not seem to defeat any optimizations wrt
  109. // operations involving this struct.
  110. absl::uint128 hi;
  111. absl::uint128 lo;
  112. };
  113. constexpr uint256_pod kuint256max = {absl::Uint128Max(), absl::Uint128Max()};
  114. // allow uint256 to be logged
  115. extern std::ostream& operator<<(std::ostream& o, const uint256& b);
  116. // Methods to access low and high pieces of 256-bit value.
  117. // Defined externally from uint256 to facilitate conversion
  118. // to native 256-bit types when compilers support them.
  119. inline absl::uint128 Uint256Low128(const uint256& v) { return v.lo_; }
  120. inline absl::uint128 Uint256High128(const uint256& v) { return v.hi_; }
  121. // --------------------------------------------------------------------------
  122. // Implementation details follow
  123. // --------------------------------------------------------------------------
  124. inline bool operator==(const uint256& lhs, const uint256& rhs) {
  125. return (Uint256Low128(lhs) == Uint256Low128(rhs) &&
  126. Uint256High128(lhs) == Uint256High128(rhs));
  127. }
  128. inline bool operator!=(const uint256& lhs, const uint256& rhs) {
  129. return !(lhs == rhs);
  130. }
  131. inline constexpr uint256::uint256() : lo_(0), hi_(0) {}
  132. inline constexpr uint256::uint256(absl::uint128 top, absl::uint128 bottom)
  133. : lo_(bottom), hi_(top) {}
  134. inline constexpr uint256::uint256(const uint256_pod& v)
  135. : lo_(v.lo), hi_(v.hi) {}
  136. inline constexpr uint256::uint256(absl::uint128 bottom) : lo_(bottom), hi_(0) {}
  137. #ifndef SWIG
  138. inline constexpr uint256::uint256(int bottom)
  139. : lo_(bottom), hi_((bottom < 0) ? -1 : 0) {}
  140. inline constexpr uint256::uint256(Uint32 bottom) : lo_(bottom), hi_(0) {}
  141. #endif
  142. inline constexpr uint256::uint256(Uint8 bottom) : lo_(bottom), hi_(0) {}
  143. inline constexpr uint256::uint256(unsigned long bottom)
  144. : lo_(bottom), hi_(0) {}
  145. inline constexpr uint256::uint256(unsigned long long bottom)
  146. : lo_(bottom), hi_(0) {}
  147. inline void uint256::Initialize(absl::uint128 top, absl::uint128 bottom) {
  148. hi_ = top;
  149. lo_ = bottom;
  150. }
  151. // Conversion operators to integer types.
  152. constexpr uint256::operator bool() const { return lo_ || hi_; }
  153. constexpr uint256::operator char() const { return static_cast<char>(lo_); }
  154. constexpr uint256::operator signed char() const {
  155. return static_cast<signed char>(lo_);
  156. }
  157. constexpr uint256::operator unsigned char() const {
  158. return static_cast<unsigned char>(lo_);
  159. }
  160. constexpr uint256::operator char16_t() const {
  161. return static_cast<char16_t>(lo_);
  162. }
  163. constexpr uint256::operator char32_t() const {
  164. return static_cast<char32_t>(lo_);
  165. }
  166. constexpr uint256::operator short() const { return static_cast<short>(lo_); }
  167. constexpr uint256::operator unsigned short() const {
  168. return static_cast<unsigned short>(lo_);
  169. }
  170. constexpr uint256::operator int() const { return static_cast<int>(lo_); }
  171. constexpr uint256::operator unsigned int() const {
  172. return static_cast<unsigned int>(lo_);
  173. }
  174. constexpr uint256::operator long() const { return static_cast<long>(lo_); }
  175. constexpr uint256::operator unsigned long() const {
  176. return static_cast<unsigned long>(lo_);
  177. }
  178. constexpr uint256::operator long long() const {
  179. return static_cast<long long>(lo_);
  180. }
  181. constexpr uint256::operator unsigned long long() const {
  182. return static_cast<unsigned long long>(lo_);
  183. }
  184. constexpr uint256::operator absl::uint128() const { return lo_; }
  185. constexpr uint256::operator absl::int128() const {
  186. return static_cast<absl::int128>(lo_);
  187. }
  188. // Conversion operators to floating point types.
  189. inline uint256::operator float() const {
  190. return static_cast<float>(lo_) + std::ldexp(static_cast<float>(hi_), 128);
  191. }
  192. inline uint256::operator double() const {
  193. return static_cast<double>(lo_) + std::ldexp(static_cast<double>(hi_), 128);
  194. }
  195. inline uint256::operator long double() const {
  196. return static_cast<long double>(lo_) +
  197. std::ldexp(static_cast<long double>(hi_), 128);
  198. }
  199. // Comparison operators.
  200. #define CMP256(op) \
  201. inline bool operator op(const uint256& lhs, const uint256& rhs) { \
  202. return (Uint256High128(lhs) == Uint256High128(rhs)) \
  203. ? (Uint256Low128(lhs) op Uint256Low128(rhs)) \
  204. : (Uint256High128(lhs) op Uint256High128(rhs)); \
  205. }
  206. CMP256(<)
  207. CMP256(>)
  208. CMP256(>=)
  209. CMP256(<=)
  210. #undef CMP256
  211. // Unary operators
  212. inline uint256 operator-(const uint256& val) {
  213. const absl::uint128 hi_flip = ~Uint256High128(val);
  214. const absl::uint128 lo_flip = ~Uint256Low128(val);
  215. const absl::uint128 lo_add = lo_flip + 1;
  216. if (lo_add < lo_flip) {
  217. return uint256(hi_flip + 1, lo_add);
  218. }
  219. return uint256(hi_flip, lo_add);
  220. }
  221. inline bool operator!(const uint256& val) {
  222. return !Uint256High128(val) && !Uint256Low128(val);
  223. }
  224. // Logical operators.
  225. inline uint256 operator~(const uint256& val) {
  226. return uint256(~Uint256High128(val), ~Uint256Low128(val));
  227. }
  228. #define LOGIC256(op) \
  229. inline uint256 operator op(const uint256& lhs, const uint256& rhs) { \
  230. return uint256(Uint256High128(lhs) op Uint256High128(rhs), \
  231. Uint256Low128(lhs) op Uint256Low128(rhs)); \
  232. }
  233. LOGIC256(|)
  234. LOGIC256(&)
  235. LOGIC256(^)
  236. #undef LOGIC256
  237. #define LOGICASSIGN256(op) \
  238. inline uint256& uint256::operator op(const uint256& b) { \
  239. hi_ op b.hi_; \
  240. lo_ op b.lo_; \
  241. return *this; \
  242. }
  243. LOGICASSIGN256(|=)
  244. LOGICASSIGN256(&=)
  245. LOGICASSIGN256(^=)
  246. #undef LOGICASSIGN256
  247. // Shift operators.
  248. inline uint256 operator<<(const uint256& val, int amount) {
  249. uint256 out(val);
  250. out <<= amount;
  251. return out;
  252. }
  253. inline uint256 operator>>(const uint256& val, int amount) {
  254. uint256 out(val);
  255. out >>= amount;
  256. return out;
  257. }
  258. inline uint256& uint256::operator<<=(int amount) {
  259. // uint128 shifts of >= 128 are undefined, so we will need some special-casing
  260. if (amount < 128) {
  261. if (amount != 0) {
  262. hi_ = (hi_ << amount) | (lo_ >> (128 - amount));
  263. lo_ = lo_ << amount;
  264. }
  265. } else if (amount < 256) {
  266. hi_ = lo_ << (amount - 128);
  267. lo_ = 0;
  268. } else {
  269. hi_ = 0;
  270. lo_ = 0;
  271. }
  272. return *this;
  273. }
  274. inline uint256& uint256::operator>>=(int amount) {
  275. // uint128 shifts of >= 128 are undefined, so we will need some special-casing
  276. if (amount < 128) {
  277. if (amount != 0) {
  278. lo_ = (lo_ >> amount) | (hi_ << (128 - amount));
  279. hi_ = hi_ >> amount;
  280. }
  281. } else if (amount < 256) {
  282. lo_ = hi_ >> (amount - 128);
  283. hi_ = 0;
  284. } else {
  285. lo_ = 0;
  286. hi_ = 0;
  287. }
  288. return *this;
  289. }
  290. inline uint256 operator+(const uint256& lhs, const uint256& rhs) {
  291. return uint256(lhs) += rhs;
  292. }
  293. inline uint256 operator-(const uint256& lhs, const uint256& rhs) {
  294. return uint256(lhs) -= rhs;
  295. }
  296. inline uint256 operator*(const uint256& lhs, const uint256& rhs) {
  297. return uint256(lhs) *= rhs;
  298. }
  299. inline uint256 operator/(const uint256& lhs, const uint256& rhs) {
  300. return uint256(lhs) /= rhs;
  301. }
  302. inline uint256 operator%(const uint256& lhs, const uint256& rhs) {
  303. return uint256(lhs) %= rhs;
  304. }
  305. inline uint256& uint256::operator+=(const uint256& b) {
  306. hi_ += b.hi_;
  307. absl::uint128 lolo = lo_ + b.lo_;
  308. if (lolo < lo_)
  309. ++hi_;
  310. lo_ = lolo;
  311. return *this;
  312. }
  313. inline uint256& uint256::operator-=(const uint256& b) {
  314. hi_ -= b.hi_;
  315. if (b.lo_ > lo_)
  316. --hi_;
  317. lo_ -= b.lo_;
  318. return *this;
  319. }
  320. inline uint256& uint256::operator*=(const uint256& b) {
  321. // Computes the product c = a * b modulo 2^256.
  322. //
  323. // We have that
  324. // a = [a.hi_ || a.lo_] and b = [b.hi_ || b.lo_]
  325. // where hi_, lo_ are 128-bit numbers. Further, we have that
  326. // a.lo_ = [a64 || a00] and b.lo_ = [b64 || b00]
  327. // where a64, a00, b64, b00 are 64-bit numbers.
  328. //
  329. // The product c = (a * b mod 2^256) is equal to
  330. // (a.hi_ * b.lo_ + a64 * b64 + b.hi_ * a.lo_ mod 2^128) * 2^128 +
  331. // (a64 * b00 + a00 * b64) * 2^64 +
  332. // (a00 * b00)
  333. //
  334. // The first and last lines can be computed without worrying about the
  335. // carries, and then we add the two elements from the second line.
  336. absl::uint128 a64 = absl::Uint128High64(lo_);
  337. absl::uint128 a00 = absl::Uint128Low64(lo_);
  338. absl::uint128 b64 = absl::Uint128High64(b.lo_);
  339. absl::uint128 b00 = absl::Uint128Low64(b.lo_);
  340. // Compute the high order and low order part of c (safe to ignore carry bits).
  341. this->hi_ = hi_ * b.lo_ + a64 * b64 + lo_ * b.hi_;
  342. this->lo_ = a00 * b00;
  343. // add middle term and capture carry
  344. uint256 middle_term = uint256(a64 * b00) + uint256(a00 * b64);
  345. *this += middle_term << 64;
  346. return *this;
  347. }
  348. inline uint256 uint256::operator++(int) {
  349. uint256 tmp(*this);
  350. lo_++;
  351. if (lo_ == 0) hi_++; // If there was a wrap around, increase the high word.
  352. return tmp;
  353. }
  354. inline uint256 uint256::operator--(int) {
  355. uint256 tmp(*this);
  356. if (lo_ == 0) hi_--; // If it wraps around, decrease the high word.
  357. lo_--;
  358. return tmp;
  359. }
  360. inline uint256& uint256::operator++() {
  361. lo_++;
  362. if (lo_ == 0) hi_++; // If there was a wrap around, increase the high word.
  363. return *this;
  364. }
  365. inline uint256& uint256::operator--() {
  366. if (lo_ == 0) hi_--; // If it wraps around, decrease the high word.
  367. lo_--;
  368. return *this;
  369. }
  370. } // namespace rlwe
  371. // Specialized numeric_limits for uint256.
  372. namespace std {
  373. template <>
  374. class numeric_limits<rlwe::uint256> {
  375. public:
  376. static constexpr bool is_specialized = true;
  377. static constexpr bool is_signed = false;
  378. static constexpr bool is_integer = true;
  379. static constexpr bool is_exact = true;
  380. static constexpr bool has_infinity = false;
  381. static constexpr bool has_quiet_NaN = false;
  382. static constexpr bool has_signaling_NaN = false;
  383. static constexpr float_denorm_style has_denorm = denorm_absent;
  384. static constexpr bool has_denorm_loss = false;
  385. static constexpr float_round_style round_style = round_toward_zero;
  386. static constexpr bool is_iec559 = false;
  387. static constexpr bool is_bounded = true;
  388. static constexpr bool is_modulo = true;
  389. static constexpr int digits = 256;
  390. static constexpr int digits10 = 77;
  391. static constexpr int max_digits10 = 0;
  392. static constexpr int radix = 2;
  393. static constexpr int min_exponent = 0;
  394. static constexpr int min_exponent10 = 0;
  395. static constexpr int max_exponent = 0;
  396. static constexpr int max_exponent10 = 0;
  397. static constexpr bool traps = numeric_limits<absl::uint128>::traps;
  398. static constexpr bool tinyness_before = false;
  399. static constexpr rlwe::uint256(min)() { return 0; }
  400. static constexpr rlwe::uint256 lowest() { return 0; }
  401. static constexpr rlwe::uint256(max)() { return rlwe::Uint256Max(); }
  402. static constexpr rlwe::uint256 epsilon() { return 0; }
  403. static constexpr rlwe::uint256 round_error() { return 0; }
  404. static constexpr rlwe::uint256 infinity() { return 0; }
  405. static constexpr rlwe::uint256 quiet_NaN() { return 0; }
  406. static constexpr rlwe::uint256 signaling_NaN() { return 0; }
  407. static constexpr rlwe::uint256 denorm_min() { return 0; }
  408. };
  409. } // namespace std
  410. #endif // RLWE_INT256_H_