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 #include <google/protobuf/port_def.inc>
41
42 namespace google {
43 namespace protobuf {
44
TEST(Int128,AllTests)45 TEST(Int128, AllTests) {
46 uint128 zero(0);
47 uint128 one(1);
48 uint128 one_2arg(0, 1);
49 uint128 two(0, 2);
50 uint128 three(0, 3);
51 uint128 big(2000, 2);
52 uint128 big_minus_one(2000, 1);
53 uint128 bigger(2001, 1);
54 uint128 biggest(kuint128max);
55 uint128 high_low(1, 0);
56 uint128 low_high(0, kuint64max);
57 EXPECT_LT(one, two);
58 EXPECT_GT(two, one);
59 EXPECT_LT(one, big);
60 EXPECT_LT(one, big);
61 EXPECT_EQ(one, one_2arg);
62 EXPECT_NE(one, two);
63 EXPECT_GT(big, one);
64 EXPECT_GE(big, two);
65 EXPECT_GE(big, big_minus_one);
66 EXPECT_GT(big, big_minus_one);
67 EXPECT_LT(big_minus_one, big);
68 EXPECT_LE(big_minus_one, big);
69 EXPECT_NE(big_minus_one, big);
70 EXPECT_LT(big, biggest);
71 EXPECT_LE(big, biggest);
72 EXPECT_GT(biggest, big);
73 EXPECT_GE(biggest, big);
74 EXPECT_EQ(big, ~~big);
75 EXPECT_EQ(one, one | one);
76 EXPECT_EQ(big, big | big);
77 EXPECT_EQ(one, one | zero);
78 EXPECT_EQ(one, one & one);
79 EXPECT_EQ(big, big & big);
80 EXPECT_EQ(zero, one & zero);
81 EXPECT_EQ(zero, big & ~big);
82 EXPECT_EQ(zero, one ^ one);
83 EXPECT_EQ(zero, big ^ big);
84 EXPECT_EQ(one, one ^ zero);
85
86 // Shift operators.
87 EXPECT_EQ(big, big << 0);
88 EXPECT_EQ(big, big >> 0);
89 EXPECT_GT(big << 1, big);
90 EXPECT_LT(big >> 1, big);
91 EXPECT_EQ(big, (big << 10) >> 10);
92 EXPECT_EQ(big, (big >> 1) << 1);
93 EXPECT_EQ(one, (one << 80) >> 80);
94 EXPECT_EQ(zero, (one >> 80) << 80);
95 EXPECT_EQ(zero, big >> 128);
96 EXPECT_EQ(zero, big << 128);
97
98 // Shift assignments.
99 uint128 big_copy = big;
100 EXPECT_EQ(big << 0, big_copy <<= 0);
101 big_copy = big;
102 EXPECT_EQ(big >> 0, big_copy >>= 0);
103 big_copy = big;
104 EXPECT_EQ(big << 1, big_copy <<= 1);
105 big_copy = big;
106 EXPECT_EQ(big >> 1, big_copy >>= 1);
107 big_copy = big;
108 EXPECT_EQ(big << 10, big_copy <<= 10);
109 big_copy = big;
110 EXPECT_EQ(big >> 10, big_copy >>= 10);
111 big_copy = big;
112 EXPECT_EQ(big << 64, big_copy <<= 64);
113 big_copy = big;
114 EXPECT_EQ(big >> 64, big_copy >>= 64);
115 big_copy = big;
116 EXPECT_EQ(big << 73, big_copy <<= 73);
117 big_copy = big;
118 EXPECT_EQ(big >> 73, big_copy >>= 73);
119 big_copy = big;
120 EXPECT_EQ(big << 128, big_copy <<= 128);
121 big_copy = big;
122 EXPECT_EQ(big >> 128, big_copy >>= 128);
123
124 EXPECT_EQ(Uint128High64(biggest), kuint64max);
125 EXPECT_EQ(Uint128Low64(biggest), kuint64max);
126 EXPECT_EQ(zero + one, one);
127 EXPECT_EQ(one + one, two);
128 EXPECT_EQ(big_minus_one + one, big);
129 EXPECT_EQ(one - one, zero);
130 EXPECT_EQ(one - zero, one);
131 EXPECT_EQ(zero - one, biggest);
132 EXPECT_EQ(big - big, zero);
133 EXPECT_EQ(big - one, big_minus_one);
134 EXPECT_EQ(big + kuint64max, bigger);
135 EXPECT_EQ(biggest + 1, zero);
136 EXPECT_EQ(zero - 1, biggest);
137 EXPECT_EQ(high_low - one, low_high);
138 EXPECT_EQ(low_high + one, high_low);
139 EXPECT_EQ(Uint128High64((uint128(1) << 64) - 1), 0);
140 EXPECT_EQ(Uint128Low64((uint128(1) << 64) - 1), kuint64max);
141 EXPECT_TRUE(!!one);
142 EXPECT_TRUE(!!high_low);
143 EXPECT_FALSE(!!zero);
144 EXPECT_FALSE(!one);
145 EXPECT_FALSE(!high_low);
146 EXPECT_TRUE(!zero);
147 EXPECT_TRUE(zero == 0);
148 EXPECT_FALSE(zero != 0);
149 EXPECT_FALSE(one == 0);
150 EXPECT_TRUE(one != 0);
151
152 uint128 test = zero;
153 EXPECT_EQ(++test, one);
154 EXPECT_EQ(test, one);
155 EXPECT_EQ(test++, one);
156 EXPECT_EQ(test, two);
157 EXPECT_EQ(test -= 2, zero);
158 EXPECT_EQ(test, zero);
159 EXPECT_EQ(test += 2, two);
160 EXPECT_EQ(test, two);
161 EXPECT_EQ(--test, one);
162 EXPECT_EQ(test, one);
163 EXPECT_EQ(test--, one);
164 EXPECT_EQ(test, zero);
165 EXPECT_EQ(test |= three, three);
166 EXPECT_EQ(test &= one, one);
167 EXPECT_EQ(test ^= three, two);
168 EXPECT_EQ(test >>= 1, one);
169 EXPECT_EQ(test <<= 1, two);
170
171 EXPECT_EQ(big, -(-big));
172 EXPECT_EQ(two, -((-one) - 1));
173 EXPECT_EQ(kuint128max, -one);
174 EXPECT_EQ(zero, -zero);
175
176 GOOGLE_LOG(INFO) << one;
177 GOOGLE_LOG(INFO) << big_minus_one;
178 }
179
TEST(Int128,PodTests)180 TEST(Int128, PodTests) {
181 uint128_pod pod = { 12345, 67890 };
182 uint128 from_pod(pod);
183 EXPECT_EQ(12345, Uint128High64(from_pod));
184 EXPECT_EQ(67890, Uint128Low64(from_pod));
185
186 uint128 zero(0);
187 uint128_pod zero_pod = {0, 0};
188 uint128 one(1);
189 uint128_pod one_pod = {0, 1};
190 uint128 two(2);
191 uint128_pod two_pod = {0, 2};
192 uint128 three(3);
193 uint128_pod three_pod = {0, 3};
194 uint128 big(1, 0);
195 uint128_pod big_pod = {1, 0};
196
197 EXPECT_EQ(zero, zero_pod);
198 EXPECT_EQ(zero_pod, zero);
199 EXPECT_EQ(zero_pod, zero_pod);
200 EXPECT_EQ(one, one_pod);
201 EXPECT_EQ(one_pod, one);
202 EXPECT_EQ(one_pod, one_pod);
203 EXPECT_EQ(two, two_pod);
204 EXPECT_EQ(two_pod, two);
205 EXPECT_EQ(two_pod, two_pod);
206
207 EXPECT_NE(one, two_pod);
208 EXPECT_NE(one_pod, two);
209 EXPECT_NE(one_pod, two_pod);
210
211 EXPECT_LT(one, two_pod);
212 EXPECT_LT(one_pod, two);
213 EXPECT_LT(one_pod, two_pod);
214 EXPECT_LE(one, one_pod);
215 EXPECT_LE(one_pod, one);
216 EXPECT_LE(one_pod, one_pod);
217 EXPECT_LE(one, two_pod);
218 EXPECT_LE(one_pod, two);
219 EXPECT_LE(one_pod, two_pod);
220
221 EXPECT_GT(two, one_pod);
222 EXPECT_GT(two_pod, one);
223 EXPECT_GT(two_pod, one_pod);
224 EXPECT_GE(two, two_pod);
225 EXPECT_GE(two_pod, two);
226 EXPECT_GE(two_pod, two_pod);
227 EXPECT_GE(two, one_pod);
228 EXPECT_GE(two_pod, one);
229 EXPECT_GE(two_pod, one_pod);
230
231 EXPECT_EQ(three, one | two_pod);
232 EXPECT_EQ(three, one_pod | two);
233 EXPECT_EQ(three, one_pod | two_pod);
234 EXPECT_EQ(one, three & one_pod);
235 EXPECT_EQ(one, three_pod & one);
236 EXPECT_EQ(one, three_pod & one_pod);
237 EXPECT_EQ(two, three ^ one_pod);
238 EXPECT_EQ(two, three_pod ^ one);
239 EXPECT_EQ(two, three_pod ^ one_pod);
240 EXPECT_EQ(two, three & (~one));
241 EXPECT_EQ(three, ~~three);
242
243 EXPECT_EQ(two, two_pod << 0);
244 EXPECT_EQ(two, one_pod << 1);
245 EXPECT_EQ(big, one_pod << 64);
246 EXPECT_EQ(zero, one_pod << 128);
247 EXPECT_EQ(two, two_pod >> 0);
248 EXPECT_EQ(one, two_pod >> 1);
249 EXPECT_EQ(one, big_pod >> 64);
250
251 EXPECT_EQ(one, zero + one_pod);
252 EXPECT_EQ(one, zero_pod + one);
253 EXPECT_EQ(one, zero_pod + one_pod);
254 EXPECT_EQ(one, two - one_pod);
255 EXPECT_EQ(one, two_pod - one);
256 EXPECT_EQ(one, two_pod - one_pod);
257 }
258
TEST(Int128,OperatorAssignReturnRef)259 TEST(Int128, OperatorAssignReturnRef) {
260 uint128 v(1);
261 (v += 4) -= 3;
262 EXPECT_EQ(2, v);
263 }
264
TEST(Int128,Multiply)265 TEST(Int128, Multiply) {
266 uint128 a, b, c;
267
268 // Zero test.
269 a = 0;
270 b = 0;
271 c = a * b;
272 EXPECT_EQ(0, c);
273
274 // Max carries.
275 a = uint128(0) - 1;
276 b = uint128(0) - 1;
277 c = a * b;
278 EXPECT_EQ(1, c);
279
280 // Self-operation with max carries.
281 c = uint128(0) - 1;
282 c *= c;
283 EXPECT_EQ(1, c);
284
285 // 1-bit x 1-bit.
286 for (int i = 0; i < 64; ++i) {
287 for (int j = 0; j < 64; ++j) {
288 a = uint128(1) << i;
289 b = uint128(1) << j;
290 c = a * b;
291 EXPECT_EQ(uint128(1) << (i+j), c);
292 }
293 }
294
295 // Verified with dc.
296 a = uint128(PROTOBUF_ULONGLONG(0xffffeeeeddddcccc),
297 PROTOBUF_ULONGLONG(0xbbbbaaaa99998888));
298 b = uint128(PROTOBUF_ULONGLONG(0x7777666655554444),
299 PROTOBUF_ULONGLONG(0x3333222211110000));
300 c = a * b;
301 EXPECT_EQ(uint128(PROTOBUF_ULONGLONG(0x530EDA741C71D4C3),
302 PROTOBUF_ULONGLONG(0xBF25975319080000)),
303 c);
304 EXPECT_EQ(0, c - b * a);
305 EXPECT_EQ(a * a - b * b, (a + b) * (a - b));
306
307 // Verified with dc.
308 a = uint128(PROTOBUF_ULONGLONG(0x0123456789abcdef),
309 PROTOBUF_ULONGLONG(0xfedcba9876543210));
310 b = uint128(PROTOBUF_ULONGLONG(0x02468ace13579bdf),
311 PROTOBUF_ULONGLONG(0xfdb97531eca86420));
312 c = a * b;
313 EXPECT_EQ(uint128(PROTOBUF_ULONGLONG(0x97a87f4f261ba3f2),
314 PROTOBUF_ULONGLONG(0x342d0bbf48948200)),
315 c);
316 EXPECT_EQ(0, c - b * a);
317 EXPECT_EQ(a*a - b*b, (a+b) * (a-b));
318 }
319
TEST(Int128,AliasTests)320 TEST(Int128, AliasTests) {
321 uint128 x1(1, 2);
322 uint128 x2(2, 4);
323 x1 += x1;
324 EXPECT_EQ(x2, x1);
325
326 uint128 x3(1, static_cast<uint64>(1) << 63);
327 uint128 x4(3, 0);
328 x3 += x3;
329 EXPECT_EQ(x4, x3);
330 }
331
332 #ifdef PROTOBUF_HAS_DEATH_TEST
TEST(Int128,DivideByZeroCheckFails)333 TEST(Int128, DivideByZeroCheckFails) {
334 uint128 a = 0;
335 uint128 b = 0;
336 EXPECT_DEATH(a / b, "Division or mod by zero:");
337 a = 123;
338 EXPECT_DEATH(a / b, "Division or mod by zero:");
339 }
340
TEST(Int128,ModByZeroCheckFails)341 TEST(Int128, ModByZeroCheckFails) {
342 uint128 a = 0;
343 uint128 b = 0;
344 EXPECT_DEATH(a % b, "Division or mod by zero:");
345 a = 123;
346 EXPECT_DEATH(a % b, "Division or mod by zero:");
347 }
348 #endif // PROTOBUF_HAS_DEATH_TEST
349
TEST(Int128,DivideAndMod)350 TEST(Int128, DivideAndMod) {
351 // a := q * b + r
352 uint128 a, b, q, r;
353
354 // Zero test.
355 a = 0;
356 b = 123;
357 q = a / b;
358 r = a % b;
359 EXPECT_EQ(0, q);
360 EXPECT_EQ(0, r);
361
362 a = uint128(PROTOBUF_ULONGLONG(0x530eda741c71d4c3),
363 PROTOBUF_ULONGLONG(0xbf25975319080000));
364 q = uint128(PROTOBUF_ULONGLONG(0x4de2cab081),
365 PROTOBUF_ULONGLONG(0x14c34ab4676e4bab));
366 b = uint128(0x1110001);
367 r = uint128(0x3eb455);
368 ASSERT_EQ(a, q * b + r); // Sanity-check.
369
370 uint128 result_q, result_r;
371 result_q = a / b;
372 result_r = a % b;
373 EXPECT_EQ(q, result_q);
374 EXPECT_EQ(r, result_r);
375
376 // Try the other way around.
377 std::swap(q, b);
378 result_q = a / b;
379 result_r = a % b;
380 EXPECT_EQ(q, result_q);
381 EXPECT_EQ(r, result_r);
382 // Restore.
383 std::swap(b, q);
384
385 // Dividend < divisor; result should be q:0 r:<dividend>.
386 std::swap(a, b);
387 result_q = a / b;
388 result_r = a % b;
389 EXPECT_EQ(0, result_q);
390 EXPECT_EQ(a, result_r);
391 // Try the other way around.
392 std::swap(a, q);
393 result_q = a / b;
394 result_r = a % b;
395 EXPECT_EQ(0, result_q);
396 EXPECT_EQ(a, result_r);
397 // Restore.
398 std::swap(q, a);
399 std::swap(b, a);
400
401 // Try a large remainder.
402 b = a / 2 + 1;
403 uint128 expected_r(PROTOBUF_ULONGLONG(0x29876d3a0e38ea61),
404 PROTOBUF_ULONGLONG(0xdf92cba98c83ffff));
405 // Sanity checks.
406 ASSERT_EQ(a / 2 - 1, expected_r);
407 ASSERT_EQ(a, b + expected_r);
408 result_q = a / b;
409 result_r = a % b;
410 EXPECT_EQ(1, result_q);
411 EXPECT_EQ(expected_r, result_r);
412 }
413
RandomUint64()414 static uint64 RandomUint64() {
415 uint64 v1 = rand();
416 uint64 v2 = rand();
417 uint64 v3 = rand();
418 return v1 * v2 + v3;
419 }
420
TEST(Int128,DivideAndModRandomInputs)421 TEST(Int128, DivideAndModRandomInputs) {
422 const int kNumIters = 1 << 18;
423 for (int i = 0; i < kNumIters; ++i) {
424 const uint128 a(RandomUint64(), RandomUint64());
425 const uint128 b(RandomUint64(), RandomUint64());
426 if (b == 0) {
427 continue; // Avoid a div-by-zero.
428 }
429 const uint128 q = a / b;
430 const uint128 r = a % b;
431 ASSERT_EQ(a, b * q + r);
432 }
433 }
434
435 #ifdef GOOGLE_PROTOBUF_HAS_CONSTEXPR
TEST(Int128,ConstexprTest)436 TEST(Int128, ConstexprTest) {
437 constexpr uint128 zero;
438 constexpr uint128 one = 1;
439 constexpr uint128_pod pod = {2, 3};
440 constexpr uint128 from_pod = pod;
441 constexpr uint128 minus_two = -2;
442 EXPECT_EQ(one, uint128(1));
443 EXPECT_EQ(from_pod, uint128(2, 3));
444 EXPECT_EQ(minus_two, uint128(-1ULL, -2ULL));
445 }
446
TEST(Int128,Traits)447 TEST(Int128, Traits) {
448 EXPECT_TRUE(std::is_trivially_copy_constructible<uint128>::value);
449 EXPECT_TRUE(std::is_trivially_copy_assignable<uint128>::value);
450 EXPECT_TRUE(std::is_trivially_destructible<uint128>::value);
451 }
452 #endif // GOOGLE_PROTOBUF_HAS_CONSTEXPR
453
TEST(Int128,OStream)454 TEST(Int128, OStream) {
455 struct {
456 uint128 val;
457 std::ios_base::fmtflags flags;
458 std::streamsize width;
459 char fill;
460 const char* rep;
461 } cases[] = {
462 // zero with different bases
463 {uint128(0), std::ios::dec, 0, '_', "0"},
464 {uint128(0), std::ios::oct, 0, '_', "0"},
465 {uint128(0), std::ios::hex, 0, '_', "0"},
466 // crossover between lo_ and hi_
467 {uint128(0, -1), std::ios::dec, 0, '_', "18446744073709551615"},
468 {uint128(0, -1), std::ios::oct, 0, '_', "1777777777777777777777"},
469 {uint128(0, -1), std::ios::hex, 0, '_', "ffffffffffffffff"},
470 {uint128(1, 0), std::ios::dec, 0, '_', "18446744073709551616"},
471 {uint128(1, 0), std::ios::oct, 0, '_', "2000000000000000000000"},
472 {uint128(1, 0), std::ios::hex, 0, '_', "10000000000000000"},
473 // just the top bit
474 {uint128(PROTOBUF_ULONGLONG(0x8000000000000000), 0), std::ios::dec, 0,
475 '_', "170141183460469231731687303715884105728"},
476 {uint128(PROTOBUF_ULONGLONG(0x8000000000000000), 0), std::ios::oct, 0,
477 '_', "2000000000000000000000000000000000000000000"},
478 {uint128(PROTOBUF_ULONGLONG(0x8000000000000000), 0), std::ios::hex, 0,
479 '_', "80000000000000000000000000000000"},
480 // maximum uint128 value
481 {uint128(-1, -1), std::ios::dec, 0, '_',
482 "340282366920938463463374607431768211455"},
483 {uint128(-1, -1), std::ios::oct, 0, '_',
484 "3777777777777777777777777777777777777777777"},
485 {uint128(-1, -1), std::ios::hex, 0, '_',
486 "ffffffffffffffffffffffffffffffff"},
487 // uppercase
488 {uint128(-1, -1), std::ios::hex | std::ios::uppercase, 0, '_',
489 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"},
490 // showbase
491 {uint128(1), std::ios::dec | std::ios::showbase, 0, '_', "1"},
492 {uint128(1), std::ios::oct | std::ios::showbase, 0, '_', "01"},
493 {uint128(1), std::ios::hex | std::ios::showbase, 0, '_', "0x1"},
494 // showbase does nothing on zero
495 {uint128(0), std::ios::dec | std::ios::showbase, 0, '_', "0"},
496 {uint128(0), std::ios::oct | std::ios::showbase, 0, '_', "0"},
497 {uint128(0), std::ios::hex | std::ios::showbase, 0, '_', "0"},
498 // showpos does nothing on unsigned types
499 {uint128(1), std::ios::dec | std::ios::showpos, 0, '_', "1"},
500 // padding
501 {uint128(9), std::ios::dec, 6, '_', "_____9"},
502 {uint128(12345), std::ios::dec, 6, '_', "_12345"},
503 // left adjustment
504 {uint128(9), std::ios::dec | std::ios::left, 6, '_', "9_____"},
505 {uint128(12345), std::ios::dec | std::ios::left, 6, '_', "12345_"},
506 };
507 for (size_t i = 0; i < GOOGLE_ARRAYSIZE(cases); ++i) {
508 std::ostringstream os;
509 os.flags(cases[i].flags);
510 os.width(cases[i].width);
511 os.fill(cases[i].fill);
512 os << cases[i].val;
513 EXPECT_EQ(cases[i].rep, os.str());
514 }
515 }
516 } // namespace protobuf
517 } // namespace google
518