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 unsigned char gf_mul(unsigned char a
, unsigned char b
)
38 #ifndef GF_LARGE_TABLES
41 if ((a
== 0) || (b
== 0))
44 return gff_base
[(i
= gflog_base
[a
] + gflog_base
[b
]) > 254 ? i
- 255 : i
];
46 return gf_mul_table_base
[b
* 256 + a
];
50 unsigned char gf_inv(unsigned char a
)
52 #ifndef GF_LARGE_TABLES
56 return gff_base
[255 - gflog_base
[a
]];
58 return gf_inv_table_base
[a
];
62 void gf_gen_rs_matrix(unsigned char *a
, int m
, int k
)
65 unsigned char p
, gen
= 1;
68 for (i
= 0; i
< k
; i
++)
71 for (i
= k
; i
< m
; i
++) {
73 for (j
= 0; j
< k
; j
++) {
81 void gf_gen_cauchy1_matrix(unsigned char *a
, int m
, int k
)
86 // Identity matrix in high position
88 for (i
= 0; i
< k
; i
++)
91 // For the rest choose 1/(i + j) | i != j
93 for (i
= k
; i
< m
; i
++)
94 for (j
= 0; j
< k
; j
++)
99 int gf_invert_matrix(unsigned char *in_mat
, unsigned char *out_mat
, const int n
)
104 // Set out_mat[] to the identity matrix
105 for (i
= 0; i
< n
* n
; i
++) // memset(out_mat, 0, n*n)
108 for (i
= 0; i
< n
; i
++)
109 out_mat
[i
* n
+ i
] = 1;
112 for (i
= 0; i
< n
; i
++) {
113 // Check for 0 in pivot element
114 if (in_mat
[i
* n
+ i
] == 0) {
115 // Find a row with non-zero in current column and swap
116 for (j
= i
+ 1; j
< n
; j
++)
117 if (in_mat
[j
* n
+ i
])
120 if (j
== n
) // Couldn't find means it's singular
123 for (k
= 0; k
< n
; k
++) { // Swap rows i,j
124 temp
= in_mat
[i
* n
+ k
];
125 in_mat
[i
* n
+ k
] = in_mat
[j
* n
+ k
];
126 in_mat
[j
* n
+ k
] = temp
;
128 temp
= out_mat
[i
* n
+ k
];
129 out_mat
[i
* n
+ k
] = out_mat
[j
* n
+ k
];
130 out_mat
[j
* n
+ k
] = temp
;
134 temp
= gf_inv(in_mat
[i
* n
+ i
]); // 1/pivot
135 for (j
= 0; j
< n
; j
++) { // Scale row i by 1/pivot
136 in_mat
[i
* n
+ j
] = gf_mul(in_mat
[i
* n
+ j
], temp
);
137 out_mat
[i
* n
+ j
] = gf_mul(out_mat
[i
* n
+ j
], temp
);
140 for (j
= 0; j
< n
; j
++) {
144 temp
= in_mat
[j
* n
+ i
];
145 for (k
= 0; k
< n
; k
++) {
146 out_mat
[j
* n
+ k
] ^= gf_mul(temp
, out_mat
[i
* n
+ k
]);
147 in_mat
[j
* n
+ k
] ^= gf_mul(temp
, in_mat
[i
* n
+ k
]);
154 // Calculates const table gftbl in GF(2^8) from single input A
155 // gftbl(A) = {A{00}, A{01}, A{02}, ... , A{0f} }, {A{00}, A{10}, A{20}, ... , A{f0} }
157 void gf_vect_mul_init(unsigned char c
, unsigned char *tbl
)
159 unsigned char c2
= (c
<< 1) ^ ((c
& 0x80) ? 0x1d : 0); //Mult by GF{2}
160 unsigned char c4
= (c2
<< 1) ^ ((c2
& 0x80) ? 0x1d : 0); //Mult by GF{2}
161 unsigned char c8
= (c4
<< 1) ^ ((c4
& 0x80) ? 0x1d : 0); //Mult by GF{2}
163 #if __WORDSIZE == 64 || _WIN64 || __x86_64__
164 unsigned long long v1
, v2
, v4
, v8
, *t
;
165 unsigned long long v10
, v20
, v40
, v80
;
166 unsigned char c17
, c18
, c20
, c24
;
168 t
= (unsigned long long *)tbl
;
170 v1
= c
* 0x0100010001000100ull
;
171 v2
= c2
* 0x0101000001010000ull
;
172 v4
= c4
* 0x0101010100000000ull
;
173 v8
= c8
* 0x0101010101010101ull
;
179 c17
= (c8
<< 1) ^ ((c8
& 0x80) ? 0x1d : 0); //Mult by GF{2}
180 c18
= (c17
<< 1) ^ ((c17
& 0x80) ? 0x1d : 0); //Mult by GF{2}
181 c20
= (c18
<< 1) ^ ((c18
& 0x80) ? 0x1d : 0); //Mult by GF{2}
182 c24
= (c20
<< 1) ^ ((c20
& 0x80) ? 0x1d : 0); //Mult by GF{2}
184 v10
= c17
* 0x0100010001000100ull
;
185 v20
= c18
* 0x0101000001010000ull
;
186 v40
= c20
* 0x0101010100000000ull
;
187 v80
= c24
* 0x0101010101010101ull
;
189 v40
= v10
^ v20
^ v40
;
193 #else // 32-bit or other
194 unsigned char c3
, c5
, c6
, c7
, c9
, c10
, c11
, c12
, c13
, c14
, c15
;
195 unsigned char c17
, c18
, c19
, c20
, c21
, c22
, c23
, c24
, c25
, c26
, c27
, c28
, c29
, c30
,
228 c17
= (c8
<< 1) ^ ((c8
& 0x80) ? 0x1d : 0); //Mult by GF{2}
229 c18
= (c17
<< 1) ^ ((c17
& 0x80) ? 0x1d : 0); //Mult by GF{2}
231 c20
= (c18
<< 1) ^ ((c18
& 0x80) ? 0x1d : 0); //Mult by GF{2}
235 c24
= (c20
<< 1) ^ ((c20
& 0x80) ? 0x1d : 0); //Mult by GF{2}
261 #endif //__WORDSIZE == 64 || _WIN64 || __x86_64__
264 void gf_vect_dot_prod_base(int len
, int vlen
, unsigned char *v
,
265 unsigned char **src
, unsigned char *dest
)
269 for (i
= 0; i
< len
; i
++) {
271 for (j
= 0; j
< vlen
; j
++)
272 s
^= gf_mul(src
[j
][i
], v
[j
* 32 + 1]);
278 void gf_vect_mad_base(int len
, int vec
, int vec_i
,
279 unsigned char *v
, unsigned char *src
, unsigned char *dest
)
283 for (i
= 0; i
< len
; i
++) {
285 s
^= gf_mul(src
[i
], v
[vec_i
* 32 + 1]);
290 void ec_encode_data_base(int len
, int srcs
, int dests
, unsigned char *v
,
291 unsigned char **src
, unsigned char **dest
)
296 for (l
= 0; l
< dests
; l
++) {
297 for (i
= 0; i
< len
; i
++) {
299 for (j
= 0; j
< srcs
; j
++)
300 s
^= gf_mul(src
[j
][i
], v
[j
* 32 + l
* srcs
* 32 + 1]);
307 void ec_encode_data_update_base(int len
, int k
, int rows
, int vec_i
, unsigned char *v
,
308 unsigned char *data
, unsigned char **dest
)
313 for (l
= 0; l
< rows
; l
++) {
314 for (i
= 0; i
< len
; i
++) {
316 s
^= gf_mul(data
[i
], v
[vec_i
* 32 + l
* k
* 32 + 1]);
323 void gf_vect_mul_base(int len
, unsigned char *a
, unsigned char *src
, unsigned char *dest
)
325 //2nd element of table array is ref value used to fill it in
326 unsigned char c
= a
[1];
328 *dest
++ = gf_mul(c
, *src
++);
338 struct slver gf_vect_mul_init_slver_00020035
;
339 struct slver gf_vect_mul_init_slver
= { 0x0035, 0x02, 0x00 };
341 struct slver ec_encode_data_base_slver_00010135
;
342 struct slver ec_encode_data_base_slver
= { 0x0135, 0x01, 0x00 };
344 struct slver gf_vect_mul_base_slver_00010136
;
345 struct slver gf_vect_mul_base_slver
= { 0x0136, 0x01, 0x00 };
347 struct slver gf_vect_dot_prod_base_slver_00010137
;
348 struct slver gf_vect_dot_prod_base_slver
= { 0x0137, 0x01, 0x00 };
350 struct slver gf_mul_slver_00000214
;
351 struct slver gf_mul_slver
= { 0x0214, 0x00, 0x00 };
353 struct slver gf_invert_matrix_slver_00000215
;
354 struct slver gf_invert_matrix_slver
= { 0x0215, 0x00, 0x00 };
356 struct slver gf_gen_rs_matrix_slver_00000216
;
357 struct slver gf_gen_rs_matrix_slver
= { 0x0216, 0x00, 0x00 };
359 struct slver gf_gen_cauchy1_matrix_slver_00000217
;
360 struct slver gf_gen_cauchy1_matrix_slver
= { 0x0217, 0x00, 0x00 };