tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

charconv_bigint_test.cc (9073B)

      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 
     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 
    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 
    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 
    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 
    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 
    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