Created
December 1, 2019 05:42
-
-
Save oberrich/b310bfef2b9fd5eaaa65b032238e62ae to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment