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

    Allowed values for "data_blocks" and "encoded_blocks" must obey the
    following equation:

       data_blocks <= encoded_blocks <= MAXBLOCKS

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

    $fec = new data_blocks, encoded_blocks, blocksize
    $fec->set_encode_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 block of index "block_index", which must be
        between 0 and "encoded_blocks-1" (inclusive). The blocks from 0 to
        "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.

    $fec->set_decode_blocks ([array_of_blocks], [array_of_indices])
        Prepares to decode "data_blocks" of blocks (see "set_encode_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_blocks-1") must be supplied
        as the second arrayref.

        Both arrays must have exactly "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 "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 "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 "indices = [4,3,1]", with
        "data_blocks = 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)
              if ($idx[$i] != $i) # need we move this block?
                 copy encoded block $idx[$i] to position $i
              }
           }

        The "copy" method can be helpful here.

        This method destroys the block array as set up by
        "set_encode_blocks".

    $fec->shuffle ([array_of_blocks], [array_of_indices])
        The same same as "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 "set_decode_blocks" incurs lower overhead than calling
        "set_decode_blocks" twice, as files are not mmapped etc.

    $fec->decode
        Decode the blocks set by a prior call to "set_decode_blocks".

        This method destroys the block array as set up by
        "set_decode_blocks".

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

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

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

Revision:	1.4
Committed:	Sat Sep 13 21:59:29 2003 UTC (23 years ago) by root
Branch:	MAIN
Changes since 1.3:	+60 -33 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	root	1.4	This library implements a simple ("encoded_blocks","data_blocks")
12	root	1.1	erasure code based on Vandermonde matrices. The encoder takes
13	root	1.4	"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	root	1.1	permits reconstruction of the original data.
17
18	root	1.4	Allowed values for "data_blocks" and "encoded_blocks" must obey the
19	root	1.1	following equation:
20
21	root	1.4	data_blocks <= encoded_blocks <= MAXBLOCKS
22	root	1.1
23			Where "MAXBLOCKS=256" for the fast implementation and "MAXBLOCKS=65536"
24			for the slow implementation (the implementation is chosen
25			automatically).
26
27	root	1.4	$fec = new data_blocks, encoded_blocks, blocksize
28			$fec->set_encode_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	root	1.4	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	root	1.1
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	root	1.4	$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	root	1.1
65			Since these are not necessarily the original data blocks, an array
66	root	1.4	of indices (ranging from 0 to "encoded_blocks-1") must be supplied
67	root	1.1	as the second arrayref.
68
69	root	1.4	Both arrays must have exactly "data_blocks" entries.
70	root	1.1
71	root	1.4	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	root	1.1
88			That is, if you call this function with "indices = [4,3,1]", with
89	root	1.4	"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	root	1.1
93			You can just iterate over this array and write out the corresponding
94	root	1.3	data block (although this is inefficient):
95
96	root	1.4	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	root	1.3	}
101	root	1.1
102	root	1.4	The "copy" method can be helpful here.
103	root	1.1
104	root	1.4	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	root	1.1
122	root	1.2	$fec->copy ($srcblock, $dstblock)
123	root	1.1	Utility function that simply copies one block (specified like in
124	root	1.4	"set_encode_blocks") into another. This, btw., destroys the blocks
125			set by "set_*_blocks".
126	root	1.1
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	root	1.4	* too complicated.
140	root	1.1	* 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