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 "erasure_code.h" 34 #include "test.h" 35 36 #define TEST_LEN 8192 37 #define TEST_SIZE (TEST_LEN/2) 38 39 #ifndef TEST_SOURCES 40 # define TEST_SOURCES 250 41 #endif 42 #ifndef RANDOMS 43 # define RANDOMS 20 44 #endif 45 46 #define MMAX TEST_SOURCES 47 #define KMAX TEST_SOURCES 48 49 typedef unsigned char u8; 50 51 void dump(unsigned char *buf, int len) 52 { 53 int i; 54 for (i = 0; i < len;) { 55 printf(" %2x", 0xff & buf[i++]); 56 if (i % 32 == 0) 57 printf("\n"); 58 } 59 printf("\n"); 60 } 61 62 void dump_matrix(unsigned char **s, int k, int m) 63 { 64 int i, j; 65 for (i = 0; i < k; i++) { 66 for (j = 0; j < m; j++) { 67 printf(" %2x", s[i][j]); 68 } 69 printf("\n"); 70 } 71 printf("\n"); 72 } 73 74 void dump_u8xu8(unsigned char *s, int k, int m) 75 { 76 int i, j; 77 for (i = 0; i < k; i++) { 78 for (j = 0; j < m; j++) { 79 printf(" %2x", 0xff & s[j + (i * m)]); 80 } 81 printf("\n"); 82 } 83 printf("\n"); 84 } 85 86 int main(int argc, char *argv[]) 87 { 88 int i, j, rtest, m, k, nerrs, r, err; 89 void *buf; 90 u8 g[TEST_SOURCES], g_tbls[TEST_SOURCES * 32], src_in_err[TEST_SOURCES]; 91 u8 *dest, *dest_ref, *temp_buff, *buffs[TEST_SOURCES]; 92 u8 a[MMAX * KMAX], b[MMAX * KMAX], d[MMAX * KMAX]; 93 u8 src_err_list[TEST_SOURCES], *recov[TEST_SOURCES]; 94 95 printf("gf_vect_dot_prod_base: %dx%d ", TEST_SOURCES, TEST_LEN); 96 97 // Allocate the arrays 98 for (i = 0; i < TEST_SOURCES; i++) { 99 if (posix_memalign(&buf, 64, TEST_LEN)) { 100 printf("alloc error: Fail"); 101 return -1; 102 } 103 buffs[i] = buf; 104 } 105 106 if (posix_memalign(&buf, 64, TEST_LEN)) { 107 printf("alloc error: Fail"); 108 return -1; 109 } 110 dest = buf; 111 112 if (posix_memalign(&buf, 64, TEST_LEN)) { 113 printf("alloc error: Fail"); 114 return -1; 115 } 116 dest_ref = buf; 117 118 if (posix_memalign(&buf, 64, TEST_LEN)) { 119 printf("alloc error: Fail"); 120 return -1; 121 } 122 temp_buff = buf; 123 124 // Init 125 for (i = 0; i < TEST_SOURCES; i++) 126 memset(buffs[i], 0, TEST_LEN); 127 128 memset(dest, 0, TEST_LEN); 129 memset(temp_buff, 0, TEST_LEN); 130 memset(dest_ref, 0, TEST_LEN); 131 memset(g, 0, TEST_SOURCES); 132 133 // Test erasure code using gf_vect_dot_prod 134 // Pick a first test 135 m = 9; 136 k = 5; 137 if (m > MMAX || k > KMAX) 138 return -1; 139 140 gf_gen_cauchy1_matrix(a, m, k); 141 142 // Make random data 143 for (i = 0; i < k; i++) 144 for (j = 0; j < TEST_LEN; j++) 145 buffs[i][j] = rand(); 146 147 // Make parity vects 148 for (i = k; i < m; i++) { 149 for (j = 0; j < k; j++) 150 gf_vect_mul_init(a[k * i + j], &g_tbls[j * 32]); 151 152 gf_vect_dot_prod_base(TEST_LEN, k, g_tbls, buffs, buffs[i]); 153 } 154 155 // Random buffers in erasure 156 memset(src_in_err, 0, TEST_SOURCES); 157 for (i = 0, nerrs = 0; i < k && nerrs < m - k; i++) { 158 err = 1 & rand(); 159 src_in_err[i] = err; 160 if (err) 161 src_err_list[nerrs++] = i; 162 } 163 164 // construct b by removing error rows 165 for (i = 0, r = 0; i < k; i++, r++) { 166 while (src_in_err[r]) { 167 r++; 168 continue; 169 } 170 for (j = 0; j < k; j++) 171 b[k * i + j] = a[k * r + j]; 172 } 173 174 if (gf_invert_matrix((u8 *) b, (u8 *) d, k) < 0) 175 printf("BAD MATRIX\n"); 176 177 for (i = 0, r = 0; i < k; i++, r++) { 178 while (src_in_err[r]) { 179 r++; 180 continue; 181 } 182 recov[i] = buffs[r]; 183 } 184 185 // Recover data 186 for (i = 0; i < nerrs; i++) { 187 for (j = 0; j < k; j++) 188 gf_vect_mul_init(d[k * src_err_list[i] + j], &g_tbls[j * 32]); 189 190 gf_vect_dot_prod_base(TEST_LEN, k, g_tbls, recov, temp_buff); 191 192 if (0 != memcmp(temp_buff, buffs[src_err_list[i]], TEST_LEN)) { 193 printf("Fail error recovery (%d, %d, %d)\n", m, k, nerrs); 194 printf("recov %d:", src_err_list[i]); 195 dump(temp_buff, 25); 196 printf("orig :"); 197 dump(buffs[src_err_list[i]], 25); 198 return -1; 199 } 200 } 201 202 // Do more random tests 203 204 for (rtest = 0; rtest < RANDOMS; rtest++) { 205 while ((m = (rand() % MMAX)) < 2) ; 206 while ((k = (rand() % KMAX)) >= m || k < 1) ; 207 208 if (m > MMAX || k > KMAX) 209 continue; 210 211 gf_gen_cauchy1_matrix(a, m, k); 212 213 // Make random data 214 for (i = 0; i < k; i++) 215 for (j = 0; j < TEST_LEN; j++) 216 buffs[i][j] = rand(); 217 218 // Make parity vects 219 for (i = k; i < m; i++) { 220 for (j = 0; j < k; j++) 221 gf_vect_mul_init(a[k * i + j], &g_tbls[j * 32]); 222 223 gf_vect_dot_prod_base(TEST_LEN, k, g_tbls, buffs, buffs[i]); 224 } 225 226 // Random errors 227 memset(src_in_err, 0, TEST_SOURCES); 228 for (i = 0, nerrs = 0; i < k && nerrs < m - k; i++) { 229 err = 1 & rand(); 230 src_in_err[i] = err; 231 if (err) 232 src_err_list[nerrs++] = i; 233 } 234 if (nerrs == 0) { // should have at least one error 235 while ((err = (rand() % KMAX)) >= k) ; 236 src_err_list[nerrs++] = err; 237 src_in_err[err] = 1; 238 } 239 // construct b by removing error rows 240 for (i = 0, r = 0; i < k; i++, r++) { 241 while (src_in_err[r]) { 242 r++; 243 continue; 244 } 245 for (j = 0; j < k; j++) 246 b[k * i + j] = a[k * r + j]; 247 } 248 249 if (gf_invert_matrix((u8 *) b, (u8 *) d, k) < 0) 250 printf("BAD MATRIX\n"); 251 252 for (i = 0, r = 0; i < k; i++, r++) { 253 while (src_in_err[r]) { 254 r++; 255 continue; 256 } 257 recov[i] = buffs[r]; 258 } 259 260 // Recover data 261 for (i = 0; i < nerrs; i++) { 262 for (j = 0; j < k; j++) 263 gf_vect_mul_init(d[k * src_err_list[i] + j], &g_tbls[j * 32]); 264 265 gf_vect_dot_prod_base(TEST_LEN, k, g_tbls, recov, temp_buff); 266 267 if (0 != memcmp(temp_buff, buffs[src_err_list[i]], TEST_LEN)) { 268 printf("Fail error recovery (%d, %d, %d) - ", m, k, nerrs); 269 printf(" - erase list = "); 270 for (i = 0; i < nerrs; i++) 271 printf(" %d", src_err_list[i]); 272 printf("\na:\n"); 273 dump_u8xu8((u8 *) a, m, k); 274 printf("inv b:\n"); 275 dump_u8xu8((u8 *) d, k, k); 276 printf("orig data:\n"); 277 dump_matrix(buffs, m, 25); 278 printf("orig :"); 279 dump(buffs[src_err_list[i]], 25); 280 printf("recov %d:", src_err_list[i]); 281 dump(temp_buff, 25); 282 return -1; 283 } 284 } 285 #ifdef TEST_VERBOSE 286 putchar('.'); 287 #endif 288 } 289 290 printf("done all: Pass\n"); 291 return 0; 292 } 293