lustre/include/erasure_code.h

   1 // SPDX-License-Identifier: BSD-2-Clause
   2 /**********************************************************************
   3  * Copyright(c) 2011-2015 Intel Corporation All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  *  modification, are permitted provided that the following conditions
   7  *  are met:
   8  *    Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  *  Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in
  12  *    the documentation and/or other materials provided with the
  13  *    distribution.
  14  *  Neither the name of Intel Corporation nor the names of its
  15  *    contributors may be used to endorse or promote products derived
  16  *    from this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #ifndef _ERASURE_CODE_H_
  32 #define _ERASURE_CODE_H_
  33
  34 /**
  35  *  @file erasure_code.h
  36  *  @brief Interface to functions supporting erasure code encode and decode.
  37  *
  38  *  This file defines the interface to optimized functions used in erasure
  39  *  codes.  Encode and decode of erasures in GF(2^8) are made by calculating the
  40  *  dot product of the symbols (bytes in GF(2^8)) across a set of buffers and a
  41  *  set of coefficients.  Values for the coefficients are determined by the type
  42  *  of erasure code.  Using a general dot product means that any sequence of
  43  *  coefficients may be used including erasure codes based on random
  44  *  coefficients.
  45  *  Multiple versions of dot product are supplied to calculate 1-6 output
  46  *  vectors in one pass.
  47  *  Base GF multiply and divide functions can be sped up by defining
  48  *  GF_LARGE_TABLES at the expense of memory size.
  49  *
  50  */
  51
  52 #ifdef __cplusplus
  53 extern "C" {
  54 #endif
  55
  56 /**
  57  * @brief Initialize 32-byte constant array for GF(2^8) vector multiply
  58  *
  59  * Calculates array {C{00}, C{01}, C{02}, ... , C{0f} }, {C{00}, C{10},
  60  * C{20}, ... , C{f0} } as required by other fast vector multiply
  61  * functions.
  62  * @param c     Constant input.
  63  * @param gftbl Table output.
  64  */
  65 void gf_vect_mul_init(unsigned char c, unsigned char *gftbl);
  66
  67 /**
  68  * @brief Initialize tables for fast Erasure Code encode and decode.
  69  *
  70  * Generates the expanded tables needed for fast encode or decode for erasure
  71  * codes on blocks of data.  32bytes is generated for each input coefficient.
  72  *
  73  * @param k      The number of vector sources or rows in the generator matrix
  74  *               for coding.
  75  * @param rows   The number of output vectors to concurrently encode/decode.
  76  * @param a      Pointer to sets of arrays of input coefficients used to encode
  77  *               or decode data.
  78  * @param gftbls Pointer to start of space for concatenated output tables
  79  *               generated from input coefficients.  Must be of size 32*k*rows.
  80  * @returns none
  81  */
  82 void ec_init_tables(int k, int rows, unsigned char *a, unsigned char *gftbls);
  83
  84 /**
  85  * @brief Generate or decode erasure codes on blocks of data, runs appropriate
  86  * version.
  87  *
  88  * Given a list of source data blocks, generate one or multiple blocks of
  89  * encoded data as specified by a matrix of GF(2^8) coefficients. When given a
  90  * suitable set of coefficients, this function will perform the fast generation
  91  * or decoding of Reed-Solomon type erasure codes.
  92  *
  93  * This function determines what instruction sets are enabled and
  94  * selects the appropriate version at runtime.
  95  *
  96  * @param len    Length of each block of data (vector) of source or dest data.
  97  * @param k      The number of vector sources or rows in the generator matrix
  98  *               for coding.
  99  * @param rows   The number of output vectors to concurrently encode/decode.
 100  * @param gftbls Pointer to array of input tables generated from coding
 101  *                coefficients in ec_init_tables(). Must be of size 32*k*rows
 102  * @param data   Array of pointers to source input buffers.
 103  * @param coding Array of pointers to coded output buffers.
 104  * @returns none
 105  */
 106 void ec_encode_data(int len, int k, int rows, unsigned char *gftbls,
 107                     unsigned char **data, unsigned char **coding);
 108
 109 /**
 110  * @brief Generate a Cauchy matrix of coefficients to be used for encoding.
 111  *
 112  * Cauchy matrix example of encoding coefficients where high portion of matrix
 113  * is identity matrix I and lower portion is constructed as 1/(i + j) | i != j,
 114  * i:{0,k-1} j:{k,m-1}.  Any sub-matrix of a Cauchy matrix should be invertable.
 115  *
 116  * @param a  [m x k] array to hold coefficients
 117  * @param m  number of rows in matrix corresponding to srcs + parity.
 118  * @param k  number of columns in matrix corresponding to srcs.
 119  * @returns  none
 120  */
 121 void gf_gen_cauchy1_matrix(unsigned char *a, int m, int k);
 122
 123 /**
 124  * @brief Invert a matrix in GF(2^8)
 125  *
 126  * Attempts to construct an n x n inverse of the input matrix. Returns non-zero
 127  * if singular. Will always destroy input matrix in process.
 128  *
 129  * @param in  input matrix, destroyed by invert process
 130  * @param out output matrix such that [in] x [out] = [I] - identity matrix
 131  * @param n   size of matrix [nxn]
 132  * @returns 0 successful, other fail on singular input matrix
 133  */
 134 int gf_invert_matrix(unsigned char *in, unsigned char *out, const int n);
 135
 136 /*************************************************************/
 137
 138 #ifdef __cplusplus
 139 }
 140 #endif
 141
 142 #endif /* _ERASURE_CODE_H_ */