Chinaunix首页 | 论坛 | 博客
  • 博客访问: 543186
  • 博文数量: 129
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1888
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-20 11:09
文章分类

全部博文(129)

文章存档

2016年(1)

2015年(5)

2014年(64)

2013年(59)

我的朋友

分类: C/C++

2013-09-14 19:32:39

一、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. 1、fec_t结构:
  2.    1: typedef struct {
  3.    2: unsigned long magic;
  4.    3: unsigned short k, n;            /*其中的k是数据块的个数,n是所有块的总数(包括数据块和校验块)*/          
  5.    4: gf* enc_matrix;           
  6.    5: } fec_t;

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

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

  1. 4、fec_encode()
  2.    1: void fec_encode(
  3.    2: const fec_t* code,                                  /*fec_t 结构的指针*/
  4.    3: const gf*restrict const*restrict const src,         /*原始数据指针*/
  5.    4: gf*restrict const*restrict const fecs,              /*fec_encode 生成的校验数据的指针*/
  6.    5: const unsigned*restrict const block_nums,           /*记录冗余数据块在整个数据(包含原始数据)中的索引数组*/
  7.    7: size_t num_block_nums,                              /*校验块索引数组的指针*/
  8.    8: size_t sz                                           /*每个数据块的大小*/
  9.    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,以此类推。


  1. 5、fec_decode()

  2.    1: void fec_decode(
  3.    2: const fec_t* code,                                  /*fec_t 结构的指针*/
  4.    3: const gf*restrict const*restrict const inpkts,      /*用来恢复丢失数据的数据数组,其内的指针必须按编码前的顺序升序存放,如果丢包则拿冗余块补入, 其中冗                                                             余块必须放在丢失数据块的位置。指针所指数组大小为k*/
  5.    4: 
  6.    5: gf*restrict const*restrict const outpkts,            /*存放找回的数据块,所指数组大小为丢失块数量*/
  7.    6:
  8.    7: const unsigned*restrict const index,                 /*传入的数据包的序号,数组大小为k,对应inpkts中每个数据块在全部数据块中的索引*/
  9.    8:
  10.    9: size_t sz
  11.    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 一段简单测试,对指定字符串进行编码解码:

 
  1. #include<stdlib.h>
  2. #include<stdio.h>
  3. #include "fec.h"

  4. #define ECC_K 4
  5. #define ECC_N 8
  6. #define ECC_C (ECC_N-ECC_K)

  7. #define BLK_SZ (24/ECC_K)

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

  18.     char *in_recovery[ECC_K];
  19.     char *out_recovery[ECC_K];
  20.     char buf_recovery[ECC_K*BLK_SZ+1]={0};
  21.     
  22.     for(i=0;i<ECC_K;i++)                           //填充原始数据
  23.         src[i]=data+i*BLK_SZ;
  24.     for(i=0;i<ECC_C;i++)
  25.     {
  26.          blocks[i]=ECC_K+i;                        //冗余数据块的索引
  27.          fecs[i]=cdata+i*BLK_SZ;
  28.     }
  29.     
  30.     code=fec_new(ECC_K,ECC_N);
  31.     printf("src:\t%s\n",*src);                      //输出原始数据信息
  32.     printf("cdata:\t%s\n",*cdata);
  33.     printf("fecs:\t%s\n",*fecs);
  34.     printf("ECC_C / BLK_SZ:\t%d / %d\n",ECC_C,BLK_SZ);

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

  52.    //假设数据快d1,d4失效,并以校验块c3,c4来恢复
  53.     index[0]=6;
  54.     index[1]=1;
  55.     index[2]=2;
  56.     index[3]=7;
  57.     in_recovery[0]=fecs[2];
  58.     in_recovery[1]=src[1];
  59.     in_recovery[2]=src[2];
  60.     in_recovery[3]=fecs[3];
  61.     for(i=0;i<ECC_K;i++)
  62.         out_recovery[i]=buf_recovery+i*BLK_SZ;
  63.     fec_decode(code,(gf**)in_recovery,(gf**)out_recovery,index,BLK_SZ);
  64.     buf_recovery[ECC_K*BLK_SZ]='\0';
  65.     printf("Recovery:\t%s\n",buf_recovery);
  66.     return 0;
  67. }

运行结果如下:
  

注意:
  如果在linux下编译时出现fec.h中的fec_encode()和fec_decode()无法编译通过,则fec.h文件中的fec_encode()和fec_decode()函数定义改为如下形式:
    
  1. void fec_encode(const fec_t* code, gf**src, gf**fecs, const unsigned* block_nums, size_t num_block_nums, size_t sz);

  1. void fec_decode(const fec_t* code,gf**inpkts, gf**outpkts, const unsigned*index, size_t sz);
  相应的fec.c文件也要改!!!


 
 




阅读(2572) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~