package com.google.zxing.common;\r
\r
/**\r
- * <p>Represents a square matrix of bits. In function arguments below, and throughout the common\r
+ * <p>Represents a 2D matrix of bits. In function arguments below, and throughout the common\r
* module, x is the column position, and y is the row position. The ordering is always x, y.\r
* The origin is at the top-left.</p>\r
*\r
- * <p>Internally the bits are represented in a compact 1-D array of 32-bit ints.\r
- * The ordering of bits is row-major. Within each int, the least significant bits are used first,\r
+ * <p>Internally the bits are represented in a 1-D array of 32-bit ints. However, each row begins\r
+ * with a new int. This is done intentionally so that we can copy out a row into a BitArray very\r
+ * efficiently.</p>\r
+ *\r
+ * <p>The ordering of bits is row-major. Within each int, the least significant bits are used first,\r
* meaning they represent lower x values. This is compatible with BitArray's implementation.</p>\r
*\r
* @author Sean Owen\r
*/\r
public final class BitMatrix {\r
\r
- private final int dimension;\r
- private final int[] bits;\r
+ // TODO: Just like BitArray, these need to be public so ProGuard can inline them.\r
+ public final int width;\r
+ public final int height;\r
+ public final int rowSize;\r
+ public final int[] bits;\r
\r
+ // A helper to construct a square matrix.\r
public BitMatrix(int dimension) {\r
- if (dimension < 1) {\r
- throw new IllegalArgumentException("dimension must be at least 1");\r
- }\r
- this.dimension = dimension;\r
- int numBits = dimension * dimension;\r
- int arraySize = numBits >> 5; // one int per 32 bits\r
- if ((numBits & 0x1F) != 0) { // plus one more if there are leftovers\r
- arraySize++;\r
+ this(dimension, dimension);\r
+ }\r
+\r
+ public BitMatrix(int width, int height) {\r
+ if (width < 1 || height < 1) {\r
+ throw new IllegalArgumentException("Both dimensions must be greater than 0");\r
}\r
- bits = new int[arraySize];\r
+ this.width = width;\r
+ this.height = height;\r
+ this.rowSize = (width + 31) >> 5;\r
+ bits = new int[rowSize * height];\r
}\r
\r
/**\r
* @return value of given bit in matrix\r
*/\r
public boolean get(int x, int y) {\r
- int offset = y * dimension + x;\r
- return ((bits[offset >> 5] >>> (offset & 0x1F)) & 0x01) != 0;\r
+ int offset = y * rowSize + (x >> 5);\r
+ return ((bits[offset] >>> (x & 0x1f)) & 1) != 0;\r
}\r
\r
/**\r
* @param y The vertical component (i.e. which row)\r
*/\r
public void set(int x, int y) {\r
- int offset = y * dimension + x;\r
- bits[offset >> 5] |= 1 << (offset & 0x1F);\r
+ int offset = y * rowSize + (x >> 5);\r
+ bits[offset] |= 1 << (x & 0x1f);\r
}\r
\r
/**\r
* @param y The vertical component (i.e. which row)\r
*/\r
public void flip(int x, int y) {\r
- int offset = y * dimension + x;\r
- bits[offset >> 5] ^= 1 << (offset & 0x1F);\r
+ int offset = y * rowSize + (x >> 5);\r
+ bits[offset] ^= 1 << (x & 0x1f);\r
+ }\r
+\r
+ /**\r
+ * Clears all bits (sets to false).\r
+ */\r
+ public void clear() {\r
+ int max = bits.length;\r
+ for (int i = 0; i < max; i++) {\r
+ bits[i] = 0;\r
+ }\r
}\r
\r
/**\r
*/\r
public void setRegion(int left, int top, int width, int height) {\r
if (top < 0 || left < 0) {\r
- throw new IllegalArgumentException("left and top must be nonnegative");\r
+ throw new IllegalArgumentException("Left and top must be nonnegative");\r
}\r
if (height < 1 || width < 1) {\r
- throw new IllegalArgumentException("height and width must be at least 1");\r
+ throw new IllegalArgumentException("Height and width must be at least 1");\r
}\r
int right = left + width;\r
int bottom = top + height;\r
- if (bottom > dimension || right > dimension) {\r
- throw new IllegalArgumentException(\r
- "top + height and left + width must be <= matrix dimension");\r
+ if (bottom > this.height || right > this.width) {\r
+ throw new IllegalArgumentException("The region must fit inside the matrix");\r
}\r
for (int y = top; y < bottom; y++) {\r
- int yoffset = dimension * y;\r
+ int offset = y * rowSize;\r
for (int x = left; x < right; x++) {\r
- int xoffset = yoffset + x;\r
- bits[xoffset >> 5] |= 1 << (xoffset & 0x1F);\r
+ bits[offset + (x >> 5)] |= 1 << (x & 0x1f);\r
}\r
}\r
}\r
\r
/**\r
- * @return row/column dimension of this matrix\r
+ * A fast method to retrieve one row of data from the matrix as a BitArray.\r
+ *\r
+ * @param y The row to retrieve\r
+ * @param row An optional caller-allocated BitArray, will be allocated if null or too small\r
+ * @return The resulting BitArray - this reference should always be used even when passing\r
+ * your own row\r
+ */\r
+ public BitArray getRow(int y, BitArray row) {\r
+ if (row == null || row.getSize() < width) {\r
+ row = new BitArray(width);\r
+ }\r
+ int offset = y * rowSize;\r
+ for (int x = 0; x < rowSize; x++) {\r
+ row.setBulk(x << 5, bits[offset + x]);\r
+ }\r
+ return row;\r
+ }\r
+\r
+ /**\r
+ * This is useful in detecting a corner of a 'pure' barcode.\r
+ * \r
+ * @return {x,y} coordinate of top-left-most 1 bit, or null if it is all white\r
+ */\r
+ public int[] getTopLeftOnBit() {\r
+ int bitsOffset = 0;\r
+ while (bitsOffset < bits.length && bits[bitsOffset] == 0) {\r
+ bitsOffset++;\r
+ }\r
+ if (bitsOffset == bits.length) {\r
+ return null;\r
+ }\r
+ int y = bitsOffset / rowSize;\r
+ int x = (bitsOffset % rowSize) << 5;\r
+ \r
+ int theBits = bits[bitsOffset];\r
+ int bit = 0;\r
+ while ((theBits << (31-bit)) == 0) {\r
+ bit++;\r
+ }\r
+ x += bit;\r
+ return new int[] {x, y};\r
+ }\r
+\r
+ /**\r
+ * @return The width of the matrix\r
+ */\r
+ public int getWidth() {\r
+ return width;\r
+ }\r
+\r
+ /**\r
+ * @return The height of the matrix\r
*/\r
- public int getDimension() {\r
- return dimension;\r
+ public int getHeight() {\r
+ return height;\r
+ }\r
+\r
+ public boolean equals(Object o) {\r
+ if (!(o instanceof BitMatrix)) {\r
+ return false;\r
+ }\r
+ BitMatrix other = (BitMatrix) o;\r
+ if (width != other.width || height != other.height ||\r
+ rowSize != other.rowSize || bits.length != other.bits.length) {\r
+ return false;\r
+ }\r
+ for (int i = 0; i < bits.length; i++) {\r
+ if (bits[i] != other.bits[i]) {\r
+ return false;\r
+ }\r
+ }\r
+ return true;\r
+ }\r
+\r
+ public int hashCode() {\r
+ int hash = width;\r
+ hash = 31 * hash + width;\r
+ hash = 31 * hash + height;\r
+ hash = 31 * hash + rowSize;\r
+ for (int i = 0; i < bits.length; i++) {\r
+ hash = 31 * hash + bits[i];\r
+ }\r
+ return hash;\r
}\r
\r
public String toString() {\r
- StringBuffer result = new StringBuffer(dimension * (dimension + 1));\r
- for (int y = 0; y < dimension; y++) {\r
- for (int x = 0; x < dimension; x++) {\r
+ StringBuffer result = new StringBuffer(height * (width + 1));\r
+ for (int y = 0; y < height; y++) {\r
+ for (int x = 0; x < width; x++) {\r
result.append(get(x, y) ? "X " : " ");\r
}\r
result.append('\n');\r