summaryrefslogtreecommitdiff
path: root/src/adblock/khtml_filter.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/adblock/khtml_filter.cpp')
-rw-r--r--src/adblock/khtml_filter.cpp266
1 files changed, 266 insertions, 0 deletions
diff --git a/src/adblock/khtml_filter.cpp b/src/adblock/khtml_filter.cpp
new file mode 100644
index 00000000..f258d1e7
--- /dev/null
+++ b/src/adblock/khtml_filter.cpp
@@ -0,0 +1,266 @@
+/* This file is part of the KDE project
+
+ Copyright (C) 2005 Ivor Hewitt <ivor@kde.org>
+ Copyright (C) 2008 Maksim Orlovich <maksim@kde.org>
+ Copyright (C) 2008 Vyacheslav Tokarev <tsjoker@gmail.com>
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Library General Public
+ License as published by the Free Software Foundation; either
+ version 2 of the License, or (at your option) any later version.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Library General Public License for more details.
+
+ You should have received a copy of the GNU Library General Public License
+ along with this library; see the file COPYING.LIB. If not, write to
+ the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
+*/
+
+#include "khtml_filter_p.h"
+#include <QDebug>
+
+// rolling hash parameters
+#define HASH_P (1997)
+#define HASH_Q (17509)
+// HASH_MOD = (HASH_P^7) % HASH_Q
+#define HASH_MOD (523)
+
+namespace khtml {
+
+void FilterSet::addFilter(const QString& filterStr)
+{
+ QString filter = filterStr;
+
+ if (filter.startsWith(QLatin1Char('!')))
+ return;
+
+ // Strip leading @@
+ int first = 0;
+ int last = filter.length() - 1;
+ if (filter.startsWith(QLatin1String("@@")))
+ first = 2;
+
+ // Strip options, we ignore them for now.
+ int dollar = filter.lastIndexOf(QLatin1Char('$'));
+ if (dollar != -1)
+ last = dollar - 1;
+
+ // Perhaps nothing left?
+ if (first > last)
+ return;
+
+ filter = filter.mid(first, last - first + 1);
+
+ // Is it a regexp filter?
+ if (filter.length()>2 && filter.startsWith(QLatin1Char('/')) && filter.endsWith(QLatin1Char('/')))
+ {
+ QString inside = filter.mid(1, filter.length()-2);
+ QRegExp rx(inside);
+ reFilters.append(rx);
+// qDebug() << "R:" << inside;
+ }
+ else
+ {
+ // Nope, a wildcard one.
+ // Note: For these, we also need to handle |.
+
+ // Strip wildcards at the ends
+ first = 0;
+ last = filter.length() - 1;
+
+ while (first < filter.length() && filter[first] == QLatin1Char('*'))
+ ++first;
+
+ while (last >= 0 && filter[last] == QLatin1Char('*'))
+ --last;
+
+ if (first > last)
+ filter = QLatin1String("*"); // erm... Well, they asked for it.
+ else
+ filter = filter.mid(first, last - first + 1);
+
+ // Now, do we still have any wildcard stuff left?
+ if (filter.contains("*") || filter.contains("?"))
+ {
+// qDebug() << "W:" << filter;
+ // check if we can use RK first (and then check full RE for the rest) for better performance
+ int aPos = filter.indexOf('*');
+ if (aPos < 0)
+ aPos = filter.length();
+ int qPos = filter.indexOf('?');
+ if (qPos < 0)
+ qPos = filter.length();
+ int pos = qMin(aPos, qPos);
+ if (pos > 7) {
+ QRegExp rx;
+
+ rx.setPatternSyntax(QRegExp::Wildcard);
+ rx.setPattern(filter.mid(pos));
+
+ stringFiltersMatcher.addWildedString(filter.mid(0, pos), rx);
+
+ } else {
+ QRegExp rx;
+
+ rx.setPatternSyntax(QRegExp::Wildcard);
+ rx.setPattern(filter);
+ reFilters.append(rx);
+ }
+ }
+ else
+ {
+ // Fast path
+ stringFiltersMatcher.addString(filter);
+ }
+ }
+}
+
+bool FilterSet::isUrlMatched(const QString& url)
+{
+ if (stringFiltersMatcher.isMatched(url))
+ return true;
+
+ for (int c = 0; c < reFilters.size(); ++c)
+ {
+ if (url.contains(reFilters[c]))
+ return true;
+ }
+
+ return false;
+}
+
+void FilterSet::clear()
+{
+ reFilters.clear();
+ stringFiltersMatcher.clear();
+}
+
+
+void StringsMatcher::addString(const QString& pattern)
+{
+ if (pattern.length() < 8) {
+ // handle short string differently
+ shortStringFilters.append(pattern);
+ } else {
+ // use modified Rabin-Karp's algorithm with 8-length string hash
+ // i.e. store hash of first 8 chars in the HashMap for fast look-up
+ stringFilters.append(pattern);
+ int ind = stringFilters.size() - 1;
+ int current = 0;
+
+ // compute hash using rolling hash
+ // hash for string: x0,x1,x2...xn-1 will be:
+ // (p^(n-1)*x0 + p^(n-2)*x1 + ... + p * xn-2 + xn-1) % q
+ // where p and q some wisely-chosen integers
+ /*for (int k = 0; k < 8; ++k)*/
+ int len = pattern.length();
+ for (int k = len - 8; k < len; ++k)
+ current = (current * HASH_P + pattern[k].unicode()) % HASH_Q;
+
+ // insert computed hash value into HashMap
+ QHash<int, QVector<int> >::iterator it = stringFiltersHash.find(current + 1);
+ if (it == stringFiltersHash.end()) {
+ QVector<int> list;
+ list.append(ind);
+ stringFiltersHash.insert(current + 1, list);
+ fastLookUp.setBit(current);
+ } else {
+ it.value().append(ind);
+ }
+ }
+}
+
+void StringsMatcher::addWildedString(const QString& prefix, const QRegExp& rx)
+{
+ rePrefixes.append(prefix);
+ reFilters.append(rx);
+ int index = -rePrefixes.size();
+
+ int current = 0;
+ for (int k = 0; k < 8; ++k)
+ current = (current * HASH_P + prefix[k].unicode()) % HASH_Q;
+
+ // insert computed hash value into HashMap
+ QHash<int, QVector<int> >::iterator it = stringFiltersHash.find(current + 1);
+ if (it == stringFiltersHash.end()) {
+ QVector<int> list;
+ list.append(index);
+ stringFiltersHash.insert(current + 1, list);
+ fastLookUp.setBit(current);
+ } else {
+ it.value().append(index);
+ }
+}
+
+bool StringsMatcher::isMatched(const QString& str) const
+{
+ // check short strings first
+ for (int i = 0; i < shortStringFilters.size(); ++i) {
+ if (str.contains(shortStringFilters[i]))
+ return true;
+ }
+
+ int len = str.length();
+ int k;
+
+ int current = 0;
+ int next = 0;
+ // compute hash for first 8 characters
+ for (k = 0; k < 8 && k < len; ++k)
+ current = (current * HASH_P + str[k].unicode()) % HASH_Q;
+
+ QHash<int, QVector<int> >::const_iterator hashEnd = stringFiltersHash.end();
+ // main Rabin-Karp's algorithm loop
+ for (k = 7; k < len; ++k, current = next) {
+ // roll the hash if not at the end
+ // (calculate hash for the next iteration)
+ if (k + 1 < len)
+ next = (HASH_P * ((current + HASH_Q - ((HASH_MOD * str[k - 7].unicode()) % HASH_Q)) % HASH_Q) + str[k + 1].unicode()) % HASH_Q;
+
+ if (!fastLookUp.testBit(current))
+ continue;
+
+ // look-up the hash in the HashMap and check all strings
+ QHash<int, QVector<int> >::const_iterator it = stringFiltersHash.find(current + 1);
+
+ // check possible strings
+ if (it != hashEnd) {
+ for (int j = 0; j < it.value().size(); ++j) {
+ int index = it.value()[j];
+ // check if we got simple string or REs prefix
+ if (index >= 0) {
+ int flen = stringFilters[index].length();
+ if (k - flen + 1 >= 0 && stringFilters[index] == str.midRef(k - flen + 1 , flen))
+ return true;
+ } else {
+ index = -index - 1;
+ int flen = rePrefixes[index].length();
+ if (k - 8 + flen < len && rePrefixes[index] == str.midRef(k - 7, flen) &&
+ str.indexOf(reFilters[index], k - 7 + flen) == k - 7 + flen)
+ return true;
+ }
+ }
+ }
+ }
+
+ return false;
+}
+
+void StringsMatcher::clear()
+{
+ stringFilters.clear();
+ shortStringFilters.clear();
+ reFilters.clear();
+ rePrefixes.clear();
+ stringFiltersHash.clear();
+ fastLookUp.resize(HASH_Q);
+ fastLookUp.fill(0, 0, HASH_Q);
+}
+
+}
+
+// kate: indent-width 4; replace-tabs on; tab-width 4; space-indent on;
generated by cgit v1.2.1 (git 2.18.0) at 2024-07-21 03:22:14 +0000