2 * Copyright 2007 ZXing authors
\r
4 * Licensed under the Apache License, Version 2.0 (the "License");
\r
5 * you may not use this file except in compliance with the License.
\r
6 * You may obtain a copy of the License at
\r
8 * http://www.apache.org/licenses/LICENSE-2.0
\r
10 * Unless required by applicable law or agreed to in writing, software
\r
11 * distributed under the License is distributed on an "AS IS" BASIS,
\r
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
\r
13 * See the License for the specific language governing permissions and
\r
14 * limitations under the License.
\r
17 package com.google.zxing.common;
\r
20 * <p>Represents a 2D matrix of bits. In function arguments below, and throughout the common
\r
21 * module, x is the column position, and y is the row position. The ordering is always x, y.
\r
22 * The origin is at the top-left.</p>
\r
24 * <p>Internally the bits are represented in a 1-D array of 32-bit ints. However, each row begins
\r
25 * with a new int. This is done intentionally so that we can copy out a row into a BitArray very
\r
28 * <p>The ordering of bits is row-major. Within each int, the least significant bits are used first,
\r
29 * meaning they represent lower x values. This is compatible with BitArray's implementation.</p>
\r
32 * @author dswitkin@google.com (Daniel Switkin)
\r
34 public final class BitMatrix {
\r
36 // TODO: Just like BitArray, these need to be public so ProGuard can inline them.
\r
37 public final int width;
\r
38 public final int height;
\r
39 public final int rowSize;
\r
40 public final int[] bits;
\r
42 // A helper to construct a square matrix.
\r
43 public BitMatrix(int dimension) {
\r
44 this(dimension, dimension);
\r
47 public BitMatrix(int width, int height) {
\r
48 if (width < 1 || height < 1) {
\r
49 throw new IllegalArgumentException("Both dimensions must be greater than 0");
\r
52 this.height = height;
\r
53 this.rowSize = (width + 31) >> 5;
\r
54 bits = new int[rowSize * height];
\r
58 * <p>Gets the requested bit, where true means black.</p>
\r
60 * @param x The horizontal component (i.e. which column)
\r
61 * @param y The vertical component (i.e. which row)
\r
62 * @return value of given bit in matrix
\r
64 public boolean get(int x, int y) {
\r
65 int offset = y * rowSize + (x >> 5);
\r
66 return ((bits[offset] >>> (x & 0x1f)) & 1) != 0;
\r
70 * <p>Sets the given bit to true.</p>
\r
72 * @param x The horizontal component (i.e. which column)
\r
73 * @param y The vertical component (i.e. which row)
\r
75 public void set(int x, int y) {
\r
76 int offset = y * rowSize + (x >> 5);
\r
77 bits[offset] |= 1 << (x & 0x1f);
\r
81 * <p>Flips the given bit.</p>
\r
83 * @param x The horizontal component (i.e. which column)
\r
84 * @param y The vertical component (i.e. which row)
\r
86 public void flip(int x, int y) {
\r
87 int offset = y * rowSize + (x >> 5);
\r
88 bits[offset] ^= 1 << (x & 0x1f);
\r
92 * Clears all bits (sets to false).
\r
94 public void clear() {
\r
95 int max = bits.length;
\r
96 for (int i = 0; i < max; i++) {
\r
102 * <p>Sets a square region of the bit matrix to true.</p>
\r
104 * @param left The horizontal position to begin at (inclusive)
\r
105 * @param top The vertical position to begin at (inclusive)
\r
106 * @param width The width of the region
\r
107 * @param height The height of the region
\r
109 public void setRegion(int left, int top, int width, int height) {
\r
110 if (top < 0 || left < 0) {
\r
111 throw new IllegalArgumentException("Left and top must be nonnegative");
\r
113 if (height < 1 || width < 1) {
\r
114 throw new IllegalArgumentException("Height and width must be at least 1");
\r
116 int right = left + width;
\r
117 int bottom = top + height;
\r
118 if (bottom > this.height || right > this.width) {
\r
119 throw new IllegalArgumentException("The region must fit inside the matrix");
\r
121 for (int y = top; y < bottom; y++) {
\r
122 int offset = y * rowSize;
\r
123 for (int x = left; x < right; x++) {
\r
124 bits[offset + (x >> 5)] |= 1 << (x & 0x1f);
\r
130 * A fast method to retrieve one row of data from the matrix as a BitArray.
\r
132 * @param y The row to retrieve
\r
133 * @param row An optional caller-allocated BitArray, will be allocated if null or too small
\r
134 * @return The resulting BitArray - this reference should always be used even when passing
\r
137 public BitArray getRow(int y, BitArray row) {
\r
138 if (row == null || row.getSize() < width) {
\r
139 row = new BitArray(width);
\r
141 int offset = y * rowSize;
\r
142 for (int x = 0; x < rowSize; x++) {
\r
143 row.setBulk(x << 5, bits[offset + x]);
\r
149 * This is useful in detecting a corner of a 'pure' barcode.
\r
151 * @return {x,y} coordinate of top-left-most 1 bit, or null if it is all white
\r
153 public int[] getTopLeftOnBit() {
\r
154 int bitsOffset = 0;
\r
155 while (bitsOffset < bits.length && bits[bitsOffset] == 0) {
\r
158 if (bitsOffset == bits.length) {
\r
161 int y = bitsOffset / rowSize;
\r
162 int x = (bitsOffset % rowSize) << 5;
\r
164 int theBits = bits[bitsOffset];
\r
166 while ((theBits << (31-bit)) == 0) {
\r
170 return new int[] {x, y};
\r
174 * @return The width of the matrix
\r
176 public int getWidth() {
\r
181 * @return The height of the matrix
\r
183 public int getHeight() {
\r
187 public boolean equals(Object o) {
\r
188 if (!(o instanceof BitMatrix)) {
\r
191 BitMatrix other = (BitMatrix) o;
\r
192 if (width != other.width || height != other.height ||
\r
193 rowSize != other.rowSize || bits.length != other.bits.length) {
\r
196 for (int i = 0; i < bits.length; i++) {
\r
197 if (bits[i] != other.bits[i]) {
\r
204 public int hashCode() {
\r
206 hash = 31 * hash + width;
\r
207 hash = 31 * hash + height;
\r
208 hash = 31 * hash + rowSize;
\r
209 for (int i = 0; i < bits.length; i++) {
\r
210 hash = 31 * hash + bits[i];
\r
215 public String toString() {
\r
216 StringBuffer result = new StringBuffer(height * (width + 1));
\r
217 for (int y = 0; y < height; y++) {
\r
218 for (int x = 0; x < width; x++) {
\r
219 result.append(get(x, y) ? "X " : " ");
\r
221 result.append('\n');
\r
223 return result.toString();
\r