1// Copyright (C) 2020 The Qt Company Ltd.
2// Copyright (C) 2019 Intel Corporation.
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
4
5#include "qbitarray.h"
6#include <qalgorithms.h>
7#include <qdatastream.h>
8#include <qdebug.h>
9#include <qendian.h>
10
11#include <limits>
12
13#include <string.h>
14
15QT_BEGIN_NAMESPACE
16
17/*!
18 \class QBitArray
19 \inmodule QtCore
20 \brief The QBitArray class provides an array of bits.
21
22 \ingroup tools
23 \ingroup shared
24 \reentrant
25
26 \compares equality
27
28 A QBitArray is an array that gives access to individual bits and
29 provides operators (\l{operator&()}{AND}, \l{operator|()}{OR},
30 \l{operator^()}{XOR}, and \l{operator~()}{NOT}) that work on
31 entire arrays of bits. It uses \l{implicit sharing} (copy-on-write)
32 to reduce memory usage and to avoid the needless copying of data.
33
34 The following code constructs a QBitArray containing 200 bits
35 initialized to false (0):
36
37 \snippet code/src_corelib_tools_qbitarray.cpp 0
38
39 To initialize the bits to true, either pass \c true as second
40 argument to the constructor, or call fill() later on.
41
42 QBitArray uses 0-based indexes, just like C++ arrays. To access
43 the bit at a particular index position, you can use operator[]().
44 On non-const bit arrays, operator[]() returns a reference to a
45 bit that can be used on the left side of an assignment. For
46 example:
47
48 \snippet code/src_corelib_tools_qbitarray.cpp 1
49
50 For technical reasons, it is more efficient to use testBit() and
51 setBit() to access bits in the array than operator[](). For
52 example:
53
54 \snippet code/src_corelib_tools_qbitarray.cpp 2
55
56 QBitArray supports \c{&} (\l{operator&()}{AND}), \c{|}
57 (\l{operator|()}{OR}), \c{^} (\l{operator^()}{XOR}),
58 \c{~} (\l{operator~()}{NOT}), as well as
59 \c{&=}, \c{|=}, and \c{^=}. These operators work in the same way
60 as the built-in C++ bitwise operators of the same name. For
61 example:
62
63 \snippet code/src_corelib_tools_qbitarray.cpp 3
64
65 For historical reasons, QBitArray distinguishes between a null
66 bit array and an empty bit array. A \e null bit array is a bit
67 array that is initialized using QBitArray's default constructor.
68 An \e empty bit array is any bit array with size 0. A null bit
69 array is always empty, but an empty bit array isn't necessarily
70 null:
71
72 \snippet code/src_corelib_tools_qbitarray.cpp 4
73
74 All functions except isNull() treat null bit arrays the same as
75 empty bit arrays; for example, QBitArray() compares equal to
76 QBitArray(0). We recommend that you always use isEmpty() and
77 avoid isNull().
78
79 \sa QByteArray, QList
80*/
81
82#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
83/*!
84 \fn QBitArray::QBitArray(QBitArray &&other)
85
86 Move-constructs a QBitArray instance, making it point at the same
87 object that \a other was pointing to.
88
89 \since 5.2
90*/
91#endif
92
93/*! \fn QBitArray::QBitArray()
94
95 Constructs an empty bit array.
96
97 \sa isEmpty()
98*/
99
100/*
101 * QBitArray construction note:
102 *
103 * We overallocate the byte array by 1 byte. The first user bit is at
104 * d.data()[1]. On the extra first byte, we store the difference between the
105 * number of bits in the byte array (including this byte) and the number of
106 * bits in the bit array. Therefore, for a non-empty QBitArray, it's always a
107 * number between 8 and 15. For the empty one, d is the an empty QByteArray and
108 * *d.constData() is the QByteArray's terminating NUL (0) byte.
109 *
110 * This allows for fast calculation of the bit array size:
111 * inline qsizetype size() const { return (d.size() << 3) - *d.constData(); }
112 */
113
114static constexpr qsizetype storage_size(qsizetype size)
115{
116 // avoid overflow when adding 7, by doing the arithmetic in unsigned space:
117 return qsizetype((size_t(size) + 7) / 8);
118}
119
120static constexpr qsizetype allocation_size(qsizetype size)
121{
122 return size <= 0 ? 0 : storage_size(size) + 1;
123}
124
125static void adjust_head_and_tail(char *data, qsizetype storageSize, qsizetype logicalSize)
126{
127 quint8 *c = reinterpret_cast<quint8 *>(data);
128 // store the difference between storage and logical size in d[0]:
129 *c = quint8(size_t(storageSize) * 8 - logicalSize);
130 // reset unallocated bits to 0:
131 if (logicalSize & 7)
132 *(c + 1 + logicalSize / 8) &= (1 << (logicalSize & 7)) - 1;
133}
134
135/*!
136 Constructs a bit array containing \a size bits. The bits are
137 initialized with \a value, which defaults to false (0).
138*/
139QBitArray::QBitArray(qsizetype size, bool value)
140 : d(allocation_size(size), value ? 0xFF : 0x00)
141{
142 Q_ASSERT_X(size >= 0, "QBitArray::QBitArray", "Size must be greater than or equal to 0.");
143 if (size <= 0)
144 return;
145
146 adjust_head_and_tail(data: d.data(), storageSize: d.size(), logicalSize: size);
147}
148
149/*! \fn qsizetype QBitArray::size() const
150
151 Returns the number of bits stored in the bit array.
152
153 \sa resize()
154*/
155
156/*! \fn qsizetype QBitArray::count() const
157
158 Same as size().
159*/
160
161/*!
162 If \a on is true, this function returns the number of
163 1-bits stored in the bit array; otherwise the number
164 of 0-bits is returned.
165*/
166qsizetype QBitArray::count(bool on) const
167{
168 qsizetype numBits = 0;
169 const quint8 *bits = reinterpret_cast<const quint8 *>(d.data()) + 1;
170
171 // the loops below will try to read from *end
172 // it's the QByteArray implicit NUL, so it will not change the bit count
173 const quint8 *const end = reinterpret_cast<const quint8 *>(d.end());
174
175 while (bits + 7 <= end) {
176 quint64 v = qFromUnaligned<quint64>(src: bits);
177 bits += 8;
178 numBits += qsizetype(qPopulationCount(v));
179 }
180 if (bits + 3 <= end) {
181 quint32 v = qFromUnaligned<quint32>(src: bits);
182 bits += 4;
183 numBits += qsizetype(qPopulationCount(v));
184 }
185 if (bits + 1 < end) {
186 quint16 v = qFromUnaligned<quint16>(src: bits);
187 bits += 2;
188 numBits += qsizetype(qPopulationCount(v));
189 }
190 if (bits < end)
191 numBits += qsizetype(qPopulationCount(v: bits[0]));
192
193 return on ? numBits : size() - numBits;
194}
195
196/*!
197 Resizes the bit array to \a size bits.
198
199 If \a size is greater than the current size, the bit array is
200 extended to make it \a size bits with the extra bits added to the
201 end. The new bits are initialized to false (0).
202
203 If \a size is less than the current size, bits are removed from
204 the end.
205
206 \sa size()
207*/
208void QBitArray::resize(qsizetype size)
209{
210 Q_ASSERT_X(size >= 0, "QBitArray::resize", "Size must be greater than or equal to 0.");
211 if (size <= 0) {
212 d.resize(size: 0);
213 } else {
214 d.resize(size: allocation_size(size), c: 0x00);
215 adjust_head_and_tail(data: d.data(), storageSize: d.size(), logicalSize: size);
216 }
217}
218
219/*! \fn bool QBitArray::isEmpty() const
220
221 Returns \c true if this bit array has size 0; otherwise returns
222 false.
223
224 \sa size()
225*/
226
227/*! \fn bool QBitArray::isNull() const
228
229 Returns \c true if this bit array is null; otherwise returns \c false.
230
231 Example:
232 \snippet code/src_corelib_tools_qbitarray.cpp 5
233
234 Qt makes a distinction between null bit arrays and empty bit
235 arrays for historical reasons. For most applications, what
236 matters is whether or not a bit array contains any data,
237 and this can be determined using isEmpty().
238
239 \sa isEmpty()
240*/
241
242/*! \fn bool QBitArray::fill(bool value, qsizetype size = -1)
243
244 Sets every bit in the bit array to \a value, returning true if successful;
245 otherwise returns \c false. If \a size is different from -1 (the default),
246 the bit array is resized to \a size beforehand.
247
248 Example:
249 \snippet code/src_corelib_tools_qbitarray.cpp 6
250
251 \sa resize()
252*/
253
254/*!
255 \overload
256
257 Sets bits at index positions \a begin up to (but not including) \a end
258 to \a value.
259
260 \a begin must be a valid index position in the bit array
261 (0 <= \a begin < size()).
262
263 \a end must be either a valid index position or equal to size(), in
264 which case the fill operation runs until the end of the array
265 (0 <= \a end <= size()).
266
267 Example:
268 \snippet code/src_corelib_tools_qbitarray.cpp 15
269*/
270
271void QBitArray::fill(bool value, qsizetype begin, qsizetype end)
272{
273 while (begin < end && begin & 0x7)
274 setBit(i: begin++, val: value);
275 qsizetype len = end - begin;
276 if (len <= 0)
277 return;
278 qsizetype s = len & ~qsizetype(0x7);
279 uchar *c = reinterpret_cast<uchar *>(d.data());
280 memset(s: c + (begin >> 3) + 1, c: value ? 0xff : 0, n: s >> 3);
281 begin += s;
282 while (begin < end)
283 setBit(i: begin++, val: value);
284}
285
286/*!
287 \fn const char *QBitArray::bits() const
288 \since 5.11
289
290 Returns a pointer to a dense bit array for this QBitArray. Bits are counted
291 upwards from the least significant bit in each byte. The number of bits
292 relevant in the last byte is given by \c{size() % 8}.
293
294 \sa fromBits(), size()
295 */
296
297/*!
298 \since 5.11
299
300 Creates a QBitArray with the dense bit array located at \a data, with \a
301 size bits. The byte array at \a data must be at least \a size / 8 (rounded up)
302 bytes long.
303
304 If \a size is not a multiple of 8, this function will include the lowest
305 \a size % 8 bits from the last byte in \a data.
306
307 \sa bits()
308 */
309QBitArray QBitArray::fromBits(const char *data, qsizetype size)
310{
311 Q_ASSERT_X(size >= 0, "QBitArray::fromBits", "Size must be greater than or equal to 0.");
312 QBitArray result;
313 if (size <= 0)
314 return result;
315
316 auto &d = result.d;
317 d.resize(size: allocation_size(size));
318 memcpy(dest: d.data() + 1, src: data, n: d.size() - 1);
319 adjust_head_and_tail(data: d.data(), storageSize: d.size(), logicalSize: size);
320 return result;
321}
322
323/*!
324 \since 6.0
325
326 Returns the array of bit converted to an int. The conversion is based on \a endianness.
327 Converts up to the first 32 bits of the array to \c quint32 and returns it,
328 obeying \a endianness. If \a ok is not a null pointer, and the array has more
329 than 32 bits, \a ok is set to false and this function returns zero; otherwise,
330 it's set to true.
331*/
332quint32 QBitArray::toUInt32(QSysInfo::Endian endianness, bool *ok) const noexcept
333{
334 const qsizetype _size = size();
335 if (_size > 32) {
336 if (ok)
337 *ok = false;
338 return 0;
339 }
340
341 if (ok)
342 *ok = true;
343
344 quint32 factor = 1;
345 quint32 total = 0;
346 for (qsizetype i = 0; i < _size; ++i, factor *= 2) {
347 const auto index = endianness == QSysInfo::Endian::LittleEndian ? i : (_size - i - 1);
348 if (testBit(i: index))
349 total += factor;
350 }
351
352 return total;
353}
354
355/*! \fn bool QBitArray::isDetached() const
356
357 \internal
358*/
359
360/*! \fn void QBitArray::detach()
361
362 \internal
363*/
364
365/*! \fn void QBitArray::clear()
366
367 Clears the contents of the bit array and makes it empty.
368
369 \sa resize(), isEmpty()
370*/
371
372/*! \fn void QBitArray::truncate(qsizetype pos)
373
374 Truncates the bit array at index position \a pos.
375
376 If \a pos is beyond the end of the array, nothing happens.
377
378 \sa resize()
379*/
380
381/*! \fn bool QBitArray::toggleBit(qsizetype i)
382
383 Inverts the value of the bit at index position \a i, returning the
384 previous value of that bit as either true (if it was set) or false (if
385 it was unset).
386
387 If the previous value was 0, the new value will be 1. If the
388 previous value was 1, the new value will be 0.
389
390 \a i must be a valid index position in the bit array (i.e., 0 <=
391 \a i < size()).
392
393 \sa setBit(), clearBit()
394*/
395
396/*! \fn bool QBitArray::testBit(qsizetype i) const
397
398 Returns \c true if the bit at index position \a i is 1; otherwise
399 returns \c false.
400
401 \a i must be a valid index position in the bit array (i.e., 0 <=
402 \a i < size()).
403
404 \sa setBit(), clearBit()
405*/
406
407/*! \fn bool QBitArray::setBit(qsizetype i)
408
409 Sets the bit at index position \a i to 1.
410
411 \a i must be a valid index position in the bit array (i.e., 0 <=
412 \a i < size()).
413
414 \sa clearBit(), toggleBit()
415*/
416
417/*! \fn void QBitArray::setBit(qsizetype i, bool value)
418
419 \overload
420
421 Sets the bit at index position \a i to \a value.
422*/
423
424/*! \fn void QBitArray::clearBit(qsizetype i)
425
426 Sets the bit at index position \a i to 0.
427
428 \a i must be a valid index position in the bit array (i.e., 0 <=
429 \a i < size()).
430
431 \sa setBit(), toggleBit()
432*/
433
434/*! \fn bool QBitArray::at(qsizetype i) const
435
436 Returns the value of the bit at index position \a i.
437
438 \a i must be a valid index position in the bit array (i.e., 0 <=
439 \a i < size()).
440
441 \sa operator[]()
442*/
443
444/*! \fn QBitRef QBitArray::operator[](qsizetype i)
445
446 Returns the bit at index position \a i as a modifiable reference.
447
448 \a i must be a valid index position in the bit array (i.e., 0 <=
449 \a i < size()).
450
451 Example:
452 \snippet code/src_corelib_tools_qbitarray.cpp 7
453
454 The return value is of type QBitRef, a helper class for QBitArray.
455 When you get an object of type QBitRef, you can assign to
456 it, and the assignment will apply to the bit in the QBitArray
457 from which you got the reference.
458
459 The functions testBit(), setBit(), and clearBit() are slightly
460 faster.
461
462 \sa at(), testBit(), setBit(), clearBit()
463*/
464
465/*! \fn bool QBitArray::operator[](qsizetype i) const
466
467 \overload
468*/
469
470#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
471/*! \fn QBitArray::QBitArray(const QBitArray &other) noexcept
472
473 Constructs a copy of \a other.
474
475 This operation takes \l{constant time}, because QBitArray is
476 \l{implicitly shared}. This makes returning a QBitArray from a
477 function very fast. If a shared instance is modified, it will be
478 copied (copy-on-write), and that takes \l{linear time}.
479
480 \sa operator=()
481*/
482
483/*! \fn QBitArray &QBitArray::operator=(const QBitArray &other) noexcept
484
485 Assigns \a other to this bit array and returns a reference to
486 this bit array.
487*/
488
489/*! \fn QBitArray &QBitArray::operator=(QBitArray &&other)
490 \since 5.2
491
492 Moves \a other to this bit array and returns a reference to
493 this bit array.
494*/
495#endif // Qt 6
496
497/*! \fn void QBitArray::swap(QBitArray &other)
498 \since 4.8
499 \memberswap{bit array}
500*/
501
502/*! \fn bool QBitArray::operator==(const QBitArray &lhs, const QBitArray &rhs)
503
504 Returns \c true if \a lhs is equal to \a rhs bit array; otherwise
505 returns \c false.
506
507 \sa operator!=()
508*/
509
510/*! \fn bool QBitArray::operator!=(const QBitArray &lhs, const QBitArray &rhs)
511
512 Returns \c true if \a lhs is not equal to \a rhs bit array;
513 otherwise returns \c false.
514
515 \sa operator==()
516*/
517
518// Returns a new QBitArray that has the same size as the bigger of \a a1 and
519// \a a2, but whose contents are uninitialized.
520static QBitArray sizedForOverwrite(const QBitArray &a1, const QBitArray &a2)
521{
522 QBitArray result;
523 const QByteArrayData &d1 = a1.data_ptr();
524 const QByteArrayData &d2 = a2.data_ptr();
525 qsizetype n1 = d1.size;
526 qsizetype n2 = d2.size;
527 qsizetype n = qMax(a: n1, b: n2);
528
529 QByteArrayData bytes(n, n);
530
531 // initialize the count of bits in the last byte (see construction note)
532 // and the QByteArray null termination (some of our algorithms read it)
533 if (n1 > n2) {
534 *bytes.ptr = *d1.ptr;
535 bytes.ptr[n1] = 0;
536 } else if (n2 > n1) {
537 *bytes.ptr = *d2.ptr;
538 bytes.ptr[n2] = 0;
539 } else if (n1) { // n1 == n2
540 *bytes.ptr = qMin(a: *d1.ptr, b: *d2.ptr);
541 bytes.ptr[n1] = 0;
542 }
543
544 result.data_ptr() = std::move(bytes);
545 return result;
546}
547
548template <typename BitwiseOp> Q_NEVER_INLINE static
549QBitArray &performBitwiseOperationHelper(QBitArray &out, const QBitArray &a1,
550 const QBitArray &a2, BitwiseOp op)
551{
552 const QByteArrayData &d1 = a1.data_ptr();
553 const QByteArrayData &d2 = a2.data_ptr();
554
555 // Sizes in bytes (including the initial bit difference counter)
556 qsizetype n1 = d1.size;
557 qsizetype n2 = d2.size;
558 Q_ASSERT(out.data_ptr().size == qMax(n1, n2));
559 Q_ASSERT(out.data_ptr().size == 0 || !out.data_ptr().needsDetach());
560
561 // Bypass QByteArray's emptiness verification; we won't dereference
562 // these pointers if their size is zero.
563 auto dst = reinterpret_cast<uchar *>(out.data_ptr().data());
564 auto p1 = reinterpret_cast<const uchar *>(d1.data());
565 auto p2 = reinterpret_cast<const uchar *>(d2.data());
566
567 // Main: perform the operation in the range where both arrays have data
568 if (n1 < n2) {
569 std::swap(a&: n1, b&: n2);
570 std::swap(a&: p1, b&: p2);
571 }
572 for (qsizetype i = 1; i < n2; ++i)
573 dst[i] = op(p1[i], p2[i]);
574
575 // Tail: operate as if both arrays had the same data by padding zeroes to
576 // the end of the shorter of the two (for std::bit_or and std::bit_xor, this is
577 // a memmove; for std::bit_and, it's memset to 0).
578 for (qsizetype i = qMax(a: n2, b: qsizetype(1)); i < n1; ++i)
579 dst[i] = op(p1[i], uchar(0));
580
581 return out;
582}
583
584template <typename BitwiseOp> Q_NEVER_INLINE static
585QBitArray &performBitwiseOperationInCopy(QBitArray &self, const QBitArray &other, BitwiseOp op)
586{
587 QBitArray tmp(std::move(self));
588 self = sizedForOverwrite(a1: tmp, a2: other);
589 return performBitwiseOperationHelper(self, tmp, other, op);
590}
591
592template <typename BitwiseOp> Q_NEVER_INLINE static
593QBitArray &performBitwiseOperationInPlace(QBitArray &self, const QBitArray &other, BitwiseOp op)
594{
595 if (self.size() < other.size())
596 self.resize(size: other.size());
597 return performBitwiseOperationHelper(self, self, other, op);
598}
599
600template <typename BitwiseOp> static
601QBitArray &performBitwiseOperation(QBitArray &self, const QBitArray &other, BitwiseOp op)
602{
603 if (self.data_ptr().needsDetach())
604 return performBitwiseOperationInCopy(self, other, op);
605 return performBitwiseOperationInPlace(self, other, op);
606}
607
608// SCARY helper
609enum { InCopy, InPlace };
610static auto prepareForBitwiseOperation(QBitArray &self, QBitArray &other)
611{
612 QByteArrayData &d1 = self.data_ptr();
613 QByteArrayData &d2 = other.data_ptr();
614 bool detached1 = !d1.needsDetach();
615 bool detached2 = !d2.needsDetach();
616 if (!detached1 && !detached2)
617 return InCopy;
618
619 // at least one of the two is detached, we'll reuse its buffer
620 bool swap = false;
621 if (detached1 && detached2) {
622 // both are detached, so choose the larger of the two
623 swap = d1.allocatedCapacity() < d2.allocatedCapacity();
624 } else if (detached2) {
625 // we can re-use other's buffer but not self's, so swap the two
626 swap = true;
627 }
628 if (swap)
629 self.swap(other);
630 return InPlace;
631}
632
633template <typename BitwiseOp> static
634QBitArray &performBitwiseOperation(QBitArray &self, QBitArray &other, BitwiseOp op)
635{
636 auto choice = prepareForBitwiseOperation(self, other);
637 if (choice == InCopy)
638 return performBitwiseOperationInCopy(self, other, std::move(op));
639 return performBitwiseOperationInPlace(self, other, std::move(op));
640}
641
642/*!
643 \fn QBitArray &QBitArray::operator&=(const QBitArray &other)
644 \fn QBitArray &QBitArray::operator&=(QBitArray &&other)
645
646 Performs the AND operation between all bits in this bit array and
647 \a other. Assigns the result to this bit array, and returns a
648 reference to it.
649
650 The result has the length of the longest of the two bit arrays,
651 with any missing bits (if one array is shorter than the other)
652 taken to be 0.
653
654 Example:
655 \snippet code/src_corelib_tools_qbitarray.cpp 8
656
657 \sa operator&(), operator|=(), operator^=(), operator~()
658*/
659
660QBitArray &QBitArray::operator&=(QBitArray &&other)
661{
662 return performBitwiseOperation(self&: *this, other, op: std::bit_and<uchar>());
663}
664
665QBitArray &QBitArray::operator&=(const QBitArray &other)
666{
667 return performBitwiseOperation(self&: *this, other, op: std::bit_and<uchar>());
668}
669
670/*!
671 \fn QBitArray &QBitArray::operator|=(const QBitArray &other)
672 \fn QBitArray &QBitArray::operator|=(QBitArray &&other)
673
674 Performs the OR operation between all bits in this bit array and
675 \a other. Assigns the result to this bit array, and returns a
676 reference to it.
677
678 The result has the length of the longest of the two bit arrays,
679 with any missing bits (if one array is shorter than the other)
680 taken to be 0.
681
682 Example:
683 \snippet code/src_corelib_tools_qbitarray.cpp 9
684
685 \sa operator|(), operator&=(), operator^=(), operator~()
686*/
687
688QBitArray &QBitArray::operator|=(QBitArray &&other)
689{
690 return performBitwiseOperation(self&: *this, other, op: std::bit_or<uchar>());
691}
692
693QBitArray &QBitArray::operator|=(const QBitArray &other)
694{
695 return performBitwiseOperation(self&: *this, other, op: std::bit_or<uchar>());
696}
697
698/*!
699 \fn QBitArray &QBitArray::operator^=(const QBitArray &other)
700 \fn QBitArray &QBitArray::operator^=(QBitArray &&other)
701
702 Performs the XOR operation between all bits in this bit array and
703 \a other. Assigns the result to this bit array, and returns a
704 reference to it.
705
706 The result has the length of the longest of the two bit arrays,
707 with any missing bits (if one array is shorter than the other)
708 taken to be 0.
709
710 Example:
711 \snippet code/src_corelib_tools_qbitarray.cpp 10
712
713 \sa operator^(), operator&=(), operator|=(), operator~()
714*/
715
716QBitArray &QBitArray::operator^=(QBitArray &&other)
717{
718 return performBitwiseOperation(self&: *this, other, op: std::bit_xor<uchar>());
719}
720
721QBitArray &QBitArray::operator^=(const QBitArray &other)
722{
723 return performBitwiseOperation(self&: *this, other, op: std::bit_xor<uchar>());
724}
725
726/*!
727 \fn QBitArray QBitArray::operator~(QBitArray a)
728 Returns a bit array that contains the inverted bits of the bit
729 array \a a.
730
731 Example:
732 \snippet code/src_corelib_tools_qbitarray.cpp 11
733
734 \sa operator&(), operator|(), operator^()
735*/
736
737Q_NEVER_INLINE QBitArray QBitArray::inverted_inplace() &&
738{
739 qsizetype n = d.size();
740 uchar *dst = reinterpret_cast<uchar *>(data_ptr().data());
741 const uchar *src = dst;
742 QBitArray result([&] {
743 if (d.isDetached() || n == 0)
744 return std::move(d.data_ptr()); // invert in-place
745
746 QByteArrayData tmp(n, n);
747 dst = reinterpret_cast<uchar *>(tmp.data());
748 return tmp;
749 }());
750
751 uchar bitdiff = 8;
752 if (n)
753 bitdiff = dst[0] = src[0]; // copy the count of bits in the last byte
754
755 for (qsizetype i = 1; i < n; ++i)
756 dst[i] = ~src[i];
757
758 if (int tailCount = 16 - bitdiff; tailCount != 8) {
759 // zero the bits beyond our size in the last byte
760 Q_ASSERT(n > 1);
761 uchar tailMask = (1U << tailCount) - 1;
762 dst[n - 1] &= tailMask;
763 }
764
765 return result;
766}
767
768/*!
769 \fn QBitArray QBitArray::operator&(const QBitArray &a1, const QBitArray &a2)
770 \fn QBitArray QBitArray::operator&(QBitArray &&a1, const QBitArray &a2)
771 \fn QBitArray QBitArray::operator&(const QBitArray &a1, QBitArray &&a2)
772 \fn QBitArray QBitArray::operator&(QBitArray &&a1, QBitArray &&a2)
773
774 Returns a bit array that is the AND of the bit arrays \a a1 and \a
775 a2.
776
777 The result has the length of the longest of the two bit arrays,
778 with any missing bits (if one array is shorter than the other)
779 taken to be 0.
780
781 Example:
782 \snippet code/src_corelib_tools_qbitarray.cpp 12
783
784 \sa {QBitArray::}{operator&=()}, {QBitArray::}{operator|()}, {QBitArray::}{operator^()}
785*/
786
787QBitArray operator&(const QBitArray &a1, const QBitArray &a2)
788{
789 QBitArray tmp = sizedForOverwrite(a1, a2);
790 performBitwiseOperationHelper(out&: tmp, a1, a2, op: std::bit_and<uchar>());
791 return tmp;
792}
793
794/*!
795 \fn QBitArray QBitArray::operator|(const QBitArray &a1, const QBitArray &a2)
796 \fn QBitArray QBitArray::operator|(QBitArray &&a1, const QBitArray &a2)
797 \fn QBitArray QBitArray::operator|(const QBitArray &a1, QBitArray &&a2)
798 \fn QBitArray QBitArray::operator|(QBitArray &&a1, QBitArray &&a2)
799
800 Returns a bit array that is the OR of the bit arrays \a a1 and \a
801 a2.
802
803 The result has the length of the longest of the two bit arrays,
804 with any missing bits (if one array is shorter than the other)
805 taken to be 0.
806
807 Example:
808 \snippet code/src_corelib_tools_qbitarray.cpp 13
809
810 \sa QBitArray::operator|=(), operator&(), operator^()
811*/
812
813QBitArray operator|(const QBitArray &a1, const QBitArray &a2)
814{
815 QBitArray tmp = sizedForOverwrite(a1, a2);
816 performBitwiseOperationHelper(out&: tmp, a1, a2, op: std::bit_or<uchar>());
817 return tmp;
818}
819
820/*!
821 \fn QBitArray QBitArray::operator^(const QBitArray &a1, const QBitArray &a2)
822 \fn QBitArray QBitArray::operator^(QBitArray &&a1, const QBitArray &a2)
823 \fn QBitArray QBitArray::operator^(const QBitArray &a1, QBitArray &&a2)
824 \fn QBitArray QBitArray::operator^(QBitArray &&a1, QBitArray &&a2)
825
826 Returns a bit array that is the XOR of the bit arrays \a a1 and \a
827 a2.
828
829 The result has the length of the longest of the two bit arrays,
830 with any missing bits (if one array is shorter than the other)
831 taken to be 0.
832
833 Example:
834 \snippet code/src_corelib_tools_qbitarray.cpp 14
835
836 \sa {QBitArray}{operator^=()}, {QBitArray}{operator&()}, {QBitArray}{operator|()}
837*/
838
839QBitArray operator^(const QBitArray &a1, const QBitArray &a2)
840{
841 QBitArray tmp = sizedForOverwrite(a1, a2);
842 performBitwiseOperationHelper(out&: tmp, a1, a2, op: std::bit_xor<uchar>());
843 return tmp;
844}
845
846/*!
847 \class QBitRef
848 \inmodule QtCore
849 \reentrant
850 \brief The QBitRef class is an internal class, used with QBitArray.
851
852 \internal
853
854 The QBitRef is required by the indexing [] operator on bit arrays.
855 It is not for use in any other context.
856*/
857
858/*! \fn QBitRef::QBitRef (QBitArray& a, qsizetype i)
859
860 Constructs a reference to element \a i in the QBitArray \a a.
861 This is what QBitArray::operator[] constructs its return value
862 with.
863*/
864
865/*! \fn QBitRef::operator bool() const
866
867 Returns the value referenced by the QBitRef.
868*/
869
870/*! \fn bool QBitRef::operator!() const
871
872 \internal
873*/
874
875/*! \fn QBitRef& QBitRef::operator= (const QBitRef& v)
876
877 Sets the value referenced by the QBitRef to that referenced by
878 QBitRef \a v.
879*/
880
881/*! \fn QBitRef& QBitRef::operator= (bool v)
882 \overload
883
884 Sets the value referenced by the QBitRef to \a v.
885*/
886
887/*****************************************************************************
888 QBitArray stream functions
889 *****************************************************************************/
890
891#ifndef QT_NO_DATASTREAM
892/*!
893 \relates QBitArray
894
895 Writes bit array \a ba to stream \a out.
896
897 \sa {Serializing Qt Data Types}{Format of the QDataStream operators}
898*/
899
900QDataStream &operator<<(QDataStream &out, const QBitArray &ba)
901{
902 const qsizetype len = ba.size();
903 if (out.version() < QDataStream::Qt_6_0) {
904 if (Q_UNLIKELY(len > qsizetype{(std::numeric_limits<qint32>::max)()})) {
905 out.setStatus(QDataStream::Status::SizeLimitExceeded);
906 return out;
907 }
908 out << quint32(len);
909 } else {
910 out << quint64(len);
911 }
912 if (len > 0)
913 out.writeRawData(ba.d.data() + 1, len: ba.d.size() - 1);
914 return out;
915}
916
917/*!
918 \relates QBitArray
919
920 Reads a bit array into \a ba from stream \a in.
921
922 \sa {Serializing Qt Data Types}{Format of the QDataStream operators}
923*/
924
925QDataStream &operator>>(QDataStream &in, QBitArray &ba)
926{
927 ba.clear();
928 qsizetype len;
929 if (in.version() < QDataStream::Qt_6_0) {
930 quint32 tmp;
931 in >> tmp;
932 if (Q_UNLIKELY(tmp > quint32((std::numeric_limits<qint32>::max)()))) {
933 in.setStatus(QDataStream::ReadCorruptData);
934 return in;
935 }
936 len = tmp;
937 } else {
938 quint64 tmp;
939 in >> tmp;
940 if (Q_UNLIKELY(tmp > quint64((std::numeric_limits<qsizetype>::max)()))) {
941 in.setStatus(QDataStream::Status::SizeLimitExceeded);
942 return in;
943 }
944 len = tmp;
945 }
946 if (len == 0) {
947 ba.clear();
948 return in;
949 }
950
951 const qsizetype Step = 8 * 1024 * 1024;
952 const qsizetype totalBytes = storage_size(size: len);
953 qsizetype allocated = 0;
954
955 while (allocated < totalBytes) {
956 qsizetype blockSize = qMin(a: Step, b: totalBytes - allocated);
957 ba.d.resize(size: allocated + blockSize + 1);
958 if (in.readRawData(ba.d.data() + 1 + allocated, len: blockSize) != blockSize) {
959 ba.clear();
960 in.setStatus(QDataStream::ReadPastEnd);
961 return in;
962 }
963 allocated += blockSize;
964 }
965
966 const auto fromStream = ba.d.back();
967 adjust_head_and_tail(data: ba.d.data(), storageSize: ba.d.size(), logicalSize: len);
968 if (ba.d.back() != fromStream) {
969 ba.clear();
970 in.setStatus(QDataStream::ReadCorruptData);
971 return in;
972 }
973 return in;
974}
975#endif // QT_NO_DATASTREAM
976
977#ifndef QT_NO_DEBUG_STREAM
978QDebug operator<<(QDebug dbg, const QBitArray &array)
979{
980 QDebugStateSaver saver(dbg);
981 dbg.nospace() << "QBitArray(";
982 for (qsizetype i = 0; i < array.size();) {
983 if (array.testBit(i))
984 dbg << '1';
985 else
986 dbg << '0';
987 i += 1;
988 if (!(i % 4) && (i < array.size()))
989 dbg << ' ';
990 }
991 dbg << ')';
992 return dbg;
993}
994#endif
995
996/*!
997 \fn DataPtr &QBitArray::data_ptr()
998 \internal
999*/
1000
1001/*!
1002 \typedef QBitArray::DataPtr
1003 \internal
1004*/
1005
1006QT_END_NAMESPACE
1007

source code of qtbase/src/corelib/tools/qbitarray.cpp