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 = '1.1'; |
40 |
|
41 |
XSLoader::load Algorithm::FEC, $VERSION; |
42 |
|
43 |
=item $fec = new Algorithm::FEC $data_blocks, $encoded_blocks, $blocksize |
44 |
|
45 |
Creates a new Algorithm::FEC object with the given parameters. |
46 |
|
47 |
=item $fec->set_encode_blocks ([array_of_blocks]) |
48 |
|
49 |
Sets the data blocks used for the encoding. Each member of the array can either be: |
50 |
|
51 |
=over 4 |
52 |
|
53 |
=item * a string of size C<blocksize> C<exactly>. |
54 |
|
55 |
This is useful for small files (encoding entirely in memory). |
56 |
|
57 |
=item * a filehandle of a file of size C<blocksize> C<exactly>. |
58 |
|
59 |
This is useful when the amount of data is large and resides in single files. |
60 |
|
61 |
=item * a reference to an array containing a filehandle and, optionally, an offset into that file. |
62 |
|
63 |
This is useful if the amount of data is large and resides in a single |
64 |
file. Needless to say, all parts must not overlap and must fit into the |
65 |
file. |
66 |
|
67 |
=back |
68 |
|
69 |
If your data is not of the required size (i.e. a multiple of C<blocksize> |
70 |
bytes), then you must pad it (e.g. with zero bytes) on encoding (and you |
71 |
should truncate it after decoding). Otherwise, this library croaks. |
72 |
|
73 |
Future versions might instead load the short segment into memory or extend |
74 |
your scalar (this might enable nice tricks, like C<$fec->copy (..., my |
75 |
$x)> :). Mail me if you want this to happen. |
76 |
|
77 |
If called without arguments, the internal storage associated with the |
78 |
blocks is freed again. |
79 |
|
80 |
=item $block = $fec->encode ($block_index) |
81 |
|
82 |
Creates a single encoded block of index C<block_index>, which must be |
83 |
between C<0> and C<encoded_blocks-1> (inclusive). The blocks from C<0> to |
84 |
C<data_blocks-1> are simply copies of the original data blocks. |
85 |
|
86 |
The encoded block is returned as a perl scalar (so the blocks should fit |
87 |
into memory. If this is a problem for you mail me and I'll make it a file. |
88 |
|
89 |
=item $fec->set_decode_blocks ([array_of_blocks], [array_of_indices]) |
90 |
|
91 |
Prepares to decode C<data_blocks> of blocks (see C<set_encode_blocks> for |
92 |
the C<array_of_blocks> parameter). |
93 |
|
94 |
Since these are not usually the original data blocks, an array of |
95 |
indices (ranging from C<0> to C<encoded_blocks-1>) must be supplied as |
96 |
the second arrayref. |
97 |
|
98 |
Both arrays must have exactly C<data_blocks> entries. |
99 |
|
100 |
This method also reorders the blocks and index array in place (if |
101 |
necessary) to reflect the order the blocks will have in the decoded |
102 |
result. |
103 |
|
104 |
The index array represents the decoded ordering, in that the n-th entry |
105 |
in the indices array corresponds to the n-th data block of the decoded |
106 |
result. The value stored in the n-th place in the array will contain the |
107 |
index of the encoded data block. |
108 |
|
109 |
Input blocks with indices less than C<data_blocks> will be moved to their |
110 |
final position (block k to position k), while the gaps between them will |
111 |
be filled with check blocks. The decoding process will not modify the |
112 |
already decoded data blocks, but will modify the check blocks. |
113 |
|
114 |
That is, if you call this function with C<indices = [4,3,1]>, with |
115 |
C<data_blocks = 3>, then this array will be returned: C<[0,2,1]>. This |
116 |
means that input block C<0> corresponds to file block C<0>, input block |
117 |
C<1> to file block C<2> and input block C<2> to data block C<1>. |
118 |
|
119 |
You can just iterate over this array and write out the corresponding data |
120 |
block (although this is inefficient): |
121 |
|
122 |
for my $i (0 .. $#idx) |
123 |
if ($idx[$i] != $i) # need we move this block? |
124 |
copy encoded block $idx[$i] to position $i |
125 |
} |
126 |
} |
127 |
|
128 |
The C<copy> method can be helpful here. |
129 |
|
130 |
This method destroys the block array as set up by C<set_encode_blocks>. |
131 |
|
132 |
=item $fec->shuffle ([array_of_blocks], [array_of_indices]) |
133 |
|
134 |
The same same as C<set_decode_blocks>, with the exception that the blocks |
135 |
are not actually set for decoding. |
136 |
|
137 |
This method is not normally used, but if you want to move blocks |
138 |
around after reordering and before decoding, then calling C<shuffle> |
139 |
followed by C<set_decode_blocks> incurs lower overhead than calling |
140 |
C<set_decode_blocks> twice, as files are not mmapped etc. |
141 |
|
142 |
=item $fec->decode |
143 |
|
144 |
Decode the blocks set by a prior call to C<set_decode_blocks>. |
145 |
|
146 |
This method destroys the block array as set up by C<set_decode_blocks>. |
147 |
|
148 |
=item $fec->copy ($srcblock, $dstblock) |
149 |
|
150 |
Utility function that simply copies one block (specified like in |
151 |
C<set_encode_blocks>) into another. This, btw., destroys the blocks set by |
152 |
C<set_*_blocks>. |
153 |
|
154 |
=back |
155 |
|
156 |
=head1 COMPATIBILITY |
157 |
|
158 |
The way this module works is compatible with the way freenet |
159 |
(L<http://freenet.sf.net>) encodes files. Comaptibility to other file |
160 |
formats or networks is not known, please tell me if you find more examples. |
161 |
|
162 |
=head1 SEE ALSO |
163 |
|
164 |
L<Net::FCP>. And the author, who might be happy to receive mail from any |
165 |
user, just to see that this rather rarely-used module is actually being |
166 |
used (except for freenet ;) |
167 |
|
168 |
=head1 BUGS |
169 |
|
170 |
* too complicated. |
171 |
* largely untested, please change this. |
172 |
* file descriptors are not supported, but should be. |
173 |
* utility functions for files should be provided. |
174 |
* 16 bit version not tested |
175 |
|
176 |
=head1 AUTHOR |
177 |
|
178 |
Marc Lehmann <schmorp@schmorp.de> |
179 |
http://home.schmorp.de |
180 |
|
181 |
=cut |
182 |
|
183 |
1; |
184 |
|