UnsignedBigInteger.cpp 25 KB

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