/****************************************************************************

**

** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtCore module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qbytearray.h"

#include "qbytearraymatcher.h"

#include "qtools_p.h"

#include "qstring.h"

#include "qlist.h"

#include "qlocale.h"

#include "qlocale_p.h"

#include "qunicodetables_p.h"

#include "qscopedpointer.h"

#ifndef QT_NO_DATASTREAM

#include <qdatastream.h>

#endif

#ifndef QT_NO_COMPRESS

#include <zlib.h>

#endif

#include <ctype.h>

#include <limits.h>

#include <string.h>

#include <stdlib.h>

#define IS_RAW_DATA(d) ((d)->data != (d)->array)

QT_BEGIN_NAMESPACE

int qFindByteArray(

    const char *haystack0, int haystackLen, int from,

    const char *needle0, int needleLen);

int qAllocMore(int alloc, int extra)

{

    if (alloc == 0 && extra == 0)

        return 0;

    const int page = 1 << 12;

    int nalloc;

    alloc += extra;

    if (alloc < 1<<6) {

        nalloc = (1<<3) + ((alloc >>3) << 3);

    } else  {

        // don't do anything if the loop will overflow signed int.

        if (alloc >= INT_MAX/2)

            return INT_MAX;

        nalloc = (alloc < page) ? 1 << 3 : page;

        while (nalloc < alloc) {

            if (nalloc <= 0)

                return INT_MAX;

            nalloc *= 2;

        }

    }

    return nalloc - extra;

}

/*****************************************************************************

  Safe and portable C string functions; extensions to standard string.h

 *****************************************************************************/

/*! \relates QByteArray

    Returns a duplicate string.

    Allocates space for a copy of \a src, copies it, and returns a

    pointer to the copy. If \a src is 0, it immediately returns 0.

    Ownership is passed to the caller, so the returned string must be

    deleted using \c delete[].

*/

char *qstrdup(const char *src)

{

    if (!src)

        return 0;

    char *dst = new char[strlen(src) + 1];

    return qstrcpy(dst, src);

}

/*! \relates QByteArray

    Copies all the characters up to and including the '\\0' from \a

    src into \a dst and returns a pointer to \a dst. If \a src is 0,

    it immediately returns 0.

    This function assumes that \a dst is large enough to hold the

    contents of \a src.

    \sa qstrncpy()

*/

char *qstrcpy(char *dst, const char *src)

{

    if (!src)

        return 0;

#if defined(_MSC_VER) && _MSC_VER >= 1400

    int len = qstrlen(src);

	// This is actually not secure!!! It will be fixed

	// properly in a later release!

    if (len >= 0 && strcpy_s(dst, len+1, src) == 0)

	    return dst;

    return 0;

#else

    return strcpy(dst, src);

#endif

}

/*! \relates QByteArray

    A safe \c strncpy() function.

    Copies at most \a len bytes from \a src (stopping at \a len or the

    terminating '\\0' whichever comes first) into \a dst and returns a

    pointer to \a dst. Guarantees that \a dst is '\\0'-terminated. If

    \a src or \a dst is 0, returns 0 immediately.

    This function assumes that \a dst is at least \a len characters

    long.

    \sa qstrcpy()

*/

char *qstrncpy(char *dst, const char *src, uint len)

{

    if (!src || !dst)

        return 0;

#if defined(_MSC_VER) && _MSC_VER >= 1400

	strncpy_s(dst, len, src, len-1);

#else

    strncpy(dst, src, len);

#endif

    if (len > 0)

        dst[len-1] = '\0';

    return dst;

}

/*! \fn uint qstrlen(const char *str)

    \relates QByteArray

    A safe \c strlen() function.

    Returns the number of characters that precede the terminating '\\0',

    or 0 if \a str is 0.

    \sa qstrnlen()

*/

/*! \fn uint qstrnlen(const char *str, uint maxlen)

    \relates QByteArray

    \since 4.2

    A safe \c strnlen() function.

    Returns the number of characters that precede the terminating '\\0', but

    at most \a maxlen. If \a str is 0, returns 0.

    \sa qstrlen()

*/

/*!

    \relates QByteArray

    A safe \c strcmp() function.

    Compares \a str1 and \a str2. Returns a negative value if \a str1

    is less than \a str2, 0 if \a str1 is equal to \a str2 or a

    positive value if \a str1 is greater than \a str2.

    Special case 1: Returns 0 if \a str1 and \a str2 are both 0.

    Special case 2: Returns an arbitrary non-zero value if \a str1 is 0

    or \a str2 is 0 (but not both).

    \sa qstrncmp(), qstricmp(), qstrnicmp(), {8-bit Character Comparisons}

*/

int qstrcmp(const char *str1, const char *str2)

{

    return (str1 && str2) ? strcmp(str1, str2)

        : (str1 ? 1 : (str2 ? -1 : 0));

}

/*! \fn int qstrncmp(const char *str1, const char *str2, uint len);

    \relates QByteArray

    A safe \c strncmp() function.

    Compares at most \a len bytes of \a str1 and \a str2.

    Returns a negative value if \a str1 is less than \a str2, 0 if \a

    str1 is equal to \a str2 or a positive value if \a str1 is greater

    than \a str2.

    Special case 1: Returns 0 if \a str1 and \a str2 are both 0.

    Special case 2: Returns a random non-zero value if \a str1 is 0

    or \a str2 is 0 (but not both).

    \sa qstrcmp(), qstricmp(), qstrnicmp(), {8-bit Character Comparisons}

*/

/*! \relates QByteArray

    A safe \c stricmp() function.

    Compares \a str1 and \a str2 ignoring the case of the

    characters. The encoding of the strings is assumed to be Latin-1.

    Returns a negative value if \a str1 is less than \a str2, 0 if \a

    str1 is equal to \a str2 or a positive value if \a str1 is greater

    than \a str2.

    Special case 1: Returns 0 if \a str1 and \a str2 are both 0.

    Special case 2: Returns a random non-zero value if \a str1 is 0

    or \a str2 is 0 (but not both).

    \sa qstrcmp(), qstrncmp(), qstrnicmp(), {8-bit Character Comparisons}

*/

int qstricmp(const char *str1, const char *str2)

{

    register const uchar *s1 = reinterpret_cast<const uchar *>(str1);

    register const uchar *s2 = reinterpret_cast<const uchar *>(str2);

    int res;

    uchar c;

    if (!s1 || !s2)

        return s1 ? 1 : (s2 ? -1 : 0);

    for (; !(res = (c = QChar::toLower((ushort)*s1)) - QChar::toLower((ushort)*s2)); s1++, s2++)

        if (!c)                                // strings are equal

            break;

    return res;

}

/*! \relates QByteArray

    A safe \c strnicmp() function.

    Compares at most \a len bytes of \a str1 and \a str2 ignoring the

    case of the characters. The encoding of the strings is assumed to

    be Latin-1.

    Returns a negative value if \a str1 is less than \a str2, 0 if \a str1

    is equal to \a str2 or a positive value if \a str1 is greater than \a

    str2.

    Special case 1: Returns 0 if \a str1 and \a str2 are both 0.

    Special case 2: Returns a random non-zero value if \a str1 is 0

    or \a str2 is 0 (but not both).

    \sa qstrcmp(), qstrncmp(), qstricmp(), {8-bit Character Comparisons}

*/

int qstrnicmp(const char *str1, const char *str2, uint len)

{

    register const uchar *s1 = reinterpret_cast<const uchar *>(str1);

    register const uchar *s2 = reinterpret_cast<const uchar *>(str2);

    int res;

    uchar c;

    if (!s1 || !s2)

        return s1 ? 1 : (s2 ? -1 : 0);

    for (; len--; s1++, s2++) {

        if ((res = (c = QChar::toLower((ushort)*s1)) - QChar::toLower((ushort)*s2)))

            return res;

        if (!c)                                // strings are equal

            break;

    }

    return 0;

}

/*!

    \internal

 */

int qstrcmp(const QByteArray &str1, const char *str2)

{

    if (!str2)

        return str1.isEmpty() ? 0 : +1;

    const char *str1data = str1.constData();

    const char *str1end = str1data + str1.length();

    for ( ; str1data < str1end && *str2; ++str1data, ++str2) {

        register int diff = int(uchar(*str1data)) - uchar(*str2);

        if (diff)

            // found a difference

            return diff;

    }

    // Why did we stop?

    if (*str2 != '\0')

        // not the null, so we stopped because str1 is shorter

        return -1;

    if (str1data < str1end)

        // we haven't reached the end, so str1 must be longer

        return +1;

    return 0;

}

/*!

    \internal

 */

int qstrcmp(const QByteArray &str1, const QByteArray &str2)

{

    int l1 = str1.length();

    int l2 = str2.length();

    int ret = memcmp(str1, str2, qMin(l1, l2));

    if (ret != 0)

        return ret;

    // they matched qMin(l1, l2) bytes

    // so the longer one is lexically after the shorter one

    return l1 - l2;

}

// the CRC table below is created by the following piece of code

#if 0

static void createCRC16Table()                        // build CRC16 lookup table

{

    register unsigned int i;

    register unsigned int j;

    unsigned short crc_tbl[16];

    unsigned int v0, v1, v2, v3;

    for (i = 0; i < 16; i++) {

        v0 = i & 1;

        v1 = (i >> 1) & 1;

        v2 = (i >> 2) & 1;

        v3 = (i >> 3) & 1;

        j = 0;

#undef SET_BIT

#define SET_BIT(x, b, v) (x) |= (v) << (b)

        SET_BIT(j,  0, v0);

        SET_BIT(j,  7, v0);

        SET_BIT(j, 12, v0);

        SET_BIT(j,  1, v1);

        SET_BIT(j,  8, v1);

        SET_BIT(j, 13, v1);

        SET_BIT(j,  2, v2);

        SET_BIT(j,  9, v2);

        SET_BIT(j, 14, v2);

        SET_BIT(j,  3, v3);

        SET_BIT(j, 10, v3);

        SET_BIT(j, 15, v3);

        crc_tbl[i] = j;

    }

    printf("static const quint16 crc_tbl[16] = {\n");

    for (int i = 0; i < 16; i +=4)

        printf("    0x%04x, 0x%04x, 0x%04x, 0x%04x,\n", crc_tbl[i], crc_tbl[i+1], crc_tbl[i+2], crc_tbl[i+3]);

    printf("};\n");

}

#endif

static const quint16 crc_tbl[16] = {

    0x0000, 0x1081, 0x2102, 0x3183,

    0x4204, 0x5285, 0x6306, 0x7387,

    0x8408, 0x9489, 0xa50a, 0xb58b,

    0xc60c, 0xd68d, 0xe70e, 0xf78f

};

/*! 

    \relates QByteArray

    Returns the CRC-16 checksum of the first \a len bytes of \a data.

    The checksum is independent of the byte order (endianness).

    \note This function is a 16-bit cache conserving (16 entry table)

    implementation of the CRC-16-CCITT algorithm.

*/

quint16 qChecksum(const char *data, uint len)

{

    register quint16 crc = 0xffff;

    uchar c;

    const uchar *p = reinterpret_cast<const uchar *>(data);

    while (len--) {

        c = *p++;

        crc = ((crc >> 4) & 0x0fff) ^ crc_tbl[((crc ^ c) & 15)];

        c >>= 4;

        crc = ((crc >> 4) & 0x0fff) ^ crc_tbl[((crc ^ c) & 15)];

    }

    return ~crc & 0xffff;

}

/*!     

    \fn QByteArray qCompress(const QByteArray& data, int compressionLevel)

    \relates QByteArray

    Compresses the \a data byte array and returns the compressed data

    in a new byte array.

    The \a compressionLevel parameter specifies how much compression

    should be used. Valid values are between 0 and 9, with 9

    corresponding to the greatest compression (i.e. smaller compressed

    data) at the cost of using a slower algorithm. Smaller values (8,

    7, ..., 1) provide successively less compression at slightly

    faster speeds. The value 0 corresponds to no compression at all.

    The default value is -1, which specifies zlib's default

    compression.

    \sa qUncompress()

*/

/*! \relates QByteArray

    \overload

    Compresses the first \a nbytes of \a data and returns the

    compressed data in a new byte array.

*/

#ifndef QT_NO_COMPRESS

QByteArray qCompress(const uchar* data, int nbytes, int compressionLevel)

{

    if (nbytes == 0) {

        return QByteArray(4, '\0');

    }

    if (!data) {

        qWarning("qCompress: Data is null");

        return QByteArray();

    }

    if (compressionLevel < -1 || compressionLevel > 9)

        compressionLevel = -1;

    ulong len = nbytes + nbytes / 100 + 13;

    QByteArray bazip;

    int res;

    do {

        bazip.resize(len + 4);

        res = ::compress2((uchar*)bazip.data()+4, &len, (uchar*)data, nbytes, compressionLevel);

        switch (res) {

        case Z_OK:

            bazip.resize(len + 4);

            bazip[0] = (nbytes & 0xff000000) >> 24;

            bazip[1] = (nbytes & 0x00ff0000) >> 16;

            bazip[2] = (nbytes & 0x0000ff00) >> 8;

            bazip[3] = (nbytes & 0x000000ff);

            break;

        case Z_MEM_ERROR:

            qWarning("qCompress: Z_MEM_ERROR: Not enough memory");

            bazip.resize(0);

            break;

        case Z_BUF_ERROR:

            len *= 2;

            break;

        }

    } while (res == Z_BUF_ERROR);

    return bazip;

}

#endif

/*!

    \fn QByteArray qUncompress(const QByteArray& data)

    \relates QByteArray

    Uncompresses the \a data byte array and returns a new byte array

    with the uncompressed data.

    Returns an empty QByteArray if the input data was corrupt.

    This function will uncompress data compressed with qCompress()

    from this and any earlier Qt version, back to Qt 3.1 when this

    feature was added.

    \bold{Note:} If you want to use this function to uncompress external

    data compressed using zlib, you first need to prepend four bytes to the

    byte array that contain the expected length (as an unsigned integer)

    of the uncompressed data encoded in big-endian order (most significant

    byte first).

    \sa qCompress()

*/

/*! \relates QByteArray

    \overload

    Uncompresses the first \a nbytes of \a data and returns a new byte

    array with the uncompressed data.

*/

#ifndef QT_NO_COMPRESS

QByteArray qUncompress(const uchar* data, int nbytes)

{

    if (!data) {

        qWarning("qUncompress: Data is null");