1 | /* |
2 | * Copyright (C) 2013 Mark Adler |
3 | * Originally by: crc64.c Version 1.4 16 Dec 2013 Mark Adler |
4 | * Modifications by Matt Stancliff <[email protected]>: |
5 | * - removed CRC64-specific behavior |
6 | * - added generation of lookup tables by parameters |
7 | * - removed inversion of CRC input/result |
8 | * - removed automatic initialization in favor of explicit initialization |
9 | |
10 | This software is provided 'as-is', without any express or implied |
11 | warranty. In no event will the author be held liable for any damages |
12 | arising from the use of this software. |
13 | |
14 | Permission is granted to anyone to use this software for any purpose, |
15 | including commercial applications, and to alter it and redistribute it |
16 | freely, subject to the following restrictions: |
17 | |
18 | 1. The origin of this software must not be misrepresented; you must not |
19 | claim that you wrote the original software. If you use this software |
20 | in a product, an acknowledgment in the product documentation would be |
21 | appreciated but is not required. |
22 | 2. Altered source versions must be plainly marked as such, and must not be |
23 | misrepresented as being the original software. |
24 | 3. This notice may not be removed or altered from any source distribution. |
25 | |
26 | Mark Adler |
27 | [email protected] |
28 | */ |
29 | |
30 | #include "crcspeed.h" |
31 | |
32 | /* Fill in a CRC constants table. */ |
33 | void crcspeed64little_init(crcfn64 crcfn, uint64_t table[8][256]) { |
34 | uint64_t crc; |
35 | |
36 | /* generate CRCs for all single byte sequences */ |
37 | for (int n = 0; n < 256; n++) { |
38 | unsigned char v = n; |
39 | table[0][n] = crcfn(0, &v, 1); |
40 | } |
41 | |
42 | /* generate nested CRC table for future slice-by-8 lookup */ |
43 | for (int n = 0; n < 256; n++) { |
44 | crc = table[0][n]; |
45 | for (int k = 1; k < 8; k++) { |
46 | crc = table[0][crc & 0xff] ^ (crc >> 8); |
47 | table[k][n] = crc; |
48 | } |
49 | } |
50 | } |
51 | |
52 | void crcspeed16little_init(crcfn16 crcfn, uint16_t table[8][256]) { |
53 | uint16_t crc; |
54 | |
55 | /* generate CRCs for all single byte sequences */ |
56 | for (int n = 0; n < 256; n++) { |
57 | table[0][n] = crcfn(0, &n, 1); |
58 | } |
59 | |
60 | /* generate nested CRC table for future slice-by-8 lookup */ |
61 | for (int n = 0; n < 256; n++) { |
62 | crc = table[0][n]; |
63 | for (int k = 1; k < 8; k++) { |
64 | crc = table[0][(crc >> 8) & 0xff] ^ (crc << 8); |
65 | table[k][n] = crc; |
66 | } |
67 | } |
68 | } |
69 | |
70 | /* Reverse the bytes in a 64-bit word. */ |
71 | static inline uint64_t rev8(uint64_t a) { |
72 | #if defined(__GNUC__) || defined(__clang__) |
73 | return __builtin_bswap64(a); |
74 | #else |
75 | uint64_t m; |
76 | |
77 | m = UINT64_C(0xff00ff00ff00ff); |
78 | a = ((a >> 8) & m) | (a & m) << 8; |
79 | m = UINT64_C(0xffff0000ffff); |
80 | a = ((a >> 16) & m) | (a & m) << 16; |
81 | return a >> 32 | a << 32; |
82 | #endif |
83 | } |
84 | |
85 | /* This function is called once to initialize the CRC table for use on a |
86 | big-endian architecture. */ |
87 | void crcspeed64big_init(crcfn64 fn, uint64_t big_table[8][256]) { |
88 | /* Create the little endian table then reverse all the entries. */ |
89 | crcspeed64little_init(fn, big_table); |
90 | for (int k = 0; k < 8; k++) { |
91 | for (int n = 0; n < 256; n++) { |
92 | big_table[k][n] = rev8(big_table[k][n]); |
93 | } |
94 | } |
95 | } |
96 | |
97 | void crcspeed16big_init(crcfn16 fn, uint16_t big_table[8][256]) { |
98 | /* Create the little endian table then reverse all the entries. */ |
99 | crcspeed16little_init(fn, big_table); |
100 | for (int k = 0; k < 8; k++) { |
101 | for (int n = 0; n < 256; n++) { |
102 | big_table[k][n] = rev8(big_table[k][n]); |
103 | } |
104 | } |
105 | } |
106 | |
107 | /* Calculate a non-inverted CRC multiple bytes at a time on a little-endian |
108 | * architecture. If you need inverted CRC, invert *before* calling and invert |
109 | * *after* calling. |
110 | * 64 bit crc = process 8 bytes at once; |
111 | */ |
112 | uint64_t crcspeed64little(uint64_t little_table[8][256], uint64_t crc, |
113 | void *buf, size_t len) { |
114 | unsigned char *next = buf; |
115 | |
116 | /* process individual bytes until we reach an 8-byte aligned pointer */ |
117 | while (len && ((uintptr_t)next & 7) != 0) { |
118 | crc = little_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8); |
119 | len--; |
120 | } |
121 | |
122 | /* fast middle processing, 8 bytes (aligned!) per loop */ |
123 | while (len >= 8) { |
124 | crc ^= *(uint64_t *)next; |
125 | crc = little_table[7][crc & 0xff] ^ |
126 | little_table[6][(crc >> 8) & 0xff] ^ |
127 | little_table[5][(crc >> 16) & 0xff] ^ |
128 | little_table[4][(crc >> 24) & 0xff] ^ |
129 | little_table[3][(crc >> 32) & 0xff] ^ |
130 | little_table[2][(crc >> 40) & 0xff] ^ |
131 | little_table[1][(crc >> 48) & 0xff] ^ |
132 | little_table[0][crc >> 56]; |
133 | next += 8; |
134 | len -= 8; |
135 | } |
136 | |
137 | /* process remaining bytes (can't be larger than 8) */ |
138 | while (len) { |
139 | crc = little_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8); |
140 | len--; |
141 | } |
142 | |
143 | return crc; |
144 | } |
145 | |
146 | uint16_t crcspeed16little(uint16_t little_table[8][256], uint16_t crc, |
147 | void *buf, size_t len) { |
148 | unsigned char *next = buf; |
149 | |
150 | /* process individual bytes until we reach an 8-byte aligned pointer */ |
151 | while (len && ((uintptr_t)next & 7) != 0) { |
152 | crc = little_table[0][((crc >> 8) ^ *next++) & 0xff] ^ (crc << 8); |
153 | len--; |
154 | } |
155 | |
156 | /* fast middle processing, 8 bytes (aligned!) per loop */ |
157 | while (len >= 8) { |
158 | uint64_t n = *(uint64_t *)next; |
159 | crc = little_table[7][(n & 0xff) ^ ((crc >> 8) & 0xff)] ^ |
160 | little_table[6][((n >> 8) & 0xff) ^ (crc & 0xff)] ^ |
161 | little_table[5][(n >> 16) & 0xff] ^ |
162 | little_table[4][(n >> 24) & 0xff] ^ |
163 | little_table[3][(n >> 32) & 0xff] ^ |
164 | little_table[2][(n >> 40) & 0xff] ^ |
165 | little_table[1][(n >> 48) & 0xff] ^ |
166 | little_table[0][n >> 56]; |
167 | next += 8; |
168 | len -= 8; |
169 | } |
170 | |
171 | /* process remaining bytes (can't be larger than 8) */ |
172 | while (len) { |
173 | crc = little_table[0][((crc >> 8) ^ *next++) & 0xff] ^ (crc << 8); |
174 | len--; |
175 | } |
176 | |
177 | return crc; |
178 | } |
179 | |
180 | /* Calculate a non-inverted CRC eight bytes at a time on a big-endian |
181 | * architecture. |
182 | */ |
183 | uint64_t crcspeed64big(uint64_t big_table[8][256], uint64_t crc, void *buf, |
184 | size_t len) { |
185 | unsigned char *next = buf; |
186 | |
187 | crc = rev8(crc); |
188 | while (len && ((uintptr_t)next & 7) != 0) { |
189 | crc = big_table[0][(crc >> 56) ^ *next++] ^ (crc << 8); |
190 | len--; |
191 | } |
192 | |
193 | while (len >= 8) { |
194 | crc ^= *(uint64_t *)next; |
195 | crc = big_table[0][crc & 0xff] ^ |
196 | big_table[1][(crc >> 8) & 0xff] ^ |
197 | big_table[2][(crc >> 16) & 0xff] ^ |
198 | big_table[3][(crc >> 24) & 0xff] ^ |
199 | big_table[4][(crc >> 32) & 0xff] ^ |
200 | big_table[5][(crc >> 40) & 0xff] ^ |
201 | big_table[6][(crc >> 48) & 0xff] ^ |
202 | big_table[7][crc >> 56]; |
203 | next += 8; |
204 | len -= 8; |
205 | } |
206 | |
207 | while (len) { |
208 | crc = big_table[0][(crc >> 56) ^ *next++] ^ (crc << 8); |
209 | len--; |
210 | } |
211 | |
212 | return rev8(crc); |
213 | } |
214 | |
215 | /* WARNING: Completely untested on big endian architecture. Possibly broken. */ |
216 | uint16_t crcspeed16big(uint16_t big_table[8][256], uint16_t crc_in, void *buf, |
217 | size_t len) { |
218 | unsigned char *next = buf; |
219 | uint64_t crc = crc_in; |
220 | |
221 | crc = rev8(crc); |
222 | while (len && ((uintptr_t)next & 7) != 0) { |
223 | crc = big_table[0][((crc >> (56 - 8)) ^ *next++) & 0xff] ^ (crc >> 8); |
224 | len--; |
225 | } |
226 | |
227 | while (len >= 8) { |
228 | uint64_t n = *(uint64_t *)next; |
229 | crc = big_table[0][(n & 0xff) ^ ((crc >> (56 - 8)) & 0xff)] ^ |
230 | big_table[1][((n >> 8) & 0xff) ^ (crc & 0xff)] ^ |
231 | big_table[2][(n >> 16) & 0xff] ^ |
232 | big_table[3][(n >> 24) & 0xff] ^ |
233 | big_table[4][(n >> 32) & 0xff] ^ |
234 | big_table[5][(n >> 40) & 0xff] ^ |
235 | big_table[6][(n >> 48) & 0xff] ^ |
236 | big_table[7][n >> 56]; |
237 | next += 8; |
238 | len -= 8; |
239 | } |
240 | |
241 | while (len) { |
242 | crc = big_table[0][((crc >> (56 - 8)) ^ *next++) & 0xff] ^ (crc >> 8); |
243 | len--; |
244 | } |
245 | |
246 | return rev8(crc); |
247 | } |
248 | |
249 | /* Return the CRC of buf[0..len-1] with initial crc, processing eight bytes |
250 | at a time using passed-in lookup table. |
251 | This selects one of two routines depending on the endianness of |
252 | the architecture. */ |
253 | uint64_t crcspeed64native(uint64_t table[8][256], uint64_t crc, void *buf, |
254 | size_t len) { |
255 | uint64_t n = 1; |
256 | |
257 | return *(char *)&n ? crcspeed64little(table, crc, buf, len) |
258 | : crcspeed64big(table, crc, buf, len); |
259 | } |
260 | |
261 | uint16_t crcspeed16native(uint16_t table[8][256], uint16_t crc, void *buf, |
262 | size_t len) { |
263 | uint64_t n = 1; |
264 | |
265 | return *(char *)&n ? crcspeed16little(table, crc, buf, len) |
266 | : crcspeed16big(table, crc, buf, len); |
267 | } |
268 | |
269 | /* Initialize CRC lookup table in architecture-dependent manner. */ |
270 | void crcspeed64native_init(crcfn64 fn, uint64_t table[8][256]) { |
271 | uint64_t n = 1; |
272 | |
273 | *(char *)&n ? crcspeed64little_init(fn, table) |
274 | : crcspeed64big_init(fn, table); |
275 | } |
276 | |
277 | void crcspeed16native_init(crcfn16 fn, uint16_t table[8][256]) { |
278 | uint64_t n = 1; |
279 | |
280 | *(char *)&n ? crcspeed16little_init(fn, table) |
281 | : crcspeed16big_init(fn, table); |
282 | } |
283 | |