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_packets>,C<data_packets>)
erasure code based on Vandermonde matrices.  The encoder takes
C<data_packets> packets of size C<block_size> each, and is able to produce
up to C<encoded_packets> different encoded packets, numbered from C<0>
to C<encoded_packets-1>, such that any subset of C<data_packets> members
permits reconstruction of the original data.

Allowed values for C<data_packets> and C<encoded_packets> must obey the
following equation:

   data_packets <= encoded_packets <= 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 data_packets, encoded_packets, blocksize

=item $fec->set_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
truncate it after decoding.

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

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

Creates a single encoded packet of index C<block_index>, which must be
between C<0> and C<encoded_packets-1> (inclusive). The blocks from C<0> to
C<data_packets-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->decode ([array_of_blocks], [array_of_indices])

Decode C<data_packets> of blocks (see C<set_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_packets-1>) must be supplied as
the second arrayref.

Both arrays must have exactly C<data_packets> entries.

After decoding, the blocks will be modified in place (if necessary), and
the array of indices will be updates to reflect the changes: The n-th
entry in the indices array is the index of the n-th data block of the
file.

That is, if you call this function with C<indices = [4,3,1]>, with
C<data_packets = 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) {
      copy $decode_input_block[$idx[$i]], $file_output_block[$i];
   }

Only input blocks with indices >= C<data_packets> will be modified, blocks
that already contain the original data will just be reordered.

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

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

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

If you don't understand why this helps, feel free to ignore it :)

=item 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

 * 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.5
Committed:	Sat Sep 13 20:35:49 2003 UTC (23 years ago) by root
Branch:	MAIN
Changes since 1.4:	+1 -1 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	=head1 NAME
2
3	root	1.3	Algorithm::FEC - Forward Error Correction using Vandermonde Matrices
4	root	1.1
5			=head1 SYNOPSIS
6
7	root	1.3	use Algorithm::FEC;
8	root	1.1
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	root	1.3	package Algorithm::FEC;
34	root	1.1
35			require XSLoader;
36
37			no warnings;
38
39	root	1.5	$VERSION = 0.5;
40	root	1.1
41	root	1.3	XSLoader::load Algorithm::FEC, $VERSION;
42	root	1.1
43			=item $fec = new data_packets, encoded_packets, blocksize
44
45	root	1.2	=item $fec->set_blocks ([array_of_blocks])
46	root	1.1
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	root	1.2	Decode C<data_packets> of blocks (see C<set_blocks> for the
86	root	1.1	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	root	1.4	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	root	1.1
104			You can just iterate over this array and write out the corresponding data
105	root	1.4	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	root	1.1
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	root	1.2	This method destroys the block array as set up by C<set_blocks>.
115	root	1.1
116	root	1.2	=item $fec->copy ($srcblock, $dstblock)
117	root	1.1
118			Utility function that simply copies one block (specified like in
119	root	1.2	C<set_blocks>) into another. This, btw., destroys the blocks set by
120			C<set_blocks>.
121	root	1.1
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