jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Peter Bocan <me@pbocan.net>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibCrypto/BigInt/Algorithms/UnsignedBigIntegerAlgorithms.h>
8#include <LibCrypto/BigInt/SignedBigInteger.h>
9#include <LibCrypto/BigInt/UnsignedBigInteger.h>
10#include <LibCrypto/NumberTheory/ModularFunctions.h>
11#include <LibTest/TestCase.h>
12#include <math.h>
13
14static Crypto::UnsignedBigInteger bigint_fibonacci(size_t n)
15{
16 Crypto::UnsignedBigInteger num1(0);
17 Crypto::UnsignedBigInteger num2(1);
18 for (size_t i = 0; i < n; ++i) {
19 Crypto::UnsignedBigInteger t = num1.plus(num2);
20 num2 = num1;
21 num1 = t;
22 }
23 return num1;
24}
25
26static Crypto::SignedBigInteger bigint_signed_fibonacci(size_t n)
27{
28 Crypto::SignedBigInteger num1(0);
29 Crypto::SignedBigInteger num2(1);
30 for (size_t i = 0; i < n; ++i) {
31 Crypto::SignedBigInteger t = num1.plus(num2);
32 num2 = num1;
33 num1 = t;
34 }
35 return num1;
36}
37
38TEST_CASE(test_bigint_fib500)
39{
40 Vector<u32> result {
41 315178285, 505575602, 1883328078, 125027121, 3649625763,
42 347570207, 74535262, 3832543808, 2472133297, 1600064941, 65273441
43 };
44
45 EXPECT_EQ(bigint_fibonacci(500).words(), result);
46}
47
48TEST_CASE(test_unsigned_bigint_addition_initialization)
49{
50 Crypto::UnsignedBigInteger num1;
51 Crypto::UnsignedBigInteger num2(70);
52 Crypto::UnsignedBigInteger num3 = num1.plus(num2);
53 bool pass = (num3 == num2);
54 pass &= (num1 == Crypto::UnsignedBigInteger(0));
55 EXPECT(pass);
56}
57
58TEST_CASE(test_unsigned_bigint_addition_borrow_with_zero)
59{
60 Crypto::UnsignedBigInteger num1({ UINT32_MAX - 3, UINT32_MAX });
61 Crypto::UnsignedBigInteger num2({ UINT32_MAX - 2, 0 });
62 Vector<u32> expected_result { 4294967289, 0, 1 };
63 EXPECT_EQ(num1.plus(num2).words(), expected_result);
64}
65
66TEST_CASE(test_unsigned_bigint_basic_add_to_accumulator)
67{
68 Crypto::UnsignedBigInteger num1(10);
69 Crypto::UnsignedBigInteger num2(70);
70 Crypto::UnsignedBigIntegerAlgorithms::add_into_accumulator_without_allocation(num1, num2);
71 EXPECT_EQ(num1.words(), Vector<u32> { 80 });
72}
73
74TEST_CASE(test_unsigned_bigint_basic_add_to_empty_accumulator)
75{
76 Crypto::UnsignedBigInteger num1 {};
77 Crypto::UnsignedBigInteger num2(10);
78 Crypto::UnsignedBigIntegerAlgorithms::add_into_accumulator_without_allocation(num1, num2);
79 EXPECT_EQ(num1.words(), Vector<u32> { 10 });
80}
81
82TEST_CASE(test_unsigned_bigint_basic_add_to_smaller_accumulator)
83{
84 Crypto::UnsignedBigInteger num1(10);
85 Crypto::UnsignedBigInteger num2({ 10, 10 });
86 Crypto::UnsignedBigIntegerAlgorithms::add_into_accumulator_without_allocation(num1, num2);
87 Vector<u32> expected_result { 20, 10 };
88 EXPECT_EQ(num1.words(), expected_result);
89}
90
91TEST_CASE(test_unsigned_bigint_add_to_accumulator_with_multiple_carry_levels)
92{
93 Crypto::UnsignedBigInteger num1({ UINT32_MAX - 2, UINT32_MAX });
94 Crypto::UnsignedBigInteger num2(5);
95 Crypto::UnsignedBigIntegerAlgorithms::add_into_accumulator_without_allocation(num1, num2);
96 Vector<u32> expected_result { 2, 0, 1 };
97 EXPECT_EQ(num1.words(), expected_result);
98}
99
100TEST_CASE(test_unsigned_bigint_add_to_accumulator_with_leading_zero)
101{
102 Crypto::UnsignedBigInteger num1(1);
103 Crypto::UnsignedBigInteger num2({ 1, 0 });
104 Crypto::UnsignedBigIntegerAlgorithms::add_into_accumulator_without_allocation(num1, num2);
105 EXPECT_EQ(num1.words(), Vector<u32> { 2 });
106}
107
108TEST_CASE(test_unsigned_bigint_add_to_accumulator_with_carry_and_leading_zero)
109{
110 Crypto::UnsignedBigInteger num1({ UINT32_MAX, 0, 0, 0 });
111 Crypto::UnsignedBigInteger num2({ 1, 0 });
112 Crypto::UnsignedBigIntegerAlgorithms::add_into_accumulator_without_allocation(num1, num2);
113 Vector<u32> expected_result { 0, 1, 0, 0 };
114 EXPECT_EQ(num1.words(), expected_result);
115}
116
117TEST_CASE(test_unsigned_bigint_simple_subtraction)
118{
119 Crypto::UnsignedBigInteger num1(80);
120 Crypto::UnsignedBigInteger num2(70);
121
122 EXPECT_EQ(num1.minus(num2), Crypto::UnsignedBigInteger(10));
123}
124
125TEST_CASE(test_unsigned_bigint_simple_subtraction_invalid)
126{
127 Crypto::UnsignedBigInteger num1(50);
128 Crypto::UnsignedBigInteger num2(70);
129
130 EXPECT(num1.minus(num2).is_invalid());
131}
132
133TEST_CASE(test_unsigned_bigint_simple_subtraction_with_borrow)
134{
135 Crypto::UnsignedBigInteger num1(UINT32_MAX);
136 Crypto::UnsignedBigInteger num2(1);
137 Crypto::UnsignedBigInteger num3 = num1.plus(num2);
138 Crypto::UnsignedBigInteger result = num3.minus(num2);
139 EXPECT_EQ(result, num1);
140}
141
142TEST_CASE(test_unsigned_bigint_subtraction_with_large_numbers)
143{
144 Crypto::UnsignedBigInteger num1 = bigint_fibonacci(343);
145 Crypto::UnsignedBigInteger num2 = bigint_fibonacci(218);
146 Crypto::UnsignedBigInteger result = num1.minus(num2);
147
148 Vector<u32> expected_result {
149 811430588, 2958904896, 1130908877, 2830569969, 3243275482,
150 3047460725, 774025231, 7990
151 };
152 EXPECT_EQ(result.plus(num2), num1);
153 EXPECT_EQ(result.words(), expected_result);
154}
155
156TEST_CASE(test_unsigned_bigint_subtraction_with_large_numbers2)
157{
158 Crypto::UnsignedBigInteger num1(Vector<u32> { 1483061863, 446680044, 1123294122, 191895498, 3347106536, 16, 0, 0, 0 });
159 Crypto::UnsignedBigInteger num2(Vector<u32> { 4196414175, 1117247942, 1123294122, 191895498, 3347106536, 16 });
160 Crypto::UnsignedBigInteger result = num1.minus(num2);
161 // this test only verifies that we don't crash on an assertion
162}
163
164TEST_CASE(test_unsigned_bigint_subtraction_regression_1)
165{
166 auto num = Crypto::UnsignedBigInteger { 1 }.shift_left(256);
167 Vector<u32> expected_result {
168 4294967295, 4294967295, 4294967295, 4294967295, 4294967295,
169 4294967295, 4294967295, 4294967295, 0
170 };
171 EXPECT_EQ(num.minus(1).words(), expected_result);
172}
173
174TEST_CASE(test_unsigned_bigint_simple_multiplication)
175{
176 Crypto::UnsignedBigInteger num1(8);
177 Crypto::UnsignedBigInteger num2(251);
178 Crypto::UnsignedBigInteger result = num1.multiplied_by(num2);
179 EXPECT_EQ(result.words(), Vector<u32> { 2008 });
180}
181
182TEST_CASE(test_unsigned_bigint_multiplication_with_big_numbers1)
183{
184 Crypto::UnsignedBigInteger num1 = bigint_fibonacci(200);
185 Crypto::UnsignedBigInteger num2(12345678);
186 Crypto::UnsignedBigInteger result = num1.multiplied_by(num2);
187 Vector<u32> expected_result { 669961318, 143970113, 4028714974, 3164551305, 1589380278, 2 };
188 EXPECT_EQ(result.words(), expected_result);
189}
190
191TEST_CASE(test_unsigned_bigint_multiplication_with_big_numbers2)
192{
193 Crypto::UnsignedBigInteger num1 = bigint_fibonacci(200);
194 Crypto::UnsignedBigInteger num2 = bigint_fibonacci(341);
195 Crypto::UnsignedBigInteger result = num1.multiplied_by(num2);
196 Vector<u32> expected_result {
197 3017415433, 2741793511, 1957755698, 3731653885, 3154681877,
198 785762127, 3200178098, 4260616581, 529754471, 3632684436,
199 1073347813, 2516430
200 };
201 EXPECT_EQ(result.words(), expected_result);
202}
203
204TEST_CASE(test_unsigned_bigint_simple_division)
205{
206 Crypto::UnsignedBigInteger num1(27194);
207 Crypto::UnsignedBigInteger num2(251);
208 auto result = num1.divided_by(num2);
209 Crypto::UnsignedDivisionResult expected = { Crypto::UnsignedBigInteger(108), Crypto::UnsignedBigInteger(86) };
210 EXPECT_EQ(result.quotient, expected.quotient);
211 EXPECT_EQ(result.remainder, expected.remainder);
212}
213
214TEST_CASE(test_unsigned_bigint_division_with_big_numbers)
215{
216 Crypto::UnsignedBigInteger num1 = bigint_fibonacci(386);
217 Crypto::UnsignedBigInteger num2 = bigint_fibonacci(238);
218 auto result = num1.divided_by(num2);
219 Crypto::UnsignedDivisionResult expected = {
220 Crypto::UnsignedBigInteger(Vector<u32> { 2300984486, 2637503534, 2022805584, 107 }),
221 Crypto::UnsignedBigInteger(Vector<u32> { 1483061863, 446680044, 1123294122, 191895498, 3347106536, 16, 0, 0, 0 })
222 };
223 EXPECT_EQ(result.quotient, expected.quotient);
224 EXPECT_EQ(result.remainder, expected.remainder);
225}
226
227TEST_CASE(test_unsigned_bigint_division_combined_test)
228{
229 auto num1 = bigint_fibonacci(497);
230 auto num2 = bigint_fibonacci(238);
231 auto div_result = num1.divided_by(num2);
232 EXPECT_EQ(div_result.quotient.multiplied_by(num2).plus(div_result.remainder), num1);
233}
234
235TEST_CASE(test_unsigned_bigint_base10_from_string)
236{
237 auto result = Crypto::UnsignedBigInteger::from_base(10, "57195071295721390579057195715793"sv);
238 Vector<u32> expected_result { 3806301393, 954919431, 3879607298, 721 };
239 EXPECT_EQ(result.words(), expected_result);
240}
241
242TEST_CASE(test_unsigned_bigint_base10_to_string)
243{
244 auto bigint = Crypto::UnsignedBigInteger {
245 Vector<u32> { 3806301393, 954919431, 3879607298, 721 }
246 };
247 auto result = MUST(bigint.to_base(10));
248 EXPECT_EQ(result, "57195071295721390579057195715793");
249}
250
251TEST_CASE(test_bigint_modular_inverse)
252{
253 auto result = Crypto::NumberTheory::ModularInverse(7, 87);
254 EXPECT_EQ(result, 25);
255}
256
257TEST_CASE(test_bigint_even_simple_modular_power)
258{
259 Crypto::UnsignedBigInteger base { 7 };
260 Crypto::UnsignedBigInteger exponent { 2 };
261 Crypto::UnsignedBigInteger modulo { 10 };
262 auto result = Crypto::NumberTheory::ModularPower(base, exponent, modulo);
263 EXPECT_EQ(result.words(), Vector<u32> { 9 });
264}
265
266TEST_CASE(test_bigint_odd_simple_modular_power)
267{
268 Crypto::UnsignedBigInteger base { 10 };
269 Crypto::UnsignedBigInteger exponent { 2 };
270 Crypto::UnsignedBigInteger modulo { 9 };
271 auto result = Crypto::NumberTheory::ModularPower(base, exponent, modulo);
272 EXPECT_EQ(result.words(), Vector<u32> { 1 });
273}
274
275TEST_CASE(test_bigint_large_even_fibonacci_modular_power)
276{
277 Crypto::UnsignedBigInteger base = bigint_fibonacci(200);
278 Crypto::UnsignedBigInteger exponent = bigint_fibonacci(100);
279 Crypto::UnsignedBigInteger modulo = bigint_fibonacci(150);
280 // Result according to Wolfram Alpha : 7195284628716783672927396027925
281 auto result = Crypto::NumberTheory::ModularPower(base, exponent, modulo);
282 Vector<u32> expected_result { 2042093077, 1351416233, 3510104665, 90 };
283 EXPECT_EQ(result.words(), expected_result);
284}
285
286TEST_CASE(test_bigint_large_odd_fibonacci_modular_power)
287{
288 Crypto::UnsignedBigInteger base = bigint_fibonacci(200);
289 Crypto::UnsignedBigInteger exponent = bigint_fibonacci(100);
290 Crypto::UnsignedBigInteger modulo = bigint_fibonacci(149);
291 // Result according to Wolfram Alpha : 1136278609611966596838389694992
292 auto result = Crypto::NumberTheory::ModularPower(base, exponent, modulo);
293 Vector<u32> expected_result { 2106049040, 2169509253, 1468244710, 14 };
294 EXPECT_EQ(result.words(), expected_result);
295}
296
297TEST_CASE(test_bigint_large_odd_fibonacci_with_carry_modular_power)
298{
299 Crypto::UnsignedBigInteger base = bigint_fibonacci(200);
300 Crypto::UnsignedBigInteger exponent = bigint_fibonacci(100);
301 Crypto::UnsignedBigInteger modulo = bigint_fibonacci(185);
302 // Result according to Wolfram Alpha : 55094573983071006678665780782730672080
303 auto result = Crypto::NumberTheory::ModularPower(base, exponent, modulo);
304 Vector<u32> expected_result { 1988720592, 2097784252, 347129583, 695391288 };
305 EXPECT_EQ(result.words(), expected_result);
306}
307
308TEST_CASE(test_bigint_modular_power_extra_tests)
309{
310 struct {
311 Crypto::UnsignedBigInteger base;
312 Crypto::UnsignedBigInteger exp;
313 Crypto::UnsignedBigInteger mod;
314 Crypto::UnsignedBigInteger expected;
315 } mod_pow_tests[] = {
316 { "2988348162058574136915891421498819466320163312926952423791023078876139"_bigint, "2351399303373464486466122544523690094744975233415544072992656881240319"_bigint, "10000"_bigint, "3059"_bigint },
317 { "24231"_bigint, "12448"_bigint, "14679"_bigint, "4428"_bigint },
318 { "1005404"_bigint, "8352654"_bigint, "8161408"_bigint, "2605696"_bigint },
319 { "3665005778"_bigint, "3244425589"_bigint, "565668506"_bigint, "524766494"_bigint },
320 { "10662083169959689657"_bigint, "11605678468317533000"_bigint, "1896834583057209739"_bigint, "1292743154593945858"_bigint },
321 { "99667739213529524852296932424683448520"_bigint, "123394910770101395416306279070921784207"_bigint, "238026722756504133786938677233768788719"_bigint, "197165477545023317459748215952393063201"_bigint },
322 { "49368547511968178788919424448914214709244872098814465088945281575062739912239"_bigint, "25201856190991298572337188495596990852134236115562183449699512394891190792064"_bigint, "45950460777961491021589776911422805972195170308651734432277141467904883064645"_bigint, "39917885806532796066922509794537889114718612292469285403012781055544152450051"_bigint },
323 { "48399385336454791246880286907257136254351739111892925951016159217090949616810"_bigint, "5758661760571644379364752528081901787573279669668889744323710906207949658569"_bigint, "32812120644405991429173950312949738783216437173380339653152625840449006970808"_bigint, "7948464125034399875323770213514649646309423451213282653637296324080400293584"_bigint },
324 };
325
326 for (auto test_case : mod_pow_tests) {
327 auto actual = Crypto::NumberTheory::ModularPower(
328 test_case.base, test_case.exp, test_case.mod);
329
330 EXPECT_EQ(actual, test_case.expected);
331 }
332}
333
334TEST_CASE(test_bigint_primality_test)
335{
336 struct {
337 Crypto::UnsignedBigInteger candidate;
338 bool expected_result;
339 } primality_tests[] = {
340 { "1180591620717411303424"_bigint, false }, // 2**70
341 { "620448401733239439360000"_bigint, false }, // 25!
342 { "953962166440690129601298432"_bigint, false }, // 12**25
343 { "620448401733239439360000"_bigint, false }, // 25!
344 { "147926426347074375"_bigint, false }, // 35! / 2**32
345 { "340282366920938429742726440690708343523"_bigint, false }, // 2 factors near 2^64
346 { "73"_bigint, true },
347 { "6967"_bigint, true },
348 { "787649"_bigint, true },
349 { "73513949"_bigint, true },
350 { "6691236901"_bigint, true },
351 { "741387182759"_bigint, true },
352 { "67466615915827"_bigint, true },
353 { "9554317039214687"_bigint, true },
354 { "533344522150170391"_bigint, true },
355 { "18446744073709551557"_bigint, true }, // just below 2**64
356 };
357
358 for (auto test_case : primality_tests) {
359 bool actual_result = Crypto::NumberTheory::is_probably_prime(test_case.candidate);
360 EXPECT_EQ(test_case.expected_result, actual_result);
361 }
362}
363
364TEST_CASE(test_bigint_random_number_generation)
365{
366 struct {
367 Crypto::UnsignedBigInteger min;
368 Crypto::UnsignedBigInteger max;
369 } random_number_tests[] = {
370 { "1"_bigint, "1000000"_bigint },
371 { "10000000000"_bigint, "20000000000"_bigint },
372 { "1000"_bigint, "200000000000000000"_bigint },
373 { "200000000000000000"_bigint, "200000000000010000"_bigint },
374 };
375
376 for (auto test_case : random_number_tests) {
377 auto actual_result = Crypto::NumberTheory::random_number(test_case.min, test_case.max);
378 EXPECT(!(actual_result < test_case.min));
379 EXPECT(actual_result < test_case.max);
380 }
381}
382
383TEST_CASE(test_bigint_random_distribution)
384{
385 auto actual_result = Crypto::NumberTheory::random_number(
386 "1"_bigint,
387 "100000000000000000000000000000"_bigint); // 10**29
388 if (actual_result < "100000000000000000000"_bigint) { // 10**20
389 FAIL("Too small");
390 outln("The generated number {} is extremely small. This *can* happen by pure chance, but should happen only once in a billion times. So it's probably an error.", MUST(actual_result.to_base(10)));
391 } else if ("99999999900000000000000000000"_bigint < actual_result) { // 10**29 - 10**20
392 FAIL("Too large");
393 outln("The generated number {} is extremely large. This *can* happen by pure chance, but should happen only once in a billion times. So it's probably an error.", MUST(actual_result.to_base(10)));
394 }
395}
396
397TEST_CASE(test_bigint_import_big_endian_decode_encode_roundtrip)
398{
399 u8 random_bytes[128];
400 u8 target_buffer[128];
401 fill_with_random(random_bytes, 128);
402 auto encoded = Crypto::UnsignedBigInteger::import_data(random_bytes, 128);
403 encoded.export_data({ target_buffer, 128 });
404 EXPECT(memcmp(target_buffer, random_bytes, 128) == 0);
405}
406
407TEST_CASE(test_bigint_import_big_endian_encode_decode_roundtrip)
408{
409 u8 target_buffer[128];
410 auto encoded = "12345678901234567890"_bigint;
411 auto size = encoded.export_data({ target_buffer, 128 });
412 auto decoded = Crypto::UnsignedBigInteger::import_data(target_buffer, size);
413 EXPECT_EQ(encoded, decoded);
414}
415
416TEST_CASE(test_bigint_big_endian_import)
417{
418 auto number = Crypto::UnsignedBigInteger::import_data("hello"sv);
419 EXPECT_EQ(number, "448378203247"_bigint);
420}
421
422TEST_CASE(test_bigint_big_endian_export)
423{
424 auto number = "448378203247"_bigint;
425 char exported[8] { 0 };
426 auto exported_length = number.export_data({ exported, 8 }, true);
427 EXPECT_EQ(exported_length, 5u);
428 EXPECT(memcmp(exported + 3, "hello", 5) == 0);
429}
430
431TEST_CASE(test_bigint_one_based_index_of_highest_set_bit)
432{
433 auto num1 = "1234567"_bigint;
434 auto num2 = "1234567"_bigint;
435 EXPECT_EQ("0"_bigint.one_based_index_of_highest_set_bit(), 0u);
436 EXPECT_EQ("1"_bigint.one_based_index_of_highest_set_bit(), 1u);
437 EXPECT_EQ("7"_bigint.one_based_index_of_highest_set_bit(), 3u);
438 EXPECT_EQ("4294967296"_bigint.one_based_index_of_highest_set_bit(), 33u);
439}
440
441TEST_CASE(test_signed_bigint_bitwise_not_fill_to_one_based_index)
442{
443 EXPECT_EQ("0"_bigint.bitwise_not_fill_to_one_based_index(0), "0"_bigint);
444 EXPECT_EQ("0"_bigint.bitwise_not_fill_to_one_based_index(1), "1"_bigint);
445 EXPECT_EQ("0"_bigint.bitwise_not_fill_to_one_based_index(2), "3"_bigint);
446 EXPECT_EQ("0"_bigint.bitwise_not_fill_to_one_based_index(4), "15"_bigint);
447 EXPECT_EQ("0"_bigint.bitwise_not_fill_to_one_based_index(32), "4294967295"_bigint);
448 EXPECT_EQ("0"_bigint.bitwise_not_fill_to_one_based_index(33), "8589934591"_bigint);
449}
450
451TEST_CASE(test_bigint_bitwise_or)
452{
453 auto num1 = "1234567"_bigint;
454 auto num2 = "1234567"_bigint;
455 EXPECT_EQ(num1.bitwise_or(num2), num1);
456}
457
458TEST_CASE(test_bigint_bitwise_or_different_lengths)
459{
460 auto num1 = "1234567"_bigint;
461 auto num2 = "123456789012345678901234567890"_bigint;
462 auto expected = "123456789012345678901234622167"_bigint;
463 auto result = num1.bitwise_or(num2);
464 EXPECT_EQ(result, expected);
465}
466
467TEST_CASE(test_signed_bigint_bitwise_or)
468{
469 auto num1 = "-1234567"_sbigint;
470 auto num2 = "1234567"_sbigint;
471 EXPECT_EQ(num1.bitwise_or(num1), num1);
472 EXPECT_EQ(num1.bitwise_or(num2), "-1"_sbigint);
473 EXPECT_EQ(num2.bitwise_or(num1), "-1"_sbigint);
474 EXPECT_EQ(num2.bitwise_or(num2), num2);
475
476 EXPECT_EQ("0"_sbigint.bitwise_or("-1"_sbigint), "-1"_sbigint);
477}
478
479TEST_CASE(test_bigint_bitwise_and)
480{
481 auto num1 = "1234567"_bigint;
482 auto num2 = "1234561"_bigint;
483 EXPECT_EQ(num1.bitwise_and(num2), "1234561"_bigint);
484}
485
486TEST_CASE(test_bigint_bitwise_and_different_lengths)
487{
488 auto num1 = "1234567"_bigint;
489 auto num2 = "123456789012345678901234567890"_bigint;
490 EXPECT_EQ(num1.bitwise_and(num2), "1180290"_bigint);
491}
492
493TEST_CASE(test_signed_bigint_bitwise_not)
494{
495 EXPECT_EQ("3"_sbigint.bitwise_not(), "-4"_sbigint);
496 EXPECT_EQ("-1"_sbigint.bitwise_not(), "0"_sbigint);
497}
498
499TEST_CASE(test_signed_bigint_bitwise_and)
500{
501 auto num1 = "-1234567"_sbigint;
502 auto num2 = "1234567"_sbigint;
503 EXPECT_EQ(num1.bitwise_and(num1), num1);
504 EXPECT_EQ(num1.bitwise_and(num2), "1"_sbigint);
505 EXPECT_EQ(num2.bitwise_and(num1), "1"_sbigint);
506 EXPECT_EQ(num2.bitwise_and(num2), num2);
507
508 EXPECT_EQ("-3"_sbigint.bitwise_and("-2"_sbigint), "-4"_sbigint);
509}
510
511TEST_CASE(test_bigint_bitwise_xor)
512{
513 auto num1 = "1234567"_bigint;
514 auto num2 = "1234561"_bigint;
515 EXPECT_EQ(num1.bitwise_xor(num2), 6);
516}
517
518TEST_CASE(test_bigint_bitwise_xor_different_lengths)
519{
520 auto num1 = "1234567"_bigint;
521 auto num2 = "123456789012345678901234567890"_bigint;
522 EXPECT_EQ(num1.bitwise_xor(num2), "123456789012345678901233441877"_bigint);
523}
524
525TEST_CASE(test_signed_bigint_bitwise_xor)
526{
527 auto num1 = "-3"_sbigint;
528 auto num2 = "1"_sbigint;
529 EXPECT_EQ(num1.bitwise_xor(num1), "0"_sbigint);
530 EXPECT_EQ(num1.bitwise_xor(num2), "-4"_sbigint);
531 EXPECT_EQ(num2.bitwise_xor(num1), "-4"_sbigint);
532 EXPECT_EQ(num2.bitwise_xor(num2), "0"_sbigint);
533}
534
535TEST_CASE(test_signed_bigint_fibo500)
536{
537 Vector<u32> expected_result {
538 315178285, 505575602, 1883328078, 125027121,
539 3649625763, 347570207, 74535262, 3832543808,
540 2472133297, 1600064941, 65273441
541 };
542 auto result = bigint_signed_fibonacci(500);
543 EXPECT_EQ(result.unsigned_value().words(), expected_result);
544}
545
546TEST_CASE(test_signed_addition_edgecase_borrow_with_zero)
547{
548 Crypto::SignedBigInteger num1 { Crypto::UnsignedBigInteger { { UINT32_MAX - 3, UINT32_MAX } }, false };
549 Crypto::SignedBigInteger num2 { Crypto::UnsignedBigInteger { UINT32_MAX - 2 }, false };
550 Vector<u32> expected_result { 4294967289, 0, 1 };
551 EXPECT_EQ(num1.plus(num2).unsigned_value().words(), expected_result);
552}
553
554TEST_CASE(test_signed_addition_edgecase_addition_to_other_sign)
555{
556 Crypto::SignedBigInteger num1 = INT32_MAX;
557 Crypto::SignedBigInteger num2 = num1;
558 num2.negate();
559 EXPECT_EQ(num1.plus(num2), Crypto::SignedBigInteger { 0 });
560}
561
562TEST_CASE(test_signed_subtraction_simple_subtraction_positive_result)
563{
564 Crypto::SignedBigInteger num1(80);
565 Crypto::SignedBigInteger num2(70);
566 EXPECT_EQ(num1.minus(num2), Crypto::SignedBigInteger(10));
567}
568
569TEST_CASE(test_signed_subtraction_simple_subtraction_negative_result)
570{
571 Crypto::SignedBigInteger num1(50);
572 Crypto::SignedBigInteger num2(70);
573
574 EXPECT_EQ(num1.minus(num2), Crypto::SignedBigInteger { -20 });
575}
576
577TEST_CASE(test_signed_subtraction_both_negative)
578{
579 Crypto::SignedBigInteger num1(-50);
580 Crypto::SignedBigInteger num2(-70);
581
582 EXPECT_EQ(num1.minus(num2), Crypto::SignedBigInteger { 20 });
583 EXPECT_EQ(num2.minus(num1), Crypto::SignedBigInteger { -20 });
584}
585
586TEST_CASE(test_signed_subtraction_simple_subtraction_with_borrow)
587{
588 Crypto::SignedBigInteger num1(Crypto::UnsignedBigInteger { UINT32_MAX });
589 Crypto::SignedBigInteger num2(1);
590 Crypto::SignedBigInteger num3 = num1.plus(num2);
591 Crypto::SignedBigInteger result = num2.minus(num3);
592 num1.negate();
593 EXPECT_EQ(result, num1);
594}
595
596TEST_CASE(test_signed_subtraction_with_large_numbers)
597{
598 Crypto::SignedBigInteger num1 = bigint_signed_fibonacci(343);
599 Crypto::SignedBigInteger num2 = bigint_signed_fibonacci(218);
600 Crypto::SignedBigInteger result = num2.minus(num1);
601 auto expected = Crypto::UnsignedBigInteger { Vector<u32> { 811430588, 2958904896, 1130908877, 2830569969, 3243275482, 3047460725, 774025231, 7990 } };
602 EXPECT_EQ(result.plus(num1), num2);
603 EXPECT_EQ(result.unsigned_value(), expected);
604}
605
606TEST_CASE(test_signed_subtraction_with_large_numbers_check_for_assertion)
607{
608 Crypto::SignedBigInteger num1(Crypto::UnsignedBigInteger { Vector<u32> { 1483061863, 446680044, 1123294122, 191895498, 3347106536, 16, 0, 0, 0 } });
609 Crypto::SignedBigInteger num2(Crypto::UnsignedBigInteger { Vector<u32> { 4196414175, 1117247942, 1123294122, 191895498, 3347106536, 16 } });
610 Crypto::SignedBigInteger result = num1.minus(num2);
611 // this test only verifies that we don't crash on an assertion
612}
613
614TEST_CASE(test_signed_multiplication_with_negative_number)
615{
616 Crypto::SignedBigInteger num1(8);
617 Crypto::SignedBigInteger num2(-251);
618 Crypto::SignedBigInteger result = num1.multiplied_by(num2);
619 EXPECT_EQ(result, Crypto::SignedBigInteger { -2008 });
620}
621
622TEST_CASE(test_signed_multiplication_with_big_number)
623{
624 Crypto::SignedBigInteger num1 = bigint_signed_fibonacci(200);
625 Crypto::SignedBigInteger num2(-12345678);
626 Crypto::SignedBigInteger result = num1.multiplied_by(num2);
627 Vector<u32> expected_result { 669961318, 143970113, 4028714974, 3164551305, 1589380278, 2 };
628 EXPECT_EQ(result.unsigned_value().words(), expected_result);
629 EXPECT(result.is_negative());
630}
631
632TEST_CASE(test_signed_multiplication_with_two_big_numbers)
633{
634 Crypto::SignedBigInteger num1 = bigint_signed_fibonacci(200);
635 Crypto::SignedBigInteger num2 = bigint_signed_fibonacci(341);
636 num1.negate();
637 Crypto::SignedBigInteger result = num1.multiplied_by(num2);
638 Vector<u32> expected_results {
639 3017415433, 2741793511, 1957755698, 3731653885,
640 3154681877, 785762127, 3200178098, 4260616581,
641 529754471, 3632684436, 1073347813, 2516430
642 };
643 EXPECT_EQ(result.unsigned_value().words(), expected_results);
644 EXPECT(result.is_negative());
645}
646
647TEST_CASE(test_negative_zero_is_not_allowed)
648{
649 Crypto::SignedBigInteger zero(Crypto::UnsignedBigInteger(0), true);
650 EXPECT(!zero.is_negative());
651
652 zero.negate();
653 EXPECT(!zero.is_negative());
654
655 Crypto::SignedBigInteger positive_five(Crypto::UnsignedBigInteger(5), false);
656 Crypto::SignedBigInteger negative_five(Crypto::UnsignedBigInteger(5), true);
657 zero = positive_five.plus(negative_five);
658
659 EXPECT(zero.unsigned_value().is_zero());
660 EXPECT(!zero.is_negative());
661}
662
663TEST_CASE(double_comparisons) {
664#define EXPECT_LESS_THAN(bigint, double_value) EXPECT_EQ(bigint.compare_to_double(double_value), Crypto::UnsignedBigInteger::CompareResult::DoubleGreaterThanBigInt)
665#define EXPECT_GREATER_THAN(bigint, double_value) EXPECT_EQ(bigint.compare_to_double(double_value), Crypto::UnsignedBigInteger::CompareResult::DoubleLessThanBigInt)
666#define EXPECT_EQUAL_TO(bigint, double_value) EXPECT_EQ(bigint.compare_to_double(double_value), Crypto::UnsignedBigInteger::CompareResult::DoubleEqualsBigInt)
667 { Crypto::SignedBigInteger zero { 0 };
668EXPECT_EQUAL_TO(zero, 0.0);
669EXPECT_EQUAL_TO(zero, -0.0);
670}
671
672{
673 Crypto::SignedBigInteger one { 1 };
674 EXPECT_EQUAL_TO(one, 1.0);
675 EXPECT_GREATER_THAN(one, -1.0);
676 EXPECT_GREATER_THAN(one, 0.5);
677 EXPECT_GREATER_THAN(one, -0.5);
678 EXPECT_LESS_THAN(one, 1.000001);
679
680 one.negate();
681 auto const& negative_one = one;
682 EXPECT_EQUAL_TO(negative_one, -1.0);
683 EXPECT_LESS_THAN(negative_one, 1.0);
684 EXPECT_LESS_THAN(one, 0.5);
685 EXPECT_LESS_THAN(one, -0.5);
686 EXPECT_GREATER_THAN(one, -1.5);
687 EXPECT_LESS_THAN(one, 1.000001);
688 EXPECT_GREATER_THAN(one, -1.000001);
689}
690
691{
692 double double_infinity = HUGE_VAL;
693 VERIFY(isinf(double_infinity));
694 Crypto::SignedBigInteger one { 1 };
695 EXPECT_LESS_THAN(one, double_infinity);
696 EXPECT_GREATER_THAN(one, -double_infinity);
697}
698
699{
700 double double_max_value = NumericLimits<double>::max();
701 double double_below_max_value = nextafter(double_max_value, 0.0);
702 VERIFY(double_below_max_value < double_max_value);
703 VERIFY(double_below_max_value < (double_max_value - 1.0));
704 auto max_value_in_bigint = Crypto::SignedBigInteger::from_base(16, "fffffffffffff800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv);
705 auto max_value_plus_one = max_value_in_bigint.plus(Crypto::SignedBigInteger { 1 });
706 auto max_value_minus_one = max_value_in_bigint.minus(Crypto::SignedBigInteger { 1 });
707
708 auto below_max_value_in_bigint = Crypto::SignedBigInteger::from_base(16, "fffffffffffff000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv);
709
710 EXPECT_EQUAL_TO(max_value_in_bigint, double_max_value);
711 EXPECT_LESS_THAN(max_value_minus_one, double_max_value);
712 EXPECT_GREATER_THAN(max_value_plus_one, double_max_value);
713 EXPECT_LESS_THAN(below_max_value_in_bigint, double_max_value);
714
715 EXPECT_GREATER_THAN(max_value_in_bigint, double_below_max_value);
716 EXPECT_GREATER_THAN(max_value_minus_one, double_below_max_value);
717 EXPECT_GREATER_THAN(max_value_plus_one, double_below_max_value);
718 EXPECT_EQUAL_TO(below_max_value_in_bigint, double_below_max_value);
719}
720
721{
722 double double_min_value = NumericLimits<double>::lowest();
723 double double_above_min_value = nextafter(double_min_value, 0.0);
724 VERIFY(double_above_min_value > double_min_value);
725 VERIFY(double_above_min_value > (double_min_value + 1.0));
726 auto min_value_in_bigint = Crypto::SignedBigInteger::from_base(16, "-fffffffffffff800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv);
727 auto min_value_plus_one = min_value_in_bigint.plus(Crypto::SignedBigInteger { 1 });
728 auto min_value_minus_one = min_value_in_bigint.minus(Crypto::SignedBigInteger { 1 });
729
730 auto above_min_value_in_bigint = Crypto::SignedBigInteger::from_base(16, "-fffffffffffff000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv);
731
732 EXPECT_EQUAL_TO(min_value_in_bigint, double_min_value);
733 EXPECT_LESS_THAN(min_value_minus_one, double_min_value);
734 EXPECT_GREATER_THAN(min_value_plus_one, double_min_value);
735 EXPECT_GREATER_THAN(above_min_value_in_bigint, double_min_value);
736
737 EXPECT_LESS_THAN(min_value_in_bigint, double_above_min_value);
738 EXPECT_LESS_THAN(min_value_minus_one, double_above_min_value);
739 EXPECT_LESS_THAN(min_value_plus_one, double_above_min_value);
740 EXPECT_EQUAL_TO(above_min_value_in_bigint, double_above_min_value);
741}
742
743{
744 double just_above_255 = bit_cast<double>(0x406fe00000000001ULL);
745 double just_below_255 = bit_cast<double>(0x406fdfffffffffffULL);
746 double double_255 = 255.0;
747 Crypto::SignedBigInteger bigint_255 { 255 };
748
749 EXPECT_EQUAL_TO(bigint_255, double_255);
750 EXPECT_GREATER_THAN(bigint_255, just_below_255);
751 EXPECT_LESS_THAN(bigint_255, just_above_255);
752}
753
754#undef EXPECT_LESS_THAN
755#undef EXPECT_GREATER_THAN
756#undef EXPECT_EQUAL_TO
757}
758
759TEST_CASE(to_double)
760{
761#define EXPECT_TO_EQUAL_DOUBLE(bigint, double_value) \
762 EXPECT_EQ((bigint).to_double(Crypto::UnsignedBigInteger::RoundingMode::RoundTowardZero), double_value)
763
764 EXPECT_TO_EQUAL_DOUBLE(Crypto::UnsignedBigInteger(0), 0.0);
765 // Make sure we don't get negative zero!
766 EXPECT_EQ(signbit(Crypto::UnsignedBigInteger(0).to_double()), 0);
767 {
768 Crypto::SignedBigInteger zero { 0 };
769
770 EXPECT(!zero.is_negative());
771 EXPECT_TO_EQUAL_DOUBLE(zero, 0.0);
772 EXPECT_EQ(signbit(zero.to_double()), 0);
773
774 zero.negate();
775
776 EXPECT(!zero.is_negative());
777 EXPECT_TO_EQUAL_DOUBLE(zero, 0.0);
778 EXPECT_EQ(signbit(zero.to_double()), 0);
779 }
780
781 EXPECT_TO_EQUAL_DOUBLE(Crypto::UnsignedBigInteger(9682), 9682.0);
782 EXPECT_TO_EQUAL_DOUBLE(Crypto::SignedBigInteger(-9660), -9660.0);
783
784 double double_max_value = NumericLimits<double>::max();
785 double infinity = INFINITY;
786
787 EXPECT_TO_EQUAL_DOUBLE(
788 Crypto::UnsignedBigInteger::from_base(16, "fffffffffffff800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv),
789 double_max_value);
790
791 EXPECT_TO_EQUAL_DOUBLE(
792 Crypto::UnsignedBigInteger::from_base(16, "ffffffffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv),
793 double_max_value);
794
795 EXPECT_TO_EQUAL_DOUBLE(
796 Crypto::UnsignedBigInteger::from_base(16, "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"sv),
797 double_max_value);
798
799 EXPECT_TO_EQUAL_DOUBLE(
800 Crypto::UnsignedBigInteger::from_base(16, "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv),
801 infinity);
802
803 EXPECT_TO_EQUAL_DOUBLE(
804 Crypto::SignedBigInteger::from_base(16, "-fffffffffffff800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv),
805 -double_max_value);
806
807 EXPECT_TO_EQUAL_DOUBLE(
808 Crypto::SignedBigInteger::from_base(16, "-ffffffffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv),
809 -double_max_value);
810
811 EXPECT_TO_EQUAL_DOUBLE(
812 Crypto::SignedBigInteger::from_base(16, "-ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"sv),
813 -double_max_value);
814
815 EXPECT_TO_EQUAL_DOUBLE(
816 Crypto::SignedBigInteger::from_base(16, "-10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv),
817 -infinity);
818
819 EXPECT_TO_EQUAL_DOUBLE(
820 Crypto::UnsignedBigInteger::from_base(16, "ffffffffffffffff"sv),
821 18446744073709549568.0);
822
823 EXPECT_TO_EQUAL_DOUBLE(
824 Crypto::UnsignedBigInteger::from_base(16, "fffffffffffff800"sv),
825 18446744073709549568.0);
826
827 EXPECT_TO_EQUAL_DOUBLE(
828 Crypto::UnsignedBigInteger::from_base(16, "fffffffffffff8ff"sv),
829 18446744073709549568.0);
830
831 EXPECT_TO_EQUAL_DOUBLE(Crypto::SignedBigInteger::from_base(10, "1234567890123456789"sv),
832 1234567890123456800.0);
833
834 EXPECT_TO_EQUAL_DOUBLE(Crypto::SignedBigInteger::from_base(10, "2345678901234567890"sv),
835 2345678901234567680.0);
836
837 EXPECT_EQ(
838 Crypto::UnsignedBigInteger::from_base(16, "1fffffffffffff00"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
839 2305843009213693696.0);
840
841 EXPECT_EQ(
842 Crypto::UnsignedBigInteger::from_base(16, "1fffffffffffff00"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::RoundTowardZero),
843 2305843009213693696.0);
844
845 EXPECT_EQ(
846 Crypto::UnsignedBigInteger::from_base(16, "1fffffffffffff80"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
847 2305843009213693952.0);
848
849 EXPECT_EQ(Crypto::UnsignedBigInteger::from_base(16, "20000000000001"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
850 9007199254740992.0);
851
852 EXPECT_EQ(Crypto::UnsignedBigInteger::from_base(16, "20000000000002"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
853 9007199254740994.0);
854
855 // 2^53 = 20000000000000, +3 Rounds up because of tiesRoundToEven
856 EXPECT_EQ(Crypto::UnsignedBigInteger::from_base(16, "20000000000003"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
857 9007199254740996.0);
858
859 // +4 is exactly 9007199254740996
860 EXPECT_EQ(Crypto::UnsignedBigInteger::from_base(16, "20000000000004"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
861 9007199254740996.0);
862
863 // +5 rounds down because of tiesRoundToEven
864 EXPECT_EQ(Crypto::UnsignedBigInteger::from_base(16, "20000000000005"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
865 9007199254740996.0);
866
867 EXPECT_EQ(Crypto::UnsignedBigInteger::from_base(16, "20000000000006"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
868 9007199254740998.0);
869
870 EXPECT_EQ(Crypto::UnsignedBigInteger::from_base(10, "98382635059784269824"sv).to_double(Crypto::UnsignedBigInteger::RoundingMode::IEEERoundAndTiesToEvenMantissa),
871 bit_cast<double>(0x4415555555555555ULL));
872
873#undef EXPECT_TO_EQUAL_DOUBLE
874}
875
876TEST_CASE(bigint_from_double)
877{
878 {
879 Crypto::UnsignedBigInteger from_zero { 0.0 };
880 EXPECT(from_zero.is_zero());
881 EXPECT(!from_zero.is_invalid());
882 }
883
884#define SURVIVES_ROUND_TRIP_UNSIGNED(double_value) \
885 { \
886 Crypto::UnsignedBigInteger bigint { (double_value) }; \
887 EXPECT_EQ(bigint.to_double(), (double_value)); \
888 }
889
890 SURVIVES_ROUND_TRIP_UNSIGNED(0.0);
891 SURVIVES_ROUND_TRIP_UNSIGNED(1.0);
892 SURVIVES_ROUND_TRIP_UNSIGNED(100000.0);
893 SURVIVES_ROUND_TRIP_UNSIGNED(1000000000000.0);
894 SURVIVES_ROUND_TRIP_UNSIGNED(10000000000000000000.0);
895 SURVIVES_ROUND_TRIP_UNSIGNED(NumericLimits<double>::max());
896
897 SURVIVES_ROUND_TRIP_UNSIGNED(bit_cast<double>(0x4340000000000002ULL));
898 SURVIVES_ROUND_TRIP_UNSIGNED(bit_cast<double>(0x4340000000000001ULL));
899 SURVIVES_ROUND_TRIP_UNSIGNED(bit_cast<double>(0x4340000000000000ULL));
900
901 // Failed on last bits of mantissa
902 SURVIVES_ROUND_TRIP_UNSIGNED(bit_cast<double>(0x7EDFFFFFFFFFFFFFULL));
903 SURVIVES_ROUND_TRIP_UNSIGNED(bit_cast<double>(0x7ed5555555555555ULL));
904 SURVIVES_ROUND_TRIP_UNSIGNED(bit_cast<double>(0x7EDCBA9876543210ULL));
905
906 // Has exactly exponent of 32
907 SURVIVES_ROUND_TRIP_UNSIGNED(bit_cast<double>(0x41f22f74e0000000ULL));
908
909#define SURVIVES_ROUND_TRIP_SIGNED(double_value) \
910 { \
911 Crypto::SignedBigInteger bigint_positive { (double_value) }; \
912 EXPECT_EQ(bigint_positive.to_double(), (double_value)); \
913 Crypto::SignedBigInteger bigint_negative { -(double_value) }; \
914 EXPECT_EQ(bigint_negative.to_double(), -(double_value)); \
915 EXPECT(bigint_positive != bigint_negative); \
916 bigint_positive.negate(); \
917 EXPECT(bigint_positive == bigint_negative); \
918 }
919
920 {
921 // Negative zero should be converted to positive zero
922 double const negative_zero = bit_cast<double>(0x8000000000000000);
923
924 // However it should give a bit exact +0.0
925 Crypto::SignedBigInteger from_negative_zero { negative_zero };
926 EXPECT(from_negative_zero.is_zero());
927 EXPECT(!from_negative_zero.is_negative());
928 double result = from_negative_zero.to_double();
929 EXPECT_EQ(result, 0.0);
930 EXPECT_EQ(bit_cast<u64>(result), 0ULL);
931 }
932
933 SURVIVES_ROUND_TRIP_SIGNED(1.0);
934 SURVIVES_ROUND_TRIP_SIGNED(100000.0);
935 SURVIVES_ROUND_TRIP_SIGNED(-1000000000000.0);
936 SURVIVES_ROUND_TRIP_SIGNED(10000000000000000000.0);
937 SURVIVES_ROUND_TRIP_SIGNED(NumericLimits<double>::max());
938 SURVIVES_ROUND_TRIP_SIGNED(NumericLimits<double>::lowest());
939
940 SURVIVES_ROUND_TRIP_SIGNED(bit_cast<double>(0x4340000000000002ULL));
941 SURVIVES_ROUND_TRIP_SIGNED(bit_cast<double>(0x4340000000000001ULL));
942 SURVIVES_ROUND_TRIP_SIGNED(bit_cast<double>(0x4340000000000000ULL));
943 SURVIVES_ROUND_TRIP_SIGNED(bit_cast<double>(0x7EDFFFFFFFFFFFFFULL));
944 SURVIVES_ROUND_TRIP_SIGNED(bit_cast<double>(0x7ed5555555555555ULL));
945 SURVIVES_ROUND_TRIP_SIGNED(bit_cast<double>(0x7EDCBA9876543210ULL));
946
947#undef SURVIVES_ROUND_TRIP_SIGNED
948#undef SURVIVES_ROUND_TRIP_UNSIGNED
949}
950
951TEST_CASE(unsigned_bigint_double_comparisons)
952{
953#define EXPECT_LESS_THAN(bigint, double_value) EXPECT_EQ(bigint.compare_to_double(double_value), Crypto::UnsignedBigInteger::CompareResult::DoubleGreaterThanBigInt)
954#define EXPECT_GREATER_THAN(bigint, double_value) EXPECT_EQ(bigint.compare_to_double(double_value), Crypto::UnsignedBigInteger::CompareResult::DoubleLessThanBigInt)
955#define EXPECT_EQUAL_TO(bigint, double_value) EXPECT_EQ(bigint.compare_to_double(double_value), Crypto::UnsignedBigInteger::CompareResult::DoubleEqualsBigInt)
956
957 {
958 Crypto::UnsignedBigInteger zero { 0 };
959 EXPECT_EQUAL_TO(zero, 0.0);
960 EXPECT_EQUAL_TO(zero, -0.0);
961 }
962
963 {
964 Crypto::UnsignedBigInteger one { 1 };
965 EXPECT_EQUAL_TO(one, 1.0);
966 EXPECT_GREATER_THAN(one, -1.0);
967 EXPECT_GREATER_THAN(one, 0.5);
968 EXPECT_GREATER_THAN(one, -0.5);
969 EXPECT_LESS_THAN(one, 1.000001);
970 }
971
972 {
973 double double_infinity = HUGE_VAL;
974 VERIFY(isinf(double_infinity));
975 Crypto::UnsignedBigInteger one { 1 };
976 EXPECT_LESS_THAN(one, double_infinity);
977 EXPECT_GREATER_THAN(one, -double_infinity);
978 }
979
980 {
981 double double_max_value = NumericLimits<double>::max();
982 double double_below_max_value = nextafter(double_max_value, 0.0);
983 VERIFY(double_below_max_value < double_max_value);
984 VERIFY(double_below_max_value < (double_max_value - 1.0));
985 auto max_value_in_bigint = Crypto::UnsignedBigInteger::from_base(16, "fffffffffffff800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv);
986 auto max_value_plus_one = max_value_in_bigint.plus(Crypto::UnsignedBigInteger { 1 });
987 auto max_value_minus_one = max_value_in_bigint.minus(Crypto::UnsignedBigInteger { 1 });
988
989 auto below_max_value_in_bigint = Crypto::UnsignedBigInteger::from_base(16, "fffffffffffff000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"sv);
990
991 EXPECT_EQUAL_TO(max_value_in_bigint, double_max_value);
992 EXPECT_LESS_THAN(max_value_minus_one, double_max_value);
993 EXPECT_GREATER_THAN(max_value_plus_one, double_max_value);
994 EXPECT_LESS_THAN(below_max_value_in_bigint, double_max_value);
995
996 EXPECT_GREATER_THAN(max_value_in_bigint, double_below_max_value);
997 EXPECT_GREATER_THAN(max_value_minus_one, double_below_max_value);
998 EXPECT_GREATER_THAN(max_value_plus_one, double_below_max_value);
999 EXPECT_EQUAL_TO(below_max_value_in_bigint, double_below_max_value);
1000 }
1001
1002 {
1003 double just_above_255 = bit_cast<double>(0x406fe00000000001ULL);
1004 double just_below_255 = bit_cast<double>(0x406fdfffffffffffULL);
1005 double double_255 = 255.0;
1006 Crypto::UnsignedBigInteger bigint_255 { 255 };
1007
1008 EXPECT_EQUAL_TO(bigint_255, double_255);
1009 EXPECT_GREATER_THAN(bigint_255, just_below_255);
1010 EXPECT_LESS_THAN(bigint_255, just_above_255);
1011 }
1012
1013#undef EXPECT_LESS_THAN
1014#undef EXPECT_GREATER_THAN
1015#undef EXPECT_EQUAL_TO
1016}
1017
1018namespace AK {
1019
1020template<>
1021struct Formatter<Crypto::UnsignedBigInteger::CompareResult> : Formatter<StringView> {
1022 ErrorOr<void> format(FormatBuilder& builder, Crypto::UnsignedBigInteger::CompareResult const& compare_result)
1023 {
1024 switch (compare_result) {
1025 case Crypto::UnsignedBigInteger::CompareResult::DoubleEqualsBigInt:
1026 return builder.put_string("Equals"sv);
1027 case Crypto::UnsignedBigInteger::CompareResult::DoubleLessThanBigInt:
1028 return builder.put_string("LessThan"sv);
1029 case Crypto::UnsignedBigInteger::CompareResult::DoubleGreaterThanBigInt:
1030 return builder.put_string("GreaterThan"sv);
1031 default:
1032 return builder.put_string("???"sv);
1033 }
1034 }
1035};
1036
1037}