1 /* zlib.h -- interface of the 'zlib' general purpose compression library
2 version 1.2.11, January 15th, 2017
3
4 Copyright (C) 1995-2017 Jean-loup Gailly and Mark Adler
5
6 This software is provided 'as-is', without any express or implied
7 warranty. In no event will the authors be held liable for any damages
8 arising from the use of this software.
9
10 Permission is granted to anyone to use this software for any purpose,
11 including commercial applications, and to alter it and redistribute it
12 freely, subject to the following restrictions:
13
14 1. The origin of this software must not be misrepresented; you must not
15 claim that you wrote the original software. If you use this software
16 in a product, an acknowledgment in the product documentation would be
17 appreciated but is not required.
18 2. Altered source versions must be plainly marked as such, and must not be
19 misrepresented as being the original software.
20 3. This notice may not be removed or altered from any source distribution.
21
22 Jean-loup Gailly Mark Adler
23 jloup@gzip.org madler@alumni.caltech.edu
24
25
26 The data format used by the zlib library is described by RFCs (Request for
27 Comments) 1950 to 1952 in the files http://tools.ietf.org/html/rfc1950
28 (zlib format), rfc1951 (deflate format) and rfc1952 (gzip format).
29 */
30
31 /* crc32.c -- compute the CRC-32 of a data stream
32 * Copyright (C) 1995-2006, 2010, 2011, 2012, 2016 Mark Adler
33 * For conditions of distribution and use, see copyright notice in zlib.h
34 *
35 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
36 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
37 * tables for updating the shift register in one step with three exclusive-ors
38 * instead of four steps with four exclusive-ors. This results in about a
39 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
40 */
41
42 /**
43 Modified to make it standalone.
44 Dennis Heimbigner
45 UCAR
46 */
47
48 /* crc32.c -- compute the CRC-32 of a data stream
49 * Copyright (C) 1995-2006, 2010, 2011, 2012, 2016 Mark Adler
50 * For conditions of distribution and use, see copyright notice in zlib.h
51 *
52 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
53 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
54 * tables for updating the shift register in one step with three exclusive-ors
55 * instead of four steps with four exclusive-ors. This results in about a
56 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
57 */
58
59 /* @(#) $Id$ */
60
61 /*
62 Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
63 protection on the static variables used to control the first-use generation
64 of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
65 first call get_crc_table() to initialize the tables before allowing more than
66 one thread to use crc32().
67
68 DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h.
69 */
70
71 /* Prototype for the crc32 function
72 extern unsigned int NC_crc32(unsigned int crc, const unsigned char* buf, unsigned int len);
73 */
74
75 /* Define some of the macros used here */
76 #define FAR
77 #define ZEXPORT
78 #define local static
79 #define OF(x) x
80 #define uLong unsigned long
81 #define uInt unsigned int
82 #define z_off64_t long long
83 #define z_off_t long
84 #define z_crc_t unsigned long
85 #define z_size_t size_t
86 #define Z_NULL NULL
87
88 #include <stdlib.h>
89
90 #ifdef MAKECRCH
91 # include <stdio.h>
92 # ifndef DYNAMIC_CRC_TABLE
93 # define DYNAMIC_CRC_TABLE
94 # endif /* !DYNAMIC_CRC_TABLE */
95 #endif /* MAKECRCH */
96
97
98 /* Definitions for doing the crc four data bytes at a time. */
99 #if !defined(NOBYFOUR) && defined(Z_U4)
100 # define BYFOUR
101 #endif
102 #ifdef BYFOUR
103 local unsigned long crc32_little OF((unsigned long,
104 const unsigned char FAR *, z_size_t));
105 local unsigned long crc32_big OF((unsigned long,
106 const unsigned char FAR *, z_size_t));
107 # define TBLS 8
108 #else
109 # define TBLS 1
110 #endif /* BYFOUR */
111
112 #ifdef DYNAMIC_CRC_TABLE
113
114 local volatile int crc_table_empty = 1;
115 local z_crc_t FAR crc_table[TBLS][256];
116 local void make_crc_table OF((void));
117 #ifdef MAKECRCH
118 local void write_table OF((FILE *, const z_crc_t FAR *));
119 #endif /* MAKECRCH */
120 /*
121 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
122 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.
123
124 Polynomials over GF(2) are represented in binary, one bit per coefficient,
125 with the lowest powers in the most significant bit. Then adding polynomials
126 is just exclusive-or, and multiplying a polynomial by x is a right shift by
127 one. If we call the above polynomial p, and represent a byte as the
128 polynomial q, also with the lowest power in the most significant bit (so the
129 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
130 where a mod b means the remainder after dividing a by b.
131
132 This calculation is done using the shift-register method of multiplying and
133 taking the remainder. The register is initialized to zero, and for each
134 incoming bit, x^32 is added mod p to the register if the bit is a one (where
135 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
136 x (which is shifting right by one and adding x^32 mod p if the bit shifted
137 out is a one). We start with the highest power (least significant bit) of
138 q and repeat for all eight bits of q.
139
140 The first table is simply the CRC of all possible eight bit values. This is
141 all the information needed to generate CRCs on data a byte at a time for all
142 combinations of CRC register values and incoming bytes. The remaining tables
143 allow for word-at-a-time CRC calculation for both big-endian and little-
144 endian machines, where a word is four bytes.
145 */
make_crc_table()146 local void make_crc_table()
147 {
148 z_crc_t c;
149 int n, k;
150 z_crc_t poly; /* polynomial exclusive-or pattern */
151 /* terms of polynomial defining this crc (except x^32): */
152 static volatile int first = 1; /* flag to limit concurrent making */
153 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
154
155 /* See if another task is already doing this (not thread-safe, but better
156 than nothing -- significantly reduces duration of vulnerability in
157 case the advice about DYNAMIC_CRC_TABLE is ignored) */
158 if (first) {
159 first = 0;
160
161 /* make exclusive-or pattern from polynomial (0xedb88320UL) */
162 poly = 0;
163 for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
164 poly |= (z_crc_t)1 << (31 - p[n]);
165
166 /* generate a crc for every 8-bit value */
167 for (n = 0; n < 256; n++) {
168 c = (z_crc_t)n;
169 for (k = 0; k < 8; k++)
170 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
171 crc_table[0][n] = c;
172 }
173
174 #ifdef BYFOUR
175 /* generate crc for each value followed by one, two, and three zeros,
176 and then the byte reversal of those as well as the first table */
177 for (n = 0; n < 256; n++) {
178 c = crc_table[0][n];
179 crc_table[4][n] = ZSWAP32(c);
180 for (k = 1; k < 4; k++) {
181 c = crc_table[0][c & 0xff] ^ (c >> 8);
182 crc_table[k][n] = c;
183 crc_table[k + 4][n] = ZSWAP32(c);
184 }
185 }
186 #endif /* BYFOUR */
187
188 crc_table_empty = 0;
189 }
190 else { /* not first */
191 /* wait for the other guy to finish (not efficient, but rare) */
192 while (crc_table_empty)
193 ;
194 }
195
196 #ifdef MAKECRCH
197 /* write out CRC tables to crc32.h */
198 {
199 FILE *out;
200
201 out = fopen("crc32.h", "w");
202 if (out == NULL) return;
203 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
204 fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
205 fprintf(out, "local const z_crc_t FAR ");
206 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
207 write_table(out, crc_table[0]);
208 # ifdef BYFOUR
209 fprintf(out, "#ifdef BYFOUR\n");
210 for (k = 1; k < 8; k++) {
211 fprintf(out, " },\n {\n");
212 write_table(out, crc_table[k]);
213 }
214 fprintf(out, "#endif\n");
215 # endif /* BYFOUR */
216 fprintf(out, " }\n};\n");
217 fclose(out);
218 }
219 #endif /* MAKECRCH */
220 }
221
222 #ifdef MAKECRCH
write_table(out,table)223 local void write_table(out, table)
224 FILE *out;
225 const z_crc_t FAR *table;
226 {
227 int n;
228
229 for (n = 0; n < 256; n++)
230 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ",
231 (unsigned long)(table[n]),
232 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
233 }
234 #endif /* MAKECRCH */
235
236 #else /* !DYNAMIC_CRC_TABLE */
237 /* ========================================================================
238 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
239 */
240 #include "crc32.h"
241 #endif /* DYNAMIC_CRC_TABLE */
242
243 /* =========================================================================
244 * This function can be used by asm versions of crc32()
245 */
246 #if 0 /* Unused */
247 local const z_crc_t FAR * ZEXPORT get_crc_table()
248 {
249 #ifdef DYNAMIC_CRC_TABLE
250 if (crc_table_empty)
251 make_crc_table();
252 #endif /* DYNAMIC_CRC_TABLE */
253 return (const z_crc_t FAR *)crc_table;
254 }
255 #endif
256
257 /* ========================================================================= */
258 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
259 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
260
261 /* ========================================================================= */
crc32_z(crc,buf,len)262 local unsigned long ZEXPORT crc32_z(crc, buf, len)
263 unsigned long crc;
264 const unsigned char FAR *buf;
265 z_size_t len;
266 {
267 if (buf == Z_NULL) return 0UL;
268
269 #ifdef DYNAMIC_CRC_TABLE
270 if (crc_table_empty)
271 make_crc_table();
272 #endif /* DYNAMIC_CRC_TABLE */
273
274 #ifdef BYFOUR
275 if (sizeof(void *) == sizeof(ptrdiff_t)) {
276 z_crc_t endian;
277
278 endian = 1;
279 if (*((unsigned char *)(&endian)))
280 return crc32_little(crc, buf, len);
281 else
282 return crc32_big(crc, buf, len);
283 }
284 #endif /* BYFOUR */
285 crc = crc ^ 0xffffffffUL;
286 while (len >= 8) {
287 DO8;
288 len -= 8;
289 }
290 if (len) do {
291 DO1;
292 } while (--len);
293 return crc ^ 0xffffffffUL;
294 }
295
296 /* ========================================================================= */
NC_crc32(unsigned int crc,const unsigned char * buf,unsigned int len)297 unsigned int ZEXPORT NC_crc32(unsigned int crc, const unsigned char* buf, unsigned int len)
298 {
299 unsigned long value = (unsigned long)crc;
300 value = crc32_z(value, buf, len);
301 return (unsigned int)(value & 0xFFFFFFFF); /* in case |long| is 64 bits */
302 }
303
304 #ifdef BYFOUR
305
306 /*
307 This BYFOUR code accesses the passed unsigned char * buffer with a 32-bit
308 integer pointer type. This violates the strict aliasing rule, where a
309 compiler can assume, for optimization purposes, that two pointers to
310 fundamentally different types won't ever point to the same memory. This can
311 manifest as a problem only if one of the pointers is written to. This code
312 only reads from those pointers. So long as this code remains isolated in
313 this compilation unit, there won't be a problem. For this reason, this code
314 should not be copied and pasted into a compilation unit in which other code
315 writes to the buffer that is passed to these routines.
316 */
317
318 /* ========================================================================= */
319 #define DOLIT4 c ^= *buf4++; \
320 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
321 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
322 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
323
324 /* ========================================================================= */
crc32_little(crc,buf,len)325 local unsigned long crc32_little(crc, buf, len)
326 unsigned long crc;
327 const unsigned char FAR *buf;
328 z_size_t len;
329 {
330 register z_crc_t c;
331 register const z_crc_t FAR *buf4;
332
333 c = (z_crc_t)crc;
334 c = ~c;
335 while (len && ((ptrdiff_t)buf & 3)) {
336 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
337 len--;
338 }
339
340 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
341 while (len >= 32) {
342 DOLIT32;
343 len -= 32;
344 }
345 while (len >= 4) {
346 DOLIT4;
347 len -= 4;
348 }
349 buf = (const unsigned char FAR *)buf4;
350
351 if (len) do {
352 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
353 } while (--len);
354 c = ~c;
355 return (unsigned long)c;
356 }
357
358 /* ========================================================================= */
359 #define DOBIG4 c ^= *buf4++; \
360 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
361 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
362 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
363
364 /* ========================================================================= */
crc32_big(crc,buf,len)365 local unsigned long crc32_big(crc, buf, len)
366 unsigned long crc;
367 const unsigned char FAR *buf;
368 z_size_t len;
369 {
370 register z_crc_t c;
371 register const z_crc_t FAR *buf4;
372
373 c = ZSWAP32((z_crc_t)crc);
374 c = ~c;
375 while (len && ((ptrdiff_t)buf & 3)) {
376 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
377 len--;
378 }
379
380 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
381 while (len >= 32) {
382 DOBIG32;
383 len -= 32;
384 }
385 while (len >= 4) {
386 DOBIG4;
387 len -= 4;
388 }
389 buf = (const unsigned char FAR *)buf4;
390
391 if (len) do {
392 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
393 } while (--len);
394 c = ~c;
395 return (unsigned long)(ZSWAP32(c));
396 }
397
398 #endif /* BYFOUR */
399
400 #define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */
401
402 /* ========================================================================= */
403 #if 0 /* Unused */
404 local unsigned long gf2_matrix_times(mat, vec)
405 unsigned long *mat;
406 unsigned long vec;
407 {
408 unsigned long sum;
409
410 sum = 0;
411 while (vec) {
412 if (vec & 1)
413 sum ^= *mat;
414 vec >>= 1;
415 mat++;
416 }
417 return sum;
418 }
419
420 /* ========================================================================= */
421 local void gf2_matrix_square(square, mat)
422 unsigned long *square;
423 unsigned long *mat;
424 {
425 int n;
426
427 for (n = 0; n < GF2_DIM; n++)
428 square[n] = gf2_matrix_times(mat, mat[n]);
429 }
430
431 /* ========================================================================= */
432
433 local uLong crc32_combine_(crc1, crc2, len2)
434 uLong crc1;
435 uLong crc2;
436 z_off64_t len2;
437 {
438 int n;
439 unsigned long row;
440 unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */
441 unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */
442
443 /* degenerate case (also disallow negative lengths) */
444 if (len2 <= 0)
445 return crc1;
446
447 /* put operator for one zero bit in odd */
448 odd[0] = 0xedb88320UL; /* CRC-32 polynomial */
449 row = 1;
450 for (n = 1; n < GF2_DIM; n++) {
451 odd[n] = row;
452 row <<= 1;
453 }
454
455 /* put operator for two zero bits in even */
456 gf2_matrix_square(even, odd);
457
458 /* put operator for four zero bits in odd */
459 gf2_matrix_square(odd, even);
460
461 /* apply len2 zeros to crc1 (first square will put the operator for one
462 zero byte, eight zero bits, in even) */
463 do {
464 /* apply zeros operator for this bit of len2 */
465 gf2_matrix_square(even, odd);
466 if (len2 & 1)
467 crc1 = gf2_matrix_times(even, crc1);
468 len2 >>= 1;
469
470 /* if no more bits set, then done */
471 if (len2 == 0)
472 break;
473
474 /* another iteration of the loop with odd and even swapped */
475 gf2_matrix_square(odd, even);
476 if (len2 & 1)
477 crc1 = gf2_matrix_times(odd, crc1);
478 len2 >>= 1;
479
480 /* if no more bits set, then done */
481 } while (len2 != 0);
482
483 /* return combined crc */
484 crc1 ^= crc2;
485 return crc1;
486 }
487
488 /* ========================================================================= */
489 local uLong ZEXPORT crc32_combine(crc1, crc2, len2)
490 uLong crc1;
491 uLong crc2;
492 z_off_t len2;
493 {
494 return crc32_combine_(crc1, crc2, len2);
495 }
496
497 local uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
498 uLong crc1;
499 uLong crc2;
500 z_off64_t len2;
501 {
502 return crc32_combine_(crc1, crc2, len2);
503 }
504 #endif
505