Botan
1.11.15
|
00001 /** 00002 * (C) Copyright Projet SECRET, INRIA, Rocquencourt 00003 * (C) Bhaskar Biswas and Nicolas Sendrier 00004 * 00005 * (C) 2014 cryptosource GmbH 00006 * (C) 2014 Falko Strenzke fstrenzke@cryptosource.de 00007 * 00008 * Botan is released under the Simplified BSD License (see license.txt) 00009 * 00010 */ 00011 00012 #include <botan/internal/binary_matrix.h> 00013 #include <botan/internal/xor_buf.h> 00014 00015 namespace Botan { 00016 00017 binary_matrix::binary_matrix (u32bit rown, u32bit coln) 00018 { 00019 m_coln = coln; 00020 m_rown = rown; 00021 m_rwdcnt = (1 + (m_coln - 1) / BITS_PER_U32); 00022 m_elem = std::vector<u32bit>(m_rown * m_rwdcnt); 00023 } 00024 00025 void binary_matrix::row_xor(u32bit a, u32bit b) 00026 { 00027 u32bit i; 00028 for(i=0;i<m_rwdcnt;i++) 00029 { 00030 m_elem[a*m_rwdcnt+i]^=m_elem[b*m_rwdcnt+i]; 00031 } 00032 } 00033 00034 //the matrix is reduced from LSB...(from right) 00035 secure_vector<int> binary_matrix::row_reduced_echelon_form() 00036 { 00037 u32bit i, failcnt, findrow, max=m_coln - 1; 00038 00039 secure_vector<int> perm(m_coln); 00040 for(i=0;i<m_coln;i++) 00041 { 00042 perm[i]=i;//initialize permutation. 00043 } 00044 failcnt = 0; 00045 00046 for(i=0;i<m_rown;i++,max--) 00047 { 00048 findrow=0; 00049 for(u32bit j=i;j<m_rown;j++) 00050 { 00051 if(coef(j,max)) 00052 { 00053 if (i!=j)//not needed as ith row is 0 and jth row is 1. 00054 row_xor(i,j);//xor to the row.(swap)? 00055 findrow=1; 00056 break; 00057 }//largest value found (end if) 00058 } 00059 00060 if(!findrow)//if no row with a 1 found then swap last column and the column with no 1 down. 00061 { 00062 perm[m_coln - m_rown - 1 - failcnt] = max; 00063 failcnt++; 00064 if (!max) 00065 { 00066 //CSEC_FREE_MEM_CHK_SET_NULL(*p_perm); 00067 //CSEC_THR_RETURN(); 00068 perm.resize(0); 00069 } 00070 i--; 00071 } 00072 else 00073 { 00074 perm[i+m_coln - m_rown] = max; 00075 for(u32bit j=i+1;j<m_rown;j++)//fill the column downwards with 0's 00076 { 00077 if(coef(j,(max))) 00078 { 00079 row_xor(j,i);//check the arg. order. 00080 } 00081 } 00082 00083 for(int j=i-1;j>=0;j--)//fill the column with 0's upwards too. 00084 { 00085 if(coef(j,(max))) 00086 { 00087 row_xor(j,i); 00088 } 00089 } 00090 } 00091 }//end for(i) 00092 return perm; 00093 } 00094 00095 00096 } // end namespace Botan