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, | |
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 kNotFound is returned. | |
89 int LookupString(const unsigned char* graph, | |
tyoshino (SeeGerritForStatus)
2015/10/19 07:15:10
You've moved this out of the anonymous namespace.
Adam Rice
2015/10/19 12:03:07
Good point, thank you. I changed the name to Looku
| |
90 size_t length, | |
91 const char* key, | |
92 size_t key_length) { | |
93 const unsigned char* pos = graph; | |
94 const unsigned char* end = graph + length; | |
95 const unsigned char* offset = pos; | |
96 const char* key_end = key + key_length; | |
97 while (GetNextOffset(&pos, end, &offset)) { | |
98 // char <char>+ end_char offsets | |
99 // char <char>+ return value | |
100 // char end_char offsets | |
101 // char return value | |
102 // end_char offsets | |
103 // return_value | |
104 bool did_consume = false; | |
105 if (key != key_end && !IsEOL(offset, end)) { | |
106 // Leading <char> is not a match. Don't dive into this child | |
107 if (!IsMatch(offset, end, key)) | |
108 continue; | |
109 did_consume = true; | |
110 ++offset; | |
111 ++key; | |
112 // Possible matches at this point: | |
113 // <char>+ end_char offsets | |
114 // <char>+ return value | |
115 // end_char offsets | |
116 // return value | |
117 // Remove all remaining <char> nodes possible | |
118 while (!IsEOL(offset, end) && key != key_end) { | |
119 if (!IsMatch(offset, end, key)) | |
120 return kNotFound; | |
121 ++key; | |
122 ++offset; | |
123 } | |
124 } | |
125 // Possible matches at this point: | |
126 // end_char offsets | |
127 // return_value | |
128 // If one or more <char> elements were consumed, a failure | |
129 // to match is terminal. Otherwise, try the next node. | |
130 if (key == key_end) { | |
131 int return_value; | |
132 if (GetReturnValue(offset, end, &return_value)) | |
133 return return_value; | |
134 // The DAFSA guarantees that if the first char is a match, all | |
135 // remaining char elements MUST match if the key is truly present. | |
136 if (did_consume) | |
137 return kNotFound; | |
138 continue; | |
139 } | |
140 if (!IsEndCharMatch(offset, end, key)) { | |
141 if (did_consume) | |
142 return kNotFound; // Unexpected | |
143 continue; | |
144 } | |
145 ++key; | |
146 pos = ++offset; // Dive into child | |
147 } | |
148 return kNotFound; // No match | |
149 } | |
150 | |
151 } // namespace net | |
OLD | NEW |