Qt 4.8
qbitarray.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtCore module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 
42 #include "qbitarray.h"
43 #include <qdatastream.h>
44 #include <qdebug.h>
45 #include <string.h>
46 
48 
129 QBitArray::QBitArray(int size, bool value)
130 {
131  if (!size) {
132  d.resize(0);
133  return;
134  }
135  d.resize(1 + (size+7)/8);
136  uchar* c = reinterpret_cast<uchar*>(d.data());
137  memset(c, value ? 0xff : 0, d.size());
138  *c = d.size()*8 - size;
139  if (value && size && size % 8)
140  *(c+1+size/8) &= (1 << (size%8)) - 1;
141 }
142 
166 int QBitArray::count(bool on) const
167 {
168  int numBits = 0;
169  int len = size();
170 #if 0
171  for (int i = 0; i < len; ++i)
172  numBits += testBit(i);
173 #else
174  // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
175  const quint8 *bits = reinterpret_cast<const quint8 *>(d.data()) + 1;
176  while (len >= 32) {
177  quint32 v = quint32(bits[0]) | (quint32(bits[1]) << 8) | (quint32(bits[2]) << 16) | (quint32(bits[3]) << 24);
178  quint32 c = ((v & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
179  c += (((v & 0xfff000) >> 12) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
180  c += ((v >> 24) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
181  len -= 32;
182  bits += 4;
183  numBits += int(c);
184  }
185  while (len >= 24) {
186  quint32 v = quint32(bits[0]) | (quint32(bits[1]) << 8) | (quint32(bits[2]) << 16);
187  quint32 c = ((v & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
188  c += (((v & 0xfff000) >> 12) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
189  len -= 24;
190  bits += 3;
191  numBits += int(c);
192  }
193  while (len >= 0) {
194  if (bits[len / 8] & (1 << ((len - 1) & 7)))
195  ++numBits;
196  --len;
197  }
198 #endif
199  return on ? numBits : size() - numBits;
200 }
201 
215 {
216  if (!size) {
217  d.resize(0);
218  } else {
219  int s = d.size();
220  d.resize(1 + (size+7)/8);
221  uchar* c = reinterpret_cast<uchar*>(d.data());
222  if (size > (s << 3))
223  memset(c + s, 0, d.size() - s);
224  else if ( size % 8)
225  *(c+1+size/8) &= (1 << (size%8)) - 1;
226  *c = d.size()*8 - size;
227  }
228 }
229 
287 void QBitArray::fill(bool value, int begin, int end)
288 {
289  while (begin < end && begin & 0x7)
290  setBit(begin++, value);
291  int len = end - begin;
292  if (len <= 0)
293  return;
294  int s = len & ~0x7;
295  uchar *c = reinterpret_cast<uchar*>(d.data());
296  memset(c + (begin >> 3) + 1, value ? 0xff : 0, s >> 3);
297  begin += s;
298  while (begin < end)
299  setBit(begin++, value);
300 }
301 
526 {
527  resize(qMax(size(), other.size()));
528  uchar *a1 = reinterpret_cast<uchar*>(d.data()) + 1;
529  const uchar *a2 = reinterpret_cast<const uchar*>(other.d.constData()) + 1;
530  int n = other.d.size() -1 ;
531  int p = d.size() - 1 - n;
532  while (n-- > 0)
533  *a1++ &= *a2++;
534  while (p-- > 0)
535  *a1++ = 0;
536  return *this;
537 }
538 
555 {
556  resize(qMax(size(), other.size()));
557  uchar *a1 = reinterpret_cast<uchar*>(d.data()) + 1;
558  const uchar *a2 = reinterpret_cast<const uchar *>(other.d.constData()) + 1;
559  int n = other.d.size() - 1;
560  while (n-- > 0)
561  *a1++ |= *a2++;
562  return *this;
563 }
564 
581 {
582  resize(qMax(size(), other.size()));
583  uchar *a1 = reinterpret_cast<uchar*>(d.data()) + 1;
584  const uchar *a2 = reinterpret_cast<const uchar *>(other.d.constData()) + 1;
585  int n = other.d.size() - 1;
586  while (n-- > 0)
587  *a1++ ^= *a2++;
588  return *this;
589 }
590 
602 {
603  int sz = size();
604  QBitArray a(sz);
605  const uchar *a1 = reinterpret_cast<const uchar *>(d.constData()) + 1;
606  uchar *a2 = reinterpret_cast<uchar*>(a.d.data()) + 1;
607  int n = d.size() - 1;
608 
609  while (n-- > 0)
610  *a2++ = ~*a1++;
611 
612  if (sz && sz%8)
613  *(a2-1) &= (1 << (sz%8)) - 1;
614  return a;
615 }
616 
636 QBitArray operator&(const QBitArray &a1, const QBitArray &a2)
637 {
638  QBitArray tmp = a1;
639  tmp &= a2;
640  return tmp;
641 }
642 
662 QBitArray operator|(const QBitArray &a1, const QBitArray &a2)
663 {
664  QBitArray tmp = a1;
665  tmp |= a2;
666  return tmp;
667 }
668 
688 QBitArray operator^(const QBitArray &a1, const QBitArray &a2)
689 {
690  QBitArray tmp = a1;
691  tmp ^= a2;
692  return tmp;
693 }
694 
751 /*****************************************************************************
752  QBitArray stream functions
753  *****************************************************************************/
754 
755 #ifndef QT_NO_DATASTREAM
756 
768 {
769  quint32 len = ba.size();
770  out << len;
771  if (len > 0)
772  out.writeRawData(ba.d.constData() + 1, ba.d.size() - 1);
773  return out;
774 }
775 
788 {
789  ba.clear();
790  quint32 len;
791  in >> len;
792  if (len == 0) {
793  ba.clear();
794  return in;
795  }
796 
797  const quint32 Step = 8 * 1024 * 1024;
798  quint32 totalBytes = (len + 7) / 8;
799  quint32 allocated = 0;
800 
801  while (allocated < totalBytes) {
802  int blockSize = qMin(Step, totalBytes - allocated);
803  ba.d.resize(allocated + blockSize + 1);
804  if (in.readRawData(ba.d.data() + 1 + allocated, blockSize) != blockSize) {
805  ba.clear();
807  return in;
808  }
809  allocated += blockSize;
810  }
811 
812  int paddingMask = ~((0x1 << (len & 0x7)) - 1);
813  if (paddingMask != ~0x0 && (ba.d.constData()[ba.d.size() - 1] & paddingMask)) {
814  ba.clear();
816  return in;
817  }
818 
819  *ba.d.data() = ba.d.size() * 8 - len;
820  return in;
821 }
822 #endif // QT_NO_DATASTREAM
823 
void clear()
Clears the contents of the bit array and makes it empty.
Definition: qbitarray.h:85
QBitArray operator^(const QBitArray &a1, const QBitArray &a2)
Returns a bit array that is the XOR of the bit arrays a1 and a2.
Definition: qbitarray.cpp:688
const int blockSize
QBitArray()
Constructs an empty bit array.
Definition: qbitarray.h:62
unsigned char c[8]
Definition: qnumeric_p.h:62
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
void setBit(int i)
Sets the bit at index position i to 1.
Definition: qbitarray.h:128
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
char * data()
Returns a pointer to the data stored in the byte array.
Definition: qbytearray.h:429
long ASN1_INTEGER_get ASN1_INTEGER * a
void setStatus(Status status)
Sets the status of the data stream to the status given.
unsigned char quint8
Definition: qglobal.h:934
bool testBit(int i) const
Returns true if the bit at index position i is 1; otherwise returns false.
Definition: qbitarray.h:124
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
QBitArray & operator &=(const QBitArray &)
QBitArray operator~() const
Returns a bit array that contains the inverted bits of this bit array.
Definition: qbitarray.cpp:601
QByteArray d
Definition: qbitarray.h:59
unsigned char uchar
Definition: qglobal.h:994
bool fill(bool val, int size=-1)
Sets every bit in the bit array to value, returning true if successful; otherwise returns false...
Definition: qbitarray.h:117
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
int readRawData(char *, int len)
Reads at most len bytes from the stream into s and returns the number of bytes read.
void resize(int size)
Resizes the bit array to size bits.
Definition: qbitarray.cpp:214
The QBitArray class provides an array of bits.
Definition: qbitarray.h:54
const char * constData() const
Returns a pointer to the data stored in the byte array.
Definition: qbytearray.h:433
QBitArray & operator|=(const QBitArray &)
Performs the OR operation between all bits in this bit array and other.
Definition: qbitarray.cpp:554
void resize(int size)
Sets the size of the byte array to size bytes.
unsigned int quint32
Definition: qglobal.h:938
int count() const
Same as size().
Definition: qbitarray.h:74
int size() const
Returns the number of bytes in this byte array.
Definition: qbytearray.h:402
The QDataStream class provides serialization of binary data to a QIODevice.
Definition: qdatastream.h:71
friend Q_CORE_EXPORT QDataStream & operator<<(QDataStream &, const QBitArray &)
Writes bit array ba to stream out.
Definition: qbitarray.cpp:767
#define Q_UINT64_C(c)
Definition: qglobal.h:941
QBitArray operator|(const QBitArray &a1, const QBitArray &a2)
Returns a bit array that is the OR of the bit arrays a1 and a2.
Definition: qbitarray.cpp:662
static const KeyPair *const end
QBitArray & operator^=(const QBitArray &)
Performs the XOR operation between all bits in this bit array and other.
Definition: qbitarray.cpp:580
int size() const
Returns the number of bits stored in the bit array.
Definition: qbitarray.h:73
int writeRawData(const char *, int len)
Writes len bytes from s to the stream.
friend Q_CORE_EXPORT QDataStream & operator>>(QDataStream &, QBitArray &)
Reads a bit array into ba from stream in.
Definition: qbitarray.cpp:787
QBitArray operator&(const QBitArray &a1, const QBitArray &a2)
Returns a bit array that is the AND of the bit arrays a1 and a2.
Definition: qbitarray.cpp:636