liberasurecode  1.6.1
Erasure Code API library
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 
34 const 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 
43 int 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 
48 int 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 
53 int parity_bit_lookup(xor_code_t *code_desc, int index)
54 {
55  return g_bit_lookup[code_desc->k - index];
56 }
57 
58 int data_bit_lookup(xor_code_t *code_desc, int index)
59 {
60  return g_bit_lookup[index];
61 }
62 
63 int 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 
76 failure_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 
130 void 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  */
141 void 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 
180 void 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 
193 void 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 
208 int * 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 
225 int * 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  */
245 void 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 
309 int 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 
328 int 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 
363 void 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
int * get_missing_data(xor_code_t *code_desc, int *missing_idxs)
Definition: xor_code.c:225
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 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
int * get_missing_parity(xor_code_t *code_desc, int *missing_idxs)
Definition: xor_code.c:208
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