reverse engineering - CRC32 calculation with CRC hash at the beginning of the message in C -

i need calculate crc of message , put at beginning of message, final crc of message 'prepended' patch bytes equals 0. able of few articles, not specific parameters. thing have use given crc32 algorithm calculates crc of memory block, don't have 'reverse' algorithm calculates 4 patch bytes/'kind of crc'. parameters of given crc32 algorithm are:

• polynomial: 0x04c11db7
• endianess: big-endian
• initial value: 0xffffffff
• reflected: false
• xor out with: 0l
• test stream: 0x0123, 0x4567, 0x89ab, 0xcdef results in crc = 0x612793c3

the code calculate crc (half-byte, table-driven, hope data type definitions self-explanatory):

uint32 crc32tab(uint16* data, uint32 len, uint32 crc) {     uint8 nibble;     int i;     while(len--)     {         for(i = 3; >= 0; i--)         {             nibble = (*data >> i*4) & 0x0f;             crc = ((crc << 4) | nibble) ^ tab[crc >> 28];         }         data++;     }      return crc; } 

the table needed (i thougth short [16] table should contain every 16th element large [256] table, table contains first 16 elements, that's how provided me):

static const uint32 tab[16]= {     0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,     0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,     0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,     0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd };   

i modified code it's not long, functionality stays same. problem forward crc calculation looks more backward/reverse crc calc.
i've spent week trying find out correct polynomial/algorithm/table combination, no luck. if helps, came bit-wise algorithm corresponds table-driven code above, although not hard after all:

uint32 crc32(uint16* data, uint32 len, uint32 crc) {     uint32 i;     while(len--)     {         for(i = 0; < 16; i++)         {             // #define poly 0x04c11db7             crc = (crc << 1) ^ (((crc ^ *data) & 0x80000000) ? poly : 0);         }         crc ^= *data++;     }      return crc; } 

here expected results - first 2 16-bit words make needed unknown crc , rest known data (by feeding these examples provided algorithm, result 0).

{0x3288, 0xd244, 0xcdef, 0x89ab, 0x4567, 0x0123} {0xc704, 0xdd7b, 0x0000} - append many zeros like, result same {0xcebd, 0x1add, 0xffff} {0x81ab, 0xb932, 0xffff, 0xffff} {0x0857, 0x0465, 0x0000, 0x0123} {0x1583, 0xd959, 0x0123}    ^        ^    |        |    unknown bytes need calculate 

i think testing on 0xffff or 0x0000 words convenient because direction of calculation , endianess not important (i hope :d). careful use other test bytes, because direction of calculation quite devious :d. can see feeding zeros algorithm (both forward , backward), result so-called residue (0xc704dd7b), may helpful.

so...i wrote @ least 10 different functions (bite-wise, tables, combination of polynomials etc.) trying solve this, no luck. give here function in put hopes into. it's 'reversed' algorithm of table-driven 1 above, different table of course. problem correct crc 0s message , that's not unexpected. have written reversed implementation of bit-wise algorithm (reversed shifts, etc.), 1 returns first byte correctly.
here table-driven one, pointer data should point last element of message , crc input should requested crc (0s whole message or can maybe take approach - last 4 bytes of message crc looking for: calculating crc initial value instead of appending crc payload) :

uint32 crc32tabrev(uint16* data, uint32 len, uint32 crc) {     uint8 nibble;     int i;     while(len--)     {         for(i = 0; < 4; i++)         {             nibble = (*data >> i*4) & 0x0f;             crc = (crc >> 4) ^ revtab[((crc ^ nibble) & 0x0f)];         }         data--;      }       return reverse(crc); //reverse() flips bits around center (msb <-> lsb ...)  } 

the table, hope 'the chosen one':

static const uint32 revtab[16]= {     0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac,     0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,     0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c,     0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c }; 

as can see, algorithm has perks make me run in circles , think i'm maybe on right track, i'm missing something. hope pair of eyes see can not. i'm sorry long post (no potato :d), think of explanation neccessary. thank in advance insight or advice.

i answer crc specification, of crc-32/mpeg-2. have ignore attempts @ calculating crc, since incorrect.

anyway, answer question, happen have written program solves problem. called spoof.c. rapidly computes bits change in message desired crc. in order log(n) time, n length of message. here example:

let's take nine-byte message 123456789 (those digits represented in ascii). prepend 4 0 bytes, change desired crc @ end. message in hex then: 00 00 00 00 31 32 33 34 35 36 37 38 39. compute crc-32/mpeg-2 message. 373c5870.

now run spoof input, crc length in bits, fact not reflected, polynomial, crc computed, length of message in bytes, , 32 bit locations in first 4 bytes (which allowing spoof change):

32 0 04c11db7 373c5870 13 0 0 1 2 3 4 5 6 7  1 0 1 2 3 4 5 6 7 2 0 1 2 3 4 5 6 7 3 0 1 2 3 4 5 6 7 

it gives output bits in first 4 bytes set:

invert these bits in sequence: offset bit      0 1      0 2      0 4      0 5      0 6      1 0      1 2      1 5      1 7      2 0      2 2      2 5      2 6      2 7      3 0      3 1      3 2      3 4      3 5      3 7 

we set first 4 bytes to: 76 a5 e5 b7. test computing crc-32/mpeg-2 of message 76 a5 e5 b7 31 32 33 34 35 36 37 38 39 , 00000000, desired result.

you can adapt spoof.c application.

here example correctly computes crc-32/mpeg-2 on stream of bytes using bit-wise algorithm:

uint32_t crc32m(uint32_t crc, const unsigned char *buf, size_t len) {     int k;      while (len--) {         crc ^= (uint32_t)(*buf++) << 24;         (k = 0; k < 8; k++)             crc = crc & 0x80000000 ? (crc << 1) ^ 0x04c11db7 : crc << 1;     }     return crc; } 

and nybble-wise algorithm using table in question (which correct):

uint32_t crc_table[] = {     0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,     0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,     0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,     0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd };  uint32_t crc32m_nyb(uint32_t crc, const unsigned char *buf, size_t len) {     while (len--) {         crc ^= (uint32_t)(*buf++) << 24;         crc = (crc << 4) ^ crc_table[crc >> 28];         crc = (crc << 4) ^ crc_table[crc >> 28];     }     return crc; } 

in both cases, initial crc must 0xffffffff.