cpp/core/src/zxing/common/BitArray.cpp

   1 /*
   2  *  BitArray.cpp
   3  *  zxing
   4  *
   5  *  Created by Christian Brunschen on 09/05/2008.
   6  *  Copyright 2008 Google UK. All rights reserved.
   7  *
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20
  21 #include <zxing/common/BitArray.h>
  22 #include <iostream>
  23 #include <limits>
  24
  25 using namespace std;
  26
  27 namespace zxing {
  28 static unsigned int logDigits(unsigned digits) {
  29   unsigned log = 0;
  30   unsigned val = 1;
  31   while (val < digits) {
  32     log++;
  33     val <<= 1;
  34   }
  35   return log;
  36 }
  37 const unsigned int BitArray::bitsPerWord_ = numeric_limits<unsigned int>::digits;
  38 const unsigned int BitArray::logBits_ = logDigits(bitsPerWord_);
  39 const unsigned int BitArray::bitsMask_ = (1 << logBits_) - 1;
  40 size_t BitArray::wordsForBits(size_t bits) {
  41   int arraySize = bits >> logBits_;
  42   if (bits - (arraySize << logBits_) != 0) {
  43     arraySize++;
  44   }
  45   return arraySize;
  46 }
  47 BitArray::BitArray() {
  48   cout << "hey! don't use this BitArrayConstructor!\n";
  49 }
  50
  51 BitArray::BitArray(size_t size) :
  52     size_(size), bits_(wordsForBits(size), (const unsigned int)0) {
  53 }
  54 BitArray::~BitArray() {
  55 }
  56 size_t BitArray::getSize() {
  57   return size_;
  58 }
  59 bool BitArray::get(size_t i) {
  60   return (bits_[i >> logBits_] & (1 << (i & bitsMask_))) != 0;
  61 }
  62 void BitArray::set(size_t i) {
  63   bits_[i >> logBits_] |= 1 << (i & bitsMask_);
  64 }
  65 void BitArray::setBulk(size_t i, unsigned int newBits) {
  66   bits_[i >> logBits_] = newBits;
  67 }
  68 void BitArray::clear() {
  69   size_t max = bits_.size();
  70   for (size_t i = 0; i < max; i++) {
  71     bits_[i] = 0;
  72   }
  73 }
  74 bool BitArray::isRange(size_t start, size_t end, bool value) {
  75   if (end < start) {
  76     throw IllegalArgumentException("end must be after start");
  77   }
  78   if (end == start) {
  79     return true;
  80   }
  81   // treat the 'end' as inclusive, rather than exclusive
  82   end--;
  83   size_t firstWord = start >> logBits_;
  84   size_t lastWord = end >> logBits_;
  85   for (size_t i = firstWord; i <= lastWord; i++) {
  86     size_t firstBit = i > firstWord ? 0 : start & bitsMask_;
  87     size_t lastBit = i < lastWord ? logBits_ : end & bitsMask_;
  88     unsigned int mask;
  89     if (firstBit == 0 && lastBit == logBits_) {
  90       mask = numeric_limits<unsigned int>::max();
  91     } else {
  92       mask = 0;
  93       for (size_t j = firstBit; j <= lastBit; j++) {
  94         mask |= 1 << j;
  95       }
  96     }
  97     if (value) {
  98       if ((bits_[i] & mask) != mask) {
  99         return false;
 100       }
 101     } else {
 102       if ((bits_[i] & mask) != 0) {
 103         return false;
 104       }
 105     }
 106   }
 107   return true;
 108 }
 109 vector<unsigned int>& BitArray::getBitArray() {
 110   return bits_;
 111 }
 112 void BitArray::reverse() {
 113   unsigned int allBits = numeric_limits<unsigned int>::max();
 114   size_t max = bits_.size();
 115   for (size_t i = 0; i < max; i++) {
 116     bits_[i] = bits_[i] ^ allBits;
 117   }
 118 }
 119 }