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
  48 BitArray::BitArray(size_t size) :
  49     size_(size), bits_(wordsForBits(size), (const unsigned int)0) {
  50 }
  51 BitArray::~BitArray() {
  52 }
  53 size_t BitArray::getSize() {
  54   return size_;
  55 }
  56 bool BitArray::get(size_t i) {
  57   return (bits_[i >> logBits_] & (1 << (i & bitsMask_))) != 0;
  58 }
  59 void BitArray::set(size_t i) {
  60   bits_[i >> logBits_] |= 1 << (i & bitsMask_);
  61 }
  62 void BitArray::setBulk(size_t i, unsigned int newBits) {
  63   bits_[i >> logBits_] = newBits;
  64 }
  65 void BitArray::clear() {
  66   size_t max = bits_.size();
  67   for (size_t i = 0; i < max; i++) {
  68     bits_[i] = 0;
  69   }
  70 }
  71 bool BitArray::isRange(size_t start, size_t end, bool value) {
  72   if (end < start) {
  73     throw IllegalArgumentException("end must be after start");
  74   }
  75   if (end == start) {
  76     return true;
  77   }
  78   // treat the 'end' as inclusive, rather than exclusive
  79   end--;
  80   size_t firstWord = start >> logBits_;
  81   size_t lastWord = end >> logBits_;
  82   for (size_t i = firstWord; i <= lastWord; i++) {
  83     size_t firstBit = i > firstWord ? 0 : start & bitsMask_;
  84     size_t lastBit = i < lastWord ? logBits_ : end & bitsMask_;
  85     unsigned int mask;
  86     if (firstBit == 0 && lastBit == logBits_) {
  87       mask = numeric_limits<unsigned int>::max();
  88     } else {
  89       mask = 0;
  90       for (size_t j = firstBit; j <= lastBit; j++) {
  91         mask |= 1 << j;
  92       }
  93     }
  94     if (value) {
  95       if ((bits_[i] & mask) != mask) {
  96         return false;
  97       }
  98     } else {
  99       if ((bits_[i] & mask) != 0) {
 100         return false;
 101       }
 102     }
 103   }
 104   return true;
 105 }
 106 vector<unsigned int>& BitArray::getBitArray() {
 107   return bits_;
 108 }
 109 void BitArray::reverse() {
 110   std::vector<unsigned int> newBits(bits_.size(),(const unsigned int) 0);
 111   for (size_t i = 0; i < size_; i++) {
 112     if (get(size_ - i - 1)) {
 113       newBits[i >> logBits_] |= 1<< (i & bitsMask_);
 114     }
 115   }
 116   bits_ = newBits;
 117 }
 118 }