Crate reed_solomon

Source
Expand description

Reed-Solomon BCH encoder and decoder suitable for no_std environment.

This library implements block encoder and decoder: error correction code is appended to original data.

§Example

extern crate reed_solomon;

use reed_solomon::Encoder;
use reed_solomon::Decoder;

fn main() {
    let data = b"Hello World!";

    // Length of error correction code
    let ecc_len = 8;

    // Create encoder and decoder with
    let enc = Encoder::new(ecc_len);
    let dec = Decoder::new(ecc_len);

    // Encode data
    let encoded = enc.encode(&data[..]);

    // Simulate some transmission errors
    let mut corrupted = *encoded;
    for i in 0..4 {
        corrupted[i] = 0x0;
    }

    // Try to recover data
    let known_erasures = [0];
    let recovered = dec.correct(&mut corrupted, Some(&known_erasures)).unwrap();

    let orig_str = std::str::from_utf8(data).unwrap();
    let recv_str = std::str::from_utf8(recovered.data()).unwrap();

    println!("message:               {:?}", orig_str);
    println!("original data:         {:?}", data);
    println!("error correction code: {:?}", encoded.ecc());
    println!("corrupted:             {:?}", corrupted);
    println!("repaired:              {:?}", recv_str);
}

§Unsafe

This library uses some slices indexind that is boundary checked.

You can disable checks with library feature unsafe_indexing, then unsafe Slice::get_inchecked() would be utilized to improve speed where unchecked indexing is considered safe and LLVM cannot drop boundary checks.

§Bandwidth

Software implementation is relatively slow because general purpose processors do not support Galois field arithmetic operations. For example, Galois field multiply requires test for 0, two table look-ups, modulo add, and anti-log table look-up.

Besides this performance bound, current implementation is not very optimal and performs some unnecessary memcpys.

Encoder bandwidth using one Sandy Bridge core operating on 2.8 GHz:

data
 ecc bandwidth
251 4 115.20 MB/s
239 16 37.76 MB/s
223 32 19.59 MB/s

Decoder bandwidth using one Sandy Bridge core operating on 2.8 GHz:

data
 ecc errors bandwidth
251 4 0
 49 MB/s


1 16.91 MB/s

2 15.90 MB/s
239 16 0 10.75 MB/s
1 4.86 MB/s
8 3.81 MB/s
223 32 0 4.80 MB/s
1 2.32 MB/s
16 1.82 MB/s

Structs§

Enums§