ceph/src/erasure-code/shec/determinant.c

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2014 Fujitsu Laboratories
   7  *
   8  * Author: Takanori Nakao <nakao.takanori@jp.fujitsu.com>
   9  * Author: Takeshi Miyamae <miyamae.takeshi@jp.fujitsu.com>
  10  *
  11  *  This library is free software; you can redistribute it and/or
  12  *  modify it under the terms of the GNU Lesser General Public
  13  *  License as published by the Free Software Foundation; either
  14  *  version 2.1 of the License, or (at your option) any later version.
  15  *
  16  */
  17
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21
  22 #include "jerasure/include/galois.h"
  23
  24 void print_matrix(int *mat, int dim)
  25 {
  26   int i, j;
  27
  28   for (i=0; i<dim; i++) {
  29     for (j=0; j<dim; j++) {
  30       printf("%d ", mat[i*dim+j]);
  31     }
  32     printf("\n");
  33   }
  34 }
  35
  36 int calc_determinant(int *matrix, int dim)
  37 {
  38   int i, j, k, *mat, det = 1, coeff_1, coeff_2, *row;
  39
  40 //  print_matrix(matrix, dim);
  41
  42   mat = (int *)malloc(sizeof(int)*dim*dim);
  43   if (mat == NULL) {
  44     printf("mat malloc err\n");
  45     goto out0;
  46   }
  47   memcpy((int *)mat, (int *)matrix, sizeof(int)*dim*dim);
  48
  49   row = (int *)malloc(sizeof(int)*dim);
  50   if (row == NULL) {
  51     printf("row malloc err\n");
  52     goto out1;
  53   }
  54
  55   for (i=0; i<dim; i++) {
  56     if (mat[i*dim+i] == 0) {
  57       for (k=i+1; k<dim; k++) {
  58         if (mat[k*dim+i] != 0) {
  59           memcpy((int *)row, (int *)&mat[k*dim], sizeof(int)*dim);
  60           memcpy((int *)&mat[k*dim], (int *)&mat[i*dim], sizeof(int)*dim);
  61           memcpy((int *)&mat[i*dim], (int *)row, sizeof(int)*dim);
  62           break;
  63         }
  64       }
  65       if (k == dim) {
  66         det = 0;
  67         goto out2;
  68       }
  69     }
  70     coeff_1 = mat[i*dim+i];
  71     for (j=i; j<dim; j++) {
  72       mat[i*dim+j] = galois_single_divide(mat[i*dim+j], coeff_1, 8);
  73     }
  74     for (k=i+1; k<dim; k++) {
  75       if (mat[k*dim+i] != 0) {
  76         coeff_2 = mat[k*dim+i];
  77         for (j=i; j<dim; j++) {
  78           mat[k*dim+j] = mat[k*dim+j] ^ galois_single_multiply(mat[i*dim+j], coeff_2, 8);
  79         }
  80       }
  81     }
  82     det = galois_single_multiply(det, coeff_1, 8);
  83   }
  84 //  print_matrix(mat, dim);
  85
  86 out2:
  87   free(row);
  88
  89 out1:
  90   free(mat);
  91
  92 out0:
  93   return det;
  94 }