CRC

[Zacariaz]

Ok, new question...

I know this simple but i simply can't find any sources of information, well i can, but they are either writen by idiots or complicatet like hell.

I am of course talking about the cyclic redundancy check which i need to understand playing around with png files, and i should understand it, it seems so simple and yet it is so complicated.

I guess pone og my problems is that i never really understod what plynomials were all about, i mean x^27 + x^7 + x^0 can't possible result in a value endless you assign a value to x, and yet, somehow, it does. (at least according to the documents i've read)

Then there are the metodes which people uses, i'm sure they work fine, but they are not ment to be read by "first timers".

This is not a hard subject and therefor i hope that someone will spend a minute or two guiding me in the right direction.


Thanks

[Wave]

I don't know if this helps, but it's a crc32 example written in assembly and basic. It's very simple and quick to read through.

[Zacariaz]

ill look at it but me and basic don't work well together. comunication problems i think.

The best code example i've found is this:

Code: Select all

unsigned long crc_table[256];
int crc_table_computed = 0;

void make_crc_table(void) {
	unsigned long c;
	int n, k;
	for(n = 0; n < 256; n++) {
		c = (unsigned long) n;
		for(k = 0; k < 8; k++) {
			if(c & 1) c = 0xedb88320L ^ (c >> 1);
			else c = c >> 1;
		}
		crc_table[n] = c;
	}
	crc_table_computed = 1;
}

unsigned long update_crc(unsigned long crc, unsigned char *buf, int len) {
	unsigned long c = crc;
	int n;
	if(!crc_table_computed) make_crc_table();
	for(n = 0; n < len; n++) {
		c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
	}
	return c;
}

unsigned long crc(unsigned char *buf, int len) {
	return update_crc(0xffffffffL, buf, len) ^ 0xffffffffL;
}

Now, i allready knew i weren't a very good programmer, but this just makes me cry... (safe to say i don't understand a bit. Not even the parts i thought i understod before i found this code)

[Combuster]

The key thing you have to understand is how tail division works - You'll probably recall it from school.

Code: Select all

123456
------  =  ?
  7


7 / 123456 \ 17636 (or 017636), remainder 4
     7....   1.... x7 =  7, 12- 7=5
    --....    ....
     53...    ....
     49...    7... x7 = 49, 53-49=4
     --...     ...
      44..     ...
      42..     6.. x7 = 42, 44-42=2
      --..      ..
       25.      ..
       21.      3. x7 = 21, 25-21=4
       --.       .
        46       .
        42       6 x7 = 42, 46-42=4
        --
         4

each step you add a digit from the right, then you try to find the highest multiple of 7 that fits within that number, and write it down for the result. then subtract this amount. then go on with the next step. add a digit, find a multiple of 7, write down number, subtract, continue. In the end you run out of digits, and you have the remainder. If you wanted to go for decimal places, you'd write a comma in the answer and append a zero to the right, but we're not doing floating point math

A processor performs tail division in binary:

Code: Select all

 10 / 110 \ 11, remainder 0
      10.
      --.
       10
       10
       --
        0

CRC performs something along the lines of tail division, however it XORs each step instead of subtracting, and we are only interested in the remainder.

Code: Select all

 11 / 100 \ 11, remainder 1
      11.
      --.
       10
       11
       --
        1

In this case, the CRC checksum is 1. The 100 is the data we want check over, and 11 is a predefined constant for this specific CRC check. For your 32-bit checksum, you should be able to find the divisor that they used for computing their CRC.

Since doing division over each bit is horribly slow, most people use a shortcut using a lookup table. Instead of only looking at the first bit, we can determine what happens by looking at the next 8 bits at the same time, and then determine what remainder belongs to that - in essence they are doing CRC in a 256-digit system, rather than binary.

[Zacariaz]

I have just done my best converting the c code to c++:

Code: Select all

class CRC {
    unsigned long table[256];
public:
    CRC() {
        unsigned long c;
        for(short n = 0; n < 256; n++) {
            c = n;
            for(char k = 0; k < 8; k++) {
                if(c & 1) c = 0xedb88320 ^ (c >> 1);
			    else c = c >> 1;
            }
            table[n] = c;
        }
    }
    unsigned long update(unsigned char *buf, int len) {
	    unsigned long c = 0xffffffff;
    	for(int n = 0; n < len; n++) {
	    	c = table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
	    }
	    return c ^ 0xffffffff;;
    }
};

It seems to work, i have yet to test the results though, but if anyone have something to say, i'm listening.

[Zacariaz]

and no matter what i d it wont give the right result... obiously theres something wrong.

[Zacariaz]

Code: Select all

Standard CRC-32 generator polynomial:
       Name               : CRC-32 Standard
       Standards          : ISO 3309, ITU-T V.42, ANSI X3.66, FIPS PUB 71
       References         : ZIP, RAR, Ethernet, AUTODIN II, FDDI
       Initializing value : FFFFFFFF
       Finalizing value   : FFFFFFFF
       Polynomial value   : 04C11DB7 (Mirror value = EDB88320)
       Polynom            : x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 +
                            x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

Can anyone explain to me how this polunom can equal any of the given values? Agreed, i get a result very simular to the first value, but i really get a 33 bit value, thus a bit have been cut of. I haven read about this anywhere so is this just implyed or what? what is the x^32 doing in the polynom if it isn't used?

this might be stupid question but i have spend 4 hour looking for answers now and there isn't any, which is odd considering the subject.

[Combuster]

If you have read my previous post, you might have noticed where that 33rd bit comes from: The remainder you want is 32 bits (CRC-32, right), that means that the generator must be 33 bits.

lets look at a 5-bit generator: 10001
before you can apply it to a number, that number must be 5 bits long (for the bits to match), and have the top bit set (otherwise it wouldnt get altered).

so the number that you have is 1xxxx, xor it with 10001, and you get 0xxxx.
if the top bit was a zero, you dont xor and you have 0yyyy. In other words, a 5-bit generator gives a remainder of 4 bits, a 33-bit generator gives a remainder of 32 bits.

[Zacariaz]

every single piece of code i have come upon uses 32 bit values as constants and most of them uses:

04C11DB7 (Mirror value = EDB88320)

this is what confuses me when infact it is states that a 33 bit value is needed.
I do understand the principle, allthough im having trouble with the lookup tables and the code it self.

[Dex]

Here some links that may help ?
http://www.faqs.org/rfcs/rfc1950.html
http://www.faqs.org/rfcs/rfc1951.html

Note: the zip file is not a zip file but a .7z but i could not upload as such, so change it to a .7z before unzipping it.

[bewing]

I use CRC32 for all hashing in my OS. So it's important to me.

Here is the best source I found for a CRC explanation, with C code.
http://www.programmersheaven.com/downlo ... nload.aspx

(There is more CRC code on that website, if you do a search.)

Here are my 16bit and 8bit CRC functions (AFTER the lookup tables have been created.)

Code: Select all

; crc32s calculates a crc32 "checksum" for a string of shorts
; inputs: esi -> data string, ecx = number of shorts in data string
; outputs: crc value in eax -- all other registers are preserved
crc32s:
	mov eax, 0xffffffff		; eax is "crc"
crcp32s:
	push esi
	push ebx
	push ecx
	push edx
	mov ebx, 0x1c0000		; addy of crc table
	xor edx, edx
	jecxz crcs_don
crc_lp1:
	mov dx, ax			; dx is the low short of crc
	xor dx, [esi]			; xor it with "*p"
	add esi, 2			; ++
	shr eax, 16			; high short of crc for xor
	xor eax, [ebx+edx*4]		; xor it with the polytable
	loop crc_lp1			; decrement ecx and loop

crcs_don:
	not eax				; finally, flip all the crc bits
	pop edx
	pop ecx
	pop ebx
	pop esi
	ret

;  crc = 0xffffffff;  /* byte version */
;  while (i-- !=0) crc = poly_lookup[((unsigned char) crc ^ *(p++))] ^ (crc >> 8);
;  crc ^= 0xffffffff;

; crc32b calculates a crc32 checksum on a byte string (half as fast as crc32s)
; Note: maybe merge this with the word version -- do 1b to an even boundary, etc.
crc32b:
	mov eax, 0xffffffff		; eax is running crc value
crcp32b:				; entrypoint if modifying a precalculated crc
	push esi
	push ecx
	push ebx
	push edx
	mov ebx, crc_btbl		; addy of crc table
	xor edx, edx
	jecxz crcb_don
crc_bl1:
	mov dl, al			; dx is the low byte of crc
	xor dl, [esi]			; xor it with "*p"
	inc esi				; ++
	shr eax, 8			; high 3 bytes of crc for xor
	xor eax, [ebx+edx*4]		; xor it with the polytable
	loop crc_bl1			; decrement ecx and loop

crcb_don:
	not eax				; finally, flip all the crc bits
	pop edx
	pop ebx
	pop ecx
	pop esi
	ret

Please note the 3 lines of C in the middle of that. Creating the lookup tables is a little hard (it's all spelled out in the download I mentioned), but the actual CRC calculation is trivial.