]>
Commit | Line | Data |
---|---|---|
f91f0fd5 TL |
1 | /********************************************************************** |
2 | Copyright(c) 2011-2018 Intel Corporation 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 | |
6 | are met: | |
7 | * Redistributions of source code must retain the above copyright | |
8 | notice, this list of conditions and the following disclaimer. | |
9 | * Redistributions in binary form must reproduce the above copyright | |
10 | notice, this list of conditions and the following disclaimer in | |
11 | the documentation and/or other materials provided with the | |
12 | distribution. | |
13 | * Neither the name of Intel Corporation nor the names of its | |
14 | contributors may be used to endorse or promote products derived | |
15 | from this software without specific prior written permission. | |
16 | ||
17 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
18 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
19 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
20 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
21 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
22 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
23 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
24 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
25 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
26 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
27 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
28 | **********************************************************************/ | |
29 | ||
30 | #include <stdio.h> | |
31 | #include <stdlib.h> | |
32 | #include <string.h> | |
33 | #include <getopt.h> | |
34 | #include "erasure_code.h" // use <isa-l.h> instead when linking against installed | |
35 | #include "test.h" | |
36 | ||
37 | #define MMAX 255 | |
38 | #define KMAX 255 | |
39 | ||
40 | typedef unsigned char u8; | |
41 | int verbose = 0; | |
42 | ||
43 | int usage(void) | |
44 | { | |
45 | fprintf(stderr, | |
46 | "Usage: ec_piggyback_example [options]\n" | |
47 | " -h Help\n" | |
48 | " -k <val> Number of source fragments\n" | |
49 | " -p <val> Number of parity fragments\n" | |
50 | " -l <val> Length of fragments\n" | |
51 | " -e <val> Simulate erasure on frag index val. Zero based. Can be repeated.\n" | |
52 | " -v Verbose\n" | |
53 | " -b Run timed benchmark\n" | |
54 | " -s Toggle use of sparse matrix opt\n" | |
55 | " -r <seed> Pick random (k, p) with seed\n"); | |
56 | exit(0); | |
57 | } | |
58 | ||
59 | // Cauchy-based matrix | |
60 | void gf_gen_full_pb_cauchy_matrix(u8 * a, int m, int k) | |
61 | { | |
62 | int i, j, p = m - k; | |
63 | ||
64 | // Identity matrix in top k x k to indicate a symetric code | |
65 | memset(a, 0, k * m); | |
66 | for (i = 0; i < k; i++) | |
67 | a[k * i + i] = 1; | |
68 | ||
69 | for (i = k; i < (k + p / 2); i++) { | |
70 | for (j = 0; j < k / 2; j++) | |
71 | a[k * i + j] = gf_inv(i ^ j); | |
72 | for (; j < k; j++) | |
73 | a[k * i + j] = 0; | |
74 | } | |
75 | for (; i < m; i++) { | |
76 | for (j = 0; j < k / 2; j++) | |
77 | a[k * i + j] = 0; | |
78 | for (; j < k; j++) | |
79 | a[k * i + j] = gf_inv((i - p / 2) ^ (j - k / 2)); | |
80 | } | |
81 | ||
82 | // Fill in mixture of B parity depending on a few localized A sources | |
83 | int r = 0, c = 0; | |
84 | int repeat_len = k / (p - 2); | |
85 | int parity_rows = p / 2; | |
86 | ||
87 | for (i = 1 + k + parity_rows; i < m; i++, r++) { | |
88 | if (r == (parity_rows - 1) - ((k / 2 % (parity_rows - 1)))) | |
89 | repeat_len++; | |
90 | ||
91 | for (j = 0; j < repeat_len; j++, c++) | |
92 | a[k * i + c] = gf_inv((k + 1) ^ c); | |
93 | } | |
94 | } | |
95 | ||
96 | // Vandermonde based matrix - not recommended due to limits when invertable | |
97 | void gf_gen_full_pb_vand_matrix(u8 * a, int m, int k) | |
98 | { | |
99 | int i, j, p = m - k; | |
100 | unsigned char q, gen = 1; | |
101 | ||
102 | // Identity matrix in top k x k to indicate a symetric code | |
103 | memset(a, 0, k * m); | |
104 | for (i = 0; i < k; i++) | |
105 | a[k * i + i] = 1; | |
106 | ||
107 | for (i = k; i < (k + (p / 2)); i++) { | |
108 | q = 1; | |
109 | for (j = 0; j < k / 2; j++) { | |
110 | a[k * i + j] = q; | |
111 | q = gf_mul(q, gen); | |
112 | } | |
113 | for (; j < k; j++) | |
114 | a[k * i + j] = 0; | |
115 | gen = gf_mul(gen, 2); | |
116 | } | |
117 | gen = 1; | |
118 | for (; i < m; i++) { | |
119 | q = 1; | |
120 | for (j = 0; j < k / 2; j++) { | |
121 | a[k * i + j] = 0; | |
122 | } | |
123 | for (; j < k; j++) { | |
124 | a[k * i + j] = q; | |
125 | q = gf_mul(q, gen); | |
126 | } | |
127 | gen = gf_mul(gen, 2); | |
128 | } | |
129 | ||
130 | // Fill in mixture of B parity depending on a few localized A sources | |
131 | int r = 0, c = 0; | |
132 | int repeat_len = k / (p - 2); | |
133 | int parity_rows = p / 2; | |
134 | ||
135 | for (i = 1 + k + parity_rows; i < m; i++, r++) { | |
136 | if (r == (parity_rows - 1) - ((k / 2 % (parity_rows - 1)))) | |
137 | repeat_len++; | |
138 | ||
139 | for (j = 0; j < repeat_len; j++) | |
140 | a[k * i + c++] = 1; | |
141 | } | |
142 | } | |
143 | ||
144 | void print_matrix(int m, int k, unsigned char *s, const char *msg) | |
145 | { | |
146 | int i, j; | |
147 | ||
148 | printf("%s:\n", msg); | |
149 | for (i = 0; i < m; i++) { | |
150 | printf("%3d- ", i); | |
151 | for (j = 0; j < k; j++) { | |
152 | printf(" %2x", 0xff & s[j + (i * k)]); | |
153 | } | |
154 | printf("\n"); | |
155 | } | |
156 | printf("\n"); | |
157 | } | |
158 | ||
159 | void print_list(int n, unsigned char *s, const char *msg) | |
160 | { | |
161 | int i; | |
162 | if (!verbose) | |
163 | return; | |
164 | ||
165 | printf("%s: ", msg); | |
166 | for (i = 0; i < n; i++) | |
167 | printf(" %d", s[i]); | |
168 | printf("\n"); | |
169 | } | |
170 | ||
171 | static int gf_gen_decode_matrix(u8 * encode_matrix, | |
172 | u8 * decode_matrix, | |
173 | u8 * invert_matrix, | |
174 | u8 * temp_matrix, | |
175 | u8 * decode_index, | |
176 | u8 * frag_err_list, int nerrs, int k, int m); | |
177 | ||
178 | int main(int argc, char *argv[]) | |
179 | { | |
180 | int i, j, m, c, e, ret; | |
181 | int k = 10, p = 4, len = 8 * 1024; // Default params | |
182 | int nerrs = 0; | |
183 | int benchmark = 0; | |
184 | int sparse_matrix_opt = 1; | |
185 | ||
186 | // Fragment buffer pointers | |
187 | u8 *frag_ptrs[MMAX]; | |
188 | u8 *parity_ptrs[KMAX]; | |
189 | u8 *recover_srcs[KMAX]; | |
190 | u8 *recover_outp[KMAX]; | |
191 | u8 frag_err_list[MMAX]; | |
192 | ||
193 | // Coefficient matrices | |
194 | u8 *encode_matrix, *decode_matrix; | |
195 | u8 *invert_matrix, *temp_matrix; | |
196 | u8 *g_tbls; | |
197 | u8 decode_index[MMAX]; | |
198 | ||
199 | if (argc == 1) | |
200 | for (i = 0; i < p; i++) | |
201 | frag_err_list[nerrs++] = rand() % (k + p); | |
202 | ||
203 | while ((c = getopt(argc, argv, "k:p:l:e:r:hvbs")) != -1) { | |
204 | switch (c) { | |
205 | case 'k': | |
206 | k = atoi(optarg); | |
207 | break; | |
208 | case 'p': | |
209 | p = atoi(optarg); | |
210 | break; | |
211 | case 'l': | |
212 | len = atoi(optarg); | |
213 | if (len < 0) | |
214 | usage(); | |
215 | break; | |
216 | case 'e': | |
217 | e = atoi(optarg); | |
218 | frag_err_list[nerrs++] = e; | |
219 | break; | |
220 | case 'r': | |
221 | srand(atoi(optarg)); | |
222 | k = (rand() % MMAX) / 4; | |
223 | k = (k < 2) ? 2 : k; | |
224 | p = (rand() % (MMAX - k)) / 4; | |
225 | p = (p < 2) ? 2 : p; | |
226 | for (i = 0; i < k && nerrs < p; i++) | |
227 | if (rand() & 1) | |
228 | frag_err_list[nerrs++] = i; | |
229 | break; | |
230 | case 'v': | |
231 | verbose++; | |
232 | break; | |
233 | case 'b': | |
234 | benchmark = 1; | |
235 | break; | |
236 | case 's': | |
237 | sparse_matrix_opt = !sparse_matrix_opt; | |
238 | break; | |
239 | case 'h': | |
240 | default: | |
241 | usage(); | |
242 | break; | |
243 | } | |
244 | } | |
245 | m = k + p; | |
246 | ||
247 | // Check for valid parameters | |
248 | if (m > (MMAX / 2) || k > (KMAX / 2) || m < 0 || p < 2 || k < 1) { | |
249 | printf(" Input test parameter error m=%d, k=%d, p=%d, erasures=%d\n", | |
250 | m, k, p, nerrs); | |
251 | usage(); | |
252 | } | |
253 | if (nerrs > p) { | |
254 | printf(" Number of erasures chosen exceeds power of code erasures=%d p=%d\n", | |
255 | nerrs, p); | |
256 | } | |
257 | for (i = 0; i < nerrs; i++) { | |
258 | if (frag_err_list[i] >= m) | |
259 | printf(" fragment %d not in range\n", frag_err_list[i]); | |
260 | } | |
261 | ||
262 | printf("ec_piggyback_example:\n"); | |
263 | ||
264 | /* | |
265 | * One simple way to implement piggyback codes is to keep a 2x wide matrix | |
266 | * that covers the how each parity is related to both A and B sources. This | |
267 | * keeps it easy to generalize in parameters m,k and the resulting sparse | |
268 | * matrix multiplication can be optimized by pre-removal of zero items. | |
269 | */ | |
270 | ||
271 | int k2 = 2 * k; | |
272 | int p2 = 2 * p; | |
273 | int m2 = k2 + p2; | |
274 | int nerrs2 = nerrs; | |
275 | ||
276 | encode_matrix = malloc(m2 * k2); | |
277 | decode_matrix = malloc(m2 * k2); | |
278 | invert_matrix = malloc(m2 * k2); | |
279 | temp_matrix = malloc(m2 * k2); | |
280 | g_tbls = malloc(k2 * p2 * 32); | |
281 | ||
282 | if (encode_matrix == NULL || decode_matrix == NULL | |
283 | || invert_matrix == NULL || temp_matrix == NULL || g_tbls == NULL) { | |
284 | printf("Test failure! Error with malloc\n"); | |
285 | return -1; | |
286 | } | |
287 | // Allocate the src fragments | |
288 | for (i = 0; i < k; i++) { | |
289 | if (NULL == (frag_ptrs[i] = malloc(len))) { | |
290 | printf("alloc error: Fail\n"); | |
291 | return -1; | |
292 | } | |
293 | } | |
294 | // Allocate the parity fragments | |
295 | for (i = 0; i < p2; i++) { | |
296 | if (NULL == (parity_ptrs[i] = malloc(len / 2))) { | |
297 | printf("alloc error: Fail\n"); | |
298 | return -1; | |
299 | } | |
300 | } | |
301 | ||
302 | // Allocate buffers for recovered data | |
303 | for (i = 0; i < p2; i++) { | |
304 | if (NULL == (recover_outp[i] = malloc(len / 2))) { | |
305 | printf("alloc error: Fail\n"); | |
306 | return -1; | |
307 | } | |
308 | } | |
309 | ||
310 | // Fill sources with random data | |
311 | for (i = 0; i < k; i++) | |
312 | for (j = 0; j < len; j++) | |
313 | frag_ptrs[i][j] = rand(); | |
314 | ||
315 | printf(" encode (m,k,p)=(%d,%d,%d) len=%d\n", m, k, p, len); | |
316 | ||
317 | // Pick an encode matrix. | |
318 | gf_gen_full_pb_cauchy_matrix(encode_matrix, m2, k2); | |
319 | ||
320 | if (verbose) | |
321 | print_matrix(m2, k2, encode_matrix, "encode matrix"); | |
322 | ||
323 | // Initialize g_tbls from encode matrix | |
324 | ec_init_tables(k2, p2, &encode_matrix[k2 * k2], g_tbls); | |
325 | ||
326 | // Fold A and B into single list of fragments | |
327 | for (i = 0; i < k; i++) | |
328 | frag_ptrs[i + k] = &frag_ptrs[i][len / 2]; | |
329 | ||
330 | if (!sparse_matrix_opt) { | |
331 | // Standard encode using no assumptions on the encode matrix | |
332 | ||
333 | // Generate EC parity blocks from sources | |
334 | ec_encode_data(len / 2, k2, p2, g_tbls, frag_ptrs, parity_ptrs); | |
335 | ||
336 | if (benchmark) { | |
337 | struct perf start; | |
338 | BENCHMARK(&start, BENCHMARK_TIME, | |
339 | ec_encode_data(len / 2, k2, p2, g_tbls, frag_ptrs, | |
340 | parity_ptrs)); | |
341 | printf("ec_piggyback_encode_std: "); | |
342 | perf_print(start, m2 * len / 2); | |
343 | } | |
344 | } else { | |
345 | // Sparse matrix optimization - use fact that input matrix is sparse | |
346 | ||
347 | // Keep an encode matrix with some zero elements removed | |
348 | u8 *encode_matrix_faster, *g_tbls_faster; | |
349 | encode_matrix_faster = malloc(m * k); | |
350 | g_tbls_faster = malloc(k * p * 32); | |
351 | if (encode_matrix_faster == NULL || g_tbls_faster == NULL) { | |
352 | printf("Test failure! Error with malloc\n"); | |
353 | return -1; | |
354 | } | |
355 | ||
356 | /* | |
357 | * Pack with only the part that we know are non-zero. Alternatively | |
358 | * we could search and keep track of non-zero elements but for | |
359 | * simplicity we just skip the lower quadrant. | |
360 | */ | |
361 | for (i = k, j = k2; i < m; i++, j++) | |
362 | memcpy(&encode_matrix_faster[k * i], &encode_matrix[k2 * j], k); | |
363 | ||
364 | if (verbose) { | |
365 | print_matrix(p, k, &encode_matrix_faster[k * k], | |
366 | "encode via sparse-opt"); | |
367 | print_matrix(p2 / 2, k2, &encode_matrix[(k2 + p2 / 2) * k2], | |
368 | "encode via sparse-opt"); | |
369 | } | |
370 | // Initialize g_tbls from encode matrix | |
371 | ec_init_tables(k, p, &encode_matrix_faster[k * k], g_tbls_faster); | |
372 | ||
373 | // Generate EC parity blocks from sources | |
374 | ec_encode_data(len / 2, k, p, g_tbls_faster, frag_ptrs, parity_ptrs); | |
375 | ec_encode_data(len / 2, k2, p, &g_tbls[k2 * p * 32], frag_ptrs, | |
376 | &parity_ptrs[p]); | |
377 | ||
378 | if (benchmark) { | |
379 | struct perf start; | |
380 | BENCHMARK(&start, BENCHMARK_TIME, | |
381 | ec_encode_data(len / 2, k, p, g_tbls_faster, frag_ptrs, | |
382 | parity_ptrs); | |
383 | ec_encode_data(len / 2, k2, p, &g_tbls[k2 * p * 32], | |
384 | frag_ptrs, &parity_ptrs[p])); | |
385 | printf("ec_piggyback_encode_sparse: "); | |
386 | perf_print(start, m2 * len / 2); | |
387 | } | |
388 | } | |
389 | ||
390 | if (nerrs <= 0) | |
391 | return 0; | |
392 | ||
393 | printf(" recover %d fragments\n", nerrs); | |
394 | ||
395 | // Set frag pointers to correspond to parity | |
396 | for (i = k2; i < m2; i++) | |
397 | frag_ptrs[i] = parity_ptrs[i - k2]; | |
398 | ||
399 | print_list(nerrs2, frag_err_list, " frag err list"); | |
400 | ||
401 | // Find a decode matrix to regenerate all erasures from remaining frags | |
402 | ret = gf_gen_decode_matrix(encode_matrix, decode_matrix, | |
403 | invert_matrix, temp_matrix, decode_index, frag_err_list, | |
404 | nerrs2, k2, m2); | |
405 | ||
406 | if (ret != 0) { | |
407 | printf("Fail on generate decode matrix\n"); | |
408 | return -1; | |
409 | } | |
410 | // Pack recovery array pointers as list of valid fragments | |
411 | for (i = 0; i < k2; i++) | |
412 | if (decode_index[i] < k2) | |
413 | recover_srcs[i] = frag_ptrs[decode_index[i]]; | |
414 | else | |
415 | recover_srcs[i] = parity_ptrs[decode_index[i] - k2]; | |
416 | ||
417 | print_list(k2, decode_index, " decode index"); | |
418 | ||
419 | // Recover data | |
420 | ec_init_tables(k2, nerrs2, decode_matrix, g_tbls); | |
421 | ec_encode_data(len / 2, k2, nerrs2, g_tbls, recover_srcs, recover_outp); | |
422 | ||
423 | if (benchmark) { | |
424 | struct perf start; | |
425 | BENCHMARK(&start, BENCHMARK_TIME, | |
426 | ec_encode_data(len / 2, k2, nerrs2, g_tbls, recover_srcs, | |
427 | recover_outp)); | |
428 | printf("ec_piggyback_decode: "); | |
429 | perf_print(start, (k2 + nerrs2) * len / 2); | |
430 | } | |
431 | // Check that recovered buffers are the same as original | |
432 | printf(" check recovery of block {"); | |
433 | for (i = 0; i < nerrs2; i++) { | |
434 | printf(" %d", frag_err_list[i]); | |
435 | if (memcmp(recover_outp[i], frag_ptrs[frag_err_list[i]], len / 2)) { | |
436 | printf(" Fail erasure recovery %d, frag %d\n", i, frag_err_list[i]); | |
437 | return -1; | |
438 | } | |
439 | } | |
440 | printf(" } done all: Pass\n"); | |
441 | ||
442 | return 0; | |
443 | } | |
444 | ||
445 | // Generate decode matrix from encode matrix and erasure list | |
446 | ||
447 | static int gf_gen_decode_matrix(u8 * encode_matrix, | |
448 | u8 * decode_matrix, | |
449 | u8 * invert_matrix, | |
450 | u8 * temp_matrix, | |
451 | u8 * decode_index, u8 * frag_err_list, int nerrs, int k, int m) | |
452 | { | |
453 | int i, j, p, r; | |
454 | int nsrcerrs = 0; | |
455 | u8 s, *b = temp_matrix; | |
456 | u8 frag_in_err[MMAX]; | |
457 | ||
458 | memset(frag_in_err, 0, sizeof(frag_in_err)); | |
459 | ||
460 | // Order the fragments in erasure for easier sorting | |
461 | for (i = 0; i < nerrs; i++) { | |
462 | if (frag_err_list[i] < k) | |
463 | nsrcerrs++; | |
464 | frag_in_err[frag_err_list[i]] = 1; | |
465 | } | |
466 | ||
467 | // Construct b (matrix that encoded remaining frags) by removing erased rows | |
468 | for (i = 0, r = 0; i < k; i++, r++) { | |
469 | while (frag_in_err[r]) | |
470 | r++; | |
471 | for (j = 0; j < k; j++) | |
472 | b[k * i + j] = encode_matrix[k * r + j]; | |
473 | decode_index[i] = r; | |
474 | } | |
475 | if (verbose > 1) | |
476 | print_matrix(k, k, b, "matrix to invert"); | |
477 | ||
478 | // Invert matrix to get recovery matrix | |
479 | if (gf_invert_matrix(b, invert_matrix, k) < 0) | |
480 | return -1; | |
481 | ||
482 | if (verbose > 2) | |
483 | print_matrix(k, k, invert_matrix, "matrix inverted"); | |
484 | ||
485 | // Get decode matrix with only wanted recovery rows | |
486 | for (i = 0; i < nsrcerrs; i++) { | |
487 | for (j = 0; j < k; j++) { | |
488 | decode_matrix[k * i + j] = invert_matrix[k * frag_err_list[i] + j]; | |
489 | } | |
490 | } | |
491 | ||
492 | // For non-src (parity) erasures need to multiply encode matrix * invert | |
493 | for (p = nsrcerrs; p < nerrs; p++) { | |
494 | for (i = 0; i < k; i++) { | |
495 | s = 0; | |
496 | for (j = 0; j < k; j++) | |
497 | s ^= gf_mul(invert_matrix[j * k + i], | |
498 | encode_matrix[k * frag_err_list[p] + j]); | |
499 | ||
500 | decode_matrix[k * p + i] = s; | |
501 | } | |
502 | } | |
503 | if (verbose > 1) | |
504 | print_matrix(nerrs, k, decode_matrix, "decode matrix"); | |
505 | return 0; | |
506 | } |