ceph/src/isa-l/erasure_code/gf_inverse_test.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 <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>             // for memset, memcmp
  33 #include <assert.h>
  34
  35 #include "erasure_code.h"
  36
  37 #define TEST_LEN 8192
  38
  39 #ifndef TEST_SOURCES
  40 # define TEST_SOURCES  128
  41 #endif
  42 #ifndef RANDOMS
  43 # define RANDOMS 200
  44 #endif
  45
  46 #define KMAX TEST_SOURCES
  47
  48 typedef unsigned char u8;
  49
  50 void matrix_mult(u8 * a, u8 * b, u8 * c, int n)
  51 {
  52         int i, j, k;
  53         u8 d;
  54
  55         for (i = 0; i < n; i++) {
  56                 for (j = 0; j < n; j++) {
  57                         d = 0;
  58                         for (k = 0; k < n; k++) {
  59                                 d ^= gf_mul(a[n * i + k], b[n * k + j]);
  60                         }
  61                         c[i * n + j] = d;
  62                 }
  63         }
  64 }
  65
  66 void print_matrix(u8 * a, int n)
  67 {
  68         int i, j;
  69
  70         for (i = 0; i < n; i++) {
  71                 for (j = 0; j < n; j++) {
  72                         printf(" %2x", a[i * n + j]);
  73                 }
  74                 printf("\n");
  75         }
  76         printf("\n");
  77 }
  78
  79 int is_ident(u8 * a, const int n)
  80 {
  81         int i, j;
  82         u8 c;
  83         for (i = 0; i < n; i++) {
  84                 for (j = 0; j < n; j++) {
  85                         c = *a++;
  86                         if (i == j)
  87                                 c--;
  88                         if (c != 0)
  89                                 return -1;
  90                 }
  91         }
  92         return 0;
  93 }
  94
  95 int inv_test(u8 * in, u8 * inv, u8 * sav, int n)
  96 {
  97         memcpy(sav, in, n * n);
  98
  99         if (gf_invert_matrix(in, inv, n)) {
 100                 printf("Given singular matrix\n");
 101                 print_matrix(sav, n);
 102                 return -1;
 103         }
 104
 105         matrix_mult(inv, sav, in, n);
 106
 107         if (is_ident(in, n)) {
 108                 printf("fail\n");
 109                 print_matrix(sav, n);
 110                 print_matrix(inv, n);
 111                 print_matrix(in, n);
 112                 return -1;
 113         }
 114         putchar('.');
 115
 116         return 0;
 117 }
 118
 119 int main(int argc, char *argv[])
 120 {
 121         int i, k, t;
 122         u8 *test_mat, *save_mat, *invr_mat;
 123
 124         u8 test1[] = { 1, 1, 6,
 125                 1, 1, 1,
 126                 7, 1, 9
 127         };
 128
 129         u8 test2[] = { 0, 1, 6,
 130                 1, 0, 1,
 131                 0, 1, 9
 132         };
 133
 134         u8 test3[] = { 0, 0, 1,
 135                 1, 0, 0,
 136                 0, 1, 1
 137         };
 138
 139         u8 test4[] = { 0, 1, 6, 7,
 140                 1, 1, 0, 0,
 141                 0, 1, 2, 3,
 142                 3, 2, 2, 3
 143         };                      // = row3+3*row2
 144
 145         printf("gf_inverse_test: max=%d ", KMAX);
 146
 147         test_mat = malloc(KMAX * KMAX);
 148         save_mat = malloc(KMAX * KMAX);
 149         invr_mat = malloc(KMAX * KMAX);
 150
 151         if (NULL == test_mat || NULL == save_mat || NULL == invr_mat)
 152                 return -1;
 153
 154         // Test with lots of leading 1's
 155         k = 3;
 156         memcpy(test_mat, test1, k * k);
 157         if (inv_test(test_mat, invr_mat, save_mat, k))
 158                 return -1;
 159
 160         // Test with leading zeros
 161         k = 3;
 162         memcpy(test_mat, test2, k * k);
 163         if (inv_test(test_mat, invr_mat, save_mat, k))
 164                 return -1;
 165
 166         // Test 3
 167         k = 3;
 168         memcpy(test_mat, test3, k * k);
 169         if (inv_test(test_mat, invr_mat, save_mat, k))
 170                 return -1;
 171
 172         // Test 4 - try a singular matrix
 173         k = 4;
 174         memcpy(test_mat, test4, k * k);
 175         if (!gf_invert_matrix(test_mat, invr_mat, k)) {
 176                 printf("Fail: didn't catch singular matrix\n");
 177                 print_matrix(test4, 4);
 178                 return -1;
 179         }
 180         // Do random test of size KMAX
 181         k = KMAX;
 182
 183         for (i = 0; i < k * k; i++)
 184                 test_mat[i] = save_mat[i] = rand();
 185
 186         if (gf_invert_matrix(test_mat, invr_mat, k)) {
 187                 printf("rand picked a singular matrix, try again\n");
 188                 return -1;
 189         }
 190
 191         matrix_mult(invr_mat, save_mat, test_mat, k);
 192
 193         if (is_ident(test_mat, k)) {
 194                 printf("fail\n");
 195                 print_matrix(save_mat, k);
 196                 print_matrix(invr_mat, k);
 197                 print_matrix(test_mat, k);
 198                 return -1;
 199         }
 200         // Do Randoms.  Random size and coefficients
 201         for (t = 0; t < RANDOMS; t++) {
 202                 k = rand() % KMAX;
 203
 204                 for (i = 0; i < k * k; i++)
 205                         test_mat[i] = save_mat[i] = rand();
 206
 207                 if (gf_invert_matrix(test_mat, invr_mat, k))
 208                         continue;
 209
 210                 matrix_mult(invr_mat, save_mat, test_mat, k);
 211
 212                 if (is_ident(test_mat, k)) {
 213                         printf("fail rand k=%d\n", k);
 214                         print_matrix(save_mat, k);
 215                         print_matrix(invr_mat, k);
 216                         print_matrix(test_mat, k);
 217                         return -1;
 218                 }
 219                 if (0 == (t % 8))
 220                         putchar('.');
 221         }
 222
 223         printf(" Pass\n");
 224         return 0;
 225 }