PVer4: V4Store: Check whether a hash prefix exists for a full hash

components/safe_browsing_db/v4_store.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/base64.h"
 #include "base/bind.h"
 #include "base/files/file_util.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/metrics/sparse_histogram.h"
 #include "base/strings/stringprintf.h"
@@ skipping 195 matching lines @@
     HashPrefix* smallest_hash_prefix) {
   HashPrefix current_hash_prefix;
   bool has_unmerged = false;
 
   for (const auto& iterator_pair : iterator_map) {
     PrefixSize prefix_size = iterator_pair.first;
     HashPrefixes::const_iterator start = iterator_pair.second;
     const HashPrefixes& hash_prefixes = hash_prefix_map.at(prefix_size);
     if (prefix_size <=
         static_cast<PrefixSize>(std::distance(start, hash_prefixes.end()))) {
-      current_hash_prefix = std::string(start, start + prefix_size);
+      current_hash_prefix = HashPrefix(start, start + prefix_size);
       if (!has_unmerged || *smallest_hash_prefix > current_hash_prefix) {
         has_unmerged = true;
         smallest_hash_prefix->swap(current_hash_prefix);
       }
     }
   }
   return has_unmerged;
 }
 
 // static
@@ skipping 191 matching lines @@
   DCHECK_EQ(file_format_string.size(), written);
 
   if (!base::Move(new_filename, store_path_)) {
     DVLOG(1) << "store_path_: " << store_path_.value();
     return UNABLE_TO_RENAME_FAILURE;
   }
 
   return WRITE_SUCCESS;
 }
 
+HashPrefix V4Store::GetMatchingHashPrefix(const FullHash& full_hash) {
+  DCHECK_EQ(32u, full_hash.size());
+  for (const auto& pair : hash_prefix_map_) {
+    const PrefixSize& prefix_size = pair.first;
+    const HashPrefixes& hash_prefixes = pair.second;
+    const HashPrefix& hash_prefix = full_hash.substr(0, prefix_size);

[Nathan Parker, 2016/07/19 23:01:31]

This is a reference to a temporary... I'm not sure about the lifetime of that
here.  Might be safer to make it a non-reference, since there has to be a copy
anyway.

[vakh (use Gerrit instead), 2016/07/20 00:24:51]

Done.

+    if (HashPrefixMatches(hash_prefix, hash_prefixes.begin(),
+                          hash_prefixes.end())) {
+      return hash_prefix;
+    }
+  }
+  return HashPrefix();
+}
+
+// static
+bool V4Store::HashPrefixMatches(const HashPrefix& hash_prefix,
+                                const HashPrefixes::const_iterator& begin,
+                                const HashPrefixes::const_iterator& end) {
+  if (begin == end) {
+    return false;
+  }
+  size_t distance = std::distance(begin, end);
+  const PrefixSize& prefix_size = hash_prefix.length();

[Nathan Parker, 2016/07/19 23:01:31]

no need for reference, since it's just as cheap (cheaper, actually) to copy the
length than it is to copy a ptr to the length.  And this is a reference to a
temporary.

[vakh (use Gerrit instead), 2016/07/20 00:24:52]

Done.

+  DCHECK_EQ(0u, distance % prefix_size);
+  size_t mid_prefix_index = ((distance / prefix_size) / 2) * prefix_size;
+  HashPrefixes::const_iterator mid = begin + mid_prefix_index;
+  HashPrefix mid_prefix = HashPrefix(mid, mid + prefix_size);

[Nathan Parker, 2016/07/19 23:01:31]

This is making a copy, which I suppose would copy about log2(num_hashes) of the
prefixes.  To avoid it, you could switch to StringPiece.  I still thing
HashPrefix could be a StringPiece in most cases.

[vakh (use Gerrit instead), 2016/07/20 00:24:52]

It copies exactly prefix_size bytes.

+  if (mid_prefix == hash_prefix) {
+    return true;
+  }
+  if (hash_prefix < mid_prefix) {

[Nathan Parker, 2016/07/19 23:01:31]

You can avoid iterating over both strings twice (in most cases) by using
std::string::compare(..). It'll return <, =, or > 0 with at most one pass over
the strings.

In fact... it allows you to compare against a part of a string, which avoids the
copying above.

[vakh (use Gerrit instead), 2016/07/20 00:24:52]

Done.

+    return HashPrefixMatches(hash_prefix, begin, mid);
+  } else {
+    return HashPrefixMatches(hash_prefix, mid + prefix_size, end);
+  }
+}
+
 }  // namespace safe_browsing