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 "build/build_config.h"
 #include "components/safe_browsing_db/v4_rice.h"
 
+#if defined(OS_WIN)
+#include <winsock2.h>
+#elif defined(OS_POSIX)
+#include <arpa/inet.h>
+#endif
+
 using ::google::protobuf::RepeatedField;
 using ::google::protobuf::int32;
+using ::google::protobuf::int64;
+
+#if !defined(ARCH_CPU_LITTLE_ENDIAN) || (ARCH_CPU_LITTLE_ENDIAN != 1)
+#error The code below assumes little-endianness.
+#endif

[Scott Hess - ex-Googler, 2016/08/17 22:42:27]

Is this still necessary now that it's using htonl?

[vakh (use Gerrit instead), 2016/08/17 23:40:07]

To be frank, I won't be 100% sure until I observe it.
I'd much rather it fails loud and then someone can make it work, than it fails
silently and no one notices.

 
 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);
-}
-
 }  // namespace
 
 // static
 V4DecodeResult V4RiceDecoder::ValidateInput(const int32 rice_parameter,
                                             const int32 num_entries,
                                             const std::string& encoded_data) {
   if (num_entries < 0) {
     NOTREACHED();
     return NUM_ENTRIES_NEGATIVE_FAILURE;
   }
 
   if (num_entries == 0) {
     return DECODE_SUCCESS;
   }
 
   if (rice_parameter <= 0) {
     NOTREACHED();
     return RICE_PARAMETER_NON_POSITIVE_FAILURE;
   }
 
   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(htonl(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 done so that the decoded uint32 is interpreted
+      // correcly as a string of 4 bytes.
+      out->push_back(htonl(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;
-    }
+  // Flipping the bytes, as done above, destroys the sort order. Sort the
+  // values back.
+  std::sort(out->begin(), out->end());

[Scott Hess - ex-Googler, 2016/08/17 22:42:26]

I think at least part of the confusion is that there's a sorting constraint
which is being explained from the bottom up (comments probably added as you
discovered things), and maybe it would be cleaner if the header comment for this
function described how the results should be sorted.

AFAICT, the sort order is because someone elsewhere is going to interpret the
raw vector::data() bytes.  I'm not making a value judgement on _that_, I'm just
saying that if you're going to bake that assumption in here, then you need to
describe it because it's a completely non-obvious requirement for someone
looking at this code.

That said ... I'm also not entirely convinced that this should return a vector
of integers, given that there's this odd sorting constraint and someone else is
accessing it as raw data.  If the only reason for the vector is for unit tests,
then IMHO it would be reasonable for the unit tests to decode/flip things for
purposes of testing.

[vakh (use Gerrit instead), 2016/08/17 23:40:07]

Done. Let me know if that isn't clear enough for a new reader.
Done.
The reason it returns a vector is that I am trying to interpret the same memory
block some times as std::vector<uint32_t> and other times as std::string.

The other way to do this would be to create a std::string, reserve its size
appropriately, and then re-interpret that block of memory as vector<uint32_t>.
The problem with that approach is that string::data() returns a const char *
pointer, so I cannot modify the memory underneath that string.
Of course I could cast away the constness but that's probably not a good idea
either. So I am between a rock and a hard place.

 
-    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] = ntohl((*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 78 matching lines @@
     V4DecodeResult result = GetNextWord(&current_word_);
     if (result != DECODE_SUCCESS) {
       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);
+    *x = GetBitsFromCurrentWord(num_requested_bits);
   } 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 = GetBitsFromCurrentWord(num_bits_left_in_current_word);
+
     unsigned int num_bits_from_next_word =
         num_requested_bits - num_bits_left_in_current_word;
     uint32_t upper;
-    V4DecodeResult result = GetNextWord(&current_word_);
+    V4DecodeResult 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 V4RiceDecoder::GetBitsFromCurrentWord(
+    unsigned int num_requested_bits) {
   uint32_t mask = 0xFFFFFFFF >> (kMaxBitIndex - num_requested_bits);
-  *x = current_word_ & mask;
+  uint32_t x = current_word_ & mask;
   current_word_ = current_word_ >> num_requested_bits;
   current_word_bit_index_ += num_requested_bits;
+  return x;
 };
 
 std::string V4RiceDecoder::DebugString() const {
   // Calculates the total number of bits that we have read from the buffer,
   // excluding those that have been read into current_word_ but not yet
   // consumed byt GetNextBits().
   unsigned bits_read = (data_byte_index_ - sizeof(uint32_t)) * kBitsPerByte +
                        current_word_bit_index_;
   return base::StringPrintf(
       "bits_read: %x; current_word_: %x; data_byte_index_; %x, "
       "current_word_bit_index_: %x; rice_parameter_: %x",
       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