PVer4: DecodeHashes needs to sort the output of the Rice decoder

components/safe_browsing_db/v4_rice.cc

Index: components/safe_browsing_db/v4_rice.cc
diff --git a/components/safe_browsing_db/v4_rice.cc b/components/safe_browsing_db/v4_rice.cc
index 0e7148048fc379e1a3645906d818845e9932ab16..2486962fb12a5bed3cfb2c29c8496e1c8ca03150 100644
--- a/components/safe_browsing_db/v4_rice.cc
+++ b/components/safe_browsing_db/v4_rice.cc
@@ -2,13 +2,15 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "base/logging.h"

[Scott Hess - ex-Googler, 2016/08/12 23:25:46]

I think you still need logging.h for things like NOTREACHED().  Just because
safe_math.h has it for you doesn't mean you should skip it here.

[vakh (use Gerrit instead), 2016/08/13 00:15:14]

I agree. Didn't realize it was needed for that. Added back.

+#include <set>
+
 #include "base/numerics/safe_math.h"
 #include "base/strings/stringprintf.h"
 #include "components/safe_browsing_db/v4_rice.h"
 
 using ::google::protobuf::RepeatedField;
 using ::google::protobuf::int32;
+using ::google::protobuf::int64;
 
 namespace safe_browsing {
 
@@ -17,12 +19,17 @@ namespace {
 const int kBitsPerByte = 8;
 const unsigned int kMaxBitIndex = kBitsPerByte * sizeof(uint32_t);
 
+uint32_t FlipEndianness(uint32_t word) {

[Scott Hess - ex-Googler, 2016/08/12 23:25:47]

Is this right?  I don't _think_ we have a mix of little-endian and big-endian
platforms running Chrome, but I'm not entirely certain.  I know there are MIPS
ports out there, and I see evidence that someone was working on cleaning up
big-endian support for MIPS.  Does this really need to always flip, or is it
more like ntohl()?  If the latter, then I suspect we have base/ support for that
kind of thing.

[Maybe base/big_endian.h ?  Or perhaps something in net/?]

[vakh (use Gerrit instead), 2016/08/13 00:15:14]

Is this flip always needed: Waiting to get a confirmation from the SafeBrowsing
team on that. cc'd you on that email.

[Scott Hess - ex-Googler, 2016/08/15 21:18:15]

To be clear - I suspect they are just serving network byte order, so you need to
use ntohl() or base/big_endian.h .  My guess is that they don't rearrange the
byte order based on user-agent request, so the right thing to do would be to
conditionally flip (such as those two options do).  It probably would be
preferable to use something like base/big_endian.h so that the data is simply
read out right, rather than have separate steps for read-the-data and
conditional-flip, though cache hierarchies on modern CPUs may make the
difference moot.

Actually, if it's little-endian on the wire, then having a read like your prior
reader is probably best, since it's not conditional (it simply put the first
byte in the low-order bits, and so on).

[vakh (use Gerrit instead), 2016/08/16 00:23:03]

Noe -- can you please review this part of the code since you are most aware of
the server side implementation?

This is what my implementation does for now:
1. decode encoded_data field using Rice decoder.
2. Flip the bits of each output uint32_t value
3. Sort these uint32_t (since flipping the bits destroys sort order).
4. Flip the bits back and reinterpret them as bytes in a string.

Can you specifically comment on what parts of this are avoidable and what parts
are platform specific?

+  return (word >> 24) | ((word << 8) & 0x00FF0000) |
+         ((word >> 8) & 0x0000FF00) | (word << 24);
+}
+
 void GetBytesFromUInt32(uint32_t word, char* bytes) {
   const size_t mask = 0xFF;
-  bytes[0] = (char)(word & mask);
-  bytes[1] = (char)((word >> 8) & mask);
-  bytes[2] = (char)((word >> 16) & mask);
-  bytes[3] = (char)((word >> 24) & mask);
+  bytes[3] = (char)(word & mask);
+  bytes[2] = (char)((word >> 8) & mask);
+  bytes[1] = (char)((word >> 16) & mask);
+  bytes[0] = (char)((word >> 24) & mask);
 }
 
 }  // namespace
@@ -54,7 +61,7 @@ V4DecodeResult V4RiceDecoder::ValidateInput(const int32 rice_parameter,
 }
 
 // static
-V4DecodeResult V4RiceDecoder::DecodeIntegers(const int32 first_value,
+V4DecodeResult V4RiceDecoder::DecodeIntegers(const int64 first_value,
                                              const int32 rice_parameter,
                                              const int32 num_entries,
                                              const std::string& encoded_data,
@@ -95,7 +102,7 @@ V4DecodeResult V4RiceDecoder::DecodeIntegers(const int32 first_value,
 }
 
 // static
-V4DecodeResult V4RiceDecoder::DecodeBytes(const int32 first_value,
+V4DecodeResult V4RiceDecoder::DecodeBytes(const int64 first_value,
                                           const int32 rice_parameter,
                                           const int32 num_entries,
                                           const std::string& encoded_data,
@@ -109,34 +116,32 @@ V4DecodeResult V4RiceDecoder::DecodeBytes(const int32 first_value,
   }
   out->reserve((num_entries + 1) * 4);
 
-  // Cast to unsigned since we don't look at the sign bit as a sign bit.
-  // first_value should have been an unsigned to begin with but proto don't
-  // allow that.
-  uint32_t first_value_unsigned = static_cast<uint32_t>(first_value);
-  base::CheckedNumeric<uint32_t> last_value(first_value_unsigned);
-  char bytes[4];
-  GetBytesFromUInt32(last_value.ValueOrDie(), bytes);
-  out->append(bytes, 4);
-
-  if (num_entries == 0) {
-    return DECODE_SUCCESS;
-  }
+  base::CheckedNumeric<uint32_t> last_value(first_value);
+  std::set<uint32_t> hash_prefixes;
+  hash_prefixes.insert(FlipEndianness(last_value.ValueOrDie()));
+
+  if (num_entries > 0) {
+    V4RiceDecoder decoder(rice_parameter, num_entries, encoded_data);
+    while (decoder.HasAnotherValue()) {
+      uint32_t offset;
+      result = decoder.GetNextValue(&offset);
+      if (result != DECODE_SUCCESS) {
+        return result;
+      }
 
-  V4RiceDecoder decoder(rice_parameter, num_entries, encoded_data);
-  while (decoder.HasAnotherValue()) {
-    uint32_t offset;
-    result = decoder.GetNextValue(&offset);
-    if (result != DECODE_SUCCESS) {
-      return result;
-    }
+      last_value += offset;
+      if (!last_value.IsValid()) {
+        NOTREACHED();
+        return DECODED_INTEGER_OVERFLOW_FAILURE;
+      }
 
-    last_value += offset;
-    if (!last_value.IsValid()) {
-      NOTREACHED();
-      return DECODED_INTEGER_OVERFLOW_FAILURE;
+      hash_prefixes.insert(FlipEndianness(last_value.ValueOrDie()));
     }
+  }
 
-    GetBytesFromUInt32(last_value.ValueOrDie(), bytes);
+  char bytes[4];
+  for (const uint32_t& hash_prefix : hash_prefixes) {
+    GetBytesFromUInt32(hash_prefix, bytes);
     out->append(bytes, 4);
   }
 
@@ -238,20 +243,24 @@ V4DecodeResult V4RiceDecoder::GetNextBits(unsigned int num_requested_bits,
     // All the bits that we need are in |current_word_|.
     GetBitsFromCurrentWord(num_requested_bits, x);
   } else {
-    // |current_word_| contains fewer bits than we need so we store the current
-    // value of |current_word_| in |lower|, then read in a new |current_word_|,
-    // and then pick the remaining bits from the new value of |current_word_|.
-    uint32_t lower = current_word_;
-    // Bits we need after we read all of |current_word_|
+    // |current_word_| contains fewer bits than we need so read the remaining
+    // bits from |current_word_| into |lower|, and then call GetNextBits on the
+    // remaining number of bits, which will read in a new word into
+    // |current_word_|.

[Scott Hess - ex-Googler, 2016/08/12 23:25:46]

I'm finding this confusing.  I _think_ what it's saying is that the entire span
of bits does not exist in current_word_.  But below it calls GetNextBits() to
read num_bits_left_in_current_word, which _does_ exist in current_word_ (so I
think it will always degenerate to GetBitsFromCurrentWord).  Then upper has to
be read via GetNextBits() to load a new word.  [Is the same possibly true for
reading lower?  Or would num_bits_left_in_current_word be zero in that case?]

[vakh (use Gerrit instead), 2016/08/13 00:15:14]

Let me illustrate with an example: Let's say we want to read 28 bits, but we've
already read 23 from current_word_. This means:
num_requested_bits = 28
current_word_bit_index_ = 23
num_bits_left_in_current_word = 9

We split the read operation into two parts: read 9 bits, then read 19 bits for a
total of 28.

lower = GetNextBits(9)
=> current_word_bit_index_ = 23 + 9 = 32.

upper = GetNextBits(19)
=> but, current_word_bit_index_ == 32 (kMaxBitIndex)
=> => Read next word into current_word_ and reset current_word_bit_index_ to 0
(see line 233).
=> Read 19 bits from new current_word_ into upper.
=> current_word_bit_index_ = 0 + 19 = 19

[Scott Hess - ex-Googler, 2016/08/15 21:18:15]

Yes, but the comment is written in terms of current_word_, which is not a thing
the local code is using.  Maybe try writing a new comment without reference to
the current one, to see if a cleaner description can be made.  Like "Combine the
rest of current_word_ with additional bits from the next word."

I think the first call to GetNextBits() should actually be calling
GetBitsFromCurrentWord() to eat the remainder of current_word_.

[vakh (use Gerrit instead), 2016/08/16 00:23:03]

Done.

+    uint32_t lower;
+    V4DecodeResult result = GetNextBits(num_bits_left_in_current_word, &lower);
+    if (result != DECODE_SUCCESS) {
+      return result;
+    }
+
     unsigned int num_bits_from_next_word =
         num_requested_bits - num_bits_left_in_current_word;
     uint32_t upper;
-    V4DecodeResult result = GetNextWord(&current_word_);
+    result = GetNextBits(num_bits_from_next_word, &upper);
     if (result != DECODE_SUCCESS) {
       return result;
     }
-    GetBitsFromCurrentWord(num_bits_from_next_word, &upper);
-    *x = (upper << (num_requested_bits - num_bits_from_next_word)) | lower;
+    *x = (upper << num_bits_left_in_current_word) | lower;
   }
   return DECODE_SUCCESS;
 }