Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(14)

Side by Side Diff: base/lookup_string_in_fixed_set.h

Issue 2784933002: Mitigate spoofing attempt using Latin letters. (Closed)
Patch Set: add similarity check unittests Created 3 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 // Copyright 2015 The Chromium Authors. All rights reserved. 1 // Copyright 2015 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #ifndef NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_ 5 #ifndef BASE_LOOKUP_STRING_IN_FIXED_SET_H_
6 #define NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_ 6 #define BASE_LOOKUP_STRING_IN_FIXED_SET_H_
7 7
8 #include <stddef.h> 8 #include <stddef.h>
9 9
10 #include "net/base/net_export.h" 10 #include "base/base_export.h"
11 11
12 namespace net { 12 namespace base {
13 13
14 enum { 14 enum {
15 kDafsaNotFound = -1, // key is not in set 15 kDafsaNotFound = -1, // key is not in set
16 kDafsaFound = 0, // key is in set 16 kDafsaFound = 0, // key is in set
17 // The following return values are used by the implementation of 17 // The following return values are used by the implementation of
18 // GetDomainAndRegistry() and are probably not generally useful. 18 // GetDomainAndRegistry() and are probably not generally useful.
19 kDafsaExceptionRule = 1, // key excluded from set via exception 19 kDafsaExceptionRule = 1, // key excluded from set via exception
20 kDafsaWildcardRule = 2, // key matched a wildcard rule 20 kDafsaWildcardRule = 2, // key matched a wildcard rule
21 kDafsaPrivateRule = 4, // key matched a private rule 21 kDafsaPrivateRule = 4, // key matched a private rule
22 }; 22 };
23 23
24 // Looks up the string |key| with length |key_length| in a fixed set of 24 // Looks up the string |key| with length |key_length| in a fixed set of
25 // strings. The set of strings must be known at compile time. It is converted to 25 // strings. The set of strings must be known at compile time. It is converted to
26 // a graph structure named a DAFSA (Deterministic Acyclic Finite State 26 // a graph structure named a DAFSA (Deterministic Acyclic Finite State
27 // Automaton) by the script make_dafsa.py during compilation. This permits 27 // Automaton) by the script make_dafsa.py during compilation. This permits
28 // efficient (in time and space) lookup. The graph generated by make_dafsa.py 28 // efficient (in time and space) lookup. The graph generated by make_dafsa.py
29 // takes the form of a constant byte array which should be supplied via the 29 // takes the form of a constant byte array which should be supplied via the
30 // |graph| and |length| parameters. The return value is kDafsaNotFound, 30 // |graph| and |length| parameters. The return value is kDafsaNotFound,
31 // kDafsaFound, or a bitmap consisting of one or more of kDafsaExceptionRule, 31 // kDafsaFound, or a bitmap consisting of one or more of kDafsaExceptionRule,
32 // kDafsaWildcardRule and kDafsaPrivateRule ORed together. 32 // kDafsaWildcardRule and kDafsaPrivateRule ORed together.
33 // 33 //
34 // TODO(nick): Replace this with FixedSetIncrementalLookup everywhere. 34 // TODO(nick): Replace this with FixedSetIncrementalLookup everywhere.
35 NET_EXPORT int LookupStringInFixedSet(const unsigned char* graph, 35 BASE_EXPORT int LookupStringInFixedSet(const unsigned char* graph,
36 size_t length, 36 size_t length,
37 const char* key, 37 const char* key,
38 size_t key_length); 38 size_t key_length);
39 39
40 // FixedSetIncrementalLookup provides efficient membership and prefix queries 40 // FixedSetIncrementalLookup provides efficient membership and prefix queries
41 // against a fixed set of strings. The set of strings must be known at compile 41 // against a fixed set of strings. The set of strings must be known at compile
42 // time. The set is converted to a graph structure named a DAFSA (Deterministic 42 // time. The set is converted to a graph structure named a DAFSA (Deterministic
43 // Acyclic Finite State Automaton) by the script //net/tools/dafsa/make_dafsa.py 43 // Acyclic Finite State Automaton) by the script //net/tools/dafsa/make_dafsa.py
44 // during compilation. The conversion generates a C++ header file defining the 44 // during compilation. The conversion generates a C++ header file defining the
45 // encoded graph as a constant byte array. This class provides a fast, constant- 45 // encoded graph as a constant byte array. This class provides a fast, constant-
(...skipping 23 matching lines...) Expand all
69 // FixedSetIncrementalLookup prefix_lookup(kDafsa, sizeof(kDafsa)); 69 // FixedSetIncrementalLookup prefix_lookup(kDafsa, sizeof(kDafsa));
70 // size_t longest_match_end = 0; 70 // size_t longest_match_end = 0;
71 // for (size_t i = 0; i < input.length(); ++i) { 71 // for (size_t i = 0; i < input.length(); ++i) {
72 // if (!prefix_lookup.Advance(input[i])) 72 // if (!prefix_lookup.Advance(input[i]))
73 // break; 73 // break;
74 // if (prefix_lookup.GetResultForCurrentSequence() == 3) 74 // if (prefix_lookup.GetResultForCurrentSequence() == 3)
75 // longest_match_end = (i + 1); 75 // longest_match_end = (i + 1);
76 // } 76 // }
77 // return input.substr(0, longest_match_end); 77 // return input.substr(0, longest_match_end);
78 // 78 //
79 class NET_EXPORT FixedSetIncrementalLookup { 79 class BASE_EXPORT FixedSetIncrementalLookup {
80 public: 80 public:
81 // Begin a lookup against the provided fixed set. |graph| and |length| 81 // Begin a lookup against the provided fixed set. |graph| and |length|
82 // describe a byte buffer generated by the make_dafsa.py script, as described 82 // describe a byte buffer generated by the make_dafsa.py script, as described
83 // in the class comment. 83 // in the class comment.
84 // 84 //
85 // FixedSetIncrementalLookup is initialized to a state corresponding to the 85 // FixedSetIncrementalLookup is initialized to a state corresponding to the
86 // empty input sequence. Calling GetResultForCurrentSequence() in the initial 86 // empty input sequence. Calling GetResultForCurrentSequence() in the initial
87 // state would indicate whether the empty string appears in the fixed set. 87 // state would indicate whether the empty string appears in the fixed set.
88 // Characters can be added to the sequence by calling Advance(), and the 88 // Characters can be added to the sequence by calling Advance(), and the
89 // lookup result can be checked after each addition by calling 89 // lookup result can be checked after each addition by calling
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
135 // Pointer just past the end of the graph. |pos_| should never get here. This 135 // Pointer just past the end of the graph. |pos_| should never get here. This
136 // is used only in DCHECKs. 136 // is used only in DCHECKs.
137 const unsigned char* end_; 137 const unsigned char* end_;
138 138
139 // Contains the current decoder state. If true, |pos_| points to a label 139 // Contains the current decoder state. If true, |pos_| points to a label
140 // character or a return code. If false, |pos_| points to a sequence of 140 // character or a return code. If false, |pos_| points to a sequence of
141 // offsets that indicate the child nodes of the current state. 141 // offsets that indicate the child nodes of the current state.
142 bool pos_is_label_character_; 142 bool pos_is_label_character_;
143 }; 143 };
144 144
145 } // namespace net 145 } // namespace base
146 146
147 #endif // NET_BASE_LOOKUP_STRING_IN_FIXED_SET_H_ 147 #endif // BASE_LOOKUP_STRING_IN_FIXED_SET_H_
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698