1 |
=head1 NAME |
2 |
|
3 |
Algorithm::FEC - Forward Error Correction using Vandermonde Matrices |
4 |
|
5 |
=head1 SYNOPSIS |
6 |
|
7 |
use Algorithm::FEC; |
8 |
|
9 |
=head1 DESCRIPTION |
10 |
|
11 |
This module is an interface to the fec library by Luigi Rizzo et al., see |
12 |
the file README.fec in the distribution for more details. |
13 |
|
14 |
This library implements a simple (C<encoded_blocks>,C<data_blocks>) |
15 |
erasure code based on Vandermonde matrices. The encoder takes |
16 |
C<data_blocks> blocks of size C<block_size> each, and is able to produce |
17 |
up to C<encoded_blocks> different encoded blocks, numbered from C<0> |
18 |
to C<encoded_blocks-1>, such that any subset of C<data_blocks> members |
19 |
permits reconstruction of the original data. |
20 |
|
21 |
Allowed values for C<data_blocks> and C<encoded_blocks> must obey the |
22 |
following equation: |
23 |
|
24 |
data_blocks <= encoded_blocks <= MAXBLOCKS |
25 |
|
26 |
Where C<MAXBLOCKS=256> for the fast implementation and C<MAXBLOCKS=65536> |
27 |
for the slow implementation (the implementation is chosen automatically). |
28 |
|
29 |
=over 4 |
30 |
|
31 |
=cut |
32 |
|
33 |
package Algorithm::FEC; |
34 |
|
35 |
require XSLoader; |
36 |
|
37 |
no warnings; |
38 |
|
39 |
$VERSION = 0.4; |
40 |
|
41 |
XSLoader::load Algorithm::FEC, $VERSION; |
42 |
|
43 |
=item $fec = new data_blocks, encoded_blocks, blocksize |
44 |
|
45 |
=item $fec->set_encode_blocks ([array_of_blocks]) |
46 |
|
47 |
Sets the data blocks used for the encoding. Each member of the array can either be: |
48 |
|
49 |
=over 4 |
50 |
|
51 |
=item * a string of size C<blocksize> C<exactly>. |
52 |
|
53 |
This is useful for small files (encoding entirely in memory). |
54 |
|
55 |
=item * a filehandle of a file of size C<blocksize> C<exactly>. |
56 |
|
57 |
This is useful when the amount of data is large and resides in single files. |
58 |
|
59 |
=item * a reference to an array containing a filehandle and, optionally, an offset into that file. |
60 |
|
61 |
This is useful if the amount of data is large and resides in a single |
62 |
file. Needless to say, all parts must not overlap and must fit into the |
63 |
file. |
64 |
|
65 |
=back |
66 |
|
67 |
If your data is not of the required size (i.e. a multiple of C<blocksize> |
68 |
bytes), then you must pad it (e.g. with zero bytes) on encoding, and |
69 |
truncate it after decoding. |
70 |
|
71 |
If called without arguments, the internal storage associated with the |
72 |
blocks is freed again. |
73 |
|
74 |
=item $block = $fec->encode (block_index) |
75 |
|
76 |
Creates a single encoded block of index C<block_index>, which must be |
77 |
between C<0> and C<encoded_blocks-1> (inclusive). The blocks from C<0> to |
78 |
C<data_blocks-1> are simply copies of the original data blocks. |
79 |
|
80 |
The encoded block is returned as a perl scalar (so the blocks should fit |
81 |
into memory. If this is a problem for you mail me and I'll make it a file. |
82 |
|
83 |
=item $fec->set_decode_blocks ([array_of_blocks], [array_of_indices]) |
84 |
|
85 |
Prepares to decode C<data_blocks> of blocks (see C<set_encode_blocks> for |
86 |
the C<array_of_blocks> parameter). |
87 |
|
88 |
Since these are not necessarily the original data blocks, an array of |
89 |
indices (ranging from C<0> to C<encoded_blocks-1>) must be supplied as |
90 |
the second arrayref. |
91 |
|
92 |
Both arrays must have exactly C<data_blocks> entries. |
93 |
|
94 |
This method also reorders the blocks and index array in place (if |
95 |
necessary) to reflect the order the blocks will have in the decoded |
96 |
result. |
97 |
|
98 |
Both arrays must have exactly C<data_blocks> entries. |
99 |
|
100 |
The index array represents the decoded ordering, in that the n-th entry |
101 |
in the indices array corresponds to the n-th data block of the decoded |
102 |
result. The value stored in the n-th place in the array will contain the |
103 |
index of the encoded data block. |
104 |
|
105 |
Input blocks with indices less than C<data_blocks> will be moved to their |
106 |
final position (block k to position k), while the gaps between them will |
107 |
be filled with check blocks. The decoding process will not modify the |
108 |
already decoded data blocks, but will modify the check blocks. |
109 |
|
110 |
That is, if you call this function with C<indices = [4,3,1]>, with |
111 |
C<data_blocks = 3>, then this array will be returned: C<[0,2,1]>. This |
112 |
means that input block C<0> corresponds to file block C<0>, input block |
113 |
C<1> to file block C<2> and input block C<2> to data block C<1>. |
114 |
|
115 |
You can just iterate over this array and write out the corresponding data |
116 |
block (although this is inefficient): |
117 |
|
118 |
for my $i (0 .. $#idx) |
119 |
if ($idx[$i] != $i) # need we move this block? |
120 |
copy encoded block $idx[$i] to position $i |
121 |
} |
122 |
} |
123 |
|
124 |
The C<copy> method can be helpful here. |
125 |
|
126 |
This method destroys the block array as set up by C<set_encode_blocks>. |
127 |
|
128 |
=item $fec->shuffle ([array_of_blocks], [array_of_indices]) |
129 |
|
130 |
The same same as C<set_decode_blocks>, with the exception that the blocks |
131 |
are not actually set for decoding. |
132 |
|
133 |
This method is not normally used, but if you want to move blocks |
134 |
around after reodering and before decoding, then calling Cshuffle> |
135 |
followed by C<set_decode_blocks> incurs lower overhead than calling |
136 |
C<set_decode_blocks> twice, as files are not mmapped etc. |
137 |
|
138 |
=item $fec->decode |
139 |
|
140 |
Decode the blocks set by a prior call to C<set_decode_blocks>. |
141 |
|
142 |
This method destroys the block array as set up by C<set_decode_blocks>. |
143 |
|
144 |
=item $fec->copy ($srcblock, $dstblock) |
145 |
|
146 |
Utility function that simply copies one block (specified like in |
147 |
C<set_encode_blocks>) into another. This, btw., destroys the blocks set by |
148 |
C<set_*_blocks>. |
149 |
|
150 |
=item COMPATIBILITY |
151 |
|
152 |
The way this module works is compatible with the way freenet |
153 |
(L<http://freenet.sf.net>) encodes files. Comaptibility to other file |
154 |
formats or networks is not know, please tell me if you find more examples. |
155 |
|
156 |
=head1 SEE ALSO |
157 |
|
158 |
L<Net::FCP>. And the author, who might be happy to receive mail from any |
159 |
user, just to see that this rather rarely-used module is actually being |
160 |
used (except for freenet ;) |
161 |
|
162 |
=head1 BUGS |
163 |
|
164 |
* too complicated. |
165 |
* largely untested, please change this. |
166 |
* file descriptors are not supported, but should be. |
167 |
* utility functions for files should be provided. |
168 |
* 16 bit version not tested |
169 |
|
170 |
=head1 AUTHOR |
171 |
|
172 |
Marc Lehmann <pcg@goof.com> |
173 |
http://home.schmorp.de |
174 |
|
175 |
=cut |
176 |
|
177 |
1; |
178 |
|