-
Notifications
You must be signed in to change notification settings - Fork 21
/
crc16speed.c
213 lines (193 loc) · 7.89 KB
/
crc16speed.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
/* Copyright (c) 2014, Matt Stancliff <matt@genges.com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Redis nor the names of its contributors may be used
* to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE. */
#include "crc16speed.h"
/* If CRCSPEED16_DUAL is defined, we allow calls to
* both _little and _big CRC.
* By default, we only allow one endianness to be used
* and the first call to either _init function will set the
* lookup table endianness for the life of this module.
* We don't enable dual lookups by default because
* each 8x256 lookup table is 4k. */
#ifndef CRC16SPEED_DUAL
static uint16_t crc16_table[8][256] = {{0}};
static void *crc16_table_little = NULL, *crc16_table_big = NULL;
static const bool dual = false;
#else
static uint16_t crc16_table_little[8][256] = {{0}};
static uint16_t crc16_table_big[8][256] = {{0}};
static void *crc16_table = NULL;
static const bool dual = true;
#endif
/* value of crc16_table[0][1], architecture dependent. */
#define LITTLE1 UINT16_C(0x1021)
#define BIG1 UINT16_C(0x2110)
/* Define CRC16SPEED_SAFE if you want runtime checks to stop
* CRCs from being calculated by uninitialized tables (and also stop tables
* from being initialized more than once). */
#ifdef CRC16SPEED_SAFE
#define should_init(table, val) \
do { \
if ((table)[0][1] == (val)) \
return false; \
} while (0)
#define check_init(table, val) \
do { \
if ((table)[0][1] != (val)) \
return false; \
} while (0)
#else
#define should_init(a, b)
#define check_init(a, b)
#endif
/* This is CRC-16-CCITT (non-reflected poly, non-inverted input/output).
* crc16() is only used to bootstrap an initial 256-entry lookup table. */
#define POLY 0x1021
uint16_t crc16(uint16_t crc, const void *in_data, uint64_t len) {
const uint8_t *data = in_data;
for (uint64_t i = 0; i < len; i++) {
crc = crc ^ (data[i] << 8);
for (int j = 0; j < 8; j++) {
if (crc & 0x8000) {
crc = (crc << 1) ^ POLY;
} else {
crc = (crc << 1);
}
}
}
return crc;
}
/* Only for testing; doesn't support DUAL */
uint16_t crc16_lookup(uint16_t crc, const void *in_data, uint64_t len) {
const uint8_t *data = in_data;
for (uint64_t i = 0; i < len; i++) {
crc = (crc << 8) ^ crc16_table[0][((crc >> 8) ^ data[i]) & 0x00ff];
}
return crc;
}
/* Returns false if CRC16SPEED_SAFE and table already initialized. */
bool crc16speed_init(void) {
#ifndef CRC16SPEED_DUAL
should_init(crc16_table, LITTLE1);
#else
should_init(crc16_table_little, LITTLE1);
#endif
crcspeed16little_init(crc16, dual ? crc16_table_little : crc16_table);
return true;
}
/* Returns false if CRC16SPEED_SAFE and table already initialized. */
bool crc16speed_init_big(void) {
#ifndef CRC16SPEED_DUAL
should_init(crc16_table, BIG1);
#else
should_init(crc16_table_big, BIG1);
#endif
crcspeed16big_init(crc16, dual ? crc16_table_big : crc16_table);
return true;
}
uint16_t crc16speed(uint16_t crc, const void *s, const uint64_t l) {
/* Quickly check if CRC table is initialized to little endian correctly. */
#ifndef CRC16SPEED_DUAL
check_init(crc16_table, LITTLE1);
#else
check_init(crc16_table_little, LITTLE1);
#endif
return crcspeed16little(dual ? crc16_table_little : crc16_table, crc,
(void *)s, l);
}
uint16_t crc16speed_big(uint16_t crc, const void *s, const uint64_t l) {
/* Quickly check if CRC table is initialized to big endian correctly. */
#ifndef CRC16SPEED_DUAL
check_init(crc16_table, BIG1);
#else
check_init(crc16_table_big, BIG1);
#endif
return crcspeed16big(dual ? crc16_table_big : crc16_table, crc, (void *)s,
l);
}
bool crc16speed_init_native(void) {
const uint64_t n = 1;
return *(char *)&n ? crc16speed_init() : crc16speed_init_big();
}
/* If you are on a platform where endianness can change at runtime, this
* will break unless you compile with CRC16SPEED_DUAL and manually run
* _init() and _init_big() instead of using _init_native() */
uint16_t crc16speed_native(uint16_t crc, const void *s, const uint64_t l) {
const uint64_t n = 1;
return *(char *)&n ? crc16speed(crc, s, l) : crc16speed_big(crc, s, l);
}
/* Iterate over table to fully load it into a cache near the CPU. */
void crc16speed_cache_table(void) {
uint16_t m;
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 256; ++j) {
#ifndef CRC16SPEED_DUAL
m = crc16_table[i][j];
#else
m = crc16_table_little[i][j];
m += crc16_table_big[i][j];
#endif
++m;
}
}
}
/* Test main */
#if defined(CRCSPEED_TEST) || defined(CRCSPEED_TEST_MAIN)
#include <stdio.h>
#include <stdlib.h>
#define UNUSED(x) (void)(x)
int crc16Test(int argc, char *argv[]) {
UNUSED(argc);
UNUSED(argv);
crc16speed_init();
printf("[calcula]: 31c3 == %04" PRIx64 "\n",
(uint64_t)crc16(0, "123456789", 9));
printf("[lookupt]: 31c3 == %04" PRIx64 "\n",
(uint64_t)crc16_lookup(0, "123456789", 9));
printf("[16speed]: 31c3 == %04" PRIx64 "\n",
(uint64_t)crc16speed(0, "123456789", 9));
char li[] = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
"do eiusmod tempor incididunt ut labore et dolore magna "
"aliqua. Ut enim ad minim veniam, quis nostrud exercitation "
"ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis "
"aute irure dolor in reprehenderit in voluptate velit esse "
"cillum dolore eu fugiat nulla pariatur. Excepteur sint "
"occaecat cupidatat non proident, sunt in culpa qui officia "
"deserunt mollit anim id est laborum.";
printf("[calcula]: 4b20 == %04" PRIx64 "\n",
(uint64_t)crc16(0, li, sizeof(li)));
printf("[lookupt]: 4b20 == %04" PRIx64 "\n",
(uint64_t)crc16_lookup(0, li, sizeof(li)));
printf("[16speed]: 4b20 == %04" PRIx64 "\n",
(uint64_t)crc16speed(0, li, sizeof(li)));
return 0;
}
#endif
#ifdef CRCSPEED_TEST_MAIN
int main(int argc, char *argv[]) {
return crc16Test(argc, argv);
}
#endif