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