https://github.com/Bulat-Ziganshin/FastECC Skip to content Sign up * Product + Features + Mobile + Actions + Codespaces + Copilot + Packages + Security + Code review + Issues + Integrations + GitHub Sponsors + Customer stories * Team * Enterprise * Explore + Explore GitHub + Learn and contribute + Topics + Collections + Trending + Skills + GitHub Sponsors + Open source guides + Connect with others + The ReadME Project + Events + Community forum + GitHub Education + GitHub Stars program * Marketplace * Pricing + Plans + Compare plans + Contact Sales + Education [ ] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this user All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up {{ message }} Bulat-Ziganshin / FastECC Public * Notifications * Fork 35 * Star 337 Reed-Solomon coder computing one million parity blocks at 1 GB/s. O (N*log(N)) algo employing FFT. License Apache-2.0 license 337 stars 35 forks Star Notifications * Code * Issues 4 * Pull requests 0 * Actions * Projects 0 * Wiki * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Wiki * Security * Insights Bulat-Ziganshin/FastECC This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. master Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags 1 branch 0 tags Code Latest commit @Bulat-Ziganshin Bulat-Ziganshin ReedSolomonFFT-ru: added brief algorithm summary ... b8ca7db Aug 14, 2017 ReedSolomonFFT-ru: added brief algorithm summary b8ca7db Git stats * 200 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time .gitignore Benchmarks.md: final benchmark results and bechmarking script benchma... May 5, 2017 Benchmarks.md *.md: various minor edits May 15, 2017 GF(p).cpp GF(p): modified GF_Mul32 to provide SSE2-compatible code when SIMD>= S... Apr 30, 2017 GF.md GF.md: generic data packing algo and fast asm routine May 17, 2017 LICENSE Initial commit Nov 20, 2015 LargePages.cpp Linux: more changes required for compilation May 11, 2017 Makefile README: added links to the two papers May 18, 2017 NTT.md "ntt s" now benchmarks small NTTs, "ntt q" benchmarks slow NTT; "ECC"... May 13, 2017 Overview.md *.md: various minor edits May 15, 2017 README.md README: added info about Leopard and error decoding Jun 29, 2017 RS.cpp Linux: two more fixes May 12, 2017 RS.md *.md: various minor edits May 15, 2017 ReedSolomonFFT-ru.md ReedSolomonFFT-ru: added brief algorithm summary Aug 14, 2017 SIMD.h Use -DSIMD=AVX2/SSE42/SSE2 in compiler cmdline to choose code vectori... Apr 30, 2017 benchmark.cmd Benchmarks.md: final benchmark results and bechmarking script benchma... May 5, 2017 compile.cmd *.md: various minor edits May 15, 2017 compile.sh Linux: more changes required for compilation May 11, 2017 main.cpp "ntt s" now benchmarks small NTTs, "ntt q" benchmarks slow NTT; "ECC"... May 13, 2017 ntt.cpp Linux: two more fixes May 12, 2017 prime.cpp Minor edits Apr 24, 2017 wall_clock_timer.h Linux: more changes required for compilation May 11, 2017 View code [ ] What How Fast Faster Fastest Why not Roadmap Want to know more? Discussion README.md FastECC implements FFT-based O(N*log(N)) Reed-Solomon coder, running at 1.2 GB/s on i7-4770 for (n,k)=(2^20,2^19), i.e. calculating 524288 parity blocks from 524288 data blocks. It's also pretty fast for small orders, outperforming previously fastest Reed-Solomon library, Intel ISA-L for 64+ parity blocks. The encoding and decoding algorithms going to be implemented by FastECC were described in the paper An Efficient (n,k) Information Dispersal Algorithm based on Fermat Number Transforms by Sian-Jheng Lin and Wei-Ho Chung. FastECC v0.1 implements only encoding, so it isn't yet ready for real use. What Almost all existing Reed-Solomon ECC implementations employ matrix multiplication and thus have O(N^2) speed behavior, i.e. they can produce N parity blocks in O(N^2) time, thus spending O(N) time per block. F.e. the fastest implementation I know, MultiPar, can compute 1000 parity blocks at the speed ~50MB/s, but only at ~2 MB/s in its maximum configuration, 32000 parity blocks. And computations in GF(2^ 32), implemented in the same way, will build one million parity blocks at 50 KB/s. One of few exceptions is closed-source RSC32 by persicum with O(N*log (N)) speed, i.e. it spends O(log(N)) time per parity block. Its speed with million parity blocks is 100 MB/s, i.e. it computes one million of 4 KB parity blocks from one million of data blocks (processing 8 GB overall) in just 80 seconds. Note that all speeds mentioned here are measured on i7-4770, employing all features available in a particular program - including multi-threading, SIMD and x64 support. FastECC is open-source library implementing O(N*log(N)) encoding algorithm. It computes million parity blocks at [1.2 GB/s]. Future versions will implement decoding that's also O(N*log(N)), although 1.5-3 times slower than encoding. Current implementation is limited to 2^20 blocks, removing this limit is the main priority for future work aside of decoder implementation. And if you are interested in smaller configs, look at small NTT benchmarks - FastECC outperforms quadratic algorithms (ISA-L, CM256 and MultiPar) starting from 32-64 parity blocks. Leopard is a new library, faster than FastECC, especially for small orders. It implements similar algorithm, described in newer paper by the same authors: Lin, Han and Chung "Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes". You can also find a few research-grade libraries with O(N*log(N)) speed. For comparison - Wirehair, the best open-source LDPC codec I know, is O(N) and already as fast as FastECC, but can be made several times faster using SSE1. It's limited to 64000 source blocks, but amount of parity blocks can be arbitrary. It's an LDPC codec, so not MDS, but chances that it needs even a single extra block to recover is as low as 0.1%. Moreover, it works with binary data, so no need for recoding and no need for extra space to store "overflow" bits. How All O(N*log(N)) Reed-Solomon implementations I'm aware of, use fast transforms like FFT or FWT. FastECC employs fast Number-Theoretic Transform that is just an FFT over integer field or ring. Let's see how it works. Note that below by length-N polynomial I mean any polynomial with order < N. For any given set of N points, only one length-N polynomial may go through all these points. Let's consider N input words as values of some length-N polynomial at N fixed points, only one such polynomial may exist. Typical Reed-Solomon encoding computes coefficients of this unique polynomial (so-called polynomial interpolation), evaluates the polynomial at M another fixed points (the polynomial evaluation) and outputs these M words as the resulting parity data. At the decoding stage, we may receive any subset of N values out of those N source data words and M computed parity words. But since they all belong to the original length-N polynomial, we may recover this polynomial from N known points and then compute its values at other points, in particular those N points assigned to original data, thus restoring them. Fast Usually, Reed-Solomon libraries implement encoding by multiplication with Vandermonde matrix (O(N^2) algo) and decoding by multiplication with the matrix inverse. But with special choice of fixed points we can perform polynomial interpolation and evaluation at these points in O(N*log(N)) time, using NTT for evaluation and inverse NTT for interpolation. So, the fast encoding is as simple as: * consider N input words as values of length-N polynomial at N special points * compute the polynomial coefficients in O(N*log(N)) time using inverse NTT * evaluate the polynomial at another M special points in O(M*log (M)) time using NTT Decoding is more involved. We have N words representing values of length-N polynomial at some N points. Since we can't choose these points, we can't just use iNTT to compute the polynomial coefficients. So it's a generic polynomial interpolation problem that can be solved in O(N*log(N)^2) time. Faster But this specific polynomial interpolation problem has faster solution. Indeed, decoder knows values of length-N polynomial f(x) at N points a[i], but lost its values at M erasure points e[i]. Let's build "erasure locator" polynomial l(x) = (x-e[1])*...*(x-e[M]) and compute polynomial product p(x)=f(x)*l(x). We have order(p) = order (f)+order(l) < N+M and l(e[i])=0, so by computing values l(a[i]) and then multiplying f(x) and l(x) in the value space we can build polynomial p(x) with order