00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include <stdio.h>
00022 #include <stdlib.h>
00023 #include <string.h>
00024
00025 #include "matrix.h"
00026
00027
00029
00030
00031
00032
00033 binmat_t mat_ini (int rown, int coln)
00034 {
00035 binmat_t A;
00036
00037 A = (binmat_t) malloc (sizeof (struct matrix));
00038 A->coln = coln;
00039 A->rown = rown;
00040 A->rwdcnt = (1 + (coln - 1) / BITS_PER_LONG);
00041 A->alloc_size = rown * A->rwdcnt * sizeof (unsigned long);
00042 A->elem = (unsigned long *)malloc(A->alloc_size);
00043 return A;
00044 }
00045
00046
00047 binmat_t mat_ini_from_string(int rown, int coln, const unsigned char * s)
00048 {
00049 binmat_t A;
00050
00051 A = (binmat_t) malloc (sizeof (struct matrix));
00052 A->coln = coln;
00053 A->rown = rown;
00054 A->rwdcnt = (1 + (coln - 1) / BITS_PER_LONG);
00055 A->alloc_size = rown * A->rwdcnt * sizeof (unsigned long);
00056 A->elem = (unsigned long *) s;
00057 return A;
00058 }
00059
00060 void mat_free(binmat_t A)
00061 {
00062 free(A->elem);
00063 free(A);
00064 }
00065
00066 binmat_t mat_copy(binmat_t A)
00067 {
00068 binmat_t X;
00069 int i;
00070
00071 X=mat_ini(A->rown,A->coln);
00072 for(i=0;i<((A->rwdcnt)*(A->rown));i++)
00073 X->elem[i]=A->elem[i];
00074
00075 return(X);
00076 }
00077
00078 binmat_t mat_rowxor(binmat_t A,int a, int b)
00079 {
00080 int i;
00081 for(i=0;i<A->rwdcnt;i++)
00082 {
00083 A->elem[a*A->rwdcnt+i]^=A->elem[b*A->rwdcnt+i];
00084 }
00085 return A;
00086 }
00087
00088
00089
00090
00091 int * mat_rref(binmat_t A)
00092 {
00093 int i,j,failcnt,findrow,max=A->coln - 1;
00094 int *perm;
00095
00096 perm = malloc(A->coln * sizeof(int));
00097
00098 for(i=0;i<A->coln;i++)
00099 perm[i]=i;
00100 failcnt = 0;
00101
00102 for(i=0;i<A->rown;i++,max--)
00103 {
00104 findrow=0;
00105 for(j=i;j<A->rown;j++)
00106 {
00107 if(mat_coeff(A,j,max))
00108 {
00109
00110 if (i!=j)
00111 A=mat_rowxor(A,i,j);
00112 findrow=1;
00113 break;
00114 }
00115
00116 }
00117
00118 if(!findrow)
00119 {
00120 perm[A->coln - A->rown - 1 - failcnt] = max;
00121 failcnt++;
00122 if (!max)
00123 {
00124 return NULL;
00125 }
00126 i--;
00127 }
00128 else
00129 {
00130 perm[i+A->coln - A->rown] = max;
00131 for(j=i+1;j<A->rown;j++)
00132 {
00133 if(mat_coeff(A,j,(max)))
00134 A=mat_rowxor(A,j,i);
00135 }
00136
00137 for(j=i-1;j>=0;j--)
00138 {
00139 if(mat_coeff(A,j,(max)))
00140 A=mat_rowxor(A,j,i);
00141 }
00142 }
00143 }
00144
00145 return(perm);
00146 }
00147
00148 void mat_vec_mul(unsigned long *cR, unsigned char *x, binmat_t A)
00149 {
00150 int i,j;
00151 unsigned long *pt;
00152
00153 memset(cR,0,A->rwdcnt*sizeof(long));
00154 pt = A->elem;
00155 for(i=0;i<A->rown;i++)
00156 {
00157 if((x[i/8]>>(i%8))&1)
00158 for (j = 0; j < A->rwdcnt; ++j)
00159 cR[j] ^= *pt++;
00160 else
00161 pt += A->rwdcnt;
00162 }
00163 }
00164
00165 binmat_t mat_mul(binmat_t A, binmat_t B)
00166 {
00167 binmat_t C;
00168 int i,j,k;
00169
00170 if (A->coln != B->rown)
00171 exit(0);
00172
00173 C = mat_ini(A->rown, B->coln);
00174 memset(C->elem,0,C->alloc_size);
00175 for(i=0;i<A->rown;i++)
00176 for(j=0;j<B->coln;j++)
00177 for (k = 0; k < A->coln; ++k)
00178 if (mat_coeff(A,i,k) && mat_coeff(B,k,j))
00179 mat_change_coeff(C,i,j);
00180
00181 return C;
00182 }
00183