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_packets>,C<data_packets>) |
15 |
erasure code based on Vandermonde matrices. The encoder takes |
16 |
C<data_packets> packets of size C<block_size> each, and is able to produce |
17 |
up to C<encoded_packets> different encoded packets, numbered from C<0> |
18 |
to C<encoded_packets-1>, such that any subset of C<data_packets> members |
19 |
permits reconstruction of the original data. |
20 |
|
21 |
Allowed values for C<data_packets> and C<encoded_packets> must obey the |
22 |
following equation: |
23 |
|
24 |
data_packets <= encoded_packets <= 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.5; |
40 |
|
41 |
XSLoader::load Algorithm::FEC, $VERSION; |
42 |
|
43 |
=item $fec = new data_packets, encoded_packets, blocksize |
44 |
|
45 |
=item $fec->set_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 packet of index C<block_index>, which must be |
77 |
between C<0> and C<encoded_packets-1> (inclusive). The blocks from C<0> to |
78 |
C<data_packets-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->decode ([array_of_blocks], [array_of_indices]) |
84 |
|
85 |
Decode C<data_packets> of blocks (see C<set_blocks> for the |
86 |
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_packets-1>) must be supplied as |
90 |
the second arrayref. |
91 |
|
92 |
Both arrays must have exactly C<data_packets> entries. |
93 |
|
94 |
After decoding, the blocks will be modified in place (if necessary), and |
95 |
the array of indices will be updates to reflect the changes: The n-th |
96 |
entry in the indices array is the index of the n-th data block of the |
97 |
file. |
98 |
|
99 |
That is, if you call this function with C<indices = [4,3,1]>, with |
100 |
C<data_packets = 3>, then this array will be returned: C<[0,2,1]>. This |
101 |
means that input block C<0> corresponds to file block C<0>, input block |
102 |
C<1> to file block C<2> and input block C<2> to data block C<1>. |
103 |
|
104 |
You can just iterate over this array and write out the corresponding data |
105 |
block (although this is inefficient): |
106 |
|
107 |
for my $i (0 .. $#idx) { |
108 |
copy $decode_input_block[$idx[$i]], $file_output_block[$i]; |
109 |
} |
110 |
|
111 |
Only input blocks with indices >= C<data_packets> will be modified, blocks |
112 |
that already contain the original data will just be reordered. |
113 |
|
114 |
This method destroys the block array as set up by C<set_blocks>. |
115 |
|
116 |
=item $fec->copy ($srcblock, $dstblock) |
117 |
|
118 |
Utility function that simply copies one block (specified like in |
119 |
C<set_blocks>) into another. This, btw., destroys the blocks set by |
120 |
C<set_blocks>. |
121 |
|
122 |
If you don't understand why this helps, feel free to ignore it :) |
123 |
|
124 |
=item COMPATIBILITY |
125 |
|
126 |
The way this module works is compatible with the way freenet |
127 |
(L<http://freenet.sf.net>) encodes files. Comaptibility to other file |
128 |
formats or networks is not know, please tell me if you find more examples. |
129 |
|
130 |
=head1 SEE ALSO |
131 |
|
132 |
L<Net::FCP>. And the author, who might be happy to receive mail from any |
133 |
user, just to see that this rather rarely-used module is actually being |
134 |
used (except for freenet ;) |
135 |
|
136 |
=head1 BUGS |
137 |
|
138 |
* largely untested, please change this. |
139 |
* file descriptors are not supported, but should be. |
140 |
* utility functions for files should be provided. |
141 |
* 16 bit version not tested |
142 |
|
143 |
=head1 AUTHOR |
144 |
|
145 |
Marc Lehmann <pcg@goof.com> |
146 |
http://home.schmorp.de |
147 |
|
148 |
=cut |
149 |
|
150 |
1; |
151 |
|