[ViewVC] Contents 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 Algorithm::FEC $data_blocks, $encoded_blocks, $blocksize
        Creates a new Algorithm::FEC object with the given parameters.

    $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 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 "$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.

    $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 usually 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.

        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 reordering and before decoding, then calling "shuffle"
        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 known, 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 <schmorp@schmorp.de>
     http://home.schmorp.de

Revision:	1.8
Committed:	Thu Nov 22 01:41:39 2012 UTC (11 years, 5 months ago) by root
Branch:	MAIN
CVS Tags:	rel-1_1, HEAD
Changes since 1.7:	+7 -4 lines
Log Message:	1.1
#	Content
1	NAME
2	Algorithm::FEC - Forward Error Correction using Vandermonde Matrices
3
4	SYNOPSIS
5	use Algorithm::FEC;
6
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_blocks","data_blocks")
12	erasure code based on Vandermonde matrices. The encoder takes
13	"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	permits reconstruction of the original data.
17
18	Allowed values for "data_blocks" and "encoded_blocks" must obey the
19	following equation:
20
21	data_blocks <= encoded_blocks <= 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 Algorithm::FEC $data_blocks, $encoded_blocks, $blocksize
28	Creates a new Algorithm::FEC object with the given parameters.
29
30	$fec->set_encode_blocks ([array_of_blocks])
31	Sets the data blocks used for the encoding. Each member of the array
32	can either be:
33
34	* a string of size "blocksize" "exactly".
35
36	This is useful for small files (encoding entirely in memory).
37
38	* a filehandle of a file of size "blocksize" "exactly".
39
40	This is useful when the amount of data is large and resides in
41	single files.
42
43	* a reference to an array containing a filehandle and, optionally,
44	an offset into that file.
45
46	This is useful if the amount of data is large and resides in a
47	single file. Needless to say, all parts must not overlap and
48	must fit into the file.
49
50	If your data is not of the required size (i.e. a multiple of
51	"blocksize" bytes), then you must pad it (e.g. with zero bytes) on
52	encoding (and you should truncate it after decoding). Otherwise,
53	this library croaks.
54
55	Future versions might instead load the short segment into memory or
56	extend your scalar (this might enable nice tricks, like "$fec-"copy
57	(..., my $x)> :). Mail me if you want this to happen.
58
59	If called without arguments, the internal storage associated with
60	the blocks is freed again.
61
62	$block = $fec->encode ($block_index)
63	Creates a single encoded block of index "block_index", which must be
64	between 0 and "encoded_blocks-1" (inclusive). The blocks from 0 to
65	"data_blocks-1" are simply copies of the original data blocks.
66
67	The encoded block is returned as a perl scalar (so the blocks should
68	fit into memory. If this is a problem for you mail me and I'll make
69	it a file.
70
71	$fec->set_decode_blocks ([array_of_blocks], [array_of_indices])
72	Prepares to decode "data_blocks" of blocks (see "set_encode_blocks"
73	for the "array_of_blocks" parameter).
74
75	Since these are not usually the original data blocks, an array of
76	indices (ranging from 0 to "encoded_blocks-1") must be supplied as
77	the second arrayref.
78
79	Both arrays must have exactly "data_blocks" entries.
80
81	This method also reorders the blocks and index array in place (if
82	necessary) to reflect the order the blocks will have in the decoded
83	result.
84
85	The index array represents the decoded ordering, in that the n-th
86	entry in the indices array corresponds to the n-th data block of the
87	decoded result. The value stored in the n-th place in the array will
88	contain the index of the encoded data block.
89
90	Input blocks with indices less than "data_blocks" will be moved to
91	their final position (block k to position k), while the gaps between
92	them will be filled with check blocks. The decoding process will not
93	modify the already decoded data blocks, but will modify the check
94	blocks.
95
96	That is, if you call this function with "indices = [4,3,1]", with
97	"data_blocks = 3", then this array will be returned: "[0,2,1]". This
98	means that input block 0 corresponds to file block 0, input block 1
99	to file block 2 and input block 2 to data block 1.
100
101	You can just iterate over this array and write out the corresponding
102	data block (although this is inefficient):
103
104	for my $i (0 .. $#idx)
105	if ($idx[$i] != $i) # need we move this block?
106	copy encoded block $idx[$i] to position $i
107	}
108	}
109
110	The "copy" method can be helpful here.
111
112	This method destroys the block array as set up by
113	"set_encode_blocks".
114
115	$fec->shuffle ([array_of_blocks], [array_of_indices])
116	The same same as "set_decode_blocks", with the exception that the
117	blocks are not actually set for decoding.
118
119	This method is not normally used, but if you want to move blocks
120	around after reordering and before decoding, then calling "shuffle"
121	followed by "set_decode_blocks" incurs lower overhead than calling
122	"set_decode_blocks" twice, as files are not mmapped etc.
123
124	$fec->decode
125	Decode the blocks set by a prior call to "set_decode_blocks".
126
127	This method destroys the block array as set up by
128	"set_decode_blocks".
129
130	$fec->copy ($srcblock, $dstblock)
131	Utility function that simply copies one block (specified like in
132	"set_encode_blocks") into another. This, btw., destroys the blocks
133	set by "set_*_blocks".
134
135	COMPATIBILITY
136	The way this module works is compatible with the way freenet
137	(<http://freenet.sf.net>) encodes files. Comaptibility to other file
138	formats or networks is not known, please tell me if you find more
139	examples.
140
141	SEE ALSO
142	Net::FCP. And the author, who might be happy to receive mail from any
143	user, just to see that this rather rarely-used module is actually being
144	used (except for freenet ;)
145
146	BUGS
147	* too complicated.
148	* largely untested, please change this.
149	* file descriptors are not supported, but should be.
150	* utility functions for files should be provided.
151	* 16 bit version not tested
152
153	AUTHOR
154	Marc Lehmann <schmorp@schmorp.de>
155	http://home.schmorp.de
156