]>
git.proxmox.com Git - ceph.git/blob - ceph/src/isa-l/erasure_code/gen_rs_matrix_limits.c
4 #include "erasure_code.h"
6 #define MAX_CHECK 63 /* Size is limited by using uint64_t to represent subsets */
12 static inline int min(int a
, int b
)
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
)
25 for (i
= 0, r
= 0; i
< rows
; i
++) {
26 if (!(row_indicator
& ((uint64_t) 1 << i
)))
29 for (j
= 0, s
= 0; j
< cols
; j
++) {
30 if (!(col_indicator
& ((uint64_t) 1 << j
)))
32 out_matrix
[dim
* r
+ s
] = in_matrix
[cols
* i
+ j
];
40 uint64_t next_subset(uint64_t * subset
, uint64_t element_count
, uint64_t subsize
)
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;
54 int are_submatrices_singular(unsigned char *vmatrix
, int rows
, int cols
)
56 unsigned char matrix
[COLS
* COLS
];
57 unsigned char invert_matrix
[COLS
* COLS
];
58 uint64_t row_indicator
, col_indicator
, subset_init
, subsize
;
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
;
66 row_indicator
= subset_init
;
68 gen_sub_matrix(matrix
, subsize
, vmatrix
, rows
,
69 cols
, row_indicator
, col_indicator
);
70 if (gf_invert_matrix(matrix
, invert_matrix
, subsize
))
73 } while (next_subset(&row_indicator
, rows
, subsize
) == 0);
74 } while (next_subset(&col_indicator
, cols
, subsize
) == 0);
80 int main(int argc
, char **argv
)
82 unsigned char vmatrix
[(ROWS
+ COLS
) * COLS
];
85 if (K_MAX
> MAX_CHECK
) {
86 printf("K_MAX too large for this test\n");
89 if (M_MAX
> MAX_CHECK
) {
90 printf("M_MAX too large for this test\n");
94 printf("M_MAX must be smaller than K_MAX");
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");
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
);
105 /* Verify the Vandermonde portion of vmatrix contains no
106 * singular submatrix */
107 if (are_submatrices_singular(&vmatrix
[cols
* cols
], rows
, cols
))
111 printf(" k = %2d, m <= %2d \n", cols
, rows
+ cols
- 1);