Botan  1.11.15
src/lib/pubkey/mce/binary_matrix.cpp
Go to the documentation of this file.
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