Use zig-zag encoding in the source position table.

src/interpreter/source-position-table.cc

 // Copyright 2016 the V8 project 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 "src/interpreter/source-position-table.h"
 
 #include "src/objects-inl.h"
 #include "src/objects.h"
 
 namespace v8 {
 namespace internal {
 namespace interpreter {
 
 // We'll use a simple encoding scheme to record the source positions.
 // Conceptually, each position consists of:
 // - bytecode_offset: An integer index into the BytecodeArray
 // - source_position: An integer index into the source string.
 // - position type: Each position is either a statement or an expression.
 //
 // The basic idea for the encoding is to use a variable-length integer coding,
 // where each byte contains 7 bits of payload data, and 1 'more' bit that
 // determines whether additional bytes follow. Additionally:
 // - we record the difference from the previous position,
 // - we just stuff one bit for the type into the bytecode offset,
 // - we write least-significant bits first,
-// - negative numbers occur only rarely, so we use a denormalized
-//   most-significant byte (a byte with all zeros, which normally wouldn't
-//   make any sense) to encode a negative sign, so that we 'pay' nothing for
-//   positive numbers, but have to pay a full byte for negative integers.
+// - we use zig-zag encoding to encode both positive and negative numbers.
 
 namespace {
 
-// A zero-value in the most-significant byte is used to mark negative numbers.
-const int kNegativeSignMarker = 0;
-
 // Each byte is encoded as MoreBit | ValueBits.
 class MoreBit : public BitField8<bool, 7, 1> {};
-class ValueBits : public BitField8<int, 0, 7> {};
+class ValueBits : public BitField8<unsigned, 0, 7> {};
 
 // Helper: Add the offsets from 'other' to 'value'. Also set is_statement.
 void AddAndSetEntry(PositionTableEntry& value,
                     const PositionTableEntry& other) {
   value.bytecode_offset += other.bytecode_offset;
   value.source_position += other.source_position;
   value.is_statement = other.is_statement;
 }
 
 // Helper: Substract the offsets from 'other' from 'value'.
 void SubtractFromEntry(PositionTableEntry& value,
                        const PositionTableEntry& other) {
   value.bytecode_offset -= other.bytecode_offset;
   value.source_position -= other.source_position;
 }
 
 // Helper: Encode an integer.
 void EncodeInt(ZoneVector<byte>& bytes, int value) {
-  bool sign = false;
-  if (value < 0) {
-    sign = true;
-    value = -value;
-  }
-
+  // Zig-zag encoding.
+  static const int kShift = kIntSize * kBitsPerByte - 1;
+  value = ((value << 1) ^ (value >> kShift));

[vogelheim, 2016/06/21 14:11:12]

nitpick: This relies on >> doing sign extension on negative values. I think this
is implementation defined in C++. (Not sure this is truly an issue; but...
well.)

[Yang, 2016/06/21 15:11:16]

So... two's complement for negative integer representation is also undefined
behavior, which is apparently the cause for sign extension not being defined in
the first place. We heavily rely on two's complement here, so...

If it turns out that on some platform we cannot rely on this, we can still use
branching and have something to the effect of (value < 0) ? -(value*2) + 1 :
value*2

+  DCHECK_GE(value, 0);
+  unsigned int encoded = static_cast<unsigned int>(value);
   bool more;
   do {
-    more = value > ValueBits::kMax;
-    bytes.push_back(MoreBit::encode(more || sign) |
-                    ValueBits::encode(value & ValueBits::kMax));
-    value >>= ValueBits::kSize;
+    more = encoded > ValueBits::kMax;
+    bytes.push_back(MoreBit::encode(more) |
+                    ValueBits::encode(encoded & ValueBits::kMask));
+    encoded >>= ValueBits::kSize;
   } while (more);
-
-  if (sign) {
-    bytes.push_back(MoreBit::encode(false) |
-                    ValueBits::encode(kNegativeSignMarker));
-  }
 }
 
 // Encode a PositionTableEntry.
 void EncodeEntry(ZoneVector<byte>& bytes, const PositionTableEntry& entry) {
-  // 1 bit for sign + is_statement each, which leaves 30b for the value.
-  DCHECK(abs(entry.bytecode_offset) < (1 << 30));
-  EncodeInt(bytes, (entry.is_statement ? 1 : 0) | (entry.bytecode_offset << 1));
+  // We only accept ascending bytecode offsets.
+  DCHECK(entry.bytecode_offset >= 0);
+  // Since bytecode_offset is not negative, we  use sign to encode is_statement.

[vogelheim, 2016/06/21 14:11:12]

super nitpick: double space between "we  use".

+  EncodeInt(bytes, entry.is_statement ? entry.bytecode_offset
+                                      : -entry.bytecode_offset - 1);
   EncodeInt(bytes, entry.source_position);
 }
 
 // Helper: Decode an integer.
 void DecodeInt(ByteArray* bytes, int* index, int* v) {
   byte current;
-  int n = 0;
-  int value = 0;
+  int shift = 0;
+  int decoded = 0;
   bool more;
   do {
     current = bytes->get((*index)++);
-    value |= ValueBits::decode(current) << (n * ValueBits::kSize);
-    n++;
+    decoded |= ValueBits::decode(current) << shift;
     more = MoreBit::decode(current);
+    shift += ValueBits::kSize;
   } while (more);
-
-  if (ValueBits::decode(current) == kNegativeSignMarker) {
-    value = -value;
-  }
-  *v = value;
+  DCHECK_GE(decoded, 0);
+  decoded = (decoded >> 1) ^ (-(decoded & 1));
+  *v = decoded;
 }
 
 void DecodeEntry(ByteArray* bytes, int* index, PositionTableEntry* entry) {
   int tmp;
   DecodeInt(bytes, index, &tmp);
-  entry->is_statement = (tmp & 1);
-
-  // Note that '>>' needs to be arithmetic shift in order to handle negative
-  // numbers properly.
-  entry->bytecode_offset = (tmp >> 1);
-
+  if (tmp >= 0) {
+    entry->is_statement = true;
+    entry->bytecode_offset = tmp;
+  } else {
+    entry->is_statement = false;
+    entry->bytecode_offset = -(tmp + 1);
+  }
   DecodeInt(bytes, index, &entry->source_position);
 }
 
 }  // namespace
 
 void SourcePositionTableBuilder::AddPosition(size_t bytecode_offset,
                                              int source_position,
                                              bool is_statement) {
   int offset = static_cast<int>(bytecode_offset);
   AddEntry({offset, source_position, is_statement});
@@ skipping 57 matching lines @@
   } else {
     PositionTableEntry tmp;
     DecodeEntry(table_, &index_, &tmp);
     AddAndSetEntry(current_, tmp);
   }
 }
 
 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8