moon-raptorq

    Bounded pure MoonBit RFC 6330 RaptorQ with incremental decoding and interoperability checks

    raptorq
    fec
    rfc6330
    erasure-coding
    Download zip
    Author
    Version
    0.1.0
    License
    Apache-2.0
    Last updated
    5 hours ago
    Downloads
    4

    #MoonRaptorQ

    面向丢包环境对象分发的纯 MoonBit RaptorQ 库。实现 RFC 6330 的系统式编码、LDPC/HDPC 预编码和 GF(256) 恢复,支持按需生成修复符号。它与原来的 moonbit-roaring 是独立项目。

    项目定位、三个使用场景和交付范围见项目申报书。

    当前是有明确规模限制的实现,重点是标准符号互操作和可检查的恢复过程。它不是完整规模的 RFC 6330 实现,也没有采用稀疏失活译码。

    #支持范围

    项目当前支持
    单源块K=1~256,符号大小 T=1~4096 字节
    多源块对象Z=1~16,每块 K≤256,总对象最多 16 MiB
    子块与对齐N=1、Al=1;不支持子块交织
    标准报文12 字节 OTI;1 字节源块号、3 字节 ESI、一个 T 字节符号
    编码符号 ID0~16,777,215;源符号与修复符号正确映射到内部 ISI
    接收上限每块保留 K+64 个不同 ESI;重复包不占额外名额
    后端Wasm、Wasm GC、JavaScript

    Encoder 直接建立中间符号;EncodingPlan 允许复用同一 K 的编码变换。Decoder 提供批量恢复,StreamDecoder 每包更新一次方程基础,并公开独立秩和剩余自由度。ObjectDecoder 完成一个块后释放其消元矩阵,通过活跃块预算限制内存。PacketFramer 和 ObjectFramer 接受任意字节分片,遇到错误时整次输入回滚。

    单块接收器支持检查点:保存已收标准符号、OTI 和 CRC32C,重启后可恢复成批量或流式接收器。外层检查点是本项目自己的存储格式,不是 RFC 网络报文,也不提供真实性验证。

    收到 K 个不同符号不等于一定能恢复。 应检查解码结果或独立秩,必要时继续接收修复符号。RaptorQ 处理擦除,不提供对象身份、密码学完整性或真实性。恢复结果进入真实固件、配置或资源系统前,应由上层验证对象摘要和签名。

    #运行

    本次验证使用 MoonBit v0.10.19、moon 0.1.20261102。先执行:

    moon update moon check --deny-warn moon test --release --deny-warn moon run examples/multicast --release moon run examples/device --release moon run examples/edge --release --target js moon run examples/object --release moon run examples/resume --release

    前三个示例分别模拟多接收方资源分发、设备传输中断和边缘对象交接;另外两个演示多源块内存释放与检查点续传。它们都是离线模拟,没有声称已经接入真实设备或浏览器页面。

    CLI 接受十六进制字节,适合检查报文和小规模联调:

    moon run cmd/main --release -- encode 4 0102030405060708 2 12 moon run cmd/main --release -- estimate 1048576 4096 moon run cmd/main --release -- --help

    第一条输出 OTI 和修复包。将 OTI 与若干包的十六进制内容依次传给 decode OTI_HEX PACKET_HEX ... 即可恢复;方程不足时输出 waiting。大文件应使用库 API,避免命令行参数长度限制。

    save OTI_HEX PACKET_HEX ... 输出检查点;resume CHECKPOINT_HEX PACKET_HEX ... 加载检查点后继续收包。未完成时会输出更新的检查点和 waiting,完成后输出原始数据。

    在其他 MoonBit 包中,通过 moon.pkg 导入本模块并取别名 rq:

    let source = b"MoonBit object distribution"
    let encoder = @rq.Encoder::new(source, 4).unwrap()
    let receiver = @rq.StreamDecoder::new(encoder.config())
    let k = encoder.config().source_symbols()
    for id in k..<(2 * k + 8) {
    ignore(receiver.push_bytes(encoder.packet(id).unwrap().serialize()).unwrap())
    }
    assert_eq(receiver.decode().unwrap(), Some(source))

    源码仓库:cauchyQ/moon-raptorq。发布版本为 cauchyQ/moon-raptorq@0.1.0,在消费项目中执行 moon add cauchyQ/moon-raptorq@0.1.0 安装,然后在 moon.pkg 导入并取别名 rq。

    #独立验证与对照

    核心库只调用 MoonBit 标准库;模块中的 MoonErasure 和 MoonRecoder 依赖用于对照实验,没有参与本库编解码。独立参考是 Rust raptorq==2.0.0,Python 仅负责调用其编译后的实现。

    Linux 下安装参考库并运行:

    python -m pip install --target .verification/reference-python2 raptorq==2.0.0 python tools/verify_interop.py python tools/benchmark.py python tools/scaling.py python tools/check.py python tools/source_lines.py

    Windows 上,互操作脚本通过 WSL 调用 Linux Python。将参考库安装到同一个 .verification/reference-python2 目录即可;普通 MoonBit 测试和示例不依赖 WSL。

    多块验证由独立 Python 划分对象,再逐块调用 Rust 编解码器,并检查完整对象重组。Rust Python 接口没有自定义多块 OTI 入口,因此没有把它写成 Rust 完整多块接口的端到端验证。

    #来源和许可证

    Apache-2.0,见 LICENSE 与 NOTICE。标准常量和 HDPC 递推参考 cberner/raptorq 的固定版本;归属和修改范围已记录。固定常量、自动生成的参考向量与手写代码分开统计,见 代码统计。

    本项目解决的是有界标准纠删码和对象恢复,无法凭代码行数或本地测试保证比赛验收结果。正式提交时应核对发布版本、远程 CI 和申报材料,后续开发记录应持续、真实地积累。

    Basis

    type Basis

    Online row echelon form. A pivot owns its row and right-hand side.

    Config

    pub struct Config {
    // private fields
    }

    Validated single-block, single-subblock RFC 6330 profile.

    Config::new

    fn Config::new(length : Int, symbol_size : Int) -> Result[Config, RaptorError]

    Small bounded profile: 1..256 source symbols, 1..4096 bytes per symbol.

    Config::parse_packet

    fn Config::parse_packet(self : Config, bytes : Bytes) -> Result[Packet, RaptorError]

    Strict one-symbol packet framing; aggregation is outside this API.

    Config::serialize

    fn Config::serialize(self : Config) -> Bytes

    Standard 12-byte Object Transmission Information (Z=1, N=1, Al=1).

    Config::source_symbols

    fn Config::source_symbols(self : Config) -> Int

    Config::stream_storage

    fn Config::stream_storage(self : Config) -> StorageEstimate

    Conservative raw-element bound when K+64 packets have been retained and a full-rank decode is in progress. This is not a measured process peak RSS.

    Config::symbol_size

    fn Config::symbol_size(self : Config) -> Int

    Config::transfer_length

    fn Config::transfer_length(self : Config) -> Int

    Decoder

    pub struct Decoder {
    // private fields
    }

    Bounded receiver with duplicate checking and no hidden decode on insertion.

    Decoder::checkpoint

    fn Decoder::checkpoint(self : Decoder) -> Bytes

    Retain portable symbols instead of serializing backend-specific matrices.

    Decoder::decode

    fn Decoder::decode(self : Decoder) -> Result[Bytes?, RaptorError]

    None means insufficient independent equations, not a malformed packet.

    Decoder::new

    fn Decoder::new(config : Config) -> Decoder

    Decoder::push

    fn Decoder::push(self : Decoder, packet : Packet) -> Result[Bool, RaptorError]

    True when a new symbol was retained; identical retransmissions return false.

    Decoder::push_bytes

    fn Decoder::push_bytes(self : Decoder, bytes : Bytes) -> Result[Bool, RaptorError]

    Decoder::received

    fn Decoder::received(self : Decoder) -> Int

    Encoder

    pub struct Encoder {
    // private fields
    }

    Immutable encoder retaining intermediate symbols for on-demand repairs.

    Encoder::config

    fn Encoder::config(self : Encoder) -> Config

    Encoder::new

    fn Encoder::new(data : Bytes, symbol_size : Int) -> Result[Encoder, RaptorError]

    Build the intermediate symbols using the RFC systematic constraints.

    Encoder::packet

    fn Encoder::packet(self : Encoder, id : Int) -> Result[Packet, RaptorError]

    ESI below K is systematic; ESI >=K generates repair symbols.

    EncodingPlan

    pub struct EncodingPlan {
    // private fields
    }

    Reusable linear encoding transform for objects with the same source-symbol count. Construction costs a dense solve; each object then needs only matrix products. Useful for repeated fixed-size telemetry or asset blocks.

    EncodingPlan::coefficient_bytes

    fn EncodingPlan::coefficient_bytes(self : EncodingPlan) -> Int

    Actual Int32 coefficient storage, excluding array headers and allocator overhead. Plans can be shared across different symbol sizes and objects.

    EncodingPlan::encode

    fn EncodingPlan::encode(self : EncodingPlan, data : Bytes, symbol_size : Int) -> Result[Encoder, RaptorError]

    EncodingPlan::new

    fn EncodingPlan::new(source_symbols : Int) -> Result[EncodingPlan, RaptorError]

    EncodingPlan::source_symbols

    fn EncodingPlan::source_symbols(self : EncodingPlan) -> Int

    FrameBuffer

    type FrameBuffer

    Incremental parser for concatenated single-symbol RFC packets with the same OTI. Symbol size fixes the frame length; no extra wire bytes are added.

    ObjectConfig

    pub struct ObjectConfig {
    // private fields
    }

    RFC 6330 object profile with up to 16 source blocks, N=1 and Al=1. Each block has at most 256 source symbols. This does not support sub-block interleaving or the full standard's large-block parameter range.

    ObjectConfig::automatic

    fn ObjectConfig::automatic(length : Int, symbol_size : Int) -> Result[ObjectConfig, RaptorError]

    Choose the fewest blocks that keep every source block within K<=256.

    ObjectConfig::block_config

    fn ObjectConfig::block_config(self : ObjectConfig, block : Int) -> Result[Config, RaptorError]

    ObjectConfig::block_offset

    fn ObjectConfig::block_offset(self : ObjectConfig, block : Int) -> Result[Int, RaptorError]

    ObjectConfig::new

    fn ObjectConfig::new(length : Int, symbol_size : Int, blocks : Int) -> Result[ObjectConfig, RaptorError]

    ObjectConfig::packet

    fn ObjectConfig::packet(self : ObjectConfig, block : Int, symbol : Packet) -> Result[ObjectPacket, RaptorError]

    ObjectConfig::parse_packet

    fn ObjectConfig::parse_packet(self : ObjectConfig, bytes : Bytes) -> Result[ObjectPacket, RaptorError]

    ObjectConfig::serialize

    fn ObjectConfig::serialize(self : ObjectConfig) -> Bytes

    ObjectConfig::source_blocks

    fn ObjectConfig::source_blocks(self : ObjectConfig) -> Int

    ObjectConfig::symbol_size

    fn ObjectConfig::symbol_size(self : ObjectConfig) -> Int

    ObjectConfig::transfer_length

    fn ObjectConfig::transfer_length(self : ObjectConfig) -> Int

    ObjectDecoder

    pub struct ObjectDecoder {
    // private fields
    }

    Completed blocks retain only recovered bytes and release the elimination basis. An explicit active-block budget prevents interleaved arrivals from allocating all block matrices at once. Completed blocks ignore late packets; authentication and object identity remain the surrounding protocol's job.

    ObjectDecoder::active_blocks

    fn ObjectDecoder::active_blocks(self : ObjectDecoder) -> Int

    ObjectDecoder::block_progress

    fn ObjectDecoder::block_progress(self : ObjectDecoder, index : Int) -> Result[Progress, RaptorError]

    ObjectDecoder::completed_blocks

    fn ObjectDecoder::completed_blocks(self : ObjectDecoder) -> Int

    ObjectDecoder::decode

    fn ObjectDecoder::decode(self : ObjectDecoder) -> Bytes?

    ObjectDecoder::new

    fn ObjectDecoder::new(config : ObjectConfig, max_active_blocks? : Int) -> Result[ObjectDecoder, RaptorError]

    ObjectDecoder::push

    fn ObjectDecoder::push(self : ObjectDecoder, packet : ObjectPacket) -> Result[Bool, RaptorError]

    New symbols update one block. Completing a block performs one back substitution and releases its dense state. Late packets for it return false.

    ObjectDecoder::push_bytes

    fn ObjectDecoder::push_bytes(self : ObjectDecoder, bytes : Bytes) -> Result[Bool, RaptorError]

    ObjectEncoder

    pub struct ObjectEncoder {
    // private fields
    }

    Stores the original object and constructs one source-block encoder on request. Callers can release that encoder before moving to the next block.

    ObjectEncoder::block

    fn ObjectEncoder::block(self : ObjectEncoder, index : Int) -> Result[Encoder, RaptorError]

    ObjectEncoder::config

    ObjectEncoder::new

    fn ObjectEncoder::new(data : Bytes, symbol_size : Int, blocks : Int) -> Result[ObjectEncoder, RaptorError]

    ObjectFramer

    pub struct ObjectFramer {
    // private fields
    }

    Identical byte-stream framing with source block demultiplexing. Each frame must use a valid source block number from the object's OTI.

    ObjectFramer::buffered

    fn ObjectFramer::buffered(self : ObjectFramer) -> Int

    ObjectFramer::finish

    fn ObjectFramer::finish(self : ObjectFramer) -> Result[Int, RaptorError]

    ObjectFramer::new

    fn ObjectFramer::new(config : ObjectConfig, max_packets? : Int) -> Result[ObjectFramer, RaptorError]

    ObjectFramer::parsed

    fn ObjectFramer::parsed(self : ObjectFramer) -> Int

    ObjectFramer::push

    fn ObjectFramer::push(self : ObjectFramer, chunk : Bytes) -> Result[Array[ObjectPacket], RaptorError]

    ObjectPacket

    pub struct ObjectPacket {
    // private fields
    }

    A standard source block number plus the same 24-bit ESI and symbol bytes used by Packet. OTI is external, as specified by RFC 6330.

    ObjectPacket::block

    fn ObjectPacket::block(self : ObjectPacket) -> Int

    ObjectPacket::serialize

    fn ObjectPacket::serialize(self : ObjectPacket) -> Bytes

    ObjectPacket::symbol

    fn ObjectPacket::symbol(self : ObjectPacket) -> Packet

    Packet

    pub struct Packet {
    // private fields
    }

    One standard FEC payload ID followed by exactly one encoding symbol.

    Packet::id

    fn Packet::id(self : Packet) -> Int

    Packet::new

    fn Packet::new(id : Int, payload : Bytes) -> Result[Packet, RaptorError]

    Source block number is zero in the supported single-block profile.

    Packet::payload

    fn Packet::payload(self : Packet) -> Bytes

    Packet::serialize

    fn Packet::serialize(self : Packet) -> Bytes

    PacketFramer

    pub struct PacketFramer {
    // private fields
    }

    Framing for the single-source-block API. Chunk errors are atomic; finish rejects a truncated frame and seals the reader after success.

    PacketFramer::buffered

    fn PacketFramer::buffered(self : PacketFramer) -> Int

    PacketFramer::finish

    fn PacketFramer::finish(self : PacketFramer) -> Result[Int, RaptorError]

    PacketFramer::new

    fn PacketFramer::new(config : Config, max_packets? : Int) -> Result[PacketFramer, RaptorError]

    PacketFramer::parsed

    fn PacketFramer::parsed(self : PacketFramer) -> Int

    PacketFramer::push

    fn PacketFramer::push(self : PacketFramer, chunk : Bytes) -> Result[Array[Packet], RaptorError]

    Progress

    pub(all) struct Progress {
    received : Int
    independent : Int
    required : Int
    }

    Progress counts independent source information, not just packet arrivals.

    Progress::complete

    fn Progress::complete(self : Progress) -> Bool

    Progress::remaining

    fn Progress::remaining(self : Progress) -> Int

    RaptorError

    pub(all) enum RaptorError {
    InvalidParameters(String)
    UnsupportedProfile(String)
    InvalidPacket(String)
    ResourceLimit(String)
    ConflictingDuplicate(Int)
    InconsistentEquations
    }

    Explicit limits for the dense reference solver.

    RaptorError::message

    fn RaptorError::message(self : RaptorError) -> String

    StorageEstimate

    pub(all) struct StorageEstimate {
    coefficient_bytes : Int
    symbol_bytes : Int
    retained_payload_bytes : Int
    decode_scratch_bytes : Int
    shared_field_table_bytes : Int
    }

    Raw numeric storage for the supported streaming profile. Array headers, allocator overhead, input ownership and runtime GC space are not included.

    StorageEstimate::raw_total

    fn StorageEstimate::raw_total(self : StorageEstimate) -> Int

    StreamDecoder

    pub struct StreamDecoder {
    // private fields
    }

    Bounded incremental GF(256) receiver. Each packet is reduced once; repeated decode calls do not rebuild or eliminate the full constraint matrix.

    StreamDecoder::checkpoint

    fn StreamDecoder::checkpoint(self : StreamDecoder) -> Bytes

    StreamDecoder::config

    fn StreamDecoder::config(self : StreamDecoder) -> Config

    StreamDecoder::decode

    fn StreamDecoder::decode(self : StreamDecoder) -> Result[Bytes?, RaptorError]

    StreamDecoder::new

    fn StreamDecoder::new(config : Config) -> StreamDecoder

    StreamDecoder::progress

    fn StreamDecoder::progress(self : StreamDecoder) -> Progress

    StreamDecoder::push

    fn StreamDecoder::push(self : StreamDecoder, packet : Packet) -> Result[Bool, RaptorError]

    A retained packet can be algebraically dependent and still be new. The return value reports retention; use progress() for independent rank. Inconsistent equations are rejected without retaining the packet.

    StreamDecoder::push_bytes

    fn StreamDecoder::push_bytes(self : StreamDecoder, bytes : Bytes) -> Result[Bool, RaptorError]

    parse_config

    fn parse_config(bytes : Bytes) -> Result[Config, RaptorError]

    Parse only the explicitly supported single-source-block profile.

    parse_object_config

    fn parse_object_config(bytes : Bytes) -> Result[ObjectConfig, RaptorError]

    restore_decoder

    fn restore_decoder(bytes : Bytes) -> Result[Decoder, RaptorError]

    Restoring a batch decoder validates framing and duplicates. Algebraic consistency is checked at decode(), as with ordinary batch insertion.

    restore_stream_decoder

    fn restore_stream_decoder(bytes : Bytes) -> Result[StreamDecoder, RaptorError]

    Restoring a streaming decoder replays each saved symbol once. A checksum match does not exempt equations from the normal consistency checks.