core/src/com/google/zxing/qrcode/encoder/BitVector.java

   1 /*
   2  * Copyright 2008 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.qrcode.encoder;
  18
  19 /**
  20  * JAVAPORT: This should be combined with BitArray in the future, although that class is not yet
  21  * dynamically resizeable. This implementation is reasonable but there is a lot of function calling
  22  * in loops I'd like to get rid of.
  23  *
  24  * @author satorux@google.com (Satoru Takabayashi) - creator
  25  * @author dswitkin@google.com (Daniel Switkin) - ported from C++
  26  */
  27 public final class BitVector {
  28
  29   private int sizeInBits;
  30   private byte[] array;
  31
  32   // For efficiency, start out with some room to work.
  33   private static final int DEFAULT_SIZE_IN_BYTES = 32;
  34
  35   public BitVector() {
  36     sizeInBits = 0;
  37     array = new byte[DEFAULT_SIZE_IN_BYTES];
  38   }
  39
  40   // Return the bit value at "index".
  41   public int at(final int index) {
  42     if (index < 0 || index >= sizeInBits) {
  43       throw new IllegalArgumentException("Bad index: " + index);
  44     }
  45     final int value = array[index >> 3] & 0xff;
  46     return (value >> (7 - (index & 0x7))) & 1;
  47   }
  48
  49   // Return the number of bits in the bit vector.
  50   public int size() {
  51     return sizeInBits;
  52   }
  53
  54   // Return the number of bytes in the bit vector.
  55   // JAVAPORT: I would have made this ((sizeInBits + 7) >> 3), but apparently users of this class
  56   // depend on the number of bytes being rounded down. I don't see how that works though.
  57   public int num_bytes() {
  58     return sizeInBits >> 3;
  59   }
  60
  61   // Append one bit to the bit vector.
  62   public void AppendBit(final int bit) {
  63     if (!(bit == 0 || bit == 1)) {
  64       throw new IllegalArgumentException("Bad bit");
  65     }
  66     final int num_bits_in_last_byte = sizeInBits & 0x7;
  67     // We'll expand array if we don't have bits in the last byte.
  68     if (num_bits_in_last_byte == 0) {
  69       appendByte(0);
  70       sizeInBits -= 8;
  71     }
  72     // Modify the last byte.
  73     array[sizeInBits >> 3] |= (bit << (7 - num_bits_in_last_byte));
  74     ++sizeInBits;
  75   }
  76
  77   // Append "num_bits" bits in "value" to the bit vector.
  78   // REQUIRES: 0<= num_bits <= 32.
  79   //
  80   // Examples:
  81   // - AppendBits(0x00, 1) adds 0.
  82   // - AppendBits(0x00, 4) adds 0000.
  83   // - AppendBits(0xff, 8) adds 11111111.
  84   public void AppendBits(final int value, final int num_bits) {
  85     if (num_bits < 0 || num_bits > 32) {
  86       throw new IllegalArgumentException("Num bits must be between 0 and 32");
  87     }
  88     int num_bits_left = num_bits;
  89     while (num_bits_left > 0) {
  90       // Optimization for byte-oriented appending.
  91       if ((sizeInBits & 0x7) == 0 && num_bits_left >= 8) {
  92         final int newByte = (value >> (num_bits_left - 8)) & 0xff;
  93         appendByte(newByte);
  94         num_bits_left -= 8;
  95       } else {
  96         final int bit = (value >> (num_bits_left - 1)) & 1;
  97         AppendBit(bit);
  98         --num_bits_left;
  99       }
 100     }
 101   }
 102
 103   // Append "bits".
 104   public void AppendBitVector(final BitVector bits) {
 105     int size = bits.size();
 106     for (int i = 0; i < size; ++i) {
 107       AppendBit(bits.at(i));
 108     }
 109   }
 110
 111   // Modify the bit vector by XOR'ing with "other"
 112   public void XOR(final BitVector other) {
 113     if (sizeInBits != other.size()) {
 114       throw new IllegalArgumentException("BitVector sizes don't match");
 115     }
 116     int sizeInBytes = (sizeInBits + 7) >> 3;
 117     for (int i = 0; i < sizeInBytes; ++i) {
 118       // The last byte could be incomplete (i.e. not have 8 bits in
 119       // it) but there is no problem since 0 XOR 0 == 0.
 120       array[i] ^= other.array[i];
 121     }
 122   }
 123
 124   // Return String like "01110111" for debugging.
 125   public String toString() {
 126     StringBuffer result = new StringBuffer(sizeInBits);
 127     for (int i = 0; i < sizeInBits; ++i) {
 128       if (at(i) == 0) {
 129         result.append("0");
 130       } else if (at(i) == 1) {
 131         result.append("1");
 132       } else {
 133         throw new IllegalArgumentException("Byte isn't 0 or 1");
 134       }
 135     }
 136     return result.toString();
 137   }
 138
 139   // Callers should not assume that array.length is the exact number of bytes needed to hold
 140   // sizeInBits - it will typically be larger for efficiency.
 141   public byte[] getArray() {
 142     return array;
 143   }
 144
 145   // Add a new byte to the end, possibly reallocating and doubling the size of the array if we've
 146   // run out of room.
 147   private void appendByte(int value) {
 148     if ((sizeInBits >> 3) == array.length) {
 149       byte[] newArray = new byte[array.length * 2];
 150       System.arraycopy(array, 0, newArray, 0, array.length);
 151       array = newArray;
 152     }
 153     array[sizeInBits >> 3] = (byte) value;
 154     sizeInBits += 8;
 155   }
 156
 157 }