/******************************************************************************** Copyright (C) 1992-2006 Trolltech ASA. All rights reserved.**** This file is part of the QtCore module of the Qt Toolkit.**** This file may be used under the terms of the GNU General Public** License version 2.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 GNU** General Public Licensing requirements will be met:** http://www.trolltech.com/products/qt/opensource.html**** If you are unsure which license is appropriate for your use, please** review the following information:** http://www.trolltech.com/products/qt/licensing.html or contact the** sales department at sales@trolltech.com.**** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.******************************************************************************/#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"#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>int qAllocMore(int alloc, int extra){    const int page = 1<<12;    int nalloc;    alloc += extra;    if (alloc < 1<<6) {        nalloc = (1<<3) + ((alloc >>3) << 3);    } else  {        nalloc = (alloc < page) ? 1<<3 : page;        while (nalloc < alloc)            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 a random non-zero value if \a str1 is 0    or \a str2 is 0 (but not both).    \sa qstrncmp(), qstricmp(), qstrnicmp(), {Note on 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(),        {Note on 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(),        {Note on 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 = QUnicodeTables::lower(*s1)) - QUnicodeTables::lower(*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(),        {Note on 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 = QUnicodeTables::lower(*s1)) - QUnicodeTables::lower(*s2)))            return res;        if (!c)                                // strings are equal            break;    }    return 0;}// the CRC table below is created by the following piece of code#if 0static 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");}#endifstatic 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).*/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_COMPRESSQByteArray 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 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_COMPRESSQByteArray qUncompress(const uchar* data, int nbytes){    if (!data) {        qWarning("qUncompress: Data is null");        return QByteArray();    }    if (nbytes <= 4) {        if (nbytes < 4 || (data[0]!=0 || data[1]!=0 || data[2]!=0 || data[3]!=0))            qWarning("qUncompress: Input data is corrupted");        return QByteArray();    }    ulong expectedSize = (data[0] << 24) | (data[1] << 16) |                       (data[2] <<  8) | (data[3]      );    ulong len = qMax(expectedSize, 1ul);    QByteArray baunzip;    int res;    do {        baunzip.resize(len);        res = ::uncompress((uchar*)baunzip.data(), &len,                            (uchar*)data+4, nbytes-4);        switch (res) {        case Z_OK:            if ((int)len != baunzip.size())                baunzip.resize(len);            break;        case Z_MEM_ERROR:            qWarning("qUncompress: Z_MEM_ERROR: Not enough memory");            break;        case Z_BUF_ERROR:            len *= 2;            break;        case Z_DATA_ERROR:            qWarning("qUncompress: Z_DATA_ERROR: Input data is corrupted");            break;