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 int bytePosition;
  31   private byte[] array;
  32
  33   // For efficiency, start out with some room to work.
  34   private static final int DEFAULT_SIZE_IN_BITS = 32 * 8;
  35
  36   public BitVector() {
  37     sizeInBits = DEFAULT_SIZE_IN_BITS;
  38     bytePosition = 0;
  39     array = new byte[DEFAULT_SIZE_IN_BITS / 8];
  40   }
  41
  42   // Return the bit value at "index".
  43   public int at(final int index) {
  44     Debug.DCHECK_LE(0, index);
  45     Debug.DCHECK_LT(index, sizeInBits);
  46     final int value = array[index / 8];
  47     return (value >> (7 - (index % 8))) & 1;
  48   }
  49
  50   // Return the number of bits in the bit vector.
  51   public int size() {
  52     return sizeInBits;
  53   }
  54
  55   // Return the number of bytes in the bit vector.
  56   public int num_bytes() {
  57     return sizeInBits / 8;
  58   }
  59
  60   // Append one bit to the bit vector.
  61   public void AppendBit(final int bit) {
  62     Debug.DCHECK(bit == 0 || bit == 1);
  63     final int num_bits_in_last_byte = sizeInBits % 8;
  64     // We'll expand array if we don't have bits in the last byte.
  65     if (num_bits_in_last_byte == 0) {
  66       appendByte(0);
  67     }
  68     // Modify the last byte.
  69     array[array.length - 1] |= (bit << (7 - num_bits_in_last_byte));
  70     ++sizeInBits;
  71   }
  72
  73   // Append "num_bits" bits in "value" to the bit vector.
  74   // REQUIRES: 0<= num_bits <= 32.
  75   //
  76   // Examples:
  77   // - AppendBits(0x00, 1) adds 0.
  78   // - AppendBits(0x00, 4) adds 0000.
  79   // - AppendBits(0xff, 8) adds 11111111.
  80   public void AppendBits(final int value, final int num_bits) {
  81     Debug.DCHECK(num_bits >= 0 && num_bits <= 32);
  82     int num_bits_left = num_bits;
  83     while (num_bits_left > 0) {
  84       // Optimization for byte-oriented appending.
  85       if (sizeInBits % 8 == 0 && num_bits_left >= 8) {
  86         final int newByte = (value >> (num_bits_left - 8)) & 0xff;
  87         appendByte(newByte);
  88         sizeInBits += 8;
  89         num_bits_left -= 8;
  90       } else {
  91         final int bit = (value >> (num_bits_left - 1)) & 1;
  92         AppendBit(bit);
  93         --num_bits_left;
  94       }
  95     }
  96   }
  97
  98   // Append "bytes".
  99   //
 100   // JAVAPORT: Uncomment and implement when a substitute for StringPiece is chosen.
 101 //  public void AppendBytes(final StringPiece stringPiece) {
 102 //    for (int i = 0; i < stringPiece.size(); ++i) {
 103 //      AppendBits(stringPiece[i], 8);
 104 //    }
 105 //  }
 106
 107   // Append "bits".
 108   public void AppendBitVector(final BitVector bits) {
 109     int size = bits.size();
 110     for (int i = 0; i < size; ++i) {
 111       AppendBit(bits.at(i));
 112     }
 113   }
 114
 115   // Modify the bit vector by XOR'ing with "other"
 116   public void XOR(final BitVector other) {
 117     Debug.DCHECK_EQ(sizeInBits, other.size());
 118     for (int i = 0; i < array.length; ++i) {
 119       // The last byte could be incomplete (i.e. not have 8 bits in
 120       // it) but there is no problem since 0 XOR 0 == 0.
 121       array[i] ^= other.array[i];
 122     }
 123   }
 124
 125   // Return String like "01110111" for debugging.
 126   public String toString() {
 127     StringBuffer result = new StringBuffer(sizeInBits);
 128     for (int i = 0; i < sizeInBits; ++i) {
 129       if (at(i) == 0) {
 130         result.append("0");
 131       } else if (at(i) == 1) {
 132         result.append("1");
 133       } else {
 134         Debug.DCHECK(false);
 135       }
 136     }
 137     return result.toString();
 138   }
 139
 140   // Add a new byte to the end, possibly reallocating and doubling the size of the array if we've
 141   // run out of room.
 142   private void appendByte(int value) {
 143     if (bytePosition >= array.length) {
 144       byte[] newArray = new byte[array.length * 2];
 145       System.arraycopy(array, 0, newArray, 0, array.length);
 146       array = newArray;
 147     }
 148     array[bytePosition] = (byte) value;
 149     bytePosition++;
 150   }
 151
 152 }