Obliczanie sum kontrolnych CRC-32

cepa

2005-01-26 12:39:51
2008-12-08 20:16:36
3 komentarze
29803 odsłony

Obliczanie sumy kontrolnej CRC-32

Algorytm CRC 32bit służy do wyznaczania sum kontrolnych dla dowolnych danych
wejściowych.Jest to nic innego jak 32-bitowa liczba całkowita określająca poprawność
danych ze wzorcem. CRC-32 jest stosowane wszędzie tam gdzie potrzebna jest kontrola
plików i przesyłanych danych (np: archiwizery, multimedia, internet, programy cad,
itp). CRC jest skrótem od Cyclic Redundancy Check (Cykliczna Kontrola Nadmiarowa).

W tym artykule opisze tylko sposób implementacji, pomijając większość teori
matematycznej.

Podstawą działania algorytmu CRC-32 jest wielomian:
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 + x^0

Wielomian ten jest reprezentowany jako pojedyncza liczba 32-bitowa. Każdy fragment
to bit o wartości 1 ustawiony w miejscu wyznaczonym przez wykładnik potęgi.

Tak więc po wstawieniu bitów w odpowiednie miejsca otrzymujemy liczbę:

Kopiuj

32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 00
 1  0  0  0  0  0  1  0  0  1  1  0  0  0  0  0  1  0  0  0  1  1  0  0  1  1  0  1  1  0  1  1  1

czyli: 100000100110000010001100110110111 (2)
Jej długosć wynosci 33 bity więc o jeden bit zadużo (stała ma mieć 32 bity).
Usuwamy najstarszy bit i otrzymujemy 32-bitową reprezentacje wielomianu CRC-32.
00000100110000010001100110110111 (2) = 04C11DB7 (16)
Wartosć ta jest zawsze stała.

Jak wiadomo każda informacja jest reprezentowana w postaci 8 bitów (bajt), który
przyjmuje wartości z zakresu 0 do 255. Kody o tych wartościach to kody ASCII.
Kolejnym krokiem do obliczenia sumy kontrolnej jest obliczenie pewnych wartości dla
każdego kodu ASCII, robi się to w następujący sposób:

Kopiuj

0: for(ascii = 0; ascii < 255; ascii = ascii + 1)     // petla od 0 do 255
1:   A[ascii] = ascii;
2:   odwróć 8 najmłodszych bitów A[ascii];
3:   A[ascii] = A[ascii] << 24;                       // przesuń o 24 bity w lewo
4:   for(i = 0; i < 8; i = i + 1)                     // petla od 0 do 7
5:     if((A[ascii] AND 0x80000000) != 0)             // jesli jest rożne od 0
6:       A[ascii] = (A[ascii] << 1) XOR 0x04C11DB7;   // przesuń o 1 bit w lewo i xor'uj z 0x04C11DB7
7:     else
8:       A[ascii] = A[ascii] << 1;                    // przesuń o 1 bit w lewo
9:   odwróć 32 bity A[ascii];

gdzie:
A[0..255] - tablica liczb 32 bitowych o 256 elementach (każdy po 32bity)
ascii - iterator pętli, wskaźnik w tablicy A

Wartości w tablicy A są zawsze stałe co oznacza, że w praktyce lepiej jest
zdefiniować tablicę A i zapełnić ją stałymi wartościami niz obliczać ją za każdym
razem. Dlaczego ? Ano dlatego że tak czy siak zajmie ona 1024 bajty (256 * 32bity)
i zmniejszy się ilość potrzebnych funkcji w implementacji.

Gdy mamy już tablicę możemy obliczyć sumę kontrolną dla dowolnego ciągu danych:

Kopiuj

0: crc32 = 0xFFFFFFFF;   // wartość początkowa
1: for(i = 0; i < n; i = i + 1)   // pętla od 0 do n - 1
2:   crc32 = (crc32 >> 8) XOR A[(crc32 AND 0xFF) XOR B[i]];
4: crc32 = crc32 XOR 0xFFFFFFFF;

gdzie:
crc32 - 32bitowa liczba całkowita
A[0..255] - tablica ze stałymi obliczona wcześniej
B[0..n] - ciąg danych
n - długość ciągu danych
i - iterator pętli, wskaźnik w ciągu B

W wyniku powyższej procedury otrzymujemy liczbę będącą naszą sumą kontrolną.
Najczęściej wyswietla się ją jako 8 znakowa liczba hexadecymalna.

O to kod w C który oblicza CRC-32 dla plików. Tablica jest zadeklarowana z gotowymi
stałymi.

Kopiuj

/*
 * Cyclic Redundancy Check (32bit CRC checksum)
 * By CEPA 2005 (BSD License)
 * www.cepa.one.pl
 */

/* 2005-01-24 */

#include <stdio.h>

/* io read buffer size */
#define BUFSIZE 8192

/* CRC-32 const table for ASCII codes */
unsigned long int crc32_tab[256] =
{
  0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
  0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
  0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
  0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
  0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
  0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
  0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
  0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
  0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
  0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
  0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
  0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
  0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
  0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
  0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
  0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
  0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
  0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
  0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
  0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
  0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
  0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
  0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
  0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
  0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
  0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
  0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
  0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
  0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
  0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
  0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
  0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
  0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
  0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
  0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
  0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
  0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
  0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
  0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
  0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
  0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
  0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
  0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
  0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
  0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
  0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
  0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
  0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
  0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
  0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
  0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
  0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
  0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
  0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
  0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
  0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
  0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
  0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
  0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
  0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
  0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
  0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
  0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
  0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};

int main(int argc, char **argv)
{
  FILE *file = NULL;
  unsigned char buf[BUFSIZE];
  unsigned long int crc32 = 0;
  int arg = 0;
  size_t i = 0, n = 0;

  if(argc < 2)
  {
    printf("crc32 [file ...]\n");
    return 0;
  }

  for(arg = 1; arg < argc; arg++)
  {
    if(!(file = fopen(argv[arg], "rb")))
    {
      perror(argv[arg]);
      return -1;
    }

    fseek(file, 0, SEEK_SET);

    crc32 = 0xffffffff;

    while((n = fread(buf, 1, BUFSIZE, file)) > 0)
    {
      for(i = 0; i < n; i++)
        crc32 = (crc32 >> 8) ^ crc32_tab[(crc32 & 0xff) ^ buf[i]];
    }

    crc32 ^= 0xffffffff;

    fclose(file);

    printf("CRC-32 (%s) = %lx\n", argv[arg], crc32);
  }

  return 0;
}

/* EOF */

Poniżej jest program w C który wyświetla elementy tablicy A:

Kopiuj

/* CRC-32 Const Table Generator */

#include <stdio.h>

unsigned long int mirror_bits(unsigned long int x, int nbits)
{
  unsigned long int ret = 0;
  int i = 0;
  
  for(i = 1; i <= nbits; i++)
  {
    if(x & 1)
      ret |= 1 << (nbits - i);
      
    x >>= 1;  
  } 
  
  return ret;
}

int main()
{
  unsigned long int ascii = 0;
  int i = 0, j = 0;
  
  for(i = 0; i < 256; i++)
  {
    ascii = mirror_bits(i, 8) << 24;
    
    for(j = 0; j < 8; j++)
      ascii = ((ascii & 0x80000000) != 0) ? (ascii << 1) ^ 0x04c11db7 : ascii << 1;
          
    ascii = mirror_bits(ascii, 32);
    
    printf("0x%0.8lx\n", ascii);  
  } 
  
  return 0;
}
 
/* EOF */

Więcej o algorytmach CRC (CRC-12 CRC-16 itp) można znaleść w necie :)

Napisane na podstawie artykułu z <url>www.algorytm.cad.pl</url>

<url>www.cepa.one.pl</url>
cepa@o2.pl

2004-01-26

3 komentarzy