[DO NOT COMMIT] Re-use the dafsa code for s-w-r histograms

net/base/registry_controlled_domains/registry_controlled_domain.cc

 // 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.
 
 // NB: Modelled after Mozilla's code (originally written by Pamela Greene,
 // later modified by others), but almost entirely rewritten for Chrome.
 //   (netwerk/dns/src/nsEffectiveTLDService.cpp)
 /* ***** BEGIN LICENSE BLOCK *****
  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  *
@@ skipping 30 matching lines @@
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "net/base/registry_controlled_domains/registry_controlled_domain.h"
 
 #include "base/logging.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
+#include "net/base/dafsa/lookup_string.h"
 #include "net/base/net_module.h"
 #include "net/base/net_util.h"
 #include "url/gurl.h"
 #include "url/third_party/mozilla/url_parse.h"
 
 namespace net {
 namespace registry_controlled_domains {
 
 namespace {
 #include "net/base/registry_controlled_domains/effective_tld_names-inc.cc"
 
 // See make_dafsa.py for documentation of the generated dafsa byte array.
 
 const unsigned char* g_graph = kDafsa;
 size_t g_graph_length = sizeof(kDafsa);
 
-const int kNotFound = -1;
-const int kExceptionRule = 1;
-const int kWildcardRule = 2;
-const int kPrivateRule = 4;
-
-// Read next offset from pos.
-// Returns true if an offset could be read, false otherwise.
-bool GetNextOffset(const unsigned char** pos, const unsigned char* end,
-                   const unsigned char** offset) {
-  if (*pos == end)
-    return false;
-
-  // When reading an offset the byte array must always contain at least
-  // three more bytes to consume. First the offset to read, then a node
-  // to skip over and finally a destination node. No object can be smaller
-  // than one byte.
-  CHECK_LT(*pos + 2, end);
-  size_t bytes_consumed;
-  switch (**pos & 0x60) {
-    case 0x60:  // Read three byte offset
-      *offset += (((*pos)[0] & 0x1F) << 16) | ((*pos)[1] << 8) | (*pos)[2];
-      bytes_consumed = 3;
-      break;
-    case 0x40:  // Read two byte offset
-      *offset += (((*pos)[0] & 0x1F) << 8) | (*pos)[1];
-      bytes_consumed = 2;
-      break;
-    default:
-      *offset += (*pos)[0] & 0x3F;
-      bytes_consumed = 1;
-  }
-  if ((**pos & 0x80) != 0) {
-    *pos = end;
-  } else {
-    *pos += bytes_consumed;
-  }
-  return true;
-}
-
-// Check if byte at offset is last in label.
-bool IsEOL(const unsigned char* offset, const unsigned char* end) {
-  CHECK_LT(offset, end);
-  return (*offset & 0x80) != 0;
-}
-
-// Check if byte at offset matches first character in key.
-// This version matches characters not last in label.
-bool IsMatch(const unsigned char* offset, const unsigned char* end,
-             const char* key) {
-  CHECK_LT(offset, end);
-  return *offset == *key;
-}
-
-// Check if byte at offset matches first character in key.
-// This version matches characters last in label.
-bool IsEndCharMatch(const unsigned char* offset, const unsigned char* end,
-                    const char* key) {
-  CHECK_LT(offset, end);
-  return *offset == (*key | 0x80);
-}
-
-// Read return value at offset.
-// Returns true if a return value could be read, false otherwise.
-bool GetReturnValue(const unsigned char* offset, const unsigned char* end,
-                    int* return_value) {
-  CHECK_LT(offset, end);
-  if ((*offset & 0xE0) == 0x80) {
-    *return_value = *offset & 0x0F;
-    return true;
-  }
-  return false;
-}
-
-// Lookup a domain key in a byte array generated by make_dafsa.py.
-// The rule type is returned if key is found, otherwise kNotFound is returned.
-int LookupString(const unsigned char* graph, size_t length, const char* key,
-                 size_t key_length) {
-  const unsigned char* pos = graph;
-  const unsigned char* end = graph + length;
-  const unsigned char* offset = pos;
-  const char* key_end = key + key_length;
-  while (GetNextOffset(&pos, end, &offset)) {
-    //   char <char>+ end_char offsets
-    //   char <char>+ return value
-    //   char end_char offsets
-    //   char return value
-    //   end_char offsets
-    //   return_value
-    bool did_consume = false;
-    if (key != key_end && !IsEOL(offset, end)) {
-      // Leading <char> is not a match. Don't dive into this child
-      if (!IsMatch(offset, end, key))
-        continue;
-      did_consume = true;
-      ++offset;
-      ++key;
-      // Possible matches at this point:
-      // <char>+ end_char offsets
-      // <char>+ return value
-      // end_char offsets
-      // return value
-      // Remove all remaining <char> nodes possible
-      while (!IsEOL(offset, end) && key != key_end) {
-        if (!IsMatch(offset, end, key))
-          return kNotFound;
-        ++key;
-        ++offset;
-      }
-    }
-    // Possible matches at this point:
-    // end_char offsets
-    // return_value
-    // If one or more <char> elements were consumed, a failure
-    // to match is terminal. Otherwise, try the next node.
-    if (key == key_end) {
-      int return_value;
-      if (GetReturnValue(offset, end, &return_value))
-        return return_value;
-      // The DAFSA guarantees that if the first char is a match, all
-      // remaining char elements MUST match if the key is truly present.
-      if (did_consume)
-        return kNotFound;
-      continue;
-    }
-    if (!IsEndCharMatch(offset, end, key)) {
-      if (did_consume)
-        return kNotFound;  // Unexpected
-      continue;
-    }
-    ++key;
-    pos = ++offset;  // Dive into child
-  }
-  return kNotFound;  // No match
-}
-
 size_t GetRegistryLengthImpl(
     const std::string& host,
     UnknownRegistryFilter unknown_filter,
     PrivateRegistryFilter private_filter) {
   DCHECK(!host.empty());
 
   // Skip leading dots.
   const size_t host_check_begin = host.find_first_not_of('.');
   if (host_check_begin == std::string::npos)
     return 0;  // Host is only dots.
@@ skipping 12 matching lines @@
   // Walk up the domain tree, most specific to least specific,
   // looking for matches at each level.
   size_t prev_start = std::string::npos;
   size_t curr_start = host_check_begin;
   size_t next_dot = host.find('.', curr_start);
   if (next_dot >= host_check_len)  // Catches std::string::npos as well.
     return 0;  // This can't have a registry + domain.
   while (1) {
     const char* domain_str = host.data() + curr_start;
     size_t domain_length = host_check_len - curr_start;
-    int type = LookupString(g_graph, g_graph_length, domain_str, domain_length);
-    bool do_check =
-        type != kNotFound && (!(type & kPrivateRule) ||
-                              private_filter == INCLUDE_PRIVATE_REGISTRIES);
+    int type =
+        LookupStringInDafsa(g_graph, g_graph_length, domain_str, domain_length);
+    bool do_check = type != kDafsaNotFound &&
+                    (!(type & kDafsaPrivateRule) ||
+                     private_filter == INCLUDE_PRIVATE_REGISTRIES);
 
     // If the apparent match is a private registry and we're not including
     // those, it can't be an actual match.
     if (do_check) {
       // Exception rules override wildcard rules when the domain is an exact
       // match, but wildcards take precedence when there's a subdomain.
-      if (type & kWildcardRule && (prev_start != std::string::npos)) {
+      if (type & kDafsaWildcardRule && (prev_start != std::string::npos)) {
         // If prev_start == host_check_begin, then the host is the registry
         // itself, so return 0.
         return (prev_start == host_check_begin) ? 0
                                                 : (host.length() - prev_start);
       }
 
-      if (type & kExceptionRule) {
+      if (type & kDafsaExceptionRule) {
         if (next_dot == std::string::npos) {
           // If we get here, we had an exception rule with no dots (e.g.
           // "!foo").  This would only be valid if we had a corresponding
           // wildcard rule, which would have to be "*".  But we explicitly
           // disallow that case, so this kind of rule is invalid.
           NOTREACHED() << "Invalid exception rule";
           return 0;
         }
         return host.length() - next_dot - 1;
       }
@@ skipping 124 matching lines @@
 
 void SetFindDomainGraph(const unsigned char* domains, size_t length) {
   CHECK(domains);
   CHECK_NE(length, 0u);
   g_graph = domains;
   g_graph_length = length;
 }
 
 }  // namespace registry_controlled_domains
 }  // namespace net