]>
Commit | Line | Data |
---|---|---|
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 <limits.h> | |
31 | #include <string.h> // for memset | |
32 | #include "erasure_code.h" | |
33 | #include "ec_base.h" // for GF tables | |
34 | #include "types.h" | |
35 | ||
36 | void ec_init_tables(int k, int rows, unsigned char *a, unsigned char *g_tbls) | |
37 | { | |
38 | int i, j; | |
39 | ||
40 | for (i = 0; i < rows; i++) { | |
41 | for (j = 0; j < k; j++) { | |
42 | gf_vect_mul_init(*a++, g_tbls); | |
43 | g_tbls += 32; | |
44 | } | |
45 | } | |
46 | } | |
47 | ||
48 | unsigned char gf_mul(unsigned char a, unsigned char b) | |
49 | { | |
50 | #ifndef GF_LARGE_TABLES | |
51 | int i; | |
52 | ||
53 | if ((a == 0) || (b == 0)) | |
54 | return 0; | |
55 | ||
56 | return gff_base[(i = gflog_base[a] + gflog_base[b]) > 254 ? i - 255 : i]; | |
57 | #else | |
58 | return gf_mul_table_base[b * 256 + a]; | |
59 | #endif | |
60 | } | |
61 | ||
62 | unsigned char gf_inv(unsigned char a) | |
63 | { | |
64 | #ifndef GF_LARGE_TABLES | |
65 | if (a == 0) | |
66 | return 0; | |
67 | ||
68 | return gff_base[255 - gflog_base[a]]; | |
69 | #else | |
70 | return gf_inv_table_base[a]; | |
71 | #endif | |
72 | } | |
73 | ||
74 | void gf_gen_rs_matrix(unsigned char *a, int m, int k) | |
75 | { | |
76 | int i, j; | |
77 | unsigned char p, gen = 1; | |
78 | ||
79 | memset(a, 0, k * m); | |
80 | for (i = 0; i < k; i++) | |
81 | a[k * i + i] = 1; | |
82 | ||
83 | for (i = k; i < m; i++) { | |
84 | p = 1; | |
85 | for (j = 0; j < k; j++) { | |
86 | a[k * i + j] = p; | |
87 | p = gf_mul(p, gen); | |
88 | } | |
89 | gen = gf_mul(gen, 2); | |
90 | } | |
91 | } | |
92 | ||
93 | void gf_gen_cauchy1_matrix(unsigned char *a, int m, int k) | |
94 | { | |
95 | int i, j; | |
96 | unsigned char *p; | |
97 | ||
98 | // Identity matrix in high position | |
99 | memset(a, 0, k * m); | |
100 | for (i = 0; i < k; i++) | |
101 | a[k * i + i] = 1; | |
102 | ||
103 | // For the rest choose 1/(i + j) | i != j | |
104 | p = &a[k * k]; | |
105 | for (i = k; i < m; i++) | |
106 | for (j = 0; j < k; j++) | |
107 | *p++ = gf_inv(i ^ j); | |
108 | ||
109 | } | |
110 | ||
111 | int gf_invert_matrix(unsigned char *in_mat, unsigned char *out_mat, const int n) | |
112 | { | |
113 | int i, j, k; | |
114 | unsigned char temp; | |
115 | ||
116 | // Set out_mat[] to the identity matrix | |
117 | for (i = 0; i < n * n; i++) // memset(out_mat, 0, n*n) | |
118 | out_mat[i] = 0; | |
119 | ||
120 | for (i = 0; i < n; i++) | |
121 | out_mat[i * n + i] = 1; | |
122 | ||
123 | // Inverse | |
124 | for (i = 0; i < n; i++) { | |
125 | // Check for 0 in pivot element | |
126 | if (in_mat[i * n + i] == 0) { | |
127 | // Find a row with non-zero in current column and swap | |
128 | for (j = i + 1; j < n; j++) | |
129 | if (in_mat[j * n + i]) | |
130 | break; | |
131 | ||
132 | if (j == n) // Couldn't find means it's singular | |
133 | return -1; | |
134 | ||
135 | for (k = 0; k < n; k++) { // Swap rows i,j | |
136 | temp = in_mat[i * n + k]; | |
137 | in_mat[i * n + k] = in_mat[j * n + k]; | |
138 | in_mat[j * n + k] = temp; | |
139 | ||
140 | temp = out_mat[i * n + k]; | |
141 | out_mat[i * n + k] = out_mat[j * n + k]; | |
142 | out_mat[j * n + k] = temp; | |
143 | } | |
144 | } | |
145 | ||
146 | temp = gf_inv(in_mat[i * n + i]); // 1/pivot | |
147 | for (j = 0; j < n; j++) { // Scale row i by 1/pivot | |
148 | in_mat[i * n + j] = gf_mul(in_mat[i * n + j], temp); | |
149 | out_mat[i * n + j] = gf_mul(out_mat[i * n + j], temp); | |
150 | } | |
151 | ||
152 | for (j = 0; j < n; j++) { | |
153 | if (j == i) | |
154 | continue; | |
155 | ||
156 | temp = in_mat[j * n + i]; | |
157 | for (k = 0; k < n; k++) { | |
158 | out_mat[j * n + k] ^= gf_mul(temp, out_mat[i * n + k]); | |
159 | in_mat[j * n + k] ^= gf_mul(temp, in_mat[i * n + k]); | |
160 | } | |
161 | } | |
162 | } | |
163 | return 0; | |
164 | } | |
165 | ||
166 | // Calculates const table gftbl in GF(2^8) from single input A | |
167 | // gftbl(A) = {A{00}, A{01}, A{02}, ... , A{0f} }, {A{00}, A{10}, A{20}, ... , A{f0} } | |
168 | ||
169 | void gf_vect_mul_init(unsigned char c, unsigned char *tbl) | |
170 | { | |
171 | unsigned char c2 = (c << 1) ^ ((c & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
172 | unsigned char c4 = (c2 << 1) ^ ((c2 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
173 | unsigned char c8 = (c4 << 1) ^ ((c4 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
174 | ||
175 | #if __WORDSIZE == 64 || _WIN64 || __x86_64__ | |
176 | unsigned long long v1, v2, v4, v8, *t; | |
177 | unsigned long long v10, v20, v40, v80; | |
178 | unsigned char c17, c18, c20, c24; | |
179 | ||
180 | t = (unsigned long long *)tbl; | |
181 | ||
182 | v1 = c * 0x0100010001000100ull; | |
183 | v2 = c2 * 0x0101000001010000ull; | |
184 | v4 = c4 * 0x0101010100000000ull; | |
185 | v8 = c8 * 0x0101010101010101ull; | |
186 | ||
187 | v4 = v1 ^ v2 ^ v4; | |
188 | t[0] = v4; | |
189 | t[1] = v8 ^ v4; | |
190 | ||
191 | c17 = (c8 << 1) ^ ((c8 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
192 | c18 = (c17 << 1) ^ ((c17 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
193 | c20 = (c18 << 1) ^ ((c18 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
194 | c24 = (c20 << 1) ^ ((c20 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
195 | ||
196 | v10 = c17 * 0x0100010001000100ull; | |
197 | v20 = c18 * 0x0101000001010000ull; | |
198 | v40 = c20 * 0x0101010100000000ull; | |
199 | v80 = c24 * 0x0101010101010101ull; | |
200 | ||
201 | v40 = v10 ^ v20 ^ v40; | |
202 | t[2] = v40; | |
203 | t[3] = v80 ^ v40; | |
204 | ||
205 | #else // 32-bit or other | |
206 | unsigned char c3, c5, c6, c7, c9, c10, c11, c12, c13, c14, c15; | |
207 | unsigned char c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29, c30, | |
208 | c31; | |
209 | ||
210 | c3 = c2 ^ c; | |
211 | c5 = c4 ^ c; | |
212 | c6 = c4 ^ c2; | |
213 | c7 = c4 ^ c3; | |
214 | ||
215 | c9 = c8 ^ c; | |
216 | c10 = c8 ^ c2; | |
217 | c11 = c8 ^ c3; | |
218 | c12 = c8 ^ c4; | |
219 | c13 = c8 ^ c5; | |
220 | c14 = c8 ^ c6; | |
221 | c15 = c8 ^ c7; | |
222 | ||
223 | tbl[0] = 0; | |
224 | tbl[1] = c; | |
225 | tbl[2] = c2; | |
226 | tbl[3] = c3; | |
227 | tbl[4] = c4; | |
228 | tbl[5] = c5; | |
229 | tbl[6] = c6; | |
230 | tbl[7] = c7; | |
231 | tbl[8] = c8; | |
232 | tbl[9] = c9; | |
233 | tbl[10] = c10; | |
234 | tbl[11] = c11; | |
235 | tbl[12] = c12; | |
236 | tbl[13] = c13; | |
237 | tbl[14] = c14; | |
238 | tbl[15] = c15; | |
239 | ||
240 | c17 = (c8 << 1) ^ ((c8 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
241 | c18 = (c17 << 1) ^ ((c17 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
242 | c19 = c18 ^ c17; | |
243 | c20 = (c18 << 1) ^ ((c18 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
244 | c21 = c20 ^ c17; | |
245 | c22 = c20 ^ c18; | |
246 | c23 = c20 ^ c19; | |
247 | c24 = (c20 << 1) ^ ((c20 & 0x80) ? 0x1d : 0); //Mult by GF{2} | |
248 | c25 = c24 ^ c17; | |
249 | c26 = c24 ^ c18; | |
250 | c27 = c24 ^ c19; | |
251 | c28 = c24 ^ c20; | |
252 | c29 = c24 ^ c21; | |
253 | c30 = c24 ^ c22; | |
254 | c31 = c24 ^ c23; | |
255 | ||
256 | tbl[16] = 0; | |
257 | tbl[17] = c17; | |
258 | tbl[18] = c18; | |
259 | tbl[19] = c19; | |
260 | tbl[20] = c20; | |
261 | tbl[21] = c21; | |
262 | tbl[22] = c22; | |
263 | tbl[23] = c23; | |
264 | tbl[24] = c24; | |
265 | tbl[25] = c25; | |
266 | tbl[26] = c26; | |
267 | tbl[27] = c27; | |
268 | tbl[28] = c28; | |
269 | tbl[29] = c29; | |
270 | tbl[30] = c30; | |
271 | tbl[31] = c31; | |
272 | ||
273 | #endif //__WORDSIZE == 64 || _WIN64 || __x86_64__ | |
274 | } | |
275 | ||
276 | void gf_vect_dot_prod_base(int len, int vlen, unsigned char *v, | |
277 | unsigned char **src, unsigned char *dest) | |
278 | { | |
279 | int i, j; | |
280 | unsigned char s; | |
281 | for (i = 0; i < len; i++) { | |
282 | s = 0; | |
283 | for (j = 0; j < vlen; j++) | |
284 | s ^= gf_mul(src[j][i], v[j * 32 + 1]); | |
285 | ||
286 | dest[i] = s; | |
287 | } | |
288 | } | |
289 | ||
290 | void gf_vect_mad_base(int len, int vec, int vec_i, | |
291 | unsigned char *v, unsigned char *src, unsigned char *dest) | |
292 | { | |
293 | int i; | |
294 | unsigned char s; | |
295 | for (i = 0; i < len; i++) { | |
296 | s = dest[i]; | |
297 | s ^= gf_mul(src[i], v[vec_i * 32 + 1]); | |
298 | dest[i] = s; | |
299 | } | |
300 | } | |
301 | ||
302 | void ec_encode_data_base(int len, int srcs, int dests, unsigned char *v, | |
303 | unsigned char **src, unsigned char **dest) | |
304 | { | |
305 | int i, j, l; | |
306 | unsigned char s; | |
307 | ||
308 | for (l = 0; l < dests; l++) { | |
309 | for (i = 0; i < len; i++) { | |
310 | s = 0; | |
311 | for (j = 0; j < srcs; j++) | |
312 | s ^= gf_mul(src[j][i], v[j * 32 + l * srcs * 32 + 1]); | |
313 | ||
314 | dest[l][i] = s; | |
315 | } | |
316 | } | |
317 | } | |
318 | ||
319 | void ec_encode_data_update_base(int len, int k, int rows, int vec_i, unsigned char *v, | |
320 | unsigned char *data, unsigned char **dest) | |
321 | { | |
322 | int i, l; | |
323 | unsigned char s; | |
324 | ||
325 | for (l = 0; l < rows; l++) { | |
326 | for (i = 0; i < len; i++) { | |
327 | s = dest[l][i]; | |
328 | s ^= gf_mul(data[i], v[vec_i * 32 + l * k * 32 + 1]); | |
329 | ||
330 | dest[l][i] = s; | |
331 | } | |
332 | } | |
333 | } | |
334 | ||
335 | void gf_vect_mul_base(int len, unsigned char *a, unsigned char *src, unsigned char *dest) | |
336 | { | |
337 | //2nd element of table array is ref value used to fill it in | |
338 | unsigned char c = a[1]; | |
339 | while (len-- > 0) | |
340 | *dest++ = gf_mul(c, *src++); | |
341 | } | |
342 | ||
343 | struct slver { | |
344 | UINT16 snum; | |
345 | UINT8 ver; | |
346 | UINT8 core; | |
347 | }; | |
348 | ||
349 | // Version info | |
350 | struct slver gf_vect_mul_init_slver_00020035; | |
351 | struct slver gf_vect_mul_init_slver = { 0x0035, 0x02, 0x00 }; | |
352 | ||
353 | struct slver ec_encode_data_base_slver_00010135; | |
354 | struct slver ec_encode_data_base_slver = { 0x0135, 0x01, 0x00 }; | |
355 | ||
356 | struct slver gf_vect_mul_base_slver_00010136; | |
357 | struct slver gf_vect_mul_base_slver = { 0x0136, 0x01, 0x00 }; | |
358 | ||
359 | struct slver gf_vect_dot_prod_base_slver_00010137; | |
360 | struct slver gf_vect_dot_prod_base_slver = { 0x0137, 0x01, 0x00 }; | |
361 | ||
362 | struct slver gf_mul_slver_00000214; | |
363 | struct slver gf_mul_slver = { 0x0214, 0x00, 0x00 }; | |
364 | ||
365 | struct slver gf_invert_matrix_slver_00000215; | |
366 | struct slver gf_invert_matrix_slver = { 0x0215, 0x00, 0x00 }; | |
367 | ||
368 | struct slver gf_gen_rs_matrix_slver_00000216; | |
369 | struct slver gf_gen_rs_matrix_slver = { 0x0216, 0x00, 0x00 }; | |
370 | ||
371 | struct slver gf_gen_cauchy1_matrix_slver_00000217; | |
372 | struct slver gf_gen_cauchy1_matrix_slver = { 0x0217, 0x00, 0x00 }; |