BitArray.cpp Example File
appdemos/qtws/QZXing/zxing/zxing/common/BitArray.cpp
#include <zxing/common/BitArray.h>
#include <zxing/common/Array.h>
#include <cstring>
#include <sstream>
using std::vector;
using zxing::BitArray;
using zxing::Ref;
namespace zxing {
int BitArray::makeArraySize(int size) {
return (size + 31) / 32;
}
BitArray::BitArray(): size(0), bits(1) {}
BitArray::BitArray(int size_)
: size(size_), bits(makeArraySize(size)) {}
BitArray::BitArray(std::vector<int> other)
: size(other.size()), bits(other.size())
{
for(int i=0; i<other.size(); i++)
if(other[i])
set(i);
}
BitArray::~BitArray() {
}
int BitArray::getSize() const {
return size;
}
int BitArray::getSizeInBytes() const
{
return (size + 7)/8;
}
void BitArray::setBulk(int i, int newBits) {
bits[i / 32] = newBits;
}
void BitArray::clear() {
int max = bits->size();
for (int i = 0; i < max; i++) {
bits[i] = 0;
}
}
bool BitArray::isRange(int start, int end, bool value) {
if (end < start) {
throw IllegalArgumentException();
}
if (end == start) {
return true;
}
end--;
int firstInt = start / 32;
int lastInt = end / 32;
for (int i = firstInt; i <= lastInt; i++) {
int firstBit = i > firstInt ? 0 : start & 0x1F;
int lastBit = i < lastInt ? 31 : end & 0x1F;
int mask = (2 << lastBit) - (1 << firstBit);
if ((bits[i] & mask) != (value ? mask : 0)) {
return false;
}
}
return true;
}
vector<int>& BitArray::getBitArray() {
return bits->values();
}
void BitArray::reverse()
{
ArrayRef<int> newBits(bits->size());
int len = ((this->size-1) / 32);
int oldBitsLen = len + 1;
for (int i = 0; i < oldBitsLen; i++) {
long x = (long) bits[i];
x = ((x >> 1) & 0x55555555L) | ((x & 0x55555555L) << 1);
x = ((x >> 2) & 0x33333333L) | ((x & 0x33333333L) << 2);
x = ((x >> 4) & 0x0f0f0f0fL) | ((x & 0x0f0f0f0fL) << 4);
x = ((x >> 8) & 0x00ff00ffL) | ((x & 0x00ff00ffL) << 8);
x = ((x >> 16) & 0x0000ffffL) | ((x & 0x0000ffffL) << 16);
newBits[len - i] = (int) x;
}
if (size != oldBitsLen * 32) {
int leftOffset = oldBitsLen * 32 - size;
int mask = 1;
for (int i = 0; i < 31 - leftOffset; i++) {
mask = (mask << 1) | 1;
}
int currentInt = (newBits[0] >> leftOffset) & mask;
for (int i = 1; i < oldBitsLen; i++) {
int nextInt = newBits[i];
currentInt |= nextInt << (32 - leftOffset);
newBits[i - 1] = currentInt;
currentInt = (nextInt >> leftOffset) & mask;
}
newBits[oldBitsLen - 1] = currentInt;
}
bits = newBits;
}
BitArray::Reverse::Reverse(Ref<BitArray> array_) : array(array_) {
array->reverse();
}
BitArray::Reverse::~Reverse() {
array->reverse();
}
namespace {
int numberOfTrailingZeros(int i) {
#if defined(__clang__) || defined(__GNUC__)
return __builtin_ctz(i);
#else
int y;
if (i == 0) return 32;
int n = 31;
y = i <<16; if (y != 0) { n = n -16; i = y; }
y = i << 8; if (y != 0) { n = n - 8; i = y; }
y = i << 4; if (y != 0) { n = n - 4; i = y; }
y = i << 2; if (y != 0) { n = n - 2; i = y; }
return n - (((unsigned int)(i << 1)) >> 31);
#endif
}
}
int BitArray::getNextSet(int from) {
if (from >= size) {
return size;
}
int bitsOffset = from >> logBits;
int currentBits = bits[bitsOffset];
currentBits &= ~((1 << (from & bitsMask)) - 1);
while (currentBits == 0) {
if (++bitsOffset == (int)bits->size()) {
return size;
}
currentBits = bits[bitsOffset];
}
int result = (bitsOffset << logBits) + numberOfTrailingZeros(currentBits);
return result > size ? size : result;
}
int BitArray::getNextUnset(int from) {
if (from >= size) {
return size;
}
int bitsOffset = from >> logBits;
int currentBits = ~bits[bitsOffset];
currentBits &= ~((1 << (from & bitsMask)) - 1);
while (currentBits == 0) {
if (++bitsOffset == (int)bits->size()) {
return size;
}
currentBits = ~bits[bitsOffset];
}
int result = (bitsOffset << logBits) + numberOfTrailingZeros(currentBits);
return result > size ? size : result;
}
void BitArray::appendBit(bool bit)
{
ensureCapacity(size + 1);
if (bit) {
bits[size / 32] |= 1 << (size & 0x1F);
}
size++;
}
void BitArray::appendBits(int value, int numBits)
{
if (numBits < 0 || numBits > 32) {
throw IllegalArgumentException("Num bits must be between 0 and 32");
}
ensureCapacity(size + numBits);
for (int numBitsLeft = numBits; numBitsLeft > 0; numBitsLeft--) {
appendBit(((value >> (numBitsLeft - 1)) & 0x01) == 1);
}
}
void BitArray::appendBitArray(const BitArray& other)
{
int otherSize = other.size;
ensureCapacity(size + otherSize);
for (int i = 0; i < otherSize; i++) {
appendBit(other.get(i));
}
}
void BitArray::ensureCapacity(int size)
{
if (size > bits->size() * 32)
{
ArrayRef<int> newBits = makeArray(size);
for (size_t i=0; i<bits->size(); ++i) {
newBits[i] = bits[i];
}
bits = newBits;
}
}
void BitArray::xor_(const BitArray& other)
{
if (bits->size() != other.bits->size()) {
throw IllegalArgumentException("Sizes don't match");
}
for (int i = 0; i < bits->size(); i++) {
bits[i] ^= other.bits[i];
}
}
void BitArray::toBytes(int bitOffset, std::vector<byte>& array, int offset, int numBytes) const
{
if(array.size() < (numBytes + offset))
array.resize(numBytes + offset);
for (int i = 0; i < numBytes; i++) {
int theByte = 0;
for (int j = 0; j < 8; j++) {
if (get(bitOffset)) {
theByte |= 1 << (7 - j);
}
bitOffset++;
}
array[offset + i] = (byte) theByte;
}
}
const std::string BitArray::toString() const
{
std::stringstream result;
for (size_t i = 0; i < size; i++) {
if ((i & 0x07) == 0) {
result << ' ';
}
result << (get(i) ? 'X' : '.');
}
return result.str();
}
}