zfec 是Tahoe（一个基于云的文件系统）中纠删码的一个模块，其中的fec 模块是核心部分，实现了基于范德蒙矩阵的系统纠删码，对外提供以下接口：
- fec_t ：这是一个结构，通过fec_new() 返回可以得到，不用自己初始化。fec->k 是数据块的数目，fec->n 是所有块总数（数据块+校验块）
- fec_new()：初始化，生成fec_t 结构，并给定了k，m（需要重建数据块数，总数据块数）
- fec_free()：释放初始化的空间
- fec_encode()：编码 （具体参数如下）
- fec_decode()：解码 （具体参数如下）
fec_t
1: typedef struct {
2: unsigned long magic;
3: unsigned short k, n; /* parameters of the code */
4: gf* enc_matrix;
5: } fec_t;
fec_new()
1: fec_t* fec_new(
2: unsigned short k, /*原数据块个数，对应编码理论中k */
3: unsigned short m /*编码后所有数据块个数，对应编码理论中n */
4: )
fec_free()
1: void fec_free(
2: fec_t* p
3: )
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 生成的校验数据的指针*/
5: const unsigned*restrict const block_nums,
6: /*记录冗余数据块在整个数据（包含原始数据）中的索引数组*/
7: size_t num_block_nums, /*冗余数组的大小*/
8: size_t sz /*每个数据块的大小*/
9: )
- src[0] 到src[ECC_K-1] 是指向第0 个到第ECC_K-1 个数据块的指针；（分别指向D1-D5）
- fecs[0] 到fecs[ECC_C-1] 是指向第0 个到第ECC_C-1 个校验块的指针；（需要预先分配好校验块的空间，分别指向C1-C3）
- blocks_nums 是校验块索引数组的指针，blocks_nums 指向的空间也应该提前分配好，是一个ECC_C 大小的空间，保存从ECC_K,…,ECC_N-1。（对应下图，索引数组保存5、6、7 ）
- num_block_nums 是上面blocks_nums 指向空间的大小，也就是校验块个数：ECC_C = ECC_N – ECC_K。
fec_decode()
1: void fec_decode(
2: const fec_t* code, /*fec_t 结构的指针*/
3: const gf*restrict const*restrict const inpkts,
4: /*用来恢复丢失数据的数据数组，其内的指针必须按编码前的顺序升序存放，如果丢包则拿冗余块补入，
5: 其中冗余块必须放在丢失数据块的位置。指针所指数组大小为k*/
6: gf*restrict const*restrict const outpkts,
7: /*存放找回的数据块，所指数组大小为丢失块数量*/
8: const unsigned*restrict const index,
9: /*传入的数据包的序号，数组大小为k，对应inpkts中每个数据块在全部数据块中的索引*/
10: size_t sz
11: )
- inpkts 是恢复数据块和校验块指针，需要注意的是数据块应该按照其原来的位置放置，缺少数据块的部分用校验块填充，不可以按照数据块校验块顺序放置，否则会解码错误
- outpkts 是恢复出来的数据块的指针，也要预先分配空间
- index 是用于恢复的数据块与校验块对应在inpkts 里面的索引。
如下图D1/D4/C2 块发生损坏，那么重建的数据块由D2/D3/D5/C1/C3。那么inpkts 指针应该有这样关系：
inpkts->C1（校验块的位置只需和后面index 索引对齐即可）
inpkts+1->D2 （数据块应该保持其原来位置）
inpkts+2->D3（数据块应该保持其原来位置）
inpkts+3->C3（校验块的位置只需和后面index 索引对齐即可）
inpkts+4->D5（数据块应该保持其原来位置）
那么对应index 指向的数组应该为[5,1,2,7,4] ，对应的也就是C1/D2/D3/C3/D5 在初始位置的索引。
写自己程序的需要将fec.c 编译为fec.o ，再和自己的测试程序一起编译链接生成执行文件，fec 中使用了C99 的语法，需要gcc test.c libfec.o –o out.a –std=c99 生成执行程序out.a 。
下面是encode 和decode 一段简单测试，对指定字符串进行编码解码：
1: #include <stdlib.h>
2: #include <stdio.h>
3: #include <sys/fcntl.h>
4: #include <sys/stat.h>
5: #include <unistd.h>
6: #include "fec.h"
7:
8: #define ECC_K 4
9: #define ECC_N 8
10: #define ECC_C (ECC_N - ECC_K)
11:
12: #define BLK_SZ (48/ECC_K)
13:
14: int main(int argv, char *argc[]){
15: fec_t *code;
16: char data[] = "0123456789qwertyuiopasdfghjklzxcvbnm-=[];',./`!%";
17: char cdata[49] = {0};
18: char *src[ECC_K];
19: unsigned blocks[ECC_C];
20: char *fecs[ECC_C];
21: int i;
22: unsigned index[ECC_K]={4,5,6,7};
23: char *in_recovery[ECC_K];
24: char *out_recovery[ECC_K];
25: char buf_recovery[ECC_K*BLK_SZ+1];
26:
27: for(i = 0; i < ECC_K; i++)
28: src[i] = data + i*BLK_SZ;
29: for(i = 0; i < ECC_C; i++){
30: blocks[i] = ECC_K + i;
31: fecs[i] = cdata + i*BLK_SZ;
32: }
33:
34: code = fec_new(ECC_K, ECC_N);
35: printf("src:\t%s\n",*src);
36: printf("cdata:\t%s\n",*cdata);
37: printf("fecs:\t%s\n",*fecs);
38: printf("blocks:\t%c\n",*blocks);
39: printf("ECC_C/BLK_SZ:\t%d / %d\n",ECC_C,BLK_SZ);
40: fec_encode(code, src, fecs, blocks, ECC_C, BLK_SZ);
41: printf("========================\n");
42: for(i = 0 ; i < ECC_K ; i++){
43: in_recovery[i] = fecs[i];
44: out_recovery[i] = buf_recovery + i*BLK_SZ;
45: }
46: fec_decode(code, in_recovery, out_recovery, index, BLK_SZ);
47: buf_recovery[ECC_K*BLK_SZ] = '\0';
48: printf("Recovery:\t%s\n",buf_recovery);
49:
50: index[0] = 6;
51: index[1] = 1;
52: index[2] = 2;
53: index[3] = 7;
54: in_recovery[0] = data + 1*BLK_SZ;
55: in_recovery[1] = fecs[2];
56: in_recovery[2] = fecs[3];
57: in_recovery[3] = data + 2*BLK_SZ;
58: for(i = 0 ; i < ECC_K ; i++){
59: out_recovery[i] = buf_recovery + i*BLK_SZ;
60: }
61: fec_decode(code, in_recovery, out_recovery, index, BLK_SZ);
62: buf_recovery[ECC_K*BLK_SZ] = '\0';
63: printf("Recovery:\t%s\n",buf_recovery);
64: }
下面是一个[4,8] 编码速度的测试，选择合适大小的缓存（数据块大小也随之改变）很重要：
测试程序：
1: #include <stdlib.h>
2: #include <stdio.h>
3: #include <sys/fcntl.h>
4: #include <sys/stat.h>
5: #include <unistd.h>
6: #include <sys/time.h>
7: #include "fec.h"
8:
9: #define DATASIZE 1024*1024*512
10: #define DATASIZEM (DATASIZE/(1024*1024))
11: #define BUFSIZE 1024*4
12: #define TIMES (DATASIZE/BUFSIZE)
13:
14: #define ECC_K 4
15: #define ECC_N 8
16: #define ECC_C (ECC_N - ECC_K)
17:
18: #define BLK_SZ (BUFSIZE/ECC_K)
19:
20: double dt(struct timeval end , struct timeval start){
21: double tm;
22: tm = ((end.tv_sec-start.tv_sec)*1000.0)+(end.tv_usec-start.tv_usec)/1000.0;
23: return tm;
24: }
25:
26:
27: int main(int argv, char *argc[]){
28: fec_t *code;
29: char *inbuf;
30: char *outbuf;
31: char *src[ECC_K];
32: char *fecs[ECC_C];
33: unsigned blocks[ECC_K];
34: int i;
35: int j=0;
36: double delta;
37: struct timeval start,end;
38:
39: code = fec_new(ECC_K, ECC_N);
40:
41: printf("===== START TO COUNT =====\n");
42: printf("k/n:\t%d\t%d\n" , ECC_K , ECC_N);
43: printf("Data/buf = %d MB\t%d KB\n" , DATASIZEM , BUFSIZE/1024);
44: gettimeofday(&start , NULL);
45: while( j < TIMES ){
46: inbuf = (char *)malloc(BUFSIZE*sizeof(char));
47: outbuf = (char *)malloc(BUFSIZE*sizeof(char));
48: for(i = 0; i < ECC_K; i++){
49: src[i] = inbuf + i*BLK_SZ;
50: blocks[i] = ECC_K + i;
51: fecs[i] = outbuf + i*BLK_SZ;
52: }
53: fec_encode(code , src , fecs , blocks , ECC_C , BLK_SZ);
54: j++;
55: free(inbuf);
56: free(outbuf);
57: }
58: gettimeofday(&end,NULL);
59: delta=dt(end,start)/1000;
60: printf("Time:\t%lf s\t\tSpeed:\t%3.1lf MB/S\t\n",delta,DATASIZEM/delta);
程序中在对求余使用了改进的modnn () 方法，在注释中是这样解释的：
/*
* modnn(x) computes x % GF_SIZE, where GF_SIZE is 2**GF_BITS – 1,
* without a slow divide.
*/
该方法没有使用常规的除法，从而加速了求余，但估计现代处理器中对求余上进行了硬件上的优化，所有在下面的测试中并没有得到更快的速度，normal mod 使用% 进行求余，fast mod 使用modnn() 方法求余。将这个方法进行了修改再次进行了上面编码速度的测试，发现速度没有改变，可见这里的求余并不是计算的瓶颈。
-
0: normal mod
Time: 2.242347 s
1: fast mod
Time: 5.798104 s
2: normal function mod
Time: 3.876389 s
3: fast function mod
Time: 6.808311 s
1: #include <stdlib.h>
2: #include <stdio.h>
3: #include <sys/time.h>
4:
5: double dt(struct timeval end , struct timeval start){
6: double tm;
7: tm = ((end.tv_sec-start.tv_sec)*1000.0)+(end.tv_usec-start.tv_usec)/1000.0;
8: return tm;
9: }
10:
11: int modnn(int x) {
12: while (x >= 255) {
13: x -= 255;
14: x = (x >> 8) + (x & 255);
15: }
16: return x;
17: }
18:
19: int moddd(int x){
20: x = x % 255;
21: return x;
22: }
23:
24: int main(void){
25: int i,j;
26: int x=65535;
27: double delta;
28: struct timeval start,end;
29:
30: printf(" 0:\t normal mod \n");
31: gettimeofday(&start , NULL);
32: for(i = 0 ; i < 1000 ; i++)
33: for(x = 65535 ; x < 655350 ; x++)
34: j = x % 255;
35: gettimeofday(&end,NULL);
36: delta=dt(end,start)/1000;
37: printf("Time:\t%lf s\t\t\n",delta);
38:
39: printf(" 1:\t fast mod \n");
40: gettimeofday(&start , NULL);
41: for(i = 0 ; i < 1000 ; i++)
42: for(x = 65535 ; x < 655350 ; x++){
43: j = x;
44: while (j >= 255) {
45: j -= 255;
46: j = (j >> 8) + (j & 255);
47: }
48: }
49: gettimeofday(&end,NULL);
50: delta=dt(end,start)/1000;
51: printf("Time:\t%lf s\t\t\n",delta);
52:
53: gettimeofday(&start , NULL);
54: printf(" 2:\t normal function mod \n");
55: for(i = 0 ; i < 1000 ; i++)
56: for(x = 65535 ; x < 655350 ; x++)
57: j = moddd(x);
58: gettimeofday(&end,NULL);
59: delta=dt(end,start)/1000;
60: printf("Time:\t%lf s\t\t\n",delta);
61:
62: gettimeofday(&start , NULL);
63: printf(" 3:\t fast function mod \n");
64: for(i = 0 ; i < 1000 ; i++)
65: for(x = 65535 ; x < 655350 ; x++)
66: j = modnn(x);
67: gettimeofday(&end,NULL);
68: delta=dt(end,start)/1000;
69: printf("Time:\t%lf s\t\t\n",delta);
70: return(1);
71: }
