Reduce memory use of GetLevenshteinDistance() by almost 50%

components/ssl_errors/error_classification.cc

 // Copyright 2015 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 "components/ssl_errors/error_classification.h"
 
 #include <limits.h>
 #include <stddef.h>
 
 #include <vector>
@@ skipping 49 matching lines @@
 void RecordSSLInterstitialCause(bool overridable, SSLInterstitialCause event) {
   if (overridable) {
     UMA_HISTOGRAM_ENUMERATION("interstitial.ssl.cause.overridable", event,
                               UNUSED_INTERSTITIAL_CAUSE_ENTRY);
   } else {
     UMA_HISTOGRAM_ENUMERATION("interstitial.ssl.cause.nonoverridable", event,
                               UNUSED_INTERSTITIAL_CAUSE_ENTRY);
   }
 }
 
-// Returns the Levenshtein distance between |str1| and |str2|.
-// Which is the minimum number of single-character edits (i.e. insertions,
-// deletions or substitutions) required to change one word into the other.
-// https://en.wikipedia.org/wiki/Levenshtein_distance
-size_t GetLevenshteinDistance(const std::string& str1,
-                              const std::string& str2) {
-  if (str1 == str2)
-    return 0;
-  if (str1.size() == 0)
-    return str2.size();
-  if (str2.size() == 0)
-    return str1.size();
-  std::vector<size_t> kFirstRow(str2.size() + 1, 0);
-  std::vector<size_t> kSecondRow(str2.size() + 1, 0);
-
-  for (size_t i = 0; i < kFirstRow.size(); ++i)
-    kFirstRow[i] = i;
-  for (size_t i = 0; i < str1.size(); ++i) {
-    kSecondRow[0] = i + 1;
-    for (size_t j = 0; j < str2.size(); ++j) {
-      int cost = str1[i] == str2[j] ? 0 : 1;
-      kSecondRow[j + 1] =
-          std::min(std::min(kSecondRow[j] + 1, kFirstRow[j + 1] + 1),
-                   kFirstRow[j] + cost);
-    }
-    for (size_t j = 0; j < kFirstRow.size(); j++)
-      kFirstRow[j] = kSecondRow[j];
-  }
-  return kSecondRow[str2.size()];
-}
-
 std::vector<HostnameTokens> GetTokenizedDNSNames(
     const std::vector<std::string>& dns_names) {
   std::vector<HostnameTokens> dns_name_tokens;
   for (const auto& dns_name : dns_names) {
     HostnameTokens dns_name_token_single;
     if (dns_name.empty() || dns_name.find('\0') != std::string::npos ||
         !(IsHostNameKnownTLD(dns_name))) {
       dns_name_token_single.push_back(std::string());
     } else {
       dns_name_token_single = Tokenize(dns_name);
@@ skipping 31 matching lines @@
   std::vector<std::string> dns_names;
   cert.GetDNSNames(&dns_names);
   return GetWWWSubDomainMatch(request_url, dns_names, &www_host);
 }
 
 // The time to use when doing build time operations in browser tests.
 base::LazyInstance<base::Time> g_testing_build_time = LAZY_INSTANCE_INITIALIZER;
 
 }  // namespace
 
+// Returns the Levenshtein distance between |str1| and |str2|.
+// Which is the minimum number of single-character edits (i.e. insertions,
+// deletions or substitutions) required to change one word into the other.
+// https://en.wikipedia.org/wiki/Levenshtein_distance
+size_t GetLevenshteinDistance(const std::string& str1,
+                              const std::string& str2) {
+  if (str1 == str2)
+    return 0;
+  if (str1.size() == 0)
+    return str2.size();
+  if (str2.size() == 0)
+    return str1.size();
+
+  std::vector<size_t> row(str2.size() + 1);
+  for (size_t i = 0; i < row.size(); ++i)
+    row[i] = i;
+
+  for (size_t i = 0; i < str1.size(); ++i) {
+    row[0] = i + 1;
+    size_t previous = i;
+    for (size_t j = 0; j < str2.size(); ++j) {
+      size_t old_row = row[j + 1];
+      int cost = str1[i] == str2[j] ? 0 : 1;
+      row[j + 1] = std::min(std::min(row[j], row[j + 1]) + 1, previous + cost);
+      previous = old_row;
+    }
+  }
+  return row[str2.size()];
+}
+
+
 void RecordUMAStatistics(bool overridable,
                          const base::Time& current_time,
                          const GURL& request_url,
                          int cert_error,
                          const net::X509Certificate& cert) {
   ssl_errors::ErrorInfo::ErrorType type =
       ssl_errors::ErrorInfo::NetErrorToErrorType(cert_error);
   UMA_HISTOGRAM_ENUMERATION("interstitial.ssl_error_type", type,
                             ssl_errors::ErrorInfo::END_OF_ENUM);
   switch (type) {
@@ skipping 219 matching lines @@
   static const int kDistinctNameThreshold = 5;
   if (dns_names_size > kDistinctNameThreshold)
     return true;
 
   // Heuristic - The edit distance between all the strings should be at least 5
   // for it to be counted as a shared SSLCertificate. If even one pair of
   // strings edit distance is below 5 then the certificate is no longer
   // considered as a shared certificate. Include the host name in the URL also
   // while comparing.
   dns_names.push_back(host_name);
-  static const size_t kMinimumEditDsitance = 5;
+  static const size_t kMinimumEditDistance = 5;
   for (size_t i = 0; i < dns_names_size; ++i) {
     for (size_t j = i + 1; j < dns_names_size; ++j) {
       size_t edit_distance = GetLevenshteinDistance(dns_names[i], dns_names[j]);
-      if (edit_distance < kMinimumEditDsitance)
+      if (edit_distance < kMinimumEditDistance)
         return false;
     }
   }
   return true;
 }
 
 bool IsCertLikelyFromSameDomain(const GURL& request_url,
                                 const net::X509Certificate& cert) {
   std::string host_name = request_url.host();
   std::vector<std::string> dns_names;
@@ skipping 16 matching lines @@
   return std::find(dns_names_domain.begin(), dns_names_domain.end() - 1,
                    host_name_domain) != dns_names_domain.end() - 1;
 }
 
 bool IsHostnameNonUniqueOrDotless(const std::string& hostname) {
   return net::IsHostnameNonUnique(hostname) ||
          hostname.find('.') == std::string::npos;
 }
 
 }  // namespace ssl_errors