Index: chrome/browser/safe_browsing/bloom_filter.cc |
diff --git a/chrome/browser/safe_browsing/bloom_filter.cc b/chrome/browser/safe_browsing/bloom_filter.cc |
deleted file mode 100644 |
index 747a86f62b1715d36b3e76c726a4bf2fe0a1faba..0000000000000000000000000000000000000000 |
--- a/chrome/browser/safe_browsing/bloom_filter.cc |
+++ /dev/null |
@@ -1,223 +0,0 @@ |
-// Copyright (c) 2012 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 "chrome/browser/safe_browsing/bloom_filter.h" |
- |
-#include "base/metrics/histogram.h" |
-#include "base/rand_util.h" |
-#include "net/base/file_stream.h" |
-#include "net/base/net_errors.h" |
- |
-namespace { |
- |
-// The Jenkins 96 bit mix function: |
-// http://www.concentric.net/~Ttwang/tech/inthash.htm |
-uint32 HashMix(BloomFilter::HashKey hash_key, uint32 c) { |
- uint32 a = static_cast<uint32>(hash_key) & 0xFFFFFFFF; |
- uint32 b = static_cast<uint32>(hash_key >> 32) & 0xFFFFFFFF; |
- |
- a -= (b + c); a ^= (c >> 13); |
- b -= (c + a); b ^= (a << 8); |
- c -= (a + b); c ^= (b >> 13); |
- a -= (b + c); a ^= (c >> 12); |
- b -= (c + a); b ^= (a << 16); |
- c -= (a + b); c ^= (b >> 5); |
- a -= (b + c); a ^= (c >> 3); |
- b -= (c + a); b ^= (a << 10); |
- c -= (a + b); c ^= (b >> 15); |
- |
- return c; |
-} |
- |
-uint32 CalculateChecksum(const char* data, size_t size, |
- const BloomFilter::HashKeys& keys) { |
- uint32 checksum = 0; |
- for (size_t i = 0; i < keys.size(); ++i) { |
- checksum ^= static_cast<uint32>(keys[i]); |
- checksum ^= static_cast<uint32>(keys[i]>>32); |
- } |
- |
- // Watch out for sign-extension in the calculation. |
- // TODO(shess): Bit manipulation of signed chars is insane. |
- const unsigned char* udata = reinterpret_cast<const unsigned char*>(data); |
- for (size_t i = 0; i < size; ++i) { |
- checksum ^= udata[i] << ((i * 8) % 32); |
- } |
- |
- return checksum; |
-} |
- |
-} // namespace |
- |
-// static |
-int BloomFilter::FilterSizeForKeyCount(int key_count) { |
- const int default_min = BloomFilter::kBloomFilterMinSize; |
- const int number_of_keys = std::max(key_count, default_min); |
- return std::min(number_of_keys * BloomFilter::kBloomFilterSizeRatio, |
- BloomFilter::kBloomFilterMaxSize * 8); |
-} |
- |
-// static |
-void BloomFilter::RecordFailure(FailureType failure_type) { |
- UMA_HISTOGRAM_ENUMERATION("SB2.BloomFailure", failure_type, |
- FAILURE_FILTER_MAX); |
-} |
- |
-BloomFilter::BloomFilter(int bit_size) { |
- for (int i = 0; i < kNumHashKeys; ++i) |
- hash_keys_.push_back(base::RandUint64()); |
- |
- // Round up to the next boundary which fits bit_size. |
- byte_size_ = (bit_size + 7) / 8; |
- bit_size_ = byte_size_ * 8; |
- DCHECK_LE(bit_size, bit_size_); // strictly more bits. |
- data_.reset(new char[byte_size_]); |
- memset(data_.get(), 0, byte_size_); |
- checksum_ = CalculateChecksum(data_.get(), 0, hash_keys_); |
-} |
- |
-BloomFilter::BloomFilter(char* data, int size, const HashKeys& keys) |
- : hash_keys_(keys) { |
- byte_size_ = size; |
- bit_size_ = byte_size_ * 8; |
- data_.reset(data); |
- checksum_ = CalculateChecksum(data_.get(), byte_size_, hash_keys_); |
-} |
- |
-BloomFilter::~BloomFilter() { |
-} |
- |
-void BloomFilter::Insert(SBPrefix hash) { |
- uint32 hash_uint32 = static_cast<uint32>(hash); |
- for (size_t i = 0; i < hash_keys_.size(); ++i) { |
- uint32 index = HashMix(hash_keys_[i], hash_uint32) % bit_size_; |
- // Checksum needs to track the transition. Remove the if() when |
- // the checksum goes away. |
- if (!(data_[index / 8] & (1 << (index % 8)))) { |
- data_[index / 8] |= 1 << (index % 8); |
- checksum_ ^= 1u << (index % 32); |
- } |
- } |
-} |
- |
-bool BloomFilter::Exists(SBPrefix hash) const { |
- uint32 hash_uint32 = static_cast<uint32>(hash); |
- for (size_t i = 0; i < hash_keys_.size(); ++i) { |
- uint32 index = HashMix(hash_keys_[i], hash_uint32) % bit_size_; |
- if (!(data_[index / 8] & (1 << (index % 8)))) |
- return false; |
- } |
- return true; |
-} |
- |
-// static. |
-BloomFilter* BloomFilter::LoadFile(const FilePath& filter_name) { |
- net::FileStream filter(NULL); |
- |
- if (filter.OpenSync(filter_name, |
- base::PLATFORM_FILE_OPEN | |
- base::PLATFORM_FILE_READ) != net::OK) { |
- RecordFailure(FAILURE_FILTER_READ_OPEN); |
- return NULL; |
- } |
- |
- // Make sure we have a file version that we can understand. |
- int file_version; |
- int bytes_read = filter.ReadSync(reinterpret_cast<char*>(&file_version), |
- sizeof(file_version)); |
- if (bytes_read != sizeof(file_version) || file_version != kFileVersion) { |
- RecordFailure(FAILURE_FILTER_READ_VERSION); |
- return NULL; |
- } |
- |
- // Get all the random hash keys. |
- int num_keys; |
- bytes_read = filter.ReadSync(reinterpret_cast<char*>(&num_keys), |
- sizeof(num_keys)); |
- if (bytes_read != sizeof(num_keys) || |
- num_keys < 1 || num_keys > kNumHashKeys) { |
- RecordFailure(FAILURE_FILTER_READ_NUM_KEYS); |
- return NULL; |
- } |
- |
- HashKeys hash_keys; |
- for (int i = 0; i < num_keys; ++i) { |
- HashKey key; |
- bytes_read = filter.ReadSync(reinterpret_cast<char*>(&key), sizeof(key)); |
- if (bytes_read != sizeof(key)) { |
- RecordFailure(FAILURE_FILTER_READ_KEY); |
- return NULL; |
- } |
- hash_keys.push_back(key); |
- } |
- |
- // Read in the filter data, with sanity checks on min and max sizes. |
- int64 remaining64 = filter.Available(); |
- if (remaining64 < kBloomFilterMinSize) { |
- RecordFailure(FAILURE_FILTER_READ_DATA_MINSIZE); |
- return NULL; |
- } else if (remaining64 > kBloomFilterMaxSize) { |
- RecordFailure(FAILURE_FILTER_READ_DATA_MAXSIZE); |
- return NULL; |
- } |
- |
- int byte_size = static_cast<int>(remaining64); |
- scoped_array<char> data(new char[byte_size]); |
- bytes_read = filter.ReadSync(data.get(), byte_size); |
- if (bytes_read < byte_size) { |
- RecordFailure(FAILURE_FILTER_READ_DATA_SHORT); |
- return NULL; |
- } else if (bytes_read != byte_size) { |
- RecordFailure(FAILURE_FILTER_READ_DATA); |
- return NULL; |
- } |
- |
- // We've read everything okay, commit the data. |
- return new BloomFilter(data.release(), byte_size, hash_keys); |
-} |
- |
-bool BloomFilter::WriteFile(const FilePath& filter_name) const { |
- net::FileStream filter(NULL); |
- |
- if (filter.OpenSync(filter_name, |
- base::PLATFORM_FILE_WRITE | |
- base::PLATFORM_FILE_CREATE_ALWAYS) != net::OK) |
- return false; |
- |
- // Write the version information. |
- int version = kFileVersion; |
- int bytes_written = filter.WriteSync(reinterpret_cast<char*>(&version), |
- sizeof(version)); |
- if (bytes_written != sizeof(version)) |
- return false; |
- |
- // Write the number of random hash keys. |
- int num_keys = static_cast<int>(hash_keys_.size()); |
- bytes_written = filter.WriteSync(reinterpret_cast<char*>(&num_keys), |
- sizeof(num_keys)); |
- if (bytes_written != sizeof(num_keys)) |
- return false; |
- |
- for (int i = 0; i < num_keys; ++i) { |
- bytes_written = |
- filter.WriteSync(reinterpret_cast<const char*>(&hash_keys_[i]), |
- sizeof(hash_keys_[i])); |
- if (bytes_written != sizeof(hash_keys_[i])) |
- return false; |
- } |
- |
- // Write the filter data. |
- bytes_written = |
- filter.WriteSync(data_.get(), byte_size_); |
- if (bytes_written != byte_size_) |
- return false; |
- |
- return true; |
-} |
- |
-bool BloomFilter::CheckChecksum() const { |
- const uint32 checksum = CalculateChecksum(data_.get(), byte_size_, |
- hash_keys_); |
- return checksum_ == checksum; |
-} |