Pileus Git - ~andy/freeotp/blob - src/com/google/zxing/common/BitArray.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>A simple, fast array of bits, represented compactly by an array of ints internally.</p>
  21  *
  22  * @author Sean Owen
  23  */
  24 public final class BitArray {
  25
  26   private int[] bits;
  27   private int size;
  28
  29   public BitArray() {
  30     this.size = 0;
  31     this.bits = new int[1];
  32   }
  33
  34   public BitArray(int size) {
  35     this.size = size;
  36     this.bits = makeArray(size);
  37   }
  38
  39   // For testing only
  40   BitArray(int[] bits, int size) {
  41     this.bits = bits;
  42     this.size = size;
  43   }
  44
  45   public int getSize() {
  46     return size;
  47   }
  48
  49   public int getSizeInBytes() {
  50     return (size + 7) / 8;
  51   }
  52
  53   private void ensureCapacity(int size) {
  54     if (size > bits.length * 32) {
  55       int[] newBits = makeArray(size);
  56       System.arraycopy(bits, 0, newBits, 0, bits.length);
  57       this.bits = newBits;
  58     }
  59   }
  60
  61   /**
  62    * @param i bit to get
  63    * @return true iff bit i is set
  64    */
  65   public boolean get(int i) {
  66     return (bits[i / 32] & (1 << (i & 0x1F))) != 0;
  67   }
  68
  69   /**
  70    * Sets bit i.
  71    *
  72    * @param i bit to set
  73    */
  74   public void set(int i) {
  75     bits[i / 32] |= 1 << (i & 0x1F);
  76   }
  77
  78   /**
  79    * Flips bit i.
  80    *
  81    * @param i bit to set
  82    */
  83   public void flip(int i) {
  84     bits[i / 32] ^= 1 << (i & 0x1F);
  85   }
  86
  87   /**
  88    * @param from first bit to check
  89    * @return index of first bit that is set, starting from the given index, or size if none are set
  90    *  at or beyond this given index
  91    * @see #getNextUnset(int)
  92    */
  93   public int getNextSet(int from) {
  94     if (from >= size) {
  95       return size;
  96     }
  97     int bitsOffset = from / 32;
  98     int currentBits = bits[bitsOffset];
  99     // mask off lesser bits first
 100     currentBits &= ~((1 << (from & 0x1F)) - 1);
 101     while (currentBits == 0) {
 102       if (++bitsOffset == bits.length) {
 103         return size;
 104       }
 105       currentBits = bits[bitsOffset];
 106     }
 107     int result = (bitsOffset * 32) + Integer.numberOfTrailingZeros(currentBits);
 108     return result > size ? size : result;
 109   }
 110
 111   /**
 112    * @see #getNextSet(int)
 113    */
 114   public int getNextUnset(int from) {
 115     if (from >= size) {
 116       return size;
 117     }
 118     int bitsOffset = from / 32;
 119     int currentBits = ~bits[bitsOffset];
 120     // mask off lesser bits first
 121     currentBits &= ~((1 << (from & 0x1F)) - 1);
 122     while (currentBits == 0) {
 123       if (++bitsOffset == bits.length) {
 124         return size;
 125       }
 126       currentBits = ~bits[bitsOffset];
 127     }
 128     int result = (bitsOffset * 32) + Integer.numberOfTrailingZeros(currentBits);
 129     return result > size ? size : result;
 130   }
 131
 132   /**
 133    * Sets a block of 32 bits, starting at bit i.
 134    *
 135    * @param i first bit to set
 136    * @param newBits the new value of the next 32 bits. Note again that the least-significant bit
 137    * corresponds to bit i, the next-least-significant to i+1, and so on.
 138    */
 139   public void setBulk(int i, int newBits) {
 140     bits[i / 32] = newBits;
 141   }
 142
 143   /**
 144    * Sets a range of bits.
 145    *
 146    * @param start start of range, inclusive.
 147    * @param end end of range, exclusive
 148    */
 149   public void setRange(int start, int end) {
 150     if (end < start) {
 151       throw new IllegalArgumentException();
 152     }
 153     if (end == start) {
 154       return;
 155     }
 156     end--; // will be easier to treat this as the last actually set bit -- inclusive
 157     int firstInt = start / 32;
 158     int lastInt = end / 32;
 159     for (int i = firstInt; i <= lastInt; i++) {
 160       int firstBit = i > firstInt ? 0 : start & 0x1F;
 161       int lastBit = i < lastInt ? 31 : end & 0x1F;
 162       int mask;
 163       if (firstBit == 0 && lastBit == 31) {
 164         mask = -1;
 165       } else {
 166         mask = 0;
 167         for (int j = firstBit; j <= lastBit; j++) {
 168           mask |= 1 << j;
 169         }
 170       }
 171       bits[i] |= mask;
 172     }
 173   }
 174
 175   /**
 176    * Clears all bits (sets to false).
 177    */
 178   public void clear() {
 179     int max = bits.length;
 180     for (int i = 0; i < max; i++) {
 181       bits[i] = 0;
 182     }
 183   }
 184
 185   /**
 186    * Efficient method to check if a range of bits is set, or not set.
 187    *
 188    * @param start start of range, inclusive.
 189    * @param end end of range, exclusive
 190    * @param value if true, checks that bits in range are set, otherwise checks that they are not set
 191    * @return true iff all bits are set or not set in range, according to value argument
 192    * @throws IllegalArgumentException if end is less than or equal to start
 193    */
 194   public boolean isRange(int start, int end, boolean value) {
 195     if (end < start) {
 196       throw new IllegalArgumentException();
 197     }
 198     if (end == start) {
 199       return true; // empty range matches
 200     }
 201     end--; // will be easier to treat this as the last actually set bit -- inclusive
 202     int firstInt = start / 32;
 203     int lastInt = end / 32;
 204     for (int i = firstInt; i <= lastInt; i++) {
 205       int firstBit = i > firstInt ? 0 : start & 0x1F;
 206       int lastBit = i < lastInt ? 31 : end & 0x1F;
 207       int mask;
 208       if (firstBit == 0 && lastBit == 31) {
 209         mask = -1;
 210       } else {
 211         mask = 0;
 212         for (int j = firstBit; j <= lastBit; j++) {
 213           mask |= 1 << j;
 214         }
 215       }
 216
 217       // Return false if we're looking for 1s and the masked bits[i] isn't all 1s (that is,
 218       // equals the mask, or we're looking for 0s and the masked portion is not all 0s
 219       if ((bits[i] & mask) != (value ? mask : 0)) {
 220         return false;
 221       }
 222     }
 223     return true;
 224   }
 225
 226   public void appendBit(boolean bit) {
 227     ensureCapacity(size + 1);
 228     if (bit) {
 229       bits[size / 32] |= 1 << (size & 0x1F);
 230     }
 231     size++;
 232   }
 233
 234   /**
 235    * Appends the least-significant bits, from value, in order from most-significant to
 236    * least-significant. For example, appending 6 bits from 0x000001E will append the bits
 237    * 0, 1, 1, 1, 1, 0 in that order.
 238    */
 239   public void appendBits(int value, int numBits) {
 240     if (numBits < 0 || numBits > 32) {
 241       throw new IllegalArgumentException("Num bits must be between 0 and 32");
 242     }
 243     ensureCapacity(size + numBits);
 244     for (int numBitsLeft = numBits; numBitsLeft > 0; numBitsLeft--) {
 245       appendBit(((value >> (numBitsLeft - 1)) & 0x01) == 1);
 246     }
 247   }
 248
 249   public void appendBitArray(BitArray other) {
 250     int otherSize = other.size;
 251     ensureCapacity(size + otherSize);
 252     for (int i = 0; i < otherSize; i++) {
 253       appendBit(other.get(i));
 254     }
 255   }
 256
 257   public void xor(BitArray other) {
 258     if (bits.length != other.bits.length) {
 259       throw new IllegalArgumentException("Sizes don't match");
 260     }
 261     for (int i = 0; i < bits.length; i++) {
 262       // The last byte could be incomplete (i.e. not have 8 bits in
 263       // it) but there is no problem since 0 XOR 0 == 0.
 264       bits[i] ^= other.bits[i];
 265     }
 266   }
 267
 268   /**
 269    *
 270    * @param bitOffset first bit to start writing
 271    * @param array array to write into. Bytes are written most-significant byte first. This is the opposite
 272    *  of the internal representation, which is exposed by {@link #getBitArray()}
 273    * @param offset position in array to start writing
 274    * @param numBytes how many bytes to write
 275    */
 276   public void toBytes(int bitOffset, byte[] array, int offset, int numBytes) {
 277     for (int i = 0; i < numBytes; i++) {
 278       int theByte = 0;
 279       for (int j = 0; j < 8; j++) {
 280         if (get(bitOffset)) {
 281           theByte |= 1 << (7 - j);
 282         }
 283         bitOffset++;
 284       }
 285       array[offset + i] = (byte) theByte;
 286     }
 287   }
 288
 289   /**
 290    * @return underlying array of ints. The first element holds the first 32 bits, and the least
 291    *         significant bit is bit 0.
 292    */
 293   public int[] getBitArray() {
 294     return bits;
 295   }
 296
 297   /**
 298    * Reverses all bits in the array.
 299    */
 300   public void reverse() {
 301     int[] newBits = new int[bits.length];
 302     // reverse all int's first
 303     int len = ((size-1) / 32);
 304     int oldBitsLen = len + 1;
 305     for (int i = 0; i < oldBitsLen; i++) {
 306       long x = (long) bits[i];
 307       x = ((x >>  1) & 0x55555555L) | ((x & 0x55555555L) <<  1);
 308       x = ((x >>  2) & 0x33333333L) | ((x & 0x33333333L) <<  2);
 309       x = ((x >>  4) & 0x0f0f0f0fL) | ((x & 0x0f0f0f0fL) <<  4);
 310       x = ((x >>  8) & 0x00ff00ffL) | ((x & 0x00ff00ffL) <<  8);
 311       x = ((x >> 16) & 0x0000ffffL) | ((x & 0x0000ffffL) << 16);
 312       newBits[len - i] = (int) x;
 313     }
 314     // now correct the int's if the bit size isn't a multiple of 32
 315     if (size != oldBitsLen * 32) {
 316       int leftOffset = oldBitsLen * 32 - size;
 317       int mask = 1;
 318       for (int i = 0; i < 31 - leftOffset; i++) {
 319         mask = (mask << 1) | 1;
 320       }
 321       int currentInt = (newBits[0] >> leftOffset) & mask;
 322       for (int i = 1; i < oldBitsLen; i++) {
 323         int nextInt = newBits[i];
 324         currentInt |= nextInt << (32 - leftOffset);
 325         newBits[i - 1] = currentInt;
 326         currentInt = (nextInt >> leftOffset) & mask;
 327       }
 328       newBits[oldBitsLen - 1] = currentInt;
 329     }
 330     bits = newBits;
 331   }
 332
 333   private static int[] makeArray(int size) {
 334     return new int[(size + 31) / 32];
 335   }
 336
 337   @Override
 338   public String toString() {
 339     StringBuilder result = new StringBuilder(size);
 340     for (int i = 0; i < size; i++) {
 341       if ((i & 0x07) == 0) {
 342         result.append(' ');
 343       }
 344       result.append(get(i) ? 'X' : '.');
 345     }
 346     return result.toString();
 347   }
 348
 349 }