ceph/src/spdk/isa-l/erasure_code/gen_rs_matrix_limits.c

   1 #include <string.h>
   2 #include <stdint.h>
   3 #include <stdio.h>
   4 #include "erasure_code.h"
   5
   6 #define MAX_CHECK 63            /* Size is limited by using uint64_t to represent subsets */
   7 #define M_MAX 0x20
   8 #define K_MAX 0x10
   9 #define ROWS M_MAX
  10 #define COLS K_MAX
  11
  12 static inline int min(int a, int b)
  13 {
  14         if (a <= b)
  15                 return a;
  16         else
  17                 return b;
  18 }
  19
  20 void gen_sub_matrix(unsigned char *out_matrix, int dim, unsigned char *in_matrix, int rows,
  21                     int cols, uint64_t row_indicator, uint64_t col_indicator)
  22 {
  23         int i, j, r, s;
  24
  25         for (i = 0, r = 0; i < rows; i++) {
  26                 if (!(row_indicator & ((uint64_t) 1 << i)))
  27                         continue;
  28
  29                 for (j = 0, s = 0; j < cols; j++) {
  30                         if (!(col_indicator & ((uint64_t) 1 << j)))
  31                                 continue;
  32                         out_matrix[dim * r + s] = in_matrix[cols * i + j];
  33                         s++;
  34                 }
  35                 r++;
  36         }
  37 }
  38
  39 /* Gosper's Hack */
  40 uint64_t next_subset(uint64_t * subset, uint64_t element_count, uint64_t subsize)
  41 {
  42         uint64_t tmp1 = *subset & -*subset;
  43         uint64_t tmp2 = *subset + tmp1;
  44         *subset = (((*subset ^ tmp2) >> 2) / tmp1) | tmp2;
  45         if (*subset & (((uint64_t) 1 << element_count))) {
  46                 /* Overflow on last subset */
  47                 *subset = ((uint64_t) 1 << subsize) - 1;
  48                 return 1;
  49         }
  50
  51         return 0;
  52 }
  53
  54 int are_submatrices_singular(unsigned char *vmatrix, int rows, int cols)
  55 {
  56         unsigned char matrix[COLS * COLS];
  57         unsigned char invert_matrix[COLS * COLS];
  58         uint64_t row_indicator, col_indicator, subset_init, subsize;
  59
  60         /* Check all square subsize x subsize submatrices of the rows x cols
  61          * vmatrix for singularity*/
  62         for (subsize = 1; subsize <= min(rows, cols); subsize++) {
  63                 subset_init = (1 << subsize) - 1;
  64                 col_indicator = subset_init;
  65                 do {
  66                         row_indicator = subset_init;
  67                         do {
  68                                 gen_sub_matrix(matrix, subsize, vmatrix, rows,
  69                                                cols, row_indicator, col_indicator);
  70                                 if (gf_invert_matrix(matrix, invert_matrix, subsize))
  71                                         return 1;
  72
  73                         } while (next_subset(&row_indicator, rows, subsize) == 0);
  74                 } while (next_subset(&col_indicator, cols, subsize) == 0);
  75         }
  76
  77         return 0;
  78 }
  79
  80 int main(int argc, char **argv)
  81 {
  82         unsigned char vmatrix[(ROWS + COLS) * COLS];
  83         int rows, cols;
  84
  85         if (K_MAX > MAX_CHECK) {
  86                 printf("K_MAX too large for this test\n");
  87                 return 0;
  88         }
  89         if (M_MAX > MAX_CHECK) {
  90                 printf("M_MAX too large for this test\n");
  91                 return 0;
  92         }
  93         if (M_MAX < K_MAX) {
  94                 printf("M_MAX must be smaller than K_MAX");
  95                 return 0;
  96         }
  97
  98         printf("Checking gen_rs_matrix for k <= %d and m <= %d.\n", K_MAX, M_MAX);
  99         printf("gen_rs_matrix creates erasure codes for:\n");
 100
 101         for (cols = 1; cols <= K_MAX; cols++) {
 102                 for (rows = 1; rows <= M_MAX - cols; rows++) {
 103                         gf_gen_rs_matrix(vmatrix, rows + cols, cols);
 104
 105                         /* Verify the Vandermonde portion of vmatrix contains no
 106                          * singular submatrix */
 107                         if (are_submatrices_singular(&vmatrix[cols * cols], rows, cols))
 108                                 break;
 109
 110                 }
 111                 printf("   k = %2d, m <= %2d \n", cols, rows + cols - 1);
 112
 113         }
 114         return 0;
 115 }