00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifdef MAKECRCH
00023 # include <stdio.h>
00024 # ifndef DYNAMIC_CRC_TABLE
00025 # define DYNAMIC_CRC_TABLE
00026 # endif
00027 #endif
00028
00029 #include "zutil.h"
00030
00031 #define local static
00032
00033
00034 #ifndef NOBYFOUR
00035 # ifdef STDC
00036 # include <limits.h>
00037 # define BYFOUR
00038 # if (UINT_MAX == 0xffffffffUL)
00039 typedef unsigned int u4;
00040 # else
00041 # if (ULONG_MAX == 0xffffffffUL)
00042 typedef unsigned long u4;
00043 # else
00044 # if (USHRT_MAX == 0xffffffffUL)
00045 typedef unsigned short u4;
00046 # else
00047 # undef BYFOUR
00048 # endif
00049 # endif
00050 # endif
00051 # endif
00052 #endif
00053
00054
00055 #ifdef BYFOUR
00056 # define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
00057 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
00058 local unsigned long crc32_little OF((unsigned long,
00059 const unsigned char FAR *, unsigned));
00060 local unsigned long crc32_big OF((unsigned long,
00061 const unsigned char FAR *, unsigned));
00062 # define TBLS 8
00063 #else
00064 # define TBLS 1
00065 #endif
00066
00067
00068 local unsigned long gf2_matrix_times OF((unsigned long *mat,
00069 unsigned long vec));
00070 local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
00071
00072 #ifdef DYNAMIC_CRC_TABLE
00073
00074 local volatile int crc_table_empty = 1;
00075 local unsigned long FAR crc_table[TBLS][256];
00076 local void make_crc_table OF((void));
00077 #ifdef MAKECRCH
00078 local void write_table OF((FILE *, const unsigned long FAR *));
00079 #endif
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106 local void make_crc_table()
00107 {
00108 unsigned long c;
00109 int n, k;
00110 unsigned long poly;
00111
00112 static volatile int first = 1;
00113 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
00114
00115
00116
00117
00118 if (first) {
00119 first = 0;
00120
00121
00122 poly = 0UL;
00123 for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
00124 poly |= 1UL << (31 - p[n]);
00125
00126
00127 for (n = 0; n < 256; n++) {
00128 c = (unsigned long)n;
00129 for (k = 0; k < 8; k++)
00130 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
00131 crc_table[0][n] = c;
00132 }
00133
00134 #ifdef BYFOUR
00135
00136
00137 for (n = 0; n < 256; n++) {
00138 c = crc_table[0][n];
00139 crc_table[4][n] = REV(c);
00140 for (k = 1; k < 4; k++) {
00141 c = crc_table[0][c & 0xff] ^ (c >> 8);
00142 crc_table[k][n] = c;
00143 crc_table[k + 4][n] = REV(c);
00144 }
00145 }
00146 #endif
00147
00148 crc_table_empty = 0;
00149 }
00150 else {
00151
00152 while (crc_table_empty)
00153 ;
00154 }
00155
00156 #ifdef MAKECRCH
00157
00158 {
00159 FILE *out;
00160
00161 out = fopen("crc32.h", "w");
00162 if (out == NULL) return;
00163 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
00164 fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
00165 fprintf(out, "local const unsigned long FAR ");
00166 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
00167 write_table(out, crc_table[0]);
00168 # ifdef BYFOUR
00169 fprintf(out, "#ifdef BYFOUR\n");
00170 for (k = 1; k < 8; k++) {
00171 fprintf(out, " },\n {\n");
00172 write_table(out, crc_table[k]);
00173 }
00174 fprintf(out, "#endif\n");
00175 # endif
00176 fprintf(out, " }\n};\n");
00177 fclose(out);
00178 }
00179 #endif
00180 }
00181
00182 #ifdef MAKECRCH
00183 local void write_table(out, table)
00184 FILE *out;
00185 const unsigned long FAR *table;
00186 {
00187 int n;
00188
00189 for (n = 0; n < 256; n++)
00190 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n],
00191 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
00192 }
00193 #endif
00194
00195 #else
00196
00197
00198
00199 #include "crc32.h"
00200 #endif
00201
00202
00203
00204
00205 const unsigned long FAR * ZEXPORT get_crc_table()
00206 {
00207 #ifdef DYNAMIC_CRC_TABLE
00208 if (crc_table_empty)
00209 make_crc_table();
00210 #endif
00211 return (const unsigned long FAR *)crc_table;
00212 }
00213
00214
00215 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
00216 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
00217
00218
00219 unsigned long ZEXPORT crc32(crc, buf, len)
00220 unsigned long crc;
00221 const unsigned char FAR *buf;
00222 unsigned len;
00223 {
00224 if (buf == Z_NULL) return 0UL;
00225
00226 #ifdef DYNAMIC_CRC_TABLE
00227 if (crc_table_empty)
00228 make_crc_table();
00229 #endif
00230
00231 #ifdef BYFOUR
00232 if (sizeof(void *) == sizeof(ptrdiff_t)) {
00233 u4 endian;
00234
00235 endian = 1;
00236 if (*((unsigned char *)(&endian)))
00237 return crc32_little(crc, buf, len);
00238 else
00239 return crc32_big(crc, buf, len);
00240 }
00241 #endif
00242 crc = crc ^ 0xffffffffUL;
00243 while (len >= 8) {
00244 DO8;
00245 len -= 8;
00246 }
00247 if (len) do {
00248 DO1;
00249 } while (--len);
00250 return crc ^ 0xffffffffUL;
00251 }
00252
00253 #ifdef BYFOUR
00254
00255
00256 #define DOLIT4 c ^= *buf4++; \
00257 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
00258 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
00259 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
00260
00261
00262 local unsigned long crc32_little(crc, buf, len)
00263 unsigned long crc;
00264 const unsigned char FAR *buf;
00265 unsigned len;
00266 {
00267 register u4 c;
00268 register const u4 FAR *buf4;
00269
00270 c = (u4)crc;
00271 c = ~c;
00272 while (len && ((ptrdiff_t)buf & 3)) {
00273 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
00274 len--;
00275 }
00276
00277 buf4 = (const u4 FAR *)(const void FAR *)buf;
00278 while (len >= 32) {
00279 DOLIT32;
00280 len -= 32;
00281 }
00282 while (len >= 4) {
00283 DOLIT4;
00284 len -= 4;
00285 }
00286 buf = (const unsigned char FAR *)buf4;
00287
00288 if (len) do {
00289 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
00290 } while (--len);
00291 c = ~c;
00292 return (unsigned long)c;
00293 }
00294
00295
00296 #define DOBIG4 c ^= *++buf4; \
00297 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
00298 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
00299 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
00300
00301
00302 local unsigned long crc32_big(crc, buf, len)
00303 unsigned long crc;
00304 const unsigned char FAR *buf;
00305 unsigned len;
00306 {
00307 register u4 c;
00308 register const u4 FAR *buf4;
00309
00310 c = REV((u4)crc);
00311 c = ~c;
00312 while (len && ((ptrdiff_t)buf & 3)) {
00313 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
00314 len--;
00315 }
00316
00317 buf4 = (const u4 FAR *)(const void FAR *)buf;
00318 buf4--;
00319 while (len >= 32) {
00320 DOBIG32;
00321 len -= 32;
00322 }
00323 while (len >= 4) {
00324 DOBIG4;
00325 len -= 4;
00326 }
00327 buf4++;
00328 buf = (const unsigned char FAR *)buf4;
00329
00330 if (len) do {
00331 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
00332 } while (--len);
00333 c = ~c;
00334 return (unsigned long)(REV(c));
00335 }
00336
00337 #endif
00338
00339 #define GF2_DIM 32
00340
00341
00342 local unsigned long gf2_matrix_times(mat, vec)
00343 unsigned long *mat;
00344 unsigned long vec;
00345 {
00346 unsigned long sum;
00347
00348 sum = 0;
00349 while (vec) {
00350 if (vec & 1)
00351 sum ^= *mat;
00352 vec >>= 1;
00353 mat++;
00354 }
00355 return sum;
00356 }
00357
00358
00359 local void gf2_matrix_square(square, mat)
00360 unsigned long *square;
00361 unsigned long *mat;
00362 {
00363 int n;
00364
00365 for (n = 0; n < GF2_DIM; n++)
00366 square[n] = gf2_matrix_times(mat, mat[n]);
00367 }
00368
00369
00370 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
00371 uLong crc1;
00372 uLong crc2;
00373 z_off_t len2;
00374 {
00375 int n;
00376 unsigned long row;
00377 unsigned long even[GF2_DIM];
00378 unsigned long odd[GF2_DIM];
00379
00380
00381 if (len2 == 0)
00382 return crc1;
00383
00384
00385 odd[0] = 0xedb88320L;
00386 row = 1;
00387 for (n = 1; n < GF2_DIM; n++) {
00388 odd[n] = row;
00389 row <<= 1;
00390 }
00391
00392
00393 gf2_matrix_square(even, odd);
00394
00395
00396 gf2_matrix_square(odd, even);
00397
00398
00399
00400 do {
00401
00402 gf2_matrix_square(even, odd);
00403 if (len2 & 1)
00404 crc1 = gf2_matrix_times(even, crc1);
00405 len2 >>= 1;
00406
00407
00408 if (len2 == 0)
00409 break;
00410
00411
00412 gf2_matrix_square(odd, even);
00413 if (len2 & 1)
00414 crc1 = gf2_matrix_times(odd, crc1);
00415 len2 >>= 1;
00416
00417
00418 } while (len2 != 0);
00419
00420
00421 crc1 ^= crc2;
00422 return crc1;
00423 }