[Sync] Generalize StringOrdinal to handle ordinal_in_parent field

Rename StringOrdinal to Ordinal, move it to sync/, and templatize it.
Make StringOrdinal be an instantiation of Ordinal that matches its
previous behavior.

Create NodeOrdinal, which is another instantiation of Ordinal for
the ordinal_in_parent field in SyncEntity.

Rework Ordinal to handle arbitrary byte ranges and to simplify the
interpolation code a bit.

Generalize StringOrdinal unit tests for Ordinal.

Update users of StringOrdinal to prepend syncer::.

BUG=145412
TBR=estade@chromium.org,jianli@chromium.org,brettw@chromium.org, 

Review URL: https://chromiumcodereview.appspot.com/10920017

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@155368 0039d316-1c4b-4281-b951-d872f2087c98

8 files changed, 1143 insertions, 1 deletions

diff --git a/sync/api/string_ordinal.h b/sync/api/string_ordinal.h
new file mode 100644
index 0000000..8952d47
--- /dev/null
+++ b/sync/api/string_ordinal.h
@@ -0,0 +1,47 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef SYNC_API_STRING_ORDINAL_H_
+#define SYNC_API_STRING_ORDINAL_H_
+
+#include "base/basictypes.h"
+#include "sync/internal_api/public/base/ordinal.h"
+
+namespace syncer {
+
+// A StringOrdinal is an Ordinal with range 'a'-'z' for printability
+// of its internal byte string representation.  (Think of
+// StringOrdinal as being short for PrintableStringOrdinal.)  It
+// should be used for data types that want to maintain one or more
+// orderings for nodes.
+//
+// Since StringOrdinals contain only printable characters, it is safe
+// to store as a string in a protobuf.
+
+struct StringOrdinalTraits {
+  static const uint8 kZeroDigit = 'a';
+  static const uint8 kMaxDigit = 'z';
+  static const size_t kMinLength = 1;
+};
+
+typedef Ordinal<StringOrdinalTraits> StringOrdinal;
+
+COMPILE_ASSERT(StringOrdinal::kZeroDigit == 'a',
+               StringOrdinalHasCorrectZeroDigit);
+COMPILE_ASSERT(StringOrdinal::kOneDigit == 'b',
+               StringOrdinalHasCorrectOneDigit);
+COMPILE_ASSERT(StringOrdinal::kMidDigit == 'n',
+               StringOrdinalHasCorrectMidDigit);
+COMPILE_ASSERT(StringOrdinal::kMaxDigit == 'z',
+               StringOrdinalHasCorrectMaxDigit);
+COMPILE_ASSERT(StringOrdinal::kMidDigitValue == 13,
+               StringOrdinalHasCorrectMidDigitValue);
+COMPILE_ASSERT(StringOrdinal::kMaxDigitValue == 25,
+               StringOrdinalHasCorrectMaxDigitValue);
+COMPILE_ASSERT(StringOrdinal::kRadix == 26,
+               StringOrdinalHasCorrectRadix);
+
+}  // namespace syncer
+
+#endif  // SYNC_API_STRING_ORDINAL_H_
diff --git a/sync/internal_api/public/base/node_ordinal.cc b/sync/internal_api/public/base/node_ordinal.cc
new file mode 100644
index 0000000..1b5c42c
--- /dev/null
+++ b/sync/internal_api/public/base/node_ordinal.cc
@@ -0,0 +1,47 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "sync/internal_api/public/base/node_ordinal.h"
+
+#include <algorithm>
+
+namespace syncer {
+
+NodeOrdinal Int64ToNodeOrdinal(int64 x) {
+  uint64 y = static_cast<uint64>(x);
+  y ^= 0x8000000000000000ULL;
+  std::string bytes(NodeOrdinal::kMinLength, '\x00');
+  if (y == 0) {
+    // 0 is a special case since |bytes| must not be all zeros.
+    bytes.push_back('\x80');
+  } else {
+    for (int i = 7; i >= 0; --i) {
+      bytes[i] = static_cast<uint8>(y);
+      y >>= 8;
+    }
+  }
+  NodeOrdinal ordinal(bytes);
+  DCHECK(ordinal.IsValid());
+  return ordinal;
+}
+
+int64 NodeOrdinalToInt64(const NodeOrdinal& ordinal) {
+  uint64 y = 0;
+  const std::string& s = ordinal.ToInternalValue();
+  size_t l = NodeOrdinal::kMinLength;
+  if (s.length() < l) {
+    NOTREACHED();
+    l = s.length();
+  }
+  for (size_t i = 0; i < l; ++i) {
+    const uint8 byte = s[l - i - 1];
+    y |= static_cast<uint64>(byte) << (i * 8);
+  }
+  y ^= 0x8000000000000000ULL;
+  // This is technically implementation-defined if y > INT64_MAX, so
+  // we're assuming that we're on a twos-complement machine.
+  return static_cast<int64>(y);
+}
+
+}  // namespace syncer
diff --git a/sync/internal_api/public/base/node_ordinal.h b/sync/internal_api/public/base/node_ordinal.h
new file mode 100644
index 0000000..1c49be0
--- /dev/null
+++ b/sync/internal_api/public/base/node_ordinal.h
@@ -0,0 +1,55 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef SYNC_INTERNAL_API_PUBLIC_BASE_NODE_ORDINAL_H_
+#define SYNC_INTERNAL_API_PUBLIC_BASE_NODE_ORDINAL_H_
+
+#include "base/basictypes.h"
+#include "sync/internal_api/public/base/ordinal.h"
+
+namespace syncer {
+
+// A NodeOrdinal is an Ordinal whose internal value comes from the
+// ordinal_in_parent field of SyncEntity (see sync.proto).  It uses
+// the entire uint8 range for backwards compatibility with the old
+// int64-based positioning.
+
+struct NodeOrdinalTraits {
+  static const uint8 kZeroDigit = 0;
+  static const uint8 kMaxDigit = kuint8max;
+  static const size_t kMinLength = 8;
+};
+
+typedef Ordinal<NodeOrdinalTraits> NodeOrdinal;
+
+COMPILE_ASSERT(static_cast<char>(NodeOrdinal::kZeroDigit) == '\x00',
+               NodeOrdinalHasCorrectZeroDigit);
+COMPILE_ASSERT(static_cast<char>(NodeOrdinal::kOneDigit) == '\x01',
+               NodeOrdinalHasCorrectOneDigit);
+COMPILE_ASSERT(static_cast<char>(NodeOrdinal::kMidDigit) == '\x80',
+               NodeOrdinalHasCorrectMidDigit);
+COMPILE_ASSERT(static_cast<char>(NodeOrdinal::kMaxDigit) == '\xff',
+               NodeOrdinalHasCorrectMaxDigit);
+COMPILE_ASSERT(NodeOrdinal::kMidDigitValue == 128,
+               NodeOrdinalHasCorrectMidDigitValue);
+COMPILE_ASSERT(NodeOrdinal::kMaxDigitValue == 255,
+               NodeOrdinalHasCorrectMaxDigitValue);
+COMPILE_ASSERT(NodeOrdinal::kRadix == 256,
+               NodeOrdinalHasCorrectRadix);
+
+// Converts an int64 position (usually from the position_in_parent
+// field of SyncEntity) to a NodeOrdinal.  This transformation
+// preserves the ordering relation: a < b under integer ordering if
+// and only if Int64ToNodeOrdinal(a) < Int64ToNodeOrdinal(b).
+NodeOrdinal Int64ToNodeOrdinal(int64 x);
+
+// The inverse of Int64ToNodeOrdinal.  This conversion is, in general,
+// lossy: NodeOrdinals can have arbitrary fidelity, while numeric
+// positions contain only 64 bits of information (in fact, this is the
+// reason we've moved away from them).
+int64 NodeOrdinalToInt64(const NodeOrdinal& ordinal);
+
+}  // namespace syncer
+
+#endif  // SYNC_INTERNAL_API_PUBLIC_BASE_NODE_ORDINAL_H_
diff --git a/sync/internal_api/public/base/node_ordinal_unittest.cc b/sync/internal_api/public/base/node_ordinal_unittest.cc
new file mode 100644
index 0000000..d951cb7
--- /dev/null
+++ b/sync/internal_api/public/base/node_ordinal_unittest.cc
@@ -0,0 +1,125 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/basictypes.h"
+#include "sync/internal_api/public/base/node_ordinal.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+#include <algorithm>
+#include <cstddef>
+
+namespace syncer {
+
+namespace {
+
+const int64 kTestValues[] = {
+  0LL,
+  1LL, -1LL,
+  2LL, -2LL,
+  3LL, -3LL,
+  0x79LL, -0x79LL,
+  0x80LL, -0x80LL,
+  0x81LL, -0x81LL,
+  0xFELL, -0xFELL,
+  0xFFLL, -0xFFLL,
+  0x100LL, -0x100LL,
+  0x101LL, -0x101LL,
+  0xFA1AFELL, -0xFA1AFELL,
+  0xFFFFFFFELL, -0xFFFFFFFELL,
+  0xFFFFFFFFLL, -0xFFFFFFFFLL,
+  0x100000000LL, -0x100000000LL,
+  0x100000001LL, -0x100000001LL,
+  0xFFFFFFFFFFLL, -0xFFFFFFFFFFLL,
+  0x112358132134LL, -0x112358132134LL,
+  0xFEFFBEEFABC1234LL, -0xFEFFBEEFABC1234LL,
+  kint64max,
+  kint64min,
+  kint64min + 1,
+  kint64max - 1
+};
+
+const size_t kNumTestValues = arraysize(kTestValues);
+
+// Convert each test value to an ordinal.  All ordinals should be
+// valid.
+TEST(NodeOrdinalTest, IsValid) {
+  for (size_t i = 0; i < kNumTestValues; ++i) {
+    const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]);
+    EXPECT_TRUE(ordinal.IsValid()) << "i = " << i;
+  }
+}
+
+// Convert each test value to an ordinal.  All ordinals should have
+// 8-byte strings, except for kint64min, which should have a 9-byte
+// string.
+TEST(NodeOrdinalTest, Size) {
+  EXPECT_EQ(9U, Int64ToNodeOrdinal(kint64min).ToInternalValue().size());
+
+  for (size_t i = 0; i < kNumTestValues; ++i) {
+    if (kTestValues[i] == kint64min) {
+      continue;
+    }
+    const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]);
+    EXPECT_EQ(8U, ordinal.ToInternalValue().size()) << "i = " << i;
+  }
+}
+
+// Convert each test value to an ordinal and back.  That resulting
+// value should be equal to the original value.
+TEST(NodeOrdinalTest, PositionToOrdinalToPosition) {
+  for (size_t i = 0; i < kNumTestValues; ++i) {
+    const int64 expected_value = kTestValues[i];
+    const NodeOrdinal ordinal = Int64ToNodeOrdinal(expected_value);
+    const int64 value = NodeOrdinalToInt64(ordinal);
+    EXPECT_EQ(expected_value, value) << "i = " << i;
+  }
+}
+
+template <typename T, typename LessThan = std::less<T> >
+class IndexedLessThan {
+ public:
+  IndexedLessThan(const T* values) : values_(values) {}
+
+  bool operator()(int i1, int i2) {
+    return less_than_(values_[i1], values_[i2]);
+  }
+
+ private:
+  const T* values_;
+  LessThan less_than_;
+};
+
+// Sort kTestValues by int64 value and then sort it by NodeOrdinal
+// value.  kTestValues should not already be sorted (by either
+// comparator) and the two orderings should be the same.
+TEST(NodeOrdinalTest, ConsistentOrdering) {
+  NodeOrdinal ordinals[kNumTestValues];
+  std::vector<int> original_ordering(kNumTestValues);
+  std::vector<int> int64_ordering(kNumTestValues);
+  std::vector<int> ordinal_ordering(kNumTestValues);
+  for (size_t i = 0; i < kNumTestValues; ++i) {
+    ordinals[i] = Int64ToNodeOrdinal(kTestValues[i]);
+    original_ordering[i] = int64_ordering[i] = ordinal_ordering[i] = i;
+  }
+
+  std::sort(int64_ordering.begin(), int64_ordering.end(),
+            IndexedLessThan<int64>(kTestValues));
+  std::sort(ordinal_ordering.begin(), ordinal_ordering.end(),
+            IndexedLessThan<NodeOrdinal, NodeOrdinal::LessThanFn>(ordinals));
+  EXPECT_NE(original_ordering, int64_ordering);
+  EXPECT_EQ(int64_ordering, ordinal_ordering);
+}
+
+// Create two NodeOrdinals and create another one between them.  It
+// should lie halfway between them.
+TEST(NodeOrdinalTest, CreateBetween) {
+  const NodeOrdinal ordinal1("\1\1\1\1\1\1\1\1");
+  const NodeOrdinal ordinal2("\1\1\1\1\1\1\1\3");
+  EXPECT_EQ("\1\1\1\1\1\1\1\2",
+            ordinal1.CreateBetween(ordinal2).ToInternalValue());
+}
+
+}  // namespace
+
+}  // namespace syncer
diff --git a/sync/internal_api/public/base/ordinal.h b/sync/internal_api/public/base/ordinal.h
new file mode 100644
index 0000000..9189759
--- /dev/null
+++ b/sync/internal_api/public/base/ordinal.h
@@ -0,0 +1,486 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_
+#define SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_
+
+#include <algorithm>
+#include <cstddef>
+#include <string>
+
+#include "base/basictypes.h"
+#include "base/json/string_escape.h"
+#include "base/logging.h"
+
+namespace syncer {
+
+// An Ordinal<T> is an object that can be used for ordering. The
+// Ordinal<T> class has an unbounded dense strict total order, which
+// mean for any Ordinal<T>s a, b and c:
+//
+//  - a < b and b < c implies a < c (transitivity);
+//  - exactly one of a < b, b < a and a = b holds (trichotomy);
+//  - if a < b, there is a Ordinal<T> x such that a < x < b (density);
+//  - there are Ordinals<T> x and y such that x < a < y (unboundedness).
+//
+// This means that when Ordinal<T> is used for sorting a list, if any
+// item changes its position in the list, only its Ordinal<T> value
+// has to change to represent the new order, and all the other values
+// can stay the same.
+//
+// An Ordinal<T> is internally represented as an array of bytes, so it
+// can be serialized to and deserialized from disk.
+//
+// The Traits class should look like the following:
+//
+//   // Don't forget to #include "base/basictypes.h".
+//   struct MyOrdinalTraits {
+//     // There must be at least two distinct values greater than kZeroDigit
+//     // and less than kMaxDigit.
+//     static const uint8 kZeroDigit = '0';
+//     static const uint8 kMaxDigit = '9';
+//     // kMinLength must be positive.
+//     static const size_t kMinLength = 1;
+//   };
+//
+// An Ordinal<T> is valid iff its corresponding string has at least
+// kMinLength characters, does not contain any characters less than
+// kZeroDigit or greater than kMaxDigit, is not all zero digits, and
+// does not have any unnecessary trailing zero digits.
+//
+// Note that even if the native char type is signed, strings still
+// compare as if their they are unsigned.  (This is explicitly in
+// C++11 but not in C++98, even though all implementations do so
+// anyway in practice.)  Thus, it is safe to use any byte range for
+// Ordinal<T>s.
+template <typename Traits>
+class Ordinal {
+ public:
+  // Functors for use with STL algorithms and containers.
+  class LessThanFn {
+   public:
+    LessThanFn();
+
+    bool operator()(const Ordinal<Traits>& lhs,
+                    const Ordinal<Traits>& rhs) const;
+  };
+
+  class EqualsFn {
+   public:
+    EqualsFn();
+
+    bool operator()(const Ordinal<Traits>& lhs,
+                    const Ordinal<Traits>& rhs) const;
+  };
+
+  // Creates an Ordinal from the given string of bytes. The Ordinal
+  // may be valid or invalid.
+  explicit Ordinal(const std::string& bytes);
+
+  // Creates an invalid Ordinal.
+  Ordinal();
+
+  // Creates a valid initial Ordinal. This is called to create the first
+  // element of Ordinal list (i.e. before we have any other values we can
+  // generate from).
+  static Ordinal CreateInitialOrdinal();
+
+  // Returns true iff this Ordinal is valid.  This takes constant
+  // time.
+  bool IsValid() const;
+
+  // Returns true iff |*this| == |other| or |*this| and |other|
+  // are both invalid.
+  bool EqualsOrBothInvalid(const Ordinal& other) const;
+
+  // Returns a printable string representation of the Ordinal suitable
+  // for logging.
+  std::string ToDebugString() const;
+
+  // All remaining functions can only be called if IsValid() holds.
+  // It is an error to call them if IsValid() is false.
+
+  // Order-related functions.
+
+  // Returns true iff |*this| < |other|.
+  bool LessThan(const Ordinal& other) const;
+
+  // Returns true iff |*this| > |other|.
+  bool GreaterThan(const Ordinal& other) const;
+
+  // Returns true iff |*this| == |other| (i.e. |*this| < |other| and
+  // |other| < |*this| are both false).
+  bool Equals(const Ordinal& other) const;
+
+  // Given |*this| != |other|, returns a Ordinal x such that
+  // min(|*this|, |other|) < x < max(|*this|, |other|). It is an error
+  // to call this function when |*this| == |other|.
+  Ordinal CreateBetween(const Ordinal& other) const;
+
+  // Returns a Ordinal |x| such that |x| < |*this|.
+  Ordinal CreateBefore() const;
+
+  // Returns a Ordinal |x| such that |*this| < |x|.
+  Ordinal CreateAfter() const;
+
+  // Returns the string of bytes representing the Ordinal.  It is
+  // guaranteed that an Ordinal constructed from the returned string
+  // will be valid.
+  std::string ToInternalValue() const;
+
+  // Use of copy constructor and default assignment for this class is allowed.
+
+  // Constants for Ordinal digits.
+  static const uint8 kZeroDigit = Traits::kZeroDigit;
+  static const uint8 kMaxDigit = Traits::kMaxDigit;
+  static const size_t kMinLength = Traits::kMinLength;
+  static const uint8 kOneDigit = kZeroDigit + 1;
+  static const uint8 kMidDigit = kOneDigit + (kMaxDigit - kOneDigit) / 2;
+  static const unsigned int kMidDigitValue = kMidDigit - kZeroDigit;
+  static const unsigned int kMaxDigitValue = kMaxDigit - kZeroDigit;
+  static const unsigned int kRadix = kMaxDigitValue + 1;
+
+  COMPILE_ASSERT(kOneDigit > kZeroDigit, OrdinalOneDigitGreaterThanMinDigit);
+  COMPILE_ASSERT(kMidDigit > kOneDigit, OrdinalMidDigitGreaterThanOneDigit);
+  COMPILE_ASSERT(kMaxDigit > kMidDigit, OrdinalMaxDigitGreaterThanMidDigit);
+  COMPILE_ASSERT(kMinLength > 0, OrdinalMinLengthIsPositive);
+  COMPILE_ASSERT(kMidDigitValue > 1, OrdinalMidDigitValueGreaterThanOne);
+  COMPILE_ASSERT(kMaxDigitValue > kMidDigitValue,
+                 OrdinalMaxDigitValueGreaterThanMidDigitValue);
+  COMPILE_ASSERT(kRadix == kMaxDigitValue + 1,
+                 OrdinalRadixIsMaxDigitValuePlusOne);
+
+ private:
+  // Returns true iff the given byte string satisfies the criteria for
+  // a valid Ordinal.
+  static bool IsValidOrdinalBytes(const std::string& bytes);
+
+  // Returns the length that bytes.substr(0, length) would be with
+  // trailing zero digits removed.
+  static size_t GetLengthWithoutTrailingZeroDigits(
+      const std::string& bytes,
+      size_t length);
+
+  // Returns the digit at position i, padding with zero digits if
+  // required.
+  static uint8 GetDigit(const std::string& bytes, size_t i);
+
+  // Returns the digit value at position i, padding with 0 if required.
+  static int GetDigitValue(const std::string& bytes, size_t i);
+
+  // Adds the given value to |bytes| at position i, carrying when
+  // necessary.  Returns the left-most carry.
+  static int AddDigitValue(std::string* bytes, size_t i, int digit_value);
+
+  // Returns the proper length |bytes| should be resized to, i.e. the
+  // smallest length such that |bytes| is still greater than
+  // |lower_bound| and is still valid.  |bytes| should be greater than
+  // |lower_bound|.
+  static size_t GetProperLength(const std::string& lower_bound,
+                                const std::string& bytes);
+
+  // Compute the midpoint ordinal byte string that is between |start|
+  // and |end|.
+  static std::string ComputeMidpoint(const std::string& start,
+                                     const std::string& end);
+
+  // Create a Ordinal that is lexigraphically greater than |start| and
+  // lexigraphically less than |end|. The returned Ordinal will be roughly
+  // between |start| and |end|.
+  static Ordinal<Traits> CreateOrdinalBetween(const Ordinal<Traits>& start,
+                                              const Ordinal<Traits>& end);
+
+  // The internal byte string representation of the Ordinal.  Never
+  // changes after construction except for assignment.
+  std::string bytes_;
+
+  // A cache of the result of IsValidOrdinalBytes(bytes_).
+  bool is_valid_;
+};
+
+template <typename Traits> const uint8 Ordinal<Traits>::kZeroDigit;
+template <typename Traits> const uint8 Ordinal<Traits>::kMaxDigit;
+template <typename Traits> const size_t Ordinal<Traits>::kMinLength;
+template <typename Traits> const uint8 Ordinal<Traits>::kOneDigit;
+template <typename Traits> const uint8 Ordinal<Traits>::kMidDigit;
+template <typename Traits> const unsigned int Ordinal<Traits>::kMidDigitValue;
+template <typename Traits> const unsigned int Ordinal<Traits>::kMaxDigitValue;
+template <typename Traits> const unsigned int Ordinal<Traits>::kRadix;
+
+template <typename Traits>
+Ordinal<Traits>::LessThanFn::LessThanFn() {}
+
+template <typename Traits>
+bool Ordinal<Traits>::LessThanFn::operator()(const Ordinal<Traits>& lhs,
+                                             const Ordinal<Traits>& rhs) const {
+  return lhs.LessThan(rhs);
+}
+
+template <typename Traits>
+Ordinal<Traits>::EqualsFn::EqualsFn() {}
+
+template <typename Traits>
+bool Ordinal<Traits>::EqualsFn::operator()(const Ordinal<Traits>& lhs,
+                                           const Ordinal<Traits>& rhs) const {
+  return lhs.Equals(rhs);
+}
+
+template <typename Traits>
+Ordinal<Traits>::Ordinal(const std::string& bytes)
+    : bytes_(bytes),
+      is_valid_(IsValidOrdinalBytes(bytes_)) {}
+
+template <typename Traits>
+Ordinal<Traits>::Ordinal() : is_valid_(false) {}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateInitialOrdinal() {
+  std::string bytes(Traits::kMinLength, kZeroDigit);
+  bytes[0] = kMidDigit;
+  return Ordinal(bytes);
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::IsValid() const {
+  DCHECK_EQ(IsValidOrdinalBytes(bytes_), is_valid_);
+  return is_valid_;
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::EqualsOrBothInvalid(const Ordinal& other) const {
+  if (!IsValid() && !other.IsValid())
+    return true;
+
+  if (!IsValid() || !other.IsValid())
+    return false;
+
+  return Equals(other);
+}
+
+template <typename Traits>
+std::string Ordinal<Traits>::ToDebugString() const {
+  std::string debug_string;
+  base::JsonDoubleQuote(bytes_, false /* put_in_quotes */, &debug_string);
+  if (!is_valid_) {
+    debug_string = "INVALID[" + debug_string + "]";
+  }
+  return debug_string;
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::LessThan(const Ordinal& other) const {
+  CHECK(IsValid());
+  CHECK(other.IsValid());
+  return bytes_ < other.bytes_;
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::GreaterThan(const Ordinal& other) const {
+  CHECK(IsValid());
+  CHECK(other.IsValid());
+  return bytes_ > other.bytes_;
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::Equals(const Ordinal& other) const {
+  CHECK(IsValid());
+  CHECK(other.IsValid());
+  return bytes_ == other.bytes_;
+}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateBetween(const Ordinal& other) const {
+  CHECK(IsValid());
+  CHECK(other.IsValid());
+  CHECK(!Equals(other));
+
+  if (LessThan(other)) {
+    return CreateOrdinalBetween(*this, other);
+  } else {
+    return CreateOrdinalBetween(other, *this);
+  }
+}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateBefore() const {
+  CHECK(IsValid());
+  // Create the smallest valid Ordinal of the appropriate length
+  // to be the minimum boundary.
+  const size_t length = bytes_.length();
+  std::string start(length, kZeroDigit);
+  start[length - 1] = kOneDigit;
+  if (start == bytes_) {
+    start[length - 1] = kZeroDigit;
+    start += kOneDigit;
+  }
+
+  // Even though |start| is already a valid Ordinal that is less
+  // than |*this|, we don't return it because we wouldn't have much space in
+  // front of it to insert potential future values.
+  return CreateBetween(Ordinal(start));
+}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateAfter() const {
+  CHECK(IsValid());
+  // Create the largest valid Ordinal of the appropriate length to be
+  // the maximum boundary.
+  std::string end(bytes_.length(), kMaxDigit);
+  if (end == bytes_)
+    end += kMaxDigit;
+
+  // Even though |end| is already a valid Ordinal that is greater than
+  // |*this|, we don't return it because we wouldn't have much space after
+  // it to insert potential future values.
+  return CreateBetween(Ordinal(end));
+}
+
+template <typename Traits>
+std::string Ordinal<Traits>::ToInternalValue() const {
+  CHECK(IsValid());
+  return bytes_;
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::IsValidOrdinalBytes(const std::string& bytes) {
+  const size_t length = bytes.length();
+  if (length < kMinLength)
+    return false;
+
+  bool found_non_zero = false;
+  for (size_t i = 0; i < length; ++i) {
+    const uint8 byte = bytes[i];
+    if (byte < kZeroDigit || byte > kMaxDigit)
+      return false;
+    if (byte > kZeroDigit)
+      found_non_zero = true;
+  }
+  if (!found_non_zero)
+    return false;
+
+  if (length > kMinLength) {
+    const uint8 last_byte = bytes[length - 1];
+    if (last_byte == kZeroDigit)
+      return false;
+  }
+
+  return true;
+}
+
+template <typename Traits>
+size_t Ordinal<Traits>::GetLengthWithoutTrailingZeroDigits(
+    const std::string& bytes, size_t length) {
+  DCHECK(!bytes.empty());
+  DCHECK_GT(length, 0U);
+
+  size_t end_position =
+      bytes.find_last_not_of(static_cast<char>(kZeroDigit), length - 1);
+
+  // If no non kZeroDigit is found then the string is a string of all zeros
+  // digits so we return 0 as the correct length.
+  if (end_position == std::string::npos)
+    return 0;
+
+  return end_position + 1;
+}
+
+template <typename Traits>
+uint8 Ordinal<Traits>::GetDigit(const std::string& bytes, size_t i) {
+  return (i < bytes.length()) ? bytes[i] : kZeroDigit;
+}
+
+template <typename Traits>
+int Ordinal<Traits>::GetDigitValue(const std::string& bytes, size_t i) {
+  return GetDigit(bytes, i) - kZeroDigit;
+}
+
+template <typename Traits>
+int Ordinal<Traits>::AddDigitValue(std::string* bytes,
+                                   size_t i, int digit_value) {
+  DCHECK_GE(i, 0U);
+  DCHECK_LT(i, bytes->length());
+
+  for (int j = i; j >= 0 && digit_value > 0; --j) {
+    int byte_j_value = GetDigitValue(*bytes, j) + digit_value;
+    digit_value = byte_j_value / kRadix;
+    DCHECK_LE(digit_value, 1);
+    byte_j_value %= kRadix;
+    (*bytes)[j] = static_cast<char>(kZeroDigit + byte_j_value);
+  }
+  return digit_value;
+}
+
+template <typename Traits>
+size_t Ordinal<Traits>::GetProperLength(const std::string& lower_bound,
+                                        const std::string& bytes) {
+  CHECK_GT(bytes, lower_bound);
+
+  size_t drop_length =
+      GetLengthWithoutTrailingZeroDigits(bytes, bytes.length());
+  // See if the |ordinal| can be truncated after its last non-zero
+  // digit without affecting the ordering.
+  if (drop_length > kMinLength) {
+    size_t truncated_length =
+        GetLengthWithoutTrailingZeroDigits(bytes, drop_length - 1);
+
+    if (truncated_length > 0 &&
+        bytes.compare(0, truncated_length, lower_bound) > 0)
+      drop_length = truncated_length;
+  }
+  return std::max(drop_length, kMinLength);
+}
+
+template <typename Traits>
+std::string Ordinal<Traits>::ComputeMidpoint(
+    const std::string& start,
+    const std::string& end) {
+  size_t max_size = std::max(start.length(), end.length()) + 1;
+  std::string midpoint(max_size, kZeroDigit);
+
+  // Perform the operation (start + end) / 2 left-to-right by
+  // maintaining a "forward carry" which is either 0 or
+  // kMidDigitValue.  AddDigitValue() is in general O(n), but this
+  // operation is still O(n) despite that; calls to AddDigitValue()
+  // will overflow at most to the last position where AddDigitValue()
+  // last overflowed.
+  int forward_carry = 0;
+  for (size_t i = 0; i < max_size; ++i) {
+    const int sum_value = GetDigitValue(start, i) + GetDigitValue(end, i);
+    const int digit_value = sum_value / 2 + forward_carry;
+    // AddDigitValue returning a non-zero carry would imply that
+    // midpoint[0] >= kMaxDigit, which one can show is impossible.
+    CHECK_EQ(AddDigitValue(&midpoint, i, digit_value), 0);
+    forward_carry = (sum_value % 2 == 1) ? kMidDigitValue : 0;
+  }
+  DCHECK_EQ(forward_carry, 0);
+
+  return midpoint;
+}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateOrdinalBetween(
+    const Ordinal<Traits>& start,
+    const Ordinal<Traits>& end) {
+  CHECK(start.IsValid());
+  CHECK(end.IsValid());
+  CHECK(start.LessThan(end));
+  const std::string& start_bytes = start.ToInternalValue();
+  const std::string& end_bytes = end.ToInternalValue();
+  DCHECK_LT(start_bytes, end_bytes);
+
+  std::string midpoint = ComputeMidpoint(start_bytes, end_bytes);
+  const size_t proper_length = GetProperLength(start_bytes, midpoint);
+  midpoint.resize(proper_length, kZeroDigit);
+
+  DCHECK_GT(midpoint, start_bytes);
+  DCHECK_LT(midpoint, end_bytes);
+
+  Ordinal<Traits> midpoint_ordinal(midpoint);
+  DCHECK(midpoint_ordinal.IsValid());
+  return midpoint_ordinal;
+}
+
+}  // namespace syncer
+
+#endif  // SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_
diff --git a/sync/internal_api/public/base/ordinal_unittest.cc b/sync/internal_api/public/base/ordinal_unittest.cc
new file mode 100644
index 0000000..20a6d19
--- /dev/null
+++ b/sync/internal_api/public/base/ordinal_unittest.cc
@@ -0,0 +1,376 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "base/basictypes.h"
+#include "sync/internal_api/public/base/ordinal.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+#include <algorithm>
+#include <cctype>
+#include <cstddef>
+#include <string>
+#include <vector>
+
+namespace syncer {
+
+namespace {
+
+struct TestOrdinalTraits {
+  static const uint8 kZeroDigit = '0';
+  static const uint8 kMaxDigit = '3';
+  static const size_t kMinLength = 1;
+};
+
+struct LongOrdinalTraits {
+  static const uint8 kZeroDigit = '0';
+  static const uint8 kMaxDigit = '9';
+  static const size_t kMinLength = 5;
+};
+
+struct LargeOrdinalTraits {
+  static const uint8 kZeroDigit = 0;
+  static const uint8 kMaxDigit = kuint8max;
+  static const size_t kMinLength = 1;
+};
+
+typedef Ordinal<TestOrdinalTraits> TestOrdinal;
+typedef Ordinal<LongOrdinalTraits> LongOrdinal;
+typedef Ordinal<LargeOrdinalTraits> LargeOrdinal;
+
+COMPILE_ASSERT(TestOrdinal::kZeroDigit == '0',
+               TestOrdinalHasCorrectZeroDigit);
+COMPILE_ASSERT(TestOrdinal::kOneDigit == '1',
+               TestOrdinalHasCorrectOneDigit);
+COMPILE_ASSERT(TestOrdinal::kMidDigit == '2',
+               TestOrdinalHasCorrectMidDigit);
+COMPILE_ASSERT(TestOrdinal::kMaxDigit == '3',
+               TestOrdinalHasCorrectMaxDigit);
+COMPILE_ASSERT(TestOrdinal::kMidDigitValue == 2,
+               TestOrdinalHasCorrectMidDigitValue);
+COMPILE_ASSERT(TestOrdinal::kMaxDigitValue == 3,
+               TestOrdinalHasCorrectMaxDigitValue);
+COMPILE_ASSERT(TestOrdinal::kRadix == 4,
+               TestOrdinalHasCorrectRadix);
+
+COMPILE_ASSERT(LongOrdinal::kZeroDigit == '0',
+               LongOrdinalkZeroDigit_incorrect);
+COMPILE_ASSERT(LongOrdinal::kOneDigit == '1',
+               LongOrdinalkOneDigit_incorrect);
+COMPILE_ASSERT(LongOrdinal::kMidDigit == '5',
+               LongOrdinalkMidDigit_incorrect);
+COMPILE_ASSERT(LongOrdinal::kMaxDigit == '9',
+               LongOrdinalkMaxDigit_incorrect);
+COMPILE_ASSERT(LongOrdinal::kMidDigitValue == 5,
+               LongOrdinalkMidDigitValue_incorrect);
+COMPILE_ASSERT(LongOrdinal::kMaxDigitValue == 9,
+               LongOrdinalkMaxDigitValue_incorrect);
+COMPILE_ASSERT(LongOrdinal::kRadix == 10,
+               LongOrdinalkRadix_incorrect);
+
+COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kZeroDigit) == '\x00',
+               LargeOrdinalkZeroDigit_incorrect);
+COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kOneDigit) == '\x01',
+               LargeOrdinalkOneDigit_incorrect);
+COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kMidDigit) == '\x80',
+               LargeOrdinalkMidDigit_incorrect);
+COMPILE_ASSERT(static_cast<char>(LargeOrdinal::kMaxDigit) == '\xff',
+               LargeOrdinalkMaxDigit_incorrect);
+COMPILE_ASSERT(LargeOrdinal::kMidDigitValue == 128,
+               LargeOrdinalkMidDigitValue_incorrect);
+COMPILE_ASSERT(LargeOrdinal::kMaxDigitValue == 255,
+               LargeOrdinalkMaxDigitValue_incorrect);
+COMPILE_ASSERT(LargeOrdinal::kRadix == 256,
+               LargeOrdinalkRadix_incorrect);
+
+// Create Ordinals that satisfy all but one criterion for validity.
+// IsValid() should return false for all of them.
+TEST(Ordinal, Invalid) {
+  // Length criterion.
+  EXPECT_FALSE(TestOrdinal("").IsValid());
+  EXPECT_FALSE(LongOrdinal("0001").IsValid());
+
+  const char kBeforeZero[] = { '0' - 1, '\0' };
+  const char kAfterNine[] = { '9' + 1, '\0' };
+
+  // Character criterion.
+  EXPECT_FALSE(TestOrdinal(kBeforeZero).IsValid());
+  EXPECT_FALSE(TestOrdinal("4").IsValid());
+  EXPECT_FALSE(LongOrdinal(std::string("0000") + kBeforeZero).IsValid());
+  EXPECT_FALSE(LongOrdinal(std::string("0000") + kAfterNine).IsValid());
+
+  // Zero criterion.
+  EXPECT_FALSE(TestOrdinal("0").IsValid());
+  EXPECT_FALSE(TestOrdinal("00000").IsValid());
+
+  // Trailing zero criterion.
+  EXPECT_FALSE(TestOrdinal("10").IsValid());
+  EXPECT_FALSE(TestOrdinal("111110").IsValid());
+}
+
+// Create Ordinals that satisfy all criteria for validity.
+// IsValid() should return true for all of them.
+TEST(Ordinal, Valid) {
+  // Length criterion.
+  EXPECT_TRUE(TestOrdinal("1").IsValid());
+  EXPECT_TRUE(LongOrdinal("10000").IsValid());
+}
+
+// Create Ordinals from CreateInitialOrdinal.  They should be valid
+// and close to the middle of the range.
+TEST(Ordinal, CreateInitialOrdinal) {
+  const TestOrdinal& ordinal1 = TestOrdinal::CreateInitialOrdinal();
+  const LongOrdinal& ordinal2 = LongOrdinal::CreateInitialOrdinal();
+  ASSERT_TRUE(ordinal1.IsValid());
+  ASSERT_TRUE(ordinal2.IsValid());
+  EXPECT_TRUE(ordinal1.Equals(TestOrdinal("2")));
+  EXPECT_TRUE(ordinal2.Equals(LongOrdinal("50000")));
+}
+
+// Create an invalid and a valid Ordinal.  EqualsOrBothInvalid should
+// return true if called reflexively and false otherwise.
+TEST(Ordinal, EqualsOrBothInvalid) {
+  const TestOrdinal& valid_ordinal = TestOrdinal::CreateInitialOrdinal();
+  const TestOrdinal invalid_ordinal;
+
+  EXPECT_TRUE(valid_ordinal.EqualsOrBothInvalid(valid_ordinal));
+  EXPECT_TRUE(invalid_ordinal.EqualsOrBothInvalid(invalid_ordinal));
+  EXPECT_FALSE(invalid_ordinal.EqualsOrBothInvalid(valid_ordinal));
+  EXPECT_FALSE(valid_ordinal.EqualsOrBothInvalid(invalid_ordinal));
+}
+
+// Create three Ordinals in order.  LessThan should return values
+// consistent with that order.
+TEST(Ordinal, LessThan) {
+  const TestOrdinal small_ordinal("1");
+  const TestOrdinal middle_ordinal("2");
+  const TestOrdinal big_ordinal("3");
+
+  EXPECT_FALSE(small_ordinal.LessThan(small_ordinal));
+  EXPECT_TRUE(small_ordinal.LessThan(middle_ordinal));
+  EXPECT_TRUE(small_ordinal.LessThan(big_ordinal));
+
+  EXPECT_FALSE(middle_ordinal.LessThan(small_ordinal));
+  EXPECT_FALSE(middle_ordinal.LessThan(middle_ordinal));
+  EXPECT_TRUE(middle_ordinal.LessThan(big_ordinal));
+
+  EXPECT_FALSE(big_ordinal.LessThan(small_ordinal));
+  EXPECT_FALSE(big_ordinal.LessThan(middle_ordinal));
+  EXPECT_FALSE(big_ordinal.LessThan(big_ordinal));
+}
+
+// Create two single-digit ordinals with byte values 0 and 255.  The
+// former should compare as less than the latter, even though the
+// native char type may be signed.
+TEST(Ordinal, LessThanLarge) {
+  const LargeOrdinal small_ordinal("\x01");
+  const LargeOrdinal big_ordinal("\xff");
+
+  EXPECT_TRUE(small_ordinal.LessThan(big_ordinal));
+}
+
+// Create three Ordinals in order.  GreaterThan should return values
+// consistent with that order.
+TEST(Ordinal, GreaterThan) {
+  const LongOrdinal small_ordinal("10000");
+  const LongOrdinal middle_ordinal("55555");
+  const LongOrdinal big_ordinal("99999");
+
+  EXPECT_FALSE(small_ordinal.GreaterThan(small_ordinal));
+  EXPECT_FALSE(small_ordinal.GreaterThan(middle_ordinal));
+  EXPECT_FALSE(small_ordinal.GreaterThan(big_ordinal));
+
+  EXPECT_TRUE(middle_ordinal.GreaterThan(small_ordinal));
+  EXPECT_FALSE(middle_ordinal.GreaterThan(middle_ordinal));
+  EXPECT_FALSE(middle_ordinal.GreaterThan(big_ordinal));
+
+  EXPECT_TRUE(big_ordinal.GreaterThan(small_ordinal));
+  EXPECT_TRUE(big_ordinal.GreaterThan(middle_ordinal));
+  EXPECT_FALSE(big_ordinal.GreaterThan(big_ordinal));
+}
+
+// Create two valid Ordinals.  Equals should return true only when
+// called reflexively.
+TEST(Ordinal, Equals) {
+  const TestOrdinal ordinal1("1");
+  const TestOrdinal ordinal2("2");
+
+  EXPECT_TRUE(ordinal1.Equals(ordinal1));
+  EXPECT_FALSE(ordinal1.Equals(ordinal2));
+
+  EXPECT_FALSE(ordinal2.Equals(ordinal1));
+  EXPECT_TRUE(ordinal2.Equals(ordinal2));
+}
+
+// Create some valid ordinals from some byte strings.
+// ToInternalValue() should return the original byte string.
+TEST(OrdinalTest, ToInternalValue) {
+  EXPECT_EQ("2", TestOrdinal("2").ToInternalValue());
+  EXPECT_EQ("12345", LongOrdinal("12345").ToInternalValue());
+  EXPECT_EQ("\1\2\3\4\5", LargeOrdinal("\1\2\3\4\5").ToInternalValue());
+}
+
+bool IsNonEmptyPrintableString(const std::string& str) {
+  if (str.empty())
+    return false;
+  for (size_t i = 0; i < str.length(); ++i) {
+    if (!isprint(str[i]))
+      return false;
+  }
+  return true;
+}
+
+// Create some invalid/valid ordinals.  ToDebugString() should always
+// return a non-empty printable string.
+TEST(OrdinalTest, ToDebugString) {
+  EXPECT_TRUE(
+      IsNonEmptyPrintableString(TestOrdinal().ToDebugString()));
+  EXPECT_TRUE(
+      IsNonEmptyPrintableString(TestOrdinal("invalid string").ToDebugString()));
+  EXPECT_TRUE(
+      IsNonEmptyPrintableString(TestOrdinal("2").ToDebugString()));
+  EXPECT_TRUE(
+      IsNonEmptyPrintableString(LongOrdinal("12345").ToDebugString()));
+  EXPECT_TRUE(
+      IsNonEmptyPrintableString(LargeOrdinal("\1\2\3\4\5").ToDebugString()));
+}
+
+// Create three Ordinals in order.  LessThanFn should return values
+// consistent with that order.
+TEST(Ordinal, LessThanFn) {
+  const TestOrdinal small_ordinal("1");
+  const TestOrdinal middle_ordinal("2");
+  const TestOrdinal big_ordinal("3");
+
+  const TestOrdinal::LessThanFn less_than;
+
+  EXPECT_FALSE(less_than(small_ordinal, small_ordinal));
+  EXPECT_TRUE(less_than(small_ordinal, middle_ordinal));
+  EXPECT_TRUE(less_than(small_ordinal, big_ordinal));
+
+  EXPECT_FALSE(less_than(middle_ordinal, small_ordinal));
+  EXPECT_FALSE(less_than(middle_ordinal, middle_ordinal));
+  EXPECT_TRUE(less_than(middle_ordinal, big_ordinal));
+
+  EXPECT_FALSE(less_than(big_ordinal, small_ordinal));
+  EXPECT_FALSE(less_than(big_ordinal, middle_ordinal));
+  EXPECT_FALSE(less_than(big_ordinal, big_ordinal));
+}
+
+template <typename Traits>
+std::string GetBetween(const std::string& ordinal_string1,
+                       const std::string& ordinal_string2) {
+  const Ordinal<Traits> ordinal1(ordinal_string1);
+  const Ordinal<Traits> ordinal2(ordinal_string2);
+  const Ordinal<Traits> between1 = ordinal1.CreateBetween(ordinal2);
+  const Ordinal<Traits> between2 = ordinal2.CreateBetween(ordinal1);
+  EXPECT_TRUE(between1.Equals(between2));
+  return between1.ToInternalValue();
+}
+
+// Create some Ordinals from single-digit strings.  Given two strings
+// from this set, CreateBetween should return an Ordinal roughly between
+// them that are also single-digit when possible.
+TEST(Ordinal, CreateBetweenSingleDigit) {
+  EXPECT_EQ("2", GetBetween<TestOrdinal>("1", "3"));
+  EXPECT_EQ("12", GetBetween<TestOrdinal>("1", "2"));
+  EXPECT_EQ("22", GetBetween<TestOrdinal>("2", "3"));
+}
+
+// Create some Ordinals from strings of various lengths.  Given two
+// strings from this set, CreateBetween should return an Ordinal roughly
+// between them that have as few digits as possible.
+TEST(Ordinal, CreateBetweenDifferentLengths) {
+  EXPECT_EQ("102", GetBetween<TestOrdinal>("1", "11"));
+  EXPECT_EQ("2", GetBetween<TestOrdinal>("1", "31"));
+  EXPECT_EQ("132", GetBetween<TestOrdinal>("13", "2"));
+  EXPECT_EQ("2", GetBetween<TestOrdinal>("10001", "3"));
+  EXPECT_EQ("20000", GetBetween<LongOrdinal>("10001", "30000"));
+  EXPECT_EQ("2", GetBetween<TestOrdinal>("10002", "3"));
+  EXPECT_EQ("20001", GetBetween<LongOrdinal>("10002", "30000"));
+  EXPECT_EQ("2", GetBetween<TestOrdinal>("1", "30002"));
+  EXPECT_EQ("20001", GetBetween<LongOrdinal>("10000", "30002"));
+}
+
+// Create some Ordinals specifically designed to trigger overflow
+// cases.  Given two strings from this set, CreateBetween should
+// return an Ordinal roughly between them that have as few digits as
+// possible.
+TEST(Ordinal, CreateBetweenOverflow) {
+  EXPECT_EQ("03", GetBetween<TestOrdinal>("01", "11"));
+  EXPECT_EQ("13", GetBetween<TestOrdinal>("11", "21"));
+  EXPECT_EQ("113", GetBetween<TestOrdinal>("111", "121"));
+  EXPECT_EQ("2", GetBetween<TestOrdinal>("001", "333"));
+  EXPECT_EQ("31", GetBetween<TestOrdinal>("222", "333"));
+  EXPECT_EQ("3", GetBetween<TestOrdinal>("201", "333"));
+  EXPECT_EQ("2", GetBetween<TestOrdinal>("003", "333"));
+  EXPECT_EQ("2", GetBetween<TestOrdinal>("2223", "1113"));
+}
+
+// Create some Ordinals specifically designed to trigger digit
+// overflow cases.  Given two strings from this set, CreateBetween
+// should return an Ordinal roughly between them that have as few digits
+// as possible.
+TEST(Ordinal, CreateBetweenOverflowLarge) {
+  EXPECT_EQ("\x80", GetBetween<LargeOrdinal>("\x01\xff", "\xff\xff"));
+  EXPECT_EQ("\xff\xfe\x80", GetBetween<LargeOrdinal>("\xff\xfe", "\xff\xff"));
+}
+
+// Create some Ordinals.  CreateBefore should return an Ordinal
+// roughly halfway towards 0.
+TEST(Ordinal, CreateBefore) {
+  EXPECT_EQ("02", TestOrdinal("1").CreateBefore().ToInternalValue());
+  EXPECT_EQ("03", TestOrdinal("11").CreateBefore().ToInternalValue());
+  EXPECT_EQ("03", TestOrdinal("12").CreateBefore().ToInternalValue());
+  EXPECT_EQ("1", TestOrdinal("13").CreateBefore().ToInternalValue());
+}
+
+// Create some Ordinals.  CreateAfter should return an Ordinal
+// roughly halfway towards 0.
+TEST(Ordinal, CreateAfter) {
+  EXPECT_EQ("31", TestOrdinal("3").CreateAfter().ToInternalValue());
+  EXPECT_EQ("322", TestOrdinal("32").CreateAfter().ToInternalValue());
+  EXPECT_EQ("33322", TestOrdinal("3332").CreateAfter().ToInternalValue());
+  EXPECT_EQ("3", TestOrdinal("22").CreateAfter().ToInternalValue());
+  EXPECT_EQ("3", TestOrdinal("23").CreateAfter().ToInternalValue());
+}
+
+// Create two valid Ordinals.  EqualsFn should return true only when
+// called reflexively.
+TEST(Ordinal, EqualsFn) {
+  const TestOrdinal ordinal1("1");
+  const TestOrdinal ordinal2("2");
+
+  const TestOrdinal::EqualsFn equals;
+
+  EXPECT_TRUE(equals(ordinal1, ordinal1));
+  EXPECT_FALSE(equals(ordinal1, ordinal2));
+
+  EXPECT_FALSE(equals(ordinal2, ordinal1));
+  EXPECT_TRUE(equals(ordinal2,ordinal2));
+}
+
+// Create some Ordinals and shuffle them.  Sorting them using
+// LessThanFn should produce the correct order.
+TEST(Ordinal, Sort) {
+  const LongOrdinal ordinal1("12345");
+  const LongOrdinal ordinal2("54321");
+  const LongOrdinal ordinal3("87654");
+  const LongOrdinal ordinal4("98765");
+
+  std::vector<LongOrdinal> sorted_ordinals;
+  sorted_ordinals.push_back(ordinal1);
+  sorted_ordinals.push_back(ordinal2);
+  sorted_ordinals.push_back(ordinal3);
+  sorted_ordinals.push_back(ordinal4);
+
+  std::vector<LongOrdinal> ordinals = sorted_ordinals;
+  std::random_shuffle(ordinals.begin(), ordinals.end());
+  std::sort(ordinals.begin(), ordinals.end(), LongOrdinal::LessThanFn());
+  EXPECT_TRUE(std::equal(ordinals.begin(), ordinals.end(),
+                         sorted_ordinals.begin(), LongOrdinal::EqualsFn()));
+}
+
+}  // namespace
+
+}  // namespace syncer
diff --git a/sync/protocol/sync.proto b/sync/protocol/sync.proto
index 8f44823..6d0622b2 100644
--- a/sync/protocol/sync.proto
+++ b/sync/protocol/sync.proto
@@ -308,7 +308,7 @@ message SyncEntity {
 
   // Supplies an ordinal for this item, relative to other items with the
   // same parent.  Ordinals are ordered lexicographically bytewise.
-  // Ordinals must be a least 8 bytes (for backwards compatibility), and
+  // Ordinals must be at least 8 bytes (for backwards compatibility), and
   // must not be all zeroes.
   //
   // Clients should not make sure that each item they know of has a
diff --git a/sync/sync.gyp b/sync/sync.gyp
index 3701d34..ab54597 100644
--- a/sync/sync.gyp
+++ b/sync/sync.gyp
@@ -46,6 +46,9 @@
         'internal_api/public/base/model_type.h',
         'internal_api/public/base/model_type_state_map.cc',
         'internal_api/public/base/model_type_state_map.h',
+        'internal_api/public/base/node_ordinal.cc',
+        'internal_api/public/base/node_ordinal.h',
+        'internal_api/public/base/ordinal.h',
         'internal_api/public/engine/model_safe_worker.cc',
         'internal_api/public/engine/model_safe_worker.h',
         'internal_api/public/engine/passive_model_worker.cc',
@@ -385,6 +388,7 @@
       # We avoid including header files from sync_proto in our public
       # header files so we don't need to export its settings.
       'sources': [
+        'api/string_ordinal.h',
         'api/syncable_service.cc',
         'api/syncable_service.h',
         'api/sync_data.h',
@@ -585,6 +589,8 @@
         'sources': [
           'internal_api/public/base/enum_set_unittest.cc',
           'internal_api/public/base/model_type_state_map_unittest.cc',
+          'internal_api/public/base/node_ordinal_unittest.cc',
+          'internal_api/public/base/ordinal_unittest.cc',
           'internal_api/public/engine/model_safe_worker_unittest.cc',
           'internal_api/public/util/immutable_unittest.cc',
           'engine/apply_control_data_updates_unittest.cc',