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) {
+  // It should never be the case that more than one hash prefixes match a given
+  // full hash. However, if that happens, this method returns any one of them.
+  // It does not guarantee which one of those will be returned.
+  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;
+    HashPrefix hash_prefix = full_hash.substr(0, prefix_size);
+    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();
+  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);
+  int result = hash_prefix.compare(mid_prefix);
+  if (result == 0) {
+    return true;
+  } else if (result < 0) {
+    return HashPrefixMatches(hash_prefix, begin, mid);
+  } else {
+    return HashPrefixMatches(hash_prefix, mid + prefix_size, end);
+  }
+}
+
 }  // namespace safe_browsing