liberasurecode 1.6.3
Erasure Code API library
Loading...
Searching...
No Matches
liberasurecode_rs_vand.c
Go to the documentation of this file.
1/*
2 * Copyright 2015 Kevin M Greenan
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * Redistributions of source code must retain the above copyright notice, this
8 * list of conditions and the following disclaimer.
9 *
10 * Redistributions in binary form must reproduce the above copyright notice, this
11 * list of conditions and the following disclaimer in the documentation and/or
12 * other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY
13 * THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
14 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
16 * EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
17 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
18 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
19 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
20 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
21 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
22 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23 *
24 * vi: set noai tw=79 ts=4 sw=4:
25 */
26
27// DISCLAIMER: This is a totally basic implementation of RS used if a user does not
28// want to install one of the supported backends, such as Jerasure and ISA-L.
29// This is not expected to perform as well as the other supported backends,
30// but does not make any assumptions about the host system. Using a library
31// like Jerasure with GF-Complete will give users the ability to tune to their
32// architecture (Intel or ARM), CPU and memory (lots of options).
33
34#include <stdio.h>
35#include <stdlib.h>
36#include <string.h>
37#include <stdint.h>
38#include <rs_galois.h>
39#include <liberasurecode_rs_vand.h>
40
41#include <unistd.h>
42#include <fcntl.h>
43
44void print_matrix(int *matrix, int rows, int cols)
45{
46 int i, j;
47
48 printf("\n");
49 for (i = 0; i < rows; i++) {
50 for (j = 0; j < cols; j++) {
51 printf("%d ", matrix[(i * cols) + j]);
52 }
53 printf("\n");
54 }
55 printf("\n");
56}
57
58void square_matrix_multiply(int *m1, int *m2, int *prod, int n)
59{
60 int i, j, k;
61
62 for (i = 0; i < n; i++) {
63 for (j = 0; j < n; j++) {
64 int p = 0;
65 for (k = 0; k < n; k++) {
66 p ^= rs_galois_mult(m1[(j*n)+k], m2[(k*n)+i]);
67 }
68 prod[(j*n)+i] = p;
69 }
70 }
71}
72
73int is_identity_matrix(int *matrix, int n)
74{
75 int i, j;
76
77 for (i = 0; i < n; i++) {
78 for (j = 0; j < n; j++) {
79 int val = matrix[(i*n) + j];
80 if (i != j) {
81 if (val != 0) {
82 return 0;
83 }
84 } else {
85 if (val != 1) {
86 return 0;
87 }
88 }
89 }
90 }
91 return 1;
92}
93
94int* get_matrix_row(int *matrix, int row_idx, int num_cols)
95{
96 return &matrix[row_idx * num_cols];
97}
98
99void copy_row(int *from_matrix, int *to_matrix, int from_row_idx, int to_row_idx, int num_cols)
100{
101 int *from_row = get_matrix_row(from_matrix, from_row_idx, num_cols);
102 int *to_row = get_matrix_row(to_matrix, to_row_idx, num_cols);
103
104 memcpy(to_row, from_row, sizeof(int)*num_cols);
105}
106
107int is_missing(int *missing_idxs, int index_to_check)
108{
109 int i = 0;
110 while (missing_idxs[i] > -1) {
111 if (missing_idxs[i] == index_to_check) {
112 return 1;
113 }
114 i++;
115 }
116 return 0;
117}
118
119int create_decoding_matrix(int *gen_matrix, int *dec_matrix, int *missing_idxs, int k, int m)
120{
121 int i, j;
122 int n = k+m;
123
124 for (i = 0, j = 0; i < n && j < k; i++) {
125 if (!is_missing(missing_idxs, i)) {
126 copy_row(gen_matrix, dec_matrix, i, j, k);
127 j++;
128 }
129 }
130
131 return j == k;
132}
133
134
136{
138}
139
141{
143}
144
146{
147 int rows = k + m;
148 int cols = k;
149 int i, j, acc;
150 int *matrix = (int*)malloc(sizeof(int)*rows*cols);
151
152 if (NULL == matrix) return NULL;
153
154 // First row is 1, 0, 0, ..., 0
155 matrix[0] = 1;
156 for (i = 1; i < cols; i++) matrix[i] = 0;
157
158 // Other rows are:
159 // i^0 (=1), i^1, i^2, ..., i^(cols-1)
160 for (i = 1; i < rows; i++) {
161 acc = 1;
162 for (j = 0; j < cols; j++) {
163 matrix[i * cols + j] = acc;
164 acc = rs_galois_mult(acc, i);
165 }
166 }
167
168 return matrix;
169}
170
171// Swap the entries of two rows in a matrix
172void swap_matrix_rows(int *r1, int *r2, int num_cols)
173{
174 int i;
175 int tmp;
176
177 for (i = 0; i < num_cols; i++) {
178 tmp = r1[i];
179 r1[i] = r2[i];
180 r2[i] = tmp;
181 }
182}
183
184void col_mult(int *matrix, int elem, int col_idx, int num_rows, int num_cols)
185{
186 int i;
187
188 for (i = 0; i < num_rows; i++) {
189 matrix[col_idx] = rs_galois_mult(matrix[col_idx], elem);
190 col_idx += num_cols;
191 }
192}
193
194void row_mult(int *matrix, int elem, int row_idx, int num_rows, int num_cols)
195{
196 int i, to_row = row_idx * num_cols;
197
198 for (i = 0; i < num_cols; i++) {
199 matrix[to_row] = rs_galois_mult(matrix[to_row], elem);
200 to_row++;
201 }
202}
203
204void col_mult_and_add(int *matrix, int elem, int from_col, int to_col, int num_rows, int num_cols)
205{
206 int i;
207
208 for (i = 0; i < num_rows; i++) {
209 matrix[to_col] = matrix[to_col] ^ rs_galois_mult(matrix[from_col], elem);
210 from_col += num_cols;
211 to_col += num_cols;
212 }
213}
214
215void row_mult_and_add(int *matrix, int elem, int from_row, int to_row, int num_rows, int num_cols)
216{
217 int i;
218 from_row = from_row * num_cols;
219 to_row = to_row * num_cols;
220 for (i = 0; i < num_cols; i++) {
221 matrix[to_row] = matrix[to_row] ^ rs_galois_mult(matrix[from_row], elem);
222 to_row++;
223 from_row++;
224 }
225}
226
227int get_non_zero_diagonal(int *matrix, int row, int num_rows, int num_cols)
228{
229 int i, row_idx;
230
231 row_idx = (num_cols * row) + row;
232 for (i = row; i < num_rows; i++) {
233 if (matrix[row_idx] != 0) {
234 return i;
235 }
236 row_idx += num_cols;
237 }
238
239 return -1;
240}
241
242int * make_systematic_matrix(int k, int m)
243{
244 int rows = k + m;
245 int cols = k;
246 int i, j;
247 int *matrix = create_non_systematic_vand_matrix(k, m);
248
249 if (NULL == matrix) return NULL;
250
251 // The first row is already 1, 0, 0, ..., 0
252 for (i = 1; i < cols; i++) {
253 int diag_idx = ((cols*i) + i);
254 // Get next row candidate, whose diagonal entry @ i,i != 0
255 int next_row = get_non_zero_diagonal(matrix, i, rows, cols);
256
257 // Swap candidate row with row i, if needed
258 if (next_row != i) {
259 swap_matrix_rows(&matrix[next_row*cols], &matrix[i*cols], cols);
260 }
261
262 // Ensure the leading entry of row i is 1 by multiplying the
263 // column by the inverse of matrix[diag_idx]
264 if (matrix[diag_idx] != 1) {
265 col_mult(matrix, rs_galois_inverse(matrix[diag_idx]), i, rows, cols);
266 }
267
268 // Zero-out all non-zero, non-diagonal entries in row i
269 // by multiplying the corresponding columns by col-i*<row_value>
270 for (j = 0; j < cols; j++) {
271 int row_val = matrix[(i * cols) + j];
272 if (i != j && row_val != 0) {
273 col_mult_and_add(matrix, row_val, i, j, rows, cols);
274 }
275 }
276 }
277
278 // Create all-XOR parity as first row of parity submatrix
279 for (i = 0; i < cols; i++) {
280 int row_val = matrix[(cols * cols) + i];
281 if (row_val != 1) {
282 // Multiply the parity sub-column by the inverse of row_val
283 // We then implicitly multuply row i by the inverse of row_val
284 // (not explicitly necessary, since all other entries are 0)
285 col_mult(&matrix[cols*cols], rs_galois_inverse(row_val), i, rows - cols, cols);
286 }
287 }
288
289 return matrix;
290}
291
292void free_systematic_matrix(int *matrix)
293{
294 free(matrix);
295}
296
297int gaussj_inversion(int *matrix, int *inverse, int n)
298{
299 int i, j;
300
301 // Zero out the inverse matrix
302 memset(inverse, 0, sizeof(int)*n*n);
303
304 // Make the inverse matrix an identity matrix
305 for (i = 0; i < n; i++) {
306 int diag_idx = ((n*i) + i);
307 inverse[diag_idx] = 1;
308 }
309
310 for (i = 0; i < n; i++) {
311 int diag_idx = ((n*i) + i);
312 // Get next row candidate, whose diagonal entry @ i,i != 0
313 int next_row = get_non_zero_diagonal(matrix, i, n, n);
314
315 // Swap candidate row with row i, if needed
316 if (next_row != i) {
317 swap_matrix_rows(&matrix[next_row*n], &matrix[i*n], n);
318 swap_matrix_rows(&inverse[next_row*n], &inverse[i*n], n);
319 }
320
321 // Make the leading entry a '1'
322 if (matrix[diag_idx] != 1) {
323 int leading_val_inv = rs_galois_inverse(matrix[diag_idx]);
324 row_mult(matrix, leading_val_inv, i, n, n);
325 row_mult(inverse, leading_val_inv, i, n, n);
326 }
327
328 // Zero-out all other entries in column i
329 for (j = 0; j < n; j++) {
330 if (i != j) {
331 int val = matrix[(j * n) + i];
332 row_mult_and_add(matrix, val, i, j, n, n);
333 row_mult_and_add(inverse, val, i, j, n, n);
334 }
335 }
336 }
337 return 0;
338}
339
340void region_xor(char *from_buf, char *to_buf, int blocksize)
341{
342 int i;
343
344 uint32_t *_from_buf = (uint32_t*)from_buf;
345 uint32_t *_to_buf = (uint32_t*)to_buf;
346 int adj_blocksize = blocksize / 4;
347 int trailing_bytes = blocksize % 4;
348
349 for (i = 0; i < adj_blocksize; i++) {
350 _to_buf[i] = _to_buf[i] ^ _from_buf[i];
351 }
352
353 for (i = blocksize-trailing_bytes; i < blocksize; i++) {
354 to_buf[i] = to_buf[i] ^ from_buf[i];
355 }
356}
357
358void region_multiply(char *from_buf, char *to_buf, int mult, int xor, int blocksize)
359{
360 int i;
361 uint16_t *_from_buf = (uint16_t*)from_buf;
362 uint16_t *_to_buf = (uint16_t*)to_buf;
363 int adj_blocksize = blocksize / 2;
364 int trailing_bytes = blocksize % 2;
365
366 if (xor) {
367 for (i = 0; i < adj_blocksize; i++) {
368 _to_buf[i] = _to_buf[i] ^ (uint16_t)rs_galois_mult(_from_buf[i], mult);
369 }
370
371 if (trailing_bytes == 1) {
372 i = blocksize - 1;
373 to_buf[i] = to_buf[i] ^ (char)rs_galois_mult(from_buf[i], mult);
374 }
375 } else {
376 for (i = 0; i < adj_blocksize; i++) {
377 _to_buf[i] = (uint16_t)rs_galois_mult(_from_buf[i], mult);
378 }
379
380 if (trailing_bytes == 1) {
381 i = blocksize - 1;
382 to_buf[i] = (char)rs_galois_mult(from_buf[i], mult);
383 }
384 }
385}
386
387void region_dot_product(char **from_bufs, char *to_buf, int *matrix_row, int num_entries, int blocksize)
388{
389 int i;
390
391 for (i = 0; i < num_entries; i++) {
392 int mult = matrix_row[i];
393 if (mult == 1) {
394 region_xor(from_bufs[i], to_buf, blocksize);
395 } else {
396 region_multiply(from_bufs[i], to_buf, mult, 1, blocksize);
397 }
398 }
399}
400
401int liberasurecode_rs_vand_encode(int *generator_matrix, char **data, char **parity, int k, int m, int blocksize)
402{
403 int i;
404 int n = k + m;
405
406 for (i = k; i < n; i++) {
407 memset(parity[i - k], 0, blocksize);
408 region_dot_product(data, parity[i - k], &generator_matrix[(i * k)], k, blocksize);
409 }
410
411 return 0;
412}
413
414char **get_first_k_available(char **data, char **parity, int *missing, int k)
415{
416 int i, j;
417 char **first_k_available = (char**)malloc(sizeof(char*)*k);
418
419 for (i = 0, j = 0; j < k; i++) {
420 if (!missing[i]) {
421 first_k_available[j] = i < k ? data[i] : parity[i - k];
422 j++;
423 }
424 }
425 return first_k_available;
426}
427
428int liberasurecode_rs_vand_decode(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int blocksize, int rebuild_parity)
429{
430 int *decoding_matrix = NULL;
431 int *inverse_decoding_matrix = NULL;
432 char **first_k_available = NULL;
433 int n = m + k;
434 int *_missing = (int*)malloc(sizeof(int)*n);
435 int i = 0;
436 int num_missing = 0;
437
438 memset(_missing, 0, sizeof(int)*n);
439
440 while (missing[num_missing] > -1) {
441 _missing[missing[num_missing]] = 1;
442 num_missing++;
443 }
444
445 if (num_missing > m) {
446 free(_missing);
447 return -1;
448 }
449
450 decoding_matrix = (int*)malloc(sizeof(int)*k*k);
451 inverse_decoding_matrix = (int*)malloc(sizeof(int)*k*k);
452 first_k_available = get_first_k_available(data, parity, _missing, k);
453
454 create_decoding_matrix(generator_matrix, decoding_matrix, missing, k, m);
455 gaussj_inversion(decoding_matrix, inverse_decoding_matrix, k);
456
457 // Rebuild data fragments
458 for (i = 0; i < k; i++) {
459 // Data fragment i is missing, recover it
460 if (_missing[i]) {
461 region_dot_product(first_k_available, data[i], &inverse_decoding_matrix[(i * k)], k, blocksize);
462 }
463 }
464
465 // Rebuild parity fragments
466 if (rebuild_parity) {
467 for (i = k; i < n; i++) {
468 // Parity fragment i is missing, recover it
469 if (_missing[i]) {
470 region_dot_product(data, parity[i - k], &generator_matrix[(i * k)], k, blocksize);
471 }
472 }
473 }
474
475 free(decoding_matrix);
476 free(inverse_decoding_matrix);
477 free(first_k_available);
478 free(_missing);
479
480 return 0;
481}
482
483int liberasurecode_rs_vand_reconstruct(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int destination_idx, int blocksize)
484{
485 int *decoding_matrix = NULL;
486 int *inverse_decoding_matrix = NULL;
487 char **first_k_available = NULL;
488 int *parity_row = NULL;
489 int n = k + m;
490 int *_missing = (int*)malloc(sizeof(int)*n);
491 int i, j;
492 int num_missing = 0;
493
494 memset(_missing, 0, sizeof(int)*n);
495
496 while (missing[num_missing] > -1) {
497 _missing[missing[num_missing]] = 1;
498 num_missing++;
499 }
500
501 if (num_missing > m) {
502 free(_missing);
503 return -1;
504 }
505
506 decoding_matrix = (int*)malloc(sizeof(int)*k*k);
507 inverse_decoding_matrix = (int*)malloc(sizeof(int)*k*k);
508 first_k_available = get_first_k_available(data, parity, _missing, k);
509
510 create_decoding_matrix(generator_matrix, decoding_matrix, missing, k, m);
511 gaussj_inversion(decoding_matrix, inverse_decoding_matrix, k);
512
513 // Rebuilding data is easy, just do a dot product using the inverted decoding
514 // matrix
515 if (destination_idx < k) {
516 region_dot_product(first_k_available, data[destination_idx], &inverse_decoding_matrix[(destination_idx * k)], k, blocksize);
517 } else {
518 // Rebuilding parity is a little tricker, we first copy the corresp. parity row
519 // and update it to reconstruct the parity with the first k available elements
520
521 // Copy the parity entries for available data elements
522 // from the original generator matrix
523 parity_row = (int*)malloc(sizeof(int)*k);
524 memset(parity_row, 0, sizeof(int)*k);
525 j = 0;
526 for (i = 0; i < k; i++) {
527 if (!_missing[i]) {
528 parity_row[j] = generator_matrix[(destination_idx * k) + i];
529 j++;
530 }
531 }
532
533 i = 0;
534 // For each missing data element, we substitute in the row (equation) for the data element into the
535 // the parity row.
536 while (missing[i] > -1) {
537 if (missing[i] < k) {
538 for (j = 0; j < k; j++) {
539 parity_row[j] ^= rs_galois_mult(generator_matrix[(destination_idx * k) + missing[i]], inverse_decoding_matrix[(missing[i] * k) + j]);
540 }
541 }
542 i++;
543 }
544 region_dot_product(first_k_available, parity[destination_idx - k], parity_row, k, blocksize);
545 }
546 free(parity_row);
547 free(decoding_matrix);
548 free(inverse_decoding_matrix);
549 free(first_k_available);
550 free(_missing);
551
552 return 0;
553}
static int liberasurecode_rs_vand_encode(void *desc, char **data, char **parity, int blocksize)
static int liberasurecode_rs_vand_decode(void *desc, char **data, char **parity, int *missing_idxs, int blocksize)
static int liberasurecode_rs_vand_reconstruct(void *desc, char **data, char **parity, int *missing_idxs, int destination_idx, int blocksize)
void row_mult_and_add(int *matrix, int elem, int from_row, int to_row, int num_rows, int num_cols)
void region_xor(char *from_buf, char *to_buf, int blocksize)
int get_non_zero_diagonal(int *matrix, int row, int num_rows, int num_cols)
int gaussj_inversion(int *matrix, int *inverse, int n)
void swap_matrix_rows(int *r1, int *r2, int num_cols)
void region_multiply(char *from_buf, char *to_buf, int mult, int xor, int blocksize)
void square_matrix_multiply(int *m1, int *m2, int *prod, int n)
void copy_row(int *from_matrix, int *to_matrix, int from_row_idx, int to_row_idx, int num_cols)
int * create_non_systematic_vand_matrix(int k, int m)
void region_dot_product(char **from_bufs, char *to_buf, int *matrix_row, int num_entries, int blocksize)
int is_missing(int *missing_idxs, int index_to_check)
int * get_matrix_row(int *matrix, int row_idx, int num_cols)
void row_mult(int *matrix, int elem, int row_idx, int num_rows, int num_cols)
void col_mult(int *matrix, int elem, int col_idx, int num_rows, int num_cols)
void print_matrix(int *matrix, int rows, int cols)
int * make_systematic_matrix(int k, int m)
int is_identity_matrix(int *matrix, int n)
void deinit_liberasurecode_rs_vand()
int create_decoding_matrix(int *gen_matrix, int *dec_matrix, int *missing_idxs, int k, int m)
void col_mult_and_add(int *matrix, int elem, int from_col, int to_col, int num_rows, int num_cols)
char ** get_first_k_available(char **data, char **parity, int *missing, int k)
void init_liberasurecode_rs_vand(int k, int m)
void free_systematic_matrix(int *matrix)
int rs_galois_inverse(int x)
Definition rs_galois.c:98
void rs_galois_init_tables()
Definition rs_galois.c:48
int rs_galois_mult(int x, int y)
Definition rs_galois.c:74
void rs_galois_deinit_tables()
Definition rs_galois.c:68