qstring.cpp

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
** Contact: http://www.qt-project.org/legal
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Digia.  For licensing terms and
** conditions see http://qt.digia.com/licensing.  For further information
** use the contact form at http://qt.digia.com/contact-us.
**
** 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, Digia gives you certain additional
** rights.  These rights are described in the Digia Qt LGPL Exception
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3.0 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU General Public License version 3.0 requirements will be
** met: http://www.gnu.org/copyleft/gpl.html.
**
**
** $QT_END_LICENSE$
**
****************************************************************************/

#include "qstringlist.h"
#include "qregexp.h"
#include "qunicodetables_p.h"
#ifndef QT_NO_TEXTCODEC
#include <qtextcodec.h>
#endif
#include <private/qutfcodec_p.h>
#include "qsimd_p.h"
#include <qdatastream.h>
#include <qlist.h>
#include "qlocale.h"
#include "qlocale_p.h"
#include "qstringmatcher.h"
#include "qvarlengtharray.h"
#include "qtools_p.h"
#include "qhash.h"
#include "qdebug.h"
#include "qendian.h"
#include "qmutex.h"

#ifdef Q_OS_MAC
#include <private/qcore_mac_p.h>
#endif

#include <private/qfunctions_p.h>

#if defined(Q_OS_WINCE)
#include <windows.h>
#include <winnls.h>
#endif

#ifdef Q_OS_SYMBIAN
#include <e32cmn.h>
#endif

#include <limits.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>

#ifdef truncate
#undef truncate
#endif

#include "qchar.cpp"
#include "qstringmatcher.cpp"

#ifndef LLONG_MAX
#define LLONG_MAX qint64_C(9223372036854775807)
#endif
#ifndef LLONG_MIN
#define LLONG_MIN (-LLONG_MAX - qint64_C(1))
#endif
#ifndef ULLONG_MAX
#define ULLONG_MAX quint64_C(18446744073709551615)
#endif

QT_BEGIN_NAMESPACE

#ifndef QT_NO_TEXTCODEC
QTextCodec *QString::codecForCStrings;
#endif

#ifdef QT3_SUPPORT
static QHash<void *, QByteArray> *asciiCache = 0;
Q_GLOBAL_STATIC(QMutex, asciiCacheMutex)

#endif

#ifdef QT_USE_ICU
// qlocale_icu.cpp
extern bool qt_ucol_strcoll(const QChar *source, int sourceLength, const QChar *target, int targetLength, int *result);
#endif

// internal
int qFindString(const QChar *haystack, int haystackLen, int from,
    const QChar *needle, int needleLen, Qt::CaseSensitivity cs);
int qFindStringBoyerMoore(const QChar *haystack, int haystackLen, int from,
    const QChar *needle, int needleLen, Qt::CaseSensitivity cs);
static inline int qt_last_index_of(const QChar *haystack, int haystackLen, const QChar &needle,
                                   int from, Qt::CaseSensitivity cs);
static inline int qt_string_count(const QChar *haystack, int haystackLen,
                                  const QChar *needle, int needleLen,
                                  Qt::CaseSensitivity cs);
static inline int qt_string_count(const QChar *haystack, int haystackLen,
                                  const QChar &needle, Qt::CaseSensitivity cs);
static inline int qt_find_latin1_string(const QChar *hay, int size, const QLatin1String &needle,
                                        int from, Qt::CaseSensitivity cs);
static inline bool qt_starts_with(const QChar *haystack, int haystackLen,
                                  const QChar *needle, int needleLen, Qt::CaseSensitivity cs);
static inline bool qt_starts_with(const QChar *haystack, int haystackLen,
                                  const QLatin1String &needle, Qt::CaseSensitivity cs);
static inline bool qt_ends_with(const QChar *haystack, int haystackLen,
                                const QChar *needle, int needleLen, Qt::CaseSensitivity cs);
static inline bool qt_ends_with(const QChar *haystack, int haystackLen,
                                const QLatin1String &needle, Qt::CaseSensitivity cs);

// Unicode case-insensitive comparison
static int ucstricmp(const ushort *a, const ushort *ae, const ushort *b, const ushort *be)
{
    if (a == b)
        return (ae - be);
    if (a == 0)
        return 1;
    if (b == 0)
        return -1;

    const ushort *e = ae;
    if (be - b < ae - a)
        e = a + (be - b);

    uint alast = 0;
    uint blast = 0;
    while (a < e) {
//         qDebug() << hex << alast << blast;
//         qDebug() << hex << "*a=" << *a << "alast=" << alast << "folded=" << foldCase (*a, alast);
//         qDebug() << hex << "*b=" << *b << "blast=" << blast << "folded=" << foldCase (*b, blast);
        int diff = foldCase(*a, alast) - foldCase(*b, blast);
        if ((diff))
            return diff;
        ++a;
        ++b;
    }
    if (a == ae) {
        if (b == be)
            return 0;
        return -1;
    }
    return 1;
}

// Case-insensitive comparison between a Unicode string and a QLatin1String
static int ucstricmp(const ushort *a, const ushort *ae, const uchar *b)
{
    if (a == 0) {
        if (b == 0)
            return 0;
        return 1;
    }
    if (b == 0)
        return -1;

    while (a < ae && *b) {
        int diff = foldCase(*a) - foldCase(*b);
        if ((diff))
            return diff;
        ++a;
        ++b;
    }
    if (a == ae) {
        if (!*b)
            return 0;
        return -1;
    }
    return 1;
}

// Unicode case-sensitive compare two same-sized strings
static int ucstrncmp(const QChar *a, const QChar *b, int l)
{
    while (l-- && *a == *b)
        a++,b++;
    if (l==-1)
        return 0;
    return a->unicode() - b->unicode();
}

// Unicode case-sensitive comparison
static int ucstrcmp(const QChar *a, int alen, const QChar *b, int blen)
{
    if (a == b && alen == blen)
        return 0;
    int l = qMin(alen, blen);
    int cmp = ucstrncmp(a, b, l);
    return cmp ? cmp : (alen-blen);
}

// Unicode case-insensitive compare two same-sized strings
static int ucstrnicmp(const ushort *a, const ushort *b, int l)
{
    return ucstricmp(a, a + l, b, b + l);
}

// Benchmarking indicates that doing memcmp is much slower than
// executing the comparison ourselves.
//
// The profiling was done on a population of calls to qMemEquals, generated
// during a run of the demo browser. The profile of the data (32-bit x86
// Linux) was:
//
//  total number of comparisons: 21353
//  longest string compared: 95
//  average comparison length: 14.8786
//  cache-line crosses: 5661 (13.3%)
//  alignment histogram:
//   0xXXX0 = 512 (1.2%) strings, 0 (0.0%) of which same-aligned
//   0xXXX2 = 15087 (35.3%) strings, 5145 (34.1%) of which same-aligned
//   0xXXX4 = 525 (1.2%) strings, 0 (0.0%) of which same-aligned
//   0xXXX6 = 557 (1.3%) strings, 6 (1.1%) of which same-aligned
//   0xXXX8 = 509 (1.2%) strings, 0 (0.0%) of which same-aligned
//   0xXXXa = 24358 (57.0%) strings, 9901 (40.6%) of which same-aligned
//   0xXXXc = 557 (1.3%) strings, 0 (0.0%) of which same-aligned
//   0xXXXe = 601 (1.4%) strings, 15 (2.5%) of which same-aligned
//   total  = 42706 (100%) strings, 15067 (35.3%) of which same-aligned
//
// 92% of the strings have alignment of 2 or 10, which is due to malloc on
// 32-bit Linux returning values aligned to 8 bytes, and offsetof(array, QString::Data) == 18.
//
// The profile on 64-bit will be different since offsetof(array, QString::Data) == 26.
//
// The benchmark results were, for a Core-i7 @ 2.67 GHz 32-bit, compiled with -O3 -funroll-loops:
//   16-bit loads only:           872,301 CPU ticks [Qt 4.5 / memcmp]
//   32- and 16-bit loads:        773,362 CPU ticks [Qt 4.6]
//   SSE2 "movdqu" 128-bit loads: 618,736 CPU ticks
//   SSE3 "lddqu" 128-bit loads:  619,954 CPU ticks
//   SSSE3 "palignr" corrections: 852,147 CPU ticks
//   SSE4.2 "pcmpestrm":          738,702 CPU ticks
//
// The same benchmark on an Atom N450 @ 1.66 GHz, is:
//  16-bit loads only:            2,185,882 CPU ticks
//  32- and 16-bit loads:         1,805,060 CPU ticks
//  SSE2 "movdqu" 128-bit loads:  2,529,843 CPU ticks
//  SSE3 "lddqu" 128-bit loads:   2,514,858 CPU ticks
//  SSSE3 "palignr" corrections:  2,160,325 CPU ticks
//  SSE4.2 not available
//
// The conclusion we reach is that alignment the SSE2 unaligned code can gain
// 20% improvement in performance in some systems, but suffers a penalty due
// to the unaligned loads on others.

static bool qMemEquals(const quint16 *a, const quint16 *b, int length)
{
    if (a == b || !length)
        return true;

    register union {
        const quint16 *w;
        const quint32 *d;
        quintptr value;
    } sa, sb;
    sa.w = a;
    sb.w = b;

    // check alignment
    if ((sa.value & 2) == (sb.value & 2)) {
        // both addresses have the same alignment
        if (sa.value & 2) {
            // both addresses are not aligned to 4-bytes boundaries
            // compare the first character
            if (*sa.w != *sb.w)
                return false;
            --length;
            ++sa.w;
            ++sb.w;

            // now both addresses are 4-bytes aligned
        }

        // both addresses are 4-bytes aligned
        // do a fast 32-bit comparison
        register const quint32 *e = sa.d + (length >> 1);
        for ( ; sa.d != e; ++sa.d, ++sb.d) {
            if (*sa.d != *sb.d)
                return false;
        }

        // do we have a tail?
        return (length & 1) ? *sa.w == *sb.w : true;
    } else {
        // one of the addresses isn't 4-byte aligned but the other is
        register const quint16 *e = sa.w + length;
        for ( ; sa.w != e; ++sa.w, ++sb.w) {
            if (*sa.w != *sb.w)
                return false;
        }
    }
    return true;
}

static int findChar(const QChar *str, int len, QChar ch, int from,
    Qt::CaseSensitivity cs)
{
    const ushort *s = (const ushort *)str;
    ushort c = ch.unicode();
    if (from < 0)
        from = qMax(from + len, 0);
    if (from < len) {
        const ushort *n = s + from - 1;
        const ushort *e = s + len;
        if (cs == Qt::CaseSensitive) {
            while (++n != e)
                if (*n == c)
                    return  n - s;
        } else {
            c = foldCase(c);
            while (++n != e)
                if (foldCase(*n) == c)
                    return  n - s;
        }
    }
    return -1;
}

#define REHASH(a) \
    if (sl_minus_1 < (int)sizeof(int) * CHAR_BIT)       \
        hashHaystack -= (a) << sl_minus_1; \
    hashHaystack <<= 1

inline bool qIsUpper(char ch)
{
    return ch >= 'A' && ch <= 'Z';
}

inline bool qIsDigit(char ch)
{
    return ch >= '0' && ch <= '9';
}

inline char qToLower(char ch)
{
    if (ch >= 'A' && ch <= 'Z')
        return ch - 'A' + 'a';
    else
        return ch;
}

const QString::Null QString::null = { };

QString::Data QString::shared_null = { Q_BASIC_ATOMIC_INITIALIZER(1),
                                       0, 0, shared_null.array, 0, 0, 0, 0, 0, 0, {0} };
QString::Data QString::shared_empty = { Q_BASIC_ATOMIC_INITIALIZER(1),
                                        0, 0, shared_empty.array, 0, 0, 0, 0, 0, 0, {0} };

int QString::grow(int size)
{
    return qAllocMore(size * sizeof(QChar), sizeof(Data)) / sizeof(QChar);
}

QString QString::fromWCharArray(const wchar_t *string, int size)
{
    if (sizeof(wchar_t) == sizeof(QChar)) {
        return fromUtf16((const ushort *)string, size);
    } else {
        return fromUcs4((uint *)string, size);
    }
}

template<typename T> int toUcs4_helper(const unsigned short *uc, int length, T *out)
{
    int i = 0;
    for (; i < length; ++i) {
        uint u = uc[i];
        if (QChar::isHighSurrogate(u) && i < length-1) {
            ushort low = uc[i+1];
            if (QChar::isLowSurrogate(low)) {
                ++i;
                u = QChar::surrogateToUcs4(u, low);
            }
        }
        *out = T(u);
        ++out;
    }
    return i;
}

int QString::toWCharArray(wchar_t *array) const
{
    if (sizeof(wchar_t) == sizeof(QChar)) {
        memcpy(array, utf16(), sizeof(wchar_t)*length());
        return length();
    } else {
        return toUcs4_helper<wchar_t>(utf16(), length(), array);
    }
}

QString::QString(const QChar *unicode, int size)
{
   if (!unicode) {
        d = &shared_null;
        d->ref.ref();
    } else if (size <= 0) {
        d = &shared_empty;
        d->ref.ref();
    } else {
        d = (Data*) qMalloc(sizeof(Data)+size*sizeof(QChar));
        Q_CHECK_PTR(d);
        d->ref = 1;
        d->alloc = d->size = size;
        d->clean = d->asciiCache = d->simpletext = d->righttoleft = d->capacity = 0;
        d->data = d->array;
        memcpy(d->array, unicode, size * sizeof(QChar));
        d->array[size] = '\0';
    }
}

QString::QString(const QChar *unicode)
{
     if (!unicode) {
         d = &shared_null;
         d->ref.ref();
     } else {
         int size = 0;
         while (unicode[size] != 0)
             ++size;
         if (!size) {
             d = &shared_empty;
             d->ref.ref();
         } else {
             d = (Data*) qMalloc(sizeof(Data)+size*sizeof(QChar));
             Q_CHECK_PTR(d);
             d->ref = 1;
             d->alloc = d->size = size;
             d->clean = d->asciiCache = d->simpletext = d->righttoleft = d->capacity = 0;
             d->data = d->array;
             memcpy(d->array, unicode, size * sizeof(QChar));
             d->array[size] = '\0';
         }
     }
}


QString::QString(int size, QChar ch)
{
   if (size <= 0) {
        d = &shared_empty;
        d->ref.ref();
    } else {
        d = (Data*) qMalloc(sizeof(Data)+size*sizeof(QChar));
        Q_CHECK_PTR(d);
        d->ref = 1;
        d->alloc = d->size = size;
        d->clean = d->asciiCache = d->simpletext = d->righttoleft = d->capacity = 0;
        d->data = d->array;
        d->array[size] = '\0';
        ushort *i = d->array + size;
        ushort *b = d->array;
        const ushort value = ch.unicode();
        while (i != b)
           *--i = value;
    }
}

QString::QString(int size, Qt::Initialization)
{
    d = (Data*) qMalloc(sizeof(Data)+size*sizeof(QChar));
    Q_CHECK_PTR(d);
    d->ref = 1;
    d->alloc = d->size = size;
    d->clean = d->asciiCache = d->simpletext = d->righttoleft = d->capacity = 0;
    d->data = d->array;
    d->array[size] = '\0';
}

QString::QString(QChar ch)
{
    void *buf = qMalloc(sizeof(Data) + sizeof(QChar));
    Q_CHECK_PTR(buf);
    d = reinterpret_cast<Data *>(buf);
    d->ref = 1;
    d->alloc = d->size = 1;
    d->clean = d->asciiCache = d->simpletext = d->righttoleft = d->capacity = 0;
    d->data = d->array;
    d->array[0] = ch.unicode();
    d->array[1] = '\0';
}

// ### Qt 5: rename freeData() to avoid confusion. See task 197625.
void QString::free(Data *d)
{
#ifdef QT3_SUPPORT
    if (d->asciiCache) {
        QMutexLocker locker(asciiCacheMutex());
        Q_ASSERT(asciiCache);
        asciiCache->remove(d);
    }
#endif
    qFree(d);
}

void QString::resize(int size)
{
    if (size < 0)
        size = 0;

    if (size == 0 && !d->capacity) {
        Data *x = &shared_empty;
        x->ref.ref();
        if (!d->ref.deref())
            QString::free(d);
        d = x;
    } else {
        if (d->ref != 1 || size > d->alloc ||
            (!d->capacity && size < d->size && size < d->alloc >> 1))
            realloc(grow(size));
        if (d->alloc >= size) {
            d->size = size;
            if (d->data == d->array) {
                d->array[size] = '\0';
            }
        }
    }
}

// ### Qt 5: rename reallocData() to avoid confusion. 197625
void QString::realloc(int alloc)
{
    if (d->ref != 1 || d->data != d->array) {
        Data *x = static_cast<Data *>(qMalloc(sizeof(Data) + alloc * sizeof(QChar)));
        Q_CHECK_PTR(x);
        x->size = qMin(alloc, d->size);
        ::memcpy(x->array, d->data, x->size * sizeof(QChar));
        x->array[x->size] = 0;
        x->asciiCache = 0;
        x->ref = 1;
        x->alloc = alloc;
        x->clean = d->clean;
        x->simpletext = d->simpletext;
        x->righttoleft = d->righttoleft;
        x->capacity = d->capacity;
        x->data = x->array;
        if (!d->ref.deref())
            QString::free(d);
        d = x;
    } else {
#ifdef QT3_SUPPORT
        if (d->asciiCache) {
            QMutexLocker locker(asciiCacheMutex());
            Q_ASSERT(asciiCache);
            asciiCache->remove(d);
        }
#endif
        Data *p = static_cast<Data *>(qRealloc(d, sizeof(Data) + alloc * sizeof(QChar)));
        Q_CHECK_PTR(p);
        d = p;
        d->alloc = alloc;
        d->data = d->array;
    }
}

void QString::realloc()
{
    realloc(d->size);
}

void QString::expand(int i)
{
    int sz = d->size;
    resize(qMax(i + 1, sz));
    if (d->size - 1 > sz) {
        ushort *n = d->data + d->size - 1;
        ushort *e = d->data + sz;
        while (n != e)
           * --n = ' ';
    }
}

QString &QString::operator=(const QString &other)
{
    other.d->ref.ref();
    if (!d->ref.deref())
        QString::free(d);
    d = other.d;
    return *this;
}


QString &QString::operator=(QChar ch)
{
    return operator=(QString(ch));
}

QString &QString::insert(int i, const QLatin1String &str)
{
    const uchar *s = (const uchar *)str.latin1();
    if (i < 0 || !s || !(*s))
        return *this;

    int len = qstrlen(str.latin1());
    expand(qMax(d->size, i) + len - 1);

    ::memmove(d->data + i + len, d->data + i, (d->size - i - len) * sizeof(QChar));
    for (int j = 0; j < len; ++j)
        d->data[i + j] = s[j];
    return *this;
}

QString& QString::insert(int i, const QChar *unicode, int size)
{
    if (i < 0 || size <= 0)
        return *this;

    const ushort *s = (const ushort *)unicode;
    if (s >= d->data && s < d->data + d->alloc) {
        // Part of me - take a copy
        ushort *tmp = static_cast<ushort *>(qMalloc(size * sizeof(QChar)));
        Q_CHECK_PTR(tmp);
        memcpy(tmp, s, size * sizeof(QChar));
        insert(i, reinterpret_cast<const QChar *>(tmp), size);
        qFree(tmp);
        return *this;
    }

    expand(qMax(d->size, i) + size - 1);

    ::memmove(d->data + i + size, d->data + i, (d->size - i - size) * sizeof(QChar));
    memcpy(d->data + i, s, size * sizeof(QChar));
    return *this;
}

QString& QString::insert(int i, QChar ch)
{
    if (i < 0)
        i += d->size;
    if (i < 0)
        return *this;
    expand(qMax(i, d->size));
    ::memmove(d->data + i + 1, d->data + i, (d->size - i) * sizeof(QChar));
    d->data[i] = ch.unicode();
    return *this;
}

QString &QString::append(const QString &str)
{
    if (str.d != &shared_null) {
        if (d == &shared_null) {
            operator=(str);
        } else {
            if (d->ref != 1 || d->size + str.d->size > d->alloc)
                realloc(grow(d->size + str.d->size));
            memcpy(d->data + d->size, str.d->data, str.d->size * sizeof(QChar));
            d->size += str.d->size;
            d->data[d->size] = '\0';
        }
    }
    return *this;
}

QString &QString::append(const QLatin1String &str)
{
    const uchar *s = (const uchar *)str.latin1();
    if (s) {
        int len = qstrlen((char *)s);
        if (d->ref != 1 || d->size + len > d->alloc)
            realloc(grow(d->size + len));
        ushort *i = d->data + d->size;
        while ((*i++ = *s++))
            ;
        d->size += len;
    }
    return *this;
}

QString &QString::append(QChar ch)
{
    if (d->ref != 1 || d->size + 1 > d->alloc)
        realloc(grow(d->size + 1));
    d->data[d->size++] = ch.unicode();
    d->data[d->size] = '\0';
    return *this;
}

QString &QString::remove(int pos, int len)
{
    if (pos < 0)  // count from end of string
        pos += d->size;
    if (pos < 0 || pos >= d->size) {
        // range problems
    } else if (len >= d->size - pos) {
        resize(pos); // truncate
    } else if (len > 0) {
        detach();
        memmove(d->data + pos, d->data + pos + len,
                (d->size - pos - len + 1) * sizeof(ushort));
        d->size -= len;
    }
    return *this;
}

QString &QString::remove(const QString &str, Qt::CaseSensitivity cs)
{
    if (str.d->size) {
        int i = 0;
        while ((i = indexOf(str, i, cs)) != -1)
            remove(i, str.d->size);
    }
    return *this;
}

QString &QString::remove(QChar ch, Qt::CaseSensitivity cs)
{
    int i = 0;
    ushort c = ch.unicode();
    if (cs == Qt::CaseSensitive) {
        while (i < d->size)
            if (d->data[i] == ch)
                remove(i, 1);
            else
                i++;
    } else {
        c = foldCase(c);
        while (i < d->size)
            if (foldCase(d->data[i]) == c)
                remove(i, 1);
            else
                i++;
    }
    return *this;
}

QString &QString::replace(int pos, int len, const QString &after)
{
    QString copy = after;
    return replace(pos, len, copy.constData(), copy.length());
}

QString &QString::replace(int pos, int len, const QChar *unicode, int size)
{
    if (pos < 0 || pos > d->size)
        return *this;
    if (pos + len > d->size)
        len = d->size - pos;

    uint index = pos;
    replace_helper(&index, 1, len, unicode, size);
    return *this;
}

QString &QString::replace(int pos, int len, QChar after)
{
    return replace(pos, len, &after, 1);
}

QString &QString::replace(const QString &before, const QString &after, Qt::CaseSensitivity cs)
{
    return replace(before.constData(), before.size(), after.constData(), after.size(), cs);
}

void QString::replace_helper(uint *indices, int nIndices, int blen, const QChar *after, int alen)
{
    // copy *after in case it lies inside our own d->data area
    // (which we could possibly invalidate via a realloc or corrupt via memcpy operations.)
    QChar *afterBuffer = const_cast<QChar *>(after);
    if (after >= reinterpret_cast<QChar *>(d->data) && after < reinterpret_cast<QChar *>(d->data) + d->size) {
        afterBuffer = static_cast<QChar *>(qMalloc(alen*sizeof(QChar)));
        Q_CHECK_PTR(afterBuffer);
        ::memcpy(afterBuffer, after, alen*sizeof(QChar));
    }

    QT_TRY {
        if (blen == alen) {
            // replace in place
            detach();
            for (int i = 0; i < nIndices; ++i)
                memcpy(d->data + indices[i], afterBuffer, alen * sizeof(QChar));
        } else if (alen < blen) {
            // replace from front
            detach();
            uint to = indices[0];
            if (alen)
                memcpy(d->data+to, after, alen*sizeof(QChar));
            to += alen;
            uint movestart = indices[0] + blen;
            for (int i = 1; i < nIndices; ++i) {
                int msize = indices[i] - movestart;
                if (msize > 0) {
                    memmove(d->data + to, d->data + movestart, msize * sizeof(QChar));
                    to += msize;
                }
                if (alen) {
                    memcpy(d->data + to, afterBuffer, alen*sizeof(QChar));
                    to += alen;
                }
                movestart = indices[i] + blen;
            }
            int msize = d->size - movestart;
            if (msize > 0)
                memmove(d->data + to, d->data + movestart, msize * sizeof(QChar));
            resize(d->size - nIndices*(blen-alen));
        } else {
            // replace from back
            int adjust = nIndices*(alen-blen);
            int newLen = d->size + adjust;
            int moveend = d->size;
            resize(newLen);

            while (nIndices) {
                --nIndices;
                int movestart = indices[nIndices] + blen;
                int insertstart = indices[nIndices] + nIndices*(alen-blen);
                int moveto = insertstart + alen;
                memmove(d->data + moveto, d->data + movestart,
                        (moveend - movestart)*sizeof(QChar));
                memcpy(d->data + insertstart, afterBuffer, alen*sizeof(QChar));
                moveend = movestart-blen;
            }
        }
    } QT_CATCH(const std::bad_alloc &) {
        if (afterBuffer != after)
            qFree(afterBuffer);
        QT_RETHROW;
    }
    if (afterBuffer != after)
        qFree(afterBuffer);
}

QString &QString::replace(const QChar *before, int blen,
                          const QChar *after, int alen,
                          Qt::CaseSensitivity cs)
{
    if (d->size == 0) {
        if (blen)
            return *this;
    } else {
        if (cs == Qt::CaseSensitive && before == after && blen == alen)
            return *this;
    }
    if (alen == 0 && blen == 0)
        return *this;

    QStringMatcher matcher(before, blen, cs);

    int index = 0;
    while (1) {
        uint indices[1024];
        uint pos = 0;
        while (pos < 1023) {
            index = matcher.indexIn(*this, index);
            if (index == -1)
                break;
            indices[pos++] = index;
            index += blen;
            // avoid infinite loop
            if (!blen)
                index++;
        }
        if (!pos)
            break;

        replace_helper(indices, pos, blen, after, alen);

        if (index == -1)
            break;
        // index has to be adjusted in case we get back into the loop above.
        index += pos*(alen-blen);
    }

    return *this;
}

QString& QString::replace(QChar ch, const QString &after, Qt::CaseSensitivity cs)
{
    if (after.d->size == 0)
        return remove(ch, cs);

    if (after.d->size == 1)
        return replace(ch, after.d->data[0], cs);

    if (d->size == 0)
        return *this;

    ushort cc = (cs == Qt::CaseSensitive ? ch.unicode() : ch.toCaseFolded().unicode());

    int index = 0;
    while (1) {
        uint indices[1024];
        uint pos = 0;
        if (cs == Qt::CaseSensitive) {
            while (pos < 1023 && index < d->size) {
                if (d->data[index] == cc)
                    indices[pos++] = index;
                index++;
            }
        } else {
            while (pos < 1023 && index < d->size) {
                if (QChar::toCaseFolded(d->data[index]) == cc)
                    indices[pos++] = index;
                index++;
            }
        }
        if (!pos)
            break;

        replace_helper(indices, pos, 1, after.constData(), after.d->size);

        if (index == -1)
            break;
        // index has to be adjusted in case we get back into the loop above.
        index += pos*(after.d->size - 1);
    }
    return *this;
}

QString& QString::replace(QChar before, QChar after, Qt::CaseSensitivity cs)
{
    ushort a = after.unicode();
    ushort b = before.unicode();
    if (d->size) {
        detach();
        ushort *i = d->data;
        const ushort *e = i + d->size;
        if (cs == Qt::CaseSensitive) {
            for (; i != e; ++i)
                if (*i == b)
                    *i = a;
        } else {
            b = foldCase(b);
            for (; i != e; ++i)
                if (foldCase(*i) == b)
                    *i = a;
        }
    }
    return *this;
}

QString &QString::replace(const QLatin1String &before,
                          const QLatin1String &after,
                          Qt::CaseSensitivity cs)
{
    int alen = qstrlen(after.latin1());
    QVarLengthArray<ushort> a(alen);
    for (int i = 0; i < alen; ++i)
        a[i] = (uchar)after.latin1()[i];
    int blen = qstrlen(before.latin1());
    QVarLengthArray<ushort> b(blen);
    for (int i = 0; i < blen; ++i)
        b[i] = (uchar)before.latin1()[i];
    return replace((const QChar *)b.data(), blen, (const QChar *)a.data(), alen, cs);
}

QString &QString::replace(const QLatin1String &before,
                          const QString &after,
                          Qt::CaseSensitivity cs)
{
    int blen = qstrlen(before.latin1());
    QVarLengthArray<ushort> b(blen);
    for (int i = 0; i < blen; ++i)
        b[i] = (uchar)before.latin1()[i];
    return replace((const QChar *)b.data(), blen, after.constData(), after.d->size, cs);
}

QString &QString::replace(const QString &before,
                          const QLatin1String &after,
                          Qt::CaseSensitivity cs)
{
    int alen = qstrlen(after.latin1());
    QVarLengthArray<ushort> a(alen);
    for (int i = 0; i < alen; ++i)
        a[i] = (uchar)after.latin1()[i];
    return replace(before.constData(), before.d->size, (const QChar *)a.data(), alen, cs);
}

QString &QString::replace(QChar c, const QLatin1String &after, Qt::CaseSensitivity cs)
{
    int alen = qstrlen(after.latin1());
    QVarLengthArray<ushort> a(alen);
    for (int i = 0; i < alen; ++i)
        a[i] = (uchar)after.latin1()[i];
    return replace(&c, 1, (const QChar *)a.data(), alen, cs);
}


bool QString::operator==(const QString &other) const
{
    if (d->size != other.d->size)
        return false;

    return qMemEquals(d->data, other.d->data, d->size);
}

bool QString::operator==(const QLatin1String &other) const
{
    const ushort *uc = d->data;
    const ushort *e = uc + d->size;
    const uchar *c = (uchar *)other.latin1();

    if (!c)
        return isEmpty();

    while (*c) {
        if (uc == e || *uc != *c)
            return false;
        ++uc;
        ++c;
    }
    return (uc == e);
}

bool QString::operator<(const QString &other) const
{
    return ucstrcmp(constData(), length(), other.constData(), other.length()) < 0;
}

bool QString::operator<(const QLatin1String &other) const
{
    const ushort *uc = d->data;
    const ushort *e = uc + d->size;
    const uchar *c = (uchar *) other.latin1();

    if (!c || *c == 0)
        return false;

    while (*c) {
        if (uc == e || *uc != *c)
            break;
        ++uc;
        ++c;
    }
    return (uc == e ? *c : *uc < *c);
}

bool QString::operator>(const QLatin1String &other) const
{
    const ushort *uc = d->data;;
    const ushort *e = uc + d->size;
    const uchar *c = (uchar *) other.latin1();

    if (!c || *c == '\0')
        return !isEmpty();

    while (*c) {
        if (uc == e || *uc != *c)
            break;
        ++uc;
        ++c;
    }
    return (uc == e ? false : *uc > *c);
}

int QString::indexOf(const QString &str, int from, Qt::CaseSensitivity cs) const
{
    return qFindString(unicode(), length(), from, str.unicode(), str.length(), cs);
}

int QString::indexOf(const QLatin1String &str, int from, Qt::CaseSensitivity cs) const
{
    return qt_find_latin1_string(unicode(), size(), str, from, cs);
}

int qFindString(
    const QChar *haystack0, int haystackLen, int from,
    const QChar *needle0, int needleLen, Qt::CaseSensitivity cs)
{
    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, needle0[0], from, cs);

    /*
        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 qFindStringBoyerMoore(haystack0, haystackLen, from,
            needle0, needleLen, cs);

    /*
        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
        ucstrncmp() or ucstrnicmp().
    */
    const ushort *needle = (const ushort *)needle0;
    const ushort *haystack = (const ushort *)haystack0 + from;
    const ushort *end = (const ushort *)haystack0 + (l-sl);
    const int sl_minus_1 = sl-1;
    int hashNeedle = 0, hashHaystack = 0, idx;

    if (cs == Qt::CaseSensitive) {
        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
                 && ucstrncmp((const QChar *)needle, (const QChar *)haystack, sl) == 0)
                return haystack - (const ushort *)haystack0;

            REHASH(*haystack);
            ++haystack;
        }
    } else {
        const ushort *haystack_start = (const ushort *)haystack0;
        for (idx = 0; idx < sl; ++idx) {
            hashNeedle = (hashNeedle<<1) + foldCase(needle + idx, needle);
            hashHaystack = (hashHaystack<<1) + foldCase(haystack + idx, haystack_start);
        }
        hashHaystack -= foldCase(haystack + sl_minus_1, haystack_start);

        while (haystack <= end) {
            hashHaystack += foldCase(haystack + sl_minus_1, haystack_start);
            if (hashHaystack == hashNeedle && ucstrnicmp(needle, haystack, sl) == 0)
                return haystack - (const ushort *)haystack0;

            REHASH(foldCase(haystack, haystack_start));
            ++haystack;
        }
    }
    return -1;
}

int QString::indexOf(QChar ch, int from, Qt::CaseSensitivity cs) const
{
    return findChar(unicode(), length(), ch, from, cs);
}

int QString::indexOf(const QStringRef &str, int from, Qt::CaseSensitivity cs) const
{
    return qFindString(unicode(), length(), from, str.unicode(), str.length(), cs);
}

static int lastIndexOfHelper(const ushort *haystack, int from, const ushort *needle, int sl, Qt::CaseSensitivity cs)
{
    /*
        See indexOf() for explanations.
    */

    const ushort *end = haystack;
    haystack += from;
    const int sl_minus_1 = sl-1;
    const ushort *n = needle+sl_minus_1;
    const ushort *h = haystack+sl_minus_1;
    int hashNeedle = 0, hashHaystack = 0, idx;

    if (cs == Qt::CaseSensitive) {
        for (idx = 0; idx < sl; ++idx) {
            hashNeedle = ((hashNeedle<<1) + *(n-idx));
            hashHaystack = ((hashHaystack<<1) + *(h-idx));
        }
        hashHaystack -= *haystack;

        while (haystack >= end) {
            hashHaystack += *haystack;
            if (hashHaystack == hashNeedle
                 && ucstrncmp((const QChar *)needle, (const QChar *)haystack, sl) == 0)
                return haystack - end;
            --haystack;
            REHASH(haystack[sl]);
        }
    } else {
        for (idx = 0; idx < sl; ++idx) {
            hashNeedle = ((hashNeedle<<1) + foldCase(n-idx, needle));
            hashHaystack = ((hashHaystack<<1) + foldCase(h-idx, end));
        }
        hashHaystack -= foldCase(haystack, end);

        while (haystack >= end) {
            hashHaystack += foldCase(haystack, end);
            if (hashHaystack == hashNeedle && ucstrnicmp(needle, haystack, sl) == 0)
                return haystack - end;
            --haystack;
            REHASH(foldCase(haystack + sl, end));
        }
    }
    return -1;
}

int QString::lastIndexOf(const QString &str, int from, Qt::CaseSensitivity cs) const
{
    const int sl = str.d->size;
    if (sl == 1)
        return lastIndexOf(QChar(str.d->data[0]), from, cs);

    const int l = d->size;
    if (from < 0)
        from += l;
    int delta = l-sl;
    if (from == l && sl == 0)
        return from;
    if (from < 0 || from >= l || delta < 0)
        return -1;
    if (from > delta)
        from = delta;

    return lastIndexOfHelper(d->data, from, str.d->data, str.d->size, cs);
}

int QString::lastIndexOf(const QLatin1String &str, int from, Qt::CaseSensitivity cs) const
{
    const int sl = qstrlen(str.latin1());
    if (sl == 1)
        return lastIndexOf(QLatin1Char(str.latin1()[0]), from, cs);

    const int l = d->size;
    if (from < 0)
        from += l;
    int delta = l-sl;
    if (from == l && sl == 0)
        return from;
    if (from < 0 || from >= l || delta < 0)
        return -1;
    if (from > delta)
        from = delta;

    QVarLengthArray<ushort> s(sl);
    for (int i = 0; i < sl; ++i)
        s[i] = str.latin1()[i];

    return lastIndexOfHelper(d->data, from, s.data(), sl, cs);
}

int QString::lastIndexOf(QChar ch, int from, Qt::CaseSensitivity cs) const
{
    return qt_last_index_of(unicode(), size(), ch, from, cs);
    }

int QString::lastIndexOf(const QStringRef &str, int from, Qt::CaseSensitivity cs) const
{
    const int sl = str.size();
    if (sl == 1)
        return lastIndexOf(str.at(0), from, cs);

    const int l = d->size;
    if (from < 0)
        from += l;
    int delta = l - sl;
    if (from == l && sl == 0)
        return from;
    if (from < 0 || from >= l || delta < 0)
    return -1;
    if (from > delta)
        from = delta;

    return lastIndexOfHelper(d->data, from, reinterpret_cast<const ushort*>(str.unicode()),
                             str.size(), cs);
}

#ifndef QT_NO_REGEXP
struct QStringCapture
{
    int pos;
    int len;
    int no;
};

QString& QString::replace(const QRegExp &rx, const QString &after)
{
    QRegExp rx2(rx);

    if (isEmpty() && rx2.indexIn(*this) == -1)
        return *this;

    realloc();

    int index = 0;
    int numCaptures = rx2.captureCount();
    int al = after.length();
    QRegExp::CaretMode caretMode = QRegExp::CaretAtZero;

    if (numCaptures > 0) {
        const QChar *uc = after.unicode();
        int numBackRefs = 0;

        for (int i = 0; i < al - 1; i++) {
            if (uc[i] == QLatin1Char('\\')) {
                int no = uc[i + 1].digitValue();
                if (no > 0 && no <= numCaptures)
                    numBackRefs++;
            }
        }

        /*
            This is the harder case where we have back-references.
        */
        if (numBackRefs > 0) {
            QVarLengthArray<QStringCapture, 16> captures(numBackRefs);
            int j = 0;

            for (int i = 0; i < al - 1; i++) {
                if (uc[i] == QLatin1Char('\\')) {
                    int no = uc[i + 1].digitValue();
                    if (no > 0 && no <= numCaptures) {
                        QStringCapture capture;
                        capture.pos = i;
                        capture.len = 2;

                        if (i < al - 2) {
                            int secondDigit = uc[i + 2].digitValue();
                            if (secondDigit != -1 && ((no * 10) + secondDigit) <= numCaptures) {
                                no = (no * 10) + secondDigit;
                                ++capture.len;
                            }
                        }

                        capture.no = no;
                        captures[j++] = capture;
                    }
                }
            }

            while (index <= length()) {
                index = rx2.indexIn(*this, index, caretMode);
                if (index == -1)
                    break;

                QString after2(after);
                for (j = numBackRefs - 1; j >= 0; j--) {
                    const QStringCapture &capture = captures[j];
                    after2.replace(capture.pos, capture.len, rx2.cap(capture.no));
                }

                replace(index, rx2.matchedLength(), after2);
                index += after2.length();

                // avoid infinite loop on 0-length matches (e.g., QRegExp("[a-z]*"))
                if (rx2.matchedLength() == 0)
                    ++index;

                caretMode = QRegExp::CaretWontMatch;
            }
            return *this;
        }
    }

    /*
        This is the simple and optimized case where we don't have
        back-references.
    */
    while (index != -1) {
        struct {
            int pos;
            int length;
        } replacements[2048];

        int pos = 0;
        int adjust = 0;
        while (pos < 2047) {
            index = rx2.indexIn(*this, index, caretMode);
            if (index == -1)
                break;
            int ml = rx2.matchedLength();
            replacements[pos].pos = index;
            replacements[pos++].length = ml;
            index += ml;
            adjust += al - ml;
            // avoid infinite loop
            if (!ml)
                index++;
        }
        if (!pos)
            break;
        replacements[pos].pos = d->size;
        int newlen = d->size + adjust;

        // to continue searching at the right position after we did
        // the first round of replacements
        if (index != -1)
            index += adjust;
        QString newstring;
        newstring.reserve(newlen + 1);
        QChar *newuc = newstring.data();
        QChar *uc = newuc;
        int copystart = 0;
        int i = 0;
        while (i < pos) {
            int copyend = replacements[i].pos;
            int size = copyend - copystart;
            memcpy(uc, d->data + copystart, size * sizeof(QChar));
            uc += size;
            memcpy(uc, after.d->data, al * sizeof(QChar));
            uc += al;
            copystart = copyend + replacements[i].length;
            i++;
        }
        memcpy(uc, d->data + copystart, (d->size - copystart) * sizeof(QChar));
        newstring.resize(newlen);
        *this = newstring;
        caretMode = QRegExp::CaretWontMatch;
    }
    return *this;
}
#endif

int QString::count(const QString &str, Qt::CaseSensitivity cs) const
{
    return qt_string_count(unicode(), size(), str.unicode(), str.size(), cs);
}

int QString::count(QChar ch, Qt::CaseSensitivity cs) const
{
    return qt_string_count(unicode(), size(), ch, cs);
    }

int QString::count(const QStringRef &str, Qt::CaseSensitivity cs) const
{
    return qt_string_count(unicode(), size(), str.unicode(), str.size(), cs);
}


#ifndef QT_NO_REGEXP

int QString::indexOf(const QRegExp& rx, int from) const
{
    QRegExp rx2(rx);
    return rx2.indexIn(*this, from);
}

int QString::indexOf(QRegExp& rx, int from) const
{
    return rx.indexIn(*this, from);
}

int QString::lastIndexOf(const QRegExp& rx, int from) const
{
    QRegExp rx2(rx);
    return rx2.lastIndexIn(*this, from);
}

int QString::lastIndexOf(QRegExp& rx, int from) const
{
    return rx.lastIndexIn(*this, from);
}

int QString::count(const QRegExp& rx) const
{
    QRegExp rx2(rx);
    int count = 0;
    int index = -1;
    int len = length();
    while (index < len - 1) {                 // count overlapping matches
        index = rx2.indexIn(*this, index + 1);
        if (index == -1)
            break;
        count++;
    }
    return count;
}
#endif // QT_NO_REGEXP

QString QString::section(const QString &sep, int start, int end, SectionFlags flags) const
{
    QStringList sections = split(sep, KeepEmptyParts,
                                 (flags & SectionCaseInsensitiveSeps) ? Qt::CaseInsensitive : Qt::CaseSensitive);
    if (sections.isEmpty())
        return QString();
    if (!(flags & SectionSkipEmpty)) {
        if (start < 0)
            start += sections.count();
        if (end < 0)
            end += sections.count();
    } else {
        int skip = 0;
        for (int k=0; k<sections.size(); ++k) {
            if (sections.at(k).isEmpty())
                skip++;
        }
        if (start < 0)
            start += sections.count() - skip;
        if (end < 0)
            end += sections.count() - skip;
    }
    int x = 0;
    QString ret;
    int first_i = start, last_i = end;
    for (int i = 0; x <= end && i < sections.size(); ++i) {
        QString section = sections.at(i);
        const bool empty = section.isEmpty();
        if (x >= start) {
            if(x == start)
                first_i = i;
            if(x == end)
                last_i = i;
            if(x > start)
                ret += sep;
            ret += section;
        }
        if (!empty || !(flags & SectionSkipEmpty))
            x++;
    }
    if((flags & SectionIncludeLeadingSep) && first_i)
        ret.prepend(sep);
    if((flags & SectionIncludeTrailingSep) && last_i < sections.size()-1)
        ret += sep;
    return ret;
}

#ifndef QT_NO_REGEXP
class qt_section_chunk {
public:
    qt_section_chunk(int l, QString s) { length = l; string = s; }
    int length;
    QString string;
};

QString QString::section(const QRegExp &reg, int start, int end, SectionFlags flags) const
{
    const QChar *uc = unicode();
    if(!uc)
        return QString();

    QRegExp sep(reg);
    sep.setCaseSensitivity((flags & SectionCaseInsensitiveSeps) ? Qt::CaseInsensitive
                                                                : Qt::CaseSensitive);

    QList<qt_section_chunk> sections;
    int n = length(), m = 0, last_m = 0, last_len = 0;
    while ((m = sep.indexIn(*this, m)) != -1) {
        sections.append(qt_section_chunk(last_len, QString(uc + last_m, m - last_m)));
        last_m = m;
        last_len = sep.matchedLength();
        m += qMax(sep.matchedLength(), 1);
    }
    sections.append(qt_section_chunk(last_len, QString(uc + last_m, n - last_m)));

    if(start < 0)
        start += sections.count();
    if(end < 0)
        end += sections.count();

    QString ret;
    int x = 0;
    int first_i = start, last_i = end;
    for (int i = 0; x <= end && i < sections.size(); ++i) {
        const qt_section_chunk &section = sections.at(i);
        const bool empty = (section.length == section.string.length());
        if (x >= start) {
            if(x == start)
                first_i = i;
            if(x == end)
                last_i = i;
            if(x != start)
                ret += section.string;
            else
                ret += section.string.mid(section.length);
        }
        if (!empty || !(flags & SectionSkipEmpty))
            x++;
    }
    if((flags & SectionIncludeLeadingSep) && first_i < sections.size()) {
        const qt_section_chunk &section = sections.at(first_i);
        ret.prepend(section.string.left(section.length));
    }
    if((flags & SectionIncludeTrailingSep) && last_i+1 <= sections.size()-1) {
        const qt_section_chunk &section = sections.at(last_i+1);
        ret += section.string.left(section.length);
    }
    return ret;
}
#endif

QString QString::left(int n)  const
{
    if (n >= d->size || n < 0)
        return *this;
    return QString((const QChar*) d->data, n);
}

QString QString::right(int n) const
{
    if (n >= d->size || n < 0)
        return *this;
    return QString((const QChar*) d->data + d->size - n, n);
}

QString QString::mid(int position, int n) const
{
    if (d == &shared_null || position >= d->size)
        return QString();
    if (n < 0)
        n = d->size - position;
    if (position < 0) {
        n += position;
        position = 0;
    }
    if (n + position > d->size)
        n = d->size - position;
    if (position == 0 && n == d->size)
        return *this;
    return QString((const QChar*) d->data + position, n);
}

bool QString::startsWith(const QString& s, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(isNull() ? 0 : unicode(), size(),
                          s.isNull() ? 0 : s.unicode(), s.size(), cs);
}

bool QString::startsWith(const QLatin1String& s, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(isNull() ? 0 : unicode(), size(), s, cs);
}

bool QString::startsWith(const QChar &c, Qt::CaseSensitivity cs) const
{
    return d->size
           && (cs == Qt::CaseSensitive
               ? d->data[0] == c
               : foldCase(d->data[0]) == foldCase(c.unicode()));
}

bool QString::startsWith(const QStringRef &s, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(isNull() ? 0 : unicode(), size(),
                          s.isNull() ? 0 : s.unicode(), s.size(), cs);
}

bool QString::endsWith(const QString& s, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(isNull() ? 0 : unicode(), size(),
                        s.isNull() ? 0 : s.unicode(), s.size(), cs);
    }

bool QString::endsWith(const QStringRef &s, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(isNull() ? 0 : unicode(), size(),
                        s.isNull() ? 0 : s.unicode(), s.size(), cs);
}


bool QString::endsWith(const QLatin1String& s, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(isNull() ? 0 : unicode(), size(), s, cs);
}

bool QString::endsWith(const QChar &c, Qt::CaseSensitivity cs) const
{
    return d->size
           && (cs == Qt::CaseSensitive
               ? d->data[d->size - 1] == c
               : foldCase(d->data[d->size - 1]) == foldCase(c.unicode()));
}

#if defined(QT_ALWAYS_HAVE_SSE2)
static inline __m128i mergeQuestionMarks(__m128i chunk)
{
    const __m128i questionMark = _mm_set1_epi16('?');

# ifdef __SSE4_2__
    // compare the unsigned shorts for the range 0x0100-0xFFFF
    // note on the use of _mm_cmpestrm:
    //  The MSDN documentation online (http://technet.microsoft.com/en-us/library/bb514080.aspx)
    //  says for range search the following:
    //    For each character c in a, determine whether b0 <= c <= b1 or b2 <= c <= b3
    //
    //  However, all examples on the Internet, including from Intel
    //  (see http://software.intel.com/en-us/articles/xml-parsing-accelerator-with-intel-streaming-simd-extensions-4-intel-sse4/)
    //  put the range to be searched first
    //
    //  Disassembly and instruction-level debugging with GCC and ICC show
    //  that they are doing the right thing. Inverting the arguments in the
    //  instruction does cause a bunch of test failures.

    const int mode = _SIDD_UWORD_OPS | _SIDD_CMP_RANGES | _SIDD_UNIT_MASK;
    const __m128i rangeMatch = _mm_cvtsi32_si128(0xffff0100);
    const __m128i offLimitMask = _mm_cmpestrm(rangeMatch, 2, chunk, 8, mode);

    // replace the non-Latin 1 characters in the chunk with question marks
    chunk = _mm_blendv_epi8(chunk, questionMark, offLimitMask);
# else
    // SSE has no compare instruction for unsigned comparison.
    // The variables must be shiffted + 0x8000 to be compared
    const __m128i signedBitOffset = _mm_set1_epi16(0x8000);
    const __m128i thresholdMask = _mm_set1_epi16(0xff + 0x8000);

    const __m128i signedChunk = _mm_add_epi16(chunk, signedBitOffset);
    const __m128i offLimitMask = _mm_cmpgt_epi16(signedChunk, thresholdMask);

#  ifdef __SSE4_1__
    // replace the non-Latin 1 characters in the chunk with question marks
    chunk = _mm_blendv_epi8(chunk, questionMark, offLimitMask);
#  else
    // offLimitQuestionMark contains '?' for each 16 bits that was off-limit
    // the 16 bits that were correct contains zeros
    const __m128i offLimitQuestionMark = _mm_and_si128(offLimitMask, questionMark);

    // correctBytes contains the bytes that were in limit
    // the 16 bits that were off limits contains zeros
    const __m128i correctBytes = _mm_andnot_si128(offLimitMask, chunk);

    // merge offLimitQuestionMark and correctBytes to have the result
    chunk = _mm_or_si128(correctBytes, offLimitQuestionMark);
#  endif
# endif
    return chunk;
}
#endif

static QByteArray toLatin1_helper(const QChar *data, int length)
{
    QByteArray ba;
    if (length) {
        ba.resize(length);
        const ushort *src = reinterpret_cast<const ushort *>(data);
        uchar *dst = (uchar*) ba.data();
#if defined(QT_ALWAYS_HAVE_SSE2)
        if (length >= 16) {
            const int chunkCount = length >> 4; // divided by 16

            for (int i = 0; i < chunkCount; ++i) {
                __m128i chunk1 = _mm_loadu_si128((__m128i*)src); // load
                chunk1 = mergeQuestionMarks(chunk1);
                src += 8;

                __m128i chunk2 = _mm_loadu_si128((__m128i*)src); // load
                chunk2 = mergeQuestionMarks(chunk2);
                src += 8;

                // pack the two vector to 16 x 8bits elements
                const __m128i result = _mm_packus_epi16(chunk1, chunk2);

                _mm_storeu_si128((__m128i*)dst, result); // store
                dst += 16;
            }
            length = length % 16;
        }
#elif defined(QT_ALWAYS_HAVE_NEON)
        // Refer to the documentation of the SSE2 implementation
        // this use eactly the same method as for SSE except:
        // 1) neon has unsigned comparison
        // 2) packing is done to 64 bits (8 x 8bits component).
        if (length >= 16) {
            const int chunkCount = length >> 3; // divided by 8
            const uint16x8_t questionMark = vdupq_n_u16('?'); // set
            const uint16x8_t thresholdMask = vdupq_n_u16(0xff); // set
            for (int i = 0; i < chunkCount; ++i) {
                uint16x8_t chunk = vld1q_u16((uint16_t *)src); // load
                src += 8;

                const uint16x8_t offLimitMask = vcgtq_u16(chunk, thresholdMask); // chunk > thresholdMask
                const uint16x8_t offLimitQuestionMark = vandq_u16(offLimitMask, questionMark); // offLimitMask & questionMark
                const uint16x8_t correctBytes = vbicq_u16(chunk, offLimitMask); // !offLimitMask & chunk
                chunk = vorrq_u16(correctBytes, offLimitQuestionMark); // correctBytes | offLimitQuestionMark
                const uint8x8_t result = vmovn_u16(chunk); // narrowing move->packing
                vst1_u8(dst, result); // store
                dst += 8;
            }
            length = length % 8;
        }
#endif
        while (length--) {
            *dst++ = (*src>0xff) ? '?' : (uchar) *src;
            ++src;
        }
    }
    return ba;
}

QByteArray QString::toLatin1() const
{
    return toLatin1_helper(unicode(), length());
}

// ### Qt 5: Change the return type of at least toAscii(),
// toLatin1() and unicode() such that the use of Q_COMPILER_MANGLES_RETURN_TYPE
// isn't necessary in the header. See task 177402.

QByteArray QString::toAscii() const
{
#ifndef QT_NO_TEXTCODEC
    if (codecForCStrings)
        return codecForCStrings->fromUnicode(*this);
#endif // QT_NO_TEXTCODEC
    return toLatin1();
}

#if !defined(Q_WS_MAC) && defined(Q_OS_UNIX)
static QByteArray toLocal8Bit_helper(const QChar *data, int length)
{
#ifndef QT_NO_TEXTCODEC
    if (QTextCodec::codecForLocale())
        return QTextCodec::codecForLocale()->fromUnicode(data, length);
#endif // QT_NO_TEXTCODEC
    return toLatin1_helper(data, length);
}
#endif

QByteArray QString::toLocal8Bit() const
{
#ifndef QT_NO_TEXTCODEC
    if (QTextCodec::codecForLocale())
        return QTextCodec::codecForLocale()->fromUnicode(*this);
#endif // QT_NO_TEXTCODEC
    return toLatin1();
}

QByteArray QString::toUtf8() const
{
    if (isNull())
        return QByteArray();

    return QUtf8::convertFromUnicode(constData(), length(), 0);
}

QVector<uint> QString::toUcs4() const
{
    QVector<uint> v(length());
    uint *a = v.data();
    int len = toUcs4_helper<uint>(utf16(), length(), a);
    v.resize(len);
    return v;
}

QString::Data *QString::fromLatin1_helper(const char *str, int size)
{
    Data *d;
    if (!str) {
        d = &shared_null;
        d->ref.ref();
    } else if (size == 0 || (!*str && size < 0)) {
        d = &shared_empty;
        d->ref.ref();
    } else {
        if (size < 0)
            size = qstrlen(str);
        d = static_cast<Data *>(qMalloc(sizeof(Data) + size * sizeof(QChar)));
        Q_CHECK_PTR(d);
        d->ref = 1;
        d->alloc = d->size = size;
        d->clean = d->asciiCache = d->simpletext = d->righttoleft = d->capacity = 0;
        d->data = d->array;
        d->array[size] = '\0';
        ushort *dst = d->data;
        /* SIMD:
         * Unpacking with SSE has been shown to improve performance on recent CPUs
         * The same method gives no improvement with NEON.
         */
#if defined(QT_ALWAYS_HAVE_SSE2)
        if (size >= 16) {
            int chunkCount = size >> 4; // divided by 16
            const __m128i nullMask = _mm_set1_epi32(0);
            for (int i = 0; i < chunkCount; ++i) {
                const __m128i chunk = _mm_loadu_si128((__m128i*)str); // load
                str += 16;

                // unpack the first 8 bytes, padding with zeros
                const __m128i firstHalf = _mm_unpacklo_epi8(chunk, nullMask);
                _mm_storeu_si128((__m128i*)dst, firstHalf); // store
                dst += 8;

                // unpack the last 8 bytes, padding with zeros
                const __m128i secondHalf = _mm_unpackhi_epi8 (chunk, nullMask);
                _mm_storeu_si128((__m128i*)dst, secondHalf); // store
                dst += 8;
            }
            size = size % 16;
        }
#endif
        while (size--)
            *dst++ = (uchar)*str++;
    }
    return d;
}

QString::Data *QString::fromAscii_helper(const char *str, int size)
{
#ifndef QT_NO_TEXTCODEC
    if (codecForCStrings) {
        Data *d;
        if (!str) {
            d = &shared_null;
            d->ref.ref();
        } else if (size == 0 || (!*str && size < 0)) {
            d = &shared_empty;
            d->ref.ref();
        } else {
            if (size < 0)
                size = qstrlen(str);
            QString s = codecForCStrings->toUnicode(str, size);
            d = s.d;
            d->ref.ref();
        }
        return d;
    }
#endif
    return fromLatin1_helper(str, size);
}

QString QString::fromLatin1(const char *str, int size)
{
    return QString(fromLatin1_helper(str, size), 0);
}


#ifdef QT3_SUPPORT

const char *QString::ascii_helper() const
{
    QMutexLocker locker(asciiCacheMutex());
    if (!asciiCache)
        asciiCache = new QHash<void *, QByteArray>();

    d->asciiCache = true;
    QByteArray ascii = toAscii();
    QByteArray old = asciiCache->value(d);
    if (old == ascii)
        return old.constData();
    asciiCache->insert(d, ascii);
    return ascii.constData();
}

const char *QString::latin1_helper() const
{
    QMutexLocker locker(asciiCacheMutex());
    if (!asciiCache)
        asciiCache = new QHash<void *, QByteArray>();

    d->asciiCache = true;
    QByteArray ascii = toLatin1();
    QByteArray old = asciiCache->value(d);
    if (old == ascii)
        return old.constData();
    asciiCache->insert(d, ascii);
    return ascii.constData();
}

#endif

QString QString::fromLocal8Bit(const char *str, int size)
{
    if (!str)
        return QString();
    if (size == 0 || (!*str && size < 0))
        return QLatin1String("");
#if !defined(QT_NO_TEXTCODEC)
    if (size < 0)
        size = qstrlen(str);
    QTextCodec *codec = QTextCodec::codecForLocale();
    if (codec)
        return codec->toUnicode(str, size);
#endif // !QT_NO_TEXTCODEC
    return fromLatin1(str, size);
}

QString QString::fromAscii(const char *str, int size)
{
    return QString(fromAscii_helper(str, size), 0);
}

QString QString::fromUtf8(const char *str, int size)
{
    if (!str)
        return QString();
    if (size < 0)
        size = qstrlen(str);

    return QUtf8::convertToUnicode(str, size, 0);
}

QString QString::fromUtf16(const ushort *unicode, int size)
{
    if (!unicode)
        return QString();
    if (size < 0) {
        size = 0;
        while (unicode[size] != 0)
            ++size;
    }
    return QUtf16::convertToUnicode((const char *)unicode, size*2, 0);
}


QString QString::fromUcs4(const uint *unicode, int size)
{
    if (!unicode)
        return QString();
    if (size < 0) {
        size = 0;
        while (unicode[size] != 0)
            ++size;
    }
    return QUtf32::convertToUnicode((const char *)unicode, size*4, 0);
}

QString& QString::setUnicode(const QChar *unicode, int size)
{
     resize(size);
     if (unicode && size)
         memcpy(d->data, unicode, size * sizeof(QChar));
     return *this;
}

QString QString::simplified() const
{
    if (d->size == 0)
        return *this;

    const QChar * const start = reinterpret_cast<QChar *>(d->data);
    const QChar *from = start;
    const QChar *fromEnd = start + d->size;
    forever {
        QChar ch = *from;
        if (!ch.isSpace())
            break;
        if (++from == fromEnd) {
            // All-whitespace string
            shared_empty.ref.ref();
            return QString(&shared_empty, 0);
        }
    }
    // This loop needs no underflow check, as we already determined that
    // the string contains non-whitespace. If the string has exactly one
    // non-whitespace, it will be checked twice - we can live with that.
    while (fromEnd[-1].isSpace())
        fromEnd--;
    // The rest of the function depends on the fact that we already know
    // that the last character in the source is no whitespace.
    const QChar *copyFrom = from;
    int copyCount;
    forever {
        if (++from == fromEnd) {
            // Only leading and/or trailing whitespace, if any at all
            return mid(copyFrom - start, from - copyFrom);
        }
        QChar ch = *from;
        if (!ch.isSpace())
            continue;
        if (ch != QLatin1Char(' ')) {
            copyCount = from - copyFrom;
            break;
        }
        ch = *++from;
        if (ch.isSpace()) {
            copyCount = from - copyFrom - 1;
            break;
        }
    }
    // 'from' now points at the non-trailing whitespace which made the
    // string not simplified in the first place. 'copyCount' is the number
    // of already simplified characters - at least one, obviously -
    // without a trailing space.
    QString result((fromEnd - from) + copyCount, Qt::Uninitialized);
    QChar *to = reinterpret_cast<QChar *>(result.d->data);
    ::memcpy(to, copyFrom, copyCount * 2);
    to += copyCount;
    fromEnd--;
    QChar ch;
    forever {
        *to++ = QLatin1Char(' ');
        do {
            ch = *++from;
        } while (ch.isSpace());
        if (from == fromEnd)
            break;
        do {
            *to++ = ch;
            ch = *++from;
            if (from == fromEnd)
                goto done;
        } while (!ch.isSpace());
    }
  done:
    *to++ = ch;
    result.truncate(to - reinterpret_cast<QChar *>(result.d->data));
    return result;
}

QString QString::trimmed() const
{
    if (d->size == 0)
        return *this;
    const QChar *s = (const QChar*)d->data;
    if (!s->isSpace() && !s[d->size-1].isSpace())
        return *this;
    int start = 0;
    int end = d->size - 1;
    while (start<=end && s[start].isSpace())  // skip white space from start
        start++;
    if (start <= end) {                          // only white space
        while (end && s[end].isSpace())           // skip white space from end
            end--;
    }
    int l = end - start + 1;
    if (l <= 0) {
        shared_empty.ref.ref();
        return QString(&shared_empty, 0);
    }
    return QString(s + start, l);
}

void QString::truncate(int pos)
{
    if (pos < d->size)
        resize(pos);
}


void QString::chop(int n)
{
    if (n > 0)
        resize(d->size - n);
}

QString& QString::fill(QChar ch, int size)
{
    resize(size < 0 ? d->size : size);
    if (d->size) {
        QChar *i = (QChar*)d->data + d->size;
        QChar *b = (QChar*)d->data;
        while (i != b)
           *--i = ch;
    }
    return *this;
}

int QString::compare(const QString &other) const
{
    return ucstrcmp(constData(), length(), other.constData(), other.length());
}

int QString::compare(const QString &other, Qt::CaseSensitivity cs) const
{
    if (cs == Qt::CaseSensitive)
        return ucstrcmp(constData(), length(), other.constData(), other.length());
    return ucstricmp(d->data, d->data + d->size, other.d->data, other.d->data + other.d->size);
}

int QString::compare_helper(const QChar *data1, int length1, const QChar *data2, int length2,
                            Qt::CaseSensitivity cs)
{
    if (cs == Qt::CaseSensitive)
        return ucstrcmp(data1, length1, data2, length2);
    register const ushort *s1 = reinterpret_cast<const ushort *>(data1);
    register const ushort *s2 = reinterpret_cast<const ushort *>(data2);
    return ucstricmp(s1, s1 + length1, s2, s2 + length2);
}

int QString::compare(const QLatin1String &other, Qt::CaseSensitivity cs) const
{
    return compare_helper(unicode(), length(), other, cs);
}

int QString::compare_helper(const QChar *data1, int length1, QLatin1String s2,
                            Qt::CaseSensitivity cs)
{
    const ushort *uc = reinterpret_cast<const ushort *>(data1);
    const ushort *e = uc + length1;
    const uchar *c = (uchar *)s2.latin1();

    if (!c)
        return length1;

    if (cs == Qt::CaseSensitive) {
        while (uc < e && *c && *uc == *c)
            uc++, c++;

        if (uc == e)
            return -*c;

        return *uc - *c;
    } else {
        return ucstricmp(uc, e, c);
    }
}

#if !defined(CSTR_LESS_THAN)
#define CSTR_LESS_THAN    1
#define CSTR_EQUAL        2
#define CSTR_GREATER_THAN 3
#endif

int QString::localeAwareCompare(const QString &other) const
{
    return localeAwareCompare_helper(constData(), length(), other.constData(), other.length());
}

#if defined(Q_OS_WIN32) || defined(Q_OS_WINCE)
QT_END_NAMESPACE
#include "qt_windows.h"
QT_BEGIN_NAMESPACE
#endif

int QString::localeAwareCompare_helper(const QChar *data1, int length1,
                                       const QChar *data2, int length2)
{
    // do the right thing for null and empty
    if (length1 == 0 || length2 == 0)
        return ucstrcmp(data1, length1, data2, length2);

#if defined(Q_OS_WIN32) || defined(Q_OS_WINCE)
    int res = CompareString(GetUserDefaultLCID(), 0, (wchar_t*)data1, length1, (wchar_t*)data2, length2);

    switch (res) {
    case CSTR_LESS_THAN:
        return -1;
    case CSTR_GREATER_THAN:
        return 1;
    default:
        return 0;
    }
#elif defined (Q_OS_MAC)
    // Use CFStringCompare for comparing strings on Mac. This makes Qt order
    // strings the same way as native applications do, and also respects
    // the "Order for sorted lists" setting in the International preferences
    // panel.
    const CFStringRef thisString =
        CFStringCreateWithCharactersNoCopy(kCFAllocatorDefault,
            reinterpret_cast<const UniChar *>(data1), length1, kCFAllocatorNull);
    const CFStringRef otherString =
        CFStringCreateWithCharactersNoCopy(kCFAllocatorDefault,
            reinterpret_cast<const UniChar *>(data2), length2, kCFAllocatorNull);

    const int result = CFStringCompare(thisString, otherString, kCFCompareLocalized);
    CFRelease(thisString);
    CFRelease(otherString);
    return result;
#elif defined(Q_OS_SYMBIAN)
    TPtrC p1 = TPtrC16(reinterpret_cast<const TUint16 *>(data1), length1);
    TPtrC p2 = TPtrC16(reinterpret_cast<const TUint16 *>(data2), length2);
    return p1.CompareC(p2);
#elif defined(Q_OS_UNIX)
#  if defined(QT_USE_ICU)
    int res;
    if (qt_ucol_strcoll(data1, length1, data2, length2, &res)) {
        if (res == 0)
            res = ucstrcmp(data1, length1, data2, length2);
        return res;
    } // else fall through
#  endif
    // declared in <string.h>
    int delta = strcoll(toLocal8Bit_helper(data1, length1), toLocal8Bit_helper(data2, length2));
    if (delta == 0)
        delta = ucstrcmp(data1, length1, data2, length2);
    return delta;
#else
    return ucstrcmp(data1, length1, data2, length2);
#endif
}


const ushort *QString::utf16() const
{
    if (d->data != d->array) {
        QString *that = const_cast<QString*>(this);
        that->realloc();   // ensure '\\0'-termination for ::fromRawData strings
        return that->d->data;
    }
    return d->array;
}

QString QString::leftJustified(int width, QChar fill, bool truncate) const
{
    QString result;
    int len = length();
    int padlen = width - len;
    if (padlen > 0) {
        result.resize(len+padlen);
        if (len)
            memcpy(result.d->data, d->data, sizeof(QChar)*len);
        QChar *uc = (QChar*)result.d->data + len;
        while (padlen--)
           * uc++ = fill;
    } else {
        if (truncate)
            result = left(width);
        else
            result = *this;
    }
    return result;
}

QString QString::rightJustified(int width, QChar fill, bool truncate) const
{
    QString result;
    int len = length();
    int padlen = width - len;
    if (padlen > 0) {
        result.resize(len+padlen);
        QChar *uc = (QChar*)result.d->data;
        while (padlen--)
           * uc++ = fill;
        if (len)
            memcpy(uc, d->data, sizeof(QChar)*len);
    } else {
        if (truncate)
            result = left(width);
        else
            result = *this;
    }
    return result;
}

QString QString::toLower() const
{
    const ushort *p = d->data;
    if (!p)
        return *this;
    if (!d->size)
        return *this;

    const ushort *e = d->data + d->size;

    // this avoids one out of bounds check in the loop
    if (QChar(*p).isLowSurrogate())
        ++p;

    while (p != e) {
        uint c = *p;
        if (QChar(c).isLowSurrogate() && QChar(*(p - 1)).isHighSurrogate())
            c = QChar::surrogateToUcs4(*(p - 1), c);
        const QUnicodeTables::Properties *prop = qGetProp(c);
        if (prop->lowerCaseDiff || prop->lowerCaseSpecial) {
            QString s(d->size, Qt::Uninitialized);
            memcpy(s.d->data, d->data, (p - d->data)*sizeof(ushort));
            ushort *pp = s.d->data + (p - d->data);
            while (p < e) {
                uint c = *p;
                if (QChar(c).isLowSurrogate() && QChar(*(p - 1)).isHighSurrogate())
                    c = QChar::surrogateToUcs4(*(p - 1), c);
                prop = qGetProp(c);
                if (prop->lowerCaseSpecial) {
                    int pos = pp - s.d->data;
                    s.resize(s.d->size + SPECIAL_CASE_MAX_LEN);
                    pp = s.d->data + pos;
                    const ushort *specialCase = specialCaseMap + prop->lowerCaseDiff;
                    while (*specialCase)
                        *pp++ = *specialCase++;
                } else {
                    *pp++ = *p + prop->lowerCaseDiff;
                }
                ++p;
            }
            s.truncate(pp - s.d->data);
            return s;
        }
        ++p;
    }
    return *this;
}

QString QString::toCaseFolded() const
{
    if (!d->size)
        return *this;

    const ushort *p = d->data;
    if (!p)
        return *this;

    const ushort *e = d->data + d->size;

    uint last = 0;
    while (p < e) {
        ushort folded = foldCase(*p, last);
        if (folded != *p) {
            QString s(*this);
            s.detach();
            ushort *pp = s.d->data + (p - d->data);
            const ushort *ppe = s.d->data + s.d->size;
            last = pp > s.d->data ? *(pp - 1) : 0;
            while (pp < ppe) {
                *pp = foldCase(*pp, last);
                ++pp;
            }
            return s;
        }
        p++;
    }
    return *this;
}

QString QString::toUpper() const
{
    const ushort *p = d->data;
    if (!p)
        return *this;
    if (!d->size)
        return *this;

    const ushort *e = d->data + d->size;

    // this avoids one out of bounds check in the loop
    if (QChar(*p).isLowSurrogate())
        ++p;

    while (p != e) {
        uint c = *p;
        if (QChar(c).isLowSurrogate() && QChar(*(p - 1)).isHighSurrogate())
            c = QChar::surrogateToUcs4(*(p - 1), c);
        const QUnicodeTables::Properties *prop = qGetProp(c);
        if (prop->upperCaseDiff || prop->upperCaseSpecial) {
            QString s(d->size, Qt::Uninitialized);
            memcpy(s.d->data, d->data, (p - d->data)*sizeof(ushort));
            ushort *pp = s.d->data + (p - d->data);
            while (p < e) {
                uint c = *p;
                if (QChar(c).isLowSurrogate() && QChar(*(p - 1)).isHighSurrogate())
                    c = QChar::surrogateToUcs4(*(p - 1), c);
                prop = qGetProp(c);
                if (prop->upperCaseSpecial) {
                    int pos = pp - s.d->data;
                    s.resize(s.d->size + SPECIAL_CASE_MAX_LEN);
                    pp = s.d->data + pos;
                    const ushort *specialCase = specialCaseMap + prop->upperCaseDiff;
                    while (*specialCase)
                        *pp++ = *specialCase++;
                } else {
                    *pp++ = *p + prop->upperCaseDiff;
                }
                ++p;
            }
            s.truncate(pp - s.d->data);
            return s;
        }
        ++p;
    }
    return *this;
}

// ### Qt 5: Consider whether this function shouldn't be removed See task 202871.
QString &QString::sprintf(const char *cformat, ...)
{
    va_list ap;
    va_start(ap, cformat);
    QString &s = vsprintf(cformat, ap);
    va_end(ap);
    return s;
}

QString &QString::vsprintf(const char* cformat, va_list ap)
{
    QLocale locale(QLocale::C);

    if (!cformat || !*cformat) {
        // Qt 1.x compat
        *this = fromLatin1("");
        return *this;
    }

    // Parse cformat

    QString result;
    const char *c = cformat;
    for (;;) {
        // Copy non-escape chars to result
#ifndef QT_NO_TEXTCODEC
        int i = 0;
        while (*(c + i) != '\0' && *(c + i) != '%')
            ++i;
        if (codecForCStrings)
            result.append(codecForCStrings->toUnicode(c, i));
        else
            result.append(fromLatin1(c, i));
        c += i;
#else
        while (*c != '\0' && *c != '%')
            result.append(QLatin1Char(*c++));
#endif

        if (*c == '\0')
            break;

        // Found '%'
        const char *escape_start = c;
        ++c;

        if (*c == '\0') {
            result.append(QLatin1Char('%')); // a % at the end of the string - treat as non-escape text
            break;
        }
        if (*c == '%') {
            result.append(QLatin1Char('%')); // %%
            ++c;
            continue;
        }

        // Parse flag characters
        uint flags = 0;
        bool no_more_flags = false;
        do {
            switch (*c) {
                case '#': flags |= QLocalePrivate::Alternate; break;
                case '0': flags |= QLocalePrivate::ZeroPadded; break;
                case '-': flags |= QLocalePrivate::LeftAdjusted; break;
                case ' ': flags |= QLocalePrivate::BlankBeforePositive; break;
                case '+': flags |= QLocalePrivate::AlwaysShowSign; break;
                case '\'': flags |= QLocalePrivate::ThousandsGroup; break;
                default: no_more_flags = true; break;
            }

            if (!no_more_flags)
                ++c;
        } while (!no_more_flags);

        if (*c == '\0') {
            result.append(QLatin1String(escape_start)); // incomplete escape, treat as non-escape text
            break;
        }

        // Parse field width
        int width = -1; // -1 means unspecified
        if (qIsDigit(*c)) {
            QString width_str;
            while (*c != '\0' && qIsDigit(*c))
                width_str.append(QLatin1Char(*c++));

            // can't be negative - started with a digit
            // contains at least one digit
            width = width_str.toInt();
        }
        else if (*c == '*') {
            width = va_arg(ap, int);
            if (width < 0)
                width = -1; // treat all negative numbers as unspecified
            ++c;
        }

        if (*c == '\0') {
            result.append(QLatin1String(escape_start)); // incomplete escape, treat as non-escape text
            break;
        }

        // Parse precision
        int precision = -1; // -1 means unspecified
        if (*c == '.') {
            ++c;
            if (qIsDigit(*c)) {
                QString precision_str;
                while (*c != '\0' && qIsDigit(*c))
                    precision_str.append(QLatin1Char(*c++));

                // can't be negative - started with a digit
                // contains at least one digit
                precision = precision_str.toInt();
            }
            else if (*c == '*') {
                precision = va_arg(ap, int);
                if (precision < 0)
                    precision = -1; // treat all negative numbers as unspecified
                ++c;
            }
        }

        if (*c == '\0') {
            result.append(QLatin1String(escape_start)); // incomplete escape, treat as non-escape text
            break;
        }

        // Parse the length modifier
        enum LengthMod { lm_none, lm_hh, lm_h, lm_l, lm_ll, lm_L, lm_j, lm_z, lm_t };
        LengthMod length_mod = lm_none;
        switch (*c) {
            case 'h':
                ++c;
                if (*c == 'h') {
                    length_mod = lm_hh;
                    ++c;
                }
                else
                    length_mod = lm_h;
                break;

            case 'l':
                ++c;
                if (*c == 'l') {
                    length_mod = lm_ll;
                    ++c;
                }
                else
                    length_mod = lm_l;
                break;

            case 'L':
                ++c;
                length_mod = lm_L;
                break;

            case 'j':
                ++c;
                length_mod = lm_j;
                break;

            case 'z':
            case 'Z':
                ++c;
                length_mod = lm_z;
                break;

            case 't':
                ++c;
                length_mod = lm_t;
                break;

            default: break;
        }

        if (*c == '\0') {
            result.append(QLatin1String(escape_start)); // incomplete escape, treat as non-escape text
            break;
        }

        // Parse the conversion specifier and do the conversion
        QString subst;
        switch (*c) {
            case 'd':
            case 'i': {
                qint64 i;
                switch (length_mod) {
                    case lm_none: i = va_arg(ap, int); break;
                    case lm_hh: i = va_arg(ap, int); break;
                    case lm_h: i = va_arg(ap, int); break;
                    case lm_l: i = va_arg(ap, long int); break;
                    case lm_ll: i = va_arg(ap, qint64); break;
                    case lm_j: i = va_arg(ap, long int); break;
                    case lm_z: i = va_arg(ap, size_t); break;
                    case lm_t: i = va_arg(ap, int); break;
                    default: i = 0; break;
                }
                subst = locale.d()->longLongToString(i, precision, 10, width, flags);
                ++c;
                break;
            }
            case 'o':
            case 'u':
            case 'x':
            case 'X': {
                quint64 u;
                switch (length_mod) {
                    case lm_none: u = va_arg(ap, uint); break;
                    case lm_hh: u = va_arg(ap, uint); break;
                    case lm_h: u = va_arg(ap, uint); break;
                    case lm_l: u = va_arg(ap, ulong); break;
                    case lm_ll: u = va_arg(ap, quint64); break;
                    case lm_z: u = va_arg(ap, size_t); break;
                    default: u = 0; break;
                }

                if (qIsUpper(*c))
                    flags |= QLocalePrivate::CapitalEorX;

                int base = 10;
                switch (qToLower(*c)) {
                    case 'o':
                        base = 8; break;
                    case 'u':
                        base = 10; break;
                    case 'x':
                        base = 16; break;
                    default: break;
                }
                subst = locale.d()->unsLongLongToString(u, precision, base, width, flags);
                ++c;
                break;
            }
            case 'E':
            case 'e':
            case 'F':
            case 'f':
            case 'G':
            case 'g':
            case 'A':
            case 'a': {
                double d;
                if (length_mod == lm_L)
                    d = va_arg(ap, long double); // not supported - converted to a double
                else
                    d = va_arg(ap, double);

                if (qIsUpper(*c))
                    flags |= QLocalePrivate::CapitalEorX;

                QLocalePrivate::DoubleForm form = QLocalePrivate::DFDecimal;
                switch (qToLower(*c)) {
                    case 'e': form = QLocalePrivate::DFExponent; break;
                    case 'a':                             // not supported - decimal form used instead
                    case 'f': form = QLocalePrivate::DFDecimal; break;
                    case 'g': form = QLocalePrivate::DFSignificantDigits; break;
                    default: break;
                }
                subst = locale.d()->doubleToString(d, precision, form, width, flags);
                ++c;
                break;
            }
            case 'c': {
                if (length_mod == lm_l)
                    subst = QChar((ushort) va_arg(ap, int));
                else
                    subst = QLatin1Char((uchar) va_arg(ap, int));
                ++c;
                break;
            }
            case 's': {
                if (length_mod == lm_l) {
                    const ushort *buff = va_arg(ap, const ushort*);
                    const ushort *ch = buff;
                    while (*ch != 0)
                        ++ch;
                    subst.setUtf16(buff, ch - buff);
                } else
                    subst = QString::fromUtf8(va_arg(ap, const char*));
                if (precision != -1)
                    subst.truncate(precision);
                ++c;
                break;
            }
            case 'p': {
                void *arg = va_arg(ap, void*);
#ifdef Q_OS_WIN64
                quint64 i = reinterpret_cast<quint64>(arg);
#else
                quint64 i = reinterpret_cast<unsigned long>(arg);
#endif
                flags |= QLocalePrivate::Alternate;
                subst = locale.d()->unsLongLongToString(i, precision, 16, width, flags);
                ++c;
                break;
            }
            case 'n':
                switch (length_mod) {
                    case lm_hh: {
                        signed char *n = va_arg(ap, signed char*);
                        *n = result.length();
                        break;
                    }
                    case lm_h: {
                        short int *n = va_arg(ap, short int*);
                        *n = result.length();
                            break;
                    }
                    case lm_l: {
                        long int *n = va_arg(ap, long int*);
                        *n = result.length();
                        break;
                    }
                    case lm_ll: {
                        qint64 *n = va_arg(ap, qint64*);
                        volatile uint tmp = result.length(); // egcs-2.91.66 gets internal
                        *n = tmp;                             // compiler error without volatile
                        break;
                    }
                    default: {
                        int *n = va_arg(ap, int*);
                        *n = result.length();
                        break;
                    }
                }
                ++c;
                break;

            default: // bad escape, treat as non-escape text
                for (const char *cc = escape_start; cc != c; ++cc)
                    result.append(QLatin1Char(*cc));
                continue;
        }

        if (flags & QLocalePrivate::LeftAdjusted)
            result.append(subst.leftJustified(width));
        else
            result.append(subst.rightJustified(width));
    }

    *this = result;

    return *this;
}

qint64 QString::toLongLong(bool *ok, int base) const
{
#if defined(QT_CHECK_RANGE)
    if (base != 0 && (base < 2 || base > 36)) {
        qWarning("QString::toLongLong: Invalid base (%d)", base);
        base = 10;
    }
#endif

    bool my_ok;
    QLocale def_locale;
    qint64 result = def_locale.d()->stringToLongLong(*this, base, &my_ok, QLocalePrivate::FailOnGroupSeparators);
    if (my_ok) {
        if (ok != 0)
            *ok = true;
        return result;
    }

    QLocale c_locale(QLocale::C);
    return c_locale.d()->stringToLongLong(*this, base, ok, QLocalePrivate::FailOnGroupSeparators);
}

quint64 QString::toULongLong(bool *ok, int base) const
{
#if defined(QT_CHECK_RANGE)
    if (base != 0 && (base < 2 || base > 36)) {
        qWarning("QString::toULongLong: Invalid base (%d)", base);
        base = 10;
    }
#endif

    bool my_ok;
    QLocale def_locale;
    quint64 result = def_locale.d()->stringToUnsLongLong(*this, base, &my_ok, QLocalePrivate::FailOnGroupSeparators);
    if (my_ok) {
        if (ok != 0)
            *ok = true;
        return result;
    }

    QLocale c_locale(QLocale::C);
    return c_locale.d()->stringToUnsLongLong(*this, base, ok, QLocalePrivate::FailOnGroupSeparators);
}

long QString::toLong(bool *ok, int base) const
{
    qint64 v = toLongLong(ok, base);
    if (v < LONG_MIN || v > LONG_MAX) {
        if (ok)
            *ok = false;
        v = 0;
    }
    return (long)v;
}

ulong QString::toULong(bool *ok, int base) const
{
    quint64 v = toULongLong(ok, base);
    if (v > ULONG_MAX) {
        if (ok)
            *ok = false;
        v = 0;
    }
    return (ulong)v;
}


int QString::toInt(bool *ok, int base) const
{
    qint64 v = toLongLong(ok, base);
    if (v < INT_MIN || v > INT_MAX) {
        if (ok)
            *ok = false;
        v = 0;
    }
    return v;
}

uint QString::toUInt(bool *ok, int base) const
{
    quint64 v = toULongLong(ok, base);
    if (v > UINT_MAX) {
        if (ok)
            *ok = false;
        v = 0;
    }
    return (uint)v;
}

short QString::toShort(bool *ok, int base) const
{
    long v = toLongLong(ok, base);
    if (v < SHRT_MIN || v > SHRT_MAX) {
        if (ok)
            *ok = false;
        v = 0;
    }
    return (short)v;
}

ushort QString::toUShort(bool *ok, int base) const
{
    ulong v = toULongLong(ok, base);
    if (v > USHRT_MAX) {
        if (ok)
            *ok = false;
        v = 0;
    }
    return (ushort)v;
}


double QString::toDouble(bool *ok) const
{
    bool my_ok;
    QLocale def_locale;
    double result = def_locale.d()->stringToDouble(*this, &my_ok, QLocalePrivate::FailOnGroupSeparators);
    if (my_ok) {
        if (ok != 0)
            *ok = true;
        return result;
    }

    QLocale c_locale(QLocale::C);
    return c_locale.d()->stringToDouble(*this, ok, QLocalePrivate::FailOnGroupSeparators);
}

#define QT_MAX_FLOAT 3.4028234663852886e+38

float QString::toFloat(bool *ok) const
{
    bool myOk;
    double d = toDouble(&myOk);
    if (!myOk || d > QT_MAX_FLOAT || d < -QT_MAX_FLOAT) {
        if (ok != 0)
            *ok = false;
        return 0.0;
    }
    if (ok != 0)
        *ok = true;
    return (float) d;
}

QString &QString::setNum(qlonglong n, int base)
{
#if defined(QT_CHECK_RANGE)
    if (base < 2 || base > 36) {
        qWarning("QString::setNum: Invalid base (%d)", base);
        base = 10;
    }
#endif
    QLocale locale(QLocale::C);
    *this = locale.d()->longLongToString(n, -1, base);
    return *this;
}

QString &QString::setNum(qulonglong n, int base)
{
#if defined(QT_CHECK_RANGE)
    if (base < 2 || base > 36) {
        qWarning("QString::setNum: Invalid base (%d)", base);
        base = 10;
    }
#endif
    QLocale locale(QLocale::C);
    *this = locale.d()->unsLongLongToString(n, -1, base);
    return *this;
}

QString &QString::setNum(double n, char f, int prec)
{
    QLocalePrivate::DoubleForm form = QLocalePrivate::DFDecimal;
    uint flags = 0;

    if (qIsUpper(f))
        flags = QLocalePrivate::CapitalEorX;
    f = qToLower(f);

    switch (f) {
        case 'f':
            form = QLocalePrivate::DFDecimal;
            break;
        case 'e':
            form = QLocalePrivate::DFExponent;
            break;
        case 'g':
            form = QLocalePrivate::DFSignificantDigits;
            break;
        default:
#if defined(QT_CHECK_RANGE)
            qWarning("QString::setNum: Invalid format char '%c'", f);
#endif
            break;
    }

    QLocale locale(QLocale::C);
    *this = locale.d()->doubleToString(n, prec, form, -1, flags);
    return *this;
}

QString QString::number(long n, int base)
{
    QString s;
    s.setNum(n, base);
    return s;
}

QString QString::number(ulong n, int base)
{
    QString s;
    s.setNum(n, base);
    return s;
}

QString QString::number(int n, int base)
{
    QString s;
    s.setNum(n, base);
    return s;
}

QString QString::number(uint n, int base)
{
    QString s;
    s.setNum(n, base);
    return s;
}

QString QString::number(qlonglong n, int base)
{
    QString s;
    s.setNum(n, base);
    return s;
}

QString QString::number(qulonglong n, int base)
{
    QString s;
    s.setNum(n, base);
    return s;
}


QString QString::number(double n, char f, int prec)
{
    QString s;
    s.setNum(n, f, prec);
    return s;
}

QStringList QString::split(const QString &sep, SplitBehavior behavior, Qt::CaseSensitivity cs) const
{
    QStringList list;
    int start = 0;
    int extra = 0;
    int end;
    while ((end = indexOf(sep, start + extra, cs)) != -1) {
        if (start != end || behavior == KeepEmptyParts)
            list.append(mid(start, end - start));
        start = end + sep.size();
        extra = (sep.size() == 0 ? 1 : 0);
    }
    if (start != size() || behavior == KeepEmptyParts)
        list.append(mid(start));
    return list;
}

QStringList QString::split(const QChar &sep, SplitBehavior behavior, Qt::CaseSensitivity cs) const
{
    QStringList list;
    int start = 0;
    int end;
    while ((end = indexOf(sep, start, cs)) != -1) {
        if (start != end || behavior == KeepEmptyParts)
            list.append(mid(start, end - start));
        start = end + 1;
    }
    if (start != size() || behavior == KeepEmptyParts)
        list.append(mid(start));
    return list;
}

#ifndef QT_NO_REGEXP

QStringList QString::split(const QRegExp &rx, SplitBehavior behavior) const
{
    QRegExp rx2(rx);
    QStringList list;
    int start = 0;
    int extra = 0;
    int end;
    while ((end = rx2.indexIn(*this, start + extra)) != -1) {
        int matchedLen = rx2.matchedLength();
        if (start != end || behavior == KeepEmptyParts)
            list.append(mid(start, end - start));
        start = end + matchedLen;
        extra = (matchedLen == 0) ? 1 : 0;
    }
    if (start != size() || behavior == KeepEmptyParts)
        list.append(mid(start));
    return list;
}
#endif

QString QString::normalized(QString::NormalizationForm mode) const
{
    return normalized(mode, UNICODE_DATA_VERSION);
}

QString QString::repeated(int times) const
{
    if (d->size == 0)
        return *this;

    if (times <= 1) {
        if (times == 1)
            return *this;
        return QString();
    }

    const int resultSize = times * d->size;

    QString result;
    result.reserve(resultSize);
    if (result.d->alloc != resultSize)
        return QString(); // not enough memory

    memcpy(result.d->data, d->data, d->size * sizeof(ushort));

    int sizeSoFar = d->size;
    ushort *end = result.d->data + sizeSoFar;

    const int halfResultSize = resultSize >> 1;
    while (sizeSoFar <= halfResultSize) {
        memcpy(end, result.d->data, sizeSoFar * sizeof(ushort));
        end += sizeSoFar;
        sizeSoFar <<= 1;
    }
    memcpy(end, result.d->data, (resultSize - sizeSoFar) * sizeof(ushort));
    result.d->data[resultSize] = '\0';
    result.d->size = resultSize;
    return result;
}

void qt_string_normalize(QString *data, QString::NormalizationForm mode, QChar::UnicodeVersion version, int from);
QString QString::normalized(QString::NormalizationForm mode, QChar::UnicodeVersion version) const
{
    QString copy = *this;
    qt_string_normalize(&copy, mode, version, 0);
    return copy;
}

void qt_string_normalize(QString *data, QString::NormalizationForm mode, QChar::UnicodeVersion version, int from)
{
    bool simple = true;
    const QChar *p = data->constData();
    int len = data->length();
    for (int i = from; i < len; ++i) {
        if (p[i].unicode() >= 0x80) {
            simple = false;
            break;
        }
    }
    if (simple)
        return;

    if (version == QChar::Unicode_Unassigned) {
        version = UNICODE_DATA_VERSION;
    } else if (version != UNICODE_DATA_VERSION) {
        const QString &s = *data;
        QChar *d = 0;
        for (int i = 0; i < NumNormalizationCorrections; ++i) {
            const NormalizationCorrection &n = uc_normalization_corrections[i];
            if (n.version > version) {
                int pos = from;
                if (QChar::requiresSurrogates(n.ucs4)) {
                    ushort ucs4High = QChar::highSurrogate(n.ucs4);
                    ushort ucs4Low = QChar::lowSurrogate(n.ucs4);
                    ushort oldHigh = QChar::highSurrogate(n.old_mapping);
                    ushort oldLow = QChar::lowSurrogate(n.old_mapping);
                    while (pos < s.length() - 1) {
                        if (s.at(pos).unicode() == ucs4High && s.at(pos + 1).unicode() == ucs4Low) {
                            if (!d)
                                d = data->data();
                            d[pos] = QChar(oldHigh);
                            d[++pos] = QChar(oldLow);
                        }
                        ++pos;
                    }
                } else {
                    while (pos < s.length()) {
                        if (s.at(pos).unicode() == n.ucs4) {
                            if (!d)
                                d = data->data();
                            d[pos] = QChar(n.old_mapping);
                        }
                        ++pos;
                    }
                }
            }
        }
    }
    decomposeHelper(data, mode < QString::NormalizationForm_KD, version, from);

    canonicalOrderHelper(data, version, from);

    if (mode == QString::NormalizationForm_D || mode == QString::NormalizationForm_KD)
        return;

    composeHelper(data, version, from);
}


struct ArgEscapeData
{
    int min_escape;            // lowest escape sequence number
    int occurrences;           // number of occurrences of the lowest escape sequence number
    int locale_occurrences;    // number of occurrences of the lowest escape sequence number that
                               // contain 'L'
    int escape_len;            // total length of escape sequences which will be replaced
};

static ArgEscapeData findArgEscapes(const QString &s)
{
    const QChar *uc_begin = s.unicode();
    const QChar *uc_end = uc_begin + s.length();

    ArgEscapeData d;

    d.min_escape = INT_MAX;
    d.occurrences = 0;
    d.escape_len = 0;
    d.locale_occurrences = 0;

    const QChar *c = uc_begin;
    while (c != uc_end) {
        while (c != uc_end && c->unicode() != '%')
            ++c;

        if (c == uc_end)
            break;
        const QChar *escape_start = c;
        if (++c == uc_end)
            break;

        bool locale_arg = false;
        if (c->unicode() == 'L') {
            locale_arg = true;
            if (++c == uc_end)
                break;
        }

        if (c->digitValue() == -1)
            continue;

        int escape = c->digitValue();
        ++c;

        if (c != uc_end && c->digitValue() != -1) {
            escape = (10 * escape) + c->digitValue();
            ++c;
        }

        if (escape > d.min_escape)
            continue;

        if (escape < d.min_escape) {
            d.min_escape = escape;
            d.occurrences = 0;
            d.escape_len = 0;
            d.locale_occurrences = 0;
        }

        ++d.occurrences;
        if (locale_arg)
            ++d.locale_occurrences;
        d.escape_len += c - escape_start;
    }
    return d;
}

static QString replaceArgEscapes(const QString &s, const ArgEscapeData &d, int field_width,
                                 const QString &arg, const QString &larg, const QChar &fillChar = QLatin1Char(' '))
{
    const QChar *uc_begin = s.unicode();
    const QChar *uc_end = uc_begin + s.length();

    int abs_field_width = qAbs(field_width);
    int result_len = s.length()
                     - d.escape_len
                     + (d.occurrences - d.locale_occurrences)
                     *qMax(abs_field_width, arg.length())
                     + d.locale_occurrences
                     *qMax(abs_field_width, larg.length());

    QString result(result_len, Qt::Uninitialized);
    QChar *result_buff = (QChar*) result.unicode();

    QChar *rc = result_buff;
    const QChar *c = uc_begin;
    int repl_cnt = 0;
    while (c != uc_end) {
        /* We don't have to check if we run off the end of the string with c,
           because as long as d.occurrences > 0 we KNOW there are valid escape
           sequences. */

        const QChar *text_start = c;

        while (c->unicode() != '%')
            ++c;

        const QChar *escape_start = c++;

        bool locale_arg = false;
        if (c->unicode() == 'L') {
            locale_arg = true;
            ++c;
        }

        int escape = c->digitValue();
        if (escape != -1) {
            if (c + 1 != uc_end && (c + 1)->digitValue() != -1) {
                escape = (10 * escape) + (c + 1)->digitValue();
                ++c;
            }
        }

        if (escape != d.min_escape) {
            memcpy(rc, text_start, (c - text_start)*sizeof(QChar));
            rc += c - text_start;
        }
        else {
            ++c;

            memcpy(rc, text_start, (escape_start - text_start)*sizeof(QChar));
            rc += escape_start - text_start;

            uint pad_chars;
            if (locale_arg)
                pad_chars = qMax(abs_field_width, larg.length()) - larg.length();
            else
                pad_chars = qMax(abs_field_width, arg.length()) - arg.length();

            if (field_width > 0) { // left padded
                for (uint i = 0; i < pad_chars; ++i)
                    (rc++)->unicode() = fillChar.unicode();
            }

            if (locale_arg) {
                memcpy(rc, larg.unicode(), larg.length()*sizeof(QChar));
                rc += larg.length();
            }
            else {
                memcpy(rc, arg.unicode(), arg.length()*sizeof(QChar));
                rc += arg.length();
            }

            if (field_width < 0) { // right padded
                for (uint i = 0; i < pad_chars; ++i)
                    (rc++)->unicode() = fillChar.unicode();
            }

            if (++repl_cnt == d.occurrences) {
                memcpy(rc, c, (uc_end - c)*sizeof(QChar));
                rc += uc_end - c;
                Q_ASSERT(rc - result_buff == result_len);
                c = uc_end;
            }
        }
    }
    Q_ASSERT(rc == result_buff + result_len);

    return result;
}

QString QString::arg(const QString &a, int fieldWidth, const QChar &fillChar) const
{
    ArgEscapeData d = findArgEscapes(*this);

    if (d.occurrences == 0) {
        qWarning("QString::arg: Argument missing: %s, %s", toLocal8Bit().data(),
                  a.toLocal8Bit().data());
        return *this;
    }
    return replaceArgEscapes(*this, d, fieldWidth, a, a, fillChar);
}

QString QString::arg(qlonglong a, int fieldWidth, int base, const QChar &fillChar) const
{
    ArgEscapeData d = findArgEscapes(*this);

    if (d.occurrences == 0) {
        qWarning() << "QString::arg: Argument missing:" << *this << ',' << a;
        return *this;
    }

    unsigned flags = QLocalePrivate::NoFlags;
    if (fillChar == QLatin1Char('0'))
        flags = QLocalePrivate::ZeroPadded;

    QString arg;
    if (d.occurrences > d.locale_occurrences)
        arg = QLocale::c().d()->longLongToString(a, -1, base, fieldWidth, flags);

    QString locale_arg;
    if (d.locale_occurrences > 0) {
        QLocale locale;
        if (!locale.numberOptions() & QLocale::OmitGroupSeparator)
            flags |= QLocalePrivate::ThousandsGroup;
        locale_arg = locale.d()->longLongToString(a, -1, base, fieldWidth, flags);
    }

    return replaceArgEscapes(*this, d, fieldWidth, arg, locale_arg, fillChar);
}

QString QString::arg(qulonglong a, int fieldWidth, int base, const QChar &fillChar) const
{
    ArgEscapeData d = findArgEscapes(*this);

    if (d.occurrences == 0) {
        qWarning() << "QString::arg: Argument missing:" << *this << ',' << a;
        return *this;
    }

    unsigned flags = QLocalePrivate::NoFlags;
    if (fillChar == QLatin1Char('0'))
        flags = QLocalePrivate::ZeroPadded;

    QString arg;
    if (d.occurrences > d.locale_occurrences)
        arg = QLocale::c().d()->unsLongLongToString(a, -1, base, fieldWidth, flags);

    QString locale_arg;
    if (d.locale_occurrences > 0) {
        QLocale locale;
        if (!locale.numberOptions() & QLocale::OmitGroupSeparator)
            flags |= QLocalePrivate::ThousandsGroup;
        locale_arg = locale.d()->unsLongLongToString(a, -1, base, fieldWidth, flags);
    }

    return replaceArgEscapes(*this, d, fieldWidth, arg, locale_arg, fillChar);
}

QString QString::arg(QChar a, int fieldWidth, const QChar &fillChar) const
{
    QString c;
    c += a;
    return arg(c, fieldWidth, fillChar);
}

QString QString::arg(char a, int fieldWidth, const QChar &fillChar) const
{
    QString c;
    c += QLatin1Char(a);
    return arg(c, fieldWidth, fillChar);
}

QString QString::arg(double a, int fieldWidth, char fmt, int prec, const QChar &fillChar) const
{
    ArgEscapeData d = findArgEscapes(*this);

    if (d.occurrences == 0) {
        qWarning("QString::arg: Argument missing: %s, %g", toLocal8Bit().data(), a);
        return *this;
    }

    unsigned flags = QLocalePrivate::NoFlags;
    if (fillChar == QLatin1Char('0'))
        flags = QLocalePrivate::ZeroPadded;

    if (qIsUpper(fmt))
        flags |= QLocalePrivate::CapitalEorX;
    fmt = qToLower(fmt);

    QLocalePrivate::DoubleForm form = QLocalePrivate::DFDecimal;
    switch (fmt) {
    case 'f':
        form = QLocalePrivate::DFDecimal;
        break;
    case 'e':
        form = QLocalePrivate::DFExponent;
        break;
    case 'g':
        form = QLocalePrivate::DFSignificantDigits;
        break;
    default:
#if defined(QT_CHECK_RANGE)
        qWarning("QString::arg: Invalid format char '%c'", fmt);
#endif
        break;
    }

    QString arg;
    if (d.occurrences > d.locale_occurrences)
        arg = QLocale::c().d()->doubleToString(a, prec, form, fieldWidth, flags);

    QString locale_arg;
    if (d.locale_occurrences > 0) {
        QLocale locale;

        if (!locale.numberOptions() & QLocale::OmitGroupSeparator)
            flags |= QLocalePrivate::ThousandsGroup;
        locale_arg = locale.d()->doubleToString(a, prec, form, fieldWidth, flags);
    }

    return replaceArgEscapes(*this, d, fieldWidth, arg, locale_arg, fillChar);
}

static int getEscape(const QChar *uc, int *pos, int len, int maxNumber = 999)
{
    int i = *pos;
    ++i;
    if (i < len && uc[i] == QLatin1Char('L'))
        ++i;
    if (i < len) {
        int escape = uc[i].unicode() - '0';
        if (uint(escape) >= 10U)
            return -1;
        ++i;
        while (i < len) {
            int digit = uc[i].unicode() - '0';
            if (uint(digit) >= 10U)
                break;
            escape = (escape * 10) + digit;
            ++i;
        }
        if (escape <= maxNumber) {
            *pos = i;
            return escape;
        }
    }
    return -1;
}

QString QString::multiArg(int numArgs, const QString **args) const
{
    QString result;
    QMap<int, int> numbersUsed;
    const QChar *uc = (const QChar *) d->data;
    const int len = d->size;
    const int end = len - 1;
    int lastNumber = -1;
    int i = 0;

    // populate the numbersUsed map with the %n's that actually occur in the string
    while (i < end) {
        if (uc[i] == QLatin1Char('%')) {
            int number = getEscape(uc, &i, len);
            if (number != -1) {
                numbersUsed.insert(number, -1);
                continue;
            }
        }
        ++i;
    }

    // assign an argument number to each of the %n's
    QMap<int, int>::iterator j = numbersUsed.begin();
    QMap<int, int>::iterator jend = numbersUsed.end();
    int arg = 0;
    while (j != jend && arg < numArgs) {
        *j = arg++;
        lastNumber = j.key();
        ++j;
    }

    // sanity
    if (numArgs > arg) {
        qWarning("QString::arg: %d argument(s) missing in %s", numArgs - arg, toLocal8Bit().data());
        numArgs = arg;
    }

    i = 0;
    while (i < len) {
        if (uc[i] == QLatin1Char('%') && i != end) {
            int number = getEscape(uc, &i, len, lastNumber);
            int arg = numbersUsed[number];
            if (number != -1 && arg != -1) {
                result += *args[arg];
                continue;
            }
        }
        result += uc[i++];
    }
    return result;
}

static bool isStringRightToLeft(const ushort *p, const ushort *end)
{
    bool righttoleft = false;
    while (p < end) {
        switch(QChar::direction(*p))
        {
        case QChar::DirL:
            goto end;
        case QChar::DirR:
        case QChar::DirAL:
            righttoleft = true;
            goto end;
        default:
            break;
        }
        ++p;
    }
 end:
    return righttoleft;
}

void QString::updateProperties() const
{
    ushort *p = d->data;
    ushort *end = p + d->size;
    d->simpletext = true;
    while (p < end) {
        ushort uc = *p;
        // sort out regions of complex text formatting
        if (uc > 0x058f && (uc < 0x1100 || uc > 0xfb0f)) {
            d->simpletext = false;
        }
        p++;
    }

    d->righttoleft = isStringRightToLeft(d->data, d->data + d->size);
    d->clean = true;
}

bool QString::isRightToLeft() const
{
    return isStringRightToLeft(d->data, d->data + d->size);
}

QString QString::fromRawData(const QChar *unicode, int size)
{
    Data *x = static_cast<Data *>(qMalloc(sizeof(Data)));
    Q_CHECK_PTR(x);
    if (unicode) {
        x->data = (ushort *)unicode;
    } else {
        x->data = x->array;
        size = 0;
    }
    x->ref = 1;
    x->alloc = x->size = size;
    *x->array = '\0';
    x->clean = x->asciiCache = x->simpletext = x->righttoleft = x->capacity = 0;
    return QString(x, 0);
}

QString &QString::setRawData(const QChar *unicode, int size)
{
    if (d->ref != 1 || (d->data == d->array && d->alloc)) {
        *this = fromRawData(unicode, size);
    } else {
#ifdef QT3_SUPPORT
        if (d->asciiCache) {
            QMutexLocker locker(asciiCacheMutex());
            Q_ASSERT(asciiCache);
            asciiCache->remove(d);
        }
#endif
        if (unicode) {
            d->data = (ushort *)unicode;
        } else {
            d->data = d->array;
            size = 0;
        }
        d->alloc = d->size = size;
        *d->array = '\0';
        d->clean = d->asciiCache = d->simpletext = d->righttoleft = d->capacity = 0;
    }
    return *this;
}

/* \fn bool operator==(const QLatin1String &s1, const QLatin1String &s2)
   \relates QLatin1String

   Returns true if string \a s1 is lexically equal to string \a s2; otherwise
   returns false.
*/
/* \fn bool operator!=(const QLatin1String &s1, const QLatin1String &s2)
   \relates QLatin1String

   Returns true if string \a s1 is lexically unequal to string \a s2; otherwise
   returns false.
*/
/* \fn bool operator<(const QLatin1String &s1, const QLatin1String &s2)
   \relates QLatin1String

   Returns true if string \a s1 is lexically smaller than string \a s2; otherwise
   returns false.
*/
/* \fn bool operator<=(const QLatin1String &s1, const QLatin1String &s2)
   \relates QLatin1String

   Returns true if string \a s1 is lexically smaller than or equal to string \a s2; otherwise
   returns false.
*/
/* \fn bool operator>(const QLatin1String &s1, const QLatin1String &s2)
   \relates QLatin1String

   Returns true if string \a s1 is lexically greater than string \a s2; otherwise
   returns false.
*/
/* \fn bool operator>=(const QLatin1String &s1, const QLatin1String &s2)
   \relates QLatin1String

   Returns true if string \a s1 is lexically greater than or equal to
   string \a s2; otherwise returns false.
*/


#if !defined(QT_NO_DATASTREAM) || (defined(QT_BOOTSTRAPPED) && !defined(QT_BUILD_QMAKE))

QDataStream &operator<<(QDataStream &out, const QString &str)
{
    if (out.version() == 1) {
        out << str.toLatin1();
    } else {
        if (!str.isNull() || out.version() < 3) {
            if ((out.byteOrder() == QDataStream::BigEndian) == (QSysInfo::ByteOrder == QSysInfo::BigEndian)) {
                out.writeBytes(reinterpret_cast<const char *>(str.unicode()), sizeof(QChar) * str.length());
            } else {
                QVarLengthArray<ushort> buffer(str.length());
                const ushort *data = reinterpret_cast<const ushort *>(str.constData());
                for (int i = 0; i < str.length(); i++) {
                    buffer[i] = qbswap(*data);
                    ++data;
                }
                out.writeBytes(reinterpret_cast<const char *>(buffer.data()), sizeof(ushort) * buffer.size());
            }
        } else {
            // write null marker
            out << (quint32)0xffffffff;
        }
    }
    return out;
}

QDataStream &operator>>(QDataStream &in, QString &str)
{
#ifdef QT_QSTRING_UCS_4
#if defined(Q_CC_GNU)
#warning "operator>> not working properly"
#endif
#endif

    if (in.version() == 1) {
        QByteArray l;
        in >> l;
        str = QString::fromLatin1(l);
    } else {
        quint32 bytes = 0;
        in >> bytes;                                  // read size of string
        if (bytes == 0xffffffff) {                    // null string
            str.clear();
        } else if (bytes > 0) {                       // not empty
            if (bytes & 0x1) {
                str.clear();
                in.setStatus(QDataStream::ReadCorruptData);
                return in;
            }

            const quint32 Step = 1024 * 1024;
            quint32 len = bytes / 2;
            quint32 allocated = 0;

            while (allocated < len) {
                int blockSize = qMin(Step, len - allocated);
                str.resize(allocated + blockSize);
                if (in.readRawData(reinterpret_cast<char *>(str.data()) + allocated * 2,
                                   blockSize * 2) != blockSize * 2) {
                    str.clear();
                    in.setStatus(QDataStream::ReadPastEnd);
                    return in;
                }
                allocated += blockSize;
            }

            if ((in.byteOrder() == QDataStream::BigEndian)
                    != (QSysInfo::ByteOrder == QSysInfo::BigEndian)) {
                ushort *data = reinterpret_cast<ushort *>(str.data());
                while (len--) {
                    *data = qbswap(*data);
                    ++data;
                }
            }
        } else {
            str = QLatin1String("");
        }
    }
    return in;
}
#endif // QT_NO_DATASTREAM

QString QStringRef::toString() const {
    if (!m_string)
        return QString();
    if (m_size && m_position == 0 && m_size == m_string->size())
        return *m_string;
    return QString(m_string->unicode() + m_position, m_size);
}


bool operator==(const QStringRef &s1,const QStringRef &s2)
{ return (s1.size() == s2.size() &&
          qMemEquals((const ushort *)s1.unicode(), (const ushort *)s2.unicode(), s1.size()));
}

bool operator==(const QString &s1,const QStringRef &s2)
{ return (s1.size() == s2.size() &&
          qMemEquals((const ushort *)s1.unicode(), (const ushort *)s2.unicode(), s1.size()));
}

bool operator==(const QLatin1String &s1, const QStringRef &s2)
{
    const ushort *uc = reinterpret_cast<const ushort *>(s2.unicode());
    const ushort *e = uc + s2.size();
    const uchar *c = reinterpret_cast<const uchar *>(s1.latin1());
    if (!c)
        return s2.isEmpty();

    while (*c) {
        if (uc == e || *uc != *c)
            return false;
        ++uc;
        ++c;
    }
    return (uc == e);
}

bool operator<(const QStringRef &s1,const QStringRef &s2)
{
    return ucstrcmp(s1.constData(), s1.length(), s2.constData(), s2.length()) < 0;
}

QStringRef QStringRef::appendTo(QString *string) const
{
    if (!string)
        return QStringRef();
    int pos = string->size();
    string->insert(pos, unicode(), size());
    return QStringRef(string, pos, size());
}

QString &QString::append(const QStringRef &str)
{
    if (str.string() == this) {
        str.appendTo(this);
    } else if (str.string()) {
        int oldSize = size();
        resize(oldSize + str.size());
        memcpy(data() + oldSize, str.unicode(), str.size() * sizeof(QChar));
    }
    return *this;
}

QStringRef QString::leftRef(int n)  const
{
    if (n >= d->size || n < 0)
        n = d->size;
    return QStringRef(this, 0, n);
}

QStringRef QString::rightRef(int n) const
{
    if (n >= d->size || n < 0)
        n = d->size;
    return QStringRef(this, d->size - n, n);
}

QStringRef QString::midRef(int position, int n) const
{
    if (d == &shared_null || position >= d->size)
        return QStringRef();
    if (n < 0)
        n = d->size - position;
    if (position < 0) {
        n += position;
        position = 0;
    }
    if (n + position > d->size)
        n = d->size - position;
    return QStringRef(this, position, n);
}

int QStringRef::indexOf(const QString &str, int from, Qt::CaseSensitivity cs) const
{
    return qFindString(unicode(), length(), from, str.unicode(), str.length(), cs);
}

int QStringRef::indexOf(QChar ch, int from, Qt::CaseSensitivity cs) const
{
    return findChar(unicode(), length(), ch, from, cs);
}

int QStringRef::indexOf(QLatin1String str, int from, Qt::CaseSensitivity cs) const
{
    return qt_find_latin1_string(unicode(), size(), str, from, cs);
}

int QStringRef::indexOf(const QStringRef &str, int from, Qt::CaseSensitivity cs) const
{
    return qFindString(unicode(), size(), from, str.unicode(), str.size(), cs);
}

int QStringRef::lastIndexOf(const QString &str, int from, Qt::CaseSensitivity cs) const
{
    const int sl = str.size();
    if (sl == 1)
        return lastIndexOf(str.at(0), from, cs);

    const int l = size();;
    if (from < 0)
        from += l;
    int delta = l - sl;
    if (from == l && sl == 0)
        return from;
    if (from < 0 || from >= l || delta < 0)
        return -1;
    if (from > delta)
        from = delta;

    return lastIndexOfHelper(reinterpret_cast<const ushort*>(unicode()), from,
                             reinterpret_cast<const ushort*>(str.unicode()), str.size(), cs);
}

int QStringRef::lastIndexOf(QChar ch, int from, Qt::CaseSensitivity cs) const
{
    return qt_last_index_of(unicode(), size(), ch, from, cs);
}

int QStringRef::lastIndexOf(QLatin1String str, int from, Qt::CaseSensitivity cs) const
{
    const int sl = qstrlen(str.latin1());
    if (sl == 1)
        return lastIndexOf(QLatin1Char(str.latin1()[0]), from, cs);

    const int l = size();
    if (from < 0)
        from += l;
    int delta = l - sl;
    if (from == l && sl == 0)
        return from;
    if (from < 0 || from >= l || delta < 0)
        return -1;
    if (from > delta)
        from = delta;

    QVarLengthArray<ushort> s(sl);
    for (int i = 0; i < sl; ++i)
        s[i] = str.latin1()[i];

    return lastIndexOfHelper(reinterpret_cast<const ushort*>(unicode()), from, s.data(), sl, cs);
}

int QStringRef::lastIndexOf(const QStringRef &str, int from, Qt::CaseSensitivity cs) const
{
    const int sl = str.size();
    if (sl == 1)
        return lastIndexOf(str.at(0), from, cs);

    const int l = size();
    if (from < 0)
        from += l;
    int delta = l - sl;
    if (from == l && sl == 0)
        return from;
    if (from < 0 || from >= l || delta < 0)
        return -1;
    if (from > delta)
        from = delta;

    return lastIndexOfHelper(reinterpret_cast<const ushort*>(unicode()), from,
                             reinterpret_cast<const ushort*>(str.unicode()),
                             str.size(), cs);
}

int QStringRef::count(const QString &str, Qt::CaseSensitivity cs) const
{
    return qt_string_count(unicode(), size(), str.unicode(), str.size(), cs);
}

int QStringRef::count(QChar ch, Qt::CaseSensitivity cs) const
{
    return qt_string_count(unicode(), size(), ch, cs);
}

int QStringRef::count(const QStringRef &str, Qt::CaseSensitivity cs) const
{
    return qt_string_count(unicode(), size(), str.unicode(), str.size(), cs);
}

bool QStringRef::startsWith(const QString &str, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(isNull() ? 0 : unicode(), size(),
                          str.isNull() ? 0 : str.unicode(), str.size(), cs);
}

bool QStringRef::startsWith(QLatin1String str, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(isNull() ? 0 : unicode(), size(), str, cs);
}

bool QStringRef::startsWith(const QStringRef &str, Qt::CaseSensitivity cs) const
{
    return qt_starts_with(isNull() ? 0 : unicode(), size(),
                          str.isNull() ? 0 : str.unicode(), str.size(), cs);
}

bool QStringRef::startsWith(QChar ch, Qt::CaseSensitivity cs) const
{
    if (!isEmpty()) {
        const ushort *data = reinterpret_cast<const ushort*>(unicode());
        return (cs == Qt::CaseSensitive
                ? data[0] == ch
                : foldCase(data[0]) == foldCase(ch.unicode()));
    } else {
        return false;
    }
}

bool QStringRef::endsWith(const QString &str, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(isNull() ? 0 : unicode(), size(),
                        str.isNull() ? 0 : str.unicode(), str.size(), cs);
}

bool QStringRef::endsWith(QChar ch, Qt::CaseSensitivity cs) const
{
    if (!isEmpty()) {
        const ushort *data = reinterpret_cast<const ushort*>(unicode());
        const int size = length();
        return (cs == Qt::CaseSensitive
                ? data[size - 1] == ch
                : foldCase(data[size - 1]) == foldCase(ch.unicode()));
    } else {
        return false;
    }
}

bool QStringRef::endsWith(QLatin1String str, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(isNull() ? 0 : unicode(), size(), str, cs);
}

bool QStringRef::endsWith(const QStringRef &str, Qt::CaseSensitivity cs) const
{
    return qt_ends_with(isNull() ? 0 : unicode(), size(),
                        str.isNull() ? 0 : str.unicode(), str.size(), cs);
}


static inline int qt_last_index_of(const QChar *haystack, int haystackLen, const QChar &needle,
                                   int from, Qt::CaseSensitivity cs)
{
    ushort c = needle.unicode();
    if (from < 0)
        from += haystackLen;
    if (from < 0 || from >= haystackLen)
        return -1;
    if (from >= 0) {
        const ushort *b = reinterpret_cast<const ushort*>(haystack);
        const ushort *n = b + from;
        if (cs == Qt::CaseSensitive) {
            for (; n >= b; --n)
                if (*n == c)
                    return n - b;
        } else {
            c = foldCase(c);
            for (; n >= b; --n)
                if (foldCase(*n) == c)
                    return n - b;
        }
    }
    return -1;


}

static inline int qt_string_count(const QChar *haystack, int haystackLen,
                                  const QChar *needle, int needleLen,
                                  Qt::CaseSensitivity cs)
{
    int num = 0;
    int i = -1;
    if (haystackLen > 500 && needleLen > 5) {
        QStringMatcher matcher(needle, needleLen, cs);
        while ((i = matcher.indexIn(haystack, haystackLen, i + 1)) != -1)
            ++num;
    } else {
        while ((i = qFindString(haystack, haystackLen, i + 1, needle, needleLen, cs)) != -1)
            ++num;
    }
    return num;
}

static inline int qt_string_count(const QChar *unicode, int size, const QChar &ch,
                                  Qt::CaseSensitivity cs)
{
    ushort c = ch.unicode();
    int num = 0;
    const ushort *b = reinterpret_cast<const ushort*>(unicode);
    const ushort *i = b + size;
    if (cs == Qt::CaseSensitive) {
        while (i != b)
            if (*--i == c)
                ++num;
    } else {
        c = foldCase(c);
        while (i != b)
            if (foldCase(*(--i)) == c)
                ++num;
    }
    return num;
}

static inline int qt_find_latin1_string(const QChar *haystack, int size,
                                        const QLatin1String &needle,
                                        int from, Qt::CaseSensitivity cs)
{
    const char *latin1 = needle.latin1();
    int len = qstrlen(latin1);
    QVarLengthArray<ushort> s(len);
    for (int i = 0; i < len; ++i)
        s[i] = latin1[i];

    return qFindString(haystack, size, from,
                       reinterpret_cast<const QChar*>(s.constData()), len, cs);
}

static inline bool qt_starts_with(const QChar *haystack, int haystackLen,
                                  const QChar *needle, int needleLen, Qt::CaseSensitivity cs)
{
    if (!haystack)
        return !needle;
    if (haystackLen == 0)
        return needleLen == 0;
    if (needleLen > haystackLen)
        return false;

    const ushort *h = reinterpret_cast<const ushort*>(haystack);
    const ushort *n = reinterpret_cast<const ushort*>(needle);

    if (cs == Qt::CaseSensitive) {
        return qMemEquals(h, n, needleLen);
    } else {
        uint last = 0;
        uint olast = 0;
        for (int i = 0; i < needleLen; ++i)
            if (foldCase(h[i], last) != foldCase(n[i], olast))
                return false;
    }
    return true;
}

static inline bool qt_starts_with(const QChar *haystack, int haystackLen,
                                  const QLatin1String &needle, Qt::CaseSensitivity cs)
{
    if (!haystack)
        return !needle.latin1();
    if (haystackLen == 0)
        return !needle.latin1() || *needle.latin1() == 0;
    const int slen = qstrlen(needle.latin1());
    if (slen > haystackLen)
        return false;
    const ushort *data = reinterpret_cast<const ushort*>(haystack);
    const uchar *latin = reinterpret_cast<const uchar*>(needle.latin1());
    if (cs == Qt::CaseSensitive) {
        for (int i = 0; i < slen; ++i)
            if (data[i] != latin[i])
                return false;
    } else {
        for (int i = 0; i < slen; ++i)
            if (foldCase(data[i]) != foldCase((ushort)latin[i]))
                return false;
    }
    return true;
}

static inline bool qt_ends_with(const QChar *haystack, int haystackLen,
                                const QChar *needle, int needleLen, Qt::CaseSensitivity cs)
{
    if (!haystack)
        return !needle;
    if (haystackLen == 0)
        return needleLen == 0;
    const int pos = haystackLen - needleLen;
    if (pos < 0)
        return false;

    const ushort *h = reinterpret_cast<const ushort*>(haystack);
    const ushort *n = reinterpret_cast<const ushort*>(needle);

    if (cs == Qt::CaseSensitive) {
        return qMemEquals(h + pos, n, needleLen);
    } else {
        uint last = 0;
        uint olast = 0;
        for (int i = 0; i < needleLen; i++)
            if (foldCase(h[pos+i], last) != foldCase(n[i], olast))
                return false;
    }
    return true;
}


static inline bool qt_ends_with(const QChar *haystack, int haystackLen,
                                const QLatin1String &needle, Qt::CaseSensitivity cs)
{
    if (!haystack)
        return !needle.latin1();
    if (haystackLen == 0)
        return !needle.latin1() || *needle.latin1() == 0;
    const int slen = qstrlen(needle.latin1());
    int pos = haystackLen - slen;
    if (pos < 0)
        return false;
    const uchar *latin = reinterpret_cast<const uchar*>(needle.latin1());
    const ushort *data = reinterpret_cast<const ushort*>(haystack);
    if (cs == Qt::CaseSensitive) {
        for (int i = 0; i < slen; i++)
            if (data[pos+i] != latin[i])
                return false;
    } else {
        for (int i = 0; i < slen; i++)
            if (foldCase(data[pos+i]) != foldCase((ushort)latin[i]))
                return false;
    }
    return true;
}

QByteArray QStringRef::toLatin1() const
{
    return toLatin1_helper(unicode(), length());
}

QByteArray QStringRef::toAscii() const
{
#ifndef QT_NO_TEXTCODEC
    if (QString::codecForCStrings)
        return QString::codecForCStrings->fromUnicode(unicode(), length());
#endif // QT_NO_TEXTCODEC
    return toLatin1();
}

QByteArray QStringRef::toLocal8Bit() const
{
#ifndef QT_NO_TEXTCODEC
    if (QTextCodec::codecForLocale())
        return QTextCodec::codecForLocale()->fromUnicode(unicode(), length());
#endif // QT_NO_TEXTCODEC
    return toLatin1();
}

QByteArray QStringRef::toUtf8() const
{
    if (isNull())
        return QByteArray();

    return QUtf8::convertFromUnicode(constData(), length(), 0);
}

QVector<uint> QStringRef::toUcs4() const
{
    QVector<uint> v(length());
    uint *a = v.data();
    int len = toUcs4_helper<uint>(reinterpret_cast<const unsigned short *>(unicode()), length(), a);
    v.resize(len);
    return v;
}

QT_END_NAMESPACE