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..bf49f0d72c80c6e596bb67f273638e3c8cc528b2 100644
--- a/components/safe_browsing_db/v4_rice.cc
+++ b/components/safe_browsing_db/v4_rice.cc
@@ -2,6 +2,9 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include <algorithm>
+#include <vector>
+
 #include "base/logging.h"
 #include "base/numerics/safe_math.h"
 #include "base/strings/stringprintf.h"
@@ -9,6 +12,7 @@
 
 using ::google::protobuf::RepeatedField;
 using ::google::protobuf::int32;
+using ::google::protobuf::int64;
 
 namespace safe_browsing {
 
@@ -17,12 +21,9 @@ namespace {
 const int kBitsPerByte = 8;
 const unsigned int kMaxBitIndex = kBitsPerByte * sizeof(uint32_t);
 
-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);
+uint32_t FlipEndianness(uint32_t word) {
+  return (word >> 24) | ((word << 8) & 0x00FF0000) |
+         ((word >> 8) & 0x0000FF00) | (word << 24);
 }
 
 }  // namespace
@@ -54,7 +55,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,11 +96,11 @@ 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,
-                                          std::string* out) {
+                                          std::vector<uint32_t>* out) {
   DCHECK(out);
 
   V4DecodeResult result =
@@ -107,37 +108,37 @@ V4DecodeResult V4RiceDecoder::DecodeBytes(const int32 first_value,
   if (result != DECODE_SUCCESS) {
     return result;
   }
-  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;
-  }
+  out->reserve((num_entries + 1));
+
+  base::CheckedNumeric<uint32_t> last_value(first_value);
+  out->push_back(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;
+      // This flipping is mandated by the protocol. For details, see:
+      // https://developers.google.com/safe-browsing/v4/compression

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

The protocol says the data is in network byte order, it doesn't say that it
needs to be flipped.  If the platform is little-endian, flipping would be
incorrect.

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

My machine is little-endian and it does require byte flipping.

The encoded data (in the form of a string) passed by the server is read
bit-by-bit to produce the Rice-decoded values. I believe, that part of the
process is independent of the machine's endianness.

Once that decoder has produced a uint32_t value, the only way to match the
checksum is to flip those bits (at least on a little-endian machine). I am not
sure about the expected behavior on big-endian machines so I'd let Noe comment
on that.

FWIW, I know that the SafeBrowsing code in Android does this bit flipping
unconditionally.

+      out->push_back(FlipEndianness(last_value.ValueOrDie()));
     }
+  }
+  std::sort(out->begin(), out->end());

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

Whoa!  I could see ASSERT_TRUE(std::is_sorted(...)) here, as if these aren't
already sorted, I think something is fubar.

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

These aren't already sorted. That's because of the bit flipping I do just before
push_back.

 
-    GetBytesFromUInt32(last_value.ValueOrDie(), bytes);
-    out->append(bytes, 4);
+  // This flipping is done so that when the vector is interpreted as a string,
+  // the bytes are in the correct order.
+  for (unsigned i = 0; i < out->size(); i++) {
+    (*out)[i] = FlipEndianness((*out)[i]);
   }
 
   return DECODE_SUCCESS;
@@ -238,20 +239,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_|.
+    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;
 }