OLD | NEW |
---|---|
(Empty) | |
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 | |
3 // found in the LICENSE file. | |
4 | |
5 #include "net/base/dafsa/lookup_string.h" | |
6 | |
7 #include "base/logging.h" | |
8 | |
9 namespace net { | |
10 | |
11 namespace { | |
12 | |
13 // Read next offset from pos. | |
14 // Returns true if an offset could be read, false otherwise. | |
15 bool GetNextOffset(const unsigned char** pos, | |
eroman
2015/11/06 23:35:50
This shows up as a new file, is the expectation th
Adam Rice
2015/11/09 11:01:21
No, this is not new code. I have added --similarit
| |
16 const unsigned char* end, | |
17 const unsigned char** offset) { | |
18 if (*pos == end) | |
19 return false; | |
20 | |
21 // When reading an offset the byte array must always contain at least | |
22 // three more bytes to consume. First the offset to read, then a node | |
23 // to skip over and finally a destination node. No object can be smaller | |
24 // than one byte. | |
25 CHECK_LT(*pos + 2, end); | |
26 size_t bytes_consumed; | |
27 switch (**pos & 0x60) { | |
28 case 0x60: // Read three byte offset | |
29 *offset += (((*pos)[0] & 0x1F) << 16) | ((*pos)[1] << 8) | (*pos)[2]; | |
30 bytes_consumed = 3; | |
31 break; | |
32 case 0x40: // Read two byte offset | |
33 *offset += (((*pos)[0] & 0x1F) << 8) | (*pos)[1]; | |
34 bytes_consumed = 2; | |
35 break; | |
36 default: | |
37 *offset += (*pos)[0] & 0x3F; | |
38 bytes_consumed = 1; | |
39 } | |
40 if ((**pos & 0x80) != 0) { | |
41 *pos = end; | |
42 } else { | |
43 *pos += bytes_consumed; | |
44 } | |
45 return true; | |
46 } | |
47 | |
48 // Check if byte at offset is last in label. | |
49 bool IsEOL(const unsigned char* offset, const unsigned char* end) { | |
50 CHECK_LT(offset, end); | |
51 return (*offset & 0x80) != 0; | |
52 } | |
53 | |
54 // Check if byte at offset matches first character in key. | |
55 // This version matches characters not last in label. | |
56 bool IsMatch(const unsigned char* offset, | |
57 const unsigned char* end, | |
58 const char* key) { | |
59 CHECK_LT(offset, end); | |
60 return *offset == *key; | |
61 } | |
62 | |
63 // Check if byte at offset matches first character in key. | |
64 // This version matches characters last in label. | |
65 bool IsEndCharMatch(const unsigned char* offset, | |
66 const unsigned char* end, | |
67 const char* key) { | |
68 CHECK_LT(offset, end); | |
69 return *offset == (*key | 0x80); | |
70 } | |
71 | |
72 // Read return value at offset. | |
73 // Returns true if a return value could be read, false otherwise. | |
74 bool GetReturnValue(const unsigned char* offset, | |
75 const unsigned char* end, | |
76 int* return_value) { | |
77 CHECK_LT(offset, end); | |
78 if ((*offset & 0xE0) == 0x80) { | |
79 *return_value = *offset & 0x0F; | |
80 return true; | |
81 } | |
82 return false; | |
83 } | |
84 | |
85 } // namespace | |
86 | |
87 // Lookup a domain key in a byte array generated by make_dafsa.py. | |
88 // The rule type is returned if key is found, otherwise kDafsaNotFound is | |
89 // returned. | |
90 int LookupStringInDafsa(const unsigned char* graph, | |
91 size_t length, | |
92 const char* key, | |
93 size_t key_length) { | |
94 const unsigned char* pos = graph; | |
95 const unsigned char* end = graph + length; | |
96 const unsigned char* offset = pos; | |
97 const char* key_end = key + key_length; | |
98 while (GetNextOffset(&pos, end, &offset)) { | |
99 // char <char>+ end_char offsets | |
100 // char <char>+ return value | |
101 // char end_char offsets | |
102 // char return value | |
103 // end_char offsets | |
104 // return_value | |
105 bool did_consume = false; | |
106 if (key != key_end && !IsEOL(offset, end)) { | |
107 // Leading <char> is not a match. Don't dive into this child | |
108 if (!IsMatch(offset, end, key)) | |
109 continue; | |
110 did_consume = true; | |
111 ++offset; | |
112 ++key; | |
113 // Possible matches at this point: | |
114 // <char>+ end_char offsets | |
115 // <char>+ return value | |
116 // end_char offsets | |
117 // return value | |
118 // Remove all remaining <char> nodes possible | |
119 while (!IsEOL(offset, end) && key != key_end) { | |
120 if (!IsMatch(offset, end, key)) | |
121 return kDafsaNotFound; | |
122 ++key; | |
123 ++offset; | |
124 } | |
125 } | |
126 // Possible matches at this point: | |
127 // end_char offsets | |
128 // return_value | |
129 // If one or more <char> elements were consumed, a failure | |
130 // to match is terminal. Otherwise, try the next node. | |
131 if (key == key_end) { | |
132 int return_value; | |
133 if (GetReturnValue(offset, end, &return_value)) | |
134 return return_value; | |
135 // The DAFSA guarantees that if the first char is a match, all | |
136 // remaining char elements MUST match if the key is truly present. | |
137 if (did_consume) | |
138 return kDafsaNotFound; | |
139 continue; | |
140 } | |
141 if (!IsEndCharMatch(offset, end, key)) { | |
142 if (did_consume) | |
143 return kDafsaNotFound; // Unexpected | |
144 continue; | |
145 } | |
146 ++key; | |
147 pos = ++offset; // Dive into child | |
148 } | |
149 return kDafsaNotFound; // No match | |
150 } | |
151 | |
152 } // namespace net | |
OLD | NEW |