CRC.java

public class CRC {
  private int degree;
  private int poly;

  public CRC(int poly) {
    this.poly = poly;
    this.degree = mostSignificantSetBit(poly) - 1;
  }

  public int getDegree() {
    return degree;
  }

  /**
   * Returns the crc remainder of the given string
   * Returns -1 for str == null or a polynomial of degree == -1 (infinite)
   *
   * @param str the string to calculate a remainder for
   */
  public int crcASCIIString(String str) {
    if (str == null || degree == -1)
      return -1;

    BitQueue bitQueue = new BitQueue();
    for (int j = 0; j < str.length(); ++j)
      bitQueue.enqueue((int)str.charAt(j));
    bitQueue.enqueue((byte)0, degree);

    int msbPoly = mostSignificantSetBit(poly);
    int crc = bitQueue.dequeue(0, msbPoly);

    while (bitQueue.getSize() > 0) {
      if (mostSignificantSetBit(crc) < msbPoly) {
        crc = bitQueue.dequeue(crc);
        if (mostSignificantSetBit(crc) < msbPoly)
          continue;
      }
      crc ^= poly;
    }

    return crc;
  }

  /**
   * Returns the position of the most significant ("highest") set bit within [1;32]
   * Returns 0 if no bit was set
   *
   * @param bits any 32-bit integer
   */
  private int mostSignificantSetBit(int bits) {
    for (int i = 31; i >= 0; --i)
      if (isBitSet(bits, i))
        return i + 1;

    return 0;
  }

  private static byte getBit(int bits, int n) {
    return isBitSet(bits, n) ? (byte)1 : (byte)0;
  }

  private static boolean isBitSet(int bits, int n) {
    return (bits & (1 << n)) != 0;
  }

  /**
   * This class implements a FIFO-Bit-Queue to be used within and only within the crcASCIIString method.
   * For simplicity this implementation is using an array internally, that gets copied on each insertion/deletion.
   */
  class BitQueue {
    private byte[] bits;
    private int size;

    public BitQueue() {
      this.bits = new byte[0];
    }

    public int getSize() {
      return size;
    }

    /**
     * Enqueues the bits of a 32-bit int after trimming it's "leading" zero bits in reverse (backwards)
     *
     * @param bits 32-bit int containing a set of bits
     */
    public void enqueue(int bits) {
      // insert bits backwards
      for (int i = mostSignificantSetBit(bits) - 1; i >= 0; --i) {
        enqueue(getBit(bits, i), 1);
      }
    }

    /**
     * Enqueues the bit parameter count times into the back of the queue
     *
     * @param bit the bit to enqueue
     * @param count the number of times to enqueue it
     */
    public void enqueue(byte bit, int count) {
      if (count <= 0)
        return;

      int newSize = size + count;
      byte[] newBits = new byte[newSize];
      //copy original
      for (int i = 0; i < size; ++i) {
        newBits[i] = this.bits[i];
      }
      //copy new bits
      for (int i = size; i < newSize; ++i)
        newBits[i] = bit;
      this.bits = newBits;
      this.size = newSize;
    }

    /**
     * Dequeues n bits from the front of the queue and adds them to the back of/"combines" it with the bits parameter
     * (shifts the bits parameter n bits to the left and "or"s it with the dequeued bits)
     * Returns the dequeued bits "combined" with the bits parameter.
     * If the count to dequeue is negative or > size, 0 is returned instead
     *
     * @param bits 32-bit int containing a set of bits
     * @param count the number of bits to dequeue within (0; getSize()]
     */
    public int dequeue(int bits, int count) {
      if (count <= 0 || count > size)
        return 0;

      int newSize = size - count;
      byte[] newBits = new byte[newSize];
      for (int i = 0; i < newSize && count + i < size; ++i) {
        newBits[i] = this.bits[i + count];
      }

      for (int i = 0; i < count && i < size; ++i) {
        bits <<= 1;
        bits |= this.bits[i];
      }

      this.bits = newBits;
      this.size = newSize;
      return bits;
    }

    /** @see #dequeue(int, int) */
    public int dequeue(int bits) {
      return dequeue(bits, 1);
    }
  }
}