#reed-solomon #erasure #encoding #algorithm

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

#76 in Algorithms

Download history 29179/week @ 2023-11-01 26676/week @ 2023-11-08 29194/week @ 2023-11-15 32319/week @ 2023-11-22 28631/week @ 2023-11-29 25218/week @ 2023-12-06 21492/week @ 2023-12-13 15189/week @ 2023-12-20 8201/week @ 2023-12-27 17052/week @ 2024-01-03 21168/week @ 2024-01-10 26368/week @ 2024-01-17 25691/week @ 2024-01-24 20608/week @ 2024-01-31 25407/week @ 2024-02-07 22319/week @ 2024-02-14

98,038 downloads per month
Used in 19 crates (4 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

~1–2MB
~37K SLoC