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

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