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 36 #define MMAX 255 37 #define KMAX 255 38 39 typedef unsigned char u8; 40 41 int 42 usage(void) 43 { 44 fprintf(stderr, 45 "Usage: ec_simple_example [options]\n" 46 " -h Help\n" 47 " -k <val> Number of source fragments\n" 48 " -p <val> Number of parity fragments\n" 49 " -l <val> Length of fragments\n" 50 " -e <val> Simulate erasure on frag index val. Zero based. Can be repeated.\n" 51 " -r <seed> Pick random (k, p) with seed\n"); 52 exit(0); 53 } 54 55 static int 56 gf_gen_decode_matrix_simple(u8 *encode_matrix, u8 *decode_matrix, u8 *invert_matrix, 57 u8 *temp_matrix, u8 *decode_index, u8 *frag_err_list, int nerrs, int k, 58 int m); 59 60 int 61 main(int argc, char *argv[]) 62 { 63 int i, j, m, c, e, ret; 64 int k = 10, p = 4, len = 8 * 1024; // Default params 65 int nerrs = 0; 66 67 // Fragment buffer pointers 68 u8 *frag_ptrs[MMAX]; 69 u8 *recover_srcs[KMAX]; 70 u8 *recover_outp[KMAX]; 71 u8 frag_err_list[MMAX]; 72 73 // Coefficient matrices 74 u8 *encode_matrix, *decode_matrix; 75 u8 *invert_matrix, *temp_matrix; 76 u8 *g_tbls; 77 u8 decode_index[MMAX]; 78 79 if (argc == 1) 80 for (i = 0; i < p; i++) 81 frag_err_list[nerrs++] = rand() % (k + p); 82 83 while ((c = getopt(argc, argv, "k:p:l:e:r:h")) != -1) { 84 switch (c) { 85 case 'k': 86 k = atoi(optarg); 87 break; 88 case 'p': 89 p = atoi(optarg); 90 break; 91 case 'l': 92 len = atoi(optarg); 93 if (len < 0) 94 usage(); 95 break; 96 case 'e': 97 e = atoi(optarg); 98 frag_err_list[nerrs++] = e; 99 break; 100 case 'r': 101 srand(atoi(optarg)); 102 k = (rand() % (MMAX - 1)) + 1; // Pick k {1 to MMAX - 1} 103 p = (rand() % (MMAX - k)) + 1; // Pick p {1 to MMAX - k} 104 105 for (i = 0; i < k + p && nerrs < p; i++) 106 if (rand() & 1) 107 frag_err_list[nerrs++] = i; 108 break; 109 case 'h': 110 default: 111 usage(); 112 break; 113 } 114 } 115 m = k + p; 116 117 // Check for valid parameters 118 if (m > MMAX || k > KMAX || m < 0 || p < 1 || k < 1) { 119 printf(" Input test parameter error m=%d, k=%d, p=%d, erasures=%d\n", m, k, p, 120 nerrs); 121 usage(); 122 } 123 if (nerrs > p) { 124 printf(" Number of erasures chosen exceeds power of code erasures=%d p=%d\n", nerrs, 125 p); 126 usage(); 127 } 128 for (i = 0; i < nerrs; i++) { 129 if (frag_err_list[i] >= m) { 130 printf(" fragment %d not in range\n", frag_err_list[i]); 131 usage(); 132 } 133 } 134 135 printf("ec_simple_example:\n"); 136 137 // Allocate coding matrices 138 encode_matrix = malloc(m * k); 139 decode_matrix = malloc(m * k); 140 invert_matrix = malloc(m * k); 141 temp_matrix = malloc(m * k); 142 g_tbls = malloc(k * p * 32); 143 144 if (encode_matrix == NULL || decode_matrix == NULL || invert_matrix == NULL || 145 temp_matrix == NULL || g_tbls == NULL) { 146 printf("Test failure! Error with malloc\n"); 147 return -1; 148 } 149 // Allocate the src & parity buffers 150 for (i = 0; i < m; i++) { 151 if (NULL == (frag_ptrs[i] = malloc(len))) { 152 printf("alloc error: Fail\n"); 153 return -1; 154 } 155 } 156 157 // Allocate buffers for recovered data 158 for (i = 0; i < p; i++) { 159 if (NULL == (recover_outp[i] = malloc(len))) { 160 printf("alloc error: Fail\n"); 161 return -1; 162 } 163 } 164 165 // Fill sources with random data 166 for (i = 0; i < k; i++) 167 for (j = 0; j < len; j++) 168 frag_ptrs[i][j] = rand(); 169 170 printf(" encode (m,k,p)=(%d,%d,%d) len=%d\n", m, k, p, len); 171 172 // Pick an encode matrix. A Cauchy matrix is a good choice as even 173 // large k are always invertable keeping the recovery rule simple. 174 gf_gen_cauchy1_matrix(encode_matrix, m, k); 175 176 // Initialize g_tbls from encode matrix 177 ec_init_tables(k, p, &encode_matrix[k * k], g_tbls); 178 179 // Generate EC parity blocks from sources 180 ec_encode_data(len, k, p, g_tbls, frag_ptrs, &frag_ptrs[k]); 181 182 if (nerrs <= 0) 183 return 0; 184 185 printf(" recover %d fragments\n", nerrs); 186 187 // Find a decode matrix to regenerate all erasures from remaining frags 188 ret = gf_gen_decode_matrix_simple(encode_matrix, decode_matrix, invert_matrix, temp_matrix, 189 decode_index, frag_err_list, nerrs, k, m); 190 if (ret != 0) { 191 printf("Fail on generate decode matrix\n"); 192 return -1; 193 } 194 // Pack recovery array pointers as list of valid fragments 195 for (i = 0; i < k; i++) 196 recover_srcs[i] = frag_ptrs[decode_index[i]]; 197 198 // Recover data 199 ec_init_tables(k, nerrs, decode_matrix, g_tbls); 200 ec_encode_data(len, k, nerrs, g_tbls, recover_srcs, recover_outp); 201 202 // Check that recovered buffers are the same as original 203 printf(" check recovery of block {"); 204 for (i = 0; i < nerrs; i++) { 205 printf(" %d", frag_err_list[i]); 206 if (memcmp(recover_outp[i], frag_ptrs[frag_err_list[i]], len)) { 207 printf(" Fail erasure recovery %d, frag %d\n", i, frag_err_list[i]); 208 return -1; 209 } 210 } 211 212 printf(" } done all: Pass\n"); 213 return 0; 214 } 215 216 /* 217 * Generate decode matrix from encode matrix and erasure list 218 * 219 */ 220 221 static int 222 gf_gen_decode_matrix_simple(u8 *encode_matrix, u8 *decode_matrix, u8 *invert_matrix, 223 u8 *temp_matrix, u8 *decode_index, u8 *frag_err_list, int nerrs, int k, 224 int m) 225 { 226 int i, j, p, r; 227 int nsrcerrs = 0; 228 u8 s, *b = temp_matrix; 229 u8 frag_in_err[MMAX]; 230 231 memset(frag_in_err, 0, sizeof(frag_in_err)); 232 233 // Order the fragments in erasure for easier sorting 234 for (i = 0; i < nerrs; i++) { 235 if (frag_err_list[i] < k) 236 nsrcerrs++; 237 frag_in_err[frag_err_list[i]] = 1; 238 } 239 240 // Construct b (matrix that encoded remaining frags) by removing erased rows 241 for (i = 0, r = 0; i < k; i++, r++) { 242 while (frag_in_err[r]) 243 r++; 244 for (j = 0; j < k; j++) 245 b[k * i + j] = encode_matrix[k * r + j]; 246 decode_index[i] = r; 247 } 248 249 // Invert matrix to get recovery matrix 250 if (gf_invert_matrix(b, invert_matrix, k) < 0) 251 return -1; 252 253 // Get decode matrix with only wanted recovery rows 254 for (i = 0; i < nerrs; i++) { 255 if (frag_err_list[i] < k) // A src err 256 for (j = 0; j < k; j++) 257 decode_matrix[k * i + j] = invert_matrix[k * frag_err_list[i] + j]; 258 } 259 260 // For non-src (parity) erasures need to multiply encode matrix * invert 261 for (p = 0; p < nerrs; p++) { 262 if (frag_err_list[p] >= k) { // A parity err 263 for (i = 0; i < k; i++) { 264 s = 0; 265 for (j = 0; j < k; j++) 266 s ^= gf_mul(invert_matrix[j * k + i], 267 encode_matrix[k * frag_err_list[p] + j]); 268 decode_matrix[k * p + i] = s; 269 } 270 } 271 } 272 return 0; 273 } 274