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