MySQL 9.1.0
Source Code Documentation
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.