3.5. CRC32 CALCULATION EXAMPLE
0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8,
0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b,
0x2d02ef8d
};
/ how to derive the values in crctab[] from polynomial 0xedb88320 /
void build_table()
{
ub4 i, j;
for (i=0; i<256; ++i) {
j = i;
j = (j>>1) ^ ((j&1)? 0xedb88320 : 0);
j = (j>>1) ^ ((j&1)? 0xedb88320 : 0);
j = (j>>1) ^ ((j&1)? 0xedb88320 : 0);
j = (j>>1) ^ ((j&1)? 0xedb88320 : 0);
j = (j>>1) ^ ((j&1)? 0xedb88320 : 0);
j = (j>>1) ^ ((j&1)? 0xedb88320 : 0);
j = (j>>1) ^ ((j&1)? 0xedb88320 : 0);
j = (j>>1) ^ ((j&1)? 0xedb88320 : 0);
printf("0x%.8lx, ", j);
if (i%6 == 5) printf("\n");
}
}
/ the hash function /
ub4 crc(const void key, ub4 len, ub4 hash)
{
ub4 i;
const ub1 k = key;
for (hash=len, i=0; i<len; ++i)
hash = (hash >> 8) ^ crctab[(hash & 0xff) ^ k[i]];
return hash;
}
/ To use, try "gcc -O crc.c -o crc; crc < crc.c" /
int main()
{
char s[1000];
while (gets(s)) printf("%.8lx\n", crc(s, strlen(s), 0));
return 0;
}
We are interested in thecrc()function only. By the way, pay attention to the two loop initializers in the
for()statement: hash=len, i=0. The C/C++ standard allows this, of course. The emitted code will
contain two operations in the loop initialization part instead of one.
Let’s compile it in MSVC with optimization (/Ox). For the sake of brevity, only thecrc()function is listed
here, with my comments.
_key$ = 8 ; size = 4
_len$ = 12 ; size = 4
_hash$ = 16 ; size = 4
_crc PROC
mov edx, DWORD PTR _len$[esp-4]
xor ecx, ecx ; i will be stored in ECX
mov eax, edx
test edx, edx
jbe SHORT $LN1@crc
push ebx
push esi
mov esi, DWORD PTR _key$[esp+4] ; ESI = key
push edi
$LL3@crc:
; work with bytes using only 32-bit registers. byte from address key+i we store into EDI
movzx edi, BYTE PTR [ecx+esi]
mov ebx, eax ; EBX = (hash = len)