cpp/core/src/zxing/common/BitMatrix.cpp

   1 /*
   2  *  BitMatrix.cpp
   3  *  zxing
   4  *
   5  *  Created by Christian Brunschen on 12/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/BitMatrix.h>
  22 #include <zxing/common/IllegalArgumentException.h>
  23
  24 #include <iostream>
  25 #include <sstream>
  26 #include <string>
  27
  28 namespace zxing {
  29 using namespace std;
  30
  31 unsigned int logDigits(unsigned digits) {
  32   unsigned log = 0;
  33   unsigned val = 1;
  34   while (val < digits) {
  35     log++;
  36     val <<= 1;
  37   }
  38   return log;
  39 }
  40
  41
  42 const unsigned int bitsPerWord = numeric_limits<unsigned int>::digits;
  43 const unsigned int logBits = logDigits(bitsPerWord);
  44 const unsigned int bitsMask = (1 << logBits) - 1;
  45
  46 static size_t wordsForSize(size_t width, size_t height) {
  47   size_t bits = width * height;
  48   int arraySize = bits >> logBits;
  49   if (bits - (arraySize << logBits) != 0) {
  50     arraySize++;
  51   }
  52   return arraySize;
  53 }
  54
  55 BitMatrix::BitMatrix(size_t dimension) :
  56     width_(dimension), height_(dimension), words_(0), bits_(NULL) {
  57
  58   words_ = wordsForSize(width_, height_);
  59   bits_ = new unsigned int[words_];
  60   clear();
  61 }
  62
  63 BitMatrix::BitMatrix(size_t width, size_t height) :
  64     width_(width), height_(height), words_(0), bits_(NULL) {
  65
  66   words_ = wordsForSize(width_, height_);
  67   bits_ = new unsigned int[words_];
  68   clear();
  69 }
  70
  71 BitMatrix::~BitMatrix() {
  72   delete[] bits_;
  73 }
  74
  75
  76 bool BitMatrix::get(size_t x, size_t y) const {
  77   size_t offset = x + width_ * y;
  78   return ((bits_[offset >> logBits] >> (offset & bitsMask)) & 0x01) != 0;
  79 }
  80
  81 void BitMatrix::set(size_t x, size_t y) {
  82   size_t offset = x + width_ * y;
  83   bits_[offset >> logBits] |= 1 << (offset & bitsMask);
  84 }
  85
  86 void BitMatrix::flip(size_t x, size_t y) {
  87   size_t offset = x + width_ * y;
  88   bits_[offset >> logBits] ^= 1 << (offset & bitsMask);
  89 }
  90
  91 void BitMatrix::clear() {
  92   std::fill(bits_, bits_+words_, 0);
  93 }
  94
  95 void BitMatrix::setRegion(size_t left, size_t top, size_t width, size_t height) {
  96   if (top < 0 || left < 0) {
  97     throw IllegalArgumentException("topI and leftJ must be nonnegative");
  98   }
  99   if (height < 1 || width < 1) {
 100     throw IllegalArgumentException("height and width must be at least 1");
 101   }
 102   size_t right = left + width;
 103   size_t bottom = top + height;
 104   if (right > width_ || bottom > height_) {
 105     throw IllegalArgumentException("top + height and left + width must be <= matrix dimension");
 106   }
 107   for (size_t y = top; y < bottom; y++) {
 108     int yOffset = width_ * y;
 109     for (size_t x = left; x < right; x++) {
 110       size_t offset = x + yOffset;
 111       bits_[offset >> logBits] |= 1 << (offset & bitsMask);
 112     }
 113   }
 114 }
 115
 116 Ref<BitArray> BitMatrix::getRow(int y, Ref<BitArray> row) {
 117   if (row.empty() || row->getSize() < width_) {
 118     row = new BitArray(width_);
 119   } else {
 120     row->clear();
 121   }
 122   size_t start = y * width_;
 123   size_t end = start + width_ - 1; // end is inclusive
 124   size_t firstWord = start >> logBits;
 125   size_t lastWord = end >> logBits;
 126   size_t bitOffset = start & bitsMask;
 127   for (size_t i = firstWord; i <= lastWord; i++) {
 128     size_t firstBit = i > firstWord ? 0 : start & bitsMask;
 129     size_t lastBit = i < lastWord ? bitsPerWord - 1 : end & bitsMask;
 130     unsigned int mask;
 131     if (firstBit == 0 && lastBit == logBits) {
 132       mask = numeric_limits<unsigned int>::max();
 133     } else {
 134       mask = 0;
 135       for (size_t j = firstBit; j <= lastBit; j++) {
 136         mask |= 1 << j;
 137       }
 138     }
 139     row->setBulk((i - firstWord) << logBits, (bits_[i] & mask) >> bitOffset);
 140     if (firstBit == 0 && bitOffset != 0) {
 141       unsigned int prevBulk = row->getBitArray()[i - firstWord - 1];
 142       prevBulk |= (bits_[i] & mask) << (bitsPerWord - bitOffset);
 143       row->setBulk((i - firstWord - 1) << logBits, prevBulk);
 144     }
 145   }
 146   return row;
 147 }
 148
 149 size_t BitMatrix::getWidth() const {
 150   return width_;
 151 }
 152
 153 size_t BitMatrix::getHeight() const {
 154   return height_;
 155 }
 156
 157 size_t BitMatrix::getDimension() const {
 158   return width_;
 159 }
 160
 161 unsigned int* BitMatrix::getBits() const {
 162   return bits_;
 163 }
 164
 165 ostream& operator<<(ostream &out, const BitMatrix &bm) {
 166   for (size_t y = 0; y < bm.height_; y++) {
 167     for (size_t x = 0; x < bm.width_; x++) {
 168       out << (bm.get(x, y) ? "X " : "  ");
 169     }
 170     out << "\n";
 171   }
 172   return out;
 173 }
 174 const char *BitMatrix::description() {
 175   ostringstream out;
 176   out << *this;
 177   return out.str().c_str();
 178 }
 179
 180 }