54 #define POLY 0x82f63b78
64 static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec) {
77 static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat) {
78 for (
unsigned n = 0; n < 32; n++)
79 square[n] = gf2_matrix_times(mat, mat[n]);
87 static void crc32c_zeros_op(uint32_t *even,
size_t len) {
93 for (
unsigned n = 1; n < 32; n++) {
99 gf2_matrix_square(even, odd);
102 gf2_matrix_square(odd, even);
108 gf2_matrix_square(even, odd);
112 gf2_matrix_square(odd, even);
117 for (
unsigned n = 0; n < 32; n++)
123 static void crc32c_zeros(uint32_t zeros[][256],
size_t len) {
126 crc32c_zeros_op(op, len);
127 for (
unsigned n = 0; n < 256; n++) {
128 zeros[0][n] = gf2_matrix_times(op, n);
129 zeros[1][n] = gf2_matrix_times(op, n << 8);
130 zeros[2][n] = gf2_matrix_times(op, n << 16);
131 zeros[3][n] = gf2_matrix_times(op, n << 24);
136 static inline uint32_t crc32c_shift(uint32_t zeros[][256], uint32_t crc) {
137 return zeros[0][crc & 0xff] ^ zeros[1][(crc >> 8) & 0xff] ^
138 zeros[2][(crc >> 16) & 0xff] ^ zeros[3][crc >> 24];
145 #define LONGx1 "8192"
146 #define LONGx2 "16384"
148 #define SHORTx1 "256"
149 #define SHORTx2 "512"
152 static pthread_once_t crc32c_once_hw = PTHREAD_ONCE_INIT;
153 static uint32_t crc32c_long[4][256];
154 static uint32_t crc32c_short[4][256];
157 static void crc32c_init_hw(
void) {
158 crc32c_zeros(crc32c_long, LONG);
159 crc32c_zeros(crc32c_short, SHORT);
163 static uint32_t crc32c_hw(uint32_t crc,
void const *buf,
size_t len) {
165 pthread_once(&crc32c_once_hw, crc32c_init_hw);
173 unsigned char const *next = (
unsigned char const *)buf;
174 while (len && ((uintptr_t)next & 7) != 0) {
175 __asm__(
"crc32b\t" "(%1), %0"
177 :
"r"(next),
"0"(crc0));
186 while (len >= LONG*3) {
189 unsigned char const *
const end = next + LONG;
191 __asm__(
"crc32q\t" "(%3), %0\n\t"
192 "crc32q\t" LONGx1
"(%3), %1\n\t"
193 "crc32q\t" LONGx2
"(%3), %2"
194 :
"=r"(crc0),
"=r"(crc1),
"=r"(crc2)
195 :
"r"(next),
"0"(crc0),
"1"(crc1),
"2"(crc2));
197 }
while (next < end);
198 crc0 = crc32c_shift(crc32c_long, crc0) ^ crc1;
199 crc0 = crc32c_shift(crc32c_long, crc0) ^ crc2;
206 while (len >= SHORT*3) {
209 unsigned char const *
const end = next + SHORT;
211 __asm__(
"crc32q\t" "(%3), %0\n\t"
212 "crc32q\t" SHORTx1
"(%3), %1\n\t"
213 "crc32q\t" SHORTx2
"(%3), %2"
214 :
"=r"(crc0),
"=r"(crc1),
"=r"(crc2)
215 :
"r"(next),
"0"(crc0),
"1"(crc1),
"2"(crc2));
217 }
while (next < end);
218 crc0 = crc32c_shift(crc32c_short, crc0) ^ crc1;
219 crc0 = crc32c_shift(crc32c_short, crc0) ^ crc2;
227 unsigned char const *
const end = next + (len - (len & 7));
229 __asm__(
"crc32q\t" "(%1), %0"
231 :
"r"(next),
"0"(crc0));
239 __asm__(
"crc32b\t" "(%1), %0"
241 :
"r"(next),
"0"(crc0));
255 #define SSE42(have) \
263 (have) = (ecx >> 20) & 1; \
268 uint32_t
crc32c(uint32_t crc,
void const *buf,
size_t len) {
272 return sse42 ? crc32c_hw(crc, buf, len) :
crc32c_sw(crc, buf, len);
277 uint32_t
crc32c(uint32_t crc,
void const *buf,
size_t len) {
287 for (
unsigned n = 0; n < 256; n++) {
289 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
290 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
291 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
292 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
293 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
294 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
295 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
296 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
299 for (
unsigned n = 0; n < 256; n++) {
301 for (
unsigned k = 1; k < 8; k++) {
311 unsigned char const *next = (
unsigned char const *)buf;
315 while (len && ((uintptr_t)next & 7) != 0) {
322 crcw ^= *(uint64_t
const *)next;
344 #if defined(__has_builtin) || (defined(__GNUC__) && \
345 (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)))
346 # define swap __builtin_bswap64
348 static inline uint64_t
swap(uint64_t x) {
349 x = ((x << 8) & 0xff00ff00ff00ff00) | ((x >> 8) & 0xff00ff00ff00ff);
350 x = ((x << 16) & 0xffff0000ffff0000) | ((x >> 16) & 0xffff0000ffff);
351 return (x << 32) | (x >> 32);
360 for (
unsigned n = 0; n < 256; n++) {
362 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
363 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
364 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
365 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
366 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
367 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
368 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
369 crc = crc & 1 ? (crc >> 1) ^
POLY : crc >> 1;
372 for (
unsigned n = 0; n < 256; n++) {
375 for (
unsigned k = 1; k < 8; k++) {
385 unsigned char const *next = (
unsigned char const *)buf;
389 while (len && ((uintptr_t)next & 7) != 0) {
394 uint64_t crcw =
swap(crc);
396 crcw ^= *(uint64_t
const *)next;
424 uint32_t
crc32c_sw(uint32_t crc,
void const *buf,
size_t len) {
425 static int const little = 1;
426 if (*(
char const *)&little)
438 int main(
int argc,
char **argv) {
441 fputs(
"only one argument permitted\n", stderr);
444 long rep = argc == 1 ? 1 : strtol(argv[1], NULL, 10);
446 fputs(
"usage: crc32c [[-]nnn] < data\n"
447 " where nnn is the number of times to repeat\n"
448 " negative forces the software implementation\n", stderr);
458 int ret = load(stdin, 0, &dat, &size, &len);
460 fputs(
"error reading from stdin\n", stderr);
471 printf(
"0x%08x\n", crc);
int main(int argc, char *argv[])
static pthread_once_t crc32c_once_little
uint32_t crc32c(uint32_t crc, void const *buf, size_t len)
static uint64_t swap(uint64_t x)
uint32_t crc32c_sw_big(uint32_t crc, void const *buf, size_t len)
uint32_t crc32c_sw(uint32_t crc, void const *buf, size_t len)
static uint64_t crc32c_table_big[8][256]
static void crc32c_init_sw_little(void)
static uint32_t crc32c_table_big_byte[256]
static void crc32c_init_sw_big(void)
uint32_t crc32c_sw_little(uint32_t crc, void const *buf, size_t len)
static uint32_t crc32c_table_little[8][256]
static pthread_once_t crc32c_once_big