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
usage(void)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
main(int argc,char * argv[])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
gf_gen_decode_matrix_simple(u8 * encode_matrix,u8 * decode_matrix,u8 * invert_matrix,u8 * temp_matrix,u8 * decode_index,u8 * frag_err_list,int nerrs,int k,int m)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