CRC32 implementation from Facebook, based on the zlib implementation. More...

#include <string.h>
#include "my_compiler.h"
#include "my_config.h"
#include "my_inttypes.h"
#include "univ.i"
#include "ut0crc32.h"

Classes
struct	hardware::Loop< iterations >
	A helper template to statically unroll a loop with a fixed number of iterations, where the iteration number itself is constexpr. More...

struct	hardware::Loop< 0 >

struct	hardware::crc32_impl
	The collection of functions implementing hardware accelerated updating of CRC32-C hash by processing a few (1,2,4 or 8) bytes of input. More...

struct	hardware::use_pclmul
	Implementation of polynomial_mul_rev<w>(rev_u) function which uses hardware accelerated polynomial multiplication to compute rev(w*u), where rev_u=rev(u). More...

struct	hardware::use_unrolled_loop_poly_mul
	Implementation of polynomial_mul_rev<w>(rev_u) function which uses a simple loop over i: if(w>>i&1)result^=rev_u<<(32-i), which is equivalent to w * flip_at_32(rev_u), which in turn is equivalent to rev(rev(w) * rev_u),. More...

struct	hardware::use_unrolled_loop_poly_mul::Polynomial_mul_rev_step_executor< x_to_len_8 >

struct	hardware::Update_step_executor< algo_to_use, slice_len >
	The body of unrolled loop used to process slices in parallel, which in i-th iteration processes 8 bytes from the i-th slice of data, where each slice has slice_len bytes. More...

struct	hardware::Combination_step_executor< algo_to_use, slice_len, slices_count >
	The body of unrolled loop used to combine partial results from each slice into the final hash of whole chunk, which in i-th iteration takes the crc of i-th slice and "rolls it forward" by virtually processing as many zeros as there are from the end of the i-th slice to the end of the chunk. More...

Namespaces
namespace	software

namespace	hardware

Functions
uint64_t	software::swap_byteorder (uint64_t i)
	Swap the byte order of an 8 byte integer. More...

static void	software::crc32_slice8_table_init ()
	Initializes the table that is used to generate the CRC32 if the CPU does not have support for it. More...

void	software::crc32_8 (uint32_t crc, const byte data, size_t len)
	Calculate CRC32 over 8-bit data using a software implementation. More...

uint32_t	software::crc32_64_low (uint32_t crc, uint64_t data)
	Calculate CRC32 over a 64-bit integer using a software implementation. More...

static void	software::crc32_64 (uint32_t crc, const byte data, size_t len)
	Calculate CRC32 over 64-bit byte string using a software implementation. More...

static void	software::crc32_64_legacy_big_endian (uint32_t crc, const byte data, size_t len)
	Calculate CRC32 over 64-bit byte string using a software implementation. More...

template<void crc32_64>
uint32_t	software::crc32_processing_64bit_chunks (const byte *buf, size_t len)
	Calculates CRC32 in software, without using CPU instructions. More...

uint32_t	software::crc32 (const byte *buf, size_t len)
	Computes CRC32-C hash not using any hardware acceleration. More...

uint32_t	ut_crc32_legacy_big_endian (const byte *buf, size_t len)
	Calculates CRC32 using legacy algorithm, which uses big-endian byte ordering when converting byte sequence to integers - flips each full aligned 8-byte chunk within the buf, but not the initial and trailing unaligned fragments. More...

bool	hardware::can_use_crc32 ()
	Checks if hardware accelerated crc32 instructions are available to this process right now. More...

bool	hardware::can_use_poly_mul ()
	Checks if hardware accelerated polynomial multiplication instructions are available to this process right now. More...

constexpr uint32_t	hardware::compute_x_to_8len (size_t len)
	Computes x^(len*8) modulo CRC32-C polynomial, which is useful, when you need to conceptually append len bytes of zeros to already computed hash. More...

constexpr uint64_t	hardware::flip_at_32 (uint32_t w)
	Produces a 64-bit result by moving i-th bit of 32-bit input to the 32-i-th position (zeroing the other bits). More...

template<size_t len, typename algo_to_use >
static uint64_t	hardware::roll (uint32_t crc)
	Rolls the crc forward by len bytes, that is updates it as if 8*len zero bits were processed. More...

template<typename algo_to_use >
static uint32_t	hardware::fold_64_to_32 (uint64_t big)
	Takes a 64-bit reversed representation of a polynomial, and computes the 32-bit reversed representation of it modulo CRC32-C. More...

template<size_t slice_len, size_t slices_count, typename algo_to_use >
static uint32_t	hardware::consume_chunk (uint32_t crc0, const unsigned char *data)
	Updates the crc checksum by processing slices_count*slice_len bytes of data. More...

template<size_t slice_len, size_t slices_count, typename algo_to_use >
static void	hardware::consume_chunks (uint32_t &crc, const byte *&data, size_t &len)
	Updates the crc checksum by processing at most len bytes of data. More...

template<typename Chunk , typename algo_to_use >
static void	hardware::consume_pow2 (uint32_t &crc, const byte *&data, size_t len)
	Updates the crc checksum by processing Chunk (1,2 or 4 bytes) of data, but only when the len of the data provided, when decomposed into powers of two, has a Chunk of this length. More...

template<typename algo_to_use >
static uint32_t	hardware::crc32 (uint32_t crc, const byte *data, size_t len)
	The hardware accelerated implementation of CRC32-C exploiting within-core parallelism on reordering processors, by consuming the data in large chunks split into 3 independent slices each. More...

uint32_t	hardware::crc32_using_pclmul (const byte *data, size_t len)
	The specialization of crc32<> template for use_pclmul and 0 as initial value of the hash. More...

uint32_t	hardware::crc32_using_unrolled_loop_poly_mul (const byte *data, size_t len)
	The specialization of crc32<> template for use_unrolled_loop_poly_mul and 0 as initial value of the hash. More...

void	ut_crc32_init ()
	Initializes the data structures used by ut_crc32*(). More...

Variables
ut_crc32_func_t	ut_crc32
	NOTE: The functions in this file should only use functions from other files in library. More...

bool	ut_crc32_cpu_enabled = false
	Flag that tells whether the CPU supports CRC32 or not. More...

bool	ut_poly_mul_cpu_enabled = false
	Flag that tells whether the CPU supports polynomial multiplication or not. More...

static uint32_t	software::crc32_slice8_table [8][256]

static bool	software::crc32_slice8_table_initialized = false

Detailed Description

CRC32 implementation from Facebook, based on the zlib implementation.

Created Aug 8, 2011, Vasil Dimov, based on mysys/my_crc32.c and mysys/my_perf.c, contributed by Facebook under the following license.

Function Documentation

◆ ut_crc32_init()

void ut_crc32_init ( )

Initializes the data structures used by ut_crc32*().

Does not do any allocations, would not hurt if called twice, but would be pointless.

◆ ut_crc32_legacy_big_endian()

uint32_t ut_crc32_legacy_big_endian	(	const byte *	buf,
		size_t	len
	)

Calculates CRC32 using legacy algorithm, which uses big-endian byte ordering when converting byte sequence to integers - flips each full aligned 8-byte chunk within the buf, but not the initial and trailing unaligned fragments.

ut_crc32_init() needs to be called at least once before calling this function.

Parameters

[in]	buf	data over which to calculate CRC32
[in]	len	data length

Returns: calculated hash

Variable Documentation

◆ ut_crc32

ut_crc32_func_t ut_crc32

NOTE: The functions in this file should only use functions from other files in library.

Pointer to standard-compliant CRC32-C (using the GF(2) primitive polynomial 0x11EDC6F41) calculation function picked by ut_crc32_init() as the fastest implementation for the current environment.

The code in this file is used to make a library for external tools. Pointer to CRC32 calculation function.

◆ ut_crc32_cpu_enabled

bool ut_crc32_cpu_enabled = false

Flag that tells whether the CPU supports CRC32 or not.

◆ ut_poly_mul_cpu_enabled

bool ut_poly_mul_cpu_enabled = false

Flag that tells whether the CPU supports polynomial multiplication or not.

Classes

Namespaces

Functions

Variables