qbitarray.cpp

Go to the documentation of this file.

// Copyright (C) 2020 The Qt Company Ltd.
// Copyright (C) 2019 Intel Corporation.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#include "qbitarray.h"
#include <qalgorithms.h>
#include <qdatastream.h>
#include <qdebug.h>
#include <qendian.h>
#include <string.h>
 
QT_BEGIN_NAMESPACE
 
/*
 * QBitArray construction note:
 *
 * We overallocate the byte array by 1 byte. The first user bit is at
 * d.data()[1]. On the extra first byte, we store the difference between the
 * number of bits in the byte array (including this byte) and the number of
 * bits in the bit array. Therefore, for a non-empty QBitArray, it's always a
 * number between 8 and 15. For the empty one, d is the an empty QByteArray and
 * *d.constData() is the QByteArray's terminating NUL (0) byte.
 *
 * This allows for fast calculation of the bit array size:
 *    inline qsizetype size() const { return (d.size() << 3) - *d.constData(); }
 */
 
QBitArray::QBitArray(qsizetype size, bool value)
    : d(size <= 0 ? 0 : 1 + (size + 7) / 8, Qt::Uninitialized)
{
    Q_ASSERT_X(size >= 0, "QBitArray::QBitArray", "Size must be greater than or equal to 0.");
    if (size <= 0)
        return;
 
    uchar *c = reinterpret_cast<uchar *>(d.data());
    memset(c + 1, value ? 0xff : 0, d.size() - 1);
    *c = d.size() * 8 - size;
    if (value && size && size & 7)
        *(c + 1 + size / 8) &= (1 << (size & 7)) - 1;
}
 
qsizetype QBitArray::count(bool on) const
{
    qsizetype numBits = 0;
    const quint8 *bits = reinterpret_cast<const quint8 *>(d.data()) + 1;
 
    // the loops below will try to read from *end
    // it's the QByteArray implicit NUL, so it will not change the bit count
    const quint8 *const end = reinterpret_cast<const quint8 *>(d.end());
 
    while (bits + 7 <= end) {
        quint64 v = qFromUnaligned<quint64>(bits);
        bits += 8;
        numBits += qsizetype(qPopulationCount(v));
    }
    if (bits + 3 <= end) {
        quint32 v = qFromUnaligned<quint32>(bits);
        bits += 4;
        numBits += qsizetype(qPopulationCount(v));
    }
    if (bits + 1 < end) {
        quint16 v = qFromUnaligned<quint16>(bits);
        bits += 2;
        numBits += qsizetype(qPopulationCount(v));
    }
    if (bits < end)
        numBits += qsizetype(qPopulationCount(bits[0]));
 
    return on ? numBits : size() - numBits;
}
 
void QBitArray::resize(qsizetype size)
{
    if (!size) {
        d.resize(0);
    } else {
        qsizetype 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);
        else if (size & 7)
            *(c + 1 + size / 8) &= (1 << (size & 7)) - 1;
        *c = d.size() * 8 - size;
    }
}
 
void QBitArray::fill(bool value, qsizetype begin, qsizetype end)
{
    while (begin < end && begin & 0x7)
        setBit(begin++, value);
    qsizetype len = end - begin;
    if (len <= 0)
        return;
    qsizetype s = len & ~qsizetype(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::fromBits(const char *data, qsizetype size)
{
    QBitArray result;
    if (size == 0)
        return result;
    qsizetype nbytes = (size + 7) / 8;
 
    result.d = QByteArray(nbytes + 1, Qt::Uninitialized);
    char *bits = result.d.data();
    memcpy(bits + 1, data, nbytes);
 
    // clear any unused bits from the last byte
    if (size & 7)
        bits[nbytes] &= 0xffU >> (8 - (size & 7));
 
    *bits = result.d.size() * 8 - size;
    return result;
}
 
quint32 QBitArray::toUInt32(QSysInfo::Endian endianness, bool *ok) const noexcept
{
    const qsizetype _size = size();
    if (_size > 32) {
        if (ok)
            *ok = false;
        return 0;
    }
 
    if (ok)
        *ok = true;
 
    quint32 factor = 1;
    quint32 total = 0;
    for (qsizetype i = 0; i < _size; ++i, factor *= 2) {
        const auto index = endianness == QSysInfo::Endian::LittleEndian ? i : (_size - i - 1);
        if (testBit(index))
            total += factor;
    }
 
    return total;
}
 
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;
    qsizetype n = other.d.size() - 1;
    qsizetype 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;
    qsizetype 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;
    qsizetype n = other.d.size() - 1;
    while (n-- > 0)
        *a1++ ^= *a2++;
    return *this;
}
 
QBitArray QBitArray::operator~() const
{
    qsizetype sz = size();
    QBitArray a(sz);
    const uchar *a1 = reinterpret_cast<const uchar *>(d.constData()) + 1;
    uchar *a2 = reinterpret_cast<uchar *>(a.d.data()) + 1;
    qsizetype n = d.size() - 1;
 
    while (n-- > 0)
        *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)
{
    if (out.version() < QDataStream::Qt_6_0) {
        quint32 len = ba.size();
        out << len;
        if (len > 0)
            out.writeRawData(ba.d.constData() + 1, ba.d.size() - 1);
        return out;
    } else {
        quint64 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();
    qsizetype len;
    if (in.version() < QDataStream::Qt_6_0) {
        quint32 tmp;
        in >> tmp;
        len = tmp;
    } else {
        quint64 tmp;
        in >> tmp;
        len = tmp;
    }
    if (len == 0) {
        ba.clear();
        return in;
    }
 
    const qsizetype Step = 8 * 1024 * 1024;
    qsizetype totalBytes = (len + 7) / 8;
    qsizetype allocated = 0;
 
    while (allocated < totalBytes) {
        qsizetype 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;
    }
 
    qsizetype 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 // QT_NO_DATASTREAM
 
#ifndef QT_NO_DEBUG_STREAM
QDebug operator<<(QDebug dbg, const QBitArray &array)
{
    QDebugStateSaver saver(dbg);
    dbg.nospace() << "QBitArray(";
    for (qsizetype i = 0; i < array.size();) {
        if (array.testBit(i))
            dbg << '1';
        else
            dbg << '0';
        i += 1;
        if (!(i % 4) && (i < array.size()))
            dbg << ' ';
    }
    dbg << ')';
    return dbg;
}
#endif
 
QT_END_NAMESPACE