1 /**********************************************************************
2 Copyright(c) 2011-2015 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> // for memset, memcmp
33 #include <assert.h>
34 #include "erasure_code.h"
35 #include "test.h"
36
37 #define TEST_LEN 8192
38 #define TEST_SIZE (TEST_LEN / 2)
39
40 #ifndef TEST_SOURCES
41 #define TEST_SOURCES 127
42 #endif
43 #ifndef RANDOMS
44 #define RANDOMS 200
45 #endif
46
47 #define MMAX TEST_SOURCES
48 #define KMAX TEST_SOURCES
49
50 #define EFENCE_TEST_MIN_SIZE 16
51 #define EFENCE_TEST_MAX_SIZE EFENCE_TEST_MIN_SIZE + 0x100
52
53 #ifdef EC_ALIGNED_ADDR
54 // Define power of 2 range to check ptr, len alignment
55 #define PTR_ALIGN_CHK_B 0
56 #define LEN_ALIGN_CHK_B 0 // 0 for aligned only
57 #else
58 // Define power of 2 range to check ptr, len alignment
59 #define PTR_ALIGN_CHK_B 32
60 #define LEN_ALIGN_CHK_B 32 // 0 for aligned only
61 #endif
62
63 #ifndef TEST_SEED
64 #define TEST_SEED 11
65 #endif
66
67 typedef unsigned char u8;
68
69 void
dump(unsigned char * buf,int len)70 dump(unsigned char *buf, int len)
71 {
72 int i;
73 for (i = 0; i < len;) {
74 printf(" %2x", 0xff & buf[i++]);
75 if (i % 32 == 0)
76 printf("\n");
77 }
78 printf("\n");
79 }
80
81 void
dump_matrix(unsigned char ** s,int k,int m)82 dump_matrix(unsigned char **s, int k, int m)
83 {
84 int i, j;
85 for (i = 0; i < k; i++) {
86 for (j = 0; j < m; j++) {
87 printf(" %2x", s[i][j]);
88 }
89 printf("\n");
90 }
91 printf("\n");
92 }
93
94 void
dump_u8xu8(unsigned char * s,int k,int m)95 dump_u8xu8(unsigned char *s, int k, int m)
96 {
97 int i, j;
98 for (i = 0; i < k; i++) {
99 for (j = 0; j < m; j++) {
100 printf(" %2x", 0xff & s[j + (i * m)]);
101 }
102 printf("\n");
103 }
104 printf("\n");
105 }
106
107 // Generate Random errors
108 static void
gen_err_list(unsigned char * src_err_list,unsigned char * src_in_err,int * pnerrs,int * pnsrcerrs,int k,int m)109 gen_err_list(unsigned char *src_err_list, unsigned char *src_in_err, int *pnerrs, int *pnsrcerrs,
110 int k, int m)
111 {
112 int i, err;
113 int nerrs = 0, nsrcerrs = 0;
114
115 for (i = 0, nerrs = 0, nsrcerrs = 0; i < m && nerrs < m - k; i++) {
116 err = 1 & rand();
117 src_in_err[i] = err;
118 if (err) {
119 src_err_list[nerrs++] = i;
120 if (i < k) {
121 nsrcerrs++;
122 }
123 }
124 }
125 if (nerrs == 0) { // should have at least one error
126 while ((err = (rand() % KMAX)) >= m)
127 ;
128 src_err_list[nerrs++] = err;
129 src_in_err[err] = 1;
130 if (err < k)
131 nsrcerrs = 1;
132 }
133 *pnerrs = nerrs;
134 *pnsrcerrs = nsrcerrs;
135 return;
136 }
137
138 #define NO_INVERT_MATRIX -2
139 // Generate decode matrix from encode matrix
140 static int
gf_gen_decode_matrix(unsigned char * encode_matrix,unsigned char * decode_matrix,unsigned char * invert_matrix,unsigned int * decode_index,unsigned char * src_err_list,unsigned char * src_in_err,int nerrs,int nsrcerrs,int k,int m)141 gf_gen_decode_matrix(unsigned char *encode_matrix, unsigned char *decode_matrix,
142 unsigned char *invert_matrix, unsigned int *decode_index,
143 unsigned char *src_err_list, unsigned char *src_in_err, int nerrs,
144 int nsrcerrs, int k, int m)
145 {
146 int i, j, p;
147 int r;
148 unsigned char *backup, *b, s;
149 int incr = 0;
150
151 b = malloc(MMAX * KMAX);
152 backup = malloc(MMAX * KMAX);
153
154 if (b == NULL || backup == NULL) {
155 printf("Test failure! Error with malloc\n");
156 free(b);
157 free(backup);
158 return -1;
159 }
160 // Construct matrix b by removing error rows
161 for (i = 0, r = 0; i < k; i++, r++) {
162 while (src_in_err[r])
163 r++;
164 for (j = 0; j < k; j++) {
165 b[k * i + j] = encode_matrix[k * r + j];
166 backup[k * i + j] = encode_matrix[k * r + j];
167 }
168 decode_index[i] = r;
169 }
170 incr = 0;
171 while (gf_invert_matrix(b, invert_matrix, k) < 0) {
172 if (nerrs == (m - k)) {
173 free(b);
174 free(backup);
175 printf("BAD MATRIX\n");
176 return NO_INVERT_MATRIX;
177 }
178 incr++;
179 memcpy(b, backup, MMAX * KMAX);
180 for (i = nsrcerrs; i < nerrs - nsrcerrs; i++) {
181 if (src_err_list[i] == (decode_index[k - 1] + incr)) {
182 // skip the erased parity line
183 incr++;
184 continue;
185 }
186 }
187 if (decode_index[k - 1] + incr >= m) {
188 free(b);
189 free(backup);
190 printf("BAD MATRIX\n");
191 return NO_INVERT_MATRIX;
192 }
193 decode_index[k - 1] += incr;
194 for (j = 0; j < k; j++)
195 b[k * (k - 1) + j] = encode_matrix[k * decode_index[k - 1] + j];
196 };
197
198 for (i = 0; i < nsrcerrs; i++) {
199 for (j = 0; j < k; j++) {
200 decode_matrix[k * i + j] = invert_matrix[k * src_err_list[i] + j];
201 }
202 }
203 /* src_err_list from encode_matrix * invert of b for parity decoding */
204 for (p = nsrcerrs; p < nerrs; p++) {
205 for (i = 0; i < k; i++) {
206 s = 0;
207 for (j = 0; j < k; j++)
208 s ^= gf_mul(invert_matrix[j * k + i],
209 encode_matrix[k * src_err_list[p] + j]);
210
211 decode_matrix[k * p + i] = s;
212 }
213 }
214 free(b);
215 free(backup);
216 return 0;
217 }
218
219 int
main(int argc,char * argv[])220 main(int argc, char *argv[])
221 {
222 int re = -1;
223 int i, j, p, rtest, m, k;
224 int nerrs, nsrcerrs;
225 void *buf;
226 unsigned int decode_index[MMAX];
227 unsigned char *temp_buffs[TEST_SOURCES] = { NULL }, *buffs[TEST_SOURCES] = { NULL };
228 unsigned char *encode_matrix = NULL, *decode_matrix = NULL, *invert_matrix = NULL,
229 *g_tbls = NULL;
230 unsigned char src_in_err[TEST_SOURCES], src_err_list[TEST_SOURCES];
231 unsigned char *recov[TEST_SOURCES];
232
233 int rows, align, size;
234 unsigned char *efence_buffs[TEST_SOURCES];
235 unsigned int offset;
236 u8 *ubuffs[TEST_SOURCES];
237 u8 *temp_ubuffs[TEST_SOURCES];
238
239 printf("erasure_code_test: %dx%d ", TEST_SOURCES, TEST_LEN);
240 srand(TEST_SEED);
241
242 // Allocate the arrays
243 for (i = 0; i < TEST_SOURCES; i++) {
244 if (posix_memalign(&buf, 64, TEST_LEN)) {
245 printf("alloc error: Fail");
246 goto exit;
247 }
248 buffs[i] = buf;
249 }
250
251 for (i = 0; i < TEST_SOURCES; i++) {
252 if (posix_memalign(&buf, 64, TEST_LEN)) {
253 printf("alloc error: Fail");
254 goto exit;
255 }
256 temp_buffs[i] = buf;
257 }
258
259 // Test erasure code by encode and recovery
260
261 encode_matrix = malloc(MMAX * KMAX);
262 decode_matrix = malloc(MMAX * KMAX);
263 invert_matrix = malloc(MMAX * KMAX);
264 g_tbls = malloc(KMAX * TEST_SOURCES * 32);
265 if (encode_matrix == NULL || decode_matrix == NULL || invert_matrix == NULL ||
266 g_tbls == NULL) {
267 printf("Test failure! Error with malloc\n");
268 goto exit;
269 }
270 // Pick a first test
271 m = 9;
272 k = 5;
273 assert((m <= MMAX) && (k <= KMAX));
274
275 // Make random data
276 for (i = 0; i < k; i++)
277 for (j = 0; j < TEST_LEN; j++)
278 buffs[i][j] = rand();
279
280 // Generate encode matrix encode_matrix
281 // The matrix generated by gf_gen_rs_matrix
282 // is not always invertable.
283 gf_gen_rs_matrix(encode_matrix, m, k);
284
285 // Generate g_tbls from encode matrix encode_matrix
286 ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls);
287
288 // Perform matrix dot_prod for EC encoding
289 // using g_tbls from encode matrix encode_matrix
290 ec_encode_data(TEST_LEN, k, m - k, g_tbls, buffs, &buffs[k]);
291
292 // Choose random buffers to be in erasure
293 memset(src_in_err, 0, TEST_SOURCES);
294 gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m);
295
296 // Generate decode matrix
297 re = gf_gen_decode_matrix(encode_matrix, decode_matrix, invert_matrix, decode_index,
298 src_err_list, src_in_err, nerrs, nsrcerrs, k, m);
299 if (re != 0) {
300 printf("Fail to gf_gen_decode_matrix\n");
301 goto exit;
302 }
303 // Pack recovery array as list of valid sources
304 // Its order must be the same as the order
305 // to generate matrix b in gf_gen_decode_matrix
306 for (i = 0; i < k; i++) {
307 recov[i] = buffs[decode_index[i]];
308 }
309
310 // Recover data
311 ec_init_tables(k, nerrs, decode_matrix, g_tbls);
312 ec_encode_data(TEST_LEN, k, nerrs, g_tbls, recov, &temp_buffs[k]);
313 for (i = 0; i < nerrs; i++) {
314
315 if (0 != memcmp(temp_buffs[k + i], buffs[src_err_list[i]], TEST_LEN)) {
316 printf("Fail error recovery (%d, %d, %d)\n", m, k, nerrs);
317 printf(" - erase list = ");
318 for (j = 0; j < nerrs; j++)
319 printf(" %d", src_err_list[j]);
320 printf(" - Index = ");
321 for (p = 0; p < k; p++)
322 printf(" %d", decode_index[p]);
323 printf("\nencode_matrix:\n");
324 dump_u8xu8((u8 *) encode_matrix, m, k);
325 printf("inv b:\n");
326 dump_u8xu8((u8 *) invert_matrix, k, k);
327 printf("\ndecode_matrix:\n");
328 dump_u8xu8((u8 *) decode_matrix, m, k);
329 printf("recov %d:", src_err_list[i]);
330 dump(temp_buffs[k + i], 25);
331 printf("orig :");
332 dump(buffs[src_err_list[i]], 25);
333 re = -1;
334 goto exit;
335 }
336 }
337
338 // Pick a first test
339 m = 9;
340 k = 5;
341 if (m > MMAX || k > KMAX) {
342 re = -1;
343 goto exit;
344 }
345
346 // Make random data
347 for (i = 0; i < k; i++)
348 for (j = 0; j < TEST_LEN; j++)
349 buffs[i][j] = rand();
350
351 // The matrix generated by gf_gen_cauchy1_matrix
352 // is always invertable.
353 gf_gen_cauchy1_matrix(encode_matrix, m, k);
354
355 // Generate g_tbls from encode matrix encode_matrix
356 ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls);
357
358 // Perform matrix dot_prod for EC encoding
359 // using g_tbls from encode matrix encode_matrix
360 ec_encode_data(TEST_LEN, k, m - k, g_tbls, buffs, &buffs[k]);
361
362 // Choose random buffers to be in erasure
363 memset(src_in_err, 0, TEST_SOURCES);
364 gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m);
365
366 // Generate decode matrix
367 re = gf_gen_decode_matrix(encode_matrix, decode_matrix, invert_matrix, decode_index,
368 src_err_list, src_in_err, nerrs, nsrcerrs, k, m);
369 if (re != 0) {
370 printf("Fail to gf_gen_decode_matrix\n");
371 goto exit;
372 }
373 // Pack recovery array as list of valid sources
374 // Its order must be the same as the order
375 // to generate matrix b in gf_gen_decode_matrix
376 for (i = 0; i < k; i++) {
377 recov[i] = buffs[decode_index[i]];
378 }
379
380 // Recover data
381 ec_init_tables(k, nerrs, decode_matrix, g_tbls);
382 ec_encode_data(TEST_LEN, k, nerrs, g_tbls, recov, &temp_buffs[k]);
383 for (i = 0; i < nerrs; i++) {
384
385 if (0 != memcmp(temp_buffs[k + i], buffs[src_err_list[i]], TEST_LEN)) {
386 printf("Fail error recovery (%d, %d, %d)\n", m, k, nerrs);
387 printf(" - erase list = ");
388 for (j = 0; j < nerrs; j++)
389 printf(" %d", src_err_list[j]);
390 printf(" - Index = ");
391 for (p = 0; p < k; p++)
392 printf(" %d", decode_index[p]);
393 printf("\nencode_matrix:\n");
394 dump_u8xu8((u8 *) encode_matrix, m, k);
395 printf("inv b:\n");
396 dump_u8xu8((u8 *) invert_matrix, k, k);
397 printf("\ndecode_matrix:\n");
398 dump_u8xu8((u8 *) decode_matrix, m, k);
399 printf("recov %d:", src_err_list[i]);
400 dump(temp_buffs[k + i], 25);
401 printf("orig :");
402 dump(buffs[src_err_list[i]], 25);
403 re = -1;
404 goto exit;
405 }
406 }
407
408 // Do more random tests
409 for (rtest = 0; rtest < RANDOMS; rtest++) {
410 while ((m = (rand() % MMAX)) < 2)
411 ;
412 while ((k = (rand() % KMAX)) >= m || k < 1)
413 ;
414
415 if (m > MMAX || k > KMAX)
416 continue;
417
418 // Make random data
419 for (i = 0; i < k; i++)
420 for (j = 0; j < TEST_LEN; j++)
421 buffs[i][j] = rand();
422
423 // The matrix generated by gf_gen_cauchy1_matrix
424 // is always invertable.
425 gf_gen_cauchy1_matrix(encode_matrix, m, k);
426
427 // Make parity vects
428 // Generate g_tbls from encode matrix a
429 ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls);
430 // Perform matrix dot_prod for EC encoding
431 // using g_tbls from encode matrix a
432 ec_encode_data(TEST_LEN, k, m - k, g_tbls, buffs, &buffs[k]);
433
434 // Random errors
435 memset(src_in_err, 0, TEST_SOURCES);
436 gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m);
437
438 // Generate decode matrix
439 re = gf_gen_decode_matrix(encode_matrix, decode_matrix, invert_matrix, decode_index,
440 src_err_list, src_in_err, nerrs, nsrcerrs, k, m);
441 if (re != 0) {
442 printf("Fail to gf_gen_decode_matrix\n");
443 goto exit;
444 }
445 // Pack recovery array as list of valid sources
446 // Its order must be the same as the order
447 // to generate matrix b in gf_gen_decode_matrix
448 for (i = 0; i < k; i++) {
449 recov[i] = buffs[decode_index[i]];
450 }
451
452 // Recover data
453 ec_init_tables(k, nerrs, decode_matrix, g_tbls);
454 ec_encode_data(TEST_LEN, k, nerrs, g_tbls, recov, &temp_buffs[k]);
455
456 for (i = 0; i < nerrs; i++) {
457
458 if (0 != memcmp(temp_buffs[k + i], buffs[src_err_list[i]], TEST_LEN)) {
459 printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs);
460 printf(" - erase list = ");
461 for (j = 0; j < nerrs; j++)
462 printf(" %d", src_err_list[j]);
463 printf(" - Index = ");
464 for (p = 0; p < k; p++)
465 printf(" %d", decode_index[p]);
466 printf("\nencode_matrix:\n");
467 dump_u8xu8((u8 *) encode_matrix, m, k);
468 printf("inv b:\n");
469 dump_u8xu8((u8 *) invert_matrix, k, k);
470 printf("\ndecode_matrix:\n");
471 dump_u8xu8((u8 *) decode_matrix, m, k);
472 printf("orig data:\n");
473 dump_matrix(buffs, m, 25);
474 printf("orig :");
475 dump(buffs[src_err_list[i]], 25);
476 printf("recov %d:", src_err_list[i]);
477 dump(temp_buffs[k + i], 25);
478 re = -1;
479 goto exit;
480 }
481 }
482 #ifdef TEST_VERBOSE
483 putchar('.');
484 #endif
485 }
486
487 // Run tests at end of buffer for Electric Fence
488 k = 16;
489 align = (LEN_ALIGN_CHK_B != 0) ? 1 : 16;
490 if (k > KMAX) {
491 re = -1;
492 goto exit;
493 }
494
495 for (rows = 1; rows <= 16; rows++) {
496 m = k + rows;
497 if (m > MMAX) {
498 re = -1;
499 goto exit;
500 }
501
502 // Make random data
503 for (i = 0; i < k; i++)
504 for (j = 0; j < TEST_LEN; j++)
505 buffs[i][j] = rand();
506
507 for (size = EFENCE_TEST_MIN_SIZE; size <= EFENCE_TEST_MAX_SIZE; size += align) {
508 for (i = 0; i < m; i++) { // Line up TEST_SIZE from end
509 efence_buffs[i] = buffs[i] + TEST_LEN - size;
510 }
511
512 // The matrix generated by gf_gen_cauchy1_matrix
513 // is always invertable.
514 gf_gen_cauchy1_matrix(encode_matrix, m, k);
515
516 // Make parity vects
517 // Generate g_tbls from encode matrix a
518 ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls);
519 // Perform matrix dot_prod for EC encoding
520 // using g_tbls from encode matrix a
521 ec_encode_data(size, k, m - k, g_tbls, efence_buffs, &efence_buffs[k]);
522
523 // Random errors
524 memset(src_in_err, 0, TEST_SOURCES);
525 gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m);
526
527 // Generate decode matrix
528 re = gf_gen_decode_matrix(encode_matrix, decode_matrix, invert_matrix,
529 decode_index, src_err_list, src_in_err, nerrs,
530 nsrcerrs, k, m);
531 if (re != 0) {
532 printf("Fail to gf_gen_decode_matrix\n");
533 goto exit;
534 }
535 // Pack recovery array as list of valid sources
536 // Its order must be the same as the order
537 // to generate matrix b in gf_gen_decode_matrix
538 for (i = 0; i < k; i++) {
539 recov[i] = efence_buffs[decode_index[i]];
540 }
541
542 // Recover data
543 ec_init_tables(k, nerrs, decode_matrix, g_tbls);
544 ec_encode_data(size, k, nerrs, g_tbls, recov, &temp_buffs[k]);
545
546 for (i = 0; i < nerrs; i++) {
547
548 if (0 != memcmp(temp_buffs[k + i], efence_buffs[src_err_list[i]],
549 size)) {
550 printf("Efence: Fail error recovery (%d, %d, %d)\n", m, k,
551 nerrs);
552
553 printf("size = %d\n", size);
554
555 printf("Test erase list = ");
556 for (j = 0; j < nerrs; j++)
557 printf(" %d", src_err_list[j]);
558 printf(" - Index = ");
559 for (p = 0; p < k; p++)
560 printf(" %d", decode_index[p]);
561 printf("\nencode_matrix:\n");
562 dump_u8xu8((u8 *) encode_matrix, m, k);
563 printf("inv b:\n");
564 dump_u8xu8((u8 *) invert_matrix, k, k);
565 printf("\ndecode_matrix:\n");
566 dump_u8xu8((u8 *) decode_matrix, m, k);
567
568 printf("recov %d:", src_err_list[i]);
569 dump(temp_buffs[k + i], align);
570 printf("orig :");
571 dump(efence_buffs[src_err_list[i]], align);
572 re = -1;
573 goto exit;
574 }
575 }
576 }
577 }
578
579 // Test rand ptr alignment if available
580
581 for (rtest = 0; rtest < RANDOMS; rtest++) {
582 while ((m = (rand() % MMAX)) < 2)
583 ;
584 while ((k = (rand() % KMAX)) >= m || k < 1)
585 ;
586
587 if (m > MMAX || k > KMAX)
588 continue;
589
590 size = (TEST_LEN - PTR_ALIGN_CHK_B) & ~15;
591
592 offset = (PTR_ALIGN_CHK_B != 0) ? 1 : PTR_ALIGN_CHK_B;
593 // Add random offsets
594 for (i = 0; i < m; i++) {
595 memset(buffs[i], 0, TEST_LEN); // zero pad to check write-over
596 memset(temp_buffs[i], 0, TEST_LEN); // zero pad to check write-over
597 ubuffs[i] = buffs[i] + (rand() & (PTR_ALIGN_CHK_B - offset));
598 temp_ubuffs[i] = temp_buffs[i] + (rand() & (PTR_ALIGN_CHK_B - offset));
599 }
600
601 for (i = 0; i < k; i++)
602 for (j = 0; j < size; j++)
603 ubuffs[i][j] = rand();
604
605 // The matrix generated by gf_gen_cauchy1_matrix
606 // is always invertable.
607 gf_gen_cauchy1_matrix(encode_matrix, m, k);
608
609 // Make parity vects
610 // Generate g_tbls from encode matrix a
611 ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls);
612 // Perform matrix dot_prod for EC encoding
613 // using g_tbls from encode matrix a
614 ec_encode_data(size, k, m - k, g_tbls, ubuffs, &ubuffs[k]);
615
616 // Random errors
617 memset(src_in_err, 0, TEST_SOURCES);
618 gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m);
619
620 // Generate decode matrix
621 re = gf_gen_decode_matrix(encode_matrix, decode_matrix, invert_matrix, decode_index,
622 src_err_list, src_in_err, nerrs, nsrcerrs, k, m);
623 if (re != 0) {
624 printf("Fail to gf_gen_decode_matrix\n");
625 goto exit;
626 }
627 // Pack recovery array as list of valid sources
628 // Its order must be the same as the order
629 // to generate matrix b in gf_gen_decode_matrix
630 for (i = 0; i < k; i++) {
631 recov[i] = ubuffs[decode_index[i]];
632 }
633
634 // Recover data
635 ec_init_tables(k, nerrs, decode_matrix, g_tbls);
636 ec_encode_data(size, k, nerrs, g_tbls, recov, &temp_ubuffs[k]);
637
638 for (i = 0; i < nerrs; i++) {
639
640 if (0 != memcmp(temp_ubuffs[k + i], ubuffs[src_err_list[i]], size)) {
641 printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs);
642 printf(" - erase list = ");
643 for (j = 0; j < nerrs; j++)
644 printf(" %d", src_err_list[j]);
645 printf(" - Index = ");
646 for (p = 0; p < k; p++)
647 printf(" %d", decode_index[p]);
648 printf("\nencode_matrix:\n");
649 dump_u8xu8((unsigned char *) encode_matrix, m, k);
650 printf("inv b:\n");
651 dump_u8xu8((unsigned char *) invert_matrix, k, k);
652 printf("\ndecode_matrix:\n");
653 dump_u8xu8((unsigned char *) decode_matrix, m, k);
654 printf("orig data:\n");
655 dump_matrix(ubuffs, m, 25);
656 printf("orig :");
657 dump(ubuffs[src_err_list[i]], 25);
658 printf("recov %d:", src_err_list[i]);
659 dump(temp_ubuffs[k + i], 25);
660 re = -1;
661 goto exit;
662 }
663 }
664
665 // Confirm that padding around dests is unchanged
666 memset(temp_buffs[0], 0, PTR_ALIGN_CHK_B); // Make reference zero buff
667
668 for (i = 0; i < m; i++) {
669
670 offset = ubuffs[i] - buffs[i];
671
672 if (memcmp(buffs[i], temp_buffs[0], offset)) {
673 printf("Fail rand ualign encode pad start\n");
674 re = -1;
675 goto exit;
676 }
677 if (memcmp(buffs[i] + offset + size, temp_buffs[0],
678 PTR_ALIGN_CHK_B - offset)) {
679 printf("Fail rand ualign encode pad end\n");
680 re = -1;
681 goto exit;
682 }
683 }
684
685 for (i = 0; i < nerrs; i++) {
686
687 offset = temp_ubuffs[k + i] - temp_buffs[k + i];
688 if (memcmp(temp_buffs[k + i], temp_buffs[0], offset)) {
689 printf("Fail rand ualign decode pad start\n");
690 re = -1;
691 goto exit;
692 }
693 if (memcmp(temp_buffs[k + i] + offset + size, temp_buffs[0],
694 PTR_ALIGN_CHK_B - offset)) {
695 printf("Fail rand ualign decode pad end\n");
696 re = -1;
697 goto exit;
698 }
699 }
700
701 #ifdef TEST_VERBOSE
702 putchar('.');
703 #endif
704 }
705
706 // Test size alignment
707
708 align = (LEN_ALIGN_CHK_B != 0) ? 13 : 16;
709
710 for (size = TEST_LEN; size > 0; size -= align) {
711 while ((m = (rand() % MMAX)) < 2)
712 ;
713 while ((k = (rand() % KMAX)) >= m || k < 1)
714 ;
715
716 if (m > MMAX || k > KMAX)
717 continue;
718
719 for (i = 0; i < k; i++)
720 for (j = 0; j < size; j++)
721 buffs[i][j] = rand();
722
723 // The matrix generated by gf_gen_cauchy1_matrix
724 // is always invertable.
725 gf_gen_cauchy1_matrix(encode_matrix, m, k);
726
727 // Make parity vects
728 // Generate g_tbls from encode matrix a
729 ec_init_tables(k, m - k, &encode_matrix[k * k], g_tbls);
730 // Perform matrix dot_prod for EC encoding
731 // using g_tbls from encode matrix a
732 ec_encode_data(size, k, m - k, g_tbls, buffs, &buffs[k]);
733
734 // Random errors
735 memset(src_in_err, 0, TEST_SOURCES);
736 gen_err_list(src_err_list, src_in_err, &nerrs, &nsrcerrs, k, m);
737 // Generate decode matrix
738 re = gf_gen_decode_matrix(encode_matrix, decode_matrix, invert_matrix, decode_index,
739 src_err_list, src_in_err, nerrs, nsrcerrs, k, m);
740 if (re != 0) {
741 printf("Fail to gf_gen_decode_matrix\n");
742 goto exit;
743 }
744 // Pack recovery array as list of valid sources
745 // Its order must be the same as the order
746 // to generate matrix b in gf_gen_decode_matrix
747 for (i = 0; i < k; i++) {
748 recov[i] = buffs[decode_index[i]];
749 }
750
751 // Recover data
752 ec_init_tables(k, nerrs, decode_matrix, g_tbls);
753 ec_encode_data(size, k, nerrs, g_tbls, recov, &temp_buffs[k]);
754
755 for (i = 0; i < nerrs; i++) {
756
757 if (0 != memcmp(temp_buffs[k + i], buffs[src_err_list[i]], size)) {
758 printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs);
759 printf(" - erase list = ");
760 for (j = 0; j < nerrs; j++)
761 printf(" %d", src_err_list[j]);
762 printf(" - Index = ");
763 for (p = 0; p < k; p++)
764 printf(" %d", decode_index[p]);
765 printf("\nencode_matrix:\n");
766 dump_u8xu8((unsigned char *) encode_matrix, m, k);
767 printf("inv b:\n");
768 dump_u8xu8((unsigned char *) invert_matrix, k, k);
769 printf("\ndecode_matrix:\n");
770 dump_u8xu8((unsigned char *) decode_matrix, m, k);
771 printf("orig data:\n");
772 dump_matrix(buffs, m, 25);
773 printf("orig :");
774 dump(buffs[src_err_list[i]], 25);
775 printf("recov %d:", src_err_list[i]);
776 dump(temp_buffs[k + i], 25);
777 re = -1;
778 goto exit;
779 }
780 }
781 }
782
783 printf("done EC tests: Pass\n");
784 re = 0;
785
786 exit:
787 for (i = 0; i < TEST_SOURCES; i++) {
788 if (buffs[i])
789 aligned_free(buffs[i]);
790 if (temp_buffs[i])
791 aligned_free(temp_buffs[i]);
792 }
793 free(encode_matrix);
794 free(decode_matrix);
795 free(invert_matrix);
796 free(g_tbls);
797
798 return re;
799 }
800