diff options
| author | maxim-yurchuk <maxim-yurchuk@yandex-team.com> | 2024-10-09 12:29:46 +0300 |
|---|---|---|
| committer | maxim-yurchuk <maxim-yurchuk@yandex-team.com> | 2024-10-09 13:14:22 +0300 |
| commit | 9731d8a4bb7ee2cc8554eaf133bb85498a4c7d80 (patch) | |
| tree | a8fb3181d5947c0d78cf402aa56e686130179049 /contrib/libs/isa-l/erasure_code/gen_rs_matrix_limits.c | |
| parent | a44b779cd359f06c3ebbef4ec98c6b38609d9d85 (diff) | |
| download | ydb-9731d8a4bb7ee2cc8554eaf133bb85498a4c7d80.tar.gz | |
publishFullContrib: true for ydb
<HIDDEN_URL>
commit_hash:c82a80ac4594723cebf2c7387dec9c60217f603e
Diffstat (limited to 'contrib/libs/isa-l/erasure_code/gen_rs_matrix_limits.c')
| -rw-r--r-- | contrib/libs/isa-l/erasure_code/gen_rs_matrix_limits.c | 115 |
1 files changed, 115 insertions, 0 deletions
diff --git a/contrib/libs/isa-l/erasure_code/gen_rs_matrix_limits.c b/contrib/libs/isa-l/erasure_code/gen_rs_matrix_limits.c new file mode 100644 index 0000000000..85061484bc --- /dev/null +++ b/contrib/libs/isa-l/erasure_code/gen_rs_matrix_limits.c @@ -0,0 +1,115 @@ +#include <string.h> +#include <stdint.h> +#include <stdio.h> +#include "erasure_code.h" + +#define MAX_CHECK 63 /* Size is limited by using uint64_t to represent subsets */ +#define M_MAX 0x20 +#define K_MAX 0x10 +#define ROWS M_MAX +#define COLS K_MAX + +static inline int min(int a, int b) +{ + if (a <= b) + return a; + else + return b; +} + +void gen_sub_matrix(unsigned char *out_matrix, int dim, unsigned char *in_matrix, int rows, + int cols, uint64_t row_indicator, uint64_t col_indicator) +{ + int i, j, r, s; + + for (i = 0, r = 0; i < rows; i++) { + if (!(row_indicator & ((uint64_t) 1 << i))) + continue; + + for (j = 0, s = 0; j < cols; j++) { + if (!(col_indicator & ((uint64_t) 1 << j))) + continue; + out_matrix[dim * r + s] = in_matrix[cols * i + j]; + s++; + } + r++; + } +} + +/* Gosper's Hack */ +uint64_t next_subset(uint64_t * subset, uint64_t element_count, uint64_t subsize) +{ + uint64_t tmp1 = *subset & -*subset; + uint64_t tmp2 = *subset + tmp1; + *subset = (((*subset ^ tmp2) >> 2) / tmp1) | tmp2; + if (*subset & (((uint64_t) 1 << element_count))) { + /* Overflow on last subset */ + *subset = ((uint64_t) 1 << subsize) - 1; + return 1; + } + + return 0; +} + +int are_submatrices_singular(unsigned char *vmatrix, int rows, int cols) +{ + unsigned char matrix[COLS * COLS]; + unsigned char invert_matrix[COLS * COLS]; + uint64_t row_indicator, col_indicator, subset_init, subsize; + + /* Check all square subsize x subsize submatrices of the rows x cols + * vmatrix for singularity*/ + for (subsize = 1; subsize <= min(rows, cols); subsize++) { + subset_init = (1 << subsize) - 1; + col_indicator = subset_init; + do { + row_indicator = subset_init; + do { + gen_sub_matrix(matrix, subsize, vmatrix, rows, + cols, row_indicator, col_indicator); + if (gf_invert_matrix(matrix, invert_matrix, subsize)) + return 1; + + } while (next_subset(&row_indicator, rows, subsize) == 0); + } while (next_subset(&col_indicator, cols, subsize) == 0); + } + + return 0; +} + +int main(int argc, char **argv) +{ + unsigned char vmatrix[(ROWS + COLS) * COLS]; + int rows, cols; + + if (K_MAX > MAX_CHECK) { + printf("K_MAX too large for this test\n"); + return 0; + } + if (M_MAX > MAX_CHECK) { + printf("M_MAX too large for this test\n"); + return 0; + } + if (M_MAX < K_MAX) { + printf("M_MAX must be smaller than K_MAX"); + return 0; + } + + printf("Checking gen_rs_matrix for k <= %d and m <= %d.\n", K_MAX, M_MAX); + printf("gen_rs_matrix creates erasure codes for:\n"); + + for (cols = 1; cols <= K_MAX; cols++) { + for (rows = 1; rows <= M_MAX - cols; rows++) { + gf_gen_rs_matrix(vmatrix, rows + cols, cols); + + /* Verify the Vandermonde portion of vmatrix contains no + * singular submatrix */ + if (are_submatrices_singular(&vmatrix[cols * cols], rows, cols)) + break; + + } + printf(" k = %2d, m <= %2d \n", cols, rows + cols - 1); + + } + return 0; +} |