visitedlink_common.cc 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
  1. // Copyright (c) 2011 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/visitedlink/common/visitedlink_common.h"
  5. #include <string.h> // for memset()
  6. #include <ostream>
  7. #include "base/bit_cast.h"
  8. #include "base/check.h"
  9. #include "base/hash/md5.h"
  10. #include "base/notreached.h"
  11. #include "url/gurl.h"
  12. namespace visitedlink {
  13. const VisitedLinkCommon::Fingerprint VisitedLinkCommon::null_fingerprint_ = 0;
  14. const VisitedLinkCommon::Hash VisitedLinkCommon::null_hash_ = -1;
  15. VisitedLinkCommon::VisitedLinkCommon()
  16. : hash_table_(nullptr), table_length_(0) {
  17. memset(salt_, 0, sizeof(salt_));
  18. }
  19. VisitedLinkCommon::~VisitedLinkCommon() {
  20. }
  21. // FIXME: this uses linear probing, it should be replaced with quadratic
  22. // probing or something better. See VisitedLinkWriter::AddFingerprint
  23. bool VisitedLinkCommon::IsVisited(const char* canonical_url,
  24. size_t url_len) const {
  25. if (url_len == 0)
  26. return false;
  27. if (!hash_table_ || table_length_ == 0)
  28. return false;
  29. return IsVisited(ComputeURLFingerprint(canonical_url, url_len));
  30. }
  31. bool VisitedLinkCommon::IsVisited(const GURL& url) const {
  32. return IsVisited(url.spec().data(), url.spec().size());
  33. }
  34. bool VisitedLinkCommon::IsVisited(Fingerprint fingerprint) const {
  35. // Go through the table until we find the item or an empty spot (meaning it
  36. // wasn't found). This loop will terminate as long as the table isn't full,
  37. // which should be enforced by AddFingerprint.
  38. Hash first_hash = HashFingerprint(fingerprint);
  39. Hash cur_hash = first_hash;
  40. while (true) {
  41. Fingerprint cur_fingerprint = FingerprintAt(cur_hash);
  42. if (cur_fingerprint == null_fingerprint_)
  43. return false; // End of probe sequence found.
  44. if (cur_fingerprint == fingerprint)
  45. return true; // Found a match.
  46. // This spot was taken, but not by the item we're looking for, search in
  47. // the next position.
  48. cur_hash++;
  49. if (cur_hash == table_length_)
  50. cur_hash = 0;
  51. if (cur_hash == first_hash) {
  52. // Wrapped around and didn't find an empty space, this means we're in an
  53. // infinite loop because AddFingerprint didn't do its job resizing.
  54. NOTREACHED();
  55. return false;
  56. }
  57. }
  58. }
  59. // Uses the top 64 bits of the MD5 sum of the canonical URL as the fingerprint,
  60. // this is as random as any other subset of the MD5SUM.
  61. //
  62. // FIXME: this uses the MD5SUM of the 16-bit character version. For systems
  63. // where wchar_t is not 16 bits (Linux uses 32 bits, I think), this will not be
  64. // compatable. We should define explicitly what should happen here across
  65. // platforms, and convert if necessary (probably to UTF-16).
  66. // static
  67. VisitedLinkCommon::Fingerprint VisitedLinkCommon::ComputeURLFingerprint(
  68. const char* canonical_url,
  69. size_t url_len,
  70. const uint8_t salt[LINK_SALT_LENGTH]) {
  71. DCHECK(url_len > 0) << "Canonical URLs should not be empty";
  72. base::MD5Context ctx;
  73. base::MD5Init(&ctx);
  74. base::MD5Update(&ctx, base::StringPiece(reinterpret_cast<const char*>(salt),
  75. LINK_SALT_LENGTH));
  76. base::MD5Update(&ctx, base::StringPiece(canonical_url, url_len));
  77. base::MD5Digest digest;
  78. base::MD5Final(&digest, &ctx);
  79. // This is the same as "return *(Fingerprint*)&digest.a;" but if we do that
  80. // direct cast the alignment could be wrong, and we can't access a 64-bit int
  81. // on arbitrary alignment on some processors. This reinterpret_casts it
  82. // down to a char array of the same size as fingerprint, and then does the
  83. // bit cast, which amounts to a memcpy. This does not handle endian issues.
  84. return base::bit_cast<Fingerprint, uint8_t[8]>(
  85. *reinterpret_cast<uint8_t(*)[8]>(&digest.a));
  86. }
  87. } // namespace visitedlink