live_fec

fec背景和分类：

背景：主要在无线传输领域和音视频传输领域，前者是因为空气介质环境恶劣，不如光缆传输的抗性，所以会出现丢包，异常等情况，这个时候就需要有恢复动作。而后者是音视频传输对网络传输丢包很敏感，会出现卡顿等，体验不好，所以恢复也很重要。
无线传输的fec算法有：TURBO,LDPC,POLAR三种
音视频传输领域fec算法有：异或fec, RS(Reed-Solomon)，交织编码，Fountain,inband fec(带内fec)

各类别fec的原理和应用场景，例子–主要针对音视频；

1. 异或fec:异或算法实现相对简单，将M个数据包逐字节进行异或计算，计算得到的结果即为冗余包。这种算法只需要进行异常运算，复杂度低。但是抗丢包能力弱，例如 4+1算法，5个包里面最多只能丢1个包，否则就无法恢复。

2. RS fec: https://www.smiletoyou.cn/?p=319
   其实是利用多个等式方程求多个变量的方式，允许丢失多个包；

3. 交织编码：对简单异或来说，只能有一个包丢失，对复杂异或，可以进行多次异或生成N个冗余包来支持多个
   冗余。而异或方式还可以有更多，比如非均等异或等，称为交织编码：https://blog.csdn.net/CrystalShaw/article/details/83413772

4. inband fec带内fec，主要出现在Opus音频编码领域，简单的来说，带内就是指在编码时进行fec，而不是在传输时，如：|1| | -> |2|1| -> |3|2| -> |4|3| -> |5|4| -> |6|5| 若这次1没收到可以在下次收到。
   https://blog.jianchihu.net/webrtc-research-audio-inband-fec.html

5. fountain fec目前没了解；

各fec的源码使用和基本分析：

1. 东家用的 RSfec ，及相关开源库
2. webrtc用的ulpfec
3. 其他，如opus中用的fec，大致了解代码在哪就好；

RS fec:

假设每个包长为L个位bit, 有M=4个包，有N=2个冗余包，即允许丢失两个包，则；
将这M个包排成矩阵，则 （R矩阵为常数系数矩阵)
R00M00+R01M10+R02M20+R03M30 = N00
R10M00+R11M10+R12M20+R13M30 = N10
….N0LN1L

则当M0，M1包丢失时：
已知N00,N10，则可以求得M00，M10包；以此类推；

CRS 源码和使用

源码：https://github.com/catid/longhair
（CRS 开源库）

1 基本使用：Documentation is provided in the header file cauchy_256.h.
1） 初始化：

  #include "cauchy_256.h"

if (cauchy_init()) {
// Wrong static library
exit(1);
}

2） fec编码：

  int data_len = ...;
int k = 32; // Choose a number of pieces to split the data into. 原始数据包个数
int m = 12; // Choose a number of redundant pieces to generate. 冗余包个数
int bytes = 1000; // Chose a number of bytes per chunk, a multiple of 8 bytes. 包长度，为8bytes的倍数

assert(bytes % 8 == 0);
assert(data_len == k * bytes);

char *recovery_blocks = new char[m * bytes];
char *data_ptrs[32];

// Point data_ptrs to data here

// Encode the data using this library
if (cauchy_256_encode(k, m, data_ptrs, recovery_blocks, bytes)) { //传入原始包个数，冗余包个数，原始包，存放冗余包指针，包大小；
// Input was invalid
return false;
}

// For each recovery block,
for (int ii = 0; ii < m; ++ii) {
char *block = recovery_blocks + ii * bytes;
unsigned char row = k + ii; // Transmit this with block (just one byte)

// Transmit or store block bytes and row
}

delete []recovery_blocks;

3）fec解码恢复原始包:

// Use the same settings as the encoder
int k = 33;
int m = 12;
int bytes = 1000;

// Allocate block info array
// There should be exactly k blocks
Block *block_info = new Block[k];//分配空间

// Fill block_info here with data and rows from the encoder  //填充数据到block_info 
// Rows under k are original data, and the rest are redundant data //k个以下的原始数据，剩下的是冗余数据？

// Attempt decoding
if (cauchy_256_decode(k, m, block_info, bytes)) {
// Decoding should never fail - indicates input is invalid
assert(k + m <= 256);
assert(block_info != 0);
assert(bytes % 8 == 0);
return false;
}

// Now the block_info elements that used to have redundant data are
// corrected in-place and contain the original data.

3. 灵活的解码恢复使用方式：

   // Use the same settings as the encoder
   int k = 33;
   int m = 12;
   int bytes = 1000;
   
   // Allocate enough space for the original data
   char *block_data = new char[bytes * k];
   
   // Allocate block info array
   Block *block_info = new Block[k];
   
   int original_count = 0, recovery_count = 0;
   
   // This function will be called by onData() with original data after recovery
   static void processData(int row, char *data, int data_bytes) {
   // Handle original data here only
   }
   
   // Call this function with each block received, either original or recovery
   // Returns true on complete
   bool onData(unsigned char row, char *new_data) {
   int insertion_point;
   
   // If it is original data,
   if (row < k) {
   // Process the original data immediately - Do not wait for it all to arrive!
   processData(row, new_data, bytes); //处理收到的原始包；
   
   // Copy to the end of the original block data
   insertion_point = original_count++; //原始数据，则正向插入
   } else {
   // Copy to the front of the recovery block data
   insertion_point = k - ++recovery_count; //若是fec编码包，则倒着插入
   }
   
   // Copy data into place
   char *dest = block_data + insertion_point * bytes;
   memcpy(dest, new_data, bytes);//拷贝数据(原始或收到的fec编码包)
   
   // NOTE: It may be possible to avoid copying depending on if
   // you can hang onto the provided data buffer.
   
   // Fill in the block array entry //把数据赋值给block
   Block *block = block_info + insertion_point;
   block->data = dest;
   block->row = row;
   
   // If recovery is not possible yet, 凑齐了k个包(包括fec编码包，才能恢复）
   if (original_count + recovery_count < k) {
   return false;
   }
   
   // Attempt decoding
   if (cauchy_256_decode(k, m, block_info, bytes)) {
   // Decoding should never fail - indicates input is invalid
   assert(k + m <= 256);
   assert(block_info != 0);
   assert(bytes % 8 == 0);
   return false;
   }
   
   // For each recovered block,
   block = block_info + k - recovery_count;//把恢复出来的原始包处理下；
   for (int ii = 0; ii < recovery_count; ++ii, ++block) {
   // Process the recovered data
   processData(block->row, block->data, bytes);
   }
   
   return true;
   }

webrtc中的fec

https://www.cnblogs.com/ishen/p/15333271.html