Thanks for the pointer, any other similar algorithms?

O(n) sounds impressive, although I heard such claims on RQ too...

RQ complexity is O(n^3), but on the internal matrix, not on the input. It all depends on the blocksize you choose.

The numbers are impressive, too. Encoding 40Mbytes in 0usec? Will have to check the theory behind that.

You could look at ldpc triangle/staircase. They're fast even in a fairly naive implementation but have fairly high overhead unless most of your input is the systematic part of the codeword.