[Sync] Generalize StringOrdinal to handle ordinal_in_parent field

sync/internal_api/public/base/node_ordinal.cc

Index: sync/internal_api/public/base/node_ordinal.cc
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 0000000000000000000000000000000000000000..59d21ab16c879f7aa43cc119a7acfd57be51b171
--- /dev/null
+++ b/sync/internal_api/public/base/node_ordinal.cc
@@ -0,0 +1,42 @@
+// Copyright (c) 2012 The Chromium Authors. All rights reserved.

[rlarocque, 2012/09/05 21:43:46]

I'm not convinced the functions in this file are endian-safe.  

Your tests look pretty good, though.  Have they been run on non-x86 platforms
yet?

[akalin, 2012/09/06 19:25:14]

I asked, and I don't think we have access to big-endian machines.  FWIW,
sync.proto defines the conversion to be in network byte order, which is the
opposite from x86, so I'd assume any endian problems would show up in x86.

But shifts and masks are endian-neutral, so I think it's okay.  Also somewhat
related, see: http://commandcenter.blogspot.com/2012/04/byte-order-fallacy.html

[rlarocque, 2012/09/06 21:25:55]

Sounds good.  I was mainly concerned about the bit-masks and cast to uint8_t. 
I'm now reasonably convinced that it's safe.

+// 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;

[rlarocque, 2012/09/05 21:43:46]

What is the intent of this statement?

[akalin, 2012/09/06 19:25:14]

The ordering of an int differs depending on its signedness (basically, all
'negative' numbers compare greater than positive numbers when treated as
unsigned).  Flipping the high-order bit corrects for that.

[rlarocque, 2012/09/06 21:25:55]

IIRC, uint64 addition is defined to be correct modulo UINT64_MAX+1.

I think that means the same operation could be expressed as

y += 0x8000000000000000ULL

where 0x8000000000000000ULL == (UINT64_MAX+1)/2, if UINT64_MAX+1 did not
overflow.  

Another way to think about it would be that it subtracts the value of INT64_MIN.

y -= INT64_MIN

Hmm... maybe your way is better.  I was hoping there was some neat way to
express this so that it's more clear that you're trying to add a constant value
to all these numbers so they land in a positive range.

[akalin, 2012/09/06 22:55:25]

Yeah, I think it's somewhat clearer to just twiddle the bits.  I wish there were
a concise way to say "flip the high bit" but this'll have to do.

+  std::string ordinal_string(NodeOrdinal::kMinLength, '\x00');
+  if (y == 0) {
+    // 0 is a special case since |ordinal_string| must not be all
+    // zeros.
+    ordinal_string.push_back('\x80');

[rlarocque, 2012/09/05 21:43:46]

This is not symmetric, right?

Because of this, 
NodeOrdinalToInt64(Int64ToNodeOrdinal(0)) != 0

Is it OK that the conversion is not 100% reversible?

[akalin, 2012/09/06 19:25:14]

It's not symmetric, but it's still reversible, since NodeOrdinalToInt64 only
looks at the first 8 bytes, so your expression does evaluate to 0.

[rlarocque, 2012/09/06 21:25:55]

Now I understand.  I overlooked the fact that the first 8 bytes were already
initialized to zero by this point.

+  } else {
+    for (int i = 7; i >= 0; --i) {
+      ordinal_string[i] = static_cast<uint8>(y);

[rlarocque, 2012/09/05 21:43:46]

I looked up the spec because I wasn't sure the result of this statement was well
defined.  It turns out that it is defined for unsigned types.

Looks good, I guess.

[akalin, 2012/09/06 19:25:14]

Yeap, most of the pitfalls lie with signed ints.

+      y >>= 8;
+    }
+  }
+  NodeOrdinal ordinal(ordinal_string);
+  DCHECK(ordinal.IsValid());
+  return ordinal;
+}
+
+int64 NodeOrdinalToInt64(const NodeOrdinal& ordinal) {
+  uint64 y = 0;
+  const std::string& s = ordinal.ToString();

[rlarocque, 2012/09/05 21:43:46]

Huh.  I did not expect ToString() to be used this way.  

I think there's room for both a 'ToPrintableString()' and
'GetInternalRepresentation()' function on the NodeOrdinal class.  I just hadn't
expected that ToString() == GetInternalRepresentation().

[akalin, 2012/09/06 19:25:14]

As discussed in the other comment, fixed.

+  const size_t l = std::min(NodeOrdinal::kMinLength, s.length());

[rlarocque, 2012/09/05 21:43:46]

Won't this always equal kMinLength?  I think that 's' would fail
IsValidOrdinalString() if  s.length() < kMinLength.  That's not supposed to
happen, is it?

[akalin, 2012/09/06 19:25:14]

You're right.  I still want to avoid out-of-bound memory reads, so I rewrote to
have a NOTREACHED.

+  for (size_t i = 0; i < l; ++i) {
+    const uint8 byte = s[l - i - 1];
+    y |= static_cast<uint64>(byte) << (i * 8);
+  }
+  y ^= 0x8000000000000000ULL;
+  return static_cast<int64>(y);

[rlarocque, 2012/09/05 21:43:46]

Now this I think actually is undefined if y > INT64_MAX.  It's probably going to
work as expected anyway, though.

[akalin, 2012/09/06 19:25:14]

Implementation-defined, actually, so I think it's okay.  Added comment.

+}
+
+}  // namespace syncer