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

components/safe_browsing_db/v4_rice.cc

 // Copyright 2016 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 <algorithm>
+#include <vector>
+
 #include "base/logging.h"
 #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 {
 
 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
 
 // static
 V4DecodeResult V4RiceDecoder::ValidateInput(const int32 rice_parameter,
                                             const int32 num_entries,
                                             const std::string& encoded_data) {
   if (num_entries < 0) {
     NOTREACHED();
@@ skipping 11 matching lines @@
 
   if (encoded_data.empty()) {
     NOTREACHED();
     return ENCODED_DATA_UNEXPECTED_EMPTY_FAILURE;
   }
 
   return DECODE_SUCCESS;
 }
 
 // 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,
                                              RepeatedField<int32>* out) {
   DCHECK(out);
 
   V4DecodeResult result =
       ValidateInput(rice_parameter, num_entries, encoded_data);
   if (result != DECODE_SUCCESS) {
     return result;
@@ skipping 20 matching lines @@
       return DECODED_INTEGER_OVERFLOW_FAILURE;
     }
 
     out->Add(last_value.ValueOrDie());
   }
 
   return DECODE_SUCCESS;
 }
 
 // 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 =
       ValidateInput(rice_parameter, num_entries, encoded_data);
   if (result != DECODE_SUCCESS) {
     return result;
   }
-  out->reserve((num_entries + 1) * 4);
+  out->reserve((num_entries + 1));
 
-  // 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);
+  base::CheckedNumeric<uint32_t> last_value(first_value);
+  out->push_back(FlipEndianness(last_value.ValueOrDie()));
 
-  if (num_entries == 0) {
-    return DECODE_SUCCESS;
+  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;
+      }
+
+      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.

 
-  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;
-    }
-
-    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;
 }
 
 V4RiceDecoder::V4RiceDecoder(const int rice_parameter,
                              const int num_entries,
                              const std::string& encoded_data)
     : rice_parameter_(rice_parameter),
       num_entries_(num_entries),
@@ skipping 80 matching lines @@
       return result;
     }
   }
 
   unsigned int num_bits_left_in_current_word =
       kMaxBitIndex - current_word_bit_index_;
   if (num_bits_left_in_current_word >= 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;
 }
 
 void V4RiceDecoder::GetBitsFromCurrentWord(unsigned int num_requested_bits,
                                            uint32_t* x) {
   uint32_t mask = 0xFFFFFFFF >> (kMaxBitIndex - num_requested_bits);
   *x = current_word_ & mask;
   current_word_ = current_word_ >> num_requested_bits;
   current_word_bit_index_ += num_requested_bits;
@@ skipping 11 matching lines @@
       bits_read, current_word_, data_byte_index_, current_word_bit_index_,
       rice_parameter_);
 }
 
 std::ostream& operator<<(std::ostream& os, const V4RiceDecoder& rice_decoder) {
   os << rice_decoder.DebugString();
   return os;
 }
 
 }  // namespace safe_browsing