normalize and port the rest of Firebase/Port code (#713)

* normalize bits
* normalize ordered_code

4 files changed, 677 insertions, 0 deletions

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 <algorithm>
+#include <iostream>
+#include <limits>
+
+#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<int>(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<int>(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<uint32_t>(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<uint32_t>::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<uint64_t>(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<uint64_t>::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 <iostream>
+#include <limits>
+
+#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<char>(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 <typename T>
+static void OCWriteIncreasing(std::string* dest, const T& val);
+template <typename T>
+static bool OCReadIncreasing(absl::string_view* src, T* result);
+
+// Read/WriteIncreasing<std::string>
+template <>
+void OCWriteIncreasing<std::string>(std::string* dest, const std::string& val) {
+  OrderedCode::WriteString(dest, val);
+}
+template <>
+bool OCReadIncreasing<std::string>(absl::string_view* src,
+                                   std::string* result) {
+  return OrderedCode::ReadString(src, result);
+}
+
+// Read/WriteIncreasing<uint64_t>
+template <>
+void OCWriteIncreasing<uint64_t>(std::string* dest, const uint64_t& val) {
+  OrderedCode::WriteNumIncreasing(dest, val);
+}
+template <>
+bool OCReadIncreasing<uint64_t>(absl::string_view* src, uint64_t* result) {
+  return OrderedCode::ReadNumIncreasing(src, result);
+}
+
+enum Direction { INCREASING = 0 };
+
+// Read/WriteIncreasing<int64_t>
+template <>
+void OCWriteIncreasing<int64_t>(std::string* dest, const int64_t& val) {
+  OrderedCode::WriteSignedNumIncreasing(dest, val);
+}
+template <>
+bool OCReadIncreasing<int64_t>(absl::string_view* src, int64_t* result) {
+  return OrderedCode::ReadSignedNumIncreasing(src, result);
+}
+
+template <typename T>
+std::string OCWrite(T val, Direction direction) {
+  EXPECT_EQ(INCREASING, direction);  // DECREASING never implemented.
+  std::string result;
+  OCWriteIncreasing<T>(&result, val);
+  return result;
+}
+
+template <typename T>
+void OCWriteToString(std::string* result, T val, Direction direction) {
+  EXPECT_EQ(INCREASING, direction);  // DECREASING never implemented.
+  OCWriteIncreasing<T>(result, val);
+}
+
+template <typename T>
+bool OCRead(absl::string_view* s, T* val, Direction direction) {
+  EXPECT_EQ(INCREASING, direction);  // DECREASING never implemented.
+  return OCReadIncreasing<T>(s, val);
+}
+
+// ---------------------------------------------------------------------
+// Numbers
+
+template <typename T>
+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<T>(&s, NULL, d));
+    EXPECT_EQ(s, a.substr(0, i));
+  }
+
+  absl::string_view s(a);
+  T v;
+  EXPECT_TRUE(OCRead<T>(&s, &v, d));
+  EXPECT_TRUE(s.empty());
+  return v;
+}
+
+template <typename T>
+static void TestWriteRead(Direction d, T expected) {
+  EXPECT_EQ(expected, TestRead<T>(d, OCWrite<T>(expected, d)));
+}
+
+// Verifies that the second Write* call appends a non-empty std::string to its
+// output.
+template <typename T, typename U>
+static void TestWriteAppends(Direction d, T first, U second) {
+  std::string encoded;
+  OCWriteToString<T>(&encoded, first, d);
+  std::string encoded_first_only = encoded;
+  OCWriteToString<U>(&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 <typename T>
+static void TestNumbers(T multiplier) {
+  for (int j = 0; j < 1; ++j) {
+    const Direction d = static_cast<Direction>(j);
+
+    // first test powers of 2 (and nearby numbers)
+    for (T x = std::numeric_limits<T>().max(); x != 0; x /= 2) {
+      TestWriteRead(d, multiplier * (x - 1));
+      TestWriteRead(d, multiplier * x);
+      if (x != std::numeric_limits<T>::max()) {
+        TestWriteRead(d, multiplier * (x + 1));
+      } else if (multiplier < 0 && static_cast<int64_t>(multiplier) == -1) {
+        TestWriteRead(d, -x - 1);
+      }
+    }
+
+    SecureRandom rnd;  // Generate 32bit pseudo-random integer.
+    for (int bits = 1; bits <= std::numeric_limits<T>().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<T>((static_cast<uint64_t>(rnd()) << 32 |
+                              static_cast<uint64_t>(rnd())) &
+                             mask);
+        TestWriteRead(d, multiplier * x);
+        T y = static_cast<T>((static_cast<uint64_t>(rnd()) << 32 |
+                              static_cast<uint64_t>(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 <typename T>
+static void TestNumberOrdering() {
+  const Direction d = INCREASING;
+
+  // first the negative numbers (if T is signed, otherwise no-op)
+  std::string laststr = OCWrite<T>(std::numeric_limits<T>().min(), d);
+  for (T num = std::numeric_limits<T>().min() / 2; num != 0; num /= 2) {
+    std::string strminus1 = OCWrite<T>(num - 1, d);
+    std::string str = OCWrite<T>(num, d);
+    std::string strplus1 = OCWrite<T>(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<T>(0, d);
+  T num = 1;
+  while (num < std::numeric_limits<T>().max() / 2) {
+    num *= 2;
+    std::string strminus1 = OCWrite<T>(num - 1, d);
+    std::string str = OCWrite<T>(num, d);
+    std::string strplus1 = OCWrite<T>(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<size_t>(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<char>(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<char>(b0);
+          buf[start_offset + 1] = static_cast<char>(b1);
+          buf[start_offset + 2] = static_cast<char>(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<uint64_t>(1);
+}
+
+TEST(OrderedCodeUint64, Ordering) {
+  TestNumberOrdering<uint64_t>();
+}
+
+TEST(OrderedCodeInt64, EncodeDecode) {
+  TestNumbers<int64_t>(1);
+  TestNumbers<int64_t>(-1);
+}
+
+TEST(OrderedCodeInt64, Ordering) {
+  TestNumberOrdering<int64_t>();
+}
+
+// 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 <typename T>
+static void TestInvalidEncoding(Direction d, const std::string& s) {
+  absl::string_view p(s);
+  EXPECT_FALSE(OCRead<T>(&p, static_cast<T*>(NULL), d));
+  EXPECT_EQ(s, p);
+}
+
+TEST(OrderedCodeInvalidEncodingsTest, Overflow) {
+  // 1U << 64, increasing
+  const std::string k2xx64U = "\x09\x01" + std::string(8, 0);
+  TestInvalidEncoding<uint64_t>(INCREASING, k2xx64U);
+
+  // 1 << 63 and ~(1 << 63), increasing
+  const std::string k2xx63 = "\xff\xc0\x80" + std::string(7, 0);
+  TestInvalidEncoding<int64_t>(INCREASING, k2xx63);
+  TestInvalidEncoding<int64_t>(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<size_t>(n), non_minimal.length());
+
+    EXPECT_NE(OCWrite<uint64_t>(0, INCREASING), non_minimal);
+
+#if defined(NDEBUG)
+    TestRead<uint64_t>(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<char>(rnd.Uniform(256)) & ~*header.rbegin()) +
+        RandomString(&rnd, n - static_cast<int>(header.length()) - 1);
+    EXPECT_EQ(static_cast<size_t>(n), non_minimal.length());
+
+    EXPECT_NE(OCWrite<int64_t>(0, INCREASING), non_minimal);
+
+#if defined(NDEBUG)
+    TestRead<int64_t>(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<Direction>(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<std::string>(&out, a, d);
+        OCWriteToString<std::string>(&out, b, d);
+
+        std::string a2, b2, dummy;
+        absl::string_view s = out;
+        absl::string_view s2 = out;
+        EXPECT_TRUE(OCRead<std::string>(&s, &a2, d));
+        EXPECT_TRUE(OCRead<std::string>(&s2, NULL, d));
+        EXPECT_EQ(s, s2);
+
+        EXPECT_TRUE(OCRead<std::string>(&s, &b2, d));
+        EXPECT_TRUE(OCRead<std::string>(&s2, NULL, d));
+        EXPECT_EQ(s, s2);
+
+        EXPECT_TRUE(!OCRead<std::string>(&s, &dummy, d));
+        EXPECT_TRUE(!OCRead<std::string>(&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;
+}