liberasurecode  1.6.2
Erasure Code API library
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 
44 void 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 
58 void 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 
73 int 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 
94 int* get_matrix_row(int *matrix, int row_idx, int num_cols)
95 {
96  return &matrix[row_idx * num_cols];
97 }
98 
99 void 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 
107 int 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 
119 int 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 
135 void init_liberasurecode_rs_vand(int k, int m)
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
172 void 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 
184 void 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 
194 void 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 
204 void 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 
215 void 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 
227 int 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 
242 int * 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 
292 void free_systematic_matrix(int *matrix)
293 {
294  free(matrix);
295 }
296 
297 int 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 
340 void 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 
358 void 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 
387 void 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 
401 int 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 
414 char **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 
428 int 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 
483 int 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 }
is_identity_matrix
int is_identity_matrix(int *matrix, int n)
Definition: liberasurecode_rs_vand.c:73
liberasurecode_rs_vand_reconstruct
int liberasurecode_rs_vand_reconstruct(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int destination_idx, int blocksize)
Definition: liberasurecode_rs_vand.c:483
rs_galois_init_tables
void rs_galois_init_tables()
Definition: rs_galois.c:48
liberasurecode_rs_vand_decode
int liberasurecode_rs_vand_decode(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int blocksize, int rebuild_parity)
Definition: liberasurecode_rs_vand.c:428
copy_row
void copy_row(int *from_matrix, int *to_matrix, int from_row_idx, int to_row_idx, int num_cols)
Definition: liberasurecode_rs_vand.c:99
print_matrix
void print_matrix(int *matrix, int rows, int cols)
Definition: liberasurecode_rs_vand.c:44
swap_matrix_rows
void swap_matrix_rows(int *r1, int *r2, int num_cols)
Definition: liberasurecode_rs_vand.c:172
init_liberasurecode_rs_vand
void init_liberasurecode_rs_vand(int k, int m)
Definition: liberasurecode_rs_vand.c:135
liberasurecode_rs_vand_encode
int liberasurecode_rs_vand_encode(int *generator_matrix, char **data, char **parity, int k, int m, int blocksize)
Definition: liberasurecode_rs_vand.c:401
region_dot_product
void region_dot_product(char **from_bufs, char *to_buf, int *matrix_row, int num_entries, int blocksize)
Definition: liberasurecode_rs_vand.c:387
get_matrix_row
int * get_matrix_row(int *matrix, int row_idx, int num_cols)
Definition: liberasurecode_rs_vand.c:94
free_systematic_matrix
void free_systematic_matrix(int *matrix)
Definition: liberasurecode_rs_vand.c:292
row_mult
void row_mult(int *matrix, int elem, int row_idx, int num_rows, int num_cols)
Definition: liberasurecode_rs_vand.c:194
region_xor
void region_xor(char *from_buf, char *to_buf, int blocksize)
Definition: liberasurecode_rs_vand.c:340
get_non_zero_diagonal
int get_non_zero_diagonal(int *matrix, int row, int num_rows, int num_cols)
Definition: liberasurecode_rs_vand.c:227
create_non_systematic_vand_matrix
int * create_non_systematic_vand_matrix(int k, int m)
Definition: liberasurecode_rs_vand.c:145
create_decoding_matrix
int create_decoding_matrix(int *gen_matrix, int *dec_matrix, int *missing_idxs, int k, int m)
Definition: liberasurecode_rs_vand.c:119
rs_galois_deinit_tables
void rs_galois_deinit_tables()
Definition: rs_galois.c:68
region_multiply
void region_multiply(char *from_buf, char *to_buf, int mult, int xor, int blocksize)
Definition: liberasurecode_rs_vand.c:358
deinit_liberasurecode_rs_vand
void deinit_liberasurecode_rs_vand()
Definition: liberasurecode_rs_vand.c:140
gaussj_inversion
int gaussj_inversion(int *matrix, int *inverse, int n)
Definition: liberasurecode_rs_vand.c:297
row_mult_and_add
void row_mult_and_add(int *matrix, int elem, int from_row, int to_row, int num_rows, int num_cols)
Definition: liberasurecode_rs_vand.c:215
square_matrix_multiply
void square_matrix_multiply(int *m1, int *m2, int *prod, int n)
Definition: liberasurecode_rs_vand.c:58
rs_galois_mult
int rs_galois_mult(int x, int y)
Definition: rs_galois.c:74
get_first_k_available
char ** get_first_k_available(char **data, char **parity, int *missing, int k)
Definition: liberasurecode_rs_vand.c:414
is_missing
int is_missing(int *missing_idxs, int index_to_check)
Definition: liberasurecode_rs_vand.c:107
rs_galois_inverse
int rs_galois_inverse(int x)
Definition: rs_galois.c:98
col_mult_and_add
void col_mult_and_add(int *matrix, int elem, int from_col, int to_col, int num_rows, int num_cols)
Definition: liberasurecode_rs_vand.c:204
make_systematic_matrix
int * make_systematic_matrix(int k, int m)
Definition: liberasurecode_rs_vand.c:242
col_mult
void col_mult(int *matrix, int elem, int col_idx, int num_rows, int num_cols)
Definition: liberasurecode_rs_vand.c:184