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