liberasurecode  1.6.2
Erasure Code API library
xor_hd_code.c
Go to the documentation of this file.
1 /* * Copyright (c) 2013, Kevin Greenan (kmgreen2@gmail.com)
2  * All rights reserved.
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 
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include "xor_code.h"
29 #include "xor_hd_code_defs.h"
30 
31 /*
32  * Returns -1 if not possible
33  */
34 static int fragments_needed_one_data(xor_code_t *code_desc, int *missing_data, int *missing_parity, unsigned int *data_bm, unsigned int *parity_bm)
35 {
36  int data_index = missing_data[0];
37  int parity_index = index_of_connected_parity(code_desc, data_index, missing_parity, missing_data);
38 
39  if (parity_index < 0) {
40  return -1;
41  }
42 
43  // Include all data elements except for this one
44  *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
45 
46  // Include this parity element
47  *parity_bm |= (1 << (parity_index-code_desc->k));
48  *data_bm &= ~((unsigned int)1 << data_index);
49 
50  return 0;
51 }
52 
53 /*
54  * Returns -1 if not possible
55  */
56 static int fragments_needed_two_data(xor_code_t *code_desc, int *missing_data, int *missing_parity, unsigned int *data_bm, unsigned int *parity_bm)
57 {
58  // Verify that missing_data[2] == -1?
59  int data_index = missing_data[0];
60  int parity_index = index_of_connected_parity(code_desc, data_index, missing_parity, missing_data);
61  int ret;
62 
63  if (parity_index < 0) {
64  data_index = missing_data[1];
65  parity_index = index_of_connected_parity(code_desc, data_index, missing_parity, missing_data);
66  if (parity_index < 0) {
67  return -1;
68  }
69  missing_data[1] = -1;
70  } else {
71  missing_data[0] = missing_data[1];
72  missing_data[1] = -1;
73  }
74 
75  // Include all data elements except for this one
76  *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
77 
78  // Include this parity element
79  *parity_bm |= (1 << (parity_index-code_desc->k));
80 
81  ret = fragments_needed_one_data(code_desc, missing_data, missing_parity, data_bm, parity_bm);
82 
83  *data_bm &= ~((unsigned int)1 << data_index);
84 
85  return ret;
86 }
87 
88 /*
89  * Returns -1 if not possible
90  */
91 static int fragments_needed_three_data(xor_code_t *code_desc, int *missing_data, int *missing_parity, unsigned int *data_bm, unsigned int *parity_bm)
92 {
93  int i = 0;
94  int parity_index = -1;
95  int data_index = -1;
96  int tmp_parity_bm = -1;
97  int contains_2d = -1;
98  int contains_3d = -1;
99  int ret = 0;
100 
101  /*
102  * Try to find a parity that only contains
103  * one of the missing data elements.
104  */
105  while (missing_data[i] > -1) {
106  parity_index = index_of_connected_parity(code_desc, missing_data[i], missing_parity, missing_data);
107  if (parity_index > -1) {
108  data_index = missing_data[i];
109  tmp_parity_bm = code_desc->parity_bms[parity_index-code_desc->k];
110  break;
111  }
112  i++;
113  }
114  /*
115  * If we cannot find a parity that is connected to only
116  * one missing element, we must find a parity that is
117  * connected to exactly 2 (P) and another that is connected
118  * to exactly 3 (Q) (it should exist!!!).
119  *
120  * We XOR those parities together and use it to recover
121  * the element that is not connected to P.
122  */
123  if (parity_index < 0) {
124 
125  for (i=0;i < code_desc->m;i++) {
126  int num_missing = num_missing_data_in_parity(code_desc, code_desc->k+i, missing_data);
127  if (num_missing == 2 && contains_2d < 0) {
128  contains_2d = i;
129  } else if (num_missing == 3 && contains_3d < 0) {
130  contains_3d = i;
131  }
132  }
133 
134  if (contains_2d < 0 || contains_3d < 0) {
135  return -1;
136  }
137 
138  // P XOR Q
139  tmp_parity_bm = code_desc->parity_bms[contains_2d] ^ code_desc->parity_bms[contains_3d];
140 
141  i=0;
142  data_index = -1;
143  while (missing_data[i] > -1) {
144  if (is_data_in_parity(missing_data[i], tmp_parity_bm)) {
145  data_index = missing_data[i];
146  break;
147  }
148  i++;
149  }
150 
151  if (data_index < 0) {
152  return -1;
153  }
154  }
155 
156  remove_from_missing_list(data_index, missing_data);
157 
158  // Include all data elements except for this one
159  *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
160 
161  // Include this parity element
162  if (parity_index > -1) {
163  *parity_bm |= (1 << (parity_index-code_desc->k));
164  } else {
165  *parity_bm |= (1 << (contains_2d-code_desc->k));
166  *parity_bm |= (1 << (contains_3d-code_desc->k));
167  }
168 
169  ret = fragments_needed_two_data(code_desc, missing_data, missing_parity, data_bm, parity_bm);
170 
171  *data_bm &= ~((unsigned int)1 << data_index);
172 
173  return ret;
174 }
175 
176 static int fragments_needed_one_data_local(xor_code_t *code_desc,
177  int fragment_to_reconstruct,
178  int *fragments_to_exclude,
179  unsigned int *data_bm,
180  unsigned int *parity_bm)
181 {
182  int *missing_data = get_missing_data(code_desc, fragments_to_exclude);
183  int *missing_parity = get_missing_parity(code_desc, fragments_to_exclude);
184  int parity_index = index_of_connected_parity(code_desc, fragment_to_reconstruct, missing_parity, missing_data);
185  free(missing_data);
186  free(missing_parity);
187 
188  if (parity_index < 0) {
189  return -1;
190  }
191 
192  // Include all data elements except for this one
193  *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
194 
195  // Include this parity element
196  *parity_bm |= (1 << (parity_index-code_desc->k));
197  *data_bm &= ~((unsigned int)1 << fragment_to_reconstruct);
198 
199  return 0;
200 }
201 
202 int xor_hd_fragments_needed(xor_code_t *code_desc, int *fragments_to_reconstruct, int *fragments_to_exclude, int *fragments_needed)
203 {
204  failure_pattern_t pattern = get_failure_pattern(code_desc, fragments_to_reconstruct);
205  unsigned int data_bm = 0, parity_bm = 0;
206  int ret = -1;
207  int *missing_idxs = NULL;
208  int i, j;
209 
218  if (pattern == FAIL_PATTERN_1D_0P) {
219  // Since we have landed on this failure pattern, fragments_to_reconstruct[0] is defined.
220  ret = fragments_needed_one_data_local(code_desc, fragments_to_reconstruct[0], fragments_to_exclude, &data_bm, &parity_bm);
221  }
222 
227  if (ret == -1) {
231  missing_idxs = (int*)malloc(sizeof(int)*(code_desc->k + code_desc->m));
232  if (NULL == missing_idxs) {
233  ret = -1;
234  goto out;
235  }
236 
237  i = 0;
238  j = 0;
239  while (fragments_to_reconstruct[i] > -1) {
240  missing_idxs[j] = fragments_to_reconstruct[i];
241  i++;
242  j++;
243  }
244  i = 0;
245  while (fragments_to_exclude[i] > -1) {
246  missing_idxs[j] = fragments_to_exclude[i];
247  i++;
248  j++;
249  }
250  // End of list
251  missing_idxs[j] = -1;
252 
253  pattern = get_failure_pattern(code_desc, missing_idxs);
254 
255  switch(pattern) {
256  case FAIL_PATTERN_0D_0P:
257  break;
258  case FAIL_PATTERN_1D_0P:
259  {
260  int *missing_data = get_missing_data(code_desc, missing_idxs);
261  ret = fragments_needed_one_data(code_desc, missing_data, NULL, &data_bm, &parity_bm);
262  free(missing_data);
263  break;
264  }
265  case FAIL_PATTERN_2D_0P:
266  {
267  int *missing_data = get_missing_data(code_desc, missing_idxs);
268  ret = fragments_needed_two_data(code_desc, missing_data, NULL, &data_bm, &parity_bm);
269  free(missing_data);
270  break;
271  }
272  case FAIL_PATTERN_3D_0P:
273  {
274  int *missing_data = get_missing_data(code_desc, missing_idxs);
275  ret = fragments_needed_three_data(code_desc, missing_data, NULL, &data_bm, &parity_bm);
276  free(missing_data);
277  break;
278  }
279  case FAIL_PATTERN_1D_1P:
280  {
281  int *missing_data = get_missing_data(code_desc, missing_idxs);
282  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
283  unsigned int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup);
284  ret = fragments_needed_one_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm);
285  // OR all parities
286  i=0;
287  while (missing_parity[i] > -1) {
288  data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
289  data_bm &= ~(missing_data_bm);
290  i++;
291  }
292  free(missing_parity);
293  free(missing_data);
294  break;
295  }
296  case FAIL_PATTERN_1D_2P:
297  {
298  int *missing_data = get_missing_data(code_desc, missing_idxs);
299  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
300  int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup);
301  ret = fragments_needed_one_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm);
302  // OR all parities
303  i=0;
304  while (missing_parity[i] > -1) {
305  data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
306  data_bm &= ~(missing_data_bm);
307  i++;
308  }
309  free(missing_parity);
310  free(missing_data);
311  break;
312  }
313  case FAIL_PATTERN_2D_1P:
314  {
315  int *missing_data = get_missing_data(code_desc, missing_idxs);
316  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
317  unsigned int missing_data_bm = missing_elements_bm(code_desc, missing_data, data_bit_lookup);
318  ret = fragments_needed_two_data(code_desc, missing_data, missing_parity, &data_bm, &parity_bm);
319  // OR all parities
320  i=0;
321  while (missing_parity[i] > -1) {
322  data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
323  data_bm &= ~(missing_data_bm);
324  i++;
325  }
326  free(missing_parity);
327  free(missing_data);
328  break;
329  }
330  case FAIL_PATTERN_0D_1P:
331  {
332  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
333  // OR all of the parities
334  i=0;
335  while (missing_parity[i] > -1) {
336  data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
337  i++;
338  }
339  free(missing_parity);
340  ret = 0;
341  break;
342  }
343  case FAIL_PATTERN_0D_2P:
344  {
345  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
346  // OR all of the parities
347  i=0;
348  while (missing_parity[i] > -1) {
349  data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
350  i++;
351  }
352  free(missing_parity);
353  ret = 0;
354  break;
355  }
356  case FAIL_PATTERN_0D_3P:
357  {
358  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
359  // OR all of the parities
360  i=0;
361  while (missing_parity[i] > -1) {
362  data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
363  i++;
364  }
365  free(missing_parity);
366  ret = 0;
367  break;
368  }
369  case FAIL_PATTERN_GE_HD:
370  default:
371  break;
372  }
373  }
374 
375  if (ret >= 0) {
376  i=0;
377  j=0;
378  while (data_bm) {
379  if (data_bm & 1) {
380  fragments_needed[j] = i;
381  j++;
382  }
383  i++;
384  data_bm >>= 1;
385  }
386 
387  i=0;
388  while (parity_bm) {
389  if (parity_bm & 1) {
390  fragments_needed[j] = i + code_desc->k;
391  j++;
392  }
393  i++;
394  parity_bm >>= 1;
395  }
396 
397  fragments_needed[j] = -1;
398  }
399 
400 out:
401  if (NULL != missing_idxs) {
402  free(missing_idxs);
403  }
404 
405  return ret;
406 }
407 
408 /*
409  * There is one unavailable data element, so any available parity connected to
410  * the data element is sufficient to decode.
411  */
412 static void decode_one_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)
413 {
414  // Verify that missing_data[1] == -1?
415  int data_index = missing_data[0];
416  int parity_index = index_of_connected_parity(code_desc, data_index, missing_parity, missing_data);
417  int i;
418 
419  // Copy the appropriate parity into the data buffer
420  fast_memcpy(data[data_index], parity[parity_index-code_desc->k], blocksize);
421 
422  for (i=0; i < code_desc->k; i++) {
423  if (i != data_index && is_data_in_parity(i, code_desc->parity_bms[parity_index-code_desc->k])) {
424  xor_bufs_and_store(data[i], data[data_index], blocksize);
425  }
426  }
427 }
428 
429 static int decode_two_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)
430 {
431  // Verify that missing_data[2] == -1?
432  int data_index = missing_data[0];
433  int parity_index = index_of_connected_parity(code_desc, data_index, missing_parity, missing_data);
434  int i;
435 
436  if (parity_index < 0) {
437  data_index = missing_data[1];
438  parity_index = index_of_connected_parity(code_desc, data_index, missing_parity, missing_data);
439  if (parity_index < 0) {
440  fprintf(stderr, "Shit is broken, cannot find a proper parity!!!\n");
441  return -2;
442  }
443  missing_data[1] = -1;
444  } else {
445  missing_data[0] = missing_data[1];
446  missing_data[1] = -1;
447  }
448 
449  // Copy the appropriate parity into the data buffer
450  fast_memcpy(data[data_index], parity[parity_index-code_desc->k], blocksize);
451 
452  for (i=0; i < code_desc->k; i++) {
453  if (i != data_index && is_data_in_parity(i, code_desc->parity_bms[parity_index-code_desc->k])) {
454  xor_bufs_and_store(data[i], data[data_index], blocksize);
455  }
456  }
457  decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
458 
459  return 0;
460 }
461 
462 static int decode_three_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)
463 {
464  int i = 0;
465  int parity_index = -1;
466  int data_index = -1;
467  unsigned int parity_bm = -1;
468  char *parity_buffer = NULL;
469 
470  /*
471  * Try to find a parity that only contains
472  * one of the missing data elements.
473  */
474  while (missing_data[i] > -1) {
475  parity_index = index_of_connected_parity(code_desc, missing_data[i], missing_parity, missing_data);
476  if (parity_index > -1) {
477  data_index = missing_data[i];
478  parity_buffer = parity[parity_index-code_desc->k];
479  parity_bm = code_desc->parity_bms[parity_index-code_desc->k];
480  break;
481  }
482  i++;
483  }
484 
485  /*
486  * If we cannot find a parity that is connected to only
487  * one missing element, we must find a parity that is
488  * connected to exactly 2 (P) and another that is connected
489  * to exactly 3 (Q) (it should exist!!!).
490  *
491  * We XOR those parities together and use it to recover
492  * the element that is not connected to P.
493  */
494  if (parity_index < 0) {
495  int contains_2d = -1;
496  int contains_3d = -1;
497 
498  for (i=0;i < code_desc->m;i++) {
499  int num_missing = num_missing_data_in_parity(code_desc, code_desc->k+i, missing_data);
500  if (num_missing == 2 && contains_2d < 0) {
501  contains_2d = i;
502  } else if (num_missing == 3 && contains_3d < 0) {
503  contains_3d = i;
504  }
505  }
506 
507  if (contains_2d < 0 || contains_3d < 0) {
508  fprintf(stderr, "Shit is broken, cannot find a proper parity (2 and 3-connected parities)!!!\n");
509  return -2;
510  }
511 
512  if (posix_memalign((void **) &parity_buffer, 16, blocksize) != 0) {
513  fprintf(stderr, "Can't get aligned memory!\n");
514  return -1;
515  }
516 
517  // P XOR Q
518  parity_bm = code_desc->parity_bms[contains_2d] ^ code_desc->parity_bms[contains_3d];
519 
520  // Create buffer with P XOR Q -> parity_buffer
521  fast_memcpy(parity_buffer, parity[contains_2d], blocksize);
522  xor_bufs_and_store(parity[contains_3d], parity_buffer, blocksize);
523 
524  i=0;
525  data_index = -1;
526  while (missing_data[i] > -1) {
527  if (is_data_in_parity(missing_data[i], parity_bm)) {
528  data_index = missing_data[i];
529  break;
530  }
531  i++;
532  }
533 
534  if (data_index < 0) {
535  fprintf(stderr, "Shit is broken, cannot construct equations to repair 3 failures!!!\n");
536  return -2;
537  }
538  // Copy the appropriate parity into the data buffer
539  fast_memcpy(data[data_index], parity_buffer, blocksize);
540  // Free up the buffer we allocated above
541  free(parity_buffer);
542  } else {
543  // Copy the appropriate parity into the data buffer
544  fast_memcpy(data[data_index], parity_buffer, blocksize);
545  }
546 
547 
548  for (i=0; i < code_desc->k; i++) {
549  if (i != data_index && is_data_in_parity(i, parity_bm)) {
550  xor_bufs_and_store(data[i], data[data_index], blocksize);
551  }
552  }
553 
554  remove_from_missing_list(data_index, missing_data);
555 
556  return decode_two_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
557 }
558 
559 int xor_hd_decode(xor_code_t *code_desc, char **data, char **parity, int *missing_idxs, int blocksize, int decode_parity)
560 {
561  int ret = 0;
562  failure_pattern_t pattern = get_failure_pattern(code_desc, missing_idxs);
563 
564  switch(pattern) {
565  case FAIL_PATTERN_0D_0P:
566  break;
567  case FAIL_PATTERN_1D_0P:
568  {
569  int *missing_data = get_missing_data(code_desc, missing_idxs);
570  decode_one_data(code_desc, data, parity, missing_data, NULL, blocksize);
571  free(missing_data);
572  break;
573  }
574  case FAIL_PATTERN_2D_0P:
575  {
576  int *missing_data = get_missing_data(code_desc, missing_idxs);
577  ret = decode_two_data(code_desc, data, parity, missing_data, NULL, blocksize);
578  free(missing_data);
579  break;
580  }
581  case FAIL_PATTERN_3D_0P:
582  {
583  int *missing_data = get_missing_data(code_desc, missing_idxs);
584  ret = decode_three_data(code_desc, data, parity, missing_data, NULL, blocksize);
585  free(missing_data);
586  break;
587  }
588  case FAIL_PATTERN_1D_1P:
589  {
590  int *missing_data = get_missing_data(code_desc, missing_idxs);
591  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
592  decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
593  if (decode_parity) {
594  selective_encode(code_desc, data, parity, missing_parity, blocksize);
595  }
596  free(missing_parity);
597  free(missing_data);
598  break;
599  }
600  case FAIL_PATTERN_1D_2P:
601  {
602  int *missing_data = get_missing_data(code_desc, missing_idxs);
603  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
604  decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
605  if (decode_parity) {
606  selective_encode(code_desc, data, parity, missing_parity, blocksize);
607  }
608  free(missing_data);
609  free(missing_parity);
610  break;
611  }
612  case FAIL_PATTERN_2D_1P:
613  {
614  int *missing_data = get_missing_data(code_desc, missing_idxs);
615  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
616  ret = decode_two_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
617  if (decode_parity) {
618  selective_encode(code_desc, data, parity, missing_parity, blocksize);
619  }
620  free(missing_parity);
621  free(missing_data);
622  break;
623  }
624  case FAIL_PATTERN_0D_1P:
625  if (decode_parity) {
626  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
627  selective_encode(code_desc, data, parity, missing_parity, blocksize);
628  free(missing_parity);
629  }
630  break;
631  case FAIL_PATTERN_0D_2P:
632  if (decode_parity) {
633  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
634  selective_encode(code_desc, data, parity, missing_parity, blocksize);
635  free(missing_parity);
636  }
637  break;
638  case FAIL_PATTERN_0D_3P:
639  if (decode_parity) {
640  int *missing_parity = get_missing_parity(code_desc, missing_idxs);
641  selective_encode(code_desc, data, parity, missing_parity, blocksize);
642  free(missing_parity);
643  }
644  break;
645  case FAIL_PATTERN_GE_HD:
646  default:
647  break;
648  }
649 
650  return ret;
651 }
652 
653 xor_code_t* init_xor_hd_code(int k, int m, int hd)
654 {
655  xor_code_t *code_desc = NULL;
656  int is_valid = 0;
657 
658  if (hd == 3) {
659  if (m == 6) {
660  if (k <= 15 && k >= 6) {
661  is_valid = 1;
662  }
663  } else if (m == 5) {
664  if (k <= 10 && k >= 5) {
665  is_valid = 1;
666  }
667  } else if (m == 3 && k == 3) {
668  is_valid = 1;
669  }
670  }
671 
672  if (hd == 4) {
673  if (m == 6) {
674  if (k <= 20 && k >= 6) {
675  is_valid = 1;
676  }
677  } else if (m == 5) {
678  if (k <= 10 && k >= 5) {
679  is_valid = 1;
680  }
681  }
682  }
683 
684  if (is_valid) {
685  code_desc = (xor_code_t*)malloc(sizeof(xor_code_t));
686  code_desc->parity_bms = PARITY_BM_ARY(k, m, hd);
687  code_desc->data_bms = DATA_BM_ARY(k, m, hd);
688  code_desc->k = k;
689  code_desc->m = m;
690  code_desc->hd = hd;
691  code_desc->decode = xor_hd_decode;
692  code_desc->encode = xor_code_encode;
693  code_desc->fragments_needed = xor_hd_fragments_needed;
694  }
695 
696  return code_desc;
697 }
698 
decode_two_data
static int decode_two_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)
Definition: xor_hd_code.c:429
init_xor_hd_code
xor_code_t * init_xor_hd_code(int k, int m, int hd)
Definition: xor_hd_code.c:653
is_data_in_parity
int is_data_in_parity(int data_idx, unsigned int parity_bm)
Definition: xor_code.c:43
decode_one_data
static void decode_one_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)
Definition: xor_hd_code.c:412
get_missing_parity
int * get_missing_parity(xor_code_t *code_desc, int *missing_idxs)
Definition: xor_code.c:208
selective_encode
void selective_encode(xor_code_t *code_desc, char **data, char **parity, int *missing_parity, int blocksize)
Definition: xor_code.c:193
index_of_connected_parity
int index_of_connected_parity(xor_code_t *code_desc, int data_index, int *missing_parity, int *missing_data)
Definition: xor_code.c:328
fragments_needed_two_data
static int fragments_needed_two_data(xor_code_t *code_desc, int *missing_data, int *missing_parity, unsigned int *data_bm, unsigned int *parity_bm)
Definition: xor_hd_code.c:56
xor_hd_fragments_needed
int xor_hd_fragments_needed(xor_code_t *code_desc, int *fragments_to_reconstruct, int *fragments_to_exclude, int *fragments_needed)
Definition: xor_hd_code.c:202
remove_from_missing_list
void remove_from_missing_list(int element, int *missing_list)
Definition: xor_code.c:363
decode_three_data
static int decode_three_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)
Definition: xor_hd_code.c:462
xor_code_encode
void xor_code_encode(xor_code_t *code_desc, char **data, char **parity, int blocksize)
Definition: xor_code.c:180
data_bit_lookup
int data_bit_lookup(xor_code_t *code_desc, int index)
Definition: xor_code.c:58
num_missing_data_in_parity
int num_missing_data_in_parity(xor_code_t *code_desc, int parity_idx, int *missing_data)
Definition: xor_code.c:309
xor_bufs_and_store
void xor_bufs_and_store(char *buf1, char *buf2, int blocksize)
Definition: xor_code.c:141
get_failure_pattern
failure_pattern_t get_failure_pattern(xor_code_t *code_desc, int *missing_idxs)
Definition: xor_code.c:76
fragments_needed_one_data
static int fragments_needed_one_data(xor_code_t *code_desc, int *missing_data, int *missing_parity, unsigned int *data_bm, unsigned int *parity_bm)
Definition: xor_hd_code.c:34
fragments_needed_one_data_local
static int fragments_needed_one_data_local(xor_code_t *code_desc, int fragment_to_reconstruct, int *fragments_to_exclude, unsigned int *data_bm, unsigned int *parity_bm)
Definition: xor_hd_code.c:176
fragments_needed_three_data
static int fragments_needed_three_data(xor_code_t *code_desc, int *missing_data, int *missing_parity, unsigned int *data_bm, unsigned int *parity_bm)
Definition: xor_hd_code.c:91
missing_elements_bm
int missing_elements_bm(xor_code_t *code_desc, int *missing_elements, int(*bit_lookup_func)(xor_code_t *code_desc, int index))
Definition: xor_code.c:63
fast_memcpy
void fast_memcpy(char *dst, char *src, int size)
Definition: xor_code.c:130
xor_hd_decode
int xor_hd_decode(xor_code_t *code_desc, char **data, char **parity, int *missing_idxs, int blocksize, int decode_parity)
Definition: xor_hd_code.c:559
get_missing_data
int * get_missing_data(xor_code_t *code_desc, int *missing_idxs)
Definition: xor_code.c:225