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. */
33void 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
52void 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. */
71static 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. */
87void 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
97void 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 */
112uint64_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
146uint16_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 */
183uint64_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. */
216uint16_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. */
253uint64_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
261uint16_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. */
270void 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
277void 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