cpp/core/src/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 "BitMatrix.h"
  22 #include "IllegalArgumentException.h"
  23 #include <limits>
  24 #include <iostream>
  25 #include <sstream>
  26
  27 namespace common {
  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   static const unsigned int bitsPerWord_ =
  39     numeric_limits<unsigned int>::digits;
  40   static const unsigned int logBits_ = logDigits(bitsPerWord_);
  41   static const unsigned int bitsMask_ = (1 << logBits_) - 1;
  42
  43   static size_t wordsForDimension(size_t dimension) {
  44     size_t bits = dimension * dimension;
  45     int arraySize = bits >> logBits_;
  46     if (bits - (arraySize << logBits_) != 0) {
  47       arraySize++;
  48     }
  49     return arraySize;
  50   }
  51
  52   BitMatrix::BitMatrix(size_t dimension) :
  53   dimension_(dimension), bits_(wordsForDimension(dimension)) {
  54   }
  55
  56   BitMatrix::~BitMatrix() {
  57
  58   }
  59
  60   bool BitMatrix::get(size_t i, size_t j) {
  61     size_t offset = i + dimension_ * j;
  62     return ((bits_[offset >> logBits_] >> (offset & bitsMask_)) & 0x01) != 0;
  63   }
  64
  65   void BitMatrix::set(size_t i, size_t j) {
  66     size_t offset = i + dimension_ * j;
  67     bits_[offset >> logBits_] |= 1 << (offset & bitsMask_);
  68   }
  69
  70   void BitMatrix::setRegion(size_t topI,
  71                             size_t leftJ,
  72                             size_t height,
  73                             size_t width) {
  74     if (topI < 0 || leftJ < 0) {
  75       throw new IllegalArgumentException("topI and leftJ must be nonnegative");
  76     }
  77     if (height < 1 || width < 1) {
  78       throw new IllegalArgumentException("height and width must be at least 1");
  79     }
  80     size_t maxJ = leftJ + width;
  81     size_t maxI = topI + height;
  82     if (maxI > dimension_ || maxJ > dimension_) {
  83       throw new IllegalArgumentException
  84         ("topI + height and leftJ + width must be <= matrix dimension");
  85     }
  86     for (size_t j = leftJ; j < maxJ; j++) {
  87       int jOffset = dimension_ * j;
  88       for (size_t i = topI; i < maxI; i++) {
  89         size_t offset = i + jOffset;
  90         bits_[offset >> logBits_] |= 1 << (offset & bitsMask_);
  91       }
  92     }
  93   }
  94
  95   size_t BitMatrix::getDimension() {
  96     return dimension_;
  97   }
  98
  99   valarray<unsigned int> &BitMatrix::getBits() {
 100     return bits_;
 101   }
 102
 103   ostream& operator<<(ostream &out, BitMatrix &bm) {
 104     for (size_t i = 0; i < bm.dimension_; i++) {
 105       for (size_t j = 0; j < bm.dimension_; j++) {
 106         out << (bm.get(i, j) ? "* " : "- ");
 107       }
 108       out << "\n";
 109     }
 110     return out;
 111   }
 112  const char *BitMatrix::description() {
 113     ostringstream out;
 114     out << *this;
 115     return out.str().c_str();
 116   }
 117
 118 }