liberasurecode 1.6.3
Erasure Code API library
Loading...
Searching...
No Matches
xor_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#ifdef INTEL_SSE2
26#include <emmintrin.h> //SSE2
27#endif
28#include <stdio.h>
29#include <stdlib.h>
30#include <string.h>
31#include <time.h>
32#include "xor_code.h"
33
34const int g_bit_lookup[] = {0x1, 0x2, 0x4, 0x8,
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};
42
43int is_data_in_parity(int data_idx, unsigned int parity_bm)
44{
45 return ((g_bit_lookup[data_idx] & parity_bm) == g_bit_lookup[data_idx]);
46}
47
48int does_parity_have_data(int parity_idx, unsigned int data_bm)
49{
50 return ((g_bit_lookup[parity_idx] & data_bm) == g_bit_lookup[parity_idx]);
51}
52
53int parity_bit_lookup(xor_code_t *code_desc, int index)
54{
55 return g_bit_lookup[code_desc->k - index];
56}
57
58int data_bit_lookup(xor_code_t *code_desc, int index)
59{
60 return g_bit_lookup[index];
61}
62
63int missing_elements_bm(xor_code_t *code_desc, int *missing_elements, int (*bit_lookup_func)(xor_code_t *code_desc, int index))
64{
65 int i = 0;
66 int bm = 0;
67
68 while (missing_elements[i] > -1) {
69 bm |= bit_lookup_func(code_desc, missing_elements[i]);
70 i++;
71 }
72
73 return bm;
74}
75
76failure_pattern_t get_failure_pattern(xor_code_t *code_desc, int *missing_idxs)
77{
78 int i = 0;
79 int num_failures = 0;
80 failure_pattern_t pattern = FAIL_PATTERN_0D_0P;
81
82 while (missing_idxs[i] > -1) {
83 if (num_failures >= code_desc->hd) {
84 pattern = FAIL_PATTERN_GE_HD;
85 }
86 switch(pattern) {
87 case FAIL_PATTERN_0D_0P:
88 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_1D_0P : FAIL_PATTERN_0D_1P;
89 break;
90 case FAIL_PATTERN_1D_0P:
91 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_2D_0P : FAIL_PATTERN_1D_1P;
92 break;
93 case FAIL_PATTERN_2D_0P:
94 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_3D_0P : FAIL_PATTERN_2D_1P;
95 break;
96 case FAIL_PATTERN_3D_0P:
97 pattern = FAIL_PATTERN_GE_HD;
98 break;
99 case FAIL_PATTERN_1D_1P:
100 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_2D_1P : FAIL_PATTERN_1D_2P;
101 break;
102 case FAIL_PATTERN_1D_2P:
103 pattern = FAIL_PATTERN_GE_HD;
104 break;
105 case FAIL_PATTERN_2D_1P:
106 pattern = FAIL_PATTERN_GE_HD;
107 break;
108 case FAIL_PATTERN_0D_1P:
109 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_1D_1P : FAIL_PATTERN_0D_2P;
110 break;
111 case FAIL_PATTERN_0D_2P:
112 pattern = (missing_idxs[i] < code_desc->k) ? FAIL_PATTERN_1D_2P : FAIL_PATTERN_0D_3P;
113 break;
114 case FAIL_PATTERN_0D_3P:
115 pattern = FAIL_PATTERN_GE_HD;
116 break;
117 case FAIL_PATTERN_GE_HD:
118 default:
119 break;
120 }
121 if (pattern == FAIL_PATTERN_GE_HD) {
122 break;
123 }
124 i++;
125 }
126
127 return pattern;
128}
129
130void fast_memcpy(char *dst, char *src, int size)
131{
132 // Use _mm_stream_si128((__m128i*) _buf2, sum);
133 memcpy(dst, src, size);
134}
135
136/*
137 * Buffers must be aligned to 16-byte boundaries
138 *
139 * Store in buf2 (opposite of memcpy convention... Maybe change?)
140 */
141void xor_bufs_and_store(char *buf1, char *buf2, int blocksize)
142{
143#ifdef INTEL_SSE2
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);
147 int i;
148 __m128i *_buf1 = (__m128i*)buf1;
149 __m128i *_buf2 = (__m128i*)buf2;
150
151 /*
152 * XOR aligned region using 128-bit XOR
153 */
154 for (i=0; i < fast_int_blocksize; i++) {
155 _buf2[i] = _mm_xor_si128(_buf1[i], _buf2[i]);
156 }
157#else
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);
161 int i;
162
163 unsigned long*_buf1 = (unsigned long*)buf1;
164 unsigned long*_buf2 = (unsigned long*)buf2;
165
166 for (i=0; i < fast_int_blocksize; i++) {
167 _buf2[i] = _buf1[i] ^ _buf2[i];
168 }
169#endif
170
171 /*
172 * XOR unaligned end of region
173 */
174 for (i=fast_blocksize; i < blocksize; i++)
175 {
176 buf2[i] ^= buf1[i];
177 }
178}
179
180void xor_code_encode(xor_code_t *code_desc, char **data, char **parity, int blocksize)
181{
182 int i, j;
183
184 for (i=0; i < code_desc->k; i++) {
185 for (j=0; j < code_desc->m; j++) {
186 if (is_data_in_parity(i, code_desc->parity_bms[j])) {
187 xor_bufs_and_store(data[i], parity[j], blocksize);
188 }
189 }
190 }
191}
192
193void selective_encode(xor_code_t *code_desc, char **data, char **parity, int *missing_parity, int blocksize)
194{
195 int i;
196 for (i=0; i < code_desc->k; i++) {
197 int j=0;
198 while (missing_parity[j] > -1) {
199 int parity_index = missing_parity[j] - code_desc->k;
200 if (is_data_in_parity(i, code_desc->parity_bms[parity_index])) {
201 xor_bufs_and_store(data[i], parity[parity_index], blocksize);
202 }
203 j++;
204 }
205 }
206}
207
208int * get_missing_parity(xor_code_t *code_desc, int *missing_idxs)
209{
210 int *missing_parity = (int*)malloc(sizeof(int)*MAX_PARITY);
211 int i = 0, j = 0;
212
213 while (missing_idxs[i] > -1) {
214 if (missing_idxs[i] >= code_desc->k) {
215 missing_parity[j] = missing_idxs[i];
216 j++;
217 }
218 i++;
219 }
220
221 missing_parity[j] = -1;
222 return missing_parity;
223}
224
225int * get_missing_data(xor_code_t *code_desc, int *missing_idxs)
226{
227 int *missing_data = (int*)malloc(sizeof(int)*MAX_DATA);
228 int i = 0, j = 0;
229
230 while (missing_idxs[i] > -1) {
231 if (missing_idxs[i] < code_desc->k) {
232 missing_data[j] = missing_idxs[i];
233 j++;
234 }
235 i++;
236 }
237
238 missing_data[j] = -1;
239 return missing_data;
240}
241
242/*
243 * Reconstruct a single missing symbol, given other symbols may be missing
244 */
245void xor_reconstruct_one(xor_code_t *code_desc, char **data, char **parity, int *missing_idxs, int index_to_reconstruct, int blocksize)
246{
247 int *missing_data = get_missing_data(code_desc, missing_idxs);
248 int *missing_parity = get_missing_parity(code_desc, missing_idxs);
249 int i;
250
251 // If it is a data symbol, we need to figure out
252 // what data+parity symbols are needed to reconstruct
253 // If there is not at least one parity equation with
254 // one missing data element (the index to resonstruct),
255 // just call the underlying decode function
256 if (index_to_reconstruct < code_desc->k) {
257 int connected_parity_idx = index_of_connected_parity(code_desc, index_to_reconstruct, missing_parity, missing_data);
258
259 if (connected_parity_idx >= 0) {
260 // Can do a cheap reoncstruction!
261 int relative_parity_idx = connected_parity_idx - code_desc->k;
262 int parity_bm = code_desc->parity_bms[relative_parity_idx];
263
264 fast_memcpy(data[index_to_reconstruct], parity[relative_parity_idx], blocksize);
265
266 for (i=0; i < code_desc->k; i++) {
267 if (parity_bm & (1 << i)) {
268 if (i != index_to_reconstruct) {
269 xor_bufs_and_store(data[i], data[index_to_reconstruct], blocksize);
270 }
271 }
272 }
273
274 } else {
275 // Just call decode
276 code_desc->decode(code_desc, data, parity, missing_idxs, blocksize, 1);
277 }
278
279 } else {
280
281 // If it is a parity symbol, we need to figure out
282 // what data symbols are needed to reconstruct the
283 // parity. If *any* data symbols in the parity
284 // equation are missing, we are better off calling
285 // the underlying decode function.
286 int num_data_missing = num_missing_data_in_parity(code_desc, index_to_reconstruct, missing_data);
287
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];
291
292 memset(parity[relative_parity_idx], 0, blocksize);
293
294 for (i=0; i < code_desc->k; i++) {
295 if (parity_bm & (1 << i)) {
296 xor_bufs_and_store(data[i], parity[relative_parity_idx], blocksize);
297 }
298 }
299
300 } else {
301 // Just call decode
302 code_desc->decode(code_desc, data, parity, missing_idxs, blocksize, 1);
303 }
304 }
305 free(missing_data);
306 free(missing_parity);
307}
308
309int num_missing_data_in_parity(xor_code_t *code_desc, int parity_idx, int *missing_data)
310{
311 int i = 0;
312 int num_missing_data = 0;
313 int relative_parity_index = parity_idx - code_desc->k;
314 if (missing_data == NULL) {
315 return 0;
316 }
317
318 while (missing_data[i] > -1) {
319 if (does_parity_have_data(relative_parity_index, code_desc->data_bms[missing_data[i]]) > 0) {
320 num_missing_data++;
321 }
322 i++;
323 }
324
325 return num_missing_data;
326}
327
328int index_of_connected_parity(xor_code_t *code_desc, int data_index, int *missing_parity, int *missing_data)
329{
330 int parity_index = -1;
331 int i;
332
333 for (i=0; i < code_desc->m; i++) {
334 if (num_missing_data_in_parity(code_desc, i + code_desc->k, missing_data) > 1) {
335 continue;
336 }
337 if (is_data_in_parity(data_index, code_desc->parity_bms[i])) {
338 int j=0;
339 int is_missing = 0;
340 if (missing_parity == NULL) {
341 parity_index = i;
342 break;
343 }
344 while (missing_parity[j] > -1) {
345 if ((code_desc->k + i) == missing_parity[j]) {
346 is_missing = 1;
347 break;
348 }
349 j++;
350 }
351 if (!is_missing) {
352 parity_index = i;
353 break;
354 }
355 }
356 }
357
358 // Must add k to get the absolute
359 // index of the parity in the stripe
360 return parity_index > -1 ? parity_index + code_desc->k : parity_index;
361}
362
363void remove_from_missing_list(int element, int *missing_list)
364{
365 int i = 0;
366 int elem_idx = -1;
367 int num_elems = 0;
368
369 while (missing_list[i] > -1) {
370 if (missing_list[i] == element) {
371 elem_idx = i;
372 missing_list[i] = -1;
373 }
374 i++;
375 }
376
377 num_elems = i;
378
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;
383 }
384}
385
int is_missing(int *missing_idxs, int index_to_check)
void selective_encode(xor_code_t *code_desc, char **data, char **parity, int *missing_parity, int blocksize)
Definition xor_code.c:193
void xor_reconstruct_one(xor_code_t *code_desc, char **data, char **parity, int *missing_idxs, int index_to_reconstruct, int blocksize)
Definition xor_code.c:245
int is_data_in_parity(int data_idx, unsigned int parity_bm)
Definition xor_code.c:43
int data_bit_lookup(xor_code_t *code_desc, int index)
Definition xor_code.c:58
const int g_bit_lookup[]
Definition xor_code.c:34
int does_parity_have_data(int parity_idx, unsigned int data_bm)
Definition xor_code.c:48
void remove_from_missing_list(int element, int *missing_list)
Definition xor_code.c:363
void xor_bufs_and_store(char *buf1, char *buf2, int blocksize)
Definition xor_code.c:141
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
int index_of_connected_parity(xor_code_t *code_desc, int data_index, int *missing_parity, int *missing_data)
Definition xor_code.c:328
int * get_missing_parity(xor_code_t *code_desc, int *missing_idxs)
Definition xor_code.c:208
int * get_missing_data(xor_code_t *code_desc, int *missing_idxs)
Definition xor_code.c:225
int num_missing_data_in_parity(xor_code_t *code_desc, int parity_idx, int *missing_data)
Definition xor_code.c:309
failure_pattern_t get_failure_pattern(xor_code_t *code_desc, int *missing_idxs)
Definition xor_code.c:76
void fast_memcpy(char *dst, char *src, int size)
Definition xor_code.c:130
int parity_bit_lookup(xor_code_t *code_desc, int index)
Definition xor_code.c:53
void xor_code_encode(xor_code_t *code_desc, char **data, char **parity, int blocksize)
Definition xor_code.c:180