1/*
2 * Copyright (c) 2008-2016 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/* crc32.c -- compute the CRC-32 of a data stream
29 * Copyright (C) 1995-2005 Mark Adler
30 * For conditions of distribution and use, see copyright notice in zlib.h
31 *
32 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
33 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
34 * tables for updating the shift register in one step with three exclusive-ors
35 * instead of four steps with four exclusive-ors. This results in about a
36 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
37 */
38
39/* @(#) $Id$ */
40
41/*
42 Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
43 protection on the static variables used to control the first-use generation
44 of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
45 first call get_crc_table() to initialize the tables before allowing more than
46 one thread to use crc32().
47 */
48
49
50#ifdef MAKECRCH
51# include <stdio.h>
52# ifndef DYNAMIC_CRC_TABLE
53# define DYNAMIC_CRC_TABLE
54# endif /* !DYNAMIC_CRC_TABLE */
55#endif /* MAKECRCH */
56
57#include "zutil.h" /* for STDC and FAR definitions */
58
59#define local static
60
61/* Find a four-byte integer type for crc32_little() and crc32_big(). */
62#ifndef NOBYFOUR
63# ifdef STDC /* need ANSI C limits.h to determine sizes */
64# include <machine/limits.h>
65# define BYFOUR
66# if (UINT_MAX == 0xffffffffUL)
67 typedef unsigned int u4;
68# else
69# if (ULONG_MAX == 0xffffffffUL)
70 typedef unsigned long u4;
71# else
72# if (USHRT_MAX == 0xffffffffUL)
73 typedef unsigned short u4;
74# else
75# undef BYFOUR /* can't find a four-byte integer type! */
76# endif
77# endif
78# endif
79# endif /* STDC */
80#endif /* !NOBYFOUR */
81
82/* Definitions for doing the crc four data bytes at a time. */
83#ifdef BYFOUR
84# define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
85 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
86 local unsigned long crc32_little OF((unsigned long,
87 const unsigned char FAR *, unsigned));
88 local unsigned long crc32_big OF((unsigned long,
89 const unsigned char FAR *, unsigned));
90# define TBLS 8
91#else
92# define TBLS 1
93#endif /* BYFOUR */
94
95/* Local functions for crc concatenation */
96local unsigned long gf2_matrix_times OF((unsigned long *mat,
97 unsigned long vec));
98local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
99
100#ifdef DYNAMIC_CRC_TABLE
101
102local volatile int crc_table_empty = 1;
103local unsigned long FAR crc_table[TBLS][256];
104local void make_crc_table OF((void));
105#ifdef MAKECRCH
106 local void write_table OF((FILE *, const unsigned long FAR *));
107#endif /* MAKECRCH */
108/*
109 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
110 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.
111
112 Polynomials over GF(2) are represented in binary, one bit per coefficient,
113 with the lowest powers in the most significant bit. Then adding polynomials
114 is just exclusive-or, and multiplying a polynomial by x is a right shift by
115 one. If we call the above polynomial p, and represent a byte as the
116 polynomial q, also with the lowest power in the most significant bit (so the
117 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
118 where a mod b means the remainder after dividing a by b.
119
120 This calculation is done using the shift-register method of multiplying and
121 taking the remainder. The register is initialized to zero, and for each
122 incoming bit, x^32 is added mod p to the register if the bit is a one (where
123 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
124 x (which is shifting right by one and adding x^32 mod p if the bit shifted
125 out is a one). We start with the highest power (least significant bit) of
126 q and repeat for all eight bits of q.
127
128 The first table is simply the CRC of all possible eight bit values. This is
129 all the information needed to generate CRCs on data a byte at a time for all
130 combinations of CRC register values and incoming bytes. The remaining tables
131 allow for word-at-a-time CRC calculation for both big-endian and little-
132 endian machines, where a word is four bytes.
133*/
134local void
135make_crc_table(void)
136{
137 unsigned long c;
138 int n, k;
139 unsigned long poly; /* polynomial exclusive-or pattern */
140 /* terms of polynomial defining this crc (except x^32): */
141 static volatile int first = 1; /* flag to limit concurrent making */
142 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
143
144 /* See if another task is already doing this (not thread-safe, but better
145 than nothing -- significantly reduces duration of vulnerability in
146 case the advice about DYNAMIC_CRC_TABLE is ignored) */
147 if (first) {
148 first = 0;
149
150 /* make exclusive-or pattern from polynomial (0xedb88320UL) */
151 poly = 0UL;
152 for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
153 poly |= 1UL << (31 - p[n]);
154
155 /* generate a crc for every 8-bit value */
156 for (n = 0; n < 256; n++) {
157 c = (unsigned long)n;
158 for (k = 0; k < 8; k++)
159 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
160 crc_table[0][n] = c;
161 }
162
163#ifdef BYFOUR
164 /* generate crc for each value followed by one, two, and three zeros,
165 and then the byte reversal of those as well as the first table */
166 for (n = 0; n < 256; n++) {
167 c = crc_table[0][n];
168 crc_table[4][n] = REV(c);
169 for (k = 1; k < 4; k++) {
170 c = crc_table[0][c & 0xff] ^ (c >> 8);
171 crc_table[k][n] = c;
172 crc_table[k + 4][n] = REV(c);
173 }
174 }
175#endif /* BYFOUR */
176
177 crc_table_empty = 0;
178 }
179 else { /* not first */
180 /* wait for the other guy to finish (not efficient, but rare) */
181 while (crc_table_empty)
182 ;
183 }
184
185#ifdef MAKECRCH
186 /* write out CRC tables to crc32.h */
187 {
188 FILE *out;
189
190 out = fopen("crc32.h", "w");
191 if (out == NULL) return;
192 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
193 fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
194 fprintf(out, "local const unsigned long FAR ");
195 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
196 write_table(out, crc_table[0]);
197# ifdef BYFOUR
198 fprintf(out, "#ifdef BYFOUR\n");
199 for (k = 1; k < 8; k++) {
200 fprintf(out, " },\n {\n");
201 write_table(out, crc_table[k]);
202 }
203 fprintf(out, "#endif\n");
204# endif /* BYFOUR */
205 fprintf(out, " }\n};\n");
206 fclose(out);
207 }
208#endif /* MAKECRCH */
209}
210
211#ifdef MAKECRCH
212local void
213write_table(FILE *out, const unsigned long FAR *table)
214{
215 int n;
216
217 for (n = 0; n < 256; n++)
218 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n],
219 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
220}
221#endif /* MAKECRCH */
222
223#else /* !DYNAMIC_CRC_TABLE */
224/* ========================================================================
225 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
226 */
227#include "crc32.h"
228#endif /* DYNAMIC_CRC_TABLE */
229
230/* =========================================================================
231 * This function can be used by asm versions of crc32()
232 */
233const unsigned long FAR * ZEXPORT
234get_crc_table(void)
235{
236#ifdef DYNAMIC_CRC_TABLE
237 if (crc_table_empty)
238 make_crc_table();
239#endif /* DYNAMIC_CRC_TABLE */
240 return (const unsigned long FAR *)crc_table;
241}
242
243/* ========================================================================= */
244#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
245#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
246
247/* ========================================================================= */
248unsigned long ZEXPORT
249z_crc32(unsigned long crc, const unsigned char FAR *buf, unsigned len)
250{
251 if (buf == Z_NULL) return 0UL;
252
253#ifdef DYNAMIC_CRC_TABLE
254 if (crc_table_empty)
255 make_crc_table();
256#endif /* DYNAMIC_CRC_TABLE */
257
258#ifdef BYFOUR
259 if (sizeof(void *) == sizeof(ptrdiff_t)) {
260 u4 endian;
261
262 endian = 1;
263 if (*((unsigned char *)(&endian)))
264 return crc32_little(crc, buf, len);
265 else
266 return crc32_big(crc, buf, len);
267 }
268#endif /* BYFOUR */
269 crc = crc ^ 0xffffffffUL;
270 while (len >= 8) {
271 DO8;
272 len -= 8;
273 }
274 if (len) do {
275 DO1;
276 } while (--len);
277 return crc ^ 0xffffffffUL;
278}
279
280#ifdef BYFOUR
281
282/* ========================================================================= */
283#define DOLIT4 c ^= *buf4++; \
284 c = (u4)(crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
285 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24])
286#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
287
288/* ========================================================================= */
289local unsigned long
290crc32_little(unsigned long crc, const unsigned char FAR *buf, unsigned len)
291{
292 u4 c;
293 const u4 FAR *buf4;
294
295 c = (u4)crc;
296 c = ~c;
297 while (len && ((ptrdiff_t)buf & 3)) {
298 c = (u4)(crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8));
299 len--;
300 }
301
302 buf4 = (const u4 FAR *)(const void FAR *)buf;
303 while (len >= 32) {
304 DOLIT32;
305 len -= 32;
306 }
307 while (len >= 4) {
308 DOLIT4;
309 len -= 4;
310 }
311 buf = (const unsigned char FAR *)buf4;
312
313 if (len) do {
314 c = (u4)(crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8));
315 } while (--len);
316 c = ~c;
317 return (unsigned long)c;
318}
319
320/* ========================================================================= */
321#define DOBIG4 c ^= *++buf4; \
322 c = (u4)(crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
323 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24])
324#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
325
326/* ========================================================================= */
327local unsigned long
328crc32_big(unsigned long crc, const unsigned char FAR *buf, unsigned len)
329{
330 u4 c;
331 const u4 FAR *buf4;
332
333 c = REV((u4)crc);
334 c = ~c;
335 while (len && ((ptrdiff_t)buf & 3)) {
336 c = (u4)(crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8));
337 len--;
338 }
339
340 buf4 = (const u4 FAR *)(const void FAR *)buf;
341 buf4--;
342 while (len >= 32) {
343 DOBIG32;
344 len -= 32;
345 }
346 while (len >= 4) {
347 DOBIG4;
348 len -= 4;
349 }
350 buf4++;
351 buf = (const unsigned char FAR *)buf4;
352
353 if (len) do {
354 c = (u4)(crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8));
355 } while (--len);
356 c = ~c;
357 return (unsigned long)(REV(c));
358}
359
360#endif /* BYFOUR */
361
362#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */
363
364/* ========================================================================= */
365local unsigned long
366gf2_matrix_times(unsigned long *mat, unsigned long vec)
367{
368 unsigned long sum;
369
370 sum = 0;
371 while (vec) {
372 if (vec & 1)
373 sum ^= *mat;
374 vec >>= 1;
375 mat++;
376 }
377 return sum;
378}
379
380/* ========================================================================= */
381local void
382gf2_matrix_square(unsigned long *square, unsigned long *mat)
383{
384 int n;
385
386 for (n = 0; n < GF2_DIM; n++)
387 square[n] = gf2_matrix_times(mat, vec: mat[n]);
388}
389
390/* ========================================================================= */
391uLong ZEXPORT
392z_crc32_combine(uLong crc1, uLong crc2, z_off_t len2)
393{
394 int n;
395 unsigned long row;
396 unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */
397 unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */
398
399 /* degenerate case */
400 if (len2 == 0)
401 return crc1;
402
403 /* put operator for one zero bit in odd */
404 odd[0] = 0xedb88320L; /* CRC-32 polynomial */
405 row = 1;
406 for (n = 1; n < GF2_DIM; n++) {
407 odd[n] = row;
408 row <<= 1;
409 }
410
411 /* put operator for two zero bits in even */
412 gf2_matrix_square(square: even, mat: odd);
413
414 /* put operator for four zero bits in odd */
415 gf2_matrix_square(square: odd, mat: even);
416
417 /* apply len2 zeros to crc1 (first square will put the operator for one
418 zero byte, eight zero bits, in even) */
419 do {
420 /* apply zeros operator for this bit of len2 */
421 gf2_matrix_square(square: even, mat: odd);
422 if (len2 & 1)
423 crc1 = gf2_matrix_times(mat: even, vec: crc1);
424 len2 >>= 1;
425
426 /* if no more bits set, then done */
427 if (len2 == 0)
428 break;
429
430 /* another iteration of the loop with odd and even swapped */
431 gf2_matrix_square(square: odd, mat: even);
432 if (len2 & 1)
433 crc1 = gf2_matrix_times(mat: odd, vec: crc1);
434 len2 >>= 1;
435
436 /* if no more bits set, then done */
437 } while (len2 != 0);
438
439 /* return combined crc */
440 crc1 ^= crc2;
441 return crc1;
442}
443