1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
/**
* (C) Copyright Projet SECRET, INRIA, Rocquencourt
* (C) Bhaskar Biswas and Nicolas Sendrier
*
* (C) 2014 cryptosource GmbH
* (C) 2014 Falko Strenzke fstrenzke@cryptosource.de
*
* Distributed under the terms of the Botan license
*
*/
#include <botan/internal/binary_matrix.h>
#include <botan/internal/xor_buf.h>
namespace Botan {
binary_matrix::binary_matrix (u32bit rown, u32bit coln)
{
m_coln = coln;
m_rown = rown;
m_rwdcnt = (1 + (m_coln - 1) / BITS_PER_U32);
m_alloc_size = m_rown * (*this).m_rwdcnt * sizeof (u32bit);
m_elem = std::vector<u32bit>((*this).m_alloc_size/4);
}
void binary_matrix::row_xor(u32bit a, u32bit b)
{
u32bit i;
for(i=0;i<m_rwdcnt;i++)
{
m_elem[a*m_rwdcnt+i]^=m_elem[b*m_rwdcnt+i];
}
}
//the matrix is reduced from LSB...(from right)
secure_vector<int> binary_matrix::row_reduced_echelon_form()
{
u32bit i, failcnt, findrow, max=m_coln - 1;
secure_vector<int> perm(m_coln);
for(i=0;i<m_coln;i++)
{
perm[i]=i;//initialize permutation.
}
failcnt = 0;
for(i=0;i<m_rown;i++,max--)
{
findrow=0;
for(u32bit j=i;j<m_rown;j++)
{
if(coef(j,max))
{
if (i!=j)//not needed as ith row is 0 and jth row is 1.
row_xor(i,j);//xor to the row.(swap)?
findrow=1;
break;
}//largest value found (end if)
}
if(!findrow)//if no row with a 1 found then swap last column and the column with no 1 down.
{
perm[m_coln - m_rown - 1 - failcnt] = max;
failcnt++;
if (!max)
{
//CSEC_FREE_MEM_CHK_SET_NULL(*p_perm);
//CSEC_THR_RETURN();
perm.resize(0);
}
i--;
}
else
{
perm[i+m_coln - m_rown] = max;
for(u32bit j=i+1;j<m_rown;j++)//fill the column downwards with 0's
{
if(coef(j,(max)))
{
row_xor(j,i);//check the arg. order.
}
}
for(int j=i-1;j>=0;j--)//fill the column with 0's upwards too.
{
if(coef(j,(max)))
{
row_xor(j,i);
}
}
}
}//end for(i)
return perm;
}
} // end namespace Botan
|
