Pileus Git - ~andy/freeotp/blob - src/com/google/zxing/common/BitMatrix.java

   1 /*
   2  * Copyright 2007 ZXing authors
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package com.google.zxing.common;
  18
  19 /**
  20  * <p>Represents a 2D matrix of bits. In function arguments below, and throughout the common
  21  * module, x is the column position, and y is the row position. The ordering is always x, y.
  22  * The origin is at the top-left.</p>
  23  *
  24  * <p>Internally the bits are represented in a 1-D array of 32-bit ints. However, each row begins
  25  * with a new int. This is done intentionally so that we can copy out a row into a BitArray very
  26  * efficiently.</p>
  27  *
  28  * <p>The ordering of bits is row-major. Within each int, the least significant bits are used first,
  29  * meaning they represent lower x values. This is compatible with BitArray's implementation.</p>
  30  *
  31  * @author Sean Owen
  32  * @author dswitkin@google.com (Daniel Switkin)
  33  */
  34 public final class BitMatrix {
  35
  36   private final int width;
  37   private final int height;
  38   private final int rowSize;
  39   private final int[] bits;
  40
  41   // A helper to construct a square matrix.
  42   public BitMatrix(int dimension) {
  43     this(dimension, dimension);
  44   }
  45
  46   public BitMatrix(int width, int height) {
  47     if (width < 1 || height < 1) {
  48       throw new IllegalArgumentException("Both dimensions must be greater than 0");
  49     }
  50     this.width = width;
  51     this.height = height;
  52     this.rowSize = (width + 31) >> 5;
  53     bits = new int[rowSize * height];
  54   }
  55
  56   /**
  57    * <p>Gets the requested bit, where true means black.</p>
  58    *
  59    * @param x The horizontal component (i.e. which column)
  60    * @param y The vertical component (i.e. which row)
  61    * @return value of given bit in matrix
  62    */
  63   public boolean get(int x, int y) {
  64     int offset = y * rowSize + (x >> 5);
  65     return ((bits[offset] >>> (x & 0x1f)) & 1) != 0;
  66   }
  67
  68   /**
  69    * <p>Sets the given bit to true.</p>
  70    *
  71    * @param x The horizontal component (i.e. which column)
  72    * @param y The vertical component (i.e. which row)
  73    */
  74   public void set(int x, int y) {
  75     int offset = y * rowSize + (x >> 5);
  76     bits[offset] |= 1 << (x & 0x1f);
  77   }
  78
  79   /**
  80    * <p>Flips the given bit.</p>
  81    *
  82    * @param x The horizontal component (i.e. which column)
  83    * @param y The vertical component (i.e. which row)
  84    */
  85   public void flip(int x, int y) {
  86     int offset = y * rowSize + (x >> 5);
  87     bits[offset] ^= 1 << (x & 0x1f);
  88   }
  89
  90   /**
  91    * Clears all bits (sets to false).
  92    */
  93   public void clear() {
  94     int max = bits.length;
  95     for (int i = 0; i < max; i++) {
  96       bits[i] = 0;
  97     }
  98   }
  99
 100   /**
 101    * <p>Sets a square region of the bit matrix to true.</p>
 102    *
 103    * @param left The horizontal position to begin at (inclusive)
 104    * @param top The vertical position to begin at (inclusive)
 105    * @param width The width of the region
 106    * @param height The height of the region
 107    */
 108   public void setRegion(int left, int top, int width, int height) {
 109     if (top < 0 || left < 0) {
 110       throw new IllegalArgumentException("Left and top must be nonnegative");
 111     }
 112     if (height < 1 || width < 1) {
 113       throw new IllegalArgumentException("Height and width must be at least 1");
 114     }
 115     int right = left + width;
 116     int bottom = top + height;
 117     if (bottom > this.height || right > this.width) {
 118       throw new IllegalArgumentException("The region must fit inside the matrix");
 119     }
 120     for (int y = top; y < bottom; y++) {
 121       int offset = y * rowSize;
 122       for (int x = left; x < right; x++) {
 123         bits[offset + (x >> 5)] |= 1 << (x & 0x1f);
 124       }
 125     }
 126   }
 127
 128   /**
 129    * A fast method to retrieve one row of data from the matrix as a BitArray.
 130    *
 131    * @param y The row to retrieve
 132    * @param row An optional caller-allocated BitArray, will be allocated if null or too small
 133    * @return The resulting BitArray - this reference should always be used even when passing
 134    *         your own row
 135    */
 136   public BitArray getRow(int y, BitArray row) {
 137     if (row == null || row.getSize() < width) {
 138       row = new BitArray(width);
 139     }
 140     int offset = y * rowSize;
 141     for (int x = 0; x < rowSize; x++) {
 142       row.setBulk(x << 5, bits[offset + x]);
 143     }
 144     return row;
 145   }
 146
 147   /**
 148    * @param y row to set
 149    * @param row {@link BitArray} to copy from
 150    */
 151   public void setRow(int y, BitArray row) {
 152     System.arraycopy(row.getBitArray(), 0, bits, y * rowSize, rowSize);
 153   }
 154
 155   /**
 156    * This is useful in detecting the enclosing rectangle of a 'pure' barcode.
 157    *
 158    * @return {left,top,width,height} enclosing rectangle of all 1 bits, or null if it is all white
 159    */
 160   public int[] getEnclosingRectangle() {
 161     int left = width;
 162     int top = height;
 163     int right = -1;
 164     int bottom = -1;
 165
 166     for (int y = 0; y < height; y++) {
 167       for (int x32 = 0; x32 < rowSize; x32++) {
 168         int theBits = bits[y * rowSize + x32];
 169         if (theBits != 0) {
 170           if (y < top) {
 171             top = y;
 172           }
 173           if (y > bottom) {
 174             bottom = y;
 175           }
 176           if (x32 * 32 < left) {
 177             int bit = 0;
 178             while ((theBits << (31 - bit)) == 0) {
 179               bit++;
 180             }
 181             if ((x32 * 32 + bit) < left) {
 182               left = x32 * 32 + bit;
 183             }
 184           }
 185           if (x32 * 32 + 31 > right) {
 186             int bit = 31;
 187             while ((theBits >>> bit) == 0) {
 188               bit--;
 189             }
 190             if ((x32 * 32 + bit) > right) {
 191               right = x32 * 32 + bit;
 192             }
 193           }
 194         }
 195       }
 196     }
 197
 198     int width = right - left;
 199     int height = bottom - top;
 200
 201     if (width < 0 || height < 0) {
 202       return null;
 203     }
 204
 205     return new int[] {left, top, width, height};
 206   }
 207
 208   /**
 209    * This is useful in detecting a corner of a 'pure' barcode.
 210    *
 211    * @return {x,y} coordinate of top-left-most 1 bit, or null if it is all white
 212    */
 213   public int[] getTopLeftOnBit() {
 214     int bitsOffset = 0;
 215     while (bitsOffset < bits.length && bits[bitsOffset] == 0) {
 216       bitsOffset++;
 217     }
 218     if (bitsOffset == bits.length) {
 219       return null;
 220     }
 221     int y = bitsOffset / rowSize;
 222     int x = (bitsOffset % rowSize) << 5;
 223
 224     int theBits = bits[bitsOffset];
 225     int bit = 0;
 226     while ((theBits << (31-bit)) == 0) {
 227       bit++;
 228     }
 229     x += bit;
 230     return new int[] {x, y};
 231   }
 232
 233   public int[] getBottomRightOnBit() {
 234     int bitsOffset = bits.length - 1;
 235     while (bitsOffset >= 0 && bits[bitsOffset] == 0) {
 236       bitsOffset--;
 237     }
 238     if (bitsOffset < 0) {
 239       return null;
 240     }
 241
 242     int y = bitsOffset / rowSize;
 243     int x = (bitsOffset % rowSize) << 5;
 244
 245     int theBits = bits[bitsOffset];
 246     int bit = 31;
 247     while ((theBits >>> bit) == 0) {
 248       bit--;
 249     }
 250     x += bit;
 251
 252     return new int[] {x, y};
 253   }
 254
 255   /**
 256    * @return The width of the matrix
 257    */
 258   public int getWidth() {
 259     return width;
 260   }
 261
 262   /**
 263    * @return The height of the matrix
 264    */
 265   public int getHeight() {
 266     return height;
 267   }
 268
 269   @Override
 270   public boolean equals(Object o) {
 271     if (!(o instanceof BitMatrix)) {
 272       return false;
 273     }
 274     BitMatrix other = (BitMatrix) o;
 275     if (width != other.width || height != other.height ||
 276         rowSize != other.rowSize || bits.length != other.bits.length) {
 277       return false;
 278     }
 279     for (int i = 0; i < bits.length; i++) {
 280       if (bits[i] != other.bits[i]) {
 281         return false;
 282       }
 283     }
 284     return true;
 285   }
 286
 287   @Override
 288   public int hashCode() {
 289     int hash = width;
 290     hash = 31 * hash + width;
 291     hash = 31 * hash + height;
 292     hash = 31 * hash + rowSize;
 293     for (int bit : bits) {
 294       hash = 31 * hash + bit;
 295     }
 296     return hash;
 297   }
 298
 299   @Override
 300   public String toString() {
 301     StringBuilder result = new StringBuilder(height * (width + 1));
 302     for (int y = 0; y < height; y++) {
 303       for (int x = 0; x < width; x++) {
 304         result.append(get(x, y) ? "X " : "  ");
 305       }
 306       result.append('\n');
 307     }
 308     return result.toString();
 309   }
 310
 311 }