29 #include "xor_hd_code_defs.h"
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)
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);
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)
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);
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)
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) {
159 *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
162 if (parity_index > -1) {
163 *parity_bm |= (1 << (parity_index-code_desc->k));
165 *parity_bm |= (1 << (contains_2d-code_desc->k));
166 *parity_bm |= (1 << (contains_3d-code_desc->k));
171 *data_bm &= ~((
unsigned int)1 << data_index);
177 int fragment_to_reconstruct,
178 int *fragments_to_exclude,
179 unsigned int *data_bm,
180 unsigned int *parity_bm)
186 free(missing_parity);
188 if (parity_index < 0) {
193 *data_bm |= (code_desc->parity_bms[parity_index-code_desc->k]);
196 *parity_bm |= (1 << (parity_index-code_desc->k));
197 *data_bm &= ~((
unsigned int)1 << fragment_to_reconstruct);
202 int xor_hd_fragments_needed(xor_code_t *code_desc,
int *fragments_to_reconstruct,
int *fragments_to_exclude,
int *fragments_needed)
205 unsigned int data_bm = 0, parity_bm = 0;
207 int *missing_idxs = NULL;
218 if (pattern == FAIL_PATTERN_1D_0P) {
231 missing_idxs = (
int*)malloc(
sizeof(
int)*(code_desc->k + code_desc->m));
232 if (NULL == missing_idxs) {
239 while (fragments_to_reconstruct[i] > -1) {
240 missing_idxs[j] = fragments_to_reconstruct[i];
245 while (fragments_to_exclude[i] > -1) {
246 missing_idxs[j] = fragments_to_exclude[i];
251 missing_idxs[j] = -1;
256 case FAIL_PATTERN_0D_0P:
258 case FAIL_PATTERN_1D_0P:
265 case FAIL_PATTERN_2D_0P:
272 case FAIL_PATTERN_3D_0P:
279 case FAIL_PATTERN_1D_1P:
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);
292 free(missing_parity);
296 case FAIL_PATTERN_1D_2P:
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);
309 free(missing_parity);
313 case FAIL_PATTERN_2D_1P:
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);
326 free(missing_parity);
330 case FAIL_PATTERN_0D_1P:
335 while (missing_parity[i] > -1) {
336 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
339 free(missing_parity);
343 case FAIL_PATTERN_0D_2P:
348 while (missing_parity[i] > -1) {
349 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
352 free(missing_parity);
356 case FAIL_PATTERN_0D_3P:
361 while (missing_parity[i] > -1) {
362 data_bm |= code_desc->parity_bms[missing_parity[i]-code_desc->k];
365 free(missing_parity);
369 case FAIL_PATTERN_GE_HD:
380 fragments_needed[j] = i;
390 fragments_needed[j] = i + code_desc->k;
397 fragments_needed[j] = -1;
401 if (NULL != missing_idxs) {
412 static void decode_one_data(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_data,
int *missing_parity,
int blocksize)
415 int data_index = missing_data[0];
420 fast_memcpy(data[data_index], parity[parity_index-code_desc->k], blocksize);
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])) {
429 static int decode_two_data(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_data,
int *missing_parity,
int blocksize)
432 int data_index = missing_data[0];
436 if (parity_index < 0) {
437 data_index = missing_data[1];
439 if (parity_index < 0) {
440 fprintf(stderr,
"Shit is broken, cannot find a proper parity!!!\n");
443 missing_data[1] = -1;
445 missing_data[0] = missing_data[1];
446 missing_data[1] = -1;
450 fast_memcpy(data[data_index], parity[parity_index-code_desc->k], blocksize);
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])) {
457 decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
462 static int decode_three_data(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_data,
int *missing_parity,
int blocksize)
465 int parity_index = -1;
467 unsigned int parity_bm = -1;
468 char *parity_buffer = NULL;
474 while (missing_data[i] > -1) {
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];
494 if (parity_index < 0) {
495 int contains_2d = -1;
496 int contains_3d = -1;
498 for (i=0;i < code_desc->m;i++) {
500 if (num_missing == 2 && contains_2d < 0) {
502 }
else if (num_missing == 3 && contains_3d < 0) {
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");
512 if (posix_memalign((
void **) &parity_buffer, 16, blocksize) != 0) {
513 fprintf(stderr,
"Can't get aligned memory!\n");
518 parity_bm = code_desc->parity_bms[contains_2d] ^ code_desc->parity_bms[contains_3d];
521 fast_memcpy(parity_buffer, parity[contains_2d], blocksize);
526 while (missing_data[i] > -1) {
528 data_index = missing_data[i];
534 if (data_index < 0) {
535 fprintf(stderr,
"Shit is broken, cannot construct equations to repair 3 failures!!!\n");
539 fast_memcpy(data[data_index], parity_buffer, blocksize);
544 fast_memcpy(data[data_index], parity_buffer, blocksize);
548 for (i=0; i < code_desc->k; i++) {
556 return decode_two_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
559 int xor_hd_decode(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_idxs,
int blocksize,
int decode_parity)
565 case FAIL_PATTERN_0D_0P:
567 case FAIL_PATTERN_1D_0P:
570 decode_one_data(code_desc, data, parity, missing_data, NULL, blocksize);
574 case FAIL_PATTERN_2D_0P:
577 ret =
decode_two_data(code_desc, data, parity, missing_data, NULL, blocksize);
581 case FAIL_PATTERN_3D_0P:
588 case FAIL_PATTERN_1D_1P:
592 decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
596 free(missing_parity);
600 case FAIL_PATTERN_1D_2P:
604 decode_one_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
609 free(missing_parity);
612 case FAIL_PATTERN_2D_1P:
616 ret =
decode_two_data(code_desc, data, parity, missing_data, missing_parity, blocksize);
620 free(missing_parity);
624 case FAIL_PATTERN_0D_1P:
628 free(missing_parity);
631 case FAIL_PATTERN_0D_2P:
635 free(missing_parity);
638 case FAIL_PATTERN_0D_3P:
642 free(missing_parity);
645 case FAIL_PATTERN_GE_HD:
655 xor_code_t *code_desc = NULL;
660 if (k <= 15 && k >= 6) {
664 if (k <= 10 && k >= 5) {
667 }
else if (m == 3 && k == 3) {
674 if (k <= 20 && k >= 6) {
678 if (k <= 10 && k >= 5) {
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);
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)
int * get_missing_data(xor_code_t *code_desc, int *missing_idxs)
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 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)
int * get_missing_parity(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)