core/src/com/google/zxing/common/BitMatrix.java

   1 /*\r
   2  * Copyright 2007 ZXing authors\r
   3  *\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
   7  *\r
   8  *      http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\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
  15  */\r
  16 \r
  17 package com.google.zxing.common;\r
  18 \r
  19 /**\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
  23  *\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
  26  * efficiently.</p>\r
  27  *\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
  30  *\r
  31  * @author Sean Owen\r
  32  * @author dswitkin@google.com (Daniel Switkin)\r
  33  */\r
  34 public final class BitMatrix {\r
  35 \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
  41 \r
  42   // A helper to construct a square matrix.\r
  43   public BitMatrix(int dimension) {\r
  44     this(dimension, dimension);\r
  45   }\r
  46 \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
  50     }\r
  51     this.width = width;\r
  52     this.height = height;\r
  53     this.rowSize = (width + 31) >> 5;\r
  54     bits = new int[rowSize * height];\r
  55   }\r
  56 \r
  57   /**\r
  58    * <p>Gets the requested bit, where true means black.</p>\r
  59    *\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
  63    */\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
  67   }\r
  68 \r
  69   /**\r
  70    * <p>Sets the given bit to true.</p>\r
  71    *\r
  72    * @param x The horizontal component (i.e. which column)\r
  73    * @param y The vertical component (i.e. which row)\r
  74    */\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
  78   }\r
  79 \r
  80   /**\r
  81    * <p>Flips the given bit.</p>\r
  82    *\r
  83    * @param x The horizontal component (i.e. which column)\r
  84    * @param y The vertical component (i.e. which row)\r
  85    */\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
  89   }\r
  90 \r
  91   /**\r
  92    * Clears all bits (sets to false).\r
  93    */\r
  94   public void clear() {\r
  95     int max = bits.length;\r
  96     for (int i = 0; i < max; i++) {\r
  97       bits[i] = 0;\r
  98     }\r
  99   }\r
 100 \r
 101   /**\r
 102    * <p>Sets a square region of the bit matrix to true.</p>\r
 103    *\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
 108    */\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
 112     }\r
 113     if (height < 1 || width < 1) {\r
 114       throw new IllegalArgumentException("Height and width must be at least 1");\r
 115     }\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
 120     }\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
 125       }\r
 126     }\r
 127   }\r
 128 \r
 129   /**\r
 130    * A fast method to retrieve one row of data from the matrix as a BitArray.\r
 131    *\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
 135    *         your own row\r
 136    */\r
 137   public BitArray getRow(int y, BitArray row) {\r
 138     if (row == null || row.getSize() < width) {\r
 139       row = new BitArray(width);\r
 140     }\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
 144     }\r
 145     return row;\r
 146   }\r
 147 \r
 148   /**\r
 149    * This is useful in detecting a corner of a 'pure' barcode.\r
 150    * \r
 151    * @return {x,y} coordinate of top-left-most 1 bit, or null if it is all white\r
 152    */\r
 153   public int[] getTopLeftOnBit() {\r
 154     int bitsOffset = 0;\r
 155     while (bitsOffset < bits.length && bits[bitsOffset] == 0) {\r
 156       bitsOffset++;\r
 157     }\r
 158     if (bitsOffset == bits.length) {\r
 159       return null;\r
 160     }\r
 161     int y = bitsOffset / rowSize;\r
 162     int x = (bitsOffset % rowSize) << 5;\r
 163     \r
 164     int theBits = bits[bitsOffset];\r
 165     int bit = 0;\r
 166     while ((theBits << (31-bit)) == 0) {\r
 167       bit++;\r
 168     }\r
 169     x += bit;\r
 170     return new int[] {x, y};\r
 171   }\r
 172 \r
 173   /**\r
 174    * @return The width of the matrix\r
 175    */\r
 176   public int getWidth() {\r
 177     return width;\r
 178   }\r
 179 \r
 180   /**\r
 181    * @return The height of the matrix\r
 182    */\r
 183   public int getHeight() {\r
 184     return height;\r
 185   }\r
 186 \r
 187   public boolean equals(Object o) {\r
 188     if (!(o instanceof BitMatrix)) {\r
 189       return false;\r
 190     }\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
 194       return false;\r
 195     }\r
 196     for (int i = 0; i < bits.length; i++) {\r
 197       if (bits[i] != other.bits[i]) {\r
 198         return false;\r
 199       }\r
 200     }\r
 201     return true;\r
 202   }\r
 203 \r
 204   public int hashCode() {\r
 205     int hash = width;\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
 211     }\r
 212     return hash;\r
 213   }\r
 214 \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
 220       }\r
 221       result.append('\n');\r
 222     }\r
 223     return result.toString();\r
 224   }\r
 225 \r
 226 }\r