Fountain Codes

Pure Dart implementation of fountain codes for erasure coding.

Currently implemented:

  • LT Codes - Luby Transform codes
  • RaptorQ - RFC 6330 compliant implementation

Note: RaptorQ was historically subject to patent licensing claims; please evaluate any third-party patent/licensing obligations before commercial use (especially for products implementing wireless wide-area standards).

Usage

import 'package:fountain_codes/fountain_codes.dart';

// Encode
final codec = RaptorQCodec(config: FountainConfig(k: 10, t: 64));
codec.setSourceData(data);

final symbols = <Symbol>[];
for (int esi = 0; esi < 15; esi++) {
  symbols.add(codec.encode(0, esi));
}

// Decode
final decoder = RaptorQCodec(config: FountainConfig(k: 10, t: 64));
for (final symbol in symbols) {
  final result = decoder.submit(symbol);
  if (result.isComplete) {
    final decoded = decoder.getDecodedData();
    break;
  }
}

LT Codes

import 'package:fountain_codes/fountain_codes.dart';

final codec = LTCodec(config: FountainConfig(k: 100, t: 256));
codec.setSourceData(data);

// Generate encoding symbols
for (int seed = 0; ; seed++) {
  final symbol = codec.encode(0, seed);
  // transmit symbol...
}

Performance

Dart implementation is competitive with Rust implementation of RaptorQ for small data blocks (1.5x). For larger sizes, Rust version is faster by order of magnitude.

Encode Benchmark: Dart vs Rust (Symbol size: 1280 bytes)

Symbol Count Data per Block Dart Rust Gap
10 12.5 KB 163 Mbit/s 202 Mbit/s 1.2x
100 125 KB 159 Mbit/s 258 Mbit/s 1.6x
250 312 KB 83 Mbit/s 238 Mbit/s 2.9x
500 625 KB 39 Mbit/s 229 Mbit/s 5.9x
1000 1.25 MB 14.5 Mbit/s 221 Mbit/s 15x
2000 2.5 MB 4.4 Mbit/s 198 Mbit/s 45x

Decoding (we use 5% packet loss to avoid happy-path of 'no loss' case) is slower than Rust by 1-2 orders of magnitude.

Decode with 5% Packet Loss: Dart vs Rust

Symbol Count Dart Rust Gap
10 173 Mbit/s 3,047 Mbit/s 18x
100 163 Mbit/s 3,906 Mbit/s 24x
250 87 Mbit/s 4,059 Mbit/s 47x
500 39 Mbit/s 4,098 Mbit/s 105x

Benchmarked on Macbook M3 Pro.

License

Apache 2.0 - See LICENSE for details.

Libraries

fountain_codes