ZFEC源码解析及实例解析

一、ZFEC源码解析
  zfec是一种前向纠删码，用于给原始数据增加冗余信息，以提高数据的安全性。zfec为我们同时提供了C和Python接口。

  zfec源代码下载地址：

    zfec 是Tahoe（一个基于云的文件系统）中纠删码的一个模块，其中的fec 模块是核心部分，实现了基于范德蒙矩阵的系统纠删码，对外提供以下接口：
    fec_t ：这是一个结构，通过fec_new() 返回可以得到，不用自己初始化。fec->k 是数据块的数目，fec->n 是所有块总数（数据块+校验块）
    fec_new()：初始化，生成fec_t 结构，并给定了k，m
    fec_free()：释放初始化的空间
    fec_encode()：编码 （具体参数如下）
    fec_decode()：解码 （具体参数如下）

1、fec_t结构：
   1: typedef struct {
   2: unsigned long magic;
   3: unsigned short k, n;            /*其中的k是数据块的个数，n是所有块的总数（包括数据块和校验块）*/
   4: gf* enc_matrix;
   5: } fec_t;

2、fec_new()
   1: fec_t* fec_new(
   2: unsigned short k,             /*原数据块个数，对应编码理论中k */
   3: unsigned short m              /*编码后所有数据块个数，对应编码理论中n */
   4: )

3、fec_free()
   1: void fec_free(
   2: fec_t* p
   3: )

4、fec_encode()
   1: void fec_encode(
   2: const fec_t* code,                                  /*fec_t 结构的指针*/
   3: const gf*restrict const*restrict const src,         /*原始数据指针*/
   4: gf*restrict const*restrict const fecs,              /*fec_encode 生成的校验数据的指针*/
   5: const unsigned*restrict const block_nums,           /*记录冗余数据块在整个数据（包含原始数据）中的索引数组*/
   7: size_t num_block_nums,                              /*校验块索引数组的指针*/
   8: size_t sz                                           /*每个数据块的大小*/
   9: )

 假设k=4,n=8.即数据块数为4，校验块数为4；
src ：  原始数据指针的一个数组，指针所指数组大小为k。src[0] 到src[ECC_K-1] 是指向第0 个到第ECC_K-1 个数据块的指针；（分别指向D1-D4);
fecs ：冗余数据的数组指针，不包含原始数据，所指数组大小为m-k。fecs[0] 到fecs[ECC_C-1] 是指向第0 个到第ECC_C-1 个校验块的指针；（需要预先分配好校验块的空间，分别指向C1-C4）;
blocks_nums： 用来记录冗余数据块在整个数据（包含原始数据）中的索引的数组;
num_block_nums： 冗余数组大小;
sz： 每个数据块的大小。

举例，如果我们以（4,8）的方案来生成纠删码，则原始数据的索引是0-3，冗余数据的索引是4-7,那么block_nums数组的大小为8-4=4，即num_block_nums=4,其中block_nums[0]=4，block_num[1]=5,以此类推。

5、fec_decode()

   1: void fec_decode(
   2: const fec_t* code,                                  /*fec_t 结构的指针*/
   3: const gf*restrict const*restrict const inpkts,      /*用来恢复丢失数据的数据数组，其内的指针必须按编码前的顺序升序存放，如果丢包则拿冗余块补入，  其中冗                                                             余块必须放在丢失数据块的位置。指针所指数组大小为k*/
   4:
   5: gf*restrict const*restrict const outpkts,            /*存放找回的数据块，所指数组大小为丢失块数量*/
   6:
   7: const unsigned*restrict const index,                 /*传入的数据包的序号，数组大小为k，对应inpkts中每个数据块在全部数据块中的索引*/
   8:
   9: size_t sz
   10: )

inpkts :   用来恢复丢失数据的数据数组，其内的指针必须按编码前的顺序升序存放，如果丢包则拿  冗余块补入，其中冗余块必须放在丢失数据块的位置。指针所指数组大小为k。
outpkts: 存放找回的数据块，所指数组大小为丢失块数量。
index :   是用于恢复的数据块与校验块对应在inpkts 里面的索引。

举例,还是采用（4，8）编码,其中索引为2的原始数据块丢失，那么我们将随意寻找一个冗余数据块m（4<=m<=7),那么，index[] = {0,1,m,2}；同样，在inpkts中，数据块m的指针应放在第3位。

若d1,d4 块发生损坏，并且以校验快c3，c4来恢复数据。那么inpkts 指针应该有这样关系：
inpkts->c3    （校验块的位置只需和后面index 索引对齐即可）
inpkts+1->d2（数据块应该保持其原来位置）
inpkts+2->d3（数据块应该保持其原来位置）
inpkts+3->c4（校验块的位置只需和后面index 索引对齐即可）

那么对应index 指向的数组应该为[6,1,2,7] ，对应的也就是c3/d2/d3/c4 在初始位置的索引。


二、ZEFC实例解析

写自己程序的需要现将fec.h和fec.c加入到自己编写的代码目录下并编译成fec.o文件 ，再和自己的测试程序一起编译链接生成执行文件，fec 中使用了C99 的语法，需要gcc -c fec.c -std=c99编译成fec.o.然后将自己编写的testzfec.c通过gcc -c testzfec.c 得到testzfec.o 。然后gcc -o testzfec  testzfec.o fec.o  得到可以执行文件testzfec。

下面是encode 和decode 一段简单测试，对指定字符串进行编码解码：

 

#include<stdlib.h>
#include<stdio.h>
#include "fec.h"

#define ECC_K  4
#define ECC_N  8
#define ECC_C (ECC_N-ECC_K)

#define  BLK_SZ (24/ECC_K)

int main(int argc,char **argv)
{
    int i;
    fec_t *code;
    char data[]="abcdefghijklmnopqrstuvwx";      //存放原始数据信息
    char cdata[26]={0};                          //存放校验数据信息
    char *src[ECC_K];
    char *fecs[ECC_C];
    unsigned index[ECC_K];
    unsigned blocks[ECC_C];                      //记录冗余数据块在整个数据中的索引的数组

    char *in_recovery[ECC_K];
    char *out_recovery[ECC_K];
    char buf_recovery[ECC_K*BLK_SZ+1]={0};

    for(i=0;i<ECC_K;i++)                           //填充原始数据
        src[i]=data+i*BLK_SZ;
    for(i=0;i<ECC_C;i++)
    {
         blocks[i]=ECC_K+i;                        //冗余数据块的索引
         fecs[i]=cdata+i*BLK_SZ;
    }

    code=fec_new(ECC_K,ECC_N);
    printf("src:\t%s\n",*src);                      //输出原始数据信息
    printf("cdata:\t%s\n",*cdata);
    printf("fecs:\t%s\n",*fecs);
    printf("ECC_C / BLK_SZ:\t%d / %d\n",ECC_C,BLK_SZ);


    //由原始数据得到校验数据
    fec_encode(code,(gf**)src,(gf**)fecs,blocks,ECC_C,BLK_SZ);
    printf("fecs:\t%s\n",*fecs);
    printf("================\n");
    //在d1,d2,d3,d4全失效的情况下进行恢复
    /*
    for(i=0;i<ECC_K;i++)
    {
        index[i]=ECC_K+i;
        in_recovery[i]=fecs[i];
        out_recovery[i]=buf_recovery+i*BLK_SZ; //将恢复出来的数据放在out_recovery中
    }
    fec_decode(code,(const gf**)in_recovery,(const gf**)out_recovery,index,BLK_SZ); //将失效的数据解码出来
    buf_recovery[ECC_K*BLK_SZ]='\0';
    printf("Recovery:\t%s\n",buf_recovery);
    */

   //假设数据快d1,d4失效，并以校验块c3,c4来恢复
    index[0]=6;
    index[1]=1;
    index[2]=2;
    index[3]=7;
    in_recovery[0]=fecs[2];
    in_recovery[1]=src[1];
    in_recovery[2]=src[2];
    in_recovery[3]=fecs[3];
    for(i=0;i<ECC_K;i++)
        out_recovery[i]=buf_recovery+i*BLK_SZ;
    fec_decode(code,(gf**)in_recovery,(gf**)out_recovery,index,BLK_SZ);
    buf_recovery[ECC_K*BLK_SZ]='\0';
    printf("Recovery:\t%s\n",buf_recovery);
    return 0;
}

运行结果如下：
  

注意:
  如果在linux下编译时出现fec.h中的fec_encode()和fec_decode()无法编译通过,则fec.h文件中的fec_encode()和fec_decode()函数定义改为如下形式：
    

void fec_encode(const fec_t* code, gf**src, gf**fecs, const unsigned* block_nums, size_t num_block_nums, size_t sz);

void fec_decode(const fec_t* code,gf**inpkts, gf**outpkts, const unsigned*index, size_t sz);

  相应的fec.c文件也要改！！！