table driven CRC - aargh !

[thewhizkid]

Folks, I've read all the standard papers and tutorials
which explain the table-method to compute CRC,
but my grey matter simply wont oblige.

I understand the bitwise method well, so can somebody
show me a simple 4bit or a 8-bit example to demonstrate
the table-driven CRC?

Thanks much.

[Mark Adler]

thewh...@rock.com (thewhizkid) wrote in message news:<31b3e6e5.03030...@posting.google.com>...

> so can somebody
> show me a simple 4bit or a 8-bit example to demonstrate
> the table-driven CRC?

Look at crc32.c in zlib.

http://www.zlib.org/

mark

[Sebastian Gesemann]

On 4 Mar 2003, thewhizkid wrote:

> I understand the bitwise method well, so can somebody
> show me a simple 4bit or a 8-bit example to demonstrate
> the table-driven CRC?

Here're some lines of java code i recently wrote.
(simplified)

----------8<----------8<----------8<----------

public class CRC {

private int shift;
private int mask;
private int poly;
private int register;
private int[] lut; // look-up table

/**
* constructs a new CRC object.
* bits : size of register in bits (8...32)
* poly : binary representation of generator polynomial
*/
public CRC(int bits, int poly) {
this.shift = bits - 8;
this.mask = (0x100 << shift) - 1;
this.poly = poly & mask;
this.register = 0;
createLUT();
}

public void setRegisterState(int r) {
register = r;
}

public int getRegisterState() {
return register & mask;
}

public void processByte(int bite) {
register = (register << 8) ^ lut[((register >> shift) ^ bite) & 0xFF];
}

private void createLUT() {
lut = new int[0x100];
for (int z=0; z<0x100; z++) {
int tmp = 0;
for (int s=0; s<8; s++) {
int x = (tmp >> shift) ^ (z << s);
tmp <<= 1;
if ((x & 0x80) != 0) tmp ^= poly;
}
lut[z] = tmp & mask;
}
}

}

----------8<----------8<----------8<----------

HTH,
Sebastian