package com.google.zxing.qrcode.encoder;
/**
+ * JAVAPORT: This should be combined with BitArray in the future, although that class is not yet
+ * dynamically resizeable. This implementation is reasonable but there is a lot of function calling
+ * in loops I'd like to get rid of.
+ *
* @author satorux@google.com (Satoru Takabayashi) - creator
* @author dswitkin@google.com (Daniel Switkin) - ported from C++
*/
public final class BitVector {
- private int size_;
- private String bytes_;
+ private int sizeInBits;
+ private byte[] array;
+
+ // For efficiency, start out with some room to work.
+ private static final int DEFAULT_SIZE_IN_BYTES = 32;
public BitVector() {
- size_ = 0;
+ sizeInBits = 0;
+ array = new byte[DEFAULT_SIZE_IN_BYTES];
}
// Return the bit value at "index".
- public int at(final int index) {
- Debug.DCHECK_LE(0, index);
- Debug.DCHECK_LT(index, size_);
- final uint8 byte = bytes_.at(index / 8);
- return (byte >> (7 - (index % 8))) & 1;
+ public int at(int index) {
+ if (index < 0 || index >= sizeInBits) {
+ throw new IllegalArgumentException("Bad index: " + index);
+ }
+ int value = array[index >> 3] & 0xff;
+ return (value >> (7 - (index & 0x7))) & 1;
}
// Return the number of bits in the bit vector.
public int size() {
- return size_;
+ return sizeInBits;
}
// Return the number of bytes in the bit vector.
- public int num_bytes() {
- return size_ / 8;
+ public int sizeInBytes() {
+ return (sizeInBits + 7) >> 3;
}
// Append one bit to the bit vector.
- public void AppendBit(final int bit) {
- Debug.DCHECK(bit == 0 || bit == 1);
- final int num_bits_in_last_byte = size_ % 8;
- // We'll expand bytes_ if we don't have bits in the last byte.
- if (num_bits_in_last_byte == 0) {
- bytes_.push_back(0);
+ public void appendBit(int bit) {
+ if (!(bit == 0 || bit == 1)) {
+ throw new IllegalArgumentException("Bad bit");
+ }
+ int numBitsInLastByte = sizeInBits & 0x7;
+ // We'll expand array if we don't have bits in the last byte.
+ if (numBitsInLastByte == 0) {
+ appendByte(0);
+ sizeInBits -= 8;
}
// Modify the last byte.
- bytes_[bytes_.size() - 1] |= (bit << (7 - num_bits_in_last_byte));
- ++size_;
+ array[sizeInBits >> 3] |= (bit << (7 - numBitsInLastByte));
+ ++sizeInBits;
}
- // Append "num_bits" bits in "value" to the bit vector.
- // REQUIRES: 0<= num_bits <= 32.
+ // Append "numBits" bits in "value" to the bit vector.
+ // REQUIRES: 0<= numBits <= 32.
//
// Examples:
- // - AppendBits(0x00, 1) adds 0.
- // - AppendBits(0x00, 4) adds 0000.
- // - AppendBits(0xff, 8) adds 11111111.
- public void AppendBits(final uint32 value, final int num_bits) {
- Debug.DCHECK(num_bits >= 0 && num_bits <= 32);
- int num_bits_left = num_bits;
- while (num_bits_left > 0) {
+ // - appendBits(0x00, 1) adds 0.
+ // - appendBits(0x00, 4) adds 0000.
+ // - appendBits(0xff, 8) adds 11111111.
+ public void appendBits(int value, int numBits) {
+ if (numBits < 0 || numBits > 32) {
+ throw new IllegalArgumentException("Num bits must be between 0 and 32");
+ }
+ int numBitsLeft = numBits;
+ while (numBitsLeft > 0) {
// Optimization for byte-oriented appending.
- if (size_ % 8 == 0 && num_bits_left >= 8) {
- final uint8 byte = (value >> (num_bits_left - 8)) & 0xff;
- bytes_.push_back(byte);
- size_ += 8;
- num_bits_left -= 8;
+ if ((sizeInBits & 0x7) == 0 && numBitsLeft >= 8) {
+ int newByte = (value >> (numBitsLeft - 8)) & 0xff;
+ appendByte(newByte);
+ numBitsLeft -= 8;
} else {
- final int bit = (value >> (num_bits_left - 1)) & 1;
- AppendBit(bit);
- --num_bits_left;
+ int bit = (value >> (numBitsLeft - 1)) & 1;
+ appendBit(bit);
+ --numBitsLeft;
}
}
}
- // Append "bytes".
- public void AppendBytes(final StringPiece &bytes) {
- for (int i = 0; i < bytes.size(); ++i) {
- AppendBits(bytes[i], 8);
- }
- }
-
// Append "bits".
- public void AppendBitVector(final BitVector &bits) {
- for (int i = 0; i < bits.size(); ++i) {
- AppendBit(bits.at(i));
+ public void appendBitVector(BitVector bits) {
+ int size = bits.size();
+ for (int i = 0; i < size; ++i) {
+ appendBit(bits.at(i));
}
}
// Modify the bit vector by XOR'ing with "other"
- public void XOR(final BitVector &other) {
- Debug.DCHECK_EQ(size_, other.size());
- for (int i = 0; i < bytes_.size(); ++i) {
+ public void xor(BitVector other) {
+ if (sizeInBits != other.size()) {
+ throw new IllegalArgumentException("BitVector sizes don't match");
+ }
+ int sizeInBytes = (sizeInBits + 7) >> 3;
+ for (int i = 0; i < sizeInBytes; ++i) {
// The last byte could be incomplete (i.e. not have 8 bits in
// it) but there is no problem since 0 XOR 0 == 0.
- bytes_[i] ^= other.ToString()[i];
+ array[i] ^= other.array[i];
}
}
- // Return the content of the bit vector as String.
- public final String &ToString() {
- return bytes_;
- }
-
// Return String like "01110111" for debugging.
- public String ToASCII() {
- String result;
- result.reserve(size_);
- for (int i = 0; i < size_; ++i) {
+ public String toString() {
+ StringBuffer result = new StringBuffer(sizeInBits);
+ for (int i = 0; i < sizeInBits; ++i) {
if (at(i) == 0) {
- result.append("0");
+ result.append('0');
} else if (at(i) == 1) {
- result.append("1");
+ result.append('1');
} else {
- Debug.DCHECK(false);
+ throw new IllegalArgumentException("Byte isn't 0 or 1");
}
}
- return result;
+ return result.toString();
+ }
+
+ // Callers should not assume that array.length is the exact number of bytes needed to hold
+ // sizeInBits - it will typically be larger for efficiency.
+ public byte[] getArray() {
+ return array;
+ }
+
+ // Add a new byte to the end, possibly reallocating and doubling the size of the array if we've
+ // run out of room.
+ private void appendByte(int value) {
+ if ((sizeInBits >> 3) == array.length) {
+ byte[] newArray = new byte[(array.length << 1)];
+ System.arraycopy(array, 0, newArray, 0, array.length);
+ array = newArray;
+ }
+ array[sizeInBits >> 3] = (byte) value;
+ sizeInBits += 8;
}
}