core/src/com/google/zxing/common/BitArray.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>A simple, fast array of bits, represented compactly by an array of ints internally.</p>\r
  21  *\r
  22  * @author Sean Owen\r
  23  */\r
  24 public final class BitArray {\r
  25 \r
  26   // TODO: I have changed these members to be public so ProGuard can inline get() and set(). Ideally\r
  27   // they'd be private and we'd use the -allowaccessmodification flag, but Dalvik rejects the\r
  28   // resulting binary at runtime on Android. If we find a solution to this, these should be changed\r
  29   // back to private.\r
  30   public int[] bits;\r
  31   public final int size;\r
  32 \r
  33   public BitArray(int size) {\r
  34     if (size < 1) {\r
  35       throw new IllegalArgumentException("size must be at least 1");\r
  36     }\r
  37     this.size = size;\r
  38     this.bits = makeArray(size);\r
  39   }\r
  40 \r
  41   public int getSize() {\r
  42     return size;\r
  43   }\r
  44 \r
  45   /**\r
  46    * @param i bit to get\r
  47    * @return true iff bit i is set\r
  48    */\r
  49   public boolean get(int i) {\r
  50     return (bits[i >> 5] & (1 << (i & 0x1F))) != 0;\r
  51   }\r
  52 \r
  53   /**\r
  54    * Sets bit i.\r
  55    *\r
  56    * @param i bit to set\r
  57    */\r
  58   public void set(int i) {\r
  59     bits[i >> 5] |= 1 << (i & 0x1F);\r
  60   }\r
  61 \r
  62   /**\r
  63    * Flips bit i.\r
  64    *\r
  65    * @param i bit to set\r
  66    */\r
  67   public void flip(int i) {\r
  68     bits[i >> 5] ^= 1 << (i & 0x1F);\r
  69   }\r
  70 \r
  71   /**\r
  72    * Sets a block of 32 bits, starting at bit i.\r
  73    *\r
  74    * @param i first bit to set\r
  75    * @param newBits the new value of the next 32 bits. Note again that the least-significant bit\r
  76    * corresponds to bit i, the next-least-significant to i+1, and so on.\r
  77    */\r
  78   public void setBulk(int i, int newBits) {\r
  79     bits[i >> 5] = newBits;\r
  80   }\r
  81 \r
  82   /**\r
  83    * Clears all bits (sets to false).\r
  84    */\r
  85   public void clear() {\r
  86     int max = bits.length;\r
  87     for (int i = 0; i < max; i++) {\r
  88       bits[i] = 0;\r
  89     }\r
  90   }\r
  91 \r
  92   /**\r
  93    * Efficient method to check if a range of bits is set, or not set.\r
  94    *\r
  95    * @param start start of range, inclusive.\r
  96    * @param end end of range, exclusive\r
  97    * @param value if true, checks that bits in range are set, otherwise checks that they are not set\r
  98    * @return true iff all bits are set or not set in range, according to value argument\r
  99    * @throws IllegalArgumentException if end is less than or equal to start\r
 100    */\r
 101   public boolean isRange(int start, int end, boolean value) {\r
 102     if (end < start) {\r
 103       throw new IllegalArgumentException();\r
 104     }\r
 105     if (end == start) {\r
 106       return true; // empty range matches\r
 107     }\r
 108     end--; // will be easier to treat this as the last actually set bit -- inclusive    \r
 109     int firstInt = start >> 5;\r
 110     int lastInt = end >> 5;\r
 111     for (int i = firstInt; i <= lastInt; i++) {\r
 112       int firstBit = i > firstInt ? 0 : start & 0x1F;\r
 113       int lastBit = i < lastInt ? 31 : end & 0x1F;\r
 114       int mask;\r
 115       if (firstBit == 0 && lastBit == 31) {\r
 116         mask = -1;\r
 117       } else {\r
 118         mask = 0;\r
 119         for (int j = firstBit; j <= lastBit; j++) {\r
 120           mask |= 1 << j;\r
 121         }\r
 122       }\r
 123 \r
 124       // Return false if we're looking for 1s and the masked bits[i] isn't all 1s (that is,\r
 125       // equals the mask, or we're looking for 0s and the masked portion is not all 0s\r
 126       if ((bits[i] & mask) != (value ? mask : 0)) {\r
 127         return false;\r
 128       }\r
 129     }\r
 130     return true;\r
 131   }\r
 132 \r
 133   /**\r
 134    * @return underlying array of ints. The first element holds the first 32 bits, and the least\r
 135    *         significant bit is bit 0.\r
 136    */\r
 137   public int[] getBitArray() {\r
 138     return bits;\r
 139   }\r
 140 \r
 141   /**\r
 142    * Reverses all bits in the array.\r
 143    */\r
 144   public void reverse() {\r
 145     int[] newBits = new int[bits.length];\r
 146     int size = this.size;\r
 147     for (int i = 0; i < size; i++) {\r
 148       if (get(size - i - 1)) {\r
 149         newBits[i >> 5] |= 1 << (i & 0x1F);\r
 150       }\r
 151     }\r
 152     bits = newBits;\r
 153   }\r
 154 \r
 155   private static int[] makeArray(int size) {\r
 156     int arraySize = size >> 5;\r
 157     if ((size & 0x1F) != 0) {\r
 158       arraySize++;\r
 159     }\r
 160     return new int[arraySize];\r
 161   }\r
 162   \r
 163   public String toString() {\r
 164     StringBuffer result = new StringBuffer(size);\r
 165     for (int i = 0; i < size; i++) {\r
 166       if ((i & 0x07) == 0) {\r
 167         result.append(' ');\r
 168       }\r
 169       result.append(get(i) ? 'X' : '.');\r
 170     }\r
 171     return result.toString();\r
 172   }\r
 173 \r
 174 }