reed-solomon-simd

基于 Leopard-RS 的 Reed-Solomon 侵蚀编码，具有

• O(n log n) 复杂度。
• 完全用 Rust 编写。
• 在 AArch64 (Neon) 和 x86(-64) (SSSE3 和 AVX2) 上运行时选择最佳的 SIMD 实现，并提供回退到纯 Rust。
• 可以组合 1 - 32768 个原始碎片和 1 - 32768 个恢复碎片。
• 还可以使用以下限制实现多达 65535 个原始或恢复碎片

基准测试

• AMD Ryzen 5 3600 (Zen 2, 2019) 的单核 AVX2。
• 在 Apple Silicon M1 CPU 上的吞吐量大约相同 (+-10%)。
• MiB/s 和 GiB/s 是关于总数据量，即原始碎片 + 恢复碎片的。
  • 对于解码器，这包括丢失的碎片。
• 碎片大小为 1024 字节。
• 编码基准
  • 包含add_original_shard和encode方法，属于ReedSolomonEncoder。
• 解码基准测试
  • 对于1%和100%的原数据块丢失，提供了最大可能的2 MiB/s值。
  • 提供了解码器所需的最少数据块数量。
  • 包含add_original_shard、add_recovery_shard和decode方法，属于ReedSolomonDecoder。

请克隆reed-solomon-simd并运行自己的基准测试

$ cargo bench main

简单用法

1. 将数据分成大小相等的原始数据块。数据块大小必须是64字节的倍数。
2. 确定您想要的恢复数据块数量。
3. 使用reed_solomon_simd::encode生成恢复数据块。
4. 当一些原始数据块丢失时，使用reed_solomon_simd::decode恢复它们。
   • 您必须提供至少与原始数据块总数相等的数据块数量，可以是原始数据块和恢复数据块的任何组合。

注意：此包不检测或纠正数据块内的错误。因此，如果数据损坏是一个可能的场景，您应该在每个数据块中包含一个错误检测哈希，并跳过向解码器提供损坏的数据块。以下是一些非常快速的错误检测哈希建议：CRC32c（4字节）、HighwayHash（8、16或32字节）或xxHash（4、8或16字节）。

示例

将数据分成3个64字节的原始数据块，并生成5个恢复数据块。假设原始数据块#0和#2丢失，并通过提供1个原始数据块和2个恢复数据块来恢复它们。

let original = [
    b"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do ",
    b"eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut e",
    b"nim ad minim veniam, quis nostrud exercitation ullamco laboris n",
];

let recovery = reed_solomon_simd::encode(
    3, // total number of original shards
    5, // total number of recovery shards
    original, // all original shards
)?;

let restored = reed_solomon_simd::decode(
    3, // total number of original shards
    5, // total number of recovery shards
    [  // provided original shards with indexes
        (1, &original[1]),
    ],
    [  // provided recovery shards with indexes
        (1, &recovery[1]),
        (4, &recovery[4]),
    ],
)?;

assert_eq!(restored[&0], original[0]);
assert_eq!(restored[&2], original[2]);
# Ok::<(), reed_solomon_simd::Error>(())

基本用法

ReedSolomonEncoder和ReedSolomonDecoder提供了对编码/解码过程的更多控制。

以下是使用这些示例

use reed_solomon_simd::{ReedSolomonDecoder, ReedSolomonEncoder};
use std::collections::HashMap;

let original = [
    b"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do ",
    b"eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut e",
    b"nim ad minim veniam, quis nostrud exercitation ullamco laboris n",
];

let mut encoder = ReedSolomonEncoder::new(
    3, // total number of original shards
    5, // total number of recovery shards
    64, // shard size in bytes
)?;

for original in original {
    encoder.add_original_shard(original)?;
}

let result = encoder.encode()?;
let recovery: Vec<_> = result.recovery_iter().collect();

let mut decoder = ReedSolomonDecoder::new(
    3, // total number of original shards
    5, // total number of recovery shards
    64, // shard size in bytes
)?;

decoder.add_original_shard(1, original[1])?;
decoder.add_recovery_shard(1, recovery[1])?;
decoder.add_recovery_shard(4, recovery[4])?;

let result = decoder.decode()?;
let restored: HashMap<_, _> = result.restored_original_iter().collect();

assert_eq!(restored[&0], original[0]);
assert_eq!(restored[&2], original[2]);
# Ok::<(), reed_solomon_simd::Error>(())

高级用法

请参阅rate模块，以了解使用所选Engine和Rate进行高级编码/解码的方法。

与其他crate的基准测试

使用cargo run --release --example quick-comparison运行针对reed-solomon-16、reed-solomon-erasure和reed-solomon-novelpolycrate的几个简单基准测试。

该软件包在我的AMD Ryzen 5 3600上在所有情况下都是最快的，除了在解码大约42个或更少的恢复碎片时。此外，还有一次性的初始化（小于10毫秒）来计算表，这在处理非常小的数据量时可能会占主导地位。

运行测试

一些较大的测试被标记为 #[ignore]，并且不会与 cargo test 一起运行。使用 cargo test -- --ignored 来运行这些测试。

安全性

此软件包中 unsafe 的唯一用途是允许在 Ssse3、Avx2 和 Neon 中进行针对特定目标的最优化。

致谢

该软件包是Markus Laire的reed-solomon-16软件包的分支，该软件包又基于Christopher A. Taylor的Leopard-RS。