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;
+
+#if !defined(ARCH_CPU_LITTLE_ENDIAN) || (ARCH_CPU_LITTLE_ENDIAN != 1)
+#error The code below assumes little-endianness.
+#endif
 
 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) {

[Nathan Parker, 2016/08/17 20:57:27]

I feel like there's no point in building in an endianness dependency unless it
makes the code faster or a lot cleaner.  What's wrong with htonl()? 

[vakh (use Gerrit instead), 2016/08/17 22:10:41]

[I don't feel strongly about it bit have a slight preference so I changed the
code.]
There are two parts to this statement:
1. endianness dependency: this is irrelevant since Chrome has only been
supported on little-endian platforms for the longest time. I am not sure if this
code would work correctly on big endian machines so I ifdef'd it out.
2. Nothing wrong with htonl -- It is defined in different header files on
different plaforms so defining a simple bit-flipping method that does the same
thing seemed cleaner.

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

I agree with this, if it's reasonable to just do it right, do it right.  At this
point I wouldn't worry excessively about performance, because there will
probably be bigger fish to fry in here.

That said, I also support the "If it's not little endian, break the compile"
strategy.  I'm slightly nervous about doing it as macro checks, rather than some
sort of compiler-generated check.

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

Done.
I really think that if it should fail, it should fail spectacularly.

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

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

"DecodeBytes" decodes to a vector of uint32_t.  Maybe "DecodePrefixes" or
something like that.

Also this heavily overlaps the DecodeIntegers() function, other than the
ordering constraints.  I couldn't see an obvious way to steal the underlying
storage from the RepeatedField, unfortunately.

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

Done.
Hmm.

   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 done so that the decoded uint32 is interpreted

[Nathan Parker, 2016/08/17 20:57:27]

re-flow comment.
Make a comment that the ints need to be converted to 4-byte-strings as if they
were Big Endian ints, and Chrome runs only on Little Endian.

[vakh (use Gerrit instead), 2016/08/17 22:10:41]

Please see my other comment about this below.

+      // correcly
+      // as a string of 4 bytes.
+      out->push_back(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;
-    }
+  // Flipping the bytes, as done above, destroys the sort order. Sort the
+  // values back.
+  std::sort(out->begin(), out->end());
 
-    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++) {

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

size_t rather than unsigned, here.

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

Done.

+    (*out)[i] = FlipEndianness((*out)[i]);

[Nathan Parker, 2016/08/17 20:57:27]

Wait, now I'm confused again.  You're flipping, sorting as ints, then flipping
again.

OH, I think I understand: You're sorting the array as integers, rather than as
4-byte-strings, but you want them to end up in lexigraphical order.  I _think_
you could avoid all the flipping by having sort() compare 4-byte strings instead
of ints.  I'm not sure if that'll be any faster comparing ints is pretty ideal. 
But the current code has an extra pass through the array.



If what I said make sense, you could add a comment that we might want to compare
my proposed method's performance, if performance here turns out to be an issue.


It might be more clear if you didn't use uint32_t's, but instead had something
like
  typedef uint32_t Hash32Bits
  std::vector<Hash32Bits>* out

Since really once you've done the Rice decoding, you no longer treat them as
ints (and shouldn't).

[vakh (use Gerrit instead), 2016/08/17 22:10:41]

I think the explanation goes like this. The following program, on a
little-endian machine produces:

  std::vector<uint32_t> v2;
  v2.reserve(3);
  v2.push_back(0x41424344);
  v2.push_back(0);
  cptr = reinterpret_cast<char*>(v2.data());
  std::cout << "as string: " << cptr << std::endl;

Output:
as string: DCBA

This shows that when a string (which is what the server meant to send) as
re-interpreted as a uint32_t, it reverses the order of the bits.

That's why we need to do this whole bit flipping.

The server sends a response.
Parse the response as uint32_t values.
Flip bytes to reinterpret them correctly.
Sort them to get the correct lexicographical order
Flip the bytes again, since they need to be consumed as bytes not uint32_t
values.

I think the current comment describes this process fairly accurately but I am
super willing to consider suggestions.

   }
 
   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;
+    GetBitsFromCurrentWord(num_bits_left_in_current_word, &lower);
+
     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,

[Nathan Parker, 2016/08/17 20:57:27]

Could this just return x?

                                            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;
 };
 
 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