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 "base/logging.h"
+#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 {
 
 namespace {
 
 const int kBitsPerByte = 8;
 const unsigned int kMaxBitIndex = kBitsPerByte * sizeof(uint32_t);
 
+uint32_t FlipEndianness(uint32_t word) {

[Nathan Parker, 2016/08/12 23:01:49]

This should be platform-specific.  Maybe use C's htonl(), or something from
chromium/src/base/big_endian.h

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

Waiting for Noe/Alex to confirm.

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

[Nathan Parker, 2016/08/12 23:01:49]

Is this ordering endian-dependent as well?

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

No.

+  bytes[2] = (char)((word >> 8) & mask);
+  bytes[1] = (char)((word >> 16) & mask);
+  bytes[0] = (char)((word >> 24) & mask);
 }
 
 }  // 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) {
   DCHECK(out);
 
   V4DecodeResult result =
       ValidateInput(rice_parameter, num_entries, encoded_data);
   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);
+  base::CheckedNumeric<uint32_t> last_value(first_value);

[Nathan Parker, 2016/08/12 23:01:49]

You're casting a int64 to a unit32_t.  Is that intentional?

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

Yes, I am not sure why the first_value is a int64 when we only expect uint32s.
The reason for this change is to capture the value from the proto as-is and let
the NumericChecker code in Chrome raise if the value is actually greater than
what can fit in 32 bits.

+  std::set<uint32_t> hash_prefixes;

[Nathan Parker, 2016/08/12 23:01:49]

This is going to use at least another 24 bytes of RAM per 4-byte hash (three
pointers). I think it'd be better to use a different sorting mechanism, since
we've got several copies of the hashes in RAM already.

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

Let me try what we discussed offline: use the string out to store unsorted hash
prefixes using reinterpret magic and sort in-place at the end.

+  hash_prefixes.insert(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;
+      }
+
+      hash_prefixes.insert(FlipEndianness(last_value.ValueOrDie()));
+    }
   }
 
-  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);
+  char bytes[4];
+  for (const uint32_t& hash_prefix : hash_prefixes) {
+    GetBytesFromUInt32(hash_prefix, bytes);
     out->append(bytes, 4);
   }
 
   return DECODE_SUCCESS;
 }
 
 V4RiceDecoder::V4RiceDecoder(const int rice_parameter,
                              const int num_entries,
                              const std::string& encoded_data)
     : rice_parameter_(rice_parameter),
@@ skipping 81 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