src/corelib/tools/qbitarray.cpp

Go to the documentation of this file.

/****************************************************************************
**
** 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 "qbitarray.h"
#include <qdatastream.h>
#include <qdebug.h>
#include <string.h>

QBitArray::QBitArray(int size, bool value)
{
    if (!size) {
        d.resize(0);
        return;
    }
    d.resize(1 + (size+7)/8);
    uchar* c = reinterpret_cast<uchar*>(d.data());
    memset(c, value ? 0xff : 0, d.size());
    *c = d.size()*8 - size;
    if (value && size && size % 8)
        *(c+1+size/8) &= (1 << (size%8)) - 1;
}

int QBitArray::count(bool on) const
{
    int numBits = 0;
    int len = size();
#if 0
    for (int i = 0; i < len; ++i)
        numBits += testBit(i);
#else
    // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    const quint8 *bits = reinterpret_cast<const quint8 *>(d.data()) + 1;
    while (len >= 32) {
        quint32 v = quint32(bits[0]) | (quint32(bits[1]) << 8) | (quint32(bits[2]) << 16) | (quint32(bits[3]) << 24);
        quint32 c = ((v & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
        c += (((v & 0xfff000) >> 12) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
        c += ((v >> 24) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
        len -= 32;
        bits += 4;
        numBits += int(c);
    }
    while (len >= 24) {
        quint32 v = quint32(bits[0]) | (quint32(bits[1]) << 8) | (quint32(bits[2]) << 16);
        quint32 c =  ((v & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
        c += (((v & 0xfff000) >> 12) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;    
        len -= 24;
        bits += 3;
        numBits += int(c);
    }
    while (len >= 0) {
        if (bits[len / 8] & (1 << ((len - 1) & 7)))
            ++numBits;
        --len;
    }
#endif
    return on ? numBits : size() - numBits;
}

void QBitArray::resize(int size)
{
    if (!size) {
        d.resize(0);
    } else {
        int s = d.size();
        d.resize(1 + (size+7)/8);
        uchar* c = reinterpret_cast<uchar*>(d.data());
        if (size > (s << 3))
            memset(c + s, 0, d.size() - s);
        *c = d.size()*8 - size;
    }
}

void QBitArray::fill(bool value, int begin, int end)
{
    while (begin < end && begin & 0x7)
        setBit(begin++, value);
    int len = end - begin;
    if (len <= 0)
        return;
    int s = len & ~0x7;
    uchar *c = reinterpret_cast<uchar*>(d.data());
    memset(c + (begin >> 3) + 1, value ? 0xff : 0, s >> 3);
    begin += s;
    while (begin < end)
        setBit(begin++, value);
}

QBitArray &QBitArray::operator&=(const QBitArray &other)
{
    resize(qMax(size(), other.size()));
    uchar *a1 = reinterpret_cast<uchar*>(d.data()) + 1;
    const uchar *a2 = reinterpret_cast<const uchar*>(other.d.constData()) + 1;
    int n = other.d.size() -1 ; 
    int p = d.size() - 1 - n;
    while (n-- > 0)
        *a1++ &= *a2++;
    while (p-- > 0)
        *a1++ = 0;
    return *this;
}

QBitArray &QBitArray::operator|=(const QBitArray &other)
{
    resize(qMax(size(), other.size()));
    uchar *a1 = reinterpret_cast<uchar*>(d.data()) + 1;
    const uchar *a2 = reinterpret_cast<const uchar *>(other.d.constData()) + 1;
    int n = other.d.size() - 1;   
    while (n-- > 0)
        *a1++ |= *a2++;
    return *this;
}

QBitArray &QBitArray::operator^=(const QBitArray &other)
{
    resize(qMax(size(), other.size()));
    uchar *a1 = reinterpret_cast<uchar*>(d.data()) + 1;
    const uchar *a2 = reinterpret_cast<const uchar *>(other.d.constData()) + 1;
    int n = other.d.size() - 1;
    while (n-- > 0)
        *a1++ ^= *a2++;
    return *this;
}

QBitArray QBitArray::operator~() const
{
    int sz = size();
    QBitArray a(sz);
    const uchar *a1 = reinterpret_cast<const uchar *>(d.constData()) + 1;
    uchar *a2 = reinterpret_cast<uchar*>(a.d.data()) + 1;
    int n = d.size() - 1;
    while (n--)
        *a2++ = ~*a1++;
     if (sz && sz%8)
         *(a2-1) &= (1 << (sz%8)) - 1;
    return a;
}

QBitArray operator&(const QBitArray &a1, const QBitArray &a2)
{
    QBitArray tmp = a1;
    tmp &= a2;
    return tmp;
}

QBitArray operator|(const QBitArray &a1, const QBitArray &a2)
{
    QBitArray tmp = a1;
    tmp |= a2;
    return tmp;
}

QBitArray operator^(const QBitArray &a1, const QBitArray &a2)
{
    QBitArray tmp = a1;
    tmp ^= a2;
    return tmp;
}

/*****************************************************************************
  QBitArray stream functions
 *****************************************************************************/

#ifndef QT_NO_DATASTREAM
QDataStream &operator<<(QDataStream &out, const QBitArray &ba)
{
    quint32 len = ba.size();
    out << len;
    if (len > 0)
        out.writeRawData(ba.d.constData() + 1, ba.d.size() - 1);
    return out;
}

QDataStream &operator>>(QDataStream &in, QBitArray &ba)
{
    ba.clear();
    quint32 len;
    in >> len;
    if (len == 0) {
  ba.clear();
  return in;
    }

    const quint32 Step = 8 * 1024 * 1024;
    quint32 totalBytes = (len + 7) / 8;
    quint32 allocated = 0;

    while (allocated < totalBytes) {
        int blockSize = qMin(Step, totalBytes - allocated);
        ba.d.resize(allocated + blockSize + 1);
        if (in.readRawData(ba.d.data() + 1 + allocated, blockSize) != blockSize) {
            ba.clear();
            in.setStatus(QDataStream::ReadPastEnd);
            return in;
        }
        allocated += blockSize;
    }

    int paddingMask = ~((0x1 << (len & 0x7)) - 1);
    if (paddingMask != ~0x0 && (ba.d.constData()[ba.d.size() - 1] & paddingMask)) {
        ba.clear();
        in.setStatus(QDataStream::ReadCorruptData);
        return in;
    }

    *ba.d.data() = ba.d.size() * 8 - len;
    return in;
}
#endif

---