Grauel at 10:33, 31 October 2006

2006-10-31T10:33:34Z

New page

#include <stdio.h>

#define CRCPOLY 0xEDB88320
#define CRCINV 0x5B358FD3 // inverse poly of (x^N) mod CRCPOLY
#define INITXOR 0xFFFFFFFF
#define FINALXOR 0xFFFFFFFF
typedef unsigned int uint32;

/**
* Creates the CRC table with 256 32-bit entries. CAUTION: Assumes that
* enough space for the resulting table has already been allocated.
*/
void make_crc_table(uint32 *table) {
uint32 c;
int n, k;

for (n = 0; n < 256; n++) {
c = n;
for (k = 0; k < 8; k++) {
if ((c & 1) != 0) {
c = CRCPOLY ^ (c >> 1);
} else {
c = c >> 1;
}
}
table[n] = c;
}
}

/**
* Creates the reverse CRC table with 256 32-bit entries. CAUTION: Assumes
* that enough space for the resulting table has already been allocated.
*/
void make_crc_revtable(uint32 *table) {
uint32 c;
int n, k;

for (n = 0; n < 256; n++) {
c = n << 3*8;
for (k = 0; k < 8; k++) {
if ((c & 0x80000000) != 0) {
c = ((c ^ CRCPOLY) << 1) | 1;
} else {
c <<= 1;
}
}
table[n] = c;
}
}

/**
* Computes the CRC32 of the buffer of the given length using the
* (slow) bit-oriented approach
*/
int crc32_bitoriented(unsigned char *buffer, int length) {
int i, j;
uint32 crcreg = INITXOR;

for (j = 0; j < length; ++j) {
unsigned char b = buffer[j];
for (i = 0; i < 8; ++i) {
if ((crcreg ^ b) & 1) {
crcreg = (crcreg >> 1) ^ CRCPOLY;
} else {
crcreg >>= 1;
}
b >>= 1;
}
}

return crcreg ^ FINALXOR;
}

/**
* Computes the CRC32 of the buffer of the given length
* using the supplied crc_table
*/
int crc32_tabledriven(unsigned char *buffer,
int length,
uint32 *crc_table)
{
int i;
uint32 crcreg = INITXOR;

for (i = 0; i < length; ++i) {
crcreg = (crcreg >> 8) ^ crc_table[((crcreg ^ buffer[i]) & 0xFF)];
}

return crcreg ^ FINALXOR;
}

/**
* Changes the last 4 bytes of the given buffer so that it afterwards will
* compute to the "magic sequence" (usually 0x2144DF1C for CRC32)
*/
void fix_crc_magic(unsigned char *buffer, int length, uint32 *crc_table)
{
int i;

// calculate CRC32 except for the last 4 bytes
uint32 crcreg = crc32_tabledriven(buffer, length-4, crc_table);

// inject crcreg as content - nothing easier than that!
for (i = 0; i < 4; ++i)
buffer[length - 4 + i] = (crcreg >> i*8) & 0xFF;
}

/**
* Changes the last 4 bytes of the given buffer so that it afterwards will
* compute to the given tcrcreg using the given crc_table
*
* This function uses the method of the multiplication with (x^N)^-1.
*/
void fix_crc_end(unsigned char *buffer,
int length,
uint32 tcrcreg,
uint32 *crc_table)
{
int i;
tcrcreg ^= FINALXOR;

// calculate crc except for the last 4 bytes; this is essentially crc32()
uint32 crcreg = INITXOR;
for (i = 0; i < length - 4; ++i) {
crcreg = (crcreg >> 8) ^ crc_table[((crcreg ^ buffer[i]) & 0xFF)];
}

// calculate new content bits
// new_content = tcrcreg * CRCINV mod CRCPOLY
uint32 new_content = 0;
for (i = 0; i < 32; ++i) {
// reduce modulo CRCPOLY
if (new_content & 1) {
new_content = (new_content >> 1) ^ CRCPOLY;
} else {
new_content >>= 1;
}
// add CRCINV if corresponding bit of operand is set
if (tcrcreg & 1) {
new_content ^= CRCINV;
}
tcrcreg >>= 1;
}
// finally add old crc
new_content ^= crcreg;

// inject new content
for (i = 0; i < 4; ++i)
buffer[length - 4 + i] = (new_content >> i*8) & 0xFF;
}

/**
* Changes the 4 bytes of the given buffer at position fix_pos so that
* it afterwards will compute to the given tcrcreg using the given crc_table.
* A reversed crc table (crc_revtable) must be provided.
*/
void fix_crc_pos(unsigned char *buffer,
int length,
uint32 tcrcreg,
int fix_pos,
uint32 *crc_table,
uint32 *crc_revtable)
{
int i;
// make sure fix_pos is within 0..(length-1)
fix_pos = ((fix_pos%length)+length)%length;

// calculate crc register at position fix_pos; this is essentially crc32()
uint32 crcreg = INITXOR;
for (i = 0; i < fix_pos; ++i) {
crcreg = (crcreg >> 8) ^ crc_table[((crcreg ^ buffer[i]) & 0xFF)];
}

// inject crcreg as content
for (i = 0; i < 4; ++i)
buffer[fix_pos + i] = (crcreg >> i*8) & 0xFF;

// calculate crc backwards to fix_pos, beginning at the end
tcrcreg ^= FINALXOR;
for (i = length - 1; i >= fix_pos; --i) {
tcrcreg = (tcrcreg << 8) ^ crc_revtable[tcrcreg >> 3*8] ^ buffer[i];
}

// inject new content
for (i = 0; i < 4; ++i)
buffer[fix_pos + i] = (tcrcreg >> i*8) & 0xFF;

}

/**
* this function is obsolete as i used it as a testbed
*/
// 1 2 3 4 5 6 7 8
// 45678901234567890123456789012345678901234567890123456789012345678901234567890
void fix_crc_old(unsigned char *buffer, int length, uint32 target_crc, int fix_pos, uint32 *crc_table) {
int i, j;
fix_pos = ((fix_pos%length)+length)%length;

// calculate target crc register on position fix_pos+4
uint32 tcrcreg = (target_crc & 0xFFFFFFFF) ^ FINALXOR;
// uint32 tcrcreg = (target_crc & 0xFFFFFFFF) ^ 0x2144DF1C;
for (j = length - 1; j > fix_pos + 3; --j) {
// printf("fix_crc_old: \ttcrcreg[%d] = %08X\n", j, tcrcreg);
unsigned char cbyte = buffer[j];
for (i = 0; i<=7; ++i) {
uint32 xor = (tcrcreg >> 31) & 1 ;
tcrcreg = ((tcrcreg ^ (xor*CRCPOLY)) << 1) & 0xFFFFFFFF | (xor ^ (cbyte >> 7) & 1);
cbyte <<= 1;
}
}
// printf("fix_crc_old: \ttcrcreg[%d] = %08X\n", j, tcrcreg);

// calculate positions for XORing the CRCPOLY
uint32 xorreg = 0;
for (i=0; i<=31; ++i) {
xorreg <<= 1;
if ((tcrcreg & 0x80000000) != 0) {
tcrcreg ^= CRCPOLY;
xorreg |= 1;
}
tcrcreg = (tcrcreg << 1) & 0xFFFFFFFF;
}

// calculate crc register on position fix_pos
uint32 crcreg = crc32_tabledriven(buffer, fix_pos, crc_table);
crcreg ^= 0xFFFFFFFFL;

printf("fix_crc_old: \tcrcreg = %08X\n", crcreg);

// printf("fix_crc: \t*** crcreg = %08X", crcreg);

// calculate new content bits
uint32 new_content = 0;
for (i=0; i<=31; ++i) {
new_content >>= 1;
new_content |= ((crcreg ^ xorreg) & 1) << 31;
crcreg = (crcreg >> 1) ^ ((xorreg & 1) * CRCPOLY);
xorreg >>= 1;
}

// printf(", b = %08X\n", new_content);

printf("fix_crc_old: \tnew_content = %08X\n", new_content);

// inject new content
for (i=0; i<=3; ++i)
buffer[fix_pos + i] = (new_content >> i*8) & 0xFF;

}

#if 0
int main() {

int i;

uint32 crc_table[256*8];
uint32 crc_revtable[256*8];
unsigned char foostr1[] = "foobar1234";
unsigned char foostr2[] = "foobar1234";
unsigned char foostr3[] = "foobar1234";
unsigned char foostr4[] = "foobar1234";

make_crc_table(crc_table);
make_crc_revtable(crc_revtable);

unsigned char foostr[] = "bla 1234";
fix_crc_pos(foostr, 8, 0xcafebabe, -4, crc_table, crc_revtable);
printf("crc of foostr: %08X\n", crc32_tabledriven(foostr, 8, crc_table));

uint32 targetcrc = 0xdeadbeef;

printf("crc of foobar1: %08X\n", crc32_bitoriented(foostr1, 6));
printf("crc of foobar2: %08X\n", crc32_tabledriven(foostr2, 6, crc_table));
printf("crc of foobar3: %08X\n", crc32_tabledriven(foostr3, 6, crc_table));
printf("crc of foobar4: %08X\n", crc32_tabledriven(foostr4, 6, crc_table));

fix_crc_old(foostr1, 10, targetcrc, 3, crc_table);
fix_crc_pos(foostr2, 10, targetcrc, 3, crc_table, crc_revtable);
fix_crc_end(foostr3, 10, targetcrc, crc_table);
fix_crc_magic(foostr4, 10, crc_table);

printf("crc after fix old: %08X\n", crc32_tabledriven(foostr1, 10, crc_table));
for (i=0; i<10; ++i) printf("%02X ", foostr1[i]);printf("\n");
printf("crc after fix new: %08X\n", crc32_tabledriven(foostr2, 10, crc_table));
for (i=0; i<10; ++i) printf("%02X ", foostr2[i]);printf("\n");
printf("crc after fix end: %08X\n", crc32_tabledriven(foostr3, 10, crc_table));
for (i=0; i<10; ++i) printf("%02X ", foostr3[i]);printf("\n");
printf("crc after fix magic: %08X\n", crc32_tabledriven(foostr4, 10, crc_table));
for (i=0; i<10; ++i) printf("%02X ", foostr4[i]);printf("\n");

}
#endif

Crc32.c - Revision history

Grauel at 10:33, 31 October 2006