From af6976a907b0d2a9fadbb14d7258bab44f075364 Mon Sep 17 00:00:00 2001 From: zxu Date: Sat, 27 Jan 2018 17:53:27 -0500 Subject: normalize and port the rest of Firebase/Port code (#713) * normalize bits * normalize ordered_code --- .../test/firebase/firestore/util/CMakeLists.txt | 2 + .../core/test/firebase/firestore/util/bits_test.cc | 142 ++++++ .../firebase/firestore/util/ordered_code_test.cc | 508 +++++++++++++++++++++ .../firebase/firestore/util/secure_random_test.cc | 25 + 4 files changed, 677 insertions(+) create mode 100644 Firestore/core/test/firebase/firestore/util/bits_test.cc create mode 100644 Firestore/core/test/firebase/firestore/util/ordered_code_test.cc (limited to 'Firestore/core/test/firebase/firestore/util') diff --git a/Firestore/core/test/firebase/firestore/util/CMakeLists.txt b/Firestore/core/test/firebase/firestore/util/CMakeLists.txt index 13a2e46..eb5a898 100644 --- a/Firestore/core/test/firebase/firestore/util/CMakeLists.txt +++ b/Firestore/core/test/firebase/firestore/util/CMakeLists.txt @@ -36,7 +36,9 @@ cc_test( firebase_firestore_util_test SOURCES autoid_test.cc + bits_test.cc comparison_test.cc + ordered_code_test.cc string_printf_test.cc string_util_test.cc DEPENDS diff --git a/Firestore/core/test/firebase/firestore/util/bits_test.cc b/Firestore/core/test/firebase/firestore/util/bits_test.cc new file mode 100644 index 0000000..cb0976b --- /dev/null +++ b/Firestore/core/test/firebase/firestore/util/bits_test.cc @@ -0,0 +1,142 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Firestore/core/src/firebase/firestore/util/bits.h" + +#include +#include +#include + +#include "Firestore/core/src/firebase/firestore/util/secure_random.h" +#include "gtest/gtest.h" + +namespace firebase { +namespace firestore { +namespace util { + +const int kNumIterations = 10000; // "Number of test iterations to run. + +class BitsTest : public testing::Test { + protected: + SecureRandom random_; +}; + +TEST_F(BitsTest, Log2EdgeCases) { + std::cout << "TestLog2EdgeCases" << std::endl; + + EXPECT_EQ(-1, Bits::Log2Floor(0)); + EXPECT_EQ(-1, Bits::Log2Floor64(0)); + + for (int i = 0; i < 32; i++) { + uint32_t n = 1U << i; + EXPECT_EQ(i, Bits::Log2Floor(n)); + EXPECT_EQ(i, Bits::Log2FloorNonZero(n)); + if (n > 2) { + EXPECT_EQ(i - 1, Bits::Log2Floor(n - 1)); + EXPECT_EQ(i, Bits::Log2Floor(n + 1)); + EXPECT_EQ(i - 1, Bits::Log2FloorNonZero(n - 1)); + EXPECT_EQ(i, Bits::Log2FloorNonZero(n + 1)); + } + } + + for (int i = 0; i < 64; i++) { + uint64_t n = 1ULL << i; + EXPECT_EQ(i, Bits::Log2Floor64(n)); + EXPECT_EQ(i, Bits::Log2FloorNonZero64(n)); + if (n > 2) { + EXPECT_EQ(i - 1, Bits::Log2Floor64(n - 1)); + EXPECT_EQ(i, Bits::Log2Floor64(n + 1)); + EXPECT_EQ(i - 1, Bits::Log2FloorNonZero64(n - 1)); + EXPECT_EQ(i, Bits::Log2FloorNonZero64(n + 1)); + } + } +} + +TEST_F(BitsTest, Log2Random) { + std::cout << "TestLog2Random" << std::endl; + + for (int i = 0; i < kNumIterations; i++) { + int maxbit = -1; + uint32_t n = 0; + while (!random_.OneIn(32u)) { + int bit = static_cast(random_.Uniform(32u)); + n |= (1U << bit); + maxbit = std::max(bit, maxbit); + } + EXPECT_EQ(maxbit, Bits::Log2Floor(n)); + if (n != 0) { + EXPECT_EQ(maxbit, Bits::Log2FloorNonZero(n)); + } + } +} + +TEST_F(BitsTest, Log2Random64) { + std::cout << "TestLog2Random64" << std::endl; + + for (int i = 0; i < kNumIterations; i++) { + int maxbit = -1; + uint64_t n = 0; + while (!random_.OneIn(64u)) { + int bit = static_cast(random_.Uniform(64u)); + n |= (1ULL << bit); + maxbit = std::max(bit, maxbit); + } + EXPECT_EQ(maxbit, Bits::Log2Floor64(n)); + if (n != 0) { + EXPECT_EQ(maxbit, Bits::Log2FloorNonZero64(n)); + } + } +} + +TEST(Bits, Port32) { + for (int shift = 0; shift < 32; shift++) { + for (uint32_t delta = 0; delta <= 2; delta++) { + const uint32_t v = (static_cast(1) << shift) - 1 + delta; + EXPECT_EQ(Bits::Log2Floor_Portable(v), Bits::Log2Floor(v)) << v; + if (v != 0) { + EXPECT_EQ(Bits::Log2FloorNonZero_Portable(v), Bits::Log2FloorNonZero(v)) + << v; + } + } + } + static const uint32_t M32 = std::numeric_limits::max(); + EXPECT_EQ(Bits::Log2Floor_Portable(M32), Bits::Log2Floor(M32)) << M32; + EXPECT_EQ(Bits::Log2FloorNonZero_Portable(M32), Bits::Log2FloorNonZero(M32)) + << M32; +} + +TEST(Bits, Port64) { + for (int shift = 0; shift < 64; shift++) { + for (uint64_t delta = 0; delta <= 2; delta++) { + const uint64_t v = (static_cast(1) << shift) - 1 + delta; + EXPECT_EQ(Bits::Log2Floor64_Portable(v), Bits::Log2Floor64(v)) << v; + if (v != 0) { + EXPECT_EQ(Bits::Log2FloorNonZero64_Portable(v), + Bits::Log2FloorNonZero64(v)) + << v; + } + } + } + static const uint64_t M64 = std::numeric_limits::max(); + EXPECT_EQ(Bits::Log2Floor64_Portable(M64), Bits::Log2Floor64(M64)) << M64; + EXPECT_EQ(Bits::Log2FloorNonZero64_Portable(M64), + Bits::Log2FloorNonZero64(M64)) + << M64; +} + +} // namespace util +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/test/firebase/firestore/util/ordered_code_test.cc b/Firestore/core/test/firebase/firestore/util/ordered_code_test.cc new file mode 100644 index 0000000..fd2ce83 --- /dev/null +++ b/Firestore/core/test/firebase/firestore/util/ordered_code_test.cc @@ -0,0 +1,508 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Firestore/core/src/firebase/firestore/util/ordered_code.h" + +#include +#include + +#include "Firestore/core/src/firebase/firestore/util/secure_random.h" +#include "gtest/gtest.h" + +namespace firebase { +namespace firestore { +namespace util { + +static std::string RandomString(SecureRandom* rnd, int len) { + std::string x; + for (int i = 0; i < len; i++) { + x += static_cast(rnd->Uniform(256)); + } + return x; +} + +// --------------------------------------------------------------------- +// Utility template functions (they help templatize the tests below) + +// Read/WriteIncreasing are defined for string, uint64_t, int64_t below. +template +static void OCWriteIncreasing(std::string* dest, const T& val); +template +static bool OCReadIncreasing(absl::string_view* src, T* result); + +// Read/WriteIncreasing +template <> +void OCWriteIncreasing(std::string* dest, const std::string& val) { + OrderedCode::WriteString(dest, val); +} +template <> +bool OCReadIncreasing(absl::string_view* src, + std::string* result) { + return OrderedCode::ReadString(src, result); +} + +// Read/WriteIncreasing +template <> +void OCWriteIncreasing(std::string* dest, const uint64_t& val) { + OrderedCode::WriteNumIncreasing(dest, val); +} +template <> +bool OCReadIncreasing(absl::string_view* src, uint64_t* result) { + return OrderedCode::ReadNumIncreasing(src, result); +} + +enum Direction { INCREASING = 0 }; + +// Read/WriteIncreasing +template <> +void OCWriteIncreasing(std::string* dest, const int64_t& val) { + OrderedCode::WriteSignedNumIncreasing(dest, val); +} +template <> +bool OCReadIncreasing(absl::string_view* src, int64_t* result) { + return OrderedCode::ReadSignedNumIncreasing(src, result); +} + +template +std::string OCWrite(T val, Direction direction) { + EXPECT_EQ(INCREASING, direction); // DECREASING never implemented. + std::string result; + OCWriteIncreasing(&result, val); + return result; +} + +template +void OCWriteToString(std::string* result, T val, Direction direction) { + EXPECT_EQ(INCREASING, direction); // DECREASING never implemented. + OCWriteIncreasing(result, val); +} + +template +bool OCRead(absl::string_view* s, T* val, Direction direction) { + EXPECT_EQ(INCREASING, direction); // DECREASING never implemented. + return OCReadIncreasing(s, val); +} + +// --------------------------------------------------------------------- +// Numbers + +template +static T TestRead(Direction d, const std::string& a) { + // gracefully reject any proper prefix of an encoding + for (size_t i = 0; i < a.size() - 1; ++i) { + absl::string_view s(a.data(), i); + EXPECT_TRUE(!OCRead(&s, NULL, d)); + EXPECT_EQ(s, a.substr(0, i)); + } + + absl::string_view s(a); + T v; + EXPECT_TRUE(OCRead(&s, &v, d)); + EXPECT_TRUE(s.empty()); + return v; +} + +template +static void TestWriteRead(Direction d, T expected) { + EXPECT_EQ(expected, TestRead(d, OCWrite(expected, d))); +} + +// Verifies that the second Write* call appends a non-empty std::string to its +// output. +template +static void TestWriteAppends(Direction d, T first, U second) { + std::string encoded; + OCWriteToString(&encoded, first, d); + std::string encoded_first_only = encoded; + OCWriteToString(&encoded, second, d); + EXPECT_NE(encoded, encoded_first_only); + EXPECT_EQ(absl::string_view(encoded).substr(0, encoded_first_only.length()), + encoded_first_only); +} + +template +static void TestNumbers(T multiplier) { + for (int j = 0; j < 1; ++j) { + const Direction d = static_cast(j); + + // first test powers of 2 (and nearby numbers) + for (T x = std::numeric_limits().max(); x != 0; x /= 2) { + TestWriteRead(d, multiplier * (x - 1)); + TestWriteRead(d, multiplier * x); + if (x != std::numeric_limits::max()) { + TestWriteRead(d, multiplier * (x + 1)); + } else if (multiplier < 0 && static_cast(multiplier) == -1) { + TestWriteRead(d, -x - 1); + } + } + + SecureRandom rnd; // Generate 32bit pseudo-random integer. + for (int bits = 1; bits <= std::numeric_limits().digits; ++bits) { + // test random non-negative numbers with given number of significant bits + const uint64_t mask = (~0ULL) >> (64 - bits); + for (int i = 0; i < 1000; i++) { + T x = static_cast((static_cast(rnd()) << 32 | + static_cast(rnd())) & + mask); + TestWriteRead(d, multiplier * x); + T y = static_cast((static_cast(rnd()) << 32 | + static_cast(rnd())) & + mask); + TestWriteAppends(d, multiplier * x, multiplier * y); + } + } + } +} + +// Return true iff 'a' is "before" 'b' according to 'direction' +static bool CompareStrings(const std::string& a, + const std::string& b, + Direction d) { + return (INCREASING == d) ? (a < b) : (b < a); +} + +template +static void TestNumberOrdering() { + const Direction d = INCREASING; + + // first the negative numbers (if T is signed, otherwise no-op) + std::string laststr = OCWrite(std::numeric_limits().min(), d); + for (T num = std::numeric_limits().min() / 2; num != 0; num /= 2) { + std::string strminus1 = OCWrite(num - 1, d); + std::string str = OCWrite(num, d); + std::string strplus1 = OCWrite(num + 1, d); + + EXPECT_TRUE(CompareStrings(strminus1, str, d)); + EXPECT_TRUE(CompareStrings(str, strplus1, d)); + + // Compare 'str' with 'laststr'. When we approach 0, 'laststr' is + // not necessarily before 'strminus1'. + EXPECT_TRUE(CompareStrings(laststr, str, d)); + laststr = str; + } + + // then the positive numbers + laststr = OCWrite(0, d); + T num = 1; + while (num < std::numeric_limits().max() / 2) { + num *= 2; + std::string strminus1 = OCWrite(num - 1, d); + std::string str = OCWrite(num, d); + std::string strplus1 = OCWrite(num + 1, d); + + EXPECT_TRUE(CompareStrings(strminus1, str, d)); + EXPECT_TRUE(CompareStrings(str, strplus1, d)); + + // Compare 'str' with 'laststr'. + EXPECT_TRUE(CompareStrings(laststr, str, d)); + laststr = str; + } +} + +// Helper routine for testing TEST_SkipToNextSpecialByte +static size_t FindSpecial(const std::string& x) { + const char* p = x.data(); + const char* limit = p + x.size(); + const char* result = OrderedCode::TEST_SkipToNextSpecialByte(p, limit); + return static_cast(result - p); +} + +TEST(OrderedCode, SkipToNextSpecialByte) { + for (size_t len = 0; len < 256; len++) { + SecureRandom rnd; + std::string x; + while (x.size() < len) { + char c = 1 + static_cast(rnd.Uniform(254)); + ASSERT_NE(c, 0); + ASSERT_NE(c, 255); + x += c; // No 0 bytes, no 255 bytes + } + EXPECT_EQ(FindSpecial(x), x.size()); + for (size_t special_pos = 0; special_pos < len; special_pos++) { + for (int special_test = 0; special_test < 2; special_test++) { + const char special_byte = (special_test == 0) ? 0 : '\xff'; + std::string y = x; + y[special_pos] = special_byte; + EXPECT_EQ(FindSpecial(y), special_pos); + if (special_pos < 16) { + // Add some special bytes after the one at special_pos to make sure + // we still return the earliest special byte in the string + for (size_t rest = special_pos + 1; rest < len; rest++) { + if (rnd.OneIn(3)) { + y[rest] = rnd.OneIn(2) ? 0 : '\xff'; + EXPECT_EQ(FindSpecial(y), special_pos); + } + } + } + } + } + } +} + +TEST(OrderedCode, ExhaustiveFindSpecial) { + char buf[16]; + char* limit = buf + sizeof(buf); + int count = 0; + for (int start_offset = 0; start_offset <= 5; start_offset += 5) { + // We test exhaustively with all combinations of 3 bytes starting + // at offset 0 and offset 5 (so as to test with the bytes at both + // ends of a 64-bit word). + for (char& c : buf) { + c = 'a'; // Not a special byte + } + for (int b0 = 0; b0 < 256; b0++) { + for (int b1 = 0; b1 < 256; b1++) { + for (int b2 = 0; b2 < 256; b2++) { + buf[start_offset + 0] = static_cast(b0); + buf[start_offset + 1] = static_cast(b1); + buf[start_offset + 2] = static_cast(b2); + char* expected; + if (b0 == 0 || b0 == 255) { + expected = &buf[start_offset]; + } else if (b1 == 0 || b1 == 255) { + expected = &buf[start_offset + 1]; + } else if (b2 == 0 || b2 == 255) { + expected = &buf[start_offset + 2]; + } else { + expected = limit; + } + count++; + EXPECT_EQ(expected, + OrderedCode::TEST_SkipToNextSpecialByte(buf, limit)); + } + } + } + } + EXPECT_EQ(count, 256 * 256 * 256 * 2); +} + +TEST(OrderedCodeUint64, EncodeDecode) { + TestNumbers(1); +} + +TEST(OrderedCodeUint64, Ordering) { + TestNumberOrdering(); +} + +TEST(OrderedCodeInt64, EncodeDecode) { + TestNumbers(1); + TestNumbers(-1); +} + +TEST(OrderedCodeInt64, Ordering) { + TestNumberOrdering(); +} + +// Returns the bitwise complement of s. +static inline std::string StrNot(const std::string& s) { + std::string result; + for (const char c : s) result.push_back(~c); + return result; +} + +template +static void TestInvalidEncoding(Direction d, const std::string& s) { + absl::string_view p(s); + EXPECT_FALSE(OCRead(&p, static_cast(NULL), d)); + EXPECT_EQ(s, p); +} + +TEST(OrderedCodeInvalidEncodingsTest, Overflow) { + // 1U << 64, increasing + const std::string k2xx64U = "\x09\x01" + std::string(8, 0); + TestInvalidEncoding(INCREASING, k2xx64U); + + // 1 << 63 and ~(1 << 63), increasing + const std::string k2xx63 = "\xff\xc0\x80" + std::string(7, 0); + TestInvalidEncoding(INCREASING, k2xx63); + TestInvalidEncoding(INCREASING, StrNot(k2xx63)); +} + +TEST(OrderedCodeInvalidEncodingsTest, NonCanonical) { + // Test DCHECK failures of "ambiguous"/"non-canonical" encodings. + // These are non-minimal (but otherwise "valid") encodings that + // differ from the minimal encoding chosen by OrderedCode::WriteXXX + // and thus should be avoided to not mess up the string ordering of + // encodings. + + SecureRandom rnd; + + for (int n = 2; n <= 9; ++n) { + // The zero in non_minimal[1] is "redundant". + std::string non_minimal = + std::string(1, n - 1) + std::string(1, 0) + RandomString(&rnd, n - 2); + EXPECT_EQ(static_cast(n), non_minimal.length()); + + EXPECT_NE(OCWrite(0, INCREASING), non_minimal); + +#if defined(NDEBUG) + TestRead(INCREASING, non_minimal); +#else // defined(NDEBUG) + absl::string_view s(non_minimal); + EXPECT_ANY_THROW(OrderedCode::ReadNumIncreasing(&s, NULL)); +#endif // defined(NDEBUG) + } + + for (int n = 2; n <= 10; ++n) { + // Header with 1 sign bit and n-1 size bits. + std::string header = + std::string(n / 8, 0xff) + std::string(1, 0xff << (8 - (n % 8))); + // There are more than 7 zero bits between header bits and "payload". + std::string non_minimal = + header + + std::string(1, + static_cast(rnd.Uniform(256)) & ~*header.rbegin()) + + RandomString(&rnd, n - static_cast(header.length()) - 1); + EXPECT_EQ(static_cast(n), non_minimal.length()); + + EXPECT_NE(OCWrite(0, INCREASING), non_minimal); + +#if defined(NDEBUG) + TestRead(INCREASING, non_minimal); +#else // defined(NDEBUG) + absl::string_view s(non_minimal); + EXPECT_ANY_THROW(OrderedCode::ReadSignedNumIncreasing(&s, NULL)); + s = non_minimal; +#endif // defined(NDEBUG) + } +} + +// --------------------------------------------------------------------- +// Strings + +TEST(OrderedCodeString, Infinity) { + const std::string value("\xff\xff foo"); + bool is_inf; + std::string encoding, parsed; + absl::string_view s; + + // Check encoding/decoding of "infinity" for ascending order + encoding.clear(); + OrderedCode::WriteInfinity(&encoding); + encoding.push_back('a'); + s = encoding; + EXPECT_TRUE(OrderedCode::ReadInfinity(&s)); + EXPECT_EQ(1u, s.size()); + s = encoding; + is_inf = false; + EXPECT_TRUE(OrderedCode::ReadStringOrInfinity(&s, NULL, &is_inf)); + EXPECT_EQ(1u, s.size()); + EXPECT_TRUE(is_inf); + + // Check ReadStringOrInfinity() can parse ordinary strings + encoding.clear(); + OrderedCode::WriteString(&encoding, value); + encoding.push_back('a'); + s = encoding; + is_inf = false; + parsed.clear(); + EXPECT_TRUE(OrderedCode::ReadStringOrInfinity(&s, &parsed, &is_inf)); + EXPECT_EQ(1u, s.size()); + EXPECT_FALSE(is_inf); + EXPECT_EQ(value, parsed); +} + +TEST(OrderedCodeString, EncodeDecode) { + SecureRandom rnd; + for (int i = 0; i < 1; ++i) { + const Direction d = static_cast(i); + + for (int len = 0; len < 256; len++) { + const std::string a = RandomString(&rnd, len); + TestWriteRead(d, a); + for (int len2 = 0; len2 < 64; len2++) { + const std::string b = RandomString(&rnd, len2); + + TestWriteAppends(d, a, b); + + std::string out; + OCWriteToString(&out, a, d); + OCWriteToString(&out, b, d); + + std::string a2, b2, dummy; + absl::string_view s = out; + absl::string_view s2 = out; + EXPECT_TRUE(OCRead(&s, &a2, d)); + EXPECT_TRUE(OCRead(&s2, NULL, d)); + EXPECT_EQ(s, s2); + + EXPECT_TRUE(OCRead(&s, &b2, d)); + EXPECT_TRUE(OCRead(&s2, NULL, d)); + EXPECT_EQ(s, s2); + + EXPECT_TRUE(!OCRead(&s, &dummy, d)); + EXPECT_TRUE(!OCRead(&s2, NULL, d)); + EXPECT_EQ(a, a2); + EXPECT_EQ(b, b2); + EXPECT_TRUE(s.empty()); + EXPECT_TRUE(s2.empty()); + } + } + } +} + +// 'str' is a static C-style string that may contain '\0' +#define STATIC_STR(str) absl::string_view((str), sizeof(str) - 1) + +static std::string EncodeStringIncreasing(absl::string_view value) { + std::string encoded; + OrderedCode::WriteString(&encoded, value); + return encoded; +} + +TEST(OrderedCodeString, Increasing) { + // Here are a series of strings in non-decreasing order, including + // consecutive strings such that the second one is equal to, a proper + // prefix of, or has the same length as the first one. Most also contain + // the special escaping characters '\x00' and '\xff'. + EXPECT_EQ(EncodeStringIncreasing(STATIC_STR("")), + EncodeStringIncreasing(STATIC_STR(""))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("")), + EncodeStringIncreasing(STATIC_STR("\x00"))); + + EXPECT_EQ(EncodeStringIncreasing(STATIC_STR("\x00")), + EncodeStringIncreasing(STATIC_STR("\x00"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\x00")), + EncodeStringIncreasing(STATIC_STR("\x01"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\x01")), + EncodeStringIncreasing(STATIC_STR("a"))); + + EXPECT_EQ(EncodeStringIncreasing(STATIC_STR("a")), + EncodeStringIncreasing(STATIC_STR("a"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("a")), + EncodeStringIncreasing(STATIC_STR("aa"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("aa")), + EncodeStringIncreasing(STATIC_STR("\xff"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\xff")), + EncodeStringIncreasing(STATIC_STR("\xff\x00"))); + + ASSERT_LT(EncodeStringIncreasing(STATIC_STR("\xff\x00")), + EncodeStringIncreasing(STATIC_STR("\xff\x01"))); + + std::string infinity; + OrderedCode::WriteInfinity(&infinity); + ASSERT_LT(EncodeStringIncreasing(std::string(1 << 20, '\xff')), infinity); +} + +} // namespace util +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/test/firebase/firestore/util/secure_random_test.cc b/Firestore/core/test/firebase/firestore/util/secure_random_test.cc index ee2ae00..0b7a51b 100644 --- a/Firestore/core/test/firebase/firestore/util/secure_random_test.cc +++ b/Firestore/core/test/firebase/firestore/util/secure_random_test.cc @@ -30,3 +30,28 @@ TEST(SecureRandomTest, ResultsAreBounded) { EXPECT_LE(value, rng.max()); } } + +TEST(SecureRandomTest, Uniform) { + SecureRandom rng; + int count[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + + for (int i = 0; i < 1000; i++) { + count[rng.Uniform(10)]++; + } + for (int i = 0; i < 10; i++) { + // Practically, each count should be close to 100. + EXPECT_LT(50, count[i]) << count[i]; + } +} + +TEST(SecureRandomTest, OneIn) { + SecureRandom rng; + int count = 0; + + for (int i = 0; i < 1000; i++) { + if (rng.OneIn(10)) count++; + } + // Practically, count should be close to 100. + EXPECT_LT(50, count) << count; + EXPECT_GT(150, count) << count; +} -- cgit v1.2.3