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 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 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 257 TEST(Int128, OperatorAssignReturnRef) { 258 uint128 v(1); 259 (v += 4) -= 3; 260 EXPECT_EQ(2, v); 261 } 262 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 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 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 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 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 410 static uint64 RandomUint64() { 411 uint64 v1 = rand(); 412 uint64 v2 = rand(); 413 uint64 v3 = rand(); 414 return v1 * v2 + v3; 415 } 416 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 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 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 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
