UnsignedBigInteger.cpp 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746
  1. /*
  2. * Copyright (c) 2020, Itamar S. <itamar8910@gmail.com>
  3. * Copyright (c) 2022, David Tuin <davidot@serenityos.org>
  4. *
  5. * SPDX-License-Identifier: BSD-2-Clause
  6. */
  7. #include "UnsignedBigInteger.h"
  8. #include <AK/BuiltinWrappers.h>
  9. #include <AK/CharacterTypes.h>
  10. #include <AK/FloatingPoint.h>
  11. #include <AK/StringBuilder.h>
  12. #include <AK/StringHash.h>
  13. #include <LibCrypto/BigInt/Algorithms/UnsignedBigIntegerAlgorithms.h>
  14. #include <math.h>
  15. namespace Crypto {
  16. UnsignedBigInteger::UnsignedBigInteger(u8 const* ptr, size_t length)
  17. {
  18. m_words.resize_and_keep_capacity((length + sizeof(u32) - 1) / sizeof(u32));
  19. size_t in = length, out = 0;
  20. while (in >= sizeof(u32)) {
  21. in -= sizeof(u32);
  22. u32 word = ((u32)ptr[in] << 24) | ((u32)ptr[in + 1] << 16) | ((u32)ptr[in + 2] << 8) | (u32)ptr[in + 3];
  23. m_words[out++] = word;
  24. }
  25. if (in > 0) {
  26. u32 word = 0;
  27. for (size_t i = 0; i < in; i++) {
  28. word <<= 8;
  29. word |= (u32)ptr[i];
  30. }
  31. m_words[out++] = word;
  32. }
  33. }
  34. UnsignedBigInteger::UnsignedBigInteger(double value)
  35. {
  36. // Because this is currently only used for LibJS we VERIFY some preconditions
  37. // also these values don't have a clear BigInteger representation.
  38. VERIFY(!isnan(value));
  39. VERIFY(!isinf(value));
  40. VERIFY(trunc(value) == value);
  41. VERIFY(value >= 0.0);
  42. if (value <= NumericLimits<u32>::max()) {
  43. m_words.append(static_cast<u32>(value));
  44. return;
  45. }
  46. FloatExtractor<double> extractor;
  47. extractor.d = value;
  48. VERIFY(!extractor.sign);
  49. i32 real_exponent = extractor.exponent - extractor.exponent_bias;
  50. VERIFY(real_exponent > 0);
  51. // Ensure we have enough space, we will need 2^exponent bits, so round up in words
  52. auto word_index = (real_exponent + BITS_IN_WORD) / BITS_IN_WORD;
  53. m_words.resize_and_keep_capacity(word_index);
  54. // Now we just need to put the mantissa with explicit 1 bit at the top at the proper location
  55. u64 raw_mantissa = extractor.mantissa | (1ull << extractor.mantissa_bits);
  56. VERIFY((raw_mantissa & 0xfff0000000000000) == 0x0010000000000000);
  57. // Shift it so the bits we need are at the top
  58. raw_mantissa <<= 64 - extractor.mantissa_bits - 1;
  59. // The initial bit needs to be exactly aligned with exponent, this is 1-indexed
  60. auto top_word_bit_offset = real_exponent % BITS_IN_WORD + 1;
  61. auto top_word_bits_from_mantissa = raw_mantissa >> (64 - top_word_bit_offset);
  62. VERIFY(top_word_bits_from_mantissa <= NumericLimits<Word>::max());
  63. m_words[word_index - 1] = top_word_bits_from_mantissa;
  64. --word_index;
  65. // Shift used bits away
  66. raw_mantissa <<= top_word_bit_offset;
  67. i32 bits_in_mantissa = extractor.mantissa_bits + 1 - top_word_bit_offset;
  68. // Now just put everything at the top of the next words
  69. constexpr auto to_word_shift = 64 - BITS_IN_WORD;
  70. while (word_index > 0 && bits_in_mantissa > 0) {
  71. VERIFY((raw_mantissa >> to_word_shift) <= NumericLimits<Word>::max());
  72. m_words[word_index - 1] = raw_mantissa >> to_word_shift;
  73. raw_mantissa <<= to_word_shift;
  74. bits_in_mantissa -= BITS_IN_WORD;
  75. --word_index;
  76. }
  77. VERIFY(m_words.size() > word_index);
  78. VERIFY((m_words.size() - word_index) <= 3);
  79. // No bits left, otherwise we would have to round
  80. VERIFY(raw_mantissa == 0);
  81. }
  82. UnsignedBigInteger UnsignedBigInteger::create_invalid()
  83. {
  84. UnsignedBigInteger invalid(0);
  85. invalid.invalidate();
  86. return invalid;
  87. }
  88. size_t UnsignedBigInteger::export_data(Bytes data, bool remove_leading_zeros) const
  89. {
  90. size_t word_count = trimmed_length();
  91. size_t out = 0;
  92. if (word_count > 0) {
  93. ssize_t leading_zeros = -1;
  94. if (remove_leading_zeros) {
  95. UnsignedBigInteger::Word word = m_words[word_count - 1];
  96. for (size_t i = 0; i < sizeof(u32); i++) {
  97. u8 byte = (u8)(word >> ((sizeof(u32) - i - 1) * 8));
  98. data[out++] = byte;
  99. if (leading_zeros < 0 && byte != 0)
  100. leading_zeros = (int)i;
  101. }
  102. }
  103. for (size_t i = word_count - (remove_leading_zeros ? 1 : 0); i > 0; i--) {
  104. auto word = m_words[i - 1];
  105. data[out++] = (u8)(word >> 24);
  106. data[out++] = (u8)(word >> 16);
  107. data[out++] = (u8)(word >> 8);
  108. data[out++] = (u8)word;
  109. }
  110. if (leading_zeros > 0)
  111. out -= leading_zeros;
  112. }
  113. return out;
  114. }
  115. UnsignedBigInteger UnsignedBigInteger::from_base(u16 N, StringView str)
  116. {
  117. VERIFY(N <= 36);
  118. UnsignedBigInteger result;
  119. UnsignedBigInteger base { N };
  120. for (auto& c : str) {
  121. if (c == '_')
  122. continue;
  123. result = result.multiplied_by(base).plus(parse_ascii_base36_digit(c));
  124. }
  125. return result;
  126. }
  127. ErrorOr<String> UnsignedBigInteger::to_base(u16 N) const
  128. {
  129. VERIFY(N <= 36);
  130. if (*this == UnsignedBigInteger { 0 })
  131. return "0"_short_string;
  132. StringBuilder builder;
  133. UnsignedBigInteger temp(*this);
  134. UnsignedBigInteger quotient;
  135. UnsignedBigInteger remainder;
  136. while (temp != UnsignedBigInteger { 0 }) {
  137. UnsignedBigIntegerAlgorithms::divide_u16_without_allocation(temp, N, quotient, remainder);
  138. VERIFY(remainder.words()[0] < N);
  139. TRY(builder.try_append(to_ascii_base36_digit(remainder.words()[0])));
  140. temp.set_to(quotient);
  141. }
  142. return TRY(builder.to_string()).reverse();
  143. }
  144. DeprecatedString UnsignedBigInteger::to_base_deprecated(u16 N) const
  145. {
  146. return MUST(to_base(N)).to_deprecated_string();
  147. }
  148. u64 UnsignedBigInteger::to_u64() const
  149. {
  150. static_assert(sizeof(Word) == 4);
  151. if (!length())
  152. return 0;
  153. u64 value = m_words[0];
  154. if (length() > 1)
  155. value |= static_cast<u64>(m_words[1]) << 32;
  156. return value;
  157. }
  158. double UnsignedBigInteger::to_double(UnsignedBigInteger::RoundingMode rounding_mode) const
  159. {
  160. VERIFY(!is_invalid());
  161. auto highest_bit = one_based_index_of_highest_set_bit();
  162. if (highest_bit == 0)
  163. return 0;
  164. --highest_bit;
  165. using Extractor = FloatExtractor<double>;
  166. // Simple case if less than 2^53 since those number are all exactly representable in doubles
  167. if (highest_bit < Extractor::mantissa_bits + 1)
  168. return static_cast<double>(to_u64());
  169. // If it uses too many bit to represent in a double return infinity
  170. if (highest_bit > Extractor::exponent_bias)
  171. return __builtin_huge_val();
  172. // Otherwise we have to take the top 53 bits, use those as the mantissa,
  173. // and the amount of bits as the exponent. Note that the mantissa has an implicit top bit of 1
  174. // so we have to ignore the very top bit.
  175. // Since we extract at most 53 bits it will take at most 3 words
  176. static_assert(BITS_IN_WORD * 3 >= (Extractor::mantissa_bits + 1));
  177. constexpr auto bits_in_u64 = 64;
  178. static_assert(bits_in_u64 > Extractor::mantissa_bits + 1);
  179. auto bits_to_read = min(static_cast<size_t>(Extractor::mantissa_bits), highest_bit);
  180. auto last_word_index = trimmed_length();
  181. VERIFY(last_word_index > 0);
  182. // Note that highest bit is 0-indexed at this point.
  183. auto highest_bit_index_in_top_word = highest_bit % BITS_IN_WORD;
  184. // Shift initial word until highest bit is just beyond top of u64.
  185. u64 mantissa = m_words[last_word_index - 1];
  186. if (highest_bit_index_in_top_word != 0)
  187. mantissa <<= (bits_in_u64 - highest_bit_index_in_top_word);
  188. else
  189. mantissa = 0;
  190. auto bits_written = highest_bit_index_in_top_word;
  191. --last_word_index;
  192. Optional<Word> dropped_bits_for_rounding;
  193. u8 bits_dropped_from_final_word = 0;
  194. if (bits_written < bits_to_read && last_word_index > 0) {
  195. // Second word can always just cleanly be shifted up to the final bit of the first word
  196. // since the first has at most BIT_IN_WORD - 1, 31
  197. u64 next_word = m_words[last_word_index - 1];
  198. VERIFY((mantissa & (next_word << (bits_in_u64 - bits_written - BITS_IN_WORD))) == 0);
  199. mantissa |= next_word << (bits_in_u64 - bits_written - BITS_IN_WORD);
  200. bits_written += BITS_IN_WORD;
  201. --last_word_index;
  202. if (bits_written > bits_to_read) {
  203. bits_dropped_from_final_word = bits_written - bits_to_read;
  204. dropped_bits_for_rounding = m_words[last_word_index] & ((1 << bits_dropped_from_final_word) - 1);
  205. } else if (bits_written < bits_to_read && last_word_index > 0) {
  206. // The final word has to be shifted down first to discard any excess bits.
  207. u64 final_word = m_words[last_word_index - 1];
  208. --last_word_index;
  209. auto bits_to_write = bits_to_read - bits_written;
  210. bits_dropped_from_final_word = BITS_IN_WORD - bits_to_write;
  211. dropped_bits_for_rounding = final_word & ((1 << bits_dropped_from_final_word) - 1u);
  212. final_word >>= bits_dropped_from_final_word;
  213. // Then move the bits right up to the lowest bits of the second word
  214. VERIFY((mantissa & (final_word << (bits_in_u64 - bits_written - bits_to_write))) == 0);
  215. mantissa |= final_word << (bits_in_u64 - bits_written - bits_to_write);
  216. }
  217. }
  218. // Now the mantissa should be complete so shift it down
  219. mantissa >>= bits_in_u64 - Extractor::mantissa_bits;
  220. if (rounding_mode == RoundingMode::IEEERoundAndTiesToEvenMantissa) {
  221. bool round_up = false;
  222. if (bits_dropped_from_final_word == 0) {
  223. if (last_word_index > 0) {
  224. Word next_word = m_words[last_word_index - 1];
  225. last_word_index--;
  226. if ((next_word & 0x80000000) != 0) {
  227. // next top bit set check for any other bits
  228. if ((next_word ^ 0x80000000) != 0) {
  229. round_up = true;
  230. } else {
  231. while (last_word_index > 0) {
  232. if (m_words[last_word_index - 1] != 0) {
  233. round_up = true;
  234. break;
  235. }
  236. }
  237. // All other bits are 0 which is a tie thus round to even exponent
  238. // Since we are halfway, if exponent ends with 1 we round up, if 0 we round down
  239. round_up = (mantissa & 1) != 0;
  240. }
  241. } else {
  242. round_up = false;
  243. }
  244. } else {
  245. // If there are no words left the rest is implicitly 0 so just round down
  246. round_up = false;
  247. }
  248. } else {
  249. VERIFY(dropped_bits_for_rounding.has_value());
  250. VERIFY(bits_dropped_from_final_word >= 1);
  251. // In this case the top bit comes form the dropped bits
  252. auto top_bit_extractor = 1u << (bits_dropped_from_final_word - 1u);
  253. if ((*dropped_bits_for_rounding & top_bit_extractor) != 0) {
  254. // Possible tie again, if any other bit is set we round up
  255. if ((*dropped_bits_for_rounding ^ top_bit_extractor) != 0) {
  256. round_up = true;
  257. } else {
  258. while (last_word_index > 0) {
  259. if (m_words[last_word_index - 1] != 0) {
  260. round_up = true;
  261. break;
  262. }
  263. }
  264. round_up = (mantissa & 1) != 0;
  265. }
  266. } else {
  267. round_up = false;
  268. }
  269. }
  270. if (round_up) {
  271. ++mantissa;
  272. if ((mantissa & (1ull << Extractor::mantissa_bits)) != 0) {
  273. // we overflowed the mantissa
  274. mantissa = 0;
  275. highest_bit++;
  276. // In which case it is possible we have to round to infinity
  277. if (highest_bit > Extractor::exponent_bias)
  278. return __builtin_huge_val();
  279. }
  280. }
  281. } else {
  282. VERIFY(rounding_mode == RoundingMode::RoundTowardZero);
  283. }
  284. Extractor extractor;
  285. extractor.exponent = highest_bit + extractor.exponent_bias;
  286. VERIFY((mantissa & 0xfff0000000000000) == 0);
  287. extractor.mantissa = mantissa;
  288. return extractor.d;
  289. }
  290. void UnsignedBigInteger::set_to_0()
  291. {
  292. m_words.clear_with_capacity();
  293. m_is_invalid = false;
  294. m_cached_trimmed_length = {};
  295. m_cached_hash = 0;
  296. }
  297. void UnsignedBigInteger::set_to(UnsignedBigInteger::Word other)
  298. {
  299. m_is_invalid = false;
  300. m_words.resize_and_keep_capacity(1);
  301. m_words[0] = other;
  302. m_cached_trimmed_length = {};
  303. m_cached_hash = 0;
  304. }
  305. void UnsignedBigInteger::set_to(UnsignedBigInteger const& other)
  306. {
  307. m_is_invalid = other.m_is_invalid;
  308. m_words.resize_and_keep_capacity(other.m_words.size());
  309. __builtin_memcpy(m_words.data(), other.m_words.data(), other.m_words.size() * sizeof(u32));
  310. m_cached_trimmed_length = {};
  311. m_cached_hash = 0;
  312. }
  313. bool UnsignedBigInteger::is_zero() const
  314. {
  315. for (size_t i = 0; i < length(); ++i) {
  316. if (m_words[i] != 0)
  317. return false;
  318. }
  319. return true;
  320. }
  321. size_t UnsignedBigInteger::trimmed_length() const
  322. {
  323. if (!m_cached_trimmed_length.has_value()) {
  324. size_t num_leading_zeroes = 0;
  325. for (int i = length() - 1; i >= 0; --i, ++num_leading_zeroes) {
  326. if (m_words[i] != 0)
  327. break;
  328. }
  329. m_cached_trimmed_length = length() - num_leading_zeroes;
  330. }
  331. return m_cached_trimmed_length.value();
  332. }
  333. void UnsignedBigInteger::clamp_to_trimmed_length()
  334. {
  335. auto length = trimmed_length();
  336. if (m_words.size() > length)
  337. m_words.resize(length);
  338. }
  339. void UnsignedBigInteger::resize_with_leading_zeros(size_t new_length)
  340. {
  341. size_t old_length = length();
  342. if (old_length < new_length) {
  343. m_words.resize_and_keep_capacity(new_length);
  344. __builtin_memset(&m_words.data()[old_length], 0, (new_length - old_length) * sizeof(u32));
  345. }
  346. }
  347. size_t UnsignedBigInteger::one_based_index_of_highest_set_bit() const
  348. {
  349. size_t number_of_words = trimmed_length();
  350. size_t index = 0;
  351. if (number_of_words > 0) {
  352. index += (number_of_words - 1) * BITS_IN_WORD;
  353. index += BITS_IN_WORD - count_leading_zeroes(m_words[number_of_words - 1]);
  354. }
  355. return index;
  356. }
  357. FLATTEN UnsignedBigInteger UnsignedBigInteger::plus(UnsignedBigInteger const& other) const
  358. {
  359. UnsignedBigInteger result;
  360. UnsignedBigIntegerAlgorithms::add_without_allocation(*this, other, result);
  361. return result;
  362. }
  363. FLATTEN UnsignedBigInteger UnsignedBigInteger::minus(UnsignedBigInteger const& other) const
  364. {
  365. UnsignedBigInteger result;
  366. UnsignedBigIntegerAlgorithms::subtract_without_allocation(*this, other, result);
  367. return result;
  368. }
  369. FLATTEN UnsignedBigInteger UnsignedBigInteger::bitwise_or(UnsignedBigInteger const& other) const
  370. {
  371. UnsignedBigInteger result;
  372. UnsignedBigIntegerAlgorithms::bitwise_or_without_allocation(*this, other, result);
  373. return result;
  374. }
  375. FLATTEN UnsignedBigInteger UnsignedBigInteger::bitwise_and(UnsignedBigInteger const& other) const
  376. {
  377. UnsignedBigInteger result;
  378. UnsignedBigIntegerAlgorithms::bitwise_and_without_allocation(*this, other, result);
  379. return result;
  380. }
  381. FLATTEN UnsignedBigInteger UnsignedBigInteger::bitwise_xor(UnsignedBigInteger const& other) const
  382. {
  383. UnsignedBigInteger result;
  384. UnsignedBigIntegerAlgorithms::bitwise_xor_without_allocation(*this, other, result);
  385. return result;
  386. }
  387. FLATTEN UnsignedBigInteger UnsignedBigInteger::bitwise_not_fill_to_one_based_index(size_t size) const
  388. {
  389. UnsignedBigInteger result;
  390. UnsignedBigIntegerAlgorithms::bitwise_not_fill_to_one_based_index_without_allocation(*this, size, result);
  391. return result;
  392. }
  393. FLATTEN UnsignedBigInteger UnsignedBigInteger::shift_left(size_t num_bits) const
  394. {
  395. UnsignedBigInteger output;
  396. UnsignedBigInteger temp_result;
  397. UnsignedBigInteger temp_plus;
  398. UnsignedBigIntegerAlgorithms::shift_left_without_allocation(*this, num_bits, temp_result, temp_plus, output);
  399. return output;
  400. }
  401. FLATTEN UnsignedBigInteger UnsignedBigInteger::multiplied_by(UnsignedBigInteger const& other) const
  402. {
  403. UnsignedBigInteger result;
  404. UnsignedBigInteger temp_shift_result;
  405. UnsignedBigInteger temp_shift_plus;
  406. UnsignedBigInteger temp_shift;
  407. UnsignedBigIntegerAlgorithms::multiply_without_allocation(*this, other, temp_shift_result, temp_shift_plus, temp_shift, result);
  408. return result;
  409. }
  410. FLATTEN UnsignedDivisionResult UnsignedBigInteger::divided_by(UnsignedBigInteger const& divisor) const
  411. {
  412. UnsignedBigInteger quotient;
  413. UnsignedBigInteger remainder;
  414. // If we actually have a u16-compatible divisor, short-circuit to the
  415. // less computationally-intensive "divide_u16_without_allocation" method.
  416. if (divisor.trimmed_length() == 1 && divisor.m_words[0] < (1 << 16)) {
  417. UnsignedBigIntegerAlgorithms::divide_u16_without_allocation(*this, divisor.m_words[0], quotient, remainder);
  418. return UnsignedDivisionResult { quotient, remainder };
  419. }
  420. UnsignedBigInteger temp_shift_result;
  421. UnsignedBigInteger temp_shift_plus;
  422. UnsignedBigInteger temp_shift;
  423. UnsignedBigInteger temp_minus;
  424. UnsignedBigIntegerAlgorithms::divide_without_allocation(*this, divisor, temp_shift_result, temp_shift_plus, temp_shift, temp_minus, quotient, remainder);
  425. return UnsignedDivisionResult { quotient, remainder };
  426. }
  427. u32 UnsignedBigInteger::hash() const
  428. {
  429. if (m_cached_hash != 0)
  430. return m_cached_hash;
  431. return m_cached_hash = string_hash((char const*)m_words.data(), sizeof(Word) * m_words.size());
  432. }
  433. void UnsignedBigInteger::set_bit_inplace(size_t bit_index)
  434. {
  435. const size_t word_index = bit_index / UnsignedBigInteger::BITS_IN_WORD;
  436. const size_t inner_word_index = bit_index % UnsignedBigInteger::BITS_IN_WORD;
  437. m_words.ensure_capacity(word_index + 1);
  438. for (size_t i = length(); i <= word_index; ++i) {
  439. m_words.unchecked_append(0);
  440. }
  441. m_words[word_index] |= (1 << inner_word_index);
  442. m_cached_trimmed_length = {};
  443. m_cached_hash = 0;
  444. }
  445. bool UnsignedBigInteger::operator==(UnsignedBigInteger const& other) const
  446. {
  447. if (is_invalid() != other.is_invalid())
  448. return false;
  449. auto length = trimmed_length();
  450. if (length != other.trimmed_length())
  451. return false;
  452. return !__builtin_memcmp(m_words.data(), other.words().data(), length * (BITS_IN_WORD / 8));
  453. }
  454. bool UnsignedBigInteger::operator!=(UnsignedBigInteger const& other) const
  455. {
  456. return !(*this == other);
  457. }
  458. bool UnsignedBigInteger::operator<(UnsignedBigInteger const& other) const
  459. {
  460. auto length = trimmed_length();
  461. auto other_length = other.trimmed_length();
  462. if (length < other_length) {
  463. return true;
  464. }
  465. if (length > other_length) {
  466. return false;
  467. }
  468. if (length == 0) {
  469. return false;
  470. }
  471. for (int i = length - 1; i >= 0; --i) {
  472. if (m_words[i] == other.m_words[i])
  473. continue;
  474. return m_words[i] < other.m_words[i];
  475. }
  476. return false;
  477. }
  478. bool UnsignedBigInteger::operator>(UnsignedBigInteger const& other) const
  479. {
  480. return *this != other && !(*this < other);
  481. }
  482. bool UnsignedBigInteger::operator>=(UnsignedBigInteger const& other) const
  483. {
  484. return *this > other || *this == other;
  485. }
  486. UnsignedBigInteger::CompareResult UnsignedBigInteger::compare_to_double(double value) const
  487. {
  488. VERIFY(!isnan(value));
  489. if (isinf(value)) {
  490. bool is_positive_infinity = __builtin_isinf_sign(value) > 0;
  491. return is_positive_infinity ? CompareResult::DoubleGreaterThanBigInt : CompareResult::DoubleLessThanBigInt;
  492. }
  493. bool value_is_negative = value < 0;
  494. if (value_is_negative)
  495. return CompareResult::DoubleLessThanBigInt;
  496. // Value is zero.
  497. if (value == 0.0) {
  498. VERIFY(!value_is_negative);
  499. // Either we are also zero or value is certainly less than us.
  500. return is_zero() ? CompareResult::DoubleEqualsBigInt : CompareResult::DoubleLessThanBigInt;
  501. }
  502. // If value is not zero but we are, value must be greater.
  503. if (is_zero())
  504. return CompareResult::DoubleGreaterThanBigInt;
  505. FloatExtractor<double> extractor;
  506. extractor.d = value;
  507. // Value cannot be negative at this point.
  508. VERIFY(extractor.sign == 0);
  509. // Exponent cannot be all set, as then we must be NaN or infinity.
  510. VERIFY(extractor.exponent != (1 << extractor.exponent_bits) - 1);
  511. i32 real_exponent = extractor.exponent - extractor.exponent_bias;
  512. if (real_exponent < 0) {
  513. // value is less than 1, and we cannot be zero so value must be less.
  514. return CompareResult::DoubleLessThanBigInt;
  515. }
  516. u64 bigint_bits_needed = one_based_index_of_highest_set_bit();
  517. VERIFY(bigint_bits_needed > 0);
  518. // Double value is `-1^sign (1.mantissa) * 2^(exponent - bias)` so we need
  519. // `exponent - bias + 1` bit to represent doubles value,
  520. // for example `exponent - bias` = 3, sign = 0 and mantissa = 0 we get
  521. // `-1^0 * 2^3 * 1 = 8` which needs 4 bits to store 8 (0b1000).
  522. u32 double_bits_needed = real_exponent + 1;
  523. // If we need more bits to represent us, we must be of greater value.
  524. if (bigint_bits_needed > double_bits_needed)
  525. return CompareResult::DoubleLessThanBigInt;
  526. // If we need less bits to represent us, we must be of less value.
  527. if (bigint_bits_needed < double_bits_needed)
  528. return CompareResult::DoubleGreaterThanBigInt;
  529. u64 mantissa_bits = extractor.mantissa;
  530. // We add the bit which represents the 1. of the double value calculation.
  531. constexpr u64 mantissa_extended_bit = 1ull << extractor.mantissa_bits;
  532. mantissa_bits |= mantissa_extended_bit;
  533. // Now we shift value to the left virtually, with `exponent - bias` steps
  534. // we then pretend both it and the big int are extended with virtual zeros.
  535. auto next_bigint_word = (BITS_IN_WORD - 1 + bigint_bits_needed) / BITS_IN_WORD;
  536. VERIFY(next_bigint_word == trimmed_length());
  537. auto msb_in_top_word_index = (bigint_bits_needed - 1) % BITS_IN_WORD;
  538. VERIFY(msb_in_top_word_index == (BITS_IN_WORD - count_leading_zeroes(words()[next_bigint_word - 1]) - 1));
  539. // We will keep the bits which are still valid in the mantissa at the top of mantissa bits.
  540. mantissa_bits <<= 64 - (extractor.mantissa_bits + 1);
  541. auto bits_left_in_mantissa = static_cast<size_t>(extractor.mantissa_bits) + 1;
  542. auto get_next_value_bits = [&](size_t num_bits) -> Word {
  543. VERIFY(num_bits < 63);
  544. VERIFY(bits_left_in_mantissa > 0);
  545. if (num_bits > bits_left_in_mantissa)
  546. num_bits = bits_left_in_mantissa;
  547. bits_left_in_mantissa -= num_bits;
  548. u64 extracted_bits = mantissa_bits & (((1ull << num_bits) - 1) << (64 - num_bits));
  549. // Now shift the bits down to put the most significant bit on the num_bits position
  550. // this means the rest will be "virtual" zeros.
  551. extracted_bits >>= 32;
  552. // Now shift away the used bits and fit the result into a Word.
  553. mantissa_bits <<= num_bits;
  554. VERIFY(extracted_bits <= NumericLimits<Word>::max());
  555. return static_cast<Word>(extracted_bits);
  556. };
  557. auto bits_in_next_bigint_word = msb_in_top_word_index + 1;
  558. while (next_bigint_word > 0 && bits_left_in_mantissa > 0) {
  559. Word bigint_word = words()[next_bigint_word - 1];
  560. Word double_word = get_next_value_bits(bits_in_next_bigint_word);
  561. // For the first bit we have to align it with the top bit of bigint
  562. // and for all the other cases bits_in_next_bigint_word is 32 so this does nothing.
  563. double_word >>= 32 - bits_in_next_bigint_word;
  564. if (bigint_word < double_word)
  565. return CompareResult::DoubleGreaterThanBigInt;
  566. if (bigint_word > double_word)
  567. return CompareResult::DoubleLessThanBigInt;
  568. --next_bigint_word;
  569. bits_in_next_bigint_word = BITS_IN_WORD;
  570. }
  571. // If there are still bits left in bigint than any non zero bit means it has greater value.
  572. if (next_bigint_word > 0) {
  573. VERIFY(bits_left_in_mantissa == 0);
  574. while (next_bigint_word > 0) {
  575. if (words()[next_bigint_word - 1] != 0)
  576. return CompareResult::DoubleLessThanBigInt;
  577. --next_bigint_word;
  578. }
  579. } else if (bits_left_in_mantissa > 0) {
  580. VERIFY(next_bigint_word == 0);
  581. // Similarly if there are still any bits set in the mantissa it has greater value.
  582. if (mantissa_bits != 0)
  583. return CompareResult::DoubleGreaterThanBigInt;
  584. }
  585. // Otherwise if both don't have bits left or the rest of the bits are zero they are equal.
  586. return CompareResult::DoubleEqualsBigInt;
  587. }
  588. }
  589. ErrorOr<void> AK::Formatter<Crypto::UnsignedBigInteger>::format(FormatBuilder& fmtbuilder, Crypto::UnsignedBigInteger const& value)
  590. {
  591. if (value.is_invalid())
  592. return fmtbuilder.put_string("invalid"sv);
  593. StringBuilder builder;
  594. for (int i = value.length() - 1; i >= 0; --i)
  595. TRY(builder.try_appendff("{}|", value.words()[i]));
  596. return Formatter<StringView>::format(fmtbuilder, builder.string_view());
  597. }