003 File Manager
Current Path:
/usr/src/sys/libkern/x86
usr
/
src
/
sys
/
libkern
/
x86
/
📁
..
📄
crc32_sse42.c
(10.41 KB)
Editing: crc32_sse42.c
/* * Derived from crc32c.c version 1.1 by Mark Adler. * * Copyright (C) 2013 Mark Adler * * This software is provided 'as-is', without any express or implied warranty. * In no event will the author be held liable for any damages arising from the * use of this software. * * Permission is granted to anyone to use this software for any purpose, * including commercial applications, and to alter it and redistribute it * freely, subject to the following restrictions: * * 1. The origin of this software must not be misrepresented; you must not * claim that you wrote the original software. If you use this software * in a product, an acknowledgment in the product documentation would be * appreciated but is not required. * 2. Altered source versions must be plainly marked as such, and must not be * misrepresented as being the original software. * 3. This notice may not be removed or altered from any source distribution. * * Mark Adler * madler@alumni.caltech.edu */ #include <sys/cdefs.h> __FBSDID("$FreeBSD$"); /* * This file is compiled in userspace in order to run ATF unit tests. */ #ifndef _KERNEL #include <stdint.h> #include <stdlib.h> #else #include <sys/param.h> #include <sys/kernel.h> #endif #include <sys/gsb_crc32.h> static __inline uint32_t _mm_crc32_u8(uint32_t x, uint8_t y) { /* * clang (at least 3.9.[0-1]) pessimizes "rm" (y) and "m" (y) * significantly and "r" (y) a lot by copying y to a different * local variable (on the stack or in a register), so only use * the latter. This costs a register and an instruction but * not a uop. */ __asm("crc32b %1,%0" : "+r" (x) : "r" (y)); return (x); } #ifdef __amd64__ static __inline uint64_t _mm_crc32_u64(uint64_t x, uint64_t y) { __asm("crc32q %1,%0" : "+r" (x) : "r" (y)); return (x); } #else static __inline uint32_t _mm_crc32_u32(uint32_t x, uint32_t y) { __asm("crc32l %1,%0" : "+r" (x) : "r" (y)); return (x); } #endif /* CRC-32C (iSCSI) polynomial in reversed bit order. */ #define POLY 0x82f63b78 /* * Block sizes for three-way parallel crc computation. LONG and SHORT must * both be powers of two. */ #define LONG 128 #define SHORT 64 /* * Tables for updating a crc for LONG, 2 * LONG, SHORT and 2 * SHORT bytes * of value 0 later in the input stream, in the same way that the hardware * would, but in software without calculating intermediate steps. */ static uint32_t crc32c_long[4][256]; static uint32_t crc32c_2long[4][256]; static uint32_t crc32c_short[4][256]; static uint32_t crc32c_2short[4][256]; /* * Multiply a matrix times a vector over the Galois field of two elements, * GF(2). Each element is a bit in an unsigned integer. mat must have at * least as many entries as the power of two for most significant one bit in * vec. */ static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec) { uint32_t sum; sum = 0; while (vec) { if (vec & 1) sum ^= *mat; vec >>= 1; mat++; } return (sum); } /* * Multiply a matrix by itself over GF(2). Both mat and square must have 32 * rows. */ static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat) { int n; for (n = 0; n < 32; n++) square[n] = gf2_matrix_times(mat, mat[n]); } /* * Construct an operator to apply len zeros to a crc. len must be a power of * two. If len is not a power of two, then the result is the same as for the * largest power of two less than len. The result for len == 0 is the same as * for len == 1. A version of this routine could be easily written for any * len, but that is not needed for this application. */ static void crc32c_zeros_op(uint32_t *even, size_t len) { uint32_t odd[32]; /* odd-power-of-two zeros operator */ uint32_t row; int n; /* put operator for one zero bit in odd */ odd[0] = POLY; /* CRC-32C polynomial */ row = 1; for (n = 1; n < 32; n++) { odd[n] = row; row <<= 1; } /* put operator for two zero bits in even */ gf2_matrix_square(even, odd); /* put operator for four zero bits in odd */ gf2_matrix_square(odd, even); /* * first square will put the operator for one zero byte (eight zero * bits), in even -- next square puts operator for two zero bytes in * odd, and so on, until len has been rotated down to zero */ do { gf2_matrix_square(even, odd); len >>= 1; if (len == 0) return; gf2_matrix_square(odd, even); len >>= 1; } while (len); /* answer ended up in odd -- copy to even */ for (n = 0; n < 32; n++) even[n] = odd[n]; } /* * Take a length and build four lookup tables for applying the zeros operator * for that length, byte-by-byte on the operand. */ static void crc32c_zeros(uint32_t zeros[][256], size_t len) { uint32_t op[32]; uint32_t n; crc32c_zeros_op(op, len); for (n = 0; n < 256; n++) { zeros[0][n] = gf2_matrix_times(op, n); zeros[1][n] = gf2_matrix_times(op, n << 8); zeros[2][n] = gf2_matrix_times(op, n << 16); zeros[3][n] = gf2_matrix_times(op, n << 24); } } /* Apply the zeros operator table to crc. */ static inline uint32_t crc32c_shift(uint32_t zeros[][256], uint32_t crc) { return (zeros[0][crc & 0xff] ^ zeros[1][(crc >> 8) & 0xff] ^ zeros[2][(crc >> 16) & 0xff] ^ zeros[3][crc >> 24]); } /* Initialize tables for shifting crcs. */ static void #ifndef _KERNEL __attribute__((__constructor__)) #endif crc32c_init_hw(void) { crc32c_zeros(crc32c_long, LONG); crc32c_zeros(crc32c_2long, 2 * LONG); crc32c_zeros(crc32c_short, SHORT); crc32c_zeros(crc32c_2short, 2 * SHORT); } #ifdef _KERNEL SYSINIT(crc32c_sse42, SI_SUB_LOCK, SI_ORDER_ANY, crc32c_init_hw, NULL); #endif /* Compute CRC-32C using the Intel hardware instruction. */ uint32_t sse42_crc32c(uint32_t crc, const unsigned char *buf, unsigned len) { #ifdef __amd64__ const size_t align = 8; #else const size_t align = 4; #endif const unsigned char *next, *end; #ifdef __amd64__ uint64_t crc0, crc1, crc2; #else uint32_t crc0, crc1, crc2; #endif next = buf; crc0 = crc; /* Compute the crc to bring the data pointer to an aligned boundary. */ while (len && ((uintptr_t)next & (align - 1)) != 0) { crc0 = _mm_crc32_u8(crc0, *next); next++; len--; } #if LONG > SHORT /* * Compute the crc on sets of LONG*3 bytes, executing three independent * crc instructions, each on LONG bytes -- this is optimized for the * Nehalem, Westmere, Sandy Bridge, and Ivy Bridge architectures, which * have a throughput of one crc per cycle, but a latency of three * cycles. */ crc = 0; while (len >= LONG * 3) { crc1 = 0; crc2 = 0; end = next + LONG; do { #ifdef __amd64__ crc0 = _mm_crc32_u64(crc0, *(const uint64_t *)next); crc1 = _mm_crc32_u64(crc1, *(const uint64_t *)(next + LONG)); crc2 = _mm_crc32_u64(crc2, *(const uint64_t *)(next + (LONG * 2))); #else crc0 = _mm_crc32_u32(crc0, *(const uint32_t *)next); crc1 = _mm_crc32_u32(crc1, *(const uint32_t *)(next + LONG)); crc2 = _mm_crc32_u32(crc2, *(const uint32_t *)(next + (LONG * 2))); #endif next += align; } while (next < end); /*- * Update the crc. Try to do it in parallel with the inner * loop. 'crc' is used to accumulate crc0 and crc1 * produced by the inner loop so that the next iteration * of the loop doesn't depend on anything except crc2. * * The full expression for the update is: * crc = S*S*S*crc + S*S*crc0 + S*crc1 * where the terms are polynomials modulo the CRC polynomial. * We regroup this subtly as: * crc = S*S * (S*crc + crc0) + S*crc1. * This has an extra dependency which reduces possible * parallelism for the expression, but it turns out to be * best to intentionally delay evaluation of this expression * so that it competes less with the inner loop. * * We also intentionally reduce parallelism by feedng back * crc2 to the inner loop as crc0 instead of accumulating * it in crc. This synchronizes the loop with crc update. * CPU and/or compiler schedulers produced bad order without * this. * * Shifts take about 12 cycles each, so 3 here with 2 * parallelizable take about 24 cycles and the crc update * takes slightly longer. 8 dependent crc32 instructions * can run in 24 cycles, so the 3-way blocking is worse * than useless for sizes less than 8 * <word size> = 64 * on amd64. In practice, SHORT = 32 confirms these * timing calculations by giving a small improvement * starting at size 96. Then the inner loop takes about * 12 cycles and the crc update about 24, but these are * partly in parallel so the total time is less than the * 36 cycles that 12 dependent crc32 instructions would * take. * * To have a chance of completely hiding the overhead for * the crc update, the inner loop must take considerably * longer than 24 cycles. LONG = 64 makes the inner loop * take about 24 cycles, so is not quite large enough. * LONG = 128 works OK. Unhideable overheads are about * 12 cycles per inner loop. All assuming timing like * Haswell. */ crc = crc32c_shift(crc32c_long, crc) ^ crc0; crc1 = crc32c_shift(crc32c_long, crc1); crc = crc32c_shift(crc32c_2long, crc) ^ crc1; crc0 = crc2; next += LONG * 2; len -= LONG * 3; } crc0 ^= crc; #endif /* LONG > SHORT */ /* * Do the same thing, but now on SHORT*3 blocks for the remaining data * less than a LONG*3 block */ crc = 0; while (len >= SHORT * 3) { crc1 = 0; crc2 = 0; end = next + SHORT; do { #ifdef __amd64__ crc0 = _mm_crc32_u64(crc0, *(const uint64_t *)next); crc1 = _mm_crc32_u64(crc1, *(const uint64_t *)(next + SHORT)); crc2 = _mm_crc32_u64(crc2, *(const uint64_t *)(next + (SHORT * 2))); #else crc0 = _mm_crc32_u32(crc0, *(const uint32_t *)next); crc1 = _mm_crc32_u32(crc1, *(const uint32_t *)(next + SHORT)); crc2 = _mm_crc32_u32(crc2, *(const uint32_t *)(next + (SHORT * 2))); #endif next += align; } while (next < end); crc = crc32c_shift(crc32c_short, crc) ^ crc0; crc1 = crc32c_shift(crc32c_short, crc1); crc = crc32c_shift(crc32c_2short, crc) ^ crc1; crc0 = crc2; next += SHORT * 2; len -= SHORT * 3; } crc0 ^= crc; /* Compute the crc on the remaining bytes at native word size. */ end = next + (len - (len & (align - 1))); while (next < end) { #ifdef __amd64__ crc0 = _mm_crc32_u64(crc0, *(const uint64_t *)next); #else crc0 = _mm_crc32_u32(crc0, *(const uint32_t *)next); #endif next += align; } len &= (align - 1); /* Compute the crc for any trailing bytes. */ while (len) { crc0 = _mm_crc32_u8(crc0, *next); next++; len--; } return ((uint32_t)crc0); }
Upload File
Create Folder