summaryrefslogtreecommitdiff
path: root/absl/strings/internal
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-10-27 14:08:57 -0700
committerGravatar vslashg <gfalcon@google.com>2020-10-27 17:14:47 -0400
commit962b067540f511070b7afa4cda465233b42b560a (patch)
treed2ceea66018cb6d8dab291df01b61c0d22f0755e /absl/strings/internal
parent5bf048b8425cc0a342e4647932de19e25ffd6ad7 (diff)
Export of internal Abseil changes
-- e5b45b15c19e85aaa33430ac2bd45fcc2e52dad5 by Greg Falcon <gfalcon@google.com>: Add extra tests exercising ShiftLeft() at boundary conditions, to guard against logic errors in our memory bounds checking. PiperOrigin-RevId: 339326030 -- cdfde78815ca016a57f90f53d08c3335bd355f30 by Evan Brown <ezb@google.com>: Fix a bug in b-tree erase() and count() in which we weren't accounting for cases where the comparator is heterogeneous and has different equivalence classes for different lookup types. Optimize equal_range to avoid comparisons when possible. PiperOrigin-RevId: 339270230 -- b4aa337c156fa91f74f25c676c679ae146311968 by Derek Mauro <dmauro@google.com>: Fix execution of the cmake build scripts when not on Kokoro PiperOrigin-RevId: 339131253 -- fa3d1f602f711be72fde6b5f29d6341b9b5f8a2c by Derek Mauro <dmauro@google.com>: Update Docker container used for Alpine Linux testing PiperOrigin-RevId: 339074246 GitOrigin-RevId: e5b45b15c19e85aaa33430ac2bd45fcc2e52dad5 Change-Id: I2cc3adc4de3493203c8a944aedee40efa54af0c0
Diffstat (limited to 'absl/strings/internal')
-rw-r--r--absl/strings/internal/charconv_bigint_test.cc55
1 files changed, 55 insertions, 0 deletions
diff --git a/absl/strings/internal/charconv_bigint_test.cc b/absl/strings/internal/charconv_bigint_test.cc
index 363bcb03..a8b99458 100644
--- a/absl/strings/internal/charconv_bigint_test.cc
+++ b/absl/strings/internal/charconv_bigint_test.cc
@@ -69,6 +69,61 @@ TEST(BigUnsigned, ShiftLeft) {
// And we should have fully rotated all bits off by now:
EXPECT_EQ(a, BigUnsigned<84>(0u));
}
+ {
+ // Bit shifting large and small numbers by large and small offsets.
+ // Intended to exercise bounds-checking corner on ShiftLeft() (directly
+ // and under asan).
+
+ // 2**(32*84)-1
+ const BigUnsigned<84> all_bits_one(
+ "1474444211396924248063325089479706787923460402125687709454567433186613"
+ "6228083464060749874845919674257665016359189106695900028098437021384227"
+ "3285029708032466536084583113729486015826557532750465299832071590813090"
+ "2011853039837649252477307070509704043541368002938784757296893793903797"
+ "8180292336310543540677175225040919704702800559606097685920595947397024"
+ "8303316808753252115729411497720357971050627997031988036134171378490368"
+ "6008000778741115399296162550786288457245180872759047016734959330367829"
+ "5235612397427686310674725251378116268607113017720538636924549612987647"
+ "5767411074510311386444547332882472126067840027882117834454260409440463"
+ "9345147252664893456053258463203120637089916304618696601333953616715125"
+ "2115882482473279040772264257431663818610405673876655957323083702713344"
+ "4201105427930770976052393421467136557055");
+ const BigUnsigned<84> zero(0u);
+ const BigUnsigned<84> one(1u);
+ // in bounds shifts
+ for (int i = 1; i < 84*32; ++i) {
+ // shifting all_bits_one to the left should result in a smaller number,
+ // since the high bits rotate off and the low bits are replaced with
+ // zeroes.
+ BigUnsigned<84> big_shifted = all_bits_one;
+ big_shifted.ShiftLeft(i);
+ EXPECT_GT(all_bits_one, big_shifted);
+ // Shifting 1 to the left should instead result in a larger number.
+ BigUnsigned<84> small_shifted = one;
+ small_shifted.ShiftLeft(i);
+ EXPECT_LT(one, small_shifted);
+ }
+ // Shifting by zero or a negative number has no effect
+ for (int no_op_shift : {0, -1, -84 * 32, std::numeric_limits<int>::min()}) {
+ BigUnsigned<84> big_shifted = all_bits_one;
+ big_shifted.ShiftLeft(no_op_shift);
+ EXPECT_EQ(all_bits_one, big_shifted);
+ BigUnsigned<84> small_shifted = one;
+ big_shifted.ShiftLeft(no_op_shift);
+ EXPECT_EQ(one, small_shifted);
+ }
+ // Shifting by an amount greater than the number of bits should result in
+ // zero.
+ for (int out_of_bounds_shift :
+ {84 * 32, 84 * 32 + 1, std::numeric_limits<int>::max()}) {
+ BigUnsigned<84> big_shifted = all_bits_one;
+ big_shifted.ShiftLeft(out_of_bounds_shift);
+ EXPECT_EQ(zero, big_shifted);
+ BigUnsigned<84> small_shifted = one;
+ small_shifted.ShiftLeft(out_of_bounds_shift);
+ EXPECT_EQ(zero, small_shifted);
+ }
+ }
}
TEST(BigUnsigned, MultiplyByUint32) {