5 * Created by Christian Brunschen on 12/05/2008.
6 * Copyright 2008 Google UK. All rights reserved.
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
12 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 #include <zxing/common/BitMatrix.h>
22 #include <zxing/common/IllegalArgumentException.h>
31 unsigned int logDigits(unsigned digits) {
34 while (val < digits) {
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;
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) {
55 BitMatrix::BitMatrix(size_t dimension) :
56 width_(dimension), height_(dimension), words_(0), bits_(NULL) {
58 words_ = wordsForSize(width_, height_);
59 bits_ = new unsigned int[words_];
63 BitMatrix::BitMatrix(size_t width, size_t height) :
64 width_(width), height_(height), words_(0), bits_(NULL) {
66 words_ = wordsForSize(width_, height_);
67 bits_ = new unsigned int[words_];
71 BitMatrix::~BitMatrix() {
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;
81 void BitMatrix::set(size_t x, size_t y) {
82 size_t offset = x + width_ * y;
83 bits_[offset >> logBits] |= 1 << (offset & bitsMask);
86 void BitMatrix::flip(size_t x, size_t y) {
87 size_t offset = x + width_ * y;
88 bits_[offset >> logBits] ^= 1 << (offset & bitsMask);
91 void BitMatrix::clear() {
92 std::fill(bits_, bits_+words_, 0);
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");
99 if (height < 1 || width < 1) {
100 throw IllegalArgumentException("height and width must be at least 1");
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");
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);
116 Ref<BitArray> BitMatrix::getRow(int y, Ref<BitArray> row) {
117 if (row.empty() || row->getSize() < width_) {
118 row = new BitArray(width_);
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;
131 if (firstBit == 0 && lastBit == logBits) {
132 mask = numeric_limits<unsigned int>::max();
135 for (size_t j = firstBit; j <= lastBit; j++) {
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);
149 size_t BitMatrix::getWidth() const {
153 size_t BitMatrix::getHeight() const {
157 size_t BitMatrix::getDimension() const {
161 unsigned int* BitMatrix::getBits() const {
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 " : " ");
174 const char *BitMatrix::description() {
177 return out.str().c_str();