1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21 /*
22 * The crc32c algorithms are taken from sctp_crc32 implementation
23 * common/inet/sctp_crc32.{c,h}, which in turn were taken from nxge_fflp_hash.c
24 */
25
26 #include <sys/zfs_context.h>
27 #include <sys/fits_crc32c.h>
28
29 static void fits_crc32c_word(uint32_t *crcptr, const uint32_t *buf, int len);
30
31 /*
32 * Fast CRC32C calculation algorithm. The basic idea is to look at it
33 * four bytes (one word) at a time, using four tables. The
34 * standard algorithm in RFC 3309 uses one table.
35 */
36
37 #define CRC_32C_POLY 0x1EDC6F41L
38
39 /* The four CRC32c tables. */
40 static uint32_t crc32c_tab[4][256];
41 static int initialized;
42
43
44 static uint32_t
45 reflect_32(uint32_t b)
46 {
47 int i;
48 uint32_t rw = 0;
49
50 for (i = 0; i < 32; i++) {
51 if (b & 1) {
52 rw |= 1 << (31 - i);
53 }
54 b >>= 1;
55 }
56 return (rw);
57 }
58
59 #ifdef _BIG_ENDIAN
60 static uint32_t
61 flip32(uint32_t w)
62 {
63 return (((w >> 24) | ((w >> 8) & 0xff00) |
64 ((w << 8) & 0xff0000) | (w << 24)));
65 }
66 #endif
67
68 /*
69 * Initialize the crc32c tables.
70 */
71
72 void
73 fits_crc32c_init(void)
74 {
75 uint32_t index, bit, byte, crc;
76
77 for (index = 0; index < 256; index++) {
78 crc = reflect_32(index);
79 for (byte = 0; byte < 4; byte++) {
80 for (bit = 0; bit < 8; bit++) {
81 crc = (crc & 0x80000000) ?
82 (crc << 1) ^ CRC_32C_POLY : crc << 1;
83 }
84 #ifdef _BIG_ENDIAN
85 crc32c_tab[3 - byte][index] = flip32(reflect_32(crc));
86 #else
87 crc32c_tab[byte][index] = reflect_32(crc);
88 #endif
89 }
90 }
91 }
92
93 /*
94 * Lookup the crc32c for a byte stream
95 */
96 static void
97 fits_crc32c_byte(uint32_t *crcptr, const uint8_t *buf, int len)
98 {
99 uint32_t crc;
100 int i;
101
102 crc = *crcptr;
103 for (i = 0; i < len; i++) {
104 #ifdef _BIG_ENDIAN
105 crc = (crc << 8) ^ crc32c_tab[3][buf[i] ^ (crc >> 24)];
106 #else
107 crc = (crc >> 8) ^ crc32c_tab[0][buf[i] ^ (crc & 0xff)];
108 #endif
109 }
110 *crcptr = crc;
111 }
112
113 /*
114 * Lookup the crc32c for a 32 bit word stream
115 * Lookup is done fro the 4 bytes in parallel
116 * from the tables computed earlier
117 *
118 */
119 static void
120 fits_crc32c_word(uint32_t *crcptr, const uint32_t *buf, int len)
121 {
122 uint32_t w, crc;
123 int i;
124
125 crc = *crcptr;
126 for (i = 0; i < len; i++) {
127 w = crc ^ buf[i];
128 crc = crc32c_tab[0][w >> 24] ^
129 crc32c_tab[1][(w >> 16) & 0xff] ^
130 crc32c_tab[2][(w >> 8) & 0xff] ^
131 crc32c_tab[3][w & 0xff];
132 }
133 *crcptr = crc;
134 }
135
136 /*
137 * Lookup the crc32c for a stream of bytes
138 *
139 * Tries to lookup the CRC on 4 byte words
140 * If the buffer is not 4 byte aligned, first compute
141 * with byte lookup until aligned. Then compute crc
142 * for each 4 bytes. If there are bytes left at the end of
143 * the buffer, then perform a byte lookup for the remaining bytes
144 *
145 *
146 */
147 uint32_t
148 fits_crc32c(uint32_t crc32, const uint8_t *buf, int len)
149 {
150 int rem;
151
152 if (!initialized) {
153 fits_crc32c_init();
154 initialized = 1;
155 }
156
157 rem = 4 - (((uintptr_t)buf) & 3);
158 if (rem != 0) {
159 if (len < rem) {
160 rem = len;
161 }
162 fits_crc32c_byte(&crc32, buf, rem);
163 buf = buf + rem;
164 len = len - rem;
165 }
166 if (len > 3) {
167 fits_crc32c_word(&crc32, (const uint32_t *) buf, len / 4);
168 }
169 rem = len & 3;
170 if (rem != 0) {
171 fits_crc32c_byte(&crc32, buf + len - rem, rem);
172 }
173 return (crc32);
174 }