29#include "xor_hd_code_defs.h"
34static int fragments_needed_one_data(xor_code_t *code_desc,
int *missing_data,
int *missing_parity,
unsigned int *data_bm,
unsigned int *parity_bm)
36 int data_index = missing_data[0];
39 if (parity_index < 0) {
44 *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
47 *parity_bm |= (1 << (parity_index-code_desc->k));
48 *data_bm &= ~((
unsigned int)1 << data_index);
56static int fragments_needed_two_data(xor_code_t *code_desc,
int *missing_data,
int *missing_parity,
unsigned int *data_bm,
unsigned int *parity_bm)
59 int data_index = missing_data[0];
63 if (parity_index < 0) {
64 data_index = missing_data[1];
66 if (parity_index < 0) {
71 missing_data[0] = missing_data[1];
76 *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
79 *parity_bm |= (1 << (parity_index-code_desc->k));
83 *data_bm &= ~((
unsigned int)1 << data_index);
91static int fragments_needed_three_data(xor_code_t *code_desc,
int *missing_data,
int *missing_parity,
unsigned int *data_bm,
unsigned int *parity_bm)
94 int parity_index = -1;
96 int tmp_parity_bm = -1;
105 while (missing_data[i] > -1) {
107 if (parity_index > -1) {
108 data_index = missing_data[i];
109 tmp_parity_bm = code_desc->parity_bms[parity_index-code_desc->k];
123 if (parity_index < 0) {
125 for (i=0;i < code_desc->m;i++) {
127 if (num_missing == 2 && contains_2d < 0) {
129 }
else if (num_missing == 3 && contains_3d < 0) {
134 if (contains_2d < 0 || contains_3d < 0) {
139 tmp_parity_bm = code_desc->parity_bms[contains_2d] ^ code_desc->parity_bms[contains_3d];
143 while (missing_data[i] > -1) {
145 data_index = missing_data[i];
151 if (data_index < 0) {
158 if (parity_index > -1) {
160 *parity_bm |= (1 << (parity_index-code_desc->k));
162 *data_bm |= code_desc->parity_bms[parity_index-code_desc->k];
165 *parity_bm |= (1 << (contains_2d-code_desc->k));
166 *parity_bm |= (1 << (contains_3d-code_desc->k));
168 *data_bm |= tmp_parity_bm;
173 *data_bm &= ~((
unsigned int)1 << data_index);
179 int fragment_to_reconstruct,
180 int *fragments_to_exclude,
181 unsigned int *data_bm,
182 unsigned int *parity_bm)
188 free(missing_parity);
190 if (parity_index < 0) {
195 *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
198 *parity_bm |= (1 << (parity_index-code_desc->k));
199 *data_bm &= ~((
unsigned int)1 << fragment_to_reconstruct);
204int xor_hd_fragments_needed(xor_code_t *code_desc,
int *fragments_to_reconstruct,
int *fragments_to_exclude,
int *fragments_needed)
207 unsigned int data_bm = 0, parity_bm = 0;
209 int *missing_idxs = NULL;
220 if (pattern == FAIL_PATTERN_1D_0P) {
233 missing_idxs = (
int*)malloc(
sizeof(
int)*(code_desc->k + code_desc->m));
234 if (NULL == missing_idxs) {
241 while (fragments_to_reconstruct[i] > -1) {
242 missing_idxs[j] = fragments_to_reconstruct[i];
247 while (fragments_to_exclude[i] > -1) {
248 missing_idxs[j] = fragments_to_exclude[i];
253 missing_idxs[j] = -1;
258 case FAIL_PATTERN_0D_0P:
260 case FAIL_PATTERN_1D_0P:
267 case FAIL_PATTERN_2D_0P:
274 case FAIL_PATTERN_3D_0P:
281 case FAIL_PATTERN_1D_1P:
289 while (missing_parity[i] > -1) {
290 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
291 data_bm &= ~(missing_data_bm);
294 free(missing_parity);
298 case FAIL_PATTERN_1D_2P:
306 while (missing_parity[i] > -1) {
307 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
308 data_bm &= ~(missing_data_bm);
311 free(missing_parity);
315 case FAIL_PATTERN_2D_1P:
323 while (missing_parity[i] > -1) {
324 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
325 data_bm &= ~(missing_data_bm);
328 free(missing_parity);
332 case FAIL_PATTERN_0D_1P:
337 while (missing_parity[i] > -1) {
338 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
341 free(missing_parity);
345 case FAIL_PATTERN_0D_2P:
350 while (missing_parity[i] > -1) {
351 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
354 free(missing_parity);
358 case FAIL_PATTERN_0D_3P:
363 while (missing_parity[i] > -1) {
364 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
367 free(missing_parity);
371 case FAIL_PATTERN_GE_HD:
382 fragments_needed[j] = i;
392 fragments_needed[j] = i + code_desc->k;
399 fragments_needed[j] = -1;
403 if (NULL != missing_idxs) {
414static void decode_one_data(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_data,
int *missing_parity,
int blocksize)
417 int data_index = missing_data[0];
422 fast_memcpy(data[data_index], parity[parity_index-code_desc->k], blocksize);
424 for (i=0; i < code_desc->k; i++) {
425 if (i != data_index &&
is_data_in_parity(i, code_desc->parity_bms[parity_index-code_desc->k])) {
431static int decode_two_data(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_data,
int *missing_parity,
int blocksize)
434 int data_index = missing_data[0];
438 if (parity_index < 0) {
439 data_index = missing_data[1];
441 if (parity_index < 0) {
442 fprintf(stderr,
"Shit is broken, cannot find a proper parity!!!\n");
445 missing_data[1] = -1;
447 missing_data[0] = missing_data[1];
448 missing_data[1] = -1;
452 fast_memcpy(data[data_index], parity[parity_index-code_desc->k], blocksize);
454 for (i=0; i < code_desc->k; i++) {
455 if (i != data_index &&
is_data_in_parity(i, code_desc->parity_bms[parity_index-code_desc->k])) {
459 decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
464static int decode_three_data(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_data,
int *missing_parity,
int blocksize)
467 int parity_index = -1;
469 unsigned int parity_bm = -1;
470 char *parity_buffer = NULL;
476 while (missing_data[i] > -1) {
478 if (parity_index > -1) {
479 data_index = missing_data[i];
480 parity_buffer = parity[parity_index-code_desc->k];
481 parity_bm = code_desc->parity_bms[parity_index-code_desc->k];
496 if (parity_index < 0) {
497 int contains_2d = -1;
498 int contains_3d = -1;
500 for (i=0;i < code_desc->m;i++) {
502 if (num_missing == 2 && contains_2d < 0) {
504 }
else if (num_missing == 3 && contains_3d < 0) {
509 if (contains_2d < 0 || contains_3d < 0) {
510 fprintf(stderr,
"Shit is broken, cannot find a proper parity (2 and 3-connected parities)!!!\n");
514 if (posix_memalign((
void **) &parity_buffer, 16, blocksize) != 0) {
515 fprintf(stderr,
"Can't get aligned memory!\n");
520 parity_bm = code_desc->parity_bms[contains_2d] ^ code_desc->parity_bms[contains_3d];
523 fast_memcpy(parity_buffer, parity[contains_2d], blocksize);
528 while (missing_data[i] > -1) {
530 data_index = missing_data[i];
536 if (data_index < 0) {
537 fprintf(stderr,
"Shit is broken, cannot construct equations to repair 3 failures!!!\n");
541 fast_memcpy(data[data_index], parity_buffer, blocksize);
546 fast_memcpy(data[data_index], parity_buffer, blocksize);
550 for (i=0; i < code_desc->k; i++) {
558 return decode_two_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
561int xor_hd_decode(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_idxs,
int blocksize,
int decode_parity)
567 case FAIL_PATTERN_0D_0P:
569 case FAIL_PATTERN_1D_0P:
572 decode_one_data(code_desc, data, parity, missing_data, NULL, blocksize);
576 case FAIL_PATTERN_2D_0P:
579 ret =
decode_two_data(code_desc, data, parity, missing_data, NULL, blocksize);
583 case FAIL_PATTERN_3D_0P:
590 case FAIL_PATTERN_1D_1P:
594 decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
598 free(missing_parity);
602 case FAIL_PATTERN_1D_2P:
606 decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
611 free(missing_parity);
614 case FAIL_PATTERN_2D_1P:
618 ret =
decode_two_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
622 free(missing_parity);
626 case FAIL_PATTERN_0D_1P:
630 free(missing_parity);
633 case FAIL_PATTERN_0D_2P:
637 free(missing_parity);
640 case FAIL_PATTERN_0D_3P:
644 free(missing_parity);
647 case FAIL_PATTERN_GE_HD:
657 xor_code_t *code_desc = NULL;
662 if (k <= 15 && k >= 6) {
666 if (k <= 10 && k >= 5) {
669 }
else if (m == 3 && k == 3) {
676 if (k <= 20 && k >= 6) {
680 if (k <= 10 && k >= 5) {
687 code_desc = (xor_code_t*)malloc(
sizeof(xor_code_t));
688 code_desc->parity_bms = PARITY_BM_ARY(k, m, hd);
689 code_desc->data_bms = DATA_BM_ARY(k, m, hd);
void selective_encode(xor_code_t *code_desc, char **data, char **parity, int *missing_parity, int blocksize)
int is_data_in_parity(int data_idx, unsigned int parity_bm)
int data_bit_lookup(xor_code_t *code_desc, int index)
void remove_from_missing_list(int element, int *missing_list)
void xor_bufs_and_store(char *buf1, char *buf2, int blocksize)
int missing_elements_bm(xor_code_t *code_desc, int *missing_elements, int(*bit_lookup_func)(xor_code_t *code_desc, int index))
int index_of_connected_parity(xor_code_t *code_desc, int data_index, int *missing_parity, int *missing_data)
int * get_missing_parity(xor_code_t *code_desc, int *missing_idxs)
int * get_missing_data(xor_code_t *code_desc, int *missing_idxs)
int num_missing_data_in_parity(xor_code_t *code_desc, int parity_idx, int *missing_data)
failure_pattern_t get_failure_pattern(xor_code_t *code_desc, int *missing_idxs)
void fast_memcpy(char *dst, char *src, int size)
void xor_code_encode(xor_code_t *code_desc, char **data, char **parity, int blocksize)
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)
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)
xor_code_t * init_xor_hd_code(int k, int m, int hd)
static int decode_two_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)
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)
int xor_hd_fragments_needed(xor_code_t *code_desc, int *fragments_to_reconstruct, int *fragments_to_exclude, int *fragments_needed)
static void decode_one_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)
int xor_hd_decode(xor_code_t *code_desc, char **data, char **parity, int *missing_idxs, int blocksize, int decode_parity)
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)
static int decode_three_data(xor_code_t *code_desc, char **data, char **parity, int *missing_data, int *missing_parity, int blocksize)