| crc32.c (230837) | crc32.c (237248) |
|---|---|
| 1/* crc32.c -- compute the CRC-32 of a data stream | 1/* crc32.c -- compute the CRC-32 of a data stream |
| 2 * Copyright (C) 1995-2006, 2010, 2011 Mark Adler | 2 * Copyright (C) 1995-2006, 2010, 2011, 2012 Mark Adler |
| 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 * 5 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 6 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 7 * tables for updating the shift register in one step with three exclusive-ors 8 * instead of four steps with four exclusive-ors. This results in about a 9 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 10 */ --- 16 unchanged lines hidden (view full) --- 27# define DYNAMIC_CRC_TABLE 28# endif /* !DYNAMIC_CRC_TABLE */ 29#endif /* MAKECRCH */ 30 31#include "zutil.h" /* for STDC and FAR definitions */ 32 33#define local static 34 | 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 * 5 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 6 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 7 * tables for updating the shift register in one step with three exclusive-ors 8 * instead of four steps with four exclusive-ors. This results in about a 9 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 10 */ --- 16 unchanged lines hidden (view full) --- 27# define DYNAMIC_CRC_TABLE 28# endif /* !DYNAMIC_CRC_TABLE */ 29#endif /* MAKECRCH */ 30 31#include "zutil.h" /* for STDC and FAR definitions */ 32 33#define local static 34 |
| 35/* Find a four-byte integer type for crc32_little() and crc32_big(). */ 36#ifndef NOBYFOUR 37# ifdef STDC /* need ANSI C limits.h to determine sizes */ 38# include <limits.h> 39# define BYFOUR 40# if (UINT_MAX == 0xffffffffUL) 41 typedef unsigned int u4; 42# else 43# if (ULONG_MAX == 0xffffffffUL) 44 typedef unsigned long u4; 45# else 46# if (USHRT_MAX == 0xffffffffUL) 47 typedef unsigned short u4; 48# else 49# undef BYFOUR /* can't find a four-byte integer type! */ 50# endif 51# endif 52# endif 53# endif /* STDC */ 54#endif /* !NOBYFOUR */ 55 | |
| 56/* Definitions for doing the crc four data bytes at a time. */ | 35/* Definitions for doing the crc four data bytes at a time. */ |
| 36#if !defined(NOBYFOUR) && defined(Z_U4) 37# define BYFOUR 38#endif |
|
| 57#ifdef BYFOUR | 39#ifdef BYFOUR |
| 58 typedef u4 crc_table_t; 59# define REV(w) ((((w)>>24)&0xff)+(((w)>>8)&0xff00)+ \ 60 (((w)&0xff00)<<8)+(((w)&0xff)<<24)) | |
| 61 local unsigned long crc32_little OF((unsigned long, 62 const unsigned char FAR *, unsigned)); 63 local unsigned long crc32_big OF((unsigned long, 64 const unsigned char FAR *, unsigned)); 65# define TBLS 8 66#else | 40 local unsigned long crc32_little OF((unsigned long, 41 const unsigned char FAR *, unsigned)); 42 local unsigned long crc32_big OF((unsigned long, 43 const unsigned char FAR *, unsigned)); 44# define TBLS 8 45#else |
| 67 typedef unsigned long crc_table_t; | |
| 68# define TBLS 1 69#endif /* BYFOUR */ 70 71/* Local functions for crc concatenation */ 72local unsigned long gf2_matrix_times OF((unsigned long *mat, 73 unsigned long vec)); 74local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 75local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); 76 77 78#ifdef DYNAMIC_CRC_TABLE 79 80local volatile int crc_table_empty = 1; | 46# define TBLS 1 47#endif /* BYFOUR */ 48 49/* Local functions for crc concatenation */ 50local unsigned long gf2_matrix_times OF((unsigned long *mat, 51 unsigned long vec)); 52local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 53local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); 54 55 56#ifdef DYNAMIC_CRC_TABLE 57 58local volatile int crc_table_empty = 1; |
| 81local crc_table_t FAR crc_table[TBLS][256]; | 59local z_crc_t FAR crc_table[TBLS][256]; |
| 82local void make_crc_table OF((void)); 83#ifdef MAKECRCH | 60local void make_crc_table OF((void)); 61#ifdef MAKECRCH |
| 84 local void write_table OF((FILE *, const crc_table_t FAR *)); | 62 local void write_table OF((FILE *, const z_crc_t FAR *)); |
| 85#endif /* MAKECRCH */ 86/* 87 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 88 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. 89 90 Polynomials over GF(2) are represented in binary, one bit per coefficient, 91 with the lowest powers in the most significant bit. Then adding polynomials 92 is just exclusive-or, and multiplying a polynomial by x is a right shift by --- 13 unchanged lines hidden (view full) --- 106 The first table is simply the CRC of all possible eight bit values. This is 107 all the information needed to generate CRCs on data a byte at a time for all 108 combinations of CRC register values and incoming bytes. The remaining tables 109 allow for word-at-a-time CRC calculation for both big-endian and little- 110 endian machines, where a word is four bytes. 111*/ 112local void make_crc_table() 113{ | 63#endif /* MAKECRCH */ 64/* 65 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 66 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. 67 68 Polynomials over GF(2) are represented in binary, one bit per coefficient, 69 with the lowest powers in the most significant bit. Then adding polynomials 70 is just exclusive-or, and multiplying a polynomial by x is a right shift by --- 13 unchanged lines hidden (view full) --- 84 The first table is simply the CRC of all possible eight bit values. This is 85 all the information needed to generate CRCs on data a byte at a time for all 86 combinations of CRC register values and incoming bytes. The remaining tables 87 allow for word-at-a-time CRC calculation for both big-endian and little- 88 endian machines, where a word is four bytes. 89*/ 90local void make_crc_table() 91{ |
| 114 crc_table_t c; | 92 z_crc_t c; |
| 115 int n, k; | 93 int n, k; |
| 116 crc_table_t poly; /* polynomial exclusive-or pattern */ | 94 z_crc_t poly; /* polynomial exclusive-or pattern */ |
| 117 /* terms of polynomial defining this crc (except x^32): */ 118 static volatile int first = 1; /* flag to limit concurrent making */ 119 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 120 121 /* See if another task is already doing this (not thread-safe, but better 122 than nothing -- significantly reduces duration of vulnerability in 123 case the advice about DYNAMIC_CRC_TABLE is ignored) */ 124 if (first) { 125 first = 0; 126 127 /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 128 poly = 0; 129 for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) | 95 /* terms of polynomial defining this crc (except x^32): */ 96 static volatile int first = 1; /* flag to limit concurrent making */ 97 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 98 99 /* See if another task is already doing this (not thread-safe, but better 100 than nothing -- significantly reduces duration of vulnerability in 101 case the advice about DYNAMIC_CRC_TABLE is ignored) */ 102 if (first) { 103 first = 0; 104 105 /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 106 poly = 0; 107 for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) |
| 130 poly |= (crc_table_t)1 << (31 - p[n]); | 108 poly |= (z_crc_t)1 << (31 - p[n]); |
| 131 132 /* generate a crc for every 8-bit value */ 133 for (n = 0; n < 256; n++) { | 109 110 /* generate a crc for every 8-bit value */ 111 for (n = 0; n < 256; n++) { |
| 134 c = (crc_table_t)n; | 112 c = (z_crc_t)n; |
| 135 for (k = 0; k < 8; k++) 136 c = c & 1 ? poly ^ (c >> 1) : c >> 1; 137 crc_table[0][n] = c; 138 } 139 140#ifdef BYFOUR 141 /* generate crc for each value followed by one, two, and three zeros, 142 and then the byte reversal of those as well as the first table */ 143 for (n = 0; n < 256; n++) { 144 c = crc_table[0][n]; | 113 for (k = 0; k < 8; k++) 114 c = c & 1 ? poly ^ (c >> 1) : c >> 1; 115 crc_table[0][n] = c; 116 } 117 118#ifdef BYFOUR 119 /* generate crc for each value followed by one, two, and three zeros, 120 and then the byte reversal of those as well as the first table */ 121 for (n = 0; n < 256; n++) { 122 c = crc_table[0][n]; |
| 145 crc_table[4][n] = REV(c); | 123 crc_table[4][n] = ZSWAP32(c); |
| 146 for (k = 1; k < 4; k++) { 147 c = crc_table[0][c & 0xff] ^ (c >> 8); 148 crc_table[k][n] = c; | 124 for (k = 1; k < 4; k++) { 125 c = crc_table[0][c & 0xff] ^ (c >> 8); 126 crc_table[k][n] = c; |
| 149 crc_table[k + 4][n] = REV(c); | 127 crc_table[k + 4][n] = ZSWAP32(c); |
| 150 } 151 } 152#endif /* BYFOUR */ 153 154 crc_table_empty = 0; 155 } 156 else { /* not first */ 157 /* wait for the other guy to finish (not efficient, but rare) */ --- 5 unchanged lines hidden (view full) --- 163 /* write out CRC tables to crc32.h */ 164 { 165 FILE *out; 166 167 out = fopen("crc32.h", "w"); 168 if (out == NULL) return; 169 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 170 fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); | 128 } 129 } 130#endif /* BYFOUR */ 131 132 crc_table_empty = 0; 133 } 134 else { /* not first */ 135 /* wait for the other guy to finish (not efficient, but rare) */ --- 5 unchanged lines hidden (view full) --- 141 /* write out CRC tables to crc32.h */ 142 { 143 FILE *out; 144 145 out = fopen("crc32.h", "w"); 146 if (out == NULL) return; 147 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 148 fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); |
| 171 fprintf(out, "local const crc_table_t FAR "); | 149 fprintf(out, "local const z_crc_t FAR "); |
| 172 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 173 write_table(out, crc_table[0]); 174# ifdef BYFOUR 175 fprintf(out, "#ifdef BYFOUR\n"); 176 for (k = 1; k < 8; k++) { 177 fprintf(out, " },\n {\n"); 178 write_table(out, crc_table[k]); 179 } 180 fprintf(out, "#endif\n"); 181# endif /* BYFOUR */ 182 fprintf(out, " }\n};\n"); 183 fclose(out); 184 } 185#endif /* MAKECRCH */ 186} 187 188#ifdef MAKECRCH 189local void write_table(out, table) 190 FILE *out; | 150 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 151 write_table(out, crc_table[0]); 152# ifdef BYFOUR 153 fprintf(out, "#ifdef BYFOUR\n"); 154 for (k = 1; k < 8; k++) { 155 fprintf(out, " },\n {\n"); 156 write_table(out, crc_table[k]); 157 } 158 fprintf(out, "#endif\n"); 159# endif /* BYFOUR */ 160 fprintf(out, " }\n};\n"); 161 fclose(out); 162 } 163#endif /* MAKECRCH */ 164} 165 166#ifdef MAKECRCH 167local void write_table(out, table) 168 FILE *out; |
| 191 const crc_table_t FAR *table; | 169 const z_crc_t FAR *table; |
| 192{ 193 int n; 194 195 for (n = 0; n < 256; n++) 196 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", 197 (unsigned long)(table[n]), 198 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 199} --- 4 unchanged lines hidden (view full) --- 204 * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 205 */ 206#include "crc32.h" 207#endif /* DYNAMIC_CRC_TABLE */ 208 209/* ========================================================================= 210 * This function can be used by asm versions of crc32() 211 */ | 170{ 171 int n; 172 173 for (n = 0; n < 256; n++) 174 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", 175 (unsigned long)(table[n]), 176 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 177} --- 4 unchanged lines hidden (view full) --- 182 * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 183 */ 184#include "crc32.h" 185#endif /* DYNAMIC_CRC_TABLE */ 186 187/* ========================================================================= 188 * This function can be used by asm versions of crc32() 189 */ |
| 212const unsigned long FAR * ZEXPORT get_crc_table() | 190const z_crc_t FAR * ZEXPORT get_crc_table() |
| 213{ 214#ifdef DYNAMIC_CRC_TABLE 215 if (crc_table_empty) 216 make_crc_table(); 217#endif /* DYNAMIC_CRC_TABLE */ | 191{ 192#ifdef DYNAMIC_CRC_TABLE 193 if (crc_table_empty) 194 make_crc_table(); 195#endif /* DYNAMIC_CRC_TABLE */ |
| 218 return (const unsigned long FAR *)crc_table; | 196 return (const z_crc_t FAR *)crc_table; |
| 219} 220 221/* ========================================================================= */ 222#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 223#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 224 225/* ========================================================================= */ 226unsigned long ZEXPORT crc32(crc, buf, len) --- 5 unchanged lines hidden (view full) --- 232 233#ifdef DYNAMIC_CRC_TABLE 234 if (crc_table_empty) 235 make_crc_table(); 236#endif /* DYNAMIC_CRC_TABLE */ 237 238#ifdef BYFOUR 239 if (sizeof(void *) == sizeof(ptrdiff_t)) { | 197} 198 199/* ========================================================================= */ 200#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 201#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 202 203/* ========================================================================= */ 204unsigned long ZEXPORT crc32(crc, buf, len) --- 5 unchanged lines hidden (view full) --- 210 211#ifdef DYNAMIC_CRC_TABLE 212 if (crc_table_empty) 213 make_crc_table(); 214#endif /* DYNAMIC_CRC_TABLE */ 215 216#ifdef BYFOUR 217 if (sizeof(void *) == sizeof(ptrdiff_t)) { |
| 240 u4 endian; | 218 z_crc_t endian; |
| 241 242 endian = 1; 243 if (*((unsigned char *)(&endian))) 244 return crc32_little(crc, buf, len); 245 else 246 return crc32_big(crc, buf, len); 247 } 248#endif /* BYFOUR */ --- 17 unchanged lines hidden (view full) --- 266#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 267 268/* ========================================================================= */ 269local unsigned long crc32_little(crc, buf, len) 270 unsigned long crc; 271 const unsigned char FAR *buf; 272 unsigned len; 273{ | 219 220 endian = 1; 221 if (*((unsigned char *)(&endian))) 222 return crc32_little(crc, buf, len); 223 else 224 return crc32_big(crc, buf, len); 225 } 226#endif /* BYFOUR */ --- 17 unchanged lines hidden (view full) --- 244#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 245 246/* ========================================================================= */ 247local unsigned long crc32_little(crc, buf, len) 248 unsigned long crc; 249 const unsigned char FAR *buf; 250 unsigned len; 251{ |
| 274 register u4 c; 275 register const u4 FAR *buf4; | 252 register z_crc_t c; 253 register const z_crc_t FAR *buf4; |
| 276 | 254 |
| 277 c = (u4)crc; | 255 c = (z_crc_t)crc; |
| 278 c = ~c; 279 while (len && ((ptrdiff_t)buf & 3)) { 280 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 281 len--; 282 } 283 | 256 c = ~c; 257 while (len && ((ptrdiff_t)buf & 3)) { 258 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 259 len--; 260 } 261 |
| 284 buf4 = (const u4 FAR *)(const void FAR *)buf; | 262 buf4 = (const z_crc_t FAR *)(const void FAR *)buf; |
| 285 while (len >= 32) { 286 DOLIT32; 287 len -= 32; 288 } 289 while (len >= 4) { 290 DOLIT4; 291 len -= 4; 292 } --- 13 unchanged lines hidden (view full) --- 306#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 307 308/* ========================================================================= */ 309local unsigned long crc32_big(crc, buf, len) 310 unsigned long crc; 311 const unsigned char FAR *buf; 312 unsigned len; 313{ | 263 while (len >= 32) { 264 DOLIT32; 265 len -= 32; 266 } 267 while (len >= 4) { 268 DOLIT4; 269 len -= 4; 270 } --- 13 unchanged lines hidden (view full) --- 284#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 285 286/* ========================================================================= */ 287local unsigned long crc32_big(crc, buf, len) 288 unsigned long crc; 289 const unsigned char FAR *buf; 290 unsigned len; 291{ |
| 314 register u4 c; 315 register const u4 FAR *buf4; | 292 register z_crc_t c; 293 register const z_crc_t FAR *buf4; |
| 316 | 294 |
| 317 c = REV((u4)crc); | 295 c = ZSWAP32((z_crc_t)crc); |
| 318 c = ~c; 319 while (len && ((ptrdiff_t)buf & 3)) { 320 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 321 len--; 322 } 323 | 296 c = ~c; 297 while (len && ((ptrdiff_t)buf & 3)) { 298 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 299 len--; 300 } 301 |
| 324 buf4 = (const u4 FAR *)(const void FAR *)buf; | 302 buf4 = (const z_crc_t FAR *)(const void FAR *)buf; |
| 325 buf4--; 326 while (len >= 32) { 327 DOBIG32; 328 len -= 32; 329 } 330 while (len >= 4) { 331 DOBIG4; 332 len -= 4; 333 } 334 buf4++; 335 buf = (const unsigned char FAR *)buf4; 336 337 if (len) do { 338 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 339 } while (--len); 340 c = ~c; | 303 buf4--; 304 while (len >= 32) { 305 DOBIG32; 306 len -= 32; 307 } 308 while (len >= 4) { 309 DOBIG4; 310 len -= 4; 311 } 312 buf4++; 313 buf = (const unsigned char FAR *)buf4; 314 315 if (len) do { 316 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 317 } while (--len); 318 c = ~c; |
| 341 return (unsigned long)(REV(c)); | 319 return (unsigned long)(ZSWAP32(c)); |
| 342} 343 344#endif /* BYFOUR */ 345 346#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 347 348/* ========================================================================= */ 349local unsigned long gf2_matrix_times(mat, vec) --- 98 unchanged lines hidden --- | 320} 321 322#endif /* BYFOUR */ 323 324#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 325 326/* ========================================================================= */ 327local unsigned long gf2_matrix_times(mat, vec) --- 98 unchanged lines hidden --- |