View source for Crc32.c

 #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