BigInteger.hpp 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330
  1. #pragma once
  2. #include <stddef.h>
  3. #include <stdint.h>
  4. #include <string.h>
  5. #include <mpir.h>
  6. #include <vector>
  7. #include <string>
  8. #include <type_traits>
  9. #include <stdexcept>
  10. class BigInteger {
  11. private:
  12. mpz_t _Value;
  13. public:
  14. BigInteger() noexcept {
  15. mpz_init(_Value);
  16. }
  17. template<typename __IntegerType>
  18. BigInteger(__IntegerType SmallInteger) noexcept {
  19. // __IntegerType must be a integer type, i.e. char, int, unsigned long...
  20. static_assert(std::is_integral<__IntegerType>::value);
  21. if constexpr (std::is_signed<__IntegerType>::value) {
  22. mpz_init_set_sx(_Value, SmallInteger);
  23. } else {
  24. mpz_init_set_ux(_Value, SmallInteger);
  25. }
  26. }
  27. BigInteger(bool IsNegative, const void* lpBuffer, size_t cbBuffer, bool UseLittleEndian) noexcept {
  28. mpz_init(_Value);
  29. mpz_import(_Value, cbBuffer, UseLittleEndian ? -1 : 1, sizeof(unsigned char), 0, 0, lpBuffer);
  30. if (IsNegative)
  31. mpz_neg(_Value, _Value);
  32. }
  33. BigInteger(bool IsNegative, const std::vector<uint8_t>& Buffer, bool UseLittleEndian) noexcept {
  34. mpz_init(_Value);
  35. mpz_import(_Value, Buffer.size(), UseLittleEndian ? -1 : 1, sizeof(unsigned char), 0, 0, Buffer.data());
  36. if (IsNegative)
  37. mpz_neg(_Value, _Value);
  38. }
  39. BigInteger(const char* lpszValue) noexcept {
  40. mpz_init_set_str(_Value, lpszValue, 0);
  41. }
  42. BigInteger(const std::string& szValue) noexcept {
  43. mpz_init_set_str(_Value, szValue.c_str(), 0);
  44. }
  45. BigInteger(const BigInteger& Other) noexcept {
  46. mpz_init(_Value);
  47. mpz_set(_Value, Other._Value);
  48. }
  49. BigInteger(BigInteger&& Other) noexcept {
  50. mpz_init(_Value);
  51. mpz_swap(_Value, Other._Value);
  52. }
  53. BigInteger& operator=(const BigInteger& Other) noexcept {
  54. if (this != &Other) {
  55. mpz_set(_Value, Other._Value);
  56. }
  57. return *this;
  58. }
  59. BigInteger& operator=(BigInteger&& Other) noexcept {
  60. if (this != &Other) {
  61. mpz_swap(_Value, Other._Value);
  62. mpz_set_ux(Other._Value, 0);
  63. }
  64. return *this;
  65. }
  66. template<typename __IntegerType>
  67. BigInteger& operator=(__IntegerType SmallInteger) noexcept {
  68. // __IntegerType must be a integer type, i.e. char, int, unsigned long...
  69. static_assert(std::is_integral<__IntegerType>::value);
  70. if constexpr (std::is_signed<__IntegerType>::value) {
  71. mpz_set_sx(_Value, SmallInteger);
  72. } else {
  73. mpz_set_ux(_Value, SmallInteger);
  74. }
  75. return *this;
  76. }
  77. BigInteger& operator=(const char* lpszValue) noexcept {
  78. mpz_init_set_str(_Value, lpszValue, 0);
  79. return *this;
  80. }
  81. bool operator==(const BigInteger& Other) const noexcept {
  82. return mpz_cmp(_Value, Other._Value) == 0;
  83. }
  84. bool operator!=(const BigInteger& Other) const noexcept {
  85. return mpz_cmp(_Value, Other._Value) != 0;
  86. }
  87. bool operator<(const BigInteger& Other) const noexcept {
  88. return mpz_cmp(_Value, Other._Value) < 0;
  89. }
  90. bool operator<=(const BigInteger& Other) const noexcept {
  91. auto d = mpz_cmp(_Value, Other._Value);
  92. return d < 0 || d == 0;
  93. }
  94. bool operator>(const BigInteger& Other) const noexcept {
  95. return mpz_cmp(_Value, Other._Value) > 0;
  96. }
  97. bool operator>=(const BigInteger& Other) const noexcept {
  98. auto d = mpz_cmp(_Value, Other._Value);
  99. return d > 0 || d == 0;
  100. }
  101. BigInteger operator-() const noexcept {
  102. BigInteger Result;
  103. mpz_neg(Result._Value, _Value);
  104. return Result;
  105. }
  106. BigInteger operator+(const BigInteger& Other) const noexcept {
  107. BigInteger Result;
  108. mpz_add(Result._Value, _Value, Other._Value);
  109. return Result;
  110. }
  111. BigInteger& operator+=(const BigInteger& Other) noexcept {
  112. mpz_add(_Value, _Value, Other._Value);
  113. return *this;
  114. }
  115. BigInteger operator-(const BigInteger& Other) const noexcept {
  116. BigInteger Result;
  117. mpz_sub(Result._Value, _Value, Other._Value);
  118. return Result;
  119. }
  120. BigInteger& operator-=(const BigInteger& Other) noexcept {
  121. mpz_sub(_Value, _Value, Other._Value);
  122. return *this;
  123. }
  124. BigInteger operator*(const BigInteger& Other) const noexcept {
  125. BigInteger Result;
  126. mpz_mul(Result._Value, _Value, Other._Value);
  127. return Result;
  128. }
  129. BigInteger& operator*=(const BigInteger& Other) noexcept {
  130. mpz_mul(_Value, _Value, Other._Value);
  131. return *this;
  132. }
  133. BigInteger operator/(const BigInteger& Other) const noexcept {
  134. BigInteger Result;
  135. mpz_fdiv_q(Result._Value, _Value, Other._Value);
  136. return Result;
  137. }
  138. BigInteger& operator/=(const BigInteger& Other) noexcept {
  139. mpz_fdiv_q(_Value, _Value, Other._Value);
  140. return *this;
  141. }
  142. BigInteger operator%(const BigInteger& Other) const noexcept {
  143. BigInteger Result;
  144. mpz_fdiv_r(Result._Value, _Value, Other._Value);
  145. return Result;
  146. }
  147. BigInteger& operator%=(const BigInteger& Other) noexcept {
  148. mpz_fdiv_r(_Value, _Value, Other._Value);
  149. return *this;
  150. }
  151. BigInteger operator~() const noexcept {
  152. BigInteger Result;
  153. mpz_com(Result._Value, _Value);
  154. return Result;
  155. }
  156. BigInteger operator&(const BigInteger& Other) const noexcept {
  157. BigInteger Result;
  158. mpz_and(Result._Value, _Value, Other._Value);
  159. return Result;
  160. }
  161. BigInteger& operator&=(const BigInteger& Other) noexcept {
  162. mpz_and(_Value, _Value, Other._Value);
  163. return *this;
  164. }
  165. BigInteger operator|(const BigInteger& Other) const noexcept {
  166. BigInteger Result;
  167. mpz_ior(Result._Value, _Value, Other._Value);
  168. return Result;
  169. }
  170. BigInteger& operator|=(const BigInteger& Other) noexcept {
  171. mpz_ior(_Value, _Value, Other._Value);
  172. return *this;
  173. }
  174. BigInteger operator^(const BigInteger& Other) const noexcept {
  175. BigInteger Result;
  176. mpz_xor(Result._Value, _Value, Other._Value);
  177. return Result;
  178. }
  179. BigInteger& operator^=(const BigInteger& Other) noexcept {
  180. mpz_xor(_Value, _Value, Other._Value);
  181. return *this;
  182. }
  183. BigInteger& operator++() noexcept {
  184. mpz_add_ui(_Value, _Value, 1);
  185. return *this;
  186. }
  187. BigInteger operator++(int) noexcept {
  188. BigInteger Result(*this);
  189. mpz_add_ui(_Value, _Value, 1);
  190. return Result;
  191. }
  192. BigInteger& operator--() noexcept {
  193. mpz_sub_ui(_Value, _Value, 1);
  194. return *this;
  195. }
  196. BigInteger operator--(int) noexcept {
  197. BigInteger Result(*this);
  198. mpz_sub_ui(_Value, _Value, 1);
  199. return Result;
  200. }
  201. bool IsZero() const noexcept {
  202. return mpz_sgn(_Value) == 0;
  203. }
  204. bool IsPositive() const noexcept {
  205. return mpz_sgn(_Value) > 0;
  206. }
  207. bool IsNegative() const noexcept {
  208. return mpz_sgn(_Value) < 0;
  209. }
  210. bool IsOne() const noexcept {
  211. return mpz_cmp_si(_Value, 1) == 0;
  212. }
  213. BigInteger& Load(bool IsNegative, const void* lpBuffer, size_t cbBuffer, bool UseLittleEndian) noexcept {
  214. mpz_import(_Value, cbBuffer, UseLittleEndian ? -1 : 1, sizeof(uint8_t), 0, 0, lpBuffer);
  215. if (IsNegative)
  216. mpz_neg(_Value, _Value);
  217. return *this;
  218. }
  219. BigInteger& Load(bool IsNegative, const std::vector<uint8_t> Buffer, bool UseLittleEndian) noexcept {
  220. mpz_import(_Value, Buffer.size(), UseLittleEndian ? -1 : 1, sizeof(uint8_t), 0, 0, Buffer.data());
  221. if (IsNegative)
  222. mpz_neg(_Value, _Value);
  223. return *this;
  224. }
  225. void DumpAbs(void* lpBuffer, size_t cbBuffer, bool UseLittleEndian) const {
  226. size_t bit_size = mpz_sizeinbase(_Value, 2);
  227. size_t storage_size = (bit_size + 7) / 8;
  228. if (cbBuffer >= storage_size) {
  229. size_t bytes_written;
  230. mpz_export(lpBuffer, &bytes_written, UseLittleEndian ? -1 : 1, sizeof(uint8_t), 0, 0, _Value);
  231. memset(reinterpret_cast<unsigned char*>(lpBuffer) + bytes_written, 0, cbBuffer - bytes_written);
  232. } else {
  233. throw std::length_error("Insufficient buffer.");
  234. }
  235. }
  236. std::vector<uint8_t> DumpAbs(bool UseLittleEndian) const noexcept {
  237. size_t bit_size = mpz_sizeinbase(_Value, 2);
  238. size_t storage_size = (bit_size + 7) / 8;
  239. std::vector<uint8_t> bytes(storage_size);
  240. mpz_export(bytes.data(), nullptr, UseLittleEndian ? -1 : 1, sizeof(uint8_t), 0, 0, _Value);
  241. return bytes;
  242. }
  243. size_t BitLength() const noexcept {
  244. return mpz_sizeinbase(_Value, 2);
  245. }
  246. bool TestBit(size_t i) const noexcept {
  247. return mpz_tstbit(_Value, i) != 0;
  248. }
  249. void SetBit(size_t i) noexcept {
  250. mpz_setbit(_Value, i);
  251. }
  252. std::string ToString(size_t Base, bool LowerCase) const {
  253. if (2 <= Base && Base <= 10 + 26) {
  254. int base = LowerCase ? static_cast<int>(Base) : -static_cast<int>(Base);
  255. std::string s(mpz_sizeinbase(_Value, base) + 2, '\x00');
  256. mpz_get_str(s.data(), base, _Value);
  257. while (s.back() == '\x00') {
  258. s.pop_back();
  259. }
  260. return s;
  261. } else {
  262. throw std::invalid_argument("Invalid base value.");
  263. }
  264. }
  265. ~BigInteger() {
  266. mpz_clear(_Value);
  267. }
  268. };