Code Poetry
and Text Adventures

by catid posted (>30 days ago) 12:29am Mon. May 15th 2017 PDT
I just released a few new software libraries on github:

https://github.com/catid/fecal

FEC-AL is a simple, portable, fast library for Forward Error Correction. FEC-AL is a block codec derived from the Siamese streaming FEC library. From a block of input data it generates recovery symbols that can be used to recover lost originals.

It requires that data pieces are all a fixed size.
It can take as input an unlimited number of input blocks.
It can generate an unlimited stream of recovery symbols used for decoding.
The main limitation of the software is that it gets slower as O(N^^2) in the number of inputs or outputs. In trade, the encoder overhead is unusually low, and the decoder is extremely efficient when recovering from a small number of losses. It may be the best choice based on practical evaluation.

It supports an unlimited number of inputs and outputs, similar to a Fountain Code, but it is designed as a Convolutional Code. This means that it does not perform well with a large number of losses. It is faster than existing error correction code (ECC) software when the loss count is expected to be small.


https://github.com/catid/siamese

Siamese is a simple, portable, fast library for Forward Error Correction. From a stream of input data it generates redundant data that can be used to recover the lost originals without using acknowledgements.

Siamese is a streaming erasure code designed for low to medium rate streams under 2000 packets per RTT (~3MB/s on the Internet), and modest loss rates like 20% or less. It works on mobile phones and mac/linux/windows computers.

It might be the first software library to enable this. Please let me know if you find software that also does this so I can take a look at the code and incorporate any improvements into this library.

For faster file transfer it is better to not use FEC and instead use retransmission for the bulk of lost data. For higher loss rates it is better to use a stronger FEC library like Wirehair. But for more normal situations this is a very useful tool.

Target application: Writing a rUDP Protocol

If you're writing your own reliable UDP protocol, this can save you a bunch of time for the trickier parts of the code to write.
It can also generate selective acknowledgements and retransmitted data to be useful as the core engine of a Hybrid ARQ transport protocol, and it exposes its custom memory allocator to help implement outgoing data queues.


https://github.com/catid/gf256

Fast, Portable 8-bit Galois Field Math in C

This library provides efficient implementations of bulk GF(2^^8) math operations over memory buffers, which are common operations in application-layer Forward Error Correction. This library is the basis for all of my fast FEC software.

Addition is done over the base field in GF(2) meaning that addition is XOR between memory buffers.

Multiplication is performed using table lookups via vector instructions. This is somewhat slower than XOR, but fast enough to not become a major bottleneck when used sparingly.