RS码FEC机制的实现方法（基于Luigi Rizzo的代码）

Luigi Rizzo大神在1997年写了一个基于范德蒙矩阵的FEC的纠错代码，这套代码本身开源并且在多个知名项目被使用。我基于这套fec代码，也做了一份RS纠错的例子。

Rizzo, L., "Effective Erasure Codes for Reliable Computer Communication Protocols",
 ACM SIGCOMM Computer Communication Review, Vol.27, No.2, pp.24-36,April 1997.
Rizzo, L., "Reed-Solomon FEC codec (C language)",original codec: http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz, 
improved codec: http://openfec.org/,July 1998.

Luigi Rizzo的代码仅包含fec.h和fec.c两个文件。

写一个包装方法rs.c和rs.h，代码如下：

rs.h的代码：

#ifndef LIB_RS_H_
#define LIB_RS_H_

#include "fec.h"

// input:
// code, generated by fec_new() function from fec.h
// data[0....k-1 ], points to original data
// size, data length
//
// output:
// data[k....n-1], points to generated redundant data
//
// info:
// the function will always succeed,except malloc fail.if malloc fail,it will call exit()
void rs_encode(void *code,char *data[],int size); 


// input:
// data[0.....n-1] points to original data and redundate data,in right order
// if data[i] is missing ,set poniter data[i] to 0 (point it to null)
//
// outout:
// data[0.....k-1] will point to the recovered original data.
//
// info:
// return zero on success
// if the number of no-zero pointers is less than k,the function will fail and return non-zero
//
// advanced info:
// 1. rs_decode wont malloc memory for those zero pointers in data[0.....k-1]. instead it will re-use the memory of other non-zero pointers (and let data[0.....k-1] point to those memory).
// 2. if the input data[0.....n-1] contains x non-zero pointers,after called rs_decode,there will still be exactly x non-zero poninters in data[0.....n-1],just the order may change.
int rs_decode(void *code,char *data[],int size);


void rs_encode2(int k,int n,char *data[],int size);

int rs_decode2(int k,int n,char *data[],int size);





#endif /* LIB_RS_H_ */

rs.c的代码：

#include "rs.h"
#include "stdlib.h"
#include "string.h"
#include "stdio.h"

void rs_encode(void *code,char *data[],int size)
{
	int k=get_k(code);
	int n=get_n(code);
	printf("encode k:%d n:%d\n",k,n );
	for(int i=k;i<n;i++)//generate redundancy data, k is real, n is all, n-k is redundancy.
	{
		fec_encode(code, (void **)data, data[i],i, size);
	}

	return ;
}

int rs_decode(void *code,char *data[],int size)
{
	int k=get_k(code);
	int n=get_n(code);
	printf("decode k:%d n:%d\n",k,n );
	int index[n];
	int count=0;
	for(int i=0;i<n;i++)
	{
		if(data[i]!=0)
		{
			index[count++]=i;
		}
	}
	if(count<k)
		return -1;
	for(int i=0;i<n;i++)
	{
		if(i<count)
			data[i]=data[index[i]];
		else
			data[i]=0;
	}
	return fec_decode(code,(void**)data,index,size);
}

static void * (*table)[256]=0;
void* get_code(int k,int n)
{
	if (table==0)
	{
		table=(void* (*)[256]) malloc(sizeof(void*)*256*256);
		if(!table)
		{
		    return table;
		}
		memset(table,0,sizeof(void*)*256*256);
	}
	if(table[k][n]==0)
	{
		table[k][n]=fec_new(k,n);
	}
	return table[k][n];
}
void rs_encode2(int k,int n,char *data[],int size)
{
	void* code=get_code(k,n);
	rs_encode(code,data,size);
}

int rs_decode2(int k,int n,char *data[],int size)
{
	void* code=get_code(k,n);
	return rs_decode(code,data,size);
}

main函数的例子代码：

#include<stdio.h>
#include "rs.h"

int main(int argc, char *argv[])
{
	int i,j,k;
	char arr[6][100]=
	{
		"aaa","bbb","ccc"
		,"ddd","eee","fff"
	};
	char *data[6];
	for(i=0;i<6;i++)
	{
		data[i]=arr[i];
	}
	for(i=0;i<6;i++)
	{
		printf("before rs encode: <%s>\n",data[i]);
	}
//6 strings protect 5 strings.
	rs_encode2(5,6,data,3);
	for(i=0;i<6;i++)
	{
		printf("after rs encode: <%s>\n",data[i]);
	}

//simulate lost data.
	data[0]=0; // 0 is NULL.
	//data[1]=0;
	//data[2]=0;

	int ret=rs_decode2(5,6,data,3);
	for(i=0;i<6;i++)
	{
		printf("after rs decode: <%s>\n",data[i]);
	}
	return 0;
}

在main函数生成了6个字符串，通过rs_encode2将前5个字符串保护起来，第6个字符串用来存冗余数据。

data[0]=0模拟了丢失数据，然后通过rs_decode2来恢复数据。

输出如下：

before rs encode: <aaa>
before rs encode: <bbb>
before rs encode: <ccc>
before rs encode: <ddd>
before rs encode: <eee>
before rs encode: <fff>
encode k:5 n:6
after rs encode: <aaa>
after rs encode: <bbb>
after rs encode: <ccc>
after rs encode: <ddd>
after rs encode: <eee>
after rs encode: <���>
decode k:5 n:6
after rs decode: <aaa>
after rs decode: <bbb>
after rs decode: <ccc>
after rs decode: <ddd>
after rs decode: <eee>
after rs decode: <(null)>

可见aaa,bbb,ccc,ddd,eee得到了恢复，在《我的下载资源》中有完整代码