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