#reed-solomon #codec #erasure #algorithm #encoding

reed-solomon-novelpoly

An implementation of a reed solomon code / encoder / decoder with complexity O(n lg(n))

6 releases (stable)

2.0.0 Jan 25, 2024
1.0.2 Sep 17, 2023
1.0.1 Aug 30, 2023
1.0.0 Mar 26, 2021
0.0.3 Mar 19, 2021

#51 in Algorithms

Download history 24845/week @ 2024-06-13 26213/week @ 2024-06-20 24805/week @ 2024-06-27 23611/week @ 2024-07-04 28466/week @ 2024-07-11 34083/week @ 2024-07-18 31462/week @ 2024-07-25 25765/week @ 2024-08-01 39598/week @ 2024-08-08 33119/week @ 2024-08-15 32148/week @ 2024-08-22 38137/week @ 2024-08-29 39349/week @ 2024-09-05 35722/week @ 2024-09-12 36500/week @ 2024-09-19 25569/week @ 2024-09-26

143,152 downloads per month
Used in 36 crates (3 directly)

Apache-2.0 AND MIT

110KB
2.5K SLoC

Rust 2.5K SLoC // 0.1% comments C 269 SLoC // 0.1% comments

reed-solomon-novelpoly

An implementation of Novel Polynomial Basis and its Application to Reed-Solomon Erasure Codes 1 2 3.

Runs encoding and reconstruction in O(n lg(n)). Note that for small number n there is a static offset due to a walsh transform over the full domain in reconstruction.

Goals

Be really fast for n > 100.

Benchmarking

For benchmarking the implementation against itself and the naive implementation, criterion is used.

cargo bench

Fuzzing

Currently honggfuzz is used.

Install cargo install cargo-hongg and run with:

cargo-hongg fuzz --bin <binary_name>

Dependencies

~0.9–2MB
~36K SLoC