crc32.c revision 33908
1199481Srdivacky/* crc32.c -- compute the CRC-32 of a data stream 2195340Sed * Copyright (C) 1995-1998 Mark Adler 3195340Sed * For conditions of distribution and use, see copyright notice in zlib.h 4195340Sed */ 5195340Sed 6195340Sed/* $FreeBSD: head/lib/libz/crc32.c 33908 1998-02-28 06:08:17Z steve $ */ 7195340Sed 8195340Sed#include "zlib.h" 9195340Sed 10195340Sed#define local static 11195340Sed 12195340Sed#ifdef DYNAMIC_CRC_TABLE 13195340Sed 14199481Srdivackylocal int crc_table_empty = 1; 15195340Sedlocal uLongf crc_table[256]; 16199481Srdivackylocal void make_crc_table OF((void)); 17198090Srdivacky 18195340Sed/* 19195340Sed Generate a table for a byte-wise 32-bit CRC calculation on the polynomial: 20195340Sed 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. 21195340Sed 22198892Srdivacky Polynomials over GF(2) are represented in binary, one bit per coefficient, 23198892Srdivacky with the lowest powers in the most significant bit. Then adding polynomials 24195340Sed is just exclusive-or, and multiplying a polynomial by x is a right shift by 25195340Sed one. If we call the above polynomial p, and represent a byte as the 26195340Sed polynomial q, also with the lowest power in the most significant bit (so the 27195340Sed byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 28195340Sed where a mod b means the remainder after dividing a by b. 29198892Srdivacky 30198892Srdivacky This calculation is done using the shift-register method of multiplying and 31195340Sed taking the remainder. The register is initialized to zero, and for each 32195340Sed incoming bit, x^32 is added mod p to the register if the bit is a one (where 33198090Srdivacky x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 34198090Srdivacky x (which is shifting right by one and adding x^32 mod p if the bit shifted 35198090Srdivacky out is a one). We start with the highest power (least significant bit) of 36198090Srdivacky q and repeat for all eight bits of q. 37195340Sed 38198090Srdivacky The table is simply the CRC of all possible eight bit values. This is all 39198090Srdivacky the information needed to generate CRC's on data a byte at a time for all 40198090Srdivacky combinations of CRC register values and incoming bytes. 41198090Srdivacky*/ 42198090Srdivackylocal void make_crc_table() 43198090Srdivacky{ 44206124Srdivacky uLong c; 45195340Sed int n, k; 46195340Sed uLong poly; /* polynomial exclusive-or pattern */ 47207618Srdivacky /* terms of polynomial defining this crc (except x^32): */ 48207618Srdivacky static const Byte p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 49207618Srdivacky 50207618Srdivacky /* make exclusive-or pattern from polynomial (0xedb88320L) */ 51207618Srdivacky poly = 0L; 52207618Srdivacky for (n = 0; n < sizeof(p)/sizeof(Byte); n++) 53207618Srdivacky poly |= 1L << (31 - p[n]); 54207618Srdivacky 55207618Srdivacky for (n = 0; n < 256; n++) 56207618Srdivacky { 57207618Srdivacky c = (uLong)n; 58207618Srdivacky for (k = 0; k < 8; k++) 59207618Srdivacky c = c & 1 ? poly ^ (c >> 1) : c >> 1; 60207618Srdivacky crc_table[n] = c; 61207618Srdivacky } 62207618Srdivacky crc_table_empty = 0; 63195340Sed} 64195340Sed#else 65198090Srdivacky/* ======================================================================== 66198090Srdivacky * Table of CRC-32's of all single-byte values (made by make_crc_table) 67195340Sed */ 68195340Sedlocal const uLongf crc_table[256] = { 69195340Sed 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, 70195340Sed 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, 71195340Sed 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, 72195340Sed 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL, 73206124Srdivacky 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L, 74195340Sed 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L, 75195340Sed 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L, 76206083Srdivacky 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL, 77198892Srdivacky 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L, 78198892Srdivacky 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL, 79198892Srdivacky 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L, 80198892Srdivacky 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L, 81198892Srdivacky 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L, 82198892Srdivacky 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL, 83198892Srdivacky 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL, 84198090Srdivacky 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L, 85198090Srdivacky 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL, 86198892Srdivacky 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L, 87198090Srdivacky 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L, 88195340Sed 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L, 89195340Sed 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL, 90198090Srdivacky 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L, 91195340Sed 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L, 92195340Sed 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL, 93195340Sed 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L, 94195340Sed 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L, 95195340Sed 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L, 96195340Sed 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L, 97206124Srdivacky 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L, 98195340Sed 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL, 99195340Sed 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL, 100206083Srdivacky 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L, 101198892Srdivacky 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L, 102198892Srdivacky 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL, 103198892Srdivacky 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL, 104198892Srdivacky 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L, 105198892Srdivacky 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL, 106198892Srdivacky 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L, 107198892Srdivacky 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL, 108198090Srdivacky 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L, 109198892Srdivacky 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL, 110198090Srdivacky 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L, 111198090Srdivacky 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L, 112195340Sed 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL, 113198090Srdivacky 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L, 114198090Srdivacky 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L, 115198090Srdivacky 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, 116198090Srdivacky 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L, 117198090Srdivacky 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L, 118198090Srdivacky 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L, 119198090Srdivacky 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL, 120198090Srdivacky 0x2d02ef8dL 121198090Srdivacky}; 122198090Srdivacky#endif 123198090Srdivacky 124198090Srdivacky/* ========================================================================= 125198090Srdivacky * This function can be used by asm versions of crc32() 126198090Srdivacky */ 127198090Srdivackyconst uLongf * ZEXPORT get_crc_table() 128198090Srdivacky{ 129198090Srdivacky#ifdef DYNAMIC_CRC_TABLE 130198090Srdivacky if (crc_table_empty) make_crc_table(); 131198090Srdivacky#endif 132198090Srdivacky return (const uLongf *)crc_table; 133198090Srdivacky} 134198090Srdivacky 135198090Srdivacky/* ========================================================================= */ 136198090Srdivacky#define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8); 137198090Srdivacky#define DO2(buf) DO1(buf); DO1(buf); 138198090Srdivacky#define DO4(buf) DO2(buf); DO2(buf); 139198090Srdivacky#define DO8(buf) DO4(buf); DO4(buf); 140198090Srdivacky 141198090Srdivacky/* ========================================================================= */ 142198090SrdivackyuLong ZEXPORT crc32(crc, buf, len) 143198090Srdivacky uLong crc; 144198090Srdivacky const Bytef *buf; 145198090Srdivacky uInt len; 146198090Srdivacky{ 147198090Srdivacky if (buf == Z_NULL) return 0L; 148198090Srdivacky#ifdef DYNAMIC_CRC_TABLE 149198090Srdivacky if (crc_table_empty) 150198090Srdivacky make_crc_table(); 151198090Srdivacky#endif 152198090Srdivacky crc = crc ^ 0xffffffffL; 153198090Srdivacky while (len >= 8) 154198090Srdivacky { 155198090Srdivacky DO8(buf); 156198090Srdivacky len -= 8; 157198090Srdivacky } 158198090Srdivacky if (len) do { 159195340Sed DO1(buf); 160198090Srdivacky } while (--len); 161198090Srdivacky return crc ^ 0xffffffffL; 162198090Srdivacky} 163198090Srdivacky