MySQL 9.2.0
Source Code Documentation
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages Concepts
crc32.cc File Reference

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]bufdata over which to calculate CRC32
[in]lendata 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.