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 278 matching lines @@
 // 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;
+  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) {
-    kSecondRow[0] = i + 1;
+    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;
-      kSecondRow[j + 1] =
-          std::min(std::min(kSecondRow[j] + 1, kFirstRow[j + 1] + 1),
-                   kFirstRow[j] + cost);
+      row[j + 1] = std::min(std::min(row[j], row[j + 1]) + 1, previous + cost);
+      previous = old_row;
     }
-    for (size_t j = 0; j < kFirstRow.size(); j++)
-      kFirstRow[j] = kSecondRow[j];
   }
-  return kSecondRow[str2.size()];
+  return row[str2.size()];
 }
 
 bool IsSubDomainOutsideWildcard(const GURL& request_url,
                                 const net::X509Certificate& cert) {
   std::string host_name = request_url.host();
   HostnameTokens host_name_tokens = Tokenize(host_name);
   std::vector<std::string> dns_names;
   cert.GetDNSNames(&dns_names);
   bool result = false;
 
@@ skipping 47 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