1/*
2 * Copyright (C) 2015 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "DFABytecodeInterpreter.h"
28
29#include "ContentExtensionsDebugging.h"
30#include <wtf/text/CString.h>
31
32#if ENABLE(CONTENT_EXTENSIONS)
33
34namespace WebCore {
35
36namespace ContentExtensions {
37
38template <typename IntType>
39static inline IntType getBits(const DFABytecode* bytecode, uint32_t bytecodeLength, uint32_t index)
40{
41 ASSERT_UNUSED(bytecodeLength, index + sizeof(IntType) <= bytecodeLength);
42 return *reinterpret_cast<const IntType*>(&bytecode[index]);
43}
44
45static inline DFABytecodeInstruction getInstruction(const DFABytecode* bytecode, uint32_t bytecodeLength, uint32_t index)
46{
47 return static_cast<DFABytecodeInstruction>(getBits<uint8_t>(bytecode, bytecodeLength, index) & DFABytecodeInstructionMask);
48}
49
50static inline size_t jumpSizeInBytes(DFABytecodeJumpSize jumpSize)
51{
52 switch (jumpSize) {
53 case Int8:
54 return sizeof(int8_t);
55 case Int16:
56 return sizeof(int16_t);
57 case Int24:
58 return sizeof(uint16_t) + sizeof(int8_t);
59 case Int32:
60 return sizeof(int32_t);
61 default:
62 RELEASE_ASSERT_NOT_REACHED();
63 }
64}
65
66static inline DFABytecodeJumpSize getJumpSize(const DFABytecode* bytecode, uint32_t bytecodeLength, uint32_t index)
67{
68 DFABytecodeJumpSize jumpSize = static_cast<DFABytecodeJumpSize>(getBits<uint8_t>(bytecode, bytecodeLength, index) & DFABytecodeJumpSizeMask);
69 ASSERT(jumpSize == DFABytecodeJumpSize::Int32 || jumpSize == DFABytecodeJumpSize::Int24 || jumpSize == DFABytecodeJumpSize::Int16 || jumpSize == DFABytecodeJumpSize::Int8);
70 return jumpSize;
71}
72
73static inline int32_t getJumpDistance(const DFABytecode* bytecode, uint32_t bytecodeLength, uint32_t index, DFABytecodeJumpSize jumpSize)
74{
75 switch (jumpSize) {
76 case Int8:
77 return getBits<int8_t>(bytecode, bytecodeLength, index);
78 case Int16:
79 return getBits<int16_t>(bytecode, bytecodeLength, index);
80 case Int24:
81 return getBits<uint16_t>(bytecode, bytecodeLength, index) | (static_cast<int32_t>(getBits<int8_t>(bytecode, bytecodeLength, index + sizeof(uint16_t))) << 16);
82 case Int32:
83 return getBits<int32_t>(bytecode, bytecodeLength, index);
84 default:
85 RELEASE_ASSERT_NOT_REACHED();
86 }
87}
88
89static inline bool matchesCondition(uint64_t actionAndFlags, const DFABytecodeInterpreter::Actions& conditionActions)
90{
91 bool ifCondition = actionAndFlags & IfConditionFlag;
92 bool condition = conditionActions.contains(actionAndFlags);
93 return ifCondition == condition;
94}
95
96void DFABytecodeInterpreter::interpretAppendAction(uint32_t& programCounter, Actions& actions, bool ifCondition)
97{
98 ASSERT(getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::AppendAction
99 || getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::AppendActionWithIfCondition);
100 uint64_t action = (ifCondition ? IfConditionFlag : 0) | static_cast<uint64_t>(getBits<uint32_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction)));
101 if (!m_topURLActions || matchesCondition(action, *m_topURLActions))
102 actions.add(action);
103
104 programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
105 ASSERT(instructionSizeWithArguments(DFABytecodeInstruction::AppendAction) == instructionSizeWithArguments(DFABytecodeInstruction::AppendActionWithIfCondition));
106}
107
108void DFABytecodeInterpreter::interpretTestFlagsAndAppendAction(uint32_t& programCounter, uint16_t flags, Actions& actions, bool ifCondition)
109{
110 ASSERT(getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::TestFlagsAndAppendAction
111 || getInstruction(m_bytecode, m_bytecodeLength, programCounter) == DFABytecodeInstruction::TestFlagsAndAppendActionWithIfCondition);
112 uint16_t flagsToCheck = getBits<uint16_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction));
113
114 uint16_t loadTypeFlags = flagsToCheck & LoadTypeMask;
115 uint16_t resourceTypeFlags = flagsToCheck & ResourceTypeMask;
116
117 bool loadTypeMatches = loadTypeFlags ? (loadTypeFlags & flags) : true;
118 bool resourceTypeMatches = resourceTypeFlags ? (resourceTypeFlags & flags) : true;
119
120 if (loadTypeMatches && resourceTypeMatches) {
121 uint64_t actionAndFlags = (ifCondition ? IfConditionFlag : 0) | (static_cast<uint64_t>(flagsToCheck) << 32) | static_cast<uint64_t>(getBits<uint32_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint16_t)));
122 if (!m_topURLActions || matchesCondition(actionAndFlags, *m_topURLActions))
123 actions.add(actionAndFlags);
124 }
125 programCounter += instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction);
126 ASSERT(instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction) == instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendActionWithIfCondition));
127}
128
129template<bool caseSensitive>
130inline void DFABytecodeInterpreter::interpetJumpTable(const char* url, uint32_t& urlIndex, uint32_t& programCounter, bool& urlIndexIsAfterEndOfString)
131{
132 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
133
134 char character = caseSensitive ? url[urlIndex] : toASCIILower(url[urlIndex]);
135 uint8_t firstCharacter = getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction));
136 uint8_t lastCharacter = getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t));
137 if (character >= firstCharacter && character <= lastCharacter) {
138 uint32_t startOffset = programCounter + sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t);
139 uint32_t jumpLocation = startOffset + (character - firstCharacter) * jumpSizeInBytes(jumpSize);
140 programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
141 if (!character)
142 urlIndexIsAfterEndOfString = true;
143 urlIndex++; // This represents an edge in the DFA.
144 } else
145 programCounter += sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t) + jumpSizeInBytes(jumpSize) * (lastCharacter - firstCharacter + 1);
146}
147
148DFABytecodeInterpreter::Actions DFABytecodeInterpreter::actionsMatchingEverything()
149{
150 Actions actions;
151
152 // DFA header.
153 uint32_t dfaBytecodeLength = getBits<uint32_t>(m_bytecode, m_bytecodeLength, 0);
154 uint32_t programCounter = sizeof(uint32_t);
155
156 while (programCounter < dfaBytecodeLength) {
157 DFABytecodeInstruction instruction = getInstruction(m_bytecode, m_bytecodeLength, programCounter);
158 if (instruction == DFABytecodeInstruction::AppendAction)
159 interpretAppendAction(programCounter, actions, false);
160 else if (instruction == DFABytecodeInstruction::AppendActionWithIfCondition)
161 interpretAppendAction(programCounter, actions, true);
162 else if (instruction == DFABytecodeInstruction::TestFlagsAndAppendAction)
163 programCounter += instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendAction);
164 else if (instruction == DFABytecodeInstruction::TestFlagsAndAppendActionWithIfCondition)
165 programCounter += instructionSizeWithArguments(DFABytecodeInstruction::TestFlagsAndAppendActionWithIfCondition);
166 else
167 break;
168 }
169 return actions;
170}
171
172DFABytecodeInterpreter::Actions DFABytecodeInterpreter::interpretWithConditions(const CString& urlCString, uint16_t flags, const DFABytecodeInterpreter::Actions& topURLActions)
173{
174 ASSERT(!m_topURLActions);
175 m_topURLActions = &topURLActions;
176 DFABytecodeInterpreter::Actions actions = interpret(urlCString, flags);
177 m_topURLActions = nullptr;
178 return actions;
179}
180
181DFABytecodeInterpreter::Actions DFABytecodeInterpreter::interpret(const CString& urlCString, uint16_t flags)
182{
183 const char* url = urlCString.data();
184 ASSERT(url);
185
186 Actions actions;
187
188 uint32_t programCounter = 0;
189 while (programCounter < m_bytecodeLength) {
190
191 // DFA header.
192 uint32_t dfaStart = programCounter;
193 uint32_t dfaBytecodeLength = getBits<uint32_t>(m_bytecode, m_bytecodeLength, programCounter);
194 programCounter += sizeof(uint32_t);
195
196 // Skip the actions without flags on the DFA root. These are accessed via actionsMatchingEverything.
197 if (!dfaStart) {
198 while (programCounter < dfaBytecodeLength) {
199 DFABytecodeInstruction instruction = getInstruction(m_bytecode, m_bytecodeLength, programCounter);
200 if (instruction == DFABytecodeInstruction::AppendAction)
201 programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendAction);
202 else if (instruction == DFABytecodeInstruction::AppendActionWithIfCondition)
203 programCounter += instructionSizeWithArguments(DFABytecodeInstruction::AppendActionWithIfCondition);
204 else if (instruction == DFABytecodeInstruction::TestFlagsAndAppendAction)
205 interpretTestFlagsAndAppendAction(programCounter, flags, actions, false);
206 else if (instruction == DFABytecodeInstruction::TestFlagsAndAppendActionWithIfCondition)
207 interpretTestFlagsAndAppendAction(programCounter, flags, actions, true);
208 else
209 break;
210 }
211 if (programCounter >= m_bytecodeLength)
212 return actions;
213 } else {
214 ASSERT_WITH_MESSAGE(getInstruction(m_bytecode, m_bytecodeLength, programCounter) != DFABytecodeInstruction::AppendAction
215 && getInstruction(m_bytecode, m_bytecodeLength, programCounter) != DFABytecodeInstruction::AppendActionWithIfCondition
216 && getInstruction(m_bytecode, m_bytecodeLength, programCounter) != DFABytecodeInstruction::TestFlagsAndAppendAction
217 && getInstruction(m_bytecode, m_bytecodeLength, programCounter) != DFABytecodeInstruction::TestFlagsAndAppendActionWithIfCondition,
218 "Triggers that match everything should only be in the first DFA.");
219 }
220
221 // Interpret the bytecode from this DFA.
222 // This should always terminate if interpreting correctly compiled bytecode.
223 uint32_t urlIndex = 0;
224 bool urlIndexIsAfterEndOfString = false;
225 while (true) {
226 ASSERT(programCounter <= m_bytecodeLength);
227 switch (getInstruction(m_bytecode, m_bytecodeLength, programCounter)) {
228
229 case DFABytecodeInstruction::Terminate:
230 goto nextDFA;
231
232 case DFABytecodeInstruction::CheckValueCaseSensitive: {
233 if (urlIndexIsAfterEndOfString)
234 goto nextDFA;
235
236 // Check to see if the next character in the url is the value stored with the bytecode.
237 char character = url[urlIndex];
238 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
239 if (character == getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))) {
240 uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t);
241 programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
242 if (!character)
243 urlIndexIsAfterEndOfString = true;
244 urlIndex++; // This represents an edge in the DFA.
245 } else
246 programCounter += sizeof(DFABytecodeInstruction) + sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
247 break;
248 }
249
250 case DFABytecodeInstruction::CheckValueCaseInsensitive: {
251 if (urlIndexIsAfterEndOfString)
252 goto nextDFA;
253
254 // Check to see if the next character in the url is the value stored with the bytecode.
255 char character = toASCIILower(url[urlIndex]);
256 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
257 if (character == getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))) {
258 uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t);
259 programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
260 if (!character)
261 urlIndexIsAfterEndOfString = true;
262 urlIndex++; // This represents an edge in the DFA.
263 } else
264 programCounter += sizeof(DFABytecodeInstruction) + sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
265 break;
266 }
267
268 case DFABytecodeInstruction::JumpTableCaseInsensitive:
269 if (urlIndexIsAfterEndOfString)
270 goto nextDFA;
271
272 interpetJumpTable<false>(url, urlIndex, programCounter, urlIndexIsAfterEndOfString);
273 break;
274 case DFABytecodeInstruction::JumpTableCaseSensitive:
275 if (urlIndexIsAfterEndOfString)
276 goto nextDFA;
277
278 interpetJumpTable<true>(url, urlIndex, programCounter, urlIndexIsAfterEndOfString);
279 break;
280
281 case DFABytecodeInstruction::CheckValueRangeCaseSensitive: {
282 if (urlIndexIsAfterEndOfString)
283 goto nextDFA;
284
285 char character = url[urlIndex];
286 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
287 if (character >= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))
288 && character <= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t))) {
289 uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t);
290 programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
291 if (!character)
292 urlIndexIsAfterEndOfString = true;
293 urlIndex++; // This represents an edge in the DFA.
294 } else
295 programCounter += sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
296 break;
297 }
298
299 case DFABytecodeInstruction::CheckValueRangeCaseInsensitive: {
300 if (urlIndexIsAfterEndOfString)
301 goto nextDFA;
302
303 char character = toASCIILower(url[urlIndex]);
304 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
305 if (character >= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction))
306 && character <= getBits<uint8_t>(m_bytecode, m_bytecodeLength, programCounter + sizeof(DFABytecodeInstruction) + sizeof(uint8_t))) {
307 uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t);
308 programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
309 if (!character)
310 urlIndexIsAfterEndOfString = true;
311 urlIndex++; // This represents an edge in the DFA.
312 } else
313 programCounter += sizeof(DFABytecodeInstruction) + 2 * sizeof(uint8_t) + jumpSizeInBytes(jumpSize);
314 break;
315 }
316
317 case DFABytecodeInstruction::Jump: {
318 if (!url[urlIndex] || urlIndexIsAfterEndOfString)
319 goto nextDFA;
320
321 uint32_t jumpLocation = programCounter + sizeof(DFABytecodeInstruction);
322 DFABytecodeJumpSize jumpSize = getJumpSize(m_bytecode, m_bytecodeLength, programCounter);
323 programCounter += getJumpDistance(m_bytecode, m_bytecodeLength, jumpLocation, jumpSize);
324 urlIndex++; // This represents an edge in the DFA.
325 break;
326 }
327
328 case DFABytecodeInstruction::AppendAction:
329 interpretAppendAction(programCounter, actions, false);
330 break;
331
332 case DFABytecodeInstruction::AppendActionWithIfCondition:
333 interpretAppendAction(programCounter, actions, true);
334 break;
335
336 case DFABytecodeInstruction::TestFlagsAndAppendAction:
337 interpretTestFlagsAndAppendAction(programCounter, flags, actions, false);
338 break;
339
340 case DFABytecodeInstruction::TestFlagsAndAppendActionWithIfCondition:
341 interpretTestFlagsAndAppendAction(programCounter, flags, actions, true);
342 break;
343
344 default:
345 RELEASE_ASSERT_NOT_REACHED(); // Invalid bytecode.
346 }
347 // We should always terminate before or at a null character at the end of a String.
348 ASSERT(urlIndex <= urlCString.length() || (urlIndexIsAfterEndOfString && urlIndex <= urlCString.length() + 1));
349 }
350 RELEASE_ASSERT_NOT_REACHED(); // The while loop can only be exited using goto nextDFA.
351 nextDFA:
352 ASSERT(dfaBytecodeLength);
353 programCounter = dfaStart + dfaBytecodeLength;
354 }
355 return actions;
356}
357
358} // namespace ContentExtensions
359
360} // namespace WebCore
361
362#endif // ENABLE(CONTENT_EXTENSIONS)
363