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 <limits>
 
#include <string.h>
 
QT_BEGIN_NAMESPACE
 
#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
#endif
 
/*
 * 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(); }
 */
 
static constexpr qsizetype storage_size(qsizetype size)
{
    // avoid overflow when adding 7, by doing the arithmetic in unsigned space:
    return qsizetype((size_t(size) + 7) / 8);
}
 
static constexpr qsizetype allocation_size(qsizetype size)
{
    return size <= 0 ? 0 : storage_size(size) + 1;
}
 
static void adjust_head_and_tail(char *data, qsizetype storageSize, qsizetype logicalSize)
{
    quint8 *c = reinterpret_cast<quint8 *>(data);
    // store the difference between storage and logical size in d[0]:
    *c = quint8(size_t(storageSize) * 8 - logicalSize);
    // reset unallocated bits to 0:
    if (logicalSize & 7)
        *(c + 1 + logicalSize / 8) &= (1 << (logicalSize & 7)) - 1;
}
 
QBitArray::QBitArray(qsizetype size, bool value)
    : d(allocation_size(size), value ? 0xFF : 0x00)
{
    Q_ASSERT_X(size >= 0, "QBitArray::QBitArray", "Size must be greater than or equal to 0.");
    if (size <= 0)
        return;
 
    adjust_head_and_tail(d.data(), d.size(), size);
}
 
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)
{
    Q_ASSERT_X(size >= 0, "QBitArray::resize", "Size must be greater than or equal to 0.");
    if (size <= 0) {
        d.resize(0);
    } else {
        d.resize(allocation_size(size), 0x00);
        adjust_head_and_tail(d.data(), d.size(), 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)
{
    Q_ASSERT_X(size >= 0, "QBitArray::fromBits", "Size must be greater than or equal to 0.");
    QBitArray result;
    if (size <= 0)
        return result;
 
    auto &d = result.d;
    d.resize(allocation_size(size));
    memcpy(d.data() + 1, data, d.size() - 1);
    adjust_head_and_tail(d.data(), d.size(), 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;
}
 
#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
#endif // Qt 6
 
// Returns a new QBitArray that has the same size as the bigger of \a a1 and
// \a a2, but whose contents are uninitialized.
static QBitArray sizedForOverwrite(const QBitArray &a1, const QBitArray &a2)
{
    QBitArray result;
    const QByteArrayData &d1 = a1.data_ptr();
    const QByteArrayData &d2 = a2.data_ptr();
    qsizetype n1 = d1.size;
    qsizetype n2 = d2.size;
    qsizetype n = qMax(n1, n2);
 
    QByteArrayData bytes(n, n);
 
    // initialize the count of bits in the last byte (see construction note)
    if (n1 > n2)
        *bytes.ptr = *d1.ptr;
    else if (n2 > n1)
        *bytes.ptr = *d2.ptr;
    else if (n1)        // n1 == n2
        *bytes.ptr = qMin(*d1.ptr, *d2.ptr);
 
    result.data_ptr() = std::move(bytes);
    return result;
}
 
template <typename BitwiseOp> static Q_NEVER_INLINE
QBitArray &performBitwiseOperationHelper(QBitArray &out, const QBitArray &a1,
                                         const QBitArray &a2, BitwiseOp op)
{
    const QByteArrayData &d1 = a1.data_ptr();
    const QByteArrayData &d2 = a2.data_ptr();
 
    // Sizes in bytes (including the initial bit difference counter)
    qsizetype n1 = d1.size;
    qsizetype n2 = d2.size;
    Q_ASSERT(out.data_ptr().size == qMax(n1, n2));
    Q_ASSERT(out.data_ptr().size == 0 || !out.data_ptr().needsDetach());
 
    // Bypass QByteArray's emptiness verification; we won't dereference
    // these pointers if their size is zero.
    auto dst = reinterpret_cast<uchar *>(out.data_ptr().data());
    auto p1 = reinterpret_cast<const uchar *>(d1.data());
    auto p2 = reinterpret_cast<const uchar *>(d2.data());
 
    // Main: perform the operation in the range where both arrays have data
    if (n1 < n2) {
        std::swap(n1, n2);
        std::swap(p1, p2);
    }
    for (qsizetype i = 1; i < n2; ++i)
        dst[i] = op(p1[i], p2[i]);
 
    // Tail: operate as if both arrays had the same data by padding zeroes to
    // the end of the shorter of the two (for std::bit_or and std::bit_xor, this is
    // a memmove; for std::bit_and, it's memset to 0).
    for (qsizetype i = qMax(n2, qsizetype(1)); i < n1; ++i)
        dst[i] = op(p1[i], uchar(0));
 
    return out;
}
 
template <typename BitwiseOp> static Q_NEVER_INLINE
QBitArray &performBitwiseOperationInCopy(QBitArray &self, const QBitArray &other, BitwiseOp op)
{
    QBitArray tmp(std::move(self));
    self = sizedForOverwrite(tmp, other);
    return performBitwiseOperationHelper(self, tmp, other, op);
}
 
template <typename BitwiseOp> static Q_NEVER_INLINE
QBitArray &performBitwiseOperationInPlace(QBitArray &self, const QBitArray &other, BitwiseOp op)
{
    if (self.size() < other.size())
        self.resize(other.size());
    return performBitwiseOperationHelper(self, self, other, op);
}
 
template <typename BitwiseOp> static
QBitArray &performBitwiseOperation(QBitArray &self, const QBitArray &other, BitwiseOp op)
{
    if (self.data_ptr().needsDetach())
        return performBitwiseOperationInCopy(self, other, op);
    return performBitwiseOperationInPlace(self, other, op);
}
 
// SCARY helper
enum { InCopy, InPlace };
static auto prepareForBitwiseOperation(QBitArray &self, QBitArray &other)
{
    QByteArrayData &d1 = self.data_ptr();
    QByteArrayData &d2 = other.data_ptr();
    bool detached1 = !d1.needsDetach();
    bool detached2 = !d2.needsDetach();
    if (!detached1 && !detached2)
        return InCopy;
 
    // at least one of the two is detached, we'll reuse its buffer
    bool swap = false;
    if (detached1 && detached2) {
        // both are detached, so choose the larger of the two
        swap = d1.allocatedCapacity() < d2.allocatedCapacity();
    } else if (detached2) {
        // we can re-use other's buffer but not self's, so swap the two
        swap = true;
    }
    if (swap)
        self.swap(other);
    return InPlace;
}
 
template <typename BitwiseOp> static
QBitArray &performBitwiseOperation(QBitArray &self, QBitArray &other, BitwiseOp op)
{
    auto choice = prepareForBitwiseOperation(self, other);
    if (choice == InCopy)
        return performBitwiseOperationInCopy(self, other, std::move(op));
    return performBitwiseOperationInPlace(self, other, std::move(op));
}
 
QBitArray &QBitArray::operator&=(QBitArray &&other)
{
    return performBitwiseOperation(*this, other, std::bit_and<uchar>());
}
 
QBitArray &QBitArray::operator&=(const QBitArray &other)
{
    return performBitwiseOperation(*this, other, std::bit_and<uchar>());
}
 
QBitArray &QBitArray::operator|=(QBitArray &&other)
{
    return performBitwiseOperation(*this, other, std::bit_or<uchar>());
}
 
QBitArray &QBitArray::operator|=(const QBitArray &other)
{
    return performBitwiseOperation(*this, other, std::bit_or<uchar>());
}
 
QBitArray &QBitArray::operator^=(QBitArray &&other)
{
    return performBitwiseOperation(*this, other, std::bit_xor<uchar>());
}
 
QBitArray &QBitArray::operator^=(const QBitArray &other)
{
    return performBitwiseOperation(*this, other, std::bit_xor<uchar>());
}
 
Q_NEVER_INLINE QBitArray QBitArray::inverted_inplace() &&
{
    qsizetype n = d.size();
    uchar *dst = reinterpret_cast<uchar *>(data_ptr().data());
    const uchar *src = dst;
    QBitArray result([&] {
        if (d.isDetached() || n == 0)
            return std::move(d.data_ptr());     // invert in-place
 
        QByteArrayData tmp(n, n);
        dst = reinterpret_cast<uchar *>(tmp.data());
        return tmp;
    }());
 
    uchar bitdiff = 8;
    if (n)
        bitdiff = dst[0] = src[0];      // copy the count of bits in the last byte
 
    for (qsizetype i = 1; i < n; ++i)
        dst[i] = ~src[i];
 
    if (int tailCount = 16 - bitdiff; tailCount != 8) {
        // zero the bits beyond our size in the last byte
        Q_ASSERT(n > 1);
        uchar tailMask = (1U << tailCount) - 1;
        dst[n - 1] &= tailMask;
    }
 
    return result;
}
 
QBitArray operator&(const QBitArray &a1, const QBitArray &a2)
{
    QBitArray tmp = sizedForOverwrite(a1, a2);
    performBitwiseOperationHelper(tmp, a1, a2, std::bit_and<uchar>());
    return tmp;
}
 
QBitArray operator|(const QBitArray &a1, const QBitArray &a2)
{
    QBitArray tmp = sizedForOverwrite(a1, a2);
    performBitwiseOperationHelper(tmp, a1, a2, std::bit_or<uchar>());
    return tmp;
}
 
QBitArray operator^(const QBitArray &a1, const QBitArray &a2)
{
    QBitArray tmp = sizedForOverwrite(a1, a2);
    performBitwiseOperationHelper(tmp, a1, a2, std::bit_xor<uchar>());
    return tmp;
}
 
/*****************************************************************************
  QBitArray stream functions
 *****************************************************************************/
 
#ifndef QT_NO_DATASTREAM
QDataStream &operator<<(QDataStream &out, const QBitArray &ba)
{
    const qsizetype len = ba.size();
    if (out.version() < QDataStream::Qt_6_0) {
        if (Q_UNLIKELY(len > qsizetype{(std::numeric_limits<qint32>::max)()})) {
            out.setStatus(QDataStream::Status::SizeLimitExceeded);
            return out;
        }
        out << quint32(len);
    } else {
        out << quint64(len);
    }
    if (len > 0)
        out.writeRawData(ba.d.data() + 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;
        if (Q_UNLIKELY(tmp > quint32((std::numeric_limits<qint32>::max)()))) {
            in.setStatus(QDataStream::ReadCorruptData);
            return in;
        }
        len = tmp;
    } else {
        quint64 tmp;
        in >> tmp;
        if (Q_UNLIKELY(tmp > quint64((std::numeric_limits<qsizetype>::max)()))) {
            in.setStatus(QDataStream::Status::SizeLimitExceeded);
            return in;
        }
        len = tmp;
    }
    if (len == 0) {
        ba.clear();
        return in;
    }
 
    const qsizetype Step = 8 * 1024 * 1024;
    const qsizetype totalBytes = storage_size(len);
    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;
    }
 
    const auto fromStream = ba.d.back();
    adjust_head_and_tail(ba.d.data(), ba.d.size(), len);
    if (ba.d.back() != fromStream) {
        ba.clear();
        in.setStatus(QDataStream::ReadCorruptData);
        return in;
    }
    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