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),
  54   bits_((const unsigned int)0, wordsForDimension(dimension)) {
  55   }
  56
  57   BitMatrix::~BitMatrix() {
  58
  59   }
  60
  61   bool BitMatrix::get(size_t i, size_t j) {
  62     size_t offset = i + dimension_ * j;
  63     return ((bits_[offset >> logBits_] >> (offset & bitsMask_)) & 0x01) != 0;
  64   }
  65
  66   void BitMatrix::set(size_t i, size_t j) {
  67     size_t offset = i + dimension_ * j;
  68     bits_[offset >> logBits_] |= 1 << (offset & bitsMask_);
  69   }
  70
  71   void BitMatrix::setRegion(size_t topI,
  72                             size_t leftJ,
  73                             size_t height,
  74                             size_t width) {
  75     if (topI < 0 || leftJ < 0) {
  76       throw new IllegalArgumentException("topI and leftJ must be nonnegative");
  77     }
  78     if (height < 1 || width < 1) {
  79       throw new IllegalArgumentException("height and width must be at least 1");
  80     }
  81     size_t maxJ = leftJ + width;
  82     size_t maxI = topI + height;
  83     if (maxI > dimension_ || maxJ > dimension_) {
  84       throw new IllegalArgumentException
  85         ("topI + height and leftJ + width must be <= matrix dimension");
  86     }
  87     for (size_t j = leftJ; j < maxJ; j++) {
  88       int jOffset = dimension_ * j;
  89       for (size_t i = topI; i < maxI; i++) {
  90         size_t offset = i + jOffset;
  91         bits_[offset >> logBits_] |= 1 << (offset & bitsMask_);
  92       }
  93     }
  94   }
  95
  96   size_t BitMatrix::getDimension() {
  97     return dimension_;
  98   }
  99
 100   valarray<unsigned int> &BitMatrix::getBits() {
 101     return bits_;
 102   }
 103
 104   ostream& operator<<(ostream &out, BitMatrix &bm) {
 105     for (size_t i = 0; i < bm.dimension_; i++) {
 106       for (size_t j = 0; j < bm.dimension_; j++) {
 107         out << (bm.get(i, j) ? "* " : "- ");
 108       }
 109       out << "\n";
 110     }
 111     return out;
 112   }
 113  const char *BitMatrix::description() {
 114     ostringstream out;
 115     out << *this;
 116     return out.str().c_str();
 117   }
 118
 119 }