1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/strings/internal/charconv_bigint.h"
16
17 #include <string>
18
19 #include "gtest/gtest.h"
20
21 namespace absl {
22 ABSL_NAMESPACE_BEGIN
23 namespace strings_internal {
24
TEST(BigUnsigned,ShiftLeft)25 TEST(BigUnsigned, ShiftLeft) {
26 {
27 // Check that 3 * 2**100 is calculated correctly
28 BigUnsigned<4> num(3u);
29 num.ShiftLeft(100);
30 EXPECT_EQ(num, BigUnsigned<4>("3802951800684688204490109616128"));
31 }
32 {
33 // Test that overflow is truncated properly.
34 // 15 is 4 bits long, and BigUnsigned<4> is a 128-bit bigint.
35 // Shifting left by 125 bits should truncate off the high bit, so that
36 // 15 << 125 == 7 << 125
37 // after truncation.
38 BigUnsigned<4> a(15u);
39 BigUnsigned<4> b(7u);
40 BigUnsigned<4> c(3u);
41 a.ShiftLeft(125);
42 b.ShiftLeft(125);
43 c.ShiftLeft(125);
44 EXPECT_EQ(a, b);
45 EXPECT_NE(a, c);
46 }
47 {
48 // Same test, larger bigint:
49 BigUnsigned<84> a(15u);
50 BigUnsigned<84> b(7u);
51 BigUnsigned<84> c(3u);
52 a.ShiftLeft(84 * 32 - 3);
53 b.ShiftLeft(84 * 32 - 3);
54 c.ShiftLeft(84 * 32 - 3);
55 EXPECT_EQ(a, b);
56 EXPECT_NE(a, c);
57 }
58 {
59 // Check that incrementally shifting has the same result as doing it all at
60 // once (attempting to capture corner cases.)
61 const std::string seed = "1234567890123456789012345678901234567890";
62 BigUnsigned<84> a(seed);
63 for (int i = 1; i <= 84 * 32; ++i) {
64 a.ShiftLeft(1);
65 BigUnsigned<84> b(seed);
66 b.ShiftLeft(i);
67 EXPECT_EQ(a, b);
68 }
69 // And we should have fully rotated all bits off by now:
70 EXPECT_EQ(a, BigUnsigned<84>(0u));
71 }
72 {
73 // Bit shifting large and small numbers by large and small offsets.
74 // Intended to exercise bounds-checking corner on ShiftLeft() (directly
75 // and under asan).
76
77 // 2**(32*84)-1
78 const BigUnsigned<84> all_bits_one(
79 "1474444211396924248063325089479706787923460402125687709454567433186613"
80 "6228083464060749874845919674257665016359189106695900028098437021384227"
81 "3285029708032466536084583113729486015826557532750465299832071590813090"
82 "2011853039837649252477307070509704043541368002938784757296893793903797"
83 "8180292336310543540677175225040919704702800559606097685920595947397024"
84 "8303316808753252115729411497720357971050627997031988036134171378490368"
85 "6008000778741115399296162550786288457245180872759047016734959330367829"
86 "5235612397427686310674725251378116268607113017720538636924549612987647"
87 "5767411074510311386444547332882472126067840027882117834454260409440463"
88 "9345147252664893456053258463203120637089916304618696601333953616715125"
89 "2115882482473279040772264257431663818610405673876655957323083702713344"
90 "4201105427930770976052393421467136557055");
91 const BigUnsigned<84> zero(0u);
92 const BigUnsigned<84> one(1u);
93 // in bounds shifts
94 for (int i = 1; i < 84*32; ++i) {
95 // shifting all_bits_one to the left should result in a smaller number,
96 // since the high bits rotate off and the low bits are replaced with
97 // zeroes.
98 BigUnsigned<84> big_shifted = all_bits_one;
99 big_shifted.ShiftLeft(i);
100 EXPECT_GT(all_bits_one, big_shifted);
101 // Shifting 1 to the left should instead result in a larger number.
102 BigUnsigned<84> small_shifted = one;
103 small_shifted.ShiftLeft(i);
104 EXPECT_LT(one, small_shifted);
105 }
106 // Shifting by zero or a negative number has no effect
107 for (int no_op_shift : {0, -1, -84 * 32, std::numeric_limits<int>::min()}) {
108 BigUnsigned<84> big_shifted = all_bits_one;
109 big_shifted.ShiftLeft(no_op_shift);
110 EXPECT_EQ(all_bits_one, big_shifted);
111 BigUnsigned<84> small_shifted = one;
112 big_shifted.ShiftLeft(no_op_shift);
113 EXPECT_EQ(one, small_shifted);
114 }
115 // Shifting by an amount greater than the number of bits should result in
116 // zero.
117 for (int out_of_bounds_shift :
118 {84 * 32, 84 * 32 + 1, std::numeric_limits<int>::max()}) {
119 BigUnsigned<84> big_shifted = all_bits_one;
120 big_shifted.ShiftLeft(out_of_bounds_shift);
121 EXPECT_EQ(zero, big_shifted);
122 BigUnsigned<84> small_shifted = one;
123 small_shifted.ShiftLeft(out_of_bounds_shift);
124 EXPECT_EQ(zero, small_shifted);
125 }
126 }
127 }
128
TEST(BigUnsigned,MultiplyByUint32)129 TEST(BigUnsigned, MultiplyByUint32) {
130 const BigUnsigned<84> factorial_100(
131 "933262154439441526816992388562667004907159682643816214685929638952175999"
132 "932299156089414639761565182862536979208272237582511852109168640000000000"
133 "00000000000000");
134 BigUnsigned<84> a(1u);
135 for (uint32_t i = 1; i <= 100; ++i) {
136 a.MultiplyBy(i);
137 }
138 EXPECT_EQ(a, BigUnsigned<84>(factorial_100));
139 }
140
TEST(BigUnsigned,MultiplyByBigUnsigned)141 TEST(BigUnsigned, MultiplyByBigUnsigned) {
142 {
143 // Put the terms of factorial_200 into two bigints, and multiply them
144 // together.
145 const BigUnsigned<84> factorial_200(
146 "7886578673647905035523632139321850622951359776871732632947425332443594"
147 "4996340334292030428401198462390417721213891963883025764279024263710506"
148 "1926624952829931113462857270763317237396988943922445621451664240254033"
149 "2918641312274282948532775242424075739032403212574055795686602260319041"
150 "7032406235170085879617892222278962370389737472000000000000000000000000"
151 "0000000000000000000000000");
152 BigUnsigned<84> evens(1u);
153 BigUnsigned<84> odds(1u);
154 for (uint32_t i = 1; i < 200; i += 2) {
155 odds.MultiplyBy(i);
156 evens.MultiplyBy(i + 1);
157 }
158 evens.MultiplyBy(odds);
159 EXPECT_EQ(evens, factorial_200);
160 }
161 {
162 // Multiply various powers of 10 together.
163 for (int a = 0 ; a < 700; a += 25) {
164 SCOPED_TRACE(a);
165 BigUnsigned<84> a_value("3" + std::string(a, '0'));
166 for (int b = 0; b < (700 - a); b += 25) {
167 SCOPED_TRACE(b);
168 BigUnsigned<84> b_value("2" + std::string(b, '0'));
169 BigUnsigned<84> expected_product("6" + std::string(a + b, '0'));
170 b_value.MultiplyBy(a_value);
171 EXPECT_EQ(b_value, expected_product);
172 }
173 }
174 }
175 }
176
TEST(BigUnsigned,MultiplyByOverflow)177 TEST(BigUnsigned, MultiplyByOverflow) {
178 {
179 // Check that multiplcation overflow predictably truncates.
180
181 // A big int with all bits on.
182 BigUnsigned<4> all_bits_on("340282366920938463463374607431768211455");
183 // Modulo 2**128, this is equal to -1. Therefore the square of this,
184 // modulo 2**128, should be 1.
185 all_bits_on.MultiplyBy(all_bits_on);
186 EXPECT_EQ(all_bits_on, BigUnsigned<4>(1u));
187 }
188 {
189 // Try multiplying a large bigint by 2**50, and compare the result to
190 // shifting.
191 BigUnsigned<4> value_1("12345678901234567890123456789012345678");
192 BigUnsigned<4> value_2("12345678901234567890123456789012345678");
193 BigUnsigned<4> two_to_fiftieth(1u);
194 two_to_fiftieth.ShiftLeft(50);
195
196 value_1.ShiftLeft(50);
197 value_2.MultiplyBy(two_to_fiftieth);
198 EXPECT_EQ(value_1, value_2);
199 }
200 }
201
TEST(BigUnsigned,FiveToTheNth)202 TEST(BigUnsigned, FiveToTheNth) {
203 {
204 // Sanity check that MultiplyByFiveToTheNth gives consistent answers, up to
205 // and including overflow.
206 for (int i = 0; i < 1160; ++i) {
207 SCOPED_TRACE(i);
208 BigUnsigned<84> value_1(123u);
209 BigUnsigned<84> value_2(123u);
210 value_1.MultiplyByFiveToTheNth(i);
211 for (int j = 0; j < i; j++) {
212 value_2.MultiplyBy(5u);
213 }
214 EXPECT_EQ(value_1, value_2);
215 }
216 }
217 {
218 // Check that the faster, table-lookup-based static method returns the same
219 // result that multiplying in-place would return, up to and including
220 // overflow.
221 for (int i = 0; i < 1160; ++i) {
222 SCOPED_TRACE(i);
223 BigUnsigned<84> value_1(1u);
224 value_1.MultiplyByFiveToTheNth(i);
225 BigUnsigned<84> value_2 = BigUnsigned<84>::FiveToTheNth(i);
226 EXPECT_EQ(value_1, value_2);
227 }
228 }
229 }
230
TEST(BigUnsigned,TenToTheNth)231 TEST(BigUnsigned, TenToTheNth) {
232 {
233 // Sanity check MultiplyByTenToTheNth.
234 for (int i = 0; i < 800; ++i) {
235 SCOPED_TRACE(i);
236 BigUnsigned<84> value_1(123u);
237 BigUnsigned<84> value_2(123u);
238 value_1.MultiplyByTenToTheNth(i);
239 for (int j = 0; j < i; j++) {
240 value_2.MultiplyBy(10u);
241 }
242 EXPECT_EQ(value_1, value_2);
243 }
244 }
245 {
246 // Alternate testing approach, taking advantage of the decimal parser.
247 for (int i = 0; i < 200; ++i) {
248 SCOPED_TRACE(i);
249 BigUnsigned<84> value_1(135u);
250 value_1.MultiplyByTenToTheNth(i);
251 BigUnsigned<84> value_2("135" + std::string(i, '0'));
252 EXPECT_EQ(value_1, value_2);
253 }
254 }
255 }
256
257
258 } // namespace strings_internal
259 ABSL_NAMESPACE_END
260 } // namespace absl
261