Initial import from the monolithic Qt.

This is the beginning of revision history for this module. If you
want to look at revision history older than this, please refer to the
Qt Git wiki for how to use Git history grafting. At the time of
writing, this wiki is located here:

http://qt.gitorious.org/qt/pages/GitIntroductionWithQt

If you have already performed the grafting and you don't see any
history beyond this commit, try running "git log" with the "--follow"
argument.

Branched from the monolithic repo, Qt master branch, at commit
896db169ea224deb96c59ce8af800d019de63f12

1 files changed, 324 insertions, 0 deletions

diff --git a/src/corelib/tools/qbytearraymatcher.cpp b/src/corelib/tools/qbytearraymatcher.cpp
new file mode 100644
index 0000000000..bc99760ddc
--- /dev/null
+++ b/src/corelib/tools/qbytearraymatcher.cpp
@@ -0,0 +1,324 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qbytearraymatcher.h"
+
+#include <limits.h>
+
+QT_BEGIN_NAMESPACE
+
+static inline void bm_init_skiptable(const uchar *cc, int len, uchar *skiptable)
+{
+    int l = qMin(len, 255);
+    memset(skiptable, l, 256*sizeof(uchar));
+    cc += len - l;
+    while (l--)
+        skiptable[*cc++] = l;
+}
+
+static inline int bm_find(const uchar *cc, int l, int index, const uchar *puc, uint pl,
+                          const uchar *skiptable)
+{
+    if (pl == 0)
+        return index > l ? -1 : index;
+    const uint pl_minus_one = pl - 1;
+
+    register const uchar *current = cc + index + pl_minus_one;
+    const uchar *end = cc + l;
+    while (current < end) {
+        uint skip = skiptable[*current];
+        if (!skip) {
+            // possible match
+            while (skip < pl) {
+                if (*(current - skip) != puc[pl_minus_one - skip])
+                    break;
+                skip++;
+            }
+            if (skip > pl_minus_one) // we have a match
+                return (current - cc) - skip + 1;
+
+            // in case we don't have a match we are a bit inefficient as we only skip by one
+            // when we have the non matching char in the string.
+            if (skiptable[*(current - skip)] == pl)
+                skip = pl - skip;
+            else
+                skip = 1;
+        }
+        if (current > end - skip)
+            break;
+        current += skip;
+    }
+    return -1; // not found
+}
+
+/*! \class QByteArrayMatcher
+    \brief The QByteArrayMatcher class holds a sequence of bytes that
+    can be quickly matched in a byte array.
+
+    \ingroup tools
+    \ingroup string-processing
+
+    This class is useful when you have a sequence of bytes that you
+    want to repeatedly match against some byte arrays (perhaps in a
+    loop), or when you want to search for the same sequence of bytes
+    multiple times in the same byte array. Using a matcher object and
+    indexIn() is faster than matching a plain QByteArray with
+    QByteArray::indexOf() if repeated matching takes place. This
+    class offers no benefit if you are doing one-off byte array
+    matches.
+
+    Create the QByteArrayMatcher with the QByteArray you want to
+    search for. Then call indexIn() on the QByteArray that you want to
+    search.
+
+    \sa QByteArray, QStringMatcher
+*/
+
+/*!
+    Constructs an empty byte array matcher that won't match anything.
+    Call setPattern() to give it a pattern to match.
+*/
+QByteArrayMatcher::QByteArrayMatcher()
+    : d(0)
+{
+    p.p = 0;
+    p.l = 0;
+    qMemSet(p.q_skiptable, 0, sizeof(p.q_skiptable));
+}
+
+/*!
+  Constructs a byte array matcher from \a pattern. \a pattern
+  has the given \a length. \a pattern must remain in scope, but
+  the destructor does not delete \a pattern.
+ */
+QByteArrayMatcher::QByteArrayMatcher(const char *pattern, int length)
+    : d(0)
+{
+    p.p = reinterpret_cast<const uchar *>(pattern);
+    p.l = length;
+    bm_init_skiptable(p.p, p.l, p.q_skiptable);
+}
+
+/*!
+    Constructs a byte array matcher that will search for \a pattern.
+    Call indexIn() to perform a search.
+*/
+QByteArrayMatcher::QByteArrayMatcher(const QByteArray &pattern)
+    : d(0), q_pattern(pattern)
+{
+    p.p = reinterpret_cast<const uchar *>(pattern.constData());
+    p.l = pattern.size();
+    bm_init_skiptable(p.p, p.l, p.q_skiptable);
+}
+
+/*!
+    Copies the \a other byte array matcher to this byte array matcher.
+*/
+QByteArrayMatcher::QByteArrayMatcher(const QByteArrayMatcher &other)
+    : d(0)
+{
+    operator=(other);
+}
+
+/*!
+    Destroys the byte array matcher.
+*/
+QByteArrayMatcher::~QByteArrayMatcher()
+{
+}
+
+/*!
+    Assigns the \a other byte array matcher to this byte array matcher.
+*/
+QByteArrayMatcher &QByteArrayMatcher::operator=(const QByteArrayMatcher &other)
+{
+    q_pattern = other.q_pattern;
+    memcpy(&p, &other.p, sizeof(p));
+    return *this;
+}
+
+/*!
+    Sets the byte array that this byte array matcher will search for
+    to \a pattern.
+
+    \sa pattern(), indexIn()
+*/
+void QByteArrayMatcher::setPattern(const QByteArray &pattern)
+{
+    q_pattern = pattern;
+    p.p = reinterpret_cast<const uchar *>(pattern.constData());
+    p.l = pattern.size();
+    bm_init_skiptable(p.p, p.l, p.q_skiptable);
+}
+
+/*!
+    Searches the byte array \a ba, from byte position \a from (default
+    0, i.e. from the first byte), for the byte array pattern() that
+    was set in the constructor or in the most recent call to
+    setPattern(). Returns the position where the pattern() matched in
+    \a ba, or -1 if no match was found.
+*/
+int QByteArrayMatcher::indexIn(const QByteArray &ba, int from) const
+{
+    if (from < 0)
+        from = 0;
+    return bm_find(reinterpret_cast<const uchar *>(ba.constData()), ba.size(), from,
+                   p.p, p.l, p.q_skiptable);
+}
+
+/*!
+    Searches the char string \a str, which has length \a len, from
+    byte position \a from (default 0, i.e. from the first byte), for
+    the byte array pattern() that was set in the constructor or in the
+    most recent call to setPattern(). Returns the position where the
+    pattern() matched in \a str, or -1 if no match was found.
+*/
+int QByteArrayMatcher::indexIn(const char *str, int len, int from) const
+{
+    if (from < 0)
+        from = 0;
+    return bm_find(reinterpret_cast<const uchar *>(str), len, from,
+                   p.p, p.l, p.q_skiptable);
+}
+
+/*!
+    \fn QByteArray QByteArrayMatcher::pattern() const
+
+    Returns the byte array pattern that this byte array matcher will
+    search for.
+
+    \sa setPattern()
+*/
+
+
+static int findChar(const char *str, int len, char ch, int from)
+{
+    const uchar *s = (const uchar *)str;
+    uchar c = (uchar)ch;
+    if (from < 0)
+        from = qMax(from + len, 0);
+    if (from < len) {
+        const uchar *n = s + from - 1;
+        const uchar *e = s + len;
+        while (++n != e)
+            if (*n == c)
+                return  n - s;
+    }
+    return -1;
+}
+
+/*! \internal
+ */
+static int qFindByteArrayBoyerMoore(
+    const char *haystack, int haystackLen, int haystackOffset,
+    const char *needle, int needleLen)
+{
+    uchar skiptable[256];
+    bm_init_skiptable((const uchar *)needle, needleLen, skiptable);
+    if (haystackOffset < 0)
+        haystackOffset = 0;
+    return bm_find((const uchar *)haystack, haystackLen, haystackOffset,
+                   (const uchar *)needle, needleLen, skiptable);
+}
+
+#define REHASH(a) \
+    if (sl_minus_1 < sizeof(uint) * CHAR_BIT) \
+        hashHaystack -= (a) << sl_minus_1; \
+    hashHaystack <<= 1
+
+/*! \internal
+ */
+int qFindByteArray(
+    const char *haystack0, int haystackLen, int from,
+    const char *needle, int needleLen)
+{
+    const int l = haystackLen;
+    const int sl = needleLen;
+    if (from < 0)
+        from += l;
+    if (uint(sl + from) > (uint)l)
+        return -1;
+    if (!sl)
+        return from;
+    if (!l)
+        return -1;
+
+    if (sl == 1)
+        return findChar(haystack0, haystackLen, needle[0], from);
+
+    /*
+      We use the Boyer-Moore algorithm in cases where the overhead
+      for the skip table should pay off, otherwise we use a simple
+      hash function.
+    */
+    if (l > 500 && sl > 5)
+        return qFindByteArrayBoyerMoore(haystack0, haystackLen, from,
+                                        needle, needleLen);
+
+    /*
+      We use some hashing for efficiency's sake. Instead of
+      comparing strings, we compare the hash value of str with that
+      of a part of this QString. Only if that matches, we call memcmp().
+    */
+    const char *haystack = haystack0 + from;
+    const char *end = haystack0 + (l - sl);
+    const uint sl_minus_1 = sl - 1;
+    uint hashNeedle = 0, hashHaystack = 0;
+    int idx;
+    for (idx = 0; idx < sl; ++idx) {
+        hashNeedle = ((hashNeedle<<1) + needle[idx]);
+        hashHaystack = ((hashHaystack<<1) + haystack[idx]);
+    }
+    hashHaystack -= *(haystack + sl_minus_1);
+
+    while (haystack <= end) {
+        hashHaystack += *(haystack + sl_minus_1);
+        if (hashHaystack == hashNeedle && *needle == *haystack
+             && memcmp(needle, haystack, sl) == 0)
+            return haystack - haystack0;
+
+        REHASH(*haystack);
+        ++haystack;
+    }
+    return -1;
+}
+
+QT_END_NAMESPACE