1592N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1592N/A * This code is free software; you can redistribute it and/or modify it 1592N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 1592N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 1592N/A * This code is distributed in the hope that it will be useful, but WITHOUT 1592N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1592N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1592N/A * version 2 for more details (a copy is included in the LICENSE file that 1592N/A * You should have received a copy of the GNU General Public License version 1592N/A * 2 along with this work; if not, write to the Free Software Foundation, 1592N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1592N/A * Copyright (C) 1995-2005 Mark Adler 1592N/A * For conditions of distribution and use, see copyright notice in zlib.h 1592N/A * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 1592N/A * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 1592N/A * tables for updating the shift register in one step with three exclusive-ors 1592N/A * instead of four steps with four exclusive-ors. This results in about a 1592N/A * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 1592N/A Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 1592N/A protection on the static variables used to control the first-use generation 1592N/A of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 1592N/A first call get_crc_table() to initialize the tables before allowing more than 1592N/A#
endif /* !DYNAMIC_CRC_TABLE */ 1592N/A/* Find a four-byte integer type for crc32_little() and crc32_big(). */ 1592N/A/* Definitions for doing the crc four data bytes at a time. */ 1592N/A#
define REV(w) (((w)>>
24)+(((w)>>
8)&
0xff00)+ \
1592N/A (((w)&
0xff00)<<
8)+(((w)&
0xff)<<
24))
1592N/A/* Local functions for crc concatenation */ 1592N/A Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 1592N/A 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. 1592N/A Polynomials over GF(2) are represented in binary, one bit per coefficient, 1592N/A with the lowest powers in the most significant bit. Then adding polynomials 1592N/A is just exclusive-or, and multiplying a polynomial by x is a right shift by 1592N/A one. If we call the above polynomial p, and represent a byte as the 1592N/A polynomial q, also with the lowest power in the most significant bit (so the 1592N/A byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 1592N/A where a mod b means the remainder after dividing a by b. 1592N/A This calculation is done using the shift-register method of multiplying and 1592N/A taking the remainder. The register is initialized to zero, and for each 1592N/A incoming bit, x^32 is added mod p to the register if the bit is a one (where 1592N/A x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 1592N/A x (which is shifting right by one and adding x^32 mod p if the bit shifted 1592N/A out is a one). We start with the highest power (least significant bit) of 1592N/A q and repeat for all eight bits of q. 1592N/A The first table is simply the CRC of all possible eight bit values. This is 1592N/A all the information needed to generate CRCs on data a byte at a time for all 1592N/A combinations of CRC register values and incoming bytes. The remaining tables 1592N/A allow for word-at-a-time CRC calculation for both big-endian and little- 1592N/A endian machines, where a word is four bytes. 1592N/A unsigned long poly;
/* polynomial exclusive-or pattern */ 1592N/A /* terms of polynomial defining this crc (except x^32): */ 1592N/A static volatile int first =
1;
/* flag to limit concurrent making */ 1592N/A static const unsigned char p[] = {0,
1,
2,
4,
5,
7,
8,
10,
11,
12,
16,
22,
23,
26};
1592N/A /* See if another task is already doing this (not thread-safe, but better 1592N/A than nothing -- significantly reduces duration of vulnerability in 1592N/A case the advice about DYNAMIC_CRC_TABLE is ignored) */ 1592N/A /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 1592N/A for (n = 0; n <
sizeof(p)/
sizeof(
unsigned char); n++)
1592N/A /* generate a crc for every 8-bit value */ 1592N/A for (n = 0; n <
256; n++) {
1592N/A /* generate crc for each value followed by one, two, and three zeros, 1592N/A and then the byte reversal of those as well as the first table */ 1592N/A for (n = 0; n <
256; n++) {
1592N/A /* wait for the other guy to finish (not efficient, but rare) */ 1592N/A n ==
255 ?
"\n" : (n %
5 ==
4 ?
",\n" :
", "));
1592N/A#
else /* !DYNAMIC_CRC_TABLE */ 1592N/A/* ======================================================================== 1592N/A * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 1592N/A#
endif /* DYNAMIC_CRC_TABLE */ 1592N/A/* ========================================================================= 1592N/A * This function can be used by asm versions of crc32() 1592N/A#
endif /* DYNAMIC_CRC_TABLE */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= */ 1592N/A#
endif /* DYNAMIC_CRC_TABLE */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= */ 1592N/A#
define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= */ 1592N/A/* ========================================================================= */ 1592N/A /* put operator for one zero bit in odd */ 2987N/A odd[0] =
0xedb88320UL;
/* CRC-32 polynomial */ 1592N/A /* put operator for two zero bits in even */ 1592N/A /* put operator for four zero bits in odd */ 1592N/A /* apply len2 zeros to crc1 (first square will put the operator for one 1592N/A zero byte, eight zero bits, in even) */ 1592N/A /* apply zeros operator for this bit of len2 */ 1592N/A /* if no more bits set, then done */ 1592N/A /* another iteration of the loop with odd and even swapped */ 1592N/A /* if no more bits set, then done */