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

* normalize bits
* normalize ordered_code

10 files changed, 1657 insertions, 0 deletions

diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
index 51621a0..b763a63 100644
--- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
+++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
@@ -107,11 +107,15 @@ cc_library(
   SOURCES
     autoid.cc
     autoid.h
+    bits.cc
+    bits.h
     comparison.cc
     comparison.h
     config.h
     firebase_assert.h
     log.h
+    ordered_code.cc
+    ordered_code.h
     secure_random.h
     string_util.cc
     string_util.h
diff --git a/Firestore/core/src/firebase/firestore/util/bits.cc b/Firestore/core/src/firebase/firestore/util/bits.cc
new file mode 100644
index 0000000..0bfe4c3
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/bits.cc
@@ -0,0 +1,43 @@
+/*
+ * 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 "Firestore/core/src/firebase/firestore/util/firebase_assert.h"
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+int Bits::Log2Floor_Portable(uint32_t n) {
+  if (n == 0) return -1;
+  int log = 0;
+  uint32_t value = n;
+  for (int i = 4; i >= 0; --i) {
+    int shift = (1 << i);
+    uint32_t x = value >> shift;
+    if (x != 0) {
+      value = x;
+      log += shift;
+    }
+  }
+  FIREBASE_ASSERT(value == 1);
+  return log;
+}
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
diff --git a/Firestore/core/src/firebase/firestore/util/bits.h b/Firestore/core/src/firebase/firestore/util/bits.h
new file mode 100644
index 0000000..185273f
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/bits.h
@@ -0,0 +1,166 @@
+/*
+ * 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.
+ */
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_
+
+// Various bit-twiddling functions, all of which are static members of the Bits
+// class (making it effectively a namespace). Operands are unsigned integers.
+// Munging bits in _signed_ integers is fraught with peril! For example,
+// -5 << n has undefined behavior (for some values of n).
+
+#include <stdint.h>
+
+class Bits_Port32_Test;
+class Bits_Port64_Test;
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+class Bits {
+ public:
+  /** Return floor(log2(n)) for positive integer n.  Returns -1 iff n == 0. */
+  static int Log2Floor(uint32_t n);
+  static int Log2Floor64(uint64_t n);
+
+  /**
+   * Potentially faster version of Log2Floor() that returns an
+   * undefined value if n == 0.
+   */
+  static int Log2FloorNonZero(uint32_t n);
+  static int Log2FloorNonZero64(uint64_t n);
+
+ private:
+  // Portable implementations.
+  static int Log2Floor_Portable(uint32_t n);
+  static int Log2Floor64_Portable(uint64_t n);
+  static int Log2FloorNonZero_Portable(uint32_t n);
+  static int Log2FloorNonZero64_Portable(uint64_t n);
+
+  Bits(Bits const&) = delete;
+  void operator=(Bits const&) = delete;
+
+  // Allow tests to call _Portable variants directly.
+  friend class Bits_Port32_Test;
+  friend class Bits_Port64_Test;
+};
+
+// ------------------------------------------------------------------------
+// Implementation details follow
+// ------------------------------------------------------------------------
+
+#if defined(__GNUC__)
+
+inline int Bits::Log2Floor(uint32_t n) {
+  return n == 0 ? -1 : 31 ^ __builtin_clz(n);
+}
+
+inline int Bits::Log2FloorNonZero(uint32_t n) {
+  return 31 ^ __builtin_clz(n);
+}
+
+inline int Bits::Log2Floor64(uint64_t n) {
+  return n == 0 ? -1 : 63 ^ __builtin_clzll(n);
+}
+
+inline int Bits::Log2FloorNonZero64(uint64_t n) {
+  return 63 ^ __builtin_clzll(n);
+}
+
+#elif defined(COMPILER_MSVC)
+
+inline int Bits::Log2FloorNonZero(uint32 n) {
+#ifdef _M_IX86
+  _asm {
+    bsr ebx, n
+    mov n, ebx
+  }
+  return n;
+#else
+  return Bits::Log2FloorNonZero_Portable(n);
+#endif
+}
+
+inline int Bits::Log2Floor(uint32 n) {
+#ifdef _M_IX86
+  _asm {
+    xor ebx, ebx
+    mov eax, n
+    and eax, eax
+    jz return_ebx
+    bsr ebx, eax
+  return_ebx:
+    mov n, ebx
+  }
+  return n;
+#else
+  return Bits::Log2Floor_Portable(n);
+#endif
+}
+
+inline int Bits::Log2Floor64(uint64_t n) {
+  return Bits::Log2Floor64_Portable(n);
+}
+
+inline int Bits::Log2FloorNonZero64(uint64_t n) {
+  return Bits::Log2FloorNonZero64_Portable(n);
+}
+
+#else  // !__GNUC__ && !COMPILER_MSVC
+
+inline int Bits::Log2Floor64(uint64_t n) {
+  return Bits::Log2Floor64_Portable(n);
+}
+
+inline int Bits::Log2FloorNonZero64(uint64_t n) {
+  return Bits::Log2FloorNonZero64_Portable(n);
+}
+
+#endif
+
+inline int Bits::Log2FloorNonZero_Portable(uint32_t n) {
+  // Just use the common routine
+  return Log2Floor(n);
+}
+
+// Log2Floor64() is defined in terms of Log2Floor32(), Log2FloorNonZero32()
+inline int Bits::Log2Floor64_Portable(uint64_t n) {
+  const uint32_t topbits = static_cast<uint32_t>(n >> 32);
+  if (topbits == 0) {
+    // Top bits are zero, so scan in bottom bits
+    return Log2Floor(static_cast<uint32_t>(n));
+  } else {
+    return 32 + Log2FloorNonZero(topbits);
+  }
+}
+
+// Log2FloorNonZero64() is defined in terms of Log2FloorNonZero32()
+inline int Bits::Log2FloorNonZero64_Portable(uint64_t n) {
+  const uint32_t topbits = static_cast<uint32_t>(n >> 32);
+  if (topbits == 0) {
+    // Top bits are zero, so scan in bottom bits
+    return Log2FloorNonZero(static_cast<uint32_t>(n));
+  } else {
+    return 32 + Log2FloorNonZero(topbits);
+  }
+}
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_
diff --git a/Firestore/core/src/firebase/firestore/util/ordered_code.cc b/Firestore/core/src/firebase/firestore/util/ordered_code.cc
new file mode 100644
index 0000000..688f15c
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/ordered_code.cc
@@ -0,0 +1,622 @@
+/*
+ * 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 <absl/base/internal/endian.h>
+#include <absl/base/internal/unaligned_access.h>
+#include <absl/base/port.h>
+
+#include "Firestore/core/src/firebase/firestore/util/bits.h"
+#include "Firestore/core/src/firebase/firestore/util/firebase_assert.h"
+
+#define UNALIGNED_LOAD32 ABSL_INTERNAL_UNALIGNED_LOAD32
+#define UNALIGNED_LOAD64 ABSL_INTERNAL_UNALIGNED_LOAD64
+#define UNALIGNED_STORE32 ABSL_INTERNAL_UNALIGNED_STORE32
+#define UNALIGNED_STORE64 ABSL_INTERNAL_UNALIGNED_STORE64
+
+// We encode a string in different ways depending on whether the item
+// should be in lexicographically increasing or decreasing order.
+//
+//
+// Lexicographically increasing order
+//
+// We want a string-to-string mapping F(x) such that for any two strings
+//
+//      x < y   =>   F(x) < F(y)
+//
+// In addition to the normal characters '\x00' through '\xff', we want to
+// encode a few extra symbols in strings:
+//
+//      <sep>           Separator between items
+//      <infinity>      Infinite string
+//
+// Therefore we need an alphabet with at least 258 symbols.  Each
+// character '\1' through '\xfe' is mapped to itself.  The other four are
+// encoded into two-letter sequences starting with '\0' and '\xff':
+//
+//      <sep>           encoded as =>           \0\1
+//      \0              encoded as =>           \0\xff
+//      \xff            encoded as =>           \xff\x00
+//      <infinity>      encoded as =>           \xff\xff
+//
+// The remaining two-letter sequences starting with '\0' and '\xff' are
+// currently unused.
+//
+// F(<infinity>) is defined above.  For any finite string x, F(x) is the
+// the encodings of x's characters followed by the encoding for <sep>.  The
+// ordering of two finite strings is the same as the ordering of the
+// respective characters at the first position where they differ, which in
+// turn is the same as the ordering of the encodings of those two
+// characters.  Moreover, for every finite string x, F(x) < F(<infinity>).
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+static const char kEscape1 = '\000';
+static const char kNullCharacter = '\xff';  // Combined with kEscape1
+static const char kSeparator = '\001';      // Combined with kEscape1
+
+static const char kEscape2 = '\xff';
+static const char kInfinity = '\xff';     // Combined with kEscape2
+static const char kFFCharacter = '\000';  // Combined with kEscape2
+
+static const char kEscape1_Separator[2] = {kEscape1, kSeparator};
+
+/** Append to "*dest" the "len" bytes starting from "*src". */
+inline static void AppendBytes(std::string* dest, const char* src, size_t len) {
+  dest->append(src, len);
+}
+
+inline static bool IsSpecialByte(char c) {
+  return ((unsigned char)(c + 1)) < 2;
+}
+
+/**
+ * Returns 0 if one or more of the bytes in the specified uint32 value
+ * are the special values 0 or 255, and returns 4 otherwise.  The
+ * result of this routine can be added to "p" to either advance past
+ * the next 4 bytes if they do not contain a special byte, or to
+ * remain on this set of four bytes if they contain the next special
+ * byte occurrence.
+ *
+ * REQUIRES: v_32 is the value of loading the next 4 bytes from "*p" (we
+ * pass in v_32 rather than loading it because in some cases, the client
+ * may already have the value in a register: "p" is just used for
+ * assertion checking).
+ */
+inline static int AdvanceIfNoSpecialBytes(uint32_t v_32, const char* p) {
+  FIREBASE_ASSERT(UNALIGNED_LOAD32(p) == v_32);
+  // See comments in SkipToNextSpecialByte if you wish to
+  // understand this expression (which checks for the occurrence
+  // of the special byte values 0 or 255 in any of the bytes of v_32).
+  if ((v_32 - 0x01010101u) & ~(v_32 + 0x01010101u) & 0x80808080u) {
+    // Special byte is in p[0..3]
+    FIREBASE_ASSERT(IsSpecialByte(p[0]) || IsSpecialByte(p[1]) ||
+                    IsSpecialByte(p[2]) || IsSpecialByte(p[3]));
+    return 0;
+  } else {
+    FIREBASE_ASSERT(!IsSpecialByte(p[0]));
+    FIREBASE_ASSERT(!IsSpecialByte(p[1]));
+    FIREBASE_ASSERT(!IsSpecialByte(p[2]));
+    FIREBASE_ASSERT(!IsSpecialByte(p[3]));
+    return 4;
+  }
+}
+
+/**
+ * Return a pointer to the first byte in the range "[start..limit)"
+ * whose value is 0 or 255 (kEscape1 or kEscape2).  If no such byte
+ * exists in the range, returns "limit".
+ */
+inline static const char* SkipToNextSpecialByte(const char* start,
+                                                const char* limit) {
+  // If these constants were ever changed, this routine needs to change
+  FIREBASE_ASSERT(kEscape1 == 0);
+  FIREBASE_ASSERT((kEscape2 & 0xff) == 255);
+  const char* p = start;
+  while (p + 8 <= limit) {
+    // Find out if any of the next 8 bytes are either 0 or 255 (our
+    // two characters that require special handling).  We do this using
+    // the technique described in:
+    //
+    //    http://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord
+    //
+    // We use the test (x + 1) < 2 to check x = 0 or -1(255)
+    //
+    // If x is a byte value (0x00..0xff):
+    // (x - 0x01) & 0x80 is true only when x = 0x81..0xff, 0x00
+    // ~(x + 0x01) & 0x80 is true only when x = 0x00..0x7e, 0xff
+    // The intersection of the above two sets is x = 0x00 or 0xff.
+    // We can ignore carry between bytes because only x = 0x00 or 0xff
+    // can cause carry in the expression -- and such x already makes the
+    // result value non-zero.
+    uint64_t v = UNALIGNED_LOAD64(p);
+    bool hasZeroOr255Byte = (v - 0x0101010101010101ull) &
+                            ~(v + 0x0101010101010101ull) &
+                            0x8080808080808080ull;
+    if (!hasZeroOr255Byte) {
+      // No special values in the next 8 bytes
+      p += 8;
+    } else {
+// We know the next 8 bytes have a special byte: find it
+#ifdef IS_LITTLE_ENDIAN
+      uint32_t v_32 = static_cast<uint32_t>(v);  // Low 32 bits of v
+#else
+      uint32_t v_32 = UNALIGNED_LOAD32(p);
+#endif
+      // Test 32 bits at once to see if special byte is in next 4 bytes
+      // or the following 4 bytes
+      p += AdvanceIfNoSpecialBytes(v_32, p);
+      if (IsSpecialByte(p[0])) return p;
+      if (IsSpecialByte(p[1])) return p + 1;
+      if (IsSpecialByte(p[2])) return p + 2;
+      FIREBASE_ASSERT(
+          IsSpecialByte(p[3]));  // Last byte must be the special one
+      return p + 3;
+    }
+  }
+  if (p + 4 <= limit) {
+    uint32_t v_32 = UNALIGNED_LOAD32(p);
+    p += AdvanceIfNoSpecialBytes(v_32, p);
+  }
+  while (p < limit && !IsSpecialByte(*p)) {
+    p++;
+  }
+  return p;
+}
+
+// Expose SkipToNextSpecialByte for testing purposes
+const char* OrderedCode::TEST_SkipToNextSpecialByte(const char* start,
+                                                    const char* limit) {
+  return SkipToNextSpecialByte(start, limit);
+}
+
+/**
+ * Helper routine to encode "s" and append to "*dest", escaping special
+ * characters.
+ */
+inline static void EncodeStringFragment(std::string* dest,
+                                        absl::string_view s) {
+  const char* p = s.data();
+  const char* limit = p + s.size();
+  const char* copy_start = p;
+  while (true) {
+    p = SkipToNextSpecialByte(p, limit);
+    if (p >= limit) break;  // No more special characters that need escaping
+    char c = *(p++);
+    FIREBASE_ASSERT(IsSpecialByte(c));
+    if (c == kEscape1) {
+      AppendBytes(dest, copy_start, static_cast<size_t>(p - copy_start) - 1);
+      dest->push_back(kEscape1);
+      dest->push_back(kNullCharacter);
+      copy_start = p;
+    } else {
+      FIREBASE_ASSERT(c == kEscape2);
+      AppendBytes(dest, copy_start, static_cast<size_t>(p - copy_start) - 1);
+      dest->push_back(kEscape2);
+      dest->push_back(kFFCharacter);
+      copy_start = p;
+    }
+  }
+  if (p > copy_start) {
+    AppendBytes(dest, copy_start, static_cast<size_t>(p - copy_start));
+  }
+}
+
+void OrderedCode::WriteString(std::string* dest, absl::string_view s) {
+  EncodeStringFragment(dest, s);
+  AppendBytes(dest, kEscape1_Separator, 2);
+}
+
+/**
+ * Return number of bytes needed to encode the non-length portion
+ * of val in ordered coding.  Returns number in range [0,8].
+ */
+static inline unsigned int OrderedNumLength(uint64_t val) {
+  const int lg = Bits::Log2Floor64(val);  // -1 if val==0
+  return static_cast<unsigned int>(lg + 1 + 7) / 8;
+}
+
+/**
+ * Append n bytes from src to *dst.
+ * REQUIRES: n <= 9
+ * REQUIRES: src[0..8] are readable bytes (even if n is smaller)
+ *
+ * If we use string::append() instead of this routine, it increases the
+ * runtime of WriteNumIncreasing from ~9ns to ~13ns.
+ */
+static inline void AppendUpto9(std::string* dst,
+                               const char* src,
+                               unsigned int n) {
+  dst->append(src, 9);         // Fixed-length append
+  const size_t extra = 9 - n;  // How many extra bytes we added
+  dst->erase(dst->size() - extra, extra);
+}
+
+void OrderedCode::WriteNumIncreasing(std::string* dest, uint64_t val) {
+  // Values are encoded with a single byte length prefix, followed
+  // by the actual value in big-endian format with leading 0 bytes
+  // dropped.
+
+  // 8 bytes for value plus one byte for length.  In addition, we have
+  // 8 extra bytes at the end so that we can have a fixed-length append
+  // call on *dest.
+  char buf[17];
+
+  UNALIGNED_STORE64(buf + 1,
+                    absl::ghtonll(val));  // buf[0] may be needed for length
+  const unsigned int length = OrderedNumLength(val);
+  char* start = buf + 9 - length - 1;
+  *start = static_cast<char>(length);
+  AppendUpto9(dest, start, length + 1);
+}
+
+inline static void WriteInfinityInternal(std::string* dest) {
+  // Make an array so that we can just do one string operation for performance
+  static const char buf[2] = {kEscape2, kInfinity};
+  dest->append(buf, 2);
+}
+
+void OrderedCode::WriteInfinity(std::string* dest) {
+  WriteInfinityInternal(dest);
+}
+
+void OrderedCode::WriteTrailingString(std::string* dest,
+                                      absl::string_view str) {
+  dest->append(str.data(), str.size());
+}
+
+/**
+ * Parse the encoding of a string previously encoded with or without
+ * inversion.  If parse succeeds, return true, consume encoding from
+ * "*src", and if result != NULL append the decoded string to "*result".
+ * Otherwise, return false and leave both undefined.
+ */
+inline static bool ReadStringInternal(absl::string_view* src,
+                                      std::string* result) {
+  const char* start = src->data();
+  const char* string_limit = src->data() + src->size();
+
+  // We only scan up to "limit-2" since a valid string must end with
+  // a two character terminator: 'kEscape1 kSeparator'
+  const char* limit = string_limit - 1;
+  const char* copy_start = start;
+  while (true) {
+    start = SkipToNextSpecialByte(start, limit);
+    if (start >= limit) break;  // No terminator sequence found
+    const char c = *(start++);
+    // If inversion is required, instead of inverting 'c', we invert the
+    // character constants to which 'c' is compared.  We get the same
+    // behavior but save the runtime cost of inverting 'c'.
+    FIREBASE_ASSERT(IsSpecialByte(c));
+    if (c == kEscape1) {
+      if (result) {
+        AppendBytes(result, copy_start,
+                    static_cast<size_t>(start - copy_start) - 1);
+      }
+      // kEscape1 kSeparator ends component
+      // kEscape1 kNullCharacter represents '\0'
+      const char next = *(start++);
+      if (next == kSeparator) {
+        src->remove_prefix(static_cast<size_t>(start - src->data()));
+        return true;
+      } else if (next == kNullCharacter) {
+        if (result) {
+          *result += '\0';
+        }
+      } else {
+        return false;
+      }
+      copy_start = start;
+    } else {
+      FIREBASE_ASSERT(c == kEscape2);
+      if (result) {
+        AppendBytes(result, copy_start,
+                    static_cast<size_t>(start - copy_start) - 1);
+      }
+      // kEscape2 kFFCharacter represents '\xff'
+      // kEscape2 kInfinity is an error
+      const char next = *(start++);
+      if (next == kFFCharacter) {
+        if (result) {
+          *result += '\xff';
+        }
+      } else {
+        return false;
+      }
+      copy_start = start;
+    }
+  }
+  return false;
+}
+
+bool OrderedCode::ReadString(absl::string_view* src, std::string* result) {
+  return ReadStringInternal(src, result);
+}
+
+bool OrderedCode::ReadNumIncreasing(absl::string_view* src, uint64_t* result) {
+  if (src->empty()) {
+    return false;  // Not enough bytes
+  }
+
+  // Decode length byte
+  const size_t len = static_cast<size_t>((*src)[0]);
+
+  // If len > 0 and src is longer than 1, the first byte of "payload"
+  // must be non-zero (otherwise the encoding is not minimal).
+  // In opt mode, we don't enforce that encodings must be minimal.
+  FIREBASE_ASSERT(0 == len || src->size() == 1 || (*src)[1] != '\0');
+
+  if (len + 1 > src->size() || len > 8) {
+    return false;  // Not enough bytes or too many bytes
+  }
+
+  if (result) {
+    uint64_t tmp = 0;
+    for (size_t i = 0; i < len; i++) {
+      tmp <<= 8;
+      tmp |= static_cast<unsigned char>((*src)[1 + i]);
+    }
+    *result = tmp;
+  }
+  src->remove_prefix(len + 1);
+  return true;
+}
+
+inline static bool ReadInfinityInternal(absl::string_view* src) {
+  if (src->size() >= 2 && ((*src)[0] == kEscape2) && ((*src)[1] == kInfinity)) {
+    src->remove_prefix(2);
+    return true;
+  } else {
+    return false;
+  }
+}
+
+bool OrderedCode::ReadInfinity(absl::string_view* src) {
+  return ReadInfinityInternal(src);
+}
+
+inline static bool ReadStringOrInfinityInternal(absl::string_view* src,
+                                                std::string* result,
+                                                bool* inf) {
+  if (ReadInfinityInternal(src)) {
+    if (inf) *inf = true;
+    return true;
+  }
+
+  // We don't use ReadStringInternal here because that would inline
+  // the whole encoded string parsing code here.  Depending on INVERT, only
+  // one of the following two calls will be generated at compile time.
+  bool success = OrderedCode::ReadString(src, result);
+  if (success) {
+    if (inf) *inf = false;
+    return true;
+  } else {
+    return false;
+  }
+}
+
+bool OrderedCode::ReadStringOrInfinity(absl::string_view* src,
+                                       std::string* result,
+                                       bool* inf) {
+  return ReadStringOrInfinityInternal(src, result, inf);
+}
+
+bool OrderedCode::ReadTrailingString(absl::string_view* src,
+                                     std::string* result) {
+  if (result) result->assign(src->data(), src->size());
+  src->remove_prefix(src->size());
+  return true;
+}
+
+void OrderedCode::TEST_Corrupt(std::string* str, int k) {
+  int seen_seps = 0;
+  for (size_t i = 0; i < str->size() - 1; i++) {
+    if ((*str)[i] == kEscape1 && (*str)[i + 1] == kSeparator) {
+      seen_seps++;
+      if (seen_seps == k) {
+        (*str)[i + 1] = kSeparator + 1;
+        return;
+      }
+    }
+  }
+}
+
+// Signed number encoding/decoding /////////////////////////////////////
+//
+// The format is as follows:
+//
+// The first bit (the most significant bit of the first byte)
+// represents the sign, 0 if the number is negative and
+// 1 if the number is >= 0.
+//
+// Any unbroken sequence of successive bits with the same value as the sign
+// bit, up to 9 (the 8th and 9th are the most significant bits of the next
+// byte), are size bits that count the number of bytes after the first byte.
+// That is, the total length is between 1 and 10 bytes.
+//
+// The value occupies the bits after the sign bit and the "size bits"
+// till the end of the string, in network byte order.  If the number
+// is negative, the bits are in 2-complement.
+//
+//
+// Example 1: number 0x424242 -> 4 byte big-endian hex string 0xf0424242:
+//
+// +---------------+---------------+---------------+---------------+
+//  1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0
+// +---------------+---------------+---------------+---------------+
+//  ^ ^ ^ ^   ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+//  | | | |   | | | | | | | | | | | | | | | | | | | | | | | | | | |
+//  | | | |   payload: the remaining bits after the sign and size bits
+//  | | | |            and the delimiter bit, the value is 0x424242
+//  | | | |
+//  | size bits: 3 successive bits with the same value as the sign bit
+//  |            (followed by a delimiter bit with the opposite value)
+//  |            mean that there are 3 bytes after the first byte, 4 total
+//  |
+//  sign bit: 1 means that the number is non-negative
+//
+// Example 2: negative number -0x800 -> 2 byte big-endian hex string 0x3800:
+//
+// +---------------+---------------+
+//  0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
+// +---------------+---------------+
+//  ^ ^   ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+//  | |   | | | | | | | | | | | | | | | | | | | | | | | | | | |
+//  | |   payload: the remaining bits after the sign and size bits and the
+//  | |            delimiter bit, 2-complement because of the negative sign,
+//  | |            value is ~0x7ff, represents the value -0x800
+//  | |
+//  | size bits: 1 bit with the same value as the sign bit
+//  |            (followed by a delimiter bit with the opposite value)
+//  |            means that there is 1 byte after the first byte, 2 total
+//  |
+//  sign bit: 0 means that the number is negative
+//
+//
+// Compared with the simpler unsigned format used for uint64_t numbers,
+// this format is more compact for small numbers, namely one byte encodes
+// numbers in the range [-64,64), two bytes cover the range [-2^13,2^13), etc.
+// In general, n bytes encode numbers in the range [-2^(n*7-1),2^(n*7-1)).
+// (The cross-over point for compactness of representation is 8 bytes,
+// where this format only covers the range [-2^55,2^55),
+// whereas an encoding with sign bit and length in the first byte and
+// payload in all following bytes would cover [-2^56,2^56).)
+
+static const int kMaxSigned64Length = 10;
+
+// This array maps encoding length to header bits in the first two bytes.
+static const char kLengthToHeaderBits[1 + kMaxSigned64Length][2] = {
+    {0, 0},      {'\x80', 0},      {'\xc0', 0},     {'\xe0', 0},
+    {'\xf0', 0}, {'\xf8', 0},      {'\xfc', 0},     {'\xfe', 0},
+    {'\xff', 0}, {'\xff', '\x80'}, {'\xff', '\xc0'}};
+
+// This array maps encoding lengths to the header bits that overlap with
+// the payload and need fixing when reading.
+static const uint64_t kLengthToMask[1 + kMaxSigned64Length] = {
+    0ULL,
+    0x80ULL,
+    0xc000ULL,
+    0xe00000ULL,
+    0xf0000000ULL,
+    0xf800000000ULL,
+    0xfc0000000000ULL,
+    0xfe000000000000ULL,
+    0xff00000000000000ULL,
+    0x8000000000000000ULL,
+    0ULL};
+
+// This array maps the number of bits in a number to the encoding
+// length produced by WriteSignedNumIncreasing.
+// For positive numbers, the number of bits is 1 plus the most significant
+// bit position (the highest bit position in a positive int64_t is 63).
+// For a negative number n, we count the bits in ~n.
+// That is, length = kBitsToLength[Bits::Log2Floor64(n < 0 ? ~n : n) + 1].
+static const int8_t kBitsToLength[1 + 63] = {
+    1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4,
+    4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7,
+    7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10};
+
+/** Calculates the encoding length in bytes of the signed number n. */
+static inline int SignedEncodingLength(int64_t n) {
+  return kBitsToLength[Bits::Log2Floor64(
+                           static_cast<uint64_t>(n < 0 ? ~n : n)) +
+                       1];
+}
+
+/** Slightly faster version for n > 0. */
+static inline int SignedEncodingLengthPositive(int64_t n) {
+  return kBitsToLength[Bits::Log2FloorNonZero64(static_cast<uint64_t>(n)) + 1];
+}
+
+void OrderedCode::WriteSignedNumIncreasing(std::string* dest, int64_t val) {
+  const int64_t x = val < 0 ? ~val : val;
+  if (x < 64) {  // fast path for encoding length == 1
+    *dest += static_cast<char>(kLengthToHeaderBits[1][0] ^ val);
+    return;
+  }
+  // buf = val in network byte order, sign extended to 10 bytes
+  const char sign_byte = val < 0 ? '\xff' : '\0';
+  char buf[10] = {
+      sign_byte,
+      sign_byte,
+  };
+  UNALIGNED_STORE64(buf + 2, absl::ghtonll(static_cast<uint64_t>(val)));
+
+  FIREBASE_ASSERT_MESSAGE_WITH_EXPRESSION(sizeof(buf) == kMaxSigned64Length,
+                                          sizeof(buf) == kMaxSigned64Length,
+                                          "max length size mismatch");
+  const size_t len = static_cast<size_t>(SignedEncodingLengthPositive(x));
+  FIREBASE_ASSERT(len >= 2);
+  char* const begin = buf + sizeof(buf) - len;
+  begin[0] ^= kLengthToHeaderBits[len][0];
+  begin[1] ^= kLengthToHeaderBits[len][1];  // ok because len >= 2
+  dest->append(begin, len);
+}
+
+bool OrderedCode::ReadSignedNumIncreasing(absl::string_view* src,
+                                          int64_t* result) {
+  if (src->empty()) return false;
+  const uint64_t xor_mask = (!((*src)[0] & 0x80)) ? ~0ULL : 0ULL;
+  const unsigned char first_byte = static_cast<unsigned char>(
+      static_cast<uint64_t>((*src)[0]) ^ (xor_mask & 0xff));
+
+  // now calculate and test length, and set x to raw (unmasked) result
+  size_t len;
+  uint64_t x;
+  if (first_byte != 0xff) {
+    len = static_cast<size_t>(7 - Bits::Log2FloorNonZero(first_byte ^ 0xff));
+    if (src->size() < len) return false;
+    x = xor_mask;  // sign extend using xor_mask
+    for (size_t i = 0; i < len; ++i)
+      x = (x << 8) | static_cast<unsigned char>((*src)[i]);
+  } else {
+    len = 8;
+    if (src->size() < len) return false;
+    const unsigned char second_byte = static_cast<unsigned char>(
+        static_cast<uint64_t>((*src)[1]) ^ (xor_mask & 0xff));
+    if (second_byte >= 0x80) {
+      if (second_byte < 0xc0) {
+        len = 9;
+      } else {
+        const unsigned char third_byte = static_cast<unsigned char>(
+            static_cast<uint64_t>((*src)[2]) ^ (xor_mask & 0xff));
+        if (second_byte == 0xc0 && third_byte < 0x80) {
+          len = 10;
+        } else {
+          return false;  // either len > 10 or len == 10 and #bits > 63
+        }
+      }
+      if (src->size() < len) return false;
+    }
+    x = absl::gntohll(UNALIGNED_LOAD64(src->data() + len - 8));
+  }
+
+  x ^= kLengthToMask[len];  // remove spurious header bits
+
+  FIREBASE_ASSERT(len == static_cast<size_t>(
+                             SignedEncodingLength(static_cast<int64_t>(x))));
+
+  if (result) *result = static_cast<int64_t>(x);
+  src->remove_prefix(static_cast<size_t>(len));
+  return true;
+}
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
diff --git a/Firestore/core/src/firebase/firestore/util/ordered_code.h b/Firestore/core/src/firebase/firestore/util/ordered_code.h
new file mode 100644
index 0000000..57b84bd
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/ordered_code.h
@@ -0,0 +1,129 @@
+/*
+ * 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.
+ */
+
+// This module provides routines for encoding a sequence of typed
+// entities into a string.  The resulting strings can be
+// lexicographically compared to yield the same comparison value that
+// would have been generated if the encoded items had been compared
+// one by one according to their type.
+//
+// More precisely, suppose:
+//  1. string A is generated by encoding the sequence of items [A_1..A_n]
+//  2. string B is generated by encoding the sequence of items [B_1..B_n]
+//  3. The types match; i.e., for all i: A_i was encoded using
+//     the same routine as B_i
+// Then:
+//    Comparing A vs. B lexicographically is the same as comparing
+//    the vectors [A_1..A_n] and [B_1..B_n] lexicographically.
+//
+// Furthermore, if n < m, the encoding of [A_1..A_n] is a strict prefix of
+// [A_1..A_m] (unless m = n+1 and A_m is the empty string encoded with
+// WriteTrailingString, in which case the encodings are equal).
+//
+// This module is often useful when generating multi-part sstable
+// keys that have to be ordered in a particular fashion.
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ORDERED_CODE_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ORDERED_CODE_H_
+
+#include <string>
+
+#include "absl/strings/string_view.h"
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+class OrderedCode {
+ public:
+  // -------------------------------------------------------------------
+  // Encoding routines: each one of the following routines append
+  // one item to "*dest".  The Write(Signed)NumIncreasing() and
+  // Write(Signed)NumDecreasing() routines differ in whether the resulting
+  // encoding is ordered by increasing number or decreasing number.
+  // Similarly, WriteString() and WriteStringDecreasing() differ in whether
+  // the resulting encoding is ordered by the original string in
+  // lexicographically increasing or decreasing order.  WriteString()
+  // is not called WriteStringIncreasing() for convenience and backward
+  // compatibility.
+
+  static void WriteString(std::string* dest, absl::string_view str);
+  static void WriteNumIncreasing(std::string* dest, uint64_t num);
+  static void WriteSignedNumIncreasing(std::string* dest, int64_t num);
+
+  /**
+   * Creates an encoding for the "infinite string", a value considered to
+   * be lexicographically after any real string.  Note that in the case of
+   * WriteInfinityDecreasing(), this would come before any real string as
+   * the ordering puts lexicographically greater values first.
+   */
+  static void WriteInfinity(std::string* dest);
+
+  /**
+   * Special string append that can only be used at the tail end of
+   * an encoded string -- blindly appends "str" to "*dest".
+   */
+  static void WriteTrailingString(std::string* dest, absl::string_view str);
+
+  // -------------------------------------------------------------------
+  // Decoding routines: these extract an item earlier encoded using
+  // the corresponding WriteXXX() routines above.  The item is read
+  // from "*src"; "*src" is modified to point past the decoded item;
+  // and if "result" is non-NULL, "*result" is modified to contain the
+  // result.  In case of string result, the decoded string is appended to
+  // "*result".  Returns true if the next item was read successfully, false
+  // otherwise.
+
+  static bool ReadString(absl::string_view* src, std::string* result);
+  static bool ReadNumIncreasing(absl::string_view* src, uint64_t* result);
+  static bool ReadSignedNumIncreasing(absl::string_view* src, int64_t* result);
+
+  static bool ReadInfinity(absl::string_view* src);
+  static bool ReadTrailingString(absl::string_view* src, std::string* result);
+
+  /** REQUIRES: next item was encoded by WriteInfinity() or WriteString(). */
+  static bool ReadStringOrInfinity(absl::string_view* src,
+                                   std::string* result,
+                                   bool* inf);
+
+  /**
+   * Helper for testing: corrupt "*str" by changing the kth item separator
+   * in the string.
+   */
+  static void TEST_Corrupt(std::string* str, int k);
+
+  /**
+   * Helper for testing.
+   * SkipToNextSpecialByte is an internal routine defined in the .cc file
+   * with the following semantics. Return a pointer to the first byte
+   * in the range "[start..limit)" whose value is 0 or 255.  If no such
+   * byte exists in the range, returns "limit".
+   */
+  static const char* TEST_SkipToNextSpecialByte(const char* start,
+                                                const char* limit);
+
+  // Not an instantiable class, but the class exists to make it easy to
+  // use with a single using statement.
+  OrderedCode() = delete;
+  OrderedCode(const OrderedCode&) = delete;
+  OrderedCode& operator=(const OrderedCode&) = delete;
+};
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_ORDERED_CODE_H_
diff --git a/Firestore/core/src/firebase/firestore/util/secure_random.h b/Firestore/core/src/firebase/firestore/util/secure_random.h
index 72be1bd..95b41e1 100644
--- a/Firestore/core/src/firebase/firestore/util/secure_random.h
+++ b/Firestore/core/src/firebase/firestore/util/secure_random.h
@@ -50,6 +50,22 @@ class SecureRandom {
   }
 
   result_type operator()();
+
+  /** Returns a uniformly distributed pseudorandom integer in [0, n). */
+  inline result_type Uniform(result_type n) {
+    // Divides the range into buckets of size n plus leftovers.
+    const result_type rem = (max() - min()) % n + min() + 1;
+    result_type rnd;
+    // Generates random number until the number falls into a bucket.
+    do {
+      rnd = (*this)();
+    } while (rnd < rem);
+    return rnd % n;
+  }
+
+  inline bool OneIn(result_type n) {
+    return Uniform(n) == 0;
+  }
 };
 
 }  // namespace 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 <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;
+}