line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
1
|
|
|
|
|
|
|
package Algorithm::GaussianElimination::GF2; |
2
|
|
|
|
|
|
|
|
3
|
|
|
|
|
|
|
our $VERSION = '0.02'; |
4
|
|
|
|
|
|
|
|
5
|
1
|
|
|
1
|
|
746
|
use strict; |
|
1
|
|
|
|
|
3
|
|
|
1
|
|
|
|
|
35
|
|
6
|
1
|
|
|
1
|
|
6
|
use warnings; |
|
1
|
|
|
|
|
2
|
|
|
1
|
|
|
|
|
1849
|
|
7
|
|
|
|
|
|
|
|
8
|
|
|
|
|
|
|
sub new { |
9
|
50
|
|
|
50
|
1
|
189088
|
my $class = shift; |
10
|
50
|
|
|
|
|
183
|
my $self = { eqs => [] }; |
11
|
50
|
|
|
|
|
314
|
bless $self, $class; |
12
|
|
|
|
|
|
|
} |
13
|
|
|
|
|
|
|
|
14
|
|
|
|
|
|
|
sub _add_equation { |
15
|
1275
|
|
|
1275
|
|
1530
|
my ($self, $eq) = @_; |
16
|
1275
|
|
|
|
|
1257
|
push @{$self->{eqs}}, $eq; |
|
1275
|
|
|
|
|
2877
|
|
17
|
|
|
|
|
|
|
} |
18
|
|
|
|
|
|
|
|
19
|
|
|
|
|
|
|
sub new_equation { |
20
|
1275
|
|
|
1275
|
1
|
23159
|
my $self = shift; |
21
|
1275
|
|
|
|
|
3315
|
my $eq = Algorithm::GaussianElimination::GF2::Equation->_new(@_); |
22
|
1275
|
|
|
|
|
6335
|
$self->_add_equation($eq); |
23
|
1275
|
|
|
|
|
6935
|
$eq; |
24
|
|
|
|
|
|
|
} |
25
|
|
|
|
|
|
|
|
26
|
|
|
|
|
|
|
*add_equation = \&new_equation; |
27
|
|
|
|
|
|
|
|
28
|
|
|
|
|
|
|
sub _first_1 { |
29
|
2036
|
|
|
2036
|
|
4053
|
pos($_[0]) = 0; |
30
|
2036
|
100
|
|
|
|
7826
|
$_[0] =~ /[^\0]/g or return length($_[0]) * 8; |
31
|
2005
|
|
|
|
|
2908
|
my $end = pos($_[0]) * 8 - 1; |
32
|
2005
|
|
|
|
|
3011
|
for my $i (($end - 7) .. $end) { |
33
|
8624
|
100
|
|
|
|
17042
|
return $i if vec($_[0], $i, 1); |
34
|
|
|
|
|
|
|
} |
35
|
|
|
|
|
|
|
} |
36
|
|
|
|
|
|
|
|
37
|
|
|
|
|
|
|
sub dump { |
38
|
0
|
|
|
0
|
0
|
0
|
my $self = shift; |
39
|
0
|
|
|
|
|
0
|
my $eqs = $self->{eqs}; |
40
|
0
|
|
|
|
|
0
|
my $len = 0; |
41
|
0
|
|
|
|
|
0
|
for (@$eqs) { |
42
|
0
|
0
|
|
|
|
0
|
$len = $_->[2] if $_->[2] > $len; |
43
|
|
|
|
|
|
|
} |
44
|
0
|
|
|
|
|
0
|
printf "GF(2) system of %d equations and %d variables\n", scalar(@$eqs), $len; |
45
|
0
|
|
|
|
|
0
|
for (@$eqs) { |
46
|
0
|
|
|
|
|
0
|
$_->[2] = $len; |
47
|
0
|
|
|
|
|
0
|
$_->dump; |
48
|
|
|
|
|
|
|
} |
49
|
0
|
|
|
|
|
0
|
print "\n"; |
50
|
|
|
|
|
|
|
} |
51
|
|
|
|
|
|
|
|
52
|
|
|
|
|
|
|
sub solve { |
53
|
50
|
|
|
50
|
1
|
283
|
my $self = shift; |
54
|
50
|
|
|
|
|
84
|
my $eqs = $self->{eqs}; |
55
|
50
|
|
|
|
|
79
|
my $len = 0; |
56
|
50
|
|
|
|
|
97
|
for my $eq (@$eqs) { |
57
|
1275
|
100
|
|
|
|
2323
|
$len = $eq->[2] if $eq->[2] > $len; |
58
|
|
|
|
|
|
|
} |
59
|
50
|
|
|
|
|
87
|
my @v; |
60
|
50
|
|
|
|
|
86
|
for my $eq (@$eqs) { |
61
|
1275
|
|
|
|
|
1762
|
push @v, $eq->[0]; |
62
|
1275
|
|
|
|
|
2671
|
vec($v[-1], $len, 1) = $eq->[1]; |
63
|
|
|
|
|
|
|
} |
64
|
|
|
|
|
|
|
|
65
|
50
|
|
|
|
|
131
|
for my $i (0..$#v) { |
66
|
1255
|
|
|
|
|
1737
|
my $v = $v[$i]; |
67
|
1255
|
|
|
|
|
2685
|
my $ix = _first_1($v); |
68
|
1255
|
100
|
|
|
|
2214
|
if ($ix < $len) { |
|
|
100
|
|
|
|
|
|
69
|
1219
|
|
|
|
|
2116
|
for my $j (($i + 1)..$#v) { |
70
|
20773
|
100
|
|
|
|
40013
|
$v[$j] ^= $v if vec($v[$j], $ix, 1); |
71
|
|
|
|
|
|
|
} |
72
|
|
|
|
|
|
|
} |
73
|
|
|
|
|
|
|
elsif (vec($v, $len, 1)) { |
74
|
|
|
|
|
|
|
# inconsistent! |
75
|
|
|
|
|
|
|
return |
76
|
20
|
|
|
|
|
129
|
} |
77
|
|
|
|
|
|
|
} |
78
|
|
|
|
|
|
|
|
79
|
30
|
|
|
|
|
43
|
my @sol; |
80
|
30
|
|
|
|
|
120
|
$sol[$len] = 1; |
81
|
30
|
|
|
|
|
61
|
for my $v (reverse @v) { |
82
|
781
|
|
|
|
|
1189
|
my $ix = _first_1($v); |
83
|
781
|
100
|
|
|
|
1474
|
if ($ix < $len) { |
84
|
766
|
|
|
|
|
802
|
my $sol = 0; |
85
|
766
|
|
|
|
|
1051
|
for my $i (($ix + 1) .. $len) { |
86
|
14064
|
100
|
|
|
|
29469
|
$sol ^= vec($v, $i, 1) if $sol[$i]; |
87
|
|
|
|
|
|
|
} |
88
|
766
|
|
|
|
|
1698
|
$sol[$ix] = $sol; |
89
|
|
|
|
|
|
|
} |
90
|
|
|
|
|
|
|
} |
91
|
|
|
|
|
|
|
|
92
|
30
|
|
|
|
|
43
|
my @free; |
93
|
30
|
|
|
|
|
59
|
for my $i (0 .. $len - 1) { |
94
|
781
|
100
|
|
|
|
1302
|
unless (defined $sol[$i]) { |
95
|
15
|
|
|
|
|
42
|
push @free, $i; |
96
|
15
|
|
|
|
|
28
|
$sol[$i] = 0; |
97
|
|
|
|
|
|
|
} |
98
|
|
|
|
|
|
|
} |
99
|
30
|
|
|
|
|
58
|
pop @sol; |
100
|
|
|
|
|
|
|
|
101
|
30
|
50
|
|
|
|
342
|
return \@sol unless wantarray; |
102
|
|
|
|
|
|
|
|
103
|
0
|
|
|
|
|
0
|
my @base0; |
104
|
0
|
|
|
|
|
0
|
for my $free (@free) { |
105
|
0
|
|
|
|
|
0
|
my @sol0; |
106
|
0
|
|
|
|
|
0
|
$sol0[$_] = 0 for @free; |
107
|
0
|
|
|
|
|
0
|
$sol0[$free] = 1; |
108
|
0
|
|
|
|
|
0
|
for my $v (reverse @v) { |
109
|
0
|
|
|
|
|
0
|
my $ix = _first_1($v); |
110
|
0
|
0
|
|
|
|
0
|
if ($ix < $len) { |
111
|
0
|
|
|
|
|
0
|
my $sol = 0; |
112
|
0
|
|
|
|
|
0
|
for my $i (($ix + 1) .. ($len - 1)) { |
113
|
0
|
0
|
|
|
|
0
|
$sol ^= vec($v, $i, 1) if $sol0[$i]; |
114
|
|
|
|
|
|
|
} |
115
|
0
|
|
|
|
|
0
|
$sol0[$ix] = $sol; |
116
|
|
|
|
|
|
|
} |
117
|
|
|
|
|
|
|
} |
118
|
0
|
|
|
|
|
0
|
push @base0, \@sol0; |
119
|
|
|
|
|
|
|
} |
120
|
0
|
|
|
|
|
0
|
return \@sol, @base0; |
121
|
|
|
|
|
|
|
} |
122
|
|
|
|
|
|
|
|
123
|
|
|
|
|
|
|
package Algorithm::GaussianElimination::GF2::Equation; |
124
|
|
|
|
|
|
|
|
125
|
|
|
|
|
|
|
sub _new { |
126
|
1275
|
|
|
1275
|
|
1761
|
my $class = shift; |
127
|
1275
|
|
|
|
|
2695
|
my $self = ['', 0, 0]; |
128
|
1275
|
|
|
|
|
3056
|
bless $self, $class; |
129
|
1275
|
50
|
|
|
|
2593
|
if (@_) { |
130
|
1275
|
100
|
|
|
|
2422
|
$self->[1] = (pop @_ ? 1 : 0); |
131
|
1275
|
|
|
|
|
2372
|
for my $ix (0..$#_) { |
132
|
42925
|
|
|
|
|
93713
|
vec($self->[0], $ix, 1) = $_[$ix] |
133
|
|
|
|
|
|
|
} |
134
|
1275
|
|
|
|
|
2176
|
$self->[2] = @_; |
135
|
|
|
|
|
|
|
} |
136
|
|
|
|
|
|
|
$self |
137
|
1275
|
|
|
|
|
2239
|
} |
138
|
|
|
|
|
|
|
|
139
|
|
|
|
|
|
|
sub a { |
140
|
0
|
|
|
0
|
|
0
|
my ($self, $ix, $v) = @_; |
141
|
0
|
0
|
|
|
|
0
|
if (defined $v) { |
142
|
0
|
0
|
|
|
|
0
|
$self->[2] = $ix + 1 if $self->[2] <= $ix; |
143
|
0
|
|
|
|
|
0
|
return vec($self->[0], $ix, 1) = $v; |
144
|
|
|
|
|
|
|
} |
145
|
0
|
|
|
|
|
0
|
return vec($self->[0], $ix, 1); |
146
|
|
|
|
|
|
|
} |
147
|
|
|
|
|
|
|
|
148
|
|
|
|
|
|
|
sub as { |
149
|
0
|
|
|
0
|
|
0
|
my $self = shift; |
150
|
0
|
|
|
|
|
0
|
map { vec($self->[0], $_, 1) } 0..($self->[2] - 1); |
|
0
|
|
|
|
|
0
|
|
151
|
|
|
|
|
|
|
} |
152
|
|
|
|
|
|
|
|
153
|
|
|
|
|
|
|
sub b { |
154
|
0
|
|
|
0
|
|
0
|
my ($self, $v) = @_; |
155
|
0
|
0
|
|
|
|
0
|
if (defined $v) { |
156
|
0
|
0
|
|
|
|
0
|
return $self->[1] = ($v ? 1 : 0); |
157
|
|
|
|
|
|
|
} |
158
|
0
|
|
|
|
|
0
|
return $self->[1]; |
159
|
|
|
|
|
|
|
} |
160
|
|
|
|
|
|
|
|
161
|
0
|
|
|
0
|
|
0
|
sub len { shift->[2] } |
162
|
|
|
|
|
|
|
|
163
|
|
|
|
|
|
|
sub dump { |
164
|
0
|
|
|
0
|
|
0
|
my $self = shift; |
165
|
0
|
|
|
|
|
0
|
my $last = $self->[2] - 1; |
166
|
0
|
|
|
|
|
0
|
my @a = map vec($self->[0], $_, 1), 0.. $last; |
167
|
0
|
|
|
|
|
0
|
print "@a | $self->[1]\n"; |
168
|
|
|
|
|
|
|
} |
169
|
|
|
|
|
|
|
|
170
|
|
|
|
|
|
|
sub test_solution { |
171
|
781
|
|
|
781
|
|
1406
|
my $self = shift; |
172
|
781
|
|
|
|
|
1189
|
my $v = $self->[0]; |
173
|
781
|
|
|
|
|
911
|
my $len = $self->[2]; |
174
|
781
|
|
|
|
|
828
|
my $b = 0; |
175
|
781
|
|
|
|
|
1688
|
for my $ix (0..$#_) { |
176
|
27395
|
100
|
|
|
|
54127
|
$b ^= vec($v, $ix, 1) if $_[$ix]; |
177
|
|
|
|
|
|
|
} |
178
|
781
|
|
|
|
|
2966
|
return ($b == $self->[1]); |
179
|
|
|
|
|
|
|
} |
180
|
|
|
|
|
|
|
|
181
|
|
|
|
|
|
|
sub clone { |
182
|
0
|
|
|
0
|
|
|
my $self = shift; |
183
|
0
|
|
|
|
|
|
my @self = @$self; |
184
|
0
|
|
|
|
|
|
bless \@self, ref $self; |
185
|
|
|
|
|
|
|
} |
186
|
|
|
|
|
|
|
|
187
|
|
|
|
|
|
|
1; |
188
|
|
|
|
|
|
|
__END__ |