package reed-solomon-erasure
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=0d45118bc1ed3e1b8a4c8c05be9d8ad759e69d3b755b9448f7e35ac77da0ee2d
md5=0f58928d8b29de0081a5f5ffda89b070
Description
This library provides an encoder/decoder for Reed-Solomon erasure code.
Please note that erasure coding means errors are not directly detected or corrected, but missing data pieces(shards) can be reconstructed given that the configuration provides high enough redundancy.
You will have to implement error detection separately(e.g. via checksums) and simply leave out the corrupted shards when attempting to reconstruct the missing data.
Published: 29 Jun 2018
README
ocaml-reed-solomon-erasure
OCaml implementation of Reed-Solomon erasure coding
This is a port of reed-solomon-erasure, which is a port of several other libraries.
The SIMD C code is copied from Nicolas Trangez's Haskell implementation with minor modifications.
Installation
You can install the library via opam
opam install reed-solomon-erasure
Example
open Reed_solomon_erasure
let () =
let r = ReedSolomon.make 3 2 in (* 3 data shards, 2 parity shards *)
let master_copy = [|"\000\001\002\003";
"\004\005\006\007";
"\008\009\010\011";
"\000\000\000\000"; (* last 2 rows are parity shards *)
"\000\000\000\000"|] in
(* Construct the parity shards *)
ReedSolomon.encode_str r master_copy;
(* Make a copy and transform it into option shards arrangement
for feeding into reconstruct_opt_bytes *)
let shards = RS_Shard_utils.shards_to_option_shards_str master_copy in
(* We can remove up to 2 shards, which may be data or parity shards *)
shards.(0) <- None;
shards.(4) <- None;
(* Try to reconstruct missing shards *)
ReedSolomon.reconstruct_opt_str r shards;
(* Convert back to normal shard arrangement *)
let result = RS_Shard_utils.option_shards_to_shards_str shards in
assert (ReedSolomon.verify_str r result);
assert (master_copy = result)
Performance
The encoding performance is shown below
Machine : laptop with Intel(R) Core(TM) i5-3337U CPU @ 1.80GHz (max 2.70GHz) 2 Cores 4 Threads
Configuration | Klaus Post's | reed-solomon-erasure (Rust) | ocaml-reed-solomon-erasure (bigstr) | ... (bytes) | ... (str) |
---|---|---|---|---|---|
10x2x1M | ~7800MB/s | ~4800MB/s | ~3200MB/s | ~1500MB/s | ~1500MB/s |
Changelog
Contributions
Contributions are welcome. Note that by submitting contributions, you agree to license your work under the same license used by this project(MIT).
Credits
Many thanks to Ming for testing the library on macOS platform.
Notes
Code quality review
If you'd like to evaluate the quality of this library, you may find audit comments helpful.
Simply search for "AUDIT" to see the dev notes that are aimed at facilitating code reviews.
License
Nicolas Trangez's Haskell Reed-Solomon implementation
The C files for SIMD operations are copied(with no/minor modifications) from Nicolas Trangez's Haskell implementation, and are under the same MIT License as used by NicolasT's project
TL;DR
All files are released under the MIT License
Dependencies (7)
- ctypes-foreign
- ctypes
- core_kernel
-
bisect_ppx
build & < "2.6.0"
-
cppo
build
-
jbuilder
>= "1.0+beta7"
-
ocaml
>= "4.06"
Dev Dependencies
None
Used by
None