1 /**********************************************************************
2 Copyright(c) 2011-2015 Intel Corporation All rights reserved.
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
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
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.
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 **********************************************************************/
31 #include <string.h> // for memset
32 #include "erasure_code.h"
33 #include "ec_base.h" // for GF tables
36 void ec_init_tables(int k
, int rows
, unsigned char *a
, unsigned char *g_tbls
)
40 for (i
= 0; i
< rows
; i
++) {
41 for (j
= 0; j
< k
; j
++) {
42 gf_vect_mul_init(*a
++, g_tbls
);
48 unsigned char gf_mul(unsigned char a
, unsigned char b
)
50 #ifndef GF_LARGE_TABLES
53 if ((a
== 0) || (b
== 0))
56 return gff_base
[(i
= gflog_base
[a
] + gflog_base
[b
]) > 254 ? i
- 255 : i
];
58 return gf_mul_table_base
[b
* 256 + a
];
62 unsigned char gf_inv(unsigned char a
)
64 #ifndef GF_LARGE_TABLES
68 return gff_base
[255 - gflog_base
[a
]];
70 return gf_inv_table_base
[a
];
74 void gf_gen_rs_matrix(unsigned char *a
, int m
, int k
)
77 unsigned char p
, gen
= 1;
80 for (i
= 0; i
< k
; i
++)
83 for (i
= k
; i
< m
; i
++) {
85 for (j
= 0; j
< k
; j
++) {
93 void gf_gen_cauchy1_matrix(unsigned char *a
, int m
, int k
)
98 // Identity matrix in high position
100 for (i
= 0; i
< k
; i
++)
103 // For the rest choose 1/(i + j) | i != j
105 for (i
= k
; i
< m
; i
++)
106 for (j
= 0; j
< k
; j
++)
107 *p
++ = gf_inv(i
^ j
);
111 int gf_invert_matrix(unsigned char *in_mat
, unsigned char *out_mat
, const int n
)
116 // Set out_mat[] to the identity matrix
117 for (i
= 0; i
< n
* n
; i
++) // memset(out_mat, 0, n*n)
120 for (i
= 0; i
< n
; i
++)
121 out_mat
[i
* n
+ i
] = 1;
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
])
132 if (j
== n
) // Couldn't find means it's singular
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
;
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
;
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
);
152 for (j
= 0; j
< n
; j
++) {
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
]);
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} }
169 void gf_vect_mul_init(unsigned char c
, unsigned char *tbl
)
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}
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
;
180 t
= (unsigned long long *)tbl
;
182 v1
= c
* 0x0100010001000100ull
;
183 v2
= c2
* 0x0101000001010000ull
;
184 v4
= c4
* 0x0101010100000000ull
;
185 v8
= c8
* 0x0101010101010101ull
;
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}
196 v10
= c17
* 0x0100010001000100ull
;
197 v20
= c18
* 0x0101000001010000ull
;
198 v40
= c20
* 0x0101010100000000ull
;
199 v80
= c24
* 0x0101010101010101ull
;
201 v40
= v10
^ v20
^ v40
;
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
,
240 c17
= (c8
<< 1) ^ ((c8
& 0x80) ? 0x1d : 0); //Mult by GF{2}
241 c18
= (c17
<< 1) ^ ((c17
& 0x80) ? 0x1d : 0); //Mult by GF{2}
243 c20
= (c18
<< 1) ^ ((c18
& 0x80) ? 0x1d : 0); //Mult by GF{2}
247 c24
= (c20
<< 1) ^ ((c20
& 0x80) ? 0x1d : 0); //Mult by GF{2}
273 #endif //__WORDSIZE == 64 || _WIN64 || __x86_64__
276 void gf_vect_dot_prod_base(int len
, int vlen
, unsigned char *v
,
277 unsigned char **src
, unsigned char *dest
)
281 for (i
= 0; i
< len
; i
++) {
283 for (j
= 0; j
< vlen
; j
++)
284 s
^= gf_mul(src
[j
][i
], v
[j
* 32 + 1]);
290 void gf_vect_mad_base(int len
, int vec
, int vec_i
,
291 unsigned char *v
, unsigned char *src
, unsigned char *dest
)
295 for (i
= 0; i
< len
; i
++) {
297 s
^= gf_mul(src
[i
], v
[vec_i
* 32 + 1]);
302 void ec_encode_data_base(int len
, int srcs
, int dests
, unsigned char *v
,
303 unsigned char **src
, unsigned char **dest
)
308 for (l
= 0; l
< dests
; l
++) {
309 for (i
= 0; i
< len
; i
++) {
311 for (j
= 0; j
< srcs
; j
++)
312 s
^= gf_mul(src
[j
][i
], v
[j
* 32 + l
* srcs
* 32 + 1]);
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
)
325 for (l
= 0; l
< rows
; l
++) {
326 for (i
= 0; i
< len
; i
++) {
328 s
^= gf_mul(data
[i
], v
[vec_i
* 32 + l
* k
* 32 + 1]);
335 void gf_vect_mul_base(int len
, unsigned char *a
, unsigned char *src
, unsigned char *dest
)
337 //2nd element of table array is ref value used to fill it in
338 unsigned char c
= a
[1];
340 *dest
++ = gf_mul(c
, *src
++);
350 struct slver gf_vect_mul_init_slver_00020035
;
351 struct slver gf_vect_mul_init_slver
= { 0x0035, 0x02, 0x00 };
353 struct slver ec_encode_data_base_slver_00010135
;
354 struct slver ec_encode_data_base_slver
= { 0x0135, 0x01, 0x00 };
356 struct slver gf_vect_mul_base_slver_00010136
;
357 struct slver gf_vect_mul_base_slver
= { 0x0136, 0x01, 0x00 };
359 struct slver gf_vect_dot_prod_base_slver_00010137
;
360 struct slver gf_vect_dot_prod_base_slver
= { 0x0137, 0x01, 0x00 };
362 struct slver gf_mul_slver_00000214
;
363 struct slver gf_mul_slver
= { 0x0214, 0x00, 0x00 };
365 struct slver gf_invert_matrix_slver_00000215
;
366 struct slver gf_invert_matrix_slver
= { 0x0215, 0x00, 0x00 };
368 struct slver gf_gen_rs_matrix_slver_00000216
;
369 struct slver gf_gen_rs_matrix_slver
= { 0x0216, 0x00, 0x00 };
371 struct slver gf_gen_cauchy1_matrix_slver_00000217
;
372 struct slver gf_gen_cauchy1_matrix_slver
= { 0x0217, 0x00, 0x00 };