1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 // https://developers.google.com/protocol-buffers/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 // * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following disclaimer
13 // in the documentation and/or other materials provided with the
14 // distribution.
15 // * Neither the name of Google Inc. nor the names of its
16 // contributors may be used to endorse or promote products derived from
17 // this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31 #include <google/protobuf/stubs/int128.h>
32
33 #include <algorithm>
34 #include <sstream>
35 #include <utility>
36
37 #include <google/protobuf/testing/googletest.h>
38 #include <gtest/gtest.h>
39
40 namespace google {
41 namespace protobuf {
42
TEST(Int128,AllTests)43 TEST(Int128, AllTests) {
44 uint128 zero(0);
45 uint128 one(1);
46 uint128 one_2arg(0, 1);
47 uint128 two(0, 2);
48 uint128 three(0, 3);
49 uint128 big(2000, 2);
50 uint128 big_minus_one(2000, 1);
51 uint128 bigger(2001, 1);
52 uint128 biggest(kuint128max);
53 uint128 high_low(1, 0);
54 uint128 low_high(0, kuint64max);
55 EXPECT_LT(one, two);
56 EXPECT_GT(two, one);
57 EXPECT_LT(one, big);
58 EXPECT_LT(one, big);
59 EXPECT_EQ(one, one_2arg);
60 EXPECT_NE(one, two);
61 EXPECT_GT(big, one);
62 EXPECT_GE(big, two);
63 EXPECT_GE(big, big_minus_one);
64 EXPECT_GT(big, big_minus_one);
65 EXPECT_LT(big_minus_one, big);
66 EXPECT_LE(big_minus_one, big);
67 EXPECT_NE(big_minus_one, big);
68 EXPECT_LT(big, biggest);
69 EXPECT_LE(big, biggest);
70 EXPECT_GT(biggest, big);
71 EXPECT_GE(biggest, big);
72 EXPECT_EQ(big, ~~big);
73 EXPECT_EQ(one, one | one);
74 EXPECT_EQ(big, big | big);
75 EXPECT_EQ(one, one | zero);
76 EXPECT_EQ(one, one & one);
77 EXPECT_EQ(big, big & big);
78 EXPECT_EQ(zero, one & zero);
79 EXPECT_EQ(zero, big & ~big);
80 EXPECT_EQ(zero, one ^ one);
81 EXPECT_EQ(zero, big ^ big);
82 EXPECT_EQ(one, one ^ zero);
83
84 // Shift operators.
85 EXPECT_EQ(big, big << 0);
86 EXPECT_EQ(big, big >> 0);
87 EXPECT_GT(big << 1, big);
88 EXPECT_LT(big >> 1, big);
89 EXPECT_EQ(big, (big << 10) >> 10);
90 EXPECT_EQ(big, (big >> 1) << 1);
91 EXPECT_EQ(one, (one << 80) >> 80);
92 EXPECT_EQ(zero, (one >> 80) << 80);
93 EXPECT_EQ(zero, big >> 128);
94 EXPECT_EQ(zero, big << 128);
95
96 // Shift assignments.
97 uint128 big_copy = big;
98 EXPECT_EQ(big << 0, big_copy <<= 0);
99 big_copy = big;
100 EXPECT_EQ(big >> 0, big_copy >>= 0);
101 big_copy = big;
102 EXPECT_EQ(big << 1, big_copy <<= 1);
103 big_copy = big;
104 EXPECT_EQ(big >> 1, big_copy >>= 1);
105 big_copy = big;
106 EXPECT_EQ(big << 10, big_copy <<= 10);
107 big_copy = big;
108 EXPECT_EQ(big >> 10, big_copy >>= 10);
109 big_copy = big;
110 EXPECT_EQ(big << 64, big_copy <<= 64);
111 big_copy = big;
112 EXPECT_EQ(big >> 64, big_copy >>= 64);
113 big_copy = big;
114 EXPECT_EQ(big << 73, big_copy <<= 73);
115 big_copy = big;
116 EXPECT_EQ(big >> 73, big_copy >>= 73);
117 big_copy = big;
118 EXPECT_EQ(big << 128, big_copy <<= 128);
119 big_copy = big;
120 EXPECT_EQ(big >> 128, big_copy >>= 128);
121
122 EXPECT_EQ(Uint128High64(biggest), kuint64max);
123 EXPECT_EQ(Uint128Low64(biggest), kuint64max);
124 EXPECT_EQ(zero + one, one);
125 EXPECT_EQ(one + one, two);
126 EXPECT_EQ(big_minus_one + one, big);
127 EXPECT_EQ(one - one, zero);
128 EXPECT_EQ(one - zero, one);
129 EXPECT_EQ(zero - one, biggest);
130 EXPECT_EQ(big - big, zero);
131 EXPECT_EQ(big - one, big_minus_one);
132 EXPECT_EQ(big + kuint64max, bigger);
133 EXPECT_EQ(biggest + 1, zero);
134 EXPECT_EQ(zero - 1, biggest);
135 EXPECT_EQ(high_low - one, low_high);
136 EXPECT_EQ(low_high + one, high_low);
137 EXPECT_EQ(Uint128High64((uint128(1) << 64) - 1), 0);
138 EXPECT_EQ(Uint128Low64((uint128(1) << 64) - 1), kuint64max);
139 EXPECT_TRUE(!!one);
140 EXPECT_TRUE(!!high_low);
141 EXPECT_FALSE(!!zero);
142 EXPECT_FALSE(!one);
143 EXPECT_FALSE(!high_low);
144 EXPECT_TRUE(!zero);
145 EXPECT_TRUE(zero == 0);
146 EXPECT_FALSE(zero != 0);
147 EXPECT_FALSE(one == 0);
148 EXPECT_TRUE(one != 0);
149
150 uint128 test = zero;
151 EXPECT_EQ(++test, one);
152 EXPECT_EQ(test, one);
153 EXPECT_EQ(test++, one);
154 EXPECT_EQ(test, two);
155 EXPECT_EQ(test -= 2, zero);
156 EXPECT_EQ(test, zero);
157 EXPECT_EQ(test += 2, two);
158 EXPECT_EQ(test, two);
159 EXPECT_EQ(--test, one);
160 EXPECT_EQ(test, one);
161 EXPECT_EQ(test--, one);
162 EXPECT_EQ(test, zero);
163 EXPECT_EQ(test |= three, three);
164 EXPECT_EQ(test &= one, one);
165 EXPECT_EQ(test ^= three, two);
166 EXPECT_EQ(test >>= 1, one);
167 EXPECT_EQ(test <<= 1, two);
168
169 EXPECT_EQ(big, -(-big));
170 EXPECT_EQ(two, -((-one) - 1));
171 EXPECT_EQ(kuint128max, -one);
172 EXPECT_EQ(zero, -zero);
173
174 GOOGLE_LOG(INFO) << one;
175 GOOGLE_LOG(INFO) << big_minus_one;
176 }
177
TEST(Int128,PodTests)178 TEST(Int128, PodTests) {
179 uint128_pod pod = { 12345, 67890 };
180 uint128 from_pod(pod);
181 EXPECT_EQ(12345, Uint128High64(from_pod));
182 EXPECT_EQ(67890, Uint128Low64(from_pod));
183
184 uint128 zero(0);
185 uint128_pod zero_pod = {0, 0};
186 uint128 one(1);
187 uint128_pod one_pod = {0, 1};
188 uint128 two(2);
189 uint128_pod two_pod = {0, 2};
190 uint128 three(3);
191 uint128_pod three_pod = {0, 3};
192 uint128 big(1, 0);
193 uint128_pod big_pod = {1, 0};
194
195 EXPECT_EQ(zero, zero_pod);
196 EXPECT_EQ(zero_pod, zero);
197 EXPECT_EQ(zero_pod, zero_pod);
198 EXPECT_EQ(one, one_pod);
199 EXPECT_EQ(one_pod, one);
200 EXPECT_EQ(one_pod, one_pod);
201 EXPECT_EQ(two, two_pod);
202 EXPECT_EQ(two_pod, two);
203 EXPECT_EQ(two_pod, two_pod);
204
205 EXPECT_NE(one, two_pod);
206 EXPECT_NE(one_pod, two);
207 EXPECT_NE(one_pod, two_pod);
208
209 EXPECT_LT(one, two_pod);
210 EXPECT_LT(one_pod, two);
211 EXPECT_LT(one_pod, two_pod);
212 EXPECT_LE(one, one_pod);
213 EXPECT_LE(one_pod, one);
214 EXPECT_LE(one_pod, one_pod);
215 EXPECT_LE(one, two_pod);
216 EXPECT_LE(one_pod, two);
217 EXPECT_LE(one_pod, two_pod);
218
219 EXPECT_GT(two, one_pod);
220 EXPECT_GT(two_pod, one);
221 EXPECT_GT(two_pod, one_pod);
222 EXPECT_GE(two, two_pod);
223 EXPECT_GE(two_pod, two);
224 EXPECT_GE(two_pod, two_pod);
225 EXPECT_GE(two, one_pod);
226 EXPECT_GE(two_pod, one);
227 EXPECT_GE(two_pod, one_pod);
228
229 EXPECT_EQ(three, one | two_pod);
230 EXPECT_EQ(three, one_pod | two);
231 EXPECT_EQ(three, one_pod | two_pod);
232 EXPECT_EQ(one, three & one_pod);
233 EXPECT_EQ(one, three_pod & one);
234 EXPECT_EQ(one, three_pod & one_pod);
235 EXPECT_EQ(two, three ^ one_pod);
236 EXPECT_EQ(two, three_pod ^ one);
237 EXPECT_EQ(two, three_pod ^ one_pod);
238 EXPECT_EQ(two, three & (~one));
239 EXPECT_EQ(three, ~~three);
240
241 EXPECT_EQ(two, two_pod << 0);
242 EXPECT_EQ(two, one_pod << 1);
243 EXPECT_EQ(big, one_pod << 64);
244 EXPECT_EQ(zero, one_pod << 128);
245 EXPECT_EQ(two, two_pod >> 0);
246 EXPECT_EQ(one, two_pod >> 1);
247 EXPECT_EQ(one, big_pod >> 64);
248
249 EXPECT_EQ(one, zero + one_pod);
250 EXPECT_EQ(one, zero_pod + one);
251 EXPECT_EQ(one, zero_pod + one_pod);
252 EXPECT_EQ(one, two - one_pod);
253 EXPECT_EQ(one, two_pod - one);
254 EXPECT_EQ(one, two_pod - one_pod);
255 }
256
TEST(Int128,OperatorAssignReturnRef)257 TEST(Int128, OperatorAssignReturnRef) {
258 uint128 v(1);
259 (v += 4) -= 3;
260 EXPECT_EQ(2, v);
261 }
262
TEST(Int128,Multiply)263 TEST(Int128, Multiply) {
264 uint128 a, b, c;
265
266 // Zero test.
267 a = 0;
268 b = 0;
269 c = a * b;
270 EXPECT_EQ(0, c);
271
272 // Max carries.
273 a = uint128(0) - 1;
274 b = uint128(0) - 1;
275 c = a * b;
276 EXPECT_EQ(1, c);
277
278 // Self-operation with max carries.
279 c = uint128(0) - 1;
280 c *= c;
281 EXPECT_EQ(1, c);
282
283 // 1-bit x 1-bit.
284 for (int i = 0; i < 64; ++i) {
285 for (int j = 0; j < 64; ++j) {
286 a = uint128(1) << i;
287 b = uint128(1) << j;
288 c = a * b;
289 EXPECT_EQ(uint128(1) << (i+j), c);
290 }
291 }
292
293 // Verified with dc.
294 a = uint128(GOOGLE_ULONGLONG(0xffffeeeeddddcccc),
295 GOOGLE_ULONGLONG(0xbbbbaaaa99998888));
296 b = uint128(GOOGLE_ULONGLONG(0x7777666655554444),
297 GOOGLE_ULONGLONG(0x3333222211110000));
298 c = a * b;
299 EXPECT_EQ(uint128(GOOGLE_ULONGLONG(0x530EDA741C71D4C3),
300 GOOGLE_ULONGLONG(0xBF25975319080000)), c);
301 EXPECT_EQ(0, c - b * a);
302 EXPECT_EQ(a*a - b*b, (a+b) * (a-b));
303
304 // Verified with dc.
305 a = uint128(GOOGLE_ULONGLONG(0x0123456789abcdef),
306 GOOGLE_ULONGLONG(0xfedcba9876543210));
307 b = uint128(GOOGLE_ULONGLONG(0x02468ace13579bdf),
308 GOOGLE_ULONGLONG(0xfdb97531eca86420));
309 c = a * b;
310 EXPECT_EQ(uint128(GOOGLE_ULONGLONG(0x97a87f4f261ba3f2),
311 GOOGLE_ULONGLONG(0x342d0bbf48948200)), c);
312 EXPECT_EQ(0, c - b * a);
313 EXPECT_EQ(a*a - b*b, (a+b) * (a-b));
314 }
315
TEST(Int128,AliasTests)316 TEST(Int128, AliasTests) {
317 uint128 x1(1, 2);
318 uint128 x2(2, 4);
319 x1 += x1;
320 EXPECT_EQ(x2, x1);
321
322 uint128 x3(1, static_cast<uint64>(1) << 63);
323 uint128 x4(3, 0);
324 x3 += x3;
325 EXPECT_EQ(x4, x3);
326 }
327
328 #ifdef PROTOBUF_HAS_DEATH_TEST
TEST(Int128,DivideByZeroCheckFails)329 TEST(Int128, DivideByZeroCheckFails) {
330 uint128 a = 0;
331 uint128 b = 0;
332 EXPECT_DEATH(a / b, "Division or mod by zero:");
333 a = 123;
334 EXPECT_DEATH(a / b, "Division or mod by zero:");
335 }
336
TEST(Int128,ModByZeroCheckFails)337 TEST(Int128, ModByZeroCheckFails) {
338 uint128 a = 0;
339 uint128 b = 0;
340 EXPECT_DEATH(a % b, "Division or mod by zero:");
341 a = 123;
342 EXPECT_DEATH(a % b, "Division or mod by zero:");
343 }
344 #endif // PROTOBUF_HAS_DEATH_TEST
345
TEST(Int128,DivideAndMod)346 TEST(Int128, DivideAndMod) {
347 // a := q * b + r
348 uint128 a, b, q, r;
349
350 // Zero test.
351 a = 0;
352 b = 123;
353 q = a / b;
354 r = a % b;
355 EXPECT_EQ(0, q);
356 EXPECT_EQ(0, r);
357
358 a = uint128(GOOGLE_ULONGLONG(0x530eda741c71d4c3),
359 GOOGLE_ULONGLONG(0xbf25975319080000));
360 q = uint128(GOOGLE_ULONGLONG(0x4de2cab081),
361 GOOGLE_ULONGLONG(0x14c34ab4676e4bab));
362 b = uint128(0x1110001);
363 r = uint128(0x3eb455);
364 ASSERT_EQ(a, q * b + r); // Sanity-check.
365
366 uint128 result_q, result_r;
367 result_q = a / b;
368 result_r = a % b;
369 EXPECT_EQ(q, result_q);
370 EXPECT_EQ(r, result_r);
371
372 // Try the other way around.
373 swap(q, b);
374 result_q = a / b;
375 result_r = a % b;
376 EXPECT_EQ(q, result_q);
377 EXPECT_EQ(r, result_r);
378 // Restore.
379 swap(b, q);
380
381 // Dividend < divisor; result should be q:0 r:<dividend>.
382 swap(a, b);
383 result_q = a / b;
384 result_r = a % b;
385 EXPECT_EQ(0, result_q);
386 EXPECT_EQ(a, result_r);
387 // Try the other way around.
388 swap(a, q);
389 result_q = a / b;
390 result_r = a % b;
391 EXPECT_EQ(0, result_q);
392 EXPECT_EQ(a, result_r);
393 // Restore.
394 swap(q, a);
395 swap(b, a);
396
397 // Try a large remainder.
398 b = a / 2 + 1;
399 uint128 expected_r(GOOGLE_ULONGLONG(0x29876d3a0e38ea61),
400 GOOGLE_ULONGLONG(0xdf92cba98c83ffff));
401 // Sanity checks.
402 ASSERT_EQ(a / 2 - 1, expected_r);
403 ASSERT_EQ(a, b + expected_r);
404 result_q = a / b;
405 result_r = a % b;
406 EXPECT_EQ(1, result_q);
407 EXPECT_EQ(expected_r, result_r);
408 }
409
RandomUint64()410 static uint64 RandomUint64() {
411 uint64 v1 = rand();
412 uint64 v2 = rand();
413 uint64 v3 = rand();
414 return v1 * v2 + v3;
415 }
416
TEST(Int128,DivideAndModRandomInputs)417 TEST(Int128, DivideAndModRandomInputs) {
418 const int kNumIters = 1 << 18;
419 for (int i = 0; i < kNumIters; ++i) {
420 const uint128 a(RandomUint64(), RandomUint64());
421 const uint128 b(RandomUint64(), RandomUint64());
422 if (b == 0) {
423 continue; // Avoid a div-by-zero.
424 }
425 const uint128 q = a / b;
426 const uint128 r = a % b;
427 ASSERT_EQ(a, b * q + r);
428 }
429 }
430
431 #ifdef GOOGLE_PROTOBUF_HAS_CONSTEXPR
TEST(Int128,ConstexprTest)432 TEST(Int128, ConstexprTest) {
433 constexpr uint128 zero;
434 constexpr uint128 one = 1;
435 constexpr uint128_pod pod = {2, 3};
436 constexpr uint128 from_pod = pod;
437 constexpr uint128 minus_two = -2;
438 EXPECT_EQ(one, uint128(1));
439 EXPECT_EQ(from_pod, uint128(2, 3));
440 EXPECT_EQ(minus_two, uint128(-1ULL, -2ULL));
441 }
442
TEST(Int128,Traits)443 TEST(Int128, Traits) {
444 EXPECT_TRUE(std::is_trivially_copy_constructible<uint128>::value);
445 EXPECT_TRUE(std::is_trivially_copy_assignable<uint128>::value);
446 EXPECT_TRUE(std::is_trivially_destructible<uint128>::value);
447 }
448 #endif // GOOGLE_PROTOBUF_HAS_CONSTEXPR
449
TEST(Int128,OStream)450 TEST(Int128, OStream) {
451 struct {
452 uint128 val;
453 std::ios_base::fmtflags flags;
454 std::streamsize width;
455 char fill;
456 const char* rep;
457 } cases[] = {
458 // zero with different bases
459 {uint128(0), std::ios::dec, 0, '_', "0"},
460 {uint128(0), std::ios::oct, 0, '_', "0"},
461 {uint128(0), std::ios::hex, 0, '_', "0"},
462 // crossover between lo_ and hi_
463 {uint128(0, -1), std::ios::dec, 0, '_', "18446744073709551615"},
464 {uint128(0, -1), std::ios::oct, 0, '_', "1777777777777777777777"},
465 {uint128(0, -1), std::ios::hex, 0, '_', "ffffffffffffffff"},
466 {uint128(1, 0), std::ios::dec, 0, '_', "18446744073709551616"},
467 {uint128(1, 0), std::ios::oct, 0, '_', "2000000000000000000000"},
468 {uint128(1, 0), std::ios::hex, 0, '_', "10000000000000000"},
469 // just the top bit
470 {uint128(GOOGLE_ULONGLONG(0x8000000000000000), 0), std::ios::dec, 0, '_',
471 "170141183460469231731687303715884105728"},
472 {uint128(GOOGLE_ULONGLONG(0x8000000000000000), 0), std::ios::oct, 0, '_',
473 "2000000000000000000000000000000000000000000"},
474 {uint128(GOOGLE_ULONGLONG(0x8000000000000000), 0), std::ios::hex, 0, '_',
475 "80000000000000000000000000000000"},
476 // maximum uint128 value
477 {uint128(-1, -1), std::ios::dec, 0, '_',
478 "340282366920938463463374607431768211455"},
479 {uint128(-1, -1), std::ios::oct, 0, '_',
480 "3777777777777777777777777777777777777777777"},
481 {uint128(-1, -1), std::ios::hex, 0, '_',
482 "ffffffffffffffffffffffffffffffff"},
483 // uppercase
484 {uint128(-1, -1), std::ios::hex | std::ios::uppercase, 0, '_',
485 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"},
486 // showbase
487 {uint128(1), std::ios::dec | std::ios::showbase, 0, '_', "1"},
488 {uint128(1), std::ios::oct | std::ios::showbase, 0, '_', "01"},
489 {uint128(1), std::ios::hex | std::ios::showbase, 0, '_', "0x1"},
490 // showbase does nothing on zero
491 {uint128(0), std::ios::dec | std::ios::showbase, 0, '_', "0"},
492 {uint128(0), std::ios::oct | std::ios::showbase, 0, '_', "0"},
493 {uint128(0), std::ios::hex | std::ios::showbase, 0, '_', "0"},
494 // showpos does nothing on unsigned types
495 {uint128(1), std::ios::dec | std::ios::showpos, 0, '_', "1"},
496 // padding
497 {uint128(9), std::ios::dec, 6, '_', "_____9"},
498 {uint128(12345), std::ios::dec, 6, '_', "_12345"},
499 // left adjustment
500 {uint128(9), std::ios::dec | std::ios::left, 6, '_', "9_____"},
501 {uint128(12345), std::ios::dec | std::ios::left, 6, '_', "12345_"},
502 };
503 for (size_t i = 0; i < GOOGLE_ARRAYSIZE(cases); ++i) {
504 ostringstream os;
505 os.flags(cases[i].flags);
506 os.width(cases[i].width);
507 os.fill(cases[i].fill);
508 os << cases[i].val;
509 EXPECT_EQ(cases[i].rep, os.str());
510 }
511 }
512 } // namespace protobuf
513 } // namespace google
514