NAME
vdmfec - Block ECC for files
SYNOPSIS
vdmfec [-v] [-d] [-b blocksize] [-n N] [-k K] [file]
vdm_encode [-v] [-b blocksize] [-n N] [-k K] [file]
vdm_decode [-v] [-b blocksize] [-n N] [-k K] [file]
DESCRIPTION
vdmfec reads an input stream and adds error correction blocks so that
large consecutive sections of the output stream may be corrupted, and
the data recovered. For example, diskettes typically lose whole
sectors at once, or related groups of sectors, or even entire tracks.
Data written to a diskette with this program may be recovered even with
many read errors.
The algorithm used is a Forward Error Correction (FEC) code based on
Vandermonde (VDM) matrices in GF(2^8) due to Luigi Rizzo. Given the
FEC parameters K and N, with N greater than K, N blocks are written for
every K input blocks in such a way that any K blocks are sufficient to
reconstruct the data. That is, up to N - K blocks out of every group
of N blocks may be lost without loss of data.
The amount of overhead in the output stream is easily adjustable by
varying K. N and blocksize control the total amount of data written.
Depending on the types of errors you expect, different settings may be
more or less useful. For example, you may not expect to have two or
three bad sectors on every track (if you do it’s time to replace the
diskette!), but you might expect three bad sectors on two or three
contiguous tracks (diskette errors tend to cluster).
OPTIONS
-v Print informative messages about the encoding or decoding
process to stderr, including the expansion factor. Use -vv to
get information about each block being read or written.
-d Decode the input rather than encoding it. Using this option is
equivalent to invoking the program as vdm_decode.
-b blocksize
Set the FEC block size to blocksize bytes. The blocksize may
have a ’k’ or ’K’ appended, in which case the block size is set
to blocksize * 1024 bytes. This should usually be a multiple of
the output media block or sector size (e.g., 512, 1024, 18K,
etc.), and must be at least 26 bytes in version 1. Default
1024.
-n N -k K
Set the FEC N and K parameters. N must be greater than 2 and
less than or equal to 256. K must be greater than 0 and less
than N. Default N=18, K=14.
Note that the N, K, and blocksize parameters are NOT written to the
output! You must specify the same parameters when you run the decoder.
(Actually, the decoder is capable of explicitly detecting an invalid K
value, but incorrect blocksize or N values will result in bad blocks
and decode failure.)
The decoder is capable of reading from non-seekable media such as
pipes, however, buffer underruns are not detected and will result in
failure. Also, when reading from a pipe the entire file must be read.
Reading from a seek-able stream can be faster because only K good
blocks out of N need to be read.
The encoder stores chunk and block ids which are used to detect out of
order blocks, but those errors (which can sometimes happen due to
filesystem corruption) are not corrected. The only type of error that
can be corrected is in place corruption of data. In particular,
missing blocks (as from lost packets) result in decode failure, even
when K good blocks are available. This program is primarily intended
to recover data lost due to read errors on fixed media such as
diskettes; several other programs and libraries are available that use
FEC to handle the other (typically network packet) errors.
EXAMPLES
Consider a diskette with 80 tracks, 2 heads, and 18 512-byte sectors
per track (a standard 1.44MB diskette).
bzip2 < file | vdmfec > /dev/fd0
uses the default parameters of -b1k -n18 -k14, stores up to ~1.1MB of
compressed input data, written one (double-sided) track (18K) at a
time, and allows 4 bad clusters (8 sectors) per track.
vdmfec -d /dev/fd0 | bunzip2 > file
recovers the original file.
vdm_encode -b18k -n80 -k70 file.img > /dev/fd0
writes the entire diskette, stores up to ~1.23MB of data, and allows
multiple errors on 10 different double-sided tracks.
vdm_decode -b18k -n80 -k70 /dev/fd0 > file.img
recovers the data and reads no less than 70 tracks. Note that
vdm_decode exits with a non-zero status on failure, so that
constructions such as
vdm_decode /dev/fd0 > moo && tar -xvf moo
are possible.
dd if=/dev/tape ibs=1024 conv=noerror,sync | \
vdm_decode > file
This might be necessary to recover data from some non-seekable media.
You can of course simply write the encoded output to a normal file, as
in
tar -cf - dir | gzip | vdm_encode -v > dir.tgz.vdm
REPORTING BUGS
Report bugs to Tom Holroyd <tomh@po.crl.go.jp>.
SEE ALSO
fec(3)