26 #include <emmintrin.h>
35 0x10, 0x20, 0x40, 0x80,
36 0x100, 0x200, 0x400, 0x800,
37 0x1000, 0x2000, 0x4000, 0x8000,
38 0x10000, 0x20000, 0x40000, 0x80000,
39 0x100000, 0x200000, 0x400000, 0x800000,
40 0x1000000, 0x2000000, 0x4000000, 0x8000000,
41 0x10000000, 0x20000000, 0x40000000, 0x80000000};
63 int missing_elements_bm(xor_code_t *code_desc,
int *missing_elements,
int (*bit_lookup_func)(xor_code_t *code_desc,
int index))
68 while (missing_elements[i] > -1) {
69 bm |= bit_lookup_func(code_desc, missing_elements[i]);
80 failure_pattern_t pattern = FAIL_PATTERN_0D_0P;
82 while (missing_idxs[i] > -1) {
83 if (num_failures >= code_desc->hd) {
84 pattern = FAIL_PATTERN_GE_HD;
87 case FAIL_PATTERN_0D_0P:
88 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_1D_0P : FAIL_PATTERN_0D_1P;
90 case FAIL_PATTERN_1D_0P:
91 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_2D_0P : FAIL_PATTERN_1D_1P;
93 case FAIL_PATTERN_2D_0P:
94 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_3D_0P : FAIL_PATTERN_2D_1P;
96 case FAIL_PATTERN_3D_0P:
97 pattern = FAIL_PATTERN_GE_HD;
99 case FAIL_PATTERN_1D_1P:
100 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_2D_1P : FAIL_PATTERN_1D_2P;
102 case FAIL_PATTERN_1D_2P:
103 pattern = FAIL_PATTERN_GE_HD;
105 case FAIL_PATTERN_2D_1P:
106 pattern = FAIL_PATTERN_GE_HD;
108 case FAIL_PATTERN_0D_1P:
109 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_1D_1P : FAIL_PATTERN_0D_2P;
111 case FAIL_PATTERN_0D_2P:
112 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_1D_2P : FAIL_PATTERN_0D_3P;
114 case FAIL_PATTERN_0D_3P:
115 pattern = FAIL_PATTERN_GE_HD;
117 case FAIL_PATTERN_GE_HD:
121 if (pattern == FAIL_PATTERN_GE_HD) {
133 memcpy(dst, src, size);
144 int residual_bytes = num_unaligned_end(blocksize);
145 int fast_blocksize = blocksize > residual_bytes ? (blocksize - residual_bytes) : 0;
146 int fast_int_blocksize = fast_blocksize /
sizeof(__m128i);
148 __m128i *_buf1 = (__m128i*)buf1;
149 __m128i *_buf2 = (__m128i*)buf2;
154 for (i=0; i < fast_int_blocksize; i++) {
155 _buf2[i] = _mm_xor_si128(_buf1[i], _buf2[i]);
158 int residual_bytes = num_unaligned_end(blocksize);
159 int fast_blocksize = blocksize > residual_bytes ? (blocksize - residual_bytes) : 0;
160 int fast_int_blocksize = fast_blocksize /
sizeof(
unsigned long);
163 unsigned long*_buf1 = (
unsigned long*)buf1;
164 unsigned long*_buf2 = (
unsigned long*)buf2;
166 for (i=0; i < fast_int_blocksize; i++) {
167 _buf2[i] = _buf1[i] ^ _buf2[i];
174 for (i=fast_blocksize; i < blocksize; i++)
180 void xor_code_encode(xor_code_t *code_desc,
char **data,
char **parity,
int blocksize)
184 for (i=0; i < code_desc->k; i++) {
185 for (j=0; j < code_desc->m; j++) {
193 void selective_encode(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_parity,
int blocksize)
196 for (i=0; i < code_desc->k; i++) {
198 while (missing_parity[j] > -1) {
199 int parity_index = missing_parity[j] - code_desc->k;
210 int *missing_parity = (
int*)malloc(
sizeof(
int)*MAX_PARITY);
213 while (missing_idxs[i] > -1) {
214 if (missing_idxs[i] >= code_desc->k) {
215 missing_parity[j] = missing_idxs[i];
221 missing_parity[j] = -1;
222 return missing_parity;
227 int *missing_data = (
int*)malloc(
sizeof(
int)*MAX_DATA);
230 while (missing_idxs[i] > -1) {
231 if (missing_idxs[i] < code_desc->k) {
232 missing_data[j] = missing_idxs[i];
238 missing_data[j] = -1;
245 void xor_reconstruct_one(xor_code_t *code_desc,
char **data,
char **parity,
int *missing_idxs,
int index_to_reconstruct,
int blocksize)
256 if (index_to_reconstruct < code_desc->k) {
259 if (connected_parity_idx >= 0) {
261 int relative_parity_idx = connected_parity_idx - code_desc->k;
262 int parity_bm = code_desc->parity_bms[relative_parity_idx];
264 fast_memcpy(data[index_to_reconstruct], parity[relative_parity_idx], blocksize);
266 for (i=0; i < code_desc->k; i++) {
267 if (parity_bm & (1 << i)) {
268 if (i != index_to_reconstruct) {
276 code_desc->decode(code_desc, data, parity, missing_idxs, blocksize, 1);
288 if (num_data_missing == 0) {
289 int relative_parity_idx = index_to_reconstruct - code_desc->k;
290 int parity_bm = code_desc->parity_bms[relative_parity_idx];
292 memset(parity[relative_parity_idx], 0, blocksize);
294 for (i=0; i < code_desc->k; i++) {
295 if (parity_bm & (1 << i)) {
302 code_desc->decode(code_desc, data, parity, missing_idxs, blocksize, 1);
306 free(missing_parity);
312 int num_missing_data = 0;
313 int relative_parity_index = parity_idx - code_desc->k;
314 if (missing_data == NULL) {
318 while (missing_data[i] > -1) {
325 return num_missing_data;
330 int parity_index = -1;
333 for (i=0; i < code_desc->m; i++) {
340 if (missing_parity == NULL) {
344 while (missing_parity[j] > -1) {
345 if ((code_desc->k + i) == missing_parity[j]) {
360 return parity_index > -1 ? parity_index + code_desc->k : parity_index;
369 while (missing_list[i] > -1) {
370 if (missing_list[i] == element) {
372 missing_list[i] = -1;
379 for (i=elem_idx;i < num_elems-1;i++) {
380 int tmp = missing_list[i+1];
381 missing_list[i+1] = missing_list[i];
382 missing_list[i] = tmp;