ceph/src/spdk/isa-l/erasure_code/ec_base.c

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