Index: net/base/registry_controlled_domains/registry_controlled_domain.cc |
diff --git a/net/base/registry_controlled_domains/registry_controlled_domain.cc b/net/base/registry_controlled_domains/registry_controlled_domain.cc |
index 56d5ed9d6a176864f6f4beb9af06d9d9cfafd485..057159ed7308e447d3bcf05019800b7c2b729794 100644 |
--- a/net/base/registry_controlled_domains/registry_controlled_domain.cc |
+++ b/net/base/registry_controlled_domains/registry_controlled_domain.cc |
@@ -53,26 +53,151 @@ |
#include "url/gurl.h" |
#include "url/url_parse.h" |
-#include "effective_tld_names.cc" |
- |
namespace net { |
namespace registry_controlled_domains { |
namespace { |
+#include "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; |
-const FindDomainPtr kDefaultFindDomainFunction = Perfect_Hash::FindDomain; |
+// 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); |
+} |
-// 'stringpool' is defined as a macro by the gperf-generated |
-// "effective_tld_names.cc". Provide a real constant value for it instead. |
-const char* const kDefaultStringPool = stringpool; |
-#undef stringpool |
+// 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; |
+} |
-FindDomainPtr g_find_domain_function = kDefaultFindDomainFunction; |
-const char* g_stringpool = kDefaultStringPool; |
+// 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, |
@@ -105,46 +230,40 @@ size_t GetRegistryLengthImpl( |
return 0; // This can't have a registry + domain. |
while (1) { |
const char* domain_str = host.data() + curr_start; |
- int domain_length = host_check_len - curr_start; |
- const DomainRule* rule = g_find_domain_function(domain_str, domain_length); |
- |
- // We need to compare the string after finding a match because the |
- // no-collisions of perfect hashing only refers to items in the set. Since |
- // we're searching for arbitrary domains, there could be collisions. |
- // Furthermore, if the apparent match is a private registry and we're not |
- // including those, it can't be an actual match. |
- if (rule) { |
- bool do_check = !(rule->type & kPrivateRule) || |
- private_filter == INCLUDE_PRIVATE_REGISTRIES; |
- if (do_check && base::strncasecmp(domain_str, |
- g_stringpool + rule->name_offset, |
- domain_length) == 0) { |
- // Exception rules override wildcard rules when the domain is an exact |
- // match, but wildcards take precedence when there's a subdomain. |
- if (rule->type & kWildcardRule && (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); |
- } |
+ 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); |
+ |
+ // 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 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 (rule->type & kExceptionRule) { |
- 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; |
+ if (type & kExceptionRule) { |
+ 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; |
} |
- |
- // If curr_start == host_check_begin, then the host is the registry |
- // itself, so return 0. |
- return (curr_start == host_check_begin) ? |
- 0 : (host.length() - curr_start); |
+ return host.length() - next_dot - 1; |
} |
+ |
+ // If curr_start == host_check_begin, then the host is the registry |
+ // itself, so return 0. |
+ return (curr_start == host_check_begin) ? 0 |
+ : (host.length() - curr_start); |
} |
if (next_dot >= host_check_len) // Catches std::string::npos as well. |
@@ -264,10 +383,16 @@ size_t GetRegistryLength( |
return GetRegistryLengthImpl(canon_host, unknown_filter, private_filter); |
} |
-void SetFindDomainFunctionAndStringPoolForTesting(FindDomainPtr function, |
- const char* stringpool) { |
- g_find_domain_function = function ? function : kDefaultFindDomainFunction; |
- g_stringpool = stringpool ? stringpool : kDefaultStringPool; |
+void SetFindDomainGraph() { |
+ g_graph = kDafsa; |
+ g_graph_length = sizeof(kDafsa); |
+} |
+ |
+void SetFindDomainGraph(const unsigned char* domains, size_t length) { |
+ CHECK(domains); |
+ CHECK_NE(length, 0); |
+ g_graph = domains; |
+ g_graph_length = length; |
} |
} // namespace registry_controlled_domains |