cvsroot/Algorithm-FEC/FEC.pm

=head1 NAME

Algorithm::FEC - Forward Error Correction using Vandermonde Matrices

=head1 SYNOPSIS

 use Algorithm::FEC;

=head1 DESCRIPTION

This module is an interface to the fec library by Luigi Rizzo et al., see
the file README.fec in the distribution for more details.

This library implements a simple (C<encoded_blocks>,C<data_blocks>)
erasure code based on Vandermonde matrices.  The encoder takes
C<data_blocks> blocks of size C<block_size> each, and is able to produce
up to C<encoded_blocks> different encoded blocks, numbered from C<0>
to C<encoded_blocks-1>, such that any subset of C<data_blocks> members
permits reconstruction of the original data.

Allowed values for C<data_blocks> and C<encoded_blocks> must obey the
following equation:

   data_blocks <= encoded_blocks <= MAXBLOCKS

Where C<MAXBLOCKS=256> for the fast implementation and C<MAXBLOCKS=65536>
for the slow implementation (the implementation is chosen automatically).

=over 4

=cut

package Algorithm::FEC;

require XSLoader;

no warnings;

$VERSION = 0.5;

XSLoader::load Algorithm::FEC, $VERSION;

=item $fec = new Algorithm::FEC $data_blocks, $encoded_blocks, $blocksize

Creates a new Algorithm::FEC object with the given parameters.

=item $fec->set_encode_blocks ([array_of_blocks])

Sets the data blocks used for the encoding. Each member of the array can either be:

=over 4

=item * a string of size C<blocksize> C<exactly>.

This is useful for small files (encoding entirely in memory).

=item * a filehandle of a file of size C<blocksize> C<exactly>.

This is useful when the amount of data is large and resides in single files.

=item * a reference to an array containing a filehandle and, optionally, an offset into that file.

This is useful if the amount of data is large and resides in a single
file. Needless to say, all parts must not overlap and must fit into the
file.

=back

If your data is not of the required size (i.e. a multiple of C<blocksize>
bytes), then you must pad it (e.g. with zero bytes) on encoding (and you
should truncate it after decoding). Otherwise, this library croaks.

Future versions might instead load the short segment into memory or extend
your scalar (this might enable nice tricks, like C<$fec->copy (..., my
$x)> :). Mail me if you want this to happen.

If called without arguments, the internal storage associated with the
blocks is freed again.

=item $block = $fec->encode ($block_index)

Creates a single encoded block of index C<block_index>, which must be
between C<0> and C<encoded_blocks-1> (inclusive). The blocks from C<0> to
C<data_blocks-1> are simply copies of the original data blocks.

The encoded block is returned as a perl scalar (so the blocks should fit
into memory. If this is a problem for you mail me and I'll make it a file.

=item $fec->set_decode_blocks ([array_of_blocks], [array_of_indices])

Prepares to decode C<data_blocks> of blocks (see C<set_encode_blocks> for
the C<array_of_blocks> parameter).

Since these are not necessarily the original data blocks, an array of
indices (ranging from C<0> to C<encoded_blocks-1>) must be supplied as
the second arrayref.

Both arrays must have exactly C<data_blocks> entries.

This method also reorders the blocks and index array in place (if
necessary) to reflect the order the blocks will have in the decoded
result.

Both arrays must have exactly C<data_blocks> entries.

The index array represents the decoded ordering, in that the n-th entry
in the indices array corresponds to the n-th data block of the decoded
result. The value stored in the n-th place in the array will contain the
index of the encoded data block.

Input blocks with indices less than C<data_blocks> will be moved to their
final position (block k to position k), while the gaps between them will
be filled with check blocks. The decoding process will not modify the
already decoded data blocks, but will modify the check blocks.

That is, if you call this function with C<indices = [4,3,1]>, with
C<data_blocks = 3>, then this array will be returned: C<[0,2,1]>. This
means that input block C<0> corresponds to file block C<0>, input block
C<1> to file block C<2> and input block C<2> to data block C<1>.

You can just iterate over this array and write out the corresponding data
block (although this is inefficient):

   for my $i (0 .. $#idx)
      if ($idx[$i] != $i) # need we move this block?
         copy encoded block $idx[$i] to position $i
      }
   }

The C<copy> method can be helpful here.

This method destroys the block array as set up by C<set_encode_blocks>.

=item $fec->shuffle ([array_of_blocks], [array_of_indices])

The same same as C<set_decode_blocks>, with the exception that the blocks
are not actually set for decoding.

This method is not normally used, but if you want to move blocks
around after reodering and before decoding, then calling Cshuffle>
followed by C<set_decode_blocks> incurs lower overhead than calling
C<set_decode_blocks> twice, as files are not mmapped etc.

=item $fec->decode

Decode the blocks set by a prior call to C<set_decode_blocks>.

This method destroys the block array as set up by C<set_decode_blocks>.

=item $fec->copy ($srcblock, $dstblock)

Utility function that simply copies one block (specified like in
C<set_encode_blocks>) into another. This, btw., destroys the blocks set by
C<set_*_blocks>.

=back

=head1 COMPATIBILITY

The way this module works is compatible with the way freenet
(L<http://freenet.sf.net>) encodes files. Comaptibility to other file
formats or networks is not know, please tell me if you find more examples.

=head1 SEE ALSO

L<Net::FCP>. And the author, who might be happy to receive mail from any
user, just to see that this rather rarely-used module is actually being
used (except for freenet ;)

=head1 BUGS

 * too complicated.
 * largely untested, please change this.
 * file descriptors are not supported, but should be.
 * utility functions for files should be provided.
 * 16 bit version not tested

=head1 AUTHOR

 Marc Lehmann <pcg@goof.com>
 http://home.schmorp.de

=cut

1;

Revision:	1.9
Committed:	Sun Jun 27 12:43:08 2004 UTC (22 years, 2 months ago) by root
Branch:	MAIN
Changes since 1.8:	+4 -2 lines
Log Message:	* empty log message *
#	Content
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.5;
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 necessarily 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	Both arrays must have exactly C<data_blocks> entries.
105
106	The index array represents the decoded ordering, in that the n-th entry
107	in the indices array corresponds to the n-th data block of the decoded
108	result. The value stored in the n-th place in the array will contain the
109	index of the encoded data block.
110
111	Input blocks with indices less than C<data_blocks> will be moved to their
112	final position (block k to position k), while the gaps between them will
113	be filled with check blocks. The decoding process will not modify the
114	already decoded data blocks, but will modify the check blocks.
115
116	That is, if you call this function with C<indices = [4,3,1]>, with
117	C<data_blocks = 3>, then this array will be returned: C<[0,2,1]>. This
118	means that input block C<0> corresponds to file block C<0>, input block
119	C<1> to file block C<2> and input block C<2> to data block C<1>.
120
121	You can just iterate over this array and write out the corresponding data
122	block (although this is inefficient):
123
124	for my $i (0 .. $#idx)
125	if ($idx[$i] != $i) # need we move this block?
126	copy encoded block $idx[$i] to position $i
127	}
128	}
129
130	The C<copy> method can be helpful here.
131
132	This method destroys the block array as set up by C<set_encode_blocks>.
133
134	=item $fec->shuffle ([array_of_blocks], [array_of_indices])
135
136	The same same as C<set_decode_blocks>, with the exception that the blocks
137	are not actually set for decoding.
138
139	This method is not normally used, but if you want to move blocks
140	around after reodering and before decoding, then calling Cshuffle>
141	followed by C<set_decode_blocks> incurs lower overhead than calling
142	C<set_decode_blocks> twice, as files are not mmapped etc.
143
144	=item $fec->decode
145
146	Decode the blocks set by a prior call to C<set_decode_blocks>.
147
148	This method destroys the block array as set up by C<set_decode_blocks>.
149
150	=item $fec->copy ($srcblock, $dstblock)
151
152	Utility function that simply copies one block (specified like in
153	C<set_encode_blocks>) into another. This, btw., destroys the blocks set by
154	C<set_*_blocks>.
155
156	=back
157
158	=head1 COMPATIBILITY
159
160	The way this module works is compatible with the way freenet
161	(L<http://freenet.sf.net>) encodes files. Comaptibility to other file
162	formats or networks is not know, please tell me if you find more examples.
163
164	=head1 SEE ALSO
165
166	L<Net::FCP>. And the author, who might be happy to receive mail from any
167	user, just to see that this rather rarely-used module is actually being
168	used (except for freenet ;)
169
170	=head1 BUGS
171
172	* too complicated.
173	* largely untested, please change this.
174	* file descriptors are not supported, but should be.
175	* utility functions for files should be provided.
176	* 16 bit version not tested
177
178	=head1 AUTHOR
179
180	Marc Lehmann <pcg@goof.com>
181	http://home.schmorp.de
182
183	=cut
184
185	1;
186