[ViewVC] Diff of: cvs/Algorithm-FEC/FEC.pm

Comparing Algorithm-FEC/FEC.pm (file contents):
Revision 1.2 by root, Tue Sep 9 06:07:28 2003 UTC vs.
Revision 1.9 by root, Sun Jun 27 12:43:08 2004 UTC

…		…
1	=head1 NAME	1	=head1 NAME
2		2
3	Convert::FEC - Forward Error Correction using Vandermonde Matrices	3	Algorithm::FEC - Forward Error Correction using Vandermonde Matrices
4		4
5	=head1 SYNOPSIS	5	=head1 SYNOPSIS
6		6
7	use Convert::FEC;	7	use Algorithm::FEC;
8		8
9	=head1 DESCRIPTION	9	=head1 DESCRIPTION
10		10
11	This module is an interface to the fec library by Luigi Rizzo et al., see	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.	12	the file README.fec in the distribution for more details.
13		13
14	This library implements a simple (C<encoded_packets>,C<data_packets>)	14	This library implements a simple (C<encoded_blocks>,C<data_blocks>)
15	erasure code based on Vandermonde matrices. The encoder takes	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	16	C<data_blocks> blocks of size C<block_size> each, and is able to produce
17	up to C<encoded_packets> different encoded packets, numbered from C<0>	17	up to C<encoded_blocks> different encoded blocks, numbered from C<0>
18	to C<encoded_packets-1>, such that any subset of C<data_packets> members	18	to C<encoded_blocks-1>, such that any subset of C<data_blocks> members
19	permits reconstruction of the original data.	19	permits reconstruction of the original data.
20		20
21	Allowed values for C<data_packets> and C<encoded_packets> must obey the	21	Allowed values for C<data_blocks> and C<encoded_blocks> must obey the
22	following equation:	22	following equation:
23		23
24	data_packets <= encoded_packets <= MAXBLOCKS	24	data_blocks <= encoded_blocks <= MAXBLOCKS
25		25
26	Where C<MAXBLOCKS=256> for the fast implementation and C<MAXBLOCKS=65536>	26	Where C<MAXBLOCKS=256> for the fast implementation and C<MAXBLOCKS=65536>
27	for the slow implementation (the implementation is chosen automatically).	27	for the slow implementation (the implementation is chosen automatically).
28		28
29	=over 4	29	=over 4
30		30
31	=cut	31	=cut
32		32
33	package Convert::FEC;	33	package Algorithm::FEC;
34		34
35	require XSLoader;	35	require XSLoader;
36		36
37	no warnings;	37	no warnings;
38		38
39	$VERSION = 0.01;	39	$VERSION = 0.5;
40		40
41	XSLoader::load Convert::FEC, $VERSION;	41	XSLoader::load Algorithm::FEC, $VERSION;
42		42
43	=item $fec = new data_packets, encoded_packets, blocksize	43	=item $fec = new Algorithm::FEC $data_blocks, $encoded_blocks, $blocksize
44		44
		45	Creates a new Algorithm::FEC object with the given parameters.
		46
45	=item $fec->set_blocks ([array_of_blocks])	47	=item $fec->set_encode_blocks ([array_of_blocks])
46		48
47	Sets the data blocks used for the encoding. Each member of the array can either be:	49	Sets the data blocks used for the encoding. Each member of the array can either be:
48		50
49	=over 4	51	=over 4
50		52
63	file.	65	file.
64		66
65	=back	67	=back
66		68
67	If your data is not of the required size (i.e. a multiple of C<blocksize>	69	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	70	bytes), then you must pad it (e.g. with zero bytes) on encoding (and you
69	truncate it after decoding.	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.
70		76
71	If called without arguments, the internal storage associated with the	77	If called without arguments, the internal storage associated with the
72	blocks is freed again.	78	blocks is freed again.
73		79
74	=item $block = $fec->encode (block_index)	80	=item $block = $fec->encode ($block_index)
75		81
76	Creates a single encoded packet of index C<block_index>, which must be	82	Creates a single encoded block of index C<block_index>, which must be
77	between C<0> and C<encoded_packets-1> (inclusive). The blocks from C<0> to	83	between C<0> and C<encoded_blocks-1> (inclusive). The blocks from C<0> to
78	C<data_packets-1> are simply copies of the original data blocks.	84	C<data_blocks-1> are simply copies of the original data blocks.
79		85
80	The encoded block is returned as a perl scalar (so the blocks should fit	86	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.	87	into memory. If this is a problem for you mail me and I'll make it a file.
82		88
83	=item $fec->decode ([array_of_blocks], [array_of_indices])	89	=item $fec->set_decode_blocks ([array_of_blocks], [array_of_indices])
84		90
85	Decode C<data_packets> of blocks (see C<set_blocks> for the	91	Prepares to decode C<data_blocks> of blocks (see C<set_encode_blocks> for
86	C<array_of_blocks> parameter).	92	the C<array_of_blocks> parameter).
87		93
88	Since these are not necessarily the original data blocks, an array of	94	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	95	indices (ranging from C<0> to C<encoded_blocks-1>) must be supplied as
90	the second arrayref.	96	the second arrayref.
91		97
92	Both arrays must have exactly C<data_packets> entries.	98	Both arrays must have exactly C<data_blocks> entries.
93		99
94	After decoding, the blocks will be modified in place (if necessary), and	100	This method also reorders the blocks and index array in place (if
95	the array of indices will be updates to reflect the changes: The n-th	101	necessary) to reflect the order the blocks will have in the decoded
96	entry in the indices array is the index of the n-th data block of the	102	result.
97	file.	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.
98		115
99	That is, if you call this function with C<indices = [4,3,1]>, with	116	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	117	C<data_blocks = 3>, then this array will be returned: C<[0,2,1]>. This
101	means that input block C<0> corresponds file block C<0>, input block C<1>	118	means that input block C<0> corresponds to file block C<0>, input block
102	to file block C<2> and input block C<2> to data block C<1>.	119	C<1> to file block C<2> and input block C<2> to data block C<1>.
103		120
104	You can just iterate over this array and write out the corresponding data	121	You can just iterate over this array and write out the corresponding data
105	block (although this is inefficient).	122	block (although this is inefficient):
106		123
107	Only input blocks with indices >= C<data_packets> will be modified, blocks	124	for my $i (0 .. $#idx)
108	that already contain the original data will just be reordered.	125	if ($idx[$i] != $i) # need we move this block?
		126	copy encoded block $idx[$i] to position $i
		127	}
		128	}
109		129
		130	The C<copy> method can be helpful here.
		131
110	This method destroys the block array as set up by C<set_blocks>.	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>.
111		149
112	=item $fec->copy ($srcblock, $dstblock)	150	=item $fec->copy ($srcblock, $dstblock)
113		151
114	Utility function that simply copies one block (specified like in	152	Utility function that simply copies one block (specified like in
115	C<set_blocks>) into another. This, btw., destroys the blocks set by	153	C<set_encode_blocks>) into another. This, btw., destroys the blocks set by
116	C<set_blocks>.	154	C<set_*_blocks>.
117		155
118	If you don't understand why this helps, feel free to ignore it :)	156	=back
119		157
120	=item COMPATIBILITY	158	=head1 COMPATIBILITY
121		159
122	The way this module works is compatible with the way freenet	160	The way this module works is compatible with the way freenet
123	(L<http://freenet.sf.net>) encodes files. Comaptibility to other file	161	(L<http://freenet.sf.net>) encodes files. Comaptibility to other file
124	formats or networks is not know, please tell me if you find more examples.	162	formats or networks is not know, please tell me if you find more examples.
125		163
…		…
129	user, just to see that this rather rarely-used module is actually being	167	user, just to see that this rather rarely-used module is actually being
130	used (except for freenet ;)	168	used (except for freenet ;)
131		169
132	=head1 BUGS	170	=head1 BUGS
133		171
		172	* too complicated.
134	* largely untested, please change this.	173	* largely untested, please change this.
135	* file descriptors are not supported, but should be.	174	* file descriptors are not supported, but should be.
136	* utility functions for files should be provided.	175	* utility functions for files should be provided.
137	* 16 bit version not tested	176	* 16 bit version not tested
138		177

Diff Legend

-–
+Removed lines
-+
+Added lines
-<
+Changed lines
->
+Changed lines

Comparing Algorithm-FEC/FEC.pm (file contents): Revision 1.2 by root, Tue Sep 9 06:07:28 2003 UTC vs. Revision 1.9 by root, Sun Jun 27 12:43:08 2004 UTC

Diff Legend

Comparing Algorithm-FEC/FEC.pm (file contents):
Revision 1.2 by root, Tue Sep 9 06:07:28 2003 UTC vs.
Revision 1.9 by root, Sun Jun 27 12:43:08 2004 UTC