crc32.c revision 84228
1153761Swollman/* crc32.c -- compute the CRC-32 of a data stream 2233445Sedwin * Copyright (C) 1995-1998 Mark Adler 3192886Sedwin * For conditions of distribution and use, see copyright notice in zlib.h 4192886Sedwin */ 564499Swollman 62742Swollman#include <sys/cdefs.h> 72742Swollman__FBSDID("$FreeBSD: head/lib/libz/crc32.c 84228 2001-09-30 22:39:00Z dillon $"); 82742Swollman 92742Swollman#include "zlib.h" 10158421Swollman 112742Swollman#define local static 12158421Swollman 13158421Swollman#ifdef DYNAMIC_CRC_TABLE 142742Swollman 1586222Swollmanlocal int crc_table_empty = 1; 1620094Swollmanlocal uLongf crc_table[256]; 1720094Swollmanlocal void make_crc_table OF((void)); 1820094Swollman 1920094Swollman/* 2020094Swollman Generate a table for a byte-wise 32-bit CRC calculation on the polynomial: 21158421Swollman 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. 22158421Swollman 2320094Swollman Polynomials over GF(2) are represented in binary, one bit per coefficient, 2419878Swollman with the lowest powers in the most significant bit. Then adding polynomials 2519878Swollman is just exclusive-or, and multiplying a polynomial by x is a right shift by 2619878Swollman one. If we call the above polynomial p, and represent a byte as the 2719878Swollman polynomial q, also with the lowest power in the most significant bit (so the 2819878Swollman byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 2919878Swollman where a mod b means the remainder after dividing a by b. 3019878Swollman 3119878Swollman This calculation is done using the shift-register method of multiplying and 3258787Sru taking the remainder. The register is initialized to zero, and for each 3358787Sru incoming bit, x^32 is added mod p to the register if the bit is a one (where 3458787Sru x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 3558787Sru x (which is shifting right by one and adding x^32 mod p if the bit shifted 3658787Sru out is a one). We start with the highest power (least significant bit) of 3758787Sru q and repeat for all eight bits of q. 3858787Sru 3958787Sru The table is simply the CRC of all possible eight bit values. This is all 4058787Sru the information needed to generate CRC's on data a byte at a time for all 4158787Sru combinations of CRC register values and incoming bytes. 4258787Sru*/ 4358787Srulocal void make_crc_table() 4458787Sru{ 4558787Sru uLong c; 4658787Sru int n, k; 4758787Sru uLong poly; /* polynomial exclusive-or pattern */ 4858787Sru /* terms of polynomial defining this crc (except x^32): */ 4958787Sru static const Byte p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 502742Swollman 512742Swollman /* make exclusive-or pattern from polynomial (0xedb88320L) */ 522742Swollman poly = 0L; 532742Swollman for (n = 0; n < sizeof(p)/sizeof(Byte); n++) 542742Swollman poly |= 1L << (31 - p[n]); 552742Swollman 562742Swollman for (n = 0; n < 256; n++) 5719878Swollman { 582742Swollman c = (uLong)n; 592742Swollman for (k = 0; k < 8; k++) 602742Swollman c = c & 1 ? poly ^ (c >> 1) : c >> 1; 6119878Swollman crc_table[n] = c; 622742Swollman } 632742Swollman crc_table_empty = 0; 64149514Swollman} 6521217Swollman#else 669908Swollman/* ======================================================================== 679908Swollman * Table of CRC-32's of all single-byte values (made by make_crc_table) 682742Swollman */ 6919878Swollmanlocal const uLongf crc_table[256] = { 7019878Swollman 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L, 7119878Swollman 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L, 7219878Swollman 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, 7319878Swollman 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL, 7419878Swollman 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L, 7519878Swollman 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L, 7619878Swollman 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L, 7719878Swollman 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL, 7819878Swollman 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L, 7919878Swollman 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL, 8019878Swollman 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L, 8119878Swollman 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L, 8219878Swollman 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L, 8319878Swollman 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL, 8419878Swollman 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL, 8593799Swollman 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L, 8658787Sru 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL, 8758787Sru 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L, 8819878Swollman 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L, 8919878Swollman 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L, 9019878Swollman 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL, 919908Swollman 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L, 92149514Swollman 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L, 939908Swollman 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL, 949908Swollman 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L, 959908Swollman 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L, 9621217Swollman 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L, 9719878Swollman 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L, 9819878Swollman 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L, 999908Swollman 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL, 100149514Swollman 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL, 1019908Swollman 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L, 1029908Swollman 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L, 1039908Swollman 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL, 1049908Swollman 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL, 10558787Sru 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L, 10658787Sru 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL, 10758787Sru 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L, 10864499Swollman 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL, 10964499Swollman 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L, 110175034Sedwin 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL, 111175034Sedwin 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L, 112175034Sedwin 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L, 113175034Sedwin 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL, 114175034Sedwin 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L, 11558787Sru 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L, 11658787Sru 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, 11767578Swollman 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L, 11858787Sru 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L, 11958787Sru 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L, 12058787Sru 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL, 121149514Swollman 0x2d02ef8dL 12264499Swollman}; 12364499Swollman#endif 12464499Swollman 12564499Swollman/* ========================================================================= 12686222Swollman * This function can be used by asm versions of crc32() 12786222Swollman */ 12886222Swollmanconst uLongf * ZEXPORT get_crc_table() 12986222Swollman{ 13086222Swollman#ifdef DYNAMIC_CRC_TABLE 13186222Swollman if (crc_table_empty) make_crc_table(); 13286222Swollman#endif 13386222Swollman return (const uLongf *)crc_table; 13486222Swollman} 13586222Swollman 13686222Swollman/* ========================================================================= */ 13786222Swollman#define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8); 13886222Swollman#define DO2(buf) DO1(buf); DO1(buf); 13986222Swollman#define DO4(buf) DO2(buf); DO2(buf); 14086222Swollman#define DO8(buf) DO4(buf); DO4(buf); 14186222Swollman 14286222Swollman/* ========================================================================= */ 14386222SwollmanuLong ZEXPORT crc32(crc, buf, len) 14486222Swollman uLong crc; 14586222Swollman const Bytef *buf; 14686222Swollman uInt len; 14786222Swollman{ 14886222Swollman if (buf == Z_NULL) return 0L; 149175034Sedwin#ifdef DYNAMIC_CRC_TABLE 150175034Sedwin if (crc_table_empty) 151175034Sedwin make_crc_table(); 152175034Sedwin#endif 153175034Sedwin crc = crc ^ 0xffffffffL; 154175034Sedwin while (len >= 8) 155175034Sedwin { 156175034Sedwin DO8(buf); 157175034Sedwin len -= 8; 158175034Sedwin } 159175034Sedwin if (len) do { 160175034Sedwin DO1(buf); 161175034Sedwin } while (--len); 162175034Sedwin return crc ^ 0xffffffffL; 163175034Sedwin} 164175034Sedwin