[ViewVC] Annotation of: cvs/Algorithm-FEC/README

NAME
    Algorithm::FEC - Forward Error Correction using Vandermonde Matrices

SYNOPSIS
     use Algorithm::FEC;

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

    Allowed values for "data_packets" and "encoded_packets" must obey the
    following equation:

       data_packets <= encoded_packets <= MAXBLOCKS

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

    $fec = new data_packets, encoded_packets, blocksize
    $fec->set_blocks ([array_of_blocks])
        Sets the data blocks used for the encoding. Each member of the array
        can either be:

        * a string of size "blocksize" "exactly".
            This is useful for small files (encoding entirely in memory).

        * a filehandle of a file of size "blocksize" "exactly".
            This is useful when the amount of data is large and resides in
            single files.

        * 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.

        If your data is not of the required size (i.e. a multiple of
        "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.

    $block = $fec->encode (block_index)
        Creates a single encoded packet of index "block_index", which must
        be between 0 and "encoded_packets-1" (inclusive). The blocks from 0
        to "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.

    $fec->decode ([array_of_blocks], [array_of_indices])
        Decode "data_packets" of blocks (see "set_blocks" for the
        "array_of_blocks" parameter).

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

        Both arrays must have exactly "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 "indices = [4,3,1]", with
        "data_packets = 3", then this array will be returned: "[0,2,1]".
        This means that input block 0 corresponds to file block 0, input
        block 1 to file block 2 and input block 2 to data block 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 >= "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 "set_blocks".

    $fec->copy ($srcblock, $dstblock)
        Utility function that simply copies one block (specified like in
        "set_blocks") into another. This, btw., destroys the blocks set by
        "set_blocks".

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

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

SEE ALSO
        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 ;)

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

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

Revision:	1.3
Committed:	Sat Sep 13 20:35:49 2003 UTC (23 years ago) by root
Branch:	MAIN
Changes since 1.2:	+7 -3 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	NAME
2	root	1.2	Algorithm::FEC - Forward Error Correction using Vandermonde Matrices
3	root	1.1
4			SYNOPSIS
5	root	1.2	use Algorithm::FEC;
6	root	1.1
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_packets","data_packets")
12			erasure code based on Vandermonde matrices. The encoder takes
13			"data_packets" packets of size "block_size" each, and is able to produce
14			up to "encoded_packets" different encoded packets, numbered from 0 to
15			"encoded_packets-1", such that any subset of "data_packets" members
16			permits reconstruction of the original data.
17
18			Allowed values for "data_packets" and "encoded_packets" must obey the
19			following equation:
20
21			data_packets <= encoded_packets <= 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_packets, encoded_packets, blocksize
28	root	1.2	$fec->set_blocks ([array_of_blocks])
29	root	1.1	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 packet of index "block_index", which must
54			be between 0 and "encoded_packets-1" (inclusive). The blocks from 0
55			to "data_packets-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->decode ([array_of_blocks], [array_of_indices])
62	root	1.2	Decode "data_packets" of blocks (see "set_blocks" for the
63	root	1.1	"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_packets-1") must be supplied
67			as the second arrayref.
68
69			Both arrays must have exactly "data_packets" entries.
70
71			After decoding, the blocks will be modified in place (if necessary),
72			and the array of indices will be updates to reflect the changes: The
73			n-th entry in the indices array is the index of the n-th data block
74			of the file.
75
76			That is, if you call this function with "indices = [4,3,1]", with
77			"data_packets = 3", then this array will be returned: "[0,2,1]".
78	root	1.3	This means that input block 0 corresponds to file block 0, input
79			block 1 to file block 2 and input block 2 to data block 1.
80	root	1.1
81			You can just iterate over this array and write out the corresponding
82	root	1.3	data block (although this is inefficient):
83
84			for my $i (0 .. $#idx) {
85			copy $decode_input_block[$idx[$i]], $file_output_block[$i];
86			}
87	root	1.1
88			Only input blocks with indices >= "data_packets" will be modified,
89			blocks that already contain the original data will just be
90			reordered.
91
92	root	1.2	This method destroys the block array as set up by "set_blocks".
93	root	1.1
94	root	1.2	$fec->copy ($srcblock, $dstblock)
95	root	1.1	Utility function that simply copies one block (specified like in
96	root	1.2	"set_blocks") into another. This, btw., destroys the blocks set by
97			"set_blocks".
98	root	1.1
99			If you don't understand why this helps, feel free to ignore it :)
100
101			COMPATIBILITY
102			The way this module works is compatible with the way freenet
103			(<http://freenet.sf.net>) encodes files. Comaptibility to other file
104			formats or networks is not know, please tell me if you find more
105			examples.
106
107			SEE ALSO
108			Net::FCP. And the author, who might be happy to receive mail from
109			any user, just to see that this rather rarely-used module is
110			actually being used (except for freenet ;)
111
112			BUGS
113			* largely untested, please change this.
114			* file descriptors are not supported, but should be.
115			* utility functions for files should be provided.
116			* 16 bit version not tested
117
118			AUTHOR
119			Marc Lehmann <pcg@goof.com>
120			http://home.schmorp.de
121