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    * Sets a block of 32 bits, starting at bit i.\r
  64    *\r
  65    * @param i first bit to set\r
  66    * @param newBits the new value of the next 32 bits. Note again that the least-significant bit\r
  67    * corresponds to bit i, the next-least-significant to i+1, and so on.\r
  68    */\r
  69   public void setBulk(int i, int newBits) {\r
  70     bits[i >> 5] = newBits;\r
  71   }\r
  72 \r
  73   /**\r
  74    * Clears all bits (sets to false).\r
  75    */\r
  76   public void clear() {\r
  77     int max = bits.length;\r
  78     for (int i = 0; i < max; i++) {\r
  79       bits[i] = 0;\r
  80     }\r
  81   }\r
  82 \r
  83   /**\r
  84    * Efficient method to check if a range of bits is set, or not set.\r
  85    *\r
  86    * @param start start of range, inclusive.\r
  87    * @param end end of range, exclusive\r
  88    * @param value if true, checks that bits in range are set, otherwise checks that they are not set\r
  89    * @return true iff all bits are set or not set in range, according to value argument\r
  90    * @throws IllegalArgumentException if end is less than or equal to start\r
  91    */\r
  92   public boolean isRange(int start, int end, boolean value) {\r
  93     if (end < start) {\r
  94       throw new IllegalArgumentException();\r
  95     }\r
  96     if (end == start) {\r
  97       return true; // empty range matches\r
  98     }\r
  99     end--; // will be easier to treat this as the last actually set bit -- inclusive    \r
 100     int firstInt = start >> 5;\r
 101     int lastInt = end >> 5;\r
 102     for (int i = firstInt; i <= lastInt; i++) {\r
 103       int firstBit = i > firstInt ? 0 : start & 0x1F;\r
 104       int lastBit = i < lastInt ? 31 : end & 0x1F;\r
 105       int mask;\r
 106       if (firstBit == 0 && lastBit == 31) {\r
 107         mask = -1;\r
 108       } else {\r
 109         mask = 0;\r
 110         for (int j = firstBit; j <= lastBit; j++) {\r
 111           mask |= 1 << j;\r
 112         }\r
 113       }\r
 114 \r
 115       // Return false if we're looking for 1s and the masked bits[i] isn't all 1s (that is,\r
 116       // equals the mask, or we're looking for 0s and the masked portion is not all 0s\r
 117       if ((bits[i] & mask) != (value ? mask : 0)) {\r
 118         return false;\r
 119       }\r
 120     }\r
 121     return true;\r
 122   }\r
 123 \r
 124   /**\r
 125    * @return underlying array of ints. The first element holds the first 32 bits, and the least\r
 126    *         significant bit is bit 0.\r
 127    */\r
 128   public int[] getBitArray() {\r
 129     return bits;\r
 130   }\r
 131 \r
 132   /**\r
 133    * Reverses all bits in the array.\r
 134    */\r
 135   public void reverse() {\r
 136     int[] newBits = new int[bits.length];\r
 137     int size = this.size;\r
 138     for (int i = 0; i < size; i++) {\r
 139       if (get(size - i - 1)) {\r
 140         newBits[i >> 5] |= 1 << (i & 0x1F);\r
 141       }\r
 142     }\r
 143     bits = newBits;\r
 144   }\r
 145 \r
 146   private static int[] makeArray(int size) {\r
 147     int arraySize = size >> 5;\r
 148     if ((size & 0x1F) != 0) {\r
 149       arraySize++;\r
 150     }\r
 151     return new int[arraySize];\r
 152   }\r
 153   \r
 154   public String toString() {\r
 155     StringBuffer result = new StringBuffer(size);\r
 156     for (int i = 0; i < size; i++) {\r
 157       if ((i & 0x07) == 0) {\r
 158         result.append(' ');\r
 159       }\r
 160       result.append(get(i) ? 'X' : '.');\r
 161     }\r
 162     return result.toString();\r
 163   }\r
 164 \r
 165 }